## Educational Pearl: Automata as Macros

Shriram Krishnamurthi's classic macro automaton example, well known from his LL1 presentation, is now written up as an educational pearl for JFP.

As you may recall, the example shows how to use Scheme macros to create an an automata DSL, and concentrates on the importance of proper tail-calls for achieving the desired semantics.

## Comment viewing options

### the why of macros

I'm really happy to see this written up as a journal paper. There are so many important ideas in there. He addresses two particularly misunderstood conepts: macros and proper tail recursion.

I want to call attention to his characterization of the important applications of macros, because these really are the "why" of macros:

1. providing cosmetics
2. introducing binding constructs
3. implementing "control operators," i.e., ones that alter the order of evaluation
4. defining data languages

Almost all the useful macros I've ever seen fall into these categories. Shriram's paper neatly demonstrates all four.

### Hmm...

...you can get 2 and 3 by providing a little syntactic sugar for arbitrary monads, like Haskell's do-notation does. This lets you add binding constructs and control evaluation orders. If you integrate that with the pattern-matching syntax, then you get 4 as well, and it seems like most of the motivation for macros would go away.

This is very interesting....

### Hear, hear!

it seems like most of the motivation for macros would go away.

I like the way you think, Neel. ;-)

My favourite LtU thread was related to this.

If the Haskell/Smalltalk crowd shake your faith in Scheme macros you might still find solace with Common Lisp. Cop this for conciseness of expression of a fully compiled string-matching automaton using no dirty tricks:

(scan "c(a|d)+r" input)


### Re: Hmm...

...you can get 2 and 3 by providing a little syntactic sugar for arbitrary monads, like Haskell's do-notation does.

Only if you're willing to restrict yourself to the kinds of extensions that can be expressed as monads. Further, Haskell's monads are problematic as a lightweight syntax, since you end up having to name the results of so many intermediate computations.

This lets you add binding constructs and control evaluation orders.

Evaluation orders, yes, but binding constructs? I don't see it. But it does not, for example, allow you to abstract over second-class elements of a language, such as definitions.

### Nice but...

You would have to be an even bigger meta-programming curmudgeon than I am to not like this paper. It is well-written, clear and interesting, especially for Schemers and PLTers.

But I am still a meta-programming curmudgeon, so I can't really let it go without a critique. ;-)

Note that the example has the following properties:

• The DSL syntax is simple and self-contained.
• The example accepted languages are simple, with few states and transition labels.
• The transition labels are themselves simple tokens.
• The results of the automata are simple booleans.

Consider the situation if:

• The DSL syntax was more complex, and broken up into separate elements that all had to interact with "normal" Scheme.
• The accepted language was complex, with a large number of states and transition labels.
• The transition labels were more complex, such as regex elements.
• The automaton was a transducer with a more complex output or side-effects.

In these latter cases, I think the benefits of simplicity ,elegance and performance relative to a non-"meta" solution would be greatly diminished.

Food for thought for those who might start demanding macros everywhere after reading this. ;-)

Sir,
Does 'macros everywhere' contradict the 'Domain-Specific' in DSL, or am I missing your point?
Best,
Chris

### How domain-specific?

Sir

Geez, I'm a curmudgeon, but I'm not THAT old. ;-)

Does 'macros everywhere' contradict the 'Domain-Specific' in DSL, or am I missing your point?

I think we may want to distinguish segregated source DSLs and domain-specific extensions to a language.

If you want to build a DSL for some reason, and your are going to segregate it into its own source files/blocks/etc. or it is only going to interact with your host language through a limited abstract interface, you're not likely to run into problems.

The situation described in the paper is not this though. It describes extending the host language and using the "DSL" as though it were a native part of the host. As Krishnamurthi says explicitly, we are really talking about Scheme+.

My "macros everywhere" comment is a tongue-in-cheek quip intended to disuade someone from reading this paper, saying "Wow, macros are cool!", and starting another "Why would anyone want to program in a language without macros" thread. ;-)

### Macro-free diets?

starting another "Why would anyone want to program in a language without macros" thread. ;-)

Which languages successfully avoid macros in any form? I'm reminded of papers like Macros and Preprocessing in Haskell, which points out that "existing large Haskell systems make extensive use of the C preprocessor, CPP" and that "we need some form of Haskell preprocessor and macro system".

I'm asking this question in furtherance of my point that when you consider the entire development cycle, and not just the final compile/run stage, we all do metaprogramming anyway, we just differ in the ways in which we either acknowledge, conceal or deny that fact.

### A liquid analogy

I'm asking this question in furtherance of my point that when you consider the entire development cycle, and not just the final compile/run stage, we all do metaprogramming anyway, we just differ in the ways in which we either acknowledge, conceal or deny that fact.

Unless one has religious, health or other reasons not to, you could say we all drink alcohol.

Some of us have a glass with dinner, some of us drink ourselves under the table every night.

Some of us drink as a small, pleasant addition to life, some of us reach for the bottle as soon as there is stress.

Some of us conceal our drinking or are in denial about it, some of us are very aware and conscientious about it, making sure we don't do more of it than is really an addition to the quality of our life.

But what does it matter which way you go?... we all drink alcohol.

### But what does it matter whi

But what does it matter which way you go?... we all drink alcohol.

This makes my point. It certainly does matter which way you go: you're much better off acknowledging what you're doing, and looking for systematic ways to deal with it, rather than pretending you're not doing it and objecting to systematic approaches to dealing with it.

### On the wagon

you're much better off acknowledging what you're doing, and looking for systematic ways to deal with it, rather than pretending you're not doing it and objecting to systematic approaches to dealing with it.

I'm not sure that this follows from my "don't use more than you have to" homily. You seem to be saying, if something might be bad, and you are going to do it anyway, institutionalize it in your language.

This goes against the dictum "If you want to encourage a practice, make it easy; if you want to discourage it, make it hard."

I think we also assume different thresholds for "we do it anyway."
I know that in the Java world frameworks with XML configs, code generation, reflection and the like seem de rigueur, but I have worked on large Java projects where I could have successfully avoided all of these if it were not for the ingrained notion that these things are required ways of "doing Java".

In my experience, meta-programming can be almost entirely eliminated with good design. Most people don't try that hard though because of the "cool factor" or of the seeming path of least resistence of "meta". (If it wasn't good, they wouldn't put it in the language, right?)

If you use it very rarely, as I'm suggesting, I'm not sure that simple ad hoc solutions that address exactly and only the given problem are such a bad thing.

### Metaprogramming as higher-order programming

I think one interesting problem is that there is a programming culture (or at least several highly-visible programming subcultures) that views metaprogramming (and programmers who indulge in it regularly) as somehow better than mere programming. It certainly is an activity that one must be highly proficient and experienced to do well; unfortunately neither skill nor experience (only ambition!) are required to do it poorly.

We all remember Dick Sites' famous quote:

I'd rather write programs to write programs than write programs

I agree, if and when the metaprogramming approach produces an increase in productivity. In many cases it does; in many cases it doesn't. There are many stumbling blocks to good metaprogramming, which often get ignored by programmers who see metaprogramming as a fast-track to wizardhood.

That said--many instances of metaprogramming are not undertaken in order to pad the ego (or resume) of the programmers responsible; but instead as a form of greenspunning--working around limitations in the language of implementation. (This is especially true when the programming language in question shares the name of a large island in Indonesia).

### Institutionalizing

You seem to be saying, if something might be bad, and you are going to do it anyway, institutionalize it in your language.

Close. If something is good when used properly, but bad when used to excess, then you're better off institutionalizing it in the language because in that process, the good and bad ways of using it will become clearer, and the whole issue will be much more amenable to discussion.

Tool developers can benefit enormously from macros, and it makes no sense to me to tell tool developers that they can't have macros because others might abuse them. That's like telling doctors they can't prescribe drugs because patients might abuse them. Complex systems (pharmacies, pharmacists, prescriptions, laws) have been set up to control that issue; perhaps macros need something analogous in terms of development processes.

