Recursion in APL

APL is the acronym for “A Programming Language”, designed as a hardware description language at IBM by Ken Iverson in 1962.  It was later developed in collaboration with A.D.Falkoff, and appeared as an interactive language in 1967, and was very popular with mathematicians and engineers, due to its ability to express mathematical algorithms concisely. Dijkstra didn’t have many good things to say about APL (but at least he was honest).

“APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past; it creates a new generation of coding bums”.

Dijkstra (“How do we tell truths that might hurt”, 1975)

I never liked APL, largely because it is a very symbolic language based on mathematical notation, and as keyboards shed their symbols, it became harder to realistically code in as a language. It did however allow recursion, but texts of the period didn’t really give much credence to it. Even in the 1980s, texts gave no more than a page to the concept. In Leonard Gilman’s APL: An Interactive Approach, published in 1984 the author commented that recursion “is an intriguing topic for most neophyte computer scientists“, including a program for deriving combinations of numbers, and the ubiquitous factorial for entertainment purposes.

Here is a version of Fibonacci written in APL [1]:

    ∇ NUMBER⟵FIB N
[1] NUMBER⟵1
[2] ⟶0 IF N=1
[3] ⟶0 IF N=2
[4] NUMBER⟵(FIB N-1)+(FIB N-2)
    ∇

The program is called FIB, and it produces a NUMBER, which is the Nth in the Fibonacci sequence. In line [1] the NUMBER is assigned the value 1. In lines [2] and [3], if N=1 or N=2, the program stops with 1 as the value returned. If N is larger then 2, then NUMBER is assigned the result of (FIB N-1) and (FIB N-2), invoking a double recursion.

The problem with APL lay in its mathematical nature, although there were some constructs, such as ⟵ for assignment that are inherently more usable than the = used in most languages.

[1] Peelle, H.A., “Euclid, Fibonacci, and Pascal – recursed!”, Int. J. Math. Edu. Sci. Technol., 6(4),pp.395-405 (1975).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.