Re: [stack] sweetening concatenative syntax

Don Groves <[email protected]> Wed, 5 Mar 2008 17:34:28 -0800
Newsgroups	gmane.comp.lang.concatenative
Message-ID	<[email protected]>
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
>
>
>
>