an exchange on flatness
stevan apter — 2005-07-16 17:30:52
the following is a (slightly edited) conversation which took place
on #concatenative earlier this morning.
comments?
-------------
<eiz> How is 'flatness' in any way desirable in the first place?
<sa> it permits factoring at finer granularity
<eiz> Sorry, you have to do better than that =) Is this finer granularity
actually useful?
<sa> it is theoretically smoother - punctuation symbols become functions
<sa> the only punctuation symbol is the blank
<sa> it obviates the need for a separate macro facility
<sa> i never know how to answer the question "is it useful?" that's a very
deep question.
<sa> so there are three reasons ..
<eiz> I don't know, it seems kind of goofy to me
<sa> "goofy" =abbrev "good for you" :)
<sa> initially, i was skeptical. but the idea has grown on me.
<eiz> There aren't any compelling examples
<sa> well, not yet
<sa> reason 2 seems to me to be the strongest. flat languages have some nice
theoretical properties
<sa> e.g. a program is a sequence of tokens. all partitionings of the sequence
are semantically equivalent
<eiz> Well, you know my take on that... :P
<sa> no, i really don't
<sa> the parser for a flat language = tokenizer + typer
<eiz> Theoretical properties only interest me if they improve real programs
<sa> theoretical simplicity -> conceptual simplicity -> improvement in
productivity (other things being equal)
<eiz> Only to a point
<sa> suppose you have five programs which begin with the sequence [ 2 + *
<eiz> Unlambda and Brainfuck are certainly very conceptually simple, for example
<sa> then you can factor that out as : f [ 2 + *
<sa> unlambda isn't simple at all!
<sa> continuations, delays, promises ... side-effects!!
<eiz> pfft, it's still simple
<sa> but what about my example -- : f [ 2 + ; -- you have five programs which
begin with "make a list with 2 + as initial elements". you can factor that out
and give it a name. (assume that it's not an accident that they begin with f -
now you have just one place in the code you have to change)
<eiz> Because I don't believe that kind of micro-factoring is useful
<sa> ah
<eiz> [ 2 + is not a full thought, you're just applying compression to your
program at that point
<sa> ah
<sa> so you think that "thoughts" align on boundaries defined syntactically by
mated brackets
<sa> that's an interesting hypothesis
<eiz> Not necessarily, but I don't think [ 2 + says much of anything
<sa> and you think that factoring is only useful when it's applied to "full
thoughts"
<sa> [ 2 + means "(a program which) starts by adding 2 and continues ..."
* eiz wonders what this word would be called
<eiz> I think if you can't give it a good name, it's too small.
<sa> add2then
<eiz> heheh
<sa> you could adopt the convention that initial sub-quotation definitions
end in "then" and terminal subquotation words begin with "and"
* sa admits that this doesn't seem entirely convincing
William Tanksley, Jr — 2005-07-26 01:02:11
stevan apter <
sa@...> wrote:
> <eiz> How is 'flatness' in any way desirable in the first place?
I can say that SOME flatness is desirable -- it makes programming in
Forth pleasant. The idea of a completely flat language is new and
untested, so I can't say whether it's more desirable than all the
things we'd be giving up in order to get it.
> <sa> theoretical simplicity -> conceptual simplicity -> improvement in
> productivity (other things being equal)
> <eiz> Only to a point
Ah, but where exactly is that point? We don't know.
> <eiz> Because I don't believe that kind of micro-factoring is useful
> <eiz> [ 2 + is not a full thought, you're just applying compression to your
> program at that point
Again, nobody's tried. We just don't know -- few people have even
thought about it. Realistically, it's quite probable that
microfactoring IS useful in at least a few cases; the real question is
whether it's generally useful. Macros are more useful than most
programmers realise; just ask a Lisp programmer.
-Billy
Mackenzie Straight — 2005-07-26 07:19:48
On 7/25/05, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> Ah, but where exactly is that point? We don't know.
I don't see how adding extra modes, markers or other doodads
'simplifies' anything in the first place. From a user perspective it
seems fairly useless (pending examples to the contrary -- really, I
want to be proven wrong here), and from an implementation perspective
it's yet another thing to worry about optimizing, as the naive method
is laughably inefficient, to say nothing of the fact that the tree
structure of source code is highly useful for tools like
pretty-printers, editors, etc...
Really, what's simpler (I'll use the latest XY's notion of flatness,
as that is what my original comments were based on):
[ is a literal which, when present on the stack, causes the
interpreter to go into a special mode in which all words -- except 3
magic words -- are pushed onto the stack literally instead of being
executed.
vs.
[ ... ] is a list of things.
Or even the Factor definitions:
: [ f ; parsing
: ] reverse swons ; parsing
I know which I prefer.
> > <eiz> Because I don't believe that kind of micro-factoring is useful
> > <eiz> [ 2 + is not a full thought, you're just applying compression to your
> > program at that point
>
> Again, nobody's tried. We just don't know -- few people have even
> thought about it. Realistically, it's quite probable that
> microfactoring IS useful in at least a few cases; the real question is
> whether it's generally useful. Macros are more useful than most
> programmers realise; just ask a Lisp programmer.
I haven't managed to convince myself that it's a good idea. I don't
think about programs in terms of tokens. I don't want to.
> -Billy
--eiz
stevan apter — 2005-07-26 10:58:05
----- Original Message -----
From: "Mackenzie Straight" <eizneckam@...>
To: <concatenative@yahoogroups.com>
Sent: Tuesday, July 26, 2005 3:19 AM
Subject: Re: [stack] an exchange on flatness
> On 7/25/05, William Tanksley, Jr <wtanksleyjr@...> wrote:
> > Ah, but where exactly is that point? We don't know.
>
> I don't see how adding extra modes, markers or other doodads
> 'simplifies' anything in the first place. From a user perspective it
> seems fairly useless (pending examples to the contrary -- really, I
> want to be proven wrong here), and from an implementation perspective
> it's yet another thing to worry about optimizing, as the naive method
> is laughably inefficient, to say nothing of the fact that the tree
> structure of source code is highly useful for tools like
> pretty-printers, editors, etc...
>
> Really, what's simpler (I'll use the latest XY's notion of flatness,
> as that is what my original comments were based on):
>
> [ is a literal which, when present on the stack, causes the
> interpreter to go into a special mode in which all words -- except 3
> magic words -- are pushed onto the stack literally instead of being
> executed.
>
> vs.
>
> [ ... ] is a list of things.
>
> Or even the Factor definitions:
>
> : [ f ; parsing
> : ] reverse swons ; parsing
>
> I know which I prefer.
but if you give up quotations for eager lists, which billy seems
willing to do, then the rule is just:
[ is a literal:
X [^Y -> X^[ Y]
] finds its [-mate, enlists, pushes onto the stack, i.e.
[X^[^Z ]^Y] -> [X^[Z] Y]
there are no markers, modes, magic words, or other doo-dads.
>
> > > <eiz> Because I don't believe that kind of micro-factoring is useful
> > > <eiz> [ 2 + is not a full thought, you're just applying compression to your
> > > program at that point
> >
> > Again, nobody's tried. We just don't know -- few people have even
> > thought about it. Realistically, it's quite probable that
> > microfactoring IS useful in at least a few cases; the real question is
> > whether it's generally useful. Macros are more useful than most
> > programmers realise; just ask a Lisp programmer.
>
> I haven't managed to convince myself that it's a good idea. I don't
> think about programs in terms of tokens. I don't want to.
>
> > -Billy
>
> --eiz
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2005-07-27 05:04:19
Mackenzie Straight <
eizneckam@...> wrote:
> On 7/25/05, William Tanksley, Jr <wtanksleyjr@...> wrote:
> > Ah, but where exactly is that point? We don't know.
> I don't see how adding extra modes, markers or other doodads
> 'simplifies' anything in the first place.
That's not the question -- the question is whether *removing* all of
the modes, markers, and other doodads simplifies things too much.
That's the purpose of flatness.
> From a user perspective it
> seems fairly useless (pending examples to the contrary -- really, I
> want to be proven wrong here),
Well, consider that one of the nicest practical features of
concatenative languages, easy factoring, is easy only where the
language is flat. Anywhere the language becomes non-flat -- near an IF
in Forth, or near a [ in Joy -- factoring becomes nontrivial.
This is a handwaving claim, however. I have no real proof or evidence
-- in fact, I admit that Forth and Joy may already receive the best
benefits of flatness, and anything more will have diminishing returns.
But if so, this is an accident, because neither language was designed
with the idea of flatness in mind. It's interesting that Chuck Moore
has since invented, and now does all his work in, a flatter language
than Forth.
Rather than assuming that Forth and Joy are coincidentally already at
the perfect level of flatness, I'd like to check.
> and from an implementation perspective
> it's yet another thing to worry about optimizing, as the naive method
> is laughably inefficient,
The naive method results immediately in a dataflow graph, which other
languages have to perform multiple steps to produce. Every decent
optimiser starts with a dataflow graph. And THIS graph expresses the
explicit intentions of the programmer, not some odd combination of the
assumptions of the language designer with the (implicit) intentions of
the programmer.
> to say nothing of the fact that the tree
> structure of source code is highly useful for tools like
> pretty-printers, editors, etc...
All of those things are tools to help recover from the difficulties
caused by overstructured languages. They're symptoms of a problem, not
solutions. (I sound like Chuck Moore now... :-) And anyhow, they're
mostly useless anyhow in most concatenative languages.
> Really, what's simpler (I'll use the latest XY's notion of flatness,
> as that is what my original comments were based on):
> [ is a literal which, when present on the stack, causes the
> interpreter to go into a special mode in which all words -- except 3
> magic words -- are pushed onto the stack literally instead of being
> executed.
Well, I don't find that too useful -- it's modal. But keep in mind
that the mode he's using here is the same thing that Factor hides
behind : and ; -- it's the "compile these things" mode.
> > > <eiz> Because I don't believe that kind of micro-factoring is useful
> > > <eiz> [ 2 + is not a full thought, you're just applying compression to your
> > > program at that point
> > Again, nobody's tried. We just don't know -- few people have even
> > thought about it. Realistically, it's quite probable that
> > microfactoring IS useful in at least a few cases; the real question is
> > whether it's generally useful. Macros are more useful than most
> > programmers realise; just ask a Lisp programmer.
> I haven't managed to convince myself that it's a good idea. I don't
> think about programs in terms of tokens. I don't want to.
Could you clarify? Do you mean that you don't see distinct words when
you look at a program? What do you see?
> --eiz
-Billy
Mackenzie Straight — 2005-07-27 06:40:17
On 7/26/05, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> Mackenzie Straight <eizneckam@...> wrote:
> > On 7/25/05, William Tanksley, Jr <wtanksleyjr@...> wrote:
> > > Ah, but where exactly is that point? We don't know.
>
> > I don't see how adding extra modes, markers or other doodads
> > 'simplifies' anything in the first place.
>
> That's not the question -- the question is whether *removing* all of
> the modes, markers, and other doodads simplifies things too much.
> That's the purpose of flatness.
Except all that this 'flatness' does, as far as I can tell anyway, is
move things from parse time to runtime. The structures are still
there, it's just a matter of when you construct them.
> Well, consider that one of the nicest practical features of
> concatenative languages, easy factoring, is easy only where the
> language is flat. Anywhere the language becomes non-flat -- near an IF
> in Forth, or near a [ in Joy -- factoring becomes nontrivial.
How so? [ foo bar baz ] can be trivially replaced by [ foobar baz ]
and : foobar foo bar ;. If that's not good enough, eager lists may
also help: DEFINE eager == [] swap infra reverse. The problem you are
describing is not one that I have ever encountered in practice.
> > to say nothing of the fact that the tree
> > structure of source code is highly useful for tools like
> > pretty-printers, editors, etc...
>
> All of those things are tools to help recover from the difficulties
> caused by overstructured languages. They're symptoms of a problem, not
> solutions. (I sound like Chuck Moore now... :-) And anyhow, they're
> mostly useless anyhow in most concatenative languages.
I disagree completely, but if you don't like tools, that's fine. I do.
Another example: S-expressions are often used in Lisp to marshal data.
I utilize the syntax of my own concatenative language (a scripting
language for OCaml programs) in a very similar manner. It's quite
handy, although not nearly as powerful as the CL reader. Tree syntax
is useful, and should not be thrown away lightly.
Check this out:
http://factor.modalwebserver.co.nz/responder/browser/
This would be a lot less general and simple if the prettyprinter had
to think about [ and ], to say nothing of [[, ]], {, }, {{, }}, << and
>> as words rather than just seeing a list or other data structure.
> > I haven't managed to convince myself that it's a good idea. I don't
> > think about programs in terms of tokens. I don't want to.
>
> Could you clarify? Do you mean that you don't see distinct words when
> you look at a program? What do you see?
Of course I _see_ the individual tokens. I just don't necessarily
think about them individually. Breaking up a list which is, in my
mind, a single literal object rather than a sequence of words seems
unnatural.
We've been thinking of a Factor editor that directly edits trees in
memory (like SEdit) for some time now. Not a token in sight. I don't
know if that will actually materialize, but it would be nice...
> -Billy
--eiz
William Tanksley, Jr — 2005-08-02 00:06:01
Mackenzie Straight <
eizneckam@...> wrote:
> On 7/26/05, William Tanksley, Jr <wtanksleyjr@...> wrote:
> > Mackenzie Straight <eizneckam@...> wrote:
> > > On 7/25/05, William Tanksley, Jr <wtanksleyjr@...> wrote:
> > > > Ah, but where exactly is that point? We don't know.
> > > I don't see how adding extra modes, markers or other doodads
> > > 'simplifies' anything in the first place.
> > That's not the question -- the question is whether *removing* all of
> > the modes, markers, and other doodads simplifies things too much.
> > That's the purpose of flatness.
> Except all that this 'flatness' does, as far as I can tell anyway, is
> move things from parse time to runtime. The structures are still
> there, it's just a matter of when you construct them.
If the language is lazy such things can be accomplished by the
optimizer quickly in most cases, and deferred in other cases (and
avoided by programmers in the remaining cases). There are other lazy
languages that operate that way.
> > Well, consider that one of the nicest practical features of
> > concatenative languages, easy factoring, is easy only where the
> > language is flat. Anywhere the language becomes non-flat -- near an IF
> > in Forth, or near a [ in Joy -- factoring becomes nontrivial.
> How so? [ foo bar baz ] can be trivially replaced by [ foobar baz ]
> and : foobar foo bar ;. If that's not good enough, eager lists may
> also help: DEFINE eager == [] swap infra reverse. The problem you are
> describing is not one that I have ever encountered in practice.
You'll never encounter it as long as it's impossible to express in
your native language. Imagine trying to explain the concept of zero to
a person whose culture didn't use it... "Well, so you're trying to
tell me I need this because it's good for NOTHING?"
:-)
I've mentioned that ColorForth is a bit flatter than Forth, since it
has no compile/interpret mode, nor any special lookahead words like
":", and that added flatness is a convenience. It's the core of
several regular idioms in the language.
Unlike my extreme flatness, Chuck's colorForth doesn't attempt to take
things too far, and his language is very fast as well as very flat.
> > > to say nothing of the fact that the tree
> > > structure of source code is highly useful for tools like
> > > pretty-printers, editors, etc...
> > All of those things are tools to help recover from the difficulties
> > caused by overstructured languages. They're symptoms of a problem, not
> > solutions. (I sound like Chuck Moore now... :-) And anyhow, they're
> > mostly useless anyhow in most concatenative languages.
> I disagree completely, but if you don't like tools, that's fine. I do.
I didn't say I didn't like tools. I said that many of the tools you
name are merely attempting to overcome the problems your "solutions"
are causing you. If your code has a clear tree structure, your
definitions are too long.
> Another example: S-expressions are often used in Lisp to marshal data.
And Forth code is often used in Forth to construct data. In
colorForth, you'd actually write an editor widget to hold your data,
so that it could be edited inline with the code in a format that's
natural for the data. (I don't know of anyone that's done that aside
from Chuck himself, but he told me that's the intended use of color
Forth.)
I'm not knocking a standard format for data. But if you're talking
about code and data having the same format, well, might as well let
the code do its job.
> I utilize the syntax of my own concatenative language (a scripting
> language for OCaml programs) in a very similar manner. It's quite
> handy, although not nearly as powerful as the CL reader.
You mean not nearly as consistent as the CL reader. CL reader macros
can look like anything, but are a pain to implement; CL macros can
only look like CL function calls, and are reasonably easy to
implement. Concatenative macros can look like anything and are easy to
implement. So I'd say that they're of equal power, but for the same
power concatenative macros are easier. (Qualification: I give Lisp
props for consistency; I can't knock S-exps for consistent data
storage. But that doesn't grant you "power".)
> Tree syntax is useful, and should not be thrown away lightly.
I can see some benefit to throwing it away -- a flat language that
didn't allow tree syntax would be a lot simpler and fast than one that
did. But ignore that for the moment, because I've not proposed
throwing away tree syntax here. I've explained how to be ABLE to do
without it. Just because the language CAN express ideas without it
doesn't mean that programmers should express ALL ideas without it.
> Check this out: http://factor.modalwebserver.co.nz/responder/browser/
> This would be a lot less general and simple if the prettyprinter had
> to think about [ and ], to say nothing of [[, ]], {, }, {{, }}, << and >>
> as words rather than just seeing a list or other data structure.
Wait a sec. If all you want is list literals, my suggestion doesn't
offer anything -- I only eliminate the need to put quotations in
whenever you need conditionals. Lists and data structures are
completely different. Even in my system, you'd still need to put
quotes around strings, and something around lists.
> > > I haven't managed to convince myself that it's a good idea. I don't
> > > think about programs in terms of tokens. I don't want to.
> > Could you clarify? Do you mean that you don't see distinct words when
> > you look at a program? What do you see?
> Of course I _see_ the individual tokens. I just don't necessarily
> think about them individually. Breaking up a list which is, in my
> mind, a single literal object rather than a sequence of words seems
> unnatural.
A list is a single object, of course, and should be expressed in code
that way; its semantics are treelike. But the consequential of a
conditional isn't a list; it's not any (particular) data structure.
It's an action. Insisting that every programmer MUST write it as
though it were a list is a bit overboard.
> We've been thinking of a Factor editor that directly edits trees in
> memory (like SEdit) for some time now. Not a token in sight. I don't
> know if that will actually materialize, but it would be nice...
Good to hear! Sounds fun and useful.
colorForth's editor works essentially that way. Chris Cogan's paper on
QP and Tree-P suggest the ideas as well -- in a completely different
way than how you're planning to do it.
> --eiz
-Billy
Mackenzie Straight — 2005-08-02 00:54:36
On 8/1/05, William Tanksley, Jr <
wtanksleyjr@...> wrote:
>
> > > Well, consider that one of the nicest practical features of
> > > concatenative languages, easy factoring, is easy only where the
> > > language is flat. Anywhere the language becomes non-flat -- near an IF
> > > in Forth, or near a [ in Joy -- factoring becomes nontrivial.
>
> > How so? [ foo bar baz ] can be trivially replaced by [ foobar baz ]
> > and : foobar foo bar ;. If that's not good enough, eager lists may
> > also help: DEFINE eager == [] swap infra reverse. The problem you are
> > describing is not one that I have ever encountered in practice.
>
> You'll never encounter it as long as it's impossible to express in
> your native language. Imagine trying to explain the concept of zero to
> a person whose culture didn't use it... "Well, so you're trying to
> tell me I need this because it's good for NOTHING?"
Okay, show one example of where this sort of thing is actually useful.
That's all I've asked for. I'm not going to just take your word for
it.
> A list is a single object, of course, and should be expressed in code
> that way; its semantics are treelike. But the consequential of a
> conditional isn't a list; it's not any (particular) data structure.
> It's an action. Insisting that every programmer MUST write it as
> though it were a list is a bit overboard.
It's a quotation, which happens to be represented as a list. In the
future, Factor is actually going to have a first class quotation type,
and cons lists are going to have their role seriously reduced or
eliminated, but that's beside the point. The point is that the code
_is_ a data structure.
As for the bit about the problems my "solutions" are causing, I'll
keep them thanks. I don't care to discuss religion on the Internet. =)
> -Billy
--eiz
William Tanksley, Jr — 2005-08-02 02:36:51
Mackenzie Straight <
eizneckam@...> wrote:
> On 8/1/05, William Tanksley, Jr <wtanksleyjr@...> wrote:
> > You'll never encounter it as long as it's impossible to express in
> > your native language. Imagine trying to explain the concept of zero to
> > a person whose culture didn't use it... "Well, so you're trying to
> > tell me I need this because it's good for NOTHING?"
> Okay, show one example of where this sort of thing is actually useful.
> That's all I've asked for. I'm not going to just take your word for
> it.
Okay.
I can't give that to you. Sorry. There are no perfectly flat languages
yet, and there may never be. I'm trying to figure out how to
accomplish such a thing, and I think it can be done... But of course,
that doesn't imply that it SHOULD be done.
However, I don't think this means that it's useless to talk about it,
even though I think that pure flatness probably will be unusable. I
already know that partial flatness is useful, and languages with more
flatness get more useful. I'm certain that there's a point of
diminishing returns, but I want to find it.
Oh, and I've given you examples of partially flat languages. Typical
concatenative languages are inherently flatter than typical
applicative ones; colorForth is flatter than Forth.
> > A list is a single object, of course, and should be expressed in code
> > that way; its semantics are treelike. But the consequential of a
> > conditional isn't a list; it's not any (particular) data structure.
> > It's an action. Insisting that every programmer MUST write it as
> > though it were a list is a bit overboard.
> It's a quotation, which happens to be represented as a list.
No, it "is" not a quotation. Joy and Factor use quotations for it.
Forth doesn't define any data structure. It's easy to define an
improper subset of Forth, "flat Forth", that uses xts (which are
atoms) for the consequentials of conditionals.
Please don't confuse implementation with essence.
> In the
> future, Factor is actually going to have a first class quotation type,
> and cons lists are going to have their role seriously reduced or
> eliminated, but that's beside the point. The point is that the code
> _is_ a data structure.
The code is represented by a data structure. You use a compile-time
list. A list is a great way to gather concatenative code together, but
a very poor way to dissect and manipulate code -- you can do things
with lists that aren't sensible with code.
(You can also do things with my lazy flat language that aren't
sensible with static native code -- this suggests to me that my lazy
flat language isn't the best way to express programming ideas.)
> As for the bit about the problems my "solutions" are causing, I'll
> keep them thanks. I don't care to discuss religion on the Internet. =)
And yet you just did. I didn't bring religion up, after all.
I think your solutions are fair game -- you're the one bringing them
in as a telling argument against flatness, after all. I repeat: the
tools you use are only useful to overcome the problems of a different
type of code. With flat code, different tools would be needed. I
honestly don't know what they'd look like.
> --eiz
-Billy
Daniel Ehrenberg — 2005-08-02 02:53:24
> The code is represented by a data structure. You use a compile-time
> list. A list is a great way to gather concatenative code together, but
> a very poor way to dissect and manipulate code -- you can do things
> with lists that aren't sensible with code.
What are you saying? That a language needs to restrict how people
manipulate code? I don't see why. It's possible to do things with cons
cells that don't make sense to do with lists, but does that mean lists
shouldn't be made with cons cells? It is very useful to have code be
[represented by] an accessable data structure; Lisp macros are a
testimate to that, and Factor sometimes does similar things, though
not as often.
Daniel Ehrenberg
Mackenzie Straight — 2005-08-02 04:18:29
On 8/1/05, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> No, it "is" not a quotation. Joy and Factor use quotations for it.
> Forth doesn't define any data structure. It's easy to define an
> improper subset of Forth, "flat Forth", that uses xts (which are
> atoms) for the consequentials of conditionals.
>
> Please don't confuse implementation with essence.
I am well aware that Forth does not have quotations. Ask yourself
this, though: what is the fundamental difference between a quotation
and an xt? The answer is simple: xts are opaque, and can't really be
manipulated. But aside from that they're basically the same thing.
(Would an xt-forth qualify as 'flat'?)
>
> > In the
> > future, Factor is actually going to have a first class quotation type,
> > and cons lists are going to have their role seriously reduced or
> > eliminated, but that's beside the point. The point is that the code
> > _is_ a data structure.
>
> The code is represented by a data structure. You use a compile-time
> list. A list is a great way to gather concatenative code together, but
> a very poor way to dissect and manipulate code -- you can do things
> with lists that aren't sensible with code.
A very poor way to manipulate code? Lists have been working quite well
for manipulating source code for the last 42 years. I've grown
somewhat attached to the notion, myself.
> I think your solutions are fair game -- you're the one bringing them
> in as a telling argument against flatness, after all. I repeat: the
> tools you use are only useful to overcome the problems of a different
> type of code. With flat code, different tools would be needed. I
> honestly don't know what they'd look like.
The "solutions" which I brought up are not necessities by any means. I
don't need them. They're not solving problems; they just make my life
a bit more pleasant. They're not necessitated by the fact that the
code is too long or overstructured or any other so called problem
(aka, matter of personal taste, or in the vernacular, "religion," much
like vi vs. emacs).
It's not an argument against flatness, either. I was simply pointing
out some things that may rely on the tree representation of code, at
least in their current form. Your response was that these tools are
"symptoms of a problem" and "mostly useless anyway in most
concatenative languages." If that's your opinion on the value of the
sort of tools I mentioned, we really can't discuss how they would be
adapted to a flat language. Oh well...
> -Billy
--eiz
William Tanksley, Jr — 2005-08-02 22:18:30
Daniel Ehrenberg <
microdan@...> wrote:
> > The code is represented by a data structure. You use a compile-time
> > list. A list is a great way to gather concatenative code together, but
> > a very poor way to dissect and manipulate code -- you can do things
> > with lists that aren't sensible with code.
> What are you saying? That a language needs to restrict how people
> manipulate code?
No. I'm saying that code isn't a data structure. Perhaps I'm
misphrasing that; perhaps I should say something like "computations
aren't data structures". I can see that my origiinal phrasing was
misleading. The reason I say that is that every data structure we've
used to represent computations implies that you can manipulate the
data structure to determine things about the computation.
And that's just not true. Turing proved it -- the only general way to
know things about computations is to actually run them. Languages that
allow you to know the data structure used to represent a computation
automatically put limitations on the computation.
For example, Joy's documentation mentions that identities such as "dup
drop == nop" don't hold within quotations, because someone might use
the length of the quotation (list).
> It is very useful to have code be
> [represented by] an accessable data structure;
Agreed. When I said "code" I should have said "computations". When you
say "code" you're referring to the stuff that the programmer
manipulates in order to specify the computation.
> Lisp macros are a
> testimate to that, and Factor sometimes does similar things, though
> not as often.
Agreed. And Joy quotations as well -- very much so!
> Daniel Ehrenberg
-Billy
William Tanksley, Jr — 2005-08-03 00:38:36
Mackenzie Straight <
eizneckam@...> wrote:
> On 8/1/05, William Tanksley, Jr <wtanksleyjr@...> wrote:
> > No, it "is" not a quotation. Joy and Factor use quotations for it.
> > Forth doesn't define any data structure. It's easy to define an
> > improper subset of Forth, "flat Forth", that uses xts (which are
> > atoms) for the consequentials of conditionals.
> > Please don't confuse implementation with essence.
> I am well aware that Forth does not have quotations. Ask yourself
> this, though: what is the fundamental difference between a quotation
> and an xt? The answer is simple: xts are opaque, and can't really be
> manipulated. But aside from that they're basically the same thing.
> (Would an xt-forth qualify as 'flat'?)
Forth doesn't use xts for its conditionals, either. And yes, making it
impossible to manipulate an unexecuted computation accurately
represents the reality of a computation. The only operation that can
be performed in general on a computation is to execute it -- and of
course there's no guarantee that it'll halt.
> > > In the
> > > future, Factor is actually going to have a first class quotation type,
> > > and cons lists are going to have their role seriously reduced or
> > > eliminated, but that's beside the point. The point is that the code
> > > _is_ a data structure.
> > The code is represented by a data structure. You use a compile-time
> > list. A list is a great way to gather concatenative code together, but
> > a very poor way to dissect and manipulate code -- you can do things
> > with lists that aren't sensible with code.
> A very poor way to manipulate code? Lists have been working quite well
> for manipulating source code for the last 42 years. I've grown
> somewhat attached to the notion, myself.
I apologise -- the miscommunication is my fault. I wasn't referring to
source code; I was referring to computations. I'm not talking about
the ability for a program to build another program from parts; I'm
talking about the ability to pass a computation to an 'if' combinator
that will either execute it or drop it, and to know that the optimizer
will be able to optimize it the same as any other chunk of code in
your system.
> > I think your solutions are fair game -- you're the one bringing them
> > in as a telling argument against flatness, after all. I repeat: the
> > tools you use are only useful to overcome the problems of a different
> > type of code. With flat code, different tools would be needed. I
> > honestly don't know what they'd look like.
> The "solutions" which I brought up are not necessities by any means. I
> don't need them. They're not solving problems; they just make my life
> a bit more pleasant.
Enjoy, then. I guess that once flat programming takes the world by
storm you can freely load old, legacy, no-longer-used code into your
prettyprinters and so on and make your life as much more pleasant as
you want. :-) ;-)
I personally don't see any use to those things beyond dealing with the
complexities of code; and I know that there are many other ways of
dealing with the complexity. I'm not claiming, by the way, that my
ways are better; I am claiming that there will be other ways of
dealing with complexity, and they will work at least as well. So
unless you truly enjoy prettyprinters and structured editors for their
own sake, there's no need to bring them up in this discussion.
> It's not an argument against flatness, either.
My misunderstanding, then. I took it as such, since it was in a
paragraph of arguments against flatness.
> I was simply pointing
> out some things that may rely on the tree representation of code, at
> least in their current form.
That's true. All I can say, then, is that if you want to express your
code as a tree you still can. Flat languages are graphs, not trees;
but if the programmer wishes, he can confine his work to the shape of
a tree. I suspect that most of the time that'll give the best results,
actually (for that reason I'm not sure that flatness is ideal).
> Your response was that these tools are
> "symptoms of a problem" and "mostly useless anyway in most
> concatenative languages." If that's your opinion on the value of the
> sort of tools I mentioned, we really can't discuss how they would be
> adapted to a flat language. Oh well...
No, I don't believe they could be. Entirely new tools would have to be produced.
Prettyprinters are probably the smallest problem -- prettyprinters
force code to match conventions, and don't conceptually depend on
syntax. So all we have to do is decide what conventions we're going to
use... :-)
colorForth has no prettyprinters yet, and probably never will. I doubt
any would be needed.
I've seen Forth code that needed prettyprinting, and code that was
effectively impossible to prettyprint. I prefer the second.
> --eiz
-Billy
Daniel Ehrenberg — 2005-08-03 14:26:16
On 8/2/05, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> Daniel Ehrenberg <microdan@...> wrote:
> > > The code is represented by a data structure. You use a compile-time
> > > list. A list is a great way to gather concatenative code together, but
> > > a very poor way to dissect and manipulate code -- you can do things
> > > with lists that aren't sensible with code.
>
> > What are you saying? That a language needs to restrict how people
> > manipulate code?
>
> No. I'm saying that code isn't a data structure. Perhaps I'm
> misphrasing that; perhaps I should say something like "computations
> aren't data structures". I can see that my origiinal phrasing was
> misleading. The reason I say that is that every data structure we've
> used to represent computations implies that you can manipulate the
> data structure to determine things about the computation.
>
> And that's just not true. Turing proved it -- the only general way to
> know things about computations is to actually run them. Languages that
> allow you to know the data structure used to represent a computation
> automatically put limitations on the computation.
>
> For example, Joy's documentation mentions that identities such as "dup
> drop == nop" don't hold within quotations, because someone might use
> the length of the quotation (list).
>
...ok, but I don't really see any place for 100% abstract computations
in any programming language, and it's still extremely useful to have
code be a data structure. The quotation *is* a list, and there's
nothing you could say to make it not. It makes no sense to do length
the way you're picturing on quotations, though their length might be
needed to produce another quotation from them. Any optimizations that
the compiler might do, such as removing dup drop, should be done in a
way invisible to the user.
> > It is very useful to have code be
> > [represented by] an accessable data structure;
>
> Agreed. When I said "code" I should have said "computations". When you
> say "code" you're referring to the stuff that the programmer
> manipulates in order to specify the computation.
There are no computations. Computations are just a way of thinking
about what's actually happening, but they don't exist within the
language, as you've said would be impossible. So it's pretty useless
to talk about computations at all.
Daniel Ehrenberg
William Tanksley, Jr — 2005-08-04 00:39:25
Daniel Ehrenberg <
microdan@...> wrote:
> ...ok, but I don't really see any place for 100% abstract computations
> in any programming language,
The only purpose for using a programming language is to express
computations. I don't know what you mean by 100% abstract, though;
perhaps there's something there.
> and it's still extremely useful to have
> code be a data structure.
I believe I agreed with this -- it's useful when you explicitly want
to be able to manipulate the code before the computation it implies
needs to be run. The problem is that if this abilitity remains open to
*all* computations,
> The quotation *is* a list, and there's
> nothing you could say to make it not.
I wouldn't want to do something like that. Quotations are lists.
But I'm not talking about quotations. I'm talking about computations
-- the things you pass to an 'if', the things your source code
represents when it's being executed. Those aren't lists. You might say
they're sequences of machine-language operations, but that doesn't
provide a useful connection to the language for most programmers. You
could say that they're sequences of virtual operations, but that would
cripple performance. You could say that they're sequences of
characters, but that makes manipulating them hard and slow. And so
on...
> It makes no sense to do length
> the way you're picturing on quotations,
I thought you just said that they're lists. If so, it makes absolute
sense to do length on them.
> though their length might be
> needed to produce another quotation from them. Any optimizations that
> the compiler might do, such as removing dup drop, should be done in a
> way invisible to the user.
That's good to hope for. It's possible to come close if you've chosen
your abstraction well. Tcl chose its abstraction very poorly, and it
took them years to salvage their performance.
> > > It is very useful to have code be
> > > [represented by] an accessable data structure;
> > Agreed. When I said "code" I should have said "computations". When you
> > say "code" you're referring to the stuff that the programmer
> > manipulates in order to specify the computation.
> There are no computations. Computations are just a way of thinking
> about what's actually happening, but they don't exist within the
> language, as you've said would be impossible. So it's pretty useless
> to talk about computations at all.
I don't think both of us understand. (I'm not willing to promise that
even one of us understands. :-)
A computation is what you pass to 'if'. It's what the code that you
type into your editor represents. Deciding what you can do with a
computation is important. We both know that you can execute a
computation and destroy a computation (this seems to preclude your
claim that computations don't exist). I don't know what else you can
do with a computation. I suppose concatenating them makes sense; if a
computation is flat, splitting it makes sense too (but the definition
for "flat" may be different for computations than it is for
languages), but I don't know what you could do with the two halves.
Do you know anything else you can do with a computation?
> Daniel Ehrenberg
-Billy
Daniel Ehrenberg — 2005-08-04 02:49:44
On 8/3/05, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> Daniel Ehrenberg <microdan@...> wrote:
> > ...ok, but I don't really see any place for 100% abstract computations
> > in any programming language,
>
> The only purpose for using a programming language is to express
> computations. I don't know what you mean by 100% abstract, though;
> perhaps there's something there.
>
> > and it's still extremely useful to have
> > code be a data structure.
>
> I believe I agreed with this -- it's useful when you explicitly want
> to be able to manipulate the code before the computation it implies
> needs to be run. The problem is that if this abilitity remains open to
> *all* computations,
>
> > The quotation *is* a list, and there's
> > nothing you could say to make it not.
>
> I wouldn't want to do something like that. Quotations are lists.
>
> But I'm not talking about quotations. I'm talking about computations
> -- the things you pass to an 'if', the things your source code
> represents when it's being executed. Those aren't lists. You might say
> they're sequences of machine-language operations, but that doesn't
> provide a useful connection to the language for most programmers. You
> could say that they're sequences of virtual operations, but that would
> cripple performance. You could say that they're sequences of
> characters, but that makes manipulating them hard and slow. And so
> on...
>
> > It makes no sense to do length
> > the way you're picturing on quotations,
>
> I thought you just said that they're lists. If so, it makes absolute
> sense to do length on them.
>
> > though their length might be
> > needed to produce another quotation from them. Any optimizations that
> > the compiler might do, such as removing dup drop, should be done in a
> > way invisible to the user.
>
> That's good to hope for. It's possible to come close if you've chosen
> your abstraction well. Tcl chose its abstraction very poorly, and it
> took them years to salvage their performance.
>
> > > > It is very useful to have code be
> > > > [represented by] an accessable data structure;
>
> > > Agreed. When I said "code" I should have said "computations". When you
> > > say "code" you're referring to the stuff that the programmer
> > > manipulates in order to specify the computation.
>
> > There are no computations. Computations are just a way of thinking
> > about what's actually happening, but they don't exist within the
> > language, as you've said would be impossible. So it's pretty useless
> > to talk about computations at all.
>
> I don't think both of us understand. (I'm not willing to promise that
> even one of us understands. :-)
>
> A computation is what you pass to 'if'. It's what the code that you
> type into your editor represents. Deciding what you can do with a
> computation is important. We both know that you can execute a
> computation and destroy a computation (this seems to preclude your
> claim that computations don't exist). I don't know what else you can
> do with a computation. I suppose concatenating them makes sense; if a
> computation is flat, splitting it makes sense too (but the definition
> for "flat" may be different for computations than it is for
> languages), but I don't know what you could do with the two halves.
>
> Do you know anything else you can do with a computation?
>
> > Daniel Ehrenberg
>
> -Billy
Overall, I really don't understand where this idea of computations is
comming from. In some implementations, during runtime, it is still the
quotation, never at all anything else. A computation, as I understand
it, is a completely abstract concept. Could someone please define it
better for me?
William Tanksley, Jr — 2005-08-05 04:50:03
Daniel Ehrenberg <
microdan@...> wrote:
> William Tanksley, Jr <wtanksleyjr@...> wrote:
> > A computation is what you pass to 'if'. It's what the code that you
> > type into your editor represents. Deciding what you can do with a
> > computation is important. We both know that you can execute a
> Overall, I really don't understand where this idea of computations is
> comming from. In some implementations, during runtime, it is still the
> quotation, never at all anything else. A computation, as I understand
> it, is a completely abstract concept. Could someone please define it
> better for me?
Joy has two ways to express a computation. One example is a quotation,
the other is a function body. So it's not "never at all anything
else".
The concrete concept of "computation" is neccesary in order to compare
Forth and Joy's conditionals on equal terms, and in order to think
about the nature of a lazy concatenative language. If we only
understand "quotations", we'll only be able to work with Joy and
Factor, not Forth.
-Billy
Daniel Ehrenberg — 2005-08-05 14:59:23
> Joy has two ways to express a computation. One example is a quotation,
> the other is a function body. So it's not "never at all anything
> else".
>
> The concrete concept of "computation" is neccesary in order to compare
> Forth and Joy's conditionals on equal terms, and in order to think
> about the nature of a lazy concatenative language. If we only
> understand "quotations", we'll only be able to work with Joy and
> Factor, not Forth.
>
> -Billy
Hmm... ok, but what does that have to do with the abstract concept
you're talking about where [ dup drop ] is equivalent to [ nop ] ?
William Tanksley, Jr — 2005-08-06 01:57:15
Daniel Ehrenberg <
microdan@...> wrote:
> > Joy has two ways to express a computation. One example is a quotation,
> > the other is a function body. So it's not "never at all anything
> > else".
> > The concrete concept of "computation" is neccesary in order to compare
> > Forth and Joy's conditionals on equal terms, and in order to think
> > about the nature of a lazy concatenative language. If we only
> > understand "quotations", we'll only be able to work with Joy and
> > Factor, not Forth.
> Hmm... ok, but what does that have to do with the abstract concept
> you're talking about where [ dup drop ] is equivalent to [ nop ] ?
As a compuation, the two are the same. As quoted lists, they're
obviously not. So therefore, quoted lists are not the same as
computations. This doesn't mean that they _can't_ be used to implement
computations (although Forth in fact doesn't use them); it just means
that you should be careful about "leaky abstractions" when lists allow
you to do things that real computations don't allow.
-Billy
Daniel Ehrenberg — 2005-08-06 16:39:28
On 8/5/05, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> Daniel Ehrenberg <microdan@...> wrote:
> > > Joy has two ways to express a computation. One example is a quotation,
> > > the other is a function body. So it's not "never at all anything
> > > else".
>
> > > The concrete concept of "computation" is neccesary in order to compare
> > > Forth and Joy's conditionals on equal terms, and in order to think
> > > about the nature of a lazy concatenative language. If we only
> > > understand "quotations", we'll only be able to work with Joy and
> > > Factor, not Forth.
>
> > Hmm... ok, but what does that have to do with the abstract concept
> > you're talking about where [ dup drop ] is equivalent to [ nop ] ?
>
> As a compuation, the two are the same. As quoted lists, they're
> obviously not. So therefore, quoted lists are not the same as
> computations. This doesn't mean that they _can't_ be used to implement
> computations (although Forth in fact doesn't use them); it just means
> that you should be careful about "leaky abstractions" when lists allow
> you to do things that real computations don't allow.
>
> -Billy
You're using two different meanings of "computation". One is a body of
code, as you used for the Joy word/quotation thing, and another is the
abstract meaning of code. Could you define computation in a way that's
not just by example?
Daniel Ehrenberg
William Tanksley, Jr — 2005-08-06 19:34:01
Daniel Ehrenberg <
microdan@...> wrote:
> You're using two different meanings of "computation". One is a body of
> code, as you used for the Joy word/quotation thing, and another is the
> abstract meaning of code. Could you define computation in a way that's
> not just by example?
I'm not aware of using two different meanings; I changed from my old
and incorrect term "code" so that I could have a single meaning.
Computation as an idea is defined by compexity theory; as an object, a
computation should have an interface that allows you to do only the
things that you could do to a computation in the theoretical sense.
> Daniel Ehrenberg
-Billy
Daniel Ehrenberg — 2005-08-06 19:49:15
> I'm not aware of using two different meanings; I changed from my old
> and incorrect term "code" so that I could have a single meaning.
> Computation as an idea is defined by compexity theory; as an object, a
> computation should have an interface that allows you to do only the
> things that you could do to a computation in the theoretical sense.
So what does that have to do with the Joy thing you were talking about?
William Tanksley, Jr — 2005-08-06 20:12:38
Daniel Ehrenberg <
microdan@...> wrote:
> > I'm not aware of using two different meanings; I changed from my old
> > and incorrect term "code" so that I could have a single meaning.
> > Computation as an idea is defined by compexity theory; as an object, a
> > computation should have an interface that allows you to do only the
> > things that you could do to a computation in the theoretical sense.
> So what does that have to do with the Joy thing you were talking about?
What "Joy thing"? Sounds like a miscommunication. I wasn't addressing
anything in Joy. I did use Joy quotations as an example of how Joy
handles computations, and I explained a problem with that... But I
wasn't adressing Joy other than as a minor example.
What do you mean?
-Billy
Daniel Ehrenberg — 2005-08-06 21:40:40
Never mind. I don't really see this conversation going anywhere so I'm
going to end my part of it right here.
On 8/6/05, William Tanksley, Jr <wtanksleyjr@...> wrote:
> Daniel Ehrenberg <microdan@...> wrote:
> > > I'm not aware of using two different meanings; I changed from my old
> > > and incorrect term "code" so that I could have a single meaning.
> > > Computation as an idea is defined by compexity theory; as an object, a
> > > computation should have an interface that allows you to do only the
> > > things that you could do to a computation in the theoretical sense.
>
> > So what does that have to do with the Joy thing you were talking about?
>
> What "Joy thing"? Sounds like a miscommunication. I wasn't addressing
> anything in Joy. I did use Joy quotations as an example of how Joy
> handles computations, and I explained a problem with that... But I
> wasn't adressing Joy other than as a minor example.
>
> What do you mean?
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2005-08-06 23:38:11
Daniel Ehrenberg <
microdan@...> wrote:
> Never mind. I don't really see this conversation going anywhere so I'm
> going to end my part of it right here.
Okay. Thank you both for talking -- I apologize that I wasn't able to
answer your questions.
-Billy
Narcoleptic Electron — 2005-08-07 02:31:23
On 8/6/05, Daniel Ehrenberg <
microdan@...> wrote:
> Could you define computation in a way that's
> not just by example?
Sorry for carrying this on, but I am interested in knowing the
definition of a computation. This is fundamentally important. Here's
my stab at it...
Lexicographically, "computing" is something that a "computer" does. I
think we can all agree on that.
From here, I would define a computation as "a change from one internal
machine state to another". By this, it is possible for a computation
to be comprised of simpler computations.
Source code is a "description" of such a change of machine state, not
the change itself. It is used to generate the change it describes.
It is like thoughts (...computations) vs. language (...source code).
It is nonsensical to say that a thought can exist inside a language.
To convey a thought to another person, one can only *describe* the
thought using language, whereby the listening person will attempt to
recreate the thought from the description provided.
In this sense, I am programming all of you mailing list recipients
right now, and the message that you are reading is the source code. I
have indicated the initial machine state (the problem statement, and
what we can all agree on about this problem), and have provided a set
of translations (logical arguments) to take you to a final machine
state (the conclusion I have drawn). If I have done this 100%
correctly (which is nearly impossible, considering the complexity of
the state in question), you will all have reached the same conclusion
as me.
How did I do?
phimvt@lurac.latrobe.edu.au — 2005-08-08 03:01:50
On Sat, 6 Aug 2005, Narcoleptic Electron wrote:
I find myself in agreement with some but not all of the things you say.
First, here is what I came up with before seeing your definition.
The I shall comment on yours.
Computations happen at runtime. A computation begins at the start of a run
of a program, and it ends when then the run finishes. A computatation
starts with an initial state of the computing machine and it ends with a
final state. Even in the case where the program computes the identity
function ("noop"), the initial and the final state are different - its the
difference between "start" and "done". In between the initial state and
the final state a sequence of changes occurs. So, one way to think of a
computation is as a sequence of changes. A change is what occurs between
two successive states. So another way is to think of a computation is as
a sequence of states. The two views are entirely equivalent.
What counts as the state of the machine depends entirely on the chosen
level of description. The machine may be a virtual machine: the Joy
interpreter, the "inner interpreter" of Forth, the SECD machine of Lisp
the Pcode machine of Pascal, and so on. Or it may be the actual hardware,
at various possible levels of description. In just about all cases a
single step of a virtual machine is implemented as several steps of the
underlying machine. Indeed, there may be a whole tower of more and more
finegrained descriptions (virtual machines) down to the rock bottom.,
perhaps at the quantum level.
The sequence of changes and the sequence of states seem to bear an
interesting relation to the program. This will be especially true if the
program is written
in a concatenative language, which to a large part consists of sequences
of atomic programs. All three kinds of sequences can be concatenated
to form larger sequences. So, what is the relation between on the one
hand the program sequence and the changes/states sequences?
Clearly the closest correspondence should be expected for the
sequences of changes or states of the virtual machine.
Only in exceptional cases will there be a 1-1 correspondence, that will
only happen if the program has no conditionals, no loops, no calls of
defined functions. In all other cases there will only be short stretches
of correspondence between the program and the changes. The correspondence
will occur precisely at those stretches of program that are flat. Any such
stretch is of course mirrored by a stretch of correspondence between the
program and the states.
If concatenations of programs denote compositions of functions,
then do concatenations of sequences of changes denote anything similar?
Clearly not, they are not syntactic entities and hence do not
denote anything. A single change is just a pair of before/after states,
and a sequence of n changes is just a sequence of (n+1) states.
Also, there is a many-to-one correspondence between the functions
denoted by programs and the changes. For, consider the change of
an internal variable from -3 to +3. This could be due to a program
that takes the absolute value, or a program that adds 6, or a program
that doubles negative numbers and then adds 9, or by ...
But I must stop and discuss your contribution.
> On 8/6/05, Daniel Ehrenberg <microdan@...> wrote:
> > Could you define computation in a way that's
> > not just by example?
>
> Sorry for carrying this on, but I am interested in knowing the
> definition of a computation. This is fundamentally important. Here's
> my stab at it...
>
> Lexicographically, "computing" is something that a "computer" does. I
> think we can all agree on that.
That is taking "lexicographically" in the normal (not computerese)
sense, yes.
> From here, I would define a computation as "a change from one internal
> machine state to another". By this, it is possible for a computation
> to be comprised of simpler computations.
The tower of virtual machines, yes.
> Source code is a "description" of such a change of machine state, not
> the change itself. It is used to generate the change it describes.
Entirely agree so far.
> It is like thoughts (...computations)
Yes
> vs. language (...source code).
I don't follow at all. But you really mean source code (written, of
course, in some language).
> It is nonsensical to say that a thought can exist inside a language.
Nor can a thought exist inside an utterance in a language.
> To convey a thought to another person, one can only *describe* the
> thought using language, whereby the listening person will attempt to
> recreate the thought from the description provided.
And the description is an utterance (spoken of written) in a language.
Different descriptions (programs in your analogy) can lead to the
same thought (final state of the computation). Yes. For example
writers of textbooks attempt to write better descriptions of
thought processes than those written by the original authors.
> In this sense, I am programming all of you mailing list recipients
> right now, and the message that you are reading is the source code. I
> have indicated the initial machine state (the problem statement, and
> what we can all agree on about this problem), and have provided a set
> of translations (logical arguments) to take you to a final machine
> state (the conclusion I have drawn). If I have done this 100%
> correctly (which is nearly impossible, considering the complexity of
> the state in question), you will all have reached the same conclusion
> as me.
>
> How did I do?
Pretty well, I think. Some nice and interesting thoughts.
- Manfred
Narcoleptic Electron — 2005-08-08 04:51:31
On 8/7/05,
phimvt@... <
phimvt@...> wrote:
> Computations happen at runtime.
Yes. This includes "run time of a compiler".
I agree with the rest of what you wrote. Well said.
> On Sat, 6 Aug 2005, Narcoleptic Electron wrote:
> > It is like thoughts (...computations)
>
> Yes
>
> > vs. language (...source code).
>
> I don't follow at all. But you really mean source code (written, of
> course, in some language).
My mistake. I added the parenthetical translations as an afterthought
and, as should be expected, they are incorrect. The metaphor should
be: human thought = machine computation, human language = programming
language, utterance in human language = source code.
> > It is nonsensical to say that a thought can exist inside a language.
>
> Nor can a thought exist inside an utterance in a language.
Indeed. This is what I meant to write...
> Some nice and interesting thoughts.
Thank you. It looks like we are on the same track, minus my
"programming errors". Thanks for helping to debug my email message.
> - Manfred
N. Electron
Ivan Tomac — 2005-08-10 15:03:47
I'm a bit late to join this discussion but I'm starting to like the
idea of flat languages. If nothing else I think it's worth exploring
them further until we can say for sure whether their advantages
outweigh the disadvantages.
I have a few questions though. They may have already been answered
(I've tried to read all the posts on topic so far but there are just
so many! I'm sure I missed some things) so I apologize in advance if
that's the case.
If I remember it right you mentioned in one of the posts (can't find
it right now, otherwise I'd quote it) that the main (only?) things
that prevent Joy from being flat are it's definitions and blocks. The
problem with definitions is easy enough to solve which leaves only
code blocks. How do you get around that problem? How do you flatten
quotations?
Do you simply treat them as atomic values so that no quotation can
ever be split into smaller quotations? Or is there more to it then
that? What else is neccesary in order for a language to be truly flat?
--- In
concatenative@yahoogroups.com, "William Tanksley, Jr"
<wtanksleyjr@g...> wrote:
> > I was simply pointing
> > out some things that may rely on the tree representation of code,
at
> > least in their current form.
>
> That's true. All I can say, then, is that if you want to express
your
> code as a tree you still can. Flat languages are graphs, not trees;
> but if the programmer wishes, he can confine his work to the shape
of
> a tree.
This part confused me a bit - how is the code in a flat language a
graph?
> -Billy
Ivan
Narcoleptic Electron — 2005-08-10 15:55:18
On 8/10/05, Ivan Tomac <
e1_t@...> wrote:
> How do you flatten quotations?
> Do you simply treat them as atomic values so that no quotation can
> ever be split into smaller quotations? Or is there more to it then
> that? What else is neccesary in order for a language to be truly flat?
A short answer:
String literals.
A long answer:
In a flat language that I've been developing for a while now (no
website yet... no time), the only literal in the language is a string,
which is indicated by enclosing square brackets (i.e. [I'm a string
literal.]). Nesting is allowed (i.e. [[inner1] [inner2]] pushes the
string "[inner1] [inner2]", not including the double quotes), and
unbalanced brackets must be escaped.
A string literal means "push the string value described herein onto
the stack". If the literal is followed by whitespace, this means
"treat the string on the stack as a name, and replace it with its
defined value".
Thus:
[2][#] [3][#] [+]
-> Push string "2", push string "#", replace "#" with program and
execute (replacing "2" on stack with numeric value for 2), etc.
Results in only the numeric value 5 on the stack.
There are no numeric or quotation literals; just string literals. All
data values start as string values on the stack, which then converted
to various value types by different programs (such as "#", which
converts a string to a number).
(Even comments are handled this way: [This is a comment.][comment]
puts the comment string on the stack, then drops it.)
Note that a defined name can literally have any character, including
spaces. For example, the identity program is bound to an empty string
(i.e. []), which allows the following:
[string 1][] [string 2][]
-> Leaves "string 1" and "string 2" values on the stack.
A quotation would be as follows:
[[2][#] [3][#] [+]][code]
-> Pushes the quotation string onto the stack, then calls "code" which
converts the string to code and evaluates. (I haven't settled on my
names yet, but you get the idea.)
When quotations are handled as strings, they can be split up any which way.
(As far as my language syntax goes: that's all there is. The only
"special characters" used by the parser are "[", "]" and whitespace.)
Sorry if I've taken this too far off-topic: I just wanted to
illustrate what my solution to this has been. I've been interested in
flatness for quite some time.
sa@dfa.com — 2005-08-10 16:01:26
well that's certainly clever.
i'd like to hear more details about '#' and 'code'.
concatenative@yahoogroups.com wrote on 08/10/2005 11:55:18 AM:
> On 8/10/05, Ivan Tomac <e1_t@...> wrote:
> > How do you flatten quotations?
> > Do you simply treat them as atomic values so that no quotation can
> > ever be split into smaller quotations? Or is there more to it then
> > that? What else is neccesary in order for a language to be truly flat?
>
> A short answer:
>
> String literals.
>
> A long answer:
>
> In a flat language that I've been developing for a while now (no
> website yet... no time), the only literal in the language is a string,
> which is indicated by enclosing square brackets (i.e. [I'm a string
> literal.]). Nesting is allowed (i.e. [[inner1] [inner2]] pushes the
> string "[inner1] [inner2]", not including the double quotes), and
> unbalanced brackets must be escaped.
>
> A string literal means "push the string value described herein onto
> the stack". If the literal is followed by whitespace, this means
> "treat the string on the stack as a name, and replace it with its
> defined value".
>
> Thus:
>
> [2][#] [3][#] [+]
> -> Push string "2", push string "#", replace "#" with program and
> execute (replacing "2" on stack with numeric value for 2), etc.
> Results in only the numeric value 5 on the stack.
>
> There are no numeric or quotation literals; just string literals. All
> data values start as string values on the stack, which then converted
> to various value types by different programs (such as "#", which
> converts a string to a number).
>
> (Even comments are handled this way: [This is a comment.][comment]
> puts the comment string on the stack, then drops it.)
>
> Note that a defined name can literally have any character, including
> spaces. For example, the identity program is bound to an empty string
> (i.e. []), which allows the following:
>
> [string 1][] [string 2][]
> -> Leaves "string 1" and "string 2" values on the stack.
>
> A quotation would be as follows:
>
> [[2][#] [3][#] [+]][code]
> -> Pushes the quotation string onto the stack, then calls "code" which
> converts the string to code and evaluates. (I haven't settled on my
> names yet, but you get the idea.)
>
> When quotations are handled as strings, they can be split up any which
way.
>
> (As far as my language syntax goes: that's all there is. The only
> "special characters" used by the parser are "[", "]" and whitespace.)
>
> Sorry if I've taken this too far off-topic: I just wanted to
> illustrate what my solution to this has been. I've been interested in
> flatness for quite some time.
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
Narcoleptic Electron — 2005-08-10 16:01:31
I wrote:
> On 8/10/05, Ivan Tomac <e1_t@...> wrote:
> > How do you flatten quotations?
> > Do you simply treat them as atomic values so that no quotation can
> > ever be split into smaller quotations? Or is there more to it then
> > that? What else is neccesary in order for a language to be truly flat?
>
> A short answer:
>
> String literals.
PS: I realize that this isn't *absolutely* flat, because string
enclosures must be balanced, but I think that this is as flat as we
could get before sinking into a turing tarpit.
John.Cowan — 2005-08-10 16:05:53
Narcoleptic Electron scripsit:
> > String literals.
>
> PS: I realize that this isn't *absolutely* flat, because string
> enclosures must be balanced, but I think that this is as flat as we
> could get before sinking into a turing tarpit.
I think it's just as flat as Joy or Forth, no more, no less.
--
John Cowan
jcowan@... www.reutershealth.com www.ccil.org/~cowan
Rather than making ill-conceived suggestions for improvement based on
uninformed guesses about established conventions in a field of study with
which familiarity is limited, it is sometimes better to stick to merely
observing the usage and listening to the explanations offered, inserting
only questions as needed to fill in gaps in understanding. --Peter Constable
Narcoleptic Electron — 2005-08-10 16:14:45
On 8/10/05, John.Cowan <
cowan@...> wrote:
> Narcoleptic Electron scripsit:
>
> > > String literals.
> >
> > PS: I realize that this isn't *absolutely* flat, because string
> > enclosures must be balanced, but I think that this is as flat as we
> > could get before sinking into a turing tarpit.
>
> I think it's just as flat as Joy or Forth, no more, no less.
No: Joy has list literals and string literals. My language removes
list literals, making it a bit more flat.
Narcoleptic Electron — 2005-08-10 16:24:59
On 8/10/05,
sa@... <
sa@...> wrote:
> well that's certainly clever.
Thanks. Your shoulders are two of many that I have been perched on in
thinking it up...
> i'd like to hear more details about '#' and 'code'.
"#" and "code" are just names of programs.
For the following code:
[42][#]
The following happens:
- The string "42" is pushed onto the stack.
- The string "#" is pushed onto the stack.
- The string "#" is popped and looked up in the dictionary. The value
it is bound to is pushed onto the stack; in this case a program that
converts text to numbers.
- The program on the top of the stack is executed, which in this case
pops the string "42" below it and pushes its numerical equivalent.
"code" is the program that parses and evaluates code.
I will try to get my act together and put up a website to explain
further about how programs are defined, etc., as well as actually
implementing some of this stuff in a fashion usable to others...
John.Cowan — 2005-08-10 16:34:51
Narcoleptic Electron scripsit:
> No: Joy has list literals and string literals. My language removes
> list literals, making it a bit more flat.
It would be trivial to write a string->list word in Joy making list literals
unnecessary.
--
What asininity could I have uttered John Cowan <
jcowan@...>
that they applaud me thus?
http://www.reutershealth.com
--Phocion, Greek orator
http://www.ccil.org/~cowan
Narcoleptic Electron — 2005-08-10 16:41:46
Addendum:
On 8/10/05, Narcoleptic Electron <narcoleptic.electron@...> wrote:
> For the following code:
>
> [42][#]
>
> The following happens:
> - The string "42" is pushed onto the stack.
> - The string "#" is pushed onto the stack.
> - The string "#" is popped and looked up in the dictionary. The value
> it is bound to is pushed onto the stack; in this case a program that
> converts text to numbers.
The above step happens because whitespace is reached. When whitespace
is encountered after a string literal, the string at the top of the
stack (pushed there by the literal) is treated as a name and gets the
"lookup and replace" treatment.
[#][#] would try to convert the string "#" to a number, which would of
course fail.
[#][#][] would push two strings containing the character "#" onto the
stack, and not do anything else with them. (The [] program leaves the
stack unchanged.)
> - The program on the top of the stack is executed, which in this case
> pops the string "42" below it and pushes its numerical equivalent.
Narcoleptic Electron — 2005-08-10 16:54:22
On 8/10/05, John.Cowan <
cowan@...> wrote:
> It would be trivial to write a string->list word in Joy making list literals
> unnecessary.
Yes. I was attempting to illustrate the flattest possible non-tarpit
language for the sake of discussion. You're right: there is a
flatter subset of Joy.
However, not all non-flat parts of Joy can be removed this way.
Definitions in Joy are not flat, whereas they are in my language
(which I really should name). Explaining the details might be a
little much for this thread, but I can give more info if anyone wants
it.
Ivan Tomac — 2005-08-10 16:59:21
--- In
concatenative@yahoogroups.com, Narcoleptic Electron
<narcoleptic.electron@g...> wrote:
> On 8/10/05, John.Cowan <cowan@c...> wrote:
> > Narcoleptic Electron scripsit:
> >
> > > > String literals.
> > >
> > > PS: I realize that this isn't *absolutely* flat, because string
> > > enclosures must be balanced, but I think that this is as flat
as we
> > > could get before sinking into a turing tarpit.
> >
> > I think it's just as flat as Joy or Forth, no more, no less.
>
> No: Joy has list literals and string literals. My language removes
> list literals, making it a bit more flat.
Why does that make the language more flat.
I would think it would be more worthwhile to explore flatness from a
slightly higher level and still have strings and lists and integers
but add functions or code blocks or computations, whatever you want to
call them, as atoms that cannot be decomposed. Only executed,
concatenated or destroyed as Billy suggested.
I'm not sure if I completely misunderstood the concept of flatness
however. It's almost 3am here and my brain is shutting down :)
I think I'll have to re-read the whole thread from the beginning some
time this week..
Ivan
Narcoleptic Electron — 2005-08-10 17:17:09
On 8/10/05, Ivan Tomac <
e1_t@...> wrote:
> --- In concatenative@yahoogroups.com, Narcoleptic Electron
> <narcoleptic.electron@g...> wrote:
> > No: Joy has list literals and string literals. My language removes
> > list literals, making it a bit more flat.
>
> Why does that make the language more flat.
>
> I would think it would be more worthwhile to explore flatness from a
> slightly higher level and still have strings and lists and integers
> but add functions or code blocks or computations, whatever you want to
> call them, as atoms that cannot be decomposed. Only executed,
> concatenated or destroyed as Billy suggested.
> I'm not sure if I completely misunderstood the concept of flatness
> however. It's almost 3am here and my brain is shutting down :)
As I recall, the scenario that started this discussion was that of
breaking up a quotation literal, binding each half to a different
name, and reconstituting it later. That's the type of flatness [I
think] we're talking about.
"Code blocks" and "computations" are very different things. Code
block = quotation; computation = internal machine state change. The
former can exist in source code; the latter can't. A quotation
describes a computation.
Martin Young — 2005-08-10 20:22:18
I've only been half following this discussion - apologies if I've
got the wrong end of the stick. I was just doing a little bit of on-
paper doodling and came up with the following idea:
The execution system has two stacks: a data stack, and a dip stack.
These are initially empty.
It also has a stack/queue of incoming symbols - the program.
Initially the program queue contains the program as a series of
atoms (symbols or numbers). Symbols are removed from the program
stack and "executed" the discarded.
There are no lists, strings, tuples or suchlike in the language.
I've described the dip stack in previous posts to this list
concerning how a Joy-like language, MONKEY, operates. In short, it
moves the state storage associated with a dip out of the execution
system and into the language's domain. The atom "move" moves the
top value from the data stack on the dip stack. The atom "unmove"
does the converse. All the iterative and recursive conbinators can
be constructed on top of the data/dip stack thus moving things like
recursion state and mechanics into the langugage's domain.
The addition of two new operators, snatch and unsnatch may make the
language flat.
"snatch" takes one integer value (N) from the data stack then
arranges for the next N symbols from the program queue to be
conbined into an opaque Lump and pushed onto the dip
stack. "unsnatch" pulls one Lump from the snatch stack and pushes
its content onto the front of the program queue. Their presence on
the dip stack means that suitably polymorphic symbols such as swap
and dip can maniplate Lumps but they, the Lumps, cannot be
decomposed.
The structure previously offered by quotations (i.e. the ability to
manipulate pieces of program as entities) is replaced by the snatch
functionality. The key change is that the program's logical
structure exists (and can be changed) at runtime, but not in the
source code. That is, it is flat.
I've been trying to build an example. I started with a program
which prints the first N fibonaci numbers. One way of writing it is
as two words (in MONKEY syntax).
fibstep ==
{{
dup
{ + } dip
swap
dup .
}}
nfib ==
{{
1 . 1 .
{ 1 1 { fibstep } } dip
repeat
drop drop
}}
I've started by converting fibstep into flat MONKEY:
dup 1 snatch + move unsnatch swap dup .
I think this works. Sorry about the lack of formatting. Not sure
how to format source code that has no internal structure...
I'm currently puzzling over how to write the "repeat" word, but I
thought I'd post this before I discover that it's impossible...
--- In
concatenative@yahoogroups.com, Narcoleptic Electron
<narcoleptic.electron@g...> wrote:
> As I recall, the scenario that started this discussion was that of
> breaking up a quotation literal, binding each half to a different
> name, and reconstituting it later. That's the type of flatness [I
> think] we're talking about.
>
> "Code blocks" and "computations" are very different things. Code
> block = quotation; computation = internal machine state change.
The
> former can exist in source code; the latter can't. A quotation
> describes a computation.
Ivan Tomac — 2005-08-11 01:33:06
--- In
concatenative@yahoogroups.com, Narcoleptic Electron
<narcoleptic.electron@g...> wrote:
> On 8/10/05, Ivan Tomac <e1_t@y...> wrote:
> > --- In concatenative@yahoogroups.com, Narcoleptic Electron
> > <narcoleptic.electron@g...> wrote:
> > > No: Joy has list literals and string literals. My language
removes
> > > list literals, making it a bit more flat.
> >
> > Why does that make the language more flat.
> >
> > I would think it would be more worthwhile to explore flatness
from a
> > slightly higher level and still have strings and lists and
integers
> > but add functions or code blocks or computations, whatever you
want to
> > call them, as atoms that cannot be decomposed. Only executed,
> > concatenated or destroyed as Billy suggested.
> > I'm not sure if I completely misunderstood the concept of flatness
> > however. It's almost 3am here and my brain is shutting down :)
>
> As I recall, the scenario that started this discussion was that of
> breaking up a quotation literal, binding each half to a different
> name, and reconstituting it later. That's the type of flatness [I
> think] we're talking about.
>
> "Code blocks" and "computations" are very different things. Code
> block = quotation; computation = internal machine state change. The
> former can exist in source code; the latter can't. A quotation
> describes a computation.
You missed my point. It doesn't matter what it's called as long as the
language has functions you can pass around on stack and manipulate.
But something that's more limited then quotations in Joy - rather then
have quotations that are at the same time both lists and code, have 2
different types, one for lists and one for code. The latter can only
be executed, duplicated, concatenated, shuffled or destroyed. It
cannot be split.
What I'm asking is is this enough for a language to be flat?
I've just re-read some of the early posts on the topic and the
following definition (along with the posts about flatForth) got me
thinking:
"William Tanksley, Jr" <wtanksleyjr@g...> wrote:
>Flat: Flatness is the absence of all syntactic (compile-time)
>nesting.
>A test for flatness: a definition is flat if and only if it can
>be cut apart into two valid definitions on any blank space. A
>definition is partially flat to the extent that it can be so
>cut. This could be expressed numericly, by dividing the number
>of cuttable spaces by the total number of spaces.
I think I understand now what Billy meant by saying that a flat
language is a graph rather then a tree.
I'm not sure whether it answers my question though. If you have a type
of code blocks or functions and if each code block is an atom then
doesn't that make the language flat regardless of whether a function
in such a language has nesting or not? Why am I asking that? Because
if each code block is an atom then [1 dup 2 * drop] and [1 dup drop]
and [1] are all equivalent and if one of those is nested inside
another code block it can be replaced by a reference to an existing
code block so you can still get a graph structure as opposed to a
tree.
Narcoleptic Electron — 2005-08-11 18:04:07
On 8/10/05, Ivan Tomac <
e1_t@...> wrote:
> If you have a type
> of code blocks or functions and if each code block is an atom then
> doesn't that make the language flat regardless of whether a function
> in such a language has nesting or not? Why am I asking that? Because
> if each code block is an atom then [1 dup 2 * drop] and [1 dup drop]
> and [1] are all equivalent and if one of those is nested inside
> another code block it can be replaced by a reference to an existing
> code block so you can still get a graph structure as opposed to a
> tree.
This won't work because the only way to determine equivalence of two
computations is to perform the computations. So there is no way to do
the pre-execution optimization you describe, wherein [1 dup drop] and
[1] are replaced with references to the same computation object.
(Maybe I'm misunderstanding you...)
Narcoleptic Electron — 2005-08-11 18:06:58
Oops...
On 8/11/05, Narcoleptic Electron <narcoleptic.electron@...> wrote:
> On 8/10/05, Ivan Tomac <e1_t@...> wrote:
> > If you have a type
> > of code blocks or functions and if each code block is an atom then
> > doesn't that make the language flat regardless of whether a function
> > in such a language has nesting or not? Why am I asking that? Because
> > if each code block is an atom then [1 dup 2 * drop] and [1 dup drop]
> > and [1] are all equivalent and if one of those is nested inside
> > another code block it can be replaced by a reference to an existing
> > code block so you can still get a graph structure as opposed to a
> > tree.
>
> This won't work because the only way to determine equivalence of two
> computations is to perform the computations. So there is no way to do
> the pre-execution optimization you describe, wherein [1 dup drop] and
> [1] are replaced with references to the same computation object.
Sorry: replace "computation object" above with "quotation".
More explanation: because a computation is a change of machine state,
the only way to determine if two pieces of code will result in the
same computation (i.e. machine state delta) is to do each computation
and compare the resulting machine state of each.
Narcoleptic Electron — 2005-08-11 18:24:03
On 8/10/05, Martin Young <
martin@...> wrote:
> The execution system has two stacks: a data stack, and a dip stack.
> These are initially empty.
I like the idea of making everything in the language explicit; eg.
creating the dip stack to remove the magic of the "dip" program. This
is similar to XY, but taken a step further.
> fibstep ==
> {{
> dup
> { + } dip
> swap
> dup .
> }}
>
> nfib ==
> {{
> 1 . 1 .
> { 1 1 { fibstep } } dip
> repeat
> drop drop
> }}
>
> I've started by converting fibstep into flat MONKEY:
>
> dup 1 snatch + move unsnatch swap dup .
This type of solution has been discussed before (instead of
parentheses, specifying the number of programs to "read ahead" and
stick into a quotation). Sorry I can't find it at the moment. You
may be the first to have implemented this idea, though. (Although XY
might have something similar?)
One question: is there an easy way to create a string in your language?
Martin Young — 2005-08-11 21:10:38
--- In
concatenative@yahoogroups.com, Narcoleptic Electron
<narcoleptic.electron@g...> wrote:
> On 8/10/05, Martin Young <martin@e...> wrote:
> > The execution system has two stacks: a data stack, and a dip
stack.
> > These are initially empty.
>
> I like the idea of making everything in the language explicit; eg.
> creating the dip stack to remove the magic of the "dip" program.
This
> is similar to XY, but taken a step further.
It also removes the magic of recursion and itteration - everything
this is built from move and unmove primitives - it's analogous to
explicit continuation manipulation. For example, this post
<
http://groups.yahoo.com/group/concatenative/message/2122> shows an
implementation of linrec.
> This type of solution has been discussed before (instead of
> parentheses, specifying the number of programs to "read ahead" and
> stick into a quotation). Sorry I can't find it at the moment. You
> may be the first to have implemented this idea, though. (Although
XY
> might have something similar?)
Ah, sorry, missed that. As I said I haven't really been paying
attention. I saw some bits in a similar vein and assumed they were
parse-time constructs. Snatch and unsnatch are runtime (i.e. the
program can construct new, parameterised length snatches on the fly).
> One question: is there an easy way to create a string in your
language?
Normally MONKEY uses lists of integers as atrings. The parser has
syntactic sugar for strings whereby text inbetween double quotes is
converted into a list. E.g. "abcde" in the source would be
converted into the list literal [ 97 98 99 100 101 ] at parse time.
Flat MONKEY could do he same but converting into e.g "5 snatch 97 98
99 100 101" instead. A string would thus be opaque until it's
unsnatched whereupon its execution would cause its conponent
characters to appear on the data stack.
To be honest, I'm unconvinced that snatching (or read-ahead) is very
useful. ISTM, it makes programs even harder to write and optimise
that normal.
stevan apter — 2005-08-11 21:57:07
----- Original Message -----
From: "Martin Young" <martin@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, August 11, 2005 5:10 PM
Subject: [stack] Re: an exchange on flatness
--- In concatenative@yahoogroups.com, Narcoleptic Electron
<narcoleptic.electron@g...> wrote:
> On 8/10/05, Martin Young <martin@e...> wrote:
> > The execution system has two stacks: a data stack, and a dip
stack.
> > These are initially empty.
>
> I like the idea of making everything in the language explicit; eg.
> creating the dip stack to remove the magic of the "dip" program.
This
> is similar to XY, but taken a step further.
It also removes the magic of recursion and itteration - everything
this is built from move and unmove primitives - it's analogous to
explicit continuation manipulation. For example, this post
<http://groups.yahoo.com/group/concatenative/message/2122> shows an
implementation of linrec.
--------------
a few of joy's combinators in XY:
; i / ;
; x dup i ;
; b { [p q] p i q i } ;
; y [dup cons] swap , dup cons i ;
; cleave { [x p q] x p i x q i } ;
; construct { [p P] } ;
; slip => / <= ;
; 2slip => => / <= <= ;
; dip swap slip ;
; 2dip -rot 2slip ;
; ifte { [c t e] [e t] _x c infra* true? @ i } ;
; if pair swap zero? @ i ;
; branch [] if ;
; cond { [a] a #: 1 = [a *: i] [_x <- a cond.] if } ;
; cond. { [[[b T] A]] b T [A cond] ifte } ;
; infra { [a p] a @: [a p i] [S/ a <- p i S\] if } ;
; infra* infra |: *: ;
; unary { [n p] G\ n -: #. p map _x n -: _. swap , <- } ;
; map [jump] [each* rot => map <= swons] [pop] ifte ;
; each* => uncons <= tuck 2slip ;
; filter { [a p] a p map &: a @. } ;
; split { [a p] a p map dup ~: pair a swap [&: @] each/ i } ;
; some? { [a p] a p map 1 swap _in } ;
; all? { [a p] a p map 0 swap _in ~: } ;
; step { [a p] a [a uncons p dip p _z] branch } ;
; fold [swap] dip step ;
; fold! { [a s p] S/ a s p fold!. S\ } ;
; fold!. { [a s p] a [s 1 a _ s a *: p i p _z] [s] if } ;
; linrec { [c t r s] c i c t r s _x linrec. } ;
; linrec. { [b c t r s x] x <- b t [r i c t r s linrec s i] if } ;
; tailrec [] linrec ;
; binrec { [p t r s] p i p t r s _x binrec. } ;
; binrec. { [b p t r s x] x <- b t [r i p t r s binrec.. s i] if } ;
; binrec.. { [a b p t r s] a p t r s binrec b p t r s binrec } ;
; genrec { [p t r s] p i p t r s _x genrec. } ;
; genrec. { [b p t r s x] x <- b t [r i p t r s genrec s i] if } ;
; primrec { [n p c] p i 1 n 1 + c primrec. } ;
; primrec. { [k n c] k n = [] [k c i k 1 + n c _z] if } ;
; primrec- [zero?] -rot swap [pop] swap , swap [dup pred] swap linrec ;
see http://www.nsl.com/k/xy/xy.htm for details
> This type of solution has been discussed before (instead of
> parentheses, specifying the number of programs to "read ahead" and
> stick into a quotation). Sorry I can't find it at the moment. You
> may be the first to have implemented this idea, though. (Although
XY
> might have something similar?)
Ah, sorry, missed that. As I said I haven't really been paying
attention. I saw some bits in a similar vein and assumed they were
parse-time constructs. Snatch and unsnatch are runtime (i.e. the
program can construct new, parameterised length snatches on the fly).
> One question: is there an easy way to create a string in your
language?
Normally MONKEY uses lists of integers as atrings. The parser has
syntactic sugar for strings whereby text inbetween double quotes is
converted into a list. E.g. "abcde" in the source would be
converted into the list literal [ 97 98 99 100 101 ] at parse time.
Flat MONKEY could do he same but converting into e.g "5 snatch 97 98
99 100 101" instead. A string would thus be opaque until it's
unsnatched whereupon its execution would cause its conponent
characters to appear on the data stack.
To be honest, I'm unconvinced that snatching (or read-ahead) is very
useful. ISTM, it makes programs even harder to write and optimise
that normal.
Yahoo! Groups Links
Martin Young — 2005-08-11 22:06:54
Stevan,
I notice that your recursive combinators are still explicitly
recursive
themselves. E.g.
> ; linrec { [c t r s] c i c t r s _x linrec. } ;
> ; linrec. { [b c t r s x] x <- b t [r i c t r s linrec s i]
if } ;
With MONKEY I set out to remove all such explicit recursion from the
base language. That is, the only way to perform recursion is with
the recursive combinations where are, in turn, built on non-
recursive primitives. This is what I meant about removing the magic
of recursion (borrowing Narcoleptic's words).
I had an idea that this would make the language more amenable to
optimisation and compilation. I don't have a good theoretical basis
for this other than a very little experience.
-Martin.
stevan apter — 2005-08-11 23:30:20
----- Original Message -----
From: "Martin Young" <martin@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, August 11, 2005 6:06 PM
Subject: [stack] Re: an exchange on flatness
Stevan,
I notice that your recursive combinators are still explicitly
recursive
themselves. E.g.
> ; linrec { [c t r s] c i c t r s _x linrec. } ;
> ; linrec. { [b c t r s x] x <- b t [r i c t r s linrec s i] if } ;
---------
the recursion is an illusion. in XY, invocation of
a defined word causes the definition to be pushed onto
the queue. is this very different from the use of
the 'repeat' word in your definition of linrec?
---------
With MONKEY I set out to remove all such explicit recursion from the
base language. That is, the only way to perform recursion is with
the recursive combinations where are, in turn, built on non-
recursive primitives. This is what I meant about removing the magic
of recursion (borrowing Narcoleptic's words).
I had an idea that this would make the language more amenable to
optimisation and compilation. I don't have a good theoretical basis
for this other than a very little experience.
-Martin.
Yahoo! Groups Links
Martin Young — 2005-08-11 23:43:55
--- In
concatenative@yahoogroups.com, "stevan apter" <sa@n...> wrote:
> the recursion is an illusion. in XY, invocation of
> a defined word causes the definition to be pushed onto
> the queue. is this very different from the use of
> the 'repeat' word in your definition of linrec?
In that sense, isn't all explicit recursion an illusion? No sane
execution system actually tries to expand explicit recursion prior
to execution; the expansion of the recursive invocation is always
lazy. Not least because the expansion is non-computable.
I think MONKEY is (slightly) different because "repeat" is also
defined in terms of move and unmove. All recursive and itterative
combinators are built on top of the "pcon" word defined thusly:
pcon ==
{{
{ dip swapdup { swapif } dip unmove swap { dup unmove swap move swap
move move 0 } if drop }
cons cons
dup move move
}}
Not pretty, I grant you, and not quick to execute.
The upside is that it becomes possible to fully expand every
definition in a program; something that can't be done with
explicitly recursive definitions, as noted above. I /think/ this is
useful.
stevan apter — 2005-08-12 00:48:40
----- Original Message -----
From: "Martin Young" <martin@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, August 11, 2005 7:43 PM
Subject: [stack] Re: an exchange on flatness
> --- In concatenative@yahoogroups.com, "stevan apter" <sa@n...> wrote:
> > the recursion is an illusion. in XY, invocation of
> > a defined word causes the definition to be pushed onto
> > the queue. is this very different from the use of
> > the 'repeat' word in your definition of linrec?
>
> In that sense, isn't all explicit recursion an illusion? No sane
> execution system actually tries to expand explicit recursion prior
> to execution; the expansion of the recursive invocation is always
> lazy. Not least because the expansion is non-computable.
>
> I think MONKEY is (slightly) different because "repeat" is also
> defined in terms of move and unmove. All recursive and itterative
> combinators are built on top of the "pcon" word defined thusly:
>
> pcon ==
> {{
> { dip swapdup { swapif } dip unmove swap { dup unmove swap move swap
> move move 0 } if drop }
> cons cons
> dup move move
> }}
>
> Not pretty, I grant you, and not quick to execute.
but of course that's not important (the performance, i mean.)
i'm wondering how monkey (the unflat version) maps to XY, which also
uses a result stack X and an input queue Y and has the primitives:
-> queue [X^z Y] -> [X z]
<- stack [X^z Y] -> [z Y]
=> cache [X^z Y] -> [X Y^z]
<= uncache [X Y^z] -> [X^z Y]
/ use [X^z Y] -> [X z,Y]
\ mention [X z^Y] -> [X^z Y]
( stack* [X Y] -> [X^[X] Y]
) queue* [X Y] -> [X^[Y] Y]
i'm thinking that move/unmove are similar to cache/uncache. if so,
then i should be able to write pcon in XY. can you provide me with
some sample input/output?
apart from postings here, have you written anything up?
>
> The upside is that it becomes possible to fully expand every
> definition in a program; something that can't be done with
> explicitly recursive definitions, as noted above. I /think/ this is
> useful.
>
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2005-08-12 00:58:22
On 8/10/05, Ivan Tomac <
e1_t@...> wrote:
> But something that's more limited then quotations in Joy - rather then
> have quotations that are at the same time both lists and code, have 2
> different types, one for lists and one for code. The latter can only
> be executed, duplicated, concatenated, shuffled or destroyed. It
> cannot be split.
> What I'm asking is is this enough for a language to be flat?
No. A language with literal code blocks is not "purely" flat, at least
not within those blocks. (I use the word "purely" to imply a
similarity to the "pure" functional languages that seem to often take
a good idea too far... I don't know whether pure flatness is as
uncomfortable as pure functionality, but I'm willing to not quibble
with anyone who fears it might be. As long as they let me explore it!)
> I've just re-read some of the early posts on the topic and the
> following definition (along with the posts about flatForth) got me
> thinking:
> "William Tanksley, Jr" <wtanksleyjr@g...> wrote:
> >Flat: Flatness is the absence of all syntactic (compile-time)
> >nesting.
Yeah, I'll stand by that.
> >A test for flatness: a definition is flat if and only if it can
> >be cut apart into two valid definitions on any blank space. A
> >definition is partially flat to the extent that it can be so
> >cut. This could be expressed numericly, by dividing the number
> >of cuttable spaces by the total number of spaces.
BTW, I'm not sure anymore about the usefulness of this measure. It
does measure cuttability, but I'm not sure if that's a practical thing
to measure. I'm tempted to measure the lengths of the cuttable
sequences, but that seems to imply that a Forth program consisting of
short definitions would score lower than one consisting of long
ones... An odd result. But perhaps appropriate, since Forth
definitions aren't flat (you gotta pay somewhere for using a non-flat
language!).
> I think I understand now what Billy meant by saying that a flat
> language is a graph rather then a tree.
Actually, not quite. The lazy flat language I suggested can form
graphs, not just trees; but flat languages in general aren't any
different from non-flat ones. A lazy non-flat language could also form
graphs.
> I'm not sure whether it answers my question though. If you have a type
> of code blocks or functions and if each code block is an atom then
> doesn't that make the language flat regardless of whether a function
> in such a language has nesting or not?
Yes. HOWEVER, by saying that the "code blocks" are atoms and the
language itself is flat, you are therefore implying that the "code
blocks" are not part of the program, and in fact their structure is
not specified by the language. If their structure is part of the
language, then they are a part of the program, and the language is not
flat.
> Why am I asking that? Because
> if each code block is an atom then [1 dup 2 * drop] and [1 dup drop]
> and [1] are all equivalent and if one of those is nested inside
> another code block it can be replaced by a reference to an existing
> code block so you can still get a graph structure as opposed to a
> tree.
That's not what I meant by a graph structure. That's just an optimiser
-- any language could have one (so long as the quotations aren't too
visible to the program). The tree structure could arise if a program
took its own lazy structure and performed operations on it -- in
apter's language, you could swap bracket elements. You don't even have
to do this at runtime; you could get a nasty graph at compile time
with a little ingenuity.
-Billy
William Tanksley, Jr — 2005-08-12 05:24:52
On 8/10/05, Martin Young <
martin@...> wrote:
> I've only been half following this discussion - apologies if I've
> got the wrong end of the stick. I was just doing a little bit of on-
> paper doodling and came up with the following idea:
> The execution system has two stacks: a data stack, and a dip stack.
> These are initially empty.
The dip operator is brilliant (thanks for introducing it to us,
Manfred!), but fundamentally, the dip stack (or return stack, to use
the Forth term) is more elemental.
> It also has a stack/queue of incoming symbols - the program.
> Initially the program queue contains the program as a series of
> atoms (symbols or numbers). Symbols are removed from the program
> stack and "executed" the discarded.
Like XY. Okay.
> There are no lists, strings, tuples or suchlike in the language.
That's fine, your call. Definitely flatter in syntax -- but it occurs
to me that flatness doesn't have to be applied to data.
> The addition of two new operators, snatch and unsnatch may make the
> language flat.
> "snatch" takes one integer value (N) from the data stack then
> arranges for the next N symbols from the program queue to be
> conbined into an opaque Lump and pushed onto the dip
> stack. "unsnatch" pulls one Lump from the snatch stack and pushes
> its content onto the front of the program queue. Their presence on
> the dip stack means that suitably polymorphic symbols such as swap
> and dip can maniplate Lumps but they, the Lumps, cannot be
> decomposed.
I don't think so. The acid test of a flat program is its cuttability.
What happens if you "cut" the program right in the middle of a
snatch-snippet? The problem with snatch is that it has to look ahead,
and that means it imposes syntactic structure.
Example:
define "x" as "2 3 +"
5 snatch 1 2 3 + *
==
5 snatch x *
The two are not equal -- the second is nonsense -- but all I did was
apply a pair of cuts (to extract the program) and concatenated the
results.
Here's the above in colorForth:
:x 2 3 + ;
:y 1 2 3 + * ;
:z x * ;
The trick to notice here is that although I've put each "definition"
on a line of its own, making it look like it starts with a :name and
ends with a semicolon, they actually don't work that way. Semicolon is
actually a normal library word -- it performs a return. It doesn't
have any syntactic significance. Likewise, :name doesn't start a
definition; it merely creates a name that, when used later, refers to
that entry point in the code.
> I've been trying to build an example. I started with a program
> which prints the first N fibonaci numbers. One way of writing it is
> as two words (in MONKEY syntax).
> fibstep ==
> {{
> dup
> { + } dip
> swap
> dup .
> }}
>
> nfib ==
> {{
> 1 . 1 .
> { 1 1 { fibstep } } dip
> repeat
> drop drop
> }}
>
> I've started by converting fibstep into flat MONKEY:
>
> dup 1 snatch + move unsnatch swap dup .
Here's a similar solution in a flat colorForth variant (pop==move,
push==unmove):
:nfib for 1 1 :fibstep dup . ab--bab + 'fibstep ?loop . push drop ;
(The ab--bab is my style of stack manipulation. It does what it looks like.)
> I think this works. Sorry about the lack of formatting. Not sure
> how to format source code that has no internal structure...
Straight lines are best, IMO -- but the programmer's discretion should
not be ignored. When in doubt, stay with straight lines, and cut the
program to make each line shorter and more elemental. (This is a Forth
rule. I violate it every time.)
> I'm currently puzzling over how to write the "repeat" word, but I
> thought I'd post this before I discover that it's impossible...
I implemented the for and ?loop words, but in the final analysis
they'd be simpler to emit machine code for. Real simple... And
frankly, the flat source code for the two weren't pretty, so I cut
them out before I finished debugging them.
-Billy
Ivan Tomac — 2005-08-12 10:48:18
Thanks. Your post and Manfred's original post where flat languages are
first mentioned (and which I've just now managed to dig out - for
others who were also late to the discussion, a link:
http://groups.yahoo.com/group/concatenative/message/2471) have
answered all my questions :)
--- In
concatenative@yahoogroups.com, "William Tanksley, Jr"
<wtanksleyjr@g...> wrote:
> On 8/10/05, Ivan Tomac <e1_t@y...> wrote:
> > But something that's more limited then quotations in Joy - rather
then
> > have quotations that are at the same time both lists and code,
have 2
> > different types, one for lists and one for code. The latter can
only
> > be executed, duplicated, concatenated, shuffled or destroyed. It
> > cannot be split.
>
> > What I'm asking is is this enough for a language to be flat?
>
> No. A language with literal code blocks is not "purely" flat, at
least
> not within those blocks. (I use the word "purely" to imply a
> similarity to the "pure" functional languages that seem to often
take
> a good idea too far... I don't know whether pure flatness is as
> uncomfortable as pure functionality, but I'm willing to not quibble
> with anyone who fears it might be. As long as they let me explore
it!)
>
> > I've just re-read some of the early posts on the topic and the
> > following definition (along with the posts about flatForth) got me
> > thinking:
>
> > "William Tanksley, Jr" <wtanksleyjr@g...> wrote:
> > >Flat: Flatness is the absence of all syntactic (compile-time)
> > >nesting.
>
> Yeah, I'll stand by that.
>
> > >A test for flatness: a definition is flat if and only if it can
> > >be cut apart into two valid definitions on any blank space. A
> > >definition is partially flat to the extent that it can be so
> > >cut. This could be expressed numericly, by dividing the number
> > >of cuttable spaces by the total number of spaces.
>
> BTW, I'm not sure anymore about the usefulness of this measure. It
> does measure cuttability, but I'm not sure if that's a practical
thing
> to measure. I'm tempted to measure the lengths of the cuttable
> sequences, but that seems to imply that a Forth program consisting
of
> short definitions would score lower than one consisting of long
> ones... An odd result. But perhaps appropriate, since Forth
> definitions aren't flat (you gotta pay somewhere for using a
non-flat
> language!).
>
> > I think I understand now what Billy meant by saying that a flat
> > language is a graph rather then a tree.
>
> Actually, not quite. The lazy flat language I suggested can form
> graphs, not just trees; but flat languages in general aren't any
> different from non-flat ones. A lazy non-flat language could also
form
> graphs.
>
> > I'm not sure whether it answers my question though. If you have a
type
> > of code blocks or functions and if each code block is an atom then
> > doesn't that make the language flat regardless of whether a
function
> > in such a language has nesting or not?
>
> Yes. HOWEVER, by saying that the "code blocks" are atoms and the
> language itself is flat, you are therefore implying that the "code
> blocks" are not part of the program, and in fact their structure is
> not specified by the language. If their structure is part of the
> language, then they are a part of the program, and the language is
not
> flat.
>
> > Why am I asking that? Because
> > if each code block is an atom then [1 dup 2 * drop] and [1 dup
drop]
> > and [1] are all equivalent and if one of those is nested inside
> > another code block it can be replaced by a reference to an
existing
> > code block so you can still get a graph structure as opposed to a
> > tree.
>
> That's not what I meant by a graph structure. That's just an
optimiser
> -- any language could have one (so long as the quotations aren't too
> visible to the program). The tree structure could arise if a program
> took its own lazy structure and performed operations on it -- in
> apter's language, you could swap bracket elements. You don't even
have
> to do this at runtime; you could get a nasty graph at compile time
> with a little ingenuity.
>
> -Billy
Ivan
Martin Young — 2005-08-12 11:14:06
On Fri, 2005-08-12 at 06:24, William Tanksley, Jr wrote:
> > The addition of two new operators, snatch and unsnatch may make the
> > language flat.
>
> > "snatch" takes one integer value (N) from the data stack then
> > arranges for the next N symbols from the program queue to be
> > conbined into an opaque Lump and pushed onto the dip
> > stack. "unsnatch" pulls one Lump from the snatch stack and pushes
> > its content onto the front of the program queue. Their presence on
> > the dip stack means that suitably polymorphic symbols such as swap
> > and dip can maniplate Lumps but they, the Lumps, cannot be
> > decomposed.
>
> I don't think so. The acid test of a flat program is its cuttability.
> What happens if you "cut" the program right in the middle of a
> snatch-snippet? The problem with snatch is that it has to look ahead,
> and that means it imposes syntactic structure.
>
> Example:
>
> define "x" as "2 3 +"
>
> 5 snatch 1 2 3 + *
> ==
> 5 snatch x *
>
> The two are not equal -- the second is nonsense -- but all I did was
> apply a pair of cuts (to extract the program) and concatenated the
> results.
Good point.
> Here's the above in colorForth:
>
> :x 2 3 + ;
> :y 1 2 3 + * ;
> :z x * ;
>
> The trick to notice here is that although I've put each "definition"
> on a line of its own, making it look like it starts with a :name and
> ends with a semicolon, they actually don't work that way. Semicolon is
> actually a normal library word -- it performs a return. It doesn't
> have any syntactic significance. Likewise, :name doesn't start a
> definition; it merely creates a name that, when used later, refers to
> that entry point in the code.
Whilst this is indeed flat from the point of view of the execution
system, it's not really flat from the programmer's point of view.
Whilst you can, I guess, build a program like this...
:x 1 2
:y 3 4 + ;
...where the execution of x falls through into y, it would, I'd
suggest, be uncommon, confusing and not generally useful. The
majority of programs will retain the form where each has a start
marker and an end marker. (Or this there a school of programming
where fall-through and suchlike is the norm? I recall pulling many
such tricks when developing apps for the Z80 but I'm uncertainly about
it's continuing benefit.)
One might say that the language is technically flat but not logically
flat. Does this matter? At what level, for whom, or for what, is the
flatness important? Then again, one can write assembly language in a
functional style so perhaps the distinction is meaningless?
It seems to me colorForth has almost a direct mapping onto machine
language. I guess that's not accidental. I wonder how close you're
getting to building a smart macro assembler.
I can't quite see how you build higher level constructs from it
though. How would you go about building an anonymous closure at
runtime, for example? Wouldn't it require the ability to construct
new atoms of the form :X? But how to build an anonymous one? How
would you, or rather the execution system, generate the entry address
for a constructed program?
Before first reading about Joy, I wrote an RPN expression compiler
which had an operator ":" which droped the address of the next atom
onto the stack (as opposed to creating a name/value pair). With the
addition of a conditional call operator it could run simple loops.
This was even closer to machine language than colorForth. But, of
course, what it couldn't do was build higher level constructs - there
was no way of deferring execution. (The stack expressions were
embedded in a simple imperative language so this wasn't an issue at
the time.)
-Martin.
Martin Young — 2005-08-12 12:05:36
Stevan,
I think you're right. Any such language that can manipulate its
continuations can build an equivilent to pcon.
I don't have any convenient input/output tests. This is a failing of
mine - once it does what I want I stop building test cases and
pedagogical examples. In any case, it's mostly dip stack manipulation
which may well be different, in detail, for XY.
It expects two programs on the stack. The uppermost one is a test,
the next one the body.
pcon saves copies both of the test and body on the dip stack. It then
executes the test. If boolean True is left on top of the stack, it
executes the body then loops (i.e. it duplicates the body and the test
from the dip stack and re-executes test, tests the boolean on top of
the stack...). When boolean False is left on the stack, pcon finishes.
Here's the repeat word, implemented with pcon:
repeat ==
{{
{ dup 0 >= }
{ }
{
{ { dupmove i unmove } dip }
{ -1 + dup 0 <= }
pcon
}
ifte
drop drop
}}
What I haven't done yet is figure out how best to eliminate arbitrary
mutual recursion.
I've not written up anything other than in posts here.
-Martin.
--- In concatenative@yahoogroups.com, "stevan apter" <sa@n...> wrote:
>
> ----- Original Message -----
> From: "Martin Young" <martin@e...>
> To: <concatenative@yahoogroups.com>
> Sent: Thursday, August 11, 2005 7:43 PM
> Subject: [stack] Re: an exchange on flatness
>
>
> > --- In concatenative@yahoogroups.com, "stevan apter" <sa@n...> wrote:
> > > the recursion is an illusion. in XY, invocation of
> > > a defined word causes the definition to be pushed onto
> > > the queue. is this very different from the use of
> > > the 'repeat' word in your definition of linrec?
> >
> > In that sense, isn't all explicit recursion an illusion? No sane
> > execution system actually tries to expand explicit recursion prior
> > to execution; the expansion of the recursive invocation is always
> > lazy. Not least because the expansion is non-computable.
> >
> > I think MONKEY is (slightly) different because "repeat" is also
> > defined in terms of move and unmove. All recursive and itterative
> > combinators are built on top of the "pcon" word defined thusly:
> >
> > pcon ==
> > {{
> > { dip swapdup { swapif } dip unmove swap { dup unmove swap move swap
> > move move 0 } if drop }
> > cons cons
> > dup move move
> > }}
> >
> > Not pretty, I grant you, and not quick to execute.
>
> but of course that's not important (the performance, i mean.)
>
> i'm wondering how monkey (the unflat version) maps to XY, which also
> uses a result stack X and an input queue Y and has the primitives:
>
>
> -> queue [X^z Y] -> [X z]
> <- stack [X^z Y] -> [z Y]
>
> => cache [X^z Y] -> [X Y^z]
> <= uncache [X Y^z] -> [X^z Y]
>
> / use [X^z Y] -> [X z,Y]
> \ mention [X z^Y] -> [X^z Y]
>
> ( stack* [X Y] -> [X^[X] Y]
> ) queue* [X Y] -> [X^[Y] Y]
>
> i'm thinking that move/unmove are similar to cache/uncache. if so,
> then i should be able to write pcon in XY. can you provide me with
> some sample input/output?
>
> apart from postings here, have you written anything up?
>
> >
> > The upside is that it becomes possible to fully expand every
> > definition in a program; something that can't be done with
> > explicitly recursive definitions, as noted above. I /think/ this is
> > useful.
> >
> >
> >
> >
> >
> >
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
> >
> >
> >
William Tanksley, Jr — 2005-08-13 01:36:34
Ivan Tomac <
e1_t@...> wrote:
> I'm a bit late to join this discussion but I'm starting to like the
> idea of flat languages. If nothing else I think it's worth exploring
> them further until we can say for sure whether their advantages
> outweigh the disadvantages.
That's what I think too.
> If I remember it right you mentioned in one of the posts (can't find
> it right now, otherwise I'd quote it) that the main (only?) things
> that prevent Joy from being flat are it's definitions and blocks.
Well, kinda. Joy has a whole syntax to provide scopes for its
definitions. Other than that, yes.
> The
> problem with definitions is easy enough to solve which leaves only
> code blocks. How do you get around that problem? How do you flatten
> quotations?
> Do you simply treat them as atomic values so that no quotation can
> ever be split into smaller quotations? Or is there more to it then
> that? What else is neccesary in order for a language to be truly flat?
You'd have to make the quotations non-syntactic. I don't know how
you'd want to do that; colorForth has a simple way, while my
hypothetical flat lazy language uses a different one, and then there's
the XY stack solution.
> --- In concatenative@yahoogroups.com, "William Tanksley, Jr"
> <wtanksleyjr@g...> wrote:
> > > I was simply pointing
> > > out some things that may rely on the tree representation of code,
> > > at least in their current form.
> > That's true. All I can say, then, is that if you want to express
> > your
> > code as a tree you still can. Flat languages are graphs, not trees;
> > but if the programmer wishes, he can confine his work to the shape
> of
> > a tree.
> This part confused me a bit - how is the code in a flat language a
> graph?
I just realised I badly misspoke by saying that ALL flat languages
have graph structure. Code in my lazy flat language is a graph, as is
code in flatXY. Code in colorForth isn't. A language (any language)
can have graph-structured code if the structure of the program can be
manipulated by dynamic code.
This happens the same way that a program can have a graph-structured
dataflow -- you just use the right combinators. Just as with dataflow,
the resulting program can be staticly decidable (as with strongForth's
type checking) or not.
> Ivan
-Billy
stevan apter — 2005-08-13 12:57:12
a nice example of a language, than which there can be no
flatter, is chris barker's "jot":
http://ling.ucsd.edu/~barker/Iota/
in jot, every binary sequence is well-formed. moreover,
every expression e = e1^e2 in jot has the property that
meaning(e) = meaning(apply(meaning(e1),meaning(e2)))
i.e. you can cut an expression into an arbitrary number
of parts, then repeatedly apply the meaning of the first
to the meaning of the second, then apply that to the
meaning of the third.
now, that's flat.
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, August 12, 2005 9:36 PM
Subject: Re: [stack] Re: an exchange on flatness
Ivan Tomac <e1_t@...> wrote:
> I'm a bit late to join this discussion but I'm starting to like the
> idea of flat languages. If nothing else I think it's worth exploring
> them further until we can say for sure whether their advantages
> outweigh the disadvantages.
That's what I think too.
> If I remember it right you mentioned in one of the posts (can't find
> it right now, otherwise I'd quote it) that the main (only?) things
> that prevent Joy from being flat are it's definitions and blocks.
Well, kinda. Joy has a whole syntax to provide scopes for its
definitions. Other than that, yes.
> The
> problem with definitions is easy enough to solve which leaves only
> code blocks. How do you get around that problem? How do you flatten
> quotations?
> Do you simply treat them as atomic values so that no quotation can
> ever be split into smaller quotations? Or is there more to it then
> that? What else is neccesary in order for a language to be truly flat?
You'd have to make the quotations non-syntactic. I don't know how
you'd want to do that; colorForth has a simple way, while my
hypothetical flat lazy language uses a different one, and then there's
the XY stack solution.
> --- In concatenative@yahoogroups.com, "William Tanksley, Jr"
> <wtanksleyjr@g...> wrote:
> > > I was simply pointing
> > > out some things that may rely on the tree representation of code,
> > > at least in their current form.
> > That's true. All I can say, then, is that if you want to express
> > your
> > code as a tree you still can. Flat languages are graphs, not trees;
> > but if the programmer wishes, he can confine his work to the shape
> of
> > a tree.
> This part confused me a bit - how is the code in a flat language a
> graph?
I just realised I badly misspoke by saying that ALL flat languages
have graph structure. Code in my lazy flat language is a graph, as is
code in flatXY. Code in colorForth isn't. A language (any language)
can have graph-structured code if the structure of the program can be
manipulated by dynamic code.
This happens the same way that a program can have a graph-structured
dataflow -- you just use the right combinators. Just as with dataflow,
the resulting program can be staticly decidable (as with strongForth's
type checking) or not.
> Ivan
-Billy
Yahoo! Groups Links
stevan apter — 2005-08-13 20:41:32
----- Original Message -----
From: "stevan apter" <sa@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, August 13, 2005 8:57 AM
Subject: Re: [stack] Re: an exchange on flatness
> a nice example of a language, than which there can be no
> flatter, is chris barker's "jot":
>
> http://ling.ucsd.edu/~barker/Iota/
>
> in jot, every binary sequence is well-formed. moreover,
> every expression e = e1^e2 in jot has the property that
>
> meaning(e) = meaning(apply(meaning(e1),meaning(e2)))
>
> i.e. you can cut an expression into an arbitrary number
> of parts, then repeatedly apply the meaning of the first
> to the meaning of the second, then apply that to the
> meaning of the third.
sorry - this is wrong. what i should have said is this:
you can cut an expression into an arbitrary number of parts.
evaluate the first part on I (the identity combinator; in jot,
the empty string); then evaluate the second part on that; &c.
an example should make this clear. (schemers can futz with
chris barker's implementation to allow an initial point other
than I.)
/ combinators:
K:{y;x}
S:{x[z]y[z]}
I:{x}
B:{x[y[z]]}
/ interpreter:
j:{:[~#y;(x;y);.*y;(B[x];1_ y);(x[S][K];1_ y)]}
jot:{*(j .)/(x;"",y)}
/ the S combinator:
jot[I]"11111000"
{x[z]y[z]}
/ so now, evaluate e.g. 1000 on the evaluation of 1111:
jot[I]"1111"
{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]]
jot[jot[I]"1111";"1000"]
{x[z]y[z]}
/ in fact, evaluating the elements one bit at a time shows
/ how you progress from {x}, which is I, to {x[z]y[z]},
/ the final result:
`0:$I jot\"11111000"
{x}
{x[y[z]]}[{x}]
{x[y[z]]}[{x[y[z]]}[{x}]]
{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]
{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]]
{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]]]
{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]][{x[z]y[z]}[{y;x}]]
{x[y[z]]}[{x[y[z]]}[{x}]][{y;x}]
{x[z]y[z]}
>
> now, that's flat.
>
> ----- Original Message -----
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> To: <concatenative@yahoogroups.com>
> Sent: Friday, August 12, 2005 9:36 PM
> Subject: Re: [stack] Re: an exchange on flatness
>
>
> Ivan Tomac <e1_t@...> wrote:
> > I'm a bit late to join this discussion but I'm starting to like the
> > idea of flat languages. If nothing else I think it's worth exploring
> > them further until we can say for sure whether their advantages
> > outweigh the disadvantages.
>
> That's what I think too.
>
> > If I remember it right you mentioned in one of the posts (can't find
> > it right now, otherwise I'd quote it) that the main (only?) things
> > that prevent Joy from being flat are it's definitions and blocks.
>
> Well, kinda. Joy has a whole syntax to provide scopes for its
> definitions. Other than that, yes.
>
> > The
> > problem with definitions is easy enough to solve which leaves only
> > code blocks. How do you get around that problem? How do you flatten
> > quotations?
> > Do you simply treat them as atomic values so that no quotation can
> > ever be split into smaller quotations? Or is there more to it then
> > that? What else is neccesary in order for a language to be truly flat?
>
> You'd have to make the quotations non-syntactic. I don't know how
> you'd want to do that; colorForth has a simple way, while my
> hypothetical flat lazy language uses a different one, and then there's
> the XY stack solution.
>
> > --- In concatenative@yahoogroups.com, "William Tanksley, Jr"
> > <wtanksleyjr@g...> wrote:
> > > > I was simply pointing
> > > > out some things that may rely on the tree representation of code,
> > > > at least in their current form.
>
> > > That's true. All I can say, then, is that if you want to express
> > > your
> > > code as a tree you still can. Flat languages are graphs, not trees;
> > > but if the programmer wishes, he can confine his work to the shape
> > of
> > > a tree.
>
> > This part confused me a bit - how is the code in a flat language a
> > graph?
>
> I just realised I badly misspoke by saying that ALL flat languages
> have graph structure. Code in my lazy flat language is a graph, as is
> code in flatXY. Code in colorForth isn't. A language (any language)
> can have graph-structured code if the structure of the program can be
> manipulated by dynamic code.
>
> This happens the same way that a program can have a graph-structured
> dataflow -- you just use the right combinators. Just as with dataflow,
> the resulting program can be staticly decidable (as with strongForth's
> type checking) or not.
>
> > Ivan
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2005-08-14 15:24:38
stevan apter <
sa@...> wrote:
> > a nice example of a language, than which there can be no
> > flatter, is chris barker's "jot":
> you can cut an expression into an arbitrary number of parts.
> evaluate the first part on I (the identity combinator; in jot,
> the empty string); then evaluate the second part on that; &c.
Very interesting! There's one thing that makes this less flat than it
could be -- the meaning of each string is determined by its prefix. So
although you can chop a working program into parts, the resulting
parts don't do anything definable on their own. And it's not
concatenative either, even though any two valid programs form another
valid program, because if the first program was complete, the second
program won't do anything.
Very cool language. It looks like someone'll have to use this to
calculate Chaitin's Omega.
-Billy
stevan apter — 2005-08-14 18:54:28
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Sunday, August 14, 2005 11:24 AM
Subject: Re: [stack] Re: an exchange on flatness
> stevan apter <sa@...> wrote:
> > > a nice example of a language, than which there can be no
> > > flatter, is chris barker's "jot":
> > you can cut an expression into an arbitrary number of parts.
> > evaluate the first part on I (the identity combinator; in jot,
> > the empty string); then evaluate the second part on that; &c.
>
> Very interesting! There's one thing that makes this less flat than it
> could be -- the meaning of each string is determined by its prefix. So
> although you can chop a working program into parts, the resulting
> parts don't do anything definable on their own. And it's not
> concatenative either, even though any two valid programs form another
> valid program, because if the first program was complete, the second
> program won't do anything.
a language is flat if any program can be cut into parts which
are programs, and the meaning of the concatenation of the parts
is the same as the meaning of the whole.
concatenation can denote function-composition or function-
application. the definition of "flat" doesn't specify any
interpretation of this syntactic operation. nor does it even
require that the parts have meaning "on their own". at least,
that is how i've understood things up til now.
the way i think of jot evaluation is that you start with an
initial state and a program P. at each step, you pop the
next element of P and apply it to the state to get a new
state.
this is parallel to the way i think of joy evaluation: you
start with an initial stack and a program P. at each step,
you pop the next element of P and apply it to the stack to
get a new stack.
1 and 0 don't do anything on their own, but applied to the
state, they give you a new state.
+ and - don't do anything on their own, but applied to the
stack, they give you a new stack.
in jot, the state is a function. in joy, the state is a
stack.
it's true that the concatenation of two jot programs may
do no more than one of the programs on its own, but that
is also true in joy, is it not? for example,
2 3 + id id id
----- --------
1 2
1^2 does no more than 1.
>
> Very cool language. It looks like someone'll have to use this to
> calculate Chaitin's Omega.
i like it too. here's an even shorter jot interpreter in k:
jot:{*({(:[~#y;x;.*y;B[x];x[S][K]];1_ y)}.)/(x;"",y)}
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2005-08-14 22:05:34
stevan apter <
sa@...> wrote:
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> > stevan apter <sa@...> wrote:
> > > > a nice example of a language, than which there can be no
> > > > flatter, is chris barker's "jot":
> > > you can cut an expression into an arbitrary number of parts.
> > > evaluate the first part on I (the identity combinator; in jot,
> > > the empty string); then evaluate the second part on that; &c.
> > Very interesting! There's one thing that makes this less flat than it
> > could be -- the meaning of each string is determined by its prefix. So
> > although you can chop a working program into parts, the resulting
> > parts don't do anything definable on their own. And it's not
> > concatenative either, even though any two valid programs form another
> > valid program, because if the first program was complete, the second
> > program won't do anything.
> a language is flat if any program can be cut into parts which
> are programs, and the meaning of the concatenation of the parts
> is the same as the meaning of the whole.
Only the first half of that is in the definition of a flat language.
The second half is the definition of a concatenative language. Why?
Because it's trivially true-- it's just a neccesary consequence. Or so
it seems to me.
But your definition omitted a crucial word -- "valid". The parts must
be valid programs, in distinction to parts which are not valid. Jot is
not flat any more than it's concatenative, in spite of the fact that
splitting and joining programs does produce programs -- because the
language doesn't define validity or invalidity.
Okay, I'm stretching. But it does seem important to me that Jot is at
best "trivially" concatenative and flat, in much the same way that a
Null language would be (i.e. the language that accepted only the empty
string). Since Jot doesn't provide any definition for what makes a
string a valid program, I could invent one -- for example, "a string
is a valid program iff it describes a function, and no shorter string
could be generated by chopping bits off the tail which describes the
same function." (That's a nasty definition, and I didn't intend for it
to get so Turing-complete, but a purely syntactic version is easy to
produce.)
> concatenation can denote function-composition or function-
> application.
In Jot's case, it doesn't represent either -- it provides more
syntactic materiel for a program, or possibly does nothing at all.
> the definition of "flat" doesn't specify any
> interpretation of this syntactic operation.
It's clear, then, that my definition of "flat" is unclear and
insufficient. I think I'll have to downgrade my "definition" to the
status of a "rule of thumb". Neccesary, but not sufficient.
The primary definition of "concatenative language" isn't that the
concatenation of any two valid programs is another valid program; the
actual definition given was that it's a language in which function
composition is represented by program concatenation.
I defined flatness with that definition kind of sitting in the back of
my head -- things would have been clearer if I'd explcitly built a
similar definition.
> nor does it even
> require that the parts have meaning "on their own". at least,
> that is how i've understood things up til now.
Well, I think it's fair to require a "meaning on their own". That
meaning is a crucial part of what it means to be "valid", wouldn't you
say?
> the way i think of jot evaluation is that you start with an
> initial state and a program P. at each step, you pop the
> next element of P and apply it to the state to get a new
> state.
Mmmm. I'm not sure I see that. I have a hard time reading it, but it
looks to me like the only "state" that can be described that way is
the compiler state, not the runtime state.
> this is parallel to the way i think of joy evaluation: you
> start with an initial stack and a program P. at each step,
> you pop the next element of P and apply it to the stack to
> get a new stack.
Yes, but with a concatenative language, after you finish popping all
the elements from the queue you're done. With Jot, I think you still
have to evaluate the result.
> 1 and 0 don't do anything on their own, but applied to the
> state, they give you a new state.
Exactly.
> + and - don't do anything on their own, but applied to the
> stack, they give you a new stack.
But they DO something on their own. Or more precisely, regardless of
the depth of the stack, they perform something that can be called an
"operation" on the top two numbers on the stack. Every time.
> in jot, the state is a function. in joy, the state is a
> stack.
True.
However, the function that's being built by Jot must then be executed.
In Joy, the stack IS the entire result.
> it's true that the concatenation of two jot programs may
> do no more than one of the programs on its own, but that
> is also true in joy, is it not? for example,
> 2 3 + id id id
> ----- --------
> 1 2
> 1^2 does no more than 1.
I don't buy that. 2 is just the identity function; of course there are
SOME functions that have any conceivable property. For example, just
because + is comuatative doesn't make Joy Abelian!
-Billy
sa@dfa.com — 2005-08-15 12:36:57
jot has two elements: 0 and 1. 0 denotes the function
\x xSK
1 denotes the function
\x Bx
and the empty string denotes I, where I, S, K, and B are
the standard combinators.
so 0 and 1 do mean something "on their own", viz. they
each denote a specific function, just as + does in joy.
in joy, 2 + denotes a particular composition, viz. the
composition of the functions 2 and +.
in jot, 01 denotes a particular composition, viz. the
composition of the functions 0 and 1.
a joy program is evaluated, a token at a time, on a
stack, and returns a stack as its result.
a jot program is evaluated, a token at a time, on a
function, and returns a function as its result.
you say that since the result is a function, we're
not done yet, since "you still have to evaluate the
result." well, no. just as in joy, everything in
jot is a function. 2 3 + returns a stack containing
5, and 5 is a function.
bare jot is turing complete (we can simulate numbers,
arithmetic, lists, and so on, using functions.)
you can't get a syntax error in jot - ever sequence of
0s and 1s is well-formed. (some jot programs never
terminate, but that doesn't stand in the way of their
being "valid.")
if you embed jot in a system which allows for the
naming of jot programs, then your initial requirement
for flatness is satisfied. for example,
11111000 -> S
a:11111
b:000
ab -> S
concatenative@yahoogroups.com wrote on 08/14/2005 06:05:34 PM:
> stevan apter <sa@...> wrote:
> > From: "William Tanksley, Jr" <wtanksleyjr@...>
> > > stevan apter <sa@...> wrote:
> > > > > a nice example of a language, than which there can be no
> > > > > flatter, is chris barker's "jot":
> > > > you can cut an expression into an arbitrary number of parts.
> > > > evaluate the first part on I (the identity combinator; in jot,
> > > > the empty string); then evaluate the second part on that; &c.
>
> > > Very interesting! There's one thing that makes this less flat than it
> > > could be -- the meaning of each string is determined by its prefix.
So
> > > although you can chop a working program into parts, the resulting
> > > parts don't do anything definable on their own. And it's not
> > > concatenative either, even though any two valid programs form another
> > > valid program, because if the first program was complete, the second
> > > program won't do anything.
>
> > a language is flat if any program can be cut into parts which
> > are programs, and the meaning of the concatenation of the parts
> > is the same as the meaning of the whole.
>
> Only the first half of that is in the definition of a flat language.
> The second half is the definition of a concatenative language. Why?
> Because it's trivially true-- it's just a neccesary consequence. Or so
> it seems to me.
>
> But your definition omitted a crucial word -- "valid". The parts must
> be valid programs, in distinction to parts which are not valid. Jot is
> not flat any more than it's concatenative, in spite of the fact that
> splitting and joining programs does produce programs -- because the
> language doesn't define validity or invalidity.
>
> Okay, I'm stretching. But it does seem important to me that Jot is at
> best "trivially" concatenative and flat, in much the same way that a
> Null language would be (i.e. the language that accepted only the empty
> string). Since Jot doesn't provide any definition for what makes a
> string a valid program, I could invent one -- for example, "a string
> is a valid program iff it describes a function, and no shorter string
> could be generated by chopping bits off the tail which describes the
> same function." (That's a nasty definition, and I didn't intend for it
> to get so Turing-complete, but a purely syntactic version is easy to
> produce.)
>
> > concatenation can denote function-composition or function-
> > application.
>
> In Jot's case, it doesn't represent either -- it provides more
> syntactic materiel for a program, or possibly does nothing at all.
>
> > the definition of "flat" doesn't specify any
> > interpretation of this syntactic operation.
>
> It's clear, then, that my definition of "flat" is unclear and
> insufficient. I think I'll have to downgrade my "definition" to the
> status of a "rule of thumb". Neccesary, but not sufficient.
>
> The primary definition of "concatenative language" isn't that the
> concatenation of any two valid programs is another valid program; the
> actual definition given was that it's a language in which function
> composition is represented by program concatenation.
>
> I defined flatness with that definition kind of sitting in the back of
> my head -- things would have been clearer if I'd explcitly built a
> similar definition.
>
> > nor does it even
> > require that the parts have meaning "on their own". at least,
> > that is how i've understood things up til now.
>
> Well, I think it's fair to require a "meaning on their own". That
> meaning is a crucial part of what it means to be "valid", wouldn't you
> say?
>
> > the way i think of jot evaluation is that you start with an
> > initial state and a program P. at each step, you pop the
> > next element of P and apply it to the state to get a new
> > state.
>
> Mmmm. I'm not sure I see that. I have a hard time reading it, but it
> looks to me like the only "state" that can be described that way is
> the compiler state, not the runtime state.
>
> > this is parallel to the way i think of joy evaluation: you
> > start with an initial stack and a program P. at each step,
> > you pop the next element of P and apply it to the stack to
> > get a new stack.
>
> Yes, but with a concatenative language, after you finish popping all
> the elements from the queue you're done. With Jot, I think you still
> have to evaluate the result.
>
> > 1 and 0 don't do anything on their own, but applied to the
> > state, they give you a new state.
>
> Exactly.
>
> > + and - don't do anything on their own, but applied to the
> > stack, they give you a new stack.
>
> But they DO something on their own. Or more precisely, regardless of
> the depth of the stack, they perform something that can be called an
> "operation" on the top two numbers on the stack. Every time.
>
> > in jot, the state is a function. in joy, the state is a
> > stack.
>
> True.
>
> However, the function that's being built by Jot must then be executed.
> In Joy, the stack IS the entire result.
>
> > it's true that the concatenation of two jot programs may
> > do no more than one of the programs on its own, but that
> > is also true in joy, is it not? for example,
>
> > 2 3 + id id id
> > ----- --------
> > 1 2
>
> > 1^2 does no more than 1.
>
> I don't buy that. 2 is just the identity function; of course there are
> SOME functions that have any conceivable property. For example, just
> because + is comuatative doesn't make Joy Abelian!
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
Narcoleptic Electron — 2005-08-15 16:39:57
On 8/15/05,
sa@... <
sa@...> wrote:
> if you embed jot in a system which allows for the
> naming of jot programs, then your initial requirement
> for flatness is satisfied. for example,
>
> 11111000 -> S
>
> a:11111
> b:000
> ab -> S
When I suggested that my quotations-as-text scheme was as flat as one
could go before descending into a Turing Tarpit, Jot was the tarpit I
was specifically thinking of...
Jot is a very cool language, though. See also:
http://esoteric.voxelperfect.net/wiki/Binary_combinatory_logic
phimvt@lurac.latrobe.edu.au — 2005-08-16 10:19:31
On Sat, 13 Aug 2005, stevan apter wrote:
> a nice example of a language, than which there can be no
> flatter, is chris barker's "jot":
Indeed, it is a language flatter than which cannot be conceived
[with apologies to Aquinas(?)].
> http://ling.ucsd.edu/~barker/Iota/
>
> in jot, every binary sequence is well-formed. moreover,
> every expression e = e1^e2 in jot has the property that
>
> meaning(e) = meaning(apply(meaning(e1),meaning(e2)))
>
> i.e. you can cut an expression into an arbitrary number
> of parts, then repeatedly apply the meaning of the first
> to the meaning of the second, then apply that to the
> meaning of the third.
If I understand it correctly, it uses an idea which seems to be
due to Quine. See my only too short reference in the Joy rationale
http://www.latrobe.edu.au/philosophy/phimvt/joy/j00rat.html
to Quine's introduction to Schoenfinkel's paper "On the building blocks of
logic" in the J.van Heiyenoort collection _From Frege to Goedel_. Quine
eliminates the parentheses of combinatory calculus by the standard device
of prefix or postfix notation. Rewrite x(yz) and (xy)z with an explicit
binary infix operator o (his choice for an explicit application operator),
to give xo(yoz) and (xoy)oz. Then use the parenthesis eliminating device
to give either prefix oxoyz and ooxyz, or postfix xyzoo and xyozo.
Maybe this can be adapted for concatenative notation.
Start with 2 3 +, write the function composition explicitly using ^
to give (2 ^ 3) ^ +, now use postix for ^ to give 2 3 ^ + ^.
But that does not solve the problem for lists and quotations, which
are needed for say [1 2 3] [dup *] map. But suppose we use $ for
constructing these. How about this:
1 2 3 ^ ^ $ $ $ dup * ^ $ $ ^ map ^
where a string of N dollars means: "form a list from the N items
on the stack and push it onto the stack. Sounds rather like
a proposal we have seen on this group (Stevan?), which uses
the integer N on the stack and a single operator which means
the same.
Note that with the explicit composition operator all the usual
operators and combinators (dup, *, map) just get pushed onto the stack,
and it is only by using composition that they get executed.
Sorry, this has not been thought out properly. Is it concatenative?
Is it flat? Maybe the postfix composition operator is just an
unnecessary nuisance, but the list/quotation builder $ (or some
more elegant alternative) is of some use?
But here is yet another alternative:
DEFINE
NIL == [];
! == NIL cons i
(* execute the topmost single item on the stack *).
Everything other than ! is a push. Then write
1 2 3 NIL cons ! cons ! cons ! dup * NIL cons ! cons ! map !
Here each NIL cons ! would behave rather like $ above. Note the map !
would have to supply its own implicit ! for each item in the quotation.
Not so pretty. The real test of course would involve nested lists and
nested quotations...
But not tonight.
- Manfred
Narcoleptic Electron — 2005-08-16 17:24:06
On 8/16/05,
phimvt@... <
phimvt@...> wrote:
> Maybe this can be adapted for concatenative notation.
> Start with 2 3 +, write the function composition explicitly using ^
> to give (2 ^ 3) ^ +, now use postix for ^ to give 2 3 ^ + ^.
> But that does not solve the problem for lists and quotations, which
> are needed for say [1 2 3] [dup *] map. But suppose we use $ for
> constructing these. How about this:
>
> 1 2 3 ^ ^ $ $ $ dup * ^ $ $ ^ map ^
>
> where a string of N dollars means: "form a list from the N items
> on the stack and push it onto the stack. Sounds rather like
> a proposal we have seen on this group (Stevan?), which uses
> the integer N on the stack and a single operator which means
> the same.
>
> Note that with the explicit composition operator all the usual
> operators and combinators (dup, *, map) just get pushed onto the stack,
> and it is only by using composition that they get executed.
>
> Sorry, this has not been thought out properly. Is it concatenative?
> Is it flat? Maybe the postfix composition operator is just an
> unnecessary nuisance, but the list/quotation builder $ (or some
> more elegant alternative) is of some use?
>
> But here is yet another alternative:
>
> DEFINE
> NIL == [];
> ! == NIL cons i
> (* execute the topmost single item on the stack *).
>
> Everything other than ! is a push. Then write
>
> 1 2 3 NIL cons ! cons ! cons ! dup * NIL cons ! cons ! map !
>
> Here each NIL cons ! would behave rather like $ above. Note the map !
> would have to supply its own implicit ! for each item in the quotation.
> Not so pretty. The real test of course would involve nested lists and
> nested quotations...
This makes "!" a "special word" that doesn't just get pushed like all
the other words.
If I'm understanding correctly, this appears similar to my language,
which uses whitespace instead of "!". A quick translation of the
original Joy example follows:
[1 2 3][#s]
[[dup] [*]][code]
[map]
The basics:
- A square bracket enclosure means "push the enclosed text value onto
the stack".
- Whitespace (and end of code) means "(1) treat the text value at the
TOS as a name, then (2) evaluate it, replacing it with its defined
value."
Programs used:
- The program named "#s" replaces a text value with a list of numbers.
- The program named "code" replaces a text value with a code value,
which is a list wherein each item is either a string or an "evaluator
flag" (indicating that the string preceding it is to be evaluated as a
name) and corresponds exactly to the source code (string from
[whatever], evaluator flag from whitespace).
- The program named "map" pops a list and a code value, and applies
the code to each item in the list.
This could be considered flat as it doesn't use any nesting: inner
brackets are just text (unbalanced ones must be escaped for parsing
reasons), and text can be broken up any which way. However, it could
be rewritten so that instead of using text "quotations", the values
get built up piece by piece, as you have done in your example above.
Here is my stab at it:
[1][#] [2][#] [3][#] [nil] [cons] [cons] [cons]
[dup][!] [*][!] [nil] [cons] [cons] [cons] [cons]
[map]
Programs used:
- The program named "#" replaces the text TOS value with its numeric equivalent.
- The program named "!" pushes an evaluator flag.
For readability, the identity program named "" can be used to make
stack contents a little more clear:
[1][#] [2][#] [3][#] [nil] [cons] [cons] [cons]
[dup][] [!] [*][] [!] [nil] [cons] [cons] [cons] [cons]
[map]
Note that this is all quick-and-dirty (I haven't even implemented my
language yet...)
William Tanksley, Jr — 2005-08-20 03:44:38
sa@... <
sa@...> wrote:
> so 0 and 1 do mean something "on their own", viz. they
> each denote a specific function, just as + does in joy.
Oops -- I was wrong. I got confused between Jot and Iota. You're
definitely right; it's concatenative, and definitely belongs on this
egroup :-).
Facinating language; I don't understand a jot of it.
-Billy
William Tanksley, Jr — 2005-08-20 05:40:44
Narcoleptic Electron <
narcoleptic.electron@...> wrote:
> On 8/16/05, phimvt@... <phimvt@...> wrote:
> > 1 2 3 NIL cons ! cons ! cons ! dup * NIL cons ! cons ! map !
> > Here each NIL cons ! would behave rather like $ above. Note the map !
> > would have to supply its own implicit ! for each item in the quotation.
> > Not so pretty. The real test of course would involve nested lists and
> > nested quotations...
> This makes "!" a "special word" that doesn't just get pushed like all
> the other words.
Yes, all of our suggestions seem to add a special syntactic element.
My lazy language would require something like "!" to tell the compiler
where the dataflow ends. Some people would use EOF, others would want
something explicit.
> If I'm understanding correctly, this appears similar to my language,
> which uses whitespace instead of "!". A quick translation of the
> original Joy example follows:
> [1 2 3][#s]
> [[dup] [*]][code]
> [map]
I don't see the similarity -- your language seems to have the full
syntactic structure of a typical Joylike language. Plus some more.
> The basics:
> - A square bracket enclosure means "push the enclosed text value onto
> the stack".
> - Whitespace (and end of code) means "(1) treat the text value at the
> TOS as a name, then (2) evaluate it, replacing it with its defined
> value."
Ah. Yes, very complex syntax.
> This could be considered flat as it doesn't use any nesting: inner
> brackets are just text (unbalanced ones must be escaped for parsing
> reasons), and text can be broken up any which way. However, it could
> be rewritten so that instead of using text "quotations", the values
> get built up piece by piece, as you have done in your example above.
> Here is my stab at it:
> [1][#] [2][#] [3][#] [nil] [cons] [cons] [cons]
> [dup][!] [*][!] [nil] [cons] [cons] [cons] [cons]
> [map]
That's flat.
Try that with prefix, and all text ending at the first space:
#1 #2 #3 nil cons cons cons !dup !* nil cons cons cons map
That's essentially how colorForth works. Forth isn't too dissimilar,
either (although it's more complex and less flat).
-Billy
Narcoleptic Electron — 2005-08-20 07:48:41
On 8/20/05, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> Narcoleptic Electron <narcoleptic.electron@...> wrote:
> > On 8/16/05, phimvt@... <phimvt@...> wrote:
> > > 1 2 3 NIL cons ! cons ! cons ! dup * NIL cons ! cons ! map !
>
> > > Here each NIL cons ! would behave rather like $ above. Note the map !
> > > would have to supply its own implicit ! for each item in the quotation.
> > > Not so pretty. The real test of course would involve nested lists and
> > > nested quotations...
>
> > This makes "!" a "special word" that doesn't just get pushed like all
> > the other words.
>
> Yes, all of our suggestions seem to add a special syntactic element.
By "special syntactic element", I assume you mean one that represents
an exception to a rule (eg. a "special word"). This is not the case
with my language. Whitespace serves this single purpose only (to pop
TOS string and push the program with that name). This is why I'm
bringing it up as a seemingly cleaner solution.
> > If I'm understanding correctly, this appears similar to my language,
> > which uses whitespace instead of "!". A quick translation of the
> > original Joy example follows:
>
> > [1 2 3][#s]
> > [[dup] [*]][code]
> > [map]
>
> I don't see the similarity -- your language seems to have the full
> syntactic structure of a typical Joylike language.
You're correct: there's not much similarity in this example. The
similarity comes below when I give the flat version in the same
language. The similarity there is that whitespace in mine does the
job of the special "!" word in yours, more or less.
> Plus some more.
There is considerably less syntactic structure in my language than in Joy.
> > The basics:
> > - A square bracket enclosure means "push the enclosed text value onto
> > the stack".
> > - Whitespace (and end of code) means "(1) treat the text value at the
> > TOS as a name, then (2) evaluate it, replacing it with its defined
> > value."
>
> Ah. Yes, very complex syntax.
You're kidding, right...?
> > This could be considered flat as it doesn't use any nesting: inner
> > brackets are just text (unbalanced ones must be escaped for parsing
> > reasons), and text can be broken up any which way. However, it could
> > be rewritten so that instead of using text "quotations", the values
> > get built up piece by piece, as you have done in your example above.
> > Here is my stab at it:
>
> > [1][#] [2][#] [3][#] [nil] [cons] [cons] [cons]
> > [dup][!] [*][!] [nil] [cons] [cons] [cons] [cons]
> > [map]
>
> That's flat.
>
> Try that with prefix, and all text ending at the first space:
>
> #1 #2 #3 nil cons cons cons !dup !* nil cons cons cons map
That's not as clean, because in my language, "#" and "!" are just
regular programs, like "cons" and "nil". There are absolutely no
"special programs" or "tokens that have special parsing rules"; only
whitespace and words (enclosed in []). A word is either interpreted
as a literal or a lexeme (to be looked up in the dictionary),
depending on whether there is whitespace after it.
I didn't intend to hijack this thread to talk about my language; just
trying to demonstrate what I consider a simple and clean way to
achieve flatness.
phimvt@lurac.latrobe.edu.au — 2005-08-22 06:26:01
On Fri, 19 Aug 2005, William Tanksley, Jr wrote:
> Yes, all of our suggestions seem to add a special syntactic element.
Indeed, there seems to be no way around it. I keep on changing my mind
about whether it is possible at all. But then, after all the parser has
as input a flat sequence, and manages to construct a possibly nested
structure from that. The way the Joy parser does it is this: when it sees
[ , it starts an empty list. Subsequently, when it sees anything except ]
, it APPENDs it to the most recently constructed list. When it sees the
closing ] , it APPENDs this list to the output stream (the program to be
executed). Can we delay this construction so that it happens not at
compile time but at run time? Yes, like this:
Let A (pronounced "append") be a new unary operator which can only occur
before atoms (literals, operators, combinators). For any atom x, let "Ax"
mean: append x to the list on top of the stack. Also, we need another
ordinary operator E (pronounced "end", which means: append the list on top
of the stack to the list which is second on the stack. Then
[1 2 3] [dup *] map # ==> [1 4 9]
would be rewritten as:
[] A1 A2 A3 E [] Adup A* E map
Similarly, the nested data and nested program
[[1 2 [3]] [[dup *] map] map # ==> [[1 4][9]]
would be rewritten as
[] [] A1 A2 E [] A3 E E [] Adup A* E map
The E operator is an ordinary Joy operator, it might have been defined by
E == [reverse] dip cons reverse
But the A operator is something quite new, it cannot be defined in Joy,
and it is the price we would have to pay for this particular version of
flatness. I do not at this stage know whether it would be useful to allow
repetitions of the A operator, as in AAAx, which would append AAx to the
end of the list on top of the stack.
[Incidentally, when I wrote the implementation of Joy I had to decide
whether to use normal linked lists or the slightly more complicated and
more versatile circular lists. I used the first because it is more
efficient, and because it seemed that the extra power of circular lists
was not needed. But circular lists would be ideal for implementing the A
operator - and quite a few other things.]
Is this particular solution to the flatness problem really different from
others? Not really, much of it is identical to Stevan's XY solution which
uses a queue Y, together with some operators managing the traffic between
the stack X and the queue Y. My solution essentially treats the list on
top of the stack as a queue. Thanks, Stevan.
- Manfred
Narcoleptic Electron — 2005-08-22 15:12:17
On 8/22/05,
phimvt@... <
phimvt@...> wrote:
>
> On Fri, 19 Aug 2005, William Tanksley, Jr wrote:
>
> > Yes, all of our suggestions seem to add a special syntactic element.
>
> Indeed, there seems to be no way around it.
? I believe I just demonstrated one. My language only has string
literals (enclosed with "[]" rather than double quote) and whitespace.
No other literals or syntactic constructs, and no special rules.
This is a subset of the syntax of every other language being
discussed, as I presume that they all have a means of specifying a
string literal (probably enclosing it with double quotes).
> But then, after all the parser has
> as input a flat sequence, and manages to construct a possibly nested
> structure from that. The way the Joy parser does it is this: when it sees
> [ , it starts an empty list. Subsequently, when it sees anything except ]
> , it APPENDs it to the most recently constructed list. When it sees the
> closing ] , it APPENDs this list to the output stream (the program to be
> executed). Can we delay this construction so that it happens not at
> compile time but at run time? Yes, like this:
>
> Let A (pronounced "append") be a new unary operator which can only occur
> before atoms (literals, operators, combinators). For any atom x, let "Ax"
> mean: append x to the list on top of the stack. Also, we need another
> ordinary operator E (pronounced "end", which means: append the list on top
> of the stack to the list which is second on the stack. Then
>
> [1 2 3] [dup *] map # ==> [1 4 9]
>
> would be rewritten as:
>
> [] A1 A2 A3 E [] Adup A* E map
>
> Similarly, the nested data and nested program
>
> [[1 2 [3]] [[dup *] map] map # ==> [[1 4][9]]
>
> would be rewritten as
>
> [] [] A1 A2 E [] A3 E E [] Adup A* E map
>
> The E operator is an ordinary Joy operator, it might have been defined by
>
> E == [reverse] dip cons reverse
>
> But the A operator is something quite new, it cannot be defined in Joy,
> and it is the price we would have to pay for this particular version of
> flatness. I do not at this stage know whether it would be useful to allow
> repetitions of the A operator, as in AAAx, which would append AAx to the
> end of the list on top of the stack.
As I see it, the only reason that "A" needs to be special is so that
the word it prefixes isn't evaluated. In other words, it quotes the
word.
Instead of doing this, what is wrong with my solution of using a
string as a quoted word? All tokens are strings to start off with,
but some get evaluated as words and some remain strings, depending on
whether they are followed by whitespace or not.
William Tanksley, Jr — 2005-08-22 23:46:21
Narcoleptic Electron <
narcoleptic.electron@...> wrote:
> On 8/22/05, phimvt@... <phimvt@...> wrote:
> > On Fri, 19 Aug 2005, William Tanksley, Jr wrote:
> > > Yes, all of our suggestions seem to add a special syntactic element.
> > Indeed, there seems to be no way around it.
> ? I believe I just demonstrated one. My language only has string
> literals (enclosed with "[]" rather than double quote) and whitespace.
> No other literals or syntactic constructs, and no special rules.
But your "string literals" are more than mere strings -- they're
highly specified syntaxes, one of which (the "code" syntax) is the
full language, including the possibility for arbitrarily nested
literals.
> This is a subset of the syntax of every other language being
> discussed, as I presume that they all have a means of specifying a
> string literal (probably enclosing it with double quotes).
None of them require a complete nested syntax in the string literals.
> As I see it, the only reason that "A" needs to be special is so that
> the word it prefixes isn't evaluated. In other words, it quotes the
> word.
Yes. Or in other words, it applies some other way of reading the word
aside from the default "compile or interpret".
> Instead of doing this, what is wrong with my solution of using a
> string as a quoted word? All tokens are strings to start off with,
> but some get evaluated as words and some remain strings, depending on
> whether they are followed by whitespace or not.
Nothing's wrong with it -- your method uses postfixes, while the above
method uses suffixes. The two can be transformed seamlessly into one
another, but yours takes more characters to type, and I don't see any
advantage to it. Yours requires every symbol to be quoted with open
and close delimiters, while his requires only "extraordinary" symbols
to be quoted.
-Billy
Narcoleptic Electron — 2005-08-23 04:16:39
On 8/22/05, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> But your "string literals" are more than mere strings -- they're
> highly specified syntaxes, one of which (the "code" syntax) is the
> full language, including the possibility for arbitrarily nested
> literals.
That is incorrect. The string literals are not more than mere
strings, nor are they highly specified syntaxes. They are just
string literals. There is no nesting -- the brackets within are
characters. Unbalanced brackets must be escaped only for parsing
reasons.
The "code" program is the one implicitly called when parsing text
source code. It can also be called explicitly on any string.
> > This is a subset of the syntax of every other language being
> > discussed, as I presume that they all have a means of specifying a
> > string literal (probably enclosing it with double quotes).
>
> None of them require a complete nested syntax in the string literals.
Neither does mine. Programs can do with strings whatever they want,
and calling the "code" program is only one possible approach. I also
demonstrated a flat approach in an earlier email.
> Nothing's wrong with it -- your method uses postfixes, while the above
> method uses suffixes. The two can be transformed seamlessly into one
> another, but yours takes more characters to type, and I don't see any
> advantage to it.
Some advantages:
- Any string can be used as a word (eg. [I am a descriptive name for a word.]).
- Much simpler to parse: only string literals and whitespace.
Contrast this with string literals, whitespace, prefix quotation
operator (in Manfred's example), special "number literal" programs,
etc...
Don't get me wrong: I am not slamming Joy. That language turned me
around and helped me to see the light of concatenative programming,
and Manfred's papers are brilliant.
> Yours requires every symbol to be quoted with open
> and close delimiters, while his requires only "extraordinary" symbols
> to be quoted.
That's exactly the point! There are no "extraordinary" symbols in my
language...
phimvt@lurac.latrobe.edu.au — 2005-08-26 06:50:07
On Mon, 22 Aug 2005
phimvt@... wrote:
> On Fri, 19 Aug 2005, William Tanksley, Jr wrote:
>
> > Yes, all of our suggestions seem to add a special syntactic element.
I now think that a new special syntactic element is not necessary
as long as we relax the definition of flatness just a little bit.
I proposed the following new syntactic element, which upon relaxation
will not be necessary:
> Let A (pronounced "append") be a new unary operator which can only occur
> before atoms (literals, operators, combinators). For any atom x, let "Ax"
> mean: append x to the list on top of the stack. Also, we need another
> ordinary operator E (pronounced "end", which means: append the list on top
> of the stack to the list which is second on the stack. Then
>
> [1 2 3] [dup *] map # ==> [1 4 9]
>
> would be rewritten as:
>
> [] A1 A2 A3 E [] Adup A* E map
>
> Similarly, the nested data and nested program
>
> [[1 2 [3]] [[dup *] map] map # ==> [[1 4][9]]
>
> would be rewritten as
>
> [] [] A1 A2 E [] A3 E E [] Adup A* E map
>
> The E operator is an ordinary Joy operator, it might have been defined by
>
> E == [reverse] dip cons reverse
>
> But the A operator is something quite new, it cannot be defined in Joy,
> and it is the price we would have to pay for this particular version of
> flatness.
Now relax the definition of flatness by allowing unitlists of atoms
(literals, operators, combinators). Then the first program
> [1 2 3] [dup *] map # ==> [1 4 9]
would be rewritten as
[] [1] concat [2] concat [3] concat [] [dup] concat [*] concat map
Or for the sake of more compact notation, DEFINE c == concat. :
[] [1]c [2]c [3]c [] [dup]c [*]c map
> Similarly, the nested data and nested program
>
> [[1 2 [3]] [[dup *] map] map # ==> [[1 4][9]]
would be rewritten as
[] [] [1]c [2]c c [] [3]c c [] [] [dup]c [*]c c [] [map]c map
Define Floy ("Flat Joy") to be that subset of Joy in which the only
lists or quotations are [] and the unit lists of atoms. Can we write
a translator j2f (Joy to Floy) which takes a quoted Joy program J
and produces a quoted Floy program F such that [J] i == [F] i ?
(Note that even if F is a Floy program, its quotation [F] generally
will not be.) Moreover, can the translator j2f be written in Joy?
If so, then the translator can also be written in Floy, by passing
it through itself. So there will be a j2f.joy and a j2f.floy. Compiler
writers do that sort of thing all the time. I don't think that j2f.joy
will be longer than five short lines, and j2f.floy will just have longer
lines. I'll work on this, it looks like fun.
> Is this particular solution to the flatness problem really different from
> others? Not really, much of it is identical to Stevan's XY solution which
> uses a queue Y, together with some operators managing the traffic between
> the stack X and the queue Y. My solution essentially treats the list on
> top of the stack as a queue. Thanks, Stevan.
The debt to Stevan extends to Floy too. After all, for any atom a,
the program [a]c does precisely an append of the atom a to the quotation
on top of the stack. So the quotation is a queue on top of the stack.
- Manfred
phimvt@lurac.latrobe.edu.au — 2005-09-07 08:07:23
On Fri, 26 Aug 2005 phimvt@... wrote:
[..]
> Define Floy ("Flat Joy") to be that subset of Joy in which the only
> lists or quotations are [] and the unit lists of atoms. Can we write
> a translator j2f (Joy to Floy) which takes a quoted Joy program J
> and produces a quoted Floy program F such that [J] i == [F] i ?
That should have been [J] i == [F] i i
> (Note that even if F is a Floy program, its quotation [F] generally
> will not be.) Moreover, can the translator j2f be written in Joy?
> If so, then the translator can also be written in Floy, by passing
> it through itself. So there will be a j2f.joy and a j2f.floy. Compiler
> writers do that sort of thing all the time. I don't think that j2f.joy
> will be longer than five short lines, and j2f.floy will just have longer
> lines. I'll work on this, it looks like fun.
Well, it took much much longer than I anticipated - how embarrassing.
But it was fun, and I think I'll write it up as a more detailed note.
I haven't passed it through itself yet to get j2f.floy, but here is
the simple version, j2f.joy :
DEFINE
c == concat;
HIDE
h ==
[ list ]
[ [[[]] concat] dip [h] step [[] cons c] concat ]
[ [] cons [c] cons concat ]
ifte;
IN
j2f == [[]] swap [h] step
END;
P1 == [2 3 + dup *];
P2 == [[1 2 3] [dup *] map];
P3 == [ [[1 2][3 4][5] []] [[dup *] map] map ].
The following tests show, for each of the three example programs P1 P2 P3:
1: the original quoted Joy program,
2: the translation as a quoted flat-Joy program
3: the result of executing the translation (= the original)
4: the result of executing this result (= executing the original)
P1 .
[2 3 + dup *]
P1 j2f .
[[] [2] c [3] c [+] c [dup] c [*] c]
P1 j2f i .
[2 3 + dup *]
P1 j2f i i .
25
P2 .
[[1 2 3] [dup *] map]
P2 j2f .
[[] [] [1] c [2] c [3] c [] cons c [] [dup] c [*] c [] cons c [map] c]
P2 j2f i .
[[1 2 3] [dup *] map]
P2 j2f i i .
[1 4 9]
P3 .
[[[1 2] [3 4] [5] []] [[dup *] map] map]
P3 j2f .
[[] [] [] [1] c [2] c [] cons c [] [3] c [4] c [] cons c [] [5] c [] cons c [] [] cons c [] cons c [] [] [dup] c [*] c [] cons c [map] c [] cons c [map] c]
P3 j2f i .
[[[1 2] [3 4] [5] []] [[dup *] map] map]
P3 j2f i i .
[[1 4] [9 16] [25] []]
Note that j2f itself uses "concat" whereas the resultant flat Joy program
uses "c" (defined as "concat"). That was to distinguish what the j2f
translator does from the result that it produces. So both use a lot
of concatenation, because they both operate on queues. But concatenation
is always expensive.
Could one replace the two levels of queue manipulation with two levels
of stack manipulation which would be more efficient? Who cares, you say.
OK, but similar problems might arise elsewhere, and it is an interesting
challenge to know about general solutions. So I am now thinking about
calling the above solution j2f-q, and writing another j2f-s. They should
satisfy
[J] j2f-q i == [J] and [J] j2f-s i == [J]
or
j2f-q i == id and j2f-s i == id
Succinctly, the i combinator is the (post-)inverse of j2f-q and of j2f-s,
but not conversely.
More fun? more agony?
- Manfred