Lambda the Ultimate

....S-Expressions. :-)

is it the prefix notation? the parenthesized grouping?

Prefix notation is bad since it departs from conventional mathematics usage, but for crying out loud: this isn't mathematics, it's programming!

Function calls in mainstream programming languages always begin by name, in other words, use prefix notation. So, a java guy would say, taxDeductions( 2004 ) and a Lisp fellow, (tax-deductions 2004). What's the matter here? It also ilustrates that the difference about parenthesis usage is the location of the verb: outside in most mainstream, inside in Lisp.

Prefix notation isn't used in OO conventions though, where you first spell out the subject and then the verb to declare something about it: person.father, while (father person) looks far more natural ( to me, at least )...

Not to say it frees you from typing a lot of annoying separators ( besides read-friendly whitespace ), as in:

( OCaml )
[1; 2; 3; 4; 5; 6] vs '(1 2 3 4 5 6) or

( C )
printf( "heya! %s, %s, %s, good to see 'ya all!",
"john", "mary", "frank" ); vs
(printf "heya! ~A, ~A, ~A, good to see 'ya all!"
'john 'mary 'frank))

Is there something i'm missing?

Comment was meant to be more of a ribbing. First, I know it always grates the Lisp'ers when you complain about s-expressions. Second, we all know that any language will eventually be doomed to re-inventing Lisp. :-)

My opinion on s-expressions is that they are fine in the small but I do like clear demarcations of functions, modules, objects, etc... When I look at an s-expression program, I get bogged down in seeing "data". That can be a good thing since the distinction between data and program is arbitrary and minimizing that distinction can be used to good effect. But I'm still left with the problem of parsing it for visual clues.

But then, this is a long-running argument - of which is I was tersely alluding to in my feeble attempts at joking. IIRC, McCarthy experimented with M-expressions early on, but it did not lend itself to the use of Macros (so it was also dropped early on).

"But I'm still left with the problem of parsing it for visual clues."

how about editors with syntax-highlighting? ;)

...and not entirely reasonable along these lines. We'd get into an argument about what constitutes a readable syntax. Do we go with what makes the most sense from the standpoint of legacy (C, C++, Java, etc). Or do we go with a syntax that makes the most sense for expressiveness (Lisp, Smalltalk, etc). Or do we lay a new path that best represents the unique ideas that we are trying to convey with our new language.

Tools for manipulating programs are always interesting and Lisp has always been at the forefront on this (as well as many other things). Notes that the environment for Smalltalk is an important component in the programming experience, with it's various ways to get a handle on the inspection and manipulation of things within the image.

In the end, you could probably convince me (as I'm easily assuaged). But then you still have to convert all the masses out there that there are benefits to learning a syntax that they are not used to (whatever language du joir they happened to be using). So even if we agree with ourselves what the syntax should be and how much power it gains us, there's a lot of evangelizing that would have to be done to gain acceptance.

All this kidding aside, I think designing a language is something that's tricky. In the end, if you write a language, the first rule of thumb is that you write it to scratch an itch (be it ease of expression, ease of maintenance, or pedagogy). Once written, that's when you worry about whether it's useful for anyone else. So before you even talk about the form and substance of a language, you have to decide what exactly the itch is that you are trying to scratch.

Since LtU represents a somewhat diverse community of users with the commonality being issues concerning programming languages, I'm not sure that we really share itches. IOW, why are we wanting to design a language? A kitchen-sink approach is extremely hard (say Ada or the current effort in Fortress).

i know i'm happy with Scheme, OCaml and Haskell. and i know Java, C++, Perl and other grunts are happy too... :)

maybe a new kitchen-sink language could go by the name Babel. ;)

Why not put the function outside the parentheses, and default to quote?

