sweetening concatenative syntax
John Nowak — 2008-03-05 09:04:14
I've had some thoughts recently on syntactic additions to
concatenative languages that seem potentially quite useful. At the
very least, they would put an end to silly discussions over largely
imagined deficiencies of postfix syntax and pointfree programming.
This is perhaps crucial if we expect any significant uptake of
concatenative languages.
Below are the four extensions that I'm proposing. I'm strongly
considering one or more in the language I'm currently working on
(named "Fifth" for what are likely obvious reasons). The first two
should be fairly uncontroversial. The latter two are simple
translations I've not seen discussed before that seem potentially very
useful in practice.
I. Lambda Expressions
Assuming functions have the syntax '[<body>]', it seems useful to
introduce the syntax '[<bindings> -> <body>], where bindings are
ordered with the top of the stack towards the right as is familiar.
For example, the following two functions are equivalent:
foo :: -> [a b -> b a a]
foo = [swap dup]
foo = [a b -> b a a]
Note that the type syntax mimics the lambda expression syntax (or vice
versa if you prefer). The type notation is similar to Cat's with minor
alterations for the purposes of brevity. In particular, scalar
variables are all lowercase, row variables are all uppercase, and
concrete types are title-case and of at least two characters (to avoid
confusion with row variables).
Variables should, of course, be lexically scoped. A translation of
expressions with lambdas to efficient pointfree stack-based code is
not especially difficult. This is the case regardless of if the
language is linear (which introduces only small complications), typed,
or "lacking" a retain stack. Of course, I elide the translation here
for the sake of... space.
II. Local Function Variables
If you permit lambdas, it makes sense to offer a simple syntax for
declaring functions with named variables. This is similar to how
Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo
(lambda (<bindings>) <body>))'. The declaration syntax proposed here
mimics use. In particular, the name of the function being defined
occurs *after* the arguments.
The following two statements are equivalent (where 'i' is the identity
combinator with the type 'A (A -> B) -> B'):
a b foo = b a a
foo = [a b -> b a a] i
Here's another example in which 'unlist' is a deconstructor for a
list; the first function provided handled the null case and the second
handles the cons case:
unlist :: A [b] (A -> C) (A b [b] -> C) -> C
map :: [a] (a -> b) -> [b]
list f map = list [] [x xs -> x f i xs f map cons] unlist
It should be noted that both lambda expressions and functions declared
with the local variable syntax may use more items on the stack than
they explicitly bind. For example, the following definition of map is
equivalent to the above and likely preferable in practice:
f map = [] [x xs -> x f i xs f map cons] unlist
III. Prefix Notation
It occurred to me recently that there exists a simple syntactic
translation from prefix code (a la Scheme), where '(foo a b c)' is the
application of 'foo' to three arguments, to postfix code. This
translation can be done without any type information. The translation
consists of simply removing the parenthesis and placing the first
element at the end. If that first element is a local binding or a
lambda expression, an 'i' is prepended to cause it to be evaluated.
Here are some simple translation examples:
(cons 1 null) => 1 null cons
(+ (- 1 2) 3) => 1 2 - 3 +
[f -> (f 10)] => [f -> 10 f i]
f foo = (f 5) => f foo = 5 f i
Interestingly, you get partial application for free:
double = (* 2)
One thing that may seem like a problem is that '(1 2 3)' will be
translated to '(2 3 1)' when really an error should occur as '1' is
not a function. However, that's not the case: '1' *is* a function.
More precisely, it is a row polymorphic function that consumes a stack
and yields a new stack (1 :: A -> A int). As such, the above syntactic
translation is completely valid and it would be wrong to reject it.
Prefix notation may seem like a curiosity at first, perhaps existing
only to lure over those familiar with prefix notation. However, I'd
argue that prefix notation makes certain code objectively easier to
read. This is especially the case when dealing with deconstructors
like 'if' or 'unlist' as the higher order function of primary interest
is "announced" earlier in the definition. In the following example,
both functions are equivalent:
f map = [] [x xs -> x f i xs f map cons] unlist
f map =
(unlist []
[x xs -> x f i xs f map cons])
(Perhaps this is not the best example. Substitute a better one with
nested ifs.)
Prefix notation also has the benefit that you can express "nested"
code (as above) in a way that allows editors to automatically intent
properly. This is not at all the case with purely postfix code where
type information and perhaps some heuristics would need to be involved
to produce acceptable indentation.
Here's a rewriting of map using *only* prefix notation in a way that
most any Scheme or Haskell programmer would find comfortable:
f map =
(unlist []
[x xs -> (cons (f x) (map xs f))])
IV. Indentation
Prefix notation is often criticized for being overly verbose or noisy.
The Python solution is to use indentation instead of paired
delimiters, but this introduces a number of problems: It's harder for
machines to generate valid code, pasting between sources can be messy,
editors can't really automatically re-indent code, plenty of people
(myself included) hate it, etc.
The correct way to address this problem (if you are to address it at
all) is to do what Haskell does and offer *optional* indentation-
sensitive syntax that gets translated to the more explicit form. This
can be implemented as a relatively trivial pre-parser pass and does
not require modification of the parser itself.
Indentation-sensitive syntax is introduced with a colon. Here are some
simple examples showing how indentation-sensitive code is translated
to prefix code which is then translated to "normal" code:
a b c: d e f => a b (c d e f) => a b d e f c
a b c:
d e f: => a b (c d e (f g h)) => a b d e g h f c
g h
Finally, here again is our map example, this time even spiffier:
f map = unlist:
[]
[x xs -> cons: (f x) (map xs f)]
This looks quite close to the Haskell version, except that our
programs are, after translation, still expressed only in terms of the
functional forms of composition and quotation! (I was wrong in an
earlier email when I started that composition is the only functional
form in Joy. Quotation is also a functional form.) This definition is
arguably easier to read than the postfix, pointfree alternative, as it
clearly announces at the start that 'map' is a function that
destructures a list, details the result of the destructization at the
start of the relevant line, and indicates directly after that the
result of the function will be a list via the prefixing of 'cons'.
- John
John Nowak — 2008-03-05 09:19:19
Minor issues with the previous email:
1. I fell back to a Cat-like syntax for type definitions. Here are the
correct notations for 'i', 'map', and 'unlist':
i :: A [A -> B] -> B
map :: (List a) [a -> b] -> (List b)
unlist :: A (List b) [A -> C] [A b (List b) -> C] -> C
Arguably there should be a type abbreviation for '(List a)'; perhaps
'{a}'.
2. The phrase "allows editors to automatically intent" should read
"allows editors to automatically INDENT".
3. By "it's harder for machines to generate valid code", I mean that
it is harder to generate *source* code when compiling to a language
with indentation-sensitive syntax. Explicit paired delimiters are
easier to deal with.
4. It's too long. Unfortunately, I don't have the time to write a
shorter version.
Daniel Ehrenberg — 2008-03-05 14:14:13
> I. Lambda Expressions
> II. Local Function Variables
Sure, these two seem reasonable seems reasonable. Factor and Cat
support these. The only thing I have to say is, they shouldn't be used
too often or for everything, since they can make code unnecessarily
more verbose and less factorable.
> III. Prefix Notation
> Prefix notation may seem like a curiosity at first, perhaps existing
> only to lure over those familiar with prefix notation. However, I'd
> argue that prefix notation makes certain code objectively easier to
> read. This is especially the case when dealing with deconstructors
> like 'if' or 'unlist' as the higher order function of primary interest
> is "announced" earlier in the definition. In the following example,
> both functions are equivalent:
>
> f map = [] [x xs -> x f i xs f map cons] unlist
>
> f map =
> (unlist []
> [x xs -> x f i xs f map cons])
>
> (Perhaps this is not the best example. Substitute a better one with
> nested ifs.)
>
> Prefix notation also has the benefit that you can express "nested"
> code (as above) in a way that allows editors to automatically intent
> properly. This is not at all the case with purely postfix code where
> type information and perhaps some heuristics would need to be involved
> to produce acceptable indentation.
>
> Here's a rewriting of map using *only* prefix notation in a way that
> most any Scheme or Haskell programmer would find comfortable:
>
> f map =
> (unlist []
> [x xs -> (cons (f x) (map xs f))])
>
Now this I have a very hard time understanding the motivation for.
Sure, when you're just learning concatenative languages, it can be a
little weird that "if" comes after the quotations, but humans don't
read completely linearly in normal circumstances, and it doesn't take
too much effort to look to the end. In a case where you have to look a
page ahead, I'd say the fault lies with the author of the code writing
things unreadably, rather than the language being unreadable. Also,
what happens if a function is given too many arguments? The result is
very counterintuitive, and a more useful translation would take into
account type information.
> IV. Indentation
>
> f map = unlist:
> []
> [x xs -> cons: (f x) (map xs f)]
I don't completely get it. This example doesn't take advantage of
indentation, it only uses modified prefix syntax. I guess the
indentation can make a difference if you have multiple arguments
following the word, and then something else after that that's not an
argument?
Sure, there are lots of translations that we could make efficiently
and accurately with concatenative languages, but I'm not sure if all
of these are essential or beneficial to the nature of the languages.
They make things more complicated and they remove all of the nice
properties of concatenativity, which is useful in building software
because it helps you factor code. We could easily create a translation
from Scheme to a concatenative language, but that doesn't mean that
we'd want to do all of our concatenative programming on a Scheme skin.
John Nowak — 2008-03-05 20:14:47
On Mar 5, 2008, at 9:14 AM, Daniel Ehrenberg wrote:
> Sure, there are lots of translations that we could make efficiently
> and accurately with concatenative languages, but I'm not sure if all
> of these are essential or beneficial to the nature of the languages.
> They make things more complicated and they remove all of the nice
> properties of concatenativity, which is useful in building software
> because it helps you factor code.
I'm not convinced concatenativity offers a huge advantage in
factoring. It's easy to write code in such a way that useful chunks
can't be pulled out. It's also difficult to find useful abstractions
unless you have some experience. For example, I'd guess the novice
programmer looking to add two lists together wouldn't accidently write
zip-with.
I think how factorable a language is primarily depends on its
usefulness in building abstractions rather than any particular syntax.
Languages with first class functions offer factorability that language
like Forth don't offer. Haskell's type classes over a level of safe
and structured factorability that's inaccessible to Joy. ML's functors
offer a means of factoring I often miss when using Haskell. Types
offer a way of verifying my abstractions in a way I miss when using
Scheme. Scheme offers macros as a means of factoring that I miss when
using Haskell. Et cetera.
If a syntax that is non-concatenative makes it any easier to use any
of the other means of factoring, then it seems to me it's worth
considering.
- John
John Nowak — 2008-03-05 20:39:53
On Mar 5, 2008, at 3:14 PM, John Nowak wrote:
> I think how factorable a language is primarily depends on its
> usefulness in building abstractions rather than any particular syntax.
> Languages with first class functions offer factorability that language
> like Forth don't offer. Haskell's type classes over a level of safe
> and structured factorability that's inaccessible to Joy. ML's functors
> offer a means of factoring I often miss when using Haskell. Types
> offer a way of verifying my abstractions in a way I miss when using
> Scheme. Scheme offers macros as a means of factoring that I miss when
> using Haskell. Et cetera.
I forgot an obvious one: Joy's stack-based nature, which makes it
possible to return multiple values from a function and then easily
consume them in another, opens up many possibilities for factoring
that I often miss when using other languages.
- John
Stevan Apter — 2008-03-05 22:26:51
----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, March 05, 2008 3:39 PM
Subject: Re: [stack] sweetening concatenative syntax
> On Mar 5, 2008, at 3:14 PM, John Nowak wrote:
>
>> I think how factorable a language is primarily depends on its
>> usefulness in building abstractions rather than any particular syntax.
>> Languages with first class functions offer factorability that language
>> like Forth don't offer. Haskell's type classes over a level of safe
>> and structured factorability that's inaccessible to Joy. ML's functors
>> offer a means of factoring I often miss when using Haskell. Types
>> offer a way of verifying my abstractions in a way I miss when using
>> Scheme. Scheme offers macros as a means of factoring that I miss when
>> using Haskell. Et cetera.
temperament, taste, and further imponderable subjectivities. perhaps a
useful distinction to make is between monoglot and polyglot programmers.
i'm an extreme case of the former, and you sound like you belong way
over on the other edge. given the decision to code in a concatenative
language, i want my concatenativity neat, straight no chaser. the
sharp, clear outlines of the basic syntax are no small part of what i
like about joy. in contrast to dan, i think introducing variables in
any form should be resisted (although i've implemented both in my toy
languages, just for the heck of it.) moreover, i agree with something
dr. tanksley has often said: we don't yet know all the properties of
these languages in their pure form, since no one (as far as i can tell
from years on this list) has written any large-scale, multi-programmer,
long-lived applications in any concatenative language. many small
examples, much tinkering under the hood, but nothing approaching the
scale of, say, ebay.
>
> I forgot an obvious one: Joy's stack-based nature, which makes it
> possible to return multiple values from a function and then easily
> consume them in another, opens up many possibilities for factoring
> that I often miss when using other languages.
>
> - John
>
john@johnnowak.com — 2008-03-05 23:08:35
On Mar 5, 2008, at 5:26 PM, Stevan Apter wrote:
> temperament, taste, and further imponderable subjectivities. perhaps a
> useful distinction to make is between monoglot and polyglot programmers.
> i'm an extreme case of the former, and you sound like you belong way
> over on the other edge.
Heh, well, I'm largely playing devil's advocate here. My personal opinions
towards this sort of thing are largely the same as your own. I generally
consider myself a Scheme/Joy-pushing monoglot programmer. I do however
have a growing, nasty, type system addiction.
Still, I think there may be some value in permitting these things because
they can be completely translated away. If you don't want to use them,
then don't. No harm done. I think.
- John
Don Groves — 2008-03-06 01:34:28
Hi, John --
Where can we read about Fifth? Several years ago, someone
announced a Fifth language, is yours a continuation of that effort,
or was that you?
--
don
On Mar 5, 2008, at 19:04 , John Nowak wrote:
> I've had some thoughts recently on syntactic additions to
> concatenative languages that seem potentially quite useful. At the
> very least, they would put an end to silly discussions over largely
> imagined deficiencies of postfix syntax and pointfree programming.
> This is perhaps crucial if we expect any significant uptake of
> concatenative languages.
>
> Below are the four extensions that I'm proposing. I'm strongly
> considering one or more in the language I'm currently working on
> (named "Fifth" for what are likely obvious reasons). The first two
> should be fairly uncontroversial. The latter two are simple
> translations I've not seen discussed before that seem potentially very
> useful in practice.
>
> I. Lambda Expressions
>
> Assuming functions have the syntax '[<body>]', it seems useful to
> introduce the syntax '[<bindings> -> <body>], where bindings are
> ordered with the top of the stack towards the right as is familiar.
> For example, the following two functions are equivalent:
>
> foo :: -> [a b -> b a a]
> foo = [swap dup]
> foo = [a b -> b a a]
>
> Note that the type syntax mimics the lambda expression syntax (or vice
> versa if you prefer). The type notation is similar to Cat's with minor
> alterations for the purposes of brevity. In particular, scalar
> variables are all lowercase, row variables are all uppercase, and
> concrete types are title-case and of at least two characters (to avoid
> confusion with row variables).
>
> Variables should, of course, be lexically scoped. A translation of
> expressions with lambdas to efficient pointfree stack-based code is
> not especially difficult. This is the case regardless of if the
> language is linear (which introduces only small complications), typed,
> or "lacking" a retain stack. Of course, I elide the translation here
> for the sake of... space.
>
> II. Local Function Variables
>
> If you permit lambdas, it makes sense to offer a simple syntax for
> declaring functions with named variables. This is similar to how
> Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo
> (lambda (<bindings>) <body>))'. The declaration syntax proposed here
> mimics use. In particular, the name of the function being defined
> occurs *after* the arguments.
>
> The following two statements are equivalent (where 'i' is the identity
> combinator with the type 'A (A -> B) -> B'):
>
> a b foo = b a a
> foo = [a b -> b a a] i
>
> Here's another example in which 'unlist' is a deconstructor for a
> list; the first function provided handled the null case and the second
> handles the cons case:
>
> unlist :: A [b] (A -> C) (A b [b] -> C) -> C
>
> map :: [a] (a -> b) -> [b]
> list f map = list [] [x xs -> x f i xs f map cons] unlist
>
> It should be noted that both lambda expressions and functions declared
> with the local variable syntax may use more items on the stack than
> they explicitly bind. For example, the following definition of map is
> equivalent to the above and likely preferable in practice:
>
> f map = [] [x xs -> x f i xs f map cons] unlist
>
> III. Prefix Notation
>
> It occurred to me recently that there exists a simple syntactic
> translation from prefix code (a la Scheme), where '(foo a b c)' is the
> application of 'foo' to three arguments, to postfix code. This
> translation can be done without any type information. The translation
> consists of simply removing the parenthesis and placing the first
> element at the end. If that first element is a local binding or a
> lambda expression, an 'i' is prepended to cause it to be evaluated.
> Here are some simple translation examples:
>
> (cons 1 null) => 1 null cons
> (+ (- 1 2) 3) => 1 2 - 3 +
> [f -> (f 10)] => [f -> 10 f i]
> f foo = (f 5) => f foo = 5 f i
>
> Interestingly, you get partial application for free:
>
> double = (* 2)
>
> One thing that may seem like a problem is that '(1 2 3)' will be
> translated to '(2 3 1)' when really an error should occur as '1' is
> not a function. However, that's not the case: '1' *is* a function.
> More precisely, it is a row polymorphic function that consumes a stack
> and yields a new stack (1 :: A -> A int). As such, the above syntactic
> translation is completely valid and it would be wrong to reject it.
>
> Prefix notation may seem like a curiosity at first, perhaps existing
> only to lure over those familiar with prefix notation. However, I'd
> argue that prefix notation makes certain code objectively easier to
> read. This is especially the case when dealing with deconstructors
> like 'if' or 'unlist' as the higher order function of primary interest
> is "announced" earlier in the definition. In the following example,
> both functions are equivalent:
>
> f map = [] [x xs -> x f i xs f map cons] unlist
>
> f map =
> (unlist []
> [x xs -> x f i xs f map cons])
>
> (Perhaps this is not the best example. Substitute a better one with
> nested ifs.)
>
> Prefix notation also has the benefit that you can express "nested"
> code (as above) in a way that allows editors to automatically intent
> properly. This is not at all the case with purely postfix code where
> type information and perhaps some heuristics would need to be involved
> to produce acceptable indentation.
>
> Here's a rewriting of map using *only* prefix notation in a way that
> most any Scheme or Haskell programmer would find comfortable:
>
> f map =
> (unlist []
> [x xs -> (cons (f x) (map xs f))])
>
> IV. Indentation
>
> Prefix notation is often criticized for being overly verbose or noisy.
> The Python solution is to use indentation instead of paired
> delimiters, but this introduces a number of problems: It's harder for
> machines to generate valid code, pasting between sources can be messy,
> editors can't really automatically re-indent code, plenty of people
> (myself included) hate it, etc.
>
> The correct way to address this problem (if you are to address it at
> all) is to do what Haskell does and offer *optional* indentation-
> sensitive syntax that gets translated to the more explicit form. This
> can be implemented as a relatively trivial pre-parser pass and does
> not require modification of the parser itself.
>
> Indentation-sensitive syntax is introduced with a colon. Here are some
> simple examples showing how indentation-sensitive code is translated
> to prefix code which is then translated to "normal" code:
>
> a b c: d e f => a b (c d e f) => a b d e f c
>
> a b c:
> d e f: => a b (c d e (f g h)) => a b d e g h f c
> g h
>
> Finally, here again is our map example, this time even spiffier:
>
> f map = unlist:
> []
> [x xs -> cons: (f x) (map xs f)]
>
> This looks quite close to the Haskell version, except that our
> programs are, after translation, still expressed only in terms of the
> functional forms of composition and quotation! (I was wrong in an
> earlier email when I started that composition is the only functional
> form in Joy. Quotation is also a functional form.) This definition is
> arguably easier to read than the postfix, pointfree alternative, as it
> clearly announces at the start that 'map' is a function that
> destructures a list, details the result of the destructization at the
> start of the relevant line, and indicates directly after that the
> result of the function will be a list via the prefixing of 'cons'.
>
> - John
>
>
>
> Yahoo! Groups Links
>
>
>
>
john@johnnowak.com — 2008-03-06 02:03:15
On Mar 5, 2008, at 5:26 PM, Stevan Apter wrote:
> temperament, taste, and further imponderable subjectivities.
Well, perhaps this is worth testing then. Here's how I'm suggesting one
could write a non-tail-recursive 'map' in terms of 'cons' and 'unlist':
f map = unlist:
[]
[x xs -> (f x) (map xs f) cons]
> i want my concatenativity neat, straight no chaser.
How would you personally write this in a purely concatenative form? No
cheating by using combinators like 'fold'; you only get to use 'cons' (a
{a} -> {a}) and 'unlist' (A {b} [A -> C] [A b {b} -> C] -> C).
- John
Stevan Apter — 2008-03-06 02:34:51
----- Original Message -----
From: <john@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, March 05, 2008 9:03 PM
Subject: Re: [stack] sweetening concatenative syntax
> On Mar 5, 2008, at 5:26 PM, Stevan Apter wrote:
>
>> temperament, taste, and further imponderable subjectivities.
>
> Well, perhaps this is worth testing then. Here's how I'm suggesting one
> could write a non-tail-recursive 'map' in terms of 'cons' and 'unlist':
>
> f map = unlist:
> []
> [x xs -> (f x) (map xs f) cons]
>
>> i want my concatenativity neat, straight no chaser.
>
> How would you personally write this in a purely concatenative form? No
> cheating by using combinators like 'fold'; you only get to use 'cons' (a
> {a} -> {a}) and 'unlist' (A {b} [A -> C] [A b {b} -> C] -> C).
my joy is so rusty these days. i'm on the wagon.
in the g variant of my f language:
[[dup!count![]top!]dip!swap!
[[uncons!]dip!dup!top!
[cons!unit!. first!swons!]dipd!]
do!pop!pop!|] map "[..][f]map!"
and in XY:
; map [jump] [each* rot => map <= swons] [pop] ifte ;
; each* => uncons <= tuck 2slip ;
in both languages, all words are bottom out in symbolic primitives. six or
seven for XY, rather more for g.
details here: www.nsl.com.
>
> - John
>
>
John Nowak — 2008-03-06 02:52:32
On Mar 5, 2008, at 8:34 PM, Don Groves wrote:
> Where can we read about Fifth?
At 5th.org, in a few weeks from now.
> Several years ago, someone
> announced a Fifth language, is yours a continuation of that effort,
> or was that you?
No, it wasn't me, nor is this a continuation of anything.
- John
Don Groves — 2008-03-06 02:58:23
On Mar 5, 2008, at 19:52 , John Nowak wrote:
>
> On Mar 5, 2008, at 8:34 PM, Don Groves wrote:
>
>> Where can we read about Fifth?
>
> At 5th.org, in a few weeks from now.
Thanks!
>
>> Several years ago, someone
>> announced a Fifth language, is yours a continuation of that effort,
>> or was that you?
>
> No, it wasn't me, nor is this a continuation of anything.
I just figured that out. My references to Fifth are 20 years old ;-)
--
don
>
> - John
>
>
>
> Yahoo! Groups Links
>
>
>
>
John Nowak — 2008-03-06 03:12:39
On Mar 5, 2008, at 9:34 PM, Stevan Apter wrote:
> ; map [jump] [each* rot => map <= swons] [pop] ifte ;
> ; each* => uncons <= tuck 2slip ;
So that, versus this:
f map = unlist:
[]
[x xs -> (f x) (map xs f) cons]
It seems to me that the second version is objectively easier to
understand. It's clear that 'map' destructures a list and it's clear
how both possibilities (the null list and the non-null list) are
handled. Even if we drop the prefix/indent syntax, it's still a good
deal clearer:
f map = []
[x xs -> x f i xs f map cons]
unlist
Actually, I like that better.
At the very least, it seems that there's a strong argument for
offering lambda expressions and a locals syntax.
It's less clear that the prefix syntax is worthwhile. In particular,
point Dan made is valid:
> Also, what happens if a function is given too many arguments? The
> result is very counterintuitive, and a more useful translation would
> take into account type information.
I'd be strongly opposed to any translation that was not a purely
syntactic preprocessing step as otherwise you truly are complicating
the language. At the moment, my type system can't enforce that a given
quotation isn't given "too many" arguments because this makes no
sense; all functions operate on stacks. The type system can enforce
that a given quotation will try to use no more than a given number of
arguments when it is later evaluated, and this is critical for typing
combinators like 'infra', but that isn't helpful here. It is therefore
probably best to rule out prefix syntax.
- John
William Tanksley, Jr — 2008-03-06 17:22:11
John Nowak <
john@...> wrote:
> Daniel Ehrenberg wrote:
> > Sure, there are lots of translations that we could make efficiently
> > and accurately with concatenative languages, but I'm not sure if all
> > of these are essential or beneficial to the nature of the languages.
> > They make things more complicated and they remove all of the nice
> > properties of concatenativity, which is useful in building software
> > because it helps you factor code.
> I'm not convinced concatenativity offers a huge advantage in
> factoring.
Sure it does! The referential transparency alone is worth the price of
admission -- the famous "extract method" refactoring (considered by
many to be the first indication of "true" refactoring support in a
tool) is merely a cut-and-paste in any editor.
> It's easy to write code in such a way that useful chunks
> can't be pulled out. It's also difficult to find useful abstractions
> unless you have some experience. For example, I'd guess the novice
> programmer looking to add two lists together wouldn't accidently write
> zip-with.
You're totally right, but you're talking about a different subject.
The experienced programmer isn't going to implement zip-with either;
the experienced programmer knows it's already implemented. The
experienced programmer is going to implement something that hasn't
been done before, and notice that there's some redundancy, and if the
language allows, will factor it out. If the language makes it hard,
he'll tolerate a lot more redundancy.
An really good programmer will also notice *almost* redundancies --
places where the code would be the same if only things were a little
bit different. _That_ is the point that leads to the creation of truly
reusable tools like zip-with -- not a magic knowledge of what sort of
things will be reusable, but rather a repeated creation of the same
sort of thing, and progressive refinement of that thing until it can
actually be used in all of those cases.
A good library is rarely produced directly from pure theory. Usually
it's produced by painstaking experiments -- although if it's not
backed by a good clean conceptual model it's a bad library, and
experience won't save it.
> I think how factorable a language is primarily depends on its
> usefulness in building abstractions rather than any particular syntax.
> Languages with first class functions offer factorability that language
> like Forth don't offer.
100% agree, by the way. The problem of factoring can be addressed in
many dimensions.
> If a syntax that is non-concatenative makes it any easier to use any
> of the other means of factoring, then it seems to me it's worth
> considering.
At this point in our understanding of concatenative languages, this is
a pure cop-out. Yes, we don't have a concatenative Haskell yet -- but
give us time.
> - John
-Wm
William Tanksley, Jr — 2008-03-06 17:31:56
Stevan Apter <
sa@...> wrote:
> given the decision to code in a concatenative
> language, i want my concatenativity neat, straight no chaser.
Heh. I'm the same way -- of course. That's a little bit of the
language researcher speaking rather than the true polyglot programmer,
though. Like the chemist that I was trained as, I'm always wondering
what would happen if I made a slightly purer extract. Well, I guess I
skip the step of blowing the resulting extract up in my face -- that's
the fun part of chemistry.
> like about joy. in contrast to dan, i think introducing variables in
> any form should be resisted (although i've implemented both in my toy
> languages, just for the heck of it.)
Yup.
> moreover, i agree with something dr. tanksley has often said:
Thank you, but I'm just Mr. Tanksley so far. I'm just starting on a
Master's degree, so perhaps you'll be able to address me as "dread
lord tanksley" in a while. (Is that the correct form of address?)
> we don't yet know all the properties of
> these languages in their pure form, since no one (as far as i can tell
> from years on this list) has written any large-scale, multi-programmer,
> long-lived applications in any concatenative language. many small
> examples, much tinkering under the hood, but nothing approaching the
> scale of, say, ebay.
I'm not so sure about that. Forth has been used in enormous
applications; see
http://www.forth.com/resources/appNotes/index.html
(and that's just one Forth company). Postscript forms one of the
largest systems ever built (just about every computer is able to hook
up to just about every Postscript printer almost right out of the
box); it's not an integrated or monolithic system like eBay, but it's
phenomenally successful at what it's designed to do.
-Wm
William Tanksley, Jr — 2008-03-06 17:52:24
John Nowak <
john@...> wrote:
> Stevan Apter wrote:
> understand. It's clear that 'map' destructures a list and it's clear
> how both possibilities (the null list and the non-null list) are
> handled.
> f map = []
> [x xs -> x f i xs f map cons]
> unlist
> At the very least, it seems that there's a strong argument for
> offering lambda expressions and a locals syntax.
Of course, what you typed there is just ambiguous, or possibly
requires phenominal lookahead (to see if one of the alternatives
includes a "->" token). But in no case does this functionality REQUIRE
lambdas or locals; why should it? All you're doing is patternmatching.
Consider the famous FunForth, an implementation of a trivial little
patternmatcher in a tiny bit of Forth code
(
http://wiki.forthfreak.net/index.cgi?FunForth, note that there
appears to be a display bug in the upper right corner).
> - John
-Wm
John Nowak — 2008-03-06 20:32:02
On Mar 6, 2008, at 12:52 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>
>> f map = []
>> [x xs -> x f i xs f map cons]
>> unlist
>>
>> At the very least, it seems that there's a strong argument for
>> offering lambda expressions and a locals syntax.
>
> Of course, what you typed there is just ambiguous, or possibly
> requires phenominal lookahead (to see if one of the alternatives
> includes a "->" token).
Indeed. There's no way I'd implement it with that syntax, Scheme
programmer and hater of parsing that I am. The actual syntax I have
now doesn't require lookahead.
> But in no case does this functionality REQUIRE
> lambdas or locals; why should it? All you're doing is patternmatching.
I'm actively trying to avoid defining the language in terms of pattern
matching. Here, 'unlist' is just a normal function. But yes, of course
it doesn't require locals. You could do this as well:
map = swap
[]
[rot dup 2keep swap map cons]
unlist
Anyway, saying that "all your doing is pattern matching" gets more
complicated when types are involved. For example, when I eventually
introduce GADTs, sum deconstructors like 'unlist' will need to
introduce equality constraints. It also isn't clear how a macro could
be able to inform you if you've not covered all of the possible cases
when matching. Therefore, any sort of general pattern matching
facility would need to be implemented into the language proper, and
ideally I'd like to avoid that as it complicates things.
- John
John Nowak — 2008-03-06 20:36:15
On Mar 6, 2008, at 3:32 PM, John Nowak wrote:
>> But in no case does this functionality REQUIRE
>> lambdas or locals; why should it? All you're doing is
>> patternmatching.
>
> Anyway, saying that "all your doing is pattern matching"
Ack. Excuse me for butchering the language while quoting you.
s/your/you're
- John
Daniel Ehrenberg — 2008-03-06 20:41:09
> Anyway, saying that "all your doing is pattern matching" gets more
> complicated when types are involved. For example, when I eventually
> introduce GADTs, sum deconstructors like 'unlist' will need to
> introduce equality constraints. It also isn't clear how a macro could
> be able to inform you if you've not covered all of the possible cases
> when matching. Therefore, any sort of general pattern matching
> facility would need to be implemented into the language proper, and
> ideally I'd like to avoid that as it complicates things.
>
> - John
Pattern matching only has to be built into a language when its type
system or syntax extension system is insufficiently expressive.
There's no good reason why a complicated, library-based pattern
matching macro couldn't cooperate with a type system or completeness
constraints. Factor has two pattern matching libraries implemented,
which take different tactics but are both fairly general and
implemented without the help of the core.
If Fifth ultimately gets a good enough macro system, you won't need to
worry about all of those syntax extensions that started this
discussion until writing your standard library. Even if a macro system
is a big step and a big thing to think about, it can make your
language much simpler overall.
Dan
John Nowak — 2008-03-06 20:43:35
On Mar 6, 2008, at 12:22 PM, William Tanksley, Jr wrote:
>> I'm not convinced concatenativity offers a huge advantage in
>> factoring.
>
> Sure it does! The referential transparency alone is worth the price of
> admission -- the famous "extract method" refactoring (considered by
> many to be the first indication of "true" refactoring support in a
> tool) is merely a cut-and-paste in any editor.
Indeed, although this partially breaks down in the presence of
modules. Types also complicate things. For example, you can't factor
out the 'dup i' in '[swap] dup i' unless your system has higher-rank
polymorphism or equi-recursive types.
>> If a syntax that is non-concatenative makes it any easier to use any
>> of the other means of factoring, then it seems to me it's worth
>> considering.
>
> At this point in our understanding of concatenative languages, this is
> a pure cop-out.
Fair enough.
> Yes, we don't have a concatenative Haskell yet -- but give us time.
I'm working on it!
- John
John Nowak — 2008-03-06 20:58:59
On Mar 6, 2008, at 3:41 PM, Daniel Ehrenberg wrote:
>> Anyway, saying that "all your doing is pattern matching" gets more
>> complicated when types are involved. For example, when I eventually
>> introduce GADTs, sum deconstructors like 'unlist' will need to
>> introduce equality constraints. It also isn't clear how a macro could
>> be able to inform you if you've not covered all of the possible cases
>> when matching. Therefore, any sort of general pattern matching
>> facility would need to be implemented into the language proper, and
>> ideally I'd like to avoid that as it complicates things.
>>
>> - John
>
> Pattern matching only has to be built into a language when its type
> system or syntax extension system is insufficiently expressive.
> There's no good reason why a complicated, library-based pattern
> matching macro couldn't cooperate with a type system or completeness
> constraints.
This seems incredibly difficult in practice. Would the macro system be
able to to query the type system? Would it be able to find out all
constructors of a given data type? Would it be able to check if a
given data type requires that equality constraints be introduced when
matching? How would it generate code that handles such a thing anyway?
Would it need to be smart enough to translate to a pre-defined
deconstructor? How would it be able to give errors as intelligible as
a built-in system for subtle matters like this? If the macro were to
introduce variables, would the specification not have to indicate how
this interacts with linearity? Does the macro not then need to be in
the core anyway?
> Factor has two pattern matching libraries implemented, which take
> different tactics but are both fairly general and implemented
> without the help of the core.
Yes, it's all very easy when types aren't involved.
- John
William Tanksley, Jr — 2008-03-06 21:49:21
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > But in no case does this functionality REQUIRE
> > lambdas or locals; why should it? All you're doing is patternmatching.
> I'm actively trying to avoid defining the language in terms of pattern
> matching. Here, 'unlist' is just a normal function. But yes, of course
> it doesn't require locals. You could do this as well:
> map = swap
> []
> [rot dup 2keep swap map cons]
> unlist
...but you're still doing patternmatching. Aren't you? What am I missing?
> Anyway, saying that "all your doing is pattern matching" gets more
> complicated when types are involved.
Oh, I agree.
> when matching. Therefore, any sort of general pattern matching
> facility would need to be implemented into the language proper, and
> ideally I'd like to avoid that as it complicates things.
Well, if you're incorporating types into the language, you've got to
handle the effects of that.
> - John
-Wm
William Tanksley, Jr — 2008-03-06 22:00:14
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > Sure it does! The referential transparency alone is worth the price of
> > admission -- the famous "extract method" refactoring (considered by
> > many to be the first indication of "true" refactoring support in a
> > tool) is merely a cut-and-paste in any editor.
> Indeed, although this partially breaks down in the presence of
> modules.
I don't see why... Unless you're also talking about moving the
resulting function out of the current module, which isn't something I
intended to imply. In fact, is that what you're talking about? It
can't be, because in general that's impossible (the function might
refer to some stuff that's private to the original module).
So I definitely don't know what you mean.
> Types also complicate things. For example, you can't factor
> out the 'dup i' in '[swap] dup i' unless your system has higher-rank
> polymorphism or equi-recursive types.
Well, technically if your typesystem was "concatenative" you could
factor it out. If your typesystem isn't concatenative, then the
resulting language is no longer strictly concatenative, although it
may indeed appear concatenative, or it may be concatenative but
require some kind of type annotation which isn't concatenative.
I can't criticise anyone for failing to have a concatenative type
system, since I don't know what such a thing would look like --
_except_ in the special case where all types are declared (as in
StrongForth). Clearly that's not an optimal case. It seems to me that
it _should_ be possible to construct a truly concatenative type
system, but again, I don't know what it would look like.
> > Yes, we don't have a concatenative Haskell yet -- but give us time.
> I'm working on it!
Yes indeed, as is Chris -- and your work is very interesting.
> - John
-Wm
Stevan Apter — 2008-03-06 22:00:18
ack. it's been so long since i looked at this stuff that i'd
forgotten that 'map' in f/g and XY is an extension of the standard
definition: given a list of k-length lists, it applies a n-ary
function n>=k to each element of the list. so e.g.
[[1 2][3 4][5 6]][+]map -> [3 7 11]
if n>k, then e.g. f "projects":
[[1][3 4][5 6 7]][+ *][map] -> [[1 + *][7 *] 18]
i knew it looked more complex than it had to be! anyway, i'd
be curious how you would write this combinator (call it 'mapx').
----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, March 05, 2008 10:12 PM
Subject: Re: [stack] sweetening concatenative syntax
> On Mar 5, 2008, at 9:34 PM, Stevan Apter wrote:
>
>> ; map [jump] [each* rot => map <= swons] [pop] ifte ;
>> ; each* => uncons <= tuck 2slip ;
>
> So that, versus this:
>
> f map = unlist:
> []
> [x xs -> (f x) (map xs f) cons]
>
> It seems to me that the second version is objectively easier to
> understand. It's clear that 'map' destructures a list and it's clear
> how both possibilities (the null list and the non-null list) are
> handled. Even if we drop the prefix/indent syntax, it's still a good
> deal clearer:
>
> f map = []
> [x xs -> x f i xs f map cons]
> unlist
>
> Actually, I like that better.
>
> At the very least, it seems that there's a strong argument for
> offering lambda expressions and a locals syntax.
>
> It's less clear that the prefix syntax is worthwhile. In particular,
> point Dan made is valid:
>
>> Also, what happens if a function is given too many arguments? The
>> result is very counterintuitive, and a more useful translation would
>> take into account type information.
>
> I'd be strongly opposed to any translation that was not a purely
> syntactic preprocessing step as otherwise you truly are complicating
> the language. At the moment, my type system can't enforce that a given
> quotation isn't given "too many" arguments because this makes no
> sense; all functions operate on stacks. The type system can enforce
> that a given quotation will try to use no more than a given number of
> arguments when it is later evaluated, and this is critical for typing
> combinators like 'infra', but that isn't helpful here. It is therefore
> probably best to rule out prefix syntax.
>
> - John
>
John Nowak — 2008-03-06 22:09:04
On Mar 6, 2008, at 4:49 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>> William Tanksley, Jr wrote:
>>> But in no case does this functionality REQUIRE
>>> lambdas or locals; why should it? All you're doing is
>>> patternmatching.
>
>> I'm actively trying to avoid defining the language in terms of
>> pattern
>> matching. Here, 'unlist' is just a normal function. But yes, of
>> course
>> it doesn't require locals. You could do this as well:
>> map = swap
>> []
>> [rot dup 2keep swap map cons]
>> unlist
>
> ...but you're still doing patternmatching. Aren't you? What am I
> missing?
'unlist' is just a normal function that gets defined as a result of
declaring the 'list' data type:
unlist :: A {b} [A -> C] [A b {b} -> C] -> C
This is different from general pattern matching as there's no way to
match on particular values and "matching" here is guaranteed to be
constant time. Alternatively, it isn't pattern matching as it doesn't
involve patterns. The fact that it *looks* like pattern matching when
lambda expressions are used is a very nice thing.
>
- John
Stevan Apter — 2008-03-06 22:09:14
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, March 06, 2008 12:31 PM
Subject: Re: [stack] sweetening concatenative syntax
> Stevan Apter <sa@...> wrote:
>> given the decision to code in a concatenative
>> language, i want my concatenativity neat, straight no chaser.
>
> Heh. I'm the same way -- of course. That's a little bit of the
> language researcher speaking rather than the true polyglot programmer,
> though. Like the chemist that I was trained as, I'm always wondering
> what would happen if I made a slightly purer extract. Well, I guess I
> skip the step of blowing the resulting extract up in my face -- that's
> the fun part of chemistry.
>
>> like about joy. in contrast to dan, i think introducing variables in
>> any form should be resisted (although i've implemented both in my toy
>> languages, just for the heck of it.)
>
> Yup.
>
>> moreover, i agree with something dr. tanksley has often said:
>
> Thank you, but I'm just Mr. Tanksley so far. I'm just starting on a
> Master's degree, so perhaps you'll be able to address me as "dread
> lord tanksley" in a while. (Is that the correct form of address?)
"your royal hic-haec-hoc-itude?"
>
>> we don't yet know all the properties of
>> these languages in their pure form, since no one (as far as i can tell
>> from years on this list) has written any large-scale, multi-programmer,
>> long-lived applications in any concatenative language. many small
>> examples, much tinkering under the hood, but nothing approaching the
>> scale of, say, ebay.
>
> I'm not so sure about that. Forth has been used in enormous
> applications; see http://www.forth.com/resources/appNotes/index.html
> (and that's just one Forth company). Postscript forms one of the
> largest systems ever built (just about every computer is able to hook
> up to just about every Postscript printer almost right out of the
> box); it's not an integrated or monolithic system like eBay, but it's
> phenomenally successful at what it's designed to do.
i'm not sure either. i've often thought it would be useful to come
up with something like the complement of fred brook's no-silver-
bullet analysis: a list of the properties which make an application
"hard" -- for a programming language, for programmers, for companies,
&c. e.g. big data, need for speed, fault-tolerance, life-and-death
consequences of bugs, rapidly changing demands, need to be shrink-
wrapped for users (a.k.a. The Enemy), &c. so an app can be hard
in some dimensions, easy in others, &c. and out of that you get
consensus around a maxim i've always found somewhat depressing:
use the right tool for the job.
>
> -Wm
>
Stevan Apter — 2008-03-06 22:10:40
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, March 06, 2008 12:22 PM
Subject: Re: [stack] sweetening concatenative syntax
> John Nowak <john@...> wrote:
>> Daniel Ehrenberg wrote:
>> > Sure, there are lots of translations that we could make efficiently
>> > and accurately with concatenative languages, but I'm not sure if all
>> > of these are essential or beneficial to the nature of the languages.
>> > They make things more complicated and they remove all of the nice
>> > properties of concatenativity, which is useful in building software
>> > because it helps you factor code.
>
>> I'm not convinced concatenativity offers a huge advantage in
>> factoring.
>
> Sure it does! The referential transparency alone is worth the price of
> admission -- the famous "extract method" refactoring (considered by
> many to be the first indication of "true" refactoring support in a
> tool) is merely a cut-and-paste in any editor.
>
>> It's easy to write code in such a way that useful chunks
>> can't be pulled out. It's also difficult to find useful abstractions
>> unless you have some experience. For example, I'd guess the novice
>> programmer looking to add two lists together wouldn't accidently write
>> zip-with.
>
> You're totally right, but you're talking about a different subject.
> The experienced programmer isn't going to implement zip-with either;
> the experienced programmer knows it's already implemented. The
> experienced programmer is going to implement something that hasn't
> been done before, and notice that there's some redundancy, and if the
> language allows, will factor it out. If the language makes it hard,
> he'll tolerate a lot more redundancy.
>
> An really good programmer will also notice *almost* redundancies --
> places where the code would be the same if only things were a little
> bit different. _That_ is the point that leads to the creation of truly
> reusable tools like zip-with -- not a magic knowledge of what sort of
> things will be reusable, but rather a repeated creation of the same
> sort of thing, and progressive refinement of that thing until it can
> actually be used in all of those cases.
>
> A good library is rarely produced directly from pure theory. Usually
> it's produced by painstaking experiments -- although if it's not
> backed by a good clean conceptual model it's a bad library, and
> experience won't save it.
these are very useful and very deep insights.
>
>> I think how factorable a language is primarily depends on its
>> usefulness in building abstractions rather than any particular syntax.
>> Languages with first class functions offer factorability that language
>> like Forth don't offer.
>
> 100% agree, by the way. The problem of factoring can be addressed in
> many dimensions.
>
>> If a syntax that is non-concatenative makes it any easier to use any
>> of the other means of factoring, then it seems to me it's worth
>> considering.
>
> At this point in our understanding of concatenative languages, this is
> a pure cop-out. Yes, we don't have a concatenative Haskell yet -- but
> give us time.
>
>> - John
>
> -Wm
>
Stevan Apter — 2008-03-06 22:12:52
>
> if n>k, then e.g. f "projects":
>
> [[1][3 4][5 6 7]][+ *][map] -> [[1 + *][7 *] 18]
sorry - that should be:
[[1][3 4][5 6 7]][+ *] map -> [[1 + *][7 *] 18]
as i said, it's been a while.
John Nowak — 2008-03-06 22:20:19
On Mar 6, 2008, at 5:00 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>
>> William Tanksley, Jr wrote:
>>
>>> Sure it does! The referential transparency alone is worth the
>>> price of
>>> admission -- the famous "extract method" refactoring (considered by
>>> many to be the first indication of "true" refactoring support in a
>>> tool) is merely a cut-and-paste in any editor.
>>
>> Indeed, although this partially breaks down in the presence of
>> modules.
>
> I don't see why... Unless you're also talking about moving the
> resulting function out of the current module, which isn't something I
> intended to imply. In fact, is that what you're talking about?
Yes. It isn't a particularly interesting observation.
>> Types also complicate things. For example, you can't factor
>> out the 'dup i' in '[swap] dup i' unless your system has higher-rank
>> polymorphism or equi-recursive types.
>
> Well, technically if your typesystem was "concatenative" you could
> factor it out.
This is true. The original type system I had was concatenative (well,
really "compositional" is the correct term). Unfortunately, this
property gets lost quite quickly as you expand the power of the type
system. The only reason the original system was compositional was
because it would refuse to accept things like "[swap] dup i" as all
variables were non-generic and you'd hit an occurs check no matter
what order you attempted it in. At the moment, it seems that a truly
compositional type system imposes too many limitations. If there are
ways around this I've not discovered them yet.
> If your typesystem isn't concatenative, then the resulting language
> is no longer strictly concatenative
This all depends on your definition of concatenative. The language is
still expressed in terms of the functional forms of composition and
quotation. Concatenation still denotes composition. The limitation is
that you cannot compose functions in any order. This doesn't seem to
be a problem in practice, although it certainly is unfortunate.
> I can't criticise anyone for failing to have a concatenative type
> system, since I don't know what such a thing would look like --
I've been meaning to write up how to perform inference for a
compositional type system. If anyone is interested I'll bump this up
in my priority queue.
- John
William Tanksley, Jr — 2008-03-06 22:36:13
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > ...but you're still doing patternmatching. Aren't you? What am I
> > missing?
> 'unlist' is just a normal function that gets defined as a result of
> declaring the 'list' data type:
> unlist :: A {b} [A -> C] [A b {b} -> C] -> C
Sorry, I have no idea how to read this. It's clearly a type signature,
but I don't know any such languages more recent than ML (well, I know
a little Scala), and that only from a few college assignments.
I assumed that it was somewhat like 'i' in Joy (due to the name
'unlist' being similar to Joy's technical term 'dequote').
> This is different from general pattern matching as there's no way to
> match on particular values and "matching" here is guaranteed to be
> constant time.
Okay. I don't know of any pattern matching that doesn't work this way
(my knowledge of the modern functional languages is highly pathetic).
> Alternatively, it isn't pattern matching as it doesn't
> involve patterns. The fact that it *looks* like pattern matching when
> lambda expressions are used is a very nice thing.
Okay. I don't know what your example meant, then. Suffice it to say
that I'm just plain confused.
> - John
-Wm
John Nowak — 2008-03-06 22:40:51
On Mar 6, 2008, at 5:00 PM, Stevan Apter wrote:
> ack. it's been so long since i looked at this stuff that i'd
> forgotten that 'map' in f/g and XY is an extension of the standard
> definition: given a list of k-length lists, it applies a n-ary
> function n>=k to each element of the list. so e.g.
>
> [[1 2][3 4][5 6]][+]map -> [3 7 11]
>
> if n>k, then e.g. f "projects":
>
> [[1][3 4][5 6 7]][+ *][map] -> [[1 + *][7 *] 18]
>
> i knew it looked more complex than it had to be! anyway, i'd
> be curious how you would write this combinator (call it 'mapx').
(I'm only going to handle the first case of 'map' above. There's no
way for the type system to handle the second.)
Here's one way, writing other highly useful combinators as we go:
f map = [ ] [x xs -> x f i xs f map cons] unlist
z f foldl = [z] [x xs -> xs z x f i f foldl] unlist
foldl1 = [uncons swap] dip fold
mapx = [foldl1] compose map
Here's another, this time pointfree. I stole the definition of 'foldl'
from Cat; there may be a better one. The 'pa' function is partial
application (a [B a -> C] -> [B -> C]). Note that this version of map
is tail recursive, unlike the above version:
foldl = swapd [dip] pa [uncons swap] swap compose [null? not] while
foldl1 = [uncons swap] dip fold
rmap = null swap [cons] compose fold
map = rmap reverse
mapx = [foldl1] compose map
- John
John Nowak — 2008-03-06 22:52:19
On Mar 6, 2008, at 5:36 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>> William Tanksley, Jr wrote:
>>> ...but you're still doing patternmatching. Aren't you? What am I
>>> missing?
>> 'unlist' is just a normal function that gets defined as a result of
>> declaring the 'list' data type:
>> unlist :: A {b} [A -> C] [A b {b} -> C] -> C
>
> Sorry, I have no idea how to read this. It's clearly a type signature,
> but I don't know any such languages more recent than ML (well, I know
> a little Scala), and that only from a few college assignments.
>
> I assumed that it was somewhat like 'i' in Joy (due to the name
> 'unlist' being similar to Joy's technical term 'dequote').
I explained what 'unlist' does in an earlier email. You may've missed
it.
The 'unlist' function is not like 'i' in Joy. Joy's 'i' has the
following type:
i :: A [A -> B] -> B
In other words, given a stack and a function that transforms that
stack to another stack, it yields the transformed stack.
What 'unlist' does is take three arguments. The first is a list. The
second is a function that says what to do if that list is null. The
the third is a function that acts on the list after is has been
unconsed if it is not null. The 'unlist' function is called a sum
deconstructor as lists are sum types (they're either a "null" or a
"cons").
We can use 'unlist' to write the usual functions:
uncons = [error] [] unlist
head = [error] [pop] unlist
tail = [error] [popd] unlist
null? = [true] [cons false] unlist
- John
John Nowak — 2008-03-06 22:58:08
On Mar 6, 2008, at 5:52 PM, John Nowak wrote:
> null? = [true] [cons false] unlist
Wrong!
null? :: {a} -> {a} bool
null? = [null true] [cons false] unlist
Better. Alternatively, if you *don't* want to keep the list around:
null? :: {a} -> bool
null? = [true] [pop pop false] unlist
The first version makes a lot more sense in a linear language. The
unconsing and consing can also be easily optimized out that way. Keep
in mind that you never really use 'null?' if you have 'unlist' anyway.
- John
Stevan Apter — 2008-03-06 23:12:28
forget about the partial application case. what i want in my toolkit
is a single combinator 'map' which takes an n-ary function and applies
it to each of a list of length-n lists. not map1, map2, ... for each
case. is that what's going on here? or does typing rule out having
such a combinator?
----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, March 06, 2008 5:40 PM
Subject: Re: [stack] sweetening concatenative syntax
>
> On Mar 6, 2008, at 5:00 PM, Stevan Apter wrote:
>
>> ack. it's been so long since i looked at this stuff that i'd
>> forgotten that 'map' in f/g and XY is an extension of the standard
>> definition: given a list of k-length lists, it applies a n-ary
>> function n>=k to each element of the list. so e.g.
>>
>> [[1 2][3 4][5 6]][+]map -> [3 7 11]
>>
>> if n>k, then e.g. f "projects":
>>
>> [[1][3 4][5 6 7]][+ *][map] -> [[1 + *][7 *] 18]
>>
>> i knew it looked more complex than it had to be! anyway, i'd
>> be curious how you would write this combinator (call it 'mapx').
>
> (I'm only going to handle the first case of 'map' above. There's no
> way for the type system to handle the second.)
>
> Here's one way, writing other highly useful combinators as we go:
>
> f map = [ ] [x xs -> x f i xs f map cons] unlist
> z f foldl = [z] [x xs -> xs z x f i f foldl] unlist
> foldl1 = [uncons swap] dip fold
> mapx = [foldl1] compose map
>
> Here's another, this time pointfree. I stole the definition of 'foldl'
> from Cat; there may be a better one. The 'pa' function is partial
> application (a [B a -> C] -> [B -> C]). Note that this version of map
> is tail recursive, unlike the above version:
>
> foldl = swapd [dip] pa [uncons swap] swap compose [null? not] while
> foldl1 = [uncons swap] dip fold
> rmap = null swap [cons] compose fold
> map = rmap reverse
> mapx = [foldl1] compose map
>
> - John
>
John Nowak — 2008-03-06 23:38:16
On Mar 6, 2008, at 6:12 PM, Stevan Apter wrote:
> forget about the partial application case. what i want in my toolkit
> is a single combinator 'map' which takes an n-ary function and applies
> it to each of a list of length-n lists.
Ah, I think maybe there's some confusion here over what we mean by
"list". (Yes, really!) In Joy, lists, stacks, and functions are all
magically the same thing. I assume it's similar in XY as well. In
Fifth, lists, stacks, and functions are all different things. This is
just one more example of the endless complication that types introduce.
The 'mapx' function I gave before took a list of lists and a function
of type 'a b -> b'. In other words, the function is restricted to
taking only two arguments as is standard for the 'fold' combinator.
It sounds to me like what you're describing is a function that takes a
list of *stacks* and applies an n-ary function to each stack in the
list. This is doable, where 'map' below is the "normal" map you'd find
in a language like ML, Haskell, or Fifth:
mapx :: {(Stack A)} [A -> B] -> {(Stack B)}
mapx = quote [infra] compose map
There are some limitations. In particular, all stacks in the list need
to be of the same type. Due to how row variables in stack types must
get instantiated (the row variables are stripped out), all stacks must
have the same number of elements and elements in corresponding
positions in each stack must be of the same type.
This limitation probably isn't too onerous in practice as I can't
imagine the use case for mapping over a list of elements of various
types. Note that when I say all elements must be the same type, I
don't mean that they must all be ints or that they must all be
strings. You can always introduce sum types for handling any
combination of types you want. The only requirement is that you
explicitly wrap up all types into the sum type with the appropriate
constructors. A sum type deconstructor ensures that you handle all
possible cases when you translate back to the "raw" types.
- John
Christopher Diggins — 2008-03-06 23:41:07
On Thu, Mar 6, 2008 at 6:12 PM, Stevan Apter <
sa@...> wrote:
> forget about the partial application case. what i want in my toolkit
> is a single combinator 'map' which takes an n-ary function and applies
> it to each of a list of length-n lists. not map1, map2, ... for each
> case. is that what's going on here? or does typing rule out having
> such a combinator?
It really has to do with how you structure your lists. In Cat this is
feasible if your list is a lists of functions.
define mapN { [apply] swap compose [quote] compose map }
[[1 2] [3 4] [5 6]] list [+] mapN => [[3][7][11]]
[[1] [2] [3] [4]] list [2 *] mapN => [[2][4][6][8]] //
Cat however has untyped lists, so there is some cheating going on at
the type-level, but this would be feasible with typed lists as well.
The only serious restriction here AFAICS is that your function has to
produce a single result even though it can consume n arguments.
- Christopher
William Tanksley, Jr — 2008-03-06 23:56:16
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> I explained what 'unlist' does in an earlier email. You may've missed
> it.
Sorry, sure did.
> What 'unlist' does is take three arguments. The first is a list. The
> second is a function that says what to do if that list is null. The
> the third is a function that acts on the list after is has been
> unconsed if it is not null. The 'unlist' function is called a sum
> deconstructor as lists are sum types (they're either a "null" or a
> "cons").
Cool! So 'unlist' does exactly what FunForth does (well, it's
typesafe, unlike FunForth).
I suppose I don't get why lambdas help with that, then. I assumed you
were talking about pattern matching, since lambdas there could fit
into the pattern, therefore helping you notate what is being
extracted. But if you're only disassembling the parts of a structure,
I don't see why you have to give the parts names.
> - John
-Wm
John Nowak — 2008-03-07 00:09:44
On Mar 6, 2008, at 6:56 PM, William Tanksley, Jr wrote:
>> What 'unlist' does is take three arguments. The first is a list. The
>> second is a function that says what to do if that list is null. The
>> the third is a function that acts on the list after is has been
>> unconsed if it is not null. The 'unlist' function is called a sum
>> deconstructor as lists are sum types (they're either a "null" or a
>> "cons").
>
> Cool! So 'unlist' does exactly what FunForth does (well, it's
> typesafe, unlike FunForth).
>
> I suppose I don't get why lambdas help with that, then. I assumed you
> were talking about pattern matching, since lambdas there could fit
> into the pattern, therefore helping you notate what is being
> extracted. But if you're only disassembling the parts of a structure,
> I don't see why you have to give the parts names.
Ah, sorry if I've confused you. Lambdas don't have anything to do with
it; they just let you write it in a way that makes it look more like
pattern matching. You can write it without variables if you prefer.
You can even write it with just one variable which is actually nicer:
f map = []
[xs -> f i xs f map cons]
unlist
Since we're not binding the element below 'xs' the element is simply
left on the stack.
- John
William Tanksley, Jr — 2008-03-07 01:01:40
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > Cool! So 'unlist' does exactly what FunForth does (well, it's
> > typesafe, unlike FunForth).
> > I suppose I don't get why lambdas help with that, then. I assumed you
> > were talking about pattern matching, since lambdas there could fit
> > into the pattern, therefore helping you notate what is being
> > extracted. But if you're only disassembling the parts of a structure,
> > I don't see why you have to give the parts names.
> Ah, sorry if I've confused you.
No prob -- my ignorance is not your responsibility.
> Lambdas don't have anything to do with
> it; they just let you write it in a way that makes it look more like
> pattern matching. You can write it without variables if you prefer.
> You can even write it with just one variable which is actually nicer:
> f map = []
> [xs -> f i xs f map cons]
> unlist
Okay, so the challenge is to write that entirely without variables
(i.e. without the benefit of lambdas). Let's try. I'll prototype it
with my stack-shuffles, 'cause I like 'em.
\ f = a function, x = car, s = cdr, y=x f i
map = [] [ fxs--sfxf i sfy--ysf map cons ] unlist
Okay, translate the shuffle notation to familiar operators:
map = [] [ bury over i rot map cons ] unlist
(I define 'bury' as the inverse of 'rot'. Forth calls it '-rot'. I
prefer shuffles when possible, since a shuffle is essentially a
mnemonic name for a series of stack operators, but let's go with what
most people expect.)
Arguably no worse than yours; the body of my definition contains six
words, matching yours if we don't count your lambda and its variable
(beating it otherwise). I consider it an advantage that mine uses only
verbs, while yours mixes nouns and verbs.
> - John
-Wm
John Nowak — 2008-03-07 02:06:04
On Mar 6, 2008, at 8:01 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>
>> Lambdas don't have anything to do with
>> it; they just let you write it in a way that makes it look more like
>> pattern matching. You can write it without variables if you prefer.
>> You can even write it with just one variable which is actually nicer:
>>
>> f map = []
>> [xs -> f i xs f map cons]
>> unlist
>
> Okay, so the challenge is to write that entirely without variables
> (i.e. without the benefit of lambdas). Let's try.
You must've missed my response to you earlier where I gave this
translation:
map = swap
[]
[rot dup 2dip swap map cons]
unlist
> map = [] [ bury over i rot map cons ] unlist
Small point: You forgot the initial swap to put the list on top of the
stack. The type system would've saved you of course.
> Arguably no worse than yours; the body of my definition contains six
> words, matching yours if we don't count your lambda and its variable
> (beating it otherwise).
This seems like a poor way of measuring how easy it is to read and
write code. At least in my case, I know I wrote the pointful version
in about 15 seconds. It took me over a minute to write the pointfree
version. (Perhaps I just need more practice.) I also think the
pointful version is easier to read, although we can certainly disagree.
- John
John Nowak — 2008-03-07 02:33:54
On Mar 6, 2008, at 9:06 PM, John Nowak wrote:
> You must've missed my response to you earlier where I gave this
> translation:
>
> map = swap
> []
> [rot dup 2dip swap map cons]
> unlist
>
>> map = [] [ bury over i rot map cons ] unlist
>
> Small point: You forgot the initial swap to put the list on top of the
> stack. The type system would've saved you of course.
Oh crap. We're both wrong. In particular, if the list is null, neither
of us remembered to pop the function. I also put in a swap for no
reason. We both forgot to place a null back on top in the empty case
too. Oi!
This should work:
map = swap ; put the list on top
[pop null] ; remove 'f', restore the null
[rot dup 2dip map cons] ; i swear this works now
unlist
Perhaps this series of errors is just another argument for lambda
expressions and types. :) Considering the multitude of errors, I'd say
it's a pretty strong one...
- John
Stevan Apter — 2008-03-07 15:11:25
----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, March 06, 2008 6:38 PM
Subject: Re: [stack] sweetening concatenative syntax
>
> On Mar 6, 2008, at 6:12 PM, Stevan Apter wrote:
>
>> forget about the partial application case. what i want in my toolkit
>> is a single combinator 'map' which takes an n-ary function and applies
>> it to each of a list of length-n lists.
>
> Ah, I think maybe there's some confusion here over what we mean by
> "list". (Yes, really!) In Joy, lists, stacks, and functions are all
> magically the same thing. I assume it's similar in XY as well. In
> Fifth, lists, stacks, and functions are all different things. This is
> just one more example of the endless complication that types introduce.
this is the sort of thing that makes me type-averse. i understand that
proponents of types have their reasons, but i can't help thinking that it's
one of those things that language-designers like more than language-users.
one of the beauties of joy is that quotations are lists are programs, and
in some variants, are stacks.
is there really no way to reconcile typing with this elegant simplification?
>
> The 'mapx' function I gave before took a list of lists and a function
> of type 'a b -> b'. In other words, the function is restricted to
> taking only two arguments as is standard for the 'fold' combinator.
>
> It sounds to me like what you're describing is a function that takes a
> list of *stacks* and applies an n-ary function to each stack in the
> list. This is doable, where 'map' below is the "normal" map you'd find
> in a language like ML, Haskell, or Fifth:
>
> mapx :: {(Stack A)} [A -> B] -> {(Stack B)}
> mapx = quote [infra] compose map
>
> There are some limitations. In particular, all stacks in the list need
> to be of the same type. Due to how row variables in stack types must
> get instantiated (the row variables are stripped out), all stacks must
> have the same number of elements and elements in corresponding
> positions in each stack must be of the same type.
>
> This limitation probably isn't too onerous in practice as I can't
> imagine the use case for mapping over a list of elements of various
> types. Note that when I say all elements must be the same type, I
> don't mean that they must all be ints or that they must all be
> strings. You can always introduce sum types for handling any
> combination of types you want. The only requirement is that you
> explicitly wrap up all types into the sum type with the appropriate
> constructors. A sum type deconstructor ensures that you handle all
> possible cases when you translate back to the "raw" types.
>
> - John
>
William Tanksley, Jr — 2008-03-07 15:20:38
Stevan Apter <
sa@...> wrote:
> this is the sort of thing that makes me type-averse. i understand that
> proponents of types have their reasons, but i can't help thinking that it's
> one of those things that language-designers like more than language-users.
> one of the beauties of joy is that quotations are lists are programs, and
> in some variants, are stacks.
There are two good things about types.
The first is that, implemented right, they can help you write code
(for example, Ada's attributes, c.f. e.g.
http://www.csupomona.edu/reference/ada/rm95html-1.0/rm9x-A-05-03.html).
Most people who design statically typed languages don't bother
thinking of how types could be helpful beyond simple static
polymorphism (or worse, overloading).
The second is that they help clarify our understanding of what a
language is doing. If an operation in a language cannot yet be typed,
we do not have a complete idea of what it's doing yet.
I'm not a static typing maniac, but I'm strongly in favor of figuring
out static types, and I've often enjoyed using static languages.
-Wm
Stevan Apter — 2008-03-07 15:30:48
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, March 07, 2008 10:20 AM
Subject: Re: [stack] sweetening concatenative syntax
> Stevan Apter <sa@...> wrote:
>> this is the sort of thing that makes me type-averse. i understand that
>> proponents of types have their reasons, but i can't help thinking that it's
>> one of those things that language-designers like more than language-users.
>> one of the beauties of joy is that quotations are lists are programs, and
>> in some variants, are stacks.
>
> There are two good things about types.
>
> The first is that, implemented right, they can help you write code
> (for example, Ada's attributes, c.f. e.g.
> http://www.csupomona.edu/reference/ada/rm95html-1.0/rm9x-A-05-03.html).
> Most people who design statically typed languages don't bother
> thinking of how types could be helpful beyond simple static
> polymorphism (or worse, overloading).
>
> The second is that they help clarify our understanding of what a
> language is doing. If an operation in a language cannot yet be typed,
> we do not have a complete idea of what it's doing yet.
but if the language is incapable of expressing a well-formed thought
because the type-system prevents that, then so much the worse for typing.
that is, i start with clear and distinct idea of the algorithm and its
data-structures, and then must work around limits on expressibility created
by the type-system ... ?
>
> I'm not a static typing maniac, but I'm strongly in favor of figuring
> out static types, and I've often enjoyed using static languages.
>
> -Wm
>
Christopher Diggins — 2008-03-07 15:40:21
On Fri, Mar 7, 2008 at 10:11 AM, Stevan Apter <
sa@...> wrote:
> ----- Original Message -----
> From: "John Nowak" <john@...>
> To: <concatenative@yahoogroups.com>
> Sent: Thursday, March 06, 2008 6:38 PM
> Subject: Re: [stack] sweetening concatenative syntax
>
> >
> > On Mar 6, 2008, at 6:12 PM, Stevan Apter wrote:
> >
> >> forget about the partial application case. what i want in my toolkit
> >> is a single combinator 'map' which takes an n-ary function and applies
> >> it to each of a list of length-n lists.
> >
> > Ah, I think maybe there's some confusion here over what we mean by
> > "list". (Yes, really!) In Joy, lists, stacks, and functions are all
> > magically the same thing. I assume it's similar in XY as well. In
> > Fifth, lists, stacks, and functions are all different things. This is
> > just one more example of the endless complication that types introduce.
Well you can design a statically language that makes a list synonymous
with the function that generates it. In other words: lists are
functions. I have been experimenting with this approach in Cat, and it
seems to work well.
> this is the sort of thing that makes me type-averse. i understand that
> proponents of types have their reasons, but i can't help thinking that it's
> one of those things that language-designers like more than language-users.
Many language users like static type systems because it means that a
huge chunk of program verification can be done at compile-time. In
other words faster debugging.
> one of the beauties of joy is that quotations are lists are programs, and
> in some variants, are stacks.
Yes I agree.
> is there really no way to reconcile typing with this elegant simplification?
I believe we can.
- Christopher
Stevan Apter — 2008-03-07 15:52:31
----- Original Message -----
From: "Christopher Diggins" <cdiggins@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, March 07, 2008 10:40 AM
Subject: Re: [stack] sweetening concatenative syntax
> On Fri, Mar 7, 2008 at 10:11 AM, Stevan Apter <sa@...> wrote:
>> ----- Original Message -----
>> From: "John Nowak" <john@...>
>> To: <concatenative@yahoogroups.com>
>> Sent: Thursday, March 06, 2008 6:38 PM
>> Subject: Re: [stack] sweetening concatenative syntax
>>
>> >
>> > On Mar 6, 2008, at 6:12 PM, Stevan Apter wrote:
>> >
>> >> forget about the partial application case. what i want in my toolkit
>> >> is a single combinator 'map' which takes an n-ary function and applies
>> >> it to each of a list of length-n lists.
>> >
>> > Ah, I think maybe there's some confusion here over what we mean by
>> > "list". (Yes, really!) In Joy, lists, stacks, and functions are all
>> > magically the same thing. I assume it's similar in XY as well. In
>> > Fifth, lists, stacks, and functions are all different things. This is
>> > just one more example of the endless complication that types introduce.
>
> Well you can design a statically language that makes a list synonymous
> with the function that generates it. In other words: lists are
> functions. I have been experimenting with this approach in Cat, and it
> seems to work well.
>
>> this is the sort of thing that makes me type-averse. i understand that
>> proponents of types have their reasons, but i can't help thinking that it's
>> one of those things that language-designers like more than language-users.
>
> Many language users like static type systems because it means that a
> huge chunk of program verification can be done at compile-time. In
> other words faster debugging.
i understand, although for various reasons i am not one of those users.
mainly though, it seems to me that most of the programming errors i make
are not the kind that would be caught by static type-checking.
over the years i've come to believe that simplicity and low code-mass
in the language implementation is the best way to reduce the worst kind
of errors in end-user code. i can't help but notice how frequently haskell
and ocaml programmers (at least, those without black-belts) struggle with
their respective type-systems. the ramification of type-theories into
so many alternative approaches alone should indicate that something is
amiss.
>
>> one of the beauties of joy is that quotations are lists are programs, and
>> in some variants, are stacks.
>
> Yes I agree.
>
>> is there really no way to reconcile typing with this elegant simplification?
>
> I believe we can.
excelsior.
>
> - Christopher
>
Christopher Diggins — 2008-03-07 16:02:37
> over the years i've come to believe that simplicity and low code-mass
> in the language implementation is the best way to reduce the worst kind
> of errors in end-user code. i can't help but notice how frequently haskell
> and ocaml programmers (at least, those without black-belts) struggle with
> their respective type-systems.
And those with black-belts are so proud of themselves they think
trivial software is worth publishing in academic journals. Anyway, for
me happiness is in between the two. I like C# for this reason, as must
or little type safety as you want.
> the ramification of type-theories into
> so many alternative approaches alone should indicate that something is
> amiss.
I don't quite follow what you are getting at
On another note, I would really appreciate a list of "must-have" array
primitives. Which ones need to be implemented in a language (so that
they can be leverage by optimizers) and which ones can be defined as
libraries. The Heron 0.19 release is around the corner, and I would
like a happy Stevan Apter on my side. :-)
I have also been wondering what it means to add a vector of two
elements to a vector of four elements which I believe you mentioned in
an earlier post. In my little type-safe world, this is undefined.
Christopher Diggins
William Tanksley, Jr — 2008-03-07 16:19:22
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > John Nowak <john@...> wrote:
> >> Lambdas don't have anything to do with
> >> it; they just let you write it in a way that makes it look more like
> >> pattern matching. You can write it without variables if you prefer.
> >> You can even write it with just one variable which is actually nicer:
> >> f map = []
> >> [xs -> f i xs f map cons]
> >> unlist
> > Okay, so the challenge is to write that entirely without variables
> > (i.e. without the benefit of lambdas). Let's try.
> You must've missed my response to you earlier where I gave this
> translation:
> map = swap
> []
> [rot dup 2dip swap map cons]
> unlist
No, I saw it -- actually, I saw one with a '2keep', so perhaps I
missed the one you're showing. There are 2 reasons I wrote my own: 1.
I wanted to accept your challenge; 2. I don't like words with numbers
in them (2keep? I don't know what that does).
> > map = [] [ bury over i rot map cons ] unlist
> Small point: You forgot the initial swap to put the list on top of the
> stack. The type system would've saved you of course.
I didn't forget it; I was imitating your lambda code, in which the
list is already on top of the stack. Isn't that what "xs -> f i"
implies? So is your lambda code also wrong?
Anyhow, that makes my version look like this:
map = [drop null] [ swap bury over i rot map cons ] unlist
Or, using a shuffle:
map = [drop null] [ fsx--sfxf i rot map cons ] unlist
> > Arguably no worse than yours; the body of my definition contains six
> > words, matching yours if we don't count your lambda and its variable
> > (beating it otherwise).
> This seems like a poor way of measuring how easy it is to read and
> write code. At least in my case, I know I wrote the pointful version
> in about 15 seconds.
This is moving the goalposts. When you posted the challenge you didn't
mention anything about programming time; all you did was post a few
different variants, and then you posted one that you said was "better"
(the one with only a single lambda variable). The only difference I
see is that the single-variable one is shorter, so I assumed shortness
was your criteria.
I didn't time my coding, and I didn't know that was the goal, so I've
got no way to compete here.
Not that speed competition would be fair -- I've never seen your
'unlist' API anyhow, and now it appears you're doing something tricky
or incorrect in your example code (by putting the list on top).
> It took me over a minute to write the pointfree
> version. (Perhaps I just need more practice.) I also think the
> pointful version is easier to read, although we can certainly disagree.
Perhaps you find it easier, but there's objective reason why it
shouldn't be easier. The point-free version is linear and has fewer
symbols. (Your point-free version -- the '2dip' one -- is okay, but
IMO anytime you play with 'dip' you introduce reading difficulty.)
> Perhaps this series of errors is just another argument for lambda
> expressions and types. :) Considering the multitude of errors, I'd say
> it's a pretty strong one...
Considering that all your lambda implementations had the same errors,
I don't see how that applies. The specification was unclear, we both
misunderstood, and produced correct programs for the wrong API.
> - John
-Wm
William Tanksley, Jr — 2008-03-07 16:36:27
Stevan Apter <
sa@...> wrote:
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> > Stevan Apter <sa@...> wrote:
> >> this is the sort of thing that makes me type-averse. i understand that
> >> proponents of types have their reasons, but i can't help thinking that it's
> >> one of those things that language-designers like more than language-users.
> >> one of the beauties of joy is that quotations are lists are programs, and
> >> in some variants, are stacks.
> > The second is that they help clarify our understanding of what a
> > language is doing. If an operation in a language cannot yet be typed,
> > we do not have a complete idea of what it's doing yet.
> but if the language is incapable of expressing a well-formed thought
> because the type-system prevents that, then so much the worse for typing.
> that is, i start with clear and distinct idea of the algorithm and its
> data-structures, and then must work around limits on expressibility created
> by the type-system ... ?
Well, such a type system is simply inadequate. Yes, that describes all
known type systems :-). The eternal hope is that there might exist
some type system which will NOT place those limits on "well-formed
thoughts", but will stop poorly formed or incomplete ones.
It's known that typechecking is uncomputable -- a truly complete type
system would have to be able to specify whether a program halts, for
example. Almost all existing type systems are subsets that we HOPE
will provide enough of the problem without having to do anything
uncomputable. Type inference takes on an NP-complete problem (but, of
course, avoids the uncomputable one).
There are type systems that can easily specify uncomputable problems.
So far I'm extremely unimpressed -- they are UGLY, and they provide no
useful functionality, only restrictions.
To me, unit tests are useful for many of the things static typing is
used for, and contracts are useful for many of the rest. But there are
things remaining that static typing is good for... Especially when
your editor knows about them and can help you.
-Wm
John Nowak — 2008-03-07 19:15:56
On Mar 7, 2008, at 11:19 AM, William Tanksley, Jr wrote:
>> Small point: You forgot the initial swap to put the list on top of
>> the
>> stack. The type system would've saved you of course.
>
> I didn't forget it; I was imitating your lambda code, in which the
> list is already on top of the stack. Isn't that what "xs -> f i"
> implies? So is your lambda code also wrong?
No, it's correct. The list wasn't already on the top of the stack, the
function was. By binding the function to 'f', we remove it from the
stack, causing the list to be on top. This is why the call to 'unlist'
makes sense.
> This is moving the goalposts. When you posted the challenge you didn't
> mention anything about programming time;
>
> I didn't time my coding, and I didn't know that was the goal, so I've
> got no way to compete here.
I was just relaying my personal experience. There was no timed
challenge.
> Not that speed competition would be fair -- I've never seen your
> 'unlist' API anyhow, and now it appears you're doing something tricky
> or incorrect in your example code (by putting the list on top).
I posted the type and explained it. I showed how you can use it to
write head/tail/null?/uncons. I'm not sure what else I can do. At the
very least, I did say that, "What 'unlist' does is take three
arguments. The first is a list."
>> It took me over a minute to write the pointfree
>> version. (Perhaps I just need more practice.) I also think the
>> pointful version is easier to read, although we can certainly
>> disagree.
>
> Perhaps you find it easier, but there's objective reason why it
> shouldn't be easier. The point-free version is linear
They're both linear, at least where "linear" refers to how objects are
referenced. If you mean that it reads left to right as a strict means
of sequencing, then no, it isn't linear. I'm not sure that's
necessarily something that makes something easier to read however.
Certainly mathematicians have been inventing notations that read in
many different ways for quite awhile.
> IMO anytime you play with 'dip' you introduce reading difficulty.
Maybe it's a matter of taste then. I find 'dip' a lot easier to keep
in my head than shuffles.
>> Perhaps this series of errors is just another argument for lambda
>> expressions and types. :) Considering the multitude of errors, I'd
>> say
>> it's a pretty strong one...
>
> Considering that all your lambda implementations had the same errors,
> I don't see how that applies.
They did not have any errors, although it seems to me that the errors
in our pointfree code were due to translating the lambda-based
versions and getting it wrong. In particular, the lambda version
didn't need to pop the function because binding it to 'f' removed it
from the stack. When doing the translation, we both forgot to pop it
explicitly.
- John
John Nowak — 2008-03-07 19:26:05
On Mar 7, 2008, at 2:15 PM, John Nowak wrote:
> They did not have any errors, although it seems to me that the errors
> in our pointfree code were due to translating the lambda-based
> versions and getting it wrong. In particular, the lambda version
> didn't need to pop the function because binding it to 'f' removed it
> from the stack. When doing the translation, we both forgot to pop it
> explicitly.
Actually, let me clarify. *I* forgot to pop it explicitly. You didn't
pop it because apparently not clearly explaining how variables work.
I'll try to get this written up in a more formal manner.
- John
John Nowak — 2008-03-07 19:41:51
On Mar 7, 2008, at 10:30 AM, Stevan Apter wrote:
> but if the language is incapable of expressing a well-formed thought
> because the type-system prevents that, then so much the worse for
> typing.
> that is, i start with clear and distinct idea of the algorithm and its
> data-structures, and then must work around limits on expressibility
> created
> by the type-system ... ?
It's all a question of how much complexity the type system adds and
how much it gets in your way compared to how much it helps you out.
Before you start worrying that the type system will stop you from
expressing things in clear ways, it's probably better to get some
experience with the type system in question first. You may be
surprised that it doesn't get in the way much at all.
- John
John Nowak — 2008-03-07 19:47:01
On Mar 7, 2008, at 10:20 AM, William Tanksley, Jr wrote:
> There are two good things about types.
>
> The second is that they help clarify our understanding of what a
> language is doing. If an operation in a language cannot yet be typed,
> we do not have a complete idea of what it's doing yet.
This is a very important point, and it's the primary reason that I'm
pursuing a typed concatenative language. I'm doing all of the
prototyping in Scheme, so it isn't as if I'm insistent that typed
languages are the old way to go. Even if you prefer untyped languages,
I think further research in this direction will be helpful to
concatenative languages as a whole.
Oh I can't write anything that sounds nice in the morning...
- John
William Tanksley, Jr — 2008-03-07 20:13:18
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> >> Small point: You forgot the initial swap to put the list on top of
> >> the stack. The type system would've saved you of course.
> > I didn't forget it; I was imitating your lambda code, in which the
> > list is already on top of the stack. Isn't that what "xs -> f i"
> > implies? So is your lambda code also wrong?
> No, it's correct. The list wasn't already on the top of the stack, the
> function was. By binding the function to 'f', we remove it from the
> stack, causing the list to be on top. This is why the call to 'unlist'
> makes sense.
The *function*?? I'm confused. The function can't possibly be at the
top of the stack. Here's your code (slightly bugfixed).
> f map = [pop nil]
> [xs -> f i xs f map cons]
> unlist
As far as I can see, 'unlist' doesn't pass any function around; it
doesn't know about a function. Your 'f map' notation appears to be
creating a named lambda with a parameter named 'f'; that is the
function and it gets passed around, but if 'map' wasn't defined as a
lambda the function would be _under_ the 'x' and 'xs' parameters that
'unlist' creates for the second quotation to consume.
Right? What am I missing?
> > This is moving the goalposts. When you posted the challenge you didn't
> > mention anything about programming time;
> > I didn't time my coding, and I didn't know that was the goal, so I've
> > got no way to compete here.
> I was just relaying my personal experience. There was no timed
> challenge.
I didn't take offense -- sorry for the ambiguity (I seem to be vague a
lot). But you DID challenge us to implement this algorithm in a
"purely concatenative form", and you claimed that your version with
lambdas was "objectively easier to understand". Nothing about it
taking 15 seconds to program.
I think I've met your challenge, and am at least entitled to claim the
your "objectively easier" claim is incorrect.
> > Not that speed competition would be fair -- I've never seen your
> > 'unlist' API anyhow, and now it appears you're doing something tricky
> > or incorrect in your example code (by putting the list on top).
> I posted the type and explained it. I showed how you can use it to
> write head/tail/null?/uncons. I'm not sure what else I can do. At the
> very least, I did say that, "What 'unlist' does is take three
> arguments. The first is a list."
I wasn't complaining about bad documents in that paragraph -- I'm just
pointing out that I can't write a 15-second program in a brand new
API, even one that's fully documented. So I admit that my version took
longer than 15 seconds to write.
> >> It took me over a minute to write the pointfree
> >> version. (Perhaps I just need more practice.) I also think the
> >> pointful version is easier to read, although we can certainly
> >> disagree.
> > Perhaps you find it easier, but there's objective reason why it
> > shouldn't be easier. The point-free version is linear
> They're both linear, at least where "linear" refers to how objects are
> referenced.
'f' is referred to twice; that's nonlinear.
> If you mean that it reads left to right as a strict means
> of sequencing, then no, it isn't linear. I'm not sure that's
> necessarily something that makes something easier to read however.
> Certainly mathematicians have been inventing notations that read in
> many different ways for quite awhile.
Left to right IS easier than jumpy. That's a simple and clear rule. It
doesn't mean that jumpy is bad; sometimes you need jumpy. But it's
objectively more complex.
> > IMO anytime you play with 'dip' you introduce reading difficulty.
> Maybe it's a matter of taste then. I find 'dip' a lot easier to keep
> in my head than shuffles.
I think that's reasonable. (Wow, agreement!) When considering shuffles
versus dips, keep in mind that dip essentially *both* performs a
shuffle and an execution. Shuffles are technically simpler (because
they _only_ rearrange), but of course there's only one thing 'dip' can
do, while there's a lot of things shuffles can do. In other words, I
do have sympathy for your argument, and I concede that it's
subjective.
> >> Perhaps this series of errors is just another argument for lambda
> >> expressions and types. :) Considering the multitude of errors, I'd
> >> say it's a pretty strong one...
> > Considering that all your lambda implementations had the same errors,
> > I don't see how that applies.
> They did not have any errors, although it seems to me that the errors
> in our pointfree code were due to translating the lambda-based
> versions and getting it wrong. In particular, the lambda version
> didn't need to pop the function because binding it to 'f' removed it
> from the stack. When doing the translation, we both forgot to pop it
> explicitly.
I do concede that your lambda probably wasn't wrong; it looks right to
me. What seems wrong to me is your recent claim that in the stack
version, the function is on top of the stack rather than car and cdr.
> - John
-Wm
William Tanksley, Jr — 2008-03-07 20:18:15
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> This is a very important point, and it's the primary reason that I'm
> pursuing a typed concatenative language. I'm doing all of the
> prototyping in Scheme, so it isn't as if I'm insistent that typed
> languages are the old way to go. Even if you prefer untyped languages,
> I think further research in this direction will be helpful to
> concatenative languages as a whole.
I very much look forward to the results of your research.
> Oh I can't write anything that sounds nice in the morning...
Hmm, you made sense to me. And I also appreciate your ability to
respond to criticism politely, even when it makes little sense.
> - John
-Wm
Stevan Apter — 2008-03-07 20:30:02
----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, March 07, 2008 2:41 PM
Subject: Re: [stack] sweetening concatenative syntax
> On Mar 7, 2008, at 10:30 AM, Stevan Apter wrote:
>
>> but if the language is incapable of expressing a well-formed thought
>> because the type-system prevents that, then so much the worse for
>> typing.
>> that is, i start with clear and distinct idea of the algorithm and its
>> data-structures, and then must work around limits on expressibility
>> created
>> by the type-system ... ?
>
> It's all a question of how much complexity the type system adds and
> how much it gets in your way compared to how much it helps you out.
> Before you start worrying that the type system will stop you from
> expressing things in clear ways, it's probably better to get some
> experience with the type system in question first. You may be
> surprised that it doesn't get in the way much at all.
yes, i think that's reasonable. my first test is: can it manage
a polyvalent map combinator? bzzzzt!
ok, seriously (but i wasn't being altogether facetious just now)
my suspicion, which lacks sufficient evidence to be an opinion or
a belief, is that an adequate type system for an array language is
much more difficult to achieve than one for a scalar language, and since i
am a devoted arrayhead, the bar is pretty high for me: no convenience
offered by any statically-typed scalar language will offset the advantages i
derive from any dynamically-typed array language.
>
> - John
>
John Nowak — 2008-03-07 20:57:08
On Mar 7, 2008, at 3:13 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>> William Tanksley, Jr wrote:
>>>> Small point: You forgot the initial swap to put the list on top of
>>>> the stack. The type system would've saved you of course.
>>> I didn't forget it; I was imitating your lambda code, in which the
>>> list is already on top of the stack. Isn't that what "xs -> f i"
>>> implies? So is your lambda code also wrong?
>
>> No, it's correct. The list wasn't already on the top of the stack,
>> the
>> function was. By binding the function to 'f', we remove it from the
>> stack, causing the list to be on top. This is why the call to
>> 'unlist'
>> makes sense.
>
> The *function*?? I'm confused. The function can't possibly be at the
> top of the stack. Here's your code (slightly bugfixed).
>
>> f map = [pop nil]
>> [xs -> f i xs f map cons]
>> unlist
Er, almost. It does need to call 'nil' in the first quote, but not
pop. (Maybe it *was* buggy before as I forgot the null, I can't even
recall at this point.)
Perhaps I should break it down so this is all crystal clear.
Here's the type for map:
map :: {a} [a -> b] -> {b}
What this says is that the top element of the stack must be a
function. The element below the top must be a list. If the list is of
elements of type 'a', the function must be one that can transform
elements of type 'a' to type 'b'. The result of calling map is then a
list of type 'b'.
Alright, so when we're writing the map function, we have to keep in
mind that the function passed in will be on top of the stack.
Now let's review the type of unlist again:
unlist :: A {b} [A -> C] [A b {b} -> C] -> C
This is somewhat complicated. What it says is that the top two items
on the stack must be functions. The third item must be a list. The
function on top of the stack gets called with the list unconsed if the
list is not null. The other function gets called with nothing on the
stack if the list is null. 'A' and 'C' represent "the rest of the
stack". It isn't too important to full understand them here.
Here's a quick example that might help:
add-ignoring-list = 1 2 null [+] [pop pop +] unlist
add-ignoring-list2 = 1 2 {"hi" "lo"} [+] [pop pop +] unlist
(The curly braces indicate a list literal.)
Both functions will return "3". In the first, the list is null, so +
is just called on the stack '1 2' (the list has been permanently
killed at this point). In the second, the list is not null, so the
other function gets called with the list unconsed. At this point, the
stack is '1 2 "hi" {"lo"} null'. After we pop twice, we add 1 and 2
together yielding 3.
If you go back now and look at the type, maybe it makes some sense.
So let's look at pointfree map again:
map = swap
[pop null]
[rot dup 2dip map cons]
unlist
Now when map gets called, the function supplied to map will be on the
top. Therefore, the first thing we need to do is 'swap' so that the
list is on top as unlist needs it as the third argument. After the
swap, the stack looks something like this:
<fn> <list of a>
We then push on the quotations:
<fn> <list of a> [pop null] [rot dup 2dip map cons]
And then we call unlist. Now if the list is null, we get this scenario:
<fn> pop null
In that case, we pop the function and push on a new null list.
Therefore, mapping a function over null yields null.
Now, if the list isn't null, we get this scenario:
<fn> a <list of a> rot dup 2dip map cons
So we rotate and dup:
a <list of a> <fn> <fn> 2dip map cons
2dip is the same as dip except that it saves and restores the top two
elements instead of only the top element. This is the same as '2keep'
in factor (I think). Therefore, 2dip calls the top function with the
list and the other function off the stack, and then restores them when
finished. So we get something like this, where 'fn(a)' is the result
of applying 'fn' to 'a':
fn(a) <list of a> <fn> map cons
Right, so now we're back in the situation with a function on top and a
list below it. We can call 'map' again. It should be understandable
from this point on I think.
Now let's look at the pointful translation:
f map = [null]
[xs -> f i xs f map cons]
unlist
This version of 'map' binds the top element passed to 'map' to 'f'. As
before, the top element passed to map must be a function, so we bind
this function to 'f'. This binding in effect *removes* the function
from the stack. Therefore, when map gets called, we have something
like this:
<list of a>
f = <fn>
Right. So the list is on the top and the function is in 'f'. Now we
push on the quotations:
<list of a> [null] [xs -> f i xs f map cons]
f = <fn>
Assuming the list is null, we get this scenario:
null
f = <fn>
And so the final result is null as we want after evaluating 'null' to
push a new null onto the stack.
If the list isn't null, we get this:
a f i xs f map cons
f = <fn>
xs = <list of a>
Normally '<list of a>' would be on the stack above 'a' (as before),
but we bind the top element to 'xs' instead. Evaluating 'f' then
pushes 'f' onto the stack and 'i' calls it to apply it to a. We then
have this:
fn(a) xs f map cons
f = <fn>
xs = <list of a>
So we go ahead and push on 'xs':
fn(a) <list of a> f map cons
f = <fn>
xs = <list of a>
And then 'f':
fn(a) <list of a> <fn> map cons
f = <fn>
xs = <list of a>
And then you can see we are right where we were before the recursion
in the pointfree example.
If you managed to read that, hopefully it cleared things up a bit. If
it helps, you can think of lambdas as a more powerful shuffle
notation. Where you might write 'abc--cabb', you can write '[a b c ->
c a b b] i' instead.
- John
John Nowak — 2008-03-07 21:11:27
On Mar 7, 2008, at 3:13 PM, William Tanksley, Jr wrote:
>>> Perhaps you find it easier, but there's objective reason why it
>>> shouldn't be easier. The point-free version is linear
>
>> They're both linear, at least where "linear" refers to how objects
>> are
>> referenced.
>
> 'f' is referred to twice; that's nonlinear.
Keep in mind that the pointful version gets translated to pointfree
code. It's just syntactic sugar. After the translation, each value is
referenced only once. The function will need to be copied once (as it
does when writing the pointfree version by hand), but no actual
copying needs to occur if the function was not created via composing
or partial application; it's just a pointer assignment. That's just an
implementation detail though.
Perhaps it'll be easier to show that it's linear once I can actually
do the conversion... *ahem*
- John
William Tanksley, Jr — 2008-03-07 21:45:39
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> >> Types also complicate things. For example, you can't factor
> >> out the 'dup i' in '[swap] dup i' unless your system has higher-rank
> >> polymorphism or equi-recursive types.
> > Well, technically if your typesystem was "concatenative" you could
> > factor it out.
> This is true. The original type system I had was concatenative (well,
> really "compositional" is the correct term).
Why? I'm going to start pushing back hard on this.
"Concatenative" refers to a language in which the syntax is based on
concatenation, and in which the semantics maps concatenation to some
associative operation (function composition is the most interesting
one currently defined). I suppose "compositional" means a language
that's somehow based on function composition, which certainly
describes all the interesting concatenative languages (and also some
non-concatenative subsets of other languages).
> Unfortunately, this
> property gets lost quite quickly as you expand the power of the type
> system.
Or more accurately, it gets lost when you change the type system and
inferrer without regard for maintaining associativity. I don't mind
that, but a nagging question remains: is it possible to infer types
for a concatenative language?
> The only reason the original system was compositional was
> because it would refuse to accept things like "[swap] dup i" as all
> variables were non-generic and you'd hit an occurs check no matter
> what order you attempted it in.
Makes sense.
> At the moment, it seems that a truly
> compositional type system imposes too many limitations. If there are
> ways around this I've not discovered them yet.
I agree; there may not be any ways around it (aside from giving up on
most of the type inference). I wish I knew enough to experiment with
this; I've been thinking of a few things, but I'm hindered by a tiny
bit of knowledge, enough to know that HM type inference is exponential
in the worst case, and I kind of expect that the changes I'm thinking
about are bad cases.
> > If your typesystem isn't concatenative, then the resulting language
> > is no longer strictly concatenative
> This all depends on your definition of concatenative.
And on your definition of "language", and "type", and "is". I think
we've got an excellent definition; let's go forward with it. Or
propose a new one.
> The language is
> still expressed in terms of the functional forms of composition and
> quotation. Concatenation still denotes composition. The limitation is
> that you cannot compose functions in any order. This doesn't seem to
> be a problem in practice, although it certainly is unfortunate.
It means that the properties of the semantics fail to match the
properties of the syntax. That's a pretty severe change.
> > I can't criticise anyone for failing to have a concatenative type
> > system, since I don't know what such a thing would look like --
> I've been meaning to write up how to perform inference for a
> compositional type system. If anyone is interested I'll bump this up
> in my priority queue.
I'll read it.
> - John
-Wm
William Tanksley, Jr — 2008-03-07 22:15:56
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> >>> Perhaps you find it easier, but there's objective reason why it
> >>> shouldn't be easier. The point-free version is linear
> >> They're both linear, at least where "linear" refers to how objects
> >> are referenced.
> > 'f' is referred to twice; that's nonlinear.
> Keep in mind that the pointful version gets translated to pointfree
> code. It's just syntactic sugar.
We're comparing lambda notation to pure concatenative notation. Your
claim is that lambda notation is "objectively" superior. It's a
comparison of notations, not of underlying machine architectures.
You can't have it both ways, using lambda notation to make something
look good (subjectively) and then converting it to a concatenative
notation to make it meet some objectively measurable property.
It's objectively true that lambda notation freely allows nonlinear
references. It's also true that this can be optimized away, but it's
NOT clear how expensive that will be (the expense is always up-front
with a concatenative notation, which is sometimes uncomfortable but
always clear).
> After the translation, each value is
> referenced only once.
And before the translation, the variable is used nonlinearly.
> Perhaps it'll be easier to show that it's linear once I can actually
> do the conversion... *ahem*
In order to implement my version I directly translated your code... So
I know it can be done.
> - John
-Wm
John Nowak — 2008-03-08 02:37:16
On Mar 7, 2008, at 5:15 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>
>> William Tanksley, Jr wrote:
>>
>>> 'f' is referred to twice; that's nonlinear.
>>
>> Keep in mind that the pointful version gets translated to pointfree
>> code. It's just syntactic sugar.
>
> We're comparing lambda notation to pure concatenative notation. Your
> claim is that lambda notation is "objectively" superior.
My claim was that it was superior for a particular case, to be clear.
I certainly don't believe this is true in the general case.
> You can't have it both ways, using lambda notation to make something
> look good (subjectively) and then converting it to a concatenative
> notation to make it meet some objectively measurable property.
I don't understand. It seems I can indeed have it both ways. Isn't
converting a language to a simpler language what compilers do all the
time? Maybe I'm misunderstanding.
> It's objectively true that lambda notation freely allows nonlinear
> references.
This is incorrect. "Linear" means that *values* have at most one
reference to them. It has nothing to do really with how often a given
variable shows up the source code. Take a look at Henry Baker's Linear
Lisp. It certainly has lambdas, but it is also certainly linear. There
are also languages like Clean that enforce linearity through the type
system. Likewise, you can have non-linear languages that do not have
variables. Look at Joy for example.
> It's also true that this can be optimized away, but it's
> NOT clear how expensive that will be (the expense is always up-front
> with a concatenative notation, which is sometimes uncomfortable but
> always clear).
There actually are clear rules for determining how many times copying
will be necessary when using lambda expressions. The rule is that a
variable will be copied N-1 times where N is the number of times it is
used. There is only one exception to this rule: Uses in separate
functions "directly applied" to a sum deconstructor (unlist, if, etc)
do not require copying. The implementation may choose to eliminate
additional copies if possible as well, just as it may do when you
write code in a purely pointfree form, but that's besides the point.
One of my requirements for introducing lambdas is that there be very
clear rules for when copying will occur, so you can be sure this will
be formally specified, simple, and not implementation-dependent.
>
- John
John Nowak — 2008-03-08 03:12:27
On Mar 7, 2008, at 4:45 PM, William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>
>> William Tanksley, Jr wrote:
>>
>>
>>> Well, technically if your typesystem was "concatenative" you could
>>> factor it out.
>>
>> This is true. The original type system I had was concatenative (well,
>> really "compositional" is the correct term).
>
> Why? I'm going to start pushing back hard on this.
Ah, I should be more careful here. This has nothing to do with the
concatenative versus compositional discussion from awhile back. I use
the word "compositional" as it already has an established meaning with
respect to type systems. (See
http://www.cs.ioc.ee/~ando/publications/cats06.pdf
for one example). Compositional also implies that that we're talking
about a language where programs are expressed in terms of the
associative operation of composition. This isn't necessarily the case
with all concatenative languages. Regardless, my primary insistence on
the term was due to it already being established. I've no interest in
calling Joy "compositional" instead of "concatenative" or anything
like that.
>> Unfortunately, this property gets lost quite quickly as you
>> expand the power of the type system.
>
> Or more accurately, it gets lost when you change the type system and
> inferrer without regard for maintaining associativity.
I'd argue that you need to drop associativity if you want a more
powerful system.
> I don't mind that, but a nagging question remains: is it possible to
> infer types for a concatenative language?
A Cat-like language without generic type variables does allow a
compositional type system (even with the addition of first-class
stacks and parameterized types). The downside is that you can't apply
a single polymorphic function to arguments of different types. (This
is often called let polymorphism.) My original system worked as such.
As I've expanded it, I've had no choice but to drop the compositional
nature of the system. I should note the current system types all
functions that the original compositional system did, occasionally
with more general types, so no expressivity is lost.
Perhaps this isn't answering your question. If not, could you be more
clear?
>>> If your typesystem isn't concatenative, then the resulting language
>>> is no longer strictly concatenative
>>
>> This all depends on your definition of concatenative.
>
> And on your definition of "language", and "type", and "is". I think
> we've got an excellent definition; let's go forward with it. Or
> propose a new one.
Well, my point is this: If a concatenative language is one where
concatenation denotes function composition, then the language is still
concatenative. If a concatenative language also requires that you be
able to extract any portion of a program and replace it with a name
that represents that portion, then no, it wouldn't be concatenative.
For example, if 'a b c d e' must be equivalent to 'a f e' where 'f ==
b c d', then it isn't concatenative.
There may be a solution to this. Functions could be annotated to
indicate that it is okay if they fail to type check in certain ways.
When they are used in another function, the body of the first function
would be substituted in directly and would make use of the additional
contextual information. This would allow you to write a function like
'm = dup i' provided that it produces a valid type in the contexts in
which it is used. Of course you could always just do this with the
macro system as well, so it isn't clear that there's an additional
need for such annotations in practice.
Perhaps the system could be smart enough to detect that a function
that fails to check could be checked if more information were given
and then would appropriately delay checking. This isn't such a weird
idea: ML does something similar with overloaded operators, albeit in a
more limited form. It isn't clear that this is worth the additional
complexity however (especially as macros can be used to compensate),
or that it would be able to cover all cases, or even that the cases it
could cover would be useful functions you'd want to have anyway.
If you really want to preserve the simplicity of Joy and its
compositional nature, and yet also get some of the benefits of static
typing, I have a strong suspicion that you'll need a soft type system.
Of course, practical soft type systems introduce entirely new levels
of complexity...
- John
William Tanksley, Jr — 2008-03-08 18:14:21
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > John Nowak <john@...> wrote:
> >> William Tanksley, Jr wrote:
> >>> 'f' is referred to twice; that's nonlinear.
> >> Keep in mind that the pointful version gets translated to pointfree
> >> code. It's just syntactic sugar.
> > We're comparing lambda notation to pure concatenative notation. Your
> > claim is that lambda notation is "objectively" superior.
> My claim was that it was superior for a particular case, to be clear.
> I certainly don't believe this is true in the general case.
I didn't notice that claim; if I had I wouldn't have responded. I
agree that there are situations and needs for which lambdas are better
than stack shuffles. I don't think this is one.
> > You can't have it both ways, using lambda notation to make something
> > look good (subjectively) and then converting it to a concatenative
> > notation to make it meet some objectively measurable property.
> I don't understand. It seems I can indeed have it both ways. Isn't
> converting a language to a simpler language what compilers do all the
> time? Maybe I'm misunderstanding.
But you can't measure the readability of a language NOTATION in
comparison to a different notation by converting the first one into
the second. By that standard Brainf**k and Haskell have the same
readability (they can both be converted to x86 machine code).
> > It's objectively true that lambda notation freely allows nonlinear
> > references.
> This is incorrect. "Linear" means that *values* have at most one
> reference to them. It has nothing to do really with how often a given
> variable shows up the source code. Take a look at Henry Baker's Linear
> Lisp. It certainly has lambdas, but it is also certainly linear. There
> are also languages like Clean that enforce linearity through the type
> system.
I'm trying to find where linear lisp or Clean's uniqueness types allow
multiple uses of the same variable. I'm not finding that; it appears
to me that the opposite of what you claim is true: those languages
claim to be linear BECAUSE they enforce only one use of each variable.
What am I missing?
> Likewise, you can have non-linear languages that do not have
> variables. Look at Joy for example.
Joy appears to be linear. What am I missing?
> > It's also true that this can be optimized away, but it's
> > NOT clear how expensive that will be (the expense is always up-front
> > with a concatenative notation, which is sometimes uncomfortable but
> > always clear).
> There actually are clear rules for determining how many times copying
> will be necessary when using lambda expressions. The rule is that a
> variable will be copied N-1 times where N is the number of times it is
> used. There is only one exception to this rule: Uses in separate
> functions "directly applied" to a sum deconstructor (unlist, if, etc)
> do not require copying. The implementation may choose to eliminate
> additional copies if possible as well, just as it may do when you
> write code in a purely pointfree form, but that's besides the point.
> One of my requirements for introducing lambdas is that there be very
> clear rules for when copying will occur, so you can be sure this will
> be formally specified, simple, and not implementation-dependent.
I think that would be excellent. Objectively so :-).
> - John
-Wm
john@johnnowak.com — 2008-03-08 19:22:43
> John Nowak <john@...> wrote:
>
>> I don't understand. It seems I can indeed have it both ways. Isn't
>> converting a language to a simpler language what compilers do all the
>> time? Maybe I'm misunderstanding.
>
> But you can't measure the readability of a language NOTATION in
> comparison to a different notation by converting the first one into
> the second. By that standard Brainf**k and Haskell have the same
> readability (they can both be converted to x86 machine code).
I didn't think I was doing that. I don't mean to suggest that lambda
expressions are superior to pointfree code because they can be converted
to pointfree code and therefore are just as readable if not more so. There
are certainly cases where lambda expressions are less readable. We got
confused somewhere back there...
>> This is incorrect. "Linear" means that *values* have at most one
>> reference to them. It has nothing to do really with how often a given
>> variable shows up the source code. Take a look at Henry Baker's Linear
>> Lisp. It certainly has lambdas, but it is also certainly linear. There
>> are also languages like Clean that enforce linearity through the type
>> system.
>
> I'm trying to find where linear lisp or Clean's uniqueness types allow
> multiple uses of the same variable. I'm not finding that; it appears
> to me that the opposite of what you claim is true: those languages
> claim to be linear BECAUSE they enforce only one use of each variable.
>
> What am I missing?
Here's a function from Baker's "The Forth Shall Be First":
(defun abs (x)
(if-minusp x (- x) x))
Here, 'x' appears more than once in the source code, yet it is still
linear. The only claim I was making is that variables can appear more than
once and the language can still be linear.
What Linear Lisp disallows is implicit copying. For example, to write
"square", you need to do something like this:
(defun square (x)
(let* ((x x-prime (dup x))) ; use Dylan syntax [Shalit92].
(* x x-prime)))
The difference between Linear Lisp and Fifth is that Fifth essentially
just inserts the 'dup' expressions for you. Dan has suggested that perhaps
there should be an option to disallow this behavior so that copying is
explicit. I'm not sure this is necessary provided that there is a clear
and simple set of rules for when copying will occur as I've laid out.
>> Likewise, you can have non-linear languages that do not have
>> variables. Look at Joy for example.
>
> Joy appears to be linear. What am I missing?
Joy is not linear because Joy allows values to have multiple references to
them. For example, if I do '[1 2 3] dup', the list does not get copied.
Instead, there are now two references to the same list on the stack.
Because values can have multiple references to them, it is not safe to
mutate values because you will have visible side effects. This is in
contrast to Fifth where you can always mutate, and hence use more
efficient non-persistent data structures, while remaining purely
functional. (The one exception to this are references. The type system
separates functions that read from or write to reference values from
"pure" code.) Joy's non-linear nature is also the reason it requires a
garbage collector whereas Fifth gets on fine without one as no garbage is
ever created.
In short, enforcing that values are singly referenced is the definition of
linearity. Use-once variables are a means to achieve this that requires
explicit copying. However, you can also have a linear language by
automatically inserting the necessary copying which is what Fifth does.
- John
Don Groves — 2008-03-08 19:58:45
On Mar 8, 2008, at 19:14 , William Tanksley, Jr wrote:
> John Nowak <john@...> wrote:
>> William Tanksley, Jr wrote:
>>> John Nowak <john@...> wrote:
>>>> William Tanksley, Jr wrote:
>>>>> 'f' is referred to twice; that's nonlinear.
>
>>>> Keep in mind that the pointful version gets translated to pointfree
>>>> code. It's just syntactic sugar.
>
>>> We're comparing lambda notation to pure concatenative notation. Your
>>> claim is that lambda notation is "objectively" superior.
>
>> My claim was that it was superior for a particular case, to be
>> clear.
>> I certainly don't believe this is true in the general case.
>
> I didn't notice that claim; if I had I wouldn't have responded. I
> agree that there are situations and needs for which lambdas are better
> than stack shuffles. I don't think this is one.
>
>>> You can't have it both ways, using lambda notation to make something
>>> look good (subjectively) and then converting it to a concatenative
>>> notation to make it meet some objectively measurable property.
>
>> I don't understand. It seems I can indeed have it both ways. Isn't
>> converting a language to a simpler language what compilers do all
>> the
>> time? Maybe I'm misunderstanding.
>
> But you can't measure the readability of a language NOTATION in
> comparison to a different notation by converting the first one into
> the second. By that standard Brainf**k and Haskell have the same
> readability (they can both be converted to x86 machine code).
>
>>> It's objectively true that lambda notation freely allows nonlinear
>>> references.
>
>> This is incorrect. "Linear" means that *values* have at most one
>> reference to them. It has nothing to do really with how often a
>> given
>> variable shows up the source code. Take a look at Henry Baker's
>> Linear
>> Lisp. It certainly has lambdas, but it is also certainly linear.
>> There
>> are also languages like Clean that enforce linearity through the
>> type
>> system.
>
> I'm trying to find where linear lisp or Clean's uniqueness types allow
> multiple uses of the same variable. I'm not finding that; it appears
> to me that the opposite of what you claim is true: those languages
> claim to be linear BECAUSE they enforce only one use of each variable.
>
> What am I missing?
My understanding of linearity is that a value have only a single
reference
at any one instant. So, for example, if a value is pushed on the stack,
it may not be held anywhere else simultaneously as it is now referenced
by the stack. This seems to rule out the possibility of pushing a
variable's
value onto the stack, then doing it again later from the same variable.
Unless I'm missing something...
--
don
>> Likewise, you can have non-linear languages that do not have
>> variables. Look at Joy for example.
>
> Joy appears to be linear. What am I missing?
>
>>> It's also true that this can be optimized away, but it's
>>> NOT clear how expensive that will be (the expense is always up-front
>>> with a concatenative notation, which is sometimes uncomfortable but
>>> always clear).
>
>> There actually are clear rules for determining how many times
>> copying
>> will be necessary when using lambda expressions. The rule is that a
>> variable will be copied N-1 times where N is the number of times
>> it is
>> used. There is only one exception to this rule: Uses in separate
>> functions "directly applied" to a sum deconstructor (unlist, if,
>> etc)
>> do not require copying. The implementation may choose to eliminate
>> additional copies if possible as well, just as it may do when you
>> write code in a purely pointfree form, but that's besides the point.
>> One of my requirements for introducing lambdas is that there be very
>> clear rules for when copying will occur, so you can be sure this
>> will
>> be formally specified, simple, and not implementation-dependent.
>
> I think that would be excellent. Objectively so :-).
>
>> - John
>
> -Wm
>
>
>
> Yahoo! Groups Links
>
>
>
>
William Tanksley, Jr — 2008-03-08 20:00:18
John Nowak <
john@...> wrote:
> William Tanksley, Jr wrote:
> > John Nowak <john@...> wrote:
> >> William Tanksley, Jr wrote:
> >> This is true. The original type system I had was concatenative (well,
> >> really "compositional" is the correct term).
> > Why? I'm going to start pushing back hard on this.
> Ah, I should be more careful here. This has nothing to do with the
> concatenative versus compositional discussion from awhile back. I use
> the word "compositional" as it already has an established meaning with
> respect to type systems. (See http://www.cs.ioc.ee/~ando/publications/cats06.pdf
> for one example). Compositional also implies that that we're talking
> about a language where programs are expressed in terms of the
> associative operation of composition. This isn't necessarily the case
> with all concatenative languages. Regardless, my primary insistence on
> the term was due to it already being established. I've no interest in
> calling Joy "compositional" instead of "concatenative" or anything
> like that.
That's a cool paper; thank you. However, that's not what the paper
appears to mean by "compositionality". Look it up; compositional
appears to refer to the property that a program or statement can be
understood correctly by synthesizing the meaning of its component
phrases. The paper actually claims that the language it's studying is
"non-compositional" due to it not being composed of discrete phrases
-- which means that concatenative languages (by my definition) are
also non-compositional by his definition.
> >> Unfortunately, this property gets lost quite quickly as you
> >> expand the power of the type system.
> > Or more accurately, it gets lost when you change the type system and
> > inferrer without regard for maintaining associativity.
> I'd argue that you need to drop associativity if you want a more
> powerful system.
I'd love to hear that argument. Go for it (although in a new thread)!
The implication would be that it's impossible to define a
strongly-typed and type-inferenced concatenative language (at least by
my definition).
To me, that implies in turn that my definition of 'concatenative' is
most probably wrong.
> > I don't mind that, but a nagging question remains: is it possible to
> > infer types for a concatenative language?
> A Cat-like language without generic type variables does allow a
> compositional type system (even with the addition of first-class
> stacks and parameterized types). The downside is that you can't apply
> a single polymorphic function to arguments of different types. (This
> is often called let polymorphism.) My original system worked as such.
I'm confused by "apply a single polymorphic function to arguments of
different types". Does that refer to, for example, mapping a
polymorphic function to a list containing two values of different
types, either of which is acceptable to the function's polymorphic
type?
So for example, let
[2.0f 2] [2.0f 2] [*] over-each == [4.0f 4].
In other words, it applies a dyadic function to a pair of lists.
I think you're saying that the simple type system can't infer the
types for that code snippet, right? And then you go on to say that
it's impossible to build a type system that can both infer the types,
AND remain associative, right?
> As I've expanded it, I've had no choice but to drop the compositional
> nature of the system. I should note the current system types all
> functions that the original compositional system did, occasionally
> with more general types, so no expressivity is lost.
I would expect more general types to be helpful -- for example, in the
above example I would expect a union type into which both integers and
floats fit.
> Perhaps this isn't answering your question. If not, could you be more
> clear?
It's confirming my suspicion about what you meant, yes. And BTW, I
don't have any rebuttal or anything like that... I'd like to hear your
argument.
> >>> If your typesystem isn't concatenative, then the resulting language
> >>> is no longer strictly concatenative
> >> This all depends on your definition of concatenative.
> > And on your definition of "language", and "type", and "is". I think
> > we've got an excellent definition; let's go forward with it. Or
> > propose a new one.
> Well, my point is this: If a concatenative language is one where
> concatenation denotes function composition, then the language is still
> concatenative. If a concatenative language also requires that you be
> able to extract any portion of a program and replace it with a name
> that represents that portion, then no, it wouldn't be concatenative.
> For example, if 'a b c d e' must be equivalent to 'a f e' where 'f ==
> b c d', then it isn't concatenative.
Yes, the latter is an implication of associativity. Note that
concatenation is an associative operation, as is composition.
> There may be a solution to this. Functions could be annotated to
> indicate that it is okay if they fail to type check in certain ways.
> When they are used in another function, the body of the first function
> would be substituted in directly and would make use of the additional
> contextual information. This would allow you to write a function like
> 'm = dup i' provided that it produces a valid type in the contexts in
> which it is used. Of course you could always just do this with the
> macro system as well, so it isn't clear that there's an additional
> need for such annotations in practice.
> Perhaps the system could be smart enough to detect that a function
> that fails to check could be checked if more information were given
> and then would appropriately delay checking. This isn't such a weird
> idea: ML does something similar with overloaded operators, albeit in a
> more limited form. It isn't clear that this is worth the additional
> complexity however (especially as macros can be used to compensate),
> or that it would be able to cover all cases, or even that the cases it
> could cover would be useful functions you'd want to have anyway.
This is exactly what I've been pondering over the last few days. And
yes, the fact that ML is the only type-inferencing language I know has
contributed to those speculations. I don't insist on the type system
performing the inference automatically, although I do think that if we
can't even guess at how it could be done we don't understand the
problem yet.
> If you really want to preserve the simplicity of Joy and its
> compositional nature, and yet also get some of the benefits of static
> typing, I have a strong suspicion that you'll need a soft type system.
> Of course, practical soft type systems introduce entirely new levels
> of complexity...
After a brief google, I have to say that I'd rather not back up to a
soft type system quite yet... It may be necessary, but I'd rather
understand the static system first.
Note, by the way, that there's very few languages that can be fully
hard-typed. The only one I know is SPARK Ada, and it's hard to code
in; you have to code proofs in addition to your code. (IMO, a language
is fully hard typed ONLY IF it's possible to write serious programs in
it that don't require a runtime, i.e. exception handling.)
> - John
-Wm
john@johnnowak.com — 2008-03-08 20:06:14
On Sat, March 8, 2008 2:58 pm, Don Groves wrote:
> My understanding of linearity is that a value have only a single
> reference at any one instant.
Right.
> So, for example, if a value is pushed on the stack, it may not be held
> anywhere else simultaneously as it is now referenced by the stack.
Right.
> This seems to rule out the possibility of pushing a variable's
> value onto the stack, then doing it again later from the same variable.
There's no variable to push "from". Lambda expressions are translated to
pointfree stack-based code. If a variable is used more than once, explicit
copying is automatically inserted as I described earlier.
- John
William Tanksley, Jr — 2008-03-08 20:20:31
<
john@...> wrote:
> > But you can't measure the readability of a language NOTATION in
> > comparison to a different notation by converting the first one into
> > the second. By that standard Brainf**k and Haskell have the same
> > readability (they can both be converted to x86 machine code).
> I didn't think I was doing that. I don't mean to suggest that lambda
> expressions are superior to pointfree code because they can be converted
> to pointfree code and therefore are just as readable if not more so. There
> are certainly cases where lambda expressions are less readable. We got
> confused somewhere back there...
I'm one of the confused. You said your lambda code was objectively
superior and challenged me to write concatenative code. I did, and
then produced objective measures for my code's acceptability (function
count, token count, linearity, and smooth left-to-right reading). You
*apparently* responded by claiming that those somehow applied to your
notation too because your notation could be translated to mine.
If that's not what you meant, cool; but what DID you mean?
> >> This is incorrect. "Linear" means that *values* have at most one
> >> reference to them. It has nothing to do really with how often a given
> >> variable shows up the source code. Take a look at Henry Baker's Linear
> >> Lisp. It certainly has lambdas, but it is also certainly linear. There
> >> are also languages like Clean that enforce linearity through the type
> >> system.
> > I'm trying to find where linear lisp or Clean's uniqueness types allow
> > multiple uses of the same variable. I'm not finding that; it appears
> > to me that the opposite of what you claim is true: those languages
> > claim to be linear BECAUSE they enforce only one use of each variable.
> > What am I missing?
> Here's a function from Baker's "The Forth Shall Be First":
> (defun abs (x)
> (if-minusp x (- x) x))
> Here, 'x' appears more than once in the source code, yet it is still
> linear.
Read Baker's discussion -- he admits that this is a special case with
"relaxed" rules. It's admittedly not "strictly" linear (his words).
Your code doesn't even meet that special case; it's nonlinear in 'f',
which appears twice sequentially.
> The only claim I was making is that variables can appear more than
> once and the language can still be linear.
You actually claimed that your implementation was linear, which it's not.
I would concede that variables can appear twice, if the variable can
only possibly be encountered once (for example, in both branches of an
'if').
> What Linear Lisp disallows is implicit copying. For example, to write
> "square", you need to do something like this:
> (defun square (x)
> (let* ((x x-prime (dup x))) ; use Dylan syntax [Shalit92].
> (* x x-prime)))
> The difference between Linear Lisp and Fifth is that Fifth essentially
> just inserts the 'dup' expressions for you. Dan has suggested that perhaps
> there should be an option to disallow this behavior so that copying is
> explicit. I'm not sure this is necessary provided that there is a clear
> and simple set of rules for when copying will occur as I've laid out.
I look forward to reading more about Fifth. I agree with you that
linearity is interesting, and that the rules you hint at should make
linear coding with variables a little easier. I don't see how your
rules can improve over established techniques like SSA.
> >> Likewise, you can have non-linear languages that do not have
> >> variables. Look at Joy for example.
> > Joy appears to be linear. What am I missing?
> Joy is not linear because Joy allows values to have multiple references to
> them.
Touche'. Thank you, I definitely have to entirely concede that point.
Well played :-).
> In short, enforcing that values are singly referenced is the definition of
> linearity. Use-once variables are a means to achieve this that requires
> explicit copying. However, you can also have a linear language by
> automatically inserting the necessary copying which is what Fifth does.
Actually, this sounds like it should be pretty cool.
> - John
-Wm
Don Groves — 2008-03-08 20:29:22
On Mar 8, 2008, at 19:06 ,
john@... wrote:
> On Sat, March 8, 2008 2:58 pm, Don Groves wrote:
>
>> My understanding of linearity is that a value have only a single
>> reference at any one instant.
>
> Right.
>
>> So, for example, if a value is pushed on the stack, it may not be
>> held
>> anywhere else simultaneously as it is now referenced by the stack.
>
> Right.
>
>> This seems to rule out the possibility of pushing a variable's
>> value onto the stack, then doing it again later from the same
>> variable.
>
> There's no variable to push "from". Lambda expressions are
> translated to
> pointfree stack-based code. If a variable is used more than once,
> explicit
> copying is automatically inserted as I described earlier.
OK, thanks. The same thing happens in ACL, my as yet unfledged
contribution to the cause. Explicit copying allows you to immediately
free memory when a stack item is consumed, hence there's no way
a value can have multiple references.
--
don
>
> - John
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
john@johnnowak.com — 2008-03-08 21:07:24
William Tanksley, Jr wrote:
> That's a cool paper; thank you. However, that's not what the paper
> appears to mean by "compositionality".
Ah, you're right. Maybe that wasn't the paper I was thinking of... scratch
that then.
>>> Or more accurately, it gets lost when you change the type system and
>>> inferrer without regard for maintaining associativity.
>> I'd argue that you need to drop associativity if you want a more
>> powerful system.
> I'd love to hear that argument. Go for it (although in a new thread)!
I've hinted at the reasons in previous emails. I'll try and write up
something more detailed soon. I'll take a stab at it briefly below...
> To me, that implies in turn that my definition of 'concatenative' is
> most probably wrong.
Perhaps it's just a case of having "strong concatenative" and "weak
concatenative" languages? Different levels of purity are certainly useful
when talking about other paradigms.
> I'm confused by "apply a single polymorphic function to arguments of
> different types". Does that refer to, for example, mapping a
> polymorphic function to a list containing two values of different
> types, either of which is acceptable to the function's polymorphic
> type?
>
> So for example, let
> [2.0f 2] [2.0f 2] [*] over-each == [4.0f 4].
In that example, there'd be no way to even create such lists in the first
place without type classes (where Int and Float are instances of some Num
class) or intersection types. You could of course always wrap things up in
a sum (union/variant) type.
Anyway, what I meant is something like this:
foo = 0 "hi" [pop] dup dip i
Here, the same pop function is applied to both an integer and a string.
Without a notion of generic (aka "free") type variables, this function is
not typeable. This is because the variable in the type of the quotation
(pop :: a -> ) gets instantiated to 'String' for both functions because
the variable in the second function is not free with respect to the first.
Here's the evaluation of the above function on the type level which may help:
Int -- 0
Int String -- "hi"
Int String [a -> ] -- [pop]
Int String [a -> ] [a -> ] -- dup
Int [String ->] -- dip
At this point, we'd get a type error when composing 'i' as we can't unify
the types Int and String. Now here's the same thing allowing variables to
be free:
Int -- 0
Int String -- "hi"
Int String [a -> ] -- [pop]
Int String [a -> ] [b -> ] -- dup -- note the difference!
Int [b ->] -- dip
-- i
Hopefully that makes some sense. Now, let me briefly explain why the
second system (the one with free type variables) breaks concatenativity
with the function '[swap] dup i'. First, without generic type variables:
[a b -> b a] -- [swap]
[a b -> b a] [a b -> b a] -- dup
At this point, we get a type error when composing 'i' as we fail an occurs
check. Here's the derivation:
-- initial composition
R -> R [S a b -> S b a] [S a b -> S b a]
T [T -> U ] -> U
-- unify 'S b a' and 'U'
R -> R [S a b -> S b a] [S a b -> S b a]
T [T -> S b a] -> S b a
-- unify 'S a b' and 'T'
R -> R [S a b -> S b a] [S a b -> S b a]
S a b [S a b -> S b a] -> S b a
-- fail! cannot unify 'b' and '[S a b -> S b a]' due to infinite type
Not sure if that makes any sense. Probably not. I'll explain how to do
these compositions by hand when I eventually write this up. If it does
make sense though, then great.
Now, here's the same thing with generic variables:
[a b -> b a] -- [swap]
[a b -> b a] [c d -> d c] -- dup -- note the difference!
And here we can compose 'i' properly without running into the occurs
check. Again, here's the derivation:
-- initial composition
R -> R [S a b -> S b a] [V c d -> V d c]
T [T -> U ] -> U
-- unify 'V d c' and 'U'
R -> R [S a b -> S b a] [V c d -> V d c]
T [T -> V d c] -> V d c
-- unify 'V c d' and 'T'
R -> R [S a b -> S b a] [V c d -> V d c]
V c d [V c d -> V d c] -> V d c
-- unify '[S a b -> S b a]' and 'd' -- oh line wrap...
R -> R [S a b -> S b a] [V c [S a b -> S b a] -> V [S a b -> S b a] c]
V c [S a b -> S b a] [V c [S a b -> S b a] -> V [S a b -> S b a]
c] -> V [S a b -> S b a] c
-- unify 'R' and 'V c'
V c -> V c [S a b -> S b a] [V c [S a b -> S b a] -> V [S a b -> S b a] c]
V c [S a b -> S b a] [V c [S a b -> S b a] -> V [S a b -> S b a]
c] -> V [S a b -> S b a] c
-- final type
V c -> V [S a b -> S b a] c
-- or more nicely
a -> [b c -> b c] a
Right. So what I've shown is that the system without free type variables
cannot type '[swap] dup i' and the system with free type variables can.
However, neither system can type 'dup i' by itself. In order to type
'[swap] dup i', you need free type variables and you *must* compose types
left to right in order to gather the necessary constraints. Hence, the
system is not purely concatenative.
Languages like ML and Haskell work exactly the same way. For example, this
is untypeable in Haskell:
\x -> x x
However, this is fine as we're letting it know what the type of 'x' is:
let x = flip in x x
There are ways to lift such restrictions. One is equi-recursive types,
although all you tend to get out of this is are valid types that you can't
do much with (and hence the system will still not be purely
concatenative). The other is to allow rank-n polymorphism. Unfortunately,
systems with rank-n polymorphism are undecidable and require type
annotations for all higher rank functions (except perhaps rank-2 depending
on your particular system). This is something I'd like to tackle
eventually but will not be dealing with in earlier versions of the
language.
- John
john@johnnowak.com — 2008-03-08 21:31:01
> I'm one of the confused. You said your lambda code was objectively
> superior and challenged me to write concatenative code. I did, and
> then produced objective measures for my code's acceptability (function
> count, token count, linearity, and smooth left-to-right reading). You
> *apparently* responded by claiming that those somehow applied to your
> notation too because your notation could be translated to mine.
>
> If that's not what you meant, cool; but what DID you mean?
I meant that it could be reasoned about as easily as the pointfree version
as there would be a well-defined translation. That's what I meant by
saying you get the best of both worlds; the worlds were "simple
concatenative semantics" and "lexically scope variables".
> Read Baker's discussion -- he admits that this is a special case with
> "relaxed" rules. It's admittedly not "strictly" linear (his words).
I obviously have to re-read it! It's been awhile.
> Your code doesn't even meet that special case; it's nonlinear in 'f',
> which appears twice sequentially.
In the program that results from my code, all values are referenced once
(due to implicit copying). Values can be mutated without visible side
effects. No garbage collection is needed. In seems that it offers all of
the same benefits as Baker's Linear Lisp, does it not?
If it does offer the same benefits, then why is not linear? Is it because
all copying is not explicit? If that's the case, do macros make a language
non-linear because they can compile down to code that calls dup? If macros
do not make a language non-linear, then why do lambda expressions make it
non-linear if lambda expressions are just macros?
It seems to me that you're saying the addition of macros makes a language
non-linear. Perhaps Baker was simply not precise enough in his definition?
Perhaps I'm way off somehow?
- John
Don Groves — 2008-03-08 21:48:08
On Mar 8, 2008, at 19:31 ,
john@... wrote:
>> I'm one of the confused. You said your lambda code was objectively
>> superior and challenged me to write concatenative code. I did, and
>> then produced objective measures for my code's acceptability
>> (function
>> count, token count, linearity, and smooth left-to-right reading). You
>> *apparently* responded by claiming that those somehow applied to your
>> notation too because your notation could be translated to mine.
>>
>> If that's not what you meant, cool; but what DID you mean?
>
> I meant that it could be reasoned about as easily as the pointfree
> version
> as there would be a well-defined translation. That's what I meant by
> saying you get the best of both worlds; the worlds were "simple
> concatenative semantics" and "lexically scope variables".
>
>> Read Baker's discussion -- he admits that this is a special case with
>> "relaxed" rules. It's admittedly not "strictly" linear (his words).
>
> I obviously have to re-read it! It's been awhile.
>
>> Your code doesn't even meet that special case; it's nonlinear in 'f',
>> which appears twice sequentially.
>
> In the program that results from my code, all values are referenced
> once
> (due to implicit copying). Values can be mutated without visible side
> effects. No garbage collection is needed. In seems that it offers
> all of
> the same benefits as Baker's Linear Lisp, does it not?
>
> If it does offer the same benefits, then why is not linear? Is it
> because
> all copying is not explicit? If that's the case, do macros make a
> language
> non-linear because they can compile down to code that calls dup? If
> macros
> do not make a language non-linear, then why do lambda expressions
> make it
> non-linear if lambda expressions are just macros?
My version of dup makes an explicit copy automatically. Does that
solve the problem?
--
don
> It seems to me that you're saying the addition of macros makes a
> language
> non-linear. Perhaps Baker was simply not precise enough in his
> definition?
> Perhaps I'm way off somehow?
>
> - John
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
john@johnnowak.com — 2008-03-08 21:56:54
> My version of dup makes an explicit copy automatically. Does that
> solve the problem?
Bah. We need to get on IRC. There is a #fifth channel on freenode by the
way... although I'm the only one to have ever entered it.
Anyway: What problem? My contention is that there is no problem.
(But yes, dup must make a deep copy immediately.)
- John
Manfred Von Thun — 2008-03-11 07:58:22
On 5/3/08 8:04 PM, "John Nowak" <
john@...> wrote
>
>
> I've had some thoughts recently on syntactic additions to
> concatenative languages that seem potentially quite useful.
> ...
> I. Lambda Expressions
>
> Assuming functions have the syntax '[<body>]', it seems useful to
> introduce the syntax '[<bindings> -> <body>], where bindings are
> ordered with the top of the stack towards the right as is familiar.
> For example, the following two functions are equivalent:
>
> foo :: -> [a b -> b a a]
> foo = [swap dup]
> foo = [a b -> b a a]
>
That is exactly the conclusion I came to when playing with a Joy in Prolog,
PJoy
Here are swap, +,your foo and stack in this notation (with help from
Prolog¹s
way of allowing simple modification of its native syntax:
swap turns [A,B|R] into [B,A|R].
+ turns [A,B|R] into [C|R] :- C is A+B.
foo turns [B,A|R] into [A,A<B|R].
stack turns S into [S|S].
These are not documentation, but the implementation!
R means the rest (of the Joy stack), the vertical bar is Prolog notation.
The last one, for stack, is an example that would be difficult
in the proposed lambda notations I have seen.
>
Pattern matching, which is one of Prolog¹s strengths,
is also useful when defining new operators in terms of
several others. The output stack from one operator has
to match the input stack of the next operator, and in
a crude compiler (from Joy to Prolog) which I write, Prolog did all
the checking before I even noticed that it was doing that.
>
>
> II. Local Function Variables
>
> If you permit lambdas, it makes sense to offer a simple syntax for
> declaring functions with named variables. This is similar to how
> Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo
> (lambda (<bindings>) <body>))'. The declaration syntax proposed here
> mimics use. In particular, the name of the function being defined
> occurs *after* the arguments.
>
Indeed. They are useful when things get messy, such as the annoying
quadratic formula. With ³local variables² in Pjoy it can be defined rather
intelligibly. I¹ll have to bring the example from my home computer.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2008-03-19 02:17:03
On 11/3/08 6:58 PM, "Manfred Von Thun" <
m.vonthun@...> wrote:
>
> On 5/3/08 8:04 PM, "John Nowak" <john@...
> <mailto:john%40johnnowak.com> wrote
>
> ...
>> > II. Local Function Variables
>> >
>> > If you permit lambdas, it makes sense to offer a simple syntax for
>> > declaring functions with named variables. This is similar to how
>> > Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo
>> > (lambda (<bindings>) <body>))'. The declaration syntax proposed here
>> > mimics use. In particular, the name of the function being defined
>> > occurs *after* the arguments.
>> >
> Indeed. They are useful when things get messy, such as the annoying
> quadratic formula. With ³local variables² in Pjoy it can be defined rather
> intelligibly. I¹ll have to bring the example from my home computer.
>
Here it is, copied to paper, ported by car, sent as mail:
A, B, C are the three input variables, R is the rest of the stack.
P and Q are the output variables, the positive and negative roots.
Every datum on the stack is typed as shown. Two local variables
are used: Diff and Root.
quad turns [C:num, B:num, A:num | R] into [[P:num,N:num] list | R] :-
> Diff is B*B -$*A*C,
> ( Diff < 0.0,
> -> write(quadratic: cannot take root of negative argument¹)
> ; Root is sqrt(Diff),
> P is (0-B+Root)/(2*A),
> N is (0-B-Root)/(2*A)
> ).
>
Looks a lot more intelligible this way with local variables than when
written in [urely concatenative style.
>
> - Manfred
>
[Non-text portions of this message have been removed]
Christopher Diggins — 2008-03-19 02:35:56
On Tue, Mar 18, 2008 at 10:17 PM, Manfred Von Thun
<
m.vonthun@...> wrote:
>
> On 11/3/08 6:58 PM, "Manfred Von Thun" <m.vonthun@...> wrote:
>
> >
> > On 5/3/08 8:04 PM, "John Nowak" <john@...
> > <mailto:john%40johnnowak.com> wrote
> >
> > ...
>
> >> > II. Local Function Variables
> >> >
> >> > If you permit lambdas, it makes sense to offer a simple syntax for
> >> > declaring functions with named variables. This is similar to how
> >> > Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo
> >> > (lambda (<bindings>) <body>))'. The declaration syntax proposed here
> >> > mimics use. In particular, the name of the function being defined
> >> > occurs *after* the arguments.
> >> >
> > Indeed. They are useful when things get messy, such as the annoying
> > quadratic formula. With ³local variables² in Pjoy it can be defined rather
> > intelligibly. I¹ll have to bring the example from my home computer.
> >
> Here it is, copied to paper, ported by car, sent as mail:
>
> A, B, C are the three input variables, R is the rest of the stack.
> P and Q are the output variables, the positive and negative roots.
> Every datum on the stack is typed as shown. Two local variables
> are used: Diff and Root.
>
> quad turns [C:num, B:num, A:num | R] into [[P:num,N:num] list | R] :-
> > Diff is B*B -$*A*C,
> > ( Diff < 0.0,
> > -> write(Œquadratic: cannot take root of negative argument¹)
> > ; Root is sqrt(Diff),
> > P is (0-B+Root)/(2*A),
> > N is (0-B-Root)/(2*A)
> > ).
> >
> Looks a lot more intelligible this way with local variables than when
> written in [urely concatenative style.
I agree. I think it is worth mentioning that Slava made some
interesting points on the subject of quadratics in a concatenative
style:
http://factor-language.blogspot.com/2007/03/evaluating-quadratic-polynomial.html
When you see ">r ... r>" in Factor I believe you can just replace it
with "[...] dip".
- Christopher
John Nowak — 2008-03-19 07:06:42
On Mar 18, 2008, at 10:17 PM, Manfred Von Thun wrote:
> quad turns [C:num, B:num, A:num | R] into [[P:num,N:num] list | R] :-
> Diff is B*B -$*A*C,
> ( Diff < 0.0,
> -> write(‘quadratic: cannot take root of negative argument’)
> ; Root is sqrt(Diff),
> P is (0-B+Root)/(2*A),
> N is (0-B-Root)/(2*A)
> ).
Here's another version of the above with a syntax more suited to a
concatenative language:
quad a b c = p n
where 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 /
Ah, syntax is fun.
- John
John Nowak — 2008-03-19 07:29:55
On Mar 19, 2008, at 3:06 AM, John Nowak wrote:
> Here's another version of the above with a syntax more suited to a
> concatenative language:
>
> quad a b c = p n
> where 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 /
Or in a manner requiring less heroics for people with more taste and
sophisticated structural editors:
(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))
Unlike Manfred's original example, these return 'p' and 'n' on the
stack directly. '[...]' is just sugar for '(lambda () ...)', where
'lambda' expands to point-free code if variables are introduced.
Yes, I want a typed Scheme where functions can easily produce (and
subsequently consume) multiple values. Is that so wrong?
- John
Chris Double — 2008-03-19 07:32:37
On Wed, Mar 19, 2008 at 8:29 PM, John Nowak <
john@...> wrote:
> Yes, I want a typed Scheme where functions can easily produce (and
> subsequently consume) multiple values. Is that so wrong?
With pattern matching and destructuring assignment too please :-)
Chris
Don Groves — 2008-03-19 07:43:47
And a compiler that will generate code for any platform, including
the JVM, Parrot, etc...
--
don
On Mar 19, 2008, at 19:32 , Chris Double wrote:
> On Wed, Mar 19, 2008 at 8:29 PM, John Nowak <john@...>
> wrote:
>> Yes, I want a typed Scheme where functions can easily produce (and
>> subsequently consume) multiple values. Is that so wrong?
>
> With pattern matching and destructuring assignment too please :-)
>
> Chris
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>
Manfred Von Thun — 2008-03-19 08:04:57
On 7/3/08 9:00 AM, "Stevan Apter" <
sa@...> wrote:
> ack. it's been so long since i looked at this stuff that i'd
> forgotten that 'map' in f/g and XY is an extension of the standard
> definition: given a list of k-length lists, it applies a n-ary
> function n>=k to each element of the list. so e.g.
>
> [[1 2][3 4][5 6]][+]map -> [3 7 11]
>
Isn¹t what you want just
[[1 2] [3 4] [5 6] [sum] map => [3 7 11]
where it is not even required that the sublists are of the same
length. Or did I miss something?
> - Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2008-03-19 08:43:49
On 8/3/08 2:40 AM, "Christopher Diggins" <
cdiggins@...> wrote:
> On Fri, Mar 7, 2008 at 10:11 AM, Stevan Apter <sa@...
> <mailto:sa%40nsl.com> > wrote:
>
>> > ----- Original Message -----
>> > From: "John Nowak" <john@... <mailto:john%40johnnowak.com> >
>> > To: <concatenative@yahoogroups.com <mailto:concatenative%40yahoogroups.com>
>
>
> ....
>>> > > Ah, I think maybe there's some confusion here over what we mean by
>>> > > "list". (Yes, really!) In Joy, lists, stacks, and functions are all
>>> > > magically the same thing. I assume it's similar in XY as well. In
>>> > > Fifth, lists, stacks, and functions are all different things. This is
>>> > > just one more example of the endless complication that types introduce.
>
In Joy, stacks, list, and quotations are the same thing. A mathematician
would
tell you that a set is a truth function, giving truth for its members and
falsity
for everything else. They would also tell you that a sequence
(list,vector,array...)
is a function from an initial portion of the positive natural numbers (1 2 3
...)
to its members, and undefined beyond that (all this is done by the indexing
function, of course). But function can have all sorts of things as
argument(s)
and give all sorts of things as value. But don¹t confuse functions with
programs
that compute them. [My favourite example: there is just one doubling
function,
and there many programs that compute it: 1: (add the argument to itself),
2: (multiply the argument by 2), 3: (leftshift its binary representation by
1)
4: (lots more)] So a quotation in Joy is NOT a function, it is a program
to compute a function.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2008-03-19 10:05:51
On 19/3/08 6:06 PM, "John Nowak" <
john@...> wrote:
>
> On Mar 18, 2008, at 10:17 PM, Manfred Von Thun wrote:
>
>> quad turns [C:num, B:num, A:num | R] into [[P:num,N:num] list | R] :-
>> Diff is B*B -$*A*C,
>> ( Diff < 0.0,
>> -> write(quadratic: cannot take root of negative argument¹)
>> ; Root is sqrt(Diff),
>> P is (0-B+Root)/(2*A),
>> N is (0-B-Root)/(2*A)
>> ).
>
> Here's another version of the above with a syntax more suited to a
> concatenative language:
>
> quad a b c = p n
> where 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 /
>
Yes, I entirely agree. What I gave was the Prolog program, and if
someone implementing a concatenative language has to choose
a notation for arithmetic and other types, our form would be best.
But to get the unification for the variables in the input and the
output stacks, you have to write a little Prolog and that is not so easy.
So I just used an excellent existing Prolog, SWI-prolog.
[Non-text portions of this message have been removed]
Christopher Diggins — 2008-03-19 14:33:48
> 4: (lots more)] So a quotation in Joy is NOT a function, it is a program
> to compute a function.
I view a quotation to be a function that takes any stack and returns a
copy of that stack with a function on top.
I don't believe that this is an incorrect model.
- Christopher
John Cowan — 2008-03-19 17:31:25
Manfred Von Thun scripsit:
> 4: (lots more)] So a quotation in Joy is NOT a function, it is a program
> to compute a function.
Scheme makes essentially the same distinction between a procedure (a
piece of Scheme code), a closure (a run-time object binding a procedure
to a lexical environment), and a function (a mathematical relation).
OTOH, the closely related Common Lisp uses "function" for all three.
--
They do not preach John Cowan
that their God will rouse them
cowan@...
A little before the nuts work loose.
http://www.ccil.org/~cowan
They do not teach
that His Pity allows them --Rudyard Kipling,
to drop their job when they damn-well choose. "The Sons of Martha"
Christopher Diggins — 2008-03-19 17:36:04
> Scheme makes essentially the same distinction between a procedure (a
> piece of Scheme code), a closure (a run-time object binding a procedure
> to a lexical environment), and a function (a mathematical relation).
> OTOH, the closely related Common Lisp uses "function" for all three.
While the language description makes this distinction, but AFIAK the
run-time semantics of Scheme do not make a distinction between these
kinds of values.
In other words you can't write code (in R5RS) that distinguishes
whether a given value is a closure, a function or a procedure.
- Christopher
John Cowan — 2008-03-19 18:08:49
Christopher Diggins scripsit:
> In other words you can't write code (in R5RS) that distinguishes
> whether a given value is a closure, a function or a procedure.
Closures satisfy PROCEDURE?, procedures satisfy PAIR? (and more specific
predicates). Functions are abstracta, and don't have representations
in Scheme.
--
I now introduce Professor Smullyan, John Cowan
who will prove to you that either
cowan@...
he doesn't exist or you don't exist,
http://www.ccil.org/~cowan
but you won't know which. --Melvin Fitting
Christopher Diggins — 2008-03-19 18:27:39
> > In other words you can't write code (in R5RS) that distinguishes
> > whether a given value is a closure, a function or a procedure.
>
> Closures satisfy PROCEDURE?, procedures satisfy PAIR? (and more specific
> predicates). Functions are abstracta, and don't have representations
> in Scheme.
That is interesting. I can't find in the specification
(
http://schemers.org/Documents/Standards/R5RS/r5rs.pdf) that closures
must not satisfy "PAIR?". Can you point it out?
- Christopher
John Cowan — 2008-03-19 19:09:55
Christopher Diggins scripsit:
> > > In other words you can't write code (in R5RS) that distinguishes
> > > whether a given value is a closure, a function or a procedure.
> >
> > Closures satisfy PROCEDURE?, procedures satisfy PAIR? (and more specific
> > predicates). Functions are abstracta, and don't have representations
> > in Scheme.
>
> That is interesting. I can't find in the specification
> (http://schemers.org/Documents/Standards/R5RS/r5rs.pdf) that closures
> must not satisfy "PAIR?". Can you point it out?
3.2 says that PROCEDURE? and PAIR? are disjoint. It's true that in R5RS
"procedure" is used instead of "closure", but in talking about Scheme
I usually hear "closure" for the object, and "procedure" for the text.
--
A mosquito cried out in his pain, John Cowan
"A chemist has poisoned my brain!"
http://www.ccil.org/~cowan
The cause of his sorrow
cowan@...
Was para-dichloro-
Diphenyltrichloroethane. (aka DDT)
Christopher Diggins — 2008-03-19 19:17:41
On Wed, Mar 19, 2008 at 3:09 PM, John Cowan <
cowan@...> wrote:
> Christopher Diggins scripsit:
> > > > In other words you can't write code (in R5RS) that distinguishes
> > > > whether a given value is a closure, a function or a procedure.
> > >
> > > Closures satisfy PROCEDURE?, procedures satisfy PAIR? (and more specific
> > > predicates). Functions are abstracta, and don't have representations
> > > in Scheme.
> >
> > That is interesting. I can't find in the specification
> > (http://schemers.org/Documents/Standards/R5RS/r5rs.pdf) that closures
> > must not satisfy "PAIR?". Can you point it out?
>
> 3.2 says that PROCEDURE? and PAIR? are disjoint. It's true that in R5RS
> "procedure" is used instead of "closure", but in talking about Scheme
> I usually hear "closure" for the object, and "procedure" for the text.
And 4.1.4 is says that a lambda expression evaluates to a procedure.
- Christopher