Conquering recursion - Vector

Conquering recursion

Posted by John Earnest | May 29, 2019 | Volume 27, No. 1 | 0 |

This article presents a set of combinator patterns which can be used to decompose recursive procedures into smaller, more reusable components. Examples of the resulting programming style are contrasted with their more conventional equivalents. We additionally show that the semantic information gained by using these combinators offers opportunities for improved performance.

Background

Vector languages inspire a unique programming ethos. It is considered good style to avoid loops, instead favoring adverbs which capture abstract patterns of iteration. The behavior of the K over could be captured with a do[] loop, but over is far more specific and thus more suggestive to a reader or interpreter. By reducing the number of moving parts in a program, one can avoid would-be bugs before they’re written.

Conditional statements- both the K if[] and $[;;...] (cond)- should likewise be used sparingly. Sometimes a conditional is the most efficient or convenient way to express logic, but there is one context in which conditionals are unavoidable: recursive procedures. With cleverness, many problems which appear to require recursive solutions yield to a vector solution, such as the idiom ,// for flattening an arbitrarily-nested structure. For other problems, however, a recursive solution is by far the most natural and concise. How do we solve these problems without using explicit conditionals and recursive calls?

The Joy[1] programming language contains an unusual and enticing set of features which are applicable to our problem. Joy offers a variety of combinators– pure, higher-order functions which strictly rearrange and apply their arguments- to express the manipulation of data and control flow. Among these are combinators which capture abstract patterns of recursion.

Linear- and tail-recursive algorithms, being isomorphic to loops, have straightforward translations to an adverb-based equivalent and are therefore idiomatically expressed in K without recursion. In this discussion we will focus specifically on recursive procedures which exhibit regular "fanout". This occurs when traversing trees or problem spaces which implicitly have a similar structure. Building on ideas from Joy, we will describe a generalization of its binrec combinator which can be expressed neatly in K. The following examples and discussion incorporate a number of suggestions by my friend and colleague Stevan Apter.

Constructing rec[]

All the examples in this article will be given in K4, but should be applicable, with minor modifications, to any dialect of the language. As a refresher, .z.s is how K4 references the current function, for self-recursion. K4 lambdas, verbs and adverbs have typecodes (obtained via @:) greater than 99. Dictionaries and tables have type codes 99 and 98, respectively.

Consider the definition of the following pentad, rm:

rm: {[p;f;d;c;x]$[p x;f x;c@.z.s[p;f;d;c]'d x]}

For clarity, we will refer to the arguments p, f, d and c as predicate, finalize, divide and combine, respectively. If the predicate of x is true, finalize x. Otherwise, combine the results of recursively invoking rm with each of the results of dividing x.

This combinator is meant to be projected along its first four arguments, yielding a monad. Compare two definitions which recursively calculate the Nth term of the Fibonacci sequence. fib1 uses conventional explicit recursion while fib2 is written in terms of rm:

fib1: {$[2>x;x;+/.z.s'x-1 2]}<br>fib2: rm[2>;::;-2 -1+;+/]

The first thing you may notice about our rm-based formulation is that it now consists entirely of tacit expressions– there is no need for an explicit variable named x. The same sequence of operations takes place, but we have separated the components of the algorithm in fib1, allowing us to consider their roles separately. predicate distinguishes between the base case and recursive case of the definition, divide identifies the children of the current node of the implied recursive tree, and combine fuses results together. In this particular example, finalize is the identity function, but we will see other situations where it is more complex.

Sometimes combine needs context lost in the process of dividing. For these situations we’ll use a variation on rm which we will call rd, for which combine is a dyad:

rd: {[p;f;d;c;x]$[p x;f x;c[.z.s[p;f;d;c]'d x;x]]}

To illustrate the necessity of rd, consider a procedure incx which increments the atomic leaves of a simple expression tree:

incx: rd[@:;1+;1_;{(*y),x}]

incx (`plus;(`minus;1;5);8)<br>(`plus;(`minus;2;6);9)

We can always distinguish between times rm or rd is appropriate by considering the valence of combine. As a matter of tidiness, let’s write a single procedure which captures both:

@:'({x};{x+y};+/;1;2.0)<br>100 100 107 -7 -9h<br>ambiv: {$[99

Another refinement is to observe that the base case represented by finalize...