(1 2 3 4 5 6)
printf("heya! ~A, ~A, ~A, good to see 'ya all!"
'john 'mary 'frank)

I certainly find foo() a lot more readable than (foo).

"I certainly find foo() a lot more readable than (foo)"

Perhaps you're just used to it from Algol offsprings?

It's a simple convention: the first element in an unquoted list is _always_ a procedure. Putting it outside the parenthesis would break the all-important program-as-data concept because of a tiny nitpick which shouldn't exist if you're well aware of the convention...

it should also prove to be trickier for the Lisp interpreter to parse...

"Putting it outside the parenthesis would break the all-important program-as-data concept"

Naw, it would just be less simple to parse.

"Perhaps you're just used to it from Algol offsprings?"

It's not Algol, but general math, where you can always put parentheses around a subexpression without changing the meaning.

Also, putting things between any kind of braces would suggest containment or protection, which is quite the opposite of execution.

it's just a notation.

Yes, putting things inside parentheses certainly do convey a containment feeling. And that's great for the idea that programs are data.

On the other hand, it's just a convention: Lispers now the first element in an unquoted list is ( should be ) a procedure, so there's no confusion.

There are languages which use postfix notation, and that's just another convention as well. Just like the math notation, which BTW, has changed a lot through the centuries...

It's not common sense: it's made up conventions useful for their domain of application.

Even the mathematicians got it wrong, and we live with it. Everyone is used to seeing the syntax, y = f(x), which would have made much more sense if it had been written y = x : f, or if you want x -( f )-> y. The reason is that composition reads most naturally from the left to the right, just as in reading.

Due to this, we see Haskell with it's composition operator (.), with things like: result = (f . g . h) x, which really is h applied first, then g, then f. With the alternative notation, it becomes obvious: x -(f g h)-> y, means the result of piping x through f, then g, then h, putting the result in y.

F# and some Ocaml people have started doing this by defining |> and >> as (left) application and composition. I think that's a very nice convention.

composition reads most naturally from the left to the right, just as in reading

Left-to-right is just another arbitrary (western) convention. Other cultures read right-to-left, or even vertically.

Sure, there are different reading orders but current programming language are pseudo-English so to be coherent the notations used should be left-to-right..

That said I don't find x |> f -> y easy to read but that's probably just because I'm not used to this notation.

current programming language are pseudo-English

Might be, but he was complaining about math notation, for which this isn't the case.

When did you ever see a (math-) diagram where the arrows went left? I bet is a small percentage. I agree that this is "western" thinking, but western thinking is dominant within science.

At least one algebra book used the notation 'x f' for "x through f", and it was for sure alien, but it does make sense.

PKE.

"arabic" numerals for a reason...

... because they're really Hindu numerals.

(Actually there is a reason: because the Arabs adopted them and we got them as hand-me-downs from the Arabs.)

Hindi (language) numerals not Hindu (religion) numerals

It is Hindu (civilization - Indus|Indian) numerals not Hindi (which is a very young language ~13 A.D atleast) numerals

touché

Putting the argument before the function in applications in the lambda calculus makes beta redexes humanly easier to parse, since the part of the lambda abstraction that takes the argument, the lambda binder, is then next to the argument it takes.

This is the item notation used in Kamareddine & Nederpelt's 1995 Refining reduction in the lambda-calculus, which puts it to use to expose some redexes in terms lying just beneath the surface.

The item notation in this paper looks similar to the notation I use for CPS transformation. To simplify CPS notation the arrow is equivalent to:

z->x.y  ==  (\x k.k y) z

With this notation, the CPS transformation of ((\x.(\y.(\z.z d)) c) b) a simplifies in:

((\x kx.kx ((\y ky.ky (\z kz.kz (z d))) c)) b) a
(b->x.(\y ky.ky (\z kz.kz (z d))) c) a
b->x.c->y.(\z kz.kz (z d)) a
b->x.c->y.a->z.z d

Have you written this up?

I did not write any theorical paper on the subject ;)

In fact, that works exactly the same without CPS ((\x.y) z == z->x.y) and I cheated in my reduction by dropping the brackets at step 3. You would normally need a variable substitution before you can do that.

Self-modifying code and macros are a must.

Why do you say that? I'm all for metaprogramming, but I don't see the need to resort to something as inconsistent and complicated as macros.

So you end up with users calling eval on quoted code instead, what's the biggie? Any system that doesn't let you manipulate an AST for the code in question is going to cause major pain.

I know. What I'm saying is that macros aren't necessary to allow for such things. Really, macros are just one big premature optimization and are inflexible to boot.

Pretty random, abstract claim.

Depends on what your definition of a macro is. What would you use instead? Have you ever programmed in Scheme or Lisp? How are they related to optimizations?

Any function that operates on and generates code is a macro. They're also useful for creating new syntax, DSLs, etc. Not particularly optimization tools though.

Depends on what your definition of a macro is. What would you use instead? Have you ever programmed in Scheme or Lisp? How are they related to optimizations?

Lisp-like macros would be what I'm referring to, yes.

Any function that operates on and generates code is a macro.

Not quite. A macro is a function that operates on/generates code before normal code is executed. You've actually noticed something about macros that most people don't--the fact that macros and functions overlap completely in functionality. In essence, what I'm proposing is moving the most useful thing about macros--compile time execution--into the domain of functions, either automatically by the compiler or explicitly by the programmer. This has several advantages, including the fact that there is now a single interface to do a single thing and that compile time functions can be executed at compile time and run time without any change to said function.

Lisp macros are executed at runtime! Presumably some get evaluated at compile time too as optimizations. Macros are not about compile-time evaluation at all.

You've actually noticed something about macros that most people don't--the fact that macros and functions overlap completely in functionality.

No, I understand that perfectly well. In fact, in the very beginning I acknowledge this fact:

A macro is a function that operates on/generates code before normal code is executed.

If I did make reference to macros being executed at compile time after that, it was simply for convenience, since I don't recall the exact name other than the somewhat verbose and not very descriptive 'pre-execution time' ;-)

Can you explain your arguments then? You claimed macros are "just one big premature optimization and are inflexible to boot". I don't see where this is coming from. Then you posted about compile time execution, stating that you want the same interface for compile-time and run-time macros. But lisp already has this, and it isn't about compile time execution. So I thought you had a misunderstanding of Lisp macros, but apparently not.

So what are you arguing for? You usually have a good point, it just takes a while to beat it out of you ;)

The only optimization case that I can think of for macros is forcing inlining of code, in (-drumroll-) C (pre-C99).

