Re-definitions, tuples, and constructors

Suppose you have a source file A.factor:

IN: A

GENERIC: some-generic ( obj -- )

M: some-class some-generic ... ;

And another source file B.factor:

IN: B

M: some-other-class some-generic ... ;

If we load A.factor, then B.factor, then load A.factor again, we would like it if the method defined in B.factor was still defined. So indeed, if the parser sees a re-definition of a generic word, it does not blow away the existing methods. This is an important feature, and it means I can change kernel.factor, for example, and reload it, without blowing away tons of methods on common generic words such as equal?. One expects that re-definitions are idempotent in the sense that re-entering an existing definition does not affect other definitions in the image.

However, tuples violated this principle. When a tuple class is defined with TUPLE:, the object system would give you a default constructor. You could then override this constructor with C:. (For details, see the Factor 0.89 tuples documentation.) Consider if source file A.factor defines a tuple class, and source file B.factor defines the constructor. Now, if we load A.factor followed by B.factor, then we make some changes to A.factor and reload it, but we do not reload B.factor, what happens is that when A.factor is reloaded, the custom constructor previously defined is blown away and replaced by the default one.

This can even be a problem with the tuple and the constructor are in the same source file; for example, in Factor 0.89, reloading sequences.factor in a running image would crash Factor, because in the middle of loading it, the slice class would be re-defined. While a custom constructor follows the definition immediately, the parser relies on slices internally, and before advancing on the next line and parsing the definition custom constructor, it would invoke the default constructor, which would result in incorrect behavior.

So, I've come to the conclusion that the traditional style of tuple constructor definitions is wrong. Now, TUPLE: doesn't give you a default constructor at all. If you want a default constructor which just fills in slot values from the stack, use the new form of C: which just takes a constructor word name and a tuple class name:

TUPLE: color red green blue ;

C: <color> color

Unlike before, the constructor word can have any name:

C: <rgba> color

Custom constructors are now defined as ordinary words. Indeed, the following two definitions are equivalent:

C: <rgba> color

: <rgba> color construct-boa

Here construct-boa is a low-level word taking a class; BOA denotes "by order of arguments", and "BOA constructor" is a pun on "Boa Constrictor", one of the more amusing pieces of terminology in use by the Lisp community.

The construct-boa word is more flexible than the old hard-coded constructor. For example, suppose you have a tuple:

TUPLE: action name counter ;

We wish for the default constructor to take a name from the stack, and store zero in the other slot. Previously, you'd write something like:

C: action ( name -- action )
    [ set-action-name ] keep
    0 over set-action-counter ;

While this isn't so bad, other non-default constructors would get complicated quickly, even if all they did was fill in slots from the stack and with default values. Now, you can just write:

: <action> ( name -- action )
    0 action construct-boa ;

In addition to construct-boa, we have construct-empty:

TUPLE: person name address employer ;

: <empty-person> person construct-empty ;

<empty-person> .
T{ person f f f f }

Finally, there is construct, which takes a sequence of slot setter words and fills these in from the stack:

: <homeless-person> ( name -- person )
    { set-person-name } person construct ;

Previously, the only way to have multiple constructors for a tuple class was to define a general constructor with C:, which possibly took many inputs from the stack and required complex stack shuffling. Now, you can define multiple constructors, with arbitrary names, which do not necessarily share code.

Even more interestingly, you can write constructors parametrized on the class name; it doesn't have to be a literal value! For example, suppose you have a class of errors:

TUPLE: reactor-error reason ;

TUPLE: nuclear-meltdown severity ;

C: <nuclear-meltdown> nuclear-meltdown

We can write a word which throws a reactor error, given a reason:

: throw-reactor-error ( reason -- )
    reactor-error construct-boa throw ;

However, we might find that this is poorly factored; if we have a bunch of reasons, such as terrorist-attack, nuclear-meltdown, software-error, etc, we'd have to define constructors for each (even just using C:), then construct an instance before passing it to reactor-error. Instead, we can settle on a standard construction strategy for reasons; for example, construct-boa, and perform construction in the throw-reactor-error word:

: throw-reactor-error ( ... reason-class -- )
    construct-boa reactor-error construct-boa throw ;

Now, we can write:

