impure concatenativity: let without translation
John Nowak — 2008-03-19 08:58:13
Just moments ago, I gave this example of the quadratic formula:
(define (quad a b c)
(let ((d b 4 a c * * -)
(r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)
(x 2 a *)
(p b r - x /)
(n b r + x /))
p n))
How it works should be obvious after you get used to looking at this
sort of prefix/postfix syntax. It's a very nice way to write this
function; arguably nicer than what you can do in Scheme as the
multiple values returned can be easily consumed (or ignored) by
another function. For example, if we only cared about the positive
root, we could do 'quad pop'.
Now here's the quadratic formula in Joy:
quad ==
[[[pop pop 2 *]
[pop 0 swap -]
[swap dup * rollup * 4 * - sqrt]]
[i] map]
ternary i
[[[+ swap /]
[- swap /]]
[i] map]
ternary.
Clearly we want to be able to write the first version of 'quad' as
this version is truly awful (both in terms of readability and likely
execution speed).
Let's go back and examine how the first version works. I'd suggest
that each variable introduced via 'let' must bind the result of a
function that requires *no* arguments on the stack. This is a
necessary restriction as otherwise the order in which you evaluate the
functions matters and a bug in one can screw up the other. (Well, you
could save and restore the stack for each binding, but that requires
you represent the stack as a linked list.)
I argue that translating the 'let' expression into point-free code is
a *bad* idea. Why? Let's say we wrote this buggy version instead:
(define (quad a b c)
(let ((d b 4 a c * * * -)
(r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)
(x 2 a *)
(p b r - x /)
(n b r + x /))
p n))
See it? The 'd' function has an extra call to '*'. If we don't
translate the 'let' away, we are able to give an intelligent error
that implicates the call to '*' in the expression 'b 4 a c * * *' in
the binding of 'd'. If we translate the let away however, who knows
what the error will be. It depends how the compiler does the
translation of course. The likely result will be an unhelpful type
error that requires the programmer to tediously go over the entire
function to try and find the problem.
Worse yet, the translation might actually yield code that type checks
by requiring an additional argument on the stack, but produces the
wrong result and has the wrong type! (I'd guess that would be the case
here actually.) You'd not catch this until much later when actually
using 'quad' somewhere and getting confusing error messages. This sort
of problem can take a long time to track down. If the reason we're
introducing types is to get rid of these scenarios, then it seems
translating everything to a point-free form is a bad idea. Such a
translation necessarily discards the very information that allowed the
programmer to write the function more easily in the first place!
What I'm suggesting is that dropping any pretense of being purely
concatenative offers some clear usability benefits with no loss in
expressiveness. It would likely offer efficiency advantages as well;
splicing quotes together to embed variables into the middle of
anonymous functions is less than fun. Additionally, you can define
primitives like 'swap' within the language itself:
(define (swap a b) b a)
Are there any other proposals for an impure (or, more nicely,
"hybrid") concatenative language out there? What are the negative
practical implications of being impure?
- John
Joe Bowbeer — 2008-03-19 15:58:27
On Wed, Mar 19, 2008 at 1:58 AM, John Nowak wrote:
> Just moments ago, I gave this example of the quadratic formula:
>
> (define (quad a b c)
> (let ((d b 4 a c * * -)
> (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)
> (x 2 a *)
> (p b r - x /)
> (n b r + x /))
> p n))
>
>
Is quad invoked postfix or prefix?
The (quad a b c) syntax for declaration in scheme is especially nice because
it looks like the expression that's used to invoke the function.
I'm confused by the mixture of prefix and postfix in your example.
Actually, I'm confused by all postfix, but I'd prefer to have consistency
with my confusion:)
--Joe
[Non-text portions of this message have been removed]
John Nowak — 2008-03-19 18:58:04
On Mar 19, 2008, at 11:58 AM, Joe Bowbeer wrote:
> On Wed, Mar 19, 2008 at 1:58 AM, John Nowak wrote:
>
>> Just moments ago, I gave this example of the quadratic formula:
>>
>> (define (quad a b c)
>> (let ((d b 4 a c * * -)
>> (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)
>> (x 2 a *)
>> (p b r - x /)
>> (n b r + x /))
>> p n))
>>
>>
>
> Is quad invoked postfix or prefix?
Postfix, as are *all* procedures. Only special forms are infix.
Perhaps this is a better declaration form:
(define (a b c quad)
...)
- John
Daniel Ehrenberg — 2008-03-19 20:31:27
> Are there any other proposals for an impure (or, more nicely,
> "hybrid") concatenative language out there? What are the negative
> practical implications of being impure?
>
> - John
Another stack-based language with prevalent use of named variables is
Raven (
http://mythago.net/language.html). The only downside to
encouraging lots of variables is that the resulting language is more
complicated. But, more fundamentally, focusing on variables in your
efforts in language design draws attention away from creating
abstractions in your library, both ones that depend on the stack and
don't. This doesn't mean that you shouldn't make some way to have
lexically scoped variables, of course.
I don't understand why you say this is without translation. Of course
translation exists at some level; you're just proposing that it
happens at a level that the user not see, and that the translation be
tightly integrated into the development environment so that type
errors and such are easier to read.
Dan
Joe Bowbeer — 2008-03-19 20:51:38
On Wed, Mar 19, 2008 at 11:58 AM, John Nowak wrote:
>
> On Mar 19, 2008, at 11:58 AM, Joe Bowbeer wrote:
>
> > On Wed, Mar 19, 2008 at 1:58 AM, John Nowak wrote:
> >
> >> Just moments ago, I gave this example of the quadratic formula:
> >>
> >> (define (quad a b c)
> >> (let ((d b 4 a c * * -)
> >> (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)
> >> (x 2 a *)
> >> (p b r - x /)
> >> (n b r + x /))
> >> p n))
> >>
> >>
> >
> > Is quad invoked postfix or prefix?
>
> Postfix, as are *all* procedures. Only special forms are infix.
> Perhaps this is a better declaration form:
>
> (define (a b c quad)
> ...)
>
> - John
>
Better. Better yet is:
(...
(a b c quad) define)
This maintains a consistent right-to-left reading direction. If postfix is
the "right thing," there's no such thing as too much, right?
But if that's even better, then why not go right-to-left all the way?
(...
(c b a dauq) enifed)
Naive question: Is there any reason why concatenative languages are
(uniformly) postfix? Would prefix work just as well, pushing elements onto
the stack from right to left?
--Joe
[Non-text portions of this message have been removed]
Robbert van Dalen — 2008-03-19 21:04:23
another postfix language with named 'variables' is enchilada.
<disclaimer>
this may seem like a shameless plug :)
or i haven't been talking about enchilada that much lately :(
</disclaimer>
anyway, i don't think 'variables' defy pureness. let's consider
symbols instead.
symbols are placeholders for values to be. symbols can be bound so
that they can be replaced by values.
consider the following postfix expression with unbound symbols:
x y + z *
how do we bind z?
to do this we enclose the expression with an enchilada 'macro' operator:
{z=x y + z *}
prefixing this macro with a value, binds symbol 'z:
4 {z=x y + z *}
x y + 4 *
a macro acts like a monadic operator, binding a value with it's
internal expression at each reduction step.
in a sense, a macro fills in the blanks.
macros bind lexically, i.e.
1 2 3 {z={x={y=x y + z *}}}
reduces to:
1 2 3 {z={x={y=x y + z *}}}
1 2 {x={y=x y + 3 *}}
1 {y=2 y + 3 *}
2 1 + 3 *
3 3 *
9
another convenient (and operationally equal) form would be:
1 2 3 {y x z=x y + z *}
1 2 {y x=x y + 3 *}
1 {y=2 y + 3 *}
2 1 + 3 *
3 3 *
9
'replacing' a symbol with a value doesn't need to be destructive: it
can be pure: just leave every expression untouched. use pure copy
semantics all the time.
making copy semantics efficient and scalable: that's what enchilada is
about.
<end-shameless-plug/>
- robbert
Daniel Ehrenberg — 2008-03-19 21:06:12
> Naive question: Is there any reason why concatenative languages are
> (uniformly) postfix? Would prefix work just as well, pushing elements onto
> the stack from right to left?
>
>
> --Joe
Naive answer: prefix is readable for simple things, but when things
like "swap" are included, it gets more awkward to do prefix. It ends
up that you're reading things backwards. Neither prefix nor postfix
allows a completely left-to-right reading, but in my experience,
postfix has things *mostly* left-to-right once you're comfortable with
the language. Anyway, if the program is broken up into small units, it
doesn't matter what order things are in! And concatenativity, whether
in prefix or postfix, makes this much easier.
Dan
John Nowak — 2008-03-19 21:11:26
On Mar 19, 2008, at 4:51 PM, Joe Bowbeer wrote:
> On Wed, Mar 19, 2008 at 11:58 AM, John Nowak wrote:
>
>> Postfix, as are *all* procedures. Only special forms are infix.
>> Perhaps this is a better declaration form:
>>
>> (define (a b c quad)
>> ...)
>>
>> - John
>>
>
> Better. Better yet is:
>
> (...
> (a b c quad) define)
>
> This maintains a consistent right-to-left reading direction. If
> postfix is
> the "right thing," there's no such thing as too much, right?
There is. Special forms and macros need access to the entire tree to
do their work. If you were to put 'define' at the end, then there's no
way for it to act on the tree (without some bizarre backtracking).
Keep in mind that even [a b c] is really (lambda () a b c). Putting
meta-level things like 'define' and 'let' up front also aids in
readability.
> Naive question: Is there any reason why concatenative languages are
> (uniformly) postfix? Would prefix work just as well, pushing
> elements onto
> the stack from right to left?
Let's say these two are equivalent:
-- postfix
hypot -> sqr swap sqr + sqrt
-- prefix
sqrt + sqr swap sqr <- hypot
Sure, both mean the same thing, but which is easier to read (provided
you're used to reading left to right)?
- John
John Nowak — 2008-03-19 21:25:06
On Mar 19, 2008, at 4:31 PM, Daniel Ehrenberg wrote:
>> Are there any other proposals for an impure (or, more nicely,
>> "hybrid") concatenative language out there? What are the negative
>> practical implications of being impure?
>>
>
> I don't understand why you say this is without translation. Of course
> translation exists at some level; you're just proposing that it
> happens at a level that the user not see, and that the translation be
> tightly integrated into the development environment so that type
> errors and such are easier to read.
No, I'm proposing that there be no translation. (Or rather, if there
is any translation, it would be something entirely up to the compiler
author.)
In other words, I'm extending the core language by making 'lambda' a
fundamental component of the language. This is the reason you can
write '(lambda (a b) b a)' without needing some built-in 'swap'
primitive (or something equivalent using auxiliary stacks, etc) to
translate it to. Basic operations like 'swap' are defined in terms of
'lambda', not the other way around.
The result is significantly better error reporting, a reduction in
complexity on some level (you don't have to reduce things to the point-
free translation to reason about them as 'lambda' is a fundamental
part of the semantics), and a more efficient implementation (as you
don't have to quote values and compose quotations together at runtime
to create closures -- the implementor can choose whichever approach is
best).
Yes, you lose some interesting theoretical properties by defining the
language as such. I don't think any of these are of practical concern,
although if you can think of any, I'd be interesting in hearing them.
It seems all of the (minor) additional complexity would be born by the
implementor.
- John
rahul — 2008-03-19 21:48:56
....snip...
> There is. Special forms and macros need access to the entire tree to
> do their work. If you were to put 'define' at the end, then there's no
> way for it to act on the tree (without some bizarre backtracking).
Actually post script does:
/inc3 { 3 add } def
(and so does V :) )
I think the reverse is true, it is harder to go against the flow
when you are using postfix and give special treatment to syntactic markers
like define/let etc.
> Keep in mind that even [a b c] is really (lambda () a b c). Putting
> meta-level things like 'define' and 'let' up front also aids in
> readability.
not entirely. '[a b c]' is really '<quote literal> lambda' :)
On the second point, on One-sentence defitions (like the above) I find
the postfix define easier to parse visually. - I guess it boils down to
a matter of taste.
>> Naive question: Is there any reason why concatenative languages are
>> (uniformly) postfix? Would prefix work just as well, pushing
>> elements onto
>> the stack from right to left?
>
> Let's say these two are equivalent:
>
> -- postfix
> hypot -> sqr swap sqr + sqrt
>
> -- prefix
> sqrt + sqr swap sqr <- hypot
>
> Sure, both mean the same thing, but which is easier to read (provided
> you're used to reading left to right)?
--
William Tanksley, Jr — 2008-03-19 22:02:13
John Nowak <
john@...> wrote:
> translate it to. Basic operations like 'swap' are defined in terms of
> 'lambda', not the other way around.
I have proposed using stackshuffles instead of stack operators.
Lambdas take that a little too far, though; a stack operator or a
stack shuffle works in at worst constant time; a lambda may never
terminate, and it's impossible in principle to tell.
> The result is significantly better error reporting,
Only when you have a macro language laid on top of the base language
and the macro language has inadequate error reporting.
> a reduction in
> complexity on some level (you don't have to reduce things to the point-
> free translation to reason about them as 'lambda' is a fundamental
> part of the semantics),
Point-free is reducible to atomic components. Lambda is not. That's
not a reduction in complexity "on some level".
> and a more efficient implementation (as you
> don't have to quote values and compose quotations together at runtime
> to create closures -- the implementor can choose whichever approach is
> best).
I do agree that composing quotations shouldn't be necessary; but
indeed, it never was considered as such until Joy came along. More
power to Joy, but it's still only a convenience to be SOMETIMES used,
not a requirement.
> Yes, you lose some interesting theoretical properties by defining the
> language as such. I don't think any of these are of practical concern,
> although if you can think of any, I'd be interesting in hearing them.
> It seems all of the (minor) additional complexity would be born by the
> implementor.
You lose the ability to refactor a function using only cut-and-paste.
You lose the ability to reason about a program in chunks as small as
you want (that is, in a concatenative language if you see a phrase
whose meaning you don't grasp you can work with that phrase in
isolation, and you can be sure that the phrase in context means the
exact same thing).
Add variables, and you have to think about the program in the same way
the author thought about it.
> - John
-Wm
John Nowak — 2008-03-19 22:31:29
On Mar 19, 2008, at 5:48 PM, rahul wrote:
> ....snip...
>> There is. Special forms and macros need access to the entire tree to
>> do their work. If you were to put 'define' at the end, then there's
>> no
>> way for it to act on the tree (without some bizarre backtracking).
>
> Actually post script does:
> /inc3 { 3 add } def
>
> (and so does V :) )
This is a nice approach for a dynamically typed, late-binding
language. If 'def' is just a procedure that takes a symbol and a
quotation on the stack, you can do things like quote values on the
stack and define them at runtime for later use. There are a number of
nice tricks actually. All of the interpreters I've written for
concatenative languages work like this.
Unfortunately, this approach doesn't work for a statically-typed,
early-binding, compiled language. There are a number of reasons for
this:
1. It is necessary to run the program in order to get the definitions.
This is obviously massively complicates, well, everything really.
2. Type checking is awkward as you run into errors in the definition
before you know what the definition will be named. Error reporting
becomes more difficult.
3. There's no way to introduce recursive definitions as the recursive
call needs to be resolved before the name of the function is known.
4. Tool support is largely out the window.
5. You can't ensure that type checking or compilation will ever
terminate.
>> Keep in mind that even [a b c] is really (lambda () a b c). Putting
>> meta-level things like 'define' and 'let' up front also aids in
>> readability.
>
> not entirely. '[a b c]' is really '<quote literal> lambda' :)
The same issues described above apply here. This is actually even more
problematic as there's no way to guarantee that you can statically
resolve bindings.
- John
John Nowak — 2008-03-19 22:47:47
On Mar 19, 2008, at 6:02 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>
>> translate it to. Basic operations like 'swap' are defined in terms of
>> 'lambda', not the other way around.
>
> I have proposed using stackshuffles instead of stack operators.
> Lambdas take that a little too far, though; a stack operator or a
> stack shuffle works in at worst constant time; a lambda may never
> terminate, and it's impossible in principle to tell.
Indeed. Of course lambdas can do a lot more than just shuffle.
>> The result is significantly better error reporting,
>
> Only when you have a macro language laid on top of the base language
> and the macro language has inadequate error reporting.
Yes, we might imagine some wonderful macro system that has all sorts
of hooks into the type checker and can inform it in various ways to
allow it to somehow present code as it was written, preserving
variable names and so on, when giving type errors. I don't think this
is really possible in practice though without some massively
complicated system and a truly heroic series of macros. Ultimately, I
think it's a necessity for the type checker to be able to deal with
let/lambda/etc if you're going to offer them.
>> a reduction in
>> complexity on some level (you don't have to reduce things to the
>> point-
>> free translation to reason about them as 'lambda' is a fundamental
>> part of the semantics),
>
> Point-free is reducible to atomic components. Lambda is not. That's
> not a reduction in complexity "on some level".
Agreed. I don't dispute that this adds complexity to the semantics
overall.
>> and a more efficient implementation (as you
>> don't have to quote values and compose quotations together at runtime
>> to create closures -- the implementor can choose whichever approach
>> is
>> best).
>
> I do agree that composing quotations shouldn't be necessary; but
> indeed, it never was considered as such until Joy came along. More
> power to Joy, but it's still only a convenience to be SOMETIMES used,
> not a requirement.
Compositing quotations is equivalent to composing functions. I see
this as a necessity. In either case, I don't see how you can create
closures without quoting values and composing functions.
>> Yes, you lose some interesting theoretical properties by defining the
>> language as such. I don't think any of these are of practical
>> concern,
>> although if you can think of any, I'd be interesting in hearing them.
>> It seems all of the (minor) additional complexity would be born by
>> the
>> implementor.
>
> You lose the ability to refactor a function using only cut-and-paste.
You lose this the moment you introduce macros anyway. In either case,
you only lose it if you use variables. If you don't use them, you're
right where you were.
> You lose the ability to reason about a program in chunks as small as
> you want (that is, in a concatenative language if you see a phrase
> whose meaning you don't grasp you can work with that phrase in
> isolation, and you can be sure that the phrase in context means the
> exact same thing).
This ignores the possibility that lambdas might allow you to write
code that doesn't put you in those situations as often to begin with.
Variables are again only optional. Yes, you're stuck with them when
looking at someone else's code, but no language is going to prevent
programmers from writing terrible, confusing messes. I'm not a big fan
of denying programmers powerful tools on the grounds that others might
abuse them (not that that's what you were suggesting necessarily).
- John
rahul — 2008-03-19 23:20:15
...
> 1. It is necessary to run the program in order to get the definitions.
> This is obviously massively complicates, well, everything really.
>
> 2. Type checking is awkward as you run into errors in the definition
> before you know what the definition will be named. Error reporting
> becomes more difficult.
>
> 3. There's no way to introduce recursive definitions as the recursive
> call needs to be resolved before the name of the function is known.
Why cant we build a tree of tokens (first pass) and work with the tree?
ie, once we assure that the quotes are balanced, it resolves into a pure
expression tree (same as a prefix-lang) right?
> 4. Tool support is largely out the window.
>
> 5. You can't ensure that type checking or compilation will ever
> terminate.
>
>>> Keep in mind that even [a b c] is really (lambda () a b c). Putting
>>> meta-level things like 'define' and 'let' up front also aids in
>>> readability.
>>
>> not entirely. '[a b c]' is really '<quote literal> lambda' :)
>
> The same issues described above apply here. This is actually even more
> problematic as there's no way to guarantee that you can statically
> resolve bindings.
John Nowak — 2008-03-19 23:26:10
On Mar 19, 2008, at 7:20 PM, rahul wrote:
> ...
>> 1. It is necessary to run the program in order to get the
>> definitions.
>> This is obviously massively complicates, well, everything really.
>>
>> 2. Type checking is awkward as you run into errors in the definition
>> before you know what the definition will be named. Error reporting
>> becomes more difficult.
>>
>> 3. There's no way to introduce recursive definitions as the recursive
>> call needs to be resolved before the name of the function is known.
>>
>> 4. Tool support is largely out the window.
>>
>> 5. You can't ensure that type checking or compilation will ever
>> terminate.
>
> Why cant we build a tree of tokens (first pass) and work with the
> tree?
We can.
> ie, once we assure that the quotes are balanced, it resolves into a
> pure
> expression tree (same as a prefix-lang) right?
Yes, but I don't see how that helps with the five issues I mentioned.
- John
rahul — 2008-03-19 23:42:50
>>
>> Why cant we build a tree of tokens (first pass) and work with the
>> tree?
>
> We can.
>
>> ie, once we assure that the quotes are balanced, it resolves into a
>> pure
>> expression tree (same as a prefix-lang) right?
>
> Yes, but I don't see how that helps with the five issues I mentioned.
| 1. It is necessary to run the program in order to get the
| definitions. This is obviously massively complicates, well, everything
| really.
Once you have an expression tree, you are no longer waiting for the symbol
name to bind to .
| 2. Type checking is awkward as you run into errors in the definition
| before you know what the definition will be named. Error reporting
| becomes more difficult.
See above. You can check the wellformed-ness of the code during tree
creation,
once the tree is created, you know the symbol name to bind to, any further
error reporting can make use of the symbol that you have at the root.
| 3. There's no way to introduce recursive definitions as the recursive
| call needs to be resolved before the name of the function is known.
| 4. Tool support is largely out the window.
| 5. You can't ensure that type checking or compilation will ever
| terminate.
see above, once the expression tree is created, there is n't any difference
in what you can do with prefix and postfix notation.
i.e. 'sum(sum(1,2),3)' and '1 2 sum 3 sum' will yield the same tree,
sum - 3
|- sum - 2
|- 1
so what am I missing?
John Nowak — 2008-03-19 23:57:08
On Mar 19, 2008, at 7:42 PM, rahul wrote:
> | 1. It is necessary to run the program in order to get the
> | definitions. This is obviously massively complicates, well,
> everything
> | really.
>
> Once you have an expression tree, you are no longer waiting for the
> symbol
> name to bind to .
Yes, this all can work if define is a special form. It doesn't work if
define is a normal procedure though, which is, I thought, what you
were suggesting. If that's not what you're suggesting, then '(define
foo x y z)' or '\foo [x y z] define' is just a matter of taste
perhaps. Even then, I'd still prefer the former, if for no other
reason than it's apparent that 'define' is a special form.
- John
William Tanksley, Jr — 2008-03-20 00:03:30
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > John Nowak <john@...> wrote:
> >> translate it to. Basic operations like 'swap' are defined in terms of
> >> 'lambda', not the other way around.
> > I have proposed using stackshuffles instead of stack operators.
> > Lambdas take that a little too far, though; a stack operator or a
> > stack shuffle works in at worst constant time; a lambda may never
> > terminate, and it's impossible in principle to tell.
> Indeed. Of course lambdas can do a lot more than just shuffle.
Right; they can additionally do anything the rest of the language can
do. Only the rest of the language doesn't need them in order to do it.
> >> The result is significantly better error reporting,
> > Only when you have a macro language laid on top of the base language
> > and the macro language has inadequate error reporting.
> Yes, we might imagine some wonderful macro system that has all sorts
> of hooks into the type checker and can inform it in various ways to
> allow it to somehow present code as it was written, preserving
> variable names and so on, when giving type errors. I don't think this
> is really possible in practice though without some massively
> complicated system and a truly heroic series of macros. Ultimately, I
> think it's a necessity for the type checker to be able to deal with
> let/lambda/etc if you're going to offer them.
I admit that it's entirely unproven whether an inferential static type
checker can work at all in a concatenative language, let alone one
with macros. The ones we have now are not concatenative (or are only
partially concatenative), and it makes good theoretical sense that
this should be so.
A non-inferential typechecker would be able to do better, but I don't
see how such a thing would work with macros. Plus, inference is SUCH a
good thing.
> >> and a more efficient implementation (as you
> >> don't have to quote values and compose quotations together at runtime
> >> to create closures -- the implementor can choose whichever approach
> >> is best).
> > I do agree that composing quotations shouldn't be necessary; but
> > indeed, it never was considered as such until Joy came along. More
> > power to Joy, but it's still only a convenience to be SOMETIMES used,
> > not a requirement.
> Compositing quotations is equivalent to composing functions. I see
> this as a necessity. In either case, I don't see how you can create
> closures without quoting values and composing functions.
What do you mean "closures"? In my book, a closure is a function which
refers to lexically available variables outside its local scope. A
purely concatenative language does not have variables, and so does not
have closures in that sense.
I think you're referring to partially applied functions, which are
useful when one wishes to specialize a function. Forth is able to do
that, albeit messily, without quotations or their concatenation.
There's a lot you can't easily do in Forth; Factor is in many ways a
remediation of that. See
http://factor-language.blogspot.com/2007/08/compiled-curry.html for
the obvious way to do partial application in Factor.
> >> Yes, you lose some interesting theoretical properties by defining the
> >> language as such. I don't think any of these are of practical
> >> concern,
> >> although if you can think of any, I'd be interesting in hearing them.
> >> It seems all of the (minor) additional complexity would be born by
> >> the implementor.
> > You lose the ability to refactor a function using only cut-and-paste.
> You lose this the moment you introduce macros anyway.
No, you only lose it over syntax macros, not expansion macros.
> In either case,
> you only lose it if you use variables. If you don't use them, you're
> right where you were.
I concede this, of course.
> > You lose the ability to reason about a program in chunks as small as
> > you want (that is, in a concatenative language if you see a phrase
> > whose meaning you don't grasp you can work with that phrase in
> > isolation, and you can be sure that the phrase in context means the
> > exact same thing).
> This ignores the possibility that lambdas might allow you to write
> code that doesn't put you in those situations as often to begin with.
Well, actually, rather than ignoring it, it dismisses the possibility
with a tired wave of its hand. Metaphorically speaking. Seriously,
code has to be read carefully to be understood. Nothing will fix that.
There is no algorithm that will cause code to be understood.
I do concede and admit that having more tools is more practical than
having fewer tools, so including locals and lexical scoping is better
than not doing so; the problem isn't the locals, but the fact that
most programmers are trained in nothing but them, and use them as
crutches for their own lack of understanding rather than as poles to
vault over problems that are truly helped by them. (Problems such as
the infamous quadratic formula. I'm preparing an alternate, purely
concatenative approach to that, one which is not as pretty but has
interesting features to it.)
> Variables are again only optional. Yes, you're stuck with them when
> looking at someone else's code, but no language is going to prevent
> programmers from writing terrible, confusing messes. I'm not a big fan
> of denying programmers powerful tools on the grounds that others might
> abuse them (not that that's what you were suggesting necessarily).
I concede that this is a large factor in my worry, and I concede that
I share your attitude in general.
I want to make it clear that there are many techniques that result in
clear, simple concatenative code, and using locals is a distraction
from them. Concatenative languages are in their infancy.
> - John
-Wm
John Nowak — 2008-03-20 00:27:37
On Mar 19, 2008, at 8:03 PM, William Tanksley, Jr wrote:
> I admit that it's entirely unproven whether an inferential static type
> checker can work at all in a concatenative language,
I swear I'm going to post that example soon...
> let alone one with macros.
I don't see why macros would complicate the type checker. Perhaps you
were suggesting that macros complicate concatenativity.
>> Compositing quotations is equivalent to composing functions. I see
>> this as a necessity. In either case, I don't see how you can create
>> closures without quoting values and composing functions.
>
> What do you mean "closures"? In my book, a closure is a function which
> refers to lexically available variables outside its local scope. A
> purely concatenative language does not have variables, and so does not
> have closures in that sense.
What I'm suggesting is code like this, where 'foo' is a function that
takes an argument 'x' and returns a function with 'x' closed over:
x foo = [bar x quux]
That would get translated to point-free code like this (assuming a
clever translation mechanism):
foo = quote [bar] swap compose [quux] compose
It seems that there's no way to do a proper translation of something
like 'foo' without 'quote' and 'compose'.
> See http://factor-language.blogspot.com/2007/08/compiled-curry.html
> for
> the obvious way to do partial application in Factor.
The obvious way to implement partial application is in terms of quote
and compose:
pa = [quote] dip compose
The Factor example seems to only avoid this when the function created
via partial application is not returned from the context in which it
was created.
>>> You lose the ability to refactor a function using only cut-and-
>>> paste.
>>
>> You lose this the moment you introduce macros anyway.
>
> No, you only lose it over syntax macros, not expansion macros.
Fair enough. I was assuming a more powerful macro system.
> I do concede and admit that having more tools is more practical than
> having fewer tools, so including locals and lexical scoping is better
> than not doing so; the problem isn't the locals, but the fact that
> most programmers are trained in nothing but them, and use them as
> crutches for their own lack of understanding rather than as poles to
> vault over problems that are truly helped by them.
This is a good point, although I see this as more of a problem to be
solved via education and community conventions than anything else
really.
> (Problems such as the infamous quadratic formula. I'm preparing an
> alternate, purely concatenative approach to that, one which is not
> as pretty but has interesting features to it.)
Sometimes though, you just need something to work as quickly as
possible. If your language requires that you sit down and ponder how
to translate something like the quadratic formula, you have a problem.
I'm not suggesting that you agree or disagree with this; just stating
my opinion.
> Concatenative languages are in their infancy.
This is a very, very good point. I'm experimenting with one particular
aspect of concatenative languages; that is, placing them into a typed
context. Alternatively, I'm experimenting with effect systems and type
systems in a concatenative context if you'd prefer to put it that way.
There's so much that I'm necessarily ignoring to be able to focus on
these things. I'm still very interested in the purely concatenative
approach as a way of writing simple, concise programs in a highly
simplified language. The language I'm working on is not that language;
I'm trying to convince myself to focus on just one for the moment.
- John
Stevan Apter — 2008-03-20 01:43:41
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
:
>
> I want to make it clear that there are many techniques that result in
> clear, simple concatenative code, and using locals is a distraction
> from them. Concatenative languages are in their infancy.
this is a very important point to make. also important is that people
write applications in joy/cat/factor/whatever. that's really the only
way to discover new techniques and push the language(s) forward. it
can't be done by theory alone.
>
>> - John
>
> -Wm
>
Don Groves — 2008-03-20 02:48:18
On Mar 19, 2008, at 19:11 , John Nowak wrote:
>
> On Mar 19, 2008, at 4:51 PM, Joe Bowbeer wrote:
>
>> On Wed, Mar 19, 2008 at 11:58 AM, John Nowak wrote:
>>
>>> Postfix, as are *all* procedures. Only special forms are infix.
>>> Perhaps this is a better declaration form:
>>>
>>> (define (a b c quad)
>>> ...)
>>>
>>> - John
>>>
>>
>> Better. Better yet is:
>>
>> (...
>> (a b c quad) define)
>>
>> This maintains a consistent right-to-left reading direction. If
>> postfix is
>> the "right thing," there's no such thing as too much, right?
>
> There is. Special forms and macros need access to the entire tree to
> do their work. If you were to put 'define' at the end, then there's no
> way for it to act on the tree (without some bizarre backtracking).
> Keep in mind that even [a b c] is really (lambda () a b c). Putting
> meta-level things like 'define' and 'let' up front also aids in
> readability.
>
>> Naive question: Is there any reason why concatenative languages are
>> (uniformly) postfix? Would prefix work just as well, pushing
>> elements onto
>> the stack from right to left?
>
> Let's say these two are equivalent:
>
> -- postfix
> hypot -> sqr swap sqr + sqrt
>
> -- prefix
> sqrt + sqr swap sqr <- hypot
I'm partial to the syntax I'm using in ACL:
[sqr swap sqr + sqrt] -> hypot
This reads left-to-right and solves the problem of the
as yet undefined symbol, hypot, which is read by ->
Actually, I use "def" instead of "->" for clarity but the
meaning is the same.
--
don
> Sure, both mean the same thing, but which is easier to read (provided
> you're used to reading left to right)?
>
> - John
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>
William Tanksley, Jr — 2008-03-20 16:03:53
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > I admit that it's entirely unproven whether an inferential static type
> > checker can work at all in a concatenative language,
> > let alone one with macros.
> I don't see why macros would complicate the type checker. Perhaps you
> were suggesting that macros complicate concatenativity.
I was replying to your message, in which you appear to be talking
specifically about the problems of making the type checker emit
reasonable error messages in the presence of a sophisticated macro
system. Did you mean something else?
> >> Compositing quotations is equivalent to composing functions. I see
> >> this as a necessity. In either case, I don't see how you can create
> >> closures without quoting values and composing functions.
> > What do you mean "closures"? In my book, a closure is a function which
> > refers to lexically available variables outside its local scope. A
> > purely concatenative language does not have variables, and so does not
> > have closures in that sense.
> What I'm suggesting is code like this, where 'foo' is a function that
> takes an argument 'x' and returns a function with 'x' closed over:
> x foo = [bar x quux]
Okay, got it. You want dynamic code assembly. Forth (for example) does
this by driving the compiler, which is available at runtime. Joy uses
lists and interprets them. Either way, same basic idea: you need a
word that incorporates a value as a literal and a word that
incorporates a value as a function call into an ongoing definition.
Your "compositing functions" is my "incorporates a value as a function call".
> > See http://factor-language.blogspot.com/2007/08/compiled-curry.html
> > for the obvious way to do partial application in Factor.
> The obvious way to implement partial application is in terms of quote
> and compose:
> pa = [quote] dip compose
You're right; I apologize. I meant the obvious way to make it
reasonably fast, not the obvious way to do it.
> The Factor example seems to only avoid this when the function created
> via partial application is not returned from the context in which it
> was created.
I don't see why this is a limitation.
> > I do concede and admit that having more tools is more practical than
> > having fewer tools, so including locals and lexical scoping is better
> > than not doing so; the problem isn't the locals, but the fact that
> > most programmers are trained in nothing but them, and use them as
> > crutches for their own lack of understanding rather than as poles to
> > vault over problems that are truly helped by them.
> This is a good point, although I see this as more of a problem to be
> solved via education and community conventions than anything else
> really.
You're totally right. I see part of the purpose of this group as
finding what those conventions are, or at least might be. I admit that
I take that purpose too seriously; there's also another purpose of
this group, to find and explore uses of concatenative languages (which
definitely includes useful things like math syntax and lambda syntax).
Stevan makes a good point -- as fun as theory is, we need written
code, and even an application written by a newbie who had to lean on
the crutch of local variables almost the entire time is probably more
likely to contain something unique than something written by an old
Forther who's set in his ways.
With that said, it makes sense to learn from the programmers of the
old stack languages. There are two rules they use that seem
appropriate: avoid syntax-changing macros, and avoid local variables.
The interesting lesson for ME to take from these are that in both
cases, the language provides facilities for these; the instruction to
"avoid" them is just a recommendation, not a rule.
> > (Problems such as the infamous quadratic formula. I'm preparing an
> > alternate, purely concatenative approach to that, one which is not
> > as pretty but has interesting features to it.)
> Sometimes though, you just need something to work as quickly as
> possible. If your language requires that you sit down and ponder how
> to translate something like the quadratic formula, you have a problem.
Then every language short of Mathematica or MathCAD has "a problem" --
the quadratic formula isn't an obvious translation even in a lambda
notation, and it's one of the simpler practical formulas.
We're dealing with largely imperative languages here; they're always
going to be clearer when expressing algorithms than they are when
expressing formulas. This is one reason I find the idea of a math
sublanguage attractive, because it adds something that the main
language simply does not possess.
> > Concatenative languages are in their infancy.
> This is a very, very good point. I'm experimenting with one particular
> aspect of concatenative languages; that is, placing them into a typed
> context. Alternatively, I'm experimenting with effect systems and type
> systems in a concatenative context if you'd prefer to put it that way.
Either way, your work is very interesting. I don't know what an
"effect system" is, by the way.
> There's so much that I'm necessarily ignoring to be able to focus on
> these things. I'm still very interested in the purely concatenative
> approach as a way of writing simple, concise programs in a highly
> simplified language. The language I'm working on is not that language;
> I'm trying to convince myself to focus on just one for the moment.
That's a very good point. Your field contains enough to explore
anyhow; no need to add yet more unknowns.
> - John
-Wm
John Nowak — 2008-03-20 17:41:55
On Mar 20, 2008, at 12:03 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>>
>
>> I don't see why macros would complicate the type checker. Perhaps you
>> were suggesting that macros complicate concatenativity.
>
> I was replying to your message, in which you appear to be talking
> specifically about the problems of making the type checker emit
> reasonable error messages in the presence of a sophisticated macro
> system. Did you mean something else?
Ah, no, I didn't. I thought you were suggesting macros would make type
inference itself more difficult, not simply the ability to report
useful errors.
>> The Factor example seems to only avoid this when the function created
>> via partial application is not returned from the context in which it
>> was created.
>
> I don't see why this is a limitation.
It's not; it's quite nice in fact. I was only pointing out that it
isn't a general solution. You do need the ability to quote/compose in
certain cases.
> We're dealing with largely imperative languages here; they're always
> going to be clearer when expressing algorithms than they are when
> expressing formulas.
Perhaps this shows a difference in our thinking here. I'm interested
in making concatenative languages feel as declarative as possible. It
seems to me that variables are necessary to achieve that in some cases.
>> This is a very, very good point. I'm experimenting with one
>> particular
>> aspect of concatenative languages; that is, placing them into a typed
>> context. Alternatively, I'm experimenting with effect systems and
>> type
>> systems in a concatenative context if you'd prefer to put it that
>> way.
>
> Either way, your work is very interesting. I don't know what an
> "effect system" is, by the way.
An effect system is what Haskell programmers wish they had, even if
they don't know it. Such a system as it works in Fifth allows you to
freely mix effectful and pure code however you wish. The effect system
is powerful enough to sort out what you're doing and, with complete
accuracy, tell you which functions are pure and which aren't. In the
case of combinators, it can tell you which functions provided to the
combinator must be pure in order for the total effect of using the
combinator to be pure. If a programmer isn't at all interested in
purity, they simply ignore the system.
The system can be used to enforce that certain functions are pure
which is very useful when dealing with things like contracts, futures,
map-reduce, et cetera. On the other hand, it allows free use of things
like shared mutable arrays without them contaminating the rest of your
code. Unlike the Haskell situation with monads, you don't run into all
sorts of composability issues. See
http://tinyurl.com/yvfhnf for some
of Oleg's thoughts on this.
- John
Stevan Apter — 2008-03-20 22:54:48
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, March 20, 2008 11:03 AM
Subject: Re: [stack] impure concatenativity: let without translation
> John Nowak <john@...> wrote:
>> William Tanksley, Jr wrote:
>> > I admit that it's entirely unproven whether an inferential static type
>> > checker can work at all in a concatenative language,
>> > let alone one with macros.
>
>> I don't see why macros would complicate the type checker. Perhaps you
>> were suggesting that macros complicate concatenativity.
>
> I was replying to your message, in which you appear to be talking
> specifically about the problems of making the type checker emit
> reasonable error messages in the presence of a sophisticated macro
> system. Did you mean something else?
>
>> >> Compositing quotations is equivalent to composing functions. I see
>> >> this as a necessity. In either case, I don't see how you can create
>> >> closures without quoting values and composing functions.
>
>> > What do you mean "closures"? In my book, a closure is a function which
>> > refers to lexically available variables outside its local scope. A
>> > purely concatenative language does not have variables, and so does not
>> > have closures in that sense.
>
>> What I'm suggesting is code like this, where 'foo' is a function that
>> takes an argument 'x' and returns a function with 'x' closed over:
>> x foo = [bar x quux]
>
> Okay, got it. You want dynamic code assembly. Forth (for example) does
> this by driving the compiler, which is available at runtime. Joy uses
> lists and interprets them. Either way, same basic idea: you need a
> word that incorporates a value as a literal and a word that
> incorporates a value as a function call into an ongoing definition.
>
> Your "compositing functions" is my "incorporates a value as a function call".
>
>> > See http://factor-language.blogspot.com/2007/08/compiled-curry.html
>> > for the obvious way to do partial application in Factor.
>> The obvious way to implement partial application is in terms of quote
>> and compose:
>> pa = [quote] dip compose
>
> You're right; I apologize. I meant the obvious way to make it
> reasonably fast, not the obvious way to do it.
>
>> The Factor example seems to only avoid this when the function created
>> via partial application is not returned from the context in which it
>> was created.
>
> I don't see why this is a limitation.
>
>> > I do concede and admit that having more tools is more practical than
>> > having fewer tools, so including locals and lexical scoping is better
>> > than not doing so; the problem isn't the locals, but the fact that
>> > most programmers are trained in nothing but them, and use them as
>> > crutches for their own lack of understanding rather than as poles to
>> > vault over problems that are truly helped by them.
>
>> This is a good point, although I see this as more of a problem to be
>> solved via education and community conventions than anything else
>> really.
>
> You're totally right. I see part of the purpose of this group as
> finding what those conventions are, or at least might be. I admit that
> I take that purpose too seriously; there's also another purpose of
> this group, to find and explore uses of concatenative languages (which
> definitely includes useful things like math syntax and lambda syntax).
>
> Stevan makes a good point -- as fun as theory is, we need written
> code, and even an application written by a newbie who had to lean on
> the crutch of local variables almost the entire time is probably more
> likely to contain something unique than something written by an old
> Forther who's set in his ways.
>
> With that said, it makes sense to learn from the programmers of the
> old stack languages. There are two rules they use that seem
> appropriate: avoid syntax-changing macros, and avoid local variables.
> The interesting lesson for ME to take from these are that in both
> cases, the language provides facilities for these; the instruction to
> "avoid" them is just a recommendation, not a rule.
my experience can't be unique. i've been close to language development
for 30 years. the APL community had a high proportion of kibbitzers,
urging the addition of this or that language extension. the developers
(who were also users -- no one wrote more APL code than iverson) were
always searching for new ways to solve problems which emanated from
the user community. sometimes those were unexpected uses of existing
resources, and sometimes the problems clumped together in some new
way to suggest natural language extensions. the evolution of k in
the direction of database programming is a case in point: new primitives,
new datatypes. but that wouldn't have happened if the language's author
and many of his users weren't themselves immersed in database problems.
so the developer can't restrict his attention to the inner workings
of the language. he needs data about what's important and what's not.
those facts cannot be acquired purely deductively.
i agree with billy that teaching a concatenative language with training
wheels might be a useful approach. newbies to APL often get a mixed diet of
looping solutions and array solutions. good programmers will shed the
former quickly. others won't.
>
>> > (Problems such as the infamous quadratic formula. I'm preparing an
>> > alternate, purely concatenative approach to that, one which is not
>> > as pretty but has interesting features to it.)
>
>> Sometimes though, you just need something to work as quickly as
>> possible. If your language requires that you sit down and ponder how
>> to translate something like the quadratic formula, you have a problem.
>
> Then every language short of Mathematica or MathCAD has "a problem" --
> the quadratic formula isn't an obvious translation even in a lambda
> notation, and it's one of the simpler practical formulas.
>
> We're dealing with largely imperative languages here; they're always
> going to be clearer when expressing algorithms than they are when
> expressing formulas. This is one reason I find the idea of a math
> sublanguage attractive, because it adds something that the main
> language simply does not possess.
>
>> > Concatenative languages are in their infancy.
>
>> This is a very, very good point. I'm experimenting with one particular
>> aspect of concatenative languages; that is, placing them into a typed
>> context. Alternatively, I'm experimenting with effect systems and type
>> systems in a concatenative context if you'd prefer to put it that way.
>
> Either way, your work is very interesting. I don't know what an
> "effect system" is, by the way.
>
>> There's so much that I'm necessarily ignoring to be able to focus on
>> these things. I'm still very interested in the purely concatenative
>> approach as a way of writing simple, concise programs in a highly
>> simplified language. The language I'm working on is not that language;
>> I'm trying to convince myself to focus on just one for the moment.
>
> That's a very good point. Your field contains enough to explore
> anyhow; no need to add yet more unknowns.
>
>> - John
>
> -Wm
>
William Tanksley, Jr — 2008-03-20 22:18:54
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > We're dealing with largely imperative languages here; they're always
> > going to be clearer when expressing algorithms than they are when
> > expressing formulas.
> Perhaps this shows a difference in our thinking here. I'm interested
> in making concatenative languages feel as declarative as possible. It
> seems to me that variables are necessary to achieve that in some cases.
That's a great goal. One odd thing about concatenative languages is
that even the least functionally pure of them (like Forth) tends to
feel declarative while I'm coding in it -- my mental patterns are
similar to the ones I fall into while coding in declarative functional
languages. But, at the same time, Forth is undeniably imperative.
There's definitely more that can be done to make concatenative
languages that feel declarative. I suspect, however, that making
concatenative languages that simply look familiar to applicative
language programmers is risky since it can cause false positives.
But I'm not sure that local variables are bad here. I'm of two minds on this.
> > Either way, your work is very interesting. I don't know what an
> > "effect system" is, by the way.
> An effect system is what Haskell programmers wish they had, even if
> they don't know it. Such a system as it works in Fifth allows you to
> freely mix effectful and pure code however you wish. The effect system
> is powerful enough to sort out what you're doing and, with complete
> accuracy, tell you which functions are pure and which aren't. In the
Oh, very nice!
> - John
-Wm
William Tanksley, Jr — 2008-04-03 22:35:37
John Nowak <
john@...> wrote:
> Just moments ago, I gave this example of the quadratic formula:
> (define (quad a b c)
> (let ((d b 4 a c * * -)
> (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)
> (x 2 a *)
> (p b r - x /)
> (n b r + x /))
> p n))
> How it works should be obvious after you get used to looking at this
> sort of prefix/postfix syntax.
I'd like to deal with this post in two parts: first, exploring the
interesting issues you raise, and second, <ironic>solving once and for
all</ironic> the pesky problem of finding the roots of a quadratic
equation in a concatenative language. I'll do the latter in a distinct
post.
IMO, this is a very nice convention for special forms such as define,
let, and others. It would in general make macros a lot less risky,
since their scope would be explicitly delimited.
To take this to an extreme, one could imagine making the parens
optionally switchable with xml-style notation; such notation is useful
when the special form spans a large block, as for example with Joy's
LIBRA form. One shouldn't do this for a small block, but just as an
example:
<define>(quad a b c)
<let>(d b 4 a c * * - )
(r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if )
(x 2 a * )
<p> b r - x / </p>
<n> b r + x / </n>
</let>
p n
</define>
The rules for the transform I used should be quite obvious, and I
failed to perform it in some places just to make it clear that it's
purely syntactic, totally optional, and has no semantic effect.
Such a syntax would be unbearable over short ranges (like in the 'let'
above), but I suspect it would be convenient over large syntatic
blocks -- and would make counting parentheses a thing of the past.
I started this as a joke; now I'm tempted to modify a Scheme
interpreter to see if it's realistic.
> It's a very nice way to write this
> function; arguably nicer than what you can do in Scheme as the
> multiple values returned can be easily consumed (or ignored) by
> another function. For example, if we only cared about the positive
> root, we could do 'quad pop'.
Agreed.
> What I'm suggesting is that dropping any pretense of being purely
> concatenative offers some clear usability benefits with no loss in
> expressiveness.
The only loss is in referential transparency -- it's no longer true
that cut and paste is always precisely sufficient to perform an
"extract method" refactoring. BUT, frankly, that's not an unworkable
loss.
> It would likely offer efficiency advantages as well;
> splicing quotes together to embed variables into the middle of
> anonymous functions is less than fun.
I wouldn't encourage doing that anyways, but it's true that some
problems lend themselves nicely to this type of solution.
> Are there any other proposals for an impure (or, more nicely,
> "hybrid") concatenative language out there?
> What are the negative practical implications of being impure?
The problem is that we don't know. I'd like to understand the negative
practical implications of being purely concatenative. I know they
exist.
> - John
-Wm
John Nowak — 2008-04-04 02:03:52
On Apr 3, 2008, at 6:35 PM, William Tanksley, Jr wrote:
> second, <ironic>solving once and for
> all</ironic> the pesky problem of finding the roots of a quadratic
> equation in a concatenative language. I'll do the latter in a distinct
> post.
I look forward to it. I assume it's nicely doable even if I've not
seen it done yet.
> <define>(quad a b c)
> <let>
> ...
> </let>
> p n
> </define>
>
> Such a syntax would be unbearable over short ranges (like in the 'let'
> above), but I suspect it would be convenient over large syntatic
> blocks -- and would make counting parentheses a thing of the past.
In all honesty, I've not ever counted parentheses since I began using
DrScheme for all my Scheme editing needs years ago. I really do think
this is a tool problem. For example, to give the benefits of what you
show here, the editor could flash the name of the first element of
each list as you close them. Mousing over a closing paren could do the
same. I do think the current state of things though in DrScheme (and
presumably emacs) is quite sufficient.
>> What are the negative practical implications of being impure?
>
> The problem is that we don't know. I'd like to understand the negative
> practical implications of being purely concatenative. I know they
> exist.
After working more on this recently, I've become convinced that having
a concatenative language that is not *purely* concatenative is simply
a horrible idea (macros and so on are fine). It complicates not only
the implementation, but also how you can fundamentally reason about
the language. Additionally, as you say, we simply don't know
everything we'd be losing yet.
I've mentioned this before, but I believe such an argument possibly
extends to recursive definitions as well (e.g. fact = [zero?] [succ]
[pred dup pred fact *] if). To make a completely and wholly
unconvincing argument, such definitions destroy the soundness of my
termination checker. A special form like 'letrec' would do similarly.
At the moment, I'm going forward with a purely concatenative language
that also does away with recursive definitions and is hence
"nameless". In other words, there's no difference between a function
definition and a (simple expanding) macro definition except in terms
of implementation details (provided that quotations are opaque). I've
posted a bit about this previously, and I'm now beginning to
understand some of the implications with respect to the type system
and optimization possibilities.
I don't think it should be surprising though that such a "restriction"
helps reasoning; if the type system prevents an 'm' combinator in any
form ('dup i'), then your recursive possibilities depend entirely on
the combinator set you are given. You therefore only need to
understand the fundamental properties of each combinator to understand
the properties of a program as a whole. Any sort of indefinite looping
would require use of an appropriate combinator (e.g. "while"). You can
also take advantage of the situation to prove that a given function
uses a bounded amount of stack (where functions involving 'linrec' or
similar would not).
- John
William Tanksley, Jr — 2008-04-04 18:30:51
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > second, <ironic>solving once and for
> > all</ironic> the pesky problem of finding the roots of a quadratic
> > equation in a concatenative language. I'll do the latter in a distinct
> > post.
> I look forward to it. I assume it's nicely doable even if I've not
> seen it done yet.
Given all the time I've had, one would think I'd be finished already.
I'm not. (Of course, I haven't really put much time into it.)
Don't expect too much -- I don't make the quadratic equation's
*formula* obvious in a concatenative syntax. Instead, I make
completing the square's *process* obvious. From what I can see,
formulas learned in infix will only be recognizable when expressed
using infix. But because computers perform processes better than they
"evaluate formulas", I can always express the quadratic formula as its
equivalent process -- and even if you've never learned how to complete
the square, you'll be able to confirm or deny that the process will
find the roots of the polynomial.
> > <define>(quad a b c)
> > <let>
> > ...
> > </let>
> > p n
> > </define>
> > Such a syntax would be unbearable over short ranges (like in the 'let'
> > above), but I suspect it would be convenient over large syntatic
> > blocks -- and would make counting parentheses a thing of the past.
> In all honesty, I've not ever counted parentheses since I began using
> DrScheme for all my Scheme editing needs years ago. I really do think
I'll check it out -- I do have some recently acquired Scheme editing needs.
> this is a tool problem. For example, to give the benefits of what you
> show here, the editor could flash the name of the first element of
> each list as you close them. Mousing over a closing paren could do the
> same. I do think the current state of things though in DrScheme (and
> presumably emacs) is quite sufficient.
The nice thing about such an editor is that it's essentially a static
debugger. I've often thought of doing something like that for a
concatenative language -- flashing thin little arrows to and from the
sources and sinks of the data each word is consuming.
But... I've never found flashing parens sufficient for reading complex
structures, neither in SQL nor in Lisp. I want to be able to *look* at
any part of the code and have some hope of seeing what it's connected
to. I suppose I don't have an actual complaint with Scheme's syntax,
really, and I've never had a problem figuring out Scheme's parens
(after I learned it).
> >> What are the negative practical implications of being impure?
> > The problem is that we don't know. I'd like to understand the negative
> > practical implications of being purely concatenative. I know they
> > exist.
> After working more on this recently, I've become convinced that having
> a concatenative language that is not *purely* concatenative is simply
> a horrible idea (macros and so on are fine). It complicates not only
> the implementation, but also how you can fundamentally reason about
> the language. Additionally, as you say, we simply don't know
> everything we'd be losing yet.
Good arguments. I'll have to remember them.
> I've mentioned this before, but I believe such an argument possibly
> extends to recursive definitions as well (e.g. fact = [zero?] [succ]
> [pred dup pred fact *] if). To make a completely and wholly
> unconvincing argument, such definitions destroy the soundness of my
> termination checker. A special form like 'letrec' would do similarly.
Now this is fascinating -- and I find your termination checker
argument to be profoundly convincing. I've long been interested in
establishing a more useful lower bound for termination proofs.
(Charity always succeeds,
http://pll.cpsc.ucalgary.ca/charity1/www/home.html, but the language
seems to have passed away.)
In general, limiting the capabilities of a language in order to make
reasoning about the language has much precedent; that was (as we've
discussed) the original purpose of the FP language.
> At the moment, I'm going forward with a purely concatenative language
> that also does away with recursive definitions and is hence
> "nameless". In other words, there's no difference between a function
> definition and a (simple expanding) macro definition except in terms
> of implementation details (provided that quotations are opaque). I've
> posted a bit about this previously, and I'm now beginning to
> understand some of the implications with respect to the type system
> and optimization possibilities.
Very nice.
> - John
-Wm
John Nowak — 2008-04-04 20:39:53
On Apr 4, 2008, at 2:30 PM, William Tanksley, Jr wrote:
>> this is a tool problem. For example, to give the benefits of what you
>> show here, the editor could flash the name of the first element of
>> each list as you close them. Mousing over a closing paren could do
>> the
>> same. I do think the current state of things though in DrScheme (and
>> presumably emacs) is quite sufficient.
>
> The nice thing about such an editor is that it's essentially a static
> debugger. I've often thought of doing something like that for a
> concatenative language -- flashing thin little arrows to and from the
> sources and sinks of the data each word is consuming.
DrScheme will do exactly this when you hover over bindings (after
clicking "check syntax"). Very useful sometimes... I've not seen
anything else that does similarly.
- John