david madore's yin/yang mind-boggler
stevan apter — 2004-07-25 19:11:53
sa@dfa.com — 2004-07-28 18:08:41
basic documentation for XY is done (
http://www.nsl.com/papers/xy.htm), and
most of the bugs have been knocked out of the code (accessible from the
paper.)
i've implemented several of the k adverbs (each, apply, converge) and a
few of the many joy combinators (linrec, infra, cond, ifte).
there are 19 XY primitives. here they are (X is the result stack, Y is the
input queue, -> separates before and after state, ^ is concatenation):
{ set pattern ( X : {^a^b^}^Y -> X
: Z^Y ), Z = b/X[a]
{{ get pattern ( X : {{^a^}}^Y -> X
: Z^Y ), Z = X[a]
\s set left ( X^z : Y -> z : Y )
/s set right ( X^z : Y -> X : z )
/ cache ( X^z : Y -> X :
Y^z) )
\ uncache ( X : Y^z -> X^z : Y
)
// queue ( X^z : Y -> X : z^Y
)
\\ stack ( X : z^Y -> X^z : Y
)
; define ( X^;^w^d^; : Y -> X
: Y ), w = d
.g get ( X^".." : Y ->
X^[V("..")] : Y )
.s set ( X^v^".." : Y -> X
: Y => V("..") = v )
.p parse ( X^".." : Y ->
X^[..] : Y )
.r represent ( X^[..] : Y -> X^".." : Y
)
.i input ( X : Y -> X^s : Y,
s accepted )
.o output ( X^s : Y -> X : Y,
s printed )
.e evaluate (alternate) ( X^[p q] : Y -> p(X,Y) or
if p fails then q(X,Y) )
( X^[p] : Y ->
p(X,Y) or if p fails then X : Y )
.a apply ( X^X0^Y0 : Y ->
X^X1^Y1 : Y )
@0 amend ( X^a^b^c : Y -> X^d
: Y), d = @[a;b;:;c]
.0 dmend ( X^a^b^c : Y -> X^d
: Y), d = .[a;b;:;c]
sa@dfa.com — 2004-07-28 18:40:49
i hate my mail program.
hate hate hate.
find the un-pretzeled version on my website.
phimvt@lurac.latrobe.edu.au — 2004-08-03 06:12:06
It would be useful for readers if there was some kind of compact
comparison of the various concatenative languages that we have
been discussing here. I am proposing that this could be a joint
effort, with sections preferably pretty much the same length.
Something like 500 words, to be discussed. I would propose
sections (and authors) as follows:
1. Concatenative languages in general (MvT)
2. Forth (BT)
3. Joy (MvT)
4. cK (SA)
5. Factor (SP)
6. XY (SA)
This list is in what I remember as the chronological order.
I cannot tell whether 4. and 6. should be treated as one
or two. I also know that there are (were ?) one or two other
designs in the making, this would be a good spot to revive
them. Of course the sections can only give a superficial
view of the languages, but such is the nature of comparisons.
But we could also make the sections longer.
I there is interest in such a collaborative effort, I should
write a draft of section 1. rather quickly so that all authors
can comment on it and then write their own specialised section
with possible reference to it.
Any thoughts?
- Manfred
William Tanksley, Jr — 2004-08-04 01:43:12
I'd be glad to write about Forth. When you ask for a comparison,
though, do you mean something more like a precis, or a summary? I
couldn't compare Forth to any of the others except Joy or maybe cK; I
don't know enough about them to do them justice. But I'd be glad to
talk about Forth :-).
-Billy
Slava Pestov — 2004-08-04 01:55:21
Hi,
I think this is a great idea! Do you want each section to be 'free
standing', or discuss differences with other concatenative languages?
phimvt@... wrote:
> It would be useful for readers if there was some kind of compact
> comparison of the various concatenative languages that we have
> been discussing here. I am proposing that this could be a joint
> effort, with sections preferably pretty much the same length.
> Something like 500 words, to be discussed. I would propose
> sections (and authors) as follows:
>
> 1. Concatenative languages in general (MvT)
> 2. Forth (BT)
> 3. Joy (MvT)
> 4. cK (SA)
> 5. Factor (SP)
> 6. XY (SA)
>
> This list is in what I remember as the chronological order.
> I cannot tell whether 4. and 6. should be treated as one
> or two. I also know that there are (were ?) one or two other
> designs in the making, this would be a good spot to revive
> them. Of course the sections can only give a superficial
> view of the languages, but such is the nature of comparisons.
> But we could also make the sections longer.
>
> I there is interest in such a collaborative effort, I should
> write a draft of section 1. rather quickly so that all authors
> can comment on it and then write their own specialised section
> with possible reference to it.
>
> Any thoughts?
>
> - Manfred
sa — 2004-08-04 07:51:03
i'm not sure when i'll be able to get to this - perhaps in a few weeks.
meanwhile, i've encountered some serious difficulties with the xy
design, which i'm not sure how to handle - perhaps someone else
has some ideas.
here's the issue:
in xy, you can define uncons1 as the pattern:
; uncons1 { [[a A]] a A } ;
uncons1 expects a list with car a and cdr A, and it pushes *onto the queue*
the elements a and A. if [a A] is e.g. [1 2 3], then 1 and [2 3] are pushed
onto the queue and then evaluated, leaving 1 and [2 3] on the stack. but
if [a A] is [+ 2 3], then + and [2 3] are pushed, with the consequence that
+ is evaluated, and then [2 3]. this is not what we want for uncons. so we
can (should) define uncons as:
; uncons { [[a A]] `a A } ;
in which case `+ and [2 3] are pushed, and so + and [2 3] wind up on the
stack.
this seems to work fine: use ` to block evaluation - ` is shorthand for
\\ a
where \\ is the primitive quotation word: it takes the next thing on the
queue (a) and pushes it, unevaluated, onto the result stack.
i haven't yet convinced myself that this blocks unwanted evaluation in
all circumstances, but i've not yet succeeded in defining, in terms of the
XY primitives, all the combinators on my list (i.e. Joy + K), which i think
of as a kind of "proof of concept" of the basic idea that XY provides
methods for manipulating unevaluated tokens in the queue.
i'm tied up with work for the next several weeks, so i don't expect to have
any time to pursue this.
-----Original Message-----
From: "William Tanksley, Jr" <
wtanksleyjr@...>
Sent: Aug 4, 2004 3:43 AM
To:
concatenative@yahoogroups.com
Subject: Re: [stack] Five (?) concatenative languages
I'd be glad to write about Forth. When you ask for a comparison,
though, do you mean something more like a precis, or a summary? I
couldn't compare Forth to any of the others except Joy or maybe cK; I
don't know enough about them to do them justice. But I'd be glad to
talk about Forth :-).
-Billy
Yahoo! Groups Links
William Tanksley, Jr — 2004-08-04 15:15:16
On Wed, 4 Aug 2004 09:51:03 +0200 (GMT+02:00), sa <
sa@...> wrote:
> in xy, you can define uncons1 as the pattern:
> ; uncons1 { [[a A]] a A } ;
This makes sense.
> uncons1 expects a list with car a and cdr A, and it pushes *onto the queue*
> the elements a and A. if [a A] is e.g. [1 2 3], then 1 and [2 3] are pushed
> onto the queue and then evaluated, leaving 1 and [2 3] on the stack. but
> if [a A] is [+ 2 3], then + and [2 3] are pushed, with the consequence that
> + is evaluated, and then [2 3]. this is not what we want for uncons. so we
> can (should) define uncons as:
This doesn't make sense to me. Oh, yes, I suspect you can make it work
this way, but allowing things to execute inside your stack manipulator
word exposes your internal order of evaluation, which doesn't seem
very clean.
I also have to ask -- how did the execution of + get inside your list?
I can see how + itself got in there, so I'd expect + to be left on the
stack; but I don't see how or why any purely list operation could
"accidentally" execute anything.
-Billy
sa@dfa.com — 2004-08-04 15:39:45
suppose the queue consists of
[+ 2 3] { [[a A]] a A }
so [+ 2 3] is pushed on the stack, then { is evaluated, which looks
ahead to the closing } and takes the list [[[a A]] a A ], matches [+ 2 3]
to [a A], and populates a with + and A with [2 3]. + and [2 3] are then
pushed onto the *queue*, *not* the stack. the evaluator continues to
process the queue. it finds +, and then *evaluates* it. which is not
what we want.
on the other hand,
[+ 2 3] { [[a A]] `a A }
leaves
\\ + [2 3]
on the queue, which *is* what we want: \\ is evaluated, which
finds + on the queue, moves it to the stack, &c.
or perhaps i'm not doing a good job explaining how the evaluator
works: at every step it takes both the result stack and the input
queue, and returns both a new result stack and a new input queue.
"William Tanksley, Jr" <
wtanksleyjr@...> wrote on 08/04/2004 05:15:16
PM:
> On Wed, 4 Aug 2004 09:51:03 +0200 (GMT+02:00), sa <sa@...> wrote:
> > in xy, you can define uncons1 as the pattern:
> > ; uncons1 { [[a A]] a A } ;
>
> This makes sense.
>
> > uncons1 expects a list with car a and cdr A, and it pushes *onto the
queue*
> > the elements a and A. if [a A] is e.g. [1 2 3], then 1 and [2 3] are
pushed
> > onto the queue and then evaluated, leaving 1 and [2 3] on the stack.
but
> > if [a A] is [+ 2 3], then + and [2 3] are pushed, with the consequence
that
> > + is evaluated, and then [2 3]. this is not what we want for uncons.
so we
> > can (should) define uncons as:
>
> This doesn't make sense to me. Oh, yes, I suspect you can make it work
> this way, but allowing things to execute inside your stack manipulator
> word exposes your internal order of evaluation, which doesn't seem
> very clean.
>
> I also have to ask -- how did the execution of + get inside your list?
> I can see how + itself got in there, so I'd expect + to be left on the
> stack; but I don't see how or why any purely list operation could
> "accidentally" execute anything.
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
phimvt@lurac.latrobe.edu.au — 2004-08-06 06:08:37
Thanks to everybody for the quick responses. To answer several
questions, here is some clarification.
It would require some detailed knowledge of all the languages
to write a comparison of any one with the rest. Maybe we can
leave such a project for much later. What I had in mind is
much simpler:
The introduction would look roughly like this: Various notations,
various evaluations of expressions, postfix on stack, the
useful stack operations dup swap pop and so on. Then the
important result that these with these operations we are forced
to say that such programs do not operate on numbers but on stacks.
Hence concatenations of various programs compute the composition of
the unary stack functions that are computed by the various parts.
This is concatenative notation. No more, except to say that
the various concatenative languages have this as a common part.
I have started on this intro, and found my first version far too
technical. The current one attempts to assume as little as
possible. But I am finding it hard to stick to 500 words as
I had suggested at first. Maybe 600 or 700.
The sections on specific concatenative languages can assume
the introduction but probably not much else. The sections should
contain essentially the principal additions to the bare concatenative
notation. Word limits "negotiable", as they say.
I'll hurry up to get the intro done - but the above summary
should give you some clues to start thinking. And Stevan, yes
we are happy to wait.
Thanks all
- Manfred
Chris Cogan — 2004-08-08 04:01:26
> I'd be glad to write about Forth. When you ask for a comparison,
> though, do you mean something more like a precis, or a summary? I
> couldn't compare Forth to any of the others except Joy or maybe cK; I
> don't know enough about them to do them justice. But I'd be glad to
> talk about Forth :-).
>
> -Billy
Your remarks give me what seems to be a good idea: A list of attributes that
concatenative languages (and sometimes other languages) can have that would
enable them to be both compared to each other and also classified.
1. Concatenation is at least one common trait. But, then, all programming
languages are concatenative in a very broad sense (they concatenate
statements, etc.), so we would want to restrict the term to languages that
basically map the sequence of functions in the language to sequences of
steps in execution, without introducing complexities like
parameter-substitution and complex statements. Joy is more strictly
concatenative than Forth, for example (no control constructs to get in the
way).
2. Another of the features about Joy that distinguish it from conventional
functional languages is the lack of application (or, rather, the completely
automatic nature of application, in that every function is automatically
"applied" to the stack). I assume that all of the language in the list are
like this, so this might not be a good basis for comparison, except with
languages of completely different types.
3. The use of a stack is itself a feature of languages, at least in terms of
how they are typically implemented, and even two languages that use a stack
can be differentiated somewhat on how they use it. Forth has a return stack,
for example, and Joy does not, so those knowledgeable about the other
languages (XY, etc.) might want to discuss the specifics of how the stack is
used, whether they require a return stack, etc.
4. Variables: We can compare languages on both whether they have variables
or not, and, if they do, how they are used. Forth has variables, but it uses
them sparingly, and Joy doesn't even have them.
5. Whether a language has a fairly simple, straightforward structure is
another area of comparison and classification. Joy is even simpler in
structure than Forth, for example.
6. Usefulness for general programming might be another classificatory
dimension, in that, while some languages are theoretically universal, in
practice, they are not very useful. Of course, we might want to qualify this
by saying that a language is useful for such things as studying computation
theory, even if it is not useful for writing games, business applications,
word processors, or various other things.
7. Control constructs. No really useful language gets away with being
completely free of them, if only in the form of conditional branching. But
most modern languages have explicit loops and some variant of if-then-else.
Even Forth has them. Joy does not have them in the usual sense, of course,
but it still has (much nicer) equivalents (ifte, etc). Thus, in describing a
language, we might want to describe how it handles the need to be able to
repeatedly, conditionally, or otherwise control the execution of code.
8. Verbosity might be another dimension. Cobol and (I think) PL/1 are
probably at least among the most verbose languages. APL and Forth and Joy
all tend to require less long-windedness to "say" something in them than is
required in other languages at the same general level of programming.
9. What might be called programmer-efficient programming might be another
"dimension." One of the things I like about Joy, Forth, Factor, etc., is the
ease with which fragments of code can be given names and thereby made into
single words/atoms. Many languages typically don't allow fairly short
stretches of code to be turned into named entities. The only way you can get
significant compression is by finding longer stretches of code that you use
often enough to make it worthwhile to turn them into functions or
subroutines. You won't find swons very tersely defined in Basic. In Basic,
even if you have both swap and cons already written, there is still a lot of
overhead in using them to write swons:
Sub swons()
swap()
cons()
End Sub
Compare this with:
swons == swap cons ;
This latter is programmer-efficient coding. Don't get me started on Cobol or
Pl/1 (yes, I'm afraid I've been around long enough to have worked with PL/1
code, converting PL/1 to Fortran in the 1970's).
10. Does code = data? Can we manipulate code easily with other code? It has
been a primary design constraint of mine in making my own variant of Joy
that this facility be retained even though it is to be a "compiled" language
(in the form of what might be called "object-threaded code"(so far, this is
actually working, though I'm still in mid-implementation).
11. How far from the hardware is the language? One of the things that I
don't much like about Forth is that actual data goes on the stack, so you
can't put a long string on the stack without eating up stack space. In Joy,
it doesn't matter how big a thing is. It takes exactly one unit of stack
space regardless of its actual size, and we don't even have to know how wide
a unit of stack space is. This is not so much a criticism of Forth as it is
a recognition of their different origins and typical uses. For some
purposes, this relative closeness to the hardware is a significant
advantage, but for the kinds of programming that I'm mostly interested in, I
don't want to be concerned with actual stack-width, actual memory, etc.
12. Performance. This is so strongly dependent on how a language is
implemented that it's mostly only meaningful if we are actually considering
implementing something in the language where performance might be an issue.
However, some languages seem more inclined to inefficiency than others,
almost inherently. This is probably partly due to the difficulty that a
compiler (okay, a compiler-writer) has in determining how to determine the
"lowest common denominator" of code that will work for anything that it
might have to handle.
13. Closeness of fit between code and problem. Lower-level languages tend to
allow the programmers to quite precisely fit the program to the problem.
Higher-level languages tend to be more likely to require either doing more
than one really wants to in order to get done what one wants, or to have
extraneous processing that's not really part of doing what one really wants
the program to do. This is related to, but not identical to, the issue of
verbosity. Some languages tend to have sledgehammers and bulldozers, but no
pliers or tweezers (metaphorically speaking). Cobol has a selection of
clunky tools that are okay for their general uses (like batch processing in
business), but not so good for doing such things as writing a game like Duke
Nukem (I'd use a more recent game as an example, but I'm not a gamer so I
don't keep up). You might be able to write such a game in such a language,
but you'd end up using up a lot of CPU doing things that you don't really
want to do merely because Cobol doesn't offer any more
sharply-discriminating way to do it (consider trying to process lots
bit-masks in Cobol). One way I think of this aspect of a programming
language is: How closely does the outline of the program follow the outline
of the problem? For a metaphor from geometry: An octagon more closely fits
around a circle than a triangle does. The circumference is more nearly equal
to that of the circle, and the area between the circle and the octagon is
smaller than the area between a circle and an enclosing triangle, so there
is, in a sense, less "waste" if one can use an octagon to approximate the
circle rather than a triangle.
What else? I'm sure I've left some things out, if only because I'm getting
sleepy, so this is my official request to others to expand/modify the list
of attributes/dimensions that we might want to use in comparing the
languages MVT listed.
I don't know anything about the other languages other than Forth and a
little about XY and Factor (I skimmed over (some of) the documentation
quickly to get the general idea, but need to go back to it), so it's quite
likely that people can come up with additional language-aspects (or
reformulations of ones listed) for the list.
When we get through, we might be able to make a fairly reasonable
comparison-table (or at least have a list of things to talk about in the
500-word descriptions).
Comments, additions, suggested modifications?
--Chris Cogan
phimvt@lurac.latrobe.edu.au — 2004-08-11 05:56:40
Here is my first draft for the general introduction,
warts and all. But I think the contents will stand.
I send it out straight away so that the authors of
the specific sections can see what they can presuppose
(i.e., very little).
- Manfred
SOME TITLE TO BE DECIDED
Introduction
The following are examples for three possible notations for arithmetic
expressions:
prefix notation : - 12 + 2 3
infix notation : 12 - (2 + 3)
postix notation : 12 2 3 + -
Parentheses are necessary for most larger expressions in infix notation.
They are never necessary in prefix or postfix notation, but they are made
compulsory for two common variants of prefix notation.
Expressions in whatever notation can be evaluated in many ways. One is the
school method of stepwise rewriting of the actual expressions. Another is
translation into one of various computer methods of shuffling results of
operations across several named registers. The only restriction is that
subexpressions have to be evaluated before the enclosing expression.
Apart from this, subexpressions can be evaluated in any order, even
concurrently.
Postfix expressions can also be evaluated on a stack of anonymous
registers. A stack is a linear structure that is best conceived
vertically. There are instructions to "push" value on top, and to replace
one or several on top by the single result of a computation In the example
it works like this: "Push 12, push 2, push 3, replace top two by their
sum, replace top two by their difference. Note that the instructions are
executed in the same order as the postfix expression.
To square a number it has to be multiplied by itself. To compute the
square of the sum of two and three it should not be necessary to compute
the sum twice. On a stack it coult be computed by
2 3 + dup *
which is executed as "Push 2, push 3, replace top two by their sum, push a
duplicate or copy of the top value. Apart from the "dup" instruction, a
stack can also have a "swap" instruction to interchange the top two
values, and a "pop" instruction to discard the top value. These and
similar others that perform more complex changes are not only useful but
often essential.
The previous expression is not an arithmetical expression in postfix
notation, simply because "dup" is not an arithmetical operator. Therefore
the expression and allits parts have to be interpreted differently: the
whole and any consecutive parts compute unary functions taking a stack as
argument an yielding a stack as result. All but the first part take as
argument the result of the previous part. The whole computes the
composition of the functions computed by its parts.
The whole expression is of course just the linear concatenation of its
parts. Concatenation is an associative operation. The composition of
functions is also associative. So meaning, what is computed, maps the
syntactic operation of concatenation onto the semantic operation of
function composition. This is only possible because both operations are
associative binary operations. Languages with such a connection between
syntax and semantics are what Billy Tanksley has called concatenative
languages.
Apart from the intimate connection between syntax and semantics,
concatenative languages have an interesting property of definitions. In
conventional languegs "square(x)" might be defined as "x * x", or some
variant. Whatever the details, the head of the definition, "square(x)"
introduces a formal parameter "x" which is then used in the body, "x * x".
When the newly defined squaring function is later called with an actual
parameter, the formal parameter has to become associated with this actual
parameter, the value of an expressions. Concatenative languages do not
need such an association, since "square" is simple defined as "dup *".
Arithmetic expressions in prefix notation can also be evaluated on a
stack, and a concatenative language in prefix order can do the same. But
in either case the order of execution has to be backward and hence is less
natural. All existing concatenative languages use a stack, but this is not
required by the definition - structures other than a stack might fit the
bill. A concatenative language can use a larger structure of which the
stack is only a part. Other parts might be additional stacks or a file
system for explicit input and output. An implementation of a
concatenative language need not evaluate expressions in the order in which
they are written, but can use a different order and even evaluate
concurrently - as long as the final result is the same.
This introduction has described concatenative languages in terms of a core
that is common to all existing implementations. The remainder of this
paper gives a broad summary description of what they add to the common
core. All have numbers, some have other simple data types or structure
such as lists or vectors. Any concatenative language needs a way of
accessing the stack arbitrarily deep below the top, and this is done in
different ways in the examples. Any computer language needs a conditional
construct if-the-else, and there are several concatenative solutions.
Some have second order functions such as "map", "fold" and "filter",
possibly with different names, for processing list or vectors, and some
have many others, including user defined ones. In some "programs = data",
programs can be manipulated on the stack and later executed. Finally,
although all use a stack, some implement the stack as an array (of
consecutive memory locations), and some as a linked list (which
necessitates garbage collection). To some extent the implementations have
affected the design of the languages.
END OF INTRODUCTION
phimvt@lurac.latrobe.edu.au — 2004-08-11 06:32:21
Since there are different ways of doing the conditional in concatenative
languages, it might be good if we all had them for comparison. This is
more or less what I propose to put somewhere in the Joy section:
- Manfred
...
The conditional construct for branching is another combinator, written
"ifte" (short for if-then-else). It needs three parameters, an if-part, a
then-part and an else-part. Like all other combinators in Joy, these
parameters are expected on top of the stack: third from top the if-part,
second from top the then-part, and right on top the elSe-part. The
combinator does not care how and when the parameters got there, but in
most cases they will have been pushed just before "ifte" is executed.
Hence typical usage will take the form
[if-part] [then-part] [else-part] ifte
In execution "ifte" stores away the parameters and then executes the
if-part. Then it restores the stack to what it was before the test.
Finally, if the test yielded true, it executes the if-part, otherwise it
executes the then-part.
...
phimvt@lurac.latrobe.edu.au — 2004-08-11 06:44:32
Billy, you will have seen the previous posting about conditionals in Joy.
The corresponding one for Forth would be something like this (pardon my
Forth, you will have to Forthify it properly, but the intent should be
clear):
...
Forth also provides a conditional construct, which needs three parts: an
if-part, a then-part and an else-part. The if-part has to be a truth
value on top of the stack. The other two parts are always explicitly part
of the program, and they take the form
IF then-part ELSE else-part END
The three capitalised words are the standard syntax.
In execution the top value on the stack is examined,
and if it is true, the then-part is executed, otherwise
the else-part is executed.
...
But feel free to change the style to whatever you are using
in the rest of the Forth section.
- Manfred
phimvt@lurac.latrobe.edu.au — 2004-08-11 06:51:38
On Sat, 7 Aug 2004, Chris Cogan wrote:
[..]
> Your remarks give me what seems to be a good idea: A list of attributes that
> concatenative languages (and sometimes other languages) can have that would
> enable them to be both compared to each other and also classified.
[.. A very long and careful contribution to the discussion ..]
Thank you very much for this, much appreciated. But I will need
more time to stew over the many details. But one thing I would
like to say right now: would you be interested to write a sort
of conclusion/comparison/evaluation to the joint paper? You
seem to be in a better position to write such a thing than anybody
else.
Thanks again
- Manfred
ccogan@cox.net — 2004-08-11 14:57:33
> Thank you very much for this, much appreciated. But I will need
> more time to stew over the many details. But one thing I would
> like to say right now: would you be interested to write a sort
> of conclusion/comparison/evaluation to the joint paper? You
> seem to be in a better position to write such a thing than anybody
> else.
>
> Thanks again
>
> - Manfred
Yes, I would. Of course it would be subject to correction by the rest of the gang. All of the languages and dialects seem to have interesting features or interesting variants of features. I'm not sure of my final opinion on the XY language's queue, but I think it's a clever idea that might smooth out the flow in a language. Salvatore Sanfilippo's "local variables" (in his tcl version of Joy, which he calls Apathy) seems even nicer to me. Perhaps a section on the more or less novel or special features of the languages would be in order.
This might be a good time to bring up the subject of a book on Joy. I've been considering offering to help you do one. You've already got all or nearly all of the basic materials that would go into it. I've been hesitating because I'm not sure I'm in a position to afford the time it would take (though I could do whatever I do in such a way that others could pick up from wherever I left off if I did).
The obvious title would be, _The Joy of Programming_, but that would probably be a little too cutesy (and it suggests a much more general coverage of programming).
--Chris
John Cowan — 2004-08-11 16:14:58
ccogan@... scripsit:
> The obvious title would be, _The Joy of Programming_, but that would probably be a little too cutesy (and it suggests a much more general coverage of programming).
No, no! The title should be _The Programming of Joy_!
--
John Cowan
jcowan@... www.reutershealth.com www.ccil.org/~cowan
No man is an island, entire of itself; every man is a piece of the
continent, a part of the main. If a clod be washed away by the sea,
Europe is the less, as well as if a promontory were, as well as if a
manor of thy friends or of thine own were: any man's death diminishes me,
because I am involved in mankind, and therefore never send to know for
whom the bell tolls; it tolls for thee. --John Donne
Slava Pestov — 2004-08-15 19:41:06
Chris Cogan wrote:
> 2. Another of the features about Joy that distinguish it from conventional
> functional languages is the lack of application (or, rather, the completely
> automatic nature of application, in that every function is automatically
> "applied" to the stack). I assume that all of the language in the list are
> like this, so this might not be a good basis for comparison, except with
> languages of completely different types.
I think the stack is the key concept, not the "concatenative" nature.
The latter is just implied by the former. I'm not aware of any language
with implicit operands and postfix notation that does not use a stack.
> 3. The use of a stack is itself a feature of languages, at least in terms of
> how they are typically implemented, and even two languages that use a stack
> can be differentiated somewhat on how they use it. Forth has a return stack,
> for example, and Joy does not, so those knowledgeable about the other
> languages (XY, etc.) might want to discuss the specifics of how the stack is
> used, whether they require a return stack, etc.
It might also be worth mentioning if the stacks are reflective -- if it
is possible to write a function to print out the stack, etc.
> 5. Whether a language has a fairly simple, straightforward structure is
> another area of comparison and classification. Joy is even simpler in
> structure than Forth, for example.
Forth is simpler than all the others, I think, simply because it can fit
inside, say, 8Kb of assembly, plus some hundreds of lines of supporting
Forth code. The fact that the compiler is written in the language itself
allows one to, for exmple, create a set of words for defining classes
and methods and instantiating objects and so on, going far beyond the
builtin VARIABLE scheme. Factor borrows the Forth metaprogramming model,
but in this case the parser is not as close to the metal as a Forth
compiler -- it simply builds nested linked lists from text. However, the
style of programming is permitted in both, where one can define parsing
words for a domain-specific language.
> 7. Control constructs. No really useful language gets away with being
> completely free of them, if only in the form of conditional branching. But
> most modern languages have explicit loops and some variant of if-then-else.
> Even Forth has them. Joy does not have them in the usual sense, of course,
> but it still has (much nicer) equivalents (ifte, etc). Thus, in describing a
> language, we might want to describe how it handles the need to be able to
> repeatedly, conditionally, or otherwise control the execution of code.
One thing I've noticed is that recursive algorithms in concatenative
languages are almost always as easy to code as iterative ones, and
sometimes easier. It might be worth mentioning if each language promotes
a recursive or iterative style, or both.
> 9. What might be called programmer-efficient programming might be another
> "dimension." One of the things I like about Joy, Forth, Factor, etc., is the
> ease with which fragments of code can be given names and thereby made into
> single words/atoms.
I believe the interactive style of programming, where short expressions
can be tested at the prompt and then built up into complete definitions
in a source file, is another closely related benefit. It is very easy to
try out different approaches interactively, due to the reduced amount of
typing compared to, say, BeanShell (an interactive Java interpreter).
> Many languages typically don't allow fairly short
> stretches of code to be turned into named entities. The only way you can get
> significant compression is by finding longer stretches of code that you use
> often enough to make it worthwhile to turn them into functions or
> subroutines.
Furthermore, in many languages these longer subroutines usually can't
return more than one value. So you are forced to either:
- Side-effect a parameter
- Return a composite type of some kind -- a sequence, or an object with
slots.
- Write your code in such a way that each computation results in one
value only.
> You won't find swons very tersely defined in Basic. In Basic,
> even if you have both swap and cons already written, there is still a lot of
> overhead in using them to write swons:
One thing I've noticed is that a lot of things that are done as macros
of some kind in other languages can be defined as ordinary words in
concatenative languages. For example, a constant can be defined as a
word that just pushes it on the stack.
> 11. How far from the hardware is the language? One of the things that I
> don't much like about Forth is that actual data goes on the stack, so you
> can't put a long string on the stack without eating up stack space.
Many Forths include a memory manager in the style of malloc/free, or you
can write one. And every Forth allows memory to be allocated in the
dictionary with allot/forget.
> 12. Performance. This is so strongly dependent on how a language is
> implemented that it's mostly only meaningful if we are actually considering
> implementing something in the language where performance might be an issue.
> However, some languages seem more inclined to inefficiency than others,
> almost inherently. This is probably partly due to the difficulty that a
> compiler (okay, a compiler-writer) has in determining how to determine the
> "lowest common denominator" of code that will work for anything that it
> might have to handle.
It might be worth mentioning the execution models typical for the
language. For example, Forth is usually implemented as indirect, direct
or subroutine threaded code. Factor and Joy interpreters iterate linked
lists recursively.
Slava
phimvt@lurac.latrobe.edu.au — 2004-08-17 06:14:19
Here is my draft for the Joy section.
I humbly submit it to your savage criticism.
- Manfred
THE CONCATENATIVE LANGUAGE JOY
The datatypes of Joy are integers, reals, truth values, strings (of
characters), small sets of numbers (0..31), dates and times, possibly
heterogeneous lists of any datatypes including lists, and files for
explicit input and output. For all datatypes the usual operators are
provided, and where possible these are polymorphic. In addition to these
there are the operators for shuffling the elements of the untyped stack.
Joy has a large number of combinators, higher order functions which take
other functions as arguments. These arguments are in the form of programs
to compute other functions. Like all other arguments of functions, these
arguments are expected on the stack, but they have to be in an unevaluated
form called quotations, written inside square brackets. Lists are just a
special case of quotations, for example [3 12 7], or [peter paul mary],
or [3 [4 5] "two"].
Three well known higher order functions are for manipulating lists. For
example, given a list of numbers on top of the stack, the following simple
programs can be used: the first to produce a list of their squares, the
second to retain numbers less than 10 and discard others, the third to
compute their sum.
[dup *] map
[10 <] filter
0 [+] fold
In all three examples the quotations are being pushed onto the stack just
before the combinators execute.
One important combinator is the "dip" combinator which is used to access
the stack below the top. In the following, the first program adds the
fourth, third and second element on the stack but leaves the first element
on top. The second one interchanges the third and second element and
leaves the first on top.
[+ +] dip
[swap] dip
To access the stack further down than the top element, the "dip"
combinator can be nested.
Many combinators take several quotations as arguments. One example is the
"ifte" (if-then-else) combinator for branching. It expects three
quotations on the stack, an if-part, a then-part, and topmost an
else-part. For example a program which increments numbers less than 10 and
decrements others is this:
[1 <] [1 +] [1 +] ifte
Note that in this example the if-part [10 <] consumes the number argument,
but it is automatically restored before the appropriate other part is
executed.
The three list manipulating combinators at the beginning abstract from
common recursion patterns use with lists. Joy also has combinators that
abstract from more general recursion patterns that are not restricted to
lists. There are combinators for linear recursion, tail recursion, binary
recursion, more general n-ary recursion, and even the rare nested
recursion (best known from the Ackermann function. Most resemble the
"ifte"
combinator, except that the else-part is split into two, and the recursion
occurs between the two parts. For example the quicksort algorithm might be
paraphrased like this: If the list is small, being empty or having only
one member, then it is sorted already. Otherwise, use its first element as
a pivot to split the rest into two lists, those smaller and those larger
than the first. Recursively, sort the two lists, and then combine the two
results with the pivot. The following one-liner implements this in Joy:
[small] [] [uncons [>] split] [swapd cons concat] binrec
^^
two recursions occur here
Note that the recursion occurs without a recursive definition. Of course
Joy allows definitions, including recursive ones, in this style:
square == dup *
The various general and specialised libraries contain many useful
definitions which extend the base language. There is also a simple module
system which so far has not been used much.
The current implementation of Joy is written in C. Programs, quotations,
lists, and the stack itself are implemented as singly linked lists. I
thank members of the "concatenative" mailing group for numerous
suggestions and corrections, especially John Cowan who wrote a major
portion of the implementation.
END OF CONCAT-JOY
phimvt@lurac.latrobe.edu.au — 2004-08-17 06:25:51
On Wed, 11 Aug 2004 ccogan@... wrote:
[..]
> This might be a good time to bring up the subject of a book on Joy.
> I've been considering offering to help you do one. You've already got
> all or nearly all of the basic materials that would go into it. I've
> been hesitating because I'm not sure I'm in a position to afford the
> time it would take (though I could do whatever I do in such a way that
> others could pick up from wherever I left off if I did).
>
> The obvious title would be, _The Joy of Programming_, but that would
> probably be a little too cutesy (and it suggests a much more general
> coverage of programming).
That is certainly something we should discuss in detail. You may or may
not know that my original version of the chapters was written in Latex,
and I still have those files. I tried a publisher, but they did not bite.
Of course by now they are very much outdated, as are the current HTML
pages. We should decide whether to go for Latex or for HTML.
Views anyone ?
And thanks for the offer
- Manfred
phimvt@lurac.latrobe.edu.au — 2004-08-17 06:45:12
On Sun, 15 Aug 2004, Slava Pestov wrote:
> Chris Cogan wrote:
> > 2. Another of the features about Joy that distinguish it from conventional
> > functional languages is the lack of application (or, rather, the completely
> > automatic nature of application, in that every function is automatically
> > "applied" to the stack). I assume that all of the language in the list are
> > like this, so this might not be a good basis for comparison, except with
> > languages of completely different types.
>
> I think the stack is the key concept, not the "concatenative" nature.
> The latter is just implied by the former. I'm not aware of any language
> with implicit operands and postfix notation that does not use a stack.
The stack is not essential, except that:
1. it is an obvious and convenient may of implementing postfix
2. it is psychologically useful for explaining the language
See the chapter on rewriting systems for Joy (which I have not looked at
myself for a long time, I admit). Like any functional language, Joy and
can be implemented by a (non-deterministic) rewriting system. A stack is
just a convenient way to order the steps efficiently.
You are right in saying that Joy does not have an application operation
not even implicitly. If the stack were essential, then application
would be an implicit operation taking the stack as operand. I know
I talk like that (and everybody else does, too), when I explain Joy.
But strictly speaking it is not true. It is a useful myth, but maybe
we should make clearer that it is. So, some better way of talking
and explaining is perhaps called for.
- Manfred
Sergei Zubkov — 2004-08-18 07:35:08
Hello
I believe I haven't posted here yet, but I want to ask something
regarding this thread:
Slava and Manfred wrote:
> > I think the stack is the key concept, not the "concatenative"
> > nature. The latter is just implied by the former. I'm not aware
> > of any language with implicit operands and postfix notation that
> > does not use a stack.
> The stack is not essential, except that:
> 1. it is an obvious and convenient may of implementing postfix
> 2. it is psychologically useful for explaining the language
Here's my question - can J be considered a partially concatenative
language? It has extensive facilities for eliminating explicit
arguments from expressions and creating "trains of verbs" which are
the same (in my opinion) as fragments of a forth-like language
program. Those trains are actually encouraged throughout J manuals.
There is no data stack, but functions and higher-order operators are
contatenated to form an expression that needs only a single
application of its argument, if at all (they have functions that yield
constants, too).
--Sergey Zubkov
sa@dfa.com — 2004-08-18 12:39:43
phimvt@... wrote on 08/17/2004 08:14:19 AM:
>
>
> Here is my draft for the Joy section.
> I humbly submit it to your savage criticism.
>
> - Manfred
>
>
> Many combinators take several quotations as arguments. One example is the
> "ifte" (if-then-else) combinator for branching. It expects three
> quotations on the stack, an if-part, a then-part, and topmost an
> else-part. For example a program which increments numbers less than 10
and
> decrements others is this:
>
> [1 <] [1 +] [1 +] ifte
[10 <] [1 +] [-1 +] ifte
in XY, ifte is defined:
{ [d c t e] d [e t] d c i true? at i }
or non-patternishly as:
pair [[dup] dip i false?] dip swap at i
sa@dfa.com — 2004-08-18 16:25:19
XY implementations of map (still looking for a simpler implementation),
filter, fold:
; map { [a p] `a [a @: [a p i] [[] a p map.] else] [a] if } ;
; map. { [r a p] `a [r a uncons [,: p infra ,] dip p map.] [r] if } ;
; filter { [l p] l l p i &: @ } ;
; fold { [a s p] `a [1 a _ s a *: p i p fold] [s] if } ;
a non-patternish filter:
; filter [dup] dip i &: @ ;
William Tanksley, Jr — 2004-08-21 17:21:29
On Wed, 18 Aug 2004 07:35:08 -0000, Sergei Zubkov <
cubbi@...> wrote:
> Here's my question - can J be considered a partially concatenative
> language? It has extensive facilities for eliminating explicit
> arguments from expressions and creating "trains of verbs" which are
> the same (in my opinion) as fragments of a forth-like language
> program. Those trains are actually encouraged throughout J manuals.
> There is no data stack, but functions and higher-order operators are
> contatenated to form an expression that needs only a single
> application of its argument, if at all (they have functions that yield
> constants, too).
No; this means that J is a dataflow-using language. The ability to
write "tacit" functions in J does give you some of the advantages that
concatenative languages share; however, in J that ability is largely
accidental, and in fact all of the manuals I've read say that nobody
knows whether it's possible to write every program tacitly. In
concatenative languages, it's fundamental.
BTW, the last thing I read about J was that the newest interpreter
removed the ability to use trains. The only ones remaining are the
hook and the fork. The problem is that nobody actually used the other
ones, and they were rather arbitrary.
> --Sergey Zubkov
-Billy
phimvt@lurac.latrobe.edu.au — 2004-08-24 06:01:07
Would Sergei or Billy be interested to write a short exposition
of this for the "5 concat L's" (maybe 5.5 or 6)? Back in the
early days of the concatenative mailing group there was some
discussion of J already.
- Manfred
On Sat, 21 Aug 2004, William Tanksley, Jr wrote:
> On Wed, 18 Aug 2004 07:35:08 -0000, Sergei Zubkov <cubbi@...> wrote:
> > Here's my question - can J be considered a partially concatenative
> > language? It has extensive facilities for eliminating explicit
> > arguments from expressions and creating "trains of verbs" which are
> > the same (in my opinion) as fragments of a forth-like language
> > program. Those trains are actually encouraged throughout J manuals.
> > There is no data stack, but functions and higher-order operators are
> > contatenated to form an expression that needs only a single
> > application of its argument, if at all (they have functions that yield
> > constants, too).
>
> No; this means that J is a dataflow-using language. The ability to
> write "tacit" functions in J does give you some of the advantages that
> concatenative languages share; however, in J that ability is largely
> accidental, and in fact all of the manuals I've read say that nobody
> knows whether it's possible to write every program tacitly. In
> concatenative languages, it's fundamental.
>
> BTW, the last thing I read about J was that the newest interpreter
> removed the ability to use trains. The only ones remaining are the
> hook and the fork. The problem is that nobody actually used the other
> ones, and they were rather arbitrary.
>
> > --Sergey Zubkov
>
> -Billy
phimvt@lurac.latrobe.edu.au — 2004-08-24 06:23:34
On Wed, 18 Aug 2004
sa@... wrote:
> phimvt@... wrote on 08/17/2004 08:14:19 AM:
> > Many combinators take several quotations as arguments. One example is the
> > "ifte" (if-then-else) combinator for branching. It expects three
> > quotations on the stack, an if-part, a then-part, and topmost an
> > else-part. For example a program which increments numbers less than 10
> and
> > decrements others is this:
> >
> > [1 <] [1 +] [1 +] ifte
>
> [10 <] [1 +] [-1 +] ifte (* OOPS, yes, 10 of course, MvT *)
> in XY, ifte is defined:
>
> { [d c t e] d [e t] d c i true? at i }
>
> or non-patternishly as:
^^^^^^^^^^^^^^^^ I admire your creative use of the English language
>
> pair [[dup] dip i false?] dip swap at i
In Joy, a program that increments the number on top of the stack
if the five numbers on top of the stack add up to less than 100
and otherwise decrements it is this:
[+ + + + 100 <] [1 +] [1 -] ifte
This is possible because after the test the stack is restored
to what it was before the test, and then either the then-part
of the else-part is executed. One way to define ifte in Joy
might be a (somewhat clumsy) way that uses the stack operator
to save the stack somehow, and then uses the (Forth-like)
branch operator. But actually ifte is inbuilt, of course.
I point this out, because I am not really sure whether
you definition of ifte in XY could handle if-part tests
which destroy an arbitrary amount of stack.
Or, to give another example, here is a program which
increments/decrements the top number according as
the fifth number from the top is less than 10:
[pop pop pop pop 10 <] [1 +] [1 -] ifte
- Manfred
sa@dfa.com — 2004-08-24 07:22:54
phimvt@... wrote on 08/24/2004 08:23:34 AM:
[:]
> In Joy, a program that increments the number on top of the stack
> if the five numbers on top of the stack add up to less than 100
> and otherwise decrements it is this:
> [+ + + + 100 <] [1 +] [1 -] ifte
> This is possible because after the test the stack is restored
> to what it was before the test, and then either the then-part
> of the else-part is executed. One way to define ifte in Joy
> might be a (somewhat clumsy) way that uses the stack operator
> to save the stack somehow, and then uses the (Forth-like)
> branch operator. But actually ifte is inbuilt, of course.
>
> I point this out, because I am not really sure whether
> you definition of ifte in XY could handle if-part tests
> which destroy an arbitrary amount of stack.
of course you are right. here is a version which conforms
to the joy spec:
{ [c t e] [e t] _x c infra *: true? @ i }
thanks
>
> Or, to give another example, here is a program which
> increments/decrements the top number according as
> the fifth number from the top is less than 10:
> [pop pop pop pop 10 <] [1 +] [1 -] ifte
>
> - Manfred
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>