Sunday, November 25, 2007

Factor 0.91 benchmarks

I ran the benchmark suite against Factor 0.91. Compared to last time, there are some nice improvements in bootstrap1, iteration, reverse-complement and ring. There are a few regressions too; I've highlighted those in red and will be investigating them.
Benchmark Run time (ms)
bootstrap1 11452
bootstrap2 575675
continuations 389
dispatch1 3660
dispatch2 4399
dispatch3 5167
dispatch4 8892
empty-loop 496
fib1 238
fib2 907
fib3 1438
fib4 4962
fib5 2015
iteration 13864
mandel 4806
nsieve 2428
nsieve-bits 69021
partial-sums 31281
raytracer 26893
recursive 45196
reverse-complement 12641
ring 8051
sort 2061
spectral-norm 35304
typecheck1 5136
typecheck2 5624
typecheck3 5632
typecheck4 4049

A year and a half ago, reverse-complement was clocking in at 170 seconds. It's 14 times faster now!

Saturday, November 24, 2007

The process launcher, parser combinators, and /bin/sh

The io.launcher vocabulary lets you specify a command line in one of two ways:
"foo bar baz" run-process
{ "foo" "bar" "baz" } run-process

Both have their advantages and disadvantages. The first one is more amenable to user input, the second one is safer and more predictable if some of the arguments are themselves user input and may contain special characters.

Until now, the first form was implemented on Unix by passing the command line to /bin/sh. The shell would take care of tokenizing the command line, parsing quotes and backslashes, etc. This is problematic, for two reasons. The practical reason is that the shell does a hell of a lot of stuff (expanding env vars, tokenizing on $IFS which may change, etc) which is hard to control and predict, hence the regular security advisories we see regarding programs which use system() carelessly. The second reason is philosophical -- Factor should not depend on an external tool for such a trivial task (tokenizing arguments).

Java side-steps the whole issue in a lame way. The Java API also supports launching a process specified as a command line string, or as an array of strings. But their logic for tokenizing a command line string is simplistic, they just split the input on spaces. No quoting or escaping allowed. In Factor, this could be achieved just by calling " " split, but it is lame.

This is Factor, Factor is awesome, and parsing a simple command line string while respecting quoting and escaping should be simple. And it turns out that it is! I haven't used Chris Double's parser-combinators library for anything serious up til now, and I was (pleasantly) surprised at how simple it was. Your grammar really does map pretty much directly to parser combinators, and the clever implementation of the built-in combinators means you pretty much get a parse tree for free, with very little processing of the parse result. Chris did a wonderful job and of course the clever people in the Haskell community who invented parser combinators deserve a lot of praise too.

The command line grammar begins by defining a parser for escaped characters, and another parser for a sequence of escaped and unescaped characters. Note that the former uses &>, so that an escaped character parser result is the actual character itself, without the backslash:

LAZY: 'escaped-char' "\\" token any-char-parser &> ;

LAZY: 'chars' 'escaped-char' any-char-parser <|> <*> ;

Next up, we use the surrounded-by parser combinator to build parsers for quoted strings:
LAZY: 'quoted-1' 'chars' "\"" "\"" surrounded-by ;

LAZY: 'quoted-2' 'chars' "'" "'" surrounded-by ;

The parse result of a surrounded by parser is the result of the parser combinator in the body, so the quotes are stripped off for us automatically. Neat.

Next up, we have a parser for non-whitespace characters used in unquoted tokens:
LAZY: 'non-space-char'
'escaped-char' [ CHAR: \s = not ] satisfy <|> ;

Since we can still escape a space in a unquoted token, we re-use our escaped char parser here.
Now a parser for unquoted tokens:
LAZY: 'unquoted' 'non-space-char' <+> ;

Finally a parser for any type of argument, whether it be quoted or unquoted; we use <@ here to convert the parse result to a string (the result of <*> is an array of parsed elements; the elements are characters because of how we defined our character parsers; we turn this array of characters into a string.)
LAZY: 'argument'
'quoted-1' 'quoted-2' 'unquoted' <|> <|>
[ >string ] <@ ;

Now we have our top-level parser. We define it in a memoized word, so that it is only ever constructed once and the same instance is reused:
MEMO: 'arguments' ( -- parser )
'argument' " " token <+> list-of ;

