APL/J/K: The Array Programming Lounge

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > APL/J/K: The Array Programming Lounge

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

APL and its descendants form an obscure but powerful family of programming languages. They permit writing extremely concise programs, often expressing in a few characters what more conventional languages would take dozens of lines to say. They eschew explicit loops, conditional statements and recursion- typically the bread and butter of programming- in favor of high level built-in operators and functional abstractions. The resulting style of programming is naturally highly parallel and can be easy to optimize. At the same time, the cryptic symbiology, excessively dynamic type systems, heavy operator overloading and relative lack of accessible information can make these languages very hard to approach. Let's learn about Array languages and share our experiences.

The three most prominent languages in this family are, in order of creation, APL, J and K:

APL
APL was designed by Kenneth Iverson in the late 60s. Originally it was meant to be a concise handwritten notation for describing algorithms which unified the notations for vector and matrix arithmetic, logic and set theory, laid out in a book titled A Programming Language. APL introduced a set of special symbols as part of its notation which initially posed some challenges for typesetting and distribution. Notably, the symbols used by APL for "floor" and "ceiling" are now commonplace in mathematics.

After teaching with this notation for a number of years, an effort began to implement an interpreter for a simplified form of the notation. In the decades since, APL interpreters have absorbed ideas from functional programming (first-class functions, particularly) and object-oriented programming.

Find prime numbers between 1 and R:

quote:

(~R∊R∘.�R)/R←1↓ιR

Compute rows of Pascal's Triangle:

quote:

Pascal←{0~�⍨a⌽⊃⌽∊�0,��a∘!�a←⌽⍳⍵}

The Game of Life in APL:
https://www.youtube.com/watch?v=a9xAKttWgP4

A Sudoku solver:
https://www.youtube.com/watch?v=DmT80OseAGs

J
J was a later effort by Iverson which dispensed with a special character set in favor of ASCII digraphs. It features an extremely rich set of mathematical datatypes (arbitrary-precision, rationals, imaginary numbers, etc) and operators. It also includes some features which are largely unique, such as "forks" for expressing complex tacit expressions (expressions which contain no named variables).

Calculate the arithmetic mean of a list of numbers:

code:

avg=: +/ % #

Problems 3, 5 and 6 from Project Euler as oneliners:

code:

