Re: [stack] possibilities for macros in a typed language

On Fri, Feb 22, 2008 at 3:53 AM, John Nowak <[email protected]> wrote:
> Recently, I've been thinking about what sort of macro system might be
> suitable for a typed concatenative language. For this discussion, I'll
> assume a language like Cat minus any form of locals/variables. I'll
> call this hypothetical language 'Kitten' from this point on.

I had been calling Cat + locals Kitten at one point, but this is a
minor detail.

> Adding macros to Kitten seems fairly easy at first as the syntax is
> easily representable as a list and there are no variables to get in
> the way. Given that adding macros is fairly easy, it seems worth doing
> if they'd be truly useful.
>
> But are they?

Yes.

> In Lisp, macros are most commonly used for two reasons.
> The first is a lack of a concise syntax for anonymous functions, but
> this isn't an issue in Kitten. The second is dealing with bindings and
> binding constructs (SET!, etc), but this also isn't an issue. There
> are other uses of macros, but these two probably comprise 90% of the
> use cases.
>
> What other uses then might macros have in Kitten? One use I've come up
> with is allowing a way to write constructs that would otherwise be un-
> typeable.
>
> For an example, the m combinator 'dup i' cannot be assigned
> a type

Depends on your type system. In Cat "dup apply" has the type "(A (A (B
-> C) -> D) -> D)"

> for the same reason that '\x -> x x' cannot be assigned a type
> in Haskell; it requires the construction of an infinite type. (Cat's
> version of 'i' is called 'apply' I believe.)

The problem with Haskell is the lack of inference for inner forall
polymorphism.

> Even though 'dup i' isn't typeable, expressions like '[swap] [swap] i'
> and '[dup] [dup] i' are. Accordingly, we could define a macro like
> '[$A] m => [$A] [$A] i' that would work with quote literals. Such a
> macro is writable in a simple declarative system similar to Diggins's
> MetaCat (http://www.cat-language.com/metacat.html), although I believe
> MetaCat isn't currently usable for such things.

Currently the only thing preventing this is that "m" has to already be
predefined, a MetaCat macro can't define new instructions. I think I
may abolish that rule however.

> Another deficiency of the type system is a lack of number
> parameterized types. As such, you can't write a function like 'ndup'
> that duplicates the top N values on the stack. With an appropriate
> macro system however, you could expand '3 ndup' to a typeable
> construct. You would need something more powerful than MetaCat to do
> so however.

That is true, but it would be a very minor hack to improve the MetaCat
system to fix this. This is a very interesting idea!
The lack of parameterized types in Cat is a huge thorn in its paw.
Using macros we can side-step the issue by generating code.

The only problem I forsee is that programmers might type things like
"250 ndup" which would possibly bring the type-system to its knees,
because of the inherent complexity of typing massive stacks. The other
solution is to introduce fixed size type vectors.

> Optimization is another use of macros (as MetaCat shows). Slava Pestov
> recently walked me through some of the more interesting use cases of
> macros for optimization in Factor as well; 'case' is a good example.
>
> There are of course additional, more complex uses. One example would
> be a macro that translates code that uses locals to code that's
> pointfree. Another might be pattern matching. It's not clear if there
> are sufficiently many of such use cases to warrant the addition of a
> macro system as opposed to simply adding a few additional core
> syntactic constructs.
>
> There are obviously downsides to macros as well. Firstly, you
> sacrifice something in terms of concatenativity. For example, 'A B C
> D' might not be decomposable into 'A B' and 'C D' if macros are
> involved.

Type-checking is usually done after macro expansion.

> You also lose something in terms of consistency as
> constructors like 'm' would only be usable with function literals and
> not functions passed at runtime.
>
> Finally, you lose the "everything is
> a function" aspect of Kitten. In Kitten, even the literal '3' is
> really a function with the type 'A -> A int'. Similarly, '[dup]' is a
> function with the type 'A -> A (B c -> B c c)'.
> Macros eliminate this property,
>
> Macros are a huge design space. It seems to me that there are
> essentially four possibilities for such a system in Kitten:
>
> 1. Offer a MetaCat-like system, perhaps with some additional
> expressivity. This covers a fair chunk of the optimization cases very
> simply and it's declarative nature means that you don't need to write
> macros that cooperate with the type system. (Of course the result of
> the rewriting needs to be typeable.) It also allows for 'm' and
> perhaps other more difficult combinators (condnestrec?) to be
> integrated, at least when dealing with literals.
>
> 2. Offer a somewhat Lisp-like system where macros are pure functions
> of the type '[parse-entity] -> [parse-entity]'. This allows more
> flexibility than the MetaCat system, although pointfree syntactic
> manipulation is likely to be more complicated in practice. It is also
> likely to be a good deal more verbose as you'll either need to be
> deconstructing and reconstructing parse-entity sums or casting into
> and out of some universal type.
>
> 3. Take the Factor approach and offer proper parse words and
> everything derivable from them. Again, this seems like even more
> flexibility at the cost of even more complexity. I'm not too
> interested in this approach for a language like Kitten; it makes a lot
> of sense for Factor though.
>
> 4. Offer no macro system whatsoever as the possibilities aren't worth
> the downsides. Something like MetaCat would be integrated directly
> into the system for purposes of optimization only and wouldn't be
> exposed to the user.
>
> Of course, you could always just use Joy and get runtime macros for
> free!

If it is available at runtime then "macro" is the wrong term. You are
then describing a reflection facility.

> Many thanks if you've managed to keep reading this long. If anyone has
> thoughts on what an ideal macro system for a Kitten-like language
> might be, or even if such a system is useful, they'd be much
> appreciated.
>
> - John

Cheers,
Christopher