Ode to J
While self-isolating orchestras and amateur musicians are playing ‘Ode to Joy’ from their open windows, I would like to give it a try with my ode to J.
If you read the Hacker News or other programming resources, you probably have read the following passage:
“One summer weekend in 1989, Arthur Whitney visited Ken Iverson at Kiln Farm and produced—on one page and in one afternoon—an interpreter fragment on the AT&T 3B1 computer. I studied this interpreter for about a week for its organization and programming style; and on Sunday, August 27, 1989, at about four o’clock in the afternoon, wrote the first line of code that became the implementation described in this document.” (An Implementation of J, Appendix A: Incunabulum).
It was the beginning of the story of the J language, a weird-looking array programming language. This family of languages is notable for their terse notation, where a clever one-liner can represent what would have taken a page of Java code.
For example a common for loop for (int i = 0; i < n; i++) a[i] += b[i]; in J would simple become a=:a+b.
It’s no wonder that the snippet of code that inspired the creation of the J language is also very concise:
typedef char C;typedef long long I;
typedef struct a{I t,r,d[3],p[2];}*A;
#define P printf
#define R return
#define V1(f) A f(w)A w;
#define V2(f) A f(a,w)A a,w;
#define DO(n,x) {I i=0,_n=(n);for(;i<_n;++i){x;}}
I *ma(n){R(I*)malloc(n*8);}mv(d,s,n)I *d,*s;{DO(n,d[i]=s[i]);}
tr(r,d)I *d;{I z=1;DO(r,z=z*d[i]);R z;}
A ga(t,r,d)I *d;{A z=(A)ma(5+tr(r,d));z->t=t,z->r=r,mv(z->d,d,r);
R z;}
V1(iota){I n=*w->p;A z=ga(0,1,&n);DO(n,z->p[i]=i);R z;}
V2(plus){I r=w->r,*d=w->d,n=tr(r,d);A z=ga(0,r,d);
DO(n,z->p[i]=a->p[i]+w->p[i]);R z;}
V2(from){I r=w->r-1,*d=w->d+1,n=tr(r,d);
A z=ga(w->t,r,d);mv(z->p,w->p+(n**a->p),n);R z;}
V1(box){A z=ga(1,0,0);*z->p=(I)w;R z;}
V2(cat){I an=tr(a->r,a->d),wn=tr(w->r,w->d),n=an+wn;
A z=ga(w->t,1,&n);mv(z->p,a->p,an);mv(z->p+an,w->p,wn);R z;}
V2(find){}
V2(rsh){I r=a->r?*a->d:1,n=tr(r,a->p),wn=tr(w->r,w->d);
A z=ga(w->t,r,a->p);mv(z->p,w->p,wn=n>wn?wn:n);
if(n-=wn)mv(z->p+wn,z->p,n);R z;}
V1(sha){A z=ga(0,1,&w->r);mv(z->p,w->d,w->r);R z;}
V1(id){R w;}V1(size){A z=ga(0,0,0);*z->p=w->r?*w->d:1;R z;}
pi(i){P("%d ",i);}nl(){P("\n");}
pr(w)A w;{I r=w->r,*d=w->d,n=tr(r,d);DO(r,pi(d[i]));nl();
if(w->t)DO(n,P("< ");pr(w->p[i]))else DO(n,pi(w->p[i]));nl();}
C vt[]="+{~<#,";
A(*vd[])()={0,plus,from,find,0,rsh,cat},
(*vm[])()={0,id,size,iota,box,sha,0};
I st[26]; qp(a){R a>='a'&&a<='z';}qv(a){R a<'a';}
A ex(e)I *e;{I a=*e;
if(qp(a)){if(e[1]=='=')R st[a-'a']=ex(e+2);a= st[ a-'a'];}
R qv(a)?(*vm[a])(ex(e+1)):e[1]?(*vd[e[1]])(a,ex(e+2)):(A)a;}
noun(c){A z;if(c<'0'||c>'9')R 0;z=ga(0,0,0);*z->p=c-'0';R z;}
verb(c){I i=0;for(;vt[i];)if(vt[i++]==c)R i;R 0;}
I *wd(s)C *s;{I a,n=strlen(s),*e=ma(n+1);C c;
DO(n,e[i]=(a=noun(c=s[i]))?a:(a=verb(c))?a:c);e[n]=0;R e;}
main(){C s[99];while(gets(s))pr(ex(wd(s)));}
I dared to update the code a little bit, originally it was using long data type, and was casting it to pointers, which are 64-bit these days. So I replaced it with long long to be able to run this code.
Yes, it looks weird to modern eyes. Even if we prettify the code with clang-format - we will still find that it uses old-school K&R coding style and it’s a miracle that this code is 30 years old and still works.
What does it do? Well, it’s an interpreter. Yes, it’s a tiny array programming language, like APL or K. It has certain limitations that we will discover later, but for now I invite you to the journey of deciphering this code.
Data types
As we are dealing with an array programming language, the only data type it supports is an array. Arrays may contain numbers, or other nested arrays, which is known as “boxing”.
typedef struct a{I t,r,d[3],p[2];}*A;
// or
typedef struct {
I t; // t=0: normal array, t=1: "boxed"
I r; // rank: number of dimensions
I d[3]; // depth: size in each dimension (up to 3)
I p[2]; // array data - numbers mixed with pointers
} *A;
As you can see, arrays are limited to only integer elements, may contain other arrays and may have up to 3 dimensions (linear vectors, rectangular matrices and 3-dimensional arrays.
The fixed size of 2 for data array was probably chosen to avoid dynamic memory allocation for single numbers (arrays of zero rank with one element). But I suspect it has not been used correctly (I might be wrong, though).
For allocating integer arrays there is a helper function “ma”, which only wraps malloc to allocate n integers:
I *ma(n){R(I*)malloc(n*8);}
// or
typedef long long I;
I *ma(int n) {
return (I *) malloc(n * sizeof(I));
}
For copying array elements there is a hand-written memmove:
mv(d,s,n)I *d,*s;{DO(n,d[i]=s[i]);}
// or
void mv(I *d, I *s, int n) {
for (int i = 0; i < n; i++) {
d[i] = s[i];
}
}
As you see, DO(n, op) is a macro to avoid numerous for-loops, that are untypical in the array programming nature.
Then goes a function to multiply dimensions in each rank (to get the total number of elements in all dimensions):
tr(r,d)I *d;{I z=1;DO(r,z=z*d[i]);R z;}
// or
I tr(I r, I *d) {
I z = 1;
for (int i = 0; i < r; i++) {
z = z * d[i];
}
return z;
}
It is commonly used before calling DO() to apply some operation to all elements in all dimensions of an array.
Finally, there is a constructor for the array type:
A ga(t,r,d)I *d;{A z=(A)ma(5+tr(r,d));z->t=t,z->r=r,mv(z->d,d,r);R z;}
// or
A ga(I t, I r, I *d) {
A z = (A) ma(5 + tr(r, d)); // tr() returns number of elements here
z->t = t;
z->r = r;
mv(z->d, d, r);
return z;
}
parser
Now I suggest to skip the part with many V1 and V2 functions, and jump to the end of the program, the main function:
main(){C s[99];while(gets(s))pr(ex(wd(s)));}
// or
int main() {
char s[99]; // maximum input line length
while (gets(s)) { // until end of input:
I *words = wd(s); // tokenize input
A result = ex(words); // evaluate words
pr(result); // print result
}
}
Yes, it’s a simple REPL (read-eval-print) loop, that we commonly see in every interpreter.
Let’s have a look at the parser (which is only a tokenizer in fact):
C vt[]="+{~<#,";
noun(c){A z;if(c<'0'||c>'9')R 0;z=ga(0,0,0);*z->p=c-'0';R z;}
verb(c){I i=0;for(;vt[i];)if(vt[i++]==c)R i;R 0;}
I *wd(s)C *s;{I a,n=strlen(s),*e=ma(n+1);C c;
DO(n,e[i]=(a=noun(c=s[i]))?a:(a=verb(c))?a:c);e[n]=0;R e;}
//or
// for 0..9 - return array with one number inside,
// otherwise return NULL.
A noun(const char c) {
if (c < '0' || c > '9') {
return NULL;
}
A z = ga(0, 0, 0);
z->p[0] = c-'0';
return z;
}
// for verbs ("functions") return their index+1 in the table vt,
// otherwise return NULL.
A verb(const char c) {
for (int i = 0; vt[i];) {
if (vt[i++] == c) {
return i;
}
}
return 0;
}
I *wd(const char *s) {
I n = strlen(s);
I *tokens = ma(n + 1); // allocate a token per char + 1
for (int i = 0; i < n; i++) { // for each char
if (noun(s[i])) {
tokens[i] = noun(s[i]); // one-digit number literals
} else if (verb(s[i])) {
tokens[i] = verb(s[i]); // verbs
} else {
tokens[i] = s[i]; // one-letter variables a..z
}
}
e[n] = 0; // null-terminate and return tokens
return e;
}
So the parser converts each and every character in the input line to either a noun (numeric literal from 0 to 9), a verb (a one-symbol function) or a variable (‘a’..‘z’). It’s very fragile so you should be really careful with the input.
Now as we have an input string converted into an array of tokens - we can evaluate them.
eval
Evaluator is recursive-decent, with right-side recursion (when right part of the expression is evaluated before the left one):
A(*vd[])()={0,plus,from,find,0,rsh,cat},
(*vm[])()={0,id,size,iota,box,sha,0};
I st[26]; qp(a){R a>='a'&&a<='z';}qv(a){R a<'a';}
A ex(e)I *e;{I a=*e;
if(qp(a)){if(e[1]=='=')R st[a-'a']=ex(e+2);a= st[ a-'a'];}
R qv(a)?(*vm[a])(ex(e+1)):e[1]?(*vd[e[1]])(a,ex(e+2)):(A)a;}
// or
I st[26]; // global variables 'a'..'z'
I qp(I a) { // is a letter (variable)?
return a >= 'a' && a <= 'z';
}
I qv(a) { // is a verb symbol?
return a < 'a';
}
A ex(I *e) {
I a = *e; // take the leftmost token
if (qp(a)) { // if a variable
if (e[1] == '=') { // ..assignment:
st[a - 'a'] = ex(e + 2); // evaluate right side,
return st[a - 'a']; // store and return
}
a = st[a - 'a']; // else: load variable
}
// "a" now contains the value, or a verb symbol
if (qv(a)) { // if a verb, it must be monadic
I *right = e + 1; // take the remaining expression
return (*vm[a])(ex(right)) // apply verb and return
} else if (e[1]) { // else, if something follows this token -
// it must be a dyadic verb
// apply it to current token and the one coming after the verb
return (*vd[e[1]])(a, ex(e+2));
} else {
return a; // else, return noun `a` as is.
}
}
Again, evaluator is completely intolerant to errors and expect only correct input. You see that right-hand side of the expression is always recursively evaluated first. That’s because in APL-like languages operators are always applied right-to-left.
If you are confused about “monadic” and “dyadic” verbs - these are merely functions with one (monadic) or two (dyadic) arguments.
So, once it is clear how evaluation works - let’s have a look at the actual verbs, that manipulate our arrays.
verbs
All verbs take an array or two and return another array, which is a result.
First, monadic verbs, there’s only five of them:
V1(id){R w;}
V1(size){A z=ga(0,0,0);*z->p=w->r?*w->d:1;R z;}
V1(iota){I n=*w->p;A z=ga(0,1,&n);DO(n,z->p[i]=i);R z;}
V1(box){A z=ga(1,0,0);*z->p=(I)w;R z;}
V1(sha){A z=ga(0,1,&w->r);mv(z->p,w->d,w->r);R z;}
// or
// Example: id([1,2,3]) -> [1,2,3]
A id(A w) {
return w; // simply returns the given argument
}
// Example: size([4,5,6]) -> 3
A size(A w) { // return size of the vector
A z = ga(0, 0, 0); // allocate result
if (w->r) { // if w has any rank (is a vector or matrix)
z->p[0] = w->d[0]; // return its first dimension
} else {
z->p[0] = 1; // otherwise, return 1
}
}
// Example: iota(4) -> [0, 1, 2, 3]
A iota(A w) {
I n = w->p[0]; // number of elements to cretae
A z = ga(0, 1, &n); // allocate vector of n elements
for (int i = 0; i < n; i++) {
z->p[i] = i; // fill array from 0 to n-1.
}
return z;
}
// Example: box([1, 2, 3]) -> [[1, 2, 3]]
A box(A w) {
A z = ga(1, 0, 0); // allocate a boxed array
z->p[0] = w; // put w into the boxed array
return z;
}
// Example: sha([1, 3, 4,
5, 6, 7]) -> [3, 2] (shape of the array)
A sha(A w) {
A z = ga(0, 1, &w->r); // create array to hold the shape of w
mv(z->p, w->d, w->r); // copy dimensions of w into result z
return z;
}
Obviously, in Arthur Whitney’s notation these verbs are compact and maybe even easy to read once you know what they are supposed to do.
Now, the dyadic verbs that operate on two arguments:
V2(plus){I r=w->r,*d=w->d,n=tr(r,d);A z=ga(0,r,d);
DO(n,z->p[i]=a->p[i]+w->p[i]);R z;}
// Example: [1,2,3] + [4,5,6] -> [5,7,9]
A plus(A a, A w) {
I n = tr(w->r, w->d); // how many elements in w
A z = ga(0, w->r, w->d); // create result of the same size
for (int i = 0; i < n; i++) {
z->p[i] = a->p[i] + w->p[i]; // sum elements pairwise
}
return z;
}
V2(from){I r=w->r-1,*d=w->d+1,n=tr(r,d);
A z=ga(w->t,r,d);mv(z->p,w->p+(n**a->p),n);R z;}
// Example: 1st from [4,5,6] -> 5
A from(A a, A w) {
I n = tr(w->r - 1, w->d + 1); // one dimension less
A z = ga(w->t, w->r - 1, w->d + 1);
mv(z->p, w->p + (n * (*a->p)), n); // copy all dimensions but the first one
return z;
}
V2(cat){I an=tr(a->r,a->d),wn=tr(w->r,w->d),n=an+wn;
A z=ga(w->t,1,&n);mv(z->p,a->p,an);mv(z->p+an,w->p,wn);R z;}
// Example: [1,2,3] cat [4,5,6] -> [1,2,3,4,5,6]
A cat(A a, A w) {
I an = tr(a->r, a->d);
I wn = tr(w->r, w->d);
I n = an + wn;
A z = ga(w->t, 1, &n); // works only with vectors!
mv(z->p, a->p, an); // copy a
mv(z->p+an, w->p, wn); // append w
return z;
}
V2(rsh){I r=a->r?*a->d:1,n=tr(r,a->p),wn=tr(w->r,w->d);
A z=ga(w->t,r,a->p);mv(z->p,w->p,wn=n>wn?wn:n);
if(n-=wn)mv(z->p+wn,z->p,n);R z;}
// Example: [2,3] reshape [1,2, [1,2,3,
// 3,4] -> 4,1,2]
// Also: [4] reshape [1] -> [1,1,1,1] (repeat)
A rsh(A a, A w) {
I r = a->r ? a->d : 1; // if has dimensions - first dimension, else - 1.
I n = tr(r, a->p); // length of the resulting array/matrix
I wn = tr(w->r, w->d); // number of elements in w
A z = ga(w->t, r, a->p);
I m = MIN(wn, n); // number of elements in w,
// if we don't have to repeat them.
// n otherwise
mv(z->p, w->p, m);
if (n != m) { // if we have to repeat...
mv(z->p+m, z->p, n); // as it copes left to right - it may
// repeat initial elements many times,
// until the length is n, as requested.
}
return z;
}
Finally, printing arrays. I will leave this without any comments, but instead will show the usage of the interpreter:
// pi(i) print an interger
pi(i){P("%d ",i);}nl(){P("\n");}
// pr(w) prints an array, first shape then data, "<" indicates boxing
pr(w)A w;{I r=w->r,*d=w->d,n=tr(r,d);DO(r,pi(d[i]));nl();
if(w->t)DO(n,P("< ");pr(w->p[i]))else DO(n,pi(w->p[i]));nl();}
And here’s the usage of the whole program:
$ gcc odetoj.c -o j
$ ./j
2 // numbers
2
2+3 // plus on numbers
5
2,3 // array of 2 elements - [2,3]
2 // shape = [2]
2 3 // data = [2,3]
a=2,3
2
2 3
a+4,5 // add two vectors
2
6 8
~4 // iota 4
4
0 1 2 3
~4+1 // iota (4+1)
0 1 2 3 4
a=~9
0 1 2 3 4 5 6 7 8
b=2,3
2
2 3
a#b // kind of:
2 3 // 0 1 2
0 1 2 3 4 5 // 3 4 5
2{b // 2nd from b
...and so on...
The interpreter is very limited, but still impressive. But APL family of languages itself is a remarkable part of computer science history, where Arthur Whitney plays a very significant role. I hope this lesson of computational archeology has proven it.
P.S. As I wrote this article - I was trying to rebuild this interpreter in Rust, with some minor improvements like proper number literals and less fragile handling of data. The result can be found at https://github.com/zserge/odetoj.
I hope you’ve enjoyed this article. You can follow – and contribute to – on Github, Mastodon, Twitter or subscribe via rss.
Mar 31, 2020
See also: cucu: a compiler you can understand (3/3) and more.
