Submission instructions:

Submit a Haskell or scheme file for part 1.
Submit a Scheme file for part 2.

---------------------------------------

1. Consider the Church numerals on slide 18 and 19 of the lecture notes.

Implement Church numerals in Haskell or Scheme and add the following functions:

- functions that translate ordinary Haskell/Scheme natural numbers into
  their Church encoding and back
- a function "exp" on Church numbers such that result of exp a b corresponds to a^b

Add some test cases which show that your implementation works.

---------------------------------------

2. Consider the substitution-based FAE interpreter in Sec. 6.2 of the textbook.
It is available at
http://www.daimi.au.dk/~ko/teaching/pl/plt5-FAE-sustitutionbased.ss

Extend the interpreter as follows:

a) Add a function "step : FAE -> FAE", which performs a single reduction step
according to the operational semantics of the lambda calculus as defined on
slide 8 of the lecture notes. FAE is of course a bit richer than the pure lambda
calculus, hence think about an appropriate extension of the operational semantics
for the FAE constructs.

b) Add a function "multistep : FAE -> FAE", which performs computation steps until
the expression has been reduced to a value. Confirm with a few tests that "multistep"
agrees with "interp".

c) Extend the language with a type checker in the style of the simply-typed lambda calculus.
Lambda abstractions should be annotated with types (cf. slides 67). Think about appropriate
typing rules and base types for the arithmetic parts of FWAE.  Implement the type checker
as a function "typecheck : Context FAE -> Type" (for an appropriate definition of Context).

d) Extend the syntax, interpreter, step-relation, and type-checker with the following features (cf. slides):
  - labeled records (slides 97-99)
  - labeled variants  (108-111)
  - fixed point operator (117-118)

Test all new features!

You need to submit the complete code after you've solved 1-4 only, not the intermediate steps