MuLE Parameter Passing Lab[1]
The SLam Interpreter.
Knowledge DrScheme and the MuLE environment as well as familiarity with the theoretical distinctions between parameter passing methods.
Lecture or
reading covering parameter passing mechanisms.
This material is covered in any of the following references and is by no
means comprehensive.
Section 8.5
of Concepts of Programming Languages, 3rd Edition by Sebesta;
Section 5.2
of Programming Languages Concepts and Constructs, 2nd
Edition, by Sethi;
Section
7.3.1 of Programming Languages Design and Implementation, 3rd
Edition, by Pratt and Zelkowitz;
Section 5.4
of Programming Languages Structures and Models, 2nd Edition,
by Dershem and Jipping.
Chapter 5
of Programming Languages: Principles and Paradigms, by Tucker and
Noonan.
Chapter 9.1
of The Anatomy of Programming Languages, by Fisher and Grodzinsky.
To
understand the relationship between semantic models of procedure parameter
passing (“in”, “out” and “in out”) mechanisms and different possible
implementations. In particular, it
examines the differences between pass-by-value (an implementation of the “in”
semantic model), which is currently used in MuLE’s SLam language, and
pass-by-name (an implementation of the “in out” semantic model), which is to be
implemented.
In the pass-by-value implementation of the “in” semantic model an actual value is associated with its corresponding formal parameter. Whereas in the pass-by-name implementation of the “in out” semantic model, the formal parameter name is replaced with the actual parameter name throughout the procedure. Thus, pass-by-value essentially makes the formal parameter into a local variable for the procedure while pass-by-name makes the formal parameter into a variable that is global to the procedure. To make this more confusing, how the global is resolved depends on whether dynamic scoping or static scoping is used. In this lab we assume that dynamic scoping is used in SLam since this makes the code that deals with parameter passing easier to understand and implement.
To
understand how to implement pass-by-name, we must to review how the environment
is stored. Recall the environment is
stored as a list of name-value pairs.
Procedure calls cause a local environment to be created by creating a
list of local bindings (i.e., name-value pairs) and entering this list into the
global environment.
Currently,
the first bindings entered into the local environment are the bindings of the
formal parameters to the actual parameter values. For example, assume the following program.
(assign x 10)
(assign y 20)
(assign p1 (a) (* a 3))
(p1 x)
Just after
the call to p1 the environment would be
( ((a 10)) (x 10) (y 20) )
The local
environment ( (a 10)
) is created and the
formal parameter, a, is bound to the value of the
actual parameter x, (i.e. the value 10).
To change
the parameter passing mechanism to pass-by-name there must be some way of
indicating that formal parameters are bound to the name of the actual
parameter and not its value. The
approach described replaces the formal-actualValue binding pair with a
formal-actualName binding pair. Instead
of the ( (a 10) ) local environment in the previous
example, we would have the ( (a x) )
local environment instead.
It is not difficult
to modify the local environment created in the pass-by-value implementation to
the pass-by-name implementation.
Currently (in the pass-by-value implementation) the local environment is
created when a procedure call is evaluated by the interpreter. At procedure evaluation, the actual
parameters’ values are retrieved from the environment and are associated with
the corresponding formal parameters’ names in the local environment. To implement pass-by-name instead, the
interpreter must recognize that an actual parameter is a variable name and,
instead of associating its value with the formal parameter, must associate the name
of the actual parameter with the formal parameter. This is explained in more detail in section phase 1.
Because the
format of the local environments changes, the interpreter must also change the
way that it looks up and reassigns variable’s values. In the pass-by-value implementation, the interpreter looked for
the variable in the appropriate environment and returned or changed its
associated value. However, in a
pass-by-name implementation, the interpreter must recognize if the associated
item in a binding pair is a name or a value.
If it is a value, then the variable is not a parameter. If it is a name, the search is not over; the
interpreter must look in the environment of the calling procedure for the “new”
name. One difficulty is the actual
parameter used in the calling environment might itself have been a formal
parameter, so the process could continue.
Eventually, however, a name-value binding will be found and the value
can be changed or returned as appropriate.
This is explained in more detail in phase 2.
This lab
requires modification of the SLam interpreter to implement pass-by-name as its
default parameter passing mechanism.
Every parameter will automatically be passed by name. Currently the interpreter uses pass-by-value
exclusively. Dynamic scoping is
currently implemented in the interpreter and should remain.
Phase
1. Associating actual and formal
parameters
In SLam
when a procedure is called or applied actual parameters must be associated with
formal parameters. In the interpreter
implementation, the parser recognizes a procedure application and creates a
variant record called apply and places it into the parse
tree. It creates two variables, proc
and args, and then calls apply-proc to evaluate the procedure proc
with its args in theEnv.
To create
the variable proc, the operator contained in the apply variant
record is executed. If the operator
name is a user-defined procedure (variant record type proc), then a closure
is created by the execute function.
This closure will contain the formal parameters and the body of
the procedure.
The args
variable also created when the execute function recognizes an apply
variant record. The value bound to the args
variable depends on the type of the proc variable (which has just been
created). If the proc is a closure
(in the case of a user-defined procedure), then the function eval-opnds
is called and passed the actual parameters.
Eval-opnds evaluates (by calling execute) each of the
actual parameters and returns a list of their values. This list is then bound to the args variable.
In the
current pass-by-name implementation, procedure eval-opnds consists of a single line:
(map2 execute opnds env)
The
function map2 is defined in the utilities.s file and is a simple extension of
the built-in scheme function map. In the line above, map2 calls the function execute once for each item in the list opnds (the list of actual parameters)
passing along the current environment env. The results of these calls are gathered into
a list and returned.
This is the
appropriate approach for a pass-by-value parameter implementation. After all, the values of the actual
parameters are what must be retrieved.
If pass-by-name is implemented, however, we do not want the
values of the actual parameters, we want to associate their names with
the formal parameters. Thus, if an
actual parameter is a variable (which is represented by an ID variant
record in the interpreter), the variable’s name should be returned not its value.
Phase one
requires modification of eval-opnds
so that it returns the name of the actual parameter if the actual parameter is
an ID variant record and to generate an error otherwise. An error is generated because every
parameter in the interpreter must be pass-by-name and it makes no sense to pass
anything other than a variable.
[Note to the instructor using this lab, instead of creating an error if a value is the actual parameter, you could require the following and slightly more difficult implementation:
Phase one
requires modification of eval-opnds
so that it returns the name of the actual parameter if the actual parameter is
an ID variant record and to call the function execute in all other cases. The ID variant record must be
recognized and, in this case, return the name associated with the record
instead of calling execute.]
Phase
2. New lookup required
This new
way of binding formal parameters requires a new method of looking up and
changing the values of variable bindings.
There are two functions in the SLam interpreter that perform look up and
modification operations, enter-env,
a function that enters new bindings into the environment or changes bindings,
and get-val, a function that looks up bindings
in an environment. Both of these
functions are found in the file named dynamic.slam.
The
function get-val uses a helper function, retrieve-val, to recursively look through an
environment (passed in the parameter env) for a binding for the parameter name. (Note: name is a parameter to the function get-val but not to retrieve-val.
This will become useful later in the helper function when pass-by-name
is implemented.)
Retrieve-val searches the global environment for
the name.
If retrieve-val comes across a local environment (a list of lists),
then it will call checkLocal to determine if name is bound in the local
environment. This function checkLocal returns #t if it finds name in the local environment and #f
otherwise. If name is found in the local
environment (i.e., checkLocal returns #t), then retrieve-val calls the function getLocal to return the value bound to name.
If the
first item in the environment is not a local environment, it must be a
name-value binding in the global environment.
Since names can only be bound to values in the global environment, retrieve-val needs to examine the first item in
the name-value pair to determine if the name part of the binding matches the name that we’re looking for. If it does, retrieve-val is done and returns the
corresponding value. Otherwise, it
searches the remainder of the environment.
The
function checkLocal recurses through the local
environment that it is sent until it either finds a binding pair that contains name or reaches the end of the
environment. The function first checks
the environment theEnv to see if it is empty. If it is empty, then we obviously did not
find name in the local environment, so checkLocal returns #f. If theEnv is
not empty, checkLocal must check the first binding in theEnv to see if the name (the first item
in the binding) is the same as name. If it is, the value #t is returned.
If it is not, then checklocal
is recursively called
and is passed the environment with the first item (that was just searched)
removed.
To change get-val
so that it recognizes pass-by-name bindings, we only have to change how we
search the local environment (global variables cannot be bound to names), thuse
we only need to modify the functions checkLocal and getLocal.
must now examine the item in the value position in the name-value
binding when name matches the name in the name-value
binding. Previously, checkLocal could just return #t if name matched the first item in the first binding of its list. Now, checkLocal must examine the corresponding value and decide
whether it is a symbol or a value. If
it is a value, checkLocal can just return #t as before.
If the
associated value is a symbol, the software engineer must decide what to
do. At this point either checkLocal must change the name that is being searched for (recall that name is
global to checkLocal) or it must notify retrieve-val that it has found a symbol so that retrieve-val can search for the new name. With either approach, retrieve-val must search the remaining
environment for the new name.
Phase
3. One more thing to consider
There is
one last place where the change to pass-by-name affects the interpreter
code. The function enter-env is where the interpreter changes the value that a
variable is bound to. This code is
found in the file dynamic.slam.
This is straightforward to change if dynamic scoping rules are followed,
but more complicated when static scoping rules are followed. To reiterate, this lab assumes dynamic
scoping rules are followed.
There are
several local functions used in enter-env, but the most important to understand for this parameter
lab is change-val.
The function change-val uses a function checkLocal to search and change a local
environment. Only the latter function
must be changed to implement pass-by-name parameter passing when dynamic
scoping is used.
The
function enter-env simply calls the function change-val.
The change-val function works in an analogous
fashion as the function retrieve-val
from phase 2. It receives only one
parameter, an environment called theEnv, and it works by recursively searching through the environment one item
at a time. The function uses two
variables, var and value, defined externally to the
function. These values are the (var val) binding (in other words, the
name-item pair) we are entering/changing in the environment. They are passed into the procedure enter-env as a pair and are set in a letrec statement of that procedure.
It is
useful to understand how the function change-val works to understand what code must be changed in the
function checkLocal.
The function change-val examines the first item in the
environment to see if var is bound in that item. The first thing change-val does, is to check to see if the
environment is null. If it is null, the variable we are searching for
was not found in the environment.
Next, the
function, change-val checks to see if the first item is
a local environment (i.e., is a list of lists). If it is, then the code calls the function checkLocal to determine if the var is
in the local environment. CheckLocal works exactly the same as the checkLocal function used in the retrieve-val function from the last
section. The changes that you will need
to make are the same as the changes that you made in the previous checkLocal function.
If checkLocal returns #f,
then the rest of the environment must be checked by change-val for the var. Note that, depending on how you change checkLocal, the var variable may be changed (for
example, if checkLocal finds name bound to a symbol in the local
environment, it could change the binding of var). Since change-val must return a modified environment,
it must cons the car of the environment onto the result
of the search of the cdr
of the environment.
If checkLocal returns #t, then var is bound to a value in the local environment. In this case, change-val
calls the function changeLocal, passing it the local environment. ChangeLocal appropriately modifies
the local environment and returns the resulting new local environment. Change-val must cons this
new local environment onto the rest of the environment and return the result.
If change-val determines that the first item in
the environment is not a local environment, then the item must be a
name-value binding. If var is the same as the name in this
binding, then the name must be bound to the new value and the resulting
name-value pair must be cons’d into the rest of the environment
and the result returned.
If var does not match var, then the old name-value binding
must be cons’d onto the result of a recursive call to change-val with the first binding removed.
The faculty
member using this lab should fill in the details for project submission and
perhaps grading details.