This goes against the dictum "If you want to encourage a practice, make it easy; if you want to discourage it, make it hard."
I don't believe that dictum works in situations where there are reasons to choose behaviors that go beyond whether it's easy or hard to choose them. It just leads to horrible workarounds and strange problems.
If you use it very rarely, as I'm suggesting, I'm not sure that simple ad hoc solutions that address exactly and only the given problem are such a bad thing.

That's why I asked for examples, because I really don't know what kind of systems you're thinking of, and I'd like to contemplate examples. Are we just talking about systems which are simple or focused enough that metaprogramming doesn't arise? IME, once you combine databases of some kind with user interfaces and application logic, then useful, time-saving, abstraction-improving applications of metaprogramming abound.

### DB example

IME, once you combine databases of some kind with user interfaces and application logic, then useful, time-saving, abstraction-improving applications of metaprogramming abound.

Exactly the kind of situation where people usually reach for the "meta" solution unnecessarily, IMO. (This is the kind of thing I have been doing for a living the last few years.)

My own "pattern" for handling database calls is simple and has worked quite well on large DB apps.

The SQL statement (as a string) is encapsulated in one class that also knows how to set parameters. There is a mapper class that can take the result set and populate some domain object with the data. And there is an executer class (or a couple variations) that takes the first two and executes the transaction.

The SQL statement as string is OK because it is really just a message to an external system, not unlike a URL.

Since in particular cases you generally know how you want to convert the data, the mapper is usually quite simple, and there is no need for all the generic type-converting, code generating, meta-data manipulating OR with XML config stuff everyone seems to go in for.

And that's it, really.

(The only problem is that testing is a pain, but I'm not sure that any meta-solution really solves that either.)

The only objection (other thanf from those with framework-ophilia) I can see is that someone on the team actually has to understand the database and how to write the queries. However, if no one is any good at this, what the heck are they doing building a DB app. ;-)

[small edit for clarity]

### Metaprogramming isn't just for fun!

Since in particular cases you generally know how you want to convert the data, the mapper is usually quite simple, and there is no need for all the generic type-converting, code generating, meta-data manipulating OR with XML config stuff everyone seems to go in for.

This is a great example of the kind of thing I wanted to drill down to. You're using words like "generally" and "usually", and I think you're right, "generally" and "usually" systems are simple enough to be amenable to the approach you've described, i.e. there are many systems which are that simple.

But what about when things aren't that simple? It's rather unfortunate to find that the language you're using is not only optimized for the simple case, but that the simple case is all it's capable of handling on its own, and you're forced to resort to meta-solutions to avoid burgeoning boilerplate having to be hand-coded by a cubicle farm.

I've been through that entire cycle, for much more than the last few years, going from the hand-coding of mappings, through roll-your-own persistence solutions, to using off-the-shelf solutions, and I can tell you from significant experience that the low-tech approach you've described suffers from significant problems, in general, which metaprogramming does a convincing job of solving. The benefits of metaprogramming here are simple and easy to demonstrate on real systems: reduction in lines of code (that are written and maintained by humans) that can easily reach one or two orders of magnitude, with a corresponding improvement in the tractability of large & complex applications.

People thinking of their simple database applications in which there's a single obvious mapping from database to objects may balk at the idea that you can write 100 times more code just because you don't automate the mapping. But in enterprise-style systems, the same database may support multiple quite different applications over a common database, each of which has its own mappings, looking at the data from potentially quite different perspectives. Hand-writing one set of mappings for one application seems acceptable, but it starts seeming a lot less acceptable when you're writing twenty or a hundred different mappings for the same few hundred tables.

Working around the limitations of a language like Java is not the only reason for wanting metaprogramming in these kinds of environments. Fundamentally, the relationships expressed in your database are mirrored by the relationships expressed in your code which are mirrored by the relationships expressed in your user interface. There's a lot of repetition and duplication there, and metaprogramming can help avoid repeating yourself over and over in different code environments.

Metaprogramming is about expressing the real, underlying meaning of the application you're developing, as independently as possible of the constraints of the programming environments you're using, and ideally, producing code in whatever set of languages you need to achieve an actual implementation.

(A simple and somewhat tangential example of this relates to your claim that "the SQL statement as string is OK". That's fine until you want to switch to a different database server. Using a framework which automatically translates your object requests to SQL means you can make such a switch almost trivially, whereas SQL strings embedded throughout a large system can make the idea of switching database servers seem almost ludicrous. Again, this effect is amplified substantially in more complex systems, whereas in simple systems it may seem trivial enough as to not be worth worrying about.)

If the claim is that most systems are simple enough to not need metaprogramming, that doesn't in fact argue against metaprogramming features in a language, unless the language is explicitly targeted only at simple systems. Elsewhere you talked about "discouraging" metaprogramming and making it "hard", but what that translates to in the context I'm talking about is making it harder to develop complex applications. I'm guessing that isn't really your intent... [edit: that last sentence should be read to the tune of "you don't hate children, do you...?"]

### Trade offs: A novel ;-)

the low-tech approach you've described suffers from significant problems, in general, which metaprogramming does a convincing job of solving

Let's not get into a spitting contest here (my app is bigger than your app, I'm a bigger geezer, etc. ;-) ), but I'm talking exactly about database apps with a rich data model, not some simple data model with a one-to-one (or close) object to table mapping.

In fact, the requirements of the datamodel (say for reporting tools) are often quite different from the requirements of the application model, or different applications models that use the same database.

In such a scenario, the typical situation is that a given object actually requires data from a join across several tables, possibly with complex join conditions.

How are you going to do this with a meta-solution? I can think of two ways off the top of my head:

1) use a generic metadata-based OR mapper that essentially duplicates the database as an object model, and push a lot of the join work onto the app. You add complexity to your object model here.

2) have a bunch of config files that encode the queries and type mappings in some way. From these use dynamic creation or code generation to push out brain dead classes to ferry the results around.

Both solutions push the overhead somewhere else. Also the generic solution loses you the power of the native DB query language, the config one gives you a bunch of config files in a different language (XML... shudder ;-)) to manage.

may balk at the idea that you can write 100 times more code
Of course, meta-solutions save lines of code but at the expense of lines of meta-code or management code, which are more complex to maintain.

Now with my solution, because everything is encoded as native code, I can use all the techniques normally available to refactor out duplication (say families of similar queries).

My experience is that the simple patterns can be quickly created as needed and are easy to change if you have a sudden, significant change in the data model.

Yes you have a lot of them (probably hundreds (thousands?) of queries and mappers) but each is simple and does real work. (Repetition gets refactored out as it arises, and you are getting the data as directly as possible.) Typically, they are grouped into smaller sets related to specific parts of the system, so they are not so hard to manage as it sounds.

If you are actually specifying something you want, rather than just empty stuff you "have to do", lines of code are not wasted, and if they are simple and easy to read, they are easy to modify as well.

That's fine until you want to switch to a different database server.

I have to ask you: how many times have you changed database server? My observation is that once a particular database comes to stay in an organization, it is there to stay until its app dies. It is rare to port over a complex model DB from one DBMS to another unchanged.

And even if you do, if you rely on some features idiosyncratic to one RDBMS (pretty hard not to, with so little standard compliance), switching won't be easy anyway, even if you have one of those rare straight migration projects.

If I really, really had to do multi-database support, I can use normal query building techniques within my query classes. (Not "meta" IMO, since the SQL interpreter is external to the system already. ;-) )
Not great, but not as bad as "meta"-ing, IMO.

If the claim is that most systems are simple enough to not need metaprogramming, that doesn't in fact argue against metaprogramming features in a language, unless the language is explicitly targeted only at simple systems.

My claim is that better, simplifying design, using non-meta abstractions and techniques, can be used to handle complex systems where meta-solutions previously seemed like the only choice.

(A practical means to such a design is TDD, BTW)

### Saving lines of code

Of course, meta-solutions save lines of code but at the expense of lines of meta-code or management code, which are more complex to maintain.

This is our big point of difference, then. IME, there comes a point at which any maintenance required for the meta-code pales in comparison with the investment required in enormous quantities of boilerplate-like non-meta-code.

This is especially true if you're able to use an off-the-shelf meta-solution (in the persistence case, something like Hibernate), so that you don't have to do major development at that level.

In addition, the meta-specification information — like an OR mapping file — is not some kind of liability, it's an asset which contains a great deal of information about the system — e.g. a data model specification.

