Re: [stack] sweetening concatenative syntax

John Nowak <[email protected]> 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