4 from notebook_preamble import D, DefinitionWrapper, J, V, define
9 This article describes the ``genrec`` combinator, how to use it, and
10 several generic specializations.
14 [if] [then] [rec1] [rec2] genrec
15 ---------------------------------------------------------------------
16 [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte
18 From "Recursion Theory and Joy" (j05cmp.html) by Manfred von Thun:
20 "The genrec combinator takes four program parameters in addition to
21 whatever data parameters it needs. Fourth from the top is an
22 if-part, followed by a then-part. If the if-part yields true, then
23 the then-part is executed and the combinator terminates. The other
24 two parameters are the rec1-part and the rec2-part. If the if-part
25 yields false, the rec1-part is executed. Following that the four
26 program parameters and the combinator are again pushed onto the
27 stack bundled up in a quoted form. Then the rec2-part is executed,
28 where it will find the bundled form. Typically it will then execute
29 the bundled form, either with i or with app2, or some other
32 Designing Recursive Functions
33 -----------------------------
35 The way to design one of these is to fix your base case and test and
36 then treat ``R1`` and ``R2`` as an else-part "sandwiching" a quotation
37 of the whole function.
39 For example, given a (general recursive) function ``F``:
43 F == [I] [T] [R1] [R2] genrec
44 == [I] [T] [R1 [F] R2] ifte
46 If the ``[I]`` predicate is false you must derive ``R1`` and ``R2``
53 Set the stack arguments in front and figure out what ``R1`` and ``R2``
54 have to do to apply the quoted ``[F]`` in the proper way.
56 Primitive Recursive Functions
57 -----------------------------
59 Primitive recursive functions are those where ``R2 == i``.
63 P == [I] [T] [R] primrec
64 == [I] [T] [R [P] i] ifte
67 `Hylomorphism <https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29>`__
68 ------------------------------------------------------------------------------------
71 `hylomorphism <https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29>`__
72 is a recursive function ``H :: A -> C`` that converts a value of type
73 ``A`` into a value of type ``C`` by means of:
75 - A generator ``G :: A -> (B, A)``
76 - A combiner ``F :: (B, C) -> C``
77 - A predicate ``P :: A -> Bool`` to detect the base case
78 - A base case value ``c :: C``
79 - Recursive calls (zero or more); it has a "call stack in the form of a
82 It may be helpful to see this function implemented in imperative Python
87 def hylomorphism(c, F, P, G):
88 '''Return a hylomorphism function H.'''
95 result = F(b, H(aa)) # b is stored in the stack frame during recursive call to H().
100 Cf. `"Bananas, Lenses, & Barbed
101 Wire" <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125>`__
103 Note that during evaluation of ``H()`` the intermediate ``b`` values are
104 stored in the Python call stack. This is what is meant by "call stack in
105 the form of a cons list".
110 We can define a combinator ``hylomorphism`` that will make a
111 hylomorphism combinator ``H`` from constituent parts.
115 H == [P] c [G] [F] hylomorphism
117 The function ``H`` is recursive, so we start with ``ifte`` and set the
118 else-part to some function ``J`` that will contain a quoted copy of
119 ``H``. (The then-part just discards the leftover ``a`` and replaces it
120 with the base case value ``c``.)
124 H == [P] [pop c] [J] ifte
126 The else-part ``J`` gets just the argument ``a`` on the stack.
131 a G The first thing to do is use the generator G
132 aa b which produces b and a new aa
133 aa b [H] dip we recur with H on the new aa
134 aa H b F and run F on the result.
136 This gives us a definition for ``J``.
142 Plug it in and convert to genrec.
146 H == [P] [pop c] [G [H] dip F] ifte
147 H == [P] [pop c] [G] [dip F] genrec
149 This is the form of a hylomorphism in Joy, which nicely illustrates that
150 it is a simple specialization of the general recursion combinator.
154 H == [P] c [G] [F] hylomorphism == [P] [pop c] [G] [dip F] genrec
156 Derivation of ``hylomorphism`` combinator
157 -----------------------------------------
159 Now we just need to derive a definition that builds the ``genrec``
160 arguments out of the pieces given to the ``hylomorphism`` combinator.
164 [P] c [G] [F] hylomorphism
165 ------------------------------------------
166 [P] [pop c] [G] [dip F] genrec
170 - Use ``swoncat`` twice to decouple ``[c]`` and ``[F]``.
171 - Use ``unit`` to dequote ``c``.
172 - Use ``dipd`` to untangle ``[unit [pop] swoncat]`` from the givens.
178 H == [P] [pop c] [G] [dip F] genrec
179 [P] [c] [pop] swoncat [G] [F] [dip] swoncat genrec
180 [P] c unit [pop] swoncat [G] [F] [dip] swoncat genrec
181 [P] c [G] [F] [unit [pop] swoncat] dipd [dip] swoncat genrec
183 At this point all of the arguments (givens) to the hylomorphism are to
184 the left so we have a definition for ``hylomorphism``:
188 hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec
192 define('hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec')
194 Example: Finding `Triangular Numbers <https://en.wikipedia.org/wiki/Triangular_number>`__
195 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
197 Let's write a function that, given a positive integer, returns the sum
198 of all positive integers less than that one. (In this case the types
199 ``A``, ``B`` and ``C`` are all ``int``.)
201 To sum a range of integers from 0 to *n* - 1:
203 - ``[P]`` is ``[1 <=]``
205 - ``[G]`` is ``[-- dup]``
210 define('triangular_number == [1 <=] 0 [-- dup] [+] hylomorphism')
216 J('5 triangular_number')
226 J('[0 1 2 3 4 5 6] [triangular_number] map')
237 There are at least four kinds of recursive combinator, depending on two
238 choices. The first choice is whether the combiner function ``F`` should
239 be evaluated during the recursion or pushed into the pending expression
240 to be "collapsed" at the end. The second choice is whether the combiner
241 needs to operate on the current value of the datastructure or the
242 generator's output, in other words, whether ``F`` or ``G`` should run
243 first in the recursive branch.
247 H1 == [P] [pop c] [G ] [dip F] genrec
248 H2 == c swap [P] [pop] [G [F] dip ] [i] genrec
249 H3 == [P] [pop c] [ [G] dupdip ] [dip F] genrec
250 H4 == c swap [P] [pop] [ [F] dupdip G] [i] genrec
252 The working of the generator function ``G`` differs slightly for each.
253 Consider the recursive branches:
257 ... a G [H1] dip F w/ a G == a′ b
259 ... c a G [F] dip H2 a G == b a′
261 ... a [G] dupdip [H3] dip F a G == a′
263 ... c a [F] dupdip G H4 a G == a′
265 The following four sections illustrate how these work, omitting the
266 predicate evaluation.
273 H1 == [P] [pop c] [G] [dip F] genrec
282 ... a′ G [H1] dip F b F
283 ... a″ b′ [H1] dip F b F
285 ... a″ G [H1] dip F b′ F b F
286 ... a‴ b″ [H1] dip F b′ F b F
287 ... a‴ H1 b″ F b′ F b F
288 ... a‴ pop c b″ F b′ F b F
294 This form builds up a pending expression (continuation) that contains
295 the intermediate results along with the pending combiner functions. When
296 the base case is reached the last term is replaced by the identity value
297 ``c`` and the continuation "collapses" into the final result using the
303 When you can start with the identity value ``c`` on the stack and the
304 combiner ``F`` can operate as you go using the intermediate results
305 immediately rather than queuing them up, use this form. An important
306 difference is that the generator function must return its results in the
311 H2 == c swap [P] [pop] [G [F] dip] primrec
314 ... c b a′ [F] dip H2
317 ... d a′ G [F] dip H2
318 ... d b′ a″ [F] dip H2
321 ... d′ a″ G [F] dip H2
322 ... d′ b″ a‴ [F] dip H2
331 If you examine the traces above you'll see that the combiner ``F`` only
332 gets to operate on the results of ``G``, it never "sees" the first value
333 ``a``. If the combiner and the generator both need to work on the
334 current value then ``dup`` must be used, and the generator must produce
335 one item instead of two (the b is instead the duplicate of a.)
339 H3 == [P] [pop c] [[G] dupdip] [dip F] genrec
341 ... a [G] dupdip [H3] dip F
345 ... a′ [G] dupdip [H3] dip F a F
346 ... a′ G a′ [H3] dip F a F
347 ... a″ a′ [H3] dip F a F
349 ... a″ [G] dupdip [H3] dip F a′ F a F
350 ... a″ G a″ [H3] dip F a′ F a F
351 ... a‴ a″ [H3] dip F a′ F a F
352 ... a‴ H3 a″ F a′ F a F
353 ... a‴ pop c a″ F a′ F a F
362 And, last but not least, if you can combine as you go, starting with
363 ``c``, and the combiner ``F`` needs to work on the current item, this is
368 H4 == c swap [P] [pop] [[F] dupdip G] primrec
370 ... c a [F] dupdip G H4
374 ... d a′ [F] dupdip G H4
378 ... d′ a″ [F] dupdip G H4
388 An anamorphism can be defined as a hylomorphism that uses ``[]`` for
389 ``c`` and ``swons`` for ``F``. An anamorphic function builds a list of
394 A == [P] [] [G] [swons] hylomorphism
399 An example of an anamorphism is the ``range`` function which generates
400 the list of integers from 0 to *n* - 1 given *n*.
402 Each of the above variations can be used to make four slightly different
405 ``range`` with ``H1``
406 ^^^^^^^^^^^^^^^^^^^^^
410 H1 == [P] [pop c] [G] [dip F] genrec
411 == [0 <=] [pop []] [-- dup] [dip swons] genrec
415 define('range == [0 <=] [] [-- dup] [swons] hylomorphism')
427 ``range`` with ``H2``
428 ^^^^^^^^^^^^^^^^^^^^^
432 H2 == c swap [P] [pop] [G [F] dip] primrec
433 == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec
437 define('range_reverse == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec')
449 ``range`` with ``H3``
450 ^^^^^^^^^^^^^^^^^^^^^
454 H3 == [P] [pop c] [[G] dupdip] [dip F] genrec
455 == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec
459 define('ranger == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec')
471 ``range`` with ``H4``
472 ^^^^^^^^^^^^^^^^^^^^^
476 H4 == c swap [P] [pop] [[F] dupdip G ] primrec
477 == [] swap [0 <=] [pop] [[swons] dupdip --] primrec
481 define('ranger_reverse == [] swap [0 <=] [pop] [[swons] dupdip --] primrec')
485 J('5 ranger_reverse')
493 Hopefully this illustrates the workings of the variations. For more
494 insight you can run the cells using the ``V()`` function instead of the
495 ``J()`` function to get a trace of the Joy evaluation.
500 A catamorphism can be defined as a hylomorphism that uses
501 ``[uncons swap]`` for ``[G]`` and ``[[] =]`` (or just ``[not]``) for the
502 predicate ``[P]``. A catamorphic function tears down a list term-by-term
503 and makes some new value.
507 C == [not] c [uncons swap] [F] hylomorphism
511 define('swuncons == uncons swap') # Awkward name.
513 An example of a catamorphism is the sum function.
517 sum == [not] 0 [swuncons] [+] hylomorphism
521 define('sum == [not] 0 [swuncons] [+] hylomorphism')
533 The ``step`` combinator
534 ~~~~~~~~~~~~~~~~~~~~~~~
536 The ``step`` combinator will usually be better to use than
546 Run a quoted program on each item in a sequence.
550 -----------------------
555 ------------------------
559 ... [a b c] [Q] . step
560 ----------------------------------------
561 ... a . Q [b c] [Q] step
563 The step combinator executes the quotation on each member of the list
570 define('sum == 0 swap [+] step')
582 Example: Factorial Function
583 ---------------------------
585 For the Factorial function:
589 H4 == c swap [P] [pop] [[F] dupdip G] primrec
602 define('factorial == 1 swap [1 <=] [pop] [[*] dupdip --] primrec')
617 An example of a paramorphism for lists given in the `"Bananas..."
618 paper <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125>`__
619 is ``tails`` which returns the list of "tails" of a list.
627 We can build as we go, and we want ``F`` to run after ``G``, so we use
632 H2 == c swap [P] [pop] [G [F] dip] primrec
645 define('tails == [] swap [not] [pop] [rest dup [swons] dip] primrec')
657 Conclusion: Patterns of Recursion
658 ---------------------------------
667 H == [P ] [pop c ] [G ] [dip F ] genrec
668 A == [P ] [pop []] [G ] [dip swap cons] genrec
669 C == [not] [pop c ] [uncons swap] [dip F ] genrec
676 P == c swap [P ] [pop] [[F ] dupdip G ] primrec
677 ? == [] swap [P ] [pop] [[swap cons] dupdip G ] primrec
678 ? == c swap [not] [pop] [[F ] dupdip uncons swap] primrec
680 Appendix: Fun with Symbols
681 --------------------------
685 |[ (c, F), (G, P) ]| == (|c, F|) • [(G, P)]
687 `"Bananas, Lenses, & Barbed
688 Wire" <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125>`__
692 (|...|) [(...)] [<...>]
694 I think they are having slightly too much fun with the symbols. However,
695 "Too much is always better than not enough."