Lambda the Ultimate

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

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

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.

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 multiple levels of raising? I have trouble understanding what you mean by that.

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'

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.

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

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.

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.

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)

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"?

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.

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