1-
Let s : N ! N? be the successor function on natural numbers defined
as follows: s(n) = n + 1. Note that s does always terminate. Let the
following WHILE program P be given:
read X
Y:= cons nil X
write Y
Define an encoding c such that [[P]]WHILE implements s via c. Explain
what conditions your c needs to fulfill and show that those conditions
actually hold (Note that this is quite easy in this case).
2-
Let W0 be the following sublanguage of WHILE: W0 contains all
WHILE programs that use variable 0 as output variable. Write a
compiler [login to view URL] from WHILE to W0. This compiler takes
a WHILE program (in list notation) as input and returns a WHILE
program (in list notation) that behaves identically but uses variable 0
as output variable. [Note that this is an extremely simple compiler
which does not require complex tree traversal.]
3-
Write a compiler [login to view URL] which translates WHILE programs into I-programs,
ie WHILE programs that only use one variable, namely var 0.
Your program should call the following auxiliary functions:
While2l [login to view URL] , Number [login to view URL] , and [login to view URL] which is attached.
Your compiler only
needs to traverse commands (once you hit an expression you can call
While2l [login to view URL]).
Your compiler should not have more than about 70 lines of code (not
counting comments). Note that such non-trivial programs which call
other non-trivial programs may take some time in WIDE to compile
(on my old machine about a minute or so). Don’t forget to test your
compiler on several input programs. Add comments to your program
where useful.