Knowledge DrScheme and the MuLE environment.

An understanding of how different results may occur when the only change in the language is whether it is statically or dynamically scoped. An understanding of how the SLam environment is implemented.

Language scoping rules determine how an occurrence of a name is associated or bound to a variable. This determination is important only when the references to the variables are outside of the executing block. There are two methods of determining nonlocal access, static scoping and dynamic scoping. The concept of dynamic verses static scoping is concerned which set of rules to apply when finding a binding to a variable and/or changing a value bound to a variable. Additional complications arise depending on the parameter passing mechanism in use. For the current discussion, we assume the pass-by-value method.

In either scoping mechanism, the search for a variable begins in the local environment, that is, in the currently executing program, block, procedure or function. In the simple local variable case, static and dynamic scoping are identical, the local binding is used and/or modified. It is in the nonlocal variable case that the variable must be found in some external environment. Which set of scoping rules followed determines the exact environment or order of environments searched.

Dynamic scoping rules depend on the calling sequence of the (sub)programs and requires searching the executing subprogram’s dynamic parent, i.e., the calling environment first. Whereas, static scoping rules depend only on the static structure of the program and therefore requires searching the executing subprogram’s static parent, i.e., the defining environment first. Although dynamic scoping is not commonly used in recent languages, APL, SNOBOL4 and early versions of LISP employ dynamic scoping. The real motivation, however, in changing the scoping mechanism in an interpreter is we gain deeper insight into how scoping is implemented.

The interpreters used in MuLE handle the environment, or name space, in the same manner. Every declared variable is stored in a list as a name-value pair. In SLam, variables are declared implicitly when bound to a value. Whereas in SPoc, variables must be declared explicitly before use. In either case, the first time the interpreter encounters a variable, its name is placed into a list with a value (either the default value 0, as in SPoc or the value in the assignment, as in SLam). This list, containing the name-value pair, is placed into the list holding all program bindings.

For example, if the first variable binding encountered in a SLam program was the assignment

(assign x 5)

(assign y 7)

This environment is global because any definition is visible to any statement in the program. Both SLam and SPoc allow local environments to be defined in addition to the global environment. Because procedural or imperative languages are block-structured it is natural that SPoc allows blocks, i.e., segments of code that include local definitions. SPoc’s blocks can be nested. SLam includes procedures, i.e., segments of code that can be called from other places in the program. These two mechanisms both allow for nonlocal declarations, procedures highlight the differences between scoping rules. Following the dynamic chain to resolve a variable binding may be very different from following the static chain.

To simplify SLam’s environment (and make our task easier) procedures cannot be nested. The programming language, C, is restricted in this way. The gain is every procedure’s static scope is identical, i.e., every procedure is defined in the global environment and thus, has the same static parent.

Like variable names, names of procedures must also be entered into the environment. In SLam, a procedure is similar to any other binding except that its value is the parse tree of its code. This lab does not require entering procedures into the environment, but does require recognizing procedure bindings. Because procedures cannot be nested, every procedure binding is entered into the global environment.

When procedures are called, a new binding type needs to be created. When a procedure is called, any variables declared will take precedence over global bindings. In other words, a local environment is created. Therefore, the procedure’s local environment must be checked first for variables referenced within the procedure.

