Description
In this homework you will be starting out with the version of the interpreter
seen in the solution for homework 07 (with very minor modifications).
You will need to modify the semantics of procedure definitions in such a way that
they support recursive calls. And you will be adding C/C++ style references
to the language.
===============================================================================
1. Named recursive procedures [20p]
Modify the semantics of named function definitions to support recursive calls:
> (run
“def a(p) =
if(origin?(p))
then
42
else
call(a move(p down(1)));
call(a (0 3))
“)
(num-val 42)
You had this problem in hw07 – p5. For now, start from the initial implementation provided
in hw08-interpreter.rkt and do it again.
===============================================================================
2. Anonymous recursive procedures [20p]
To handle recursive procedures in a more complete manner, a new expression is added:
<expr> :: = recfun ( identifier* ) = <expr> “recfun-expr”
It has the same behavior as the “fun-expr” with the added behavior that the procedure
can call itself via the “self” keyword.
> (run
“val rf =
recfun (p) =
if(origin?(p))
then
42
else
#the function calls itself
call(self move(p down(1)));
call(rf (0 3))
“)
(num-val 42)
===============================================================================
3. Explicit referencing [30p]
We will be adding an explicit referencing model to our language. For reference
(pun intended) think about pointers in C/C++ with slightly different syntax.
References introduce *side effects* to our language, i.e. executing procedures
and certain expressions in our language might result in the modification of
the values stored in variables. Contrast this with how every expression in
our language resulted in a *value* and had no *effect*.
You will be adding a new type of value, references, and defining the following
set of operations on said references:
<expr> ::= ref ( <expr> ) “new-ref-expr”
;this is similar to malloc in C. It “allocates” a memory
;zone and returns a pointer to that zone. Additionally,
;it initializes it to the value of the <expr> given as a parameter
<expr> ::= * <expr> “deref-expr”
;given a pointer, the deref-expr will return the value stored
;at that location.
<expr> ::= set <expr> := <expr> “set-ref-expr”
;given a pointer and a value, sets the value at the pointer
;location to said value.
<expr> :: = ++ <expr> “inc-ref-expr”
;returns a new reference that points to the next “memory” location
<expr> :: = — <expr> “dec-ref-expr”
;returns a new reference that points to the orevious “memory” location
—
All references point to locations in the “store” datatype (described in section 4.2.3 and
provided in the hw08-env-values.rkt file).
As you might notice, the implementation of the store datatype make use of the “set!”
procedure and of a global variable called “the-store”, this is the first time in this
class where something cannot be implemented without using side-effects. Take some time
to ponder why this is the case; think about how “set-ref-expr” compares to variable
definitions, depending on scope.
===============================================================================
4. Arrays [30p]
Building on what you implemented for problem 3, add C/C++ style arrays to the language
with the syntax:
<expr> ::= [<expr>] “array-expr”
| *[] <expr> [<expr>] “array-deref-expr”
| set[] <expr> “[” <expr> “]” := <expr> “array-set-expr”
“array-expr” initializes an array of size <expr> with the value (num-val 0)
“array-deref-expr” will return the value stored at index “[” <expr> “]” of a given
array. Arrays are 0 indexed.
“array-set-expr” will behave like “set-ref-expr” but for the specified array index
by “[” <expr> “]”
Arrays should behave like normal pointers:
> (run ”
val a = [2];
#this will point to the first position of the array
*a”)
(num-val 0)
>(run ”
val a = [2];
set[] a[0] := 42
set[] a[1] := 23
#incrementing an array will return a pointer pointing to the 2nd element of the array
*++a”)
(num-val 23)