Recursive combinator stack effects
Factor handbook » The language » Stack effect checking

Prev:Combinator stack effects
Next:Branch stack effects


Most combinators do not call themselves recursively directly; instead, they are implemented in terms of existing combinators, for example while, map, and the Compositional combinators. In these cases, the rules outlined in Combinator stack effects apply.

Combinators which are recursive require additional care. In addition to being declared inline, they must be declared recursive. There are three restrictions that only apply to combinators with this declaration:

Input quotation declaration
Input parameters which are quotations must be annotated as such in the stack effect. For example, the following will not infer:
: bad ( quot -- ) [ call ] keep bad ; inline recursive [ [ ] bad ] infer.
Cannot apply 'call' to a run-time computed value macro call

The following is correct:
: good ( quot: ( -- ) -- ) [ call ] keep good ; inline recursive [ [ ] good ] infer.
( -- )

The effect of the nested quotation itself is only present for documentation purposes; the mere presence of a nested effect is sufficient to mark that value as a quotation parameter.

Data flow restrictions
The stack checker does not trace data flow in two instances.

An inline recursive word cannot pass a quotation on the data stack through the recursive call. For example, the following will not infer:
: bad ( ? quot: ( ? -- ) -- ) 2dup [ not ] dip bad call ; inline recursive [ [ drop ] bad ] infer.
Cannot apply 'call' to a run-time computed value macro call

However a small change can be made:
: good ( ? quot: ( ? -- ) -- ) [ good ] 2keep [ not ] dip call ; inline recursive [ [ drop ] good ] infer.
( x -- )

An inline recursive word must have a fixed stack effect in its base case. The following will not infer:
: foo ( quot ? -- ) [ f foo ] [ call ] if ; inline [ [ 5 ] t foo ] infer.
The inline recursive word 'foo' must be declared recursive word foo