Sunday, August 26, 2007

FactorCon wrap-up

Today is my last day in Austin. On Friday, we went jet-skiing; as it turns out, I'm not so good at driving one, so after a brief attempt which climaxed in me tipping over the jet-ski (with all three people on it), I delegated driving responsibilities to Doug's friend, also named Doug (common name in Texas?).

Eduardo had to go back to work. Me and Doug did a did a bit more hacking, Ed-less -- we got non-blocking UDP working on Windows, and Doug started working on a directory entry change notification binding for Windows. This won't be ready until Factor 0.91, but I'm going to implement the Unix side; kqueue on BSD, inotify on Linux, and whatever crap Solaris has on Solaris. Having a cross-platform directory change notification API is something I've wanted for a while; many other language implementations don't bother with features like this, but I consider it essential.

I also optimized the MD5 library a little bit, and improved the locals library (you can have local word definitions, and locals are writable). Doug updated the libs/math library for the new module system. There's a lot of cool code there; quaternions, polynomials, combinatorics, numerical integration... indispensable tools for hard-core programming.

I'd like to elaborate on one point regrading writable locals. Consider the following Lisp function:
(defun counter (n)
(values
(lambda () (prog1 n (setf n (1- n))))
(lambda () (prog1 n (setf n (1+ n))))))

This returns a pair of closures which increment and decrement a shared counter. Each closure returns the current value of the counter before changing it. The initial value of the counter is the value passed to the function, and each pair of closures has a unique internal counter value.

Using the locals library, the Factor equivalent is:
:: counter | n! |
[ n dup 1- n! ]
[ n dup 1+ n! ] ;

The ! suffix in the list of local parameter names indicates the local should be writable; now, the n! local word can be used to write to it. The Factor code is almost identical to the Lisp code, except with fewer parentheses.

In both cases, you see that we differentiate between binding and assignment, and also we are able to write to a local closed over in an outer scope; the n! word does not create a new internal variable in the counter quotation, but modifies the value in the lexical environment of the counter word.

On the other hand, some languages, such as Python, claim to support lexical closures, however the essential property of closures -- that they close over the lexical scope -- is not preserved, and assigning to a local simply creates a new binding in the innermost scope! Guys, that is retarded! Look at the workarounds these people use. It is really no better than Java's anonymous inner classes, and if you want to call those "closures", you may as well say that C# is a "dynamic" language.

Wednesday, August 22, 2007

FactorCon summer 2007

I'm in Austin right now with my girlfriend - we're staying at Doug Coleman's house. We've been eating mexican food, swimming, and having lots of fun in general. Doug, Eduardo and I have also been hacking up a storm. I've met Doug before when he came to Ottawa, but this is my first time hanging out with Eduardo. He's a really chill guy, sleeps during the day and then stays up hacking until 4 in the morning -- if you ever meet him, ask him to make you some vegan breakfast tacos, they're good at any time of day or night. It is really good to meet hackers face-to-face and write code together -- when one of us gets stuck, the others can help out, and the round-trip time is much shorter than if we were on IRC. I also got a chance to meet Ryan Murphy, who contributed a couple of Factor modules (priority heaps and EditPadPro support); he also lives in Austin.

We've been working on many things:
  • Optimizing generic word dispatch (Slava)
  • Updating the Solaris x86 port (Slava)
  • Windows IPv6 and UDP (Doug)
  • Updating the math library for the new module system (Doug)
  • Optimizing the boids demo (Eduardo)
  • Macros (Slava and Doug)

The macro feature is pretty cool. Factor has had compiler transforms for a while, but macros make them easier to use. For example, if you want to write a word which drops n elements from the stack, a first approximation might be:
: ndrop ( n -- ) [ drop ] times ;

However, this is inefficient since the compiler is unable to infer the stack effect, and in any case, if n is constant we would like to unroll the loop and not have to do it at run time. So we can use a compiler transform:
: [ndrop] ( n -- quot ) \ drop <repetition> >quotation ;
: ndrop [ndrop] call ;
\ ndrop 1 [ [ndrop] ] define-transform

The [ndrop] word outputs a quotation which drops the top n stack elements; this quotation does not loop, it is just drop repeated a number of times. The definition [ndrop] call for the ndrop word is only used in the interpreter or when the value of n is not known at compile time. The compiler transform is invoked when the value is known at compile time, and it outputs a quotation to replace the word with. So in this example, 4 ndrop compiles to drop drop drop drop, which is optimized to a single instruction which decrements the stack pointer. No looping at all.

However, there is a bit of boilerplate in the above code which becomes apparent in more complex examples. With macros, you can now write:
USE: macros