Finally a word which uses this parser:
: tokenize-command ( command -- arguments )
'arguments' parse-1 ;

The parse-1 word is a utility word which outputs the parse result from the first match (the parse word outputs a lazy list of matches).

Here's an example:
"hello 'world how are you' "\\"today\\"" blah\\ blah" tokenize-command .
{ "hello" "world how are you" "\"today\"" "blah blah" }

The entire parser is 19 lines of code, or 8 lines if we remove blank lines and squish everything together. It reads easily because it is essentially the BNF grammar we're parsing here, just written in a postfix style with some additional fluff. There's no need to use a parser generator or any kind of external tool in the build process; this is just Factor code. Sure beats calling /bin/sh.

Friday, November 23, 2007

Adventures with Cygwin on 64-bit Windows

Warning: this is a rant. If you don't like rants, skip this post and look at my previous post, which is a lot more substantial than this one.

So at FactorCon 2007, Doug and I experimented with getting Factor going on 64-bit Windows XP. The Factor compiler and FFI is ready to go, and it should be an easy port in theory, but the only problem is that we have to compile the VM (which is written in C). And this isn't trivial at all. Here is what we found:
  • First of all, Factor compiled with 32-bit Cygwin runs in 32-bit mode under "WoW emulation", however certain features don't work, for example UDP support. This is a bug in Windows and there's nothing we can do; a C testcase demonstrates the problem quite clearly. The problem is not present in 64-bit mode.
  • Cygwin also ships with broken implementations of certain C runtime functions, such as _osf_openhandle(). We have a testcase which fails in Cygwin and works in Visual Studio (I reported the bug to the Cygwin guys.)
  • 32-bit Mingw is highly unstable on 64-bit Windows -- you need an obscure workaround just to get it to run at all -- however it does not suffer from the _osf_openhandle() bug. The UDP sockets problem is still there since its a Windows bug, not specific to Cygwin or Factor.
  • There's a 64-bit Mingw port in progress, however we were unable to get it to work. Using optimization flags crashes gcc; without optimization flags gcc produces a non-functioning binary, and PE Explorer claims this binary is corrupt.
  • There are no plans at all to port Cygwin to 64-bit Windows.

So the executive summary is that we're pretty much fucked when it comes to 64-bit Windows support, and all because I made a serious miscalculation and used GNU C extensions in the VM. I should have stuck with semi-portable C and then we could use Visual Studio...

If we could compile the Factor VM as a 64-bit binary, then porting the rest of Factor would be trivial; after all, we support Windows, and we support AMD64, and we're awesome programmers. However, the GNU hippies fucked up once again and failed to deliver -- AMD64 chips have been out since 2004 and Windows XP x64 edition was released at the start of 2005, but at the end of 2007, more than two years later, there is still no stable 64-bit GNU toolchain available for Windows.

I realize that this is all just people's hobbies, they work on Cygwin/Mingw in their spare time, I shouldn't expect timely releases or stability of any sort, etc. But hell, if you GNU people want "world domination", if you want us to stop using Mac OS X, Windows and other commercial software, if you want market share greater than 0.00001%, if you want people to take GNU and Linux seriously, get to work and fix your shit. Thank you.

Deploying stand-alone applications on Windows

Everybody loves Microsoft and Windows, and Steve Ballmer is probably the greatest man alive, so for me, a solid Windows port of Factor is a high priority.

The major blocker to getting the deploy tool working on Windows was the lack of <process-stream> support. Doug had some incomplete code written for this earlier. By looking at his code together with the Twisted Python implementation of the same feature, I was able to get it working. The trick is that Windows only supports blocking reads/writes on anonymous pipes, so one has to use named pipes (and resort to stupid tricks like naming them using a random number/milliseconds to ensure uniqueness), which do support non-blocking I/O via completion ports.

So, here is an example. We wish to deploy the Tetris demo, so we type this in the listener:
"tetris" deploy-tool

This opens a window:

Now, we click "Deploy". This spawns a new Factor process which bootstraps and tree shakes a tetris image, dumping output into the current listener window (this is where <process-stream> comes in). After a few minutes, we get a "Tetris" directory which has everything we need:

