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

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