Readable Code is Unreadable

J has an infamous prototype implementation called the J Incunabulum. If you click that link, you’ll immediately understand why it has the reputation it has.

I’d like to share why I now think this “unreadable” code actually communicates better than so-called “readable” code.

Let me be clear; on my first encounter with the J Incunabulum, I found it inscrutable. However, after having heavily steeped in APL for a few years, I just gave it a quick re-read and had a completely different experience.

Seeing the Forest

The code catches flack for it’s single-letter names and terseness, but it directly references bog standard APL and parsing concepts. What’s more important is that the code macro-structure is immediately apparent and clearly answers high-level questions up front.

What Are Our Basic Datatypes?

Right off the bat, Whitney tells us the kind of data we’ll be thinking about:

typedef char C;typedef long I;
typedef struct a{I t,r,d[3],p[2];}*A;

The first line gives us our main C types, and we can easily guess the second defines an array structure. Indeed, at a bare minimum, APL arrays need to encode type, rank, and shape metadata, telling us what t, r, and d are. Thus p points to our element data. Note that d probably stands for “dimension” or perhaps “depth”; I’m unsure on this point.

We also notice that d[3] says we only support up to rank 3, already signaling the explicit limitations chosen for this proof of concept. It’s not entirely clear why we have two p pointers, though. Let’s keep reading.

What Are Our Basic Operations?

Next we find the important fundamental operations we’ll be using to build our new array language:

#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*4);}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;}

Apparently, we’ll be printing and returning a lot, as expected. APL functions have fixed arity of one or two, calling the left argument ⍺ (alpha) and the right ⍵ (omega). Considering that J functions are called “verbs”, it becomes pretty clear that V1 and V2 are all the function prototypes needed for J primitives. Note the K&R-style definitions.

• DO defines our basic loop operation, so iterations will probably all naïvely be O(1);
• ma says we’ll be allocating 4-byte (i.e. 32-bit) chunks;
• mv essentially gives us a copy operation over chunks;
• tr or “times reduce” by inspection; and finally
• ga generates a new array.

All off these—except for tr perhaps—are clearly going to be useful. The 32-bit and data model assumptions here are a bit dirty, but we can forgive that in a proof of concept.

How About Using the Basic Operations?

Now that we know our basic toolkit here’s the implementation core!

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;}

All our basic functions, both dyadic and monadic, sit together in a single block. In fact, each of these definitions is brutally simple and explicitly elide array language features in service of architectural clarity. For example,

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;}

Even if you don’t know APL, one can guess what “plus” should do. We already know that V2 defines a new arity-2 function, and what’s the obvious way to add arrays? Just vector addition, i.e. element-by-element, right? Procedurally, we need to allocate an output array of the right size and then populate it with the result, one element at a time.

Now we see why we want the tr helper: it gives us the data element count of an arbitrary multi-dimensional array.

Also, as an APLer we immediately notice the elision of scalar extension. That can me modeled with rsh on the left argument, so we’re probably just defining some minimal subset of the primitive APL functions.

Other definitions all follow a similar pattern: 1) calculate the metadata for the result array, 2) allocate a result in the conventional name z, and 3) populate said array.

Notice, too, that find is not yet implemented. Curious. What else stands out?

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(id){R w;}V1(size){A z=ga(0,0,0);*z->p=w->r?*w->d:1;R z;}

These are the only branches we see, indicating intentional complications, and rsh (read “reshape”) is obviously the longest implementation. From experience, we know that reshape recycles elements when extending, and indeed it’s clear that’s what the if-branch takes care of—cleverly using a circular copy on z->p.

Also notable is the complete lack of error handling. We are clearly trying to laser focus on exhibiting core ideas here.

What About Output?

We have just a single datatype, so display is brutally simple:

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();}

There are no pretty print facilities, but rank, element data, and recursive nesting are the bare minimum needed to fully understand array contents. This is all that is needed to get up and running.

What About Parsing?

First we setup a vtable that contains our implementation functions:

C vt[]="+{~<#,";
A(*vd[])()={0,plus,from,find,0,rsh,cat},
 (*vm[])()={0,id,size,iota,box,sha,0};

