03:31 pm, 22 Apr 04
fold
I just wrote this to the class list about fold. I'm never sure which parts are clear and which aren't, but the few students I've talked to seemed to understand things better once they saw the picture.
I have had a lot of questions about the "fold" part of the homework and what an "accumulator" is. The idea of a fold is that you want to apply some function to each element of some collection. In this assignment, the collection we're working with is the set of variables in a formula. The part that's hard to get initially is how fold can be useful when we aren't using side-effects (mutation, printing, etc.). Your intution would be to write code such that, for example, on an "And" formula we apply the function "f" first the left side and then to the right side-- but how do you put those two together? If f has no side effects, then you must use its return value in some way; otherwise there was no reason to call it in the first place! This is what we use an accumulator for. It's the thing that the /user/ (in Dan's terms, "client") of the fold function uses to track whatever it is they're doing with the variables in the formula. So they give an initial accumulator, and then the function they pass takes in an accumulator and gives back a new, potentially changed, accumulator, and fold keeps running that over all the variable and finally returns the last accumulator. To emphasize: we don't ever "change" the accumulator; we just hand it to f, which gives us back a new one, which we repeat the process with. The name "accumulator" is a bit misleading in that respect. I've found some students have been helped by seeing a picture. Please excuse my art ability: http://www.cs.washington.edu/education/courses/cse341/CurrentQtr/section/fold.png I drew the function as a box that takes its inputs on the left and has its output come out the right. You'll notice that the fold function itself makes no use of the accumulator; it merely passes it through each call to the function. I've marked all the arrows that carry the accumulator around with two little lines across them so you can see that for yourself. For that reason, the accumulator can be of *any type*, as long as it is the same type as the function inputs and outputs. In SML we write that with a 'a, pronounced "alpha" or "tick a", and it was chosen just because it is the first letter of the (Greek) alphabet. The fact that it starts with the same letter as "accumulator" is just a coincidence.
Get with the century, old man ;^P (yes, i know smalltalk was years and years ahead of its time, and i've never heard anything but good about it. I haven't learned it yet because i'm lazy. I just feel like giving you a little crap now and again, all because of your "amish" comment ;^)
Actually I learned Smalltalk-72 first. (Well, I read the manual, though I never actually used it. My first taste of OOP, and dynamic languages, and GUIs.)
I don't think there's anything that special about ST80 by today's standards. The graphics/windowing system was laughably primitive, and the language doesn't have much that today's hep scripting languages don't have, especially Ruby.
There's this newer thing called Squeak that's like a slightly-modernized ST80; but as far as I can tell, it's interesting mostly for nostalgia value, like a Flock Of Seagulls reunion tour.
I really can't think of a good way to explain this without falling back on the accumulator-register/retval-variable model of an accumulator.
I think i would introduce alpha as the "variable type" concept, but maybe your students just aren't that "with it?"
for example, your fold_vars function is a very specific fold, replacing all the Var terms with a user-provided function and presumably replacing all other terms in the tree with a composition operator (right branch of And uses result of left, I'm guessing).
you make your user-provided function take an extra value so that the user can thread an accumulator through the composition; but you will need to write such a fold for every possible family of traversal (eg. what if you want to visit Var nodes and And nodes?). a more general fold would take a function argument corresponding to each constructor in your formula type, and combine results however the user likes. that would let users replace for example all the leaves of the formula with sets, and all the other nodes with set union.
I think the use of "list folds" in haskell / ML standard libraries damages people's perception of folds in general, because they come to think of them as only representing a single value propagation during a left-to-right or right-to-left traversal (foldl and foldr). this is because lists are simple linear structures with only one leaf and only two sensible traversal directions, so replacing CONS with some ('a * 'b -> 'b) function and NIL with some 'b value sort of makes the "accumulator" intuition work. but that intuition hides intuitions about more general folds.