April, an APL Compiler for Common Lisp [video] | Hacker News Reader

April, an APL Compiler for Common Lisp [video]

youtube.com

103 pointstosh23 comments

Since the video's quite long, here are some basics on April.

Repo: https://github.com/phantomics/april

April compiles APL to Common Lisp. It has almost all of the lexical functions and operators featured in Dyalog APL, the leading commercial APL interpreter and the most featureful APL implementation. It has many more features than the FOSS GNU APL, which is based on the old IBM APL2.

Dyalog APL's source code is about 500KLOC according to Dyalog's staff. GNU APL is over 100KLOC per its homepage. April's .lisp files currently stand at 6350LOC.

APL interpreters have traditionally been hard to connect to external data sources. Because APL is typically implemented as an interpreter, any connection to a database or other external system needs to be built into that interpreter as a plugin. April is called from within a Lisp program and you can pass it any array-formatted data. You can use CL libraries to read from any database or other source, format the data as an array and pass it to April for processing.

April takes some features from the k language, including ($[oneorzero;1;0]) if-statements and (g←{[a;b;c]a+b×c} ⋄ g[1;2;3]) n-argument functions.

April is extensible - you can easily create an extension to the language with more functions and operators, and you can also re-implement the utility functions that are used to parse and compile the language. The language is designed from the ground up to support extension. There is also a framework to extend the compiler to optimize common idioms, for instance ⊃⌽,200 200 200⍴⍳9 is optimized to just fetch the last row-major-ordered element of the big array instead of actually taking the time and memory to ravel and reverse it.

The second half of the video features a preview of a hardware startup called Bloxl that's powered by Common Lisp and April. Bloxl is a big transparent block wall with LEDs inside the light up to create pixel graphics. April was used to build the animations that run on Bloxl.

> any connection to a database or other external system needs to be build into that interpreter as a plugin.

Guess: that could be the general area where Dyalog is burning most of its alleged, monstrous 500 KLOC.

> Dyalog APL's source code is about 500KLOC according to Dyalog's staff. GNU APL is over 100KLOC per its homepage. April's .lisp files currently stand at 6350LOC.

What accounts for this discrepancy?

-Common Lisp vs C/C++

-April implements the language and just punts to CL for all the I/O and system level stuff. Like it doesn't have to implement a REPL, or a line editor or APL workspace files/array stores.

Thanks. I'm guessing (based on my knowledge of J and all its optimizations/special forms) that Dyalog APL would still be more performant too? I didn't see it mentioned on the GH README.

Yes, the talk mentions that Dyalog is still much more performant, given how much time and effort has been spent on optimizing it.

A ways into the video it says the core Dyalog interpreter is about 100KLOC, with the rest being GUI code and interop such as file handling and formats, cross-platform support, .NET interop, and so on. If the 100k figure surprises you then what you are missing is just how deep array optimization is. For example, searching through an array will use an SSSE3 table lookup for 1-byte elements, a different table for 2-byte elements, and several different kinds of hash tables for other types. I tried to give a sense of the scale of this sort of thing in the first slide of my Dyalog '19 talk on Reductions (https://www.youtube.com/watch?v=TqmpSP8Knvg). You can write pages and pages of code and still there will be a way to speed up a common operation substantially.

By working on multidimensional arrays, APL expands the range of computations that are accessible to optimization. I think the writer of a scalar compiler like C would generally be happy making a single loop as fast as possible. APL immediately makes the implementer think about what happens if there are many axes (each of which is equivalent to a nested loop) even if the later axes (inner loops) are small.

Thanks for posting my presentation, April's been great fun to write.

Any sufficiently complicated Lisp program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of APL.

Arrays > lists, just ask your CPU's D$.

call me back when you decide to use APL to create a logic program that dynamically generates an expert system engine based on analyzing the meta-structure of an input factset, with an instrumentation layer that reasons about the generated system characteristics

until then, I'll call it a truce :)