Each J verb has three pieces of data: 1) its glyph, 2) its dyadic definition, and 3) its monadic definition. We use a standard APL technique of storing this data in a column-major table. The vt column names the verbs (via their glyphs), vd maps dyadic usage to it’s vtable function, and 3) similar for monadic usage with vm.

Nothing special, but clear and direct. In particular, this means that a verb’s “ID” is its table offset.

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;}

Both qp and qv are obvious predicates (q for “query”?), and we can see that ex is calling functions in our vtable. This is obviously the executor. It even supports =, which stores values in st. The one-to-one map between alphabet characters and st indices is nice and minimal. We only allow single-letter names, probably enough for small language experiments.

If we’re not an =-definition, though, then we execute. APL’s function precedence rule makes this dead simple: just right-recurse. The only question is whether we’re a dyadic, monadic, or “niladic” application. The nested digraph here creates this obvious trident branch structure.

What About Input?

After a cool three dozen SLOC, we conclude our J interpreter:

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)));}

At this point, the patterns are familiar. noun and verb do the obvious things, wd creates our token stream, notably only supporting single character tokens, and main reads exactly like R-E-P-L (well, in reverse).

Points of Note

The overall code is organized in a top-down manner. Our audience here is APLers who know a thing or two about language implementation. It makes sense to lead with high level ideas, and the code exactly mirrors this structure. We literally read the code linearly top-to-bottom just like a short whitepaper. That’s great communication, IMHO!

As mentioned offhand above a few times, the particular limitations chosen serve to clarify the presented message. It’s not about implementation shortcuts. Consider that we imposed

• Single-character tokens only;
• No Spaces;
• No parentheses to control order of operations;
• No array literals;
• No scalar extension;
• No function definitions;
• Limited rank;
• etc.

What purpose did these concessions serve? Why not more?

Look at rsh. It would clearly be simpler to remove the final conditional that allows circular extension. Given all the other limitations, why not add another? Well, this would make the domain of inputs to rsh special and different from the other functions. That complicates the conceptual model.

J didn’t exist when the Incunabulum was written. It was an idea. Iverson, Whitney, and Hui were trying to discuss and discover what a new APL language could look and feel like. The Incunabulum is a single page of code that presents tools to concisely express the salient ideas in that design space—array model, usability of ASCII glyphs, leading axis theory, etc.

With that goal, poking at things like fancier array literals or parentheses support feels like bikeshedding. The rank cutoff is arbitrary but trivially changeable; none of the code depends on a specific cutoff.

Function definitions are interesting from a language design perspective. Worrying about scope and closure support introduces questions about syntax. We could easily directly store token vectors easily enough, but this complicates the recursion in ex. All-in-all, these are questions somewhat orthogonal to the others.

I’ll stop there…

What is most interesting, IMHO, is that all the above comes across in short 20-odd minutes of reading this supposedly “inscrutable” code. What more could one ask for?

What about find?

Out of curiosity, I threw together a plausible Whitney implementation:

V2(find){I r=w->r,*d=w->d,n=tr(r,d),j=n;DO(n,if(a->p[0]==w->p[i])j=i);
 A z=ga(0,1,&w->r);DO(r,z->p[i]=(j/(r==1?1:tr(r-1-i,d+1+i)))%d[i]);R z;}

which is a bit subtle and certainly the most complicated logic in here. It works fine for simple integer arrays, but boxes compare as pointers. Recursive comparison of contents might make more sense. Apparently, find opens a whole design question about what array equality even means.

Maybe all these factors contributed to find remaining unimplemented, or maybe Whitney just ran out of time!

Epilogue: Getting Compiled

It’s fun to play around with this little implementation. I definitely recommend compiling it yourself and giving it a little test drive.

Due to the K&R function prototypes, modern GCC will need the -ansi or -std=c89 flag. Also, as noted above, the code assumes a 32-bit architecture in one place. We could cross compile, but the easiest workaround is a simple patch:

--- a/inucabulum.c
+++ b/inucabulum.c
@@ -5,7 +8,7 @@
 #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*4);}mv(d,s,n)I *d,*s;{DO(n,d[i]=s[i]);}
+I *ma(n){R(I*)malloc(n*sizeof(I));}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;}

It’ll spit out some builtin-declaration-mismatch warnings, but those are immaterial here.

Site proudly generated by Hakyll