The Awesome Factor

Code coverage tool

2011-11-01T15:11:00.000-07:00

Motivation for writing a coverage tool

In Factor, the old code-is-data adage is true and can be used to our advantage when writing runtime tools. Code is stored in what we call a quotation, which is just a sequence of functions (words) and data literals and can be called at runtime. A function (or word) in Factor is simply a named quotation, and typing that word name causes the quotation to run.

Since quotations in Factor do not terminate early unless an exception is thrown, we know that if each quotation gets run, then we have run all of the code. While this won't tell us if there are logic errors, and while we can still have code fail due to unexpected inputs, at least we can be sure that all of the code is getting exercise and there are no paths that never get run. We can use the results of this tool to write better unit tests.

Demo of the coverage tool

As a simple demo, there's a fun algorithm that produces a sequence of numbers from a start number, where the sequence always seems to end at one. For any integer greater than zero, the the Collatz conjecture states that this sequence will eventually reach the number one. The algorithm goes as follows: take any counting number (1, 2, ...) and either multiply by three and add 1, or divide by two, if the number is odd or even, respectively, and record the sequence of numbers until you reach the number one. This conjecture has been found to be true experimentally for every number up to 10^18, but no proof exists that it's true for all possible inputs.

For example, the Collatz sequence for 3 is: { 3 10 5 16 8 4 2 1 }

