J's concepts rank, composition, and GC

I've recently become interested in the J programming language - not so much as a tool I care to use but as a source of some interesting concepts.

I have found the recently revised "Learning J" by Roger Stokes to be extremely helpful for its economical and lucid presentation.

I have some vague questions to toss out to the world:

1) In J (as in APL), a multi-dimensional array is characterized by a list of dimensions called the array's "shape". For example, a tic-tac-toe board is of shape "3 3". The length of that list is called the array's "rank". Scalar (non-array) values have an empty list as their shape, and thus are of rank 0.

Simultaneously, J functions have a declared rank, which determines how array arguments are interpreted and where implicit iteration and reduction occurs. Borrowing an example from Stokes, the J function "*:" squares a number:

  *: 3
  => 9

That function is "rank 0" in its sole argument. If I hand it a rank 2 argument, there is an implicit map reduce:

   3 3 $ 1 2 3 4 5 6 7 8 9
   =>
     1 2 3
     4 5 6
     7 8 9


  *: (3 3 $ 1 2 3 4 5 6 7 8 9)
  =>
     1   4  9
     16 25 36
     49 64 81

My first question is Have any other languages besides APL and J made use of this concept of array and function rank as pertains to implicit iteration and reduction? (If you aren't familiar with and don't "get" how function rank plays out - it took me a while too - Stoke's book is helpful.)

Next:

In J, if I understand correctly, one may only define monadic or dyadic functions. Niladic functions are monadic but ignore their argument. Dyadic functions could theoretically be eliminated (because J has first class functions and every dyadic could be rewritten as a monadic function that returns a monadic function). It seems to be a stylistic choice -- a practical choice in the view of the designers -- to encourage people to think of factoring their programs into compositions of monadic and dyadic functions (and nothing more).

So the next question: Are there other languages of note that permit only monadic and dyadic function definitions? What impact does this have on the overall language design?

Next and finally:

J, as nearly as I can tell, makes an interesting compromise between being purely functional and being an imperative language with side effects.

Specifically (and glossing over I/O, for simplicity): only the bindings of explicit names in various namespaces are mutable. All values to which a name might be bound are themselves immutable.

One consequence of this is that, strictly speaking, fully general graph-tracing garbage collection is not needed in an implementation of J.

I'm aware of some other languages that share that property - such as AWK but I am wondering if there is any interesting theory out there or other careful thought that head-on analyzes the trade-off being made in mostly functional languages that forgo the need for graph tracing garbage collection by allowing mutation only of the bindings of named variables of infinite extent.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Have any other languages

Have any other languages besides APL and J made use of this concept of array and function rank as pertains to implicit iteration and reduction?

K does this, but it is based on J. A notable difference between K and J is that K does not have the "reflexive operator" (~).

Really, it is easy to find what languages have this. Just look at any code golf site and find code golf submissions with ridiculously short character counts :)

K is not based on J

Before J came about, Arthur Whitney, K's author, in one afternoon wrote one page of C coded interpreter fragment that greatly influenced the J interpreter but I don't think you can call either J or K a derivative of the other.

K did have shape function ^ until k3 (the third version of k). # is the count function so #^ gives you the rank of an array. K functions have infinite rank so the implicit map (but not reduce) happens for any rank array. K operators (higher order functions) do too.

Many A.P.L.s have a rank operator. "f rank N" says apply f to the last N dimensions of an array. From what I remember k doesn't have a rank operator but you can simulate rank N for a constant N with the each operator '. So for example (in k3):

  x:2 2 2#!8            // a 2x2x2 array
  x 
((0 1;2 3);(4 5;6 7))  
  +/x                   // f/ == reduce by f 
(4 6; 8 10)
  +/'x                  // f'   == apply f to each element
(2 4;10 12)
  +/''x                 // (+/')'x