Note the FreeType files and DLLs; they will go away as soon as we ditch FreeType and start using native font rendering APIs (real soon now), so in the future all you'll have is the executable, the image file, and factor-nt.dll. Double-clicking the executable runs the program:

Now the raptor icon is nice and all, but eventually we'll also have a way to specify custom icons for deployment, on both Mac OS X and Windows.

The completion of the Windows <process-stream> implementation marks a milestone in Factor development. The Windows I/O subsystem has now reached feature parity with the Unix side. This means Factor now offers high-level, cross-platform APIs for the following tasks:
  • Creating, renaming, copying, deleting files and directories
  • Reading and writing files sequentially
  • Memory mapped files
  • TCP/IP sockets
  • UDP/IP sockets
  • IPv4 and IPv6 addressing, host name lookups
  • Launching processes
  • Launching processes with redirected I/O

Where possible, all I/O is non-blocking (the user-level API is presented as a blocking stream API, however under the hood Factor's co-operative thread scheduler yields between threads while waiting on I/O).

On Windows CE, the I/O support is spotty. Windows CE doesn't support pipes or non-blocking I/O, so certain features are not implemented, but we try the best we can.

Factor has an awesome FFI and now it has an awesome I/O library, which will still gain additional features in the future, for example Doug is already working on Windows directory change notification and I'll be doing the Unix side of that soon. A small step for Factor, a giant leap for stack languages!

Saturday, November 17, 2007

Converting a file from big endian to little endian (or vice versa)

Suppose you have a file of 4-byte cells and you wish to reverse each cell. What do you do? Fire up Factor, the latest code from git at least!
USING: io.mmap io.files math.functions splitting sequences ;

: byte-swap ( file -- )
dup file-length 4 align [
4 <sliced-groups> [ reverse-here ] each
] with-mapped-file ;

Given a sequence, 4 <groups> creates a virtual sequence of 4-element slices of the underlying sequence. We apply reverse-here to each slice. Since slices share storage with their underlying sequene, this has the effect of reversing a portion of the underlying sequence in-place. But here, the underlying sequence is a memory-mapped file's bytes.

The interesting thing here is that we're composing two orthogonal features: memory mapped files, and sequence operations.

Also note that error handling is at least half way there: if an error is thrown for whatever reason, the memory mapping is closed and cleaned up for you.

I just got mmap working on Windows CE, too. So the above code will work any supported platform.

Monday, November 12, 2007

CGI support in the Factor HTTP server

Now that io.launcher has the ability to pass environment variables to child processes, I was able to implement CGI support very easily. I realize CGI is slow and obsolete, however it is still handy sometimes, as a lowest common denominator for integrating third-party web apps. I intend to use it to run gitweb.cgi (a git repo browsing tool written in Perl) on

The CGI support is loaded by default when one does USE: http.server, however to enable it the cgi-root variable must be set to a directory containing CGI scripts. This variable can either be set globally, per vhost, or per responder.

Files whose extension is .cgi are executed and the results are served to the client; other files are served literally.

The implementation of the CGI responder is quite straightforward. First, we have some boilerplate:
! Copyright (C) 2007 Slava Pestov.
! See for BSD license.
USING: namespaces kernel assocs io.files combinators
arrays io.launcher io http.server http.server.responders
webapps.file sequences strings ;
IN: webapps.cgi

Now, we define the configurable variable:
SYMBOL: cgi-root

Next, we have a word to build the associative mapping of environment variables which we pass to the child process. The HTTP server calls responders after storing various values pertaining to the request in variables; our task here is to convert the HTTP server's representation of this data into a form which is expected by the CGI script. This word breaks the "keep words short" rule, but its definition is so straightforward that it is readable regardless, and breaking it up into smaller words would probably not help:
: post? "method" get "post" = ;

: cgi-variables ( name -- assoc )

"Factor " version append "SERVER_SOFTWARE" set
host "SERVER_NAME" set
"" "SERVER_PORT" set
"request" get "PATH_INFO" set
"request" get "PATH_TRANSLATED" set
"" "REMOTE_HOST" set
"" "REMOTE_ADDR" set
"" "AUTH_TYPE" set
"" "REMOTE_USER" set

"method" get >upper "REQUEST_METHOD" set
"raw-query" get "QUERY_STRING" set

"User-Agent" header-param "HTTP_USER_AGENT" set
"Accept" header-param "HTTP_ACCEPT" set

post? [
"Content-Type" header-param "CONTENT_TYPE" set
"raw-response" get length "CONTENT_LENGTH" set
] when
] H{ } make-assoc ;

