Thursday, November 30, 2006

Simple XML-RPC example - Factor talking to a Common Lisp web service

This example makes a paste to the LispPaste service; it requires the latest Factor from darcs:
IN: lisppaste
REQUIRES: libs/xml-rpc ;
USING: arrays kernel xml-rpc ;

: url "" ;

: lisppaste ( channel user title contents -- response )
4array "newpaste" swap <rpc-method> url post-rpc ;

You can use it like so:
"#concatenative" "jane_doe" "Test" "Testing testing" lisppaste

But please don't flood our channel with useless pastes. As soon as Dan fixes some bugs in the XML-RPC code, I will extend this example to have a GUI which offers a channel list.

rot13 in Factor

Daniel Ehrenberg implemented the rot13 algorithm in Factor. I added it to the demos/ directory; it is very simple and elegant:
IN: rot13
USING: kernel math sequences strings ;

: rotate ( ch base -- ch ) tuck - 13 + 26 mod + ;

: rot-letter ( ch -- ch )
{ [ dup letter? ] [ CHAR: a rotate ] }
{ [ dup LETTER? ] [ CHAR: A rotate ] }
{ [ t ] [ ] }
} cond ;

: rot13 ( string -- string ) [ rot-letter ] map ;

SBCL 1.0 released

Version 1.0 of Steel Bank Common Lisp has been finalized. Bill Clementson writes,
Well, the SBCL web site hasn't been updated yet and there's been no official announcement; however, SBCL has been tagged 1.0 in CVS, and the 1.0 tarball has been put up on SourceForge, so I guess this is it.

Congratulations to the SBCL developer team and all contributors. This is milestone in the history of Common Lisp.

Sunday, November 26, 2006

Using Factor for shell scripting

For a while now you could pass a source file to the Factor runtime to have it be run on startup. Now you can also pass a code snippet to evaluate:
./f -e='2 2 + .'
If you want Factor to exit immediately after,
./f -e='2 2 + .' -shell=none

Color picker example

I put together a short example showing how the "models" feature in the Factor UI can be used to wire together interfaces with very little code. The example displays a window with three sliders for changing the R/G/B values of the color shown in a preview pane. Also, a label displays numeric R/G/B values.

The code is in darcs, examples/color-picker.factor. Here is a walk-through:

We start with the usual vocabulary boilerplate:
IN: color-picker
USING: gadgets-sliders gadgets-labels gadgets models arrays
namespaces kernel math prettyprint sequences ;

We have a word which creates a slider with a maximum value of 255, and a scrolling increment of 1 when clicking the up/down arrows:
: <color-slider> ( -- gadget )
1 over set-slider-line
255 over set-slider-max ;

Now, a word which creates a gadget whose fill color comes from a model:
: <color-preview> ( model -- gadget )
<gadget> { 100 100 } over set-rect-dim
[ set-gadget-interior ] <control> ;

A word which creates a model that wraps an underlying model, converting R/G/B triplets from 0 to 255 to an instance of the <solid> class, which can then be passed to set-gadget-interior:
: <color-model> ( model -- model )
[ [ 256 /f ] map 1 add <solid> ] <filter> ;

A word to create three slider gadgets, and a model holding the chosen R/G/B triple:
: <color-sliders> ( -- model gadget )
<color-slider> dup , control-model
<color-slider> dup , control-model
<color-slider> dup , control-model
3array <compose>
] { } make make-pile 1 over set-pack-fill ;

Finally, a word to put everything together; the color sliders, the color-changing preview gadget, and finally a label control which displays numeric R/G/B values:
: <color-picker> ( -- gadget )
{ [ <color-sliders> ] f f @top }
{ [ dup <color-model> <color-preview> ] f f @center }
{ [ [ unparse ] <filter> <label-control> ] f f @bottom }
} make-frame ;

And here is the module boilerplate:
PROVIDE: examples/color-picker ;

MAIN: examples/color-picker
<color-picker> "Color Picker" open-titled-window ;

A screenshot:

Factor 2 Enterprise Edition

... now with support for SOA, B2B, and outsourcing.