SLam’s local environment, like its global environment, is a list of variable name-value pairs. A local environment is created when a procedure is called. The procedure’s parameters are the first name-value pairs entered into the environment. (Recall, for simplicity in this lab, all parameters are pass-by-value. The "copy in" semantics calls for the actual argument’s value to be copied to the formal parameter, which in effect is a local variable that is bound at the time of the procedure call.) Local environments are added to the front of the queue when the procedure is called. (In this way we can view the added environments as a stack of environments, much like adding activation records to the run-time stack.) This will make scoping easier. Variables within the local environment are added to the back of the queue. So when adding a variable we view the list as a queue, but when adding an environment we view the list as a stack. (The example below should clear this up if it doesn't make sense.)

In summary, there are two types of entries in the environment to consider in SLam, global variable bindings (regular variables or procedure names) and local environment created by procedure calls. As an example, consider the global environment defined earlier,

( (x 5) (y 7) )

( (x 5) (y 7) (p1 #def-1) )

( ( (x 7) ) (x 5) (y 7) (p1 #def-1) (z 12 ) )

( ( (x 7) (y 30) ) (x 5) (y 7) (p1 #def-1) (z 12 ) )

( ( (x 7) (y 19) ) (x 5) (y 7) (p1 #def-1) (z 12 ) )

Currently dynamic scoping rules are implemented in SLam. This lab requires you to implement static scoping rules in SLam instead. This will neither affect the parsing of a SLam program or the execution of SLam programs. However, this modification will affect how variables are looked up and changed in the environment.

If the first item is a list, that environment must be recursively searched. If the name we are searching for is in that environment, we are finished. Otherwise, we must continue to search the environment after popping the first item (the local environment that we just searched) off the environment stack. How this search proceeds is the difference between implementing static scoping versus dynamic scoping. If the next item is not a list, then no change is needed as static rules and dynamic rules would produce the same result. But if the next item on the stack is a list which would represent a local environment (due to a procedure call) then changes to the implementation must be made. Local environments are entered in the order in which the corresponding procedures are called, and the next local environment represents the procedure that called the procedure whose environment was just searched. If dynamic scoping rules were to continue to be followed, this is would be the correct environment to search next. Since static scoping rule implementation is the goal, this must change. The global environment must be searched instead because in following static scoping rules, the static (declaring) parent must be searched for a name rather than the dynamic (calling) parent. Since we have the restriction that procedures cannot be nested, the static (declaring) parent is in fact the global environment.

The overall structure of this function is similar to the structure of get-val. The function receives two parameters, a name-value pair and an environment. There are several helper functions, but the principal function is change-val. This function receives the old environment and returns a new environment with either the name-value pair replacing the value of the old name-value pair (if the name was already in the environment) or the name-value pair added (if the name was not in the environment).

The function change-val recursively searches through the environment, taking the environment list apart one element at a time. If the end of the environment is reached and the name has not been found, then the name-value pair is returned (which results in it being added to the end of the environment once the recursion has unwound). If the environment is not empty and the name is not in the first item in the list, then change-val concatenates the first item with the result of a recursive call that passes the environment with the first item removed. In this manner, the environment list is taken apart one item at a time and then put back together one item at a time.

As in the procedure get-val, there only two possible scenarios, either the first item in the environment is a list of lists (i.e., a local environment) or a name-value pair. First, the function change-val must determine if the list is a local environment. If the first item in the environment is itself a list, then it is a local environment and change-val calls another locally defined function, checkLocal (described below).

If the first item is a local environment, then checkLocal is sent the local environment and returns #t or #f, depending on whether the name was found in the local environment. If it was, then changeLocal is called to change the value. If not, then change-val must continue the search. In the current form of change-val, which uses dynamic scoping, change-val merely begins searching at the next item in the list. It does this by considering the first item in the list (the local environment that was just searched) with a recursive call, passing the environment with the first item removed as the parameter.

Static scoping, however, cannot simply remove the local environment and recurse. Since the only blocks or local environments in SLam are procedures, a variable that is not defined in a procedure must have been defined in global environment according to static scoping rules. Thus, change-val must, at this point, skip over all of the local environments and search the global environment to implement static scoping correctly.

Under dynamic scoping rules, the function p1 returns 30 and the function p2 returns 9 in the SLam program named staticvdynamic.slam, whereas under static scoping rules, both p1 and p2 return 30.

staticvdynamic.slam:
(assign y 10)
(assign p1 (proc (x) (* x y)))
(assign p2 (proc (y) (p1 y)))
(p1 3)
(p2 3)

Under either static or dynamic scoping rules, the function p1 returns 8 and the function p2 returns 20 in the SLam program named staticvdynamic1.slam.

staticvdynamic1.slam:
(assign x 5)
(assign y 10)
(assign z (+ x y))
(assign x 2)
(assign p1 (proc (a) (* a x)))
(assign p2 (proc (b) (p1 b)))
(p1 4)
list
(p2 10)
list

staticvdynamic2.slam:
(assign y 10)
(assign x 0)
(assign p1 (proc (x) (* x y)))
(assign p2 (proc (y) (p1 y)))
(p1 3)
(p2 3)
(assign x (p2 3))

// Static:
// p1 returns 30, p2 returns 30, assign returns 30

// Dynamic:
// p1 returns 30,p2 returns 9, assign returns 9

staticvdynamic3.slam:
(assign x 5)
(assign y 10)
(assign z (+ x y))
(assign x 2)
(assign p1 (proc (a) (* a x)))
(assign p2 (proc (x) (p1 x)))
(p1 4)
list
(p2 10)
list
// Static: p1 returns 8, p2 returns 20
// Dynamic: p1 returns 8, p2 returns 100

staticvdynamic4.slam:
(assign y 10)
(assign x 0)
(assign z 7)
(assign a 5)
(assign p1 (proc (z) (assign y a)))
(assign p2 (proc (y) (p1 y)))
(assign p3 (proc (a) (p2 a)))
(p3 z)
list

// Static: y ends with the value 5
// Dynamic: y ends with the value 10

staticvdynamic5.slam:
clear
(assign x 5)
(assign y 10)
(assign z (+ x y))
(assign x 2)
(assign p1 (proc (a) (assign x (* a x))))
(assign p2 (proc (x) (p1 x)))
(p1 4)
list
(p2 10)
list
// Static: p1 returns 8 and the value of x
// becomes 8 in the first list
// p2 returns 80, x has value 80
// in the final list
// Dynamic: p1 returns 8, p2 returns 100,
// x has value 8 in the final list

Sample tests for Optional Step 3