G22.2110 Programming LanguagesModels of ComputationGenealogyCommon IdeasPredictable performance vs. ease of writingLanguage as a tool for thought (Iverson)The programming environment may be larger than the languageLanguage DefinitionSyntax and SemanticsGrammarsThe Chomsky hierarchyLexical IssuesBNF: standard notation for context-free grammarsParse treesAmbiguityThe dangling else problemG22.2110G22.2110 Programming Languages Programming LanguagesThe main themes of programming language design and use:◦Model of computation◦Expressivenesstypes and their operationscontrol structuresabstraction mechanismstools for programming in the large◦Ease of use: Writeability / Readability / MaintainabilityModels of ComputationModels of ComputationImperative: programs have mutable storage (state) modified by assignments◦by far the most common and familiarFunctional (applicative): programs are pure functions◦much use in AI, formal semantics, language researchDeclarative: programs are unordered sets of assertions and rules◦Prolog, data base applicationsGenealogyGenealogyFORTRAN (1957) => Fortran90, HPFCOBOL (1956) => COBOL2000◦still a large chunk of installed softwareAlgol60 => Algol68 => Pascal => Ada => … Ada2012Algol60 => BCPL => CSimula => Smalltalk, C++LISP => Scheme, ML, Haskell◦with plenty of cross-influences: Java inherits from C++, Smalltalk, LISP, Ada, etc.Common IdeasCommon IdeasModern imperative languages (Ada, C++, Java) have similar characteristics:◦large number of features (grammar with several hundred productions, 500 page reference manuals…)◦a rich type system◦procedural mechanisms◦object-oriented facilities◦abstraction mechanisms, with information hiding◦several storage-allocation mechanisms◦facilities for concurrent programming (not C++)◦facilities for generic programming (not older versions of Java)Predictable performance vs. ease of writingPredictable performance vs. ease of writingLow-level languages mirror the physical machine:◦Assembly, C, FortranHigh-level languages model an abstract machine with useful capabilities:◦ML, Setl, Prolog, PythonWide-spectrum languages try to do both, more or less well:◦Ada, C++, JavaHigh-level languages are often interpreted, have garbage collection, are dynamically typed, and cannot be used for real-time programming. Cost of operations is not directly visible.◦Java is a hybridMajor distinction: manual / automatic storage managementLanguage as a tool for Language as a tool for thought (Iverson)thought (Iverson)Drawing a histogram in APL:◦ “* “ [ V ° V]◦Is it natural ? ( only if you happen to think that way)◦Role of language as a communication vehicle among programmers is more important than ease of writing◦APL is an extreme case (write-only language)◦All languages have the same expressive power; arguments of the form “you can’t do this in X” are meaningless.◦But.. Idioms in language A may be useful inspiration when writing in language B.The programming environment may be larger The programming environment may be larger than the languagethan the languageThe predefined libraries are indispensable to the proper use of the language.The libraries are defined in the language itself, but they have to be internalized by a good programmer. the C++ standard template libraryThe Java Swing classesThe Ada I/O packagesThere is a law of conservation of junk: whether it goes into the language or in the library, the total amount of miscellaneous information is roughly the same from language to language.Language DefinitionLanguage DefinitionDifferent users have different needs:◦programmerstutorials, reference manuals, programming guides (idioms)◦implementorsprecise operational semantics◦verifiersrigorous axiomatic or natural semantics◦language designers and language lawyersall of the aboveDifferent levels of detail and precision◦But none of them can be sloppy!Syntax and SemanticsSyntax and SemanticsSyntax refers to external representationSemantics denotes meaningDistinction is convenient but arbitrary: can describe fully a programming language by syntactic means (Algol68 and W-grammars), but resulting grammar is hard to use.In practice, describe context-free aspects with a grammar, the rest with prose or a different formal notation (equations, pre/post conditions, assertions).GrammarsGrammarsA set of non-terminal symbolsA distinguished non-terminal: the root symbolA set of terminal symbolsA series of rewrite rules (productions) of the form: ABC.. ::= XYZ..where A, B, C, D, X, Y, Z terminals and non terminals.The language is the set of sentences containing only terminalsymbols, that can be generated by applying the rewriting rulesstarting from the root symbolThe Chomsky hierarchyThe Chomsky hierarchyRegular grammars:◦all productions have the form: N ::= TN◦(one non-terminal on each side)Context-free grammars:◦all productions have the form: N ::= XYZ◦(one non-terminal on the left-hand side)Context-sensitive languages:◦The number of symbols on the left is no greater than on the right◦(no production shrinks the size of the sentential form)Type-0 languages◦no restrictionsLexical IssuesLexical IssuesLexical structure of programming languages is simple.Described mostly by regular grammarTerminals are characters:◦need to specify character set: ASCII, Latin-1, ISO646, Unicode…◦need to specify if case is significant◦need to specify external source representation for portabilityIdentifiers:◦Id => letter ◦Id => letter IdRegular grammars can’t count: previous rule does not specify size limitEarly FORTRAN oddities: DO 10 J = 1, 10 vs. DO 10 J = 1.10BNF: standard notation for BNF: standard notation for context-free grammarscontext-free grammarsA series of conventional abbreviations:◦alternation: symb ::= Letter | Digit◦option: if_stat ::= IF condition THEN statement [else_part] END IF ◦repetition: else_part ::= {elseif_part} [ELSE statement] elsif_part ::= ELSIF condition THEN statement◦also noted with Kleene star: id ::= Letter symb*◦Does not add to expressive power of grammar, could be done with recursion (tastes on readability differ)◦need convention for metasymbols: what if ‘|’ is in