A large part of what constitutes lisp-style metaprogramming is macros, which are definitely a compile-time feature.

That's a very valid point. So I think we have these two types of metaprogramming, the runtime type and the compile time type. The latter is compatible with static typing but the former clearly is not.

If the compiler is part of the runtime (i.e. an interpreter that compiles expressions in order to evaluate them), and then the type checker is part of the compiler, even eval should be able to throw type errors. What, then, is the problem?

The problem is that the type error occurs at runtime, which is exactly what static type checking is supposed to prevent in the first place.

It depends on what you mean by "runtime." If you're creating a new datatype, is that really "at runtime," or are you just talking to the compiler interactively?

To put it another way: metaprogramming might have effects at runtime, but not the kind of effects that change depending on what the runtime does. Metaprogramming should be deterministic for your program to be considered to be "in production."

It's not a statically typed language like Haskell anymore?

you might want to google "staged programming" - it's what strongly typed languages do to get metaprogramming.

(edit: afaik it doesn't allow the full "recursive manipulation" you describe, but it does let you generate code with code)

Thank you so much! I've had informal ideas quite like this from working on my "HTML rewriting system" part of my (unreleased) Common Lisp web framework. I now have a very specific search term to acquire more formalized knowledge which should speed up some future developments a lot because I won't have to independently come up with solutions to as many of the problems now.

heh. no problem. if you're interested in this kind of thing check out http://lambda-the-ultimate.com from time to time. just skimming the conversations can keep you up to date...

If I create syntax with a program (code with code) is that metaprogramming? Doesn't c++ or any text generating code already do this?

Maybe it's not "native" and I have to run system level calls to force compiles and execution of created code.

Almost all programs do metaprogramming (interpreted code, scala on the jvm, etc).

What's the differentiatior for Lisps Metaprogramming (self contained languange structures?).

I'm pretty interested in simplification of programmer interfaces on iteratively more functional (but perhaps more complex) underbellies. I will certainly investigate.

My definition of metaprogramming is writing a program that manipulates itself. I'm not sure I would call any arbitrary code generator metaprogramming as this would cause the "self" in my definition suffer a severe identity crisis :-)

But yes, C++ templates as well as Lisp macros are compile time metaprogramming. All languages that have eval and/or allow function/method bindings to be replaced at runtime allow runtime metaprogramming.

Since static typing guarantees certain invariants it cannot be compatible with a program that violates those invariants at runtime. You could still decide to consider it metaprogramming when the program manipulates itself only within the limits of those guarantees, but when you look at what real world runtime metaprogramming is being used for (for instance in Rails) you will realise that these things (e.g method_missing) would not be possible within the limits of a statically typed language.

[edit] Lisp makes both compile time and runtime metaprogramming exceptionally easy due to its homoiconic nature.

It's certainly possible for a typed language like ML or Haskell to support metaprogramming. As other have noted, Haskell has Template Haskell. However, systems like MetaML and MetaOCaml support metaprogramming and give much stronger typing guarantees than Template Haskell. See http://www.metaocaml.org/examples/ for inspiration.

Sure, but there are theoretical limits to what runtime metprogramming can do whilst upholding the guarantees that a static type system provides.

For instance, in order to check that a particular function call conforms to the function signature, the function signature must at least exist. Type checking a call to a function for which not even the signature exists anwhere within the system is impossible.

The post above doesn't mention compile time type checking. Are you implying that to support one of the features he asks for that it is required?

One of Haskell's defining features is a very expressive and powerful static type system, so yeah, compile-time type inference/checking was pretty heavily implied by "similar to Haskell".

And yes, the fact that I was essentially asking for a language with both static typing and runtime self-modification was the reason for the tongue-in-cheek "is that so much to ask". Might as well ask for a program that can compile any legal perl program [0].

That said, I suspect there's a lot that could be done to allow certain subsets of metaprogramming techniques in a static-typed language; some sort of crazy meta-type system that lets the compiler prove that something will only produce code with a particular polymorphic type, maybe? I don't know.

[0] EDIT: My bad, it's actually parsing perl that's impossible, cf. http://www.perlmonks.org/?node_id=663393

Yes. A lot of the meta-programming is actually programming over the structure. For example, given a Java class, you could generate database code. In Java, this relies heavily on introspection, but you if you're interested in doing this in a type-safe way then you could look at Generic Programming (in Haskell).

Also, you can generate code (at runtime) which is type-safe, compile the code, etc. Everything you ask for is possible in Haskell, however, it is definitely more complicated than in Lisp.

Compiling code at runtime may improve performance, but it doesn't give the kind of guarantees that static typing gives you.

Static type checking proves that certain invariants hold at runtime and hence that certain defects are not possible. If a program can manipulate itself at runtime in arbitrary ways (not just reflect on itself in a read-only fashion), those proofs become invalid.

Yes I do imply that. camccann puts it very well, and as I said, what would Haskell be without its static type system?

There would still remain some cool parts. Like the syntax. And you could do something similar to typeclasses with duck typing.