$6$ Part $3$: Functions Due: December $32024,11$:$59$pm

$6\mathrm{.}1$ Function declaration and call

fun name$1$ name$2$

Denotes a function declaration, i$.$e$.$ the start of a function called name$1,$ which has one formal

parameter name$2.$ The expressions that follow comprise the function body. The function body is

terminated with a special keyword funEnd. Note, name$1$ and name$2$ can be any valid name, but

will never be any of the keywords in our language $($e$.$g$.$ add, push, pop, fun, funEnd, etc.$).$ Also

the function name and argument name cannot be the same.

funEnd

denotes the end of a function body.

push funName

push arg

call

Denotes applying the function funName to the actual parameter arg. When call is evaluated,

it will apply the function funName to arg and pop both funName and arg from the stack. arg can

either be a name $($this includes function names$),$ an integer, a string, a boolean, or :unit:.

When the interpreter encounters a function declaration expression it should being construction

a closure. A closure will consist of $(1)$ an environment, $(2)$ the code for the function $($the expressions

between the function declaration and funEnd$),$ and $(3)$ the name of the formal parameter. The value

:unit: should be pushed to the stack once the function declaration is evaluated and the closure

created and bound to the function name in the environment.

$1.$ The environment for the closure will be a copy of the current environment. $($Challenge: if you

would like to optimize your closure representation you do not need the entire environment, just

the bindings of the variables used inside the function that are not defined inside the function

and are not the formal parameter$).$

$2.$ To compute the code for the function, you should copy all the expressions in order starting

with the first expressions after the function declaration up to$,$ but not including, the funEnd.

$3.$ In the current environment you should create a binding between the function name and its

closure.

$24$

When a function is called, you should first check to see if there is a binding in the current

environment, which maps funName to a closure. If one does not exist, push :error: onto the

stack. You should then check to see if the current environment contains a binding for arg if it is a

name instead of a value. If it does not, then you should push :error: onto the stack. If arg is an

:error: you should push :error: onto the stack.

If both funName and arg have appropriate bindings, or arg is a valid value, then the call to

the function can proceed. To do this, push the environment stored in the closure onto the stack.

To this environment add a binding between the formal parameter $1$ and the value of the actual

parameter $($i$.$e$.$ the argument$).$ Note that if arg is a name, then it must have a binding in the

environment at the point of the call $2.$ You should then save the current stack and create a new

stack that will be used for the execution of the function $3.$ Next retrieve the code for the function

and begin executing the expressions. The function completes once the last expression in code for the

function is executed. When this happens, you should restore the environment to the environment

that existed prior to the function call $4.$ The stack should also be restored to what the stack was at

the point of the call $5.$ Once the environment has been restored, execution should resume with the

expression that follows the call.

$6\mathrm{.}2$ return

Functions can return values by using a return expression. Since functions themselves are values

$($a closure$),$ functions can take other functions as arguments and can return functions. When a

return expression is evaluated, the function stops execution. When this happens you should restore

the environment to the environment that existed prior to the function call, just like if the function

completed by executing the last expression in the function$$s code. The stack should also be restored

to what the stack was at the point of the call. Additionally, you should push the last stack frame

the function pushed onto the restored stack $($the stack at the point of the call$).$

Please note that background color and indentation is used only to improve readability. Closure

would consist of code within colored background.

$1$you will extract the formal parameter from the closure

$2$this is the current environment before you push the closure$$s environment

$3$hint: you may want to implement the stack as a stack of stacks to handled nested function calls and recursion,

much like implementing the environment as a stack of maps

$4$hint: if you are implementing your environment as a stack of local environments, this will entail popping off the

top environment

$5$hint: if you implemented your stack as a stack of stacks, this only requires popping off the top stack to restore

the stack to what it was prior to the call