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).

Currying in Smalltalk

Currying, unless you are into Thai cooking, is partial function application commonly used in functional languages. (Some argue it should be called Schönfinkelisation, but oddly so far the term hasn’t caught on). Given a function of N arguments, one can invoke it with K arguments, K < N. This produces a new “curried” function of N – K arguments, with the K arguments of the original call closed over (remembered).

In Smalltalk, currying would allow the example:

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

run without errors and produce 7. This feels like a significant change down in the foundations of the universe, but amazingly it is trivial to implement.

Both in VisualWorks and Squeak, when a Block is invoked with a wrong number of arguments, message processing ends with a primitive failure in the valueWithArguments: method. The standard Smalltalk response to that is to complain about the wrong number of arguments. All we need is change that response to curry the receiver when appropriate.

To make the example shorter and nicer (we’ll see why a little later), we define a class called CurriedBlock, with instance variables block and arguments and an obvious initialization method block:arguments:. We also change the standard valueWithArguments: as follows:

valueWithArguments: anArray
	<primitive: 500>
	(anArray isMemberOf: Array)
		ifTrue: [anArray size < self numArgs
			ifTrue: [^CurriedBlock new block: self arguments: anArray]
			ifFalse: [self error: 'Incorrect number of arguments']]
		ifFalse: [self error: 'valueWithArguments: requires an Array']

The method above is a simplification of the VisualWorks version, with the horrible UserMessages replaced by readable strings. The Squeak version is nearly identical.

CurriedBlock needs to reproduce the standard block protocol:

valueWithArguments: anArray
	^block valueWithArguments: arguments, anArray

value: anObject
	^block valueWithArguments: (arguments copyWith: anObject)

... other required value:... methods

numArgs
	^block numArgs - arguments size

This is all that is needed to make the example work.

In fact, we could do without the CurriedBlock class. Our implementation of valueWithArguments: could answer a real block by doing something like:

valueWithArguments: anArray
	...
		ifTrue: [anArray size < self numArgs
			ifTrue: [^self curriedWithArguments: anArray]
	...

curriedWithArguments: anArray
	| arity |
	arity := self numArgs - anArray size.
	arity = 1 ifTrue:
		[^[:arg | self valueWithArguments: (anArray copyWith: arg)]].
	arity = 2 ifTrue:
	...

However, since Smalltalk blocks don’t support the equivalent of Lisp “rest” arguments, the curriedWithArguments: method would have to explicitly enumerate and handle all arities we realistically expect to use in block invocations. Using CurriedBlock instead produces a nicer example.

To be continued.

I’m done, it says

Good battery, yay!I normally work on a Mac, but my “official” work laptop runs Windows (ok, it also has Linux on it) and I’ve been using it lately to be able to run Strongtalk. So I turn it on today and out of the blue pops up this message.

I think I’ll just go home now.

right click – select – do it

Two months ago I left Cincom, to reset and refresh a number of things in my work and life. For those few who might care, so far it’s been working out great. Neat things to write about come up like never before, and this looks like the perfect time for a new blog unaffiliated with any particular company or product.

Many thanks to Bob Westergaard for helping me brainstorm the idea of a sufficiently non-committal and yet vaguely relevant title. I like how 3 + 4 and the magical number 7 are related to my interest and involvement with languages and interfaces. They are the creations different and yet very much alike in being two of the many things that try and often fail to make us smart.