Factor: a practical stack language

Thursday, March 20, 2008

New slot accessors merged; future direction for Factor

The new slot accessors that I've talked about here and here have been merged into the core.

Old-style tuple slot accessors are still defined for all tuples. I will be porting code over the next few months to use the new accessors. All new code should use the new accessors. The old accessors will be removed at the end of May.

Next up in the language change department:

Implementation inheritance for tuple classes.
Removing delegation from the core and replacing it by Daniel Ehrenberg's extra/delegation library.
New tuple syntax with named slots.
Moving Doug Coleman's singletons to the core.
Moving extra/multi-methods into the core and removing the current generic word system; I have blogged about the multi-methods library in the past.
Declarative sequence construction using Eduardo's extra/bake library should be merged into the core. It can replace a whole slew of utility words and make Factor easier to learn.

Each one of these changes will be accompanied by refactorings of Factor's codebase to use the new features where appropriate.

I will spend the next few days dealing with the fallout from the new-slots merge; I also have a few minor features I want to get out of the way. Once that is done I will return to working on the web framework while continuing to ponder the implementation details of inheritance in my head. Once those are worked out I will dive back into the core.

These language changes are coming rather late in the evolution of Factor, however their utility, along with the recently merged new-slots, only became apparent after we wrote a lot of code, and so the justification for incorporating these features and removing the ones they replace is based on real experience and not just theoretical concerns.

Once these features are done I will be happy with the state of Factor's language and my focus will shift to performance, documentation, and peripheral libraries. Then, Factor 1.0 will be released and heads will roll.

Some improvements to locals: let* and methods with named parameters

The other day, Eduardo Cavazos remarked that working on Factor's locals library must be bittersweet. On one hand, we have this awesome demonstration of Factor's unmatched meta-programming capability: efficient, lexically scoped closures, integrated with Factor's syntax, implemented as a library of only 406 lines of code. On the other hand, very few libraries use it: I developed locals to provide an "escape hatch" from the world of stack code, but it turns out the only cases where it is necessary is for complex math formulas and certain hairy algorithms dealing with two-dimensional arrays and such. Maybe one in a hundred words stand to benefit from locals, and everything else can be expressed in a clean way using stack combinators. If locals were used more frequently, it would be great on one hand because this awesome library would be seeing some real usage. But on the other hand, if you had to resort to locals all the time, it would point to real weaknesses in the stack model.

Having said that, I still enjoy improving the locals library. I added two features recently that Doug Coleman requested.

