Haskell代写 | CSCI 4430 Programming Languages

CSCI 4430 Programming Languages
Homework 6: An Interpreter for the Lambda calculus in Haskell

Problem 1. Applicative order interpreter
Your first task is to write the interpreter in the style we gave in lecture. Please include your answer in comments in your Haskell file under heading Problem 1.
Problem 2. Coding the applicative order interpreter in Haskell
Next, you will code the interpreter in Haskell. A lambda expression is of the following form, as we discussed in class:
It takes a list of expressions and generates an (infinite) list of variables that are not free in any of the expressions in the list. For example, freshVars [Lambda “1_” (App (Var “x”) (App (Var “1_”) (Var “2_”)))] yields the infinite list [1_,3_,4_,5_,..]. Remember, you will leverage [1..] to implement freshVars.
Substitution. Next, write the substitution function
subst :: (Name,Expr) -> Expr -> Expr
All functions in Haskell are curried: i.e., they take just one argument. The above function takes a variable x and an expression e, and returns a function that takes an expression E and returns E[e/x]. Important: subst must implement the algorithm we gave in class! Specifically, when performing a substitution on a lambda expression λy.E1, where y≠x, subst must always replace parameter y with the next fresh variable from the list of freshVars, even if y is not free in e and it would have been safe to leave it as is. This is necessary for autograding on Submitty.

A single step. Now write a function to do a single step of reduction:
Given an integer n and an expression e, appNF_n does n reductions (or as many as possible) and returns the resulting expression.
• Write all functions described above, freeVars, freshVars, subst, appNF_OneStep, and appNF_n and include them in your Interpreter.hs file.
• You are allowed to use all features of Haskell and import modules you find useful.
• Just as with your Scheme homework, do comment your code! Write comments in the same style although there is one notable difference, namely that in Haskell type signatures are statically checked. Include type signatures for every function you write even though Haskell can infer those signatures.