Bluish Coder

Factor has a couple of different ways of automatically generating code. One of these is 'parsing words'. These are words that get run at parse time and can generate code that then gets compiled. I used this approach in the 8080 emulator to parse a domain specific language into Factor code:

INSTRUCTION: LD   SP,HL   ; opcode F9 cycles 06

Another approach is compiler transforms. These are similar to Common Lisp's define-compiler-macro construct.

They apply at compile time, producing code that gets run if the word is compiled. If the word is interpreted (ie. cannot be compiled) then the transformed code is not run.

Concatenative languages have combinators that can be used to run quotations in different ways on the stack. Words that have stack effects that vary depending on the words inputs are considered bad style and in Factor cannot be compiled. Instead they get run by the interpreter which leads to slower code. This leads to combinator words named like 'each-with', 'each-with2', 'each-with3', etc. Where the word performs the same basic action (iterate over a sequence calling a quotation on each item in it) but with a slight variation (the quotation also has access to 'n' number of items below the stack).

Most Factor combinators are implemented for up to 3 stack arguments since it's considered good style to not deal with more than 3. Sometimes though you need an 'each-with4' or 'map-with3' and they aren't available in the standard library. They can be difficult to implement correctly too.

Ideally I'd like a 'map-with' that takes the number on the stack. So these would be equivalent:

2 3 { 1 2 3 } [ * * ] map-with2
2 3 { 1 2 3 } [ * * ] 2 map-withn

Compiler transforms allows us to write code like this that transforms at compile time to code that can be compiled. By writing combinators in this form it allows efficient implementation of the common cases but allows falling back to the times when you need access to more stack items without having to write your own combinator.

For the example here I'm implementing 'dip'. This is a word from the Joy language that removes the topmost item on the stack, calls a quotation, then restores that item:

1 2 [ 5 + ] dip => 6 2
1 2 3 [ drop ] dip => 1 3

Joy has 'dip', 'dipd' and 'dipdd' where the latter two remove 2 and 3 items from the stack respectively, call the quotation and restore them.

Instead of writing separate implementations for these words I wrote one 'ndip' word which takes the number on the stack and does any number of 'dip' variants. So 'dip' is '1 ndip', dipd is '2 ndip' and dipdd is '3 ndip'. '4 ndip' and up is also catered for.

A simple implementation of 'ndip' won't compile as it has a variable stack effect depending on the inputs. To make a version that can compile I use compiler transforms. The first step is to write a word that generates the quotation that when called will do what 'ndip' should:

: [ndip] ( n -- quot )
  [ dup [ [ swap >r ] % ] times \ call , [ \ r> , ] times ] [ ] make ;

Some examples of calling this word and the results are:

1 [ndip] => [ swap >r call r> ]
2 [ndip] => [ swap >r swap >r call r> r> ]

'ndip' itself can be implemented using this as:

: ndip ( quot n -- ) [ndip] call ; inline

This will work but is inefficient as it generates a quotation on each call and cannot be compiled:

: foo ( a b -- b ) [ drop ] 1 ndip ;
1 2 foo => 2
\ foo try-compile
\ foo compiled? => f

Compiler transforms are used to make 'ndip' compile. This is the transform for 'ndip':

\ ndip 1 [ [ndip] ] define-transform

This causes the quotation produced by [ndip] to be generated at compile time and used for the call to 'ndip'. If for some reason it can't be compiled (due to the quotation being passed to 'ndip' using constructs like i/o or continuations) then it falls back to the interpreted 'ndip' definition. Now the code works compiled:

: foo ( a b -- b ) [ drop ] 1 ndip ;
1 2 foo => 2
\ foo try-compile
\ foo compiled? => t

For it to compile the number passed to 'ndip' must be a literal. If it is not, then the interpreted definition of 'ndip' is again used. This means 'ndip' works in all cases and compiles when it can. Now 'dip, 'dipd', etc can be defined in terms of 'ndip':

: dip 1 ndip ; inline
: dipd 2 ndip ; inline
: dipdd 3 ndip ; inline

Should the user ever need a dipddddddd then they can just do an '8 ndip' as needed - no need to write a special case combinator.

One advantage of compiler transforms over parsing words is that a 'see' on the the 'dip' word shows the 'ndip' call. If we generated the code using a parsing word then 'see' would see the result of the parsing words generated code.

Ideally I'd like to write 'each-with', 'map-with', etc in terms of comnbinators like this to make the one off cases of needing 'map-with6' or 'keep4' easy to deal with. They don't often come up but when they do it's hard to work around. They most commonly occur when dealing with non Factor code like Win32 api calls.

Many of these API calls have large numbers of input and output parameters which can be hard to deal with. Sometimes you can work around it with good word design but it makes sense to me to have the Factor compiler do the work of generating all the possible cases when I need them rather than me handing coding them.

I've put 'ndip' in 'libs/shuffle' and will add any others there.