Factor: a practical stack language

Charles Nutter is writing a Ruby interpreter in Java. He views Ruby's ObjectSpace feature as superfluous, because few libraries use it:

ObjectSpace is Ruby's view into the garbage-collected heap. You can use it to iterate over all objects of a particular type, attach finalizers to any object, look an object up by its object ID, and so on. In Ruby, it's a pretty low-cost heap-walker, able to dig up objects matching particular criteria for you on a whim. It sounds like it might be pretty useful, but it's used by very few libraries...and most of those uses can be implemented in other (potentially more efficient) ways.

Well of course few libraries use this feature -- it is intended for developers. Charles goes on to list a bunch of other reasons why he views ObjectSpace as undesirable; it can be dangerous when called from library code due to thread safety, etc. However, this misses the whole point. Features such as ObjectSpace are for developers to use interactively, not for libraries.

Factor has similar capabilities, and I use them regularly -- not every day, but perhaps once a week, at least. Here is just one example.

Yesterday I was debugging the compiler's interval inference code. I noticed that compiling some words, such as nth, allocated absurd amounts of memory (~30mb) in the optimizer stage. To see where the memory was going, I used the heap-stats. word to save a heap allocation breakdown snapshot before and after calling optimize on a dataflow IR graph which triggered the problem. Here is the allocation breakdown before optimization:

Class Bytes Instances
#>r 80 5
#call 1552 97
#dispatch 16 1
#if 512 32
#merge 528 33
#push 1568 98
#r> 80 5
#return 320 20
#shuffle 2208 138
#terminate 320 20
#values 720 45
alien 32 2
array 1996704 47446
article 9600 300
bignum 38088 1699
bit-array 8 1
button-down 168 7
button-up 120 5
byte-array 8 1
c-stream 48 2
c-type 896 16
char-elt 16 1
clipboard 48 2
command-map 528 22
complex 32 2
continuation 280 7
copy-action 16 1
cut-action 16 1
delete-action 16 1
doc-elt 16 1
drag 24 1
drag-timer 16 1
duplex-stream 32 1
edit-slot 16 1
effect 91904 2872
entry 24 1
float 3568 223
float-regs 72 3
gain-focus 16 1
gradient 144 6
hashtable 221264 13829
inferred-vars 32 1
int-regs 16 1
interval 240 10
key-down 1992 83
line-elt 16 1
line-reader 24 1
long-long-type 32 2
lose-focus 16 1
method 22152 923
module 768 16
motion 16 1
mouse-enter 16 1
mouse-leave 16 1
mouse-scroll 16 1
no-method 24 1
node 31616 494
one-line-elt 16 1
one-word-elt 16 1
operation 2200 55
paste-action 16 1
pathname 24 1
plain-writer 16 1
queue 24 1
quotation 510976 21677
ratio 320 20
sbuf 16 1
select-all-action 16 1
slot-spec 14600 365
source-file 15880 397
stack-params 16 1
string 1242848 16062
struct-type 72 3
temp-reg 16 1
tombstone 32 2
update-object 16 1
update-slot 16 1
value 3136 98
vector 10304 644
vocab-link 24 1
word 275880 6897
word-elt 16 1
wrapper 21280 2660

And after:

#>r 160 10
#call 1792 112
#declare 144 9
#dispatch 16 1
#if 512 32
#merge 528 33
#push 800 50
#r> 160 10
#return 320 20
#shuffle 1568 98
#terminate 320 20
#values 720 45
alien 32 2
array 2033576 48896
article 9600 300
bignum 35829360 1703
bit-array 8 1
button-down 168 7
button-up 120 5
byte-array 2584 129
c-stream 48 2
c-type 896 16
char-elt 16 1
clipboard 48 2
command-map 528 22
complex 32 2
condition 24 1
continuation 360 9
copy-action 16 1
cut-action 16 1
delete-action 16 1
doc-elt 16 1
drag 24 1
drag-timer 16 1
duplex-stream 32 1
edit-slot 16 1
effect 91904 2872
entry 24 1
float 3584 224
float-regs 72 3
gain-focus 16 1
gradient 144 6
hashtable 231248 14453
int-regs 16 1
interval 1224 51
key-down 1992 83
lexer 32 1
line-elt 16 1
line-reader 24 1
long-long-type 32 2
lose-focus 16 1
method 22152 923
module 768 16
motion 16 1
mouse-enter 16 1
mouse-leave 16 1
mouse-scroll 16 1
no-word 24 1
node 28160 440
one-line-elt 16 1
one-word-elt 16 1
operation 2200 55
parse-error 24 1
paste-action 16 1
pathname 24 1
plain-writer 16 1
queue 24 1
quotation 510992 21678
ratio 320 20
sbuf 16 1
select-all-action 16 1
slot-spec 14600 365
source-file 15880 397
stack-params 16 1
string 1243040 16064
struct-type 72 3
temp-reg 16 1
tombstone 32 2
update-object 16 1
update-slot 16 1
value 1600 50
vector 10368 648
vocab-link 24 1
word 275840 6896
word-elt 16 1
wrapper 21280 2660

The only major difference is in the space used by bignums; over 35mb worth! To get a better handle on what was going on, I obtained a list of all bignum instances from the VM, asked the VM for their size and printed out the resulting array:

[ bignum? ] instances [ size ] map pprint

