Currying in Smalltalk, part 2

In the first part we changed the behavior of the value: protocol of blocks to support currying. That changes the existing behavior of the system, making it possible for those messages to answer a block instead of a “real” value. Is that a problem?

One could argue that the new behavior comes into force only in the situations where the original system would signal an error anyway, so if it falls over because of getting a block it didn’t expect, it would still have fallen over in the old system because of the number of arguments mismatch. On the other hand, what if it doesn’t fall over immediately after it gets that unexpected block? It is possible for the new behavior to mask an error and make it difficult to find its cause later. Also, some might not like this kind of a change on the familiarity grounds. Gilad was the one who got me on the track of playing with currying, and for these reasons he suggested that it might be a good idea to keep value: and friends intact and introduce a different evaluation message that would allow currying–something like curry:curry:.

A similar in spirit approach, but one that gives us the best of both worlds, is to introduce a unary message curried used as a prefix to value: to indicate that currying is allowed. The example from the previous post then becomes

| add inc |
add := [:a :b | a + b].
inc := add curried value: 1.
(inc value: 2) + (inc value: 3)

This both preserves the familiar evaluation protocol and declares that currying is possible. To implement this, unlike in the Part 1 version, we leave valueWithArguments: unchanged from its standard implementation. Instead, we introduce a new class called Currier with an instance variable block and an initialization method block:, and add the following method to the block class (either BlockContext or BlockClosure, depending on the Smalltalk dialect):

curried
    ^Currier new block: self

This injects a Currier into the message stream as add curried value: 1 is evaluated, so that the value: message is received by the Currier. To process it, the Currier needs to invoke the original block if there are enough arguments to do so immediately, or create a CurriedBlock otherwise:

value: anObject
    block numArgs = 1
        ifTrue: [^block value: anObject].
    block numArgs > 1
        ifTrue: [^CurriedBlock new block: block arguments: {anObject}].
    self error: 'Incorrect number of arguments'

The above assumes that an expression such as {anObject} creates an Array with anObject, as in Squeak or in VisualWorks with my BraceConstructor extension.

Other value:... protocol messages are implemented similarly. Also, the CurriedBlock class should implement the same curried method as “real” blocks do–curried blocks are no different from regular ones, so they can be “re-curried”. (In Part 1 we would get such re-currying for free).