(1 5;9 13)
  +/'''x
((0 1;2 3);(4 5;6 7))   // as one might expect
 
 -/x
(-4 -4;-4 -4)
  -/'x
(-2 -2;-2 -2)
  -/''x
(-1 -1;-1 -1)
  -/'''x
((0 1;2 3);(4 5;6 7)) 

K doesn't allow you to define new infix functions or operators but it doesn't limit you to defining functions of 0/1/2 args either.

K too makes do with a ref counting GC. Only var bindings can be modified. And no full closures so you can't play tricks like (let ((k 0)) (lambda () (set! k (+1 k)) k)).

Unfortunately k3 is dead. k4 lives on as the underlying language of q (from kx.software.com). k4 removed ^ and there are other restrictions but the new things it adds are pretty interesting.

K is very different from J

K does this, but it is based on J.

Not only is not K based on J, but, appart from both being descendants of APL, they are very different (and very different from APL).
Some of the most notable differences of K from J are:
• K has heterogeneous lists rather than (homogeneous, rectangular) arrays. (To achieve heterogeneity in J, one has to deal with arrays of boxed items. One can box anything but arrays are still homogeneous and rectangular; e.g. it is not possible to have both boxed and ‘open’ data in an array.)
• K has dictionaries: associative tables with symbols as keys.
• There is the K-tree, a hierarchically organized global data space.
• K has no provision for user-defined adverbs (higher-order operators).
• Adverbs are not treated as data values (unlike verbs – the ordinary operators).
• K has rather different composition rules from those of J.
• K has fewer operators than J, but makes much heavier use of overloading. Overloading is based on both the type and the structure of an operator's arguments.
I should add that, although K3 is now obsolete, its implementation is still available for free non-commercial use.

FISh

I've never quite understood the point of it (and never used it or J), but the ideas in Barry Jay's FISh seem like they might be related.

Thanks for the FISh

Indeed. Static analysis isn't terribly important to my immediate goals and that paper is slightly over my head (which might make a good excuse to catch up and cancel that).

Nial?

1) I think Nial uses a similar system for arrays, although I've never used it.

2) I've never heard of another language having only monadic and dyadic operators. This design choice meshes well with APL/J's use of 1-2 character primitives and use of concatenation to indicate composition (hooks, forks). The whole package allows extremely concise expression. For another language, though, I don't know how much benefit there'd be to such a restriction.

3) Another really interesting aspect of J is that it's (mostly) a function-level language: the preferred method of defining new operators is to build them up from primitive operators using the various composition mechanisms. If you do this, you get benefits that aren't possible when defining a function using lambda notation. eg. func^:_1 will automatically generate an inverse* for a function.

* technically, it returns something called an "obverse", which is a generalisation of an inverse function. I don't know exactly how obverses are defined (it's in the docs), but they generally correspond to the principal branch of the inverse.

Aha... array theory...

Stupid Wikipedia. Your pointer and several others led me belatedly to Array Theory on Wikipedia which is a reasonable entry point to past work.

Thanks.

Comega

Have any other languages besides APL and J made use of this concept of array and function rank as pertains to implicit iteration and reduction?

If I remember correctly, Comega had stream types - typed, possibly unbounded, sequences of some base type - where applying an operation from the base type to a stream would do an implicit map over all the elements in the stream.

Haskell-esque FRP systems

Haskell-esque FRP systems required explicit lifting of functions over instantaneous values (e.g., 1 + 2) to values over time (e.g., 1 lift(+) seconds). FrTime made this syntactically transparent (e.g., 1 + seconds) for one level of raising. I experimented with automatically raising and lowering time varying-ness arity beyond that but found it was awkward and should instead use explicit coercions: there were multiple reasonable ways to do the lifting, and often bugs in code was due to misunderstanding arity. Supporting explicit coercions rather than doing them implicitly seemed like a more solid design.

Can you give an example of

Can you give an example of multiple levels of raising? I have trouble understanding what you mean by that.

Let's say 'lift' raises a

