Lambda the Ultimate

It's an incredibly good idea if you want type checking (with some notion of checking code without evaluating it) to make sense. The code being quoted retains its own syntax and notation still, so I don't see the problem there - whereas I really don't trust a partial evaluation phase.

Additionally, I might well want to perform IO in one of the stages of computation. That'll well and truly trash the purity.

I was going to suggest something similar [i.e. achieving types via partial evaluation] in response to your previous post, but didn't get around to it. There's been academic work on this, such as Types as Abstract Interpretation (previously mentioned here). I've seen other papers along similar lines, but I'd have to dig for them.

However, I think that as far as a special syntax for metaprogramming goes, there's more to it than you've mentioned. Good compilers for functional languages already do quite a bit of partial evaluation, but that doesn't necessarily deal with the case in which code manipulates other code. Usually, when new constructs are introduced to support metaprogramming, it's for this purpose. It's possible, though, that in the concatenative languages like Joy and Cat, that the line between ordinary programs and metaprograms is sufficiently blurred that you might not need to make any special distinctions. If so, I'd be interested to see the results of such a design.

[Edit: ...but to address the metaprogramming issue specifically, rather than the type issue, special syntax would help to statically distinguish between code that's just manipulating e.g. an ordinary list, vs. code that's manipulating other code. So I suspect that there's no getting away from special syntax for metaprogramming in general.]

Epigram does incremental typing, which is partial evaluation from my viewpoint. Since types are first class citizens in Epigram, and incremental typing allows you to inductively define many interesting things...

I agree with your hypothesis, it reminds me of FrankA's idea that dynamic or static type checking as the same thing, with static meaning 'available as a library'.

I'm glad someone pasted something on Multi-Stage Programming, as I'm futzing around with implementing a form of it under Scheme. I'm experimenting to find out if it's feasible to implement Multi-Stage evaluation via the addition of a construct to eval, which will add an additional stage either before or after (or possibly both, I don't yet know which would be best) the standard Macro-Expansion Phase, in which another round of evaluation of source code would take place.

I think that by making a construct, lets call it "par-eval", which you can use to wrap code which would benefit from additional stages of evaluation, and then reevaluating it again, you could enable some very interesting behaviors.

A trivial example is the precomputation of constants:

(define x (par-eval (+ 2 3))

which would be the same as writing:

(define x 5)


A non-trivial example would be the calculation of a non-trivial invariant prior to run-time and deployment (assuming that you can compile the resulting code after the first stages are complete), such as a Regex generator. Let's say that your final program needs to read a particular file format (such as CSV), and for convenience you'd like to read it the quick and dirty way using regular-expressions. Then using this technique, the FSM needed to grok your format can be pre-generated prior to evaluation-time so that there would be no real performance hit for using a "convenience technique" instead of a more efficient--but less convenient technique.

I'm still new to Multi-Stage programming, so I'd appreciate any feedback that you have: Does the above sound like a good or usable idea? Has it already been done (in full or in part) elsewhere?

Edit: Fixed typo.

If you consider run-time code generation as some kind of metaprogramming ( instead of macro- ), you need no extra syntax.

For example with CodeBricks you can write a run-time regexp compiler.

My own little RTCG thingy relies on run-time VM code transformations while hiding bytecode details : Comment.
With futures, it is even possible to delay the code generation/transformation until the target function is actually invoked. "Just-In-Time"...

Explicitly staged languages are a compromise, not a desirable goal.

Even the designers of MetaOcaml agree: the staging is useful as and experimental tool to learn more about how to get rid of it.

What is required is a partial evaluator, in which unknowns are progressively bound, yielding a more and more specialised program. When finally everthing is bound, you have an irreducible term, which is your final result.

Staging requires strict level boundaries and sequencing of the binding information in stages, which has two advantages: it is possible to specify clearly what the inputs for each stage are, and it is possible to actually write a partial evaluator which handles all the intermediate stages the same way (the initial and final processing is likely to be rather specialised).

In turn, the ability to multi-stage with explicit program guidance significantly simplifies the staging recursion. On the other hand a 'generalised partial evaluator' is a very open ended thing, and any system must not only be able to bind more or less arbitrary inputs, it also has to make it clear to the programmer how to proceed.

Conceptually, you could examine the current terms to see which ones might become reducible if more data were supplied, supply it, reduce the terms, then look for another term which could be simplified.

There's a big gap between such an interactive, experimental, evaluation strategy and a programming language for which you can easily predict what data to supply, without examining the internal state.