In this homework you will implement a Flang-like language by introducing a new preprocessor step into the interpreter. The preprocessor will translate bindings in the source program to a different representation that uses de-Bruijn indexes (see the class notes and Section 3.5 of Programming Languages: Application and Interpretation v1 for reference).
As is commonly done by compiler passes, you will need to keep track of the lexical scope of the code that is preprocessed. This will be done by adding an environment argument to the preprocessor which will keep track of the bindings. Note that this is not the same as a runtime environment argument in eval, it only keeps track of the names that are currently in scope — there are no runtime values at this point.
The language for this homework is:
#lang plait |
Begin your work with the Skeleton of de Bruijn index based interpreter
As mentioned above, the transformation from source to de-Bruijn indexes that we will implement is essentially a new compilation step: it translates one language (Brang) to a different language, which in this case is quite similar except for identifier references. This language will our “core” language in that it represents what we execute at the low level. CORE provides a type definition for this intermediate language. CORE is a mainly copy of BRANG except that all of its variant names are prefixed by a “C” (CNum, CAdd, etc). You will notice several important diffences. First, instead of CId, it has a CRef for identifier references. Second, the binding forms (CLam, CLet1) have one less parameter.
The basic idea of the preprocessor is to scan the input program, and convert identifiers into CRef values. This would be a mostly-routine function that translates BRANG values to CORE values. But there is one important thing: when we encounter an identifier, we need to know the ‘shape’ of the current scope — a mapping from identifiers to their de-Bruijn indexes. In other words, a kind of a compile-time environment.
Your skeleton provides a type DE-ENV and 3 functions to implement static environments.
(has-type de-extend : (Symbol DE-ENV -> DE-ENV)) (has-type de-lookup : (Symbol DE-ENV -> Number)) (has-type de-empty-env : (-> DE-ENV) ) |
(test (de-lookup 'x (de-extend 'x (de-empty-env))) 0)
(test (de-lookup 'x (de-extend 'y (de-extend 'x (de-empty-env)))) 1)
(test (de-lookup 'x (de-extend 'x (de-extend 'x (de-empty-env)))) 0)
(test (de-lookup
'y
(de-extend 'x
(de-extend 'x
(de-extend 'y (de-empty-env))))) 2)
(test/exn (de-lookup 'x (de-empty-env)) "undefined identifier") |
Using the above, implement the preprocessor. It is a simple recursive scan of its input that translates a given BRANG value (and a DE-ENV value) to the corresponding CORE value. The only interesting cases are ones that deal with scope: the two cases where a new scope is introduced, and dealing with identifiers. A couple of simple tests follow.
(module+ test
(define test-env (de-extend 'x (de-extend 'z (de-extend 'y (de-empty-env)))))
(test (preprocess (Id 'x) test-env) (CRef 0))
(test (preprocess (Add (Id 'x) (Id 'y)) test-env) (CAdd (CRef 0) (CRef 2)))
(test (preprocess (parse-sx `{{lam x {+ x 1}} 4}) (de-empty-env))
(CCall (CLam (CAdd (CRef 0) (CNum 1))) (CNum 4)))
(test (preprocess (parse-sx `{let1 {add3 {lam x {+ x 3}}} {add3 1}})
(de-empty-env))
(CLet1 (CLam (CAdd (CRef 0) (CNum 3))) (CCall (CRef 0) (CNum 1))))
) |
The preprocessed programs that we will be running will have no identifiers, as they will all be translated into de-Bruijn references. Our evaluator will be substitution based, mainly to defer some of the subtleties about environments to later. You need to define a recursive function subst, but instead of an identifier it takes a scope level to replace. This level increases whenever a new scope is introduced (i.e. with CLam and CLet1). Here are some tests to get you started.
(module+ test
;; {+ x 1}[3/x]
(test (subst (CAdd (CRef 0) (CNum 1)) 0 (CNum 3))
(CAdd (CNum 3) (CNum 1)))
;; {let1 {x 3} {+ x 1}}[2/x]
(test (subst (CLet1 (CNum 3) (CAdd (CRef 0) (CNum 1))) 0 (CNum 2))
(CLet1 (CNum 3) (CAdd (CRef 0) (CNum 1))))
;; {let1 {x 3} {lam y {+ x 1}}} => {lam y {+ x 1}}[3/x]
(test (subst (CLam (CAdd (CRef 1) (CNum 1))) 0 (CNum 3))
(CLam (CAdd (CNum 3) (CNum 1))))
) |
We (will) have gone over substitution-based evaluators for FLANG in lectures. Here the task is fill in the missing cases that use the new de-Bruijn index compatible substitution function. A few tests for raw CORE follow.
(module+ test
(test (eval (CCall (CLam (CAdd (CRef 0) (CNum 1))) (CNum 4))) (NumV 5))
(test (eval
(CLet1 (CLam (CAdd (CRef 0) (CNum 3))) (CCall (CRef 0) (CNum 1))))
(NumV 4))
) |
For the remaining tests, we use the convenience function run that does parsing of surface syntax and preprocessing.
(module+ test
(test (run `{{lam x {+ x 1}} 4})
5)
(test (run `{let1 {add3 {lam x {+ x 3}}}
{let1 {add1 {lam x {+ x 1}}}
{let1 {x 3}
{add1 {add3 x}}}}})
7)
) |
Add any tests needed for coverage. Make sure you document tests, including those provided in the assignment.
Define minutes-spent as the number of minutes you spent on your homework.