Next, we have a word which constructs a launch descriptor for the CGI script. See my post from earlier today about io.launcher improvements to learn about descriptors, which are a new feature. This word uses the cgi-root variable together with the above cgi-variables word:
: cgi-descriptor ( name -- desc )
cgi-root get over path+ 1array +arguments+ set
cgi-variables +environment+ set
] H{ } make-assoc ;

Now, the word which does the hard work. It spawns the CGI script, sends it the user input if the request type is a POST, then copies output to the socket:
: (do-cgi) ( name -- )
"200 CGI output follows" response
stdio get swap cgi-descriptor &t;process-stream> [
post? [
"raw-response" get
stream-write stream-flush
] when
stdio get swap (stream-copy)
] with-stream ;

Files whose extension is not .cgi are simply served to the client; we have a little word which fakes a file responder:
: serve-regular-file ( -- )
cgi-root get "doc-root" [ file-responder ] with-variable ;

Now, the main dispatcher. First we weed out invalid inputs, pass files which don't end with .cgi to serve-regular-file, and send everything else to (do-cgi):
: do-cgi ( name -- )
{ [ dup ".cgi" tail? not ] [ drop serve-regular-file ] }
{ [ dup empty? ] [ "403 forbidden" httpd-error ] }
{ [ cgi-root get not ] [ "404 cgi-root not set" httpd-error ] }
{ [ ".." over subseq? ] [ "403 forbidden" httpd-error ] }
{ [ t ] [ (do-cgi) ] }
} cond ;

That's it as far as code is concerned. All that's left is to register a responder which calls do-cgi:
global [
"cgi" [ "argument" get do-cgi ] add-simple-responder
] bind

Improved process launcher

The io.launcher vocabulary now supports passing environment variables to the child process.

Launching processes is a complex and inherently OS-specific task. For example, until version 1.5, Java had a bunch of methods in the Runtime class for this, each one taking a different set of arguments:
Process exec(String command)
Process exec(String[] cmdarray)
Process exec(String[] cmdarray, String[] envp)
Process exec(String[] cmdarray, String[] envp, File dir)
Process exec(String command, String[] envp)
Process exec(String command, String[] envp, File dir)

The fundamental limitation here was that it would always launch processes with stdin/stdout rebound to a new pipe; so there was no easy way to launch the process to read/write the JVM's stdin/stdout file descriptors, you had to spawn two threads to copy streams. In 1.5, they added a new ProcessBuilder class, but it doesn't seem to offer any new functionality except for merging stdout with stderr. It still always opens pipes.

The approach I decided to take in Factor is similar to the ProcessBuilder approach, but more lightweight. The run-process word takes one of the following types:
  • A string -- in which case it is passed to the system shell as a single command line
  • A sequence of strings -- which becomes the command line itself
  • An association -- a "process descriptor", containing keys from the below set.

The latter is the most general. The allowed keys are all symbols in the io.launcher vocabulary:
  • +command+ -- the command to spawn, a string, or f
  • +arguments+ -- the command to spawn, a sequence of strings, or f. Only one of +command+ and +arguments+ can be specified.
  • +detached+ -- t or f. If t, run-process won't wait for completion.
  • +environment+ - an assoc of additional environment variables to pass along.
  • +environment-mode+ - one of prepend-environment, append-environment, or replace-environment. This value controls the function used to combine the current environment with the value of +environment+ before passing it to the child process.

While run-process spawns a process which inherits the current one's stdin/stdout, <process-stream> spawns a process reading and writing on a pipe.

Idiomatic usage of run-process uses make-assoc to build the assoc:
{ "ls" "/etc" } +arguments+ set
H{ { "PATH" "/bin:/sbin" } } +environment+ set
] H{ } make-assoc run-process

I'm happy with the new interface. With two words it achieves more than Java's process launcher API, which consists of a number of methods together with a class.