The analogy here is with source code in a high-level language (the meta-information) and the low-level generated object code. You don't see many people arguing that "of course, high-level languages save lines of assembly code but at the expense of lines of high-level code, which are more complex to maintain."

That equation might change if everyone had to write their own compilers. In the persistence case, writing your own persistence layer is not uncommon - I've used that approach multiple times, and guides to doing this have been around for a long time. There's certainly a threshold below which it would not be worth rolling your own persistence layer to implement a system, but that threshold mainly applies when writing a single system.

1) use a generic metadata-based OR mapper that essentially duplicates the database as an object model, and push a lot of the join work onto the app. You add complexity to your object model here.
I would say the opposite — the object model becomes a natural one for the application, so that you're not working with a "DB app" but rather with an application that happens to persist its objects to a database.
Both solutions push the overhead somewhere else.

What you seem to be ignoring is the leverage factor. The whole point is that much of the overhead of manually maintaining a large body of mapping code is eliminated. If you want to say it's been pushed somewhere else, it's been pushed to the persistence library where much of the work is automated, rather than being manually performed by programmers.

I have to ask you: how many times have you changed database server? My observation is that once a particular database comes to stay in an organization, it is there to stay until its app dies. It is rare to port over a complex model DB from one DBMS to another unchanged.

I'm a consultant, and I've helped clients do this. Larger companies often use multiple databases, e.g. at the departmental level vs. corporate-wide. Applications can grow up from a department to wider use, or need to be deployed to departments or branch offices that have a different environment. You're right that the traditional model is one application = one DB, but that's largely because it's been technically difficult for it to be otherwise. A meta approach makes this possible, and clients tend to appreciate that level of flexibility.

For myself, any generic code I write benefits enormously from being portable in this respect. In any case, the database switching example is just an example of the kind of retargeting that meta solutions support, which was prompted by the mention of embedding SQL strings in code.

Yes you have a lot of them (probably hundreds (thousands?) of queries and mappers) but each is simple and does real work. (Repetition gets refactored out as it arises, and you are getting the data as directly as possible.) Typically, they are grouped into smaller sets related to specific parts of the system, so they are not so hard to manage as it sounds.
I've done this, and seen it done, many times. The reason my previous post had the appearance of a spitting contest is because scale and/or complexity is definitely an aspect of this equation. If you're talking about hundreds of queries or mappers, then you're presumably talking about fewer than a hundred tables. But when you have hundreds of tables, the queries and mappers do indeed reach the thousands, and if you have the same core data model being used to serve multiple applications for front office, back office, management, etc., then the equation becomes more and more attractive in favor of the meta solution.
(Not "meta" IMO, since the SQL interpreter is external to the system already. ;-) )

See, that's the hiding or denying of metaprogramming that I've referred to. ;o)

If you're looking at the world from inside a single language, especially one like Java, then your view of things is going to be skewed. The SQL interpreter isn't external to your "system", it's as much a part of your system as the Java infrastructure. Otherwise, I could say that generating Java classes is not metaprogramming, since it's external to my data model specification. If you're generating SQL code, that's certainly metaprogramming. (Technically, even substituting variable values into a SQL string is metaprogramming, but at that level I'll agree that it's trivial.)

To me, the whole point of studying subjects like programming language theory is to allow us to look at entire systems and conceive and implement solutions that aren't entirely driven by the limitations of the tools used to implement them. Metaprogramming is a natural and effective solution in this context.

### Saving the company

You don't see many people arguing that "of course, high-level languages save lines of assembly code but at the expense of lines of high-level code, which are more complex to maintain."

I'd buy this is if the config/meta languages were generally better. XML, e.g., is a lousy DSL syntax, and most config formats are pretty ad hoc.
If you showed me a really well-designed OR DSL, I'm sure my reluctance would be greatly diminished. Maybe I've just been unlucky in finding one. (Yes, I've looked at Hibernate ;-))

the object model becomes a natural one for the application, so that you're not working with a "DB app" but rather with an application that happens to persist its objects to a database.

I'm not sure how this is the case in general. The so-called "object-relational impedence mismatch" comes into play: object models and relational models have different normalization rules (e.g. Law of Demeter vs. normal forms).

Another phenomenon I've observed is that different parts of the app "want" to package the info from the database differently. This is easy to do with "small, sharp" queries, less so with a generic OR model.

The SQL interpreter isn't external to your "system", it's as much a part of your system as the Java infrastructure.

This is a matter of perspective. The fact that I have to use a SQL-based database, rather than some other integrated Java database is an arbitrary constraint. To modularize this, I simply abstract the interaction between the two systems as message passing.

The Java (or other app language) needs to know how to build messages and read the return messages. I can do all that with "native" power.

I'm a consultant

This may be the real source of our difference in perspective. I've spent most of my career on or managing in-house teams building and maintaining software.

From that perspective, one of the most important features of an app (after it works) is that if the whole dev team was hit by a bus, the company could hire people who knew the language to come in and figure the app out in short order.

A related virtue is change tolerance: if some radical new requirement comes in (and it always does, doesn't it?) it is as easy as possible to see what needs to be changed, and to be able to change it.

My experience with these two factors is that the more heterogenous the system is, the harder it is to understand and change.

Because of these two values, I'm likely inclined to try much harder to simplify or eliminate heterogenous solutions.

This goes along with one of my dicta that there is as much difference between development projects/environments as similarities.

That's why I usually say "avoid meta if you can" rather than "never use it", since I can imagine getting to a project with some particular immutable constraint that would shift the balance to a meta solution, or meta is the ONLY way to do it within the contraints.

Like a lot of things in software development, if you gotta, you gotta.

But the world would still be a better place if we tried harder to do better design before deciding we gotta.

### Definition of metaprogramming

A question seems to exist about whether or not the use of tools such as regexs, SQL, DSLs, etc. is metaprogramming.

As I understand the term, the answer is no. Simply embedding a SQL query in an application, or using a regex, isn't metaprogramming--no more so that using Lua or Tcl as a scripting language for your application.

Metaprogramming refers to the creation and maintenance of such tools; not their use. If you write yourself an object model for Scheme (ignoring for now the existence of suitable off-the-shelf solutions), then you are engaging in metaprogramming. Likewise, if you write a library designed to be instrumented or otherwise manipulated by a metaprogramming system, that's metaprogramming. If you just use the result (even if it involves "programming" in a language other than the host language), that's not metaprogramming; that's just programming.

### Re: Definition of metaprogramming

Writing a program which generates another program of some kind usually qualifies as metaprogramming, no matter what language the generated code is in. That's what I was referring to: if you generate SQL queries by piecing them together according to some algorithm, that's a kind of metaprogramming. The same would apply if you programmatically generated a regexp or some Lua or Tcl code.

I made the parenthesized point that even the process of substituting variables into a SQL string could technically be considered metaprogramming, although I described that as being trivial. Nevertheless, that trivial process generates a potentially different SQL expression each time it executes. Strictly speaking, it's code generation. If you don't agree that it's a species of metaprogramming, albeit a trivial one, then you need to provide a rule which excludes certain kinds of code generation from being metaprogramming.

IMO, it's sufficient to say that such trivial instances aren't usually particularly interesting examples of metaprogramming. However, in this case, the example is worth considering because of the contrast with less trivial cases where more significant code generation does take place.

Marc actually tried to pull a bit of a fast one here ;-), saying:

I can use normal query building techniques within my query classes. (Not "meta" IMO, since the SQL interpreter is external to the system already. ;-)

I don't consider his "external to the system" reason relevant here, because by that criterion a great deal of code generation of all kinds would not qualify as metaprogramming. I think the distinction that can be made here is that in his case, he would be generating SQL from an ordinary hard-coded program, rather than from a specification represented as some kind of metadata.

To me, this really highlights the issue in question, apart from the definition of metaprogramming: if generation of a language like SQL is acceptable, then the question we've really been focused on in this subthread is the usefulness of a metadata specification for driving such code generation, as opposed to expressing the same logic directly in code, without metadata.

I would argue that if you're generating SQL code in any non-trivial sense, then you're doing a kind of metaprogramming, which makes me think that the real objection here is to something more specific than "metaprogramming". In this case, the focus seems to be on using non-standard input languages to drive programs. Taken to an extreme, this is an argument against something as simple as configuration files, and indeed Marc has mentioned those. Is interpreting a configuration file metaprogramming? ;)

### A definition of meta-programming

Writing a program which generates another program of some kind usually qualifies as metaprogramming, no matter what language the generated code is in.

Interestingly, in my "use less meta" hierarchy, it matters whether the code generated is "first class" or not.

By this I mean, if the code generation is a convenience, and you can modify the resulting code normally thereafter, this is better than the case where the code generated is really an intermediate representation artifact between the meta-code and the compiler.

Marc actually tried to pull a bit of a fast one here ;-)

If you want, I'll grant you the SQL string thing as a meta-programming instance. I will invoke the "gotta" clause here: often SQL strings are the only decent API you have for the DB.

I still don't see that I should therefore compound my sin with code generation in my app language. ;-)

Is interpreting a configuration file metaprogramming? ;)

Joke or not, this is an interesting question. To me it depends on what kind of information is in the config.

A URL for an external resource in a config seems fairly innocuous to me, whereas a string representating the name of a class to be instantiated reflectively at runtime within my app gives me pause, not to mention a config that is really a script that changes the behaviour of my app at runtime.

This also starts to get us into static vs. dynamic territory, and I don't have the stamina to go there after this marathon thread. ;-)

### Missing ingredient

What I think this subthread is missing is some real code. Addison-Wesley have taught us that it's futile to discuss software engineering in more abstract terms.

### Well, for the record, I don't drink alcohol

When I put it in my mouth, it hurts. I don't put things in my mouth that hurt. (No hot peppers either.)

Metaprogramming isn't so painful, but it's painful enough that the benefit has to be way more than the pain.

### non-meta solution?

Regular expressions are almost always implemented with metaprogramming. They are either hard-wired into the language (Perl) or they generate C/Java/etc. programs (Yacc). I don't see how interpreted implementations (Java) are superior. Just like other non-macro solutions, they don't interoperate with the existing tools of the host language, and they perform worse.

Regular expressions are a great example of Matthew Flatt's characterization of macros as lightweight compiler API's. The benefits of macro implementations of lexers and parsers are enormous: for example, all the tools that work on the host language (such as DrScheme's lexical binding arrows, not to mention static analysis tools) also work on the embedded language.

• The DSL syntax was more complex, and broken up into separate elements that all had to interact with "normal" Scheme.

In this case, macros are a huge win! When you have to intermix embedded and host language, macros really shine.

• The accepted language was complex, with a large number of states and transition labels.
• The transition labels were more complex, such as regex elements.
• The automaton was a transducer with a more complex output or side-effects.

I don't see how any of these pose a challenge specific to metaprogramming. Or rather, I don't see how implementing regular expressions with an interpreter (the only arguably "non-metaprogramming" solution) makes this task any easier. And PLT Scheme's parser-tools collection is great evidence of the power of macros for implementing embedded data languages.

### Here's the spiel

I don't see how any of these pose a challenge specific to metaprogramming.

It's not the commonality of the challenges but the fitness of the solution I'm questioning.

I guess I'll have to re-iterate my standard spiel on this topic.

First, let me make clear that my critique of meta-programming arises mainly out of the context of complex, "real world" applications that are supported by changing groups of people through time. (The norm for professional programmers.)

Using macros in PLT research to experiment with language extentions for theoretical or proof-of-concept purposes is NOT really the target of my critique.

Having said that, the crux of my issue with meta-programming is that it makes understanding and changing source code harder in general.

The reason this is so follows from what we mean when we say that a programmer "knows" a PL. Knowing a PL means, more or less, that one understands the syntactic primitives of the language, that one understands how to use these primitives in combination, and that one understands the semantics of the evaluation of those primitives and combinations.

If you extend the language with new syntactic primitives, the programmer cannot necessarily understand and modify the source code until he has learned the semantics of the new form, and also how it interacts both syntactically and semantically with the other forms already present.

And this is already assuming that the person who created the macros is as good at it as Krishnamurthi, and hasn't left a nasty gotcha that is very difficult to find and debug.

So within this perspective, the short-term gain of elegance that a macro buys you is beat out by the long-term pain of a more difficult learning curve for the applications maintainers.

### Standalone DSLs

For these reasons, I believe that the most successful DSL's out there are the standalone ones; not ones implemented as a set of C++ templates, Lisp macros, or other such techniques:

Good standalone DSLs have the following properties, in general:

* Should represent the problem domain well. As a corollary, the problem domain should be sufficiently understood that its precepts can be codified as a language (otherwise, more dynamic approaches ought to be taken).

* One need not be a proficient programmer to use them; one need only be well-versed in the problem domain.

* One need not interface with the general-purpose programmer's toolkit to use them, either. (In other words, no messing with compilers, linkers, etc.)

* (Mostly) independent of any general-purpose programming language. (Though it's nice if they are embeddable in general-purpose languages; that is often a property of the language doing the embedding rather than the DSL itself).

* Declarative rather than imperative. (For general-purpose programming; I have little problem with imperative languages; but DSLs should require little reasoning about things like execution order and side effects)

* A syntax that is simple for humans to read/write. I think that this is more important than a syntax which is simple for computers to parse/generate; many DSLs are "optimized" for the latter case to facilitate quick implementation, often as a macro package. (This requirement assumes, of course, that the DSL will primarily be edited/read by hand. A DSL which is primarily the output of some other tool, such as most XML applications, is another matter).

It isn't a coincidence that most successful DSLs are standalone DSLs.

### Standalone DSLs create semantic gaps

There's a relatively large class of DSLs which benefit from being embedded in a host language, including query languages (e.g. SQL), regexps, and alternate programming models like logic programming.

The traditional way to embed these in a host languages is as strings passed to a DSL handler of some kind, but this is fraught with messy disadvantages and requires manual integration work. This has also inspired various kinds of metaprogramming (other than macros).

Macros have proved that they can handle this problem well, for e.g. query languages (SchemeQL, SXPath), regexps (SREs), and logic programming (Kanren, Schelog). They can improve the integration with the host language to an enormous degree.

My main point here is that standalone DSLs create their own problems. I think the main reason most DSLs have been standalone has more to do with the fact that it's been harder to implement them any other way, not because there aren't good reasons to want to integrate them better with other languages.

### The middle case

You have, of course, identified the middle case. SQL and regexs are separate "languages", often outside the general purpose language, which are nonetheless primarily used by programmers (and occasionally by other advanced users). In addition, the problem domains they solve (string matching/substitution, database queries/transactions) are much more in the realm of computer science than are the domains covered by other popular and widely-used DSLs, like HTML or Postscript.

Many languages have "solved" the regexp embedding problem; as regexs are usually represented as simple strings it isn't FTMP a problem. Some languages (eg Perl) even provide separate concrete syntax for regular expressions. That said, I often wonder if the convention of using text strings adorned with metacharacters, although consise to type, is really a good idea. Quite a few problems with this approach IMHO:

1) In all regexp systems I'm aware of in general-purpose languages (and I'm not familiar with how regexps are handled in Lisp/Scheme, so pardon my ignorance on this point), regexps are checked for well-formedness at runtime. Regexps (those which are truly "regular", at least--the Perl community appears to have abandoned the term "regular expression" precisely because the feature is Turing-complete rather than just DFA-complete) can easily be represented as recursive types, it would be advantageous to have typecheckers verify the well-formedness of a regex before the program is run.

2) Reading regexs of any complexity is always a fun challenge.

3) Regexs-as-strings suffer from all the problems of "in-band signal". Some of the characters we often like to match are metacharacters, which must then be quoted... ugh. Contributes to problem #2.

As far as SQL goes, that's also an interesting bird. At some point, I imagine, it was envisioned that executives would be able to sit at terminals and enter SQL queries before making business decisions. As it turns out, SQL is primarily used by programmers and DBAs, not by end-users. Direct embedding of SQL in application code seems to be considered distasteful by many, often on the grounds that it too-tightly couples the application to the database schemata. In addition, there's also the impedance mismatch between SQL (which is set-based) and many industrial general-purpose languages (which are scalar-based). One interesting observation about embedded SQL is the move from SQL preprocessors (which take source files in a host language containing SQL directives, replace said directives with the necessary magic incantations needed to actually implement the query, and output the processed code to the actual host-language compiler) to more dynamic (interpreted) approaches. One would think that the former approach would offer advantages over the latter; again mainly around being able to check the SQL code for validity before running the app.

### Ooops!

I often wonder if the convention of using text strings adorned with metacharacters, although consise to type, is really a good idea.

Man, you really walked into this one. Anton is going to give you an education in what Schemers deny is the ugliest regexp syntax in the universe \\\$$even uglier than Emacs Lisp's\\\$$.

I mentioned the CL-PPCRE Common Lisp regexp library before. It uses strings to specify regexps (as God intended) but also detects regexp errors at compile-time (screenshot) using plain ol' macros.

Exquisite!

P.S. if you love Scheme but want to double check that you haven't been brainwashed into doing so then you can read this antidote to be sure. Ditto Common Lisp.

### And I thought perl/sed/grep/etc. was bad...

:) Actually, regexs by themselves aren't so bad, until you try to hook actions to them. Then it gets reallllly ugly real fast. :)

Of course, we won't mention that Lisp also has a print formatting "language" that manages to make printf/scanf look elegant. (ducking...)

### FORMAT

Guilty as charged. But still a thing of beauty. :-)

(defun bottle-song (&optional (in-stock 99) (stream *standard-output*))
(format

stream
"-----~2%~
~{~&~1&~
~[~^~:;~
~1:*~@(~
~R~) bo~
ttle~:P o~
f beer on t~
he wall~01:*~[.~
~:;,~%~1:*~@(~R~
~) bottle~:*~P ~
of beer.~%You t~
ake one down, p~
ass it around, ~
~01%~[*No* more~
~:;~:01*~@(~R~)~
~] bottle~:*~P ~
of beer on the ~
wall.~2&-----~%~
~1%~:*~]~]~}~0%"

(loop for bottle from in-stock downto 0 collect bottle)))


### The Middle Kingdom

In addition, the problem domains they solve (string matching/substitution, database queries/transactions) are much more in the realm of computer science than are the domains covered by other popular and widely-used DSLs, like HTML or Postscript.

It's worth pointing out that both HTML/XML and Postscript also have embeddings in Scheme, in the form of e.g. SXML and Functional Postscript. Like the other embeddings I've mentioned, these add significant value to the languages they embed, providing ways to exploit the abstraction power of the host language — very much a "best of both worlds" scenario.

The argument for a language that's extensible in this way is that you can exploit all of these domain-specific abstractions in a common environment, which has common semantic and syntactic features. There are all sorts of benefits to doing this, both in terms of expressive power as well as ease of use and semantic overhead for programmers, who don't have to deal as much with crossing abstraction boundaries, because the implementor of the embedding has dealt with much of that for you.

People object to embedding sublanguages with alternative semantics in a language, but it's hard to see how it's worse to co-opt those sublanguages so that they share a common semantic and syntactic infrastructure, compared to just throwing up one's hands and passing a string to a foreign API and marshalling and demarshalling data between the two environments.

On the regexp front, I don't think their specific merits or otherwise are all that important, since they're just one example. They're useful when they're useful, and less so otherwise. To satsify Luke's prediction, I'll point to a post of mine about an example of using SRE regexps in Scsh. BTW, there's nothing in principle stopping a Scheme implementation from checking well-formedness of s-expression-based regexps at compile time (macro-expansion time), although I'm not sure how much of that the SRE implementation actually does (I don't use regexps very often).

I agree that direct embedding of SQL text in application code is a questionable practice. However, it's still appropriate in some cases (Marc Hamann was just making the case for it), and embeddings like SchemeQL address some of the objections to that approach. This can be a good fit if you're approaching things from a functional as opposed to OO perspective. However, SQL is just one example of a query language, which is why I mentioned SXPath as well, which is a functional superset of XPath embedded in Scheme.

In all of these cases, macros do a better job of closing the semantic gap between languages than any other approach I'm aware of[*]. These embeddings aren't intended to eliminate the need for standalone DSLs, but rather they provide close integration of the DSLs with a powerful, general purpose programming environment. The "middle case" you referred to, in many ways, is the center of my programming world. Y'all are going to have to pry these features from my cold, dead fingers. ;)

[*] The closest contender is probably the sugar-over-monads approach neelk mentioned, as seen in e.g. HaskellDB. I think all that approach really needs is a bit of extra sugar on top, perhaps via a simple macro system...

### Re: Here's the spiel

Using macros in PLT research to experiment with language extentions for theoretical or proof-of-concept purposes is NOT really the target of my critique.

Nor is it the target of my interest.

The reason this is so follows from what we mean when we say that a programmer "knows" a PL. ... If you extend the language with new syntactic primitives, the programmer cannot necessarily understand and modify the source code until he has learned the semantics of the new form, and also how it interacts both syntactically and semantically with the other forms already present.

This is turning into a familiar debate. I'm just going to point to a previous incarnation and leave it at that:

### Glasperlenspiel

This is turning into a familiar debate.

You're right it is. However, you seem to have given Guy Steele the last word on it.

While his point is well taken that if, given the right community of practice, good documentation will reign supreme, and there is no more problem with macros than with other abstraction mechanisms.

And I'm sure that will be true as I program while strumming my harp by the light of my halo, as the choirs of heaven sing.

In the meantime, I have to live with the real human limitations of large projects with too many requirements and not enough continuity or time to be so thoughtful.

My argument still stands: syntactic abstractions built into the language have familiar semantics and syntactic combination properties for someone who knows the language. Macros do not.

Macros introduce two-level grammars, which are harder to reason about.

Therefore, the onus is on the macro to prove its significant superiority in any given case.

### Re: Glasperlenspiel

While his point is well taken that if, given the right community of practice, good documentation will reign supreme, and there is no more problem with macros than with other abstraction mechanisms.

No, that isn't his point at all. His point is that *abstraction* is language extension. And language extension that comes in the form of functions can be complex, and in need of complicated documentation to be useful, just like a macro. And a macro can be simple and self-explanatory, just like a function.

For example, the (define (foo arg) (+ 1 arg)) form in Scheme is typically macro-expanded to (define foo (lambda (arg) ...)). But that doesn't make it hard to understand. Conversly, there are no macros in the API for Java Swing. But that doesn't make it easy to understand, and it certainly doesn't obviate the need for documentation.

sam th

### More than one axis

His point is that *abstraction* is language extension.

I think we have to distinguish types of extension and degrees of abstraction. Creating a function does not alter the syntax of the language, it adds an item of "vocabulary". There is a big difference between the two in terms of complexity.

If told that there is a function called "foo" that takes two integers and returns a third, if I know the PL, I know the syntax to do that and how to combine it with other syntactic forms.

Furthemore, I have a model of the semantics of function calls and how they work in context. If I have the source for the function, I can easily read it and reason about what it does within the syntax and semantics of the language I already know.

This is all independent of the existence of documentation or not.

If something is done with a macro, I first have to be able to recognize that it is one (this may not be obvious). Since the syntactic form is not familiar, and has unknown semantics, I'm not sure what interaction it has with the syntax around it, and there is not necessarily even a way to guess. (Remember that "intuitive" notation is in the eye of the beholder.)

If I have the macro definition, I can probably figure out what is going on, but I have some extra challenges. before I can do so.

I have to understand the macro language, I have to have a mental mapping of what the macro will look like when it is expanded in context and then I have to figure out what semantics that expanded syntax will have.

For the sake of comparison, think about how easy it is to add a new vocabulary item in human language, and how hard to add or understand a new syntactic expression.

The two things may both be "language extensions", but they are orders of magnitude apart in complexity.

### Consider some famous advice from Steele....

...when he was less "mad" than in the above four net-postings. Advice offered in one of his famous papers; written with fellow Scheme inventor Gerald Sussman:

One decomposition strategy is the packaging of
common patterns of the use of the language.
For example, in Algol a for loop captures a common
pattern of if and goto statements. Packages of
common patterns are not necessarily merely
abbreviations to save typing. While a simple
abbrevation has little abstraction power because a
user must know what the appreviation expands into,
a good package encapsulates a higher level concept
which has meaning indepenent of its
implemenatation. Once a package is constructed
the programmer can use it directly, without regard
for the details it contains, precisely because it
corresponds to a single notion he uses in dealing
with the programming problem.

--Guy Steele and Gerald Sussman, The Art of the Interpreter. Available at the original Lambda The Ultimate collection.

Far too many macros are written as "typing shortcuts" rather than true abtractions that stand on their own (and are independent of their implementation). While typing shortcuts aren't necessarily a bad thing--they can make the original programmer (or team) more productive; they can hinder the productivity of others who have to read the code and understand the inner workings of the macro in order to effectively use it.

In fairness, the same is true of far too many classes and functions out there; however functions are easier to understand. Functions are (in most languages) easier to debug as well; as you don't have the additional step of translating one abstract syntax tree (or blob of text!) into another AST--and in many cases it is difficult to deploy a debugger against the compiler in order to trace how the macro expands. This is especially true in compile/link languages (as opposed to image-based or REPL-based languages).

In general, I like macros--and they frequently make me more productive (even in C++ and its horrible preprocessor, which is the language that pays my bills). However, whenever I use one I always feel a twinge of guilt, wishing/wondering if there isn't a better way to deal with the problem.

### Limits?

Isn't the finite automaton example chosen very carefully to be compilable by a Scheme macro? Could you write a Yacc macro that compiles directly to Scheme like Yacc does to C and lalr.lisp does to Common Lisp?

I'm not very familiar with Scheme macros but my impression is that you can't. I peeked at Matthew Flatt's paper and it sounded like the macro part of his Yacc is just for syntactic sugar, which I suspect makes it fair game to Haskell and Smalltalk hackers.

### No

With procedural macros the question reduces to: Can you write a Scheme function that compiles Yacc to Scheme? The answer to which is obviously yes. Lacking only some "minor" surface syntax details (hence reader macros).

Personally, I think there comes a point where a large macro is essentially a compiler at which point I find macros have little to offer over an external tool. This is along the lines of Scott Johnson's standalone DSL comment.

### Host language integration

Personally, I think there comes a point where a large macro is essentially a compiler at which point I find macros have little to offer over an external tool.

One thing macros have to offer here is full integration into their host language. This makes languages with macros truly extensible. External tools don't replace that capability, especially when it comes to combining multiple unrelated applications of macros in a single program.

Discussion of the benefits of macros in the context of most functional languages suffers from limited requirements of the typical problem domains for those languages. In the commercial world, we see e.g. Java programs being metaprogrammed in all sorts of ways, including documentation generation, AOP, persistence support, and code generation from metadata specifications.

Although some of this activity may work around Java's limitations, not all of it does. It reflects real-world requirements for integration between different systems or semantic levels in a program, for example. These mechanisms all end up creating languages that aren't really Java — they have semantic information embedded in comments, or they require special preprocessors to compile, etc.

In a language with macros, all these things could be done with macros, in which case all such extensions would be part of the language, would follow the rules of the language, would require less special tool support, create fewer surprises for users, etc.

IOW, macros are still way ahead of their time. Functional languages like Haskell and ML haven't really noticed this because they're not typically facing the same kind of requirements at the moment.

Note that one of the more real-world-oriented functional languages, OCaml, does in fact have a macro-like solution in Camlp4, although that still doesn't achieve full integration into the host language, which in many ways makes it more yacc-like than like true macros.

Zooming out a bit, macros are one possible way of dealing with the kind of multi-stage programming which happens in real life, whether we design integrated tool chains to support it or not. The question is not whether we should avoid metaprogramming — all systems past a certain level of complexity involve metaprogramming, it's just a question of exactly where and how it happens. The question is how we should support it. In that respect, beyond typical ad-hoc metaprogramming approaches, there aren't exactly a plethora of good alternatives to macros out there.

### Degree of macro use

First, I didn't say that macros had no benefits over external tools. That said though, they also have costs, of which host language integration can be one of them at times!

Second, I said there "comes a point" where they lose much of their benefit over an external tool. Before that point they haven't lost their benefits. Examples of something past that "point" typically require practically the entire program to be encased in a macro call, e.g. Screamer. Also, in many of these cases the effect is more like the creation of a new language than the extension of the host; again Screamer. Many of the examples you listed for Java could be done relatively locally: e.g. documentation generation, persistence support, and generating code from a specification. These are fine examples of cases to use macros. (I'm pro-macros by the way.) I'd probably consider an AOP macro in a language like Java, past that "point" (certainly if it was based on a weaving implementation, such an implementation would require the entire source code of the application; it couldn't possibly get more non-local!)

Finally, since you're compiling to the host language, host language integration, if desired, should only be slightly more difficult as compared to a macro solution (possibly less for some macro systems). In fact, macros don't necessarily mean immediate and smooth integration with the host language, yet again Screamer demonstrates this, it also demonstrates a case where (full) host language integration is less than desirable.

### Macro-based systems as compilers

Unfortunately I'm not familiar enough with Screamer to know what problems it might have that make host language integration undesirable. Can the problems be summarized easily? I'm wondering if they don't have to do with Screamer having been implemented with a non-hygienic macro system, for example.

Another issue is that macros really need a good module system to work well on a large scale, and with other unrelated macros. But macros and module systems have notoriously complex interactions, which few systems have dealt with well (and no non-hygienic systems have). I would not be at all surprised to find that implementing Screamer using syntax-case under e.g. PLT's module system solves the problems you're thinking of.

I don't see that having "practically the entire program encased in a macro call" is necessarily a problem. In fact, that describes quite a few Scheme implementations, which are implemented as nothing but macro transformations from full Scheme into some core Scheme. The macro system is the compiler's front end, and demonstrates just how useful using a macro system instead of a traditional compiler can be. User-defined macros in this environment are no different than Scheme's own derived syntax, and integrate with Scheme automatically and cleanly, because simply by defining them, they become Scheme.

For the AOP example, CLOS demonstrates many of those kinds of things already being done with macros. Again, I'm not seeing where the problems are, or at least, nothing that can't be fixed with a macro & module system done well.

Finally, since you're compiling to the host language, host language integration, if desired, should only be slightly more difficult as compared to a macro solution

But if one extension extends a language's syntax, say by adding keywords, how does it interact with other extensions, or for that matter with tools? The answer is that it usually doesn't.

If you acknowledge the need for metaprogramming on the level of having language extensions implemented as compilers that accept some superset of an existing language and compile it to that language, then it seems to me a no-brainer that such extensions ought ideally to follow some kind of syntactic and semantic standards appropriate to the host/target language. A macro system of some kind is a natural way to implement this.

From this perspective (again accepting that metaprogramming happens and we have to deal with it), the choice is between claiming that systematizing such language extensions is too hard to do generally, and should just be done by ad-hoc extensions instead; or accepting that macro systems of some kind are the way to go. The "some kind" part is the catch: for people who won't or can't use a language with regular syntax, then macros are more difficult, and at present they may be stuck with the ad-hoc approach. However, that's primitive and non-scalable, and implies that we have to work on better systems to handle the metaprogramming that's being done anyway.

### Modules and hygene

Another issue is that macros really need a good module system to work well on a large scale, and with other unrelated macros.

I'm completely ignorant both of why module systems are important for macros (never heard it said before) and of what all the fuss is with hygene. What am I missing?

Does your theory of what "is needed to work well on a large scale" account for Emacs?

### Macros, modules and hygiene

One standard answer to the question re modules and macros is to refer to Matthew Flatt's paper, Composable and Compilable Macros: You Want it When?. The bottom line is that macro systems that can execute arbitrary code during expansion introduce multiple compilation phases, and complex interdependencies between code which executes at different phases, and those need to be dealt with carefully.

For one example of the issue, see this post by Eli Barzilay about his experience converting his Swindle library from non-hygienic to hygienic macros with PLT's module system. One of the key points is this:

"you could actually use Swindle as just another language level instead of a global hack. It became extremely simple to have Swindle code and normal Scheme code coexist, even in the same application -- so whenever you require some module outside of Swindle, it will behave exactly as it should, completely unrelated to the fact that it is used in an environment where not one primitive syntax was left unturned (Swindle overrides them all -- define, let and relatives, set!, lambda)."
Note that, amusingly, an earlier poster unintentionally gave a rationale for hygienic macros and modules in the process of dismissing them:
I use defmacro + gensym, because it is more than sufficient in 99% of the cases, regardless of what the whiners and purists say. :-) [...] I try to avoid macros, since it just makes separate compilation complicated.

A good module system solves the separate compilation problems and eliminates any need to avoid macros for that reason.

Re Emacs, what I'm referring to applies to a general purpose language where you want to be able to integrate arbitrary macros into systems doing arbitrary processing. Emacs could be compared to an application framework — it provides ways to integrate functions and macros into its framework, but I doubt anyone would want to extend the current Emacs approach to general-purpose programming (any more than has already been done). If you were going to design a more modern version of Emacs, modules and hygienic macros would go a long way towards improving its architecture - in fact, DrScheme is designed along those lines.

The "fuss with hygiene" is apparently difficult to communicate in a few sentences (based on past history). But it comes down to something similar to e.g. pointers in C - who's responsible for making programs safe from certain kinds of unwanted interactions, the language or the programmer? When the language can do it without losing any capabilities, it's usually worth doing, and that's what hygienic macros do. It's helpful to avoid programming with low-level and unhygienic macros for the same kinds of reasons that it's helpful to avoid programming with pointers and manual memory management.

Unfortunately, small examples (like that dynamic programming one in the thread you referenced earlier) don't demonstrate the problems, and in many cases even large single systems don't demonstrate these problems well (maybe Screamer does?) One way problems arise is when you want to combine unrelated systems that weren't designed with each other in mind, which is exactly what you want to be able to do if you're using macros on a real-world, large-community scale.

### Screamer

Screamer is essentially a serious implementation of amb in Common Lisp (with extras). To backtrack you need continuations, and to get continuations in CL you need to CPS-convert, so they end up writing new versions of fundamental stuff like DEFUN to dynamically keep track of what needs to be CPS-converted and what doesn't.

Series is another example of "extreme macrology".

I haven't seriously used either Screamer or Series and frankly I don't dare to because of the sheer level of macrology involved. If syntax-case can bring these applications into reach then it sounds wonderful. I will read Matthew Flatt's paper.

Note: I'm not a real Lisp hacker so the bounds of macro'ability don't necessarily end at the point that I wimp out.

### Macro-based systems as compilers (exactly my point!)

This comment will be huge if I try to reply to each thing, so let me make an agressive statement:

Macros that significantly use code walking and transformation have almost all the problems of external tools and possibly some others.

• They do not integrate with the host language immediately.
• They do not compose.
• They do not work well with many of the tools of the language (unless you consider an assembly level debugger a reasonable debugger for any compiled language). And anyways, little more than an external tool would.
• They can change semantics. (It's one thing to have a new form that does something new, it's another when an old form does something (totally) different.)

Host language integration can be a problem for analyses you may want (and their fallout), or there may just be a impedance mismatch between them. To put it one way, the host language may simply be too powerful, a good example of this is Scheme's call/cc. Another problem is the macro system may not give you enough syntactic flexibility.

Let's consider two examples: a macro that CPSes the AST it is given (this is how Screamer works) and a macro that makes the functions in it lazy (say through changing (f x) into (f (delay x)) and uses of formals into (force arg)). If we look at one way of simplifying code (that Screamer uses btw), by replacing the definition of defun there is already immediately a composition problem; none of the three defuns we'd have would be correct, we'd need a fourth (and fifth!) one that combines them. Ignoring that, lazifying CPSed code will actually work out(!), but CPSifying lazy code will be exactly wrong. You can't use CPSed or lazified functions or their combinations with normal functions or most of the combinations, so that's one host integration problem. "Keywords" added either won't be recognized by the code walker or will be expanded and whether their transformed expansions will be sensical let alone right is a toss-up. These transforms change fundamental properties of the language; they can break working code. Screamer (partially) supports backtrackable state. It'd be much easier and comprehensible if bindings were immutable and there was an ML-like reference type, but that's not how the host language works and it can't be changed. Finally, practically all extensive uses of macros in Lisp/Scheme use an S-Expression syntax, this may be undesirable for one reason or another. In Scheme this can't be changed, but in Common Lisp there are reader macros, however using them loses the benefit of a free parser (though since you could just use #'read in an external tool (implemented in CL) this wasn't really a benefit) and you have exactly the loss of composition as an external tool (i.e. not recognizing keywords etc.).

In a nutshell, Screamer and systems like it are implementations of compilers in CL, not extensions raising CL to the level of the problem domain. Being compilers they have many of the same problems as more conventionally implemented ones.

### Depends on the kind of compiler, then

Thanks, I understand this point better now. However, I don't think that the dividing line is only when "a large macro is essentially a compiler", but rather depends exactly on what that large macro is doing. In any case, you may still want to use a good macro system as your implementation language for such a compiler. (For this purpose, CL macros don't necessarily qualify as "a good macro system".)

In the Screamer case, it sounds as though lack of call/cc in CL led to a lot of its problems, so it's ironic that you also pointed to call/cc as an example of the host language being too powerful. Predictably, I'm on the side of call/cc being available because it's useful for advanced application and tool development, even if it's not something that should be used directly in average programs. Take away call/cc, and a tool like Screamer has to jump through hoops, and things only get worse from there. People in the Java world are jumping through hoops these days to simulate first-class continuations, with frameworks like Cocoon, ATCT, and RIFE. Exclude call/cc from a language and tool vendors are compelled to hack the feature back in to support the things that users want to do.

This relates to my point about metaprogramming happening anyway: restricting languages by deliberately excluding useful features on the grounds that they're too powerful is about as successful a strategy as Prohibition was for restricting the use of alcohol (reverting to the analogy raised elsewhere in this thread).

In many ways, I don't really believe in the concept of "too powerful" in a programming language — what I hear is someone trying to make my life more difficult. I'd rather make the language designer's job more difficult. I'd rather look for ways to control features — e.g. by selectively importing them in particular modules — than simply ignoring them and forever having to work around that choice. I do understand that powerful features can often have major costs, but very often those costs can be significantly mitigated by sophisticated implementations, so all this says to me is that language implementors need to work harder. ;)

Coming back to Screamer, I think there's a danger in drawing general conclusions about macros from systems based on macros in CL. The Swindle example I linked to elsewhere in this thread touches on some similar points to the ones you've mentioned. I agree there are certainly cases of unmixable macros. However, the capabilities of hygienic macro systems combined with proper module systems and language features like call/cc and proper tail recursion make many more things practical than would be otherwise, and I would be quite surprised if something like Screamer couldn't benefit substantially from such features, to the point where you might change your assessment of its appropriateness. I'd be interested to see what you think of e.g. Kanren and Schelog in this respect (neither of which actually benefit from all of the capabilities I mentioned, for portability reasons).

It'd be much easier and comprehensible if bindings were immutable and there was an ML-like reference type, but that's not how the host language works and it can't be changed.
That's an argument for a better host language, it's not an argument against macros. I'm all for better host languages.

### We seem to be converging on agreement, but one misunderstanding

Thanks, I understand this point better now. However, I don't think that the dividing line is only when "a large macro is essentially a compiler"

Me neither exactly, unfortunately I don't have a concise coherent way of explaining it. It's one of those things you know when you see.

In the Screamer case, it sounds as though lack of call/cc in CL led to a lot of its problems,

That's fer damn shure.

so it's ironic that you also pointed to call/cc as an example of the host language being too powerful.

This is the misunderstanding. call/cc is cool, though I still kinda like purity so... The issue is the host language may have features (e.g. assignment, continuations, general recursion) that utterly destroy properties you want in your "embedded language" if fully (or sometimes even partially) integrated. It is often very difficult/impossible to weaken a language. call/cc (or especially shift/reset) is at the more powerful and destructive end of this scale.

Predictably, I'm on the side of call/cc being available

For an impure general-purpose language, so am I.

[...]

In many ways, I don't really believe in the concept of "too powerful" in a programming language

For a general-purpose language me neither.

â€” what I hear is someone trying to make my life more difficult. I'd rather make the language designer's job more difficult. I'd rather look for ways to control features â€” e.g. by selectively importing them in particular modules â€” than simply ignoring them and forever having to work around that choice. I do understand that powerful features can often have major costs, but very often those costs can be significantly mitigated by sophisticated implementations, so all this says to me is that language implementors need to work harder. ;)

[big cut]

That's an argument for a better host language, it's not an argument against macros. I'm all for better host languages.

The irony here is that typically, as a language gets "better" the need for (sophisticated) macro systems wanes. For example, with call/cc you would only "need" some trivial macros to implement Screamer. To take an extreme case which by some metrics is "best", behavioural reflection, macros are completely obviated as what they can do can be done at run-time (i.e. "macros" become first-class).

This is why I qualified with "in a Java-like language" implementing AOP with macros; Common Lisp has enough expressive power to implement the AOP features it has through macro expansion rather than program transformation. However, more ironic here may be the cases that I bring up are cases that are not "macro-expressive" a la Felleisen, i.e. they are they cases that genuinely add expressive power to the language. That could be read another way: macros should not add expressive power!* We actually seem to be arriving at the same conclusions for the same reasons dressed up in differently.

Returning to the beginning: I said there comes a point where large macros have little to offer over external tools and this was refined in my latest post. We seem to more or less agree on this. From your own statements, which I agree with, this does suggest that for less expressive languages simply adding macros will not gain much: the macros will be more complicated, coding the macros will be more complicated, and the expanded code will be more complicated. Strangely, the costs of macros in an inexpressive language are greater and the benefits less and in an expressive language the costs are less, and the benefits are less(!) This seems in line with the way some (e.g. Kenny Tilton, someone on the LL1 list I'll need to find) program macros. They essentially build the system without macros and then use a thin layer of macros over it, e.g. they have call-with-open-file then a very simple with-open-file using it to take a simple case. The language is where the power is coming from.

* Actually, there are some forms of context-sensitivity that go beyond macro-expressiveness, but aren't so bad as full-blown program transformation so I'd say there is some middle ground.

### Reducing power

Host language integration can be a problem for analyses you may want (and their fallout), or there may just be a impedance mismatch between them. To put it one way, the host language may simply be too powerful, a good example of this is Scheme's call/cc.

This is were the module system comes into play. The teaching languages of DrScheme defines a series of larger and larger subsets of Scheme. Restricting a language makes it possible to give more precise and "pedagogic" errors that students can understand even in their first week of programming. The implementation of the teaching languages simply uses modules.

Consider:

; define a new module 'beginner' importing all
; exported value and macro bindings from the default
; language (module) mzscheme:
(module beginner mzscheme
(provide (all-from-except mzscheme call/cc)))

; define a module 'foo' in the new beginner language:
> (module foo beginner
(display (+ 1 2))
(call/cc call/cc))
expand: unbound variable in module in: call/cc
; Oops: We are at *compile time* told that call/cc isn't defined inside foo

; let's try without call/cc:
> (module foo beginner
(display (+ 1 2)))

; evaluate the body of the module 'foo':
> (require foo)
3

--
Jens Axel SÃ¸gaard

### That's well and good...

but if you have host language integration and can receive higher-order function, they can do anything they like.

That said, such features would probably have been helpful for Screamer, but certainly wouldn't have solved the underlying "problem".

### Yes

In PLT Scheme, anyway, you can. In fact a lexer/parser-generator that's basically a parenthesized and cleaned-up yacc is part of the standard library that ships with DrScheme. There was a paper about it at the most recent Scheme workshop.

### Re: Limits?

I'm not very familiar with Scheme macros but my impression is that you can't.

You most certainly can. The paper on PLT Scheme's parser tools collection has been linked to twice in this discussion, so I won't link it again--ah, for the love o' Google, why not--but I really recommend you take a look.

### Sorry :-)

Now I read a bit about syntax-case and it seems to be the true macro facility. I thought Schemers shunned procedural macros and only used syntax-rules so I assumed the paper was all smoke and mirrors. :-)

Very nice!

### Scheme macros

The only reason "full" macros (in some incarnation) wasn't added in r5rs is that there were several possibilities to choose from and it were non-obvious which to choose. I'd be very surprised if r6rs doesn't include "full" macros.

For more on Scheme macros see:

Flatt's paper: Composable and Compilable Macros: You Want it When?" is also worth a read.

### Good

I'm glad to hear that. I thought Schemers might be marching in the other direction after reading in Well Shaped Macros of desires to "tame" syntax-rules even further. I guess that's just some crackpot theorists :-)

### Fun

This has been a very enjoyable thread. I'm learning a lot about the current state of the Scheme world.

I just read the first two sections of the You want them when? paper. I recognise the problem he is solving and why this approach is much better than (load "P.scm"). I don't really grok how this is better than the ways other metaprogramming systems take care of compile-time dependencies (Makefile, DEFSYSTEM, etc). And I'm curious to know if module is a macro or a special form (and why).

Page 10 is pretty offensive.

### Macros and modules

When I read Flatt's paper, I tried to summarize the goals of a module system for a language with macros:

-----start-----

GOAL 1
------

An important goal for a module system that supports both interactive and compiles use is:

1) The meaning of a code fragment does not depend on the order in which code is compiled and executed.

This is an important goal because:

i) A programmer can think of the module system as a way to specify which language the code of the module should be written in. A "language" should in this context be thought of as a set of visible bindings for both values and syntax.

ii) Users of a module does not need to know how anything about the dependencies of the included module.

iii) If the program works in an interactive environment, it will also work when compiled.

GOAL 2
------

The second goal is:

2) All errors that can be checked statically should be detected at compile-time.

The rationale for this goal is:

i) Static checking provides better error messages than run-time errors, since errors can inform of the programmer of the syntactical location of the error. This saves programmer time.

ii) Things checked at compile-time need not be checked at run-time. Reducing the number of run-time checks. This leads to faster programs.

-----end-----

Macros are what makes it difficult to obtain these goals at the same time.

In order for macros to do static checking, they need to communicate at compile time. E.g. a (define-record name (field1 ...)) macro should at compile time register which fields a given record has, so, say, a macro implementing pattern matching at compile time can check in that a given record pattern has the correct number of fields.

One problem is now to communicate compile time information from the compilation of one module to the compilation of the next module. This is tricky to get right, if one want to support interactive use and separate compilation at the same time.

For a concrete (simple) example of this see An example of the intricacies of macros and modules.

If you want to grok page 10, then read the original syntax-case paper "Syntactic abstraction in Scheme" by R. Kent Dybvig, Robert Hieb and Carl Bruggeman. Get it at http://library.readscheme.org/page3.html.

--
Jens Axel SÃ¸gaard

### Error messages

One of the benefit of having the meta-programming system embedded in the language as macros is that it is possible to give error messages in terms of the original syntax.

If a language preprocessor expands a.src to b.src and
the compiler reports an error in b.src then, the compiler will give an error in terms of the expanded syntax.

Integrating macros in the language makes it possible to generate error messages in terms of the original syntax - which is a huge win when a bug is to be localized.

Getting this type of precise errors in Makefile systems are at best very difficult.

(I don't know defsystem - any pointers?)

--
Jens Axel SÃ¸gaard

### defsystem & asdf

DEFSYSTEM is the Lisp version of make. These days it seems to be succeeded by asdf, which has almost the same interface. An example of a .asd file is:
(defsystem flexichain
:name "flexichain"
:components ((:file "skiplist-package")
(:file "skiplist" :depends-on ("skiplist-package"))
(:file "flexichain-package" :depends-on ("skiplist-package"))
(:file "utilities" :depends-on ("flexichain-package"))
(:file "flexichain" :depends-on ("utilities"))
(:file "flexicursor" :depends-on ("flexichain"))))

Personally I like the simple require and provide of Emacs Lisp better.

Dan Barlow's asdf-install is Lisp's answer to apt-get and is working out very well. Example:

CL-USER> (asdf-install:install :cl-ppcre)