# pervasive operations, n-ary treemap

## stevan apter — 2003-05-29 11:53:07

    in k the atomic primitives are those which penetrate their

    list arguments to work on the atoms.  my guess (i can't seem

    to get it working, but it seems like it should) is that the

    behavior of the monadic atomics can be simulated in joy with

    the treemap combinator:

        [[1 2 3] 4 [5 6]] [0 -] treemap

      [[-1 -2 -3] -4 [-5 -6]]

    or

        0 [[1 2 3] 4 [5 6]] [-] treemap

      [[-1 -2 -3] -4 [-6 -6]]

    recurse to the leaves, apply.  result has the structure of

    the input tree.

    i'm not sure how to simulate the dyadic atomics.  here's

    the desired behavior.

    'pervade2' expects

        a b [p]

    on the stack, a and b are trees.

    if a and b are both leaves, apply p (termination condition).

    if a is a leaf, recurse on a and each piece of b; i.e.

        [[a b 0 at][a b 1 at] .. ] [p pervade] map

    if b is a leaf, recurse of each piece of a and b.

    if neither a nor b is a leaf then if their sizes differ, fail

    with a "length error", else recurse on each piece of a and

    each piece of b; i.e.

        [[a 0 at b 0 at][a 1 at b 1 at] .. ] [p pervade] map

    rearranging the trees for the recursion step would be easier

    if 'transpose' were tolerant:

        [10 [20 30 40]] transpose

      [[10 20] [10 30] [10 40]]

    but apart from performance considerations, it seems to me

    like this calls for a tree combinator which does parallel

    recursion on more than one tree:

        T1 T2 [P] treemap2

        T1 T2 T3 [P] treemap3

        :

    am i missing something obvious?

## phimvt@lurac.latrobe.edu.au — 2003-05-30 04:15:18

    On Thu, 29 May 2003, stevan apter wrote:

     > in k the atomic primitives are those which penetrate their

    > list arguments to work on the atoms.  my guess (i can't seem

    > to get it working, but it seems like it should) is that the

    > behavior of the monadic atomics can be simulated in joy with

    > the treemap combinator:

    >

    >     [[1 2 3] 4 [5 6]] [0 -] treemap

    >   [[-1 -2 -3] -4 [-5 -6]]

     Remember, postfix 'x 0 -' is infix 'x - 0' because the order

    of the operands 'x' and '0' is not changed. You probably mean

          [[1 2 3] 4 [5 6]]  [0 swap -]  treemap

    =>    [[-1 -2 -3] -4 [-5 -6]]

    This works for me.

     > or

    >

    >     0 [[1 2 3] 4 [5 6]] [-] treemap

    >   [[-1 -2 -3] -4 [-6 -6]]

     This worked for me unchanged. Maybe you are puzzled by the 0 which

    is still below the mapped list?

     > recurse to the leaves, apply.  result has the structure of

    > the input tree.

     Yes.

     > i'm not sure how to simulate the dyadic atomics.  here's

    > the desired behavior.

    >

    > 'pervade2' expects

    >

    >     a b [p]

    >

    > on the stack, a and b are trees.

     In the systematisation of names that I have at the back of my

    mind this would be called  'treemap2'.

     > if a and b are both leaves, apply p (termination condition).

    >

    > if a is a leaf, recurse on a and each piece of b; i.e.

    >

    >     [[a b 0 at][a b 1 at] .. ] [p pervade] map

    >

    > if b is a leaf, recurse of each piece of a and b.

    >

    > if neither a nor b is a leaf then if their sizes differ, fail

    > with a "length error", else recurse on each piece of a and

    > each piece of b; i.e.

    >

    >     [[a 0 at b 0 at][a 1 at b 1 at] .. ] [p pervade] map

     Several responses:

    1. No such inbuilt combinator (yet). Could write one in analogy

       with mapr2, though.

    2. "length error": yes, maybe something like that should be the

       norm for mapr2 (= zipwith in Haskell). On the other hand

       it may be better if the normal behaviour is truncation to the

       shorter of the two. Then, if one wants different lengths to count

       as an error, the programmer would have to write the check

       explicitly. Dunno what Haskell does (anyone ?).

    3. Two-aggregate variants of map, filter, fold and step:

       These need to be written as primitives in C, and I haven't done

       that yet. Like their one-aggregate originals, they should

       go through the aggregate from left to right. The same would

       be true of two-tree combinators.

    4. Such variants (e.g. mapr2) can only recurse to the end

       and then essentially o from right to left. They cannot do

       the trick         42  [1 2 3 4] [*] map

     > rearranging the trees for the recursion step would be easier

    > if 'transpose' were tolerant:

    >

    >     [10 [20 30 40]] transpose

    >   [[10 20] [10 30] [10 40]]

     How about 'cons' instead?

          [10 [20 30 40]] i [cons] map popd

     > but apart from performance considerations, it seems to me

    > like this calls for a tree combinator which does parallel

    > recursion on more than one tree:

    >

    >     T1 T2 [P] treemap2

    >     T1 T2 T3 [P] treemap3

    >     :

    >

    > am i missing something obvious?

     No, you are not missing anything. Joy does have missing bits.

    (But, I must say this: I have not really found any applications

    for the tree combinators, let alone for multi-tree combinators).

    Until such multi-tree combinators are implemented as primitives

    in C, one will have to define one's own in Joy. It may even

    be that one will only want very few specialised operators

    to be mapped (or whatever) over trees, and then a more direct

    approach might well be called for.

      - Manfred