Not only is the interface simple but so is the implementation.

The run-process first converts strings and arrays into full-fledged descriptors, then calls run-process* which is an OS-specific hook.

In the implementation of this hook, the fact that any assoc can be treated as a dynamically scoped namespace really into play. The io.launcher implementation has a pair of words:
: default-descriptor
{ +command+ f }
{ +arguments+ f }
{ +detached+ f }
{ +environment+ H{ } }
{ +environment-mode+ append-environment }
} ;

: with-descriptor ( desc quot -- )
default-descriptor [ >r clone r> bind ] bind ; inline

Passing a descriptor and a quotation to with-descriptor calls it in a scope where the various +foo+ keys can be read, assuming their default values if they're not explicitly set in the descriptor.

So, if we look at the Unix implementation for example,
M: unix-io run-process* ( desc -- )
+detached+ get [
] [
spawn-process wait-for-process
] if
] with-descriptor ;

It calls various words, all of which simply use get to read a dynamically scoped variable. These are resolved in the namespace set up by with-descriptor. For example, there is a word
: get-environment ( -- env )
+environment+ get
+environment-mode+ get {
{ prepend-environment [ os-envs union ] }
{ append-environment [ os-envs swap union ] }
{ replace-environment [ ] }
} case ;

It retrieves the environment set by the user, together with the environment of the current process, and composes them according to the function in +environment-mode+. There is no need to pass anything around on the stack; any word can call get-environment from inside a with-descriptor.

Notice that constructing a namespace with make-assoc, and then passing it to a word which binds to this namespace and builds some kind of object, is similar to the "builder design pattern" in OOP. However, it is simpler. Instead of defining a new data type with methods, we essentially just construct a namespace then run code in this namespace.

Windows CE native I/O

I fixed some bitrot in Doug's Windows CE I/O code, and added support for console I/O, and the <file-appender> word.

Recall that Factor uses ANSI C I/O functions (fread, fwrite, on FILE* pointers...) unless there is an OS-specific I/O subsystem implemented.

The ANSI C I/O functions don't perform any buffering with the (already slow) Windows CE console, which results in very slow output. Having console I/O go through a buffered I/O layer which uses native Windows APIs has improved performance considerably. Words such as see no longer make you wait and watch as individual words are printed out.

Also, a native I/O layer means networking (TCP and UDP) may be used. There are other, more minor features as well (creating directories, removing files, etc).

Unfortunately, we don't have non-blocking I/O on Windows CE, because there is no general I/O multiplexer like IO completion ports on Windows or select() on Unix. Console and file I/O is always blocking, and network I/O can go through a Winsock-only multiplexer.

In the future, I'll write a small piece of C code which is linked with the Factor runtime. This code will start a network multiplexer running in its own thread; the thread will post events to an event queue. Then, the Factor event loop can use WaitForMultipleObjects() to multiplex over the I/O event queue and the UI event queue.

However, for now, I'm done with the CE port. There is still a bug in the ARM backend preventing Chris Double from bootstrapping Factor on his Nokia n800; I'm going to look into this next. In Factor 0.92, I will implement mark/sweep/compact garbage collection for the oldest generation, which will reduce memory usage on Windows CE, and I will also look into getting the UI running there.

Factor will be the premier high-level language for Windows CE development!

Network clipboard tool written in Factor

So lately I've been going back and forth between two machines, my Mac and my Windows box. Getting small chunks of text between the machines (stuff other than what goes in the git repository) is a bit inconvenient. So I cooked up a tool to synchronize their clipboards. It is very rough, but you can use it as follows:
  • network-clipboard-tool - opens the tool, showing a list of remote hosts. Each host is a presentation.
  • "foo" add-network-clipboard - adds a remote host to the host list.
  • Clicking Clipboard Server in the window allows other machines to add this host to their network clipboard host list.
  • Right-clicking on a host presentation and invoking Send Clipboard sends the current machine's clipboard to the remote host.
  • Right-clicking on a host presentation and invoking Receive Clipboard sets the current machine's clipboard to that of the remote host.

Since bidirectional transfer is supported, only one of the two machines needs to have a server running, but for convenience I run it on both. This is what it looks like, after right-clicking on the second host in the list:

