Exam 2 Study Guide


  • Be able to read and write simple Python code.
  • How can we use .format in Python? What does the !r specifier do?
  • What is a generator function?
    • How does yield differ from return?
    • How can we use next to retrieve the next item from an iterator?
    • What is the StopIteration exception? When is it raised? How can we catch it?
    • How can we convert the outputs of a generator object into a list? How about a set? Tuple?
  • Be able to read and write generator expressions, list comprehensions, tuple comprehensions, dictionary comprehensions.
  • How can you raise an exception in Python?
  • How can you catch an exception in Python? How about a specific exception type? How can you access the exception object that was caught?
  • How does else behave when paired with a for loop? while loop? try/except?
  • What does the finally block do in Python? Why do we need it? What alternatives can commonly be used for a substitute?
  • How can we make custom exception types in Python? Why might we want less custom exception types (and use more of the builtins)?
  • What is self used for in instance methods in Python? In what position is self passed?
  • What is the __init__ method when we are writing a class? Can you write an __init__ method for something simple (like ConsCell?)
  • What are each of these magic methods used for: __repr__, __eq__, __add__, __iter__, __getitem__, __setitem__, __len__, __call__, __str__.
  • How can we use isinstance for polymorphism in Python?
  • How can we use hasattr for polymorphism in Python? What is the name of this kind of polymorphism? How does it differ from using isinstance?
  • How can we inherit from another class in Python?
  • How can we inherit from multiple classes in Python?
  • 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?
  • How can we use m.group on a match object in Python? What is m.group(0)?
  • If an expression does not match, what does p.match, p.fullmatch, or p.search return?
  • What is the meaning of r in front of a string literal in Python?

PL Concepts

  • 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))
    (define myfunc (f))
    (define x 3)
    (myfunc) ;; what would it mean if this printed 2?
             ;; what would it mean if it printed 3?
  • What is the three elements of syntax (terms) in the lambda 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.


    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.

  • Where did object oriented programming first appear?

  • Object oriented programming is a style of programming where we have objects that maintain internal state and pass messages between each other.

  • How does object oriented programming differ from making a bunch of classes with unrelated methods in them?

  • What is inheritance? Can you give an example of one type that might inherit from another?

  • What issues arise with multiple inheritance? What is the name of this problem? How does Python solve this problem? Java? C++?

  • What is polymorphism?

  • Why do we need error handling in software?

  • How can we do error handling the old school style (à la C programming)?

  • What are the three issues with old school error handling?

  • How does Go handle errors? Which issues with old school error handling does Go’s error handling solve?

  • How does Python handle errors? Which issues with old school error handling does Python’s error handling solve?

  • 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?

  • 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.

  • 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?

  • What is a tail-call?

  • What does it mean if a function is tail-recursive?

  • Given a function definition in SlytherLisp, be able to identify the tail call of the function and whether the function is tail-recursive or not.

  • How can we make a tail-recursive function optimized by placing the function body in a loop?

  • How can we use the trampoline method to solve the general case of tail-call optimization?