Word renaming (part 2)

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

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

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

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

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

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

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

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

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

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

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

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!??

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

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

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

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

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

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

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

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.