No, seriously, Daniel Ehrenberg has implemented an XML-RPC client and server in Factor; the code is in darcs, contrib/xml-rpc. Good stuff! After I release Factor 0.87 I'm going to get back to work on the web framework, and cook something up so that web apps automatically have an XML-RPC interface. I'd also like to put together a demonstration app that uses the XML-RPC client to make pastes at Lisppaste.

Thursday, November 23, 2006

OpenFirmware is now free software

OpenFirmware, the Forth-based monitor and bootloader used on Sun workstations and (all but the earliest) PowerPC Macs, is now free software. You can browse the source code.

Back from Montréal

I had a lot of fun presenting at the MSLUG, there was a great turnout. Everybody asked lots of questions and I think they all had a great time. It was well worth the two and a half hour bus ride there and back! Sébastien Pierre has a nice writeup, if your understand French. I don't but I was able to make sense of most of what he wrote :-)

The slides I used are available in the darcs repository. Make sure you have running the latest image, and then from the UI, do:
"examples/mslug-talk" run-module
Or alternatively, press C+m, and type mslug (or any other sequence until the first completion in the popup is the correct module) then press ENTER. Use the arrow keys to navigate the slides. However I don't think they will make much sense, unless you were there, since I said a lot more than what was written in the bullet points.

Friday, November 17, 2006

Genuine enterprise thought leadership

You just can't make this stuff up. Seen here:

"JavaScript growth is flat while pardoxically AJAX is taking off. In other words, we will take the AJAX and rich applications thank you very much, but please keep your tinker-toy language."

In other news, Web 2.0 is taking off, but HTML is so 90's!

Thursday, November 16, 2006

Most people who criticize Lisp don't understand it

Disclaimer: I don't program in Common Lisp these days and I don't claim to speak for the Lisp community at all, however I think I do know the Lisp language reasonably well.

Just looking the last few weeks of postings on reddit related to Lisp, people raise the following objections:
  • Lisp does not interface with the C-based world easily, unlike scripting languages -- this is clearly false, since most Lisp implementations have easy to use FFIs. To bind a C library to Ruby, you have to write C code which glues the library to the Ruby runtime system. With CFFI (which is portable across CL implementations), you just list the function prototypes in your Lisp file and you're ready to go. You can also pass structs, etc. Factor's C library interface works the same way.

  • Common Lisp was designed to perform well on Lisp machines only, and makes no concessions to ordinary computers. - this is partially true, but the CL standard did omit some features found on Lisp machines which would be difficult to implement efficiently on conventional hardware. However none of this can change the fact that Common Lisp implementations are an order of magnitude faster than scripting languages.

  • Look at all these parentheses! - of course if you don't need metaprogramming, macros, and code-as-data, may as well not use Lisp.

There are many other common misconceptions. The "Lisp only supports linked lists" and "Lisp is unsuitable for writing real-world programs" memes seem to have died down in the last few years, but more myths have taken their place. This leads me to believe that the main problem the Lisp community faces to ensure wider adoption (assuming wider adoption is what they want, which is not necessarily the case) is not a technical one, or an internal social problem as some suggest, but rather an education problem.

Most people simply don't know anything about Lisp, but feel qualified to discuss it and criticize it. Like I said, I'm not a member of the Lisp community (whatever that may be), but when advocating Lisp, Lispers should remember that a lot of things that they take for granted (sane language semantics, C library interface that works, metaprogramming, good performance from a high-level language) are completely foreign to most programmers! There's a communication gap.

And to all the programmers learning new languages, not just specifically Lisp, please hold off criticism until you know the language and have completed a significant project in it. If you did not get that far, don't criticize the language, and put it down to lack of time, lack of motivation or personal failing.

I can rag on Java all I want because I know it better than most Java advocates. But if you were first exposed to Lisp 2 weeks ago, then don't make yet another blog posting about parentheses, even if you work for Google. You're just wasting bandwidth.

Wednesday, November 15, 2006

Archaic Factor screenshots

Factor's UI has come a long way since the early days:

Some features were abandoned:

Doug Coleman's weblog

Doug Coleman now has a weblog. His first entry talks about compiling Factor on Windows from darcs. This involves setting up ssh, darcs, and msys.

