▷ Home

Recursion Combinators

This notebook describes the genrec "general recursion" combinator and how to use it, and gives several specializations. The genrec combinator isn't the only way to make recursive functions in Joy, you can also use the x combinator with branch to create recursive functions. (Because definitions aren't checked for self-reference you can also define recursive functions directly in definitions, but this, I believe, should be considered bad form.)

General Recursive Functions

In Joy recursive functions can be defined using the genrec combinator which accepts four quoted programs:

[if] [then] [rec1] [rec2] genrec

This can be thought of as transforming into an "if..then..else" expression (using the ifte combinator) that contains a quoted copy of the original function in the "else" branch (here represented as F):

[if] [then] [rec1 [F] rec2] ifte

From "Recursion Theory and Joy" by Manfred von Thun:

The genrec combinator takes four program parameters in addition to whatever data parameters it needs. Fourth from the top is an if-part, followed by a then-part. If the if-part yields true, then the then-part is executed and the combinator terminates. The other two parameters are the rec1-part and the rec2-part. If the if-part yields false, the rec1-part is executed. Following that the four program parameters and the combinator are again pushed onto the stack bundled up in a quoted form. Then the rec2-part is executed, where it will find the bundled form. Typically it will then execute the bundled form, either with i or with app2, or some other combinator.

It's a fantastic paper and if you like this you should really go read that.

In order to describe and classify recursive functions we're going to make use of some fancy terminology from the Functional Programming folks.

Hylomorphism

A hylomorphism is a recursive function H that converts a value of type 𝔸 into a value of type ℂ by means of:

It may be helpful to see this function implemented in pseudocode (Python).

def hylomorphism(c, Q, P, G):

    def H(a):
        if P(a):
            return c
        b, aa = G(a)
        return Q(b, H(aa))

    return H

Note that during evaluation of H() the intermediate b values are stored in the Python call stack. This is what is meant by "call stack in the form of a cons list".

If this sounds a bit involved, an example may help. If you read the Developing a Program notebook you encountered something that is almost, but not quite, a hylomorphism already in the form of the program to answer the first problem of Project Euler: "Multiples of 3 and 5":

1000 range [multiple-of-3-or-5] filter sum

