Full text search in help now works

This news is a couple of days old, but I should mention that Factor's online help now supports full text search. At the moment, it performs exact matches after stemming, and uses a simple ranking algorithm to rank results based on the number of search terms that appear, with a special bonus given to terms appearing in the title. In the next round of improvements, I will investigate better ranking algorithms, and implement Levenshtein edit distance matching. For now this is good enough, and I'm going to focus on bug fixes as I get ready to release Factor 0.83.

GC bug

I found and fixed a bug in the garbage collector today. It seems to have been introduced when quotations became arrays. I triggered it by following the following steps:

• Running 'tests' in the UI
• Redefining a core word
• Recompiling everything
• Invoking full-gc

At this point the runtime crashed with a memory corruption error. Further investigation revealed that some code was holding on to an address which appears to have been moved by the GC. Several hours later, I uncovered the suspect code.

When a callback is called, the current interpreter state is saved in a stack_state struct, and these structures are chained. This includes a copy of all stacks, and the currently executing quotation. This is because each nested callback runs with its own isolated data and call stacks. When leaving the callback, the topmost entry in the linked list is removed, and the saved state is restored. The top-level stack_state struct does not contain a valid saved current quotation field, since there was no current quotation when the top level object was created. So the garbage collector would not consider the saved quotation there a valid root, and would not copy this object. However, the test for this case was wrong; it would ignore the saved current quotation in the first stack_state, and not the last. The result was that if callbacks were never used, then the first and last elements of the linked list would coincide and there would be no problem. However when the garbage collector was invoked from within a nested callback, the correct pointer would not be updated, and thus the interpreter would continue executing at an address which was not even valid anymore.

Full text search in help

I'm working on implementing a search engine for the Factor documentation. As a first step, I wrote a Factor version of the Porter stemmer algorithm, using the CL version as a reference point. Personally, I find the Factor code clearer than all the other versions on that page.

Nearly All Binary Searches and Mergesorts are Broken

The naive implementation of a binary search in a language with machine arithmetic (C, Java, ...) is prone to an overflow error. You can read about it at Joshua Bloch's weblog. Bloch writes:

"The binary-search bug applies equally to mergesort, and to other divide-and-conquer algorithms. If you have any code that implements one of these algorithms, fix it now before it blows up. The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code."

It is even harder to write correct code if your language is broken. It is sad that three decades(?) after the "number tower" became a common fixture of Lisp systems, we still have programmers struggling with integer overflow issues.

Why is Groovy is big?

Sorry to beat a dead horse, but I remember several months ago somebody in #concatenative (eiz, perhaps) mentioning that Groovy has reached 120,000 lines of Java code... they asked how can a scripting language get so big, especially as it doesn't provide its own runtime services and runs on the JVM? Well if you look at the Groovy CVS today, you'll see it has in fact managed to grow to 300,000 lines.

In comparison, Factor consists of 8400 lines of C and 29,000 lines of Factor. This includes a lot of code that a JVM-based language does not have to implement, such as platform-specific GUI bindings, native code generation, and the UI.

I tend to think the majority of code people write is overly complicated, full of redundancy, and designed for such flexibility that in practice is not needed at all. I hope one day this trend reverses.

Starting copy and paste support

I implemented some simple clipboard handling code for X11 and Cocoa. So far you can paste text from other applications, but you cannot copy text yet. This will wait for selection support in the UI -- I not only want text inside editor gadgets to be selectable, but all text in the UI, including pane output.

Redesigned Cocoa binding reduces image size by 2Mb

The old Cocoa binding generated one Factor word for each Objective C method. With only a dozen or so classes imported, this added 2 megabytes to the image size. The new binding instead stores a global mapping of selector names to return/argument types, and only compiles distinct words for each possible return/arg type combination. This reduces the number of stub words from several thousand to 22!

The new syntax is a bit more verbose, however it no longer requires importing a vocabulary for each class you intend to use. Instead, you use this syntax:

NSObject -> alloc -> init

This is in fact equivalent to the following, since -> is a parsing word:

NSOject "alloc" send "init" send

Calling methods in a superclass is done in a similar way:

SUPER-> dealloc
"dealloc" send-super

The compiler transforms the calls to send; in fact, the lookup of the selector is done at compile time, and the compiler turns the above snippet into something like this:

NSObject
T{ selector f "alloc" f } selector G:78604
T{ selector f "init" f } selector G:78604

The selector object caches the Objective C selector (a sort of internalized string, analogous to a Lisp symbol). The gensym is the cached message sender which only depends on the arglist. Here is a typical definition:

"id" f "objc_msgSend" { "id" "SEL" } alien-invoke

So the new binding style uses less space in the image, and is no slower since in the end the same code is generated, except with less redundancy and duplication. There is one disadvantage, though: if two imported methods have the same selector but different argument or return types, they will clash and you will not be able to send one of the two methods using send or send-super. There are various ways around this; either make method dispatch slower and look up arguments at runtime (this also makes it harder, but not impossible, to make it compile) or provide an alternative form of send, perhaps send*, which takes as class name and can be used in the case of clashes.