de Bruijn indices: Write a procedure to transform WAE expressions into equivalent expressions using de Bruijn indices, as in the examples on page 25 of the text. For example,
{with {x 5}
{with {y 3}
{+ x y}}}
1
2
3
transforms into
{with 5
{with 3
{+ <1> <0>}}}
1
2
3
And we convert
{with {x 5}
{with {y {+ x 3}}
{+ x y}}}
1
2
3
into
{with 5
{with {+ <0> 3}
{+ <1> <0>}}}
1
2
3
Data types: Use the text’s definition of WAEs:
(define-type WAE
[num (n number?)]
[add (left WAE?) (right WAE?)]
[sub (left WAE?) (right WAE?)]
[with (name symbol?) (named-exp WAE?) (body WAE?)]
[id (name symbol?)])
1
2
3
4
5
6
Also use a datatype defining DBWAEs
(define-type DBWAE
[dbnum ...]
[dbadd ...]
[dbsub ...]
[dbwith ...]
[dbid ...])
1
2
3
4
5
6
1
where I will let you fill in the appropriate fields for each type.
Examples: The two textbook examples will look like this:
(db (with ’x (num 5)
(with ’y (num 3)
(add (id ’x) (id ’y)))) )
=>
(dbwith
(dbnum 5)
(dbwith (dbnum 3) (dbadd (dbid 1) (dbid 0))))
1
2
3
4
5
6
7
8
and
(db (with ’x (num 5)
(with ’y (add (id ’x) (num 3))
(add (id ’x) (id ’y)))) )
=>
(dbwith
(dbnum 5)
(dbwith
(dbadd (dbid 0) (dbnum 3))
(dbadd (dbid 1) (dbid 0))))
1
2
3
4
5
6
7
8
9
Optional 1: Include a parser for WAEs and an “unparser” for DBWAEs, so that the input/output can look like this:
(debruijn
‘{with {x 5}
{with {y {+ x 3}}
{+ x y}}})
=>
‘(with 5
(with (+ <0> 3)
(+ <1> <0>)))
1
2
3
4
5
6
7
8
Optional 2: Include parsers and tranformers that will go the other way, transforming DBWAEs into WAEs.
Turn in: Put all your files into a folder csci312hw05yourname, zip it, and submit to canvas.
