6 ms·

Another Programming Idiom You've Never Heard Of

26 points by AndreiVajnaII 14y ago

pdw 14y ago
Perl can do this as well: @a = (10, 5, 9, 6, 20, 17, 1); @slice = @a[0, 1, 3, 6]; Though I've never seen this used for anything other than simple sublists (like @a[0..3]).
- disgruntledphd2 14y ago
  I use this kind of stuff in R all the time. Its actually wonderful how many typical data analytic tasks can be expressed in this format. Thats why, I suspect, both R and J have this operator.
- tzs 14y ago
  I've used something like that: @state[1,2,3,5,6,7,9,10,11,13,14,15] = @state[5,10,15,9,14,3,13,2,7,1,6,11]; That's the row shift transformation in AES encryption.
- no_flags 14y ago
  So can MATLAB. a = [10 5 9 6 20 7]; slice = a([1 2 4 7]); I guess it's not called matrix laboratory for nothing.
  - roguecoder 14y ago
    plus, MATLAB has "find", which returns a list of all the positions of a matrix matching some pattern. The combination of the two makes things that are very ugly to express in other languages quite pretty. Too bad it's wicked expensive, proprietary and slow. I quite enjoy the paradigm.
    - blt 14y ago
      The obscure matrix language IDL has this too via WHERE. It's really nice. This syntax is essential for image processing unless you want to write a bunch of unnecessary for loops. img[WHERE(img LT 5)] = 0 I built a bunch of sparse image processing algorithms using index lists. Pass in the indices and the values at those locations. Everything else is assumed zero. Sort the index array and you can use binary search to look up neighbors. On my domain images which were less than 2% foreground it made a big difference.
- EvilTerran 14y ago
  I've used perl's array slices as @array[@indices] in the past. Can't remember why, but I have. It also works for hashes: %hash = (foo => "bar", one => "two", alpha => "beta"); @keys = ('alpha', 'one'); @hash{@keys} == ('beta', 'two');
- sparky_z 14y ago
  An array slice can also be used as an lvalue in an assignment: @a = (10, 5, 9, 6, 17, 1); @a[3,5,1] = qw(yes no maybe); print "@a"; >> "10 maybe 9 yes 17 no" In fact, because the slice can be both an lvalue and an rvalue, this is an easy way to transpose elements in-place. @a = (10, 5, 9, 6, 17, 1); @a[0,4] = @a[4,0]; print "@a"; >> "17, 5, 9, 6, 10, 1";
deleted 14y ago
[deleted]
peteretep 14y ago
Oh look, you just invented array slices! https://en.wikipedia.org/wiki/Array_slicing https://en.wikipedia.org/wiki/Array_slicing
- freudianquip 14y ago
  "The concept of slicing was surely known even before the invention of compilers. Slicing as a language feature probably started with FORTRAN (1957)" Maybe slightly late for that.
- batista 14y ago
  Guy who doesn't understand general statements and statistics: "Your title is wrong, _I have_ heard of that idiom". A different guy with the same deficiency: "Wrong, it's a common idiom in (list of obscure languages)". Plus: array slicing, in 95% of the languages mentioned (and 99% of common languages) is NOT what he talks about. It just returns a sub-array and it only takes an uper/lower bound.
  - peteretep 14y ago
    Do you really think of Perl as an obscure language?
    - batista 14y ago
      Are 95% and 99% difficult to parse? Plus, does "I've seen it in Perl" nullify the "an idiom you haven't seen" for the rest of millions of programmers that don't use Perl, or J, or ...?