Reminder: Factor talk in Montreal

I will be presenting Factor at the Montreal Scheme/Lisp User's Group next Wednesday, November 22nd.

I'm slowly putting together a presentation. Slides are defined using Factor help markup using a custom stylesheet, and everything is displayed by the Factor UI. So far I have 248 lines of code, most of which is the markup for slides. I'll put it in examples/mslug-talk when it is done.

Tuesday, November 14, 2006

Factor 0.86 released

Version 0.86 of the Factor programming language is now out.

Windows and Mac Intel packages were provided courtesy of Doug Coleman (thanks Doug!)


+ Core
- Improved memory management code leads to reduced memory consumption, less frequent garbage collections and fixes a few corner cases where Factor could run out of heap even if a GC would have freed enough memory to proceed
- Improved prettyprinter low lays out code in a more pleasing manner
- Windows native I/O has been sped up (Doug Coleman)

+ UI
- Double and triple clicks are now recognized, and can be used to select text in the editor gadget
- Windows now update while being resized on Windows

+ Stack effect inference
- The new infer. word should be called instead of infer, since it presents information in a more pleasing way
- Stack effect inference now infers variables read and written by a quotation to facilitate code comprehension and debugging

+ Module system
- The syntax for PROVIDE: has changed, consult the documentation
- Modules can now provide a main entry point, see run-module and MAIN:
- Modules can now provide documentation, see Documenting modules

+ Contributed libraries
- New contrib/cpuinfo (Doug Coleman)
- Updated contrib/match (Chris Double)
- Updated contrib/parser-combinators (Chris Double)
- Updated contrib/postgresql (Doug Coleman)
- Updated contrib/process (Doug Coleman)
- Updated contrib/sqlite (Doug Coleman)
- Updated contrib/textmate (Benjamin Pollack)
- Updated contrib/tuple-db (Doug Coleman)
- Updated contrib/vim (Doug Coleman)
- Updated contrib/xml (Daniel Ehrenberg)

Haar wavelet transform in Factor

Here is the Haar wavelet transform implemented in Factor. This is only the 1-dimensional version:
: averages ( seq -- seq )
[ first2 + 2 / ] map ;

: differences ( seq averages -- differences )
>r 0 <column> r> [ - ] 2map ;

: haar-step ( seq -- differences averages )
2 group dup averages [ differences ] keep ;

: haar ( seq -- seq )
dup length 1 <= [ haar-step haar swap append ] unless ;

Sunday, November 12, 2006

Some developer tools in the incubator

I have a small file of "work in progress" developer tools which I'm not releasing yet, which so far includes:
  • Calls in/out at the vocabulary level, rather than individual words
  • Finding words which read or write a given variable
  • Shortest path between two words
  • Searching for unloaded modules on disk

Some of these will eventually make it into the core. I also want to develop a graphical cross-referencing tool in the UI which combines various words one can invoke in the listener into one coherent interface.

Taming variables

I developed some new tools which perform static analysis of variable usage.

Factor's variables are dynamically scoped and very simple, there is a global namestack holding hashtables. Nesting a scope pushes a hashtable on the stack, variable lookups search up the namestack, and variable assignments store the new value in the topmost hashtable on the namestack.

The infer word has been replaced with an infer. word which gives variable usage information obtained by statically analyzing the code. Those in the know will recognize that this is a ripoff of InterLisp's MASTERSCOPE package. Here is an example:
[ 3 * x set ] infer.

* Stack effect:
( object -- )
* Writes free variables:

But if you wrap this in a with-scope, the assignment is lost as soon as the scope ends and there is no observable side effect:
  [ [ 3 * x set ] with-scope ] infer.
* Stack effect:
( object -- )

On the other hand, reading a variable from a nested scope might go up a scope if the variable is not defined, and so it can be observed from the outside:
  [ [ x get ] with-scope ] infer.
* Stack effect:
( -- object )
* Reads free variables:

But if you assign the variable in scope first, then we cannot observe the read:
  [ [ 5 x set [ x get ] with-scope ] with-scope ] infer.
* Stack effect:
( -- object )

