Programming Languages: Design, Specification, and ImplementationAdministrativeThe final examThings expected to be understood for the finalLanguages in GeneralLanguage SyntaxThe first high-level programming languageImperative languagesImperative languages, continuedApplicative languages (Lisp, Scheme, ML)Simulating objects with closuresHomework: ML Type Inference ProblemTypesObject oriented programmingMechanisms for Object-Oriented programmingGenericsConcurrencyConcurrency, continuedOther programming paradigmsOne word, two different meanings – the word “serialization”Programming Languages:Design, Specification, and ImplementationG22.2210-001Rob StromDecember 12, 2006AdministrativeFill out evaluations; return them to Room 405.All written assignments due by noon, today, December 12, so that the TA’s can grade them.•Anyone who cannot do this MUST see me personally! I will be here after class today.The final will be held on Thursday, December 21st, in this room.Open book – any kinds of written or printed notes or books permitted. No computers.The final examNot deepNot like programming projectsAnyone who understands all the classes and could do homework problems should get full marksShort answers•What does this program output?•Where is the bug in this program? Fix it.•What is the most general type of this ML function?Short discussions – sentence/paragraph•Why is this feature useful? Why is it potentially dangerous?•How would you implement this feature?Things expected to be understood for the finalLanguages in GeneralWhat benefits do high level languages achieve?What are the criteria for “good” decomposition into modules?What is the difference between an implementation and a specification?What is performance transparency? How is it good and how is it bad?What are name spaces? What are defining and applied occurrences of names? Illustrate in various languages. Be able to say for a given language what the scope of a name in it is.Language SyntaxContext-free grammars and BNF: •what are•Tokens – strings that are the “units” of parsing; identifiers, literals, punctuation•Terminals – nodes in the grammar that accept tokens and do not reduce•Non-terminals – nodes in the grammar that have rules reducing them to other nodes•Syntax rules – definitions of how a grammar node reduces to another node•Syntax tree – the result of parsing, grouping all nodes according to the reductions specified in the syntax rules•Given a BNF grammar and a string, be able to say whether the language accepts the string, and if it does, what the (concrete) syntax tree is.•Be able to define an “abstract” representation of a program•By eliminating redundant productions, and unnecessary punctuation•What does it mean for a context-free grammar to be ambiguous?•There exists a string of tokens that has more than one legal syntax treeRegular expressions:•Be able to state whether a RE accepts a string, or how to modify an RE to accept a certain kind of stringThe first high-level programming languageWhat are Fortran’s types? •(Fixed, float, arrays)What are Fortran’s name spaces •Variables are local to the procedure; common blocks and subprogram names are global; all are staticHow does Fortran pass arguments?•By referenceWhat is a “secure” language? In what ways is Fortran not secure?•Every program either (a) raises a compile-time error; (b) compiles and produces an answer; (c) compiles and produces a valid run-time error. •Fortran is not secure because of lack of bounds checking, and lack of type checking of COMMON and EQUIVALENCE, that can cause storing values of the wrong type, and because by-reference passing can cause bizarre behavior such as overriding of constants.What can interfere with invariant checking in Fortran? How are later languages better? worse?•GOTO statements make it hard to judge all the ways control can reach a program point•If I call a procedure, it might not only update my parameters, by also any COMMON storage. •If I am a called procedure, it is possible that two of my parameters are aliased.•Later languages have structured control flow, declare constants/in/out/inout•But, they have pointers, multi-tasking, inner procedures, which add additional opportunities for killing invariants.Imperative languagesWhat are:•Stack•Heap•Static Storage•Static Bounds•Dynamic Bounds•What’s the difference between an array with dynamic bounds and a varying-sized array?What’s the difference between a local variable and an own variable?Understand the difference between•Call by reference•Call by value•Call by name•Call by value-resultImperative languages, continuedWhat are invariants? How can I analyze a program at compile-time to check them? What are global variables? Why are they harmful? What’s a better way?What are nested blocks and procedures? What benefit do they provide? What risks do they have?What does it mean for a language to support first-class procedure variables? What is an example of how it’s useful?What is a closure? What is an example of using a closure? Under what circumstances can using a closure in some imperative languages be unsafe? How is it represented at runtime?What’s the difference between C struct types and higher-level language records? Give examples of each.What are exceptions? Why are they preferable to using return codes?Applicative languages (Lisp, Scheme, ML)What is an applicative language?What is a lambda expression?What is the difference between dynamic versus lexical scope of binding? Be able to understand a case where the two would lead to different results.Why did the applicative community realize that lexical scoping was better?What are let and letrec?Be able to translate a simple imperative program to applicative:•Use lambda binding instead of assignments•Use recursion instead of loopsBe able to translate a simple program into continuation-passing style – e.g. to avoid multiple outputs, or to avoid exceptionsBe able to “simulate” objects with closuresBe able to manipulate LISP’s favorite data type – the listUnderstand functionals like mapcarWhat are macros and what is referential transparency?What is eval? When might you want to use it?What is garbage collection? Why is it needed? How is it done?