CSE 413 23sp Midterm Exam Topic List

This is a summary of topic that could appear on the midterm. Briefly, everything related to Racket programming and other topics discussed up to, but not including, interpreters and MUPL might be included. If you've kept up with everything that's been covered in class, slides, notes, sample code, and homework assignments you should be well prepared.

The exam will be closed book, except that you may have one 5x8 (or smaller) index card with whatever notes you wish written on both sides for reference. The notes must be hand-written, i.e., no computer printouts, no scanned/reduced notes, and no electronic devices or other technology. We will provide reference material on the exam as needed, but you should know how to use the basic Racket functions and special forms like cons, car, cdr, list, append, map, if, define, lambda, 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 and evaluation: difference between 'a and a.
• Function application: what it means to evaluate a list (e0 e1 ... en) [Evaluate the expressions, then apply e0, which needs to be a function (procedure, closure), to the remaining arguments e1, ..., en.]
• Racket lists and recursive definitions of data (cons, car, cdr, etc.). 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.
• Function values, anonymous functions: lambda.
• Common recursion patterns involving higher-order functions: map, filter, reduce.
• Mutation in racket (set!, mcons, mcar, mcdr, set-mcar!, set-mcdr!, etc.) and when (and when not) to use it.
• Closures: what it means to evaluate a lambda to get a value (a <environment, function> pair). Static scoping and use of environments when applying closures to arguments (be sure you know how to diagram this). Nested scopes.
• Use of closures for idioms like lazy evaluation, streams, and memos.