Now, of course because this is built on stack effect inference, everything works if you have a word which indirectly calls get or set.

It even understands combinators, for example this one that applies 2 * to the value of x:
  [ x [ 2 * ] change ] infer.
* Stack effect:
( -- )
* Reads free variables:
* Writes free variables:

No special support for inferring change is defined, it just looks at the definition of change;
: change ( variable quot -- ) 
>r dup get r> rot slip set ; inline

Finally, it has special support for recording words which directly read and write globals:
  [ [ 5 x set-global ] with-scope ] infer.
* Stack effect:
( -- )
* Writes global variables:

Saturday, November 11, 2006

strongForth 1.1 released

strongForth is a statically-typed low-level Forth-like language. This release adds a floating point wordset. Right now it only runs under DOS (its actually a very old project), hopefully it will be ported to 32-bit Unix platforms at some point in the future.

Insane Cocoa bug

So it seems the frame method of NSWindow returns some client-side value, which is updated when the window receives events notifying it that it has been moved or resized. Which is all very well, but it seems that if you move the window around while it is not responding, then the frame method returns the old value! This is absurd.

It means that for example if you reload some files in the Factor UI listener, which then causes a 10-second recompile, during which you move the window, then mouse handling is completely screwed up after Factor starts responding again.

Does anybody know if there is a way to query the window system for the window's actual location?

Update: This only happens under certain circumstances. Very weird. I'll try to narrow it down.

Update 2: Actually it is pretty easy to reproduce. Start Factor and type 30000000 [ ] times (or anything else which takes several seconds to run). Then move the listener window around for a few seconds, then switch to another application. When Factor is done, switch back, and it will not respond to clicks because it will think the mouse location is different than what it actually is.

Friday, November 10, 2006

Factor 0.86 is ready

Factor 0.86 is now ready for release. As a few people on the mailing list have requested, I'm making this announcement before actually releasing Factor so that the code in darcs can get some extra testing. I'll be testing the X11 UI backend and AMD64 compiler backend tomorrow.

Thursday, November 09, 2006

You know you're too lazy to learn better tools when...

You try to justify the flaws in what you currently use on the basis that these flaws, while forcing you to do a lot more work than necessary and increasing turn-around time, encourage you to "design better".

Sad people

Some people are so blinded by Java zealotry that they choose to make a weblog dedicated to personal attacks on comp.lang.lisp posters.

Why Java zealotry you ask? I think a trait unique to Java programmers is to go antagonize other language communities, pretending to be interested in learning that language, when in fact they're just looking for excuses not to learn, and to criticize.

XML parser now supports namespaces

Daniel Ehrenberg has updated the contrib/xml module to support XML namespaces, with XML-RPC support coming up next. Dan used to be active in the Factor community six months or so ago, and now he's back, which is great. Unlike some open source projects, Factor contributors seem to stick around for a long time. When I was working on jEdit, a big problem was people throwing a few patches and plugins over the fence, then disappearing a week later...

Inline allocation refactoring

On PowerPC and x86 processors with SSE2, Factor supports floating point intrinsics, and the final boxing of a floating point value is entirely open-coded, so no GC check was done. Fixing this was the final stage of the Allocation refactoring.

At the end of a basic block, the compiler calls end-basic-block, which boxes any floating point values stored in registers, and moves them to the data stack. It also moves all other integer values and pointers to the stack too. Within a basic block, no stack writes are performed, and stack shuffling takes place at compile time in the form of register renaming. The fix for the inline allocation GC issue was to simply leave 1kb free at the top of the heap at all times, and if any float values were boxed, compile a call to a C function which performs a GC check in end-basic-block. This smells like the old issue that the entire GC refactoring was supposed to avoid (the GC on 75% heap consumption being inadequate) however very little memory is allocated by boxing floats, much less than 1Kb.

