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:38 by dharmatech