In essence, what I'm proposing is moving the most useful thing about macros--compile time execution--into the domain of functions, either automatically by the compiler or explicitly by the programmer. This has several advantages, including the fact that there is now a single interface to do a single thing and that compile time functions can be executed at compile time and run time without any change to said function.

You're describing partial evaluation. See A Hacker's Introduction to Partial Evaluation, and the Online Bibliography of Partial Evaluation Research. It's often been discussed here on LtU. There are some other links from the wikipedia article.

A related subject is abstract interpretation, which can loosely be described as executing a program before all its input is available.

Partial evaluation can move computations to compile time, which overlaps some of what macros can do, but it by no means replaces macros. The unique uses for macros, particularly in Lisp and Scheme but also more generally, are to (1) create new binding constructs, (2) implement unusual evaluation orders, and (3) define minilanguages for data definitions and other kinds of DSL (summarizing from this post by Matthias Felleisen).

None of these things are achieved by partial evaluation alone, and for the most part, these features require a syntactic transformation in principle, so whatever you do to achieve these things is going to end up being macros, in some form.

You're describing partial evaluation. See A Hacker's Introduction to Partial Evaluation, and the Online Bibliography of Partial Evaluation Research. It's often been discussed here on LtU. There are some other links from the wikipedia article.

A related subject is abstract interpretation, which can loosely be described as executing a program before all its input is available.

I don't think that's really what I'm talking about. I'm talking about compile-time execution of functions, e.g.:

def pow(x, y):
    if y == 0: return 1
    if y == 1: return x
    return x*pow(x, y-1)

x = pow<compile-time>(2, 16)