We can come up with a solution pretty easily (partially taken from the Project Euler #14, in extra/).

We do the command: "collatz" scaffold-work

Click on the link, edit the file ~/factor/extra/collatz/collatz.factor

USING: combinators.short-circuit kernel make math ;
IN: collatz

: next-collatz ( n -- n )
    dup even? [ 2 / ] [ 3 * 1 + ] if ;

: collatz-unsafe ( n -- seq )
    [ [ dup 1 > ] [ dup , next-collatz ] while , ] { } make ;

ERROR: invalid-collatz-input n ;

: collatz ( n -- seq )
    dup { [ integer? ] [ 1 >= ] } 1&&
    [ collatz-unsafe ]
    [ invalid-collatz-input ] if ;

We're going to be extra careful here to demonstrate the code coverage tool, so I added error checking to make sure it's an integer greater than or equal to one.

Let's write some unit tests to make sure it works.

Run the command: "collatz" scaffold-tests
Now click on the link to edit the file it created, ~/factor/extra/collatz/collatz-tests.factor

USING: tools.test collatz ;
IN: collatz.tests

[ { 1 } ] [ 1 collatz ] unit-test
[ { 2 1 } ] [ 2 collatz ] unit-test
[ { 3 10 5 16 8 4 2 1 } ] [ 3 collatz ] unit-test

If we run "collatz" test, we see that all tests pass.

Now, let's see how well we did with code coverage.

We run the command:

IN: scratchpad USE: tools.coverage "collatz" test-coverage .
Loading resource:work/collatz/collatz-tests.factor
Unit Test: { [ { 1 } ] [ 1 collatz ] }
Unit Test: { [ { 2 1 } ] [ 2 collatz ] }
Unit Test: { [ { 3 10 5 16 8 4 2 1 } ] [ 3 collatz ] }
{
    { next-collatz { } }
    { collatz { [ invalid-collatz-input ] } }
    {
        invalid-collatz-input
        { [ \ invalid-collatz-input boa throw ] }
    }
    { collatz-unsafe { } }
}

What this tells us is we had quotations in the collatz word and the invalid-collatz-input words that did not get called. Of course -- we never passed it anything other than valid inputs. How about passing it a string or a negative integer?

Now the result looks better:

IN: scratchpad "collatz" test-coverage .
Loading resource:work/collatz/collatz-tests.factor
Unit Test: { [ { 1 } ] [ 1 collatz ] }
Unit Test: { [ { 2 1 } ] [ 2 collatz ] }
Unit Test: { [ { 3 10 5 16 8 4 2 1 } ] [ 3 collatz ] }
Must Fail With: { [ "hello world" collatz ] [ invalid-collatz-input? ] }
Must Fail With: { [ -50 collatz ] [ invalid-collatz-input? ] }
{
    { next-collatz { } }
    { collatz { } }
    { invalid-collatz-input { } }
    { collatz-unsafe { } }
}

We can even get a number for how well tests cover a vocabulary:

"collatz" %coverage .
1.0

The implementation of the coverage tool

Every word in Factor stores its definition in the `def' slot. If we examine this slot, we see that it's a quotation that may contain other quotations. Using the annotation vocabulary, we can add code that executes before and after the code in the quotation. What the coverage tool does is adds a container that stores a boolean flag at the beginning of each quotation, and when the quotation gets run, the flag is set to true. This tool can be turned on and off, independent of the containers being in place, with the coverage-on and coverage-off words.

Here's a word that turns a Roman numeral into an integer:

\ roman> def>> .
[ >lower [ roman>= ] monotonic-split [ (roman>) ] map-sum ]

After annotating it, the new definition looks like:

\ roman> add-coverage \ roman> def>> .
[
    T{ coverage } flag-covered >lower
    [ T{ coverage } flag-covered roman>= ] monotonic-split
    [ T{ coverage } flag-covered (roman>) ] map-sum
]

The flags are all set to false right now. After turning on the flag to let enable the coverage code and running the word, we see a change:

coverage-on "iii" roman> drop \ roman> def>> .[
    T{ coverage { executed? t } } flag-covered >lower
    [ T{ coverage { executed? t } } flag-covered roman>= ]
    monotonic-split
    [ T{ coverage { executed? t } } flag-covered (roman>) ]
    map-sum
]

Notice that all of the coverage containers have been executed. To generate the report, we simply iterate over each word and collect all of the quotations where this flag has not been set -- these quotations never ran.

In writing this article, I realized that each quotation should have a flag on exit as well, in case an exception gets thrown in the middle of executing this quotation and control never reaches the end. Partially-executed quotations will soon be reported by the tool, after I make this fix.

I hope you can use this tool to improve your Factor code. Have fun!

Filling a file with zeros

2010-09-04T13:31:00.000-07:00

In this blog post I'll demonstrate a few of ways to fill a file with zeros in Factor. The goal is to write a some number of bytes to file in the least amount of time and using only a small amount of RAM; writing a large file should not fail.

Filling a file with zeros by seeking

The best way of writing a file full of zeros is to seek to one byte from the end of the file, write a zero, and close the file. Here's the code:

: (zero-file) ( n path -- )
    binary 
    [ 1 - seek-absolute seek-output 0 write1 ] with-file-writer ;

ERROR: invalid-file-size n path ;

: zero-file ( n path -- )   
    {
        { [ over 0 < ] [ invalid-file-size ] }
        { [ over 0 = ] [ nip touch-file ] }
        [ (zero-file) ]
    } cond ;

The first thing you'll notice about the zero-file is that we special-case negative and zero file sizes. Special-casing zero file length is necessary to avoid seeking to -1, which does everything correctly but throws an error in the process instead of returning normally. Special-casing negative file sizes is important because it's always an error, and though the operation fails overall, the file-system can become littered with zero-length files that are created before the exception is thrown.

To call the new word:

123,456,789 "/Users/erg/zeros.bin" zero-file
"/Users/erg/zeros.bin" file-info size>> .
123456789

Copying a zero-stream

With Factor's stream protocol, you can write new kinds of streams that, when read from or written to, do whatever you want. I wrote a read-only zero-stream below that returns zeros whenever you read from it. Wrapping a limit-stream around it, you can give the inexhaustible zero-stream an artificial length, so that copying it reaches an end and terminates.

TUPLE: zero-stream ;

C: <zero-stream> zero-stream

M: zero-stream stream-read drop <byte-array> ;
M: zero-stream stream-read1 drop 0 ;
M: zero-stream stream-read-partial stream-read ;
M: zero-stream dispose drop ;

:: zero-file2 ( n path -- )
    <zero-stream> n limit-stream 
    path binary <file-writer> stream-copy ;

The drawback to this approach is that it creates 8kb byte-arrays in memory that it immediately writes to disk.

Setting the contents of a file directly

Using the set-file-contents word, you can just assign a file's contents to be a sequence. However, this sequence has to fit into memory, so this solution is not as good for our use case.

:: zero-file3 ( n path -- )
    n <byte-array> path binary set-file-contents ;

Bonus: writing random data to a file

The canonical way of copying random data to a file in Unix systems is to use the dd tool to read from /dev/urandom and write to a file. But what about on Windows, where there is no /dev/urandom? We can come up with a cross-platform solution that uses method number two from above, but instead of a zero-stream, we have a random-stream. But then what about efficiency? Well, it turns out that Factor's Mersenne Twister implementation generates random numbers faster than /dev/urandom on my Macbook -- writing a 100MB file from /dev/urandom is about twice as slow as a Factor-only solution. So not only is the Factor solution cross-platform, it's also more efficient.

TUPLE: random-stream ;

C: <random-stream> random-stream

M: random-stream stream-read drop random-bytes ;
M: random-stream stream-read1 drop 256 random ;
M: random-stream stream-read-partial stream-read ;
M: random-stream dispose drop ;

:: stream-copy-n ( from to n -- )
    from n limit-stream to stream-copy ;

:: random-file ( n path -- )
     
    path binary <file-writer> n stream-copy-n ;

! Read from /dev/urandom
:: random-file-urandom ( n path -- )
    [
         path
        binary <file-writer> n stream-copy-n
    ] with-system-random ;

Here are the results:

$ dd if=/dev/urandom of=here.bin bs=100000000 count=1
1+0 records in
1+0 records out
100000000 bytes transferred in 17.384370 secs (5752294 bytes/sec)

100,000,000 "there.bin" random-file
Running time: 5.623136439 seconds

Conclusion

Since Factor has high-level libraries that wrap the low-level libc and system calls used for nonblocking i/o, we don't have to deal with platform-specific quirks at this level of abstraction like handling EINTR, error codes, or resource cleanup at the operating system level. When calls get interrupted, when errno is set to EINTR after the call returns, the i/o operation is simply tried again behind the scenes, and only serious i/o errors get thrown. There are many options for correct resource cleanup should an error occur, but the error handling code we used here is incorporated into the stream-copy and with-file-writer words--resources are cleaned up regardless of what happens. We also demonstrated that a Factor word is preferable to a shell script or the dd command for making files full of random data because it's more portable and faster, and that custom streams are easy to define.

Finally, there's actually a faster way to create huge files full of zeros, and that's by using sparse files. Sparse files can start off using virtually no file-system blocks, but can appear to be as large as you wish, and only start to consume more blocks as parts of the file are written. However, support for this is file-system dependent and, overall, sparse files are of questionable use. On Unix file-systems that support sparse files, the first method above should automatically creates them with no extra work. Note that on MacOSX, sparse file-systems are supported but not enabled by default. On Windows, however, you have to make a call to DeviceIoControl. If someone wants to have a small contribution to the Factor project, they are welcome to implement creation of sparse files for Windows.

Edit: Thanks to one of the commenters, I rediscovered that there's a Unix syscall truncate that creates zero-length files in constant time on my Mac. This is indeed the best solution for making files full of zeros, and although unportable, a Factor library would have no problem using a hook on the OS variable to call truncate on Unix and another method on Windows.

Monotonic timers

2009-11-19T18:59:00.001-08:00

Factor has had a calendar library for several years now. While it's great for converting timestamps to human-readable formats, calculating holidays, and finding the number of days between two dates, it's the wrong concept to use for timing code, alarms, and thread switching. In such cases where you don't need an actual date, you should use monotonic timers, which are counters that always increment from an unspecified time in the past and aren't affected by changes to the system time. Even if the user changes the clock, these monotonic timers don't go back in time -- they keep increasing. Let's look at the implementation.

Implementation of monotonic timers

Although I originally implemented monotonic timers as a Factor library, I moved the code into the C++ VM as a primitive called nano-count. To distinguish the usage of this word from the word formerly known as micros, I renamed micros to system-micros. Having the word "system" in the name of one time-returning word, and having "count" in the other, hopefully leads to less confusion on the user's part.

Windows

The code I came up with for Windows looks like this:

u64 nano_count()
{
    static double scale_factor;

    static u32 hi = 0;
    static u32 lo = 0;

    LARGE_INTEGER count;
    BOOL ret = QueryPerformanceCounter(&count);
    if(ret == 0)
        fatal_error("QueryPerformanceCounter", 0);

    if(scale_factor == 0.0)
    {
        LARGE_INTEGER frequency;
        BOOL ret = QueryPerformanceFrequency(&frequency);
        if(ret == 0)
            fatal_error("QueryPerformanceFrequency", 0);
        scale_factor = (1000000000.0 / frequency.QuadPart);
    }

#ifdef FACTOR_64
    hi = count.HighPart;
#else
    /* On VirtualBox, QueryPerformanceCounter does not increment
    the high part every time the low part overflows.  Workaround. */
    if(lo > count.LowPart)
        hi++;
#endif
    lo = count.LowPart;

    return (u64)((((u64)hi << 32) | (u64)lo) * scale_factor);
}

It could probably be optimized by only calling QueryPerformanceFrequency once, but I don't set the processor affinity yet, so I'm not convinced it will work in every case. As you can see, it's pretty simple: the performance counter is queried and returns a number of clock cycles since some arbitrary beginning epoch, and then that time is scaled by the clock frequency to get nanoseconds.
Edit: This code contains a workaround for a VirtualBox counter bug.

Some Unix systems

u64 nano_count()
{
    struct timespec t;
    int ret;
    ret = clock_gettime(CLOCK_MONOTONIC,&t);
    if(ret != 0)
        fatal_error("clock_gettime failed", 0);
    return t.tv_sec * 1000000000 + t.tv_nsec;
}

Calling clock_gettime from the librt library or, on some platforms, as a system call, gives you the number of nanoseconds since an arbitrary start point in the past. The timespec struct has a seconds and a nanoseconds slots, while the timeval struct (used by system-micros) has seconds and microseconds.

Mac OSX

u64 nano_count()
{
    u64 time = mach_absolute_time();

    static u64 scaling_factor = 0;
    if(!scaling_factor)
    {
        mach_timebase_info_data_t info;
        kern_return_t ret = mach_timebase_info(&info);
        if(ret != 0)
            fatal_error("mach_timebase_info failed",ret);
        scaling_factor = info.numer/info.denom;
    }

    return time * scaling_factor;
}

The MacOSX code is a bit different because Apple didn't implement clock_gettime. Instead, they have a couple of Mach functions that function just like the Windows code, with one returning a count and the other returning clock frequency information.

Upgraded alarms

The alarms vocabulary now uses monotonic timers instead of system time for scheduling alarms. Previously, the API for scheduling an alarm was the following, where passing f as the last input parameter would schedule a one-time alarm.

add-alarm ( quot start-timestamp interval-duration/f -- alarm )

However, this design is bad because the system time could change, resulting in a huge backlog of alarms to run. Also, most alarms were scheduled for less than a second into the future, which makes timestamps pretty useless since no date calculations are being performed. The new API takes a duration:

add-alarm ( quot start-duration interval-duration/f -- alarm)

Note that duration can be things like

300 milliseconds
5 seconds
200 nanoseconds

Using monotonic timers

Mouse drag alarm

Here's an example of using an alarm from the mouse handling code:

: start-drag-timer ( -- )
    hand-buttons get-global empty? [
        [ drag-gesture ] 300 milliseconds 100 milliseconds
        add-alarm drag-timer get-global >box
    ] when ;

The drag-gesture word gets called 300 milliseconds after a mouse button has been clicked, and again every 100 milliseconds afterwards until the alarm gets cancelled when the user releases a mouse button. The alarm is put into a global box because storing into a full box throws an error, which in this case would represent impossibility of the user dragging two things at once. Once dragging stops, the alarm gets cancelled with a call to cancel-alarm. You can look at the full source here.

Benchmark word

The benchmark word times a quotation and returns the number of nanoseconds that its execution took. Its implementation follows:

: benchmark ( quot -- runtime )
    nano-count [ call nano-count ] dip - ; inline

This word simply gets the count from the monotonic timer, calls the quotation, gets a new count, and finds the elapsed time by subtraction.

Rescheduling alarms

After repeated alarms execute, they must be rescheduled to run again.

: reschedule-alarm ( alarm -- )
    dup interval>> nano-count + >>start register-alarm ;

The alarm gets rescheduled interval>> nanoseconds into the future.

Remaining issues

Putting the computer to sleep on Snow Leopard in the middle of bootstrap and then resuming does not affect timing. However, is this the case with other operating systems such as Snow Vista or Linux? If not, it might not be worth worrying about. If someone wanted to test, just start a Factor bootstrap and then put the computer to sleep for awhile and see if bootstrap time increases. Otherwise, I'll get to it eventually.
Update: Someone on the Factor mailing list reported that putting the computer to sleep on bootstrap in Linux did not mess up the timing. Thank you!

Twin Cities Lisp Factor Presentation

2009-08-17T18:13:00.000-07:00

At the next TC Lisp meeting, I'll be explaining as much as I can about Factor in a one-hour presentation. Arrive before 6pm for the happy hour beer prices. All are welcome!

Place: Common Roots Cafe
Date: August 18, 2009
Time: 6pm

View Larger Map

A new library to manage client connections, and a proof of concept chat server in Factor

2009-05-29T09:45:00.000-07:00

Some thirty seconds into play-testing Joe Groff's terrain demo game, I realized there were no NPCs, no double-barreled shotguns or hand-cannons, and most disturbingly, no other players. Sure you can fly around, but you can't gib your friends! So I decided to do start to do something about it and write a managed server vocabulary with a generic protocol that you can extend for writing your own servers. Hey, I'm not much of an artist -- the guns will have to wait.

Managed-server infrastructure

The HTTP server already uses a library called io.servers.connections which implements a threaded-server with SSL support in 164 lines of code. A threaded-server listens for a set number of clients on an open port and handles each one individually; no client needs to know about any other. To get the code so concise, it uses libraries for concurrency, logging, sockets, and SSL that are themselves reused elsewhere.
Features of the threaded-server vocabulary:

the best nonblocking I/O code on every platform (completion ports, kqueue, epoll, not select())
connection/error logging, log rotation
correct error handling and resource cleanup
SSL support on Unix platforms
IPv4 and IPv6 support by default

For an HTTP or FTP server, handling each connection individually is what you want. However, for games or chat servers, you really want your users to interact. Building on top of this thread-server, I made a new tuple called a managed-server that tracks a list of connecting and disconnecting clients. You still get all of the features threaded-server implements, but now there's a new client handler that maintains a list of connected clients keyed by a username and utility words to send data to all clients.
You can also use this code to make custom binary protocols, and I'm mostly through implemented an SRP6 library to allow secure unencrypted logins after you create an account through an SSL connection. UDP support for first-person shooter and faster-paced games will also be supported when someone needs it.

The implementation of managed-server

A managed-server inherits from threaded-server class and adds a new slot called clients to store connections. Each connection's state -- the input/output streams, the local/remote socket addresses, username, a slot for passing quit messages, and a quit flag -- is wrapped inside a managed-client tuple and stored into the clients hashtable with the username as the key. In this way, it's easy to look up another client's stream and send it a message:

"wally" "hi wally!" send-client

You can also send a message to all connected clients,send-everyone, or to all but yourself:

"This one goes out to all the ladies." send-everyone-else

Here's what the tuple classes code looks like:

TUPLE: managed-server < threaded-server clients ;

TUPLE: managed-client
input-stream output-stream local-address remote-address
username object quit? ;

The managed-server protocol

A managed-server has some generics in place to guide you in creating your own servers. The first two generics are required, but the others default to no-ops unless you want to handle these events. Of course, the clients are still tracked no matter what your method does on the client-join or client-disconnect generics. The default method for handle-already-logged-in throws an error to prevent a new client from taking over the other client's session or logging in multiple times. You can override this behavior with your own perversions.
Here's the protocol:


HOOK: handle-login threaded-server ( -- username )
HOOK: handle-managed-client* managed-server ( -- )
HOOK: handle-already-logged-in managed-server ( -- )
HOOK: handle-client-join managed-server ( -- )
HOOK: handle-client-disconnect managed-server ( -- )

The implementation of a chat server using managed-server

Eventually someone will use managed-server for the networking code in a game, but until then I've implemented a simple chat server. Writing the chat server was fun and helped me to iron out a couple of bugs, which I wrote about below.

A walkthrough of the chat server protocol

The chat server code begins by inheriting from the managed-server tuple:

TUPLE: chat-server < managed-server ;

From here you go about implementing required parts of the protocol, handle-login and handle-managed-client*, so let's start there.

M: chat-server handle-login
    "Username: " write flush
    readln ;

The current input/output streams are bound to the client connection, so calling write will send them the login prompt. To read back the username, readln reads until a newline is sent. If you were to connect with telnet at this point, you would see the prompt and could send back a username. Then the server would kick you off because there's no implementation of handle-managed-client*.

M: chat-server handle-managed-client*
    readln dup f = [ t client (>>quit?) ] when
    [
        "/" ?head [ handle-command ] [ handle-chat ] if
    ] unless-empty ;

This word handles every other message the client sends apart from the login code. Calling readln reads the client's message one line at a time and returns false when the stream closes. The quit flag is set in such a case and will be explained later. For now, suffice to say that you're quitting if readln returns false. Next, the message is checked for any content -- both false and an empty string can be safely ignored here by the unless-empty combinator. Inside the quotation, the leading slash is stripped from the input, if any, and a boolean returned by ?head decides if the message was intended for the server or the chat room.

: handle-command ( string -- )
    dup " " split1 swap >lower commands get at* [
        call( string -- ) drop
    ] [
        2drop "Unknown command: " prepend print flush
    ] if ;

Commands sent to the server are normalized by converting to lower case and then looked up in the commands table. If you send a successful command such as /who or /nick then it gets executed; if not you get the generic "Unknown command" error.

: handle-chat ( string -- )
    [
        [ username ": " ] dip
    ] "" append-outputs-as send-everyone ;

Sending a message to the chat room is the alternative to server commands. I'm using append-outputs-as here to append together a bunch of strings, although i could easily have used 3append instead. I left this in because it's easier to change the look of the chat if you don't have to keep track of how many strings you're appending and you just let the compiler infer. Please take note: smart combinators in Factor are analogous to applying a function to a list or parameters in Lisp in that you don't need to know the number of parameters. The following two snippets will demonstrate what I mean:

(+ 1 2 10 1200)

[ 1 2 10 1200 ] sum-outputs

That's pretty much the essence of the chat server since everything else was just added for fun.

Fun with default encodings

Default encodings are terrible! Of course, you can change the encoding of a stream whenever you want, but the encoding for threaded-servers defaulted to ASCII until I changed it this evening. When I made my chat server yesterday, I forgot to set the encoding to what I wanted -- UTF8. Sending a character above 127 caused the server to throw an exception since ASCII is only 7 bits wide, and the sender would get disconnected. The FTP server I wrote started out with this bug as well, before I changed it to latin1. But now that threaded-server takes an encoding on the stack, this bug can never happen again.
So what's wrong with picking a different default encoding, maybe UTF8? Well, if I'm making a binary server, the UTF8 decoder will replace bad bit sequences with replacement characters -- another latent bug! What about binary as the default encoding, i.e. no encoding? Binary is the best option for a default, but then people who need to use UTF8 or latin1 might not know that the stream protocol supports encodings at all, and will end up doing a lot of work by hand which should be handled by the stream implementation. So not having a default encoding 1) prevents latent bugs and 2) forces the programmer to think about what they really want in each situation -- surely a good idea.

Quitting gracefully with quit flag

My first thought was just to throw an exception when I wanted to disconnect a client and cause the error handler to clean up the resources. Hopefully it's common knowledge that control flow implemented with exceptions is inefficient and bad design, in the general case. Maybe just this once? Nope, in my case the logging framework logs all exceptions, so the majority of the logs would be filled up with useless disconnect error messages. Clearly something better was needed -- the quit flag. Managed clients have a quit flag slot that is checked every time the server processes some data. Clients can quit gracefully by setting this flag to true and returning control back to the stream reader loop, and quits caused by exceptions are logged and worthy of further investigation.

Live coding on the server

After the chat server was up and running, I could add features without restarting. One of the first requested features was "/help", which required a redesign of how slash commands were handled. Instead of a case statement, now there's a word add-command that takes the implementation, the documentation, and the name of the command you want to add. Adding a command stores the code and the docs in symbols holding hashtables, indexed by the name of the command.

SYMBOL: commands
commands [ H{ } clone ] initialize

SYMBOL: chat-docs
chat-docs [ H{ } clone ] initialize

:: add-command ( quot docs key -- )
    quot key commands get set-at
    docs key chat-docs get set-at ;

I added a time command for fun:

[ drop gmt timestamp>rfc822 print flush ]
<" Syntax: /time
Returns the current GMT time."> "time" add-command

Someone else wanted a "/who" command -- easy enough.

[ drop clients keys [ "``" "''" surround ] map ", " join print flush ]
<" Syntax: /who
Shows the list of connected users.">
"who" add-command

There last feature I implemented was a way to change your nickname without reconnecting:

: handle-nick ( string -- )
    [
        "nick" usage
    ] [
        dup clients key? [
            username-taken-string print flush
        ] [
            [ username swap warn-name-changed ]
            [ username clients rename-at ]
            [ client (>>username) ] tri
        ] if
    ] if-empty ;

[ handle-nick ]
<" Syntax: /nick nickname
Changes your nickname.">
"nick" add-command

Changing your nickname is straightforward but takes the most steps of all the commands I implemented. Try to understand the code -- "string" in the stack effect is the requested nickname and the clients word returns a hashtable of connections, indexed by nicknames. If the user didn't supply a nickname, remind them of the syntax for using /nick. If they did supply a nickname, check if it's in use and, if so, refuse to change their name. Otherwise, the nick change succeeded, so tell all the users of the nickname change, apply the nick change in the clients hashtable, and set the new nickname in the client.

Chat server running live

You can try out the chat server by downloading Factor and running this command:

USING: managed-server.chat io.servers.connection ; 8889 <chat-server> start-server

Or you can connect to my running chat server:

telnet trifocus.net 8889

It's just a demo and I didn't implement any limits on your nickname or what you can send, though it would be easy enough to do so. Have fun, and please let me know if you can find any bugs.

An ID3 Parser in Factor

2009-05-24T14:10:00.000-07:00

A new contributor, Tim Wawrzynczak, wrote an ID3 parser as his first Factor program a couple of months back. The code looked pretty good, so it was easy to refactor the way ID3v1 and ID3v2 tags are represented and to add some utility words for managing directories of MP3s. The library still needs some work, but now it can take a directory tree and recursively parse all of the ID3 headers. I also realized that Factor's mmap implementation always tried to map a file read/write, so for ID3 parsing I added a read-only mmap. The finished code is here.

ID3v1 format

ID3 tags come in two flavors -- the old ID3v1 format, and the newer ID3v2 one. ID3v1 has a fixed length of 128 bytes and, if present, is the last 128 bytes of an MP3 file. The bytes begin with "TAG" and follow with the song title (30 bytes), artist (30 bytes), album (30 bytes), year (4 bytes), comment (30 bytes), and the genre (1 byte). The problem with this approach is that you are limited in the length of all the fields and in which data you can represent.

To implement the parser, we use the Memory-mapped files vocabulary to open the file. You can treat the file as an array of bytes that obeys the sequence protocol. Checking if a file has ID3v1 headers becomes:

: id3v1? ( mmap -- ? )
    { [ length 128 >= ] [ 128 tail-slice* "TAG" head? ] } 1&& ;

The logic here is straightforward: the sequence (mmapped file) is checked to make sure it's long enough to contain a header, and then the last 128 bytes are checked against the magic bytes "TAG". Since this is a short-circuit combinator, if the length test fails then the computation will end early. In this way, you can string together long computations that use short-circuit and and or. Factor's usual and/or words take two already-evaluated objects, so the short-circuit behavior is implemented as a library of macros instead.

ID3v2 format

The newer standard, ID3v2, has more room for metadata and can store anything up to 256 MB. Its use is indicated when the MP3 begins with "ID3" or when the bytes "3DI" are present 10 bytes from the end of the file or 10 bytes before the ID3v1 header. For parsing the header, the first two bytes are the version, then a flag byte, and finally four bytes for the size of the header. The size bytes are encoded as a synchsafe number, which means that the top bit is discarded and the lower seven bits are the data. In our case, 28 bits of data are the length, which is why the maximum length is 256MB.

The actual data we want to parse is stored in frames. Each frame has a tag, which is four ascii or utf16 bytes, followed by another 4 byte synchsafe integer for the length, two bytes of flag data, and the frame data. There are many different types of frames, but some of the more common ones are tagged TALB (album title), TIT2 (title), TRCK (track), COMM (comment), TPE1 (performer). All of the frame are added to a hashtable and keyed by the tag. Looking up the title frame becomes as easy as "TIT2" find-id3-frame on an ID3 tuple.

Future work

The ID3v1 "TAG+" format is not supported yet and apparently it's hardly ever used. ID3v2 tags are only looked for at the beginning of an MP3 but may be present at the end too as of version four. Most of the ID3 tags are not parsed into meaningful data besides the raw bytes. Lastly, writing out ID3 tags is not implemented yet and would be a good first program to write in Factor. Volunteers?

Files and file-systems in Factor, part 2

2009-01-13T16:01:00.000-08:00

In my previous post I wrote about the file-info and file-system-info words. Using those words, it's possible to write a portable program for directory listing (dir or ls) and one for file-systems listing (df). Uses for directory listing include file-system utility programs and FTP servers.

File listing tool

The file-listing tool is in the Factor git repository as basis/tools/files/files.factor. Which slots you see depend on how it is configured and on which platform it's running. Directory listings can be sorted by slot and the default sort is by name.

On Unix platforms, it's configured like this:

    <listing-tool>
       { permissions nlinks user group file-size file-date file-name } >>specs
       { { directory-entry>> name>> <=> } } >>sort

Listing a directory on MacOSX:

-rw-r--r-- 1  erg staff 27185 Nov 28  2008 #factor.el#
drwxr-xr-x 6  erg staff 204   Nov 17  2008 Factor.tmbundle
-rw-r--r-- 1  erg staff 30282 Nov 30  2008 factor.el
-rw-r--r-- 1  erg staff 18037 Nov 17  2008 factor.vim
-rw-r--r-- 1  erg staff 12496 Nov 17  2008 factor.vim.fgen
drwxr-xr-x 26 erg staff 884   Jan 13 11:17 fuel
drwxr-xr-x 8  erg staff 272   Nov 17  2008 icons

Windows platforms take the look of the ``dir'' command by default:

2009-01-14 00:00:53 <DIR>                Factor.tmbundle
2009-01-14 00:00:53                30282 factor.el
2009-01-14 00:00:53                18037 factor.vim
2009-01-14 00:00:53                12496 factor.vim.fgen
2009-01-14 00:00:53 <DIR>                fuel
2009-01-14 00:00:53 <DIR>                icons

File-systems tool

A tool for disk usage and mounted devices was easy to write once file-system tuples worked everywhere. Once again, it's configurable for whatever you want to see. The default file-system word is:

: file-systems. ( -- )
    {
        device-name available-space free-space used-space
        total-space percent-used mount-point
    } print-file-systems ;

File-systems on a Mac:

device-name   available-space free-space   used-space   total-space  percent-used mount-point
/dev/disk0s2  118599725056    118861869056 200867090432 319728959488 62           /
fdesc         0               0            1024         1024         100          /dev
fdesc         0               0            1024         1024         100          /dev
map -hosts    0               0            0            0            0            /net
map auto_home 0               0            0            0            0            /home

On Windows:

device-name      available-space free-space used-space total-space percent-used mount-point
                 3814506496      3814506496 6911225856 10725732352 64           C:\
VBOXADDITIONS_2. 0               0          27983872   27983872    100          D:\
                 0               0          0          0           0            A:\

Files and file-systems in Factor, part 1

2009-01-09T13:05:00.000-08:00

Factor now has an easy way access to get information about files and file-systems in a high-level way across all the platforms that it supports. The API is really simple -- pass a pathname and get information back about the file or file-system as a tuple. The second part of this post will demonstrate a clone of the Unix tools ls, for listing files, and df, for listing file-systems.

File-info

There are now words to get information about files and symlinks, using file-info and link-info which map to C system calls stat and lstat. Some slots are shared across all platforms while others are only present on a particular platform. There are symbols representing all of the file types, like +regular-file+, +directory+, and +symbolic-link+. Here are some examples.
MacOSX

( scratchpad ) "resource:license.txt" file-info .
T{ bsd-file-info
    { type +regular-file+ }
    { size 1252 }
    { permissions 33188 }
    { created
        T{ timestamp
            { year 2008 }
            { month 11 }
            { day 17 }
            { hour 23 }
            { minute 34 }
            { second 5 }
            { gmt-offset T{ duration { hour -6 } } }
        }
    }
    { modified
        T{ timestamp
            { year 2008 }
            { month 11 }
            { day 17 }
            { hour 23 }
            { minute 34 }
            { second 5 }
            { gmt-offset T{ duration { hour -6 } } }
        }
    }
    { accessed
        T{ timestamp
            { year 2008 }
            { month 12 }
            { day 9 }
            { hour 12 }
            { minute 34 }
            { second 8 }
            { gmt-offset T{ duration { hour -6 } } }
        }
    }
    { uid 501 }
    { gid 20 }
    { dev 234881026 }
    { ino 992362 }
    { nlink 1 }
    { rdev 0 }
    { blocks 8 }
    { blocksize 4096 }
    { birth-time
        T{ timestamp
            { year 2008 }
            { month 11 }
            { day 17 }
            { hour 23 }
            { minute 34 }
            { second 5 }
            { gmt-offset T{ duration { hour -6 } } }
        }
    }
    { flags 0 }
    { gen 0 }
}

Windows XP

( scratchpad ) "resource:license.txt" file-info .
T{ windows-file-info
    { type +regular-file+ }
    { size 1252 }
    { permissions 32 }
    { created
        T{ timestamp
            { year 2008 }
            { month 3 }
            { day 23 }
            { hour 23 }
            { minute 28 }
            { second 12 }
        }
    }
    { modified
        T{ timestamp
            { year 2008 }
            { month 3 }
            { day 27 }
            { hour 23 }
            { minute 24 }
            { second 12 }
        }
    }
    { accessed
        T{ timestamp
            { year 2008 }
            { month 9 }
            { day 19 }
            { hour 23 }
            { minute 8 }
            { second 41 }
        }
    }
    { attributes { +archive+ } }
}

FreeBSD

( scratchpad ) "resource:license.txt" file-info .
T{ bsd-file-info
    { type +regular-file+ }
    { size 1252 }
    { permissions 33188 }
    { created
        T{ timestamp
            { year 2008 }
            { month 4 }
            { day 6 }
            { hour 12 }
            { minute 6 }
            { second 53 }
            { gmt-offset T{ duration { hour -6 } } }
        }
    }
    { modified
        T{ timestamp
            { year 2008 }
            { month 4 }
            { day 6 }
            { hour 12 }
            { minute 6 }
            { second 53 }
            { gmt-offset T{ duration { hour -6 } } }
        }
    }
    { accessed
        T{ timestamp
            { year 2008 }
            { month 4 }
            { day 6 }
            { hour 12 }
            { minute 6 }
            { second 59 }
            { gmt-offset T{ duration { hour -6 } } }
        }
    }
    { uid 1002 }
    { gid 1002 }
    { dev 89 }
    { ino 343452 }
    { nlink 1 }
    { rdev 1348575 }
    { blocks 4 }
    { blocksize 4096 }
    { birth-time
        T{ timestamp
            { year 2008 }
            { month 4 }
            { day 6 }
            { hour 12 }
            { minute 6 }
            { second 53 }
            { gmt-offset T{ duration { hour -6 } } }
        }
    }
    { flags 0 }
    { gen 0 }
}

File Systems

The file-system utility word above works on file-system tuples that contain cross-platform information like the device name, the mount point, the number of free, used, and total bytes. A file-system tuple on Unix has all of the file-system information found in both statfs and statvfs while a Windows file-system object has the device-id, volume name, and byte usage slots. There is not a single win32 API call that gives as much information as on Unix systems -- instead I call a combination of GetDiskFreeSpaceEx, FindFirstVolume, GetVolumePathNamesForVolumeName, GetVolumeInformation.
On every Unix besides Linux, there is a member of the statfs or statvfs structure that gives you the file-system that contains the file. So, I had to roll my own for it to work the same way across all platforms. The algorithm is pretty simple: the follow-links word follows links up to 10 times (configurable) and once it stops, finds the parent directory and follows the links again until the directory is a member of the directories in the /etc/mtab file. If there is circularity or a broken link, it throws an error.

FreeBSD

( scratchpad ) "/" file-system-info .
T{ freebsd-file-system-info
    { device-name "/dev/da0s1a" }
    { mount-point "/" }
    { type "ufs" }
    { available-space 368117760 }
    { free-space 409702400 }
    { used-space 110110720 }
    { total-space 519813120 }
    { block-size 2048 }
    { preferred-block-size 2048 }
    { blocks 253815 }
    { blocks-free 200050 }
    { blocks-available 179745 }
    { files 65790 }
    { files-free 61501 }
    { files-available 61501 }
    { name-max 255 }
    { flags 20480 }
    { id { 0 0 } }
    { version 537068824 }
    { io-size 16384 }
    { owner 0 }
    { syncreads 0 }
    { syncwrites 0 }
    { asyncreads 0 }
    { asyncwrites 0 }
}

Windows XP 64

( scratchpad ) "k:\\" file-system-info .
T{ win32-file-system-info
    { device-name "" }
    { mount-point "k:\\" }
    { type "NTFS" }
    { available-space 174530142208 }
    { free-space 174530142208 }
    { used-space 225547444224 }
    { total-space 400077586432 }
    { max-component 255 }
    { flags 459007 }
    { device-serial 3695676537 }
}

The Factor build farm will start using file-system-info to report when a drive fills up pretty soon.

Sorting by tuple slots

2009-01-09T08:21:00.000-08:00

Factor's sorting has been extended to support sorting tuples by multiple slots, one after the other. In a music player application, you may wish to sort your songs first by artist, then by album, then track number. If you had a tuple representing every song, the code for such a sort is now very easy:

{ { artist>> <=> } { album>> <=> } { track>> <=> } } sort-by-slots

The main word at work is sort-by-slots ( seq sort-specs -- seq' ), where a sort-spec is an accessor paired with a comparator, one of <=>, >=<, human-<=>, human->=<. Human sort first converts consecutive digits to integers and then makes the comparison, e.g. { "a1" "a10" "a03" "a2" } sorts as { "a1" "a2" "a03" "a10" } instead of { "a03" "a1" "a10" "a2" }, as it would with natural-sort.

Sorting in reverse order is possible with the new operator >=<, which inverts the result of the <=> comparator. To sort a playlist by the most played songs in reverse order (most played first):

{ { play-count>> >=< } } sort-by-slots

Source code for sort-by-slots

: slot-comparator ( accessor comparator -- quot )
    '[ [ _ execute ] bi@ _ execute dup +eq+ eq? [ drop f ] when ] ;

MACRO: compare-slots ( sort-specs -- <=> )
    #! sort-spec: { accessor comparator }
    [ first2 slot-comparator ] map '[ _ 2|| +eq+ or ] ;

: sort-by-slots ( seq sort-specs -- seq' )
    '[ _ compare-slots ] sort ;

First, a bit about how Factor's sort ( seq quot -- sortedseq ) word works. It expects a quotation that compares two objects lexicographically, which is element by element in dictionary order. Thus, the macro compare-slots expands the sort-specs into a quotation that compares tuples slot-by-slot until there is a difference. The macro-expansion for the first example looks like this:

( scratchpad ) [ { { artist>> <=> } { album>> <=> } { track>> <=> } } compare-slots ] expand-macros .
    f 2 [
        \ artist>> \ <=> [ [ execute ] curry bi@ ] dip execute
        dup +eq+ eq? [ drop f ] when
    ] [ [ drop ] dip ndup ] dip call dup
    [ 2 [ ndrop ] curry dip ] [
        2 [
            \ album>> \ <=> [ [ execute ] curry bi@ ] dip execute
            dup +eq+ eq? [ drop f ] when
        ] [ [ drop ] dip ndup ] dip call dup
        [ 2 [ ndrop ] curry dip ] [
            2 [
                \ track>> \ <=> [ [ execute ] curry bi@ ] dip
                execute dup +eq+ eq? [ drop f ] when
            ] [ [ drop ] dip ndup ] dip call dup
            [ 2 [ ndrop ] curry dip ]
            [ 2 [ drop ] dip ndrop t [ f ] [ no-cond ] if ] if
        ] if
    ] if +eq+ or

The macro first extracts the slots and compares with the first comparator. If the comparator returns +lt+ or +gt+ then the comparison is over, but if the comparator returns +eq+ then the next comparison is invoked and the sort continues in the same way. Notice that the slot-comparator word replaces +eq+ with f to avoid short-circuiting the iteration done by 2||. The final sort-by-slots word is a trivial call to sort with the new comparator word we just defined.

Algorithmic complexity and ideas for improvement

The sorting bound is still O(n log n) for time, but of course the more comparators that you need to break ties, the longer the algorithm will take to run.
If your data has to be sorted anyway, it's possible to sort and then split the data into related slices using a sequence of accessors like the above. You could then compute the playing time of every album, or find your most-played song from every artist. Splitting with the same accessors takes O(n) time, but the odds are that you probably won't have already sorted the data. So for unsorted data, there is a more efficient way to extract features -- you can instead partition it in O(n) time and find features on each partition, avoiding sorting altogether. This will be the subject of a future blog post.

Moving primitives out of the Factor VM: Factor vs C

2008-10-19T15:42:00.000-07:00

In a previous lifetime, I added environment variable primitives to the VM. Well, it turns out that a better place for them is in the Factor basis vocabulary root, so this post is about moving them again.

To move a primitive out of the VM, implement its functionality in Factor code and replace usages with your word if necessary, remove it from vm/primitives.c and core/bootstrap/primitives.factor, remove the primitive code from the VM, make a new image, recompile Factor, and bootstrap. Basically, do the inverse of the previous post.

What's more interesting, unless you have to actually remove a primitive someday and need this reference, is comparing the code for each version side-by-side. The C code has to call functions to prevent the garbage collector from moving data around when it shouldn't, but it's written without the usual ifdefs you will find in most cross-platform C code, so overall it's fairly clean. The Factor version has a high-level protocol that is implemented by both backends across separate files, with one-liners for most of the Unix definitions and high-level combinators for the Windows ones. I find the Factor version much easier to understand and I believe it's more maintainable. Factor is a better C than C.

High-level environment variable interface

Factor's high-level environment variable words let you get a single variable or all of them, set a single variable or all of them, and unset a variable. On Windows you cannot set all of the variables at once, and on Windows CE the whole concept of environment variables does not exist.

Here is the code for the main vocabulary. Notice that there are hooks on the os word, which will be a value like macosx or winnt or linux. The boilerplate at the bottom is for loading the platform-specific code.

USING: assocs combinators kernel sequences splitting system
vocabs.loader ;
IN: environment

HOOK: os-env os ( key -- value )

HOOK: set-os-env os ( value key -- )

HOOK: unset-os-env os ( key -- )

HOOK: (os-envs) os ( -- seq )

HOOK: (set-os-envs) os ( seq -- )

: os-envs ( -- assoc )
    (os-envs) [ "=" split1 ] H{ } map>assoc ;

: set-os-envs ( assoc -- )
    [ "=" swap 3append ] { } assoc>map (set-os-envs) ;

{
    { [ os unix? ] [ "environment.unix" require ] }
    { [ os winnt? ] [ "environment.winnt" require ] }
    { [ os wince? ] [ ] }
} cond

Unix environment variables, before and after

DEFINE_PRIMITIVE(os_env)
{
    char *name = unbox_char_string();
    char *value = getenv(name);
    if(value == NULL)
        dpush(F);
    else
        box_char_string(value);
}

DEFINE_PRIMITIVE(os_envs)
{
    GROWABLE_ARRAY(result);
    REGISTER_ROOT(result);
    char **env = environ;

    while(*env)
    {
        CELL string = tag_object(from_char_string(*env));
        GROWABLE_ARRAY_ADD(result,string);
        env++;
    }

    UNREGISTER_ROOT(result);
    GROWABLE_ARRAY_TRIM(result);
    dpush(result);
}

DEFINE_PRIMITIVE(set_os_env)
{
    char *key = unbox_char_string();
    REGISTER_C_STRING(key);
    char *value = unbox_char_string();
    UNREGISTER_C_STRING(key);
    setenv(key, value, 1);
}

DEFINE_PRIMITIVE(unset_os_env)
{
    char *key = unbox_char_string();
    unsetenv(key);
}

DEFINE_PRIMITIVE(set_os_envs)
{
    F_ARRAY *array = untag_array(dpop());
    CELL size = array_capacity(array);

    /* Memory leak */
    char **env = calloc(size + 1,sizeof(CELL));

    CELL i;
    for(i = 0; i < size; i++)
    {
        F_STRING *string = untag_string(array_nth(array,i));
        CELL length = to_fixnum(string->length);

        char *chars = malloc(length + 1);
        char_string_to_memory(string,chars);
        chars[length] = '\0';
        env[i] = chars;
    }

    environ = env;
}

Factor

USING: alien alien.c-types alien.strings alien.syntax kernel
layouts sequences system unix environment io.encodings.utf8
unix.utilities vocabs.loader combinators alien.accessors ;
IN: environment.unix

HOOK: environ os ( -- void* )

M: unix environ ( -- void* ) "environ" f dlsym ;

M: unix os-env ( key -- value ) getenv ;

M: unix set-os-env ( value key -- ) swap 1 setenv io-error ;

M: unix unset-os-env ( key -- ) unsetenv io-error ;

M: unix (os-envs) ( -- seq )
    environ *void* utf8 alien>strings ;

: set-void* ( value alien -- ) 0 set-alien-cell ;

M: unix (set-os-envs) ( seq -- )
    utf8 strings>alien malloc-byte-array environ set-void* ;

os {
    { macosx [ "environment.unix.macosx" require ] }
    [ drop ]
} case

MacOSX environment variables, before and after

On OSX, we have to use a function to access the environment variable.

#ifndef environ
    extern char ***_NSGetEnviron(void);
    #define environ (*_NSGetEnviron())
#endif

Factor

USING: alien.syntax system environment.unix ;
IN: environment.unix.macosx

FUNCTION: void* _NSGetEnviron ( ) ;

M: macosx environ _NSGetEnviron ;

Windows NT environment variables, before and after

Draw your own conclusions.

DEFINE_PRIMITIVE(os_env) 
{ 
    F_CHAR *key = unbox_u16_string(); 
    F_CHAR *value = safe_malloc(MAX_UNICODE_PATH * 2); 
    int ret; 
    ret = GetEnvironmentVariable(key, value, MAX_UNICODE_PATH * 2); 
    if(ret == 0) 
        dpush(F); 
    else 
        dpush(tag_object(from_u16_string(value))); 
    free(value); 
}

DEFINE_PRIMITIVE(os_envs)
{
    GROWABLE_ARRAY(result);
    REGISTER_ROOT(result);

    TCHAR *env = GetEnvironmentStrings();
    TCHAR *finger = env;

    for(;;)
    {
        TCHAR *scan = finger;
        while(*scan != '\0')
            scan++;
        if(scan == finger)
            break;

        CELL string = tag_object(from_u16_string(finger));
        GROWABLE_ARRAY_ADD(result,string);

        finger = scan + 1;
    }

    FreeEnvironmentStrings(env);

    UNREGISTER_ROOT(result);
    GROWABLE_ARRAY_TRIM(result);
    dpush(result);
}
 
DEFINE_PRIMITIVE(set_os_env) 
{ 
    F_CHAR *key = unbox_u16_string(); 
    REGISTER_C_STRING(key); 
    F_CHAR *value = unbox_u16_string(); 
    UNREGISTER_C_STRING(key); 
    if(!SetEnvironmentVariable(key, value)) 
        general_error(ERROR_IO, tag_object(get_error_message()), F, NULL); 
} 
 
DEFINE_PRIMITIVE(unset_os_env) 
{ 
    if(!SetEnvironmentVariable(unbox_u16_string(), NULL) 
        && GetLastError() != ERROR_ENVVAR_NOT_FOUND) 
        general_error(ERROR_IO, tag_object(get_error_message()), F, NULL); 
} 
 
DEFINE_PRIMITIVE(set_os_envs) 
{ 
    not_implemented_error(); 
}

Factor

USING: alien.strings fry io.encodings.utf16 kernel
splitting windows windows.kernel32 ;
IN: environment.winnt

M: winnt os-env ( key -- value )
    MAX_UNICODE_PATH "TCHAR" <c-array>
    [ dup length GetEnvironmentVariable ] keep over 0 = [
        2drop f
    ] [
        nip utf16n alien>string
    ] if ;

M: winnt set-os-env ( value key -- )
    swap SetEnvironmentVariable win32-error=0/f ;

M: winnt unset-os-env ( key -- )
    f SetEnvironmentVariable 0 = [
        GetLastError ERROR_ENVVAR_NOT_FOUND =
        [ win32-error ] unless
    ] when ;

M: winnt (os-envs) ( -- seq )
    GetEnvironmentStrings [
        <memory-stream> [
            utf16n decode-input
            [ "\0" read-until drop dup empty? not ]
            [ ] [ drop ] produce
        ] with-input-stream*
    ] [ FreeEnvironmentStrings win32-error=0/f ] bi ;

Introducing the Factor database library

2008-10-18T13:03:00.000-07:00

Background

One of the first libraries I wrote in Factor was a binding to PostgreSQL library in May 2005. Factor makes it incredibly easy to bind to C functions -- just add a FUNCTION: declaration and call the C function. For example,

( scratchpad ) FUNCTION: int getuid ( ) ;
( scratchpad ) getuid .
0

At about the same time, Chris Double wrote a SQLite binding and a high-level library he called tuple-db. It had some good ideas, such as query-by-example and prepared SQL statements for better security.

Earlier this year, I took both of these libraries and merged them to come up with the the current database library. The supported backends are PostgreSQL and SQLite and there are protocols for implementing other backends with relative ease. Contributions are welcome.

Overview

Briefly, Factor tuples correspond one-to-one to tables in the database through a mapping defined with the define-persistent word. Tuples are then manipulated through insert, update, delete, and select words. Upon calling the insert word, all of the filled-in slots in a tuple will be saved to the database. The process is reversible, and by filling in slots for a tuple and calling select-tuples, the libary generates a select statement from the filled-in slots (query-by-example) and returns tuples in a sequence. More advanced queries and lower level raw SQL statements are possible as well.

First, we'll look at how to connect to a database.

Connecting to a database

Every database has its own setup which Factor encapsultes in a tuple. SQLite just needs a path to a file on disk, but since PostgreSQL has a server/client model, the setup is more complex. After making your database tuple, connecting works the same for any database by using the with-db word. This word takes a quotation (a block of code) and your tuple object, then calls the database open routine and your quotation. After running your quotation, the database is closed, even if your code throws an exception. Having an interface like this means you can simply swap out your SQLite database for a networked PostgreSQL one if you suddenly need more scalability or networked database access.

You should generally make a custom combinator with your project's connection information. Here are a couple of examples.

SQLite example combinator:

USING: db.sqlite db io.files ;
: with-sqlite-db ( quot -- )
    "my-database.db" temp-file <sqlite-db> swap with-db ; inline

PostgreSQL example combinator:

USING: db.postgresql db ;
: with-postgresql-db ( quot -- )
    <postgresql-db>
        "localhost" >>host
        5432 >>port
        "user" >>username
        "seeecrets?" >>password
        "factor-test" >>database
    swap with-db ; inline

To make sure your database connection works, you can test it with an empty quotation:

 [ ] with-postgresql-db

If that line of code doesn't throw an error, you can safely assume connecting to the database worked.

Defining persistent tuples

The highest-level database abstraction Factor offers relates tuples directly to database tables. Tuples must map one-to-one to a database table, but foreign keys to other tables are allowed.

Primary keys

Each tuple needs a primary key for indexing by the database. The primary key can be an increasing integer assigned by the database (a +db-assigned-id+), an object assigned by the user (a +user-defined-id+), a random number, or even a compound key consisting of multiple values used together as a key.

Database defined primary keys are automatically set on the tuple after insertion. While SQLite makes this feature easy to implement with the sqlite3_last_insert_rowid library call, PostgreSQL lacks such a feature and instead, in the backend, the inserts are done through a SQL function that queries the most recently inserted row.

User-assigned ids can be anything that the programmer knows will be unique for each object in the table. The same is true for compound keys, but only one of the values has to differ in this case for it to be unique.

Sometimes, a randomly generated id is useful, and the database library makes it easy to associate a tuple with its random key. By default, it generates a 64-bit random integer and in the unlikely event that it collides with an existing entry, it tries again up to ten times. The random integer is then set in the primary key slot of the tuple.

Database types

Data should have a type to allow the database to optimize its queries and storage. The supported data types are booleans, varchars, text, integers, big-integers, doubles, reals, timestamps, byte-arrays, URLs, and Factor blobs, which store arbitrary Factor objects. Types can have default values, unique qualifiers, and not-null restrictions. The database framework does all of the marshalling of objects for you transparently.

Creating and dropping tables

There are quite a few options when it comes to creating tables. The most basic is the create-table word. The problem is that it throws an exception when the table exists, which happens often. So one alternative is ensure-table -- we make sure a table exists and silently ignore errors. However, if we're just developing an application and we want to make sure the table is always the latest version of the code, we might use recreate-table, which drops and creates the table without throwing errors, and of course drops all the data with it. To simply drop a table, use the drop-table word.

Inserting tuples

Tuples are inserted one at a time with the insert-tuple word. SQL insert commands are generated directly from the Factor object and its filled-in slots. An example will follow.

Selecting tuples

Select statements are generated from exemplar tuples, or tuples with certain slots filled in with any value besides f. Passing an empty exemplar tuple will select all tuples from the table and return them as a sequence. A useful feature we support is querying by ranges, sequences, or intervals, as shown in following demonstration.

Exams demo

About the simplest example of interest is one that matches students names with their grades on a particular exam. Here's aa exam tuple, its mapping to the database, and a utility word to generate random exam objects.

USING: math.ranges random db.types ;

TUPLE: exam id name score ;

exam "EXAM"    {
    { "id" "ID" +db-assigned-id+ }
    { "name" "NAME" TEXT }
    { "score" "SCORE" INTEGER }
} define-persistent

: random-exam ( -- exam )
        f
        6 [ CHAR: a CHAR: z [a,b] random ] replicate >string
        100 [0,b] random
    exam boa ;

I'll use a trick for opening a database to use it interactively without putting a with-db wrapper around every call.

"my-database.db" temp-file <sqlite-db> db-open db set

Note that the database handle should be cleaned up with db get dispose if you don't want to leak memory.

Let's create the table and add some random exams to the database:

exam create-table

25 [ random-exam insert-tuple ] times

Now to demonstrate selects. You can select all the exams:

T{ exam } select-tuples .
{
    T{ exam { id 1 } { name "qklkzk" } { score 38 } }
    T{ exam { id 2 } { name "feeuwv" } { score 38 } }
    T{ exam { id 3 } { name "hlzwuu" } { score 51 } }
    T{ exam { id 4 } { name "liiptp" } { score 52 } }
    T{ exam { id 5 } { name "mwzlmv" } { score 74 } }
    ...
}

Ranges can be used with any datatype that makes sense, like integers or timestamps.

A range of passing exams:

T{ exam } 70 100 [a,b] >>score select-tuples .
{
    T{ exam { id 5 } { name "mwzlmv" } { score 74 } }
    T{ exam { id 6 } { name "ftxhuw" } { score 90 } }
    T{ exam { id 11 } { name "rorbyd" } { score 83 } }
    T{ exam { id 16 } { name "ttvkar" } { score 78 } }
    T{ exam { id 17 } { name "nnzkvs" } { score 99 } }
    T{ exam { id 21 } { name "izoiqi" } { score 83 } }
}

You can search for specific grades by using a sequence:

T{ exam } { 10 20 30 40 50 60 70 80 90 100 } >>score select-tuples .
{
    T{ exam { id 6 } { name "ftxhuw" } { score 90 } }
    T{ exam { id 9 } { name "bdoztd" } { score 30 } }
    T{ exam { id 20 } { name "lnmxfq" } { score 60 } }
}

An interval query. Nobody should have above a 100:

USE: math.intervals T{ exam } 100 1/0. (a,b) >>score select-tuples .
{ }

Let's order by the grade:

<query> T{ exam } >>tuple "score" >>order select-tuples .
...
    T{ exam { id 21 } { name "izoiqi" } { score 83 } }
    T{ exam { id 6 } { name "ftxhuw" } { score 90 } }
    T{ exam { id 17 } { name "nnzkvs" } { score 99 } }
}

Or by (random-generated) name:

<query> T{ exam } >>tuple "name" >>order select-tuples .
{
    T{ exam { id 13 } { name "aagnof" } { score 61 } }
    T{ exam { id 36 } { name "ailftz" } { score 41 } }
    T{ exam { id 9 } { name "bdoztd" } { score 30 } }
    ...

Updates and deletes are also by example and may use sequences and intervals in the 'where' clause in the same way as the selects with the update-tuples and delete-tuples words.

Raw SQL

You can drop down into SQL if you want to do anything complex or things that are not supported by the library. A drawback is that the SQL you write may not work across SQL databases. Notice that, for a select, you have to convert the data to Factor tuples yourself since the data is returned as an array of strings.

"select * from exam where name like '%a%'" sql-query .
{
    { "8" "rxoyga" "53" }
    { "10" "fchhha" "1" }
    { "13" "aagnof" "61" }
    { "16" "ttvkar" "78" }
    { "22" "yhqkav" "28" }
}

Raw SQL that does not return results is possible too:

"delete from exam where name like '%a%'" sql-command
"select * from exam where name like '%a%'" sql-query length .
    0

Another tutorial

Here is a tutorial from the database documentation that shows moref basic usage of the library. If you run this from within the Factor environment itself, you can click on the code blocks and run them one by one without copy/pasting or typing them in yourself.

Real-world usage

The Factor Wiki uses the database library, as does Factor's web framework, Furnace. Expect to see more useful websites and applications using it in the future.

Lastly, if anyone can suggest a catchy name for the database library, please let me know.

Vocabulary and documentation tool: tools.scaffold

2008-09-03T18:36:00.001-07:00

The Factor project is on a documentation binge until all of the core and basis vocabularies are documented. I noticed, as anyone tasked to write a bunch of documenation would, that quite a bit of it could be automated. To begin writing docs for a vocabulary that already exists, you can just run the tool in it and edit the generated help file.

I actually ended up writing two tools -- one for the docs, and another to create new vocabularies with a simple command.

Scaffold tool to create new vocabularies

First, an aside. Factor's module system is based on a directory layout, with several vocabulary roots which are stored in the vocab-roots symbol.

( scratchpad ) USE: vocabs.loader vocab-roots get .
V{ "resource:core" "resource:basis" "resource:extra" "resource:work" }

Knowing this, you can now create a new vocabulary and boilerplate empty Factor files from inside of Factor and click the links to edit them in your favorite editor.

( scratchpad ) "extra" "alchemy" scaffold-vocab
Creating scaffolding for P" resource:extra/alchemy/alchemy.factor"
Creating scaffolding for P" resource:extra/alchemy/alchemy-tests.factor"
Creating scaffolding for P" resource:extra/alchemy/authors.txt"

( scratchpad ) "extra" "alchemy" scaffold-help
Creating scaffolding for P" resource:extra/alchemy/alchemy-docs.factor"

The scaffold tool is programmed not to overwrite files if they already exist.

Scaffold tool for documenation

Say I have a Factor word that turns lead into gold:

: lead>gold ( lead -- gold ) ... ;

The implementation of this word is left as an exercise to the reader. We don't have to understand how it works to document what it does.

Without an automation tool, you would begin by creating a new file (extra/alchemy/alchemy-docs.factor) in the same directory as your code file (extra/alchemy/alchemy.factor). What follows is the standard bolierplate for documentation. Notice that documenation goes in the same vocabulary as your actual code, but comes from different files on disk.

! Copyright (C) 2008 Doug Coleman.
! See http://factorcode.org/license.txt for BSD license.
USING: help.markup help.syntax ;
IN: alchemy

Every doc file has such a header based on the date, who you are, and the vocabulary name. With those three pieces of information, the above can be auto-generated. I added a new symbol developer-name in tools.scaffold that should be set to your name when writing docs.

Now let's look at the documenation for lead>gold:

HELP: lead>gold
{ $values { "lead" "boring lead" } { "gold" "shiny gold" } }
{ $description "Turns lead into gold." } ;

Notice that we know the word name, the first strings in each stack effect in the $values array, and the markup structure.

Here is the generated scafford:

HELP: lead>gold
{ $values { "lead" null } { "gold" null } }
{ $description } ;

This is much less wrist punishment than typing manually. The scaffold tool can even generate the documentation with their Factor types given correct code and standard type names like "quot" and "hashtable". Types that are not known are given the null class. Documenation correctness tools can later search for null objects and report them as errors, since no words should operate on this type.

I'll finish by including a snippet of the output of running the scaffold help generator on itself.

! Copyright (C) 2008 Doug Coleman.
! See http://factorcode.org/license.txt for BSD license.
USING: arrays help.markup help.syntax io.streams.string kernel strings words ;
IN: tools.scaffold

HELP: check-root
{ $values
     { "string" string }
     { "string" string } }
{ $description } ;

HELP: check-scaffold
{ $values
     { "vocab-root" "a vocabulary root string" } { "string" string }
     { "vocab-root" "a vocabulary root string" } { "string" string } }
{ $description } ;

HELP: check-vocab-name
{ $values
     { "string" string }
     { "string" string } }
{ $description } ;

HELP: developer-name
{ $description } ;

HELP: help.
{ $values
     { "word" word } }
{ $description } ;

HELP: lookup-type
{ $values
     { "string" string }
     { "object/string" null } { "?" "a boolean" } }
{ $description } ;

HELP: main-file-string
{ $values
     { "vocab" "a vocabulary specifier" }
     { "string" string } }
{ $description } ;

HELP: not-a-vocab-root
{ $values
     { "string" string } }
{ $description } ;

HELP: not-a-vocab-root?
{ $values
     { "object" object }
     { "?" "a boolean" } }
{ $description } ;

HELP: root?
{ $values
     { "string" string }
     { "?" "a boolean" } }
{ $description } ;

HELP: scaffold-authors
{ $values
     { "path" "a pathname string" } }
{ $description } ;

HELP: scaffold-copyright
{ $description } ;

HELP: tests-file-string
{ $values
     { "vocab" "a vocabulary specifier" }
     { "string" string } }
{ $description } ;

HELP: using
{ $description } ;

HELP: vocab>scaffold-path
{ $values
     { "vocab-root" "a vocabulary root string" } { "string" string }
     { "path" "a pathname string" } }
{ $description } ;

ARTICLE: "tools.scaffold" "tools.scaffold"
;

ABOUT: "tools.scaffold"

I hope this new vocabulary makes documenation a lot less tedious and error-prone. Now to go write some docs...

Word renaming (part 2)

2008-04-28T10:49:00.000-07:00

Here are the word names that have changed:

find* -> find-from
find-last* -> find-last-from
index* -> index-from
last-index* -> last-index-from
subset -> filter

New shorthand words:

1 tail -> rest
1 tail-slice -> rest-slice
swap compose -> prepose

Changes to existing word behavior:

reverse stack effect of assoc-diff, diff
before? after? before=? after=? are now generic
min, max can compare more objects than before, such as timestamps
between? can compare more objects
<=> returns symbols

There are several motivations at work here. One is that words named foo* are a variant of foo, but otherwise the * is no help to what the word actually does differently. We're trying to move away from word names with stars to something more meaningful.

Code with common patterns that come up a lot, like 1 tail and swap compose, is more clearly understood if these patterns are given a single name.

Factor's subset is not equivalent to the mathematical definition of subset, so it was renamed to filter to avoid confusion. Along these same lines, diff and assoc-diff are now the more mathematically intuitive; you can think of diff like set subtraction now, seq1 seq2 diff is like seq1 - seq2.

Finally, the "UFO operator" <=> now returns symbols +lt+ +eq+ +gt+ instead of negative, zero, and positive numbers. The before? and after? words can compare anything that defines a method on this operator. Since between?, min, and max
are defined in terms of these comparison words, they also work on more objects.

Please let me know if you have any more suggestions for things words that have awkward argument orders, imprecise names, or if you can suggest alternate names for words with stars in their names.

Word renaming

2008-04-14T12:25:00.001-07:00

Several words have been renamed and moved around to make Factor more consistent:

new -> new-sequence
construct-empty -> new
construct-boa -> boa
diff -> assoc-diff
union -> assoc-union
intersect -> assoc-intersect
seq-diff -> diff
seq-intersect -> intersect

To make things symmetrical, a new word union operates on sequences.

Somehow, seq-diff and seq-intersect were implemented as O(n^2) algorithms. Now, they use hashtables and are O(n).

Lastly, a new vocabulary named ``sets'' contains the set theoretic words, along with a new word unique that converts a sequence to a hash table whose keys and values are the same. An efficient union and intersect are implemented in terms of this word.

Adding a new primitive

2008-04-13T14:20:00.000-07:00

I added two primitives to the Factor VM to allow setting and unsetting of environment variables. It's not that hard to do, but you have to edit several C files in the VM and a couple .factor files in the core. Really they should not be primitives, so eventually they will be moved into the core.

The primitives that I added are defined as follows:

IN: system
PRIMITIVE: set-os-env ( value key -- )
PRIMITIVE: unset-os-env ( key -- )

Adding a primitive to vm/

Since Factor's datatypes are not the same as C's datatypes, and because of the garbage collector, there are C functions for accessing and manipulating Factor objects. The data conversion functions are not documented yet, so here's a sampling of a few of them:

unbox_u16_string() - pop a Factor string off the datastack and return it as a F_CHAR*
from_u16_string() - convert a C string to a Factor object
REGISTER_C_STRING() - register a C string with Factor's garbage collector
UNREGISTER_C_STRING() - unregister a registered C string
dpush() - push an object onto the datastack
dpop() - pop an object off of the datastack

Registering a C string with the garbage collector is required when VM code calls code that may trigger a garbage collection (gc). Any call to Factor from the VM might trigger a gc, and if that happened the object could be moved, thus invalidating your C pointer. When a pointer is unregistered, it's popped from a gc stack with the corrected pointer value.

Here is the call to set-os-env:

DEFINE_PRIMITIVE(set_os_env)
{
 F_CHAR *key = unbox_u16_string();
 REGISTER_C_STRING(key);
 F_CHAR *value = unbox_u16_string();
 UNREGISTER_C_STRING(key);
 if(!SetEnvironmentVariable(key, value))
     general_error(ERROR_IO, tag_object(get_error_message()), F, NULL);
}

The function is defined with a macro DEFINE_PRIMITIVE that takes only the function name. A corresponding DECLARE_PRIMITIVE goes in run.h as your function declaration. Not all primitives use these C preprocessor macros, for instance bignums don't because it doesn't improve the performance. Parameters to your primitive are popped or unboxed off the data stack, so a primitive's declaration expands to:

F_FASTCALL primitive_set_os_env_impl(void);

F_FASTCALL void primitive_set_os_env(CELL word, F_STACK_FRAME *callstack_top) {
    save_callstack_top(callstack_top);
    primitive_set_os_env_impl();
}
INLINE void primitive_set_os_env_impl(void)

F_FASTCALL is a wrapper around FASTCALL, which on x86 will pass the first two arguments in registers as an optimization. Note that while it declares that it takes no arguments (void), most primitives will do something to the data stack.

Since unbox_u16_string() allocates memory for the Factor object, it could trigger a gc, so it's registered as a string. You can also register values using REGISTER_ROOT for cells, REGISTER_BIGNUM for bignums, and REGISTER_UNTAGGED for arrays, words, and other Factor object pointers for which the type is known. The key string can immediately be unregistered after calling unbox on the next stack value since the rest of the function will not cause a gc. If the win32 call fails, there's a function general_error() that throws an exception. In this case, it's an ERROR_IO that calls a helper function to return the Windows error message.

Now that the function is written, you have to add it to the list of primitives in primitives.c. The important thing is that this list remains in the same order as the list in core/ which you will edit in the next section. Also, add a prototype to the run.h file.

Adding a primitive to core/

Everything in Factor compiles down to primitives. Because they are by definition "primitive", the compiler cannot infer the stack effect and argument types. To make a primitive's stack effect "known", edit core/inference/known-words/known-words.factor:

\ set-os-env { string string } { } <effect> set-primitive-effect

The next step is to put your word in the file core/bootstrap/primitives.factor in the same order as in vm/primitives.c.

Sometime in the future there might be a PRIMITIVE: word that will reduce the number of different places to edit to add a primitive. If it used Factor's FFI, you could add a new primitive without even having to bootstrap again.

Recent Changes in Factor

2008-03-28T11:51:00.000-07:00

Here are some things I've been working collaboratively with some other Factor devs lately.

cwd, cd, and pathname changes

The old way to change the current working directory was to call the cd word. This is now obsolete, and code that does this won't get the expected behavior anymore. A new word, normalize-pathname, is called before every top level word using paths and adjusts the pathname based on a new dynamic variable called current-directory.

To get pathnames relative to the Factor directory you used to use the words ?resource-path and resource-path. The code "resource:foo.txt" file-contents now does what "foo.txt" resource-path file-contents used to do, so user code should avoid calling resource-path on path literals.

Also, there's a new word called with-directory ( path quot -- ) that calls your quotation with a new current working directory and restores the old one when done. All of words that deal with reading and writing files have been updated to respect this change.

Using the cd word is still useful sometimes, like when calling with-fork ( parent-quot child-quot -- ) when you want the child process to inherit the current-directory variable as its current directory.

Pathnames in Factor are still strings, but may be either strings or pathname objects in the future.

IO Launcher Priorities

Since some Factor developers still use Windows XP on single-core laptops from 2004, tools.deploy now sets the child process to have a lower priority so that the system is still usable when deploying images.

Example:

<process>
    { "cmd" "/c" "dir" "/S" "\\" } >>command
    +low-priority+ >>priority
run-process

BSD Port

Factor now supports FreeBSD, NetBSD, and OpenBSD 32 and 64bit versions. Please inform us of any bugs you find. Binary releases should happen within a week.

Fixing the Solaris port is next up, followed by the ARM Linux and WinCE port.

Random number generator protocol

Because we want to generate secure random numbers for the new web framework, the Mersenne twister algorithm just won't do as Factor's sole pseudo random number generator. So until we implement a Yarrow prng, the default prng for cryptography is /dev/random on Unix systems and the CryptGenRandom call on Windows. Does anyone have a suggestion as to which provider to use? I'm using PROV_RSA_AES right now, but I just chose it randomly from the list.

The random protocol is really simple.

GENERIC: seed-random ( tuple seed -- )
GENERIC: random-32* ( tuple -- r )
GENERIC: random-bytes* ( tuple n -- bytes )

M: object random-bytes* ( tuple n -- byte-array )
    [ drop random-32* ] with map >c-uint-array ;

M: object random-32* ( tuple -- n )
    4 random-bytes* le> ;

There are two ways to get randomness -- either 32 bits at a time, or several bytes at a time. The cool thing is that you only have to put a method on one of these words, and the other one is taken care of by the default method! Of course, if you don't define either, the callstack will overflow. You can define methods on both for efficiency if it makes sense.

Singletons in Factor

2008-03-12T13:48:00.000-07:00

A singleton is a design pattern that only allows for a unique class that is only instantiated once. In other languages, singletons can contain global data, but why not just use a global to store global state instead?

In Factor, a singleton is simply a predicate class whose predicate tests if the class is identical to itself. Singletons are defined like this:

SINGLETON: factor

That's it! No messy boilerplate to copy and paste, no subtle reasons why your singleton might be wrong in some corner case. Using the singleton, we can replace some of the less elegant parts of the Factor core code and implement things in a simpler way.

For instance, until now the core words os and cpu have returned strings based on how the Factor binary is compiled. Soon, these strings will be parsed into whichever singleton they represent, allowing for generic dispatch. I wanted to have a cross-platform library for finding out basic hardware information about your computer, like how many cpus/cores, what speed, and how much RAM is in a machine. To do this without singletons, I had to redefine information already available as strings (the cpu and os words) as symbols. With singletons, this duplication can be removed. The same applies to the compiler code and loading libraries.

Here is the way the core supported operating systems can be defined using singletons.

SINGLETON: winnt
SINGLETON: wince
SINGLETON: macosx
SINGLETON: linux
UNION: windows winnt wince ;

Now we can dispatch on these to find the number of cores:

HOOK: #cpus os ( -- n )
M: macosx #cpus { 6 3 } sysctl-query-uint ;
M: winnt #cpus system-info SYSTEM_INFO-dwNumberOfProcessors ;

For loading code, the current idiom is this:

<< "alut" {
        { [ win32? ]  [ "alut.dll" ] }
        { [ macosx? ] [ "/System/Library/Frameworks/OpenAL.framework/OpenAL" ] }
        { [ unix?  ]  [ "libalut.so" ] }
    } cond "cdecl" add-library >>

Using singletons, we can shorten this to:

"alut" {
    { win32 "alut.dll" }
    { macosx "/System/Library/Frameworks/OpenAL.framework/OpenAL" }
    { unix "libalut.so" }
} add-library

The library is assumed to be 'cdecl', but if it were 'stdcall' you could specify this by adding a "stdcall" string after the libary name, thus making a triple instead of a pair. The amount of boilerplate is reduced and the programmer can be more productive and write fewer bugs.

The implementation of singleton is:

: define-singleton-class ( class -- )
    \ word swap
    dup [ eq? ] curry define-predicate-class ;

This generates code that looks like:

PREDICATE: word winnt \ winnt eq? ;

It makes a predicate class with a superclass of 'word' that you can dispatch on and only a single instance exists. Why are singletons so hard to define in some other languages?

Google Summer of Code 2008 Project Ideas

2008-03-06T13:15:00.000-08:00

The Factor project is applying for Summer of Code. Here are our project ideas.

Applications

Write a structure editor
Write a text editor
Write an IRC client
Write a package manager for Factor
Write a file manager

Enterprise Factor

Update the bindings to MySQL, Oracle, ODBC for the latest DB framework in extra/db
Add bindings for DB2, Informix, SQL Server, Sybase, etc
Write a MySQL binding in Factor instead of calling the C library to permit nonblocking I/O operation and avoid GPL licensing issues
Write high-level wrapper for OpenSSL binding which implements encrypted Factor streams
Write a SOAP stack
Improve the continuation-based web framework with ideas from Seaside

Embedded Languages

Improve the Prolog implementation in extra/prolog
Revive extra/lisp
Write an assembler to a microcontroller and cross-compile applications from within Factor
Write an infix math DSL
Write a 'language X' to Factor compiler, where X is C, Ruby, Python, Javascript, Elisp, etc

Miscellaneous Libraries

Write a binding and high level interface to zlib or implement gzip compression in Factor
Finish the tar library
Finish the packet sniffer libraries
Implement the math algorithm of your choice for extra/math
Implement the data structures described in Purely Functional Data Structures
Write a COM interface
Improve the JNI library
Write a JNI-like bridge for Android
Write a wrapper for Windows Mobile libraries to make calls and send SMSs
Integrate the zoneinfo timezone database with Factor's calendar library
Add more calendars to the library, such as Persian, Hebrew, Islamic, Chinese, Hindu, Buddhist

Factor VM

Write a GC profiler
Make GC memory areas shrink after garbage collection
Implement dtrace probes
Make continuations serializable

User Interface

Write a binding to an image manipulation library
Finish bitmap library
Improve the look of Factor's UI gadgets
Add drag and drop support
Add any of the following gadgets: tabs, syntax highlighting text editor using the xmode library, combo boxes, tables, trees, spinners
Implement native font rendering on Windows

Disassembler Vocabulary "ported" to Windows

2008-02-14T21:41:00.000-08:00

Slava wrote a vocabulary to send gdb a process id and a range of addresses to disassemble in order to streamline the process of writing compiler optimizations. The original code only worked on Unix, requiring a call unix:getpid, which is a Unix system call. The Windows equivalent is GetCurrentProcessId. Since we need to call the Unix version on MacOSX and Linux, and the Windows API call on Windows XP, we use a Factor design pattern -- the HOOK:.

The HOOK:

The word in question is called make-disassemble-cmd. Behold its majesty:

QUALIFIED: unix

M: pair make-disassemble-cmd
    in-file [
        "attach " write
        unix:getpid number>string print
        "disassemble " write
        [ number>string write bl ] each
    ] with-file-out ;

You can see where it's calling unix:getpid. Knowing the Windows API call from above, it's easy to write a version that works on Windows:

M: pair make-disassemble-cmd
    in-file [
        "attach " write
         GetCurrentProcessId number>string print
        "disassemble " write
        [ number>string write bl ] each
    ] with-file-out ;

Obviously, this is unacceptable, because now it doesn't work on Unix! If we rename the make-disassemble-cmd word for the new platform, then there are still two copies of the exact same word, and you'll be loading them both on platforms where they shouldn't be loaded. We really just want to rename the one word that changed, so...

Let's make a HOOK:

! in io.launcher
HOOK: current-process-handle io-backend ( -- handle )

! in io.unix.launcher
M: unix-io current-process-handle ( -- handle ) getpid ;

! in io.windows.launcher
M: windows-io current-process-handle ( -- handle ) GetCurrentProcessId ;

! in tools.disassembler
M: pair make-disassemble-cmd
    in-file [
        "attach " write
        current-process-handle number>string print
        "disassemble " write
        [ number>string write bl ] each
    ] with-file-out ;

Now, there is just one word that will do the work on both platforms. The relevant code is only loaded into the image on the correct platform, and the problem is solved without renaming lots of words, without #ifdefs, and without copy/pasting.

Text Editor Integration and Directory Traversal

2008-02-12T10:19:00.002-08:00

To edit a word in Factor you pass the edit word a defspec, like \ + edit or { float + } edit, or you press CTRL-SHIFT-E on a word. If an editor path is already set, then the word definition should pop up in your editor at the line of the definition. However, if you haven't configured your text editor, a restart will be thrown and you can select it from a list. If you selected gvim, previously it would use a braindead algorithm that makes a list of all paths in \Program Files and then traverses that list looking for the gvim.exe binary. This caused it to hang while doing tons of disk IO.

Now it's better in two ways -- it only looks in \Program Files\vim\ (oops), and secondly you can search with find-file-breadth or find-file-depth. The implementation is pretty simple -- breadth first search uses a dlist, pushes the new traversal results to the back of the list, and traverses the list in order. Depth first also pushes newly found directories to the end of the list, but it pops them from the end.

The next step is to extract out the depth/breadth first algorithm so it's generally useful, but I need to continue working on the database library.

Factor Tax Library

2008-02-11T14:48:00.000-08:00

I've been doing my own taxes for a few years, so I decided to start writing some Factor words to help with the calculations. This library does FICA tax, Medicare tax, and federal income tax, along with Minnesota state tax.

To get paid by an employer you fill out a Form W-4 which they keep on file. The three relevant pieces of information are the tax year (2008), the number of allowances, and whether or not you are married.

In Factor this looks like:

TUPLE: w4 year allowances married? ;
C: <w4> w4

To calculate your withholding, or the amount your employer should withhold from your salary every pay period, the library starts with your yearly salary, a Form W-4, and a tax collector entity, such as <federal> or <minnesota> and calls the withholding word.

For the average single male programmer making $70k per year, the calculation looks like this:


( scratchpad ) 70000   2008 3 f <w4> <federal> withholding dup money.
$16,054.00
( scratchpad ) biweekly money.
$617.46

The government's cut of your paycheck isn't too hard to calculate. The employer withholds 6.2% of your paycheck for FICA (social security) and contributes a matching 6.2% that is over and above your salary, for a total of 12.4%. The FICA tax has what's known as a base rate, which is a ceiling on the amount of your salary that this tax is applied to. For 2008, the base rate is $102,000, which means that the FICA tax is not applied above this amount. Additionally, you and your employer pay Medicare tax, which is 1.45% each for a total of 3.9%, and this is applied to all income (no base rate).

Now for the Federal income tax. Take your salary and subtract $3500 times the number of allowances you claimed on your Form W-4. For instance, three allowances (working only one job, claiming self as a dependent, and head of household) will give you a $10,500 allowance, which will leave $59,500 taxable income. (Note: FICA and Medicare tax apply to the entire salary, while Federal income tax applies only to the salary - allowances) There are several equivalent charts for looking up the federal income tax withholding, so this library uses the annual one because it was easiest to encode.

So for the example salary of $70,000 with three allowances, the calculation looks like:

( scratchpad ) 70000 2008 3 f <w4> <federal> federal-tax money.
$10,699.00
( scratchpad ) 70000  2008 3 f <w4> fica-tax money.
$4,340.00
( scratchpad ) 70000  2008 3 f <w4> <federal> medicare-tax money.
$1,015.00
( scratchpad ) { 10699 4340 1015 } sum money.
$16,054.00
( scratchpad ) 70000  2008 3 f <w4> <federal> withholding money.
$16,054.00

Salaries are taxed at different rates as they increase. For example, the first $2,650 dollars you make are taxed at 0% federal income tax rate. This does not mean you pay no tax at all; FICA and Medicare still apply. From $2,650 to $10,300 the tax rate is 10%. So, if somehow you were making $8,650 per year after deducting allowances, you would be in the second tax bracket and your taxable income would be $6000, taxed at 10%, for a total of $600. Your employer would withhold this amount from your paychecks and pay it to the government quarterly. (Note: the numbers above are for single people, married people have a more advantageous table)

Minnesota has one of the highest state taxes. To calculate this tax, take the same allowances from your Form W-4 and calculate the allowance per the federal income tax, $3,500 per allowance. Again, there are two tables -- single and married. The tax amounts are 5.35%, 7.05%, and 7.85% in the highest bracket.

( scratchpad ) 70000  2008 3 f <w4> <minnesota> withholding money.
$3,686.68

So, altogether, the employer withholds your federal and state taxes from the paycheck. You can calculate this:

( scratchpad ) 70000  2008 3 f <w4>  employer-withhold dup money. biweekly money.
$19,740.68
$759.26
( scratchpad ) 70000  2008 3 f <w4> <minnesota> net money. biweekly money.
$50,259.33

So if you make $70k in Minnesota, your employer should withhold $759.26 per paycheck, to be split between the federal and state government and paid quarterly (or monthly). You would get to keep $50,259.33 and the employer would give you a Form W-2 with the relevant details. You could the file income tax returns on April 15th, where you could possibly get some of that back from various deductions and refunds.

All values are calculated in rational numbers, so they are exact until the end, where the cents are rounded to the nearest cent. Percentages are in the source as decimal numbers, and are parsed using the DECIMAL: word.

( scratchpad ) DECIMAL: .1 .
1/10

Please feel free to submit patches for other states and to help me correct any bugs.

Parsing HTTP headers in Factor with multi-assocs

2008-02-02T20:44:00.001-08:00

The implementation of setting and parsing http headers in Factor has previously used a hashtable with a single key/value pair. However, this is broken because certain fields can be sent twice, e.g. set-cookie. The new implementation is a hashtable with keys/vectors to store multiple values for the same key.

I originally tried to make this obey the assoc protocol so that you could convert from a hashtable of vectors back to any type of assoc (hashtable/alist/AVL tree/etc) but this turned out to be a really bad idea because not only was it not useful, but it breaks the semantics of the assoc protocol if set-at inserts an element instead of sets it.

So the implementation is in assocs.lib as a few helper words:

: insert-at ( value key assoc -- )
    [ ?push ] change-at ;

: peek-at* ( key assoc -- obj ? )
    at* dup [ >r peek r> ] when ;

: peek-at ( key assoc -- obj )
    peek-at* drop ;

: >multi-assoc ( assoc -- new-assoc )
    [ 1vector ] assoc-map ;

: multi-assoc-each ( assoc quot -- )
    [ with each ] curry assoc-each ; inline

: insert ( value variable -- ) namespace insert-at ;

Of course, set-at and at still set and access the values, but there are a couple new utility words. The insert-at word has the same stack effect as set-at but pushes a value instead of setting it. peek-at will give you the last value set for a given key, and this is the standard way of accessing values when you only care about the last one.

To turn an assoc into a multi-assoc, call >multi-assoc. To iterate over all the key/value pairs, use multi-assoc-each.

The insert word is for use with the make-assoc word, which executes inside a new namespace and outputs the variables you set as a hashtable.

Here's an example of what the headers look like for a website:

( scratchpad ) USE: http.client "amazon.com" http-get drop .
H{
    { "connection" V{ "close" } }
    { "content-type" V{ "text/html; charset=ISO-8859-1" } }
    { "server" V{ "Server" } }
    { "x-amz-id-2" V{ "L0oid1yo1Z6cuq+VgwWCv0G/UdPov/0v" } }
    { "x-amz-id-1" V{ "15CPXN68HXB35FXE62CX" } }
    {
        "set-cookie"
        V{
            "skin=noskin; path=/; domain=.amazon.com; expires=Sun, 03-Feb-2008 04:57:59 GMT"
            "session-id-time=1202544000l; path=/; domain=.amazon.com; expires=Sat Feb 09 08:00:00 2008 GMT"
            "session-id=002-3595241-4867224; path=/; domain=.amazon.com; expires=Sat Feb 09 08:00:00 2008 GMT"
        }
    }
    { "vary" V{ "Accept-Encoding,User-Agent" } }
    { "date" V{ "Sun, 03 Feb 2008 04:57:59 GMT" } }
}

I have normalized the keys by converting them to all lower case. For some reason, Amazon sends two headers as Set-Cookie and the last one as Set-cookie, which is pretty weird.

Since the prettyprinter outputs valid Factor code, you can copy/paste the above headers into a Factor listener and run some of the multi-assoc words on them.

Sorting Filenames Containing Numbers

2007-12-13T09:41:00.000-08:00

Jeff Atwood articulated a problem I usually run into when looking at files in Explorer. If you have a bunch of files with numbers, file "a100.txt" will come before file "a2.txt" when sorted by name. Of course, two is less than 100, so you'd expect "a2.txt" to come first.

Here's a solution in Factor:


: human-sort ( seq -- newseq )
    [ [ digit? ] cut3 >r string>number r> 3array ] map natural-sort
    [ first3 >r number>string r> 3append ] map ;

{ "a100.txt" "a10.txt" } human-sort .
    { "a10.txt" "a100.txt" }

The algorithm is simple: split a filename at the first number, convert that from a string to a number, and let Factor's natural-sort do the rest.

It maps over the sequence, { "a100.txt" "a10.txt" }, and cuts it at the first number inside each element so, after cut3, you get the result on the stack like "a" "100" ".txt", and "a" "10" ".txt". You dip under the top element and convert the to a number, >r string>number r>, and 3array to make a sequence of sequences { { "a" 100 ".txt" } { "a" 10 ".txt" } }. You then call natural-sort on this. Natural-sort knows how to compare element by element, so seeing the "a" "a" is equal it moves onto the next comparison, 100 10. Now that it's in the right order, you still need to turn your sequence back into strings. natural-sort returned { { "a" 10 ".txt" } { "a" 100 ".txt" } }, so map (do something to each element in the sequence) over this and do first3 >r number>string r> 3append, which explodes the array, converts back to a string, and appends three strings together to get the filenames. The dot at the end prints it.

I had to write cut3, but it's a generally useful word for partitioning a sequence that I put into sequences.lib.


: cut3 ( seq pred -- head match tail )
    2dup find drop [
        rot swap cut rot [ not ] compose
        dupd find drop [ cut ] [ f ] if*
    ] [
        drop nip f like f f
    ] if* ;

UPDATE:

I generalized this to work on { "a100b200.txt" "a100b2.txt" } with some suggestions from Slava. If you understood the previous code, this should be pretty understandable too. It keeps calling cut3 until it returns no matches and accumulates the result in a sequence, all the while applying a quotation to whatever matched the predicate. It then compares with natural-sort like before, and transforms these sequences back into filenames. cut3 is cleaned up in this version. I ended up with two general words, cut3 and cut-all that can be put into a library, sequences.lib, and used elsewhere.


: cut-find ( seq pred -- before after )
    dupd find drop dup [ cut ] when ;

: cut3 ( seq pred -- first mid last )
    [ cut-find ] keep [ not ] compose cut-find ;
    
: (cut-all) ( seq pred quot -- )
    [ >r cut3 r> dip >r >r , r> [ , ] when* r> ] 2keep
    pick [ (cut-all) ] [ 3drop ] if ;

: cut-all ( seq pred quot -- seq )
    [ (cut-all) ] { } make ;


: human-sort ( seq -- newseq )
    [ [ digit? ] [ string>number ] cut-all ] map natural-sort
    [ [ dup string? [ number>string ] unless ] map concat ] map ;

{ "a100b2.txt" "a100b200.txt" } human-sort .
    { "a100b2.txt" "a100b200.txt" }

UPDATE TWO:

Here is a much better algorithm that doesn't reconstruct the original filenames and thus can handle leading zeros. It constructs keys that can be sorted by sort-values or sort-keys (sort-values is just as efficient here and it lets you use dup in the map instead of a [ ] keep, which makes the code slightly more legible).


: human-sort ( seq -- newseq )
    [ dup [ digit? ] [ string>number ] cut-all ] { } map>assoc
    sort-values keys ;

{ "000a.txt" "00a.txt" } human-sort .
    { "00a.txt" "000a.txt" }

Cross-platform Factor Install Script

2007-11-26T15:50:00.001-08:00

Recently, I wrote an installer/updater bash script that downloads the git repository, compiles, and bootstraps Factor. On Linux, it compiles Factor for console-only if any of the libraries required for the graphical interface are missing (freetype, GL, GLU, X11).

To install Factor to a directory: ./factor.sh install
To update your Factor repository: ./misc/factor.sh update

The script source code is available for browsing or for download.

Tested on Windows XP/Vista in Cygwin, Debian and Ubuntu Linux, and Mac OS X.

Please send bug reports and improvements. Thanks!

Where's my Raptor!??

2007-11-18T14:19:00.000-08:00

My Macbook's dock displayed the default icon instead of a raptor. The fix was to move the move the .app directory to another name, then to move it back. Now I have a raptor!

Does 10.4 do some caching? It probably had it cached wrong since we got the new icon.

Doubly-linked Lists, Queues, and Heaps

2007-11-07T14:45:00.000-08:00

Doubly-linked Lists and Queues

Factor has had doubly-linked lists for years now, but they were not well-documented or polished. Now, they're documented and have replaced the queues library.

An example of a dlist usage:

<dlist> "red" over push-front "blue" over push-front dup pop-back .
    "red"

You can add/remove nodes of a dlist with push-front, push-back, pop-front, pop-back, delete-node, and search with dlist-find, dlist-contains?.

Finding the length of a dlist is O(1) since it stores the length as dlist-length, a tuple slot.

Heaps

Heaps have been updated to allow for <min-heap> and <max-heap> data structures. Adding elements to a heap is achieved with heap-push ( value key heap -- ), while popping elements is heap-pop ( heap -- value key ).

Factor's green threads implementation had been using a hack for the sleep-queue: each time a new entry was added it would modify a non-growable array, which would then be sorted by the smallest timeout. Adding a sequence of sleep continuations would take O(n^2 log n) time! Running 10000 [ [ 100 sleep ] in-thread ] times should spawn 10000 threads and sleep for 100 ms in each one, and with the old sleep-queue implementation it takes over a minute on my Macbook. Now it's just O(n log n), which takes a second or two.

Windows SEH Revisited

2007-09-24T20:45:00.000-07:00

It turns out there are Win32 API calls to set up a structured exception handler (SEH) on Windows NT, which is easier and more reliable to use than inline assembly. To install an exception handler, call AddVectoredExceptionHandler. An exception handler gets passed a PEXCEPTION_POINTERS struct, which is a PEXCEPTION_RECORD and a CONTEXT*, both of which are defined in the header files. The context structure is different on every platform because it lists the contents of the CPU registers at the time of the exception, while the ExceptionRecord struct is the same, and contains the ExceptionCode and the address where it occurred (in ExceptionInformation[1]).

The job of the exception handler is to determine where program execution should proceed after it returns. For Factor, the errors we handle are memory access errors, which happen when a stack overflows or underflows and hits a guard page, division by zero, and 'any other error'. We can't just jump to these Factor exception handlers inside the Win32 exception handler, but we can set the instruction pointer, the EIP register, to our handler and return EXCEPTION_CONTINUE_EXECUTION. In this way, we can let the operating system catch errors and report them to the user as "Data stack underflow", "Division by zero", and continue running Factor without expensive checks for each memory access or division.

The stack pointer at the time of the exception is also important. If we were executing compiled Factor code, as determined by checking the fault address against the C predicate in_code_heap_p, then we set a global with this address to continue execution after the exception is handled. However, if we are in C code, then the global is left as NULL.

Here is the code--much cleaner, and more correct, than before.

void c_to_factor_toplevel(CELL quot)
{
    AddVectoredExceptionHandler(0, (void*)exception_handler);
    c_to_factor(quot);
    RemoveVectoredExceptionHandler((void*)exception_handler);
}

long exception_handler(PEXCEPTION_POINTERS pe)
{
    PEXCEPTION_RECORD e = (PEXCEPTION_RECORD)pe->ExceptionRecord;
    CONTEXT *c = (CONTEXT*)pe->ContextRecord;

    if(in_code_heap_p(c->Eip))
        signal_callstack_top = (void*)c->Esp;
    else
        signal_callstack_top = NULL;

    if(e->ExceptionCode == EXCEPTION_ACCESS_VIOLATION)
    {
        signal_fault_addr = e->ExceptionInformation[1];
        c->Eip = (CELL)memory_signal_handler_impl;
    }
    else if(e->ExceptionCode == EXCEPTION_FLT_DIVIDE_BY_ZERO
            || e->ExceptionCode == EXCEPTION_INT_DIVIDE_BY_ZERO)
    {
        signal_number = ERROR_DIVIDE_BY_ZERO;
        c->Eip = (CELL)divide_by_zero_signal_handler_impl;
    }
    else
    {
        signal_number = 11;
        c->Eip = (CELL)misc_signal_handler_impl;
    }

    return EXCEPTION_CONTINUE_EXECUTION;
}

void memory_signal_handler_impl(void)
{
    memory_protection_error(signal_fault_addr,signal_callstack_top);
}

void divide_by_zero_signal_handler_impl(void)
{
    general_error(ERROR_DIVIDE_BY_ZERO,F,F,signal_callstack_top);
}

void misc_signal_handler_impl(void)
{
    signal_error(signal_number,signal_callstack_top);
}

Destructors in Factor

2007-09-08T18:23:00.000-07:00

After spending way too much time trying to perfect Factor's win32 api code, I wrote a word I should have written long ago: with-destructors. What this allows you to do is allocate a system resource, add a destructor, and automate the resource cleanup, even when an exception is thrown. Take this buggy code as an example of resource leaks.


TUPLE: mallocs one two three ;

: three-mallocs-buggy ( -- obj )
    100 malloc
    200 malloc
    300 malloc
    \ mallocs construct-boa ;

Any one of these calls to malloc could fail. If the first one fails, an error is thrown and no resources are lost. However, if the second or third fail, nothing will ever clean up after the successful allocations, and resources are leaked!

One alternative is to put each malloc into a tuple slot as they succeed. This solution is quite verbose and needs an extra cleanup word (boilerplate).


TUPLE: mallocs one two three ;

: cleanup-mallocs ( mallocs -- )
    dup mallocs-one [ free ] when*
    dup mallocs-two [ free ] when*
    dup mallocs-three [ free ] when* ;

: three-mallocs-verbose ( -- obj )
    \ mallocs construct-empty
    f
    [
        drop
        100 malloc over set-mallocs-one
        200 malloc over set-mallocs-two
        300 malloc over set-mallocs-three
        t
    ] [
        [ cleanup-mallocs ] unless
    ] cleanup ;

We need a boolean because we only want to cleanup up resources if something fails. See how we save each malloc as it's created? Otherwise it could get lost. This tedious method is how much of the win32 native io (io completion ports) is implemented right now. Notice that the cleanup word doesn't even set all the slots in the tuple to f, so if you called cleanup-mallocs twice somehow, your program would hopefully crash (sooner rather than later!). More boilerplate would fix it.

Instead, let's wrap each returned resource in a destructor.


TUPLE: mallocs one two three ;

: three-mallocs ( -- obj )
    [
        100 malloc dup [ free ] f add-destructor
        200 malloc dup [ free ] f add-destructor
        300 malloc dup [ free ] f add-destructor
        \ mallocs construct-boa
    ] with-destructors ;

Ah! This is marginally more work than the first example, but is 100% correct. The word add-destructor ( obj quot always? -- ) takes an arbitrary object, a destructor quotation (some code), and a boolean to tell it under which circumstances to cleanup the resource. Calling add-destructor with t will always clean up the resource; calling it with f will only clean up if the quotation passed to with-destructors fails. Thus, a cleanup routine is required elsewhere, but we can worry about that later. The duplicated code could be factored out if you find yourself using it often, but I have chosen not to here because of the tricky boolean flag for add-destructor. In practice, I need to save about half of the resources and to destroy the other half very soon after creation. However, it still might be best to factor out the duplicate code:

: destruct-malloc-on-fail ( obj -- ) [ free ] f add-destructor ;

This example is trivial compared to using win32 for memory mapped io, which requires: escalating two privileges, opening a file, creating a file mapping, calling map view of file, and lowering both privileges, any of which could fail! This series of calls allocates two file handles and requires unmapping the file during cleanup. The four calls to the privileges routines call malloc, and this could also leak resources!

This complexity is the norm when writing code for performance and reliability in win32.

The destructor implementation is simple:


USING: continuations kernel namespaces sequences vectors ;
IN: destructors

SYMBOL: destructors
SYMBOL: errored?
TUPLE: destructor obj quot always? ;

<PRIVATE

: filter-destructors ( -- )
    errored? get [
        destructors [ [ destructor-always? ] subset ] change
    ] unless ;

: call-destructors ( -- )
    destructors get [
        dup destructor-obj swap destructor-quot call
    ] each ;

PRIVATE>

: add-destructor ( obj quot always? -- )
    \ destructor construct-boa destructors [ ?push ] change ;

: with-destructors ( quot -- )
    [
        [ call ] [ errored? on ] recover
        filter-destructors call-destructors
        errored? get [ rethrow ] when
    ] with-scope ; inline

with-destructors and add-destructor make up the main interface. If the quotation passed to with-destructors succeeds, the always-destructs are filtered out of the destructor sequence, and call-destructors destroys the objects that are left.

Hopefully this library will make dealing with system resources in Factor all but trivial.

Managed malloc and free

2007-08-31T23:10:00.000-07:00

The Factor Windows backend has to use manual memory management for Windows runtime callbacks. This opens up a small amount of code to double free errors. And crashes. But Factor is better than that; why crash when you can easily prevent it?

The new malloc adds an entry to a global hashtable, mallocs, whenever new memory is allocated. Upon calling free, it checks that the buffer is still allocated before making the actual memory cleanup call. This managed version of malloc is now the default. To get plain old libc memory allocation, call (malloc) and (free), though the overhead is negligible compared to having your program crash.

Does it work? Yes! Opening a new UI window adds two new mallocs, and closing it takes them away. After running test-all there were two mallocs that went unchecked; both were bugs and corrected in five minutes by inspection. Finally, there is no way to call free twice on a pointer using the managed malloc/free since, if that pointer is not in the mallocs hashtable, an error is thrown. Now, to check that you balance malloc/free calls, you can run your code and make sure the malloc hash doesn't have extra entries. Here's a snippet to count the entries:

mallocs get-global assoc-size .

The code works for calloc and realloc as well, and can be perused here.

Roman Numeral Conversion in Factor

2007-06-20T22:58:00.000-07:00

I whipped up some words to convert integers to Roman numerals. The word <PRIVATE changes the IN: vocabulary to roman.private to hide the implementation from the library user. Of course you can access these private words, like all words in Factor, with a USE:.

The algorithm is simple. Going from high to low, iterate the Roman numeral values and /mod (integer division with remainder) each with the input, outputting the divisor and replacing the input with the remainder. This algorithm treats 4s and 9s as digits, just as it treats single letters as digits (i, v, x, etc). Without the 4s and 9s, you end up getting longer answers that, while logical, are wrong, e.g. 9 is "ix", not "viv". (I found this bug in the first iteration while writing unit tests.)

The words we care about, >roman and >ROMAN, are placed IN: roman because of the PRIVATE> word, which drops back to the public vocabulary roman. The > in a word's name is a convention for words that do conversions; the parentheses around the word (>roman) mean it's an implementation word; you should never have a (>roman) without also having a >roman. Picking these names is done purely by convention--the only forbidden word names are numbers and words that start with a ", which parse as strings. Everything until whitespace is a word name.

The conversion from Roman numerals back to integers and roman+, roman*, etc are in roman.factor.

USING: arrays assocs kernel math math.vectors namespaces
quotations sequences sequences.private strings ;
IN: roman

<PRIVATE

: roman-digits ( -- seq )
    { "m" "cm" "d" "cd" "c" "xc" "l" "xl" "x" "ix" "v" "iv" "i" } ;

: roman-values ( -- seq )
    { 1000 900 500 400 100 90 50 40 10 9 5 4 1 } ;

TUPLE: roman-range-error n ;

: roman-range-check ( n -- )
    dup 1 3999 between? [
        drop
    ] [
        <roman-range-error> throw
    ] if ;

: (>roman) ( n -- )
    roman-values roman-digits [
        >r /mod swap r> <repetition> concat %
    ] 2each drop ;

PRIVATE>

: >roman ( n -- str )
    dup roman-range-check [
        (>roman)
    ] "" make ;

: >ROMAN ( n -- str ) >roman >upper ;

Windows CE SEH for ARM with GCC

2007-04-27T00:35:00.000-07:00

Structure exception handling (SEH) is a low-level way to handle software and hardware exceptions in Microsoft Windows. Other exception handling mechanisms are built on top of SEH. Factor uses SEH in order to report stack underflow/overflow errors on Windows. Microsoft Visual Studio (VS) would usually take care of the tricky implementation details by supplying __try, __except, and __finally keywords, but Factor's compiler relies on globally assigning the datastack and retainstack to specific registers, a feature which VS does not support. Conversely, GCC does not support __try, so we are left to implement the exception handler in assembly.

The internal implementation is both OS and architecture dependent, meaning that we have to support SEH on Windows NT on x86, and Windows CE for x86 and ARM. Digging through MSDN leads to a page called SEH in RISC Environments, where RISC standing for "Reduced Instruction Set Computer". (You are just supposed to know that ARM is RISC and x86 is CISC). I recommend reading about SEH on MSDN, but it basically says that SEH on RISC uses Virtual Unwinding and that you will need to set the PDATA structure for your function in order to set up the exception handler. Virtual unwinding traverses the framestack until it finds a frame with an exception handler, at which time it will actually unwind the framestack to that point and call the exception handler.

All we need to do is define void run_toplevel(void){...} to install our exception_handler and call Factor's "main" subroutine, run.

vm/os-windows-ce.c


long exception_handler(PEXCEPTION_RECORD rec, void *frame, void *ctx, void *disp
atch)
{
    memory_protection_error(
        rec->ExceptionInformation[1] & 0x1ffffff, // mask off process slot
        native_stack_pointer());
    return -1; /* unreachable */
}

vm/os-windows-ce-arm.S


 .text

 .globl run_toplevel

 .word exception_handler
 .word 0

run_toplevel:
 ldr pc, _Prun

_Prun:  .word run

 .section .pdata
 .word run_toplevel
 .word 0xc0000002 | (0xFFFFF << 8)

The C code passes the memory fault address, stored in ExceptionInformation[1], and the native stack pointer (another assembly function that simply moves ESP -> EAX) to a function that converts the fault address into a Factor stack error message, e.g. "Datastack underflow". The fault address is actually a slotized address, meaning that it is relative to some process slot which must be masked off. Annoyingly, the exceptions happen at different address ranges on the emulator and on a real mobile device. Slotized addresses in this context are not well documented on MSDN, but the Windows CE Blog Team quickly answered my email. (Thanks!)

The assembly code is mostly boilerplate. The .text directive starts us in the executable code section. We're going to be exporting void run_toplevel(void){...} in order to call it from C, so we declare it as a .globl and start the definition. We simply call our "main" function, void run(void){...}, which is the platform-dependent run function to start the Factor interpreter.

Hopefully, if someone else has to do this it will take much less time.

Building Factor in Cygwin now supported

2007-04-12T11:10:00.000-07:00

Factor has only compiled on MinGW since we made the Windows Factor port a couple of years ago. The problem with Cygwin has been its dependence on cygwin1.dll, which slows your program. Also, the Cygwin installer doesn't add it to your path, so that is one more step (and not standard). Additionally, structured exception handling (SEH) works the first time but hangs on the second time it triggers with the dll, e.g. on the second stack underflow.

However, Eric Mertens, a new Factor user, found a compiler flag to disable cygwin.dll:
-mno-cygwin

Three cheers for new users!

This flag fixed both the dll dependency and the SEH bug, allowing all unit tests to pass. The only other change I had to make for the port was to #include <wchar.h> for the compiler to find wcslen().

So now you can compile Factor with either MinGW or Cygwin, and both versions are officially supported.

Serialization To Disk

2006-12-30T11:12:00.000-08:00

For fun, I wrote a TinyURL clone in Factor. You can try it out at http://wee-url.com. I needed a way to save the data to a file, so I used libs/serialize to serialize the hashtable containing the links. There was yet another bug involving vector literals -- the serialization code would reuse a vector, so the first time you serialized the output is correct, but the next time it would produce garbage.

  scratchpad SYMBOL: aa H{ { 1 2 } } aa set
  scratchpad aa get .
H{ { 1 2 } }
  scratchpad aa get [ [ serialize ] with-serialized ] string-out .
"hp\0\0\0\u0001Dap\0\0\0\u0001Ep\0\0\0\u0001\u0001ap\0\0..."
  scratchpad aa get [ [ serialize ] with-serialized ] string-out .
"op\0\0\0\u0001:"

The fix was to change a V{ } to a V{ } clone.

Serialization to Disk Code

: save-fstore ( variable path -- )
     [ [ get serialize ] with-serialized ] with-stream ;

: load-fstore ( variable path -- )
    dup exists? [
         [ [ deserialize ] with-serialized ] with-stream
        swap
    ] [
        drop >r H{ } clone r>
    ] if set-global ;

: fstore-set ( variable fstore -- )
    get >r [ get ] keep r> set-hash ;

: fstore-get ( default variable fstore -- )
    get dupd hash* [ swap set-global drop ] [ drop set-global ] if ;

save-fstore and load-fstore save/load a hashtable to disk. The hashtable keys are variable names and the values are the variable values. fstore-set puts your variable in the hashtable, so you should call this directly before saving to disk. fstore-get loads the data from your store. If there is no fstore or if the key does not exist, it uses your default value.

The loading code is pretty simple:

: fstore-name "wee-url.fstore" ;
SYMBOL: wee-shortcuts
SYMBOL: wee-fstore
wee-fstore fstore-name load-fstore
H{ } clone wee-shortcuts wee-fstore fstore-get

The variable wee-shortcuts stores the encoded URLs, while wee-fstore is the hashtable that the above code reads/writes to disk.

Finally, to write the store:

: save-shortcuts ( -- )
    wee-shortcuts wee-fstore fstore-set
    wee-fstore fstore-name save-fstore ;

Notice that we add wee-shortcuts to the hashtable before saving to disk.

I'm going to rewrite the wee-url code to use Furnace instead of callback-responder. Once I get it looking nice, I'll show you how it works.

Compiling Factor on the Intel Mac

2006-11-23T15:50:00.000-08:00

To compile Factor for Mac you will need:

Installation DVDs that came with your Mac (for X11)
darwin-ports

Run the installation disk that came with your Mac in order to install X11. Since Apple does not offer X11 as a download for OS X 10.4 for Intel computers, you have to install from the DVD.
Download the darcs binary and place it in /usr/local/bin
Open terminal (Finder->Applications->Utilities->Terminal) and go to your home directory. To get the Factor source code, run:
```
darcs get http://factorcode.org/repos
```
To compile, move into the directory darcs created with cd repos/Factor and run the command make macosx-x86
Download the boot image at http://factorcode.org/images/latest/boot.image.pentium4
./f boot.image.pentium4
make macosx.app

(Optional) Create a shell script to start Factor in your terminal window. I called mine go.

#!/bin/sh
DIR=~/repos/Factor/Factor.app/Contents
$DIR/MacOS/Factor $@

Save the file and run chmod a+x go

(Optional) You can instead run open Factor.app and use Console.app to view runtime output.

To start the UI, run ./go or open Factor.app; run ./f to start Factor in the shell. If you run Factor in the terminal, I suggest using rlwrap, which adds a history buffer

Now you can code anything!

Bootstrapping, reset-modified, and F8

2006-11-16T11:07:00.000-08:00

Factor's module system has the ability to reload changed files from the UI, in the correct order, by calling reload-modules, which is bound to F8. When you download an image someone else created, the timestamps won't match up and when you reload the modules it will try to reload all of the Factor library. You don't want this.

There are several ways to fix the problem. First, you could generate a new image USE: image "x86" make-image and bootstrap again. Another way is to call reset-modified and then save the image. However, until you bootstrap from an image that you made yourself, will have the same problem.

If you make a module, don't forget to PROVIDE: contrib/my-module ; at the very least, or else F8 will not reload the changes you make after requireing it.

Using .factor-boot-rc and .factor-rc

2006-11-15T15:04:00.000-08:00

Update: I changed the syntax to work with the new directory layout.

The two resource files Factor tries to run, if they exist, are .factor-boot-rc and .factor-rc, at bootstrap and run-time respectively. You have to create these files yourself and place them in your home directory, e.g. the directory returned by the home word.

If I used Textmate on a Mac, my .factor-boot-rc would look like this:

USING: modules namespaces ;
REQUIRES: libs/textmate ;

Here is the boot file for gvim in Windows XP:

USING: modules namespaces ;
REQUIRES: libs/vim ;
USE: vim
"c:\\program files\\vim\\vim70\\gvim.exe" vim-path set-global

Now for loading libraries. Some of the modules in contrib/ require that you load your library before running. Here are three examples of a .factor-rc that loads libraries.

Loading PostgreSQL on a Mac:

USING: alien ;
"postgresql" "/opt/local/lib/postgresql81/libpq.dylib" "cdecl" add-library

PostgreSQL and SQLite on Windows:

USING: alien ;
"postgresql" "C:\\Program Files\\PostgreSQL\\8.1\\bin\\libpq.dll"
    "cdecl" add-library
"sqlite" "C:\\Program Files\\sqlite\\sqlite3.dll"
    "cdecl" add-library

SQLite on Linux:

USING: alien ;
"sqlite" "libsqlite3.so" "cdecl" add-library

Compiling Factor on Windows

2006-11-14T19:28:00.000-08:00

To compile Factor you will need:

MinGW
MSYS
darcs
freetype6.dll
zlib1.dll

Download MinGW and install it.

Download MSYS and install it. Make sure to tell the batch script about your MinGW install.

Download the latest package version of darcs and unzip it to c:\darcsdir-w32. darcs 1.0.7 is broken on Windows, so you must also grab the 1.0.8 binary and copy it into your darcs install directory over the broken version.

Set your path to include darcs. Run:
```
start->Control Panel->System->Advanced->Environment Variables
```
In System Variables, edit PATH, and append c:\darcsdir-w32 so that your path resembles:
```
c:\Program Files\sqlite;c:\darcsdir-w32
```
Start cmd.exe from the Run box and try out your darcs installation:
```
C:\Documents and Settings\Administrator>darcs --version
1.0.8 (release)
```

(Optional) To push patches to a remote server, you will need to generate an RSA key with puttygen unless you already have a public key. Run puttygen (installed with the darcs bundle), click generate, and move the mouse around to make your key. Save both your public and private keys in c:\darcsdir-w32. Adding a passphrase is optional (I didn't do it).

(Optional) On your remote Linux box running sshd, edit the file ~/.ssh/authorized_keys2 and paste your public key so that it looks something like this (but all on one line):


ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAIEAgMPa1vvlSi4ZrS7hrk/XJNwd9trM+TyvJjhkMzf3fhks
n8TFin7dhrRfFhVdjka0ep0+RGJrUI/ja6nDyG2SvzG1ka5Ml/Nes2PtpHWcwK7fwU9gBUZNzlvXCkOk
UKO7X7N65LnyCPjJDZa+8LPqrBeESjbVmstG4cw7uh0= doug@windows

(Optional) So that darcs can find your key, start Regedit and add a key for Pageant:
```
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Run
Name: Pageant
Data: c:\darcsdir-w32\pageant.exe c:\darcsdir-w32\private.ppk
```
When you reboot or run the above command, pageant will find your key and you can begin using darcs to push patches to your Linux box.

To get the Factor source, run this command wherever you want your local copy, perhaps from c:\:
```
darcs get http://factorcode.org/repos
```

Additionally, put these dlls in your Factor directory (repos/Factor/ on a default checkout):
```
freetype6.dll
zlib1.dll
```

Start MSYS (the blue M link) and change to your Factor directory. Mine is at c:\repos\Factor, so the command is:
```
cd /c/repos/Factor
```

From here you should be able to
```
make windows
```

From cmd.exe, change to the Factor directory and bootstrap with an image (x86) from factorcode.org:
```
f -i=boot.image.x86
```

Now you can run Factor!

I recommend bootstrapping and running Factor from cmd.exe because MSYS messes up stderr--you will not notice for a while if Factor has an internal error because there will be no output.

As a final note, the latest version from darcs is usually the best. If the boot image of Factor is stale and bootstrap fails, contact one of the devs in #concatenative on irc.freenode.org.

Happy Windows Factoring!

Update: Troubleshooting

Q: When starting Factor, why do I get the error 'alien-invoke-error-library "freetype", alien-invoke-error-symbol "FT_Init_FreeType"'?

A: You forgot to put freetype6.dll and zlib1.dll in the Factor directory. Download these and bootstrap again.

Q: When I bootstrap, why does Factor spew "*** Data GC (5 minor, 24 cards)" and error out with 'Word not found in current vocabulary search path delegate f no-word-name "\u000c"'?

A: On bootstrap you must pass the '-i' command line argument. The correct command line is:

./f -i=boot.image.x86

Factor 0.86 released

2006-11-14T18:57:00.001-08:00

Factor 0.86 has been released. We took about a week to test it before releasing this time, and it promises to be the most stable release ever. Factor for Windows has a few improvements too, as a long-standing bug with the native i/o has been fixed, allowing Factor to be run in the console while still supporting native i/o with the command:

f -shell=tty

Furthermore, in 0.85, Windows Factor took several minutes to slurp through a 600 MB file; the new version takes five seconds and will speed up again when continuations compile.