"very severe" nuclear-meltdown throw-reactor-error

In this case, we don't reduce complexity by much; all we eliminated is the C: <nuclear-meltdown> nuclear-meltdown. However, in more complex cases involving delegation, being able to factor out construction logic in this way has been a real boon; I've been able to clean up and simplify a lot of constructors in the UI this way. Finally, there is one less concept to learn; the special C: syntax has been replaced by three ordinary words.

Fixing a very old bug

Two and a half years ago, Mackenzie Straight reported a bug: stack effect inference would hang when given the following input:

[ [ dup call ] dup call ]

Of course this code hangs when evaluated anyway, but one does not expect a type checker to hang when given a non-terminating program!

For a long time, I had no idea how to fix this issue, and such patterns never came up in real code anyway, so I put it aside. Until today, this was probably the oldest bug which is still open.

Well, now it is fixed!

Some background information first...

Factor's stack effect inference is the basis of the compiler, and a key optimization performed at the inference level is lifting quotations up to their call site. Most of the time this works great, however in the example is rewritten as [ dup call ] [ dup call ] call, then [ dup call ] dup call, and it loops from there. The rewrite system used by the compiler was potentially non-terminating! Calls to curry are rewritten in a similar way, and similar non-termination can occur.

Using the results proven in The Theory of Concatenative Combinators, we can write a turing-complete basis for Factor:

drop
over
curry
>r
r>
call

Using these six words, together with all quotations (recursively) built up from them, we can express any computable function.

This presents a major problem. Because all of these operations -- stack shuffling, calling of quotations, and partial application -- are partially evaluated during stack effect inference, this means that determination of the stack effect of an arbitrary Factor expression becomes equivalent to the halting problem.

In the end, the fix was simple. Stack effect inference just gives up if a quotation calls itself directly or indirectly. Since the set of child quotations nested in a given input quotation is finite, the process either terminates, or eventually gives up with an error:

( scratchpad ) [ [ dup call ] dup call ] infer.
Word: [ dup call ]
The quotation [ dup call ] calls itself.
Stack effect inference is undecidable when quotation-level recursion is permitted.
Nesting: { [ dup call ] }

In real code, we don't do combinatory-logic-style quotation-level recursion; we just define named recursive words. In any case, somebody who wants to write odd stuff like M and Y combinators in Factor will simply have to put up with slower performance because such code will run in the interpreter instead of compiling.

Christopher Diggins's Cat language doesn't suffer from this problem, because his stack effect inferencer is more sophisticated than mine; it supports parametric polymorphism and row types, so quotations don't have to lifted up to their call site in order to determine the stack effect of a combinator. However, when Chris goes on to implement compiler optimizations, he'll find that quotation lifting can bring a huge performance benefit, just like lambda lifting in functional languages. In this case, the non-termination of quotation lifting still has to be considered.

Mixins

Consider typical message-passing OOP (with made up syntax):

class Rectangle {
    state w, h;
    method area() { ... }
    method paint() { ... }
}

class Ellipse {
    state major, minor;
    method area() { ... }
    method paint() { ... }
}

We can add new types of shapes easily, but we cannot define new operations on existing shapes without modifying existing code. In a language with algebraic data types, the situation is reversed (again, made up syntax):

data Shape = Rectangle w h | Ellipse major minor
area shape =
    case shape of
        Rectangle w h -> ...
        Ellipse major minor -> ...

draw shape =
    case shape of
        Rectangle w h -> ...
        Ellipse major minor -> ...

Here, we can define new operations on existing shapes but we cannot define new shapes and have the existing operations work with them.

Generic functions/words give us the best of both worlds. Here's the Factor syntax:

GENERIC: area ( shape -- )
GENERIC: draw ( shape -- )

TUPLE: rectangle w h ;
M: rectangle area ... ;
M: rectangle draw ... ;

TUPLE: ellipse major minor ;
M: ellipse area ... ;
M: ellipse draw ... ;

We can define new shapes implementing the area and draw generic words, and we can define new generic words which implement methods for rectangle and ellipse, without coupling anything together.

Now let's go back to our first message-passing OOP example, and suppose this language supports multiple inheritance of mixins. There are many definitions of what a mixin is, but for now, assume a mixin is a class with no state, just behavior.