Where pow(2, 16) is computed at compile time (or at run time if it's run in an interpreter).

edit:
Angled brackets didn't show up.

Yeah, I'm pretty sure that's partial specialization.. and nothing to do with macros or metaprogramming.

Is it? Oh, my mistake. Either way, it may not directly replace macros, but it covers most of the cases. When you do need full-blown metaprogramming like in macros, a fairly rare event, it's not terribly hard to do using compile time functions and, say, the metaprogramming capabilities in python.

it may not directly replace macros, but it covers most of the cases

Metaprogramming is what it sounds like - writing metaprograms - that is, programs that result in programs. Not compile time evaluation, or anything. Don't get confused with C macros or C++ metaprogramming.

You give some good points, but these get lost in misunderstandings. Learn Scheme via SICP (free online); pick up OCaml; and while you're at it, read the excellent CTM. I've not read TAPL myself yet, but I gather it's good and its my personal next step.

I personally find Python's metaprogramming poor. It lacks the power and the simplicity (which you obviously desire) of lisp macros. Its true that metaprogramming in lisp is a relatively rare event, but its extremely useful and powerful when it is used. If you want you can write macros that write macros that write macros that write code.

Metaprogramming is what it sounds like - writing metaprograms - that is, programs that result in programs. Not compile time evaluation, or anything. Don't get confused with C macros or C++ metaprogramming.

Yes, I know what metaprogramming is.

You give some good points, but these get lost in misunderstandings. Learn Scheme via SICP (free online); pick up OCaml; and while you're at it, read the excellent CTM. I've not read TAPL myself yet, but I gather it's good and its my personal next step.

What for? I already know quite a bit about them.

I personally find Python's metaprogramming poor. It lacks the power and the simplicity (which you obviously desire) of lisp macros.

Python's metaprogramming (eval, exec, etc.) is fine for the very tiny amount of metaprogramming that's actually done in it. Most of the time, macros aren't even used for their metaprogramming capability, but rather for when they're executed.

What for? I already know quite a bit about them.

To learn? To me it seems your knowledge of them is actually quite limited.

How so?

You also seem to reinvent things a lot, and learning what has already been done would be good.

Perhaps, but this isn't necessarily a bad thing. It means I actually understand what I'm implementing and I've already thought it through.

I personally find Python's metaprogramming poor. It lacks the power and the simplicity (which you obviously desire) of lisp macros.

It got quite more powerfull recently. Incidentally my main motivation to create EasyExtend besides curiosity and fun was to enable partial evaluation and algebraic manipulation of expressions in Python ( without Guidos permission ;). In EasyExtend the meta-programming is compile-time only: the syntax transformations have to be performed before bytecode generation. The system is still in a rough shape i.e. there is no syntax sugar or templating for syntax transformers.

Yes, compile-time execution of functions is partial evaluation. You may not be recognizing that it's the same as what you're describing, because of unfamiliar terminology.

Either way, it may not directly replace macros, but it covers most of the cases.

This isn't correct in general. It's true that in some systems, macros can be used to move computations to compile time, but this is not their primary purpose (or shouldn't be). In my previous comment, I summarized the three categories of motivation for macros, none of which are replaced by compile-time functions. Those three categories of applications for macros refute your belief that "macros and functions overlap completely in functionality".

It sounds as though you may be generalizing too broadly from your experience with macros in particular languages (perhaps C or C++)? In that case, please try to phrase things more like "covers most of the cases in a language like C", otherwise needless argumentation results — we've already seen that in this thread.

When you do need full-blown metaprogramming like in macros, a fairly rare event, it's not terribly hard to do using compile time functions and, say, the metaprogramming capabilities in python.

This is only partly true, at best. There's some overlap, because metaprogramming is a broad term. However, the sort of macros we're discussing ("Lisp-like") let you extend the syntax of a language, and neither compile-time functions nor Python's runtime metaprogramming features actually do that. [Edit: perhaps examining EasyExtend, mentioned in another comment, will help in understanding the purpose of "real" macros in the Python context.]

There are some cases where you can get away with using Python's existing syntax in clever ways, in conjunction with metaprogramming, to do something that you might otherwise use macros for, but this is not a general solution.

In addition, runtime metaprogramming, as in Python, tends to reduce the ability to statically analyze programs, which doesn't just affect compilers - it also tends to make programs more difficult for humans to reason about.

This isn't correct in general. It's true that in some systems, macros can be used to move computations to compile time, but this is not their primary purpose (or shouldn't be)

It's how their used most of the time in the languages I've seen, e.g. common lisp.

I summarized the three categories of motivation for macros, none of which are replaced by compile-time functions. Those three categories of applications for macros refute your belief that "macros and functions overlap completely in functionality".

A function is piece of code that takes data as input and returns something. A macro is a piece of code that takes code as input and returns code to be executed. Because code can be data, a function in a language with run time metaprogramming capabilities is exactly equivalent with macros barring time of execution. To demonstrate this, consider the usual 'until' macro using python:

def until(condition, body):
    while not condition():
        body()

In this case, it doesn't even need to use any metaprogramming capabilities, because the sole reason for this even being a macro in the first place is to control when 'condition' and 'body' are executed. Of course, if you really wanted to, you could write it using metaprogramming:

def until(condition, body):
    while not eval(condition):
        exec body

This is only partly true, at best. There's some overlap, because metaprogramming is a broad term. However, the sort of macros we're discussing ("Lisp-like") let you extend the syntax of a language, and neither compile-time functions nor Python's runtime metaprogramming features actually do that.

There's probably some convoluted way to shoehorn syntax extensions into functions, but I'm not even going to try. I don't find them useful at all, so I guess if you want syntax extensions macros do have a use.

In addition, runtime metaprogramming, as in Python, tends to reduce the ability to statically analyze programs, which doesn't just affect compilers - it also tends to make programs more difficult for humans to reason about.

Ah, quite the contrary. As I've already demonstrated with my 'until' example, macros have many uses, only some of which absolutely require the use of metaprogramming. In those cases, the resulting functions become clearer because you're using normal code constructs. I do admit, however, that the cases in which you absolutely need metaprogramming would probably be slightly more complicated, but I've honestly never seen such a situation in the first place, so I'm not inclined to worry it.

It's how their used most of the time in the languages I've seen, e.g. common lisp.

I'm not sure about "most of the time", but I agree that macros are commonly used for that purpose in Common Lisp. That simply underscores the point, though, that you can't generalize from the example of one or two languages. For example, macros are used primarily for syntactic abstraction in Scheme, not for general compile-time computation.

What "syntactic abstraction" means is being able to take some pattern of syntax that occurs in multiple places in a program, and simplify the program by abstracting it out to a common place. Of course, it's possible to use this ability to do the same thing as an ordinary function does (i.e. procedural abstraction), but we both agree that this isn't a real justification for macros. The justification for macros comes in when you use them to abstract syntactic patterns that you can't abstract away with functions. Your 'until' example is a good one: the client code that uses 'until' won't look like this:

until x > 10:
  x = x + 1

Why won't it look like that? Because you're missing syntactic abstraction. Of course, you might try to "shoehorn syntax extensions into functions", as you said, but at that point you're implementing a macro system, and that'd be the first time that you're doing anything that has to do with the real purpose of macros.

A function is piece of code that takes data as input and returns something. A macro is a piece of code that takes code as input and returns code to be executed. Because code can be data, a function in a language with run time metaprogramming capabilities is exactly equivalent with macros barring time of execution.

By "code can be data", and given your "until" example, you seem to be referring to higher-order functions. This has little to do with macros. The languages with good macro facilities also have higher-order functions, but that has nothing to do with syntactic abstraction. So "exactly equivalent" is incorrect, except in the one restricted case we've discussed, i.e.:

You're saying that in cases where macros happen to be (ab)used in order to execute procedural abstractions at compile time, that this usage can be replaced by a feature in which functions execute at compile-time. We agree on that much, but you can't extrapolate from this to say anything about the usefulness of macros for syntactic abstraction, since nothing you've described so far has addressed that point.

Ah, quite the contrary. As I've already demonstrated with my 'until' example, macros have many uses, only some of which absolutely require the use of metaprogramming.

What you've demonstrated with your 'until' example has very little to do with macros. The cases you're talking about optimizing are already optimized in languages such as Haskell, SML, OCaml, Scheme, Erlang (the list goes on) in a way that has nothing to do with macros — some of those languages don't even have macros. You seem to be proposing to duplicate an aspect of the compilation model of those languages, which is fine. However, you shouldn't confuse that with replacing macros.

If you're interested in an optimization such as compile-time functions, you would probably get a lot out of learning some more theory. Books like SICP, CTM, PLAI, and EOPL, all linked to in the Getting Started thread, are well worth reading, and will give you a good grounding. If you want something to focus on as a motivation, you might look into the lambda calculus, which is a lot simpler to learn than it might sound (see links on above page), and it's an ideal system for exploring partial evaluation. There are also systems available which will help you do that exploration.

Finally, a lot of the work on compilation is extremely relevant. As Paul Snively put it here, "under the hood, all compilers end up being functional and relatively close to the Lambda Calculus". I have a couple of other relevant links in this comment.

I'm not sure about "most of the time", but I agree that macros are commonly used for that purpose in Common Lisp. That simply underscores the point, though, that you can't generalize from the example of one or two languages. For example, macros are used primarily for syntactic abstraction in Scheme, not for general compile-time computation.

Syntactic abstraction? As in, reader macros?

Why won't it look like that?

Because it'd look like this ;-)

while x <= 10:
    x += 1

I don't believe in specialized syntax outside of the compiler, which, even though they can't be replaced by functions, I don't think they need to be.

What you've demonstrated with your 'until' example has very little to do with macros.

It has everything to do with macros sans syntax modification, which I've adressed above. If you want to discuss my reasoning behind that, it's fine, but I assure you that functions can replaced every use of macros sans syntax modification.

Could you explain to me how functions (and because I'm in that kind of mood I'd like to emphasise /pure/ functions) can build and declare a new compile-time-visible type from scratch? Without access to an equivalent of Template Haskell's quotation monad?

I'm not sure what you mean by "compile-time-visible type," could you explain?

Visible for purposes of static analysis. You don't have to run the program just to know the type exists.

How about something like this:

def reverse_arg(function):
    return (x,y => function(y, x))

def inverse_class(data, functions):
    functions = functions.map(([x,y] => [x, reverse_arg(y)]))
    return data::[**functions]

obj = inverse_class(
    1, {
        "sub": (x,y => x-y))
    }
)

obj.sub(2) # 1
obj.sub("1") # error, can't subtract 1 from "1"

In this case, inverse_class would be automatically executed at compile time and thus 'object.sub' can be checked as well.

edit:
Changed 'print' to 'sub' in example.

It has everything to do with macros sans syntax modification

Right, and what I've been trying to explain is that the only purpose of macros is syntax modification. What's confusing you is that it's possible to use syntax modification in the compile-time optimization way you're describing. However, eliminating the need for that falls under the category of "ordinary compile time optimizations" in any halfway-decent compiler (as described in the compilation links in my previous comment), and has nothing to do with macros.

Right, and what I've been trying to explain is that the only purpose of macros is syntax modification.

What do you mean by syntax modification? It's not too often you actually see a reader macro used in the wild.

Curtis, we're having some kind of misunderstanding about the nature of macros. However, this really isn't the place to hash that out. I'll send you a private email about that.

In the meantime, speaking as an administrator of the site, please slow down on the number of comments you're posting here. In the week since you registered here, you've been the most prolific poster, almost double the next highest (who is a long-time member).

Much of this has been because you've been discussing ideas of yours for which the rest of us have no details (type inference, and macros or compiler optimizations). LtU depends heavily on links to papers or articles. Before posting further on these subjects, please post a more detailed writeup of what you're thinking of, on your own website or blog, so that you can link to them in future comments here. Or, as Philippa suggested, post an interpreter or other semantic description. That'll cut down on the need to hash out details here, and avoid disturbing our regular readers.

Regarding an interpreter, it'd probably be easier to start with a stripped-down "core" language that illustrates all the important points - or easier yet, the abstract syntax tree for one. I think I could see where to start building one from the descriptions given, but I can't be certain it'd be the right thing.

If you'd like, I can update the grammar I have of the language and upload it. I stopped using it a couple months ago when I really started getting parts of the interpreter done, as that's my preferred method of documentation, but it shouldn't take too much effort to update it.

Actually, nevermind. The interpreter should be done in a couple weeks, so it'd probably be easier to just release it as a mockup.

Sorry I didn't notice this sooner, apparently it got lost when I replied to a message :/

Curtis, we're having some kind of misunderstanding about the nature of macros. However, this really isn't the place to hash that out. I'll send you a private email about that.

I recently changed email addresses. The new one is now in my profile.

In the meantime, speaking as an administrator of the site, please slow down on the number of comments you're posting here. In the week since you registered here, you've been the most prolific poster, almost double the next highest (who is a long-time member).

Heh. Sorry, I can get carried away sometimes in topics like this.

Much of this has been because you've been discussing ideas of yours for which the rest of us have no details (type inference, and macros or compiler optimizations). LtU depends heavily on links to papers or articles. Before posting further on these subjects, please post a more detailed writeup of what you're thinking of, on your own website or blog, so that you can link to them in future comments here. Or, as Philippa suggested, post an interpreter or other semantic description. That'll cut down on the need to hash out details here, and avoid disturbing our regular readers.

Aye. I've tried to be at least somewhat abstract in my posts regarding the concepts I'm talking about, but I find that writing code helps to convey what I'm talking about better than just text alone, although I can tell I definitely need to relegate code examples to a secondary role and keep to text for the main concepts.

Metaprogramming is what it sounds like - writing metaprograms - that is, programs that result in programs. Not compile time evaluation, or anything. Don't get confused with C macros or C++ metaprogramming.

Now you seem to think macros are about compile-time evaluation again. Seems we are going round in circles.

Considering 'until' is a fairly common example of macros, I'd say they are used for things like that.

Couldn't you completely replace macros with partial evaluation if you also had call-by-name?

Lisp-style macros let you:
1) extend syntax
2) let add domain specific optimizations
3) let you generate code from a specification or arbitrarily transform code