The first feature is a [let* word. It is exactly like let* in Lisp and Scheme: you define a set of bindings and unlike [let, each binding can see the previous bindings.

Here is an example from the calendar library:

:: julian-day-number>date ( n -- year month day )
    #! Inverse of julian-day-number
    [let* | a [ n 32044 + ]
            b [ 4 a * 3 + 146097 /i ]
            c [ a 146097 b * 4 /i - ]
            d [ 4 c * 3 + 1461 /i ]
            e [ c 1461 d * 4 /i - ]
            m [ 5 e * 2 + 153 /i ] |
        100 b * d + 4800 -
        m 10 /i + m 3 +
        12 m 10 /i * -
        e 153 m * 2 + 5 /i - 1+
    ] ;

This is a hairy math formula for computing the year/month/day from the number of days since an epoch. Trying to do this with nested [lets would quickly get out of hand because each binding refers to the previous one. The version using dynamic variables doesn't suffer from deep nesting, but it is inefficient and harder to read because everything is bunched up with no clear demarkation of computations:

: julian-day-number>date ( n -- year month day )
    #! Inverse of julian-day-number
    [
        32044 + a set
        4 a get * 3 + 146097 /i b set
        a get 146097 b get * 4 /i - c set
        4 c get * 3 + 1461 /i d set
        c get 1461 d get * 4 /i - e set
        5 e get * 2 + 153 /i m set
        100 b get * d get + 4800 -
        m get 10 /i + m get 3 +
        12 m get 10 /i * -
        e get 153 m get * 2 + 5 /i - 1+
    ] with-scope ;

The nice thing about [let* is that after some refactoring, I was able to implement it with very little effort. Basically the only difference between it and [let is the parsing; the closure conversion stage is identical for the two, both expand into nested lambdas.

The next feature is method definitions with locals. You used to be able to define new words with named parameters, as in the above example, but there was no corresponding way to define a method with named parameters. I added a M:: word which does this. So now locals have named-parameter analogues of :, MACRO: and M:. This represents a combinatorial explosion of sorts: for every defining word you want to have named parameters for, you need to define a new version of that word. To alleviate this somewhat, I've redesigned some code in the parser and macro library so that everything is factored in a nice, logical way:

: (:) define ; parsing
: :: (::) define ; parsing

: MACRO: (:) define-macro ; parsing
: MACRO:: (::) define-macro ; parsing

: M: (M:) define ; parsing
: M:: (M::) define ; parsing

The parenthetical helper words are defined like so:

: (:) CREATE-WORD parse-definition ;
: (::) CREATE-WORD parse-locals-definition;

: (M:) CREATE-METHOD parse-definition ;
: (M::) CREATE-METHOD parse-locals-definition ;

This is what I like to call "perfect factoring".

Locals are meta-programmable and so they would be nice if someone decided to implement an efficient Scheme to Factor compiler; it seems like most of the hard work is already done. But who the hell wants to code Scheme anyway.

Wednesday, March 12, 2008

The new HTTP server, part 1

For the last couple of weeks I've been working on a redesign of Factor's HTTP server.

The old HTTP server

The old HTTP server dates back to 2003, when Factor was written in Java. At that time, the only Factor code I had written was about 5,000 lines for the core language, and some 15,000 lines of scripting code for my abandoned game project. The scripting code mostly consisted of configuration: creating hashtables filled with values, setting up various objects and calling into Java code to add them to global registries. I started writing the HTTP server because I wanted a simple example of a Factor application that I could demo independently of the game code. So it is fair to say that the HTTP server was the first "real" application written in Factor.

Four years later, the HTTP server is still around. It has evolved incrementally over the years, and survived some major changes in the Factor language, however it has never undergone a major overhaul or even been redesigned to use some abstractions that were introduced after I started working on the HTTP server.

For example, the HTTP server did not define a single class or generic word; when I started writing it, Factor didn't have an object system, I just used hashtables to simulate objects, with quotation values to simulate methods (much like Lua). HTTP headers and request parameters were stored in dynamically scoped variables named by strings. This somewhat ad-hoc design survived in the HTTP server to this day, and it made it harder to learn and extend than it had to be.

Another source of ad-hoc-ness was that while the HTTP request was parsed pretty well, writing the response was entirely up to the web app; it had to write out the headers directly. This would have made cookies and similar features harder to implement.

The old HTTP server served us well. It has powered and still powers several web sites which receive a lot of hits, and the API was good enough for simple applications. However, since I'm going to build commercial software with Factor, I need something higher-level and more robust, and I decided to redo the HTTP server from scratch, using the latest Factor abstractions and idioms, and incorporating many of the things I learned about web development over the last four years.

Progress so far

So, here is a quick rundown of the features I've implemented:

Component-based form framework with validation support
URL and cookie sessions
Database support
CRUD scaffolding
Authentication with login and registration page
User account info can be stored in memory or a database
Persistence of sessions in a database
Continuation-based page flow (based on Chris Double's code for the old server)
Logging with log rotation and nightly log analysis e-mail - this is in fact the new logging framework and I've blogged about it before

Still pending:

Documentation
Updating pastebin, planet, help web apps in extra/ to use it
SSL support using OpenSSL on Unix and native SSL APIs on Windows
Library for adding threaded discussion comments to any site
Better templating with support to make it easier to specify a common theme for the entire site

I will be blogging about the new features over the next few weeks. In this entry, I will talk about the most basic layer: HTTP request and response handling. This layer forms the foundation of any web application, even ones developed with the highest level abstractions such as CRUD scaffolding have to call into the HTTP layer at some point. I'd like to emphasize that the new HTTP server is already quite complete and moving very quickly; it is certainly not limited to the functionality I am describing in this post. I wanted to focus on the basics before I feel the fundamentals here are very well designed and they serve as a foundation for all other advanced functionality I have implemented.

HTTP requests and responses

The central concept in the new server is that HTTP requests and responses are now first-class types. The extra/http library implements these types and operations for working on them. An HTTP request can be parsed from an input stream, or written to an output stream. Similarly, an HTTP response can be parsed from an input stream, or written to an output stream.

Both the HTTP server and HTTP client use this library, and conceptually what they do can be explained in very simple terms:

The HTTP server reads a request from the client, processes it, and writes a response.

The HTTP client writes a request to the server, then reads a response from the server, and returns it to the user.

This is a very nice simplification and it allows a lot of code to be shared between the client and the server.

So in the description of the server above, it says that it "processes" the request to produce a response. The code that does this is known as a responder. There is only one responder per HTTP server. It receives requests and it outputs responses.

A responder is an object implementing a method on a generic word:

GENERIC: call-responder ( path responder -- response )

When this word is called, the request is stored in a request variable.

Here is a simple responder:

TUPLE: simple-responder ;

C: <simple-responder> simple-responder

M: simple-responder call-responder
    2drop
    <response>
        200 >>code
        "Document follows" >>message
        "text/plain" set-content-type
        "Hello world" >>body ;

Using a higher-level feature such as HTTP actions, it is possible to avoid much of this boilerplate, but let's just stick to the lowest layer for now.

If we manually call write-response on the result of the above construction, we get what we expect:

HTTP/1.1 200 Document follows
connection: close
content-type: text/plain
date: Thu, 13 Mar 2008 01:30:43 GMT

This is what the HTTP server would send given a HEAD request. Given a GET request, it calls write-response followed by write-response-body; the looks at the body slot; if it is a string, it writes it to the client, if it is a quotation, it calls it, and the quotation is free to write any output it choses.

We can create an instance of this responder, store it in the main-responder variable, and start the HTTP server:

<simple-responder> main-responder set-global
8080 httpd

Now, visiting http://localhost:8080/ produces a "Hello world" message.

This is how you start an HTTP server that serves a single web application. A more useful example is a server which simply serves static content:

"/var/www/" <static> main-responder set
8080 httpd

However, what if you wanted to have several web apps per server? Or a server that serves static content as well as web apps? Or what if your site only ran a single application conceptually, but you wanted to structure it from multiple responders? As I've described the server design above, it is not clear how this is possible. However, in fact this problem is solved in a very elegant way. A responder can call other responders: so the fact that the HTTP server can only ever have one main responder is not a limitation at all.

Dispatchers

A dispatcher is a responder which looks at the first component of a path name, chops it off, and calls one of several possible child responders depending on that path name. For example, we can create a dispatcher which has our hello world app, together with static content, as children:

<dispatcher>
    <hello-world> "hello" add-responder
    "/var/www/" <static> "data" add-responder
main-responder set
8080 httpd

Now, if we visit http://localhost:8080/hello/, we get the "Hello world" message, and if we visit http://localhost:8080/data/ we get our static content. For example, if we have a file /var/www/widgets.html on our file system, then visiting http://localhost:8080/data/widgets.html will serve that file.

What if we visit http://localhost:8080/? We get a 404 not found response, because the dispatcher doesn't know what to do in this case. However, we can give it a default responder; for example, let's change the above code so that the static content is the default:

<dispatcher>
    <hello-world> "hello" add-responder
    "/var/www/" <static> >>default
main-responder set
8080 httpd

Now, visiting http://localhost:8080/hello, we get our simple responder, and if we visit http://localhost:8080/widgets.html or any other path, we get the static data. Effectively, we've "mounted" the hello world web app in the hello/ directory.

What's next?

In the second installment, I will talk about virtual hosting, session management, and cookies, and give some more complex examples of responders. Virtual hosting is a work in progress; the design is a lot more flexible than it was before. Cookies and session management and pretty much done, but this post is already getting rather long so I will describe this next time.
In the third installment, I will talk about web actions and form validation.
In the fourth installment, I will discuss database access and CRUD actions.

Tuesday, March 11, 2008

Faster serialization

I figured out a nice trick that sped up Factor's serialization library. Because serialization is required to preserve circular and shared structure, it would previously store all objects serialized so far in a sequence. When a new object was encountered, it would scan the sequence for an object eq? to the one being serialized. This made serialization quadratic in the number of objects being serialized, which is unacceptable. While Factor's hashtables always check for equality using = and not eq?, I was able to simulate eq? hashtables by defining a new data type.

The new type is a tuple which holds a reference to a single object:

TUPLE: id obj ;

C: <id> id

The hashcode of an id is the hashcode of the underlying object:

M: id hashcode* obj>> hashcode* ;

The equality test, however, checks if the underlying objects are eq?:

M: id equal? over id? [ [ obj>> ] 2apply eq? ] [ 2drop f ] if ;

That is, two distinct instances of id are equal if their underlying objects are identical (got it?).

Now, we just have to replace two words to use a hashtable with id keys instead of a linear search of a sequence:

: add-object ( obj -- )
    #! Add an object to the sequence of already serialized
    #! objects.
    serialized get [ assoc-size swap  ] keep set-at ;

: object-id ( obj -- id )
    #! Return the id of an already serialized object 
     serialized get at ;

True id hashtables will be added at some point in the future, but for now this will suffice.

Saturday, March 08, 2008

Forth Foundation Library

It seems Factor is not the only stack-based language trying to build up a rich library. The Forth Foundation Library includes a regexp engine, various cryptographic hashes, an XML parser, binary trees, and so on. Looks pretty nice.

Friday, March 07, 2008

New-style slots in io.launcher and smtp

Yesterday I refactored the io.launcher and smtp libraries to use Eduardo's new-slots and the results were quite nice.

Prior to this, words such as run-process would take either a string, an array of strings, or an assoc. The latter was used to specify more advanced launch parameters, such as I/O redirection. Here is a typical example of the old way:

{
    { +command+ "make clean install" }
    { +stdout+ "../build-log" }
    { +stderr+ +stdout+ }
} run-process

This looks nice and neat, however, if some of the values are computed, then you cannot use a literal assoc, you have to construct one. Suppose we want to add a 5 minute timeout. Here is one way:

[
    "make clean install" +command+ set
    "../build-log" +stdout+ set
   +stdout+ +stderr+ set
    5 minutes +timeout+ set
] { } make run-process

Having to change all of the code just because one parameter becomes computed is not so nice. The other alternative is to use something like bake:

{
    { +command+ "make clean install" }
    { +stdout+ "../build-log" }
    { +stderr+ +stdout+ }
    { +timeout+ %[ 5 minutes ] }
} bake run-process

This is better but now you have bake, %[ which don't pertain to your problem domain, plus some unnecessary Lisp-style nesting. And what if you wanted to build up a descriptor in one word, but then have another word which amended it further? You'd have to bake two assocs and use an assoc word such as 'union'. Bake is nice in other contexts but it is the wrong solution here.

Now suppose we used a tuple of process launch parameters:

<process>
    "make clean install" over set-process-command
    "../build-log" over set-process-stdout
    +stdout+ over set-process-stderr
    5 minutes over set-process-timeout
run-process

This is more composable; you can write a word which takes a descriptor, and sets some slots in it. It is also relatively easy to have both literal launch parameters and computed ones, and adding a computed parameter to an all-literal descriptor doesn't require introducing make-assoc or bake. However, now we've introduced some stack shuffles and the accessor names are kind of long.

Enter new-slots:

<process>
    "make clean install" >>command
    "../build-log" >>stdout
    +stdout+ >>stderr
    5 minutes >>timeout
run-process

This is about as ideal as it gets. No unnecessary nesting, no stack shuffling, and the only words that appear directly pertain to your problem domain.

What about the case where a launch parameter comes off the stack? Suppose the command name is an input and everything else is computed on the spot. Here is the old way:

[
    +command+ set
    "../build-log" +stdout+ set
   +stdout+ +stderr+ set
    5 minutes +timeout+ set
] { } make run-process

The new way introduces a swap, but there is still a net reduction in complexity:

<process>
    swap >>command
    "../build-log" >>stdout
    +stdout+ >>stderr
    5 minutes >>timeout

Now suppose we have a make target name on the stack and we want to run make with that target. Here is the old way:

[
    "make" swap 2array +command+ set
    "../build-log" +stdout+ set
   +stdout+ +stderr+ set
    5 minutes +timeout+ set
] { } make run-process

With new-slots:

<process>
    "make" rot 2array >>command
    "../build-log" >>stdout
    +stdout+ >>stderr
    5 minutes >>timeout

With bake and new-slots:

<process>
    swap { "make" , } bake >>command
    "../build-log" >>stdout
    +stdout+ >>stderr
    5 minutes >>timeout

I find the latter preferrable to the first two.

The situation with smtp is a little different. Previously, I had a send-simple-message word which took a body, subject, from and to on the stack:

"Blahblah" "Hi" { "alice@aol.com" "joe@aol.com" } "bob@aol.com" send-simple-message

Clearly, this doesn't scale as additional parameters are added; header lines, attachments, etc. The new code uses new-slots and it is a lot more aesthetically pleasing:

<email>
    "Blahblah" >>body
    "Hi" >>subject
    { "alice@aol.com" "joe@aol.com" } >>to
    "bob@aol.com" >>from
send

Not only does it read better but also it is easy to add additional fields such as CC, BCC, attachments, S/MIME support, etc. (Well, easy enough to add the fields; actually implementing some of these is another matter altogether...)

New-slots is going into the core very soon now. Bake will need to be worked on some more; then it will go in the core and replace usages of make there. Make will go into a library in extra and be phased out along with old slots.

Saturday, March 01, 2008

New convention for unit tests

Until now, unit test files would define words in the temporary vocabulary. This made it problematic to run these words after the unit tests were done -- sometimes your tests failed, and to debug the problem you want to run some of these words, however the unit test code would forget everything in the temporary vocabulary, necessitating an annoying workflow where to access these words the test file had to be loaded with run-file first. I finally got fed up with this so I changed the convention: test files now define words in vocab.tests, not temporary, and these vocabularies are not forgotten after tests run. I've updated all tests in the repository; new code by contributors should no longer use the temporary vocab.