disallowing recursive definitions
John Nowak — 2008-02-28 20:39:47
Recently, I mentioned that if you disallow recursive definitions, then
definitions can be thought of as macros or rewrite rules. In other
words, you can replace every occurrence of foo in a program with foo's
definition and then remove the definition without changing the meaning
of the program. It is therefore trivial to remove all definitions in a
program and be left with only a single function that only uses
primitives built in to the system.
This dual view of definitions as functions and definitions as rewrite
rules is, at least, aesthetically appealing. I began to think of what
some other benefits of disallowing recursive definitions might be:
1. It isn't necessary to do tail call optimization; an appropriate
combinator is used instead.
2. The type system and formalization of the language in general are
simplified. A restriction on recursive definitions may actually be a
requirement for a truly compositional type system.
3. WIth a small addition to the type system, it becomes possible to
prove that the stack will not overflow given the correct set of
recursive combinators. (Combinators like linrec would need to be
disallowed or specially handled.)
4. Similarly, it becomes possible compute the maximum number of items
that will ever be on the stack, and pre-allocate a stack of exactly
the right size upon program initialization.
5. It allows additional ways of presenting code, such as an editor
that can expand a definition inline to show what it does while still
displaying a program with the same meaning.
6. It becomes possible to prove termination when using recursive
combinators that always terminate given that their arguments always
terminate (such as primrec).
There are likely other benefits that I'm missing.
The question therefore is how critical recursive definitions actually
are. They're not necessary in an absolute sense; any recursive
function can be expressed using while. Essentially, it seems like
disallowing recursive definitions has the same sort of tradeoff as
disallowing multiple references to the same value (and therefore
enforcing linearity): Many nice properties emerge and things are
simplified, but it may simply be too much of a pain. I think it may be
worth a shot.
Thoughts?
- John
John Nowak — 2008-02-28 20:43:28
On Feb 28, 2008, at 3:39 PM, John Nowak wrote:
> 6. It becomes possible to prove termination when using recursive
> combinators that always terminate given that their arguments always
> terminate (such as primrec).
To clarify, this is possible with recursive definitions as well.
Without them however, it's a trivial addition to the type system that
works exactly the same way that tracking of side effects works.
- John
John Cowan — 2008-02-28 20:44:53
John Nowak scripsit:
> Recently, I mentioned that if you disallow recursive definitions, then
> definitions can be thought of as macros or rewrite rules.
Sure, but then you can only compute primitive-recursive functions
(roughly speaking, ones in which all loops are bounded at compile time).
--
Do what you will, John Cowan
this Life's a Fiction
cowan@...
And is made up of
http://www.ccil.org/~cowan
Contradiction. --William Blake
Daniel Ehrenberg — 2008-02-28 21:00:32
> Recently, I mentioned that if you disallow recursive definitions, then
> definitions can be thought of as macros or rewrite rules. In other
> words, you can replace every occurrence of foo in a program with foo's
> definition and then remove the definition without changing the meaning
> of the program. It is therefore trivial to remove all definitions in a
> program and be left with only a single function that only uses
> primitives built in to the system.
>
> This dual view of definitions as functions and definitions as rewrite
> rules is, at least, aesthetically appealing. I began to think of what
> some other benefits of disallowing recursive definitions might be:
>
> 1. It isn't necessary to do tail call optimization; an appropriate
> combinator is used instead.
> 2. The type system and formalization of the language in general are
> simplified. A restriction on recursive definitions may actually be a
> requirement for a truly compositional type system.
> 3. WIth a small addition to the type system, it becomes possible to
> prove that the stack will not overflow given the correct set of
> recursive combinators. (Combinators like linrec would need to be
> disallowed or specially handled.)
> 4. Similarly, it becomes possible compute the maximum number of items
> that will ever be on the stack, and pre-allocate a stack of exactly
> the right size upon program initialization.
> 5. It allows additional ways of presenting code, such as an editor
> that can expand a definition inline to show what it does while still
> displaying a program with the same meaning.
> 6. It becomes possible to prove termination when using recursive
> combinators that always terminate given that their arguments always
> terminate (such as primrec).
>
> There are likely other benefits that I'm missing.
>
> The question therefore is how critical recursive definitions actually
> are. They're not necessary in an absolute sense; any recursive
> function can be expressed using while. Essentially, it seems like
> disallowing recursive definitions has the same sort of tradeoff as
> disallowing multiple references to the same value (and therefore
> enforcing linearity): Many nice properties emerge and things are
> simplified, but it may simply be too much of a pain. I think it may be
> worth a shot.
>
> Thoughts?
>
> - John
Strictly speaking, recursive functions aren't necessary. However, they
make code a lot more readable than directly using combinators which
take 4 or 5 quotations. Try expressing the Magic Five algorithm (see
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22)
to get the median of an array in linear time (for guaranteed O(n log
n) Quicksort) in terms of a recursive combinator. It'd be really hard,
and I'm not sure which combinator would be appropriate. So, maybe you
don't want recursive functions strictly in the minimal formalized
subset of your language, but, like lexically scoped variables, it
might be nice if the compiler did the appropriate transformations to
allow them in user code.
Also, about restricting the set of combinators so the stack doesn't
overflow: I'm not sure if that's worth it. If there's no explicit
recursion, you'd want the set of combinators included to be as general
as possible. (There is a combinator, condnestrec, which encodes
general recursion, and this would obviously not be included if you
want to prevent stack overflow.) Things like depth-first search are
much easier to express on the system stack (which could overflow from
certain graphs) than on an explicit stack, though strictly speaking
it's possible either way (and I guess in some cases you would actually
want to use an explicit stack).
Dan
Daniel Ehrenberg — 2008-02-28 21:04:09
> Sure, but then you can only compute primitive-recursive functions
> (roughly speaking, ones in which all loops are bounded at compile time).
With linrec and cons, I think you could build yourself an ad-hoc
variable-depth stack anyway, where loops aren't necessarily bounded.
It'd just be awkward and not any more efficient.
John Cowan — 2008-02-28 21:58:56
Daniel Ehrenberg scripsit:
> > Sure, but then you can only compute primitive-recursive functions
> > (roughly speaking, ones in which all loops are bounded at compile time).
>
> With linrec and cons, I think you could build yourself an ad-hoc
> variable-depth stack anyway, where loops aren't necessarily bounded.
> It'd just be awkward and not any more efficient.
True. It would be interesting to see a concatenative language
with support for data/codata, where you recurse downward on data
and upward on codata, a la "total functional programming".
--
John Cowan <
cowan@...>
http://www.ccil.org/~cowan
Raffiniert ist der Herrgott, aber boshaft ist er nicht.
--Albert Einstein
Christopher Diggins — 2008-02-28 22:23:03
On Thu, Feb 28, 2008 at 3:44 PM, John Cowan <
cowan@...> wrote:
> John Nowak scripsit:
> > Recently, I mentioned that if you disallow recursive definitions, then
> > definitions can be thought of as macros or rewrite rules.
>
> Sure, but then you can only compute primitive-recursive functions
> (roughly speaking, ones in which all loops are bounded at compile time).
I don't believe this is true. The approach I take is to pass the
function definition as a named parameter to the function, and perform
the point-free conversion.
In Cat I can write the fibonnacci function (a tree recursive
procedure) to take its body as an argument:
>> define fibrec { \f.\n.[n 1 <= [1] [f n 1 - f apply f n 2 - f apply +] if] }
Which my horrible horrible abstraction algorithm translates to:
[dup dup [[[dup dup dup] dip [[[[id 1 <= [1]] papply dip] papply dip]
papply dip] papply dip] dip] dip [[[[[[id] dip id 1 -] papply dip id
apply] papply dip id] dip id 2 -] papply papply dip id apply +] papply
papply papply papply papply papply if]
>> define fib { fibrec swap fibrec apply }
>> 5 fib
8
Incidentally this managed to completely corrupt my type checker, thanks a lot!
:-)
- Christopher
Joe Bowbeer — 2008-02-28 23:47:51
On Thu, Feb 28, 2008 at 12:39 PM, John Nowak wrote:
> Recently, I mentioned that if you disallow recursive definitions, then
> definitions can be thought of as macros or rewrite rules. In other
> words, you can replace every occurrence of foo in a program with foo's
> definition and then remove the definition without changing the meaning
> of the program. It is therefore trivial to remove all definitions in a
> program and be left with only a single function that only uses
> primitives built in to the system.
>
> This dual view of definitions as functions and definitions as rewrite
> rules is, at least, aesthetically appealing. I began to think of what
> some other benefits of disallowing recursive definitions might be:
>
> 1. It isn't necessary to do tail call optimization; an appropriate
> combinator is used instead.
> 2. The type system and formalization of the language in general are
> simplified. A restriction on recursive definitions may actually be a
> requirement for a truly compositional type system.
> 3. WIth a small addition to the type system, it becomes possible to
> prove that the stack will not overflow given the correct set of
> recursive combinators. (Combinators like linrec would need to be
> disallowed or specially handled.)
> 4. Similarly, it becomes possible compute the maximum number of items
> that will ever be on the stack, and pre-allocate a stack of exactly
> the right size upon program initialization.
> 5. It allows additional ways of presenting code, such as an editor
> that can expand a definition inline to show what it does while still
> displaying a program with the same meaning.
> 6. It becomes possible to prove termination when using recursive
> combinators that always terminate given that their arguments always
> terminate (such as primrec).
>
> There are likely other benefits that I'm missing.
>
> The question therefore is how critical recursive definitions actually
> are. They're not necessary in an absolute sense; any recursive
> function can be expressed using while. Essentially, it seems like
> disallowing recursive definitions has the same sort of tradeoff as
> disallowing multiple references to the same value (and therefore
> enforcing linearity): Many nice properties emerge and things are
> simplified, but it may simply be too much of a pain. I think it may be
> worth a shot.
>
> Thoughts?
>
> - John
>
>
As a former Schemer and fan of continuations, I'm conditioned to view (tail)
recursion as the simpler, more powerful concept. Not looping.
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...
Functional languages favor recursion over looping because looping
traditionally requires a loop variable whose value changes: a side effect.
Recursion also allows tree-like control structures that are not easily
replaced by while loops.
--Joe
[Non-text portions of this message have been removed]
John Nowak — 2008-02-29 02:19:49
On Feb 28, 2008, at 5:23 PM, Christopher Diggins wrote:
> Incidentally this managed to completely corrupt my type checker,
> thanks a lot!
I'd be surprised if Cat were able to handle such a translation in the
general case. Take something like the ackermann function in Haskell:
ack 0 n = n + 1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) (ack m (n - 1))
By passing the function itself as an additional argument, we can
remove the recursive call:
ackcore f 0 n = n + 1
ackcore f m 0 = f f (m - 1) 1
ackcore f m n = f f (m - 1) (f f m (n - 1))
ack m n = ackcore ackcore m n
Unfortunately, this will fail the occurs check. The only way that Cat
could not run into this problem is if it discards the recursive
constraint, which very well could be by your type checker is returning
nonsense. (Of course, it's hard to tell for sure from here.)
- John
John Nowak — 2008-02-29 02:43:36
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
Joe Bowbeer — 2008-02-29 03:04:09
Thanks for the examples.
I think there's a relation between stack languages and Lisp's anaphoric
macros:
http://www.bookshelf.jp/texi/onlisp/onlisp_15.html#SEC99 -and-
http://common-lisp.net/project/anaphora/anaphora.html
In a stack language, the top of the stack is the anaphoric "it".
On Thu, Feb 28, 2008 at 6:43 PM, John Nowak wrote:
>
> 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
>
>
[Non-text portions of this message have been removed]
Christopher Diggins — 2008-02-29 03:26:22
On Thu, Feb 28, 2008 at 9:19 PM, John Nowak <
john@...> wrote:
>
>
> On Feb 28, 2008, at 5:23 PM, Christopher Diggins wrote:
>
> > Incidentally this managed to completely corrupt my type checker,
> > thanks a lot!
>
> I'd be surprised if Cat were able to handle such a translation in the
> general case. Take something like the ackermann function in Haskell:
>
> ack 0 n = n + 1
> ack m 0 = ack (m - 1) 1
> ack m n = ack (m - 1) (ack m (n - 1))
>
> By passing the function itself as an additional argument, we can
> remove the recursive call:
>
> ackcore f 0 n = n + 1
> ackcore f m 0 = f f (m - 1) 1
> ackcore f m n = f f (m - 1) (f f m (n - 1))
>
> ack m n = ackcore ackcore m n
>
> Unfortunately, this will fail the occurs check. The only way that Cat
> could not run into this problem is if it discards the recursive
> constraint,
Cat does.
> which very well could be by your type checker is returning
> nonsense. (Of course, it's hard to tell for sure from here.)
I suspect this is the problem. Here is the fibonacci function again
(forcing it to use ints):
>> define fib { \f.\n.[n 1 lteq_int [1] [f n 1 sub_int f apply f n 2
sub_int f apply add_int] if] }
Here is the type:
fib : ( -> (A int int int int (A int int int int (A int int int int (A int int i
nt int ((B -> C) -> A int int int int) int -> A int int int int) int -> A int in
t int int) int -> A int int int int) int -> A int int int))
Looks like I am going to have reintroduce recursive types.
- Christopher
John Nowak — 2008-02-29 04:34:50
On Feb 28, 2008, at 10:26 PM, Christopher Diggins wrote:
> Looks like I am going to have reintroduce recursive types.
I've come to the same conclusion. They're almost certainly needed if
you disallow recursive definitions. ("Disallow" is really the wrong
way to put it of course; "choose not to introduce" is more accurate.)
- John
John Cowan — 2008-02-29 04:35:06
Joe Bowbeer scripsit:
> As a former Schemer and fan of continuations, I'm conditioned to view (tail)
> recursion as the simpler, more powerful concept. Not looping.
Sure it's simpler and more powerful. That's because it's a general goto
(with transfer of values). And as Dijkstra said, "the go to statement
as it stands is just too primitive; it is too much an invitation to make
a mess of one's program."
If you haven't actually read Dijkstra's squib, it's very much worth reading at
http://www.u.arizona.edu/~rubinson/copyright_violations/Go_To_Considered_Harmful.html
and numerous other places around the Net.
--
John Cowan
http://ccil.org/~cowan cowan@...
We want more school houses and less jails; more books and less arsenals;
more learning and less vice; more constant work and less crime; more
leisure and less greed; more justice and less revenge; in fact, more of
the opportunities to cultivate our better natures. --Samuel Gompers
William Tanksley, Jr — 2008-02-29 06:19:58
John Cowan <
cowan@...> wrote:
> Joe Bowbeer scripsit:
> > As a former Schemer and fan of continuations, I'm conditioned to view (tail)
> > recursion as the simpler, more powerful concept. Not looping.
> Sure it's simpler and more powerful. That's because it's a general goto
> (with transfer of values). And as Dijkstra said, "the go to statement
> as it stands is just too primitive; it is too much an invitation to make
> a mess of one's program."
I'm generally on Knuth's side on this one.
But I don't see how tail recursion is a general goto statement. It
seems structured -- in particular, a tail recursion has only one entry
point.
> John Cowan http://ccil.org/~cowan cowan@...
-Wm
John Cowan — 2008-02-29 13:36:38
William Tanksley, Jr scripsit:
> I'm generally on Knuth's side on this one.
Remember that Knuth thought Dijkstra was *mostly* right, and takes care to
disclaim the notion that he is in favor of random gotos. AFAIK, gotos are
only used in TeX to compensate for Pascal's lack of a return statement.
> But I don't see how tail recursion is a general goto statement. It
> seems structured -- in particular, a tail recursion has only one entry
> point.
If you take an arbitrary tagbody (a list of statements and labels with
gotos embedded in the statements), you can restructure it into a sequence
of functions, one per label, where each function ends by tail calling the
next function in sequence (corresponding to flowing through the label)
and each goto is changed into a tail call. This can be done entirely as
a local transformation.
So while it's true that tail calls have only one entry point, entry
points and labels are basically the same thing from a Scheme perspective,
something that neither Knuth nor Dijkstra deals with. "Lambda: the
ultimate GOTO."
--
Well, I have news for our current leaders John Cowan
and the leaders of tomorrow: the Bill of
cowan@...
Rights is not a frivolous luxury, in force
http://www.ccil.org/~cowan
only during times of peace and prosperity.
We don't just push it to the side when the going gets tough. --Molly Ivins
Joe Bowbeer — 2008-02-29 21:49:58
On Fri, Feb 29, 2008 at 5:36 AM, John Cowan wrote:
> William Tanksley, Jr scripsit:
>
> > I'm generally on Knuth's side on this one.
>
> Remember that Knuth thought Dijkstra was *mostly* right, and takes care to
> disclaim the notion that he is in favor of random gotos. AFAIK, gotos are
> only used in TeX to compensate for Pascal's lack of a return statement.
>
> > But I don't see how tail recursion is a general goto statement. It
> > seems structured -- in particular, a tail recursion has only one entry
> > point.
>
> If you take an arbitrary tagbody (a list of statements and labels with
> gotos embedded in the statements), you can restructure it into a sequence
> of functions, one per label, where each function ends by tail calling the
> next function in sequence (corresponding to flowing through the label)
> and each goto is changed into a tail call. This can be done entirely as
> a local transformation.
>
> So while it's true that tail calls have only one entry point, entry
> points and labels are basically the same thing from a Scheme perspective,
> something that neither Knuth nor Dijkstra deals with. "Lambda: the
> ultimate GOTO."
>
>
I would say, rather: "continuations: the ultimate goto". And I would mean
that in a good way:)
What you're describing is an equivalence between gotos and a sequence of
function calls, something which is not 100% possible without support for
recursion, and something which is not 100% efficient without tail-call
optimization, but I can't see how you can twist this around to indict
recursion.
I do sort of see, now, how the anaphoric (from hell?) quality of stack
programming languages does provide a lot of expressive power without the
need to resort to recursion.
--Joe
[Non-text portions of this message have been removed]
John Cowan — 2008-02-29 22:20:50
Joe Bowbeer scripsit:
> I do sort of see, now, how the anaphoric (from hell?) quality of stack
> programming languages does provide a lot of expressive power without the
> need to resort to recursion.
Remember the original context. I was agreeing with the statement that
tail-calling is a confusing way to write down loops. If you have loop
syntax, you can easily see where the loop begins and ends and exits.
If you just have tail calls, it's very easy to make a balls of it.
I'm not the only Schemer to think this: the standard has named-let and do
for this very reason, and there are lots of more general looping macros.
They all use tail-calling to *implement* loops, but that's not what's
at stake.
--
John Cowan
cowan@... http://ccil.org/~cowan
Any sufficiently-complicated C or Fortran program contains an ad-hoc,
informally-specified bug-ridden slow implementation of half of Common Lisp.
--Greenspun's Tenth Rule of Programming (rules 1-9 are unknown)
Stevan Apter — 2008-03-01 13:51:59
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@...>
To: <concatenative@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
>
Stevan Apter — 2008-03-01 13:55:10
> 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@...>
To: <concatenative@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@...>
> To: <concatenative@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
>>
>
Daniel Ehrenberg — 2008-03-01 14:17:23
> 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
Stevan Apter — 2008-03-01 14:46:18
----- Original Message -----
From: "Daniel Ehrenberg" <microdan@...>
To: <concatenative@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
>
Christopher Diggins — 2008-03-01 19:35:18
On Sat, Mar 1, 2008 at 8:51 AM, Stevan Apter <
sa@...> 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
Stevan Apter — 2008-03-01 20:24:41
----- Original Message -----
From: "Christopher Diggins" <cdiggins@...>
To: <concatenative@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@...> 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
>
William Tanksley, Jr — 2008-03-01 22:08:04
Christopher Diggins <
cdiggins@...> wrote:
> Stevan Apter <sa@...> 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
Christopher Diggins — 2008-03-01 22:11:33
On Sat, Mar 1, 2008 at 5:08 PM, William Tanksley, Jr
<
wtanksleyjr@...> wrote:
>
> Christopher Diggins <cdiggins@...> wrote:
> > Stevan Apter <sa@...> 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
Stevan Apter — 2008-03-01 22:43:04
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, March 01, 2008 5:08 PM
Subject: Re: [stack] disallowing recursive definitions
> Christopher Diggins <cdiggins@...> wrote:
>> Stevan Apter <sa@...> 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
>
William Tanksley, Jr — 2008-03-02 00:26:29
Christopher Diggins <
cdiggins@...> wrote:
> William Tanksley, Jr <wtanksleyjr@...> 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
Stevan Apter — 2008-03-02 01:19:19
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, March 01, 2008 7:26 PM
Subject: Re: [stack] disallowing recursive definitions
> Christopher Diggins <cdiggins@...> wrote:
>> William Tanksley, Jr <wtanksleyjr@...> 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.
that would be me i guess. with only a few exceptions, most of the
arrayheads i know don't have much interest in programming language
theory. hell, they hardly even think of APL as a language. it's
just a tool for doing math, mostly of the financial kind. one
exception that comes to mind is john scholes, CTO and principal
language designer for dyalog, the APL company in the UK. john has
done some very cool work in meshing combinators, type theory, and
array programming.
as far as doing missionary work for arrays to the concatenative
community (jeez i've come to despise that word), isn't that exactly what
i've been doing for five years? :-) three toy languages, innumerable
examples, &c. (ok, now i'm starting to whine like mrs clinton.) seriously
though, i really am puzzled why none of the *serious* language designers
around here (christopher and slava comes to mind) agree that
array primitives and composition-based functional languages form
a natural fit. i've had this conversation with slava over on his
factor chat-room, and i've never been able to persuade him on this
point. i think (and this is just pure speculation on my part) that
you have tohave to have a bad feeling about writing a loop (or an
explicit recursion) before you see the value of the alternative.
you have to resent the fact that the language is making you write
the same damned loop or recursion over and over again. i mean,
these are computers, right? you should be able to tell it just
once: when i add an n-dimensional array and a m-dimensional
array, and the structures cohere, then *you* figure out how to
write the loop.
remember that a lot of APLers learned APL as their first programming
language (in business-school or at one of the investment banks back
in the 80s, or in high-school in the 70s, when APL had a significant
presence in education) and have never been able to bring themselves to
learn java or c. so for them (and for me too) looping and recursion
are what you do when you can't find an array solution to your problem.
maybe you can't find one because there isn't one to be found, or maybe
you're just not looking at the problem correctly. either way, you
have to want to find it. fortunately, problems like that don't crop
up all that often in real life. you have to go out and look for them.
Daniel Ehrenberg — 2008-03-02 01:34:12
> 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.
You're right, there is some misunderstanding. What I was talking
about, and what Factor's missing, is the property of things like "+"
to denote both scalar and vector addition; how, in APL-based
languages, certain operators like +, =, <, etc are defined to map
their operation to atoms within vectors (assuming that shapes match).
Everything else can be fairly easily defined in the library with no
modifications to existing code, if it doesn't already exist. I might
be misunderstanding the nature of array languages, but here's my
problem with this: it creates a primitive, difficult-to-extend concept
of an array which isn't quite first-class as far as I can tell.
Anyway, I'm in the process of decoding the example given (since I
don't know Q) and translating it directly to Factor to see if adding
any idioms would be appropriate. Stevan, could you tell me what the
function f is supposed to take as an argument? Either way, when I find
myself writing explicit tail recursion (which is fairly but not
extremely rare in Factor) I often try to abstract it into a
combinator. When I make these abstractions, it's only because the
existing ones (the higher order functions like each, map and reduce
that Factor and APL basically share) can't express it. I can't imagine
a situation where the fact that + operates on vectors as well as
scalars would change whether I would have to write explicit tail
recursion.
I use tail recursion when I'm either (a) interfacing with non-arrays
that still have to be iterated over in some way, for example an I/O
stream (b) doing something weird that'd be awkward to express in terms
of the abstractions I know. So (a) would be hard to eliminate, and (b)
is more of a cause for concern. I encountered a lot of (b) cases in
implementing things like Unicode normalization and case conversion,
and in those cases I built some semi-general abstractions using tail
recursion. I wonder if some of these should be moved to a more
general-purpose library, but even if they should, that's not a case
for array primitives in the sense of + to be integrated deeply into
the language.
(Just for the record, it's very annoying that there are two languages
named Q, and the one relevant here has a very small online footprint,
and that in that small website, the maintainers can't be bothered to
type out "docs", instead calling the directory "d". Also, I just had a
sort of "whoa" moment when I realized that the same guy who came up
with the first good polynomial-time tree diffing algorithm is the same
guy who's doing all this K/Q stuff...)
Dan
Stevan Apter — 2008-03-02 02:21:23
hi dan
----- Original Message -----
From: "Daniel Ehrenberg" <microdan@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, March 01, 2008 8:34 PM
Subject: Re: [stack] disallowing recursive definitions
>> 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.
>
> You're right, there is some misunderstanding. What I was talking
> about, and what Factor's missing, is the property of things like "+"
> to denote both scalar and vector addition; how, in APL-based
> languages, certain operators like +, =, <, etc are defined to map
> their operation to atoms within vectors (assuming that shapes match).
> Everything else can be fairly easily defined in the library with no
> modifications to existing code, if it doesn't already exist. I might
> be misunderstanding the nature of array languages, but here's my
> problem with this: it creates a primitive, difficult-to-extend concept
> of an array which isn't quite first-class as far as I can tell.
in k, two arrays can be added if either or both are atoms, or their
shapes are conformable. so e.g. a 2x3x4 can be added to an array of
shape 2 (a vector), or 2x3, or 2x3x4, or 2x3x4x... or using various
combinations of each, each-left, and each-right, a 2x3x4 can be added
to a 7x2x3x4 or ... the combinators allow you to control the way
the dimensions line up for the operations.
the k bulk datatypes are: list, map, table (transposed map of lists),
and keytable (map of a table with unique rows to a table.) all
primitives are defined on all types and combinations of types. the
combinations have different comformability and extension rules.
an interesting question is what machinery, and in what strength,
could be added to support user-defined datatypes. at minimum, it
would require (i) defining what the primitives do on each combination
of the new datatype and existing datatypes, and (ii) what the
conformability rules are (since for any datatype x, you would have
to support at the very least lists and maps of x's. an open question.
but k, at least, has been grudging about the addition of new datatypes.
in practice, the policy has always been: simulate the new datatype,
see how useful it is, think about how it could be integrated, &c.
the process seems to take about five years. a small number of ideas
make it into the interpreter core, but when they do, their behavior
is fully defined for each primitive and each bulk datatype. at some
point, i may describe the evolution of the concept of tables in k, from
APL\360 to q. it's an interesting story.
so rather than proliferate datatypes (indefinitely if you leave it
up to the programmer) and give up orthogonality, we try to represent
pieces of the world with a very small set of bulk datatypes and an
orthogonal, generalized set of primitives. (atomic datatypes are
easier to deal with, and there are lots of these.)
>
> Anyway, I'm in the process of decoding the example given (since I
> don't know Q) and translating it directly to Factor to see if adding
> any idioms would be appropriate. Stevan, could you tell me what the
> function f is supposed to take as an argument?
http://www.wagerlabs.com/blog/2008/02/shortest-sudoku.html
Either way, when I find
> myself writing explicit tail recursion (which is fairly but not
> extremely rare in Factor) I often try to abstract it into a
> combinator. When I make these abstractions, it's only because the
> existing ones (the higher order functions like each, map and reduce
> that Factor and APL basically share
no, i think that's a misconception. the k higher-order functions
take functions of any valence. e.g.
f:{x+y*z}
f'[a;b;c] / each applies f to corresponding elements of a,b,c
? ) can't express it. I can't imagine
> a situation where the fact that + operates on vectors as well as
> scalars would change whether I would have to write explicit tail
> recursion.
the sudoku solver contains a single scalar function =. you'd have
to write either a loop or a recursion to handle that. other examples
abound. see eugene macdonell's paper, linked to in an earlier post.
this is what i was unable to get slava to see: extending + to arrays
(or in factor's case, vectors via v+) by itself doesn't seem to get
you anything terribly useful. so big deal, how often do i want to
add vectors?
>
> I use tail recursion when I'm either (a) interfacing with non-arrays
> that still have to be iterated over in some way, for example an I/O
> stream (b) doing something weird that'd be awkward to express in terms
> of the abstractions I know. So (a) would be hard to eliminate,
why isn't a stream a list?
and (b)
> is more of a cause for concern. I encountered a lot of (b) cases in
> implementing things like Unicode normalization and case conversion,
> and in those cases I built some semi-general abstractions using tail
> recursion. I wonder if some of these should be moved to a more
> general-purpose library, but even if they should, that's not a case
> for array primitives in the sense of + to be integrated deeply into
> the language.
lower-to-upper case in k:
u:_ci@[!256;97+!26;-;32]
i:_ic"a99*bc"
u i
"A99*BC"
no loops, no recursion. depends on - being defined on arrays.
look, this is what i meant when i said that the power of the array
approach is not obvious -- it can't be "read off" the definitions of
the primitives. or if i didn't say that, that's what i meant. as
i *have* been trying to say for several years now is that with the
right set of primitives and datatypes, all sorts of non-obvious
solutions arise. that's why the k sudoku is so short (i think it's
down to 54 characters now.)
>
> (Just for the record, it's very annoying that there are two languages
> named Q, and the one relevant here has a very small online footprint,
> and that in that small website, the maintainers can't be bothered to
> type out "docs", instead calling the directory "d". Also, I just had a
> sort of "whoa" moment when I realized that the same guy who came up
> with the first good polynomial-time tree diffing algorithm is the same
> guy who's doing all this K/Q stuff...)
you mean dennis shasha? he's also the math games editor for scientific
american. he's the man!
>
> Dan
>
Daniel Ehrenberg — 2008-03-02 03:34:10
> > I use tail recursion when I'm either (a) interfacing with non-arrays
> > that still have to be iterated over in some way, for example an I/O
> > stream (b) doing something weird that'd be awkward to express in terms
> > of the abstractions I know. So (a) would be hard to eliminate,
>
> why isn't a stream a list?
Well, if by "list" you mean "lazy linked list", Factor doesn't work
like that for input because it'd require memoizing past input values,
and it wouldn't flush output well. If you mean something else I don't
understand. As far as making input something you can iterate over with
"each", that's something I'm working on (though it won't extend to
map).
>
> lower-to-upper case in k:
>
> u:_ci@[!256;97+!26;-;32]
> i:_ic"a99*bc"
> u i
> "A99*BC"
>
> no loops, no recursion. depends on - being defined on arrays.
>
> look, this is what i meant when i said that the power of the array
> approach is not obvious -- it can't be "read off" the definitions of
> the primitives. or if i didn't say that, that's what i meant. as
> i *have* been trying to say for several years now is that with the
> right set of primitives and datatypes, all sorts of non-obvious
> solutions arise. that's why the k sudoku is so short (i think it's
> down to 54 characters now.)
Umm, well, in the general Unicode case, there's some more complicated
table lookup involved, and a bunch of corner cases. My Factor
implementation is somewhat inelegant, and it'd be interesting to see
something in K like that. Your implementation could be written in
Factor as
: >upper ( string -- newstring )
[ dup CHAR: a CHAR: z between? [ CHAR: A CHAR: a - + ] when ] map ;
These definitions have basically the same token count, so this example
doesn't present an advantage or disadvantage of K.
Dan
Stevan Apter — 2008-03-02 06:14:34
----- Original Message -----
From: "Daniel Ehrenberg" <microdan@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, March 01, 2008 10:34 PM
Subject: Re: [stack] disallowing recursive definitions
>> > I use tail recursion when I'm either (a) interfacing with non-arrays
>> > that still have to be iterated over in some way, for example an I/O
>> > stream (b) doing something weird that'd be awkward to express in terms
>> > of the abstractions I know. So (a) would be hard to eliminate,
>>
>> why isn't a stream a list?
>
> Well, if by "list" you mean "lazy linked list", Factor doesn't work
> like that for input because it'd require memoizing past input values,
> and it wouldn't flush output well. If you mean something else I don't
> understand. As far as making input something you can iterate over with
> "each", that's something I'm working on (though it won't extend to
> map).
>>
>> lower-to-upper case in k:
>>
>> u:_ci@[!256;97+!26;-;32]
>> i:_ic"a99*bc"
>> u i
>> "A99*BC"
>>
>> no loops, no recursion. depends on - being defined on arrays.
>>
>> look, this is what i meant when i said that the power of the array
>> approach is not obvious -- it can't be "read off" the definitions of
>> the primitives. or if i didn't say that, that's what i meant. as
>> i *have* been trying to say for several years now is that with the
>> right set of primitives and datatypes, all sorts of non-obvious
>> solutions arise. that's why the k sudoku is so short (i think it's
>> down to 54 characters now.)
>
> Umm, well, in the general Unicode case, there's some more complicated
> table lookup involved, and a bunch of corner cases. My Factor
> implementation is somewhat inelegant, and it'd be interesting to see
> something in K like that. Your implementation could be written in
> Factor as
>
> : >upper ( string -- newstring )
> [ dup CHAR: a CHAR: z between? [ CHAR: A CHAR: a - + ] when ] map ;
>
> These definitions have basically the same token count, so this example
> doesn't present an advantage or disadvantage of K.
apologies for misleading you with how i presented my example. here's
a better explanation:
_ic takes a string and returns a vector of ascii values
_ci takes a vector of ascii values and returns a string
e.g.
_ic "a9."
97 57 46
so we create a constant u by replacing in 0-255 the ascii values for
the lower-case letters with the ascii values for upper-case letters,
and convert that vector to a string:
u:_ci@[!256;97+!26;-;32]
@ takes four arguments: something to amend (in this case 0 to 255),
indices into that thing (97+0 to 25), a function of two arguments (-),
and a value (32). so this reads: int-to-char of subtract 32 from
positions 97+!26 in !256. this is an example of an array idiom --
you use phrases like this so often, you see them as building blocks
in larger structures. what gives this approach its power is that
the same functional schemes are used repeatedly to solve different
problems.
we don't u compute that again. (the language could easily supply
this to us as a predefined "feature", but why bother?)
then for each string we want to upper-case, we convert it:
_ic "ab3Xc"
97 98 51 88 99
and use those values to index out the values in u:
u _ic "ab3Xc"
"AB3XC"
upper-casing is just indexing, so the upper-case function is just
{u _ic x}
>
> Dan
>
Joe Bowbeer — 2008-02-29 05:06:40
On Thu, Feb 28, 2008 at 8:35 PM, John Cowan wrote:
> Joe Bowbeer scripsit:
>
> > As a former Schemer and fan of continuations, I'm conditioned to view
> (tail)
> > recursion as the simpler, more powerful concept. Not looping.
>
> Sure it's simpler and more powerful. That's because it's a general goto
> (with transfer of values). And as Dijkstra said, "the go to statement
> as it stands is just too primitive; it is too much an invitation to make
> a mess of one's program."
>
> If you haven't actually read Dijkstra's squib, it's very much worth
> reading at
>
> http://www.u.arizona.edu/~rubinson/copyright_violations/Go_To_Considered_Harmful.html<http://www.u.arizona.edu/%7Erubinson/copyright_violations/Go_To_Considered_Harmful.html>
> and numerous other places around the Net.
>
>
As far as I know, Dijkstra didn't have a beef with recursion.
The author of the following retrospective writes that Dijkstra probably
considered recursion to be intellectually easier to grasp than iterative
looping:
http://david.tribble.com/text/goto.html
In any event, it's clear from Dijkstra's letter than he didn't consider
recursion to be harmful!
To avoid confusion, I should have used the word "elegant".
Recursion is the simple, elegant solution.
--
Joe Bowbeer
http://mitpress.mit.edu/sicp/front/node3.html
[ Sobre los gustos no hay disputa. ]
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2008-03-03 17:58:23
John Cowan <
cowan@...> wrote:
> William Tanksley, Jr scripsit:
> > I'm generally on Knuth's side on this one.
> Remember that Knuth thought Dijkstra was *mostly* right, and takes care to
> disclaim the notion that he is in favor of random gotos. AFAIK, gotos are
> only used in TeX to compensate for Pascal's lack of a return statement.
Knuth seemed to see more use for it than that. But I grant your point,
and I wouldn't want to be _against_ Dijkstra on any point, anyhow.
> > But I don't see how tail recursion is a general goto statement. It
> > seems structured -- in particular, a tail recursion has only one entry
> > point.
> If you take an arbitrary tagbody (a list of statements and labels with
> gotos embedded in the statements), you can restructure it into a sequence
> of functions, one per label, where each function ends by tail calling the
> next function in sequence (corresponding to flowing through the label)
> and each goto is changed into a tail call. This can be done entirely as
> a local transformation.
That feels questionable to me. GOTOs can be conditional, and tags can
be inside conditions as well. In short and to be formal, it seems to
me that tagbodies don't form properly nested trees, as functions
must... I think they form digraphs.
I hesitate to pronounce strongly on this, because I haven't studied
it, and you clearly have. But perhaps if I make my mistake out loud
you can correct me. :-)
> "Lambda: the ultimate GOTO."
An interesting point. A recursive tail call in an applicative language
can do one thing that a simple GOTO cannot: it can, at one stroke,
change the value of all the parameters of the function to something
else. This would certainly be sufficient to make an applicative
theorist blanch...
> Well, I have news for our current leaders John Cowan
-Wm
John Cowan — 2008-03-03 18:12:18
Joe Bowbeer scripsit:
> As far as I know, Dijkstra didn't have a beef with recursion.
It seems to me from _A Discipline of Programming_ that he thought
recursion a special case, relatively unimportant: the programming language
he introduces there does not admit it. And he is very much on record as
condemning the reduction of iteration to (tail) recursion as a false
reduction, _ignotum per ignotius_.
> Recursion is the simple, elegant solution.
Recursion can be employed elegantly, when it mirrors induction, or
inelegantly, when it is an invitation to make a mess of your program.
Not all syntactic sugar is oncogenetic: there are good reasons to use
both let and lambda instead of just lambda.
--
As you read this, I don't want you to feel John Cowan
sorry for me, because, I believe everyone
cowan@...
will die someday.
http://www.ccil.org/~cowan
--From a Nigerian-type scam spam
John Cowan — 2008-03-03 18:36:52
William Tanksley, Jr scripsit:
> That feels questionable to me. GOTOs can be conditional,
True, but that doesn't matter: you translate the conditional GO into a
conditional invocation of the function corresponding to the labeled code.
> and tags can be inside conditions as well.
In a Lisp tagbody, tags are only recognized at the top level, so a label
within a conditional becomes a label at the top level of a nested tagbody
within the conditional. GOs are allowed to go to a tag in any tagbody
they are lexically nested in. In order to implement this using functions,
you have to lambda-lift the functions generated from any nested tagbody,
but that again is well-understood, local, and easily performed.
This actually allows rather more of a mess than even "normal" structured
programming languages with GO TO allow. Most languages don't permit you
to GO TO into a construct from outside, though older versions allowed jumps
out-then-back-in (Fortran 66) and/or in-and-then-back-out (simple Basics
and others). However, if you lambda-lift everything, you can actually
jump around however you please.
> In short and to be formal, it seems to me that tagbodies don't form
> properly nested trees, as functions must... I think they form digraphs.
A plausible way to think about tail recursion is to assume an infinite
return stack, and then postpone all the returns until the end of the
program (when they do not actually have to be performed). So although the
call graph is a tree, the actually extant part of it is a random directed
graph, and all the retracing is simply banished from consideration.
This is essentially how Chicken implements Scheme, except that because
the control stack (the C stack) is not infinite, it is necessary to reset
it periodically, banishing any embedded data structures that are still
live to the C heap. In effect, the C stack becomes the first generation
of the Scheme heap.
> An interesting point. A recursive tail call in an applicative language
> can do one thing that a simple GOTO cannot: it can, at one stroke,
> change the value of all the parameters of the function to something
> else. This would certainly be sufficient to make an applicative
> theorist blanch...
Absolutely. LAMBDA = GOTO + argument passing; that's what makes it
"ultimate".
--
Cash registers don't really add and subtract; John Cowan
they only grind their gears.
cowan@...
But then they don't really grind their gears, either;
they only obey the laws of physics. --Unknown
Joe Bowbeer — 2008-03-03 18:40:52
On Mon, Mar 3, 2008 at 10:12 AM, John Cowan wrote:
> Joe Bowbeer scripsit:
>
> > As far as I know, Dijkstra didn't have a beef with recursion.
>
> It seems to me from _A Discipline of Programming_ that he thought
> recursion a special case, relatively unimportant: the programming language
> he introduces there does not admit it. And he is very much on record as
> condemning the reduction of iteration to (tail) recursion as a false
> reduction, _ignotum per ignotius_.
>
But he mentions recursion favorably in the letter you were using to indict
it. I'm confused.
> > Recursion is the simple, elegant solution.
>
> Recursion can be employed elegantly, when it mirrors induction, or
> inelegantly, when it is an invitation to make a mess of your program.
> Not all syntactic sugar is oncogenetic: there are good reasons to use
> both let and lambda instead of just lambda.
>
By "mess" you mean obfuscated and unintelligible? I agree. Recursion is an
elegant concept that can lead to terse, confusing code. But so, in my
opinion, can concatenative programming, so I have trouble understanding your
complaint. If you are saying that adding recursion to concatenative
programming is beyond the pale, I think I could agree with that.
--Joe
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2008-03-03 19:48:27
John Cowan <
cowan@...> wrote:
> William Tanksley, Jr scripsit:
> > and tags can be inside conditions as well.
> In a Lisp tagbody, tags are only recognized at the top level, so a label
> within a conditional becomes a label at the top level of a nested tagbody
> within the conditional. GOs are allowed to go to a tag in any tagbody
> they are lexically nested in. In order to implement this using functions,
> you have to lambda-lift the functions generated from any nested tagbody,
> but that again is well-understood, local, and easily performed.
I don't know the term "lambda-lift", and Google knows of it mainly as
a bunch of source files (I did find a 1985 paper on the topic, but
it's a little dense to answer my questions easily). My question: does
that include code copying -- in other words, is it possible for a
single stretch of code-text in the original GOTO program to be present
in two places in the lambda-lifted code text?
> This actually allows rather more of a mess than even "normal" structured
> programming languages with GO TO allow. Most languages don't permit you
> to GO TO into a construct from outside, though older versions allowed jumps
> out-then-back-in (Fortran 66) and/or in-and-then-back-out (simple Basics
> and others). However, if you lambda-lift everything, you can actually
> jump around however you please.
Well, if you're really using GOTOs optimally (or pessimally) you don't
have ANY structures, so the language can't stop you.
http://catb.org/jargon/html/story-of-mel.html
> > In short and to be formal, it seems to me that tagbodies don't form
> > properly nested trees, as functions must... I think they form digraphs.
> A plausible way to think about tail recursion is to assume an infinite
> return stack, and then postpone all the returns until the end of the
> program (when they do not actually have to be performed). So although the
> call graph is a tree, the actually extant part of it is a random directed
> graph, and all the retracing is simply banished from consideration.
Interesting. I have a very hard time picturing this.
I suppose that's why GOTOs are considered harmful.
> > An interesting point. A recursive tail call in an applicative language
> > can do one thing that a simple GOTO cannot: it can, at one stroke,
> > change the value of all the parameters of the function to something
> > else. This would certainly be sufficient to make an applicative
> > theorist blanch...
> Absolutely. LAMBDA = GOTO + argument passing; that's what makes it
> "ultimate".
Now, interestingly, a concatenative tail-call cannot do this. Does
this imply some superiority for concatenative optimizers? :-)
-Wm
John Nowak — 2008-03-03 20:15:26
On Mar 3, 2008, at 2:48 PM, William Tanksley, Jr wrote:
>> An interesting point. A recursive tail call in an applicative
>> language
>> can do one thing that a simple GOTO cannot: it can, at one stroke,
>> change the value of all the parameters of the function to something
>> else. This would certainly be sufficient to make an applicative
>> theorist blanch...
>>
>> Absolutely. LAMBDA = GOTO + argument passing; that's what makes it
>> "ultimate".
>
> Now, interestingly, a concatenative tail-call cannot do this. Does
> this imply some superiority for concatenative optimizers? :-)
With a concatenative tail-call you're passing the stack as an
argument. In other words, you pass the entire state of the program!
- John
John Cowan — 2008-03-03 20:21:39
William Tanksley, Jr scripsit:
> Now, interestingly, a concatenative tail-call cannot do this. Does
> this imply some superiority for concatenative optimizers? :-)
No. All you do is do an arbitrary stack shuffle before the tail call.
--
John Cowan
http://www.ccil.org/~cowan cowan@...
Please leave your values Check your assumptions. In fact,
at the front desk. check your assumptions at the door.
--sign in Paris hotel --Cordelia Vorkosigan
William Tanksley, Jr — 2008-03-03 20:50:38
John Cowan <
cowan@...> wrote:
> William Tanksley, Jr scripsit:
> > Now, interestingly, a concatenative tail-call cannot do this. Does
> > this imply some superiority for concatenative optimizers? :-)
I'll reply to both of your messages in one.
> No. All you do is do an arbitrary stack shuffle before the tail call.
Then the analysis difficulty (if there is any) is obviously in the
shuffle, not in the tail-call. The analytical problem with an
applicative tail-call is that the 'shuffle' happens at the same time
as the call.
> With a concatenative tail-call you're passing the stack as an
> argument. In other words, you pass the entire state of the program!
Yes, this is how concatenative languages are modeled. That's how
*every* step in their execution is modeled, not just tail-calls or
calls. If this were a problem, concatenative languages would be
universally problematic, not merely problematic in the presence of
tail-calls.
> John Cowan http://www.ccil.org/~cowan cowan@...
-Wm
John Cowan — 2008-03-03 23:15:28
Joe Bowbeer scripsit:
> But he mentions recursion favorably in the letter you were using to indict
> it. I'm confused.
He says that humans are good at (mathematical) induction, which is one
way of understanding recursion. You can't expect him to express his
whole philosophy of programming in a squib; look into _A Discipline of
Programming_ for the details.
> But so, in my opinion, can concatenative programming, so I have trouble
> understanding your complaint. If you are saying that adding recursion
> to concatenative programming is beyond the pale, I think I could agree
> with that.
I was speaking without particular reference to concatenative programming
(off-topic, I know).
--
John Cowan <
cowan@...>
http://ccil.org/~cowan
Micropayment advocates mistakenly believe that efficient allocation of
resources is the purpose of markets. Efficiency is a byproduct of market
systems, not their goal. The reasons markets work are not because users
have embraced efficiency but because markets are the best place to allow
users to maximize their preferences, and very often their preferences are
not for conservation of cheap resources. --Clay Shirkey
John Nowak — 2008-03-04 00:16:34
On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:
>> With a concatenative tail-call you're passing the stack as an
>> argument. In other words, you pass the entire state of the program!
>
> Yes, this is how concatenative languages are modeled. That's how
> *every* step in their execution is modeled, not just tail-calls or
> calls. If this were a problem, concatenative languages would be
> universally problematic, not merely problematic in the presence of
> tail-calls.
Indeed, and I'd argue that this is exactly why many people find stack-
based languages universally problematic. They're taking issue with all
of this state passing, although they phrase it like "I can't keep the
stack in my head". Of course this isn't a problem in practice,
particularly when you have type inference involved and can get a quick
summary of what a function cares about, but it does seem to be the
source of many negative first impressions.
- John
Don Groves — 2008-03-04 01:38:52
On Mar 3, 2008, at 19:50 , William Tanksley, Jr wrote:
> John Cowan <cowan@...> wrote:
>> William Tanksley, Jr scripsit:
>>> Now, interestingly, a concatenative tail-call cannot do this. Does
>>> this imply some superiority for concatenative optimizers? :-)
>
> I'll reply to both of your messages in one.
>
>> No. All you do is do an arbitrary stack shuffle before the tail
>> call.
>
> Then the analysis difficulty (if there is any) is obviously in the
> shuffle, not in the tail-call. The analytical problem with an
> applicative tail-call is that the 'shuffle' happens at the same time
> as the call.
>
>> With a concatenative tail-call you're passing the stack as an
>> argument. In other words, you pass the entire state of the program!
>
> Yes, this is how concatenative languages are modeled. That's how
> *every* step in their execution is modeled, not just tail-calls or
> calls. If this were a problem, concatenative languages would be
> universally problematic, not merely problematic in the presence of
> tail-calls.
A few months back, I finally caught on to this: by their nature,
concatenative languages enforce computation by continuation
passing. Would it be true to say there is no other way?
--
don
>
>> John Cowan http://www.ccil.org/~cowan cowan@...
>
> -Wm
>
>
>
> Yahoo! Groups Links
>
>
>
>
Don Groves — 2008-03-04 01:42:46
On Mar 3, 2008, at 19:16 , John Nowak wrote:
>
> On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:
>
>>> With a concatenative tail-call you're passing the stack as an
>>> argument. In other words, you pass the entire state of the program!
>>
>> Yes, this is how concatenative languages are modeled. That's how
>> *every* step in their execution is modeled, not just tail-calls or
>> calls. If this were a problem, concatenative languages would be
>> universally problematic, not merely problematic in the presence of
>> tail-calls.
>
> Indeed, and I'd argue that this is exactly why many people find stack-
> based languages universally problematic. They're taking issue with all
> of this state passing, although they phrase it like "I can't keep the
> stack in my head". Of course this isn't a problem in practice,
> particularly when you have type inference involved and can get a quick
> summary of what a function cares about, but it does seem to be the
> source of many negative first impressions.
Also, there has never been a requirement to "keep it all in one's head,"
that's what comments are for. Commenting with stack diagrams is very
useful!
I know "real programmers" don't comment but in these languages, they
should.
--
don
> - John
>
>
>
> Yahoo! Groups Links
>
>
>
>
zallambo — 2008-03-04 05:42:48
--- In
concatenative@yahoogroups.com, Don Groves <dgroves@...> wrote:
>
>
> On Mar 3, 2008, at 19:16 , John Nowak wrote:
>
> >
> > On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:
> >
> >>> With a concatenative tail-call you're passing the stack as an
> >>> argument. In other words, you pass the entire state of the program!
> >>
> >> Yes, this is how concatenative languages are modeled. That's how
> >> *every* step in their execution is modeled, not just tail-calls or
> >> calls. If this were a problem, concatenative languages would be
> >> universally problematic, not merely problematic in the presence of
> >> tail-calls.
> >
> > Indeed, and I'd argue that this is exactly why many people find stack-
> > based languages universally problematic. They're taking issue with all
> > of this state passing, although they phrase it like "I can't keep the
> > stack in my head". Of course this isn't a problem in practice,
> > particularly when you have type inference involved and can get a quick
> > summary of what a function cares about, but it does seem to be the
> > source of many negative first impressions.
>
> Also, there has never been a requirement to "keep it all in one's head,"
> that's what comments are for. Commenting with stack diagrams is very
> useful!
>
> I know "real programmers" don't comment but in these languages, they
> should.
> --
> don
If code isn't readable without stack diagrams, comments seem like a
poor fix. Rather, there should be a way to make the code itself more
transparent. I think lambda expressions are a good replacement for
stack diagrams. They make the stack explicit and are often easier to
read. Compare:
#x y u v -- (x*u - y*v) (x*v + y*u)
dup4 [swap] dip * bury * swap - bury * bury * +
[x y u v] [x u * y v * - x v * y u * +] lambda
A mistake would be much easier to notice in the latter than the
former. Not being able to keep track of the stack in one's head can be
a serious problem.
Fortunately lambda expressions can be implemented as macros and
rewritten out of existence. So the language itself doesn't actually
need to be extended.
-Justin
Christopher Diggins — 2008-03-04 06:06:57
On Tue, Mar 4, 2008 at 12:42 AM, zallambo <
zallambo@...> wrote:
> --- In concatenative@yahoogroups.com, Don Groves <dgroves@...> wrote:
> >
> >
> > On Mar 3, 2008, at 19:16 , John Nowak wrote:
> >
> > >
> > > On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:
> > >
> > >>> With a concatenative tail-call you're passing the stack as an
> > >>> argument. In other words, you pass the entire state of the program!
> > >>
> > >> Yes, this is how concatenative languages are modeled. That's how
> > >> *every* step in their execution is modeled, not just tail-calls or
> > >> calls. If this were a problem, concatenative languages would be
> > >> universally problematic, not merely problematic in the presence of
> > >> tail-calls.
> > >
> > > Indeed, and I'd argue that this is exactly why many people find stack-
> > > based languages universally problematic. They're taking issue with all
> > > of this state passing, although they phrase it like "I can't keep the
> > > stack in my head". Of course this isn't a problem in practice,
> > > particularly when you have type inference involved and can get a quick
> > > summary of what a function cares about, but it does seem to be the
> > > source of many negative first impressions.
> >
> > Also, there has never been a requirement to "keep it all in one's head,"
> > that's what comments are for. Commenting with stack diagrams is very
> > useful!
> >
> > I know "real programmers" don't comment but in these languages, they
> > should.
> > --
> > don
>
> If code isn't readable without stack diagrams, comments seem like a
> poor fix. Rather, there should be a way to make the code itself more
> transparent. I think lambda expressions are a good replacement for
> stack diagrams. They make the stack explicit and are often easier to
> read. Compare:
>
> #x y u v -- (x*u - y*v) (x*v + y*u)
> dup4 [swap] dip * bury * swap - bury * bury * +
>
> [x y u v] [x u * y v * - x v * y u * +] lambda
<shamelessplug>
Cat supports this notation as: \x.\y.\u.\v.[x u * y v * - x v * y u * +]
</shamelessplug>
Don Groves — 2008-03-05 04:16:39
On Mar 3, 2008, at 19:06 , Christopher Diggins wrote:
> On Tue, Mar 4, 2008 at 12:42 AM, zallambo <zallambo@...> wrote:
>> --- In concatenative@yahoogroups.com, Don Groves <dgroves@...> wrote:
>>>
>>>
>>> On Mar 3, 2008, at 19:16 , John Nowak wrote:
>>>
>>>>
>>>> On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:
>>>>
>>>>>> With a concatenative tail-call you're passing the stack as an
>>>>>> argument. In other words, you pass the entire state of the
>>>>>> program!
>>>>>
>>>>> Yes, this is how concatenative languages are modeled. That's how
>>>>> *every* step in their execution is modeled, not just tail-calls or
>>>>> calls. If this were a problem, concatenative languages would be
>>>>> universally problematic, not merely problematic in the presence of
>>>>> tail-calls.
>>>>
>>>> Indeed, and I'd argue that this is exactly why many people find
>>>> stack-
>>>> based languages universally problematic. They're taking issue
>>>> with all
>>>> of this state passing, although they phrase it like "I can't
>>>> keep the
>>>> stack in my head". Of course this isn't a problem in practice,
>>>> particularly when you have type inference involved and can get a
>>>> quick
>>>> summary of what a function cares about, but it does seem to be the
>>>> source of many negative first impressions.
>>>
>>> Also, there has never been a requirement to "keep it all in one's
>>> head,"
>>> that's what comments are for. Commenting with stack diagrams is very
>>> useful!
>>>
>>> I know "real programmers" don't comment but in these languages, they
>>> should.
>>> --
>>> don
>>
>> If code isn't readable without stack diagrams, comments seem like a
>> poor fix. Rather, there should be a way to make the code itself more
>> transparent. I think lambda expressions are a good replacement for
>> stack diagrams. They make the stack explicit and are often easier to
>> read. Compare:
>>
>> #x y u v -- (x*u - y*v) (x*v + y*u)
>> dup4 [swap] dip * bury * swap - bury * bury * +
>>
>> [x y u v] [x u * y v * - x v * y u * +] lambda
>
> <shamelessplug>
>
> Cat supports this notation as: \x.\y.\u.\v.[x u * y v * - x v * y u
> * +]
>
> </shamelessplug>
Naming stack locations is a nice way to reduce the cognitive load
and it looks like it works particularly well for mathematical
algorithms.
How well does it work for non-mathematical things?
--
don
> Yahoo! Groups Links
>
>
>
>
John Cowan — 2008-03-05 04:25:13
William Tanksley scripsit:
> I don't know the term "lambda-lift", and Google knows of it mainly as
> a bunch of source files (I did find a 1985 paper on the topic, but
> it's a little dense to answer my questions easily). My question: does
> that include code copying -- in other words, is it possible for a
> single stretch of code-text in the original GOTO program to be present
> in two places in the lambda-lifted code text?
No, it doesn't. Lambda-lifting is a transformation of an inner (nested)
procedure into a top-level procedure by adding one argument for each
variable that is free in the inner procedure but bound in some enclosing
procedure. All calls are transformed likewise.
For example:
(lambda (x y) ... (lambda (z w) ... x ...) ...)
lambda-lifts to:
(lambda (z-of-x w x) ... x ...)
(lambda (x y) ... (z-of-x w x) ...)
so z is renamed to z-of-x (or in some other way) and goes from one
argument to two.
This will not work, or at least requires extra machinery, when z is
passed out of x to be called from somewhere else. But that is not the
case for lambdas made out of tagbody labels.
--
John Cowan
cowan@... http://ccil.org/~cowan
Sound change operates regularly to produce irregularities;
analogy operates irregularly to produce regularities.
--E.H. Sturtevant, ca. 1945, probably at Yale
Daniel Ehrenberg — 2008-03-05 04:33:12
> Naming stack locations is a nice way to reduce the cognitive load
> and it looks like it works particularly well for mathematical
> algorithms.
> How well does it work for non-mathematical things?
> --
> don
I've used it for a dynamic programming problem, which made things much
easier. But generally, I find that things come out cleaner when you
don't use named variables. The dataflow is more direct. When you write
things by dividing them into small words, the need for named variables
is diminished; the ability to omit variable names also makes it easier
to divide things into smaller chunks.
Dan
John Nowak — 2008-03-05 09:25:58
On Mar 3, 2008, at 8:38 PM, Don Groves wrote:
> A few months back, I finally caught on to this: by their nature,
> concatenative languages enforce computation by continuation
> passing.
Indeed. This in *incredibly* useful as it means your language is
essentially purely functional by default. After all, it's trivial to
thread a world state through the entire program on the top of the
stack. All you need then is a simple effect system to allow enforcing
of purity (purity = does not read/write the world value) via the type
system when desirable/necessary. The monoidal nature of Joy-like
languages also enables linearity without linear/uniquneness types. Cat
takes advantage of this, although perhaps not originally knowingly.
Fifth does as well.
- John
William Tanksley, Jr — 2008-03-06 15:23:25
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> >> With a concatenative tail-call you're passing the stack as an
> >> argument. In other words, you pass the entire state of the program!
> > Yes, this is how concatenative languages are modeled. That's how
> > *every* step in their execution is modeled, not just tail-calls or
> > calls. If this were a problem, concatenative languages would be
> > universally problematic, not merely problematic in the presence of
> > tail-calls.
> Indeed, and I'd argue that this is exactly why many people find stack-
> based languages universally problematic. They're taking issue with all
> of this state passing, although they phrase it like "I can't keep the
> stack in my head". Of course this isn't a problem in practice,
> particularly when you have type inference involved and can get a quick
> summary of what a function cares about, but it does seem to be the
> source of many negative first impressions.
Now we're treading on the marshy ground of subjective judgments... I
don't think we're going to resolve this in this manner. I disagree
that this is why some people find concatenative languages difficult,
but I suspect neither one of us can build a model strong enough to
refute the other's suspicions.
But I wasn't talking about subjective impressions; I'm talking about
mathematical analysis. We don't need to go into opinions.
Mathematically, every operation in a concatenative language is modeled
by passing the entire stack to each successive function, and yet the
mathematical analysis is exceedingly simple.
Therefore, if tail-calls are hard to analyze in a concatenative
language, the problem is NOT that "the entire stack is being passed".
The problem lies elsewhere.
Let me quote you: "No. All you do is do an arbitrary stack shuffle
before the tail call."
Again, the problem is the stack shuffle, not the tail call. Analysing
the shuffle will untangle the entire problem, without having to
involve any analysis of the tail-call. This contrasts with a tail-call
in an applicative language, in which the tail-call is inseparable from
the changing of the values of the parameters.
> - John
-Wm
William Tanksley, Jr — 2008-03-06 16:53:43
zallambo <
zallambo@...> wrote:
> If code isn't readable without stack diagrams, comments seem like a
> poor fix.
Indeed. But this isn't relevant to the discussion. Code is unreadable
for many reasons. We were originally talking about a specific cause of
unreadability which appears to apply exclusively to applicative
languages -- now people have started complaining that concatenative
languages are universally unreadable, which is not backed up by the
arguments being presented.
> Rather, there should be a way to make the code itself more
> transparent. I think lambda expressions are a good replacement for
> stack diagrams. They make the stack explicit and are often easier to
> read. Compare:
Lambda expressions are an excellent tool, but they do not replace or
augment stack diagrams; the purposes are simply different.
> #x y u v -- (x*u - y*v) (x*v + y*u)
> dup4 [swap] dip * bury * swap - bury * bury * +
> [x y u v] [x u * y v * - x v * y u * +] lambda
> A mistake would be much easier to notice in the latter than the
> former.
A mistake in either one is a programming error, which can be
arbitrarily hard to find. In this particular case, lambda is
objectively better than raw stack notation, and a mathematical
domain-specific-language would be even better (one should use the
simplest thing that will work, of course); but in general, errors in
lambdas are as hard to find as errors in stack notation; they can be
worse in some situations because in a stack language, lambda
expressions mix up and permit confusion between the two ways of
getting parameters to the functions.
Again, lambdas are useful, but in my experience they're mainly used
where a math-like expression is desired -- in other words, it would be
even more useful for the language to provide a math DSL.
> Not being able to keep track of the stack in one's head can be
> a serious problem.
Indeed. Guess what my answer is to that problem?
1. Learn better to keep track of the stack in your head;
2. Write code that's easier to track.
Both will only come with practice.
> -Justin
-Wm
John Nowak — 2008-03-06 20:11:44
On Mar 6, 2008, at 10:23 AM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>
>> Indeed, and I'd argue that this is exactly why many people find
>> stack-
>> based languages universally problematic. They're taking issue with
>> all
>> of this state passing, although they phrase it like "I can't keep the
>> stack in my head". Of course this isn't a problem in practice,
>> particularly when you have type inference involved and can get a
>> quick
>> summary of what a function cares about, but it does seem to be the
>> source of many negative first impressions.
>
> Now we're treading on the marshy ground of subjective judgments... I
> don't think we're going to resolve this in this manner.
Resolve what? Are you talking to the right John?
> But I wasn't talking about subjective impressions; I'm talking about
> mathematical analysis. We don't need to go into opinions.
> Mathematically, every operation in a concatenative language is modeled
> by passing the entire stack to each successive function, and yet the
> mathematical analysis is exceedingly simple.
I agree.
> Therefore, if tail-calls are hard to analyze in a concatenative
> language, the problem is NOT that "the entire stack is being passed".
> The problem lies elsewhere.
Of course.
> Let me quote you: "No. All you do is do an arbitrary stack shuffle
> before the tail call."
Ah, now I'm sure you have the wrong John. I'm Mr. Nowak, he's Mr. Cowan.
- John
John Cowan — 2008-03-06 20:17:26
John Nowak scripsit:
> Ah, now I'm sure you have the wrong John. I'm Mr. Nowak, he's Mr. Cowan.
I think our William has a collision in his internal hash tables.
He's responding to your message and taking you to task for contradicting
something I said. Or something like that.
--
You know, you haven't stopped talking John Cowan
since I came here. You must have been
http://www.ccil.org/~cowan
vaccinated with a phonograph needle.
cowan@...
--Rufus T. Firefly
William Tanksley, Jr — 2008-03-06 22:20:41
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > John Nowak <john@...> wrote:
> >> Indeed, and I'd argue that this is exactly why many people find
> >> stack-
> >> based languages universally problematic. They're taking issue with
> >> all
> >> of this state passing, although they phrase it like "I can't keep the
> >> stack in my head". Of course this isn't a problem in practice,
> >> particularly when you have type inference involved and can get a
> >> quick
> >> summary of what a function cares about, but it does seem to be the
> >> source of many negative first impressions.
> > Now we're treading on the marshy ground of subjective judgments... I
> > don't think we're going to resolve this in this manner.
> Resolve what? Are you talking to the right John?
I'm responding to your message, so I guess so -- I meant that I
disagree that this is the cause of people's discomfort, and also that
I disagreed that it was related to any trouble with tail-calls or
recursion.
However, after a good 5 minutes of digging, I found the source of our
confusion. I DID mix up my mind when referring to you two back when
you (Nowak) said that the entire state is passed through the
tail-call, and he (Cowan) said "No. All you do is do an arbitrary
stack shuffle before the tail call."
I agree with the facts of what you said, Nowak (although I don't agree
that this makes concatenative languages "the ultimate GOTO", which
seems to be the implication of what you wrote), and I disagree with
you, Cowan, that performing an arbitrary stack shuffle complicates the
analysis of the tail-call.
> > Let me quote you: "No. All you do is do an arbitrary stack shuffle
> > before the tail call."
> Ah, now I'm sure you have the wrong John. I'm Mr. Nowak, he's Mr. Cowan.
Ah! Man, that WAS confusing. Sorry about that -- my fault.
> - John
-Wm
John Cowan — 2008-03-07 06:55:56
William Tanksley, Jr scripsit:
> I agree with the facts of what you said, Nowak (although I don't agree
> that this makes concatenative languages "the ultimate GOTO", which
> seems to be the implication of what you wrote), and I disagree with
> you, Cowan, that performing an arbitrary stack shuffle complicates the
> analysis of the tail-call.
Good, because that's the reverse of what I said, which is that to tail-call
an arbitrary function, all you need to do is to execute an arbitrary shuffle
to get the function arguments in the right order -- which is very simple.
--
Do I contradict myself? John Cowan
Very well then, I contradict myself.
cowan@...
I am large, I contain multitudes.
http://www.ccil.org/~cowan
--Walt Whitman, Leaves of Grass
William Tanksley, Jr — 2008-03-07 15:00:51
John Cowan <
cowan@...> wrote:
> William Tanksley, Jr scripsit:
> > I agree with the facts of what you said, Nowak (although I don't agree
> > that this makes concatenative languages "the ultimate GOTO", which
> > seems to be the implication of what you wrote), and I disagree with
> > you, Cowan, that performing an arbitrary stack shuffle complicates the
> > analysis of the tail-call.
> Good, because that's the reverse of what I said, which is that to tail-call
> an arbitrary function, all you need to do is to execute an arbitrary shuffle
> to get the function arguments in the right order -- which is very simple.
Seriously, I'm confused. Why did you start your paragraph with "no,"
if you weren't intending to disagree with me? This probably all comes
down to miscommunication again...
> Do I contradict myself? John Cowan
Probably not.
-Wm
John Cowan — 2008-03-07 16:03:52
William Tanksley, Jr scripsit:
> Seriously, I'm confused. Why did you start your paragraph with "no,"
> if you weren't intending to disagree with me? This probably all comes
> down to miscommunication again...
I can no longer fully sort this out, but your remark ended with a smiley,
so I assumed it was ironic, and was answering (seriously) that the ironic
statement was wrong, meaning that what I took to be your underlying actual
opinion was correct.
In any case, a tail-call in a concatenative language is a possible stack
reshuffle to get the arguments in the correct order for the new function
and then a GO TO to that function, which is essentially how it's implemented
in tail-recursive applicative languages like Scheme: you shuffle the arguments
about in registers, possibly spilling to the stack or restoring from the stack
as needed, and then do a machine-language GO TO.
Assembler: the ultimate concatenative language....
--
After fixing the Y2K bug in an application: John Cowan
WELCOME TO <censored>
cowan@...
DATE: MONDAK, JANUARK 1, 1900
http://www.ccil.org/~cowan
William Tanksley, Jr — 2008-03-07 16:42:13
John Cowan <
cowan@...> wrote:
> William Tanksley, Jr scripsit:
> > Seriously, I'm confused. Why did you start your paragraph with "no,"
> > if you weren't intending to disagree with me? This probably all comes
> > down to miscommunication again...
> I can no longer fully sort this out, but your remark ended with a smiley,
> so I assumed it was ironic, and was answering (seriously) that the ironic
> statement was wrong, meaning that what I took to be your underlying actual
> opinion was correct.
I consider this fully sorted out. Excellent. The problem is that I
failed to explain precisely why I said what I did, leaving you having
to wonder whether I was being deep and ironic or just shallow and
obvious. Your reading makes perfect sense.
> In any case, a tail-call in a concatenative language is a possible stack
> reshuffle to get the arguments in the correct order for the new function
> and then a GO TO to that function, which is essentially how it's implemented
> in tail-recursive applicative languages like Scheme: you shuffle the arguments
> about in registers, possibly spilling to the stack or restoring from the stack
> as needed, and then do a machine-language GO TO.
> Assembler: the ultimate concatenative language....
This isn't a useful way to compare languages -- yes, they can all
generate machine code, and given a hypothetical optimizer it'll be the
same for the same semantics. Well, it'll be useful if you can specify
what that optimizer looks like.
A tail call in a concatenative language is a structured GOTO to the
beginning of the function, nothing more. A tail call in an applicative
function is a parameter reassignment combined with a structured GOTO
to the beginning of the function.
> After fixing the Y2K bug in an application: John Cowan
-Wm
John Cowan — 2008-03-07 19:19:16
William Tanksley, Jr scripsit:
> A tail call in a concatenative language is a structured GOTO to the
> beginning of the function, nothing more. A tail call in an applicative
> function is a parameter reassignment combined with a structured GOTO
> to the beginning of the function.
Correct, given that a shuffle may be needed before the concatenative
function can be successfully called (tail or otherwise), and a compiler
can arrange that the parameter reassignment requires no actual machine
instructions.
--
At the end of the Metatarsal Age, the dinosaurs John Cowan
abruptly vanished. The theory that a single
cowan@...
catastrophic event may have been responsible
http://www.ccil.org/~cowan
has been strengthened by the recent discovery of
a worldwide layer of whipped cream marking the
Creosote-Tutelary boundary. --Science Made Stupid
Manfred Von Thun — 2008-03-11 05:11:45
On 29/2/08 7:39 AM, "John Nowak" <
john@...> wrote:
>
> Recently, I mentioned that if you disallow recursive definitions, then
> definitions can be thought of as macros or rewrite rules.
>
This encourages me to ask a question about Forth which I have been
too shy to ask. I¹ve read a number of times that recursion was not
allowed or not easy to do at least in the earlier versions of
Forth. I explained this to myself like this: the colon definitions are
just macros, and the macro expansion is very simple.
Was I right about the early Forths? Was is the current situation?
I was very impressed by the current discussion in this topic.
- Manfred
>
[Non-text portions of this message have been removed]
Manfred Von Thun — 2008-03-11 05:41:30
On 2/3/08 12:51 AM, "Stevan Apter" <
sa@...> wrote:
>
> i'm still puzzled why authors of concatenative languages like cat and factor
have resisted the incorporation of array primitives into their
languages.
But why do they need to be primitives? Many languages have a small core
and a large library of defined functions. One such library might be for a
collection of basic array functions in terms of which all other array
functions
can be defined. Then the library might be expanded by also giving the
definitions of the most useful ones.
There might be many different possible collections of basic ones, that seems
to be true for most abstract algebras. Probably the ones offered by the
existing array languages are both complete as a base and most useful.
Are there any which cannot be defined in Joy (with lists instead of arrays)?
If so, please let me know.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2008-03-11 05:58:49
On 2/3/08 1:46 AM, "Stevan Apter" <
sa@...> wrote:
>
> 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.
>
I now use ³sequence² when taking about an abstract data type, and similarly
for
³set² as an abstract data type and (ordered) ³pair² as an abstract data
type.
It is well known that the three can be interdefined.
I use ³list² and ³array² as the most commonly used implementations of
sequences: lists as linked structures, arrays in consecutive memory.
Lists are better for some operations on sequences, and arrays are better
for other operations on sequences. But all operations on sequences
implemented either way.
- Manfred
>
>
[Non-text portions of this message have been removed]
Manfred Von Thun — 2008-03-11 06:54:17
On 4/3/08 6:48 AM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
>
[ apropos a discussion about tail recursion]
>
> Now, interestingly, a concatenative tail-call cannot do this. Does
> this imply some superiority for concatenative optimizers? :-)
>
> -Wm
The Joy interpreter (in file interp.c function exeterm() ) does tail
recursion,
and it is easy. This function is the core of the interpreter, it interprets
the contents of quotations. If any defined function calls itself at the end
of its body, then exeterm tail-recurses to the beginning of the body.
This is possible and particularly easy because diefined functions, like
any functions, do not have explicit parameters but take them off the stack.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2008-03-11 07:19:18
On 4/3/08 12:38 PM, "Don Groves" <
dgroves@...> wrote:
>
> A few months back, I finally caught on to this: by their nature,
> concatenative languages enforce computation by continuation
> passing. Would it be true to say there is no other way?
> --
> don
>
But continuation passing surely means something rather complex.
Cancatenative languages interpret concatenations of atomic
programs by starting at the beginning until they reach the
end. For each atom something is changed. That is pretty much
the same for all assembly languages, byte code interpreters etc.
(True at least while not intercepted by a jump or goto).
But as remember, continuation passing means giving
a procedure an additional parameter which represents the
rest of the program, and which will normally be executed
before the procedure returns. Landin¹s papers from the 60¹s
(and at least one much later) are good on this. Look for
³History of continuations² or similar.
- Manfred
[Non-text portions of this message have been removed]
pml060912 — 2008-03-11 09:35:03
--- In
concatenative@yahoogroups.com, Manfred Von Thun <m.vonthun@...>
wrote:
>
>
>
>
> On 29/2/08 7:39 AM, "John Nowak" <john@...> wrote:
>
> >
> > Recently, I mentioned that if you disallow recursive definitions, then
> > definitions can be thought of as macros or rewrite rules.
> >
> This encourages me to ask a question about Forth which I have been
> too shy to ask. I¹ve read a number of times that recursion was not
> allowed or not easy to do at least in the earlier versions of
> Forth. I explained this to myself like this: the colon definitions are
> just macros, and the macro expansion is very simple.
>
> Was I right about the early Forths? Was is the current situation?
Chuck Moore did use macros in some of his early experiments, I
believe, but by the time there were enough features for it to be
recognisably Forth he had already settled on compiling into indirect
threaded code. Other implementation methods followed, and that one is
now rare. Google for "history of Forth", which I think is at Forth
inc.'s site.
The problem with recursion was how the compiler was implemented, but
it was usually quite minor. The compiler couldn't recognise a word
that was still being compiled, as it hadn't yet been marked in the
vocabulary as a successfully compiled word. You had to achieve
recursion with a special keyword where you would have put the
recursive call, sometimes called MYSELF and sometimes RECURSE, but it
wasn't particularly difficult; you could even provide it yourself if
it wasn't already there. Where things got a little more awkward was
with mutual recursion, which required some set up work with vectors
that you used in the main words where you would have had them calling
each other. You had to reassign those to the right places after
compiling the main words, and calling them usually imposed some more
overhead. PML.
Stan Katz — 2008-03-11 13:21:15
Manfred von Thun wrote :
> This encourages me to ask a question about Forth which I have been
> too shy to ask. I¹ve read a number of times that recursion was not
> allowed or not easy to do at least in the earlier versions of
> Forth. I explained this to myself like this: the colon definitions are
> just macros, and the macro expansion is very simple.
>
> Was I right about the early Forths? Was is the current situation?
Recursion has always been available in Forth, but it needed some care because
most implementations "hide" the current definition until it is complete. This was
done so that it was possible to re-define a word and use the old definition within
the new word, e.g. to add additional processing or checking to the operation, and
possibly also to prevent a word that was not completely defined (or had an error
while it was defined) from being used.
Many Forths included the word RECURSE or MYSELF for recusrion and those that
didn't have it as a standard word usually had it as an extension.
There has actually been a discussion recently on the comp.lang.forth usenet
newsgroup about this hiding of the current definition.
Stan Katz
---------------------------------
Looking for last minute shopping deals? Find them fast with Yahoo! Search.
[Non-text portions of this message have been removed]
John Cowan — 2008-03-11 15:24:41
Manfred Von Thun scripsit:
> If any defined function calls itself at the end
> of its body, then exeterm tail-recurses to the beginning of the body.
Ideally this should happen if the last word is *any* non-primitive function,
which is why the optimization is rightly called "tail-call" (Scheme) or
"last call" (Prolog).
--
John Cowan
http://www.ccil.org/~cowan <
cowan@...>
"Any legal document draws most of its meaning from context. A telegram
that says 'SELL HUNDRED THOUSAND SHARES IBM SHORT' (only 190 bits in
5-bit Baudot code plus appropriate headers) is as good a legal document
as any, even sans digital signature." --me
William Tanksley, Jr — 2008-03-11 16:19:48
Manfred Von Thun <
m.vonthun@...> wrote:
> But as remember, continuation passing means giving
> a procedure an additional parameter which represents the
> rest of the program, and which will normally be executed
> before the procedure returns. Landin¹s papers from the 60¹s
> (and at least one much later) are good on this. Look for
> ³History of continuations² or similar.
Joy doesn't have any functionality which is like this. Forth does,
with its direct access to its return stack.
> - Manfred
-Wm
John Cowan — 2008-03-11 19:44:29
William Tanksley, Jr scripsit:
> Joy doesn't have any functionality which is like this. Forth does,
> with its direct access to its return stack.
In fact Joy does have a word "cont" which provides access to the implicit
return stack. It's been busted for a long time, though.
--
Si hoc legere scis, nimium eruditionis habes.
Don Groves — 2008-03-11 22:43:13
On Mar 11, 2008, at 19:19 , Manfred Von Thun wrote:
> On 4/3/08 12:38 PM, "Don Groves" <dgroves@...> wrote:
>>
>> A few months back, I finally caught on to this: by their nature,
>> concatenative languages enforce computation by continuation
>> passing. Would it be true to say there is no other way?
>> --
>> don
>>
> But continuation passing surely means something rather complex.
> Cancatenative languages interpret concatenations of atomic
> programs by starting at the beginning until they reach the
> end. For each atom something is changed. That is pretty much
> the same for all assembly languages, byte code interpreters etc.
> (True at least while not intercepted by a jump or goto).
>
> But as remember, continuation passing means giving
> a procedure an additional parameter which represents the
> rest of the program, and which will normally be executed
> before the procedure returns. Landin’s papers from the 60’s
> (and at least one much later) are good on this. Look for
> “History of continuations” or similar.
>
> - Manfred
Hello, Manfred --
Your description above is the usual implementation of
continuation passing but concatenative languages seem
to me to embody that implementation implicitly. A simple
Joy example:
3 [dup *] i ==> 3 3 [*] i ==> 9
I interpret this as 3 3 [*] is the continuation of the dup
operation being passed to i which is executed before i
returns.
--
don
> [Non-text portions of this message have been removed]
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
Manfred Von Thun — 2008-03-19 07:51:47
On 12/3/08 3:19 AM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
> Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>
> > wrote:
>
>> > But as remember, continuation passing means giving
>> > a procedure an additional parameter which represents the
>> > rest of the program, and which will normally be executed
>> > before the procedure returns. Landin¹s papers from the 60¹s
>> > (and at least one much later) are good on this. Look for
>> > ³History of continuations² or similar.
>
> Joy doesn't have any functionality which is like this. Forth does,
> with its direct access to its return stack.
>
Not so. In Joy all parameters are taken from the stack. Combinators
expect quotations, and quotations are also good as continuation
parameters. I have used it a number of times to implement
backtracking (in the only way I know: with continuations.) There
is one file in the Joy library
http://www.latrobe.edu.au/philosophy/phimvt/joy/plglib.joy
>
which does what are variously called truth trees, semantic tableaux
or Wang¹s algorithm. Most of the programs in that file are annotated
as expecting
t f c F
on the stack, with F on top. F is a formula in propositional logic which
the tree method tries to make true (or false) by assigning truth to some
atoms (in t) and falsity to others (in f). The c parameter is the
continuation,
and it does all the hard work of the backtracking.
So, because Joy has quotations, no extra mechanism is needed to
implement continuations.
>
John Cowan was right about the abandoned cont operator. It turned
out that quotations can do the job. However it may also be that a
different cont operator might make backtracking programs easier
to read.
>
Incidentally, the mainstream languages which allow procedures as
continuations will also allow several continuations. That is true in
Joy too. I seem to remember that the implementation of Snobol
(and maybe of Icon) used two continuations: one for success,
the other for failure.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2008-03-19 09:30:31
On 8/3/08 3:03 AM, "John Cowan" <
cowan@...> wrote:
>
> ....
> Assembler: the ultimate concatenative language....
Indeed, except for those jumps, as of course you know. But the
mention of assembler triggers an old memory about something
I have wanted to write about for some time. It concerns not
so much the high or low level of a concatenative language,
but what its shortest programs are whose concatenation
computes the composition of what those shortest programs
are. In just about all concatenative languages the shortest
programs are atoms like swap, +, map, 123, ³hello², [a b],
the first three operators and the lest three push-ops. It is
from atoms such as these that programs are constructed by
concatenation. But could there not be small programs, not
formed by concatenating with others to form their composition,
which nevertheless have parts: MOLECULES
An assembly program consists of a sequence of lines, each
holding one instruction, to be executed in sequence unless
intercepted by a jump instruction. Each instruction produces
a change somewhere, and the concatenation of the lines
produces the composition of the changes. But instructions
have part, too. They consist of an operator such as mul, fetch,
store, ..., each followed by several inscrutables having to
do with where things come from and where they should go.
So an instruction is a sort of molecule composed of several
atoms. Now think of concatenative languages in which programs
are concatenated from molecules, each consisting of an
operator (like swap, + etc) together with additional parts
that complete what is meant. Note that the additional parts
are not further parameters that should be taken from the stack.
What useful additional parts may there be?
I would take a hint from unix, which has a rich collection of
what are called filters, programs that take one input fil and
produce one output file. The names of such programs, foo, bar,
baz and zot, can be concatenated to form what is called a pipe:
(here i dare not think what my mailer will do with the vertical bar)
foo | bar | baz | zot
and this concatenation will take one input file and produce one
output file such that ... You guessed it. But each of these programs
may have a useful default behaviour and also allow switches to
modify the default. The switches are typically single letters
precededd by a minus sign. So the pipe might actually look like
this:
foo a g | bar x | baz -e q w e r | zot m d
So in the terminology I am tempted to adopt, here we have
the concatenation of four molecules or instructions,
where the first instruction consists of three atoms, namely
a program and two switches.
Apart from the pipe of output-input files, it may be necessary
to use other files, and there are lots of ways of doing that.
The upshot: have we in the concatenative world missed out
on something useful by not allowing parts to the smallest
programs. There is a lot one could and should discuss here,
but not me, not tonight.
- Manfred
[Non-text portions of this message have been removed]
Don Groves — 2008-03-19 19:42:29
On Mar 19, 2008, at 19:30 , Manfred Von Thun wrote:
>
> On 8/3/08 3:03 AM, "John Cowan" <cowan@...> wrote:
>>
>> ....
>> Assembler: the ultimate concatenative language....
>
> Indeed, except for those jumps, as of course you know. But the
> mention of assembler triggers an old memory about something
> I have wanted to write about for some time. It concerns not
> so much the high or low level of a concatenative language,
> but what its shortest programs are whose concatenation
> computes the composition of what those shortest programs
> are. In just about all concatenative languages the shortest
> programs are atoms like swap, +, map, 123, “hello”, [a b],
> the first three operators and the lest three push-ops. It is
> from atoms such as these that programs are constructed by
> concatenation. But could there not be small programs, not
> formed by concatenating with others to form their composition,
> which nevertheless have parts: MOLECULES
>
> An assembly program consists of a sequence of lines, each
> holding one instruction, to be executed in sequence unless
> intercepted by a jump instruction. Each instruction produces
> a change somewhere, and the concatenation of the lines
> produces the composition of the changes. But instructions
> have part, too. They consist of an operator such as mul, fetch,
> store, ..., each followed by several inscrutables having to
> do with where things come from and where they should go.
> So an instruction is a sort of molecule composed of several
> atoms. Now think of concatenative languages in which programs
> are concatenated from molecules, each consisting of an
> operator (like swap, + etc) together with additional parts
> that complete what is meant. Note that the additional parts
> are not further parameters that should be taken from the stack.
> What useful additional parts may there be?
>
> I would take a hint from unix,
It occurred to me a while back that the stack is to concatenative
languages as a pipe is to Unix programs and shell scripts.
> which has a rich collection of
> what are called filters, programs that take one input fil and
> produce one output file. The names of such programs, foo, bar,
> baz and zot, can be concatenated to form what is called a pipe:
> (here i dare not think what my mailer will do with the vertical bar)
>
> foo | bar | baz | zot
>
> and this concatenation will take one input file and produce one
> output file such that ... You guessed it. But each of these programs
> may have a useful default behaviour and also allow switches to
> modify the default. The switches are typically single letters
> precededd by a minus sign. So the pipe might actually look like
> this:
>
> foo –a –g | bar –x | baz -e –q –w –e –r | zot –m –d
>
> So in the terminology I am tempted to adopt, here we have
> the concatenation of four molecules or instructions,
> where the first instruction consists of three atoms, namely
> a program and two switches.
>
> Apart from the pipe of output-input files, it may be necessary
> to use other files, and there are lots of ways of doing that.
>
> The upshot: have we in the concatenative world missed out
> on something useful by not allowing parts to the smallest
> programs. There is a lot one could and should discuss here,
Agreed!
--
don
> but not me, not tonight.
>
> - Manfred
>
>
>
> [Non-text portions of this message have been removed]
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>
William Tanksley, Jr — 2008-03-19 20:47:02
Manfred Von Thun <
m.vonthun@...> wrote:
> The upshot: have we in the concatenative world missed out
> on something useful by not allowing parts to the smallest
> programs. There is a lot one could and should discuss here,
> but not me, not tonight.
We do already do that. All concatenative languages (except 01 :-)
support numbers, which are molecules by your definition. Most support
strings. Joy quotations are molecules whose component parts happen to
be a proper subset of Joy itself.
Of course, we could do more. I'm reminded of REBOL, which has some
interesting syntax that might be applicable (block modification).
> - Manfred
-Wm
Manfred Von Thun — 2008-04-01 04:56:07
On 20/3/08 6:47 AM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
> Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>
> > wrote:
>> > The upshot: have we in the concatenative world missed out
>> > on something useful by not allowing parts to the smallest
>> > programs. There is a lot one could and should discuss here,
>> > but not me, not tonight.
>
> We do already do that. All concatenative languages (except 01 :-)
> support numbers, which are molecules by your definition. Most support
> strings. Joy quotations are molecules whose component parts happen to
> be a proper subset of Joy itself.
No, I mean something quite different. I did not mean that a molecule
consists
of consecutive digits (as do numerals) or of other printing characters
(as do most symbols). Nor do I mean strings or quotations (including lists).
Using the terminology of the grammar of Joy, all of the above are factors,
resulting in a single operation being performed on the stack. My analogy
was with Unix pipes. Here each command (a molecule in my meaning)
might consist of a primary command (an atom in my meaning)) together with
any (often optional) additional atoms. Some of these are additional
parameters,
some of these are command modifiers. None of these is a command
by itself. The Unix pipe is a concatenation of such molecules.
- Manfred
[Non-text portions of this message have been removed]
John Cowan — 2008-04-01 17:15:19
Manfred Von Thun scripsit:
> My analogy was with Unix pipes. Here each command (a molecule in my
> meaning) might consist of a primary command (an atom in my meaning))
> together with any (often optional) additional atoms. Some of these
> are additional parameters, some of these are command modifiers. None
> of these is a command by itself. The Unix pipe is a concatenation of
> such molecules.
But surely a molecule like "ls -l -C 2" is just syntactic sugar for
ordinary Joy "[-l -c 2] ls", where the list is treated by the "ls"
word as a list, not a quotation?
--
"Well, I'm back." --Sam John Cowan <
cowan@...>
Manfred Von Thun — 2008-04-02 02:12:56
On 2/4/08 3:15 AM, "John Cowan" <
cowan@...> wrote:
> Manfred Von Thun scripsit:
>
>> > My analogy was with Unix pipes. Here each command (a molecule in my
>> > meaning) might consist of a primary command (an atom in my meaning))
>> > together with any (often optional) additional atoms. Some of these
>> > are additional parameters, some of these are command modifiers. None
>> > of these is a command by itself. The Unix pipe is a concatenation of
>> > such molecules.
>
> But surely a molecule like "ls -l -C 2" is just syntactic sugar for
> ordinary Joy "[-l -c 2] ls", where the list is treated by the "ls"
> word as a list, not a quotation?
That is one possible notation. But if a command frequently uses no
modifiers,
then that notation would force users to supply an empty list of modifiers,
as ³[] ls² for your example, in the most frequent uses.
My list of candidate notations, using your example of ³ls², and their
drawbacks:
1. [-l c 2] ls # forces empty list of modifiers if none are wanted
2. ³la² ls # ditto, only useful for plain flags, no good for other
parameters
3. foo | ls l c 2 | bar # unix style pipe symbol, painful if modifiers are
rare
4. (ls l c 2) # Lisp notation optional modifier list
5. ls(-l c 2) # functional notation optional modifier list, currently my
favourite
I must confess that my own list of possible modifiers for concatenative
languages
is miniscule compared with the multitude of modifiers in unix. But I am
hoping that
that is mostly a failure of imagination on my part.
If anything like this is introduced, then a decision has to be made whether
modifiers
are just for the primitives or also for user defined molecules.
- Manfred
[Non-text portions of this message have been removed]
John Cowan — 2008-04-02 03:49:52
Manfred Von Thun scripsit:
> > But surely a molecule like "ls -l -C 2" is just syntactic sugar for
> > ordinary Joy "[-l -c 2] ls", where the list is treated by the "ls"
> > word as a list, not a quotation?
>
> That is one possible notation. But if a command frequently uses no
> modifiers, then that notation would force users to supply an empty list
> of modifiers, as ³[] ls² for your example, in the most frequent uses.
Indeed. But I was only saying that arguments to a word are nothing
*fundamentally* new, unlike (say) alternation. That doesn't mean that
the syntactic sugar isn't worth having.
> 5. ls(-l c 2) # functional notation optional modifier list, currently my
> favourite
I too prefer this syntax.
> I must confess that my own list of possible modifiers for concatenative
> languages is miniscule compared with the multitude of modifiers in
> unix. But I am hoping that that is mostly a failure of imagination on
> my part.
Modifiers to primitives may not be that useful, but modifiers to
user-written words are a different story.
> If anything like this is introduced, then a decision has to be made
> whether modifiers are just for the primitives or also for user defined
> molecules.
I think it's important to have them for both.
--
John Cowan
cowan@... http://ccil.org/~cowan
I am he that buries his friends alive and drowns them and draws them
alive again from the water. I came from the end of a bag, but no bag
went over me. I am the friend of bears and the guest of eagles. I am
Ringwinner and Luckwearer; and I am Barrel-rider. --Bilbo to Smaug
William Tanksley, Jr — 2008-04-02 17:58:00
Manfred Von Thun <
m.vonthun@...> wrote:
> > > wrote:
> >> > The upshot: have we in the concatenative world missed out
> >> > on something useful by not allowing parts to the smallest
> >> > programs. There is a lot one could and should discuss here,
> >> > but not me, not tonight.
> > We do already do that. All concatenative languages (except 01 :-)
> > support numbers, which are molecules by your definition. Most support
> > strings. Joy quotations are molecules whose component parts happen to
> > be a proper subset of Joy itself.
> No, I mean something quite different. I did not mean that a molecule
> consists
> of consecutive digits (as do numerals) or of other printing characters
> (as do most symbols). Nor do I mean strings or quotations (including lists).
> Using the terminology of the grammar of Joy, all of the above are factors,
> resulting in a single operation being performed on the stack. My analogy
> was with Unix pipes. Here each command (a molecule in my meaning)
> might consist of a primary command (an atom in my meaning)) together with
> any (often optional) additional atoms. Some of these are additional
> parameters,
> some of these are command modifiers. None of these is a command
> by itself. The Unix pipe is a concatenation of such molecules.
I see. You want not an ability to define ANY type of syntax (which is
what I described), but rather a small, standard syntax suited to
common problems.
That's an interesting problem. The syntax you propose reminds me of
strongForth's inline type specifiers: because Forth's "EXECUTE" (a
rough equivalent to Joy's "i") could have any stack effect and
StrongForth has no type inference, Becher did not define "EXECUTE",
and instead defined "EXECUTE(", a word which parsed for a close-paren
and interpreted the contents as a type signature.
I also note that Joy currently has words which would benefit from
this; for example, all the words that have a number as part of their
name could be replaced by the single word without the number, but
taking an optional argument.
REBOL does this kind of thing with the "/" (refinement) construct.
> - Manfred
-Wm
Manfred Von Thun — 2008-04-09 08:02:03
On 2/4/08 1:49 PM, "John Cowan" <
cowan@...> wrote:
> Manfred Von Thun scripsit:
> ....
> Indeed. But I was only saying that arguments to a word are nothing
> *fundamentally* new, unlike (say) alternation. That doesn't mean that
> the syntactic sugar isn't worth having.
>
What a coincidence. Last weekend I started work on a non-deterministic
postfix stack language, which of course has alternation as one of its
principal program forming operators. That makes it non-concatenative
I suppose.
>
> ...
> Modifiers to primitives may not be that useful, but modifiers to
> user-written words are a different story.
>
>> > If anything like this is introduced, then a decision has to be made
>> > whether modifiers are just for the primitives or also for user defined
>> > molecules.
>
> I think it's important to have them for both.
To have both would imply a huge revision of the language. To have modifiers
just for primitives would be much easier. And there is a further, more
modest, choice: Find a collection of fixed modifiers that make sense to
apply to (just about) anything. Again I cannot think of any such beasts
whose actions cannot be achieved equally well by combinators. They would
be variants to the i combinator:
[...] i
[...] [f g h] flagged-i
Now it may be that there are no flags of any kind that whose effects cannot
be achieved by existing mechanisms. Well, that may be failure of the
imagination,
or it indicates that the existing machinery is really quite good already.
- Manfred
[Non-text portions of this message have been removed]