my interest in joy was triggered by examples contained in manfred's original
papers. those examples suggested that a way of simplifying the expression of
algorithms which had been overlooked by the mainstream programming languages.
as a long-time APLer, i was already convinced that one source of complexity
was explicit looping, but it wasn't until i found myself drowning in a welter
of explicit recursions on one particular project that i began to suspect that
it might be possible to do for recursion what APL had done for looping. joy's
small set of recursive combinators suggested how this might be done.

i'm still puzzled why authors of concatenative languages like cat and factor
have resisted the incorporation of array primitives into their languages. in
the admittedly trivial examples below, why not write

1+til / applied to n generates 0..n-1, then add 1

or

1 drop til 1+ / add 1 to n, generate 0..n, then drop the first

instead of either looping or recursion?

my sense is that programmers (and language designers) *still* do not appreciate
the power of array programming. here's an example i posted the other day on
comp.lang.functional, a general sudoku solver written in q by arthur whitney.
for readability, i've replaced the case statement of q ($[x;y;z]) with if-then-
else pseudocode.

f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p i:x find 0]find til 10]}

note the explicit tail-recursion on 'f' in the else clause. also note that this is
the standard algorithm used in sudoku solvers written in java, python, ruby, ocaml,
&c. compression is achieved through the use of a handlful of array primitives
(til, find, raze, where, all), one iterator (each), a primitive for updating
positions of an array (amend), and a single primitive extended from scalars to
arrays (=).

----- Original Message -----
From: "John Nowak" <john <at> johnnowak.com>
To: <concatenative <at> yahoogroups.com>
Sent: Thursday, February 28, 2008 9:43 PM
Subject: Re: [stack] disallowing recursive definitions

