CSE 413 19wi 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 (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). 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 (be sure you know how to diagram this). Nested scopes.
  • Use of closures for idioms like lazy evaluation, streams, and memos.
Postponed until final exam:
  • Racket structs and how to use them.
  • 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.)