#lang racket
;; Assignment 4: A church-compiler for Scheme, to Lambda-calculus
Copyright By PowCoder代写 加微信 powcoder
(provide church-compile
; provided conversions:
church->nat
church->bool
church->listof)
;; Input language:
; e ::= (letrec ([x (lambda (x …) e)]) e)
; | (let ([x e] …) e)
; | (let* ([x e] …) e)
; | (lambda (x …) e)
; | (e e …)
; | (and e …) | (or e …)
; | (if e e e)
; | (prim e) | (prim e e)
; | datum
; datum ::= nat | (quote ()) | #t | #f
; nat ::= 0 | 1 | 2 | …
; x is a symbol
; prim is a primitive operation in list prims
; The following are *extra credit*: -, =, sub1
(define prims ‘(+ * – = add1 sub1 cons car cdr null? not zero?))
; This input language has semantics identical to Scheme / Racket, except:
; + You will not be provided code that yields any kind of error in Racket
; + You do not need to treat non-boolean values as #t at if, and, or forms
; + primitive operations are either strictly unary (add1 sub1 null? zero? not car cdr),
; or binary (+ – * = cons)
; + There will be no variadic functions or applications—but any fixed arity is allowed
;; Output language:
; e ::= (lambda (x) e)
; | (e e)
; also as interpreted by Racket
;; Using the following decoding functions:
; A church-encoded nat is a function taking an f, and x, returning (f^n x)
(define (church->nat c-nat)
((c-nat add1) 0))
; A church-encoded bool is a function taking a true-thunk and false-thunk,
; returning (true-thunk) when true, and (false-thunk) when false
(define (church->bool c-bool)
((c-bool (lambda (_) #t)) (lambda (_) #f)))
; A church-encoded cons-cell is a function taking a when-cons callback, and a when-null callback (thunk),
; returning when-cons applied on the car and cdr elements
; A church-encoded cons-cell is a function taking a when-cons callback, and a when-null callback (thunk),
; returning the when-null thunk, applied on a dummy value (arbitrary value that will be thrown away)
(define ((church->listof T) c-lst)
; when it’s a pair, convert the element with T, and the tail with (church->listof T)
((c-lst (lambda (a) (lambda (b) (cons (T a) ((church->listof T) b)))))
; when it’s null, return Racket’s null
(lambda (_) ‘())))
;; Write your church-compiling code below:
; churchify recursively walks the AST and converts each expression in the input language (defined above)
; to an equivalent (when converted back via each church->XYZ) expression in the output language (defined above)
(define (churchify e)
[_ ‘todo]))
; Takes a whole program in the input language, and converts it into an equivalent program in lambda-calc
(define (church-compile program)
; Define primitive operations and needed helpers using a top-level let form?
(define todo `(lambda (x) x))
(churchify
`(let ([add1 ,todo]
[zero? ,todo])
,program)))
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com