>
> On Feb 28, 2008, at 6:47 PM, Joe Bowbeer wrote:
>
>> As a former Schemer and fan of continuations, I'm conditioned to
>> view (tail)
>> recursion as the simpler, more powerful concept. Not looping.
>
> I have a Scheme background as well.
>
>> Functional programming languages rely on recursion and still boast of
>> referential transparency: the ability to substitute function
>> applications by
>> their definitions. But they don't take the substitution as far as
>> you'd
>> like to...
>
> Indeed.
>
>> Functional languages favor recursion over looping because looping
>> traditionally requires a loop variable whose value changes: a side
>> effect.
>
> What's surprising is how easily the stack lets you write code in an
> imperative style while remaining purely functional. Here's a small
> example where, given a natural number, we construct a list from 1 to
> that number:
>
> ; Scheme, via recursion
>
> (define (foo n)
> (let f ((n n) (xs '()))
> (if (zero? n)
> xs
> (f (- n 1) (cons n xs)))))
>
> ; Joy-like, via recursive combinator
>
> foo = null swap ((cons) keep pred) (zero?) until pop
>
> ; Another Joy-like version
> ; (prec :: A int int (A int -> A) -> A)
>
> foo = null swap 1 (cons) prec
>
> - John
>

> i'm still puzzled why authors of concatenative languages like cat and factor
> have resisted the incorporation of array primitives into their languages. in
> the admittedly trivial examples below, why not write
>
> 1+til / applied to n generates 0..n-1, then add 1
>
> or
>
> 1 drop til 1+ / add 1 to n, generate 0..n, then drop the first
>
> instead of either looping or recursion?
>

or in postfix notation:

til 1 +
1 + til 1 drop

----- Original Message -----
From: "Stevan Apter" <sa <at> nsl.com>
To: <concatenative <at> yahoogroups.com>
Sent: Saturday, March 01, 2008 8:51 AM
Subject: Re: [stack] disallowing recursive definitions

> my interest in joy was triggered by examples contained in manfred's original
> papers. those examples suggested that a way of simplifying the expression of
> algorithms which had been overlooked by the mainstream programming languages.
> as a long-time APLer, i was already convinced that one source of complexity
> was explicit looping, but it wasn't until i found myself drowning in a welter
> of explicit recursions on one particular project that i began to suspect that
> it might be possible to do for recursion what APL had done for looping. joy's
> small set of recursive combinators suggested how this might be done.
>
> i'm still puzzled why authors of concatenative languages like cat and factor
> have resisted the incorporation of array primitives into their languages. in
> the admittedly trivial examples below, why not write
>
> 1+til / applied to n generates 0..n-1, then add 1
>
> or
>
> 1 drop til 1+ / add 1 to n, generate 0..n, then drop the first
>
> instead of either looping or recursion?
>
> my sense is that programmers (and language designers) *still* do not appreciate
> the power of array programming. here's an example i posted the other day on
> comp.lang.functional, a general sudoku solver written in q by arthur whitney.
> for readability, i've replaced the case statement of q ($[x;y;z]) with if-then-
> else pseudocode.
>
> f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p i:x find 0]find til 10]}
>
> note the explicit tail-recursion on 'f' in the else clause. also note that this is
> the standard algorithm used in sudoku solvers written in java, python, ruby, ocaml,
> &c. compression is achieved through the use of a handlful of array primitives
> (til, find, raze, where, all), one iterator (each), a primitive for updating
> positions of an array (amend), and a single primitive extended from scalars to
> arrays (=).
>
>
> ----- Original Message -----
> From: "John Nowak" <john <at> johnnowak.com>
> To: <concatenative <at> yahoogroups.com>
> Sent: Thursday, February 28, 2008 9:43 PM
> Subject: Re: [stack] disallowing recursive definitions
>
>
>>
>> On Feb 28, 2008, at 6:47 PM, Joe Bowbeer wrote:
>>
>>> As a former Schemer and fan of continuations, I'm conditioned to
>>> view (tail)
>>> recursion as the simpler, more powerful concept. Not looping.
>>
>> I have a Scheme background as well.
>>
>>> Functional programming languages rely on recursion and still boast of
>>> referential transparency: the ability to substitute function
>>> applications by
>>> their definitions. But they don't take the substitution as far as
>>> you'd
>>> like to...
>>
>> Indeed.
>>
>>> Functional languages favor recursion over looping because looping
>>> traditionally requires a loop variable whose value changes: a side
>>> effect.
>>
>> What's surprising is how easily the stack lets you write code in an
>> imperative style while remaining purely functional. Here's a small
>> example where, given a natural number, we construct a list from 1 to
>> that number:
>>
>> ; Scheme, via recursion
>>
>> (define (foo n)
>> (let f ((n n) (xs '()))
>> (if (zero? n)
>> xs
>> (f (- n 1) (cons n xs)))))
>>
>> ; Joy-like, via recursive combinator
>>
>> foo = null swap ((cons) keep pred) (zero?) until pop
>>
>> ; Another Joy-like version
>> ; (prec :: A int int (A int -> A) -> A)
>>
>> foo = null swap 1 (cons) prec
>>
>> - John
>>
>

> my sense is that programmers (and language designers) *still* do not
> appreciate
> the power of array programming. here's an example i posted the other day on
> comp.lang.functional, a general sudoku solver written in q by arthur
> whitney.
> for readability, i've replaced the case statement of q ($[x;y;z]) with
> if-then-
> else pseudocode.
>
> f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p
> i:x find 0]find til 10]}
>
> note the explicit tail-recursion on 'f' in the else clause. also note that
> this is
> the standard algorithm used in sudoku solvers written in java, python,
> ruby, ocaml,
> &c. compression is achieved through the use of a handlful of array
> primitives
> (til, find, raze, where, all), one iterator (each), a primitive for
> updating
> positions of an array (amend), and a single primitive extended from scalars
> to
> arrays (=).

I'm having a little trouble parsing this example. Do you think you
could translate this example to XY, or at least insert parens so it's
clear where the grouping is, and explain what 27=x... means? The
resistance of Factor to add array primitives comes from the idea
within the community that explicit, strongly typed array operations
are sufficient. (There are words like v* to multiply two sequences of
numbers.) Replacing v* with * is something that looks prettier but
doesn't directly add more functionality. Maybe there's someplace in
the middle, where functions like raze can be added without going to
full-blown array primitives. Another problem with array primitives is
that, generalized, they make arrays a little less first-class, but
this may be a misunderstanding on my part.

Thanks,

Dan

----- Original Message -----
From: "Daniel Ehrenberg" <microdan <at> gmail.com>
To: <concatenative <at> yahoogroups.com>
Sent: Saturday, March 01, 2008 9:17 AM
Subject: Re: [stack] disallowing recursive definitions

>> my sense is that programmers (and language designers) *still* do not
>> appreciate
>> the power of array programming. here's an example i posted the other day on
>> comp.lang.functional, a general sudoku solver written in q by arthur
>> whitney.
>> for readability, i've replaced the case statement of q ($[x;y;z]) with
>> if-then-
>> else pseudocode.
>>
>> f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p
>> i:x find 0]find til 10]}
>>
>> note the explicit tail-recursion on 'f' in the else clause. also note that
>> this is
>> the standard algorithm used in sudoku solvers written in java, python,
>> ruby, ocaml,
>> &c. compression is achieved through the use of a handlful of array
>> primitives
>> (til, find, raze, where, all), one iterator (each), a primitive for
>> updating
>> positions of an array (amend), and a single primitive extended from scalars
>> to
>> arrays (=).
>
> I'm having a little trouble parsing this example. Do you think you
> could translate this example to XY, or at least insert parens so it's
> clear where the grouping is, and explain what 27=x... means?

