I'm back in Ottawa. Doug, Ed, and all of their friends are very cool and lots of fun to hang out with! Once again, my luggage has been delayed en route, and I'll only get it Tuesday at the earliest. I wonder if the baggage handling infrastructure runs on Java, implemented by the regulars from JavaLobby?
Factor 0.90 will be released before the end of the month. I only have two things left on my to do list! I need to test on all platforms, then I have to fix one last bug concerning UI redraw on certain Windows systems.
I think I will aim for shorter release cycles in the future; say, 2 or 3 weeks. I'll limit the amount of new functionality in each release, so that it doesn't take so long for things to settle down. In the long term, I might try to get rid of releases altogether, and instead have daily builds; a daily build will only be uploaded if all unit and integration tests pass, and if all contributed modules load, and maybe even if there are no major performance regressions in benchmarks. It would be cool to automate something like this.
Monday, August 27, 2007
Sunday, August 26, 2007
When to use locals
Some people have wondered why I implemented the locals library, and if in fact I'm turning my back on stack-based programming and "selling out". In fact this is not the case.
First of all, Factor has already had named variables in the core for quite some time; these are found in the
In a handful of places, we also used dynamic variables as temporaries in calculations. I think once the right abstraction is found, stack code is almost always simpler and cleaner than the equivalent applicative code using named temporaries. But sometimes you have a math formula which operates on 10 values at once, or something similar, and it simply makes more sense to name these intermediate values. In these cases, we used dynamic variables. There are a handful of examples of this so far, such as the MD5 algorithm, and a couple of routines in the calendar library.
However when one uses dynamic variables for temporaries, the dynamic scope semantics no longer help and in fact get in the way; anybody who has used a Lisp with all-dynamic scope can testify. So while most values which would be lexically-scoped in a Lisp program are passed on the stack in Factor, sometimes you still want to name temporaries, and named locals with lexical scope are useful here, because they allow you to create closures and safely pass them around without running into the "funarg problem" which had the Lispers stumped through the 60's.
I never opposed having named variables in Factor, because if I did, they wouldn't be there from day one. Until recently, I didn't feel the need for lexical scope much, though, and when asked about it, my standard reply would be that the stack is Factor's equivalent of lexical scope, and that if somebody coded it up, I'd be happy to add it as an extra library.
Eduardo eventually implemented somewhat inefficient lexical scope in his
So to recap, Factor now has three main methods of passing values between words, and storing temporary values within words:
Having more abstractions to choose from when writing code is good, and I think a stack language can express the widest range of them in the most natural possible way.
First of all, Factor has already had named variables in the core for quite some time; these are found in the
namespaces vocabulary, which implements very simple dynamically-scoped namespaces. There are many cases where dynamic scope is useful, and languages which lack it often end up with a lot of code which passes parameters down long function call chains, with only the leaf functions actually using the parameters. Examples of dynamic scope usage in Factor include the current stream, and various idioms for sequence and association construction. Here dynamic scope is the right thing to use, and it makes total sense, and it cleans up code when certain values are not passed around on the stack.In a handful of places, we also used dynamic variables as temporaries in calculations. I think once the right abstraction is found, stack code is almost always simpler and cleaner than the equivalent applicative code using named temporaries. But sometimes you have a math formula which operates on 10 values at once, or something similar, and it simply makes more sense to name these intermediate values. In these cases, we used dynamic variables. There are a handful of examples of this so far, such as the MD5 algorithm, and a couple of routines in the calendar library.
However when one uses dynamic variables for temporaries, the dynamic scope semantics no longer help and in fact get in the way; anybody who has used a Lisp with all-dynamic scope can testify. So while most values which would be lexically-scoped in a Lisp program are passed on the stack in Factor, sometimes you still want to name temporaries, and named locals with lexical scope are useful here, because they allow you to create closures and safely pass them around without running into the "funarg problem" which had the Lispers stumped through the 60's.
I never opposed having named variables in Factor, because if I did, they wouldn't be there from day one. Until recently, I didn't feel the need for lexical scope much, though, and when asked about it, my standard reply would be that the stack is Factor's equivalent of lexical scope, and that if somebody coded it up, I'd be happy to add it as an extra library.
Eduardo eventually implemented somewhat inefficient lexical scope in his
extra/rewrite-closures library, which still exists because unlike extra/locals, it has first-class environments. I decided to code extra/locals because I wanted to see if I could make locals as efficient as stack values, and the experiment was a success.So to recap, Factor now has three main methods of passing values between words, and storing temporary values within words:
- The stack. Factor is and always will be a stack-based language; the whole point of the project is to explore stack-based programming. I encourage beginners to learn to think in terms of the stack before jumping into other abstractions, and for most code, the stack works really well. It is really interesting that in a stack language, function composition is expressed as concatenation, and compared to Lisp, Factor code has a lot less nesting and arbitrary introduction of temporaries. Especially now that Factor supports efficient partial function application, quotations can have internal state, and this brings much of the benefits of closures to the world of the stack.
- Dynamically scoped variables. These are useful for a set of issues totally orthogonal to temporaries: they're used to give words context-specific behavior, and when an algorithm spanning multiple words needs to operate on a common set of values.
- Lexically scoped variables. These are used to name temporary values inside calculations which otherwise would be hard to express with the stack. Hopefully this set will reduce over time, but for now, it includes any kind of hairy mathematical operation such as found in cryptography, numerical methods, and so on.
Having more abstractions to choose from when writing code is good, and I think a stack language can express the widest range of them in the most natural possible way.
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
I'd like to elaborate on one point regrading writable locals. Consider the following Lisp function:
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:
The
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
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.
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:
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:
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:
The
However, there is a bit of boilerplate in the above code which becomes apparent in more complex examples. With macros, you can now write:
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
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!
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:
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!
- Power Mac G5 2.5Ghz
- Athlon 64 2.4GHz
- Pentium 4 2.8GHz
| Benchmark | PowerPC G5 | Athlon 64 | Pentium 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-complement | 17536 | 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:
In fact, here is a test case which demonstrates the problem; compile it on x86 with
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
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
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
The idea behind futures is simple. You call
We can use futures to write a
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:
Four threads are spawned, and each one takes a second to complete. Compare with an ordinary map:
(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
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
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
Now my automated deployment tester is easy to write:
The
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.
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-eachThe
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.
Subscribe to:
Posts (Atom)