The Metacircular Evaluator $($Racket Language$)$

Add support for force and delay to your interpreter, where delay $\text{'}$ed expressions are only evaluated once when force $\text{'}$d$.$

For full credit, a delay $\text{'}$ed expression must be evaluated at most once. If your implementation evaluates a delayed expression every time it is forced but

is otherwise correct, you will receive half credit. Do not submit two implementation of force and delay.

It is highly recommended that you implement the non$-$memoizing version of force and delay first. If you get stuck on the memoizing version without

having implemented the non$-$memoizing version, stop what you're doing and get the non$-$memoizing version working first.

The implementations of both the non$-$memoizing and memoizing versions of force and delay were discussed in lecture. The easiest path to success

will follow that discussion. Although force and delay can be implemented using thunks, that approach is difficult to get right.

Your solution must demonstrate that you understand the underlying mechanisms for implementing lazy evaluation. Therefore, you may not use Racket's

force and delay or equivalent syntax macros in your solution to this problem. The homework template is set up to prevent you from accidentally

using Racket's force and delay.

If you have successfully implemented force and delay using the technique from lecture, then your evaluator should evaluate $(($delay $5))$ to $5$

$($why$?).$ However, force and delay are not identity functions! Although $($force $($delay e$))$ will have the same value as the expression e $,$

implementing both force and delay as the identity function is incorrect. Similarly, if $($delay $($error$))$ throws an error, your implementation is not

correct and will score $0$; delay must delay evaluation.

Hint: Write a function delay$->$ lambda that rewrites a delay expression as described in lecture, leading to an implementation of delay as a derived

expression. Test your delay$->$lambda independently to make sure it is performing the rewrite correctly, e$.$g$.,($delay$->$lambda $\text{'}($delay $3))$

should evaluate to $($lambda $()3)($why$?).$

$($define $($setup$-$environment$)$

$($let $(($initial$-$env

$($extend$-$environment $($primitive$-$procedure$-$names$)$

$($primitive$-$procedure$-$objects$)$

the$-$empty$-$environment$)))$

$($define$-$variable! 'true true initial$-$env$)$

$($define$-$variable! 'false false initial$-$env$)$

initial$-$env$))$

$($define $($primitive$-$procedure? proc$)$

$($tagged$-$list? proc 'primitive$))$

$($define $($primitive$-$implementation proc$)($cadr proc$))$

$($define primitive$-$procedures

$($list $($list 'car car$)$

$($list $\text{'}$cdr cdr$)$

$($list 'cons cons$)$

$($list 'null? null?$)$

;; more primitives

$))$

$($define $($primitive$-$procedure$-$names$)$

$($map car

primitive$-$procedures$))$

$($define $($primitive$-$procedure$-$objects$)$

$($map $($lambda $($proc$)($list 'primitive $($cadr proc$)))$

primitive$-$procedures$))$

$($define $($apply$-$primitive$-$procedure proc args$)$

$($apply $($primitive$-$implementation proc$)$ args$))$

$($define $($user$-$print object$)$

$($if $($compound$-$procedure? object$)$

$($display $($list 'compound$-$procedure

$($procedure$-$parameters object$)$

$($procedure$-$body object$)$

$\text{'}))$

$($display object$)))$

$($define $($top$-$mceval exp$)$

$($let $(($val $($mceval exp $($setup$-$environment$))))$

$($user$-$print val$)))$

$($define the$-$global$-$environment $($setup$-$environment$))$

$($define input$-$prompt $">")$

$($define $($driver$-$loop$)$

$($display input$-$prompt$)$

$($when $($with$-$handlers

$([$exn:fail? $($lambda $($exn$)$

$($display "Error: $")$

$($display $($exn$-$message exn$))$

$($newline$)$

#t$)])$

$($let $([$input $($read$)])$

$($if $($eof$-$object? input$)$

$($begin

$($newline$)$

#f$)$

$($let $([$output $($mceval input the$-$global$-$environment$)])$

$($user$-$print output$)$

$($newline$)$

#t$))))$

$($driver$-$loop$)))$

$($define $($main $.$ argv$)$

$($driver$-$loop$))$

$($provide mceval

setup$-$environment

main$)$