Tiny Great Languages: APL

This is part 5 from series “Tiny Great Languages”.

This would be a controversial language, but it fits perfectly into the 50-lines-of-less code category. Let’s talk about APL family, and specifically – K.

Created by Arthur Whitney the language is known for its terse and cryptic syntax. But it fixes one “issue” with APL – K uses ASCII symbols. It may sound unsurprising, since most programming languages do that, but APL required a special keyboard since most of the language operators were mathematical symbols and Greek letters, such as Pascal←{0~¨⍨a⌽⊃⌽∊¨0,¨¨a∘!¨a←⌽⍳⍵}, which is a program in APL to render Pascal triangle.

Anyway, K, J, Q, A (these card names, aren’t they?) and APL all belong to the family of array programming languages. In such languages the fundamental data type is a multi-dimensional array. Then there are “nouns”, such as numbers, matrices, variables etc. There are “verbs”, such as arithmetic operators or matrix functions. Finally, there are “adverbs” - combinators that apply verbs to nouns in a particular way.

k/simple

I previously deciphered another Arthur’s Whitney code snippet that became a foundation of a J programming language. Recently I discovered an even simpler variant of it, well-commented and more useful to our case: build an array processing language that could calculate a factorial.

K/simple is a tiny educational K interpreter originally implemented in 25 lines of C code. And by C code I mean this:

_i(u,10u>x-48?x-48:26u>x-97?r_(U[x-97]):0)
f(e,s z=x;c i=*z++;!*z?u(i):v(i)?x(e(z),Q(x)f[v(i)](x)):x(e(z+1),Q(x)58==*z?U[i-97]=r_(x):_(c f=v(*z);Qd(!f)F[f](u(i),x))))
int main(){c b[99];while(1)if(w((s)32),b[read(0,b,99)-1]=0,*b)58==b[1]?e(b):W(e(b));}

Somehow the style in which K/J are written is not the traditional C style, but rather APL style applied to C. Well, at kparc they even tried to write their own C-compatible compiler that would support their coding style - https://github.com/secti6n/kPARC/tree/master/kparc/b. This would allow to write:

