这个作业是用Haskell完成lambda计算

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.

**程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持 Alipay WeChatPay PayPal等支付方式

**E-mail:** vipdue@outlook.com **微信号:**vipnxx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。