class Shape {
    abstract method triangulate();

    method paint() {
        ... triangulate the shape with triangulate(),
        then render it with a standard algorithm ...
    }
}

class Rectangle < Shape {
    state w, h;
    method area() { ... }
    method triangulate() { ... }
}

class Ellipse < Shape {
    state major, minor;
    method area() { ... }
    method triangulate() { ... }
}

We can define new shapes which mixin the Shape mixin, but we cannot add additional mixins to the Rectangle and Ellipse data types.

In traditional Factor, the rough equivalent of the above would be to use a union class:

GENERIC: area ( shape -- )
GENERIC: triangulate ( shape -- triangle-seq )
GENERIC: draw ( shape -- )

TUPLE: rectangle w h ;
M: rectangle area ... ;
M: rectangle triangulate ... ;

TUPLE: ellipse major minor ;
M: ellipse area ... ;
M: ellipse triangulate ... ;

UNION: shape rectangle ellipse ;
M: shape draw ... triangulate, then draw the triangles ... ;

Now we can certainly define new union classes, and make either rectangles or ellipses instances of these union classes, but we cannot extend the shape union class with new shapes.

Until now, the accepted workaround ("design pattern") would be to not define a shape class at all, and instead define a draw method on the object class:

M: object draw ... triangulate, then draw the triangles ... ;

M: beizer-curve draw ... override default implementation ... ;

However, this was crufty. Defining methods on the object class is clutter. Plus, if you lose the shape union, you no longer have a way to distinguish shapes from other objects.

Enter Factor's new mixin classes feature.

Just like generic words generalize message passing OOP and case-based pattern-matching, Factor's mixin classes generalize multiple behavior inheritance and union classes.

We can define a new mixin as follows:

MIXIN: shape

We can specialize generic words on this mixin:

M: shape draw ... default implementation in terms of triangulate ...

But here's the kicker: unlike a union, where all members must be listed up-front, we can declare an existing class to be an instance of an existing mixin:

INSTANCE: rectangle shape

INSTANCE: ellipse shape

I successfully used mixins to remove some repeated code between the various implementations of sequences and associative mappings. Until now, there was no way to specialize a generic word on all sequences; now this is possible:

GENERIC: foo

M: sequence foo ... ;

A mixin is essentially a suite of methods; there is some similarity between Haskell typeclasses and Factor mixins. I'm still discovering the various applications of mixins; after Factor 0.90 is released, I intend to apply them to our I/O stream implementations and remove some boilerplate there.

So to recap, Factor's object system allows the following operations without forcing unnecessary coupling:

• Defining new operations over existing types
• Defining existing operations over new types
• Importing existing mixin method suites into new types
• Importing new method suites into existing types
• Defining new operations in existing mixin method suites
• Defining new mixin method suites which implement existing operations

This is a lot more general than mainstream message passing OOP and allows a wider range of problems to be expressed directly in terms of method dispatch.

Going to Austin

I will be in Austin, Texas from the 18th of August to the 26th. I'll be hanging out and hacking code with Doug and Eduardo. If anyone else in the Austin area wants to meet up, send me an e-mail.

Smalltalk is dying

I just saw that ObjectArts has discontinued development of Dolphin Smalltalk.

It seems Smalltalk is going the way of the dodo bird. Basically, we're left with a rapidly dwindling number of commercial implementations which are way overpriced considering their relatively low level of polish and functionality; and the only open source option is Squeak, which is not production-ready and never will be. Then there are various dead and semi-dead pre-alpha-stage projects. One commercial Smalltalk which stands out from the rest is Ambrai, but it is in early development, and it is unlikely a proprietary Mac OS X-only product will attract a significant base of library contributions. Perhaps Pepsi will get somewhere, who knows.

A pity, really, considering how computing might look today if things went differently in the early days of Smalltalk.

Update: I wasn't talking about popularity at all. It doesn't matter if Smalltalk isn't popular; for some reason, popular languages tend to suck (Java, Ruby, COBOL, etc.) The problem with Smalltalk is that the implementations are in terrible shape. The closest thing to a usable open source implementation is Squeak, and it leaves a lot to be desired. Common Lisp is an example of a less popular language which doesn't suffer from this problem; open source Lisp implementations are fantastic.

