S-K Construction of Dip?
Christopher Diggins — 2007-02-21 17:59:05
From
http://tunes.org/~iepos/joy.html
This sentence never quite sat well with me:
"however, there is no way to form "dip" or "sip" using just "s" and
"k" because, roughly speaking, they provide no way to dequote items
buried in the stack."
I may have found a counter-example:
We know that we can construct: c b and i from s
Then we can go on to define:
swap = [] c
cons = [] b
zap = [] k
unit = [] [zap] s
cat = swap [i] cons swap cons
And finally:
dip = swap unit cat i
Can anyone verify if this is this correct for me?
Thanks,
Chrstopher
Manfred Von Thun — 2007-02-22 03:03:33
I think you are wrong about cons.
First consideration: The pure (data independent) stack shufflers swap, dup,
rollup,and also pure combinators like i and dip, cannot be used to define
data (numbers,strings,lists) dependent operations and combinators
Second: in my scheme of things b is a combinator which expects two
quotations. It executes both, first the quotation second from the top, and
then the other. It satisfies the law: b = [i] dip i. I assume you mean the
same
Third, the combinator satisfies the law: i = [] b. The two laws are true,
and either could be used as a definition. But you could not use both as
definitions because of the circularity.
Hence: [...] [] b = [...] [i] dip i = ... [] i = .... [] i = ....
In other words what you called cons is just the i combinator. Hope this
helps.
Another law: b = concat i. This assumes that concat is already given.
But normally concat has to be defined in terms of cons. Alternatively,
given concat and unitlist, define cons = [unitlist] dip concat.
New year¹s greetings to all. I have been reading the recent contributions
but could not contribute for lack of understanding and my sparse time here
at uni. But I shall report separately on what I have been doing at home.
- Manfred
On 22/2/07 4:59 AM, "Christopher Diggins" <cdiggins@...> wrote:
>
>
>
>
> From http://tunes.org/~iepos/joy.html
>
> This sentence never quite sat well with me:
>
> "however, there is no way to form "dip" or "sip" using just "s" and "k"
> because, roughly speaking, they provide no way to dequote items buried in
> the stack."
>
> I may have found a counter-example:
>
> We know that we can construct: c b and i from s
>
> Then we can go on to define:
>
> swap = [] c cons = [] b zap = [] k unit = [] [zap] s cat = swap [i] cons
> swap cons
>
> And finally:
>
> dip = swap unit cat i
>
> Can anyone verify if this is this correct for me?
[Non-text portions of this message have been removed]
Christopher Diggins — 2007-02-22 03:33:25
Hmm... most of the constructions I used (except dip and cons) were lifted
directly from Brent's article.
It sounds like perhaps the your definition of b differs from Brent's?
I'll have to look into this in more depth.
I look forward to hearing more about your work!
Cheers,
Christopher
On 2/21/07, Manfred Von Thun <m.vonthun@...> wrote:
>
> I think you are wrong about cons.
>
> First consideration: The pure (data independent) stack shufflers swap,
> dup,
> rollup,and also pure combinators like i and dip, cannot be used to define
> data (numbers,strings,lists) dependent operations and combinators
>
> Second: in my scheme of things b is a combinator which expects two
> quotations. It executes both, first the quotation second from the top, and
> then the other. It satisfies the law: b = [i] dip i. I assume you mean the
> same
>
> Third, the combinator satisfies the law: i = [] b. The two laws are true,
> and either could be used as a definition. But you could not use both as
> definitions because of the circularity.
>
> Hence: [...] [] b = [...] [i] dip i = ... [] i = .... [] i = ....
>
> In other words what you called cons is just the i combinator. Hope this
> helps.
>
> Another law: b = concat i. This assumes that concat is already given.
> But normally concat has to be defined in terms of cons. Alternatively,
> given concat and unitlist, define cons = [unitlist] dip concat.
>
> New year¹s greetings to all. I have been reading the recent contributions
> but could not contribute for lack of understanding and my sparse time here
> at uni. But I shall report separately on what I have been doing at home.
>
> - Manfred
>
> On 22/2/07 4:59 AM, "Christopher Diggins" <cdiggins@...<cdiggins%40gmail.com>>
> wrote:
>
> >
> >
> >
> >
> > From http://tunes.org/~iepos/joy.html
> >
> > This sentence never quite sat well with me:
> >
> > "however, there is no way to form "dip" or "sip" using just "s" and "k"
> > because, roughly speaking, they provide no way to dequote items buried
> in
> > the stack."
> >
> > I may have found a counter-example:
> >
> > We know that we can construct: c b and i from s
> >
> > Then we can go on to define:
> >
> > swap = [] c cons = [] b zap = [] k unit = [] [zap] s cat = swap [i] cons
> > swap cons
> >
> > And finally:
> >
> > dip = swap unit cat i
> >
> > Can anyone verify if this is this correct for me?
>
> [Non-text portions of this message have been removed]
>
>
>
--
http://www.cdiggins.com
[Non-text portions of this message have been removed]
Brent L Kerby — 2007-02-22 06:55:37
> I may have found a counter-example:
The only problematic construction is "cat":
> cat = swap [i] cons swap cons
"[i] cons" is a no-op acting on one stack item:
[A] [i] cons
== [[A] i]
== [A]
So that would make
cat = swap swap cons == cons
which can't be right.
In any case, I confess it was a bit rash of me to make that claim (that "dip" cannot be constructed from {s,k}) without offering any substantial justification. So let's see if we can remedy that.
To do this carefully, we need to make a recursive definition: Say that a concatenative expression "x1 x2 x3 ... xn" (where each term xi is either an atom or a quotation) is "dip-free" relative to a set of indeterminates {A, B, ...} if the following property holds for each xi:
a) If xi is an atom, then for any j > i, xj must neither be, nor (in the case xj is a quotation) contain, any of the indeterminates {A, B, ...}.
b) If xi is a quotation, then its body must be dip-free.
I.e, an expression is dip-free if no indeterminates (whether quoted or not) occur to the right of any (dequoted) atom, and if the same holds for any (sub-)quotation.
So, for example, the following expressions are dip-free relative to {A, B}:
[B] [A]
[B] A []
[A] B s [k]
[[B] A] [A []] B [s] k
while the following are not:
A [B]
[B A]
k [A] [B]
[A] [k] [k] s [B]
Now the key observation is that a dip-free expression remains dip-free when the reduction rules for "s" and "k" are applied
[C] [B] [A] s => [[C] B] [C] A
[B] [A] k => A
(Although the converse is not true: it is possible for a non-dip-free expression to become dip-free after application of "k"'s rule, e.g., "A [B] [] k => A").
To see this, consider an arbitrary expression containing an "s" or "k" redex (i.e., an expression matching the left side of the reduction rule for "s" or "k"). For the moment, assume the redex occurs at the top level of the expression, i.e., not inside a quotation. So, in the case of "s", we have an expression
x1 x2 ... xn [q1] [q2] [q3] s z1 z2 ... zn
(where the xi's and zi's are atoms or quotations, while the qi's are arbitrary concatenative expressions), which we assume is dip-free, and which reduces to
x1 x2 ... xn [[q1] q2] [q1] q3 z1 z2 ... zn
which we verify is also dip-free, by carefully checking that each term satisfies the property in the definition: Each xi satisfies it, since (in the case xi is an atom) no new indeterminates have been introduced to the right of xi, and in the case xi is a quotation, its body remains unchanged and hence dip-free. It is satisfied for [[q1] q2] since q1 and q2, and hence "[q1] q2", are dip-free (Take a moment to check this most important step. It would break down if, for example, the quotation had been [q1 [q2]] or [q1 q2], since q1 might include an atom and q2 could contain an indeterminate). It is satisfied for [q1] since q1 is dip-free. Now, before looking at q3, notice that z1, z2, ..., zn do not contain any indeterminates, since they follow the atom "s" in the original expression. So then, for each term in q3, the property is satisfied since, if the term is an atom then it will contain no indeterminates after it since "q3" is dip-free and z1, z2, ..., zn contain no indeterminates, while if the term is a quotation, its body remains unchanged. Likewise, we easily verify that the property holds for z1, z2, ..., zn. A similar argument applies to "k".
And now, suppose the redex occurs inside a quotation, so that we have an expression
x1 x2 ... xn [q] z1 z2 ... zn
assumed to be dip-free, reducing to
x1 x2 ... xn [q'] z1 z2 ... zn
Then q must be dip-free, so by the above argument (and applying induction on the depth of nested quotations in which the redex appears), q' must also be dip-free. So the property holds for [q']. And, the property holds for each xi and zi in the new expression, since for the atoms, no new indeterminates have been introduced to their right, while for the quotations, their bodies remains unchanged and hence dip-free.
That proves that the reduction rules for "s" and "k" preserve the dip-free property. So then, finally, suppose "x" were some concatenative expression over {s,k} constituting a construction "dip", so that we have a reduction
[B] [A] x ==> A [B]
This is impossible because the left side is dip-free relative to {A, B} but the right side is not, while the right-hand side is obtained from the left-hand side only applying the reduction rules for {s, k}, which we showed preserve the dip-free property. So we cannot construct "dip" from {s,k}. Therefore, we cannot construct "cat" from {s,k} either, since otherwise this would enable the construction of "dip" which you mentioned
dip = swap unit cat i
Alternatively, we could prove directly that "cat" is inconstructible from {s,k} since "[B A]" is not dip-free relative to {A, B}.
So there we have it! It took some work, but considering the somewhat counterintuitive yet fundamental nature of the result, I think it was worth taking the time to address properly.
Does that clear things up?
- Brent
P.S., Manfred,
Christopher and I are using "b" to refer to the following combinator:
[Z] [Y] [X] b == [[Z] Y] X
which is the concatenative version of the classical "B" combinator (as "s", "c", "w", "k", and "i" are the concatenative versions of the classical S, C, W, K, and I combinators), while your "b" is
[Y] [X] b == Y X
I didn't notice you had already defined "b", so sorry about that; I wasn't intending to create a conflict in the notation.
Christopher Diggins — 2007-02-23 05:42:40
Thank you very much for patiently explaining the concept and proof of "dip
free" constructions to me Brent, I greatly appreciate it.
- Christopher
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-02-23 17:37:54
Brent L Kerby <
bkerby@...> wrote:
> Does that clear things up?
Thank you!
Let me first say that recasting combinatorial operations in terms of a
flat concatenative language has made it MUCH easier for me to reason
about them. I definitely don't understand them completely, but somehow
the reasoning seems more in line with my brain's workings. One of my
friends felt the same way. Am I just mentally disturbed from years of
Forth use and abuse, or is there actually something simpler here?
Anyhow:
I find it interesting that completeness is different between
applicative and concatenative languages (for example, {s,k} is a
complete applicative basis, but not is not complete when
concatenative).
Thinking about this, I'm guessing that this is because application
forms a syntactic tree, so that it's possible to talk about a
combinator's "siblings". Concatenation forms a syntactic list (not
nested), so although elements can have a child, there are no syntactic
siblings.
My theory: Therefore, because the syntax doesn't provide that
operation, the semantics have to provide it. And indeed, every
complete basis we've produced has combinators that can provide access
at the same level to either of two elements. In other words, the
combinators must include some way of making two different elements
into (equal) siblings.
The problem with this theory is that the cake combinator in {cake,k}
is an obvious counterexample:
[B] [A] cake == [[B] A] [A [B]]
Clearly, A and B are not siblings here. Of course, constructing concat
is possible, which obviously makes siblings out of A and B, but is it
somehow less theoretically pure to have a basis in which the siblings
are not explicit in the provided basis combinators? My theory suggests
something like that, but I (intuitively) find it difficult to believe.
Is there a better theory? Or should I reform my intuitions instead,
and accept the theory (thereby condemning {cake,k} to contempt and
contumely)?
> - Brent
-William (Billy)
Brent L Kerby — 2007-02-24 10:45:52
> Let me first say that recasting combinatorial operations in terms of a
> flat concatenative language has made it MUCH easier for me to reason
> about them. I definitely don't understand them completely, but somehow
> the reasoning seems more in line with my brain's workings. One of my
> friends felt the same way. Am I just mentally disturbed from years of
> Forth use and abuse, or is there actually something simpler here?
Well, although building flat bases (e.g., {o, k}) has been great fun, to me it seems like this system is only simpler in a fairly artificial way. This is because the system, in a sense, is not flat at all. True, we can express programs using flat syntax; but, once these programs start executing, they start building programs on the stack that aren't flat. So the system has to deal with non-flat programs in the course of execution anyway. And to do anything non-trivial the programmer needs non-flat programs, only he isn't allowed to express them directly, but rather is forced to construct them in a flat manner, with his hands tied behind his back, so to speak.
So, we ask, is it possible to modify our approach to give us a more "genuine" flat system? Well, to really be flat, we would have to not be able to push programs onto the stack, since that's the first level of non-flatness. And if we can't do that, that leaves literally nothing left that we can do, assuming we've started with just the concatenative combinators, where programs are the only type of data. So, a "genuine" flat system would have to be quite different. Special support would be needed for loops and conditionals, since these could no longer be implemented with the (rather meager) remaining set of combinators (which could only shuffle the stack, not perform restructuring or execution).
I don't know. The way I see it, non-flatness is roughly equivalent to the ability to do higher-order programming, which is a good property of a system. It seems to be a fundamental part of the Joy programming paradigm. And for that matter, any programming language that supports loops and conditionals is going to be (conceptually) non-flat in the sense that programs have structure; we think of them as being divided into pieces, subpieces, etc. The syntax may or may not reflect this; but if it doesn't, I would say it's just because it's been artificially obscured.
But, if you can show me a really nice flat programming language, you may be able to change my mind :-)
> I find it interesting that completeness is different between
> applicative and concatenative languages (for example, {s,k} is a
> complete applicative basis, but not is not complete when
> concatenative).
Right. When we map the applicative combinators to concatenative ones in the obvious way, the image of this map is not a complete (concatenative) set. But it's interesting to note that, in the other direction, things turn out differently. I.e., the image of the natural map (or at least, what I'm calling the natural map) from concatenative combinators to applicative ones _is_, remarkably enough, a complete applicative set. Here's the map I'm talking about: Call the map P, defined recursively as follows:
P(id) = \c.c
P(x) = \c.xc
P(f g) = \c.F(Gc)
P([f]) = \c.cF
P(x\ f) = \cx.Fc
where "f" and "g" are arbitrary concatenative expressions, F is P(f), G is P(g), "x" is any variable, and "c" is some variable distinct from "x" and which does not occur in "f" or "g". Actually, to make P well-defined as a map from concatenative lambda-forms to applicative lambda-forms (not merely over the equivalence classes of such forms), we need to restrict "f" (or, alternatively, "g") to be either a variable or a quotation (but not a concatenation) in order to force a unique parsing of the concatenative expression. This is a technical detail which may or may not be important to us, depending on what we're trying to do with the map.
It would take some work (which I'll skip, for now) to show that this map respects the reduction rules of the two systems (i.e., that f reduces to g if and only if P(f) reduces to P(g)).
Anyhow, although the map may at first appear strange and complicated, it really isn't so bad. Essentially, it maps any concatenative program to a function whose first parameter is treated as a continuation (hence the name "c"); an additional parameter is taken (in curried fashion, of course) for each input stack item, top item first; the body of the function is an application of the continuation to each output stack item. Note that although concatenation maps to function composition (a nifty property), we aren't exactly modelling concatenative programs as functions from a stack to a stack (if we were, concatenation would actually need to map to _reverse_ composition). It's possible to construct a map which does precisely that, but it's considerably more complicated and not as natural, in my opinion.
Anyhow, here are what some standard Joy combinators map to by P (Exercise: verify these):
P(id) = \c.c == I
P(i) = \cx.xc == T
P(dup) = \cx.cxx == W
P(zap) = \cx.c == K
P(cons) = \cxy.c(\d.ydx) == \cxy.c(Cyx)
P(cat) = \cxy.c(\d.x(yd)) == \cxy.c(Bxy)
P(dip) = \cxy.x(cy) == CB
where I, B, C, W, and K are the following standard applicative combinators:
Ix == x
Bfgx == f(gx)
Cfxy == fyx
Wfx == fxx
Kxy == x
Now, it is well-known that {I, B, C, W, K} form a complete applicative basis. So far, we have I, W, and K, so we only need to show that we can construct B and C.
Well, B comes easily: Just apply I to P(cat) (let's define Cat = P(cat)). We get
Cat I
== (\cxy.c(Bxy)) I
== \xy.I(Bxy)
== \xy.Bxy
== B
Now, we can almost get C by applying I to P(cons) (defining Cons = P(cons)):
Cons I
== (\cxy.c(Cyx)) I
== \xy.I(Cyx)
== \xy.Cyx
== CC
This is just a varient of C that takes its first two parameters in reverse order. And there is a construction of C from this combinator (which I found by computer search, although it's quite simple):
C = CC(CC)(CC)
The verification:
CC(CC)(CC)fxy
== C(CC)(CC)fxy
== CCf(CC)xy
== C(CC)fxy
== CCxfy
== Cfxy
So there we have it! The image of P is a complete applicative set! What is perhaps even more surprising is that we didn't need to use the image of "i" or "dip". So the image under P of the _incomplete_ set {id, dup, zap, cons, cat} is a complete applicative set. This set, {id, dup, zap, cons, cat}, is not only incomplete, it's really severely incomplete. These are proper combinators, none of which performs any reordering on its parameters; therefore it is impossible to construct "dip", or even "swap", from them. Moreover, none of them perform dequotation, so it is not even possible to construct "i" from them.
In any case, note that I'm not claiming P is surjective (i.e., that it maps onto to every applicative combinator), only that it maps onto a complete subset of the applicative combinators. If P (or rather, the version of P which operates on equivalence classes of lambda-forms rather than the forms themselves -- call it P^, "P-hat") is surjective, then it would be an isomorphism between the concatenative and applicative systems of combinators (the well-definedness and injectivity of P^ follow from the fact that P respects reduction). I doubt that such an isomorphism exists but don't know how to prove this. This is really the fundamental question about the relationship between concatenative and applicative combinators: are the two systems isomorphic?
Well, actually, this is two questions, since there are two main versions of both systems, namely one with the "principle of extensionality" (i.e., one with an "eta-reduction" rule, ensuring "[] dip == id" in the concatenative system, and "BI == I" in the applicative), and one without. The map P above is designed to work either way (although the two systems must either both have, or both not have, eta-reduction). The part to be careful with is
P(x) = \c.xc
in the definition of P. If we have eta-reduction, we can replace this with
P(x) = x
However, if we don't have eta-reduction, this change will break the essential property of P, i.e., that it respects reduction. For then we would have
P([x] y\ y)
= \c.(\d.dx)((\ey.ye)c))
=> \c.(\d.dx)(\y.yc)
=> \c.(\y.yc)x
=> \c.xc
P(x) = x
where
[x] y\ y => x
but not
P([x] y\ y) => P(x)
since without eta-reduction, \c.xc does not reduce to x. So P, in this case, would not respect reduction. For this argument, I'm using a special case of the Church-Rosser property, that an (applicative) combinator has a unique normal form (i.e., a form with no redexes) if it has one at all. (The general case states that if A, B, and C are lambda-forms with A=>B and A=>C, then there is a form D such that B=>D and C=>D. This essentially says that if you can get a form to reduce to two different forms (by choosing different redexes to reduce), you can perform further reduction to converge again to a common form. This an intuitive idea which is nevertheless highly non-trivial to prove). Although I'm not relying on it here, it would also be nice to know if an analogous "Church-Rosser" property holds for concatenative combinators.
> [B] [A] cake == [[B] A] [A [B]]
>
> Clearly, A and B are not siblings here. Of course, constructing concat
> is possible, which obviously makes siblings out of A and B, but is it
> somehow less theoretically pure to have a basis in which the siblings
> are not explicit in the provided basis combinators?
Well, the construction of "cat" in terms of {cake,k} relies on transparent quotation; ultimately, it's the same construction as this one from i, dip, and cons:
cat == [[i] dip i] cons cons
which works like so:
[B] [A] [[i] dip i] cons cons
== [B] [[A] [i] dip i] cons
== [[B] [A] [i] dip i]
== [[B] i [A] i]
== [B A]
To construct "cat" from {cake,k}, transparent quotation is fundamentally necessary. For, if we assume opaque quotation and consider reducing the expression
[B] [A] x
where "x" is a combination over {cake,k}, we see that each reduction step preserves the property that no quotation contains (in the shallow sense) more than one (dequoted) indeterminate, so that we can never reach [B A]. Therefore, "cat" is inconstructible in {cake,k} under opaque quotation. So, {cake,k} is not complete in as strong a sense as, for example, {q,k} (from which all combinators are constructible, even assuming opaque quotation):
[B] [A] q == [[B]] [A B]
[B] [A] k == A
In addition, I'd say "q" is a bit nicer than "cake" since, aside from being simpler, it has the pretty property that it produces a (unit) quotation and a concatenation, which correspond precisely to the two syntactic constructions of the language. This may not be particularly significant in the grand scheme of things, but we have to admit that it's a bit nifty. So I'm perfectly fine with "condemning {cake,k} to contempt and contumely" :-)
> -William (Billy)
- Brent
William Tanksley, Jr — 2007-02-24 22:17:02
Brent L Kerby <
bkerby@...> wrote:
> > Let me first say that recasting combinatorial operations in terms of a
> > flat concatenative language has made it MUCH easier for me to reason
> > about them. I definitely don't understand them completely, but somehow
> > the reasoning seems more in line with my brain's workings. One of my
> > friends felt the same way. Am I just mentally disturbed from years of
> > Forth use and abuse, or is there actually something simpler here?
> Well, although building flat bases (e.g., {o, k}) has been great fun, to me
> it seems like this system is only simpler in a fairly artificial way.
It's simpler in a syntactic sense, not in a semantic sense. That's not
artificial; syntax is a fundemental attribute of a language. However,
the conversion we did to acheive flatness was a tradeoff; our
semantics became in some ways more complex, and undeniably it takes
many more characters to express the same meaning.
So although I don't agree that the simplicity is any kind of illusion,
I certainly also agree that our flat languages (so far) are not
describable as "superior" to the old systems -- except perhaps for
very narrow purposes (but that's always true).
One of the narrow realms of superiority is how we can measure
complexity; a flat expression can be expressed as a bitstring, while a
non-flat expression cannot.
Another narrow realm is that of understanding; it's fundamentally true
that one can always break apart a flat expression in any way that
helps one understand it; there's no "wrong" way to break it apart.
There are many wrong ways to break apart a tree, and few of them are
obvious while the tree is encoded "on paper".
> This is because the system, in a sense, is not flat at all. True, we can
> express programs using flat syntax; but, once these programs start
> executing, they start building programs on the stack that aren't flat.
> So the system has to deal with non-flat programs in the course of
> execution anyway.
I agree. I don't see this as any kind of problem, but I do suspect
that there are better ways to express things in flat notation than the
one we've chosen. The semantics we're using, in particular, were
designed for a different purpose.
> And to do anything non-trivial the programmer needs non-flat programs,
This seems to me to be fundamentally true, simply a tautology,
starting with the axiom "every semantically flat program is trivial."
I don't see any way around that axiom; it makes sense.
> only he isn't allowed to express them directly, but rather is forced to
> construct them in a flat manner, with his hands tied behind his back,
> so to speak.
Well, this isn't fair in general. Every language ties your hands
behind your back to some extent; it's always easier to say some things
than it is to say others. The same complaint could be made about
dataflow languages in general when comparing them to parameter-based
languages, for example -- yet I'd argue that although there truly is a
tradeoff, the tradeoff is fair.
I can't argue this about the languages we've built. There is a
tradeoff, but the tradeoff doesn't seem entirely fair.
> So, we ask, is it possible to modify our approach to give us a more
> "genuine" flat system? Well, to really be flat, we would have to not
> be able to push programs onto the stack, since that's the first level
> of non-flatness. And if we can't do that, that leaves literally nothing
> left that we can do, assuming we've started with just the concatenative
> combinators, where programs are the only type of data. So, a "genuine"
> flat system would have to be quite different. Special support would be
> needed for loops and conditionals, since these could no longer be
> implemented with the (rather meager) remaining set of combinators
> (which could only shuffle the stack, not perform restructuring or
> execution).
I don't know if your definition of "genuinely flat" is correct. Your
requirement for "special support for loops and conditionals" requires
semantic non-flatness, though, by any definition I can see. A
conditional or loop, by definition, has to choose whether or not to
execute a function, which means that the function has to be passed to
the conditional in some way.
One conceivable possibility of doing this would be to switch from our
single-stack definition to a stack and a queue (the queue contains the
continuation), and allow a "combinator" to modify the queue. I don't
know what, if anything, such a system would look like; I haven't
pursued it because I have some other requirements percolating that it
doesn't seem like such a system could fit.
> I don't know. The way I see it, non-flatness is roughly equivalent
> to the ability to do higher-order programming, which is a good
> property of a system.
Semanticly, yes. We've already proven that this is NOT syntactically
true -- and that is an important result.
> But, if you can show me a really nice flat programming language,
> you may be able to change my mind :-)
:-)
I'm very grateful for your help on this; it's been educational and
fun. I don't know if I'll ever come up with a nice _completely_ flat
programming language; I may possibly come up with some ideas which can
make a nice language flatter.
One thing I'm looking at now is the fact that the word "flat" implies
that a function can be split in half. But our languages only can
express a single function -- this means that they can't take advantage
of their own flatness.
The obvious thing that pops to mind is to add a "dictionary" data
structure, and perhaps a couple of "combinators" that do a lookup in
it or add a definition to it. This makes spaghetti code out of our
programs, which is certainly one way of handling such things :-/.
A less obvious solution (better than my dictionary, but still not what
I want) was suggested by Landau in his research on genetic algorithms
(and related things); I would give you a link, but citeseer isn't
working. In short, he has his programs build a transition network, and
then executes that.
I'll respond more later. This is already plenty long.
> - Brent
-William
William Tanksley, Jr — 2007-03-03 01:33:21
Brent L Kerby <
bkerby@...> wrote:
> > I find it interesting that completeness is different between
> > applicative and concatenative languages (for example, {s,k} is a
> > complete applicative basis, but not is not complete when
> > concatenative).
> Right. When we map the applicative combinators to concatenative
> ones in the obvious way, the image of this map is not a complete
> (concatenative) set. But it's interesting to note that, in the other
> direction, things turn out differently. I.e., the image of the natural
> map (or at least, what I'm calling the natural map) from
> concatenative combinators to applicative ones _is_, remarkably
> enough, a complete applicative set.
This would seem to generally fit my theory -- that applicative syntax
is more powerful in its greater complexity, because an applicative
syntax allows a language to directly express the concept of
"siblings". Whenever a function takes two parameters, those parameters
are "siblings". The only way to connote the concept of siblings in a
concatenative language is to build the putative siblings into a list.
> So there we have it! The image of P is a complete applicative set!
> What is perhaps even more surprising is that we didn't need to
> use the image of "i" or "dip".
I noticed the lack of need for "i" much earlier. At first I thought
this was a problem with our notation (since the applicative notation
doesn't even have a concept of dequotation), but I believe now that
it's not a problem: it's a result of how concatenative notation can't
denote siblings, so a runtime concept (quotation) must take its place.
> In any case, note that I'm not claiming P is surjective
> (i.e., that it maps onto to every applicative combinator),
> only that it maps onto a complete subset of the applicative
> combinators.
I know many of those terms, but I don't know what "complete subset"
means. Does it mean "a subset of combinators which includes a complete
base"? If so, that makes sense.
> If P (or rather, the version of P which operates on equivalence
> classes of lambda-forms rather than the forms themselves --
> call it P^, "P-hat") is surjective, then it would be an isomorphism
> between the concatenative and applicative systems of
> combinators (the well-definedness and injectivity of P^ follow from
> the fact that P respects reduction). I doubt that such an isomorphism
> exists but don't know how to prove this. This is really the fundamental
> question about the relationship between concatenative and
> applicative combinators: are the two systems isomorphic?
This last question definitely nags at me in one way, which I can't
define. I have a nagging doubt that we're missing something.
In another way it seems evident (after much exploration) that the
systems are "equivalent" (in the sense that a program in one can
always be expressed in the other). But I don't know too much about
isomorphism, except that it's more complex than that... I've only had
a general undergrad intro to modern algebra (groups, fields, algebras,
etc).
> For this argument, I'm using a special case of the
> Church-Rosser property, that an (applicative) combinator
> has a unique normal form (i.e., a form with no redexes) if
> it has one at all. (The general case states that if A, B, and
> C are lambda-forms with A=>B and A=>C, then there is a
> form D such that B=>D and C=>D. This essentially says
> that if you can get a form to reduce to two different forms
> (by choosing different redexes to reduce), you can perform
> further reduction to converge again to a common form. This
> an intuitive idea which is nevertheless highly non-trivial to
> prove). Although I'm not relying on it here, it would also be
> nice to know if an analogous "Church-Rosser" property holds
> for concatenative combinators.
Is this something of what you mean by "isomorphism"? That would indeed
be an awesome property. There are a lot of very simple things that are
obvious about flat concatenative languages (for example, it makes
sense that once you understand the meaning of a bitstring without
context, you therefore know its meaning in any context), but there are
also a lot of things that seem to take more work to parse out (for
example, some "optimizations" seem to be very complex to express
formally).
(Sorry for the informal terminology. I'm very new at this.)
> > [B] [A] cake == [[B] A] [A [B]]
> > Clearly, A and B are not siblings here. Of course, constructing concat
> > is possible, which obviously makes siblings out of A and B, but is it
> > somehow less theoretically pure to have a basis in which the siblings
> > are not explicit in the provided basis combinators?
> Well, the construction of "cat" in terms of {cake,k} relies on transparent
> quotation; ultimately, it's the same construction as this one from i, dip,
> and cons:
Ah! And this helps me understand what "transparent quotation" means at
a semantic level. My implementation (01.py) clearly uses transparent
quotation, since it executes combinators at the earliest opportunity
(in fact, I think it actually might execute them too soon... I need to
work on that).
>Therefore, "cat" is inconstructible in {cake,k} under opaque
>quotation. So, {cake,k} is not complete in as strong a sense
>as, for example, {q,k} (from which all combinators are constructible,
>even assuming opaque quotation):
YES! I'm starting to "get it".
> In addition, I'd say "q" is a bit nicer than "cake" since, aside from
> being simpler, it has the pretty property that it produces a (unit)
> quotation and a concatenation, which correspond precisely to
> the two syntactic constructions of the language. This may not
> be particularly significant in the grand scheme of things, but we
> have to admit that it's a bit nifty.
Hmmm... I'm a ways from being knowledgable enough to be able to admit
that. I'll take your word for it, after I play around with your
joys.exe program a bit more. I'm not sure how I'm going to get any
different results; in particular, getting a concat seems to be
essential to completeness. I suspect that the only way to do anything
else would be to have a combinator which took more parameters (and
that just seems like it'd be less efficient).
Hmm again.
> So I'm perfectly fine with "condemning {cake,k} to contempt and
> contumely" :-)
It's one of the things I'm qualified to do, having studied ancient literature.
Would you like fries with that?
> - Brent
-Billy
Manfred Von Thun — 2007-03-09 02:43:28
On 22/2/07 5:55 PM, "Brent L Kerby" <
bkerby@...> wrote:
>
>
>
> [..]
> - Brent
>
> P.S., Manfred,
>
> Christopher and I are using "b" to refer to the following combinator:
>
> [Z] [Y] [X] b == [[Z] Y] X
>
> which is the concatenative version of the classical "B" combinator (as "s",
> "c", "w", "k", and "i" are the concatenative versions of the classical S, C,
> W, K, and I combinators), while your "b" is
>
> [Y] [X] b == Y X
>
> I didn't notice you had already defined "b", so sorry about that; I wasn't
> intending to create a conflict in the notation.
>
Thanks for the clarification, my mistake really.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-03-09 03:26:09
On 24/2/07 9:45 PM, "Brent L Kerby" <bkerby@...> wrote:
[..]
> But, if you can show me a really nice flat programming language, you may be
> able to change my mind :-)
>
Not a NICE flat programming language, but interesting in the present
context:
machine language or assembler.
Consider a very small procedural programming language with nesting: A
statement is either an assignment, or a compound statement which is a
sequence of statements, or a conditional consisting of a test and a
statement, or a loop consisting of a test and a statement. (Not even
procedure calls allowed). So a statement can contain other statements,
nested arbitrarily deeply. Nothing flat here.
Compile into machine language or assembler. Assignments translate into a
sequence of instructions, but that is of no interest here. Compound
statements translate into the sequence of instructions produced by the
sequence of statements, also of no interest. But interestingly, conditionals
and loops are translated into a FLAT sequence of instructions containing
two new instructions that are not in the source language: conditional and
unconditional JUMP instructions. We also have the notion of a program
counter, which is simply incremented by most instructions. Only the JUMP
instructions change the program counter explicitly.
We have: nested source language, flat target language. Price: extra
instructions in the target language, plus new concept.
A possible technique for flattening a concatenative language? Probably
yes. But the flattened version will not be pretty.
If the procedural language also has callable procedures, there is another
level of nesting. It is flattened by introducing a runtime stack and new
instructions CALL and RETURN for pushing and popping return addresses.
Powerful? Yes. Pretty? No.
Maybe this will give people some ideas about flattening concatenative
languages.
- Manfred
[Non-text portions of this message have been removed]
John Cowan — 2007-03-09 05:42:44
Manfred Von Thun scripsit:
> We have: nested source language, flat target language. Price: extra
> instructions in the target language, plus new concept.
Actually, we can do without them. The machine whose sole instruction
is "subtract 1 from data item D, and if it is now zero, jump to
instruction J, otherwise continue" is known to be Turing-complete.
Of course you end up using a lot of them.
--
John Cowan
http://ccil.org/~cowan cowan@...
We want more school houses and less jails; more books and less arsenals;
more learning and less vice; more constant work and less crime; more
leisure and less greed; more justice and less revenge; in fact, more of
the opportunities to cultivate our better natures. --Samuel Gompers
Manfred Von Thun — 2007-03-09 07:31:26
For a long time I had been dreaming of static type checking for Joy, and
perhaps even a Joy compiler of some kind. Only recently did I have a lucky
thought: why not look at Prolog as an implementation language? (Prolog =
PROgramming in LOGic - if you are willing to do violence to anybody¹s
definition of logic. Apart from the name, a wonderful language with
backtracking and unification(two sided pattern matching).
I had had an some experience with Prolog starting 25 years ago, but dropped
any involvement after the Japanese ³5-th generation language² programme
faded. But I had written some very early Joy interpreters in Prolog.
Found an old SWI-prolog on my inherited home computer, and started
what turned out to be very fruitful 6 weeks.
Implementing core Joy is ridiculously simple. There are transformation
rules for turning one stack into another:
swap turns [X, Y | S] into [Y, X | S].
+ turns [I, J | S] into [K | S] :- K is I + J.
This readable syntax is what Prolog allows you to do. The four occurrence of
³ | S mean ³the rest of the stack². The definition for swap has no
condition, the one for + has as condition the little bit after the :-
³turnstyle². Everything else is in the same style, even the combinators
I am leaving out the annoying fact that Prolog needs a comma as a separator
between listi items. I am also leaving out that I use a simple preprocessor
(written in Prolog, of course), which ³decorates² literals in programs, or
the stack, or in quotations, with type information. To keep things simple,
at the moment I only allow two types: numbers and lists.
For core Joy I only have the basic stack and list shufflers, which all do
not have a body in their definition, just like swap above. Only one
arithmetic operator, +, so far, and quite a few combinators including the
recursive step and map. That is the core interpreter.
In principle it sounds easy to turn any interpreter into a compiler: in the
program to be compiled, for each instruction of the source language, emit
the instructions of the target language which the interpreter would be
executing if it were running that program.
In practice this is a dreadful undertaking if the implementation language is
C, as it is in my version on the web. Essentially one would be writing
something as complex as the original interpreter, or more complex. Also, it
is not easy to have to maintain two large programs, especially if the
language is developing. Better to have only one version, and have a program
to turn the interpreter into the compiler. Or have a definitional version
(perhaps in M4), which can produce the interpreter or the compiler.
Prolog (like Joy) has the wonderful capability of allowing one to look at
the bodies of definitions (by ³clause²), doing something with these bodies
and constructing something that can later be executed (by ³call²). Languages
such as the Algol descendents cannot do this. I do not know whether (the
interpreted implementations of) the Lisps can (John Cowan: ?).
So Prolog allows Prolog programs to inspect other Prolog programs like the
above snippets for swap and +. This means it is extremely simple to write
all kinds of meta programs.
One kind are interpreters, which mimic the operation of Joy with some
variation. For example, I have written a simple tracer which behaves like
the i combinator but also writes out every step taken during the execution
of the quoted parameter, even if that quotation contains calls to other
combinators like the recursive step and map and their parameters. There
are several variations to this general idea.
The other kind are compilers which, just like i again, expect a quotation
(written in Joy) and leave behind a translation into Prolog. One interesting
feature of this process is that stack and list shufflers just disappear from
that translation, because all their work is essentially summarised in the
stack description for the before- and after-stack of the entire quotation.
Redundant stack and list operations just disappear. Optimisation for nix!
The output of the compilation is a typically rather short program in Prolog
which needs to be called to do any work. Compilation and calling satisfies
the equation:
compile call == i
In fact there are already variations on the compile/call theme.
I am still learning about the various possibilities of meta programs, and I
intend to explore the area further, especially since it is so easy to do in
Prolog.
So far I do not have definitions in Joy. I have left this for later, because
the intention is of course to store not the Joy form of a program but
preferably its compiled form in Prolog.
I¹ll be happy to answer any questions. Also, I intend to report further on
any progress. But I will have to learn how to move files from my PC at home
to my Emac here at (what used to be) work. Only then will I be able to send
examples to this group.
To the concatenative language smiths: best wishes with you efforts.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-03-09 07:38:41
On 9/3/07 4:42 PM, "John Cowan" <
cowan@...> wrote:
>
> Manfred Von Thun scripsit:
>
>> > We have: nested source language, flat target language. Price: extra
>> > instructions in the target language, plus new concept.
>
> Actually, we can do without them. The machine whose sole instruction
> is "subtract 1 from data item D, and if it is now zero, jump to
> instruction J, otherwise continue" is known to be Turing-complete.
> Of course you end up using a lot of them.
So, are we hoping for a single instruction flat concatenative language?
[Non-text portions of this message have been removed]
Christopher Diggins — 2007-03-09 07:54:11
> For a long time I had been dreaming of static type checking for Joy,
Have you looked at the most recent Cat paper
(
http://www.cat-language.com/paper.html)? It could prove to be a
useful starting point for designing a type system and type checker for
Joy (and even a type inference algorithm).
Cheers,
Christopher
William Tanksley, Jr — 2007-03-09 15:16:03
Manfred Von Thun <
m.vonthun@...> wrote:
> On 24/2/07 9:45 PM, "Brent L Kerby" <bkerby@...> wrote:
> > But, if you can show me a really nice flat programming language, you may be
> > able to change my mind :-)
> Not a NICE flat programming language, but interesting in the present
> context: machine language or assembler.
I've been hammering this in my mind, but I can't get it to work out right.
> Compile into machine language or assembler. Assignments translate into a
> sequence of instructions, but that is of no interest here. Compound
> statements translate into the sequence of instructions produced by the
> sequence of statements, also of no interest. But interestingly, conditionals
> and loops are translated into a FLAT sequence of instructions containing
> two new instructions that are not in the source language: conditional and
> unconditional JUMP instructions. We also have the notion of a program
> counter, which is simply incremented by most instructions. Only the JUMP
> instructions change the program counter explicitly.
The problem is that machine language/assembler uses explicit offsets
to express jumps and branches, and those destroy referential
transparency. In effect, you can't split a valid program into two
arbitrary parts and have the two parts still be valid -- if you cut in
the middle of a branch, the branch will then lead off into nowhere.
> A possible technique for flattening a concatenative language? Probably
> yes. But the flattened version will not be pretty.
Pretty is not yet my concern. But this isn't flat.
But I do suspect there's something to this. I just have to figure out
what I'm missing.
> - Manfred
-Billy
William Tanksley, Jr — 2007-03-09 15:19:17
Manfred Von Thun <
m.vonthun@...> wrote:
> "John Cowan" <cowan@...> wrote:
> > Actually, we can do without them. The machine whose sole instruction
> > is "subtract 1 from data item D, and if it is now zero, jump to
> > instruction J, otherwise continue" is known to be Turing-complete.
> > Of course you end up using a lot of them.
> So, are we hoping for a single instruction flat concatenative language?
Grin. Unfortunately, that's neither single-instruction nor flat. Its
instruction stream consists of (data index ,jump offset) pairs, so in
effect if both are 8-bit you have 16-bit instructions; that's 64,000
instructions. It's not flat because, again, you can't break apart a
valid definition and get as a result two valid definitions.
-Billy
John Cowan — 2007-03-10 20:31:27
Manfred Von Thun scripsit:
> Prolog (like Joy) has the wonderful capability of allowing one to
> look at the bodies of definitions (by "clause"), doing something with
> these bodies and constructing something that can later be executed (by
> "call"). Languages such as the Algol descendents cannot do this. I do
> not know whether (the interpreted implementations of) the Lisps can
> (John Cowan: ?).
Very few Lisps allow you to recover the source form of a definition
from its executable form (decompiling), but essentially all allow you
to evaluate source at run time, and some allow you to go from source to
executable form at run time (compiling). Even Lisp interpreters
generally do at least some compiling (expanding macros, for example).
--
John Cowan
cowan@...
I amar prestar aen, han mathon ne nen,
http://www.ccil.org/~cowan
han mathon ne chae, a han noston ne 'wilith. --Galadriel, LOTR:FOTR
Manfred Von Thun — 2007-03-14 02:54:15
On 9/3/07 6:54 PM, "Christopher Diggins" <cdiggins@...> wrote:
I did look at your paper and read it with great interest. I am not really
competent
to judge the details, so I cannot help you in any substantial way. I had
some
superficial acquaintance with natural deduction rules for typing, but have
never
used the them in earnest. But it is a formalism which I should study and
perhaps
use to describe typed Joy. Actually the type inference that I use for the
Joy-to-Prolog
compiler is so automatic when writing in Prolog that it is barely visible.
It is simply
this:
IF a turns S into T1
AND b turns T2 into U1
AND c turns U2 into V
THEN [a b c] turns S into V
where there have to be the unifications T1=T2 and U1=U2. All that is
automatic.
There are two compilers at present, both about 18 lines long. One produces
lengthy Prolog code which is still more efficient than the Joy source. The
other produces optimised Prolog code in which all the stack-and
list-shuffling
is done at compile time and leaves no trace in the Prolog code. All thanks
to
Prolog¹s unification.
I also had a look at your implementation in C#. It looks much cleaner than
my Joy implementation. Thanks in part perhaps to C#, but only in part.
You are also a better programmer than I am. Well done.
- Manfred
>
>
>> > For a long time I had been dreaming of static type checking for Joy,
>> >
> Have you looked at the most recent Cat paper
> (http://www.cat-language.com/paper.html)? It could prove to be a useful
> starting point for designing a type system and type checker for Joy (and
> even a type inference algorithm).
>
> Cheers, Christopher
>
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-03-14 05:11:16
Thanks for this, I had a vague suspicion that it might be so for
the Lisps. In fact for any interpreter written in some implementation
language it seems that the natural way to do it is to translate it into an
intermediate form from which the source cannot be retrieved. But one could
translate into a (passive) data structure which allows recovering the source
form and can also be interpreted.
On the two occasions when I tried to understand ³The Art of the Meta-Object
Protocol² (or similar), I failed to get the point. The meta-interpreters and
meta-compilers that I am writing now all look at the definitions of the
Joy-in-Prolog interpreter and do something with it. Maybe something will
click in my mind eventually. I was lucky having (re-)stumbled upon Prolog so
early.
On 11/3/07 7:31 AM, "John Cowan" <cowan@...> wrote:
> Manfred Von Thun scripsit:
>
>> > Prolog (like Joy) has the wonderful capability of allowing one to look at
>> the
>> > bodies of definitions (by "clause"), doing something with these bodies and
>> > constructing something that can later be executed (by "call"). Languages
>> such
>> > as the Algol descendents cannot do this. I do not know whether (the
>> > interpreted implementations of) the Lisps can (John Cowan: ?).
>> >
> Very few Lisps allow you to recover the source form of a definition from its
> executable form (decompiling), but essentially all allow you to evaluate
> source at run time, and some allow you to go from source to executable form
> at run time (compiling). Even Lisp interpreters generally do at least some
> compiling (expanding macros, for example).
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-03-14 06:04:11
On 10/3/07 2:16 AM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
> I've been hammering this in my mind, but I can't get it to work out right.
>
>> > Compile into machine language or assembler. Assignments translate into a
>> > sequence of instructions, but that is of no interest here. Compound
>> > statements translate into the sequence of instructions produced by the
>> > sequence of statements, also of no interest. But interestingly,
>> conditionals
>> > and loops are translated into a FLAT sequence of instructions containing
>> two
>> > new instructions that are not in the source language: conditional and
>> > unconditional JUMP instructions. We also have the notion of a program
>> counter,
>> > which is simply incremented by most instructions. Only the JUMP
>> instructions
>> > change the program counter explicitly.
>> >
> The problem is that machine language/assembler uses explicit offsets to
> express jumps and branches, and those destroy referential transparency. In
> effect, you can't split a valid program into two arbitrary parts and have
> the two parts still be valid -- if you cut in the middle of a branch, the
> branch will then lead off into nowhere.
>
Since the language had assignments, there was no referential transparency to
start with. But take the purely functional subset of just about any language
(Lisp Pascal C..), and translate the expression f(g(a),h(b)) into assembler.
In the definitions of f(,) g() and (h() there will be some code ending with
a return (which also restores the program counter from the run time stack).
The corresponding calls all push the program counter. The entire expression
assembles into something like the following five instructions: push(a),
call(g), push(b), call(h), call(f). This is just postfix code, where each
operation does something to various parts (stack, stack pointer, program
counter,..) of the actual or virtual machine. And the concatenation of the
five operations computes the composition of the five functions computed by
the five parts. Concatenative according to my definition:
If P is a program which computes a function F, and Q is a program which
computes a function G, then the concatenation P Q of the two programs
computes the composition F G of the two functions.
But I suspect that it is not by your definition. (I got a similar impression
some time much earlier). You mean (or you also mean, or you mean by ³flat²):
If P is a program consisting of concatenated parts p1 p1 .., and P computes
a function F, then each of the parts compute functions f1 f2 .., and F is
their composition.
This happens to be satisfied by my assembled expression, but it is not part
of my definition of concatenative. It is true that cutting in the middle of
a branch leads somewhere else, but where it leads is still dependent on what
the cut inserts of deletes.
Of course nobody expects cuts to be permissible inside an instruction. Thus
call(h) does not have 3 parts: cal l( h).
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-03-14 14:43:51
William Tanksley, Jr — 2007-03-14 14:26:39
Manfred Von Thun <
m.vonthun@...> wrote:
> "William Tanksley, Jr" <wtanksleyjr@...> wrote:
> > The problem is that machine language/assembler uses explicit offsets to
> > express jumps and branches, and those destroy referential transparency. In
> > effect, you can't split a valid program into two arbitrary parts and have
> > the two parts still be valid -- if you cut in the middle of a branch, the
> > branch will then lead off into nowhere.
> Since the language had assignments, there was no referential transparency to
> start with.
Oops! I meant to type "destroy flatness", not "destroy referential
transparency". Oops.
Doggone it, one slip like that and my message makes no sense at all.
> counter,..) of the actual or virtual machine. And the concatenation of the
> five operations computes the composition of the five functions computed by
> the five parts. Concatenative according to my definition:
> If P is a program which computes a function F, and Q is a program which
> computes a function G, then the concatenation P Q of the two programs
> computes the composition F G of the two functions.
That's concatenative by my definition as well.
> But I suspect that it is not by your definition. (I got a similar impression
> some time much earlier). You mean (or you also mean, or you mean by ³flat²):
The latter -- I try to use the word "concatenative" in the same way
you do; I try to use the word "flat" to mean:
> If P is a program consisting of concatenated parts p1 p1 .., and P computes
> a function F, then each of the parts compute functions f1 f2 .., and F is
> their composition.
...approximately. Actually, I define it using the hand-waving but
intuitive concept of "splitting" a function into two parts, each of
which is a valid program for all possible splits. I can make this more
rigorous by admitting that "all possible splits" includes some splits
that don't make intuitive sense, such as a split between characters of
a literal; thus I use the idea of the quantitative ratio "flatness",
where you compare the number of possible places to perform a split
with the number of splits that produce two valid programs. Our ik and
ok languages are perfectly flat; there's no possible split that
produces invalid programs, even if you get really pedantic and start
splitting between odd bits.
However, in general, similar languages will have similar possible
splits, so when we're not comparing very different languages -- for
example, the compare-and-branch versus the ik/ok languages -- we can
ignore nitpicking splits that are equally impossible in both
languages.
> This happens to be satisfied by my assembled expression, but it is not part
> of my definition of concatenative.
Agreed. That's why I use the combined expression "flat concatenative"
to describe my language.
> It is true that cutting in the middle of
> a branch leads somewhere else, but where it leads is still dependent on what
> the cut inserts of deletes.
Well, a cut doesn't insert; it only deletes.
> Of course nobody expects cuts to be permissible inside an instruction. Thus
> call(h) does not have 3 parts: cal l( h).
Right -- it's intuitively not reasonable to split inside an
instruction. I don't count that against the language :-). On the other
hand, if you can't cut inside the instruction, you have to count every
bit, so one can't claim the compare-and-branch language has only one
instruction; each instruction uses all /n/ bits of its encoding, so
such a language has 2^n instructions.
> - Manfred
-Billy
Christopher Diggins — 2007-03-15 16:29:12
On 3/13/07, Manfred Von Thun <
m.vonthun@...> wrote:
> On 9/3/07 6:54 PM, "Christopher Diggins" <cdiggins@...> wrote:
>
> I did look at your paper and read it with great interest. I am not really
> competent
> to judge the details, so I cannot help you in any substantial way. I had
> some
> superficial acquaintance with natural deduction rules for typing, but have
> never
> used the them in earnest. But it is a formalism which I should study and
> perhaps
> use to describe typed Joy.
A great book about the typing formalism which I think you may enjoy
(to be honest I found it very hard to understand, but I am not
formally educated) was Types and Programming Languages by Benjamin
Pierce which sums up the state of the art of type systems.
I hope to write an extended version of my paper which doesn't presume
a previous knowledge of type theory.
> Actually the type inference that I use for the
> Joy-to-Prolog
> compiler is so automatic when writing in Prolog that it is barely visible.
> It is simply
> this:
>
> IF a turns S into T1
> AND b turns T2 into U1
> AND c turns U2 into V
> THEN [a b c] turns S into V
>
> where there have to be the unifications T1=T2 and U1=U2. All that is
> automatic.
Now I see! That is brilliant! in a previous version of the Cat
compiler (which did type-inference) I ended up having to write a type
unifier from scratch. In effect I wrote a mini-prolog. I am surprised
that your technique of expresing types in a logic language (are there
others besides Prolog?) isn't used more often. Perhaps it is one of
those great ideas hiding in plain sight?
> There are two compilers at present, both about 18 lines long. One produces
> lengthy Prolog code which is still more efficient than the Joy source. The
> other produces optimised Prolog code in which all the stack-and
> list-shuffling
> is done at compile time and leaves no trace in the Prolog code. All thanks
> to
> Prolog¹s unification.
Very elegant!
> I also had a look at your implementation in C#. It looks much cleaner than
> my Joy implementation. Thanks in part perhaps to C#, but only in part.
> You are also a better programmer than I am. Well done.
Thank you, you make me blush. I am actually rewriting the parsing
engine so that it is easier to modify and extend. Afterwards I will
try to reimplement the type checking/inference engine (but first I
need to extend the type system with recursive types ... a long story
but I will say that they are neccessary to accurately express the type
of certain combinators such as Y and M).
Perhaps this may encourage others on the list to try their hand at
implementing their own concatenative languages. Anyway, C# is a very
pleasant and easy to use language. I find it is much easier to be
productive using C# than C or C++.
On other topic, for those interested I am now in the middle of
implementing a version of Cat with optional named parameters. This
will become the primary Cat variant (the one I plan on using in an
upcoming introductory programming book). This version of Cat gets
translated into the original point-free (i.e. no parameter names) Cat.
I'm taking a cue from Postscript with its different levels. In the end
the specification of Cat will likely have a half-dozen variants which
are expressed in terms of each other.
> - Manfred
Cheers,
Christopher
Manfred Von Thun — 2007-03-22 05:23:30
Here is a flat concatenative language which I shall call L.
After a lot of discussions on this group I now have some intuitive
understanding of what
a flat language is. I shall discuss this language L in relation to Joy.
The problem seems to be how to handle apparent non-flatness due to
quotations/lists, which can be nested. I need to introduce the notion of a
waiting room, or ante-room, or briefly, a foyer. This is where incoming
items form a queue (perhaps similar to Stevan¹s Y queue in his XY language).
At certain times a queue in a foyer gets sent elsewhere and the foyer is
destroyed. A foyer is created by the special item ³[³, and destroyed by the
special item ³]². I also need a notation for describing foyers: a newly
created empty foyer is written <>, an after a ³dup² item arrives the foyer
is written <dup>, after a ³*² item arrives it is written <dup *>. But a
foyer is not a list, in fact a foyer can contain lists. Foyers cannot be
nested, but there is a stack of foyers: I shall write this stack with the
topmost item on the right. When a foyer is destroyed by ³]², the contained
queue is sent to the foyer below as a list.
Here is a contrived example to illustrate several nestings. Let the program
be
9999 [ [2 3] [dup *] map ] dip . # should produce: [4 9] 9999
The program starts with a stack containing just one empty foyer. I shall now
trace the execution of the program by writing each step on a separate line,
followed by a picture of the stack of foyers, followed by a comment.
<> # start with stack of just one empty foyer
9999 <9999> # put 999 at end of top foyer top foyer
[ <9999> <> # start a new foyer
[ <9999> <> <> # start a new foyer
2 <9999> <> <2> # put 2 at end of top foyer
3 <9999> <> <2 3> # put 3 at end of top foyer
] <9999> <[2 3]> # pop top foyer, put is content as list into foyer
below
[ <9999> <[2 3]> <> # start a new foyer
dup <9999> <[2 3]> <dup> # put dup at end of top foyer
* <9999> <[2 3]> <dup *> # put * at end of top foyer
] <9999> <[2 3] [dup *]> # pop top foyer, put content as list into
foyer below
map <9999> <[2 3] [dup *] map] # put map at end of top foyer
] <9999 [[2 3] [dup *] map]> pop top foyer, put its content as list
into foyer below
dip <9999 [[2 3] [dup *] map] dip> put dip at end of top foyer
. pop the top foyer, execute its contents as a Joy program
The behaviour of any item such as * and dip always depends on what it finds
on the stack: if it is a foyer, join the queue, otherwise multiply or dip as
normal for Joy. There is not much one can do with a foyer: create and
destroy with ³[³ and ³]², or accept items into the queue.
This is the flat concatenative language L. But one could invent an extension
L++ which allows other things to be done to foyers writing them out,
adding things to a queue by means other than a newly arriving item, or
perhaps immediate action macros. But I do not want to explore this here.
Is L flat enough? It is a language from stacks to stacks, using
concatenative notation. The behaviour of a whole program up to its
termination as a Joy program is to compute a function, and all parts compute
functions, and function computed by the whole is the composition of the
functions computed by the parts. And of course if any parts get snipped out,
the remainder will compute a function which may well be the empty (nowhere
defined)
composition of the functions computed by the remaining parts.
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-03-22 05:34:17
My apologies for the previous posting which I wrote ages ago but did not
post then Now it is completely out of date. Somehow I slipped with the mouse
just now. Sorry.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-03-28 08:26:36
Cancel the cancellation. The previous cancellation was for a very tentative
pre-Prolog draft of something about typing Joy. My mailer claims it was
sent to concatenative, and I did receive it back, but I did not see it when
I
looked at the group from Google. I really don¹t know what I have done
wrong.
Anyhow, here is the other posting that I did intend to send, which did
get through, but which might have been mistaken as the cancelled one.
I have made a few changes, mainly because I have seen how some of
the concepts can be generalised to something possibly useful, but also
because
I noticed some really bad typos.
On 22/3/07 4:23 PM, "Manfred Von Thun" <m.vonthun@...> wrote:
>
Here is a flat concatenative language which I shall call L. After a lot of
discussions on this group I now have some intuitive understanding of what a
flat language is. I shall discuss this language L in relation to Joy.
The problem seems to be how to handle apparent non-flatness due to
quotations/lists, which can be nested. I need to introduce the notion of a
waiting room, or ante-room, or briefly, a foyer. This is where incoming
items form a queue (perhaps similar to Stevan¹s Y queue in his XY language).
At certain times a queue in a foyer gets sent elsewhere and the foyer is
destroyed. A foyer is created by the special item ³[³, and destroyed by the
special item ³]². I also need a notation for describing foyers: a newly
created empty foyer is written <>, an after a ³dup² item arrives the foyer
is written <dup>, after a ³*² item arrives it is written <dup *>. But a
foyer is not a list, in fact a foyer can contain lists. Foyers cannot be
nested, but there is a stack of foyers: I shall write this stack with the
topmost item on the right. When a foyer is destroyed by ³]², the contained
queue is sent to the foyer below as a list. Finally, a ³.² will use the
contents
of the top foyer as a program to execute by using foyer below as a stack.
>
Here is a contrived example to illustrate several nestings. Let the program
be
9999 [ [2 3] [dup *] map ] dip . # should produce: [4 9] 9999
The program starts with a stack containing two empty foyers. I shall now
trace the execution of the program by writing each step on a separate line,
followed by a picture of the stack of foyers, followed by a comment.
<> <> # start with stack of just two empty foyers
9999 <> <9999> # put 999 at end of top foyer top foyer
[ <> <9999> <> # start a new foyer
[ <> <9999> <> <> # start a new foyer
2 <> <9999> <> <2> # put 2 at end of top foyer
3 <> <9999> <> <2 3> # put 3 at end of top foyer
] <> <9999> <[2 3]> # pop top foyer, put content into foyer below
[ <> <9999> <[2 3]> <> # start a new foyer
dup <> <9999> <[2 3]> <dup> # put dup at end of top foyer
* <> <9999> <[2 3]> <dup *> # put * at end of top foyer
] <> <9999> <[2 3] [dup *]> # pop top foyer, put content into foyer
below
map <> <9999> <[2 3] [dup *] map> # put map at end of top foyer
] <> <9999 [[2 3] [dup *] map]> pop top foyer, put content below
dip <> <9999 [[2 3] [dup *] map] dip> put dip at end of top foyer
. pop the top foyer, execute its contents as a Joy program, using
the
foyer below as a normal Joy stack for execution.
finally: <[4 9] 9999> the stack contains two items, a list and a number
To recapitulate: everything gets appended to the top foyer, except for
the three special commands ³[³ ³]² and ³.² , as follows:
³[³ starts a new foyer
³]² pops the top foyer and appends its contents as a list to the foyer
below.
³.² pops top foyer and executes contents on foyer below.
This is the flat concatenative language L. The foyers are just about
invisible
to the user of the language: they are created, filled, emptied and executed
entirely behind the scenes.
Is L flat enough? It is a language from stacks to stacks, using
concatenative notation. The behaviour of a whole program up to its
termination as a Joy program is to compute a function, and all parts compute
functions, and function computed by the whole is the composition of the
functions computed by the parts. And of course if any parts get snipped out,
the remainder will compute a function which may well be the empty (nowhere
defined) composition of the functions computed by the remaining parts.
Would anyone be tempted to implement a language such as L? Don¹t
rush off to do it, because it is nothing new. I¹ll let the cat out of the
bag now:
Look again at the paragraph at the beginning of the original posting,
the paragraph that started as ³Here is a flat ...². There are three
sentences
in that paragraph. From each sentence take the last word. The three words
form a sentence. It is true. All that stuff about foyers actually occurs
inside
the function ³readterm()² inside my joy.c, which reads a term (a sequence
of factors) and translates it into internal code.
One consequence from all this is that Joy is or is not a flat language,
depending on what one considers the language to be. Presumably the same
could be said of just about any language which has nesting of one kind
or another. To express it as a slogan: flatness is in the eye of the
beholder.
But one could invent an extension L++ which allows other things to be done
to foyers. Go back again five paragraphs, to the explanation of what ³[³,
³]²
and ³.² do. Nothing there says that ³[³ and ³]² have to be properly nested.
Consider the curious looking program
> [5 *] [ [dup] infra . i .
Let us execute it in the same way as before, using ³[³ , ³]² and ³.² as
explained.
<> <> # two empty foyers
[ <> <> <> # start new foyer
5 <> <> <5> # append 5
* <> <> <5 *> # append *
] <> <[5 *]> # append as list
[ <> <[5 *]> <> # start new foyer
[ <> <[5 *]> <> <> # start another foyer
dup <> <[5 *]> <> <dup> # append dup
] <> <[5 *]> <[dup]> append as list
infra <> <[5 *]> <[dup] infra> # append infra
. <> <[5 *] [dup]]> <infra> # starting to execute
<> <[5 5 *]> # finished executing
i <> <[5 5 *] i> # append i
. <[5 5 *]> <i> # start executing
<> <5 5 *> # this is what i always does
<5> <5 *> # pushed first 5
So the stack end up with a single 5. Not an exciting way to do it,
but it points to possibilities: construct a partial program, use Joy
itself to modify it, then finally execute the modified program. I have
used something similar in some of the Joy papers, where I speak of
executing ³constructed programs². But what all this shows is that
the behaviour of foyers that occurs inside function ³readterm()²
could be extended (even indefinitely) by just allowing ³.² to occur
after a ³[³ without a closing ³]² first.
Is it worth extending Joy in this way? It would take only a few very
tiny changes inside ³readterm()². Before you hasten to make those
changes, consider obtaining the identical effects from plain ol¹ Joy,
completely ignoring what goes on inside ³readterm()². Here is
the same program in plain Joy:
> [5 *] [dup] infra i .
>
start with an empty stack:
-> # empty stack
[5 *] -> [5 *] # push the quote
[dup] -> [5 *] [dup] # push second quote
infra -> [5 5 *] # execute the dup via infra
i -> 25 # execute the top quote via i
Same behaviour, and probably a better notation.
Conjecture -- 1: Joy can be seen as a flat language, and could be programmed
that way if one really wanted to. But 2: But everything that can be done by
programming in the flat version can equally well be done with the plain
version.
I am sorry that this has been so long.
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-03-28 17:05:28
Manfred Von Thun <
m.vonthun@...> wrote:
> Cancel the cancellation. The previous cancellation was for a very tentative
> pre-Prolog draft of something about typing Joy. My mailer claims it was
> sent to concatenative, and I did receive it back, but I did not see it when
> I looked at the group from Google. I really don¹t know what I have done
> wrong.
I'm glad to hear it -- I thought your post was interesting, and I
couldn't recall having seen it before.
Thanks for taking the opportunity to clean it up.
> The problem seems to be how to handle apparent non-flatness due to
> quotations/lists, which can be nested. I need to introduce the notion of a
> waiting room, or ante-room, or briefly, a foyer. This is where incoming
> items form a queue (perhaps similar to Stevan's Y queue in his XY language).
Well, by some definitions the Y queue makes a language
non-concatenative (or more accurately, programs that manipulate the Y
queue might not be concatenative).
Such a language could indeed be flat and concatenative; but please
consider that the semantics of the language would be more complex
because words would have to consider their effect on the foyers, not
merely on the stack.
In one of my experiments with my 1-bit flat language I added two extra
symbols (thus making a 4-bit language), and had the extra symbols
serve to append an operator onto the list on the stack (I also
redefined the 0 operator to place only an empty list on the stack).
This works much like what you've described, except that foyers are the
same as lists.
So for example:
0 == []
[B] [A] 1 == A
[A] 2 == [A k]
[A] 3 == [A q]
The resulting language wasn't really any shorter than the original
1-bit language for the derivations I tried, so I set it aside. It is a
bit simpler to understand at a low level, I think, but that advantage
doesn't seem to extend to shorter code at a high level, so I'm not as
happy with it as I hoped.
> At certain times a queue in a foyer gets sent elsewhere and the foyer is
> destroyed. A foyer is created by the special item ³[³, and destroyed by the
> special item ³]². I also need a notation for describing foyers: a newly
> created empty foyer is written <>, an after a ³dup² item arrives the foyer
> is written <dup>, after a ³*² item arrives it is written <dup *>. But a
> foyer is not a list, in fact a foyer can contain lists. Foyers cannot be
> nested, but there is a stack of foyers: I shall write this stack with the
> topmost item on the right. When a foyer is destroyed by ³]², the contained
> queue is sent to the foyer below as a list. Finally, a ³.² will use the
> contents of the top foyer as a program to execute by using foyer below
> as a stack.
A nice description. This language also changes the nature of the "."
operator, so it's now a kind of an 'i' operator as well as a syntactic
delimiter.
> To recapitulate: everything gets appended to the top foyer, except for
> the three special commands ³[³ ³]² and ³.² , as follows:
> ³[³ starts a new foyer
> ³]² pops the top foyer and appends its contents as a list to the foyer
> below.
> ³.² pops top foyer and executes contents on foyer below.
Interesting... So a way to execute an anonymous function would be to
begin it with "[" and end it with ".".
> Is L flat enough? It is a language from stacks to stacks, using
> concatenative notation.
I don't know. You haven't specified the runtime semantics of foyers;
you've only explained what happens inside the parser. Are the foyers
preserved across definitions?
> One consequence from all this is that Joy is or is not a flat language,
> depending on what one considers the language to be. Presumably the same
> could be said of just about any language which has nesting of one kind
> or another. To express it as a slogan: flatness is in the eye of the
> beholder.
In spite of your interpretation, Joy (as it stands) is not flat; if
you unbalance the foyers, the parser will barf. A language without
that error message but with the interpretation otherwise the same
would be flat -- but such a language would be different from Joy.
How different? And would the difference be useful?
I'm afraid that from what I can see the differences wouldn't be
useful. The problem is that in Joy foyers aren't a first-class
construct; you can't do anything with them at runtime. The only thing
you can do is write functions of which parts will inevitably be
ignored, without receiving a warning. You can't perform a "[" or "]"
at runtime (for example, inside a loop).
One thing I'm not clear on, though. Are these foyers available at
runtime? In practical terms: if I split a Joy definition into two
parts (cutting in the middle of a quotation), giving each part of the
definition its own name, and then I define a function which contains
the two parts one after the other, is the resulting definition
equivalent to the original? For example:
DEFINE
Csucc == [dup [i] dip] dip i.
DEFINE
CsuccA == [dup [i];
CsuccB == dip] dip i;
CsuccC == CsuccA CsuccB.
Is CsuccC exactly the same as Csucc? Would it still be the same if
CsuccC were defined in a DEFINE block apart from CsuccA or CsuccB?
Any way you put this, flatness is not in the eye of the beholder.
Flatness is a language feature which Joy does not currently possess.
If you want to add it you clearly can; it looks like it would be
simple for you to do. The cost for Joy would be a syntax that accepts
many odd programs, which seems to me to be a high price to pay; to
avoid this being a useless feature, you'd have to clearly define the
runtime behavior of foyers, and provide functions to manipulate them.
> But one could invent an extension L++ which allows other things to be done
> to foyers.
This would make the change possibly useful.
> Conjecture -- 1: Joy can be seen as a flat language, and could be programmed
> that way if one really wanted to.
Not as it stands. But such a version could be constructed, yes.
> But 2: But everything that can be done by
> programming in the flat version can equally well be done with the plain
> version.
That's just because foyers aren't first-class.
> - Manfred
-Billy
Manfred Von Thun — 2007-04-02 09:53:03
On 29/3/07 3:05 AM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
> Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>
> > wrote:
>
[..]
I could not comment on the lean flat language experiment
> Such a language could indeed be flat and concatenative; but please
> consider that the semantics of the language would be more complex
> because words would have to consider their effect on the foyers, not
> merely on the stack.
to anticipate: the L that I am discussing has a stack of foyers, starting
with
a stack of two empty foyers. What a symbol does depends on the stack that
it finds, and in many cases this means just the content of the top foyer.
>
>> > At certain times a queue in a foyer gets sent elsewhere and the foyer is
>> > destroyed. A foyer is created by the special item ³[³, and destroyed by the
>> > special item ³]². I also need a notation for describing foyers: a newly
>> > created empty foyer is written <>, an after a ³dup² item arrives the foyer
>> > is written <dup>, after a ³*² item arrives it is written <dup *>. But a
>> > foyer is not a list, in fact a foyer can contain lists. Foyers cannot be
>> > nested, but there is a stack of foyers: I shall write this stack with the
>> > topmost item on the right. When a foyer is destroyed by ³]², the contained
>> > queue is sent to the foyer below as a list. Finally, a ³.² will use the
>> > contents of the top foyer as a program to execute by using foyer below
>> > as a stack.
>
> A nice description. This language also changes the nature of the "."
> operator, so it's now a kind of an 'i' operator as well as a syntactic
> delimiter.
³.² is now a full blown operator, and indeed it resembles ³i² somewhat. But
there
is a difference: ³i² executes a quotation that it expects on top of a stack
and
executes it on the remainder of the stack. By contrast, ³.² executes the
content
of the current foyer using the foyer below as a stack. Perhaps ³.² is more
like
³infra², but even that isn¹t quite right.
>> > To recapitulate: everything gets appended to the top foyer, except for
>> > the three special commands ³[³ ³]² and ³.² , as follows:
>> > ³[³ starts a new foyer
>> > ³]² pops the top foyer and appends its contents as a list to the foyer
>> > below.
>> > ³.² pops top foyer and executes contents on foyer below.
>
> Interesting... So a way to execute an anonymous function would be to
> begin it with "[" and end it with ".".
>
Indeed. In fact, assuming that we have otherwise balanced parentheses inside
³- - -², the following should be equivalent:
>> [ - - - .
>> [ - - - ] i .
>>
>> > Is L flat enough? It is a language from stacks to stacks, using
>> > concatenative notation.
>
> I don't know. You haven't specified the runtime semantics of foyers;
> you've only explained what happens inside the parser. Are the foyers
> preserved across definitions?
>
There is no parser. There is a lexer/tokeniser. Then there is the runtime.
At runtime a stack of foyers gets processed. How it is processed depends on
what it receives from the lexer. The initial stack has two empty foyers. A
conventional Joy program running L ends up with a foyer that is just like
the stack that running that program under Joy would end up with.
>> > One consequence from all this is that Joy is or is not a flat language,
>> > depending on what one considers the language to be. Presumably the same
>> > could be said of just about any language which has nesting of one kind
>> > or another. To express it as a slogan: flatness is in the eye of the
>> > beholder.
>
> In spite of your interpretation, Joy (as it stands) is not flat; if
> you unbalance the foyers, the parser will barf.
>
I don¹t know what you mean by an unbalanced foyer. If you mean something
like unbalanced parentheses, then you should get the warning in this L
(whereas it
would be an errorr in Joy):
³Incomplete program? more than one foyer remaining. See top foyer?²
> A language without
> that error message but with the interpretation otherwise the same
> would be flat -- but such a language would be different from Joy.
>
> How different? And would the difference be useful?
>
> I'm afraid that from what I can see the differences wouldn't be
> useful. The problem is that in Joy foyers aren't a first-class
> construct; you can't do anything with them at runtime.
Normally ³first class² means ³can be passed as a parameter or can be
returned as a value. Indeed, but how does this count against being
concatenative
or being flat? But you can do four things with foyers.
1. fill then up with things like 42, +, map and so on.
2. start a new one with ³[³.
3. execute them on the foyer below, by ³.²
4. append their contents as a list to the foyer below, by ³]².
> The only thing
> you can do is write functions of which parts will inevitably be
> ignored, without receiving a warning. You can't perform a "[" or "]"
> at runtime (for example, inside a loop).
>
There is no separate runtime as opposed to parsetime. ³[³ and ³]² never get
inside a foyer. The fact that lists inside a foyer are written <111 [22 33]
444> are written using ³[³ and ³]² does no mean they are in the foyer. This
foyer just contains three elements: two numbers and between them a list of
two numbers.
>
> One thing I'm not clear on, though. Are these foyers available at
> runtime?
Yes, in the L-definition of runtime. This is not your definition, I know.
But
L has a right to make its own definition. In L one would define your notion
of runtime as: executing the content of the topmost foyer using the
ONLY remaining foyer below as its stack. But the executions of topmost
foyers would be exactly the same if there are further foyers below.
>
> In practical terms: if I split a Joy definition into two
> parts (cutting in the middle of a quotation), giving each part of the
> definition its own name, and then I define a function which contains
> the two parts one after the other, is the resulting definition
> equivalent to the original? For example:
>
Since when does being able to give names to the parts have anything to
do with cuttability or flatness?
>
> DEFINE
> Csucc == [dup [i] dip] dip i.
>
> DEFINE
> CsuccA == [dup [i];
> CsuccB == dip] dip i;
> CsuccC == CsuccA CsuccB.
>
> Is CsuccC exactly the same as Csucc? Would it still be the same if
> CsuccC were defined in a DEFINE block apart from CsuccA or CsuccB?
>
I have not said anything about definitions in L, and your example does
show that if L is to be of interest at all, then L needs to use a different
style
of definitions. Thank you.
>
For a while I thought that your example (just the cutting into three bits)
even shows that
concatenativity is ruined. But no, the three bits each compute functions
from stacks of foyers to stacks of foyers, and the concatenation of the bits
computes the composition of what the bits compute. So no worry here.
>
> Any way you put this, flatness is not in the eye of the beholder.
> Flatness is a language feature which Joy does not currently possess.
> If you want to add it you clearly can; it looks like it would be
> simple for you to do. The cost for Joy would be a syntax that accepts
> many odd programs, which seems to me to be a high price to pay; to
> avoid this being a useless feature, you'd have to clearly define the
> runtime behavior of foyers, and provide functions to manipulate them.
>
But the odd programs would be just those that leave more than one foyer
below. That is no more odd than an ordinary Joy program which leaves
one or more quotationson the stack, such as [11 22 +] or [cons 42 +],
whether the are executable or not.
>
Repeat: the runtime is all there is. There are the four ways of manipulating
foyers. But why does one need new functions?
>
>> > But one could invent an extension L++ which allows other things to be done
>> > to foyers.
>
> This would make the change possibly useful.
>
The way to manipulate the contents of foyers should be obvious: apart from
filling foyers (from the ³end², if you like), an incoming ³.² calls the
content of the
top foyer to be executed using the foyer below as a stack. That is always
the same.
The whole of Joy machinery is available to manipulate the contents of
foyers.
>
>> > Conjecture -- 1: Joy can be seen as a flat language, and could be
>> programmed
>> > that way if one really wanted to.
>
> Not as it stands. But such a version could be constructed, yes.
>
>> > But 2: But everything that can be done by
>> > programming in the flat version can equally well be done with the plain
>> > version.
>
> That's just because foyers aren't first-class.
>
See earlier comments
>> > - Manfred
>
> -Billy
Thanks for the discussion, Billy. I hope I have cleared up a few things.
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-04-02 23:12:01
Manfred Von Thun <
m.vonthun@...> wrote:
Thank you for the prompt and clear answers. To cut to the chase: I
agree that the language "L" is both flat and concatenative, and that L
is not enormously different from Joy.
However...
My first reaction was that although I confess that I have researched
flatness for its own sake, I suspect that there are higher principles
in language design than perfect flatness, and I believe that L's
design compromises some of them. I don't think that's a bad thing --
but I did believe that unless I point out the problems, the obvious
conclusion would be that flatness was the cause of those problems,
rather than the design choices that allowed flatness.
I'm not certain that I was right... thanks to your explanations, I
might see the benefit to L.
> On 29/3/07 3:05 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:
> >> > Is L flat enough? It is a language from stacks to stacks, using
> >> > concatenative notation.
> > I don't know. You haven't specified the runtime semantics of foyers;
> > you've only explained what happens inside the parser. Are the foyers
> > preserved across definitions?
> There is no parser. There is a lexer/tokeniser. Then there is the runtime.
> At runtime a stack of foyers gets processed. How it is processed depends on
> what it receives from the lexer. The initial stack has two empty foyers. A
> conventional Joy program running L ends up with a foyer that is just like
> the stack that running that program under Joy would end up with.
An excellent answer. You later detail that the foyers exist at
runtime, which means that your language provides the basic support
needed to be flat.
Good job; I now clearly see that L is flat.
> >> > One consequence from all this is that Joy is or is not a flat language,
> >> > depending on what one considers the language to be. Presumably the same
> >> > could be said of just about any language which has nesting of one kind
> >> > or another. To express it as a slogan: flatness is in the eye of the
> >> > beholder.
> > In spite of your interpretation, Joy (as it stands) is not flat; if
> > you unbalance the foyers, the parser will barf.
> I don¹t know what you mean by an unbalanced foyer. If you mean something
> like unbalanced parentheses, then you should get the warning in this L
> (whereas it
> would be an errorr in Joy):
> ³Incomplete program? more than one foyer remaining. See top foyer?²
Again, I was talking about Joy. Joy is not flat; it doesn't depend on
your perspective. L _is_ flat; again, it doesn't depend on your
perspective.
Why didn't I like L -- in spite of its very manifest cleverness?
I think my shortest answer would be "Occam's razor". To quote:
"entities should not be multiplied beyond necessity." L introduces a
new entity, the "foyer", which serves no purpose but to allow the
designer to claim flatness. If the foyer also allowed some terseness
or expressiveness, or otherwise demonstrated a result in language
design, I would be much more impressed.
I'm going to try to think of one.
> > A language without
> > that error message but with the interpretation otherwise the same
> > would be flat -- but such a language would be different from Joy.
> > How different? And would the difference be useful?
> > I'm afraid that from what I can see the differences wouldn't be
> > useful. The problem is that in Joy foyers aren't a first-class
> > construct; you can't do anything with them at runtime.
> Normally ³first class² means ³can be passed as a parameter or can be
> returned as a value. Indeed, but how does this count against being
> concatenative or being flat?
I have to admit that foyers can be returned as values -- your answers
have made that clear. The ability to pass them as parameters would be
a nice addition, and I suspect would not be a difficult thing to add
-- I imagine that just as Forth has words to preserve a value on the
return stack, JoyL would have words to 'dip' into the foyers.
My imagination suggests that your new language would have more
expressive power than Joy alone. In fact, my imagination suggests that
such a language might be as purely functional, concatenative, and
perhaps even as fun to program in as Joy, while being flat as well.
Exciting, if true. Is it?
Clearly, "[" creates a new foyer on the foyer stack, and "]" converts
the top foyer into a quotation nested into the next foyer. I see no
need for any special operators to juggle entries on the foyer stack
(am I wrong?). However, it would make sense to provide a function to
append the item on top of the data stack into the current foyer, and a
function to pop the top foyer onto the data stack and convert it to a
quotation. Without those, foyers can't be manipulated at runtime.
There's one thing that's nagging at me...
GOT IT! As an old Forth hand, I remember the need for IMMEDIATE words:
functions that execute when the compiler encounters them, rather than
being compiled for later execution. The problem is that "[", "]", and
"." are immediate words... They don't act like all the other functions
in L.
All the other functions in L get appended onto the topmost foyer on
the f-stack as soon as the compiler encounters them. Not those! They
do something else.
Does this make your language non-flat? Definitely NOT. Those words are
special, but they can be made to fit by describing the functions of
all other words as "this function appends the operation denoted by its
name onto the topmost foyer". (This is similar to the way we describe
concatenative languages as denoting function composition -- in
practical we don't think of it that way, we merely get the benefits.)
I'm not going to suggest (at this point) that you do what Forth did,
and make it possible to mark ANY word "immediate", so that it's
possible to make your own IMMEDIATE words to extend the compiler. I
actually think that wasn't a good thing, and even Chuck Moore doesn't
think it should be used often.
But... We should add non-special (runtime) words that perform the
functions of "[", "]", and perhaps "." (the latter can be implemented
in terms of previously explained words).
So we have:
+ "[": syntax, new foyer.
+ "]": syntax, embed foyer.
+ ".": syntax, execute top foyer.
+ "foyer": runtime, new foyer.
+ "embed": runtime, append TOS on top foyer.
+ "quotation": runtime, convert top foyer to quotation on TOS.
I'm not sure that "." is needed. Why was it in there again? Would "."
be the same thing as "quotation i", with no need for special syntax
treatment?
> > One thing I'm not clear on, though. Are these foyers available at
> > runtime?
> Yes, in the L-definition of runtime. This is not your definition, I know.
I think it is my definition as well -- what am I missing?
> But
> L has a right to make its own definition. In L one would define your notion
> of runtime as: executing the content of the topmost foyer using the
> ONLY remaining foyer below as its stack. But the executions of topmost
> foyers would be exactly the same if there are further foyers below.
Nope, that's runtime. We're good.
> > In practical terms: if I split a Joy definition into two
> > parts (cutting in the middle of a quotation), giving each part of the
> > definition its own name, and then I define a function which contains
> > the two parts one after the other, is the resulting definition
> > equivalent to the original? For example:
> Since when does being able to give names to the parts have anything to
> do with cuttability or flatness?
It doesn't -- names help clarify things. I assume syntax to assign
names for the sake of clarity. If asked the same question about my 01
language, I would assume the same thing.
> >DEFINE
> > Csucc == [dup [i] dip] dip i.
> >DEFINE
> > CsuccA == [dup [i];
> > CsuccB == dip] dip i;
> > CsuccC == CsuccA CsuccB.
> > Is CsuccC exactly the same as Csucc? Would it still be the same if
> > CsuccC were defined in a DEFINE block apart from CsuccA or CsuccB?
> I have not said anything about definitions in L, and your example does
> show that if L is to be of interest at all, then L needs to use a different
> style of definitions. Thank you.
Interesting. How would they differ?
> For a while I thought that your example (just the cutting into three bits)
> even shows that
> concatenativity is ruined. But no, the three bits each compute functions
> from stacks of foyers to stacks of foyers, and the concatenation of the bits
> computes the composition of what the bits compute. So no worry here.
Great -- that (together with the other things you've explained) gives
sufficient evidence to me that the result is both concatenative and
flat.
> Thanks for the discussion, Billy. I hope I have cleared up a few things.
You certainly did! I hope I make more sense now that we're on the same page.
> - Manfred
-Billy
Manfred Von Thun — 2007-04-10 04:04:54
On 3/4/07 9:12 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:
[..]
Sorry Billy, I cannot respond right now. But I will clarify a few things
when I have the time
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-04-18 06:18:59
On 3/4/07 9:12 AM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
>
> Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>
> > wrote:
>
> Thank you for the prompt and clear answers. To cut to the chase: I
> agree that the language "L" is both flat and concatenative, and that L
> is not enormously different from Joy.
Indeed, not enormously. But see below.
[..]
> However...
>
> My first reaction was that although I confess that I have researched
> flatness for its own sake, I suspect that there are higher principles
> in language design than perfect flatness, and I believe that L's
> design compromises some of them. I don't think that's a bad thing --
> but I did believe that unless I point out the problems, the obvious
>> > I don¹t know what you mean by an unbalanced foyer. If you mean something
>> > like unbalanced parentheses, then you should get the warning in this L
>> > (whereas it
>> > would be an errorr in Joy):
>> > ³Incomplete program? more than one foyer remaining. See top foyer?²
>
> Again, I was talking about Joy. Joy is not flat; it doesn't depend on
> your perspective. L _is_ flat; again, it doesn't depend on your
> perspective.
See your own comment above. You agree that L is concatenative (and flat),
and that Joy is concatenative (but not flat). I thought it was clear that
they
accept the same programs more or less, perhaps. If so, then flatness is
in the eye of the beholder.
It seems we need a definition of identity between two programming languages.
(And keep in mind that any single language might have several very different
implementations.) Here is one attempt at a definition:
L1 is a sublanguage of L2 if and only if
For all programs P, if P is a correct program in L1, then P is a correct
program in L2,
and for all inputs I, program P with input I produces the same output in L1
and in L2.
L1 is identical with L2 if and only if they are sublanguages of each other.
I claim that Joy and L are identical in this sense apart from the trivial
sense
that an incomplete Joy program (as Joy is currently implemented) produces
an error message (³end of input file, incomplete program²), whereas L
would not consider it to be incomplete. But surely this is a trivial
difference,
and is easily removed,
[..]
>
>>> > > One thing I'm not clear on, though. Are these foyers available at
>>> > > runtime?
>
>> > Yes, in the L-definition of runtime. This is not your definition, I know.
>
> I think it is my definition as well -- what am I missing
>
In most languages there is scantime, parsetime and runtime. In L there
are only scantime and runtime.
>
>
>
>> > But
>> > L has a right to make its own definition. In L one would define your notion
>> > of runtime as: executing the content of the topmost foyer using the
>> > ONLY remaining foyer below as its stack. But the executions of topmost
>> > foyers would be exactly the same if there are further foyers below.
>
> Nope, that's runtime. We're good.
>
>>> > > In practical terms: if I split a Joy definition into two
>>> > > parts (cutting in the middle of a quotation), giving each part of the
>>> > > definition its own name, and then I define a function which contains
>>> > > the two parts one after the other, is the resulting definition
>>> > > equivalent to the original? For example:
>
>> > Since when does being able to give names to the parts have anything to
>> > do with cuttability or flatness?
>
> It doesn't -- names help clarify things. I assume syntax to assign
> names for the sake of clarity. If asked the same question about my 01
> language, I would assume the same thing.
>
>>> > >DEFINE
>>> > > Csucc == [dup [i] dip] dip i.
>>> > >DEFINE
>>> > > CsuccA == [dup [i];
>>> > > CsuccB == dip] dip i;
>>> > > CsuccC == CsuccA CsuccB.
>
>>> > > Is CsuccC exactly the same as Csucc? Would it still be the same if
>>> > > CsuccC were defined in a DEFINE block apart from CsuccA or CsuccB?
>
>> > I have not said anything about definitions in L, and your example does
>> > show that if L is to be of interest at all, then L needs to use a different
>> > style of definitions. Thank you.
>
> Interesting. How would they differ?
Note the ³.² at the end of these definitions. If ³.² is to be allowed inside
a definition,
then a different notation might be needed, something like:
DEFINE a == ...; b == ...; c == ... END_DEF
>
[..]
>
>> > Thanks for the discussion, Billy. I hope I have cleared up a few things.
>
> You certainly did! I hope I make more sense now that we're on the same page.
>
>> > - Manfred
>
> -Billy
>
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-04-18 14:40:17
Manfred Von Thun <
m.vonthun@...> wrote:
> "William Tanksley, Jr" <wtanksleyjr@...> wrote:
> > Again, I was talking about Joy. Joy is not flat; it doesn't depend on
> > your perspective. L _is_ flat; again, it doesn't depend on your
> > perspective.
> See your own comment above. You agree that L is concatenative (and flat),
> and that Joy is concatenative (but not flat). I thought it was clear that
> they accept the same programs more or less, perhaps. If so, then
> flatness is in the eye of the beholder.
But they do not accept the same programs. L accepts many more programs
than Joy does. L may even be more expressive than Joy (although I
haven't examined it to see whether it actually is).
> It seems we need a definition of identity between two programming languages.
> (And keep in mind that any single language might have several very different
> implementations.) Here is one attempt at a definition:
In computation theory, one formal definition of a language is the set
of all texts that are legal in the language.
> L1 is a sublanguage of L2 if and only if
> For all programs P, if P is a correct program in L1, then P is a correct
> program in L2,
> and for all inputs I, program P with input I produces the same output in L1
> and in L2.
> L1 is identical with L2 if and only if they are sublanguages of each other.
> I claim that Joy and L are identical in this sense apart from the trivial
> sense that an incomplete Joy program (as Joy is currently
> implemented) produces an error message (³end of input file, incomplete
> program²), whereas L would not consider it to be incomplete. But surely
> this is a trivial difference, and is easily removed,
A text that produces a syntax error is by definition not a "correct
program" (your words). Thus there exist correct programs in L which
are not correct programs in Joy. This is your definition of
sublanguage -- Joy is a sublanguage of L, and not the other way
around.
> >> > Yes, in the L-definition of runtime. This is not your definition, I know.
> > I think it is my definition as well -- what am I missing?
> In most languages there is scantime, parsetime and runtime. In L there
> are only scantime and runtime.
That's the case for Forth as well. I'm pretty sure that I'm okay with
that; anyone must agree that runtime is runtime.
> >> > I have not said anything about definitions in L, and your example does
> >> > show that if L is to be of interest at all, then L needs to use a different
> >> > style of definitions. Thank you.
> > Interesting. How would they differ?
> Note the ³.² at the end of these definitions. If ³.² is to be allowed inside
> a definition,
> then a different notation might be needed, something like:
> DEFINE a == ...; b == ...; c == ... END_DEF
Actually, I questioned before whether "." was truly needed as part of
the flat language. It seems to me that everything "." is doing is
semantic, not syntactic; therefore it can be a function rather than
being syntax. I believe I suggested using the phrase "quotation i"
instead of "." (using my definition of "quotation", feel free to use
your own name for the function that takes the top lobby, converts it
to a quotation, and places it on the stack).
> - Manfred
-Billy
Manfred Von Thun — 2007-04-26 07:58:36
On 19/4/07 12:40 AM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
>
> Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>
> > wrote:
>
>> > "William Tanksley, Jr" <wtanksleyjr@...
>> <mailto:wtanksleyjr%40gmail.com> > wrote:
>>> > > Again, I was talking about Joy. Joy is not flat; it doesn't depend on
>>> > > your perspective. L _is_ flat; again, it doesn't depend on your
>>> > > perspective.
>
>> > See your own comment above. You agree that L is concatenative (and flat),
>> > and that Joy is concatenative (but not flat). I thought it was clear that
>> > they accept the same programs more or less, perhaps. If so, then
>> > flatness is in the eye of the beholder.
>
> But they do not accept the same programs. L accepts many more programs
> than Joy does. L may even be more expressive than Joy (although I
> haven't examined it to see whether it actually is).
>
You are exactly right about L++ (in the terminology of my original post),
but not about L.
Reminder: L and L++ both use a stack of foyers, but they differ in whether
they allow
unmatched ³[³ before ³.² In a nutshell, again for both L and L++ :
³[³ starts a new foyer,
³]² appends the current foyer as a list to the previous foyer, and
³.² executes the current foyer on the foyer below.
>
But there is a difference:
L does not allow the sequence ³[³ ... ³.² because of unmatched brackets.
L++ does allow this sequence, and as you rightly observe, it resembles Forth
immediates.
I still maintain that L = Joy, and agree that L++ is a superset. But I am
not at all sure
whether the extras that L++ can do cannot also be achieved (in a different
way) by
using existing list- (and hence program-) manipulators. I just don¹t know.
I meant this posting to be more detailed, sorry Billy. But I got sidetracked
by downloading
the Factor tarfile and inspecting quite a lot of the files. A most
impressive piece of work,
congratulations to the author(s).
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-04-26 16:59:22
Manfred Von Thun <
m.vonthun@...> wrote:
> "William Tanksley, Jr" <wtanksleyjr@...> wrote:
> > But they do not accept the same programs. L accepts many more programs
> > than Joy does. L may even be more expressive than Joy (although I
> > haven't examined it to see whether it actually is).
> You are exactly right about L++ (in the terminology of my original post),
> but not about L.
> Reminder: L and L++ both use a stack of foyers, but they differ in whether
> they allow
> unmatched ³[³ before ³.² In a nutshell, again for both L and L++ :
I'm extremely confused. I thought you just said that L accepted
unbalanced brackets -- you said, "an incomplete Joy program (as Joy is
currently implemented) produces an error message..., whereas L would
not consider it to be incomplete."
How does this NOT mean that L accepts a superset of what Joy accepts?
The only thing I can think of is that you consider producing "an error
message" to be a way for a language to signify that it accepts the
text as a valid program. My texts list that as the ONLY way a parser
can reject a text as an invalid program.
> ³[³ starts a new foyer,
> ³]² appends the current foyer as a list to the previous foyer, and
> ³.² executes the current foyer on the foyer below.
> But there is a difference:
> L does not allow the sequence ³[³ ... ³.² because of unmatched brackets.
> L++ does allow this sequence, and as you rightly observe, it resembles Forth
> immediates.
I'm definitely completely lost on what L is. Your previous posts
seemed to indicate that it did something different from Joy, which I
interpreted as (in my own words) "it doesn't produce an error for
unmatched brackets." Now you're telling me that it doesn't allow
unmatched brackets.
> I still maintain that L = Joy, and agree that L++ is a superset.
They're your languages, so you have the right to define them as you
wish. I'm still phenomenally confused, however, because I you
previously defined L using language that (in your own words) implied
"nothing there says that '[' and ']' have to be properly nested."
Indeed, I assumed that was the case when reading your original post --
after all, if you were to imply that [ and ] nested the text they
contained, you wouldn't have been defining a flat language.
But now, looking very carefully at what you say, here's my opinion:
- Joy isn't flat; it will reject programs that were cut at arbitrary places.
- If L is exactly Joy, L isn't flat either.
- If L is Joy minus the rejection of unbalanced nesting, L is flat.
- I don't know anything about L++. I thought you were only using it
to mean "a language like L but with additional unspecified features."
There's nothing wrong with *not* being flat. I would strongly
recommend against making a language flat for any reason other than
pure research.
> But I am not at all sure
> whether the extras that L++ can do cannot also be achieved (in a different
> way) by using existing list- (and hence program-) manipulators. I just
> don't know.
Assuming that L++ is your name for a language that accepts any section
of a valid Joy program as a valid L++ program... Yes, since it's
Turing complete, Joy can do all the same things. But what Joy can't do
is be refactored 100% validly by cut and paste. L++ can.
Does that matter? A bit. A flatter language is easier to mentally
parse than a less flat one, all other things being equal. BUT... Not
all things are equal. Kerby's and my 01 languages are abominations
from the pit of mathematical hell (hey, maybe I *like* it warm!); L
and L++ add "foyers", a concept which is not needed to understand Joy
(so Joy is simpler).
So far nobody's been able to produce a flat language that's _actually_
easier to work with in general than a non-flat language. Anyone who
suspected that it's impossible would be in good company.
I don't think it's reasonable to ask for a perfectly flat language;
but I do think it might be possible to design a language that doesn't
need quite as much nesting. A _flatter_ language. Such a language
might (or might not) be like Joy, but using foyers _instead_ of
quotations (to reduce the number of simultaneous concepts that people
have to work with). I don't know. I'm taking a slightly different
approach at the moment, with no results yet to report on.
> I meant this posting to be more detailed, sorry Billy. But I got sidetracked
> by downloading
> the Factor tarfile and inspecting quite a lot of the files. A most
> impressive piece of work, congratulations to the author(s).
Indeed it is!
> - Manfred
-Billy
Manfred Von Thun — 2007-04-30 09:06:05
From time to time I have considered various alternative notations for
concatenative languages. In particular the syntax for combinators would seem
to allow some variants the might be explored. In this note I only present
some alternatives, I do not argue for or against one or the other.
When writing Joy programs with combinators, in about 95% of cases I seem to
push the quotation parameters just before the combinator. Using the ifte
combinator, a piece of program would look like this:
[if-part] [then-part] [else-part] ifte
The ifte combinator immediately removes the three quotations, and all other
combinators do the same. Could one have a different notation? Perhaps to
avoid the needless pushes, perhaps for better intelligibility, perhaps for
other reasons. Starting at one extreme of the possibilities we have several
choices:
(1) Write instead something like this mixfix notation
IF if-part THEN then-part ELSE elsepart ENDIF
in analogy with some procedural languages. Make IF, THEN, ELSE, ENDIF
reserved words, perhaps. Do something analogous for other combinators, but
restrict the palette of combinators to a fixed useful minimum. This is what
procedural languages tend to do with statements sequencing, conditionals,
various loops. Do not allow the user to define their own. (Something needs
to be said here about procedures taking other procedures as parameters but
I¹ll skip that for the moment.) The Pascals and the Cs do this, and so does
the FP language by Backus (if memory serves right). I don¹t know what a
suitable minimal set for Joy or other concatenative languages would be.
(2) Allow user defined combinators, but (probably) without the mixfix
notation. Instead do functional notation:
ifte(ifpart, then-part, else-part)
Definitions for user declared combinators now look like this:
DEFINE foo(f1, f2, ..) == ... .
The extension to the parser is trivial, and checking for agreement of formal
and actual parameters in calls is not difficult either.
Both (1) and (2) introduce more structure into programs, and allow the
language processor to check that the required structure is not violated.
In each case the combinators take stack functions (such as dup * ) as
parameters and the result behaves just like a simple stack function. Calls
now look like this:
IF ... THEN dup * ELSE ...
ifte(..., dup *, ...)
foo(..., dup *, ..., ...)
In other words the parameters have to be literally the verbatim programs
to be executed by the combinator, the program dup * in this case. Note also
that as described so far there is no need for quotation brackets in the
comma-separated list of actual parameters.
(3) But in languages like the lisps there is another possibility. In most
cases
the combinators are given their function parameters literally, but at least
for the apply combinator actual function parameter is an expression which
has to be evaluated to give the function to be applied. Suppose we allow
that for the concatenative language sketched so far. Assume we have defined
a list of quotations, with the squaring quotation in third position:
DEFINE quotelist == [ [..] [..] [dup *] [..] ....]
Now we could write things like these:
ifte(..., quotelist third, ...)
which will be equivalent to
ifte(..., [dup *], ...)
but now with quotation brackets. So there is more expressive power again,
but still the parameters are in predetermined positions which can be
enforced
by the language processor.
(4) Allow the quotation parameters to be constructed just before they are
used by the
combinator:
ifte(..., quotelist third dup concat, ...)
which is equivalent to
ifte(..., [dup * dup *], ...)
(5) Drop the restriction of predetermined positions of the parameters. Allow
them to come from anywhere on the stack, but put them in the right position
just before the combinator uses them. Examples in Joy:
... rollup quotelist third swap ifte
... rollup quotelist third dup concat swap ifte
Just as in (4), even the concat example builds up a quotation from existing
ones.
(6) Allow quotation parameters to be built by taking other quotations apart:
Examples:
ifte( ..., quotelist third rest cons, ...)
... rollup 3 quotelist third rest cons swap ifte
which are equivalent to
ifte( ..., [3 *], ...)
... rollup [3 *] swap ifte
As you the steps from 3 to 5 and 6 show, the ³spectrum² of possible
notations is not quite linear, but never mind.
We have started with a very inflexible version of combinators and allowed
more and more freedom. There may be even more restrictive and more
flexible notations than the two extremes outlined here.
Question: which level is best? Safety bought by inflexible rigidity, or
flexibility at the cost of obfuscation? I¹ll leave it at that. Pick your
level
and tell us about it.
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-04-30 14:36:10
Manfred Von Thun <
m.vonthun@...> wrote:
> Question: which level is best? Safety bought by inflexible rigidity, or
> flexibility at the cost of obfuscation? I¹ll leave it at that. Pick your
> level and tell us about it.
I think one of the great advances of Joy over Forth was its ability to
pass code to combinators. Going back to a fixed syntax would be a
pity. Safety can be acquired at less cost by adding some typechecking.
However, some of Joy's combinators might be a little overdone. 'ifte'
takes 3 quotations; that's a lot. I'd like to be able to express
'else' without having to go so deep on the stack. What if the 'if'
combinator left a conditional token on the stack, to be picked up by
an 'else' combinator?
[if-part] [conditional] if [else-part] else
alternately, if you really like traditional syntax,
[conditional] if [if-part] else [else-part] endif
The same implementation would work for more complex conditionals:
[action-choice] decisiontable
[decision-part] decision
[decision-part] decision
[decision-part] decision ...
endtable
An 'if' would build a two-choice decision table. A full decision table
could have any number of choices.
> - Manfred
-Billy
James Hague — 2007-05-01 14:23:04
>When writing Joy programs with combinators, in about 95% of cases I seem to
>push the quotation parameters just before the combinator. Using the ifte
>combinator, a piece of program would look like this:
>
>[if-part] [then-part] [else-part] ifte
>
>The ifte combinator immediately removes the three quotations, and all other
>combinators do the same. Could one have a different notation?
The Forth-like notation you suggest is a step-backwards. This is coming
from someone who has written a lot of Forth :)
I would like to see [if-part] replaced with a simple Boolean flag. Is there
a reason it needs to be a quotation? I believe it's a Boolean in Factor.
James
John Cowan — 2007-05-01 15:38:29
James Hague scripsit:
> I would like to see [if-part] replaced with a simple Boolean flag.
> Is there a reason it needs to be a quotation? I believe it's a Boolean
> in Factor.
There are two separate two-armed conditional words in Joy, "ifte" and
"choice". The latter behaves as you suggest: it takes a boolean
value and two quotations on the stack. However, "ifte" works differently:
after executing the [if-part], it gets the boolean value from the
top of the stack and then restores the stack to its former state.
Thus the program
20 [pop true] ["yes"] ["no"] ifte
is equivalent to
20 "yes"
because although the pop is executed, its effect is undone by the
stack restoration.
There are many other Joy combinators with similar behavior. For example,
"nullary" pops a combinator from the stack, preserves the stack, executes
the combinator, saves the top value, restores the stack, and pushes the
top value. Thus it does not matter how many items are popped from the
stack by the combinator.
In the Joy interpreter, the stack is a linked list rather than a vector,
and garbage collection is used to reclaim stack fragments. Consequently,
restoring the stack is a cheap operation.
--
Time alone is real John Cowan <
cowan@...>
the rest imaginary
like a quaternion --phma
http://www.ccil.org/~cowan
Manfred Von Thun — 2007-05-04 08:15:33
On 2/5/07 1:38 AM, "John Cowan" <
cowan@...> wrote:
>
>
>
>
> James Hague scripsit:
>
>> > I would like to see [if-part] replaced with a simple Boolean flag.
>> > Is there a reason it needs to be a quotation? I believe it's a Boolean
>> > in Factor.
>
> There are two separate two-armed conditional words in Joy, "ifte" and
> "choice". The latter behaves as you suggest: it takes a boolean
> value and two quotations on the stack. However, "ifte" works differently:
> after executing the [if-part], it gets the boolean value from the
> top of the stack and then restores the stack to its former state.
>
> Thus the program
>
> 20 [pop true] ["yes"] ["no"] ifte
>
> is equivalent to
>
> 20 "yes"
>
> because although the pop is executed, its effect is undone by the
> stack restoration.
>
> There are many other Joy combinators with similar behavior. For example,
> "nullary" pops a combinator from the stack, preserves the stack, executes
> the combinator, saves the top value, restores the stack, and pushes the
> top value. Thus it does not matter how many items are popped from the
> stack by the combinator.
>
> In the Joy interpreter, the stack is a linked list rather than a vector,
> and garbage collection is used to reclaim stack fragments. Consequently,
> restoring the stack is a cheap operation.
The two combinators ifte and choice are interdefinable:
[thenpart] [elsepart] choice ==
[] [thenpart] [elsepart] ifte ==
[thenpart] [elsepart] [] rollup ifte
and hence:
choice == [] rollup ifte
[ifpart] [thenpart] [elsepart] ifte ==
[ifpart] nullary [thenpart][elepart] choice ==
[ifpart] [nullary] i [thenpart] [elsepart] choice ==
[ifpart] thenpart] [nullary] dip [elsepart] choice ==
[ifpart] [thenpart] [elsepart] [[nullary]dip] dip choice
And hence:
ifte == [[nullary] dip] dip choice.
So the ifte combinator can be defined in tems of nullary and dip. Presumably
the nullary combinator will evoke the same wide variety of reactions from
programmers as the ifte combinator. By way of contrast, the dip combinator
has never evoked such a variety. But what is surprising is that nullary need
not be a primitive combinator, it can be defined in terms of dip or in terms
of infra. I cannot remember the two definitions right now. But I¹ll look
them
up at home and post them next week.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-05-07 04:23:37
On 4/5/07 6:15 PM, "Manfred Von Thun" <
m.vonthun@...> wrote:
> So the ifte combinator can be defined in tems of nullary and dip. Presumably
> the nullary combinator will evoke the same wide variety of reactions from
> programmers as the ifte combinator. By way of contrast, the dip combinator
> has never evoked such a variety. But what is surprising is that nullary need
> not be a primitive combinator, it can be defined in terms of dip or in terms
> of infra. I cannot remember the two definitions right now. But I¹ll look
> them up at home and post them next week.
>
Here we are:
First, two older versions:
nullary == [stack] dip infra first
nullary == [stack] dip dip cons unstack
My current favourites, using just one combinator (infra or dip):
nullary == stack rest swap infra first
nullary == stack rest swap dip cons unstack
With the wisdom of hindsight this should not really be a surprise.
Given any stack, the stack operator will produce essentially two
identical lists: the original stack and a copy (in the form of a list).
Put a quotation on top, and then the dip operator and the infra operator
can use the quotation to change the original or the copy.
So there exists some kind of symmetry between dip and infra.
If I had understood this earlier, I might have chosen two more
symmetric names for the two combinators.
I have not succeeded to define dip in terms of infra, or to
define infra in terms of dip. I don¹t know whether this is just
failure of the imagination or whether this is just impossible.
And this raises another question: Is there some technique by
which one can show that it is impossible to define one thing
in terms of a given set of others? I only have the vaguest
recollection of seeing a proof that ³not² cannot be defined
in terms of ³and² and ³or². Obvious, yes. But is there a
general technique?
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-05-07 10:52:30
On 2/5/07 12:23 AM, "James Hague" <
jamesh@...> wrote:
> [..]
>> >The ifte combinator immediately removes the three quotations, and all other
>> >combinators do the same. Could one have a different notation?
>
> The Forth-like notation you suggest is a step-backwards. This is coming
> from someone who has written a lot of Forth :)
Firstly, I wasn¹t actually suggesting it, I was merely listing various
alternatives.
Is it a step backwards? Maybe, but that can be a a good thing if one has
been led
up the garden path. I was really looking for a cost/benefit analysis of the
various
possible alternative notations. Then, when one has settled on one notation,
at
least one knows why it was chosen in preference to others. My own little
contribution
to the analysis was my usage statistic: 95% of programs could be written
with
a less permissive notation and be clearer. Are the 5% using the various
extras
worth the risks? It is safe rigidity versus freedom (to shoot oneself in the
foot).
I have tried not to make my preferences shine through.
- Manfred
[Non-text portions of this message have been removed]