This article describes the genrec combinator and how to use it, and then 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 a 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.)
In Joy recursive functions are defined by the genrec combinator which accepts four quoted programs:
F == [if] [then] [rec1] [rec2] genrec
This can be thought of as transforming into an "if..then..else" expression using the ifte combinator and containing a quoted copy of itself in the "else" branch:
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. This notebook is much lighter. We're going to look at things from the point-of-view of the "Bananas, Lenses, & Barbed Wire" paper, all about hylomorphisms, anamorphisms, catamorphisms, etc.
A hylomorphism is a recursive function H that converts a value of type 𝔸 into a value of type ℂ by means of:
G from 𝔸 to (𝔹, 𝔸)Q from (𝔹, ℂ) to ℂP from 𝔸 to Bool to detect the base casec of type ℂ, andIt may be helpful to see this function implemented in pseudocode (Python).
def hylomorphism(c, Q, P, G):
'''Return a hylomorphism function H.'''
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".
a H
---------
c
We can define a combinator hylomorphism that will make a hylomorphism combinator H from constituent parts. (The reason for the order of the parameters will become clear below):
H == [P] c [G] [Q] hylomorphism
The function H is recursive, so we start with ifte and set the else-part to some function J that will contain a quoted copy of H.
The then-part just discards the leftover a and replaces it with the base case value c:
H == [P] [pop c] [J] ifte
The else-part J gets just the argument a on the stack.
a J
The first thing to do is use the generator G which produces values b and a new a′:
a G
----------
a′ b
So:
J == G J′
Then we recur with H on a′:
a′ b [H] dip
------------------
a′ H b
------------------
c′ b
So:
J′ == [H] dip J″
And run Q on the result:
c′ b Q
------------
c
So:
J″ == Q
Summing up:
J == G J′
J′ == [H] dip J″
J″ == Q
This gives us a definition for J:
J == G [H] dip Q
Plug it in and convert to genrec:
H == [P] [pop c] [ J ] ifte
[P] [pop c] [G [H] dip Q] ifte
[P] [pop c] [G] [dip Q] genrec
This is the form of a hylomorphism in Joy, which nicely illustrates that it is a simple specialization of the general recursion combinator.
[P] c [G] [Q] hylomorphism
[P] [pop c] [G] [dip Q] genrechylomorphism 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:
swoncat twice to decouple [c] and [Q].unit to dequote c.Use dipd to untangle [unit [pop] swoncat] from the givens.
H == [P] [pop c] [G] [dip Q] genrec
[P] [c] [pop] swoncat [G] [Q] [dip] swoncat genrec
[P] c unit [pop] swoncat [G] [Q] [dip] swoncat genrec
[P] c [G] [Q] [unit [pop] swoncat] dipd [dip] swoncat genrecAt this point all of the parameters of the hylomorphism are to the left so we have a definition for hylomorphism:
hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec[hylomorphism [unit [pop] swoncat] dipd [dip] swoncat genrec] inscribe
Let's write a function that, given a positive integer, returns the sum of all positive integers less than that one. (In this case the types 𝔸, 𝔹 and ℂ are all int.)
To sum a range of integers from 0 to n - 1:
[P] is [1 <=]c is 0[G] is [-- dup][Q] is [+][triangular_number [1 <=] 0 [-- dup] [+] hylomorphism] inscribe
Let's try it:
5 triangular_number
clear
[0 1 2 3 4 5 6 7] [triangular_number] map
Neat!
In the Wikipedia entry for hylomorphism it says:
a hylomorphism is a recursive function, corresponding 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).
An anamorphism can be defined as a hylomorphism that uses [] for c and
swons for Q. An anamorphic function builds a list of values.
A == [P] [] [G] [swons] hylomorphism
An example of an anamorphism is the range function which generates the list of integers from $0$ to $n - 1$ given $n$.
range == [0 <=] [] [-- dup] [swons] hylomorphismclear
[range [0 <=] [] [-- dup] [swons] hylomorphism] inscribe
5 range
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 [[] =] (or just [not]) for the predicate [P].
C == [not] c [uncons swap] [Q] hylomorphism
An example of a catamorphism is the sum function.
sum == [not] 0 [uncons swap] [+] hylomorphismclear
[sum [not] 0 [uncons swap] [+] hylomorphism] inscribe
[5 4 3 2 1] sum
clear
The "Bananas, Lenses, & Barbed Wire" paper mentions the
f . (| b, (+) |) = (| c, (x) |) <== f b = c /\ f( a (+) as ) = a (x) (f as)The "Bananas, Lenses, & Barbed Wire" paper mentions the
f ∘ ⦇b,⨁⦈ = ⦇c,⨂⦈ ⇐ f b = c ∧ f(a ⨁ as) = a ⨂ (f as)b [⨁] catamorphism f == c [⨂] catamorphism
f == 10 *
0 [+] catamorphism f
0 f == 0
as a + f == as f a ⨂
⨂ = f +
0 [+] catamorphism f = 0 [f +] catamorphism⨁ ⨂ ∘ ∧ ⦇ ⦈ ⇐
step combinator¶The step combinator will often be easier to use than catamorphism.
[step] help
[sum 0 swap [+] step] inscribe
[5 4 3 2 1] sum
anamorphism == [] swap [swons] hylomorphism
catamorphism == [[not] swap [uncons swap]] dip hylomorphism
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] hylomorphismFor example, triangular_number could be defined as the composition of the range and sum functions:
triangular_number == range sumclear
[0 1 2 3 4 5 6 7] [range sum] map
However, this creates (and destroys) an intermediate list, which is a waste.
Let's review the operation of the hylomorphism:
[P] c [G] [Q] H₁ == [P] [pop c] [G] [dip Q] genrec
... a G [H₁] dip Q
... a′ b [H₁] dip Q
... a′ H₁ b Q
<predicate omitted>
... a′ G [H₁] dip Q b Q
... a″ b′ [H₁] dip Q b Q
... a″ H₁ b′ Q b Q
<predicate omitted>
... a″ G [H₁] dip Q b′ Q b Q
... a‴ b″ [H₁] dip Q b′ Q b Q
... a‴ H₁ b″ Q b′ Q b Q
<predicate omitted>
... a‴ pop c b″ Q b′ Q b Q
... c b″ Q b′ Q b Q
... c′ b′ Q b Q
... c″ b Q
... c‴
Notice that b values and the Q combiner function get pushed into the pending expression ("continuation").
Now let's try a version that doesn't do that. When you can start with the identity 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:
[P] c [G] [Q] H₂ == c [pop P] [popd] [[G] dip Q] tailrec
An important difference is that the combiner function Q must accept its arguments in the reverse order and take into account the presence of the a value:
... a c [G] dip Q H₂
... a G c Q H₂
... a′ b c Q H₂
... a′ c′ H₂
<predicate omitted>
... a′ c′ [G] dip Q H₂
... a′ G c′ Q H₂
... a″ b c′ Q H₂
... a″ c″ H₂
<predicate omitted>
... a″ c″ [G] dip Q H₂
... a″ G c″ Q H₂
... a‴ b c″ Q H₂
... a‴ c‴ H₂
<predicate omitted>
... a‴ c‴ popd
... c‴Note that the c values are processed by the Q combiner function in reverse order as compared to the original version.
range with H₂¶For example, if we reimplement the range function in the tail-recursive style it generates the list with $0$ at the head rather than $n - 1$:
range_reverse == [] [pop 0 <=] [popd] [[-- dup] dip cons] tailrecclear
[range_reverse [] [pop 0 <=] [popd] [[-- dup] dip cons] tailrec] inscribe
5 [range] [range_reverse] cleave
Instead of making Q take account of the c value we could do this:
... a′ b c [Q] ccons dip swap H₂
... a′ [b c Q] dip swap H₂
... b c Q a′ swap H₂
... c′ a′ swap H₂
... a′ c′ H₂
This shows that any function Q can be converted to [Q] ccons dip swap to deal with that a value on the stack.
Now let's try a version that doesn't do that. When you can start with the identity 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:
[P] c [G] [Q] H₂ == c swap [P] [pop] [G [Q] dip] tailrec
An important difference is that the generator function must return its results in the reverse order, and both Q and G have to take into account the presence of the c value:
... c a G [Q] dip H₂
... c b a′ [Q] dip H₂
... c b Q a′ H₂
... c′ a′ H₂
<predicate omitted>
... c′ a′ G [Q] dip H₂
... c′ b′ a″ [Q] dip H₂
... c′ b′ Q a″ H₂
... c″ a″ H₂
<predicate omitted>
... c″ a″ G [Q] dip H₂
... c″ b″ a‴ [Q] dip H₂
... c″ b″ Q a‴ H₂
... c‴ a‴ H₂
<predicate omitted>
... c‴ a‴ pop
... c‴There are (at least) four kinds of recursive combinator, depending on two choices. The first choice is whether the combiner function Q should be evaluated during the recursion or pushed into the pending expression to be "collapsed" at the end. The second choice is whether the combiner needs to operate on the current value of the datastructure or the generator's output, in other words, whether Q or G should run first in the recursive branch.
H1 == [P] [pop c] [G ] [dip Q] genrec
H2 == c swap [P] [pop] [G [Q] dip ] [i] genrec
H3 == [P] [pop c] [ [G] dupdip ] [dip Q] genrec
H4 == c swap [P] [pop] [ [Q] dupdip G] [i] genrec
The working of the generator function G differs slightly for each. Consider the recursive branches:
... a G [H1] dip Q w/ a G == a′ b
... c a G [Q] dip H2 a G == b a′
... a [G] dupdip [H3] dip Q a G == a′
... c a [Q] dupdip G H4 a G == a′
The following four sections illustrate how these work, omitting the predicate evaluation.
H1¶This form builds up a pending expression (continuation) that contains the intermediate results along with the pending combiner functions. When the base case is reached the last term is replaced by the identity value c and the continuation "collapses" into the final result using the combiner Q.
H1 == [P] [pop c] [G] [dip Q] genrec
... a G [H1] dip Q
... a′ b [H1] dip Q
... a′ H1 b Q
<predicate omitted>
... a′ G [H1] dip Q b Q
... a″ b′ [H1] dip Q b Q
... a″ H1 b′ Q b Q
<predicate omitted>
... a″ G [H1] dip Q b′ Q b Q
... a‴ b″ [H1] dip Q b′ Q b Q
... a‴ H1 b″ Q b′ Q b Q
<predicate omitted>
... a‴ pop c b″ Q b′ Q b Q
... c b″ Q b′ Q b Q
... c′ b′ Q b Q
... c″ b Q
... c‴H2¶When you can start with the identity value c on the stack and the combiner Q can operate as you go using the intermediate results immediately rather than queuing them up, use this form.
An important difference is that the generator function must return its results in the reverse order,
and both Q and G have to take into account the presence of the c value:
H2 == c swap [P] [pop] [G [Q] dip] tailrec
... c a G [Q] dip H2
... c b a′ [Q] dip H2
... c b Q a′ H2
... c′ a′ H2
<predicate omitted>
... c′ a′ G [Q] dip H2
... c′ b′ a″ [Q] dip H2
... c′ b′ Q a″ H2
... c″ a″ H2
<predicate omitted>
... c″ a″ G [Q] dip H2
... c″ b″ a‴ [Q] dip H2
... c″ b″ Q a‴ H2
... c‴ a‴ H2
<predicate omitted>
... c‴ a‴ pop
... c‴H3¶If you examine the traces above you'll see that the combiner Q only gets to operate on the results of G, it never "sees" the first value a. If the combiner and the generator both need to work on the current value then dup must be used, and the generator must produce one item instead of two (the b is instead the duplicate of a.)
H3 == [P] [pop c] [[G] dupdip] [dip Q] genrec
... a [G] dupdip [H3] dip Q
... a G a [H3] dip Q
... a′ a [H3] dip Q
... a′ H3 a Q
<predicate omitted>
... a′ [G] dupdip [H3] dip Q a Q
... a′ G a′ [H3] dip Q a Q
... a″ a′ [H3] dip Q a Q
... a″ H3 a′ Q a Q
<predicate omitted>
... a″ [G] dupdip [H3] dip Q a′ Q a Q
... a″ G a″ [H3] dip Q a′ Q a Q
... a‴ a″ [H3] dip Q a′ Q a Q
... a‴ H3 a″ Q a′ Q a Q
<predicate omitted>
... a‴ pop c a″ Q a′ Q a Q
... c a″ Q a′ Q a Q
... c′ a′ Q a Q
... c‴ a Q
... c‴H4¶And, last but not least, if you can combine as you go, starting with c, and the combiner Q needs to work on the current item, this is the form:
H4 == c swap [P] [pop] [[Q] dupdip G] primrec
... c a [Q] dupdip G H4
... c a Q a G H4
... c′ a G H4
... c′ a′ H4
<predicate omitted>
... c′ a′ [Q] dupdip G H4
... c′ a′ Q a′ G H4
... c‴ a′ G H4
... c‴ a″ H4
<predicate omitted>
... c‴ a″ [Q] dupdip G H4
... c‴ a″ Q a″ G H4
... c‴ a″ G H4
... c‴ a‴ H4
<predicate omitted>
... c‴ a‴ pop
... c‴range et. al.¶An example of an anamorphism is the range function which generates the list of integers from 0 to n - 1 given n.
Each of the above variations can be used to make four slightly different range functions.
range with H1¶H1 == [P] [pop c] [G] [dip Q] genrec
== [0 <=] [pop []] [-- dup] [dip swons] genrecclear
[range [0 <=] [] [-- dup] [swons] hylomorphism] inscribe
5 range
range with H2¶H2 == c swap [P] [pop] [G [Q] dip] tailrec
== [] swap [0 <=] [pop] [-- dup [swons] dip] tailrecclear
[range_reverse [] swap [0 <=] [pop] [-- dup [swons] dip] tailrec] inscribe
5 range_reverse
range with H3¶H3 == [P] [pop c] [[G] dupdip] [dip Q] genrec
== [0 <=] [pop []] [[--] dupdip] [dip swons] genrecclear
[ranger [0 <=] [pop []] [[--] dupdip] [dip swons] genrec] inscribe
5 ranger
range with H4¶H4 == c swap [P] [pop] [[Q] dupdip G ] primrec
== [] swap [0 <=] [pop] [[swons] dupdip --] primrecclear
[ranger_reverse [] swap [0 <=] [pop] [[swons] dupdip --] tailrec] inscribe
5 ranger_reverse
For the Factorial function:
H4 == c swap [P] [pop] [[Q] dupdip G] tailrec
With:
c == 1
Q == *
G == --
P == 1 <=clear
[factorial 1 swap [1 <=] [pop] [[*] dupdip --] tailrec] inscribe
5 factorial
An often-used function is filter which takes a list and a predicate and makes a new list with only those items from the input list that make the predicate true:
[...] [P] filter
----------------------
[...]′
Let's start by making a simpler function that just recreates the input list:
F == [not] [] [J] ifte
To figure out the recursive branch J we start by setting a dummy list in front of it.
[a b c] J
[a b c] uncons swap J′
a [b c] swap J′
[b c] a J′
J == uncons swap J′
We don't have the output list to which to cons that a so we recur instead and then cons (more precisely swons) it:
J′ == [Q] dip swons
[b c] a [Q] dip swons
[b c] Q a swons
...
[c] Q b swons a swons
...
[] c swons b swons a swons
...
[a b c]
So:
J == uncons swap [Q] dip swons
And:
F == [not] [] [uncons swap [F] dip swons] ifte
[not] [] [uncons swap] [dip swons] genrecclear
[1 2 3] [not] [] [uncons swap] [dip swons] genrec
It would seem that all we need to do now is turn the swons into an expression that applies the input P predicate to the items and only puts them on the output list if they pass.
filter == [not] [] [uncons swap] [dip W] genrec
Resulting in, e.g.:
[] c W b W a W
However, the input list will be on the stack just below the item, so W has to take account of that. If our predicate function doesn't use any values from below the item under consideration then we're okay, but if it does then we have to deal with the input list somehow.
We know W would be something like:
W == [...[P]...] [swons] [pop] ifte
Let's examine the situation:
... [...] item [...[P]...] [swons] [pop] ifte
Since the predicate of the ifte combinator is applied nullary we can just pop the output list:
... [...] item popd P
And since [P] is already a quote:
W == [popd P] [swons] [pop] ifte
Ergo:
[P] filter == [not] [] [uncons swap] [dip [popd P] [swons] [pop] ifte] genrec
Getting that P into position is straightforward. Working in reverse:
[not] [] [uncons swap] [dip [popd P] [swons] [pop] ifte] genrec
Undip the first three terms:
[dip [popd P] [swons] [pop] ifte] [[not] [] [uncons swap]] dip genrec
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Take off the [dip] prefix:
[[popd P] [swons] [pop] ifte] [dip] swoncat [[not] [] [uncons swap]] dip genrec
^^^^^^^^^^^^^
Uncons the term containing P:
[popd P] [[swons] [pop] ifte] cons [dip] swoncat [[not] [] [uncons swap]] dip genrec
^^^^^^^^ ^^^^
And then take off the [popd] prefix:
[P] [popd] swoncat [[swons] [pop] ifte] cons [dip] swoncat [[not] [] [uncons swap]] dip genrec
^^^^^^^^^^^^^^
And so:
filter == [popd] swoncat [[swons] [pop] ifte] cons [dip] swoncat [[not] [] [uncons swap]] dip genrecclear
[filter [popd] swoncat [[swons] [pop] ifte] cons [dip] swoncat [[not] [] [uncons swap]] dip genrec] inscribe
[1 2 3 4 5 6 7 8] [2 mod not]
filter
This isn't completely satisfying. For one thing, it would be nice to apply the predicate as we go so we are not putting items (and W) onto the expression for items that will fail the predicate P.
tails¶An example of a paramorphism for lists given in the "Bananas..." paper is tails which returns the list of "tails" of a list.
[1 2 3] tails
--------------------
[[] [3] [2 3]]
We can build as we go, and we want Q to run after G, so we use pattern H2:
H2 == c swap [P] [pop] [G [Q] dip] tailrec
We would use:
c == []
Q == swons
G == rest dup
P == notclear
[tails [] swap [not] [pop] [rest dup [swons] dip] tailrec] inscribe
[1 2 3] tails
Our story so far...
H == [P ] [pop c ] [G ] [dip Q ] genrec
A == [P ] [pop []] [G ] [dip swap cons] genrec
C == [not] [pop c ] [uncons swap] [dip Q ] genrec
P == c swap [P ] [pop] [[Q ] dupdip G ] primrec
? == [] swap [P ] [pop] [[swap cons] dupdip G ] primrec
? == c swap [not] [pop] [[Q ] dupdip uncons swap] primrec|[ (c, Q), (G, P) ]| == (|c, Q|) • [(G, P)]
"Bananas, Lenses, & Barbed Wire"
(|...|) [(...)] [<...>]
I think they are having slightly too much fun with the symbols. However, "Too much is always better than not enough."