hi dan.

f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p i:x find 0]find til 10]}

here's the grouping:

f:{if all x
then enlist x
else raze
f each
amend[x;i]each
where
27=
x[raze p i:x find 0]find
til 10]}

i.e. in the else clause, execute right-to-left (so read left-to-right).

The
> resistance of Factor to add array primitives comes from the idea
> within the community that explicit, strongly typed array operations
> are sufficient. (There are words like v* to multiply two sequences of
> numbers.) Replacing v* with * is something that looks prettier but
> doesn't directly add more functionality. Maybe there's someplace in
> the middle, where functions like raze can be added without going to
> full-blown array primitives. Another problem with array primitives is
> that, generalized, they make arrays a little less first-class, but
> this may be a misunderstanding on my part.

note that in f, there is only one "array primitive": in x=y, x and y
are either scalars or, if both are arrays, they must be arrays of the
same "shape" (a scalar is considered to be the same shape as any array.)

perhaps this a misunderstanding about the term "array primitive". in APL,
+, <, =, &c. are extended to arrays, but they are all scalar primitives,
i.e. they are defined on scalars. primitives like 'find' and 'where' are
array (or list) primitives: they take arrays as arguments and return arrays
or scalars as results.

perhaps this is a special case of a wider problem, viz. imprecision about
the terms "array", "list", &c. i use these terms interchangeably, whereas
others may not. for me, a list or array is an ordered collection parts of
which (sublists or subarrays or scalars) can be indexed/amended by position.
note that in some array languages, e.g. k/q, other "bulk datatypes" exist,
e.g. maps (or dictionaries), which are unordered collections parts of which
can be indexed by symbols in the domain. but i always mean objects of
all bulk-types to be "first-class": they can be assigned, passed as
arguments, returned as results. in every way, they are semantically
identical to the atomic values out of which they are constructed. moreover,
all primitives (e.g. +) are defined (at least in principle) on all bulk-types.
e.g. a vector can be added to a map (yielding a map), a table can be added to
a vector (yielding a table), &c. this "orthogonality property" is partly why
complex algorithms like the sudoku solver can be expressed so simply.

>
> Thanks,
>
> Dan
>

On Sat, Mar 1, 2008 at 8:51 AM, Stevan Apter <sa <at> nsl.com> wrote:
> i'm still puzzled why authors of concatenative languages like cat and factor
> have resisted the incorporation of array primitives into their languages.

Map, filter, fold, etc. are all part of the core Cat language. I
consider all of these array primitives. The Cat concept of list is
more or less analgous to an array, but is agnostic about
implementation details. An implementation is left to its own devices
as to what the performance characteristics of lists are. Sorry its not
more clear in the current documentation.

>in
> the admittedly trivial examples below, why not write
>
> 1+til / applied to n generates 0..n-1, then add 1

In Cat

n [1 +] map

> or
>
> 1 drop til 1+ / add 1 to n, generate 0..n, then drop the first

n [1] drop

> instead of either looping or recursion?

Sure completely valid. Of course sometimes loops are fun to have
outside of the context of a list.

> my sense is that programmers (and language designers) *still* do not
> appreciate
> the power of array programming.

Well I know that Slava (the author of Factor) does, and I'd like to
feel that I do. Its not really fair to single us out in this.

> here's an example i posted the other day on
> comp.lang.functional, a general sudoku solver written in q by arthur
> whitney.
> for readability, i've replaced the case statement of q ($[x;y;z]) with
> if-then-
> else pseudocode.
>
> f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p
> i:x find 0]find til 10]}
>
> note the explicit tail-recursion on 'f' in the else clause. also note that
> this is
> the standard algorithm used in sudoku solvers written in java, python, ruby,
> ocaml,
> &c. compression is achieved through the use of a handlful of array
> primitives
> (til, find, raze, where, all), one iterator (each), a primitive for updating
> positions of an array (amend), and a single primitive extended from scalars
> to
> arrays (=).

I'll have to look more closely at this (I don't know what "til",
"find", "raze", "where", "all", "each", and "amend" do). But it should
be easy to implement something similar.

Nonetheless, your original point is still valid that some more array
processing primitives would be valuable in Cat. I'll add some to the
specification.

- Christopher

