Array languages for Lisp programmers (2010) | Hacker News Reader

Array languages for Lisp programmers (2010)

archive.vector.org.uk

76 pointsnetworked17 comments

One of the things that annoys me most is when people suggest that the power of array-oriented programming is in having a boatload of built-in array processing functions with short names. As noted in the article, that kind of thing is simple to build as a library in most languages. There is a deeper thing, built into the semantics itself -- the way operators are automatically generalized to work on arbitrarily high-dimensional arrays, which can be manipulated by the programmer. Append (`,` in J) isn't just for tacking a vector onto a vector. It's also for sticking an extra element onto every row of a matrix (or every column), or for tacking the rows of two matrices together (or their columns), extending a rectuangular prism with a new plane (along which dimension? whichever you want!)... I'd talk about 4-, 5-dimensional, and higher if we had convenient prose terms for them. All this is from manipulating how the append function gets lifted to multi-dimensional structures. Or maybe you want to just add a matrix and a vector... do you want to treat the vector as a row or as a column? How about getting an outer product? Operate on the entirety of one argument and individual cells of the other, still just by manipulating how lifting is done. If you haven't been messing with verbs' ranks, you've only had a superficial look at array-oriented programming.

This kind of flexibility is not specific to the functions that come in the standard library. It's part of the language semantics, so it applies to every function the programmer writes. That's a fair bit harder to package up as a library (I've done it in Racket by more or less temporarily redefining function application), so I tend to be dubious of claims to have brought this paradigm into another language. Array-oriented programming is not just a combinator library.

>One of the things that annoys me most is when people suggest that the power of array-oriented programming is in having a boatload of built-in array processing functions with short names.

I agree, and that's unfortunate because that's not the most differentiating thing about array languages. As you point out, it is the semantics: some of it appears in other functional languages (like doing away without loop constructions) but some are unique to array languages (like using various properties of matrix/vector operations to express certain computations concisely).

I am a big believer of linear algebra as a great tool of thought for computation that most people have little to no knowledge of, and the APL family (and actually, Excel) brings home this point.

EDIT: And I definitely speak from my experience. I was a professional q programmer for two years, and I came to realize what makes q difficult for many people is not just its cryptic notation but also the general lack of understanding of linear algebra/matrix operations.

For anyone curious, here's a comparison (that I wrote a couple days ago) of FizzBuzz in K vs. q vs. python... please note the insane syntax for K4 (which is a proprietary language of KX Systems and is thus undocumented).

    \c 150 100 
    c:{$[0=x-5*x div 5;$[0=x-3*x div 3;"CracklePop";"Pop"];$[0=x-3*x div 3;"Crackle";x]]}'1_!101 
    r:{x@&~x in "\""} 
    p:{-1 r .Q.s x}
    p c 
    \\

q (the "readable" wrapper around K4")

    \c 150 100
    c:{$[0=x mod 5;$[0=x mod 3;"CracklePop";"Pop"];$[0=x mod 3;"Crackle";x]]} each 1_til 101 -1 ssr[.Q.s c;"\"";""] 
    \\

Here’s a python (2.7) version of the program written in as unreadable as I could muster

    for i in map(lambda x: "CracklePop" if not x % 3 and not x % 5 else "Crackle" if not x % 3 else "Pop" if not x % 5 else x, xrange(1,101)): print i

Here it is in normal python (2.7)

    for x in xrange(1,101):
        if not x % 5: 
            if not x % 3: 
                print "CracklePop" 
            else: 
                print "Pop" 
        elif not x % 3: 
            print "Crackle" 
        else: 
            print x

Notation as Tool of Thought [1] is worth reading. I always felt Ken Iverson took the wrong path in developing J. I think it was a case of wanting to fit a square peg into a round hole: Doing a non-ASCII character set was very hard back then. In leaving symbols behind he destroyed the very thing he so eloquently examines in this important paper.

[1] http://www.eecg.toronto.edu/~jzhu/csc326/readings/iverson.pd...

I remember this piece being better. Now it seems rather glib. As someone who programs mostly in Lisp, I think I’ve learned more from studying array languages than from anything else outside of Lisp. Implementing a handful of functions and declaring APL “absorbed” is silly.

A great IDE to learn array languages for most people: Excel/Google Spreadsheets.

No, I am not kidding. Excel, or spreadsheets in general, is a great, readily available environment to learn how to think like an APL programmer. Sure, the notations are not there, and you will be copy-and-pasting cell references as opposed to typing in obscure operators, but the essential idea is there: how to think about computation in a geometrical/tabular way.

Just having a collection oriented interface is not enough. However, with aggressive deforestation and JIT it would make for an interesting rival. I think and hope this is where Julia is headed.

The novelty of array languages lie not just in their semantics of acting on collections rather than items at a time. They shine when their interpreters are especially tuned for this use case. So in spite of being interpreted, these languages can be quite fast because once the interpreter dispatches to a(n ideally) hefty primitive that operates on collections, the interpreter gets out of the way for a while.

These languages are designed to express and, critically, also exploit low

   (interpetation workload) / (computation workload)

This is a similar to the notion of minimizing communication per computation.

Assuming this post will attract some array language experts, may I ask what happened to Nial ?

@sedachv If you arent familiar already, Manticore might interest you. http://manticore.cs.uchicago.edu

> However, with aggressive deforestation and JIT it would make for an interesting rival.

SERIES had a lot of early work in deforestation and almost made it into the Common Lisp standard: http://series.sourceforge.net/

I want to see NESL (http://www.cs.cmu.edu/~scandal/nesl.html) brought back for modern systems. Even StarLisp (http://en.wikipedia.org/wiki/*Lisp) makes Hadoop look absolutely retarded.

I ask about this on http://lambda-the-ultimate.org/node/5075. This make me understand how can be a interpreter be faster than C/compiled code.

I'm interested in how exactly implement this stuff. Somebody suggest this link: http://sblom.github.io/openj-core/ioj.htm

I haven't digest it yet, but I wonder if exist a more "normal" implementation example, ie: How get the semantic/performance without use single letter commands/hyper-dense coding!.

So, exist some code/tutorial in how do this as easy like http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar...?

It would be very interesting to see some code in CL, which would allow to run embedded J. Not a Lisp equivalent - since notation is important - but straight J.

In that case why not pipe in & out of a J interpreter child process?

> It would be very interesting to see some code in CL, which would allow to run embedded J.

Not exactly CL, but it seems like a natural fit for Racket.

The closest thing is Redick (https://code.google.com/p/redick/), but that's still just S-exp syntax. It wouldn't be hard to write a readtable to parse J syntax.

J's notation is a bit problematic for anything that has completely separate phases for translation and execution. An identifier may stand for a noun (array), verb (first-order function), adverb (unary second-order function), or conjunction (binary second-order function). Which one it stands for affects how the line containing it should be parsed but is not really known until run time. Historically, implementations of APL family languages have generally gone back and forth between reading a line, executing it, reading another line, etc.

True, but K doesn't have this problem - the parsing is entirely lexical, like Lisp (and unlike J, C and C++)

Seems possible. You would need to write a j->cl compiler, but once you have that, the rest is trivial.

I find it odd that R isn't mentioned. It's the most widely used and popular 'array' language, and rules the statistics/ML domain...

Reply on news.ycombinator.com