CSC 430 Study Guide (for some sections)

Here’s a study guide for the midterm.

1 Vocabulary

Be able to define, discuss, and use the following terms:

• expressions

• values

• types

• function definition

• function call

• variable reference

• variable binding / bound variable / unbound or free variable

• parsing

• interpreting

• literal

• concrete syntax

• abstract syntax

• AST

• desugaring

• language design vs implementation

• substitution

• lazy vs eager argument evaluation

• scope

• dynamic scope vs lexical scope

• environments

• first class functions

• higher order functions

• closures

• currying

• map / fold / filter

2 Skills

You should be able to do the following things:

• Use / convey the steps of the design recipe

• Know a few design recipe templates / know why the templates are the way they are so that I could create a template for a given structure

• Write functions in Racket and Typed Racket

• Convert between cons, list, quote forms, identify which element of a list is which, and generally manipulate lists and trees

• Translate between concrete and abstract syntax

• Read an EBNF and know what language forms each represent (e.g. can you tell me what abstract syntax form each line of the following represents?)

  Expr   =   Num

  |   id

  |   String

  |   {if Expr Expr Expr}

  |   {local {id Expr} ... in Expr}

  |   {{id ...} => Expr}

  |   {Expr Expr ...}

  ... where an id is not local, in, if, or =>.

• Desugar from convenient concrete syntax to core abstract syntax.

• Be able to small step through a program’s evaluation (i.e. evaluate a program one expression at a time and understand the state of the potential environment at each step)

• Be able to think through tweaks to any of the design decisions we’ve made for our language (or other languages you know) and discuss the implications of said tweaks.