// Code in kparc/b
b[Ii]{h:#x;l:0;while(h>l)$[y>x[i:/l+h];l:i+1;h:i];l}
// Equivalent code in C, in APL style
I b(I*x,I y){I h=x[-1],i,l=0;while(h>l)if(y>x[i=l+h>>1])l=i+1;else h=i;R l;}

But back to k/simple. The language uses vectors as the only data type. It simplifies things a lot, as one wouldn’t have to think about “ranks” (array dimensions) and in our case makes code easier to read as lists are native to Python.

The language supports 26 variables, a to z. Original language supported only single-digit numbers 0..9, but that’s easy to overcome in Python.

Here are all the verbs that we need to support:

┌───┬────────────────┬───────────────┐     
│   │  Monadic       │ Dyadic        │     
│───┼────────────────┼───────────────│     
│ + │  ⊘             │ 2+3→5         │     
│ - │ -3→-3          │ 7-3→4         │     
│ * │  ⊘             │ 3*4→12        │     
│ ! │ !3→[0,1,2]     │ 4!7→3 (7%3)   │     
│ # │ #4,5,6→3       │ 4#3→[3,3,3,3] │     
│ , │ ,3→[3]         │ 1,2,3→[1,2,3] │     
│ @ │ @4,5,6→4       │ a@4→a[4]      │     
│ = │  ⊘             │ 1=2→0         │     
│ ~ │  ⊘             │ 1~2→1         │     
│ & │  ⊘             │ 3&5→1         │     
│ | │ |4,5,6→[6,5,4] │ 3|5→7         │     
└────────────────────────────────────┘

A monadic verb operates on a single noun, while dyadic operates on two nouns. You may think of unary and binary operators as an analogy in other programming languages.

Some of the verbs don’t have a monadic variant, they will fail with “rank” error.

Dyadic verbs are as follows:

There are many more operators one can think of to manipulate the lists and there is plenty of ASCII symbols to assign them, but we keep it minimal and close to the original.

It would be easier to build the language from low-level operations to high-level eval. We can start by defining a primitive to tell atom from a vector (just like in Lisp), and a few monadic verbs:

#is atom?
def a(x): return type(x) == int

# a helper to return an error
def err(msg="nyi"): raise f"error: {msg}"

# negate every element
def sub(x): return -x if a(x) else list(map(lambda xi: -xi, x))
ou 
# iota 0...x or error
def iota(x): return list(range(0, x)) if a(x) else err("rank/iota")

# len(x) or error
def rank(x): return err("rank/rank") if a(x) else len(x)

# x -> [x]
def cat(x): return [x] if a(x) else x

# [abc] -> [cba]
def rev(x): return err("rank/rev") if a(x) else list(reversed(x))

Dyadic verbs have a lot in common: they can act on two numbers, or on two vectors of the same length, or on a number and a vector. So we can move this logic into a helper function and only pass an operator to it to customise the behaviour:

def dyad(x, y, op):
    if a(x): return op(x, y) if a(y) else dyad(y, x, op)
    elif a(y): return list(map(lambda n: op(n, y), x))
    elif len(x) != len(y): err("rank/opx")
    else: return list(map(lambda n: op(n[0], n[1]), zip(x, y)))

Here two numbers are processed normally. Two lists are processed with a map and if they differ in length - it’s an error. Two cases (num, list) and (list, num) are actually the same case for commutative operators such as + or *, so we can handle one of them only.

Now we can define some dyadic operators and the rest of the monads:

def Add(x, y): return dyad(x, y, lambda x, y: x + y)
def And(x, y): return dyad(x, y, lambda x, y: x & y)
def Or(x, y): return dyad(x, y, lambda x, y: x | y)
def Not(x, y): return dyad(x, y, lambda x, y: int(x != y))
def Eq(x, y): return dyad(x, y, lambda x, y: int(x == y))
def Prod(x, y): return dyad(x, y, lambda x, y: x * y)
def Sub(x, y): return Add(x, sub(y))
def Mod(x, y): return err("rank") if not a(x) else y % x if a(y) else list(map(lambda y: y % x, y))
def Take(x, y): return err("rank") if not a(x) else [y]*x if a(y) else y[:x]
def Cat(x, y): return cat(x) + cat(y)
def At(x, y): return x[y] if a(y) else list(map(lambda y: x[y], y))
def at(x): return At(x, 0)

Here Add, And, Or, not, Eq, Prod, Sub are all variants of a common dyadic operator logic. Mod only expects the left operator to be an atom and Take either repeats an atom N times (monadic) or fetches the last N elements from a list (dyadic). Cat is joining two lists. At fetches items from the list by index or a list of indices. Monadic “at” simply returns the first element.

Finally, we can implement two adverbs: scan ("/") and over (""). Scan is also known as a “reduce” function: it processes a list with some operator and accumulates the results into a single number. Over does the same but returns a list of intermediate results:

+/3,7,11 -> 3+7+11 -> 21
+\3,7,11 -> [3, 3+7, 3+7+11] -> [3,10,21]

In Python they can be implemented as:

def Over(op, x): return functools.reduce(lambda a, b: op(a, b), x)
def Scan(op, x): return list(itertools.accumulate(x, lambda a, b: op(a, b)))

And that’s the end of our interpreter, we only have to write “eval” function to apply verbs to nouns and we’re done:

def e(s):
    m = re.match(r"(?P<id>[a-zA-Z]+)|(?P<num>[0-9]+)|(?P<op>[-+!#,@=~&|*])", s)
    if not m: err(f"syntax: {s}")
    elif m.lastgroup == "id" or m.lastgroup == "num":
        x = int(s[: m.end()]) if m.lastgroup == "num" else G.get(s[: m.end()], 0)  # a noun
        if m.end() == len(s): return x  # if last in the string: return it
        if s[m.end()] == ":":  # if assignment: recursively evaluate the rest and assign a global
            x = e(s[m.end() + 1 :])
            G[s[: m.end()]] = x
            return x
        return V[s[m.end()]][1](x, e(s[m.end() + 1 :]))  # otherwise: apply dyadic function
    else:
        # If adverb (scan/over): evaluate the rest and apply verb to the resulting noun
        if len(s) > 1 and s[1] in "/\\": return (Over if s[1] == "/" else Scan)(V[s[0]][1], e(s[2:]))
        # Otherwise: apply a monadic verb to the rest of the expression
        return V[s[0]][0](e(s[1:]))

[print(e(line.split(";", 1)[0].strip().replace(" ", ""))) for line in sys.stdin if line.strip()]

Parsing happens left-to-right but evaluation happens right-to-left recursively (so 2*3+4 is actually 24 and not 10). A noun itself is its value, a noun followed by an operator is a dyadic function. A verb without a noun on the left is a monadic verb (unless it’s followed by an adverb).

A special case here is assignment. A variable name followed by : assigns the result to a variable and passes the value on, so 1+a:3+4 assigns 7 to a and returns 8.

Now, the glory of array processing languages – can they calculate a factorial? Yes, in the shortest possible manner:

*/1+!10    ; 10! => 3628800

It’s only 7 bytes of code. !10 returns a list of numbers 0 to 9. 1+!10 adds 1 to each of them resulting in a list [1, 2, …, 10]. Finally */1+!10 applies * verb with scan adverb and returns 1*2*3*...*10 which is a factorial of 10.

This language lacks many features such as loops or conditionals or even user input. But it processes arrays of numbers in such an elegant way what no other language can compete with it (well, maybe numpy).

If you are looking for an inspiration - there is J language with a great manual on how it’s implemented, there is oK.js in a few lines of JavaScript, there is ngn/k which is a K interpreter in C and many others. There is even a K dialect for CHIP-8 in only 4 KB of bytecode!

In the next chapter we will address the most classical and proper (and very much educational) programming language, with procedures and conditionals and loops - Pascal!

I hope you’ve enjoyed this article. You can follow – and contribute to – on Github, Mastodon, Twitter or subscribe via rss.

Sep 13, 2024

See also: Tiny Great Languages: BASIC and more.