Let's say 'lift' raises a function to operate over values over time, not just instantaneous ones:

1 :: int //instantaneous
seconds :: int behavior //time varying
lift2 :: (a x b -> c) x a behavior x b behavior -> c behavior  
(lift2(plus))(seconds, seconds) :: int behavior //double current time

What if we wanted to write '1 + seconds'? We'd need to somehow convert 1 to a behavior before we could add it:

constant_b :: a -> a behavior 
(lift2(plus))(constant_b(1), seconds)

One way to make this all palatable is to create some explicit helper functions. In the case of '1 + seconds', we might create a new form of lift2 that handles the raise, say lift2SecondArg. In a dynamic language with explicit calls to lift, we might, at a minimum, use reflection to have one function 'lift' that raises constants to behaviors, handles multiple #s of parameters, etc. More typically, e.g., FrTime-style FRP and pretty much any commercial data binding language, the use of 'lift' is entirely hidden for the above uses. In these systems, such as Flex, you'd just write something like


hello, double the time is { 2 * seconds }

where the multiply gets rewritten as lift(*) and lift supports both "int" and "int behavior" arguments.

In real FRP programs, due to the "F", you quickly have higher arities (e.g., int behavior behavior) and, likewise, ways to lower the arity (e.g., switch). Just as we implicitly raised "1 :: int" to "1 :: int behavior", we might also want to raise "1 :: int behavior" to "1 :: int behavior behavior" in some contexts and, in others, lower as in "1 :: int behavior behavior" being used as "1 :: int behavior".

This isn't exactly what Thomas was asking about, but seems analogous: instead of 'int behavior behavior' we now have 'int array array'

Garbage collection

J, as nearly as I can tell, makes an interesting compromise between being purely functional and being an imperative language with side effects.

Specifically (and glossing over I/O, for simplicity): only the bindings of explicit names in various namespaces are mutable. All values to which a name might be bound are themselves immutable.

One consequence of this is that, strictly speaking, fully general graph-tracing garbage collection is not needed in an implementation of J.

Do you mean that garbage collection can just look for objects released in the named object pool, and use a simpler memory management scheme for immutable objects?

re: Garbage Collection

One consequence of this is that, strictly speaking, fully general graph-tracing garbage collection is not needed in an implementation of J.

Do you mean that garbage collection can just look for objects released in the named object pool, and use a simpler memory management scheme for immutable objects?

Yes.

F-Script