----- Original Message -----
From: "Christopher Diggins" <cdiggins <at> gmail.com>
To: <concatenative <at> yahoogroups.com>
Sent: Saturday, March 01, 2008 2:35 PM
Subject: Re: [stack] disallowing recursive definitions

> On Sat, Mar 1, 2008 at 8:51 AM, Stevan Apter <sa <at> nsl.com> wrote:
>> i'm still puzzled why authors of concatenative languages like cat and factor
>> have resisted the incorporation of array primitives into their languages.
>
> Map, filter, fold, etc. are all part of the core Cat language. I
> consider all of these array primitives.

i haven't looked at cat's implementation of these combinators. how
would you use map to add a matrix to a vector? for example, suppose
you have

1 2 3 4
5 6 7 8

and

10 20 30 40

you want to add the vector to each row of the matrix. now suppose
you have a second vector

11 12

and you want to add each of those to each row of the matrix.

in general, how do you map/filter/fold/zip functions which take more
than one argument?

> The Cat concept of list is
> more or less analgous to an array, but is agnostic about
> implementation details. An implementation is left to its own devices
> as to what the performance characteristics of lists are. Sorry its not
> more clear in the current documentation.
>
>>in
>> the admittedly trivial examples below, why not write
>>
>> 1+til / applied to n generates 0..n-1, then add 1
>
> In Cat
>
> n [1 +] map
>
>> or
>>
>> 1 drop til 1+ / add 1 to n, generate 0..n, then drop the first
>
> n [1] drop
>
>> instead of either looping or recursion?
>
> Sure completely valid. Of course sometimes loops are fun to have
> outside of the context of a list.

sometimes they're necessary, but i can't say i have any fun writing
them.

>
>> my sense is that programmers (and language designers) *still* do not
>> appreciate
>> the power of array programming.
>
> Well I know that Slava (the author of Factor) does, and I'd like to
> feel that I do. Its not really fair to single us out in this.

that's true in some sense. i should have said something like this:
given the role that simplicity and expressiveness play in the cognitive
economy of concatenative language designers, i'd expect them to be
close students of the gains in these areas made by iverson and his
students over the last 45 years. (yes, it really has been that long
since iverson published "a programming language.")

>
>> here's an example i posted the other day on
>> comp.lang.functional, a general sudoku solver written in q by arthur
>> whitney.
>> for readability, i've replaced the case statement of q ($[x;y;z]) with
>> if-then-
>> else pseudocode.
>>
>> f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p
>> i:x find 0]find til 10]}
>>
>> note the explicit tail-recursion on 'f' in the else clause. also note that
>> this is
>> the standard algorithm used in sudoku solvers written in java, python, ruby,
>> ocaml,
>> &c. compression is achieved through the use of a handlful of array
>> primitives
>> (til, find, raze, where, all), one iterator (each), a primitive for updating
>> positions of an array (amend), and a single primitive extended from scalars
>> to
>> arrays (=).
>
> I'll have to look more closely at this (I don't know what "til",
> "find", "raze", "where", "all", "each", and "amend" do). But it should
> be easy to implement something similar.
>
> Nonetheless, your original point is still valid that some more array
> processing primitives would be valuable in Cat. I'll add some to the
> specification.

i'm not sure i had much of a point, beyond wanting to make a gesture of
mental irritability. concatenative languages are lovely, but, judged on
the basis of how much code one has to write, not expressive enough to
convince me i should use one.

>
> - Christopher
>

Christopher Diggins <cdiggins <at> gmail.com> wrote:
> Stevan Apter <sa <at> nsl.com> wrote:
> > i'm still puzzled why authors of concatenative languages like cat and factor
> > have resisted the incorporation of array primitives into their languages.

It shouldn't be a puzzle... They don't understand. It's hard to get
started learning about it.