This program starts with a value of type 𝔸 (integer), namely 1000, it uses the range function (an anamorphism) to build a list of values of type 𝔹 (also integer), followed by a filter (I don't know what kind of -morphism that would be called), followed by the sum function (a catamorphism) that converts the list into a single value of type ℂ (also integer).

a hylomorphism [corresponds to] the composition of an anamorphism (which first builds a set of results; also known as 'unfolding') followed by a catamorphism (which then folds these results into a final return value)

~ hylomorphism

If we leave out the filter stage and the initial input value we have:

range sum

The difference between this composition of an anamorphism and a catamorphism and a proper hylomorphism is that the latter avoids construction of the intermediate list of values, instead it stores the intermediate values in the call stack. (Joy doesn't have a call stack, so storage of intermediate values would happen on the main stack or in the pending expression.)

Hylomorphism in Joy

We can define a combinator hylomorphism that will make a hylomorphism combinator H from constituent parts. Given a value of type 𝔸 the H function converts it into a value of type ℂ:

   a H
---------
    c

The combinator we want will accept the four parts on the stack, the three functions G, P, and Q, and the "base value" c. (The reason for the order of the parameters will become clear below) This gives us the initial form of H:

[P] c [G] [Q] hylomorphism

This function H is recursive, so to develop it we can start with the ifte form that contains a quoted copy of itself:

[if] [then] [rec1 [H] rec2] ifte

We already have the predicate P:

[P] [then] [rec1 [H] rec2] ifte

The then function discards a and replaces it with the base case value c:

[P] [pop c] [rec1 [H] rec2] ifte

Recursive Case

The else function rec1 [H] rec2 gets just the argument a on the stack:

a rec1 [H] rec2

and rec1 and rec2 will have G and Q in them somewhere.

The first thing to do is use the generator G which produces values b and a new a′:

    a G
----------
   a′ b

Then we recur with H on a′ using dip:

   a′ b [H] dip
------------------
     a′ H b
------------------
      c′ b

And run Q on the result:

   c′ b Q
------------
     c

So:

rec1 [H] rec2 == G [H] dip Q

Therefore:

rec1 == G

and

rec2 == dip Q

Plugging those back into the form above give us:

[P] [pop c] [G [H] dip Q] ifte

And converting to the genrec form:

[P] [pop c] [G] [dip Q] genrec

There we have our definition for H.

The derivation of the hylomorphism combinator is given in the appendix below.

Example: Finding Triangular Numbers

Knowing the form for H we can write the hylomorphic form of the composition of range and sum like so:

[0 <=] [pop 0] [-- dup] [dip +] genrec

Our predicate P checks that the input a is positive, our base case value c is 0, our generator G is -- dup (both a′ and b happen to be the same value in this case), and our combiner Q is just +.

The complete trace for a run of this program is a bit long and unwieldy but I want to show the end of the run after 0 has been reached (here the input value a was 3):

   0 • pop 0 0 + 1 + 2 +
     • 0 0 + 1 + 2 +
   0 • 0 + 1 + 2 +
 0 0 • + 1 + 2 +
 0 0 • add 1 + 2 +
   0 • 1 + 2 +
 0 1 • + 2 +
 0 1 • add 2 +
   1 • 2 +
 1 2 • +
 1 2 • add
   3 •

Note that the intermediate values are queued up in the pending expression along with the Q combiner function and they are only summed up after the initial phase of the program has generated all of them. This is the Joy form of the "call stack in the form of a cons list".

Note also that by replacing the base case value c with the empty list and letting the combiner function Q be swons we reconstruct range:

[0 <=] [pop []] [-- dup] [dip swons] genrec

So is this a hylomorphism or an anamorphism? I don't know.

Anamorphism

An anamorphism can be defined as a hylomorphism that uses [] for c and swons for Q. An anamorphic function builds a list of values.

[P] [] [G] [swons] hylomorphism

We saw an example of an anamorphism in the range function which generates the list of integers from 0 to n - 1 given n.

[0 <=] [] [-- dup] [swons] hylomorphism

Catamorphism

A catamorphic function tears down a list term-by-term and makes some new value. It can be defined as a hylomorphism that uses uncons swap for G and nullfor the predicate P.

[null] c [uncons swap] [Q] hylomorphism

An example of a catamorphism is the sum function.

[null] 0 [uncons swap] [+] hylomorphism

The step combinator

The step combinator is similar to catamorphism but more general, in that it doesn't expect a base value, just a list to "step" through and a quoted function to run on each item in the list.

Tail Recursion

When the last thing that a recursive function does is call itself that's called "tail recursion" (the recursive call happens at the "tail" of the function) and typically language implementations will handle this specially to reuse call stack space. In Joy there is no call stack, all state is either in the stack or in the pending expression, so there is no need for special handling of "tail calls". However, there is a common pattern in recursive functions written in Joy where the last thing the function does is recur, so the rec2 part of the genrec definition is just i:

[if] [then] [rec1] [i] genrec

This is common enough that the program [i] genrec deserves it's own name, and it seems appropriate that it be tailrec.

≡ tailrec

[tailrec [i] genrec] inscribe

I mention this now because we're going to look at a variation of the triangular number hylomorphism that doesn't store intermediate arguments (neither in the stack nor the pending expression), instead it will sum the numbers as it generates them. In this case we don't need to keep them around (unlike e.g. range where the whole point is to collect them in a list and "return" them.)

Using Intermediate Results Immediately

When you can start with the base value c on the stack and the combiner Q can operate as you go using the intermediate results immediately rather than queuing them up, we can do this:

c [pop P] [popd] [[G] dip Q] tailrec

This program would begin with the initial value on the stack.

a c [pop P] [popd] [[G] dip Q] tailrec

The first thing that happens is that the predicate clause is run (using nullary so that it operates in a self-contained scope without disturbing the main stack):

a c pop P

The predicate leaves behind a Boolean value, we will assume that it's false this time and examine the recursive branch:

a c [G] dip Q [F] i

This is composed of the two arguments (the initial a and the base value c) followed by the rec1 part ([G] dip Q) followed by the recursive tail call to the quoted whole function (here represented as F) with the i combinator (as arranged by tailrec).

After the operation of dip we have:

a G c Q [F] i

We might as well "expand" i, eh? It doesn't really matter and it removes clutter:

a G c Q F

So, G operates on a to produce a value b and the next a′:

    a G c Q F
----------------
   a′ b c Q F

Then Q operates on b and c to produce the next c′:

   a′ b c Q F
----------------
     a′ c′ F

And our next "call" to F is ready to go.

If the predicate P leaves behind true then popd removes the a value leaving the c value on the stack.

The thing to note here is that the b values are produced and consumed immediately rather than being stored temporarily on the stack or pending expression. I don't know how this relates to the fancy Category theoretic nomenclature, is this still considered a hylomorphism if there is no longer a "call stack in the form of a cons list"?

The combiner function Q here can (if it were written that way) also access and operate on the next a′ value. Could this be what they call a paramorphism? It sure sounds like it:

[a paramorphism] is a more convenient version of catamorphism in that it gives the combining step function immediate access not only to the result value recursively computed from each recursive subobject, but the original subobject itself as well.

~ Paramorphism

To me it seems that whether or not the combiner needs to operate on the "original subobject" is one aspect, and whether or not the resulting computation stores or immediately consumes intermediate values, is kind of orthogonal. Although it occurs to me that you would have to also keep around the intermediate "subobjects" as well as the result values if you need to compute with them later, eh? You would store pairs of result and subobject in the "call stack in the form of a cons list".

The important thing is to keep track of what you're doing so that you can employ the proper combinator.

Order

Let me call your attention to something else about this variation of recursive function, namely that the Q combiner function encounters the intermediate values in the opposite order. E.g. sum made this way would add 0 3 2 1 rather than 0 1 2 3. Of course this doesn't matter for associative functions like addition. However if we were to implement range using this form the resulting lists of integers would be in the reversed order relative to the "normal" definition of range.

[] [pop 0 <=] [popd] [[-- dup] dip cons] tailrec

Note that other than substituting cons for swons the "parts" of this function (c, P, and G) are the same as for the "normal" definition of range.

Appendix: Derivation of hylomorphism Combinator

Now we just need to derive a definition that builds the genrec arguments out of the pieces given to the hylomorphism combinator.

   [P]      c  [G]     [Q] hylomorphism
------------------------------------------
   [P] [pop c] [G] [dip Q] genrec

Working in reverse:

[P] [pop c] [G] [dip Q] genrec

Use swoncat twice to decouple [c] and [Q].

[P] [c] [pop] swoncat [G] [Q] [dip] swoncat genrec

Use unit to dequote c.

[P] c unit [pop] swoncat [G] [Q] [dip] swoncat genrec

Use dipd to untangle unit [pop] swoncat from the givens.

[P] c [G] [Q] [unit [pop] swoncat] dipd [dip] swoncat genrec

At this point all of the parameters of the hylomorphism are to the left so we have a definition for hylomorphism:

[unit [pop] swoncat] dipd [dip] swoncat genrec

≡ hylomorphism

[hylomorphism [unit [pop] swoncat] dipd [dip] swoncat genrec] inscribe

Usage:

[P] c [G] [Q] hylomorphism

≡ anamorphism

[anamorphism [] swap [swons] hylomorphism] inscribe

Usage:

[P] [G] anamorphism

≡ catamorphism

[catamorphism [[null] swap [uncons swap]] dip hylomorphism] inscribe

Usage:

c [Q] catamorphism

A hylomorphism can be thought of as the composition of an anamorphism and a catamorphism:

[P] [G] anamorphism c [Q] catamorphism == [P] c [G] [Q] hylomorphism

Appendix: Derivation of primrec Combinator

primrec

   n            [B]            [Q] primrec
---------------------------------------------
   n [0 <=] [pop B] [dup --] [i Q] genrec

Working in reverse:

[0 <=] [pop B] [dup --] [i Q] genrec


[0 <=] [B] [pop] swoncat [dup --] [Q] [i] swoncat genrec


[0 <=] [B] [Q] [[pop] swoncat [dup --]] dip [i] swoncat genrec


[B] [Q] [0 <=] roll> [[pop] swoncat [dup --]] dip [i] swoncat genrec

Ergo:

[0 <=] roll> [[pop] swoncat [dup --]] dip [i] swoncat genrec