However there was one sticking point; in a handful of locations, end-basic-block would be called to generate machine code in a context where certain register values are not to be clobbered. For example, conditionals worked this way: first, the value at the top of the stack would be popped (which might not generate any code at all, if it is in a register), then the basic block would end so registers would sync with the in-memory stack, and then the conditional jump was performed based on the value of this register. This would no longer work, since end-basic-block could now generate a call into C, and thus the register holding the condition would be clobbered. The fix is not to end the basic block at a conditional jump, but instead "split" the virtual register representation of the stack at both branches. So for example if r3 held some known value before a conditional, the compiler could reuse this value in either branch without reading it back in.

Another place where the compiler called end-basic-block was when generating fixnum intrinsics which could overflow. These open-coded intrinsics are more efficient than calls into C, since in the common case of there not being an overflow, the code path re-uses registers rather than reading from the stack, and so on. For example, fixnum+ adds two integers, and if the result overflows, it allocates a bignum. Again, the problem was that it would read two values from the stack into registers (which might not have generated any machine code at all, if the value were already in registers), then it would end the basic block, then it would add them, and if an overflow occurred, it would call into C to allocate a bignum. This worked in the past, but now that the end of a basic block can call GC, the fix here is to open-code the bignum allocation code, and therefore avoid the need to end the basic block before fixnum+ is assembled in.

The other cases where end-basic-block were called remain untouched; namely, before jumping to another word definition, before returning from a word definition, and before an explicit alien call into C. In these cases, no values were held on in registers so a GC is safe. The removal of calls to end-basic-block from around conditionals and overflowing fixnum primitives means the compiler can keep more values in registers, generate less code to shuffle values between registers and memory, and box less floats. And of course, it also means that certain operations won't run out of memory even if plenty is available, simply because no GC check gets done.

I still have to fix the fixnum* intrinsic on both platforms; this results in an inline allocation of a 2-cell bignum, which is trickier than 1-cell bignum like fixnum+. I'm also hunting down a compiler bug which results in some words from contrib/crypto being miscompiled. Once these two items are done, I will release 0.86.

jEdit 4.3pre8 released

The jEdit developers have released version 4.3pre8.

Saturday, November 04, 2006

Article about the Cat programming language

Christopher Diggins has written an article about the Cat programming language which describes the implementation in some detail. Cat is a statically-typed stack language.

Memory allocation redesign pushed; 0.86 almost ready

The patches implementing the redesign I talked about a few days ago are now in the repository. There is one remaining instability, and that is inline float allocators do not check if a GC is necessary yet. So it is possible to run out of memory that way. I will fix this shortly. Next I will be updating documentation and fixing a few minor bugs, and then releasing 0.86!

Annotations instead of C code for JNI

A Java programmer has realized that JNI is a steaming pile of shit. He writes:

The more I think about it, the more I think something like the following would make sense:
public void bar();

Damn right it makes sense. There is no good reason one should have to program in C, and learn the internals of their language runtime, to call C libraries, even those involving structures, callbacks, and so on.
The Java OpenGL binding is 40,000 lines of Java code, including some hairy Java and C source generation, and a complicated build process (when I was doing my Java game, I never managed to get JoGL to compile, even after downloading half a dozen dependencies and playing with the build.xml. I always used the binary packages).
The Factor OpenGL binding is less than 2,000 lines of code consisting of a handful of source files. We also have bindings to FreeType, Cocoa, WinAPI, a USB library, and various other things, all implemented in Factor, without huge amounts of boilerplate or C code.

Friday, November 03, 2006

Programming languages

If you want a programming language implementation, you have to pick two out of three features:
  • Good performance
  • Expressive language
  • Popular

I know which two I care about. Assembly only satisfies the first one, Common Lisp satisfies the first two, Java satisfies the first and last, and of course Ruby has the last two but its performance sucks. No language I'm aware of has all three at this stage of human history.

Thursday, November 02, 2006

Memory allocation refactoring

Factor's garbage collector moves objects around in memory. This means that if there is not enough memory to satify an allocation request, the garbage collector has to be able to find all pointers to live objects and update them if necessary.

Until now, memory allocation in the Factor runtime did not check to see if the heap was full:
INLINE void allot_barrier(CELL address)
F_CARD *ptr = ADDR_TO_CARD(address);
F_CARD c = *ptr;
CELL b = card_base(c);
CELL a = (address & ADDR_CARD_MASK);
*ptr = (card_marked(c) | ((b < a) ? b : a));