MACRO: ndrop ( n -- ) \ drop <repetition> >quotation ;

So a macro receives its inputs and outputs a quotation -- the compiler invokes macros at compile time and replaces the macro call with the generated quotation, and the interpreter generates a quotation by calling the macro every time.

The cool thing is that the MACRO: word can be defined without modifying the compiler or anything; it is just a simple wrapper around define-transform. Check it out. The same file also defines some short-circuiting boolean operators as macros.

A more involved example of macrology can be found in extra/shuffle - this file defines some hardcore shuffle words (duplicating, dropping, swapping arbitrary numbers of stack elements) and the implementation in terms of macros looks nicer than the implementation using compiler transforms directly.

In fact these macros are exactly like Common Lisp macros -- but whereas people say Common Lisp macros are a key, fundamental language feature which differentiates Lisp from other languages, in Factor we're able to add macros as a library (and it only takes 5 lines). Another "fundamental" Lisp feature, lexically scoped closures, is also just a Factor library -- and it compiles to efficient code to boot, without the compiler having to know anything about lexical scope! I really think Factor is a better Lisp than Lisp -- it pulls off the extensible language tricks just as well or better, and the implementation is simpler and more transparent to boot.

Factor 0.90 is almost done -- I've finished most of the remaining loose ends. Updating the Solaris port was the last big item. This didn't take long because Doug had a Parallels virtual machine with Solaris installed and ready to go.

I'm still in Austin for a few more days. Going to go bike riding, jetskiing hopefully, and I also need to buy a cowboy hat! We're also going to meet up with the RScheme guy. Eduardo knows him from way back in the day; before joining the Factor community, Eduardo was a hard-core Schemer. He wrote a window manager in Scheme which was the precursor to Factory, and he also wrote a DNS server; I've been lobbying for him to port this DNS server over to Factor too. Now that we have UDP support on all platforms, it would be a great stress-test for the network backends!

Friday, August 17, 2007

The great Factor computer shootout

I ran the latest suite of benchmarks on my machines:
  • Power Mac G5 2.5Ghz
  • Athlon 64 2.4GHz
  • Pentium 4 2.8GHz
