CSE 413 Autumn 2012 Midterm Topics

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

The exam is closed book, closed notes. We will provide any necessary reference material on the exam, but you should know how to use the basic Racket functions like cons, car, append, map, if, define, and so forth.

• Racket primitive data types, particularly integers, symbols (atoms), and booleans (#t, #f)
• Basic form of Racket 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 (procedure), to the remaining arguments e2, ..., en.]
• Racket 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.
• 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.
• Use of closures for idioms like lazy evaluation, streams, and memos.
• 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 the implementation in the MUPL assignment. (You don't need to memorize the MUPL data types like int, apair, call, etc.; if these are needed for a question a summary will be provided. You do need to understand Racket structs and how to use them.)
• 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, pros and cons of reference counting vs garbage collection algorithms like mark/sweep.