The code is reasonably compact while still demonstrating TCP/IP networking and a number of UI features, such as models, operations, presentations, and commands. It has several limitations:
  • Only supports Windows and Mac, not X11, since on X11 the UI uses a different set of words for clipboard access.
  • There's no graphical way of editing the host list
  • Perhaps even better, support for something like Apple's ZeroConf
  • There is no security, but if you use it on a private LAN there is no problem

The code is in the repository now, in extra/network-clipboard. To try it out, just grab the latest Factor and do
"network-clipboard" run

The program begins with the usual boilerplate:
! Copyright (C) 2007 Slava Pestov.
! See for BSD license.
USING: io.server io.sockets io strings parser byte-arrays
namespaces ui.clipboards ui.gadgets.panes ui.gadgets.scrollers
ui.gadgets.buttons ui.gadgets.tracks ui.gadgets ui.operations
ui.commands ui kernel splitting combinators continuations
sequences io.streams.duplex models ;
IN: network-clipboard

A utility word to slurp in the current stream. It differs from the contents word in the io vocabulary in that it operates on stdio and doesn't close it at the end:
: contents ( -- str )
[ 1024 read dup ] [ ] [ drop ] unfold concat ;

Now we can implement a very simple network protocol for getting and setting clipboard contents:
: get-request
clipboard get clipboard-contents write ;

: set-request
contents clipboard get set-clipboard-contents ;

We use the with-server combinator, which sets up a simple multi-threaded accept loop with logging:
: clipboard-port 4444 ;

: clipboard-server ( -- )
clipboard-port internet-server "clip-server" [
readln {
{ "GET" [ get-request ] }
{ "SET" [ set-request ] }
} case
] with-server ;

We declare that this word is an UI command which is nullary (does not operate on a target option) and wishes to display output in a listener:
\ clipboard-server H{
{ +nullary+ t }
{ +listener+ t }
} define-command

A combinator to make a network connection:
: with-client ( addrspec quot -- )
>r <client> r> with-stream ; inline

A host type and a simple protocol where either a string or a host can answer its name:
TUPLE: host name ;

C: <host> host

M: string host-name ;

Sending the current clipboard to another host:
: send-text ( text host -- )
clipboard-port <inet4> [ write ] with-client ;

: send-clipboard ( host -- )
"SET\n" clipboard get clipboard-contents append swap send-text ;

We define it as an UI operation on hosts:
[ host? ] \ send-clipboard H{ } define-operation

Requesting another host's clipboard:
: ask-text ( text host -- )
clipboard-port <inet4>
[ write flush contents ] with-client ;

: receive-clipboard ( host -- )
"GET\n" swap ask-text
clipboard get set-clipboard-contents ;

[ host? ] \ receive-clipboard H{ } define-operation

Printing host presentations:
: hosts. ( seq -- )
"Hosts:" print
[ dup <host> write-object nl ] each ;

The UI tool class:
TUPLE: network-clipboard-tool ;

We define a command map for the toolbar, containing a single command:
\ network-clipboard-tool "toolbar" f {
{ f clipboard-server }
} define-command-map

The constructor creates a new network clipboard tool instance, adding a toolbar and a list of hosts there. It takes a model as an input:
: <network-clipboard-tool> ( model -- gadget )
\ network-clipboard-tool construct-empty [
[ hosts. ] <pane-control> <scroller> 1 track,
] { 0 1 } build-track ;

Now, a global model containing clipboard hosts and words to maintain it:
SYMBOL: network-clipboards

{ } <model> network-clipboards set-global

: set-network-clipboards ( seq -- )
network-clipboards get set-model ;

: add-network-clipboard ( host -- )
network-clipboards get [ swap add ] change-model ;

The final word -- it opens a window containing a new instance of this tool, with the global hosts model:
: network-clipboard-tool ( -- )
network-clipboards get
<network-clipboard-tool> "Network clipboard" open-window ;

Friday, November 09, 2007

Windows CE Pocket Console crash when writing long strings

This one was a pain to track down. If you write a string longer than about 1024 characters to the console, it just crashes your application. Test case:

#include <windows.h>

#define SIZE 1124