The existing array languages are, with only two exceptions, closed
source. (The early J interpreter was available, although I don't know
how to get it now, and I couldn't ever figure out how to read it.) A+
is unreservedly open source, of course, as is QNIAL. I found A+ to be
very hard to figure out, QNIAL fairly easy.

> Map, filter, fold, etc. are all part of the core Cat language. I
> consider all of these array primitives.

I suppose they technically are. They're just a beginning, though.

> The Cat concept of list is
> more or less analgous to an array, but is agnostic about
> implementation details. An implementation is left to its own devices
> as to what the performance characteristics of lists are. Sorry its not
> more clear in the current documentation.

That's a pretty important point, really. It makes the difference
between an O(n) implementation and an O(n^2) one. I'd really rather it
be specified.

> > my sense is that programmers (and language designers) *still* do not
> > appreciate the power of array programming.

We don't. I don't. I wish I did, but it's a steep hill to climb.

> Nonetheless, your original point is still valid that some more array
> processing primitives would be valuable in Cat. I'll add some to the
> specification.

I like the implicit iteration.

> - Christopher

-Wm

On Sat, Mar 1, 2008 at 5:08 PM, William Tanksley, Jr
<wtanksleyjr <at> gmail.com> wrote:
>
> Christopher Diggins <cdiggins <at> gmail.com> wrote:
> > Stevan Apter <sa <at> nsl.com> wrote:
> > > i'm still puzzled why authors of concatenative languages like cat and
> factor
> > > have resisted the incorporation of array primitives into their
> languages.
>
> It shouldn't be a puzzle... They don't understand.

That is awfully presumptious of you.

- Christopher

----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr <at> gmail.com>
To: <concatenative <at> yahoogroups.com>
Sent: Saturday, March 01, 2008 5:08 PM
Subject: Re: [stack] disallowing recursive definitions

> Christopher Diggins <cdiggins <at> gmail.com> wrote:
>> Stevan Apter <sa <at> nsl.com> wrote:
>> > i'm still puzzled why authors of concatenative languages like cat and factor
>> > have resisted the incorporation of array primitives into their languages.
>
> It shouldn't be a puzzle... They don't understand. It's hard to get
> started learning about it.
>
> The existing array languages are, with only two exceptions, closed
> source. (The early J interpreter was available, although I don't know
> how to get it now, and I couldn't ever figure out how to read it.) A+
> is unreservedly open source, of course, as is QNIAL. I found A+ to be
> very hard to figure out, QNIAL fairly easy.

there are several free APL interpreters available:

http://www.vector.org.uk/?area=dnld&page=content/interpreters

vector is probably the best general site for information about array
languages. J and Q (K) are ascii. J is free, but i agree that is
somewhat forbidding. a freeware version of K5 has been planned, but
isn't available yet.

>
>> Map, filter, fold, etc. are all part of the core Cat language. I
>> consider all of these array primitives.
>
> I suppose they technically are. They're just a beginning, though.

yes.

>
>> The Cat concept of list is
>> more or less analgous to an array, but is agnostic about
>> implementation details. An implementation is left to its own devices
>> as to what the performance characteristics of lists are. Sorry its not
>> more clear in the current documentation.
>
> That's a pretty important point, really. It makes the difference
> between an O(n) implementation and an O(n^2) one. I'd really rather it
> be specified.

yes. if you intend to let these datastructures bear the full weight of
"array programming" (by which i mean crafting your algorithms in such
a way that the language performs the iteration) then the implementation
had better be sharp -- at least as efficient as what the programmer can
do by explicitly iterating (and, one would hope, better.)

>
>> > my sense is that programmers (and language designers) *still* do not
>> > appreciate the power of array programming.
>
> We don't. I don't. I wish I did, but it's a steep hill to climb.

it goes in both directions. when i'm forced to write the simplest loop,
i usually get it wrong the first time, the second time, ... it's
embarrassing! the trick is to internalize the idioms, which means
learning them in the first place. a good resource is eugene macdonell's
k "finger exercises:

http://www.kx.com/technical/contribs/eugene/kidioms.html

so-called because having them at your fingertips as idioms is where
the productivity comes from.

and a good exercise: solve them in your favorite language.

>
>> Nonetheless, your original point is still valid that some more array
>> processing primitives would be valuable in Cat. I'll add some to the
>> specification.
>
> I like the implicit iteration.

me too, but getting the design right isn't easy, and if it's an after-
thought, it won't simplify things at all.

>
>> - Christopher
>
> -Wm
>

Christopher Diggins <cdiggins <at> gmail.com> wrote:
> William Tanksley, Jr <wtanksleyjr <at> gmail.com> wrote:
> > > > i'm still puzzled why authors of concatenative languages like cat and
> > factor
> > > > have resisted the incorporation of array primitives into their
> > languages.

> > It shouldn't be a puzzle... They don't understand.

> That is awfully presumptious of you.

I didn't expect or intend to offend, but no, it's not presumptuous.
You yourself said, 'I don't know what "til", "find", "raze", "where",
"all", "each", and "amend" do'. The "array primitives" that you do
understand, you only know about because you're extremely conversant
with functional list-processing languages (not array languages). This
shouldn't be insulting to you; you're a highly productive and
intelligent person who thoroughly understands CS. I want to challenge
the array language community to come out and educate us if they're
dissatisfied with our work.

> - Christopher

-Wm