>./q:600851475143
*./>:i.20
(([:*:+/)-[:+/*:) >:i.100

J was initially commercial and struggled with adoption, but is now open-source. Check out the extensive manual, and boggle at the cryptic one-pager which formed the nucleus of J's early implementation!

K
K was developed by Arthur Whitney while working at Morgan Stanley, and is now sold commercially by Kx Systems, inc. It feels like a hybrid of APL and Scheme, radically simplified and with a well-earned reputation for being surprisingly fast. K1 was an internal project, K2 was the first independent commercial release, the K3 dialect is targeted by the open-source re-implementation Kona, K4 is the current commercial release, bundled inside kdb+, a high-performance in-memory database. Today, K is used extensively in high-frequency trading applications but is virtually unheard of outside finance and code-golf.

Calculate the arithmetic mean of a list of numbers:

code:

{(+/x)%#x}

Decompress run-length encoded data:

code:

,/#/'

Calculate the first 10 terms of the look-and-say sequence:

code:

10{,/{(#x;*x)}'(&~~':x)_x}\,1

K5 is Arthur's bleeding-edge, next generation K dialect. I was inspired by rumors and the scant publicly available information regarding K5 to write my own implementation, and the results still aren't great yet, but they're oK. I've also tinkered with a system called iKe, which adds IO facilities that make it possible to write fun graphical programs:

code:

point: {(y;pn[f%20;0.3*x;0.1*y]*-18*sin y*pi%100)}
line:  {((30;x)+)'point[x]'!100}
draw:  {,(,/line'38+6*!16;cga;1)}

Feel free to discuss APL, J, K and other related languages. If you've never tried programming in this style before, why not give it a spin with one of these browser-based interpreters?

APL - TryAPL.org
APL - NGN APL (github)
J - Emscripted J
J - J.js
K5 - oK (github)

Internet Janitor fucked around with this message at 17:00 on Dec 13, 2015

# ¿ Dec 1, 2015 21:17

Adbot: ADBOT LOVES YOU

# ¿ May 10, 2024 06:09

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Personally, K is my favorite of the three and the one I found easiest to learn. Fluency in APL requires relearning how to type (or using a special editor), J's use of unbalanced brackets and lots of digraphs makes it tricky to learn to read. K syntax is very simple, regular and familiar in comparison.

Unfortanately K also has the fewest high-quality introductory materials available, in no small part due to its proprietary history. You must be mindful of the dialect you're working with, as some operators behave quite differently between, say, K2 and K4. Here are a few materials worth reading if you're up for it:

A suitably brief introduction to K, by Arthur Whitney
K, Remarks on Style
The K2 Reference Manual - out of date, but much of this still holds true in newer versions of K
K as a Prototyping Language
I wrote a reference manual and a programming techniques guide based on my research into k5, to go along with oK. They might be useful to someone.
No Stinking Loops is a treasure trove of interesting code.

# ¿ Dec 1, 2015 23:59

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Athas: fyi, APL symbols don't seem to work in code blocks. They work in quote blocks, though.

As far as open-source K implementations go, I think Kona and oK are the only ones in existence. There are a handful of "K-like" languages out there, though. For example, Klong.

# ¿ Dec 2, 2015 17:55

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Great writeup, Cybernetic Vermin!

I haven't worked with kdb+ myself, but it seems very expressive. How often do you find yourself writing entire programs against it, and how often do you simply use it as a way to interactively explore datasets? It seems to me that treating the language as a user interface is a strong argument in favor of the syntactic brevity of k/q/ksql.

I just found an excellent talk about J which could serve as a decent introduction to the language and the style of programming with APL-family languages:

https://www.youtube.com/watch?v=IKfJRyoiBlY
Karl Hoijarvi, Array Algorithms and J

# ¿ Dec 2, 2015 21:36

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Lately I've been making many additions to iKe, including vector drawing and audio output. Click on any of these GIFs to run the program for yourself. The X box in the top right lets you see the source and try tweaking it.

Panning around a hyperbolic projection of a grid:

A Lindenmayer-System visualizer:

A simple musical keyboard:

A chiptune music player:

Another interesting find is this OCaml implementation of K2. It's a bit unclear how much is implemented currently, but neat to see an interpreter in something radically different from C!

# ¿ Jan 13, 2016 18:42

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I think the operator you're looking for is &- "where".

code:

  &1 0 0 1 0
0 3

Given a boolean list, it gives you a list of the indices of the 1s. Let me know if that's enough or if you'd like any additional hints.

In unrelated news, I published a paper about iKe in Vector.

# ¿ Jan 23, 2016 03:17

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

One way is to store an intermediate value in a variable:

code:

t@&{0=x!2}(t:fib 5)

Downside is this leaves the temporary sitting around in the global scope. The alternative is to use lambdas whenever you need to rearrange or copy values:

code:

{x@&{0=x!2}x}(fib 5)

Simplifying,

code:

{x@&0=x!2}(fib 5)

Finally, some surface-level simplifications. The parens around the call to fibs is not necessary, and 0= is equivalent to simply negating with ~:

code:

{x@&~x!2}fib 5

In k5 this composes even more nicely because the arguments of mod are reversed and, as you mention, # can be used to filter. It is essentially {y@&x'y}.

code:

(~2!)#fib 5

# ¿ Jan 23, 2016 17:50

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Oh, that's a common gotcha that tripped me up several times-

In older versions of K, underscores were allowed as part of identifiers. By convention, built-in functions were often prefixed with an underscore. However, the underscore is also a primitive function (drop/cut/floor) so this leads to ambiguity. In Kona, adding a space after the underscore will probably do what you want:

code:

{x%/:1+/:!_ x^.5}

In k5 (and oK) underscores are no longer allowed in identifiers, but ^ has a different meaning (in this context it's "except"). The error you see is an internal error in the implementation of "odometer", which I have now made a note to correct. Clicking on red error messages in the oK repl will reveal the JS stack trace, which sometimes gives a useful hint about what went wrong.

Internet Janitor fucked around with this message at 18:04 on Jan 24, 2016

# ¿ Jan 24, 2016 18:00

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Found a fun paper:

Language as an Intellectual Tool: From Hieroglyphics to APL.

It discusses the origins of mathematical notation and in so doing provides some rationale for why APL was designed the way it was.

# ¿ Mar 9, 2016 05:01

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I recently obtained a copy of k6, the successor to k5, and I've begun studying it. I'm recording my findings in preparation for moving my interpreter toward supporting this new dialect.

Man, I'd really love to attend KxCon, but it's rather far away and I don't think I could afford it.

# ¿ Apr 28, 2016 05:29

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Rhusitaurion posted:

Using a single numeric type (doubles only I guess?) is an interesting choice, not sure how I feel about that.

Currently k6 does distinguish between ints and floats if you inspect the typecodes with @, so the implications of this choice seem to be more that ints and floats will coerce to one another in more situations and if the interpreter does something special under the hood as an optimization the programmer need not concern themselves with it. The major change here is the banshment of various subtypes, like "boolean ints" that are restricted to 0 or 1, shorts, etc. as distinct numeric types. In oK using doubles for everything hasn't produced any particularly weird problems, but then again I'm mostly applying it to toy problems.

# ¿ Apr 30, 2016 05:15

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Fun little iKe demo:

Noyemi K observed that my manhattan-distance voronoi diagrams resemble subway schematic diagrams, and was interested in trying to apply this technique to generating content for a game. I developed a simple alternative algorithm which also produces appropriate shapes: do a series of drunkard's walks radiating from a centerpoint and making turns in 45 degree increments. I think the results are reasonably convincing. It's great fun to tinker with the parameters of the simulation to see what you can come up with.

code:

t: pi%4                / turn angle
g: 10                  / step distance
s: 8                   / simulation steps
d: {8!x+*-1+1?3}       / new direction
p: {y+g*(cos x;sin x)} / new position
m: {d[x],p[x*t;y]}     / take a step (dir, pos)

wander: {s{m[*x;1_x]}\(*1?8),0 0}          / create one path
asline: {x,|x}80+1_'                       / center path and convert to polygon
subway: {20{(asline wander[];1?arne)}\()}  / render paths with random colors

/ generate a map when a key is pressed:
v: subway[]
kd: {v::subway[]}
draw:: v

Try it here.

# ¿ May 13, 2016 07:21

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Fun with Poisson Disk Sampling:

code:

spread:   10 / minimum distance between points
density:   1 / how many points per round (>1 produces clumps)
rounds:  200 / how many times do we expand the set

annulus: {(spread;2*pi)*1 0+?2}                      / ring around origin
p2c:     {x*(cos y;sin y)}                           / (radius;angle)
around:  {(x+p2c.)'annulus'!density}                 / nearby points
dist:    {%+/'{x*x}x-/:y}                            / (center;points)
more:    {x,({spread<&/dist[y;x]}[x])#around[*1?x]}  / expand point set
poisson: rounds more/,80 80

,(poisson;cga;1)

Try it here.

Still a fair bit of room to simplify this one, I think.

# ¿ May 25, 2016 03:59

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Just watched a great introductory talk about Q and array programming in general:

https://www.youtube.com/watch?v=ZGIPmC6wi7E
Tim Thornton - Data Analysis with Vector Functional Programming

# ¿ Jun 12, 2016 21:46

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Fun side note: my goofy K projects gained enough recognition to land me an interview with a large consulting firm whose backend systems are written in K.
The interview experience itself was, to put it mildly, surreal in the best way. I'm now in the process of relocating to NYC to start a new job there.

So, uh, I guess the lesson here is occasionally weird side projects can result in unexpected new career paths? :unsmith:

# ¿ Jun 13, 2016 06:55

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Suspicious Dish posted:

are you also going to be doing their internal newsletter, drawing the eldrich horror that is K itself?

Will neither confirm nor deny.

# ¿ Jun 13, 2016 17:09

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I'll be sure to check out that J meetup, SFF- thanks for the heads-up.

As for matrix multiplication I think the K formulation is pretty easy to explain. To begin with, dot product is very simple: the sum of multiplying two items. This works equally well for vectors or matrices thanks to K's conforming rules.

code:

dot: {+/x*y}

Given this definition, a matrix multiply is simply the composition of the dot-product with each-left, so you will take the dot product of each row of the left matrix with the entire right matrix.

code:

mmul: {x dot\:y}

Excerpting from an oK trace:

code:

  \x mmul[(1 2 3;4 5 6); (7 8;9 10;11 12)]

First application of dot product:

code:

        (7 8       (7 8
         9 10       18 20
1 2 3 *  11 12) ->  33 36)

   (7 8      
    18 20    
+/  33 36) -> 58 64

Second application of dot product:

code:

        (7 8       (28 32
         9 10       45 50
4 5 6 *  11 12) ->  66 72)

   (28 32    
    45 50    
+/  66 72) -> 139 154

Bringing it all together:

code:

                       (7 8      
(1 2 3                  9 10      (58 64
 4 5 6) {[x;y]+/x*y}\:  11 12) ->  139 154)

# ¿ Jun 13, 2016 18:33

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Athas posted:

Why do they make it so hard to try it out?

I've had a conversation to this effect with a number of K programmers, as well as discussing the need for more accessible documentation, and the response is basically, "eh, people will find vector languages on their own; they always have." It's a bit frustrating. The main thing I'm learning is that the isolation and obscurity of these language communities is at least partly intentional.

# ¿ Jul 2, 2016 02:11

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Ever wanted a pocket calculator that could understand K expressions?

...No?

Well, er... you can have one anyway:

Try it live- I've mainly tested the layout on my iPhone SE, so on larger devices it should still be usable. If the window/browser has a landscape aspect ratio it will instead display a full keyboard. Still tinkering a bit with the layouts. The pl and ps functions are extensions for this oK frontend which plot a line graph or plot a scatterplot, respectively, because it just didn't seem complete if it couldn't function as a graphing calculator.

Internet Janitor fucked around with this message at 18:34 on Oct 16, 2016

# ¿ Oct 16, 2016 18:32

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

The K2 Reference Manual is a bit out of date (kdb+ ships on top of K4), but largely still relevant, and it's fairly exhaustive and well-written. I used it as my primary reference when writing the initial revision of oK.

edit: Unrelated, but I've done a bit of work on oK Mobile recently- see the docs for details on spiffy new features. I'm pleased to note that several of my coworkers have started using it as a desk calculator.

Internet Janitor fucked around with this message at 00:51 on Dec 23, 2016

# ¿ Dec 23, 2016 00:47

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Happy holidays, everyone.

# ¿ Dec 25, 2016 15:46

Adbot: ADBOT LOVES YOU

# ¿ May 10, 2024 06:09

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I've been tinkering with parsing techniques lately, culminating in writing a parser combinator library in K. I may try using a similar approach in JS to simplify oK's parser.

Here's a parser for Bencode:

code:

digits:  plus oneof "0123456789"
number:  prod[seq(option lit "-";digits);.,/]
bstr:    nof[prod[seq(digits;lit ":");.*:];anychar]
bint:    prod[seq(lit "i";number                 ;lit "e");{x 1}]
blst:    prod[seq(lit "l";plus`bencode           ;lit "e");{x 1}]
bdict:   prod[seq(lit "d";plus seq(bstr;`bencode);lit "e");{!/+x 1}]
bencode: choose(bdict;bint;blst;bstr)

I'm really happy with how compact and straightforward this comes out.

# ¿ Mar 18, 2017 04:14

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > APL/J/K: The Array Programming Lounge