This is something I go over in the video - an alloy of Lisp and APL works better than either language by itself.

Lisp excels at creating semantic and logical patterns. Macros allow you to build reader-friendly data structures that transform into working code. In the April repo, check out spec.lisp which expresses the top-level spec for the language. Most language implementations don't have this kind of centralized, readable spec where all the language's features and conventions are laid out in one file. The unit tests in this file even constitute a demonstration of what each function and operator does.

APL is for writing algorithms. Data transformations that would take pages of code in other languages can be accomplished with one line of APL. It's trivial to do things like find the color palette of an image and create a copy of the image with another color palette swapped in. Signal processing, machine learning and similar tasks are a snap.

When I created the animations for the Bloxl device, I created a Lisp-based spec for animations with bits of embedded APL. Most animation effects are standardized and have Lisp functions implementing them. However, many patterns have unique algorithms used to implement effects just for that pattern. If I were using Lisp, I would have two choices as to how to do this:

1. Write the unique code into the spec for each pattern, bloating the animation specs with tons of loops to create the special effect. An individual animation spec may go from 12 lines to 60 lines or more doing this.

2. Write a function to implement the special effect. All the special effect functions would have to go into another file somewhere. The animation packages would become bloated with many functions that are only used in one place.

Instead, I can implement the unique effects in APL. It only adds one more line to the spec and avoids both kinds of code bloat described above.

Is there an example of this? I might have seen that recently.

Misses speech impediment yoke by not calling it Aplil

Without watching the video, can we guess correctly that "for Common Lisp" means "in Common Lisp"? Or is it really meant for use within Common Lisp programs?

April is usable within Common Lisp. When writing a CL program, you can invoke APL code on arrays. For example:

(april-c "{⍴∪,(3⍴2*8)⊥3 1 2⍉⍵}" (opticl:read-png-file "/path/to/image.png"))

This snippet uses the opticl library to load a PNG file, and then uses April to count the number of unique colors in the image. Consider the amount of code this would take in CL.

It would be cool if it was implemented as a reader macro instead of just passing a string to a function.

Wouldn't be too hard to do, someone in the video suggested a #⎕ reader macro followed by APL. Like take '#⎕string' then expand that to '(april "string")'.

But April has many ways of passing options and external data for the compiled code to operate upon, and implementing a reader macro system that would support all those parameters would be complicated and require developers to learn a bunch of new syntax in order to use April with reader macros.

Do it yourself! (Implementation loosely based on phantomics' comment below.)

    (defun april-reader (stream char)
      (declare (ignore char))
      `(april ,(read stream t nil t)))
    
    (set-macro-character #\⎕ #'april-reader)

You're probably gonna want something more complicated than that. Glancing at the github page it looks like at least the following need to be dealt with:

  (april "apl code") ; and april-f
  (april (with (stuff)) "apl code") ; and april-f
  (april-c "apl code" (input))
  (april-c (with (stuff)) "apl code" (input))

Yes, the above is a trivial implementation; handling multi-form input would need to be much more complex. Thankfully, for simple one-liners, you'll likely want either April literals (implemented above) or April anonymous functions, both of which won't take additional arguments; you should be able to implement both as simple reader macros.

Another option is to load APL source from a file.

(april-load #P"/path/to/code.apl")

Then you can have files of pure APL code with no Lisp hanging around.

> Consider the amount of code this would take in CL.

I don't really read APL - but isn't this just a map/reduce over the pixels? - maybe (length (remove-duplicates 'pixel-data)) or some such?

The pixels aren't singular values, the image is a height×width×3 array of 8-bit integers. The third dimension is the three RGB values for each pixel. The bulk of the string, the "(3⍴2*8)⊥3 1 2⍉⍵" part, converts the array into a height×width matrix of 24-bit integers representing the colors. Once you have a matrix M, "⍴∪,M" is all the code needed to count the unique values.

Reply on news.ycombinator.com