int main() {
HANDLE h = _fileno(_getstdfilex(1));
char buf[SIZE];
unsigned int count = 0;
printf("About to call WriteFile()\n");
int result = WriteFile(h,buf,SIZE,&count,NULL);
printf("WriteFile returns %d\n",result);

It never gets as far as "WriteFile returns...". If you change SIZE to something small like 124 it works.

Tuesday, November 06, 2007

Asus Eee PC

Looks like I've finally found a laptop that I can like: the Asus Eee PC. I'm not a fan of your average laptop; huge, heavy, runs through the battery in 3 hours, and cooks my balls. This "eee PC" only has a 7" screen, solid state disk, and (presumably) good battery life. I need to check out a few more reviews, but I'm probably going to buy one as soon as its released.

Lie algebra cohomology and cellphones

The Windows CE port is now working again. I can bootstrap and run tests successfully.
There are three main limitations:
  • Memory usage is high because of the copying collector. I will implement mark/sweep/compact collection for the oldest generation soon.
  • Network sockets and non-blocking I/O is not supported yet. I need to finish off Doug's code for that to work.
  • Factor must be run from inside the command prompt. The command prompt is awkward to install and use. Eventually I will port the Factor UI to Windows CE, in some cut-down form, and you'll get a nice listener instead.

You can download a binary package I threw together. It includes the command prompt, which might not be legal. To run it, you must follow these steps:
  • Unzip the ZIP file on your phone; root directory is the easiest place, otherwise you'll be typing full pathnames all the time (Windows CE doesn't have a "current directory" concept).
  • Run to install the console driver.
  • Open a registry editor such as TRE, and change the HKEY_LOCAL_MACHINE\Drivers\Console\OutputTo to the number 0.
  • Run cmd.exe.
  • In the command prompt, run factor-ce.
  • If you want, copy the core and extra directories from the Factor 0.91 sources, so that you can load external modules.

Annoyingly error-prone and long-winded? You bet! Soon you'll just be able to double-click on factor-ce.exe and it will start an UI listener, but for now the command prompt is as good as it gets.

To help with code input on the small dinky cellphone keyboard, I loaded some shortcut definitions. So now you can write u tools.time instead of USE: tools.time, etc.

Now, where does Lie algebra cohomology come into this? Well, I tried running extra/koszul on the phone, and it works fine. This is probably one of the least practical things I have ever done in my life, but it is a good way of testing whether a non-trivial program can run.

Playing around with extra/koszul and math stuff on the phone made me wonder. A modern cell phone has a much higher resolution (not to mention color) screen compared to a graphing calculator. Furthermore it has more RAM and a faster CPU. For example, the TI Voyage 200 is rather bulky and only has 188K of user-available RAM. My phone has more than 300 times that. The TI-89 is pretty much the same but with a different form factor. The calculators have an advantage when it comes to input, but perhaps predictive completion, handwriting recognition and the iPhone multitouch can narrow the gap there. A good CAS for cellphones and PDAs could cut into HP and TI's business...

Monday, November 05, 2007

Problems with flushing the instruction cache on Nokia n800

Chris Double noted that he was having trouble bootstrapping Factor on his Linux/ARM-based Nokia n800 Internet tablet. The crashes were random and we determined that it was due to the instruction cache not being flushed.

Factor was using the following code to flush the instruction cache:
syscall(__ARM_NR_cacheflush,start,start + len,0);

Now I wasn't checking the return value of this... silly me. After adding a check for the return value, Chris's tablet was returning "operation not permitted" from the above call.

After some Googling, I came across a post on the Parrot mailing list. Here, they were flushing the instruction cache by calling the system call directly, without using the syscall wrapper. I asked Chris to try their code, and it worked. Here it is:
 __asm__ __volatile__ (
"mov r0, %1\n"
"sub r1, %2, #1\n"
"mov r2, #0\n"
"swi " __sys1(__ARM_NR_cacheflush) "\n"
"mov %0, r0\n"
: "=r" (result)
: "r" (start), "r" (start + len)
: "r0","r1","r2");

Now, I'm pretty confused by this. In theory, the syscall function should do the same thing as the above. So either the syscall function in the version of libc shipped by Nokia is broken, or I'm stupid and missing something obvious.

Either way, it appears that Factor works on the n800 now.