An Implementation of J

Roger K.W. Hui

A Dictionary of APL 0

A discussion of an implementation of J must begin with A Dictionary of APL. I started studying it at around 1984. It is full of insights and details on how to implement an APL interpreter.
 

A Dictionary of APL 1

In particular, Table 2 provides a model in APL of how to parse an expression. There is executable code, and there is a table. (It takes some study to realize that you are looking at a table.) To me, the more valuable part is the parse table because it defines the syntax of the language; the executable code is only to help understand how the parse table worked.
 

The One-Page Thing 0

One summer weekend in 1989, Arthur visited Ken 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 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 J.

Years later, talking about “the one-page thing”, Arthur said that he still wanted to write it in one page, but using n-point font. (The value of n increases with each retelling of the story.)
 

The One-Page Thing 1

Many C programmers object to this programming style; in particular, they object to this use of macros. The current J implementation has these exact or similar macros (and many others). The F1 F2 etc. macros define the declarations and prototypes of functions that apply to array arguments and return array results. I will say more about the DF1 and DF2 macros later.

ASSERT is one of my favorite macros. The little character “!” (not) allows conditions to be stated in a positive sense, e.g. 1>=AR(w) must be true, else signal rank error.

These macros and typedefs are used over 10,000 times in the J interpreter. A C programmer told me that an objection to the programming style is that he must look things up in order to understand the code. But look, if you look up F1 and understand it, you’d understand 839 things.
 

Parsing 0

I consciously designed and built the system around the parse table. The C data and program structures were designed so that the parse table in C corresponded as directly as possible to the parse table in the dictionary. I set an objective of being able to show Ken the C source for the parser, and have him verify that the syntax being implemented was correct.
 

Parsing 1

We never did carry out the exercise (of Ken reading the C source), but I reckon I met my objective, because eventually Ken replaced the parse table in the J dictionary with the parse table from the C source. Other effects of trying to meet the objective were entirely beneficial.

In the parse table, the first two of the three numbers in each row correspond to the ↓↓↓ (down arrows) in Table 2. The last number tells the interpreter where to put the “caret” in case of an error.
 

A

typedef A defines an array. It is pretty standard: a header followed by the ravelled values. The value is “cast” to an appropriate type.

What is not so standard is that everything in J has type A , including verbs, adverbs, and conjunctions.
 

V 0

For such guys the value part is cast to be type V . An example hopefully makes it clear.
 

V 1

The verb is the fork +/ % # .  Each verb has the standard type A header. The value part cast to type V has: C function pointers to the monad and dyad; the left/right/fork operands; some bit flags; the ranks; function call depth; and the symbol. The data structure is a DAG (directed acyclic graph), because the operands are themselves a similar structure.

From within J there are facilities (5!:x) for looking at a terse version of this information.
 

V 2

Should it be desirable to implement special code (as for example in the case ,/), replace the function pointer by a pointer to the new C function. Everything else stays the same.
 

V 3

The DF1 and DF2 macros enforce the fact that derived verbs are invoked with an extra argument, the data structure we’ve been looking at.

This is how tacit definition was invented.
 

References