- kd0amg 14y ago
  Yeah, ok, array slicing, woohoo. But what's interesting here is that this doesn't come from any special/privileged syntax or from special handling by the { operator. The { operator just expects a scalar and a list and accesses an element of the list according to the scalar. This slicing capability simply falls out of the automatic lifting J does when you pass an array of higher rank than the operator expects, the same rule that gives you (2 5 3)+7 = (9 12 10).
jhuni 14y ago
I have heard of both this programming idioms: this and the original. In fact, both of these two programming idioms can be expressed in terms of in degree regular algebraic relations (e.g Common Lisp place forms). Indexes are places because you can retrieve the value at an index (nth coll i) and you can edit the value at the index (setf (nth coll i) val). Slices of collections are themselves places, and they can be decomposed further into even finer places. In Common Lisp the subseq function describes such places: (setf (subseq coll start end) slice). Injective functions have an in degree regularity of one, which means that they are trivial place forms. As such, the original programming idiom can be described as a process that moves an object to a place, runs some functions, and then moves back to the starting place.
onlyup 14y ago
This seems cool but I have a question. Is this: > 6 5 4 3 2 1 0 { 10 5 9 6 20 17 1 Stored in an array? Because if it is, when I do this: > 2 3 4 5 6 { 10 5 9 6 20 17 1 Won't I have to rearrange the whole array? (deleting two of the index parts)
- silentbicycle 14y ago
  It doesn't rearrange the array, it constructs a new one. While I'm not 100% sure about the J implementation* , K and related languages usually modify the array in place if there's only a single reference to it (so that mutation is still referentially transparent), to avoid extra allocation & copying. * It's now open-source at https://github.com/openj/core https://github.com/openj/core, but I have a hard time following their C style -- it's legal C, but written like J. APLs have memory allocators that are designed with arrays in mind, making this less expensive than you might expect. See this post I wrote about the memory management for Kona (https://github.com/kevinlawler/kona/ https://github.com/kevinlawler/kona/), an open-source implementation of K: https://groups.google.com/forum/#!topic/kona-dev/fs5GoSBtF3Y/discussion https://groups.google.com/forum/#!topic/kona-dev/fs5GoSBtF3Y... .
- darklajid 14y ago
  I don't quite understand the question. Are you asking if the latter example needs to modify the whole array, because you 'cut off' the first two elements? I don't know J at all, but I'd assume that the result of the '{' is a _new_ array. All I've seen about J is very much rooted in mathematics and therefor I'd expect a functional/immutable language. Nothing would be 'deleted', no array changed/rearranged and a new array without the first two elements created/returned. Note the fat 'no idea about J' disclaimer, of course.
simonb 14y ago
Clojure can do this as well without requiring any special syntax or function because all sequence are funcallable: (map [1 2 3 4 5 6 7 8 9 10] [0 3 4]) => (1 4 5)
- silentbicycle 14y ago
  Does it do the slicing in parallel?
  - darklajid 14y ago
    If not (I assume no), would you accept (pmap [1 2 3 4 5 6 7 8 9 10] [0 3 4]) instead? pmap being defined as "Like map, except f is applied in parallel" [1] That said, I'm too ignorant to understand the deeper benefits of the parallel approach. It seems it enables nifty things according to some other comments in this thread, yet I've been unable to understand quite why so far. 1: http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/pmap http://clojure.github.com/clojure/clojure.core-api.html#cloj...
    - silentbicycle 14y ago
      Yes, that works. The deeper benefits come from having a language design where almost everything expects to work with arrays and array indices, so that idiom can be combined with many other operators and combinators. Quick example in K, J's cousin, which I know far better: consider "{[d;p]d@&p d}". That's a 3-argument lambda which takes a data set (d) and a predicate function (p), applies the predicate function to the data set's values (p d) returning a boolean vector of the predicate's results, filters the result set to just the indices of the true/1 values (&), then indexes the data set by those indexes. The predicate function can be applied to the data set in parallel, and it can be slices by the indices in parallel. D can be a small data set in memory, or a terabyte of memory-mapped data on disk; it doesn't matter. (Really, it could just be "{x@&y x}" or "{x[&y[x]]}", but I named the parameters.) 'where' ("&") is just one of many operators that combines with array slicing like this. In pseudo-Lisp it might look something like "(lambda (d p) (pmap d (where (pmap f d))))". 'where' is a function that converts e.g. [1 2 3 4 5] to [0 1 1 2 2 2 3 3 3 3 4 4 4 4 4], and [0 1 0 1 0] to [1 3]. This works for both boolean results and reshaping data sets, but the underlying implementation is the same.
sbmassey 14y ago
He should rename it "Another Programming Idiom I Had Never Heard Of".
eevilspock 14y ago
How can it be an idiom if we haven't heard of it?
- repsilat 14y ago
  There are plenty of idioms in Hebrew that I've never heard of. This is an idiom in a subculture you aren't a part of, in languages you do not speak. There are a lot of them. The author assumed that because J is not really a "mainstream language" that the people reading his blog would probably not be familiar with its idioms.
bingbing 14y ago
That idiom is called an array slice in perl. # perl -e "print join ' ', (10,5,9,6,20,17,1)[0,1,3,6]" 10 5 6 1 http://perldoc.perl.org/perldata.html#Slices http://perldoc.perl.org/perldata.html#Slices
darkstalker 14y ago
Didn't know about the 3[array] syntax in C. I know that a[b] evaluates to *(a+b) but never tought that the inverted form would work.
Luyt 14y ago
Python version [(10,5,9,6,20,17,1)[i] for i in (6,1,3,2,0,5,4)]
bgilroy26 14y ago
If this piques anyone's interest in the J language, Dadgum writes elsewhere about a neat book to learn graphics programming in J. http://prog21.dadgum.com/19.html http://prog21.dadgum.com/19.html

26 points by AndreiVajnaII 14y ago

pdw 14y ago

Perl can do this as well: @a = (10, 5, 9, 6, 20, 17, 1); @slice = @a[0, 1, 3, 6]; Though I've never seen this used for anything other than simple sublists (like @a[0..3]).

disgruntledphd2 14y ago
I use this kind of stuff in R all the time. Its actually wonderful how many typical data analytic tasks can be expressed in this format. Thats why, I suspect, both R and J have this operator.
tzs 14y ago
I've used something like that: @state[1,2,3,5,6,7,9,10,11,13,14,15] = @state[5,10,15,9,14,3,13,2,7,1,6,11]; That's the row shift transformation in AES encryption.
no_flags 14y ago
So can MATLAB. a = [10 5 9 6 20 7]; slice = a([1 2 4 7]); I guess it's not called matrix laboratory for nothing.
- roguecoder 14y ago
  plus, MATLAB has "find", which returns a list of all the positions of a matrix matching some pattern. The combination of the two makes things that are very ugly to express in other languages quite pretty. Too bad it's wicked expensive, proprietary and slow. I quite enjoy the paradigm.
  - blt 14y ago
    The obscure matrix language IDL has this too via WHERE. It's really nice. This syntax is essential for image processing unless you want to write a bunch of unnecessary for loops. img[WHERE(img LT 5)] = 0 I built a bunch of sparse image processing algorithms using index lists. Pass in the indices and the values at those locations. Everything else is assumed zero. Sort the index array and you can use binary search to look up neighbors. On my domain images which were less than 2% foreground it made a big difference.
EvilTerran 14y ago
I've used perl's array slices as @array[@indices] in the past. Can't remember why, but I have. It also works for hashes: %hash = (foo => "bar", one => "two", alpha => "beta"); @keys = ('alpha', 'one'); @hash{@keys} == ('beta', 'two');
sparky_z 14y ago
An array slice can also be used as an lvalue in an assignment: @a = (10, 5, 9, 6, 17, 1); @a[3,5,1] = qw(yes no maybe); print "@a"; >> "10 maybe 9 yes 17 no" In fact, because the slice can be both an lvalue and an rvalue, this is an easy way to transpose elements in-place. @a = (10, 5, 9, 6, 17, 1); @a[0,4] = @a[4,0]; print "@a"; >> "17, 5, 9, 6, 10, 1";

deleted 14y ago

[deleted]

peteretep 14y ago

Oh look, you just invented array slices! https://en.wikipedia.org/wiki/Array_slicing https://en.wikipedia.org/wiki/Array_slicing

freudianquip 14y ago
"The concept of slicing was surely known even before the invention of compilers. Slicing as a language feature probably started with FORTRAN (1957)" Maybe slightly late for that.
batista 14y ago
Guy who doesn't understand general statements and statistics: "Your title is wrong, _I have_ heard of that idiom". A different guy with the same deficiency: "Wrong, it's a common idiom in (list of obscure languages)". Plus: array slicing, in 95% of the languages mentioned (and 99% of common languages) is NOT what he talks about. It just returns a sub-array and it only takes an uper/lower bound.
- peteretep 14y ago
  Do you really think of Perl as an obscure language?
  - batista 14y ago
    Are 95% and 99% difficult to parse? Plus, does "I've seen it in Perl" nullify the "an idiom you haven't seen" for the rest of millions of programmers that don't use Perl, or J, or ...?
kd0amg 14y ago
Yeah, ok, array slicing, woohoo. But what's interesting here is that this doesn't come from any special/privileged syntax or from special handling by the { operator. The { operator just expects a scalar and a list and accesses an element of the list according to the scalar. This slicing capability simply falls out of the automatic lifting J does when you pass an array of higher rank than the operator expects, the same rule that gives you (2 5 3)+7 = (9 12 10).

jhuni 14y ago

I have heard of both this programming idioms: this and the original. In fact, both of these two programming idioms can be expressed in terms of in degree regular algebraic relations (e.g Common Lisp place forms). Indexes are places because you can retrieve the value at an index (nth coll i) and you can edit the value at the index (setf (nth coll i) val). Slices of collections are themselves places, and they can be decomposed further into even finer places. In Common Lisp the subseq function describes such places: (setf (subseq coll start end) slice). Injective functions have an in degree regularity of one, which means that they are trivial place forms. As such, the original programming idiom can be described as a process that moves an object to a place, runs some functions, and then moves back to the starting place.

onlyup 14y ago

This seems cool but I have a question. Is this: > 6 5 4 3 2 1 0 { 10 5 9 6 20 17 1 Stored in an array? Because if it is, when I do this: > 2 3 4 5 6 { 10 5 9 6 20 17 1 Won't I have to rearrange the whole array? (deleting two of the index parts)

silentbicycle 14y ago
It doesn't rearrange the array, it constructs a new one. While I'm not 100% sure about the J implementation* , K and related languages usually modify the array in place if there's only a single reference to it (so that mutation is still referentially transparent), to avoid extra allocation & copying. * It's now open-source at https://github.com/openj/core https://github.com/openj/core, but I have a hard time following their C style -- it's legal C, but written like J. APLs have memory allocators that are designed with arrays in mind, making this less expensive than you might expect. See this post I wrote about the memory management for Kona (https://github.com/kevinlawler/kona/ https://github.com/kevinlawler/kona/), an open-source implementation of K: https://groups.google.com/forum/#!topic/kona-dev/fs5GoSBtF3Y/discussion https://groups.google.com/forum/#!topic/kona-dev/fs5GoSBtF3Y... .
darklajid 14y ago
I don't quite understand the question. Are you asking if the latter example needs to modify the whole array, because you 'cut off' the first two elements? I don't know J at all, but I'd assume that the result of the '{' is a _new_ array. All I've seen about J is very much rooted in mathematics and therefor I'd expect a functional/immutable language. Nothing would be 'deleted', no array changed/rearranged and a new array without the first two elements created/returned. Note the fat 'no idea about J' disclaimer, of course.

simonb 14y ago

Clojure can do this as well without requiring any special syntax or function because all sequence are funcallable: (map [1 2 3 4 5 6 7 8 9 10] [0 3 4]) => (1 4 5)

silentbicycle 14y ago
Does it do the slicing in parallel?
- darklajid 14y ago
  If not (I assume no), would you accept (pmap [1 2 3 4 5 6 7 8 9 10] [0 3 4]) instead? pmap being defined as "Like map, except f is applied in parallel" [1] That said, I'm too ignorant to understand the deeper benefits of the parallel approach. It seems it enables nifty things according to some other comments in this thread, yet I've been unable to understand quite why so far. 1: http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/pmap http://clojure.github.com/clojure/clojure.core-api.html#cloj...
  - silentbicycle 14y ago
    Yes, that works. The deeper benefits come from having a language design where almost everything expects to work with arrays and array indices, so that idiom can be combined with many other operators and combinators. Quick example in K, J's cousin, which I know far better: consider "{[d;p]d@&p d}". That's a 3-argument lambda which takes a data set (d) and a predicate function (p), applies the predicate function to the data set's values (p d) returning a boolean vector of the predicate's results, filters the result set to just the indices of the true/1 values (&), then indexes the data set by those indexes. The predicate function can be applied to the data set in parallel, and it can be slices by the indices in parallel. D can be a small data set in memory, or a terabyte of memory-mapped data on disk; it doesn't matter. (Really, it could just be "{x@&y x}" or "{x[&y[x]]}", but I named the parameters.) 'where' ("&") is just one of many operators that combines with array slicing like this. In pseudo-Lisp it might look something like "(lambda (d p) (pmap d (where (pmap f d))))". 'where' is a function that converts e.g. [1 2 3 4 5] to [0 1 1 2 2 2 3 3 3 3 4 4 4 4 4], and [0 1 0 1 0] to [1 3]. This works for both boolean results and reshaping data sets, but the underlying implementation is the same.

sbmassey 14y ago

He should rename it "Another Programming Idiom I Had Never Heard Of".

eevilspock 14y ago

How can it be an idiom if we haven't heard of it?

repsilat 14y ago
There are plenty of idioms in Hebrew that I've never heard of. This is an idiom in a subculture you aren't a part of, in languages you do not speak. There are a lot of them. The author assumed that because J is not really a "mainstream language" that the people reading his blog would probably not be familiar with its idioms.

bingbing 14y ago

That idiom is called an array slice in perl. # perl -e "print join ' ', (10,5,9,6,20,17,1)[0,1,3,6]" 10 5 6 1 http://perldoc.perl.org/perldata.html#Slices http://perldoc.perl.org/perldata.html#Slices

darkstalker 14y ago

Didn't know about the 3[array] syntax in C. I know that a[b] evaluates to *(a+b) but never tought that the inverted form would work.

Luyt 14y ago

Python version [(10,5,9,6,20,17,1)[i] for i in (6,1,3,2,0,5,4)]

bgilroy26 14y ago

If this piques anyone's interest in the J language, Dadgum writes elsewhere about a neat book to learn graphics programming in J. http://prog21.dadgum.com/19.html http://prog21.dadgum.com/19.html