## stevan apter — 2003-05-30 12:17:58

    ----- Original Message -----

    From: <phimvt@...>

    To: <concatenative@yahoogroups.com>

    Sent: Friday, May 30, 2003 12:15 AM

    Subject: Re: [stack] pervasive operations, n-ary treemap

    >

    > On Thu, 29 May 2003, stevan apter wrote:

    >

    > > in k the atomic primitives are those which penetrate their

    > > list arguments to work on the atoms.  my guess (i can't seem

    > > to get it working, but it seems like it should) is that the

    > > behavior of the monadic atomics can be simulated in joy with

    > > the treemap combinator:

    > >

    > >     [[1 2 3] 4 [5 6]] [0 -] treemap

    > >   [[-1 -2 -3] -4 [-5 -6]]

    >

    > Remember, postfix 'x 0 -' is infix 'x - 0' because the order

    > of the operands 'x' and '0' is not changed. You probably mean

    >       [[1 2 3] 4 [5 6]]  [0 swap -]  treemap

    > =>    [[-1 -2 -3] -4 [-5 -6]]

    > This works for me.

    here's what my joy console looks like:

        JOY  -  compiled at 15:46:02 on May 13 2003 (NOBDW)

        Copyright 2001 by Manfred von Thun

        [[1 2 3] 4 [5 6]]  [0 swap -]  treemap

        .

        [0 swap -]

        .

        [[1 2 3] 4 [5 6]]

    ??

    on the other hand, i'm pretty sure i've implemented treemap

    correctly in ck:

        d:\ck>k ck

        K 2.95t 2003-02-06 Copyright (C) 1993-2002 Kx Systems

        \ for k, \\ to exit, .ck.i() for cK

            [[1 2 3] 4 [5 6]]  [0 swap -]  treemap

        [-1 -2 -3] -4 [-5 -6]

    i guess i'll have to get hold of a c compiler for windows

    and learn how to make a joy interpreter from source.

    >

    > > or

    > >

    > >     0 [[1 2 3] 4 [5 6]] [-] treemap

    > >   [[-1 -2 -3] -4 [-6 -6]]

    >

    > This worked for me unchanged. Maybe you are puzzled by the 0 which

    > is still below the mapped list?

    no, i understand what's going on here.  it just occurred to me

    that burying treemap in the program to the be treemapped could

    handle the case where instead of a leaf 0 on the stack, you have

    a tree:

          [[10 20 30][40 50 60][70 80]] [[1 2 3] 4 [5 6]] [[-] treemap] treemap

    [[69 79] [68 78] [67 77]] [66 76] [[65 75] [64 74]]

    huh -- that works!  so the pattern for constructing treemapn given

    p and n is pretty obvious.

    >

    > > recurse to the leaves, apply.  result has the structure of

    > > the input tree.

    >

    > Yes.

    >

    > > i'm not sure how to simulate the dyadic atomics.  here's

    > > the desired behavior.

    > >

    > > 'pervade2' expects

    > >

    > >     a b [p]

    > >

    > > on the stack, a and b are trees.

    >

    > In the systematisation of names that I have at the back of my

    > mind this would be called  'treemap2'.

    >

    > > if a and b are both leaves, apply p (termination condition).

    > >

    > > if a is a leaf, recurse on a and each piece of b; i.e.

    > >

    > >     [[a b 0 at][a b 1 at] .. ] [p pervade] map

    > >

    > > if b is a leaf, recurse of each piece of a and b.

    > >

    > > if neither a nor b is a leaf then if their sizes differ, fail

    > > with a "length error", else recurse on each piece of a and

    > > each piece of b; i.e.

    > >

    > >     [[a 0 at b 0 at][a 1 at b 1 at] .. ] [p pervade] map

    >

    > Several responses:

    > 1. No such inbuilt combinator (yet). Could write one in analogy

    >    with mapr2, though.

    i guess my question is how one would go about writing such a

    combinator in joy, with the means at hand.  i was thinking that

    an initial step could grab the two trees below the program and

    construct a single list of two trees.  then the recursion could

    operate on that list.  so

            T1 T2 [p] treemap2 ->

            [T1 T2] [p] ...

    [but i think i like my approach above better, which only occurred

    to me while re-reading my reply]

    > 2. "length error": yes, maybe something like that should be the

    >    norm for mapr2 (= zipwith in Haskell). On the other hand

    >    it may be better if the normal behaviour is truncation to the

    >    shorter of the two. Then, if one wants different lengths to count

    >    as an error, the programmer would have to write the check

    >    explicitly. Dunno what Haskell does (anyone ?).

    other behaviors are possible, e.g. reshape the shorter list to

    the size of the longer:

            [1 2] [10 20 30 40 50] -> [1 2 1 2 1] [10 20 30 40 50]

    or pad it out with the appropriate prototype:

            -> [1 2 0 0 0] [10 20 30 40 50]

    truncation, reshape, and padding can each be done on the arrays

    before applying the function, so the consensus (in the array

    programming community) is that "length error" is the most useful

    default.  (this is borne out in practice)

    > 3. Two-aggregate variants of map, filter, fold and step:

    >    These need to be written as primitives in C, and I haven't done

    >    that yet. Like their one-aggregate originals, they should

    >    go through the aggregate from left to right. The same would

    >    be true of two-tree combinators.

    > 4. Such variants (e.g. mapr2) can only recurse to the end

    >    and then essentially o from right to left. They cannot do

    >    the trick         42  [1 2 3 4] [*] map

    >

    >

    > > rearranging the trees for the recursion step would be easier

    > > if 'transpose' were tolerant:

    > >

    > >     [10 [20 30 40]] transpose

    > >   [[10 20] [10 30] [10 40]]

    >

    > How about 'cons' instead?

    >       [10 [20 30 40]] i [cons] map popd

    aha - tricky!  you need a different trick for

            [[20 30 40] 10]

    the K primitive , which concatenates any two objects, handles

    both cases:

            [10 [20 30 40]] [,] each

            [[20 30 40] 10] [,] each

    intuitively, you just want to pair each thing on the left with

    each thing on the right.

    ideally, you (i) would like transpose to take a list k of size n

    and return the transpose subject only to the constraint that all

    the lists in k have the same size m, atoms in k being extended.

    >

    > > but apart from performance considerations, it seems to me

    > > like this calls for a tree combinator which does parallel

    > > recursion on more than one tree:

    > >

    > >     T1 T2 [P] treemap2

    > >     T1 T2 T3 [P] treemap3

    > >     :

    > >

    > > am i missing something obvious?

    >

    > No, you are not missing anything. Joy does have missing bits.

    > (But, I must say this: I have not really found any applications

    > for the tree combinators, let alone for multi-tree combinators).

    > Until such multi-tree combinators are implemented as primitives

    > in C, one will have to define one's own in Joy. It may even

    > be that one will only want very few specialised operators

    > to be mapped (or whatever) over trees, and then a more direct

    > approach might well be called for.

    this is an interesting topic, and my experience leads me to rather

    different conclusions.  in the application which i've been working

    on for the last four years, trees -- lists of arbitrary depth and

    complexity -- are ubiquitous.  so is recursion, in what seems like

    a bewildering variety of forms.

    >

    >   - Manfred

    >

    >

    >

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    >

    >

