APL Compiler Based on Tail (Typed Array Intermediate Language) | Hacker News Reader

APL Compiler Based on Tail (Typed Array Intermediate Language)

github.com

62 pointsxvilka13 comments

For anyone interested in this kind of stuff, I wrote my own Vector Virtual Machine (VVM) as part of the Empirical project [1]. It has statically-typed vector-aware opcodes. It uses register addressing (inspired by LLVM), has a linear IR, and is implemented with tricks like computed gotos.

I designed VVM to have extremely fast dispatch. It already exists on top of a vector-aware runtime, which means that a single dispatch works over an entire array. But grouped aggregations require multiple dispatches, one per unique key in a Dataframe. For example:

  from trades select volume = sum(size) by symbol

I wanted to hit the runtime repeatedly with as little overhead as possible. So VVM has no type look-up, multiple operands per instruction, and a cache-efficient IR. The sum() operand for the above example is invoked directly in a loop almost as fast as hand-written C++.

VVM has its own assembly language [2]. I have blog post that explains some of the design choices [3].

[1] https://github.com/empirical-soft/empirical-lang/tree/master...

[2] https://github.com/empirical-soft/empirical-lang/tree/master...

[3] https://www.empirical-soft.com/2020/09/03/a-tour-of-the-vect...

I imagine many people are reading this with the assumption that compiled APL is obviously the next step for the language (APLers say it's fast, but it's interpreted—compiled APL must really be something!). Compiled APL is cool and all, but the performance picture is more complicated than it is for, say, Python.

This is because, in high-performance interpreters, the arrays have element types that are tracked automatically, providing many of the advantages of C-like compiled languages at a fixed cost per array operation. In fact, these element types can be more accurate by dynamically adjusting to the data: with a table of unknown size the C programmer must declare indices as a 64-bit type, while APL could detect at runtime that only 16 bits are needed. APL also benefits from the higher-level notation, in that it's easier for a human to write a fast implementation of a particular operation than a compiler that can generally optimize code including that pattern (with TAIL this might not be so bad). I discussed the Replicate (like filter) operation in my talk The Interpretive Advantage[0]. Another page I wrote where you can read about array performance is [1].

APL compilers are needed in order to run code on a GPU (but if you have code that's well-suited to a GPU, it's going to be pretty fast on a SIMD CPU too). And for ML and scientific applications that work with floating-point types, the drawbacks of ahead-of-time compilation are much smaller. I think for truly general-purpose computing the best approach will be to unify interpretation and compilation, combining small groups of primitives and deciding how to run them as data becomes available. Both interpreted and compiled approaches are important in reaching this peak.

[0] https://dyalog.tv/Dyalog18/?v=-6no6N3i9Tg

[1] https://aplwiki.com/wiki/Performance

This sounds like APL would benefit from a JIT runtime, which is a well-established technique in other performance-focused languages. You get all the benefits of tracking types and other data at runtime while also gaining the benefit of a compiled language.

Yes, the idea described in the last paragraph could be called an array JIT. Much like a static APL compiler requires specialized type and shape handling, an APL JIT would need some new techniques for deciding when to compile things, what assumptions to make, and how to check them.

My more detailed notes are at https://mlochbaum.github.io/BQN/implementation/compile/dynam....

I have been very interested in this project, but I have not had time to implement it in my workflow. Particularly a project that was on my radar several years ago, but it seems to have lost momentum is tail2futhark[1], a way of compiling APL via tail into futhark for easier gpu programming from APL. I love array languages, and J was my first, followed by APL, and a bit of k. I am noticing a lot of uptake of the array languages this year based on YT content and traffic on the usual array hangouts. In trying to make APL my primary PL, I have been playing with April[2], a subset of APL in Lisp, another old favorite PL. It is a blast. I am honing both my Lisp and APL skills, and they seem to cover each other's weaknesses for easier adoption in the general programming world.

[1] https://github.com/henrikurms/tail2futhark

[2] https://github.com/phantomics/april

Do you have any examples of TAIL code? I'm interested in using it as a target for the compiler class I teach

The author of the project is a professor of programming languages at the institute of datalogy (DIKU), Copenhagen University.

I suggest connecting directly to DIKU for academic matters.

They are doing other interesting work on array based programming:

Futhark, a related data-parallel functional array language that compiles to GPU code and easily integrates into Python code is another interesting project from there.

Written in Standard ML by the author of the Standard ML implementation, MLKit. Very nice!

On a regular keyboard, how would you type in the examples?

Linux has a built-in keyboard that's easy enough to configure in your DE or with an X keyboard toggle.

Dyalog has some introductory documentation on how to set up the mappings. https://www.dyalog.com/apl-font-keyboard.htm

If you want to type something very small, you could also go to tryapl.org and use the on-screen keyboard and copy and paste.

If you want to work with APL, you probably want to install the free APL fonts and keyboard mappings from Dyalog at https://www.dyalog.com/apl-font-keyboard.htm

If you just want to play around with it, you might try https://tryapl.org/

Usually digraphs or special keyboard maps are used.

See https://apl.wiki/Typing_glyphs

Reply on news.ycombinator.com