These are three things that cannot be replaced by uses of HOFs or by having compile-time functions (unless they can be used to splice in code, in which case they are macros) or by PE. Run-time metaprogramming techniques (reflection) allow 2 and 3.

You can extend the syntax of Lisp as long as it looks just like Lisp. That is what I thought was ironic about the video posted recently using Lisp to recreate a DSL by Martin Fowler. The first thing the person does is make everything look like Lisp, and not like the original DSL. This seems to me like an instant disqualification.

Are there languages that allow sublanguages to be defined down to the lexical parsing level? [..googles for "scannerless parsers"]

Camlp4 allows you to use different lexers. It's pretty flexible.

On the Lisp/Scheme side, writing a lexer and parser for a language is the easy part, especially if you use a parser generator and even a lexer generator — some people don't like doing that, but it does tend to make it easy.

It's a pity Fowler didn't just do that. He must know how easy it is, and perhaps assumes the audience would know that — parser generators are one piece of academic computing technology which propagated to the mainstream a long time ago.

There are numerous good parser generators available for Scheme, and presumably for other Lisps. Implementing the semantics is where you really want to bring the heavy machinery to bear, though. In Scheme, implementing a complete DSL can involve little more than writing a few macros and snarfing the rest of the features you need from Scheme.

Assuming you already have the language design — the one part that can still require real work — and assuming there's nothing terribly unusual about the language, implementing a complete small DSL can take a few hours, including lexical syntax and grammar. Of course, you do need to be familiar with all the tools.

PLT Scheme is a good place to look if you want to see real languages implemented in Scheme. It includes its own parser generator library, and supports language implementation in a number of ways: in its module system; in its macro system, which includes a syntax object representation that includes precise source location info; and in its IDE (DrScheme). It has an implementation of a version of Python (see From Python to PLT Scheme), as well as subsets of Java used for teaching (ProfessorJ). The DrScheme IDE's ability to syntax highlight and graphically annotate code (e.g. point from uses of variables to where they're bound) works on these languages because of the underlying syntax system — see the screenshots in the linked Python paper. Of course, these language implementations are more complex than the DSL implementation I described above, because they implement big languages.

Factor allows you to write 'parsing words' from where you can parse any syntax, and generate Factor code to be spliced in. In the space invaders emulator I wrote I built a DSL based on the Z80 instruction set. Factor would parse this and produce the factor code to emulate that instruction. Instructions looked like:

INSTRUCTION: CALL P,nn ;
INSTRUCTION: SBC A,B ;

The INSTRUCTION: word was a parsing word. It analysed the input stream up to a semicolon and used parser generators to parse and produce Factor code from this. The code is here.

Common Lisp has reader macros that (modulo an "escape") would allow you to do that, though I will admit I wasn't really aiming at them (though I wasn't excluding them either). Either way, what defmacro does can still be described as extending syntax, but as you say, not at the lexical level. Others have pointed out other languages. Though I should add, in response to the post on Factor, that Forth (a direct predecessor of Factor) also has parsing words.

I think it would be useful for a language to provide a string literal syntax that (almost) never requires escaping. Use parens or braces as the begin/end string markers, but allow the string to contain other braces if they balance. Only stray unbalanced parens would require an escape and the escapes wouldn't compound as strings are nested. Strings containing code containing strings containing code containing strings would not need any escapes.

(string (the stuff between parens is a literal string (this is still in the string) string ends here->)  )

I'm not sure whether you know this or not, but this is one of the string syntaxes that PostScript (and thus PDF) supports (as described in the PostScript Language Reference Manual 3rd Edition (7.5MB PDF)

Anything macro-like that you implement with call-by-name would still be used via syntax that looks like an ordinary function call. To change that, you'd need a way to pass syntax to a function, before it's given the meaning that it would usually be given by the language parser. Once you allow that, you essentially have macros.

Lisp-style macros are effectively syntactic sugar for what I've described. They seem one of the saner ways to go about metaprogramming to me.

What did you describe?

quote and eval.

Macros are overboard for 99% of the time metaprogramming is needed.

What is your replacement?

See my reply to Anton.

You might think so. Personally, I've another 99% of cases to run with because half the things you're talking about don't need metaprogramming in many languages anyway.

Could you elaborate? I'm having a hard time understanding what you mean.

Even though you know apparently metaprogramming is about writing programs which generate programs, all your examples have focused on compile-time evaluation. Which has nothing to do with metaprogramming.

So 99% of the code that needs metaprogramming probably does need macros.

Even though you know apparently metaprogramming is about writing programs which generate programs, all your examples have focused on compile-time evaluation.

That's because it's the most common use of macros. If you give me a situation in which metaprogramming is useful, I'll gladly show you how it would be done.

I disagree with your one-sided characterisation of meta-programming as program driven code/AST generation. Computational reflection is clearly a meta-programming facility and Python as well as Ruby are quite strong at it right now.

Your idea of "99% of the times you need metaprogramming" has been influenced by things that don't actually need it and can be done via partial specialisation or lazy evaluation (Haskell has pattern-matching as part of the core language and as the main - or indeed only in the absence of IO - driver for evaluation, but all other control flow is expressible in terms of pattern-matching and recursion alone, to the extent that continuations can be implemented as a monad). I can think of multiple use cases for metaprogramming facilities off the top of my head that don't come into that 99%, whereas your examples don't spring to mind at all.

Metaprograms that inspect and optimise code, possibly using partial evaluation, would be something that occur to me - but the use of having them rather than a sufficiently smart compiler that can figure out where to perform partial evaluation would be in encoding extra domain knowledge. Using GHC's rules facility to add fusion and related optimisations would be an example.

Another might be generating accessors, datatypes etc from a database, or alternatively generating (or building code to generate, remove and otherwise administrate) the tables etc in the database from a type. At risk of recalling the O/R mapping wars, the latter in particular's something I want to have a play with - it seems a sensible way to get all the definitions in one place.

Your idea of "99% of the times you need metaprogramming" has been influenced by things that don't actually need it

I know. I was giving examples for how compile time functions remove the need for the most common usage of macros, not necessarily metaprogramming.

Yeah. The best languages are always started by a single person trying to fufill a real goal. Besides, we all probably have our favorite language already anyway.

Besides, we all probably have our favorite language already anyway.

We just haven't implemented them yet. ;)

Someone quoted me saying:

Academics are continually chewing pieces off of impossible and making them merely difficult.

But I spend my time translating the difficult into the understandable.

I try to read and understand research papers well enough to translate them into something a motivated professional programmer can understand and most importantly use. (For example, with The Monad.Reader and three years of explanations on the #haskell irc channel.)

My experiences on the #haskell channel imply that there is not enough organized and accessible documentation for the research we already have.
I would much rather create a "code as literature" website to teach elegance by example, or refactor all the threads on LtU into wikipedia-style articles.



For example, there's a common pattern on the original wiki where a wikipage will start out in ThreadMode, and once the activity has died down, will be refactored into DocumentMode, FaqMode, or whatever is appropriate for the subject. That could easily be applied here on LtU.


Increasing the accessibility of the knowledge already on LtU will advance the state of the art of programming language design as perceived by the mainstream.

--Shae Erisson - ScannedInAvian.com

How about we exchange some emails and see how we can make this happen?

I really like the idea of LtU threads refactored into somekind of LtU wikipedia. It'd certainly make finding some of the wisdom buried in the archives much easier to find.

Just let me know what to do :).

As educational as it would be, I'd have hard time dragging myself away from it. It would totally decimate my productivity, but it would still be worth it. ;-D

What's the status on the wiki idea ? It would demand a large editing effort, but it would be a great resource.

I am willing to help too.

Anyone willing to help should send me an email, so I can get in touch.

What's your email address ?

Given the affinity of LTU for domain specific languages, the present topic of joining together on one language is somewhat at odds with our common interest.

I second the interest in a language system. But perhaps existing tools are enough and a system isn't needed. It's a little puzzling how rarely LTU mentions the usefulness of specific tools, libraries, boilerplate, and architectures for implementing DSLs.

to get things right, but my feeling is, looking at my longtime favorites Scheme and Postscript, that it can be done to design a minimalist language with amazing expressiveness. E.g., a sketch of a Postscript interpreter in Postscript:

{ currentfile token { exec } { exit } ifelse } loop

C, my home turf, sucks somehow, but it is a usable mix of machine-language features and features that let me keep the overview, having a textual code representation that reflects the nesting of structure and reducing the need for arcane details like segmentation, labels, argument passing in registers and on the stack etc. Deep inside however, there is a wish in many people including me to keep control of these features as well.
A failure to modularize and abstract, if you wish.
Otherwise, C wouldn't have survived.

(And oh. There are some great languages out there. Not perfect, but quite good. It's just a matter of knowing were to look.)

The number of greater experts than me in this forum could perhaps send the less enlightened of us who agree upon the wish for an expressive, extensible, self-modifying, bare-metal language along the right search path.

Many languages have tuples/records for basic datatype which can not be extended (add/remove), it seems this would be useful where you have 10 attributes but only want to deal with 3 of them.

I am not sure what you are trying to describe here, but it sounds like subtyping might solve the problem. O'Haskell has a feature named record stuffing, it maps a selector name to an identical variable already in scope.

I totally agree with keeping the compiler very simple

This puts quite a few constraints on how your language is designed. Optimizing Compilers for Structured Programming Languages is an excellent read.

GSA sounded neat, but newer versions of that Oberon compiler don't use it.
oo2c post on using SSA.

...though rather than "C++ done right", I would describe it as "Stepaunov's dream language". Think of it as a language designed for implementing the STL in the most elegant way possible.

The language would be an imperative language with a Milner-esque type system, but have language support for concepts, which would look like type classes, only more so (e.g. dependent types), and have true dynamic binding (unlike C++ templates).

The idea is to keep the stuff that makes C++/Ada programming cool, but lose the historical baggage (from C/Algol respectively) and removing the (in retrospect) arbitrary restrictions.

Oh, and algebraic data types are a must, though I could personally give lisp-like lists a miss. If you want a modern Lisp variant, you know where to find it. :-)

That reminds me of Felix and not just because it's from Australia. It's a "C++ done right" with an ML style type system, and AFAIK without the power of concepts. Going beyond that to Stepanov's dream language would be both interesting and practical.

What would you think about macros? Good, bad?

C++ Macros ? Bad.
Lisp Macros ? Good.

Just my two cents.

As David Teller said: "Lisp macros good".

For a C++-like language, I think the direction to look in is something like lazy template instantiation, only more macro-like and with a nicer syntax.

Yep, those were the ones I meant (how dare I post about preprocessor macros on ltu :o).

Rather than recreate a whole new language, how about just hacking C to be more Haskell-like?

That's one of my lines of thinking.

My list of modifications:

• Do away with the distinction between expressions and statements.
• Prep up the logical operators to be more Perl-like: the value of a&&b should be b if a is non-null. I just love Perl's open "file.pl" or die;
  In Javascript, a couple of things have been done right in this respect.

• A basic way to explicitly collect the upvalues for lexical closures, e.g. in a nameless aggregation of values (an ad-hoc struct that is allocated on the heap and expressed with a lean syntax), in conjunction with one or more nameless ad-hoc functions with variable references into the aggregation.
• Scheme/CLisp-like macros acting on the syntax tree of the parsed input language that can annotate types of expressions and expand macros with information about expression types. This would require a simplification of the syntax (see expr/stmt above)
• more...

Basically take C, and add to it to make it a better:
-Continuations (still not sure exaclty what this is but seems important :) )
-Better threading
-Better pointer system (perhaps safer?)
-Higher order functions
-Better native array system (so if programmed correctly APL would have no performance advantage over C ?)
-Better memory handling (some sort of garbage collection?)
etc., etc., etc.

Keep it a good language for systems programming, but extend it to be a better 'intermediate representation' language. That way DSL could be built on top of C without too much hassle and we could have mini-C++ for specific domains...no?

C has something already built in with setjmp() and longjmp(). Originally intended for servicing asynchronous interrupts which is a form of continuation.

And for lack of a better place to put it, the one language feature I'd really like to see more languages build support for: Icon's concept of Success and Failure. (Griswold knows strings).

A longjmp() is an upward non-local exit to an earlier point defined by setjmp(), unwinding the C stack only, and can't support "winding" the stack in a downward jump, as provided by general continuations.

Calling a continuation is a lot like jumping up or down the stack to a spot saved when a continuation is created, and there are about as many stacks as continuations (... which share structure in languages like Scheme, where a stacks is one path in a forest of heap-based environment frames.)

A C jmpbuf initialized by setjmp() basically captures all register values -- including top of stack -- that ought to be restored by a later longjmp(), which pops the stack by virtue of restoring an earlier copy of the stack pointer. The behavior is the same as C++ exception throwing, except it's unfriendly toward finalization since destructors (for example) won't be called between the longjmp() and the second return from setjmp().

I think it is going to be instructive to see how each comes up with a language that reflects his own background...

Any idea ?

I could use a good DSL for desrcibing (and simulating) cellular automata...

I've messed around with this a little bit, but... I'm by no means an expert at the whole language thing. I was just bored in English class.

Pynchon is what i thought up. Feel free to tell me it sucks.

I'd like to suggest to pick a DSL that is unrelated to computing. This would ensure that there is no experience or any preconceived ideas about what the DSL should look like.

Do you mean a DSL related to shopping or visiting a zoo ? I'm not sure I understand your "unrelated to computing".

I wonder, if whenever a domain of DSL is computing, it really becomes a GPPL?

"Do you mean a DSL related to shopping or visiting a zoo ?"

Something like that, yes. How would you like to program a robot to do a days household tasks or something.

Each with a kind of personality of it's own. There's C lurking in the background as a close-to-the-metal language. Then there's Simula strapped on with classes. Then there's generics strapped on with Templates. Then there's.... and on and on.... It can be both a blessing and a curse to be multiparadigm. The point is not whether it can be done, but how seamless and natural the transition is from one paradigm to the other.

The designers of the type inference know that dynamic programs represent a subset of statically typed programs wherein a dynamic variable is really a variable that is an intersection of declared types. Even knowing that, it's very hard to bypass the type engine because you have to be explicit in defining the intersection - continually adding new types to the data type declaration. And also of having to intersperse the constructors every time you actually want to manipulate the variables.

Ok, so C++ can use a variant type, but I don't think it's type system qualifies as what I'm aiming for. Or to put it in a different light, what if C++ was a language with templates being the only part of the language that you actually use.