## sa@dfa.com — 2003-05-30 19:08:17

    >    [[10 20 30][40 50 60][70 80]] [[1 2 3] 4 [5 6]] [[-] treemap] treemap

    > [[69 79] [68 78] [67 77]] [66 76] [[65 75] [64 74]]

    >

    > huh -- that works!

     well actually, no it doesn't,  not even close.  not even remotely close.

## wtanksleyjr@cox.net — 2003-05-30 21:15:29

    From: phimvt@...

     >(But, I must say this: I have not really found

    >any applications for the tree combinators, let

    >alone for multi-tree combinators).

     Then you should play with cK for a while, and see what's

    been done with K, J, and APL. Automatic multi-tree

    operation is implicit in all of those languages, and

    the result is just incredibly beautiful.

    I'd _really_ love to see it automatic in Joy -- in fact,

    I'd like to see it become automatic in a freely available

    language, ANY one. All of the above except APL are

    proprietary, so I can't use it for company work (not

    interested in APL).

     >  - Manfred

     -Billy

## stevan apter — 2003-05-30 22:12:36

    ----- Original Message -----

    From: <wtanksleyjr@...>

    To: <concatenative@yahoogroups.com>

    Sent: Friday, May 30, 2003 5:15 PM

    Subject: Re: Re: [stack] pervasive operations, n-ary treemap

    > From: phimvt@...

    > >(But, I must say this: I have not really found

    > >any applications for the tree combinators, let

    > >alone for multi-tree combinators).

    >

    > Then you should play with cK for a while, and see what's

    > been done with K, J, and APL. Automatic multi-tree

    > operation is implicit in all of those languages, and

    > the result is just incredibly beautiful.

    of course i agree with this - the array languages are

    very beautiful.

    allow me to provide a brief taxonomy.

    until 1980 or so APL was limited to rectangular arrays

    of simple scalars:  vectors, matrices, rank 3 arrays,

    &c.  around 1980 the time-sharing apl vendors i.p. sharp

    and scientific time-sharing corporation released their

    nested array products:  arrays were still rectangular,

    but their scalar elements could be "enclosed" or "boxed"

    arrays.  a year or two later (i may have the chronology

    wrong, but it's close) i.b.m. released their apl2 product,

    which also supported nested arrays.  the main difference

    at this point (beyond a few disagreements about the

    primitives) was over whether the enclose of a simple

    scalar was simple or not -- a small point which consumed

    extraordinary quantities of polemical energy and generated

    corresponding heat.

    in 1993, arthur whitney invented k, which (for many of

    us) resolved the disagreement by returning to the original

    apl data semantics and relaxing the requirement of

    rectangularity:  arrays could be ragged.  in fact, what

    this amounted to was replacing APL arrays with lists.

    a matrix is a list all of whose sublists have the same

    size; a 3-d array is a list all of whose sublists agree

    in both dimensions; &c.  so rectangular arrays are a

    special case of lists.  (almost:  rectangular arrays

    with null axes can't be represented in an unenhanced

    list semantics.)

    around the same time, arthur spent a weekend with ken

    iverson, the APL zeus, and roger hui.  ken was interested

    in implementing some of his ideas in a new language, and

    arthur was able to get ken and roger off to a running

    start by providing the core of an interpreter in c, which

    eventually materialized as the 'j' language.  roger

    tells the story in a quote-quad interview, after he

    received the society's iverson award.  j continues down

    the nested array path (which i believe they call "boxed

    arrays").

    of course this is a very partial history - e.g. the apl2

    guys have gone on to found smartarrays inc., and there

    are various APLs floating around, but they have, in my

    opinion, been superceded and rendered obsolete by j and k.

    personally, i prefer the simpler data universe of k.  the

    only reason i can see to even have enclosed arrays is to

    satisfy the rectangularity condition of APL.  so i would

    look first to k to provide an array programming (i.e. list

    programming) model for possible extension of joy in that

    direction.

    a personal note:  i encountered APL first in february 1970,

    while working as a fortran programmer for the u.s. antarctic

    research project.  our shipboard computer was an i.b.m.

    1130, with a whopping 8k of core memory.  the 1130 had a

    selectric typewriter console, which made it a natural for

    APL, which at that time supported only console input and

    output.  those long antarctic nights provided a perfect

    environment in which to master all those cool-looking greek

    symbols.  for a time, our boat went its way amongst the

    bergs under the direction of an APL program designed to

    process satellite fix input.

    ah youth, carefree and immortal.

    >

    > I'd _really_ love to see it automatic in Joy -- in fact,

    > I'd like to see it become automatic in a freely available

    > language, ANY one. All of the above except APL are

    > proprietary, so I can't use it for company work (not

    > interested in APL).

    >

    > >  - Manfred

    >

    > -Billy

    >

    >

    >

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    >

    >

## phimvt@lurac.latrobe.edu.au — 2003-06-02 03:29:46

    On Fri, 30 May 2003, stevan apter wrote:

    [..]

    > here's what my joy console looks like:

    >

    >     JOY  -  compiled at 15:46:02 on May 13 2003 (NOBDW)

    >     Copyright 2001 by Manfred von Thun

    >     [[1 2 3] 4 [5 6]]  [0 swap -]  treemap

    >     .

    >     [0 swap -]

    >     .

    >     [[1 2 3] 4 [5 6]]

    I see what is happening. The treemap combinator is actually

    defined in the sequence library "seqlib.joy". After the two

    heading lines your run does not mention any libraries. Since

    you mention something to this effect in a later posting, I'll

    quickly explain here:

    "Automatic" inclusion of libraries:

        Under Unix and under VMS the Joy interpreter does this:

        If in the current working directory there is a file called

        "usrlib.joy", then Joy will start reading from there

        (typically there will be personal definitions, and also

        some calls of the form '"somethinglib.joy" include.',

        most commonly '"inilib.joy" include.", and if that has been

        included some further calls become possible such as

        '"seqlib" libload.'). After the end of all that Joy should

        be ready to read from the terminal.

        But if I remember right you are running Joy from under Windows.

        How you arrange to have at least "usrlib.joy" under

        Windows in your working directory I do not know, maybe

        someone on the group can clarify this.

    "Manual" inclusion of libraries:

        Under Unix and under VMS, if the file "usrlib.joy" does not

        exist then no file is read in automatically. In that case,

        as Joy starts up it is "raw" Joy. You can then make calls

        and definitions all from the terminal. You can also include

        library files, in the style '"somethinglib.joy" include.'.

        Typically you might want to include at least "inilib.joy",

        and then perhaps "seqlib.joy" which contains the definition

        of treemap.

        How you do this under Windows I do not know, again. But

        it should now only need to have the correct pathname - I think

        if your library files are on your Desktop, then you just need

        their names, otherwise their extended name "C\joydir\inilib.joy"

        or something like that. Again, I'm sure a proper Windower from

        the group will clarify this.

    Hope this helps.

    [..]

    > >                                                  It may even

    > > be that one will only want very few specialised operators

    > > to be mapped (or whatever) over trees, and then a more direct

    > > approach might well be called for.

    >

    > this is an interesting topic, and my experience leads me to rather

    > different conclusions.  in the application which i've been working

    > on for the last four years, trees -- lists of arbitrary depth and

    > complexity -- are ubiquitous.

    Well, yes, lists of lists of lists of lists .. I can well imagine

    such creatures occuring in many areas. These are indeed trees, but

    of a very special kind: all the lists have as members either just

    further lists and nothing else or just leaves and nothing else.

    In such trees all leaves occur at the same level (the bottom level).

    For example, a list of list of list of integers can be mapped

    over [p] by '[ [[p] map] map ] map'. Or, if you like,

        DEFINE  mmmap  ==  [map] cons [map] cons map.

    (incidentally a nice example of a constructed program) and then do

           ...  [p] mmmap

    My question is about all the other trees, which contain non-homogeneous

    lists, ones containing as members both other lists and leaves.

    Do you have any examples of those arising in practise?

    The only ones that I would come across are the formulas or expressions

    that arise from various notations e.g. [+ 2 [* 3 4]] for Lisp.

    But these are not the sort of things one would want to (tree)map.

    I have started reading your interesting paper, but so far only

    very superficially. Thanks !

      - Manfred