CSE 413 Autumn 2008 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.

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. You should not bring the Scheme language report. 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.
  • Blocks, procs, and closures: using a block, yield (with or without arguments), difference between blocks and first-class closures created with Proc.new or lambda.
  • 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.
• Inheritance, implementing objects and dynamic dispatch
  • Implementing message send: this or self implicit parameters, implementing objects on top of non-OO languages
  • Multiple inheritance, interfaces, and mixins: tradeoffs, issues.
  • Type systems for object-oriented languages (Java, C++).
  • Implementing dynamic dispatch: method lookup in dynamic languages like Ruby; object layout and vtables for method dispatch in languages like Java, C++; how inheritance works in both kinds of systems.