CSE 413 Spring 2011 Final Exam Topics

This is a summary of topics that could appear on the final exam. The exam will focus on things covered since the midterm, although earlier parts of the course could appear. You are responsible for everything covered in lectures and on the homework assignments, although not for the details of the programming language history lectures during the last week of classes..

You may bring one page of hand-written notes to the exam, and you may also bring the page you had at the midterm exam. No other books, notes, laptops, iPhones, or other gadgets allowed.

• Ruby
  • Basic concepts: objects and messages (everything is an object), dynamic typing.
  • Containers: arrays and hashes.
  • Blocks and iterators: blocks, block parameters, using iterators (each) to sequence through a container, times and upto/downto for repetition and counting.
  • Ruby class definitions: defining classes, initialize and other methods, creating instances with new, instance variables (syntax and use), accessors and mutators, attr_reader and attr_writer.
  • Modules and mixins, namespaces, important mixins: Enumerable and Comparable and how these interact with each and <=> methods in classes.
  • Duck typing: what do types mean in a dynamically typed language like Ruby? Tradeoffs compared to languages like Java.
  • Inheritance and overriding: defining subclasses, overriding methods, how a method call is resolved in Ruby.
• Grammars
  • Specification of languages using context-free grammars and regular expressions.
  • Regular expressions: basic operations, using r.e.'s to specify lexical grammar of typical programming language tokens.
  • Context-free grammars: terminals vs. non-terminals, productions, derivations (leftmost and rightmost), ambiguities and ways to deal with them.
• Scanners, parsers, and interpreters
  • Interpreters vs compilers.
  • Scanners and parsers: why split the recognizer into these two parts? Tokens as scanner/parser interface.
  • Scanners: principle of longest match, using the grammar to design a scanner, DFAs (state diagrams) for describing the operation of a recognizer.
  • Parsing: reconstructing derivations, abstract vs. concrete syntax; recursive-descent parsers, dealing with issues like left recursion and common prefixes in productions.
  • Interpreters for functional languages: environments, closures, function application, etc. (e.g., MUPL)
  • Basic implementation of dynamic dispatch: objects and vtables for method dispatch in langauges like Java and C++.