All bignums were 16 or 24 bytes, except one which was 35mb! I had a hunch that this bignum was manifesting as a result of shift being called with a very high left shift count. Also, since the problem only occurred with interval inference enabled, I guessed that the interval-shift word was the problem. Setting a watch on this word with \ interval-shift confirmed my suspicions; a "data heap growing to ... bytes" message was printed right after interval-shift was called. Some more playing around in the listener revealed that the compiler was inferring a range for a value which had very large bounds, then this value was used as the shift count passed to shift, so the resulting range of values was exceptionally huge.

The fix is something I should have thought of in hindsight; if shift is applied to a value with a large range, the compiler should not attempt to compute the range of the result. Compiling something like 10 mod 100000000 * shift should not exhaust memory.

Now, there are two ways I could have arrived at this conclusion, and been able to fix the bug:

• Do what I did above: using features such as heap introspection, word watches, and the listener to track down the problem in a very short amount of time


• Banging my head against the wall, carefully reviewing every line of code I changed in the last few hours, and doing a "binary search" (adding/removing changed lines until I pinpoint the problem)

Because Factor has nice development tools, I was able to go for the first option. Of course even the second isn't that painful in Factor (there's no recompile/restart needed, even for most compiler changes).

I suspect the real reason Charles wants to see this feature removed from Ruby is that the JVM does not support it. Similar reasoning was used to propose that Ruby's upcoming Unicode support be crippled by using UTF16 to represent code points, because this is how Java's designers chose to do it in 1995. (The list goes on: some people don't like Ruby's continuations and think they should be removed, because, again, they're hard to get right in Java. Is anybody else bothered by this type of thinking?)

So, what's the point of this post? I just wanted to say, I'm glad I don't have to cripple my language because some guys at Sun made some bad decisions while I was still in elementary school.

Christopher Diggins is working on a turtle graphics library for Cat. Cool stuff.

Daniel Ehrenberg asks LtU readers a few questions about formalizing a minimal concatenative language.

If you're running Mac OS X, check your gcc version before compiling Factor. If you have this version, the resulting VM executable will be useless:

powerpc-apple-darwin8-gcc-4.0.0 (GCC) 4.0.0 20041026 (Apple Computer, Inc. build 4061)

The following version is OK:

powerpc-apple-darwin8-gcc-4.0.0 (GCC) 4.0.0 (Apple Computer, Inc. build 5026)

Thanks to Robbert van Dalen for first noticing this issue. Unfortunately there is no workaround. You have to upgrade your gcc.

gcc seems to have chronic issues with global register variables. This latest one is caused by gcc compiling a function to save and restore all registers in the range r13-r31, however r14 is the datastack pointer, which is clobbered as a result. Thankfully it is fixed in Apple's latest gcc, but I really wish gcc was more stable.

In my entire Java career, I never found a single bug which I could blame on the HotSpot JIT compiler. The Java language and libraries suck, but I really give the HotSpot team credit for writing a compiler which is fast, stable, and generates efficient code.

On the other hand, in only a few years of working on the C implementation of Factor, I've encountered plenty of gcc bugs. This is embarrassing for a project which claims to be the cornerstone of both Linux and Mac OS X.

Robbert van Dalen is currently rewriting his Enchilada language implementation in Factor. Part of his work has yielded a reusable library, libs/isequences. This library implements immutable sequences which are stored as balanced binary trees, with efficient lookup, concatenation and slicing operations. An interesting approach, quite different from immutable linked lists and the Factor core's mutable sequences. Cool stuff.

I want to play around with improved overflow check elimination. The Factor compiler already does some elementary overflow check elimination, but is only applicable to counted loops iterating over arrays. I want to generalize this in order to speed up Chris Double's YUV to RGB conversion. YUV to RGB conversion performs a lot of integer additions and multiplications, none of which ever overflow to bignums. If the compiler can infer this fact, then it can replace generic arithmetic with machine arithmetic, resulting in a nice speedup. So as a first step I cooked up an interval arithmetic library, which represents a closed interval as a pair of numbers. I was pleasantly surprised at how simple it was:

: cartesian ( seq1 seq2 -- seq3 )
 [ swap [ swap 2array ] map-with ] map-with concat ;

: interval-op ( i1 i2 quot -- i3 )
 -rot cartesian [ first2 rot call ] map-with
 dup infimum swap supremum 2array ; inline

: >int ( n -- interval ) dup 2array ;

: int+ ( i1 i2 -- i3 ) [ + ] interval-op ;

: int- ( i1 i2 -- i3 ) [ - ] interval-op ;

: int* ( i1 i2 -- i3 ) [ * ] interval-op ;

: int-shift ( i1 n -- i2 ) >int [ shift ] interval-op ;

: int/ ( i1 i2 -- i3 ) [ / ] interval-op ;

: int/i ( i1 i2 -- i3 ) [ /i ] interval-op ;

: int-intersect ( i1 i2 -- i3/f )
 [ [ first ] 2apply max ] 2keep [ second ] 2apply min
 2dup> [ 2drop f ] [ 2array ] if ;

It is worth noting that the int+ and int- words can be made more efficient:

: int+ ( i1 i2 -- i3 ) v+ ;
: int- ( i1 i2 -- i3 ) reverse v- ;

Elle Chaftari contributed an Oracle binding, it's in libs/oracle in darcs. Factor now has bindings for SQLite, PostgreSQL, MySQL, ODBC, and Oracle. The next step would be to implement an abstraction layer (like JDBC) and higher-level tools such as prepared statements, connection pooling, and O/R mapping. Anybody wants to take this on? :-)