When we write programs such as card games, we have to be careful how we generate random events like the cards we deal. If we simply make calls to random and convert the result into one of, say, 52 cards, we have a problem: the program deals randomly from an endless supply of cards! If the random numbers come up just right, it could deal five 2s in a row, or five hundred 2s in a row. But we know that it should deal from a deck of 52 cards that contains exactly four 2s, four jacks, and so on.
A common solution to this problem is to write a procedure that creates a deck of, say, 52 cards. The deck might be stored in an array or a list. But now we have a new problem! The deck generator almost certainly produces the cards in a specific order, not randomly distributed. Now we need a procedure that shuffles a deck of cards.
Write the procedure named shuffle.
Suggestion: You might simulate the act of "riffling" two halves of the deck some number of times...
Let's take a look at a possible solution...
In the bonus reading after Session 12, we saw a merge procedure that put together two lists that were already in order. merge looked like this:
(define merge
(lambda (lon1 lon2)
(cond ((null? lon1) lon2)
((null? lon2) lon1)
((< (car lon1) (car lon2))
(cons (car lon1) (merge (cdr lon1) lon2)))
(else
(cons (car lon2) (merge lon1 (cdr lon2)))) )))
At the end of that section, I left you with a thought experiment: How could we merge lists that were in some order other than strict numeric < ? The answer was... "Think higher-order procedure."
Now that I have written riffle, I have a really good reason to solve that thought experiment, because riffle looks a lot like merge, with some randomness thrown in:
(define riffle
(lambda (lon1 lon2)
(cond ((null? lon1) lon2)
((null? lon2) lon1)
((< (random 10) 50)
(cons (car lon1) (riffle (cdr lon1) lon2)))
(else
(cons (car lon2) (riffle lon1 (cdr lon2)))) )))
We all know that repeated code is a bad idea, but how can we make this kind of repetition go away? In an OO language such as Java, we might use the strategy pattern to implement the test, and then supply every "merge object" with an appropriate test object.
In functional languages, we have higher-order procedures, so the strategy pattern becomes trivial to implement. The only difference between merge and riffle is in the way we make the choice between an item from the first list and an item from the second list. We could implement a procedure that computes the test condition -- a comparison strategy -- and then pass it as an argument to the procedure that uses it to merge two lists. Let's call the merging procedure merge-with:
(define merge-with
(lambda (selection-strategy lon1 lon2)
(cond ((null? lon1) lon2)
((null? lon2) lon1)
((selection-strategy lon1 lon2)
(cons (car lon1)
(merge-with selection-strategy (cdr lon1) lon2)))
(else
(cons (car lon2)
(merge-with selection-strategy lon1 (cdr lon2)))) )))
Of course, this procedure doesn't match the specification for either of our original procedures, so now we need to write a couple of interface procedures:
(define merge
(lambda (lon1 lon2)
(merge-with (lambda (lon1 lon2)
(< (car lon1) (car lon2)))
lon1 lon2) ))
(define riffle
(lambda (lon1 lon2)
(merge-with (lambda (lon1 lon2)
(< (random 100) 50))
lon1 lon2) ))
With higher-order procedures, though, we can do even better. Our new definitions for merge and riffle still repeat some code, because they require us to pass lon1 and lon2 to merge-with. Besides, merge and riffle aren't really procedures in their own right. Instead, they have to rely on another procedure to compute their answers for them.
Last time, we learned about a new tool, letrec, that enables us to create local recursive procedures. With a little Scheme-fu, we can use letrec to create exactly the higher-order procedure we need.
Our current solution relies on the ability to pass a procedure as an argument, but we also know how to return procedures as values. Maybe we could ask merge-with to give us an appropriate merging procedure based on a given selection-strategy:
(define merge-with
(lambda (selection-strategy)
(lambda (lon1 lon2)
(cond ((null? lon1) lon2)
((null? lon2) lon1)
((selection-strategy lon1 lon2)
(cons (car lon1)
(????? (cdr lon1) lon2)))
(else
(cons (car lon2)
(????? lon1 (cdr lon2))))))))
Notice the problem we have, though... What procedure do we call in the recursive step? The procedure that our code is creating! But that procedure doesn't have a name; it is a nameless lambda that we are building. It won't have a name until the procedure that calls merge-with binds its value to a name -- if at all.
This is the sort of problem that a letrec can solve: creating a local, recursive procedure and giving it a name. What differs from the ordinary way that we use letrec last time is that we do not intend to call the procedure from within its body -- we want to use the body of the letrec to return the local procedure as the procedure's value.
(define merge-with
(lambda (selection-strategy)
(letrec ((merge
(lambda (lon1 lon2)
(cond ((null? lon1) lon2)
((null? lon2) lon1)
((selection-strategy lon1 lon2)
(cons (car lon1)
(merge (cdr lon1) lon2)))
(else
(cons (car lon2)
(merge lon1 (cdr lon2)))) ))))
merge)))
Of course, we still need to define merge and riffle, but now we can do that as simple calls to merge-with:
(define merge
(merge-with (lambda (lon1 lon2)
(< (car lon1) (car lon2)))) )
(define riffle
(merge-with (lambda (lon1 lon2)
(< (random 100) 50))) )
The resulting procedures compute their values directly.
This approach involves the smallest amount of repeated code possible indefining merge and riffle: a call to merge-with with different arguments and no need to define new lambdas for each. It also means that later we will be able to create other merging procedures just as easily. All we need to do is to create the desired selection strategy (merging in descending order, random merges that favor longer lists, you name it) and pass it to merge-with.
Why is this problem relevant to our session today? Well, we are discussing the idea of syntactic abstractions, those features of a language that are convenient to have but that are not essential to the language. In the last few weeks, we have learned that a number of standard language features are really syntactic abstractions of more primitive features, including:
Today you learn that variable names are not necessary; they are really syntactic sugar. I'll support this claim by showing how a piece of code without explicit variable references can still convey the same information. You'll also learn how to do such lexical analysis of a program, as we prepare to write a program that manipulates variable names.
The scope of a variable declaration is the part of a program where that variable declaration is seen. If the scope of a variable can be determined at compile time (that is, statically) then the language is said to be statically- or lexically-scoped.
What is the difference between the region of a variable and the scope of a variable? We will study the distinction in some detail later. For now, the region of our Scheme identifiers (parameter names and local declarations) is identical to their scope.
If regions can be nested inside of each other, then we say that the language is block structured. These regions are called blocks. If a variable in one block is not visible because it has been re-declared within a nested block, we say that the "inner" variable creates a hole in the scope of the "outer" variable. We also say that the inner variable declaration shadows the outer one.
Consider the following Java-like snippet:
{ /* Block 1 */
int x = 4,
y = 0;
{ /* Block 2 */
int x = 3,
z = x + 1;
System.out.println( x + " " + z );
}
y = x + 1;
System.out.println( x + " " + y );
}
What is the value of x printed in Block 1? In Block 2? What is the value of y printed in Block 1? Of z in Block 2? These values follow from the fact that the declaration of x in Block 2 shadows the declaration of x in Block 1.
[ Sidebar: This is not legal Java, because Java does not allow a variable in a nested block to shadow a variable in the outer scope! We can simulate the same idea with a method-local variable that shadows an instance or class variable. See this simple test class. ]
Can we write a Scheme program with a similar structure? Certainly. We can use let to create blocks, though we will need let* to initialize our inner block properly:
(let ((x 4) ;; Block 1
(y 0))
(letrec ((x 3) ;; Block 2
(z (+ x 1)))
...)
...)
In both the Java example and the Scheme example, we can begin to see how the variable names themselves are unnecessary. Can we change the names? If so, what remains constant in how the variable bindings are determined? Each variable reference can be determined by what block the variable is declared in, along with the position of the declaration within the block. This is the idea of lexical addressing.
The lexical address of a variable reference gives the depth of the reference from the block in which the variable was declared and the position of the variable's declaration in that block. A lexical address can take the form (v : d p), where
We will treat depth and position as zero-based counters. That is, the depth tells us how many block boundaries we must cross to get from the variable reference to the declaration, and the position tells us how many steps we need to take down the list of local declarations to find the declaration.
For example, consider this lambda expression:
(lambda (x y) ;; Block 0
((lambda (a) ;; Block 1
(x (a y)))
x))
The reference to x in the last line is to the parameter x in Block 0, which is the first declaration in that block. That reference to x occurs in Block 0, too. So the address of that x has depth 0 and position 0, or (x : 0 0). The references to x and y in the third line are also to the parameters declared in Block 0. They appear in Block 1, but no declarations in that block shadow the original declarations. So the addresses of those references are (x : 1 0) and (y : 1 1), respectively. Finally, the reference to a in the same line is to the formal parameter of Block 1, so its address is (a : 0 0).
Determine the lexical addresses of the variable references in the following expressions:
(lambda (x) ;; Problem 1
(lambda (y)
((lambda (x)
(x y))
x)))
(lambda (f g) ;; Problem 2
(lambda (x)
(f (g x))))
((lambda (x) (x 3)) ;; Problem 3
(lambda (x) (* x x)))
(define x ;; Problem 4 ... sample usage:
(lambda (x) ;; > (x '(1 2 3))
(map (lambda (x) (+ x 1)) x)) ;; (2 3 4)
We could annotate the variable references in a lambda expression with each reference's lexical address. Consider the first lambda expression in the previous section:
(lambda (x y)
((lambda (a)
((x : 1 0) ((a : 0 0) (y : 1 1))))
(x : 0 0)))
This sort of annotation can be useful to a program that manipulates this expression -- say, an interpreter or compiler -- because the actual variable references are meaningless inside the machine. For example, a compiler needs to be able to compute the location of a referenced variable in memory so that it can write the addressing code into the assembly language it generates.
But can we go even one step further and remove the variable references altogether? Let's see...
(lambda (x y)
((lambda (a)
((: 1 0) ((: 0 0) (: 1 1))))
(: 0 0)))
Have we lost any information? No! The lexical addresses specify exactly which parameter is being used at each point in the computation. Given a lexical address, we can look up the associated variable name.
Very cool! But, as strange as this may sound, can we eliminate even the parameter names themselves? Let's see. We can replace the parameter list with a number that indicates how many parameters are declared:
(lambda 2
((lambda 1
((: 1 0) ((: 0 0) (: 1 1))))
(: 0 0)))
Have we lost any information? It depends whose perspective we consider.
The semantics of the expression -- its meaning when executed -- have been preserved. This must mean that variable names are syntactic sugar: we can translate any piece of code that uses names into a behaviorally-equivalent form that uses no variable names. Our examples here demonstrate the variable names really are a syntactic abstraction.
I remember my first encounter with this idea. It came in graduate school when I was learning to program in Smalltalk. I brought up a debugger on a block of code that had been compiled, only to find that all of my variable names and parameter names had been replaced with t1, t2, and so on. The debugger had to re-construct the code from its bytecode-compiled form, in which all identifiers had been replaced with lexical addresses. It could not re-create my identifier names, so it just created a sequence of unique symbols to put in their places. Not too surprisingly, the code behaved just the same anyway.
Ironically, the idea of lexical addressing also shows just how useful identifier names can be to programmers. Imagine having to read and write expressions of the above form! (I often feel equally disoriented reading some of your code... :-) Of course, these examples carry the "not-very-descriptive variable name" problem to its comic extreme. While these are extreme examples, try to remember that code with poorly-named variables can begin to look like this pretty quickly to readers who are inexperienced with your code or are otherwise unprepared to interpret the variable names. So, use variable names that are as descriptive as possible when you write your code, for the benefit of human readers, knowing that your interpreter or compiler will eliminate them from the internal representation of your code.
Quick Question: Why did I use numbers in place of the variable declarations? What do these numbers help me do or know?
Write Scheme expressions that are equivalent to the following lexical address expressions from which variable names have been removed:
(lambda 1 ;; Problem 1
(lambda 1
(: 1 0)))
(lambda (x) ;; Problem 2
(lambda (x)
(: 1 0)))
(lambda 3 ;; Problem 3
((: 0 1) ((lambda 2
((: 0 0) (: 1 0) (: 0 1)))
(: 0 2))))