F-Script (http://www.fscript.org) has borrowed some of APL's array concepts, but is extremely different in other ways, based as it is on Smalltalk.

no such thing as ‘implicit reduction’

… J functions have a declared rank, which determines how array arguments are interpreted and where implicit iteration and reduction occurs.
…
Have any other languages besides APL and J made use of this concept of array and function rank as pertains to implicit iteration and reduction?

Map is implicit, depending on the ranks of the applied verb and its arguments, but there is no such thing as ‘implicit reduction’ in J (or in APL, K, or Nial for that matter). What should an implicit reduce do anyway?

implicit reduction

The way I meant the terms, iteration + reduction = map.

The rank matching rules cause operators to be iterated over the appropriate elements, the results at each step are reduced (aggregated into a single value).

Common usage isn't consistent there. For example, "map-reduce" doesn't use the word map the same way.

I think of "map" as "iterate + reduce" probably from a lisp background. E.g., MAPCAR could be said to iterate over the elements of a list (in reverse order), apply some function to each element, and reducing the arguments with CONS (given a nil seed).

reduction should reduce

The way I meant the terms, iteration + reduction = map.

I still cannot imagine what sort of reduction can take place in a map.
A map operator acts on each element separately and produces a structure of exactly the same shape and volume as the one that is acted upon – no contraction takes place.
By contrast, the word ‘reduce’, as used in APL or LISP, a.k.a. ‘insert’ or ‘fold’ in other languages, denotes a function that applies an operator along a sequence, thereby accumulating a value. Often, that value is of lesser dimensionality than the original structure, hence the word ‘reduction’. An example is summation: a list of numbers reduces to a single number.

I think of "map" as "iterate + reduce" probably from a lisp background. E.g., MAPCAR could be said to iterate over the elements of a list (in reverse order), apply some function to each element, and reducing the arguments with CONS (given a nil seed).

How is the result of MAPCAR reduced w.r.t. the original list? In Lisp, to reduce a list one uses REDUCE. Calling just anything that conses up a list a ‘reduction‘ would empty the term of any meaning.

reduction redux

I still cannot imagine what sort of reduction can take place in a map.

Wow. Separated by a common language, I guess. I'm not trying to play language cop here -- just to point out a common way of using the word:

Let's take a simple case of reduction by binary operator. I have some operator (or function or whatever you want to call it). It takes two values as operands (or arguments or whatever) and it produces, as its output, a single value.

In lisp, you could say that CONS is a binary operator (or function or procedure etc.). Example, the integers 1 and 2 are lisp values. CONS takes two values and gives back one:

   (CONS 1 2) => (1 . 2)

NIL is also a value. It has a funny print syntax vis a vis cons pairs:

   (CONS 1 NIL)  => (1)

The results in both cases are compound values meaning that they are singular values, sure, but they have other values as "parts" in some natural sense. E.g., (CAR '(1 . 2)) => 1). Still, 1 is a value, 2 is a value, and (1 . 2) is a (singular but compound) value.

Took two values in, got just one back -- that's a reduction step.

Suppose that I have a procedure, a process, a computation -- whatever you care to call it -- that iterates backwards over a lisp list of integers, negating each. I won't say what it does with the results. I'll just say that it "yields" those results where we explicitly don't know yet what "yields" means in this context.

That's an iteration that yields multiple results.

   (mystery-iteration-thing '(1 2 3))
   "yields" (not returns) 
   -3 -2 -1

The iteration yields three lisp values, in that order. So - there is indeed a sequence there, although that sequence is not a lisp value. In this case, it is three lisp values.

So, we reduce the abstract sequence using CONS with a seed value of NIL. In effect,

   (CONS -1 (CONS -2 (CONS -3 NIL))) => (1 2 3)

Now it is true that, for example, Common LISP has a function named reduce and this does something closely related but not identical to what I'm describing.

Common LISP's function named REDUCE operates over common lisp's "sequence values" which are either lists made of cons pairs or are vectors (or other generalizations of such). That's a subset of the concept of reduction in general. REDUCE the built-in function is limited to operating on sequences that have been reified as certain types of value whereas the concept of reduction in general applies more generally.

Nevertheless,

How is the result of MAPCAR reduced w.r.t. the original list? In Lisp, to reduce a list one uses REDUCE.

Sure. If my common lisp is not too rusty:

  (mapcar #'- '(1 2 3))

  is equivalent to

  (reduce #'(lambda (a b) (cons (- a) b))
          '(1 2 3)
          :from-end t
          :initial-value nil)

  is equivalent to

  (map 'list #'- '(1 2 3))

The version that uses the function REDUCE has an implicit iteration. The version that uses MAP has an implicit reduction by CONS with initial NIL. MAPCAR is a traditional subset of the functionality of MAP.

map and reduce

How would you implement (map f list1 list2 ...) in terms of reduce?

To me map and reduce are fundamentally different. You can map an infinite list but you can't reduce it. Even for finite arrays, a map in terms of reduce would not be a practical implementation -- it would exhibit an O(n^2) behavior. In fact for map you pretty much have to do a shape analysis. No shape analysis is required for reduce.

The critical point w.r.t. array languages is that the implicit map for every function is shape preserving -- the output has the same shape. Reduce on the other hand is almost always used in a way where the resultant shape is different from its argument. For example, in q:

   x:(1;2;(3;4);5) // user input is indented
   x 
(1;2;(3;4);5)       // system response starts in column 1.
   x*x
(1;4;(9;16);25)
   -x
(-1;-2;(-3;-4);-5)
   ,/x              // ",'" joins two arrays or an array and an element. "/" is the reduce operator
(1;2;3;4;5)
  ,/((1;2);3;4;((5;6);(7;8)))
(1;2;3;4;(5;6);(7;8))

It is instructive to implement an explicit deep map like this in Scheme to get a feel for shape analysis.

(apl - '#(1 2 #(3 4) 5)) => #(-1 -2 #(-3 -4) -5)
(apl * '#(1 2 #(3 4) 5) 1/2 4) => #(2 4 #(6 8) 10)
(apl expt '#(1 2 #(3 4) 5) #(0 1 #(2 3) 4)) => #(1 2 #(9 64) 625)

"shape preserving"

The critical point w.r.t. array languages is that the implicit map for every function is shape preserving.

In J, because of the concept of function rank (which can be both absolute and relative): Shape is preserved in some outermost dimensions but inner dimensions can change and/or rank can be raised or lowered.

Is that consistent with what you mean by "shape preserving"?

Yes.... Kind of!

Applying a function of rank K on an array of rank N will preserve the shape of outer N-K dimensions. See Iversion's A Dictionary of APL paper. If you can't find that, A Dictionary of J.

Of course, in general "shape" need not be rectilinear. In K structure shape can be anything but its functions either work on the leaves (that can not be decomposed further) or functions like join or each that work top down. I don' t know if there exists a language where you can operate on sub-structures while maintaining overall structure. Things like matrix multiplication of all leaves of two trees, where a "leaf" is a vector or a table. Could be useful in graphics. Or something more complex like changing the style of all embedded elements in a tree structureed document.

adhering to the agreed meanings is much better

Your use of the word reduction is completely acceptable in the common language, but is, I believe, too confusing in programming. What you explain on the example of MAPCAR applies to any other function producing a list, and indeed any function producing an aggregate structure.
But as I already mentioned in my previous post, calling all such functions ‘reduction’ makes the very use of the word reduction in programming vacuous. Even a function that generates a sequence from a single number would then be a ‘reduction’, which is plain absurd.
Your use of reduce is particularly confusing in the context of an array language, as in your initial post. I doubt if anyone in the J community would agree with it. Same with APL, K, Nial etc.
So, let us stick to only using reduce to denote a rank lowering transform, as is common in programming; aggregate for composing a value from parts; and generate when the parts themselves are being produced in the first place. As for map, it is neither of these: it is a structure-preserving transform – as in math, and as in the general meaning of the word.

And, by the way, speaking of iteration when explaining the workings of an array language (as in your formula iteration + reduction = map) is also hardly appropriate. One reason for this is that the order in which the elements of a structure are traversed is irrelevant, and may even not exist (when processing is done in parallel). In fact, the whole point of having an array language is precisely avoiding iteration!

nah

I respectfully suggest that now that you understand me perfectly well, your language corrections are not helpful to anyone.

 

Regarding the last Lisp example in your previous post, I forgot to mention that ‘can be implemented as’ does not imply ‘is equivalent to’, and I see no other evidence why the latter phrase must be true where it stands.

And I suggest, no less respectfully, that, rather than being rude to me, you search any – I mean any – piece of literature on J, K, APL, or Nial, and find for yourself whether it uses any of the words ‘iterate’ and ‘reduce’ at least once the way you do.

Map can only be written in

Map can only be written in terms of reduce for, essentially, lists. Otherwise, the two are somewhat distinct. Since reduce eliminates structure, then you can't necessarily conjure up the same structure for, e.g., a tree.

Hence in Haskell, Functor (i.e. mappable), Foldable (i.e. reducable), and Traversable (i.e. subject to a structure-preserving reduce) are all distinct typeclasses, with Traversable requiring both Functor and Foldable.