INLINE void *allot_zone(F_ZONE *z, CELL a)
CELL h = z->here;
z->here = h + align8(a);

return (void*)h;

INLINE void *allot(CELL a)
return allot_zone(&nursery,a);

Instead every primitive which could at some stage allocate memory would simply first check if the heap was 75% full, and if so, call the GC. So the idea was that we call the GC early enough, and hope that the heap does not completely fill up until the next GC check. If the heap did fill up, a guard page would be hit, but all that we could do was kill Factor, since calling the GC from the signal handler is out of the question -- suspended stack frames could contain C local variables pointing to Factor objects.

Indeed, the GC check was always performed at points where no Factor object could be stored in a C local variable, so this made things very simple. The disadvantage is that you cannot use more than 75% of the heap, every primitive has to remember to call the GC check, and if some primitive enters with 74% of the heap full and suddenly allocates a large amount of memory, Factor would die with an 'out of memory' error even if after a GC there would be enough. Also this approach made it hard to implement a growable data heap -- at what point do you grow? If the GC check did not free enough memory, you could grow the heap there, but if the GC check did free enough memory but the primitive subsequently allocates a huge array, you'd run out of memory instead of growing the heap. So the manual GC check, and restriction on performing a GC when C variables contain roots, had to go.

So I decided to redo things, and instead potentially perform GC from the lowest-level allocation functions. The allot() function now looks like this:
INLINE void maybe_gc(CELL a)
if( + a > nursery.limit)

INLINE void *allot(CELL a)
return allot_zone(&nursery,a);

This means that before calling a runtime function which can potentially allocate memory, the C code has to register any local variables which can contain objects as GC roots. For example, here is the low-level function implementing the <array> primitive:
F_ARRAY *allot_array(CELL type, F_FIXNUM capacity, CELL fill)
int i;
F_ARRAY* array = allot_array_internal(type, capacity);
for(i = 0; i > capacity; i++)
return array;

The REGISTER_ROOT macro adds the object to a stack, internal to the runtime, and the UNREGISTER_ROOT macro removes the topmost object and stores it back in the given variable. The GC scans this stack for roots just like it does with the data stack, etc. This stack is not accessible from the Factor side, and if an error is thrown between calls to REGISTER_ROOT and UNREGISTER_ROOT, its contents are reset.

There are only a few cases where GC roots must be registered this way, and most of them are in the bignum code, especially after I simplified a lot of runtime C code and moved a number of primitives from C code into the Factor library. However forgetting to register a root can have disastrous consequences, namely random, hard to reproduce crashes (after all, 99% of the time a given allocation call does not GC). I developed two testing tool to help catch this:
  • After a GC, overwriting the former semispace with junk data so that reading from it immediately causes bogus behavior, rather than subtle corruption
  • Modifying the allocation function in the runtime to call the GC every time, or every 100 allocations

These two debugging features slow things down considerably, but have helped me find a number of problems and I'm confident I'll get the root registration 100% correct this way. The first item will be available to users as the -S command line switch; it was actually first suggested by Doug Coleman in the context of cryptography algorithms, where you don't want your private key to hang around in memory longer than needed in the event of your swap file being stolen (although this seems way too paranoid for me). Obviously the second feature will be removed before release and I don't intend to add a switch to GC on every allocation after this refactoring is done.

I've almost finished getting everything working again. Compiled alien calls and callbacks need to be updated now, since the segment of code generated by the compiler to convert Factor objects to C values (and vice versa) now needs to accomodate the fact that objects may be moved around in the middle of this process. Also in one place, the runtime's allot() function is bypassed, and allocation of a boxed float is done manually in a compiled intrinsic; this ensures that this can be done in a "basic block" without clobbering register contents, improving the efficiency of compiled floating point code.

Interestingly enough, this refactoring has shaved several hundreds of lines of C code from the runtime. It gave me a chance to review the C code and clean it up and remove some redundancies.

Once everything is stable and I fix some minor bugs on my to do list, I will release 0.86. I will not implement a growable data heap until 0.87, however with this refactoring it has become much easier to do.