New suite of benchmarks

I spent a bit of time cleaning up various benchmarks and putting them over a common framework. Now you can do "benchmark" run to run a suite of benchmarks. The results are collected and printed in a table:

Benchmark                    Run time (ms) GC time (ms)
benchmark.continuations      473           3
benchmark.empty-loop         480           0
benchmark.fib1               194           0
benchmark.fib2               855           0
benchmark.fib3               1418          0
benchmark.fib4               3334          60
benchmark.fib5               2126          11
benchmark.iteration          8829          23
benchmark.mandel             4421          77
benchmark.nsieve             2221          3
benchmark.nsieve-bits        65679         239
benchmark.partial-sums       26293         183
benchmark.raytracer          26031         242
benchmark.recursive          36740         233
benchmark.reverse-complement 15637         167
benchmark.ring               9124          79
benchmark.sort               1934          38
benchmark.spectral-norm      32142         991
benchmark.sum-file           287           0

I want to set up a continuous testing cluster with a number of machines. The machines would perform the following tasks:

• Build Factor
• Run unit tests
• Run benchmarks
• Create deployment images for various modules and upload them to a "Factor application central" web site

Named local variables and lexical closures in Factor

I previously wrote about adding named parameters to Factor as an extension library. Well, now I've beefed up this code with support for lexical closures, and threw it in extra/locals.

Hopefully, this module can now replace the less efficient rewrite-closures library by Eduardo Cavazos.

Here is an example word using locals:

:: add-test | x y z | x y + z + ;
1 2 3 add-test .
  6

The syntax is simple; to define a word which uses locals, you use :: instead of :. Then you follow the word name with a list of locals enclosed in | characters, and use these locals anywhere in the body of the word.

Closure conversion is performed:

:: map-test | seq inc | seq [ inc + ] map ;
{ 10 20 } 5 map-test .
  { 15 25 }

Here, we're using the "inc" local inside the quotation passed to map. The :: word performs all the necessary rewriting to make this work. The key to making this efficient is compiled curry.

You can also define lambdas, which are like quotations except inputs are placed in local variables:

:: map-test | seq inc | seq [| elt | elt inc + ] map ;
{ 10 20 } 5 map-test .
  { 15 25 }

The lambda [| elt | elt inc + ] is equivalent to the quotation [ inc + ], and in both cases closure conversion is performed by the :: word.

Lambdas can be used in normal colon definitions, too:

: foo-bar 1 2 [| x y | x y * ] lambda call ;
foo-bar .
  3

The lambda word converts a lambda into code for producing a quotation. If the input to lambda is literal, the code transformation is done at compile time.

So how does the closure conversion actually work? Consider the following code:

[| a b | a [| c | c b + ] map ]

The inner quotation refers to the free variable b. We can rewrite it as follows:

[| a b | a b [| c b | c b + ] curry map ]

That is, we add all free variables to the list of inputs, then fetch these free variables right before pushing the quotation; after the quotation is pushed, we use curry to partially apply the quotation to the free variables. All lambdas and quotations are rewritten this way, as we lift free variables up. In the above example, we have already arrived at a form with no free variables anywhere. Now, we convert to point-free form. This is done in a brute-force way; within a lambda, all locals are stored on the retain stack. Here is the final result of closure conversion applied to the above example:

[
    >r
    >r r>
    r>
    dup
    >r
    >r r>
    dup
    >r
    [ >r >r r> r> dup >r >r r> dup >r + r> drop r> drop ] curry
    map r>
    drop r>
    drop
]

Looks rather complicated, but most of the stack shuffling is optimized away by the compiler.

This vocabulary is not in the darcs repository yet, because it depends on compiled curry, which I'm still in the process of debugging. However, it should work with the latest code from darcs, except words using closures won't compile. I put the code up on LispPaste.

In only 121 lines, I was able to add efficient lexical scoping to Factor. Even though I encourage people to try to express everything in a clean way using the stack only, sometimes locals are handy (complex math formulas, bizarro native APIs taking 11 parameters each, etc). Having more options is always good. Plus, this library makes a great demo of how to extend the language in a radical way without altering the core implementation!