CSE 413 Autumn 2008 Midterm Topics

This is a summary of topic that could appear on the midterm. Briefly, everything related to Scheme programming and other topics discussed prior to Ruby are included, including both lectures and homework assignments.

You should bring a copy of the Scheme language report with you, and you may optionally bring one page of hand-written notes. No other books, notes, laptops, iPhones, or other gadgets allowed.

• Scheme primitive data types, particularly integers, symbols (atoms), strings, and booleans (#t, #f)
• Basic form of scheme programs: top-level definitions, basic functions (arithmetic, logical, equivalence, relations, predicates), special forms like define, if, cond.
• Use of symbols as variables. Quoting: difference between 'a and a.
• Function application: what it means to evaluate a list (e1 e2 ... en) [Evaluate the expressions, then apply e1, which needs to be a function, to the remaining arguments e2, ..., en.]
• Scheme lists and recursive definitions of data (cons, car, cdr). Be able to draw diagrams of list structures and the results of computations involving lists.
• Recursive programs to process recursive data.
• Using functions to abstract away from the underlying list structures (for example, functions to construct tree nodes and access components of them).
• Scope and bindings: let, let*, and letrec. Use of define at top-level.
• Tail recursion. What it means, how to solve problems using it, why it sometimes makes things more efficient (able to accumulate values in parameters instead of recomputing them).
• Higher-order functions - functions as data and as parameters.
• Anonymous functions: lambda.
• Common recursion patterns involving higher-order functions: map, filter, reduce (fold-left and fold-right).
• Closures: what it means to evaluate a lambda to get a value (a <function, environment> pair). Static scoping and use of environments when applying closures to arguments (for sure, know how to diagram this). Nested scopes.
• Interpreters. What an interpreter does, interpretative evaluation of programs, maintaining environments and handling closures. You should be familiar with both the whiteboard discussions in class and with the implementation in the MUPL assignment. (You don't need to memorize the MUPL data types like make-var, make-app, etc.; if these are needed for a question a summary will be provided. You do need to understand DrScheme's define-struct extension and how to use types built with it.)
• Garbage collection: Basic idea of reachable (live) data; root set of variables and other data that form the starting point for discovering the reachable data. You should know the basic ideas behind mark-sweep and compacting collectors, as well as the heuristics that explain why generational collectors are effective.
  
  
• You don't need to know how to use functions with side effects like set! and set-car!.