CISC 670 Programming Languages (Fall 2002)

Final Exam Study Guide

Time and Date: 1:00-3:00pm, Tuesday, December 17, 2002
Place: Smith 204


References 

- All Lectures. 
- Textbook: Chapters 1, 2 (2.1, 2.2.1, 2.2.2, 2.2.3), 3(not 3.5 and 3.6.2), 
                6(6.1 to 6.6 but not 6.5.3), 7(7.1, 7.2, 7.3), 8(8.1, 8.2, 8.3),
                10, 11.
- Homework assignments (1, 2, 3, 4, and 5).


Topic Coverage 

- basics of programming language implementation: interpreters, compilers: overview of what they do,
  components, differences, similarities. 
- language syntax: regular expressions, context free grammars, derivations, parse trees,
  tokens, scanners, parser classes. 
- names: scoping, implementation of scoping, symbol tables, subroutine closues, subroutines are passed as 
  parameters, or returned as results. 
- control flow: expression evaluation,  precedence, associativity, assignments, side effects, 
  short-circuit evaluation, iteration and recursion.
- storage management: basics of stack, heap, static management, activation records, garbage
  collection.


- data types: typing, type systems, type equivalence, type compatibility, type checking, 
  strong typing, static typing, name equivalence, structural equivalence, aliasing, 
  type inference, specifying rules of inference, issues in memory layout.
- object-oriented programming: inheritence, polymorphism, dynamic method dispatch, virtual mathods
  table (VTable), multiple inheritence, subtyping, issues in memory layout.
- functional programming: lambda calculus, beta reduction, normal form, applicative-order vs 
  normal-order, call-by-name, call-by-need, Y combinator
- logic programming: Prolog programming, Prolog search trees, predicate calculus basics.

Format of Exam 

The exam is closed book and notes. The exam will have a heavy emphasis on 
understanding and applying the concepts we have discussed in class.  
The exam will cover the whole semester, but with a skewed emphasis on topics after
midterm.
If coding in ML is required for some problems, the emphasis will not be 
on the correctness of syntax. 

There will be five to six problems.

Example questions: 

- True or false with one sentence explanation regarding general concepts: compilers, interpreters,... 
- Write/read regular expressions. 
- Explain the set of strings that a regular expression accepts. 
- Write/read context free grammars. 
- Draw a parse tree or derivation for a given string. 
- Determine whether a given string is accepted by a grammar. 
- Give example strings generated by a grammar. 
- Show that a given grammar is ambiguous. 
- Modify a given grammar so that it is unamgiguous or satisfies certain properties, 
  such as left-recursion free.
- Show the output or indicate the variables accessible at different points in a program 
  based on static versus dynamic scoping rules. 
- Show the implementation of static scoping and dynamic scoping
- Indicate where a particular item would most likely be stored: stack, heap, static store 
- Draw a snapshot of the stack showing frames, their static and dynamic links, 
  name and content of local variables
- Show the output or indicate the variables accessible at different points in a program based on
  different parameter passing modes 
- Identify whether a recursion is tail recursion, and modify a recursion so that it is tail recursive
- Write or modify a small ML code segment to implement certain design features for an interpretor. 
- Explain how a particular concept is exhibited by a code segment. 

- lambda expression: equivalence and reduction
- type inference
- express relations in logic
- Write short code segments to illustrate a concept. 
- Explain how a particular concept is exhibited by a code segment.