In this problem we set will represent some functional programs as data objects and manipulation them in various ways. The description of the functional programming language syntax is given in fp.mod. Various example functional programs are in the file fpexs.mod.

- The file fpeval.mod contains the description
of a call-by-value evaluator for this functional programming language.
Use this evaluator to evaluate the following expressions. It is part of
this assignment to correctly translate the informal description of a computation
into a formal one prior to evaluation.
- 3 plus 5.
- Membership of 2 in the list [3, 5, 2].
- Membership of 6 in the list [3, 5, 2].
- Fibonacci of the Fibonacci of 4.
- Using the
`map`function, compute the Fibonacci of all the members of the list [3,5,2].

- The file fptype.mod contains some type
declaration for primitive operations in our functional programming
language. Implement the predicate
type infer exp -> ty -> o.

that infers the type of expressions. If an expression is ill-typed then this predicate should fail. You should be able to reproduce the following session using the example programs in fpexs.mod. - The file fpredex.mod contains various
``rewriting'' facts with respect to the constants of our functional
programming language. These rules can be seen as one step rewriting rules:
they replace equal expressions by equal expressions. Specify the following
two predicates
type red1 exp -> exp -> o. type reduce exp -> exp -> o.

where`red1`relates two expressions if the second expression results from replacing*exactly*one rewriting redex somewhere within the first expression. The`reduce`relationship that repeatedly applies`red1`until it cannot be applied further and returns the resulting expression. You should be able to reproduce the following session using the example programs in fpredex.mod.

Lectures / Modules / Homeworks / Syllabus