CSE 360 Homework 7

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.

1. 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].

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.

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