6 ms·

Array languages for Lisp programmers (2010)

76 points by networked 12y ago

avmich 12y ago
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.
- frou_dh 12y ago
  In that case why not pipe in & out of a J interpreter child process?
- dragonwriter 12y ago
  > 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.
- sedachv 12y ago
  The closest thing is Redick (https://code.google.com/p/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.
- kd0amg 12y ago
  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.
  - beagle3 12y ago
    True, but K doesn't have this problem - the parsing is entirely lexical, like Lisp (and unlike J, C and C++)
- malisper 12y ago
  Seems possible. You would need to write a j->cl compiler, but once you have that, the rest is trivial.
srean 12y ago
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 http://manticore.cs.uchicago.edu
- sedachv 12y ago
  > 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/ http://series.sourceforge.net/ I want to see NESL (http://www.cs.cmu.edu/~scandal/nesl.html http://www.cs.cmu.edu/~scandal/nesl.html) brought back for modern systems. Even StarLisp (http://en.wikipedia.org/wiki/*Lisp http://en.wikipedia.org/wiki/*Lisp) makes Hadoop look absolutely retarded.
- mamcx 12y ago
  I ask about this on http://lambda-the-ultimate.org/node/5075 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 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-garbage-collector/ http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar...?
deleted 12y ago
[deleted]
rebootthesystem 12y ago
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.pdf http://www.eecg.toronto.edu/~jzhu/csc326/readings/iverson.pd...
kiyoto 12y ago
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.
kd0amg 12y ago
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.
- kiyoto 12y ago
  >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.
ruricolist 12y ago
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.
Mikeb85 12y ago
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...

76 points by networked 12y ago

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.

frou_dh 12y ago
In that case why not pipe in & out of a J interpreter child process?
dragonwriter 12y ago
> 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.
sedachv 12y ago
The closest thing is Redick (https://code.google.com/p/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.
kd0amg 12y ago
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.
- beagle3 12y ago
  True, but K doesn't have this problem - the parsing is entirely lexical, like Lisp (and unlike J, C and C++)
malisper 12y ago
Seems possible. You would need to write a j->cl compiler, but once you have that, the rest is trivial.

srean 12y ago

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 http://manticore.cs.uchicago.edu

sedachv 12y ago
> 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/ http://series.sourceforge.net/ I want to see NESL (http://www.cs.cmu.edu/~scandal/nesl.html http://www.cs.cmu.edu/~scandal/nesl.html) brought back for modern systems. Even StarLisp (http://en.wikipedia.org/wiki/*Lisp http://en.wikipedia.org/wiki/*Lisp) makes Hadoop look absolutely retarded.
mamcx 12y ago
I ask about this on http://lambda-the-ultimate.org/node/5075 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 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-garbage-collector/ http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar...?

deleted 12y ago

[deleted]

rebootthesystem 12y ago

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.pdf http://www.eecg.toronto.edu/~jzhu/csc326/readings/iverson.pd...

kiyoto 12y ago

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.

kd0amg 12y ago

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.

kiyoto 12y ago
>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.

ruricolist 12y ago

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.

Mikeb85 12y ago

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...