Archive for March, 2007

Sections

Saturday, March 31st, 2007

Today we are bringing together selectors as blocks from the last post and currying discussed before, to produce something pretty neat: sections.

We begin with an example. Using asBlock from the last post, we can write

#> asBlock

to mean a block comparing two arguments. If we curry it with a number, say 42:

#> asBlock curried value: 42

we get a one-argument block which, when invoked, tells whether 42 is greater than the argument. We could use it as a regular one-argument block, for example, with select:

#(1 20 50 43 11) select: (#> asBlock curried value: 42)

Of course, this by itself isn’t particularly exciting. [:each | 42 > each] would have done the same, and without excessive mental acrobatics.

Without being too concerned about the form for now, let’s consider what we have just done by writing that expression. We took an operator (a binary selector) and produced a function (a block) which is an application of that selector to 42 on the left and the function argument on the right. In Haskell such a construct is called a left section of an operator. Similarly, a block applying #> with 42 on the right and the argument on the left would be a right section. This is an interesting concept—apart from the unwieldy shape it had in our code. Let’s fix that.

We add two methods to the system, one to the Symbol class, the other to Object.

Object>>~ mustBeSymbol
	| block |
	block := mustBeSymbol asBlock.
	block numArgs ~= 2 ifTrue: [self error: 'invalid selector'].
	^block curried value: self

Symbol>>~ anObject
	| block |
	block := self asBlock.
	block numArgs ~= 2 ifTrue: [self error: 'invalid selector'].
	^[:a :b | block value: b value: a] curried value: anObject

This defines ~ as a section operator. Sent to a symbol, it produces a right section, sent to anything else with a symbol as the argument—a left section. We can now rewrite the example as

#(1 20 50 43 11) select: #> ~ 42

or to select the opposite

#(1 20 50 43 11) select: 42 ~ #>

This is more interesting than just currying (and can if fact be rewritten to not rely on currying). It will work for any binary or one-argument keyword message:

Transcript ~ #show:

is a block that writes its argument to the transcript.

#print: ~ foo

produces a block writing the printString of whatever was in the variable foo to the argument, which must be a stream-like object.

#, ~ ', hello!'

is a block that appends ‘, hello!’ to the argument, and

'Hello ' ~ #,

prepends ‘Hello ‘ to it. In general, we can think of a tilda as “stick the selector and the object together, and the object missing for this to be a complete message send will be provided when the block we create is called”.

Selectors as Blocks

Tuesday, March 27th, 2007

In the previous two posts we implemented currying in Smalltalk, and in no fewer than two different ways. As Travis asked in a comment, what good is that other than being cool?

First of all, coolness is a virtue in itself. It says a lot about the Smalltalk system and the principles of its design that something like this can be added to it in a matter of minutes by changing a method or two (or not changing anything at all).

Coolness aside, I don’t expect currying to be as useful in Smalltalk as it is elsewhere. The means of expression Smalltalk and Smalltalkers rely on are different from those of functional languages. Higher-order functions are not nearly as pervasive. Blocks in Smalltalk have always been subservient to objects, so much so that they are not real closures in a few implementations (and some Smalltalkers even proposed to get rid of them). So from a pragmatic viewpoint Smalltalk blocks are good enough as they are. But I’m not interested in being pragmatic here. This is an exercise in looking at familar things in an unfamiliar perspective, or mixing a new ingredient into the standard mix just to see what happens. Smalltalk is a pretty good chemistry set.

Today we continue our exploration by adding this method to the Symbol class:

asBlock
	| arity |
	arity := self numArgs + 1.
	arity = 1 ifTrue: [^[:r | r perform: self]].
	arity = 2 ifTrue: [^[:r :a | r perform: self with: a]].
	arity = 3 ifTrue: [^[:r :a :b | r perform: self with: a with: b]].
	"... and to keep the example simple..."
	self error: 'too many arguments'

As advertised by the selector, it turns a symbol into a block. The block sends the symbol as a message to the first argument, passing the remaining arguments as the arguments of the message. Given this method, we can write:

#('Hello' 'world') collect: #size asBlock

to collect the sizes of the collection elements.

That’s right, this reminds the (in)famous Symbol>>value: hack, however it avoids the problems the hack has.

Consider the meaning of numArgs. This message can be sent to both blocks and selectors to determine how many arguments they take. Symbol>>value: pretends that symbols are the same as blocks. Unfortunately, considered as a selector #isLower has zero arguments, while considered as a block it has one. The same holds for any other selector: a Symbol’s numArgs doesn’t count the receiver as an argument, while the receiver does become an argument of the block the selector pretends it is. (The reason arity in the code above is numArgs + 1).

In practice this means that if we pass a Symbol such as #isLower to code that explicitly checks the arity of a block it receives by doing something like

aBlock numArgs = 1 ifFalse: [self error: 'Invalid block'].
^aBlock value: foo

the code will reject it, even though #isLower was supposed to pass for a one-argument block.

Furthermore, Symbol>>value: does nothing of value (sorry) for selectors of more than zero arguments. In contrast, asBlock is a uniform mechanism to cross over from the domain of selectors to the domain of blocks equivalent to those selectors sent to the block’s first argument. In particular, binary and one-argument keyword selectors can mix well with inject:into:, fold: and with:collect:.

#(1 2 3) with: #(4 5 6) collect: #@ asBlock
#(20 20 42 16) inject: 0 into: #max: asBlock
(1 to: 6) fold: #* asBlock  "6 factorial"
#('Hello ' 'world' '!') fold: #, asBlock

Bob and Goodies

Monday, March 26th, 2007

Bob Westergaard kicks off a post series about Smalltalk ports he has done, with a teaser line:

After some surfing the web, I found something that looked easy to to port. I’ll leave that story for the next post.

I know where this is going, and it’s very cool. Don’t miss it. (The pressure is on, Bob!)

Currying in Smalltalk, part 2

Saturday, March 24th, 2007

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

Friday, March 23rd, 2007

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

Thursday, March 22nd, 2007

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

Wednesday, March 21st, 2007

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.