10 Responses to “Currying in Smalltalk, part 2”

  1. Travis Griggs says:

    So while this is really cool… what’s it good for Vassili? I’m asking a leading question here. :)

    I think currying remains a term reserved to “computer theory geeks.” Doing 3 + 4 in a way that looks like (2 + 1) + (3 + 1) -> 7 is lost on the unwashed masses. It’s like telling people that Seaside is cool because it’s based on continuations, and leaving it at that. So how ’bout a “chapter 3” showing a case where the how to use this for normal programming is illustrated by example?

  2. Vassili Bykov says:

    Yep, you are onto something here, and there will be chapters 3 and 4 at least. :) I’m now in a middle of a move though, so I can’t promise a chapter a day…

  3. Björn says:

    What comes to my mind is
    If you want to define derivation by means of blocks you can do it as follows:
    df := [:f :x :h | (f value: x + h) – (f value: x) / h].
    func := [:x | x ** 3].
    df value: func value: 4711 value: 1000000 reciprocal

    Or you can use some kind of more explicit cyrrying (if one should call it currying…)
    curry := [:f | [:x :h | (f value: x + h) – (f value: x) / h].].
    cyrryDf := curryvalue: [:x | x ** 3] .
    cyrryDf value: 4 value: 100000000000 reciprocal

    In this way the add example in the text could be written
    | add inc |
    add := [:x | [:a :b | (a + x) + (b + x)]].
    inc := add value: 1.
    inc value: 2 value: 3

    Of course one has to bind both a and b simultaneously.
    Or rewrite the thing as
    | add inc |
    add := [:x | [:a | [:b | (a + x) + (b + x)]]].
    inc := add value: 1.
    inc := inc value: 2.
    inc value: 3

    Any comments on these more explicit alternatives?

  4. Vassili Bykov says:

    The alternatives show very well what currying (or in fact, multi-argument functions and their applications in general) is all about. If you imagine a system where blocks can only have one argument, you could implement multi-argument blocks by nesting, just like in your last example

    [:a1 :a2 … aN | …] => [:a1 [:a2 [… [:aN | … ]]]]

    and rewriting every block invocation as nested ‘value:’ message sends

    aBlock value: a value: b value: c => ((aBlock value: a) value: b ) value: c

    The messages gradually “unwrap” the block. If there are enough of them, you end up running the inner block as in a “regular” block invocation. If not enough, you are left with a closure for the remaining layers, with the arguments provided so far captured in the closure’s environment.

  5. One interesting and simple example of the use of currying involves a slight variation of the derivation function mentioned before:

    df := [:f :x :h | (f value: x + h) – (f value: x) / h]

    but as I am not an Smalltalker, I cannot write my examples as blocks… :D However, note that the previous code is equivalent to the equation

    derive f x = (f x + h – f x) / h

    for a fixed (very small) value of h (this notation is Haskell, where curried functions are the thing… :))
    (Another thing to note is that “derive” is only an approximation to the real derivation function by means of Newton’s formula).

    Now, if you want to define the n-th derivation of a function, you usually use the following equations:

    deriveN 0 f = f
    deriveN n f = deriveN (n-1) (derive f)

    But the last use of derive has the “wrong” number of arguments!!
    Indeed it is not wrong, because (deriveN (n-1)) is expecting a function from numbers to numbers: the derivation of f!! And that is exactly the answer that (derive f) produces!

    This is taken from my lectures on Functional Programming for the Universities of La Plata and Quilmes, in Argentina.

    My attempt (please correct me if I made any mistakes!!) for the deriveN function as a block is

    df := [:f :x | (f value: x + h) – (f value: x) / h]
    dnf := [:n :f :x |
    (n equals: 0)
    ifTrue: [ ^ f value: x ]
    ifFalse: [ ^ dnf value: (n-1) value: (df value: f) ]
    ]

    Note that I am using df as a curried function, because the second argument to dnf has to be a function (block) with one argument!
    Also note that is it important that h takes its value in some other way, not by putting it as an argument of dnf…

    I hope that this shows some usefullnes…
    Fidel.

  6. I have thought, after re-reading my post, an extremely simple way to have h there (it bothers me not to manage as much Smalltalk… ;))

    df := [:h :f :x | (f value: x + h) – (f value: x) / h]
    dnf := [:h :n :f :x |
    (n equals: 0)
    ifTrue: [ ^ f value: x ]
    ifFalse: [ ^ dnf value: h value: (n-1) value: (df value: h value: f) ]
    ]

    (It is also bothers me that I don’t know how to put indented code in this posts… Vasili, how did you do it in your post? Thanks! ;))

    Then you can have

    snddf := [:h :f | dnf value: h value: 2 value: f ]

    I am not sure about the relation of this other two versions using Smalltalk (in Haskell they would have been totally equivalent to the first one:

    snddf’ := [:h :f :x | dnf value: h value: 2 value: f value: x ]
    snddf” := [:h | dnf value: h value: 2 ]

    Some Smalltalker can help me? ;)
    Thanks!!

  7. Still another correction (this one due to one of my students)

    df := [:h :f :x | (f value: x + h) – (f value: x) / h]
    dnf := [:h :n :f |
    (n equals: 0)
    ifTrue: [ ^ f ]
    ifFalse: [ ^ dnf value: h value: (n-1) value: (df value: h value: f) ]
    ]

    or (as I do not understand the difference between the two in Smalltalk as I have said previously, I am not sure which one is correct — or both), perhaps it is

    df := [:h :f :x | (f value: x + h) – (f value: x) / h]
    dnf := [:h :n :f :x |
    (n equals: 0)
    ifTrue: [ ^ f value: x ]
    ifFalse:
    [ ^ (dnf value: h value: (n-1) value: (df value: h value: f)) value: x ]
    ]

    Still needing help with my Smalltalk… :D

  8. Alan Rodas Bonjour says:

    Fidel, your code is quite right, although you may want to use the = sign instead of equals:, and consider that a block returns the las line executed, you dont need the ^ sign there either.

    df := [:h :f :x | (f value: x + h) – (f value: x) / h].
    dnf := [:h :n :f :x | n = 0
    ifTrue: [ f value: x ]
    ifFalse: [dnf value: h
    value: n-1
    value: (df value: h value: f) ]
    ].

    snddf := [:h :f | dnf value: h value: 2 value: f ]
    snddf1 := [:h :f :x | dnf value: h value: 2 value: f value: x ]
    snddf2 := [:h | dnf value: h value: 2 ]

    But in smalltalk, even with the curried blocks, as I undertand it, the 3 flavors of snddf differ in the way of calling them as you may not be able to pass more arguments that the snddf block expects.
    i.e.
    (snddf value: h value:f) value: x.
    snddf1 value: h value: f value: x.
    (snddf2 value: h) value: f value: x.

    This is not true for haskell as doing
    snddf h f x
    snddf’ h f x
    snddf” h f x
    will produce the same result.

    So, unless you also override value:value:value: so that the remaining arguments are sended to the result of evaluating the block with less arguments (which I think is also doable) it won’t be exactly the same.
    The only problem I find for doing such a thing is that in systems where blocks are processed as VM primitives, you will need to hack into the VM to modify the value:value:value: behavior, or remove the primitive, to end up with a not-at-all performant solution.

  9. Sebastian says:

    Hi! Just stumbled accross this old post. I tried to dabble around with this but had issues with a 3 argument example like this:

    | add inc1 inc2 |
    add := [:a :b :c | a + b + c] curried.
    inc1 := add value: 1.
    inc2 := inc value: 2.
    (inc2 value: 2) + (inc2 value: 3)

    Would it make sense to change Currier like:

    value: anObject
    block numArgs = 1
    ifTrue: [^block value: anObject].
    block numArgs > 1
    ifTrue: [^self class new block: (CurriedBlock new block: block arguments: (Array with: anObject))] .
    self error: ‘Incorrect number of arguments’

    and implement the missing
    valueWithArguments: anArray
    ^block valueWithPossibleArguments: anArray

    and

    valueWithPossibleArguments: anArray
    ^block valueWithPossibleArguments: anArray

    accordingly?

    Did you somehow use curried blocks somewhere? What was your use case?

  10. kupony rabatowe do sklepów…

    Currying in Smalltalk, part 2 « 3 + 4…

Leave a Reply

For spam filtering purposes, please copy the number 2612 to the field below: