# Exam 2 Study Guide¶

EDIT 2018-03-08: Added second item to SlytherLisp section.

## SyltherLisp¶

• Be able to read and understand SlytherLisp code. (You will not be required to write any SlytherLisp code on the exam.)
• What is the difference between a macro and a function? Can you give an example of a language feature which can only be implemented using a macro?

## Lambda Calculus¶

• What is the three syntactical elements (terms) in the lambda calculus?
• What is currying?
• Understand how currying allows us to have functions which take multiple arguments in the λ-calculus.
• Can you identify whether a variable is bound or free in a lambda term?
• What are the three transformations we can preform on lambda terms? When can we apply these transformations? Given a term and a transformed version of it, can you identify which transformation was applied (or if the transformation is invalid)?
• What is a Church numeral? If I gave you any arbitrary positive integer, could you convert it to its corresponding Church numeral?
• When we apply a church numeral to a lambda abstraction, what new kind of abstraction do we get?
• Be able to beta-reduce any lambda term and show each step (with and without currying).

Note

You do not need to memorize the shorthands for SUCC, ADD, MUL, CONS, etc.

I will give you the shorthands if you need them. The only shorthand you need to know the translation for is Church numerals.

## PL Concepts¶

• What is a cons cell? What are the left and right sides called? How can we use cons cells to build lists?

• What is static/lexical scoping? How does it differ from dynamic scoping?

• How can we use static/lexical scoping in combination with first class functions to provide us with closures?

• Given a piece of code in a Lisp-like language and its output, could you use the code to identify whether the language uses static/lexical scoping or dynamic scoping? e.g., in this code:

(define (f)
(define x 2)
(define (printer)
(print x))
printer)

(define myfunc (f))
(define x 3)
(myfunc) ;; what would it mean if this printed 2?
;; what would it mean if it printed 3?


### Memory Management¶

• What is a pointer? How is it different from (and similar to) a reference?
• In C or C++, why is BASE[OFFSET] equivalent to OFFSET[BASE]?
• What is an object lifetime?
• Name the 3 dangers of explicit heap dynamic lifetimes. Be sure you could identify which danger is demonstrated in a simple piece of C or C++ code.
• What is garbage collection? Given a diagram like presented in lecture of the visible and working variables and the heap, could you identify which nodes on the heap can be garbage collected?

### Regular Expressions and FSA¶

• What is a character set in a regular expression?
• How can we negate a character set?
• How do character sets differ from groups?
• What is the meaning of the special character sets \s, \S, \d, \D, \w, \W?
• How can we specify a range of characters in a character set?
• How can we match any character in a regular expression?
• What is the meaning of +, ?, * in a regular expression?
• What does it mean to be greedy/non-greedy in a regular expression? What are the non-greedy versions of the +, ?, * operators?
• How can we “escape” characters with a special meaning in a regular expression?
• How can we use groups in a regular expression?
• What is alternation?
• How can we make use of alternation?
• What is a capturing group?
• What is a non-capturing group? How is it written?
• What is an anchor? What are the \b, \$, ^ anchors?
• Given a regular expression, can you identify whether a string will match that regular expression?
• What is a finite state machine? What are the states? What are the transitions?
• Be able to convert a regular expression to a finite state machine graph.
• Be able to write a regular expression for matching a double-quoted string literal.
• How can we write regular expressions in Python? What is the meaning of p.match versus p.search or p.fullmatch? How about p.finditer?
• In Python, how can we use m.group on a match object in Python? What is m.group(0)?
• In Python, if an expression does not match, what does p.match, p.fullmatch, or p.search return?

### Parsing¶

• What are the two stages of parsing? What is the purpose of each stage?
• What are the inputs and outputs to parsing?
• Be able to draw an abstract syntax tree for a given string and a given grammar.
• What is the difference between a top-down parser and a bottom-up parser?
• What is shift-reduce? Can you create a parse table given a grammar and an input string?
• What is the lookahead-token in shift-reduce? How can we use it to determine if there is ambiguity?