
1. Programming Languages

You should know the answers to these questions:
- What, exactly, is a programming language?
- How do compilers and interpreters differ?
- Why was FORTRAN developed?
- What were the main achievements of ALGOL 60?
- Why do we call Pascal a "Third Generation Language"?
- What is a "Fourth Generation Language"?

Can you answer the following questions?
- Why are there so many programming languages?
- Why are FORTRAN and COBOL still important programming languages?
- What language would you use to implement a spelling checker? A filter
  to translate upper-to-lower case? A theorem prover? An address
  database? An expert system? A game server for initiating chess games
  on the internet? A user interface for a network chess client?

2. Stack-based Programming

You should know the answers to these questions:
- What kinds of stacks does PostScript manage?
- When does PostScript push values on the operand stack?
- What is a path, and how can it be displayed?
- How do you manipulate the coordinate system?
- Why would you define your own dictionaries?
- How do you compute a bounding box for your PostScript graphic?

Can you answer the following questions?
- How would you program this graphic?
- When should you use translate instead of moveto?
- How could you use dictionaries to simulate object-oriented programming?

3. Functional Programming

You should know the answers to these questions:
- What is referential transparency? Why is it important?
- When is a function tail recursive? Why is this useful?
- What is a higher-order function? An anonymous function?
- What are curried functions? Why are they useful?
- How can you avoid recalculating values in a multiply recursive function?
- What is lazy evaluation?
- What are lazy lists?

Can you answer the following questions?
- Why don't pure functional languages provide loop constructs?
- When would you use patterns rather than guards to specify functions?
- Can you build a list that contains both numbers and functions?
- How would you simplify fibs so that (a+b) is only called once?
- What kinds of applications are well-suited to functional programming?

4. Type Systems

You should know the answers to these questions:
- How are the types of functions, lists and tuples specified?
- How can the type of an expression be inferred without evaluating it?
- What is a polymorphic function?
- How can the type of a polymorphic function be inferred?
- How does overloading differ from parametric polymorphism?
- How would you define == for tuples of length 3?
- How can you define your own data types?
- Why isn't == pre-defined for all types?

Can you answer the following questions?
- Can any set of values be considered a type?
- Why does Haskell sometimes fail to infer the type of an expression?
- What is the type of the predefined function all? How would you
  implement it?

5. An application of Functional Programming

You should know the answers to these questions:
- How can you be sure a recursive function will terminate?
- How do you know where characters end in Huffmann encoded bit strings?
- How can you generate a tree from its string representation?
- Why doesn't Haskell have to load the entire file into memory when
  readFile is evaluated?

Can you answer the following questions?
- Can you prove that Huffmann's algorithm really generates the optimal map?
- What would happen if encode used foldl instead of foldr?
- Can parseTree be re-written so it uses the run-time stack instead of
  representing a stack as a list?
- Our Huffmann encoder actually outputs one byte for each "0" or "1"!
How would you adapt the program to produce bits instead of bytes?

6. Introduction to the Lambda Calculus

You should know the answers to these questions:
- Is it possible to write a Pascal compiler that will generate code
  just for programs that terminate?
- What are the alpha, beta and eta conversion rules?
- What is name capture? How does the lambda calculus avoid it?
- What is a normal form? How does one reach it?
- How can Booleans, tuples and numbers be represented in the lambda
  calculus?

Can you answer the following questions?
- How can name capture occur in a programming language?
- What happens if you try to program W in Haskell? Why?
- What do you get when you try to evaluate (pred 0)? What does this mean?
- How would you model negative integers in the lambda calculus? Fractions?
- Is it possible to model real numbers? Why, or why not?

7. Fixed Points

You should know the answers to these questions:
- Why isn't it possible to express recursion directly in the lambda calculus?
- What is a fixed point? Why is it important?
- How does the typed lambda calculus keep track of the types of terms?
- How does a polymorphic function differ from an ordinary one?

Can you answer the following questions?
- Are there more fixed-point operators other than Y?
- How can you be sure that unfolding a recursive expression will terminate?
- How would you express the semantics of the example process calculus?

8. Introduction to Denotational Semantics

You should know the answers to these questions:
- What is the difference between syntax and semantics?
- What is the difference between abstract and concrete syntax?
- What is a semantic domain?
- How can you specify semantics as mappings from syntax to behaviour?
- How can assignments and updates be modelled with (pure) functions?

Can you answer the following questions?
- Why are semantic functions typically higher-order?
- Does the calculator semantics specify strict or lazy evaluation?
- Does the implementation of the calculator semantics use strict or
  lazy evaluation?
- Why do commands and expressions have different semantic domains?

9. Logic Programming

You should know the answers to these questions:
- What are Horn clauses?
- What are resolution and unification?
- How does Prolog attempt to answer a query using facts and rules?
- When does Prolog assume that the answer to a query is false?
- When does Prolog backtrack? How does backtracking work?
- How are conjunction and disjunction represented?
- What is meant by "negation as failure"?
- How can you dynamically change the database?

Can you answer the following questions?
- How can we view functions as relations?
- Is it possible to implement negation without either cut or fail?
- What happens if you use a predicate with the wrong number of arguments?
- What does Prolog reply when you ask not(male(X)). ? What does this mean?

10. Applications of Logic Programming


Can you answer the following questions?
- What happens when we ask digits([A,B,A])?
- How many times will soln2 backtrack before finding a solution?
- How would you check if the solution to the puzzle is unique?
- How would you generalize the puzzle solution to solve arbitrary additions?
- The predicate in/2 can be used both to check if an element is in a
  list, and to select elements from a list. Does subset/2 also have
  this property? Why or why not?
- Can you justify that each of the recursive predicates will terminate?
- What would you do if you couldn't change the precedence of ->/2?
- Can you verify that the closure/3 predicate is correct?
- What would happen if we didn't cut in minkey/4?
- Would it be just as easy to implement these solutions with a
  functional language?

11. Symbolic Interpretation

You should know the answers to these questions:
- How can you represent programs as syntax trees? How can you represent
  syntax trees as Prolog terms?
- How can you define the syntax of your own language in Prolog?
- Why did we define ":" as right associate but "@" as left-associative?
- What is the difference between Succ@Zero=>One and One=Succ@Zero?

Can you answer the following questions?
- How would you implement an interpreter for the assignment language we
  defined earlier?
- Why didn't we use "." in our syntax for lambda expressions?
- Does the order of the fv/2 rules matter? What about subst/4?
- Can you explain each usage of "cut" (!) in the lambda interpreter?
- Can you think of other ways to implement newname/3?
- How would you modify the lambda interpreter to use strict evaluation?

12. Scripting

You should know the answers to these questions:
- How does "scripting" differ from "programming"?
- What happens when you "import" a module in Python?
- What is the difference between "import" and "from ... import"?
- What happens when you evaluate "x = x + y"?
- Does it matter if x is a number or a string? A user-defined object?
- How are run-time type errors handled?
- When can objects be garbage-collected?

Can you answer the following questions?
- Why are strings immutable in Python if other kinds of lists are mutable?
- How would you construct a dictionary from a list of (key, value) pairs?
- What would this program look like without using lambda and map?
- How many ways can you think of to replace blanks in a string by "+" signs?
- How would you write a script that produces an HTML index of all pages
  at a web site that are reachable from its home page?

