Factor/ifte

{[

Joy has an 'ifte' combinator. Here's how Manfred von Thun describes it:

The ifte combinator expects three quoted programs on the stack, an

if-part, a then-part and an else-part, in that order, with the

else-part on top. The ifte combinator removes and saves the three

quotations and then performs the following on the remainder of the

stack: It executes the if-part which should leave a truth value on top

of the stack. That truth value is saved and the stack is restored to

what it was before the execution of the if-part. Then, if the saved

truth value was true, the ifte combinator executes the then-part,

otherwise it executes the else-part.

(from "An informal tutorial on Joy")

'ifte' is what we call a "smart combinator" because it's behaviour is

dependent upon the effect of an input quotation. Smart combinators

are limited in that they should only be used with input quotations

that Factor can infer the effect of.

We've had an 'ifte' in 'combinators.lib' for a while but it doesn't

restore the stack correctly in all cases.

Given a quotation QUOT that will function as the predicate, the number

of values to preserve is:

QUOT infer in>>

I'll call that A.

A tells us the span of the stack that QUOT affects. However,

'ifte' doesn't require that QUOT actually consume A number of

items. As long as QUOT leaves a value on the stack that will serve as

the boolean, 'ifte' is happy.

So we need to pass the top A values on the stack to the branches of

ifte. But after QUOT is called, we need to "clean up" after it so we

get back the restored stack state.

Some examples of restoring the stack:

STACK / QUOT STACK / RESULT

10 [ even? ] 10 t

10 20 [ + even? ] 10 20 t

10 20 30 [ rot even? ] 10 20 30 t

In the first two cases, the QUOT actually consumes A items. In the

third case, A is three but QUOT only consumes one.

So, we know that we must keep A items. The 'nkeep' combinator is

close to what we need for this part.

My solution looks like this:

MACRO: ifte ( test then else -- ) [ifte] ;

:: [ifte] ( TEST THEN ELSE -- ) TEST [preserving] '[ @ THEN ELSE if ] ;

Nice. It's a straight forward expansion into an 'if'.

[preserving] is doing all the magic:

: [preserving] ( quot -- quot ) [predicating] [keeping] ;

This rewrites the quot twice. First to turn it into a pure

"predicating" quotation. By this I mean it does consume all A items

and only leaves one value on the stack. Then it rewrites it to be a

"keeping" quotation, such that it preserves A items on the stack,

leaving the result at the top.

Here are those last two words:

: [predicating] ( quot -- pred ) [ ] [ infer out>> 1 - ] bi '[ @ nnip ] ;

: [keeping] ( quot -- quot ) [ ] [ infer in>> ] bi '[ nkeep ] ;

In [predicating], there's the expression:

infer out>> 1 -

followed later by an 'nnip'. That's basically saying "I see you're

leaving N values on the stack. I want you to be a pure predicate so I'm

going to nip N-1 of those values".

nkeep is just like nkeep except that the kept values come after the

result of calling the quotation.

An 'ifte' vocabulary is available here:

http://paste.factorcode.org/paste?id=113

]}

This revision created on Fri, 7 Nov 2008 13:43:58 by dharmatech