(I didn't include the ARM-based Gumstix this time.)
Benchmark PowerPC G5Athlon 64Pentium 4
bootstrap1 14805 14217 12617
bootstrap2 437594 326091 412635
continuations 441 312 435
dispatch1 8092 6041 5473
empty-loop 485 209 565
fib1 190 79 129
fib2 847 191 279
fib3 1396 492 580
fib4 4797 2410 3311
fib5 2483 1391 1857
iteration 18200 11353 10810
mandel 4556 2148 4418
nsieve 2603 5069 2372
nsieve-bits 56640 58543 45725
partial-sums 27351 25615 19230
raytracer 25862 23301 24538
recursive 38736 12120 13662
reverse-complement17536 20827 13091
ring 9827 7470 8979
sort 1809 1885 1153
spectral-norm 31879 9383 11731
sum-file 335 277 239
typecheck1 6959 2820 2429
typecheck2 7171 2243 1919
typecheck3 4596 1950 1883
typecheck4 4887 1914 1756

As you can see, the PowerPC backend lags somewhat. The Pentium 4 box is surprisingly fast -- and at 6 years old, it's the oldest machine of the bunch!

gcc is open sores software

In Factor 0.90, I added a new function to vm/os-linux.c which returns the path of the current executable. However it seems that neither gcc 4.0.3 nor gcc 4.2.1 can compile this file on x86. I get an error like the following:
vm/os-linux.c: In function 'vm_executable_path_and':
vm/os-linux.c:20: error: unable to find a register to spill in class 'DIREG'
vm/os-linux.c:20: error: this is the insn:
(insn:HI 16 83 17 2 (parallel [
(set (reg:SI 2 cx [66])
(unspec:SI [
(mem:BLK (reg/v/f:SI 63 [ suffix ]) [0 A8])
(reg:QI 0 ax [70])
(const_int 1 [0x1])
(reg:SI 2 cx [69])
] 20))
(use (reg:SI 19 dirflag))
(clobber (reg/f:SI 68 [ suffix ]))
(clobber (reg:CC 17 flags))
]) 530 {*strlenqi_1} (insn_list:REG_DEP_TRUE 6 (insn_list:REG_DEP_TRUE 12 (insn_list:REG_DEP_TRUE 14 (insn_list:REG_DEP_TRUE 15 (nil)))))
(expr_list:REG_DEAD (reg:SI 19 dirflag)
(expr_list:REG_DEAD (reg:SI 2 cx [69])
(expr_list:REG_DEAD (reg:QI 0 ax [70])
(expr_list:REG_UNUSED (reg:CC 17 flags)
(expr_list:REG_UNUSED (reg/f:SI 68 [ suffix ])
(expr_list:REG_EQUAL (unspec:SI [
(mem:BLK (reg/v/f:SI 63 [ suffix ]) [0 A8])
(reg:QI 0 ax [70])
(const_int 1 [0x1])
(reg:SI 2 cx [69])
] 20)
(nil))))))))

In fact, here is a test case which demonstrates the problem; compile it on x86 with -O3,using gcc 4.2.1, 4.0.3 or 3.4.6 (I tested them all):
#include <stdlib.h>
#include <string.h>

register long foo asm("esi");
register long bar asm("edi");

char * crash_me_baby(char *str) {
char *path = malloc(1 + strlen(str));
return path;
}

I'm sick and tired of the gcc team's total unwillingness to support basic, documented, features. In this case, it is the global register variables which trigger the bug. However, the crash_me_baby() function does not use these variables at all, and in any case they are non-volatile registers which need to be saved/restored, so why the hell would it break gcc?

I submitted a bug to the gcc team. But I'm not holding my breath; I've already filed a report about the same issue a few years ago. This is a recurring problem which has been coming and going since the days of gcc 3.3.

The real way forward is to stop using register global variables. When the Factor VM no longer includes an interpreter, and all quotations are compiled, this will be possible without adversely affecting performance. It will also have the side benefit of making the Factor VM pure ANSI C, with some inline assembly. Which means that on Windows for example, we should soon be able to compile Factor with an alternative compiler, such as Microsoft's Visual Studio.

For now, I've found a workaround -- I had to write my own version of strlen().

Thursday, August 16, 2007

Parallel map and each

To ensure that Factor 0.90 is robust and stable, I'm setting up a "compile farm" for testing Factor on a variety of machines; this involves bootstrapping, loading all modules, running unit tests, and benchmarks.

Additionally, onn Mac OS X, the .app deployment tool is tested in an automated fashion. The deploy.app tool spawns a separate Factor process to ensure that deployment is done in a clean image, then blocks until this process completes. Since I'm on a quad CPU machine, I can save a lot of time by deploying all modules at the same time. I do this using Chris Double's extra/concurrency library. What I want to do is spawn a bunch of threads, then wait until all these threads complete. Each thread calls deploy.app to Factor process, then waits for this process to comoplete. As suggested by Chris, I can use concurrency futures for this.

The idea behind futures is simple. You call future with a quotation yielding a value; this spawns a process to compute the value. Then at a later time, you call ?future which waits until the value is ready, and returns this value.

We can use futures to write a parallel-map combinator:
: parallel-map ( seq quot -- newquot )
[ curry future ] curry map [ ?future ] map ;

This spawns a thread to compute each value, then waits until all values have been computed, collecting them into a new sequence.

We can test this out:
  [ { 1 2 3 4 } [ 1000 sleep 1 + ] parallel-map ] time .
1003 ms run / 0 ms GC time
{ 2 3 4 5 }

Four threads are spawned, and each one takes a second to complete. Compare with an ordinary map:
  [ { 1 2 3 4 } [ 1000 sleep 1 + ] map ] time
4001 ms run / 0 ms GC time
{ 2 3 4 5 }

(Incidentally, the reason the run time does not come out exactly at 1000 and 4000 ms, respectively, is not because a simple iteration over 4 elements takes 3 ms in Factor -- it doesn't -- but because the sleep word has poor resolution. This will be fixed at some point.)

In my specific use-case, I don't care about a return value, I just want to spawn a bunch of threads and wait until they're all done. So I can implement parallel-each in terms of parallel-map:
: parallel-each ( seq quot -- )
[ f ] compose parallel-map drop ;

We simply modify the quotation to yield a null value, then we parallel map this quotation across the sequence and drop the results (which should be a sequence consisting entirely of fs).

Now my automated deployment tester is easy to write:

{
"automata.ui"
"boids.ui"
"bunny"
"color-picker"
"gesture-logger"
"golden-section"
"hello-ui"
"lsys.ui"
"maze"
"nehe"
"tetris"
} [
"deploy-log/" over append <file-writer>
[ deploy.app ] with-stream
] parallel-each

The parallel-map and parallel-each combinators are now in extra/concurrency.

In this case, each thread simply spawns another OS process then waits for I/O to complete, so Factor's simple co-operative scheduler has no problem parallelizing the work. For compute-intensive tasks, this approach is not useful, since Factor cannot take advantage of pre-emptive threading or multiple CPUs.

Tuesday, August 14, 2007

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.

Sunday, August 12, 2007

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.