CSE 341 - Autumn 2005 - Homework 5

Smalltalk is an unusually flexible language in the power it gives to the programmer to define new control structures, to add functionality to system classes, and to redefine the meaning of basic syntactic constructs such as the + operator. The purpose of this assignment is to have you explore these features.

Please see updated Turnin directions (at the bottom of this web page).

1. Defining a New Control Structure. Most languages (except purely functional ones) include a while loop. Some languages also define another indefinite loop, the repeat-until loop. The syntax is something like:

   repeat statements until test;
   

   The semantics is that the statements (the body of the loop) are executed. Then the test is evaluated; if it evaluates to true, the loop terminates. If the test evaluates to false, the statements are executed again, and so forth. So the differences from a while loop are the order between test and the body of the loop is reversed; and also that the body is always executed at least one time.

   Smalltalk doesn't have a repeat-until loop built in, but it's easy to define one. Do so, and demonstrate that it works correctly.

   Hint: you will want to define a new method called repeatUntil: in the class BlockContext. For example, after executing the following code the numbers 6, 7, 8, 9 will be printed to the transcript.

   | j  |
   j := 5.
   [j:=j+1.  Transcript show: j printString.  Transcript cr.] 
     repeatUntil: [j>8]
   

   As another example, to show that the body of the loop is always executed at least once, the following will print 6 on the transcript, even though the value of the test is always false.

   | j  |
   j := 5.
   [j:=j+1.  Transcript show: j printString.  Transcript cr.] 
     repeatUntil: [j>0]
   

   Deliverable: include your repeatUntil: method in your change set, and write a 'test' method for BlockContext that shows your loop in operation.
2. Adding Dynamic Scoping to Smalltalk. Like most other modern languages, Smalltalk is lexically scoped. A number of older languages, for example the original version of Lisp, were instead dynamically scoped. (See the 341 glossary for definitions of static and dynamic scoping.) It can still be useful to provide the option of dynamic scoping in a modern language, even though the default mechanism is lexical scoping. For example, suppose you have a variable debugging. Suppose also you want to set debugging to true while evaluating a piece of code, and then reset it to its old value afterwards. You could pass debugging as a parameter through all calls in your program, but this is clearly inconvenient. Or you could make it be a global variable, set it to true, and then restore its old value after the computation is done -- but that won't work correctly if there are multiple processes with different values for debugging; and also, if the computation is interrupted somehow, the old value won't be restored.

   Dynamic scoping provides a nice solution for handling such situations. For example, you can make debugging be a dynamically scoped variable, and bind it to true before evaluating the piece of code in question. Smalltalk doesn't have dynamic scoping built-in, but (in contrast to nearly all other languages) you can implement it yourself in Smalltalk.

   The article "Defining New Control Structures in Smalltalk-80", by L. Peter Deutsch, which appeared in the August 1981 issue of Byte Magazine, describes how to implement dynamic scoping in Smalltalk. A copy of the relevant parts of the article will be distributed in class on Monday, or here is a scanned copy (pdf format). (I was going to ask you to figure out how to implement dynamic scoping yourself -- but decided it was a bit too tricky. Those wanting a challenge are still welcome to do so!)

   Your task for this problem: implement dynamic binding in Smalltalk (using the code in Deutsch's article), and then demonstrate convincingly that your code is working correctly. In particular, in addition to simply finding the binding of a dynamically scoped variable, you should demonstrate how one binding can shadow another.

3. Symbolic Differentiation. For this question, you should define a number of new Smalltalk classes, along with new methods for existing classes, to implement a small system for symbolic differentiation. Recall the rules for differentiation involving constants, variables, addition, and multiplication from your basic calculus class:
   • the derivative of a constant with respect to x is 0
   • the derivative of variable y with respect to x is 1 if y=x, and otherwise 0
   • deriv (e1+e2) dx = deriv e1 dx + deriv e2 dx.
   • deriv (e1*e2) dx = e2*(deriv e1 dx) + e1*(deriv e2 dx).

   Implement the system in two stages.

   First, implement a class SymbolicExpression, with subclasses SymbolicVariable, and BinaryExpression. BinaryExpression should have two subclasses itself: Addition, and Multiplication. Define methods deriv: and printOn: for these classes, as appropriate. Also add a deriv: method to the built-in class Number. SymbolicExpression won't have any functionality in this simple implementation. For this class, the bodies of your methods will just be self subclassResponsibility. This is the standard way in Smalltalk to document methods that should be overridden in subclasses. (Even though SymbolicExpression doesn't have any useful methods at this point, structuring your code well is likely to pay off later if you extend it -- and indeed, if you do the second optional question, you'll make use of this decomposition.)

   Be sure and factor other parts of your code well -- for example, factor out common parts of Addition and Multiplication that belong in BinaryExpression. (This amount of class and subclass definition may seem like overdoing it for this simple system, but we're practicing ...)

   You should now be able to test code such as:

   | x y e1 e2 |
   x := SymbolicVariable name: 'x'.
   y := SymbolicVariable name: 'y'.
   e1 := Addition exp1: x exp2: 3.
   e2 := Multiplication exp1: e1 exp2: x.
   e3 := Addition exp1: 20 exp2: (Multiplication exp1: 3.14 exp2: y).
   
   x printOn: Transcript.  Transcript cr.
   e1 printOn: Transcript.  Transcript cr.
   e2 printOn: Transcript.  Transcript cr.
   e3 printOn: Transcript.  Transcript cr.
   (x deriv: x) printOn: Transcript. Transcript cr.
   (3 deriv: x) printOn: Transcript. Transcript cr.
   (e1 deriv: x) printOn: Transcript. Transcript cr.
   (e2 deriv: x) printOn: Transcript. Transcript cr.
   (e3 deriv: x) printOn: Transcript. Transcript cr.
   

   This should print the following. (You can have more or less parentheses; and use spacing in expressions as you wish -- it's the value of the expression that matters.)

   x
   (x+3)
   ((x+3)*x)
   (20+(3.14*y))
   1
   0
   (1+0)
   ((x*(1+0)) + ((x+3)*1))
   (0+((y*0)+(3.14*0)))
   

   Next, implement a simplify method in each of your expression classes, as well as in Number. This should implement the following simplification rules:
   • for constants j and k, j+k simplifies to the result of adding them (e.g. 3+4 simplifies to 7)
   • for constants j and k, j*k simplifies to the result of multiplying them (e.g. 3*4 simplifies to 12)
   • for any expression e, e+0, or 0+e, simplifies to e
   • for any expression e, e*0, or 0*e, simplifies to 0
   • for any expression e, e*1, or 1*e, simplifies to e
   Now, if you find the derivatives as above and then simplify, you should get more reasonable-looking answers. For example, (e1 deriv: x) simplify should evaluate to 1, (e2 deriv: x) simplify should evaluate to x+(x+3), and (e3 deriv: x) simplify should evaluate to 0.0 (or to 0).

   Both the deriv: and simplify methods should have no side effects -- they just return new objects (or for simplify, just return the receiver if no simplification is possible).

   Hint: do simplification recursively. For example, when finding the simplified version of an addition, first find the simplified version of its components (exp1 and exp2), then simplify the result.

4. Extra Credit Part 1: Some further simplication of the results from the symoblic differentiator is possible -- for example, (e2 deriv: x) simplify ought to produce 2*x+3. Or as another example, 2+x+5 could be simplified to x+7. Come up with a set of additional rules for simplication, and implement them. (Hint: you may want to change the class Addition, for example, to have a set of expressions that are being added, rather than just two expressions.)
5. Extra Credit Part 2: inputting expressions for symbolic differentiation is tedious. However, by defining + and * for SymbolicExpression, you can write the above example in a nicer form:

   | x y e1 e2 e3 |
   x := SymbolicVariable name: 'x'.
   y := SymbolicVariable name: 'y'.
   e1 := x+3.
   e2 := e1*x.
   e3 := 20+(3.14*y).
   

   What about e3? Here 20 is getting the message +, and 3.14 is getting the message * -- what should we do? This turns out to be not that difficult -- you just need to define the methods adaptToInteger:andSend: and adaptToFloat:andSend: in SymbolicExpression. (Study the number hierarchy, such as the implementation of + and * in Float, to see how these methods are used to implement coercion among different kinds of numbers.)

Turnin (updated directions)

Please just include code for this assignment in the change set. If you have a copy of Squeak with old changes you don't want, you can pick "create new change set" from the changes menu to start a fresh one. Or open a change sorter, and delete the old changes you don't want included.

Also, to cut down on the number of workspace files to hand in, please write a "test" method in the class BlockContext, Binding, and SymbolicExpression that comprehensively tests your answers to questions 1, 2, and 3. Make these class methods, not instance methods (just select the 'class' button on the browser to do this). Your method should include (in a comment) an expression to run it, for example

"Binding test"