Lambda the Ultimate

The august Waldemar Horwat -- who was at one time the lead Javascript developer at AOL-Time-Warner-Netscape -- once told me that he considered Javascript to be just another syntax for Common Lisp. I'm pretty sure he was being serious.

Waldemar is a former colleague of mine. Believe me, he was being 100% serious.

I think this is what water's talking about. According to the readme, it's more of a semantic verifier rather than a full implementation. It also includes some goodies, like an HTML-to-RTF translator, written in CL.

PS - From what I've encountered, it seems there's an awful lot of people [hoards] who believe that Lisp's syntax sucks compared to Jscript/Python/Whatever despite never having touched the language. Citing the hoards of other people who are able to use language X, but have never heard of Lisp, as evidence of said hoards' inability to use Lisp (therefore proving once and for all that prefix syntax sucks) also seems a popular pastime.

My experience agrees with Vlad. That Lisp's syntax is "unusable" is a foregone conclusion that seems to have very little to do with the syntax itself, and everything to do with the mere observation that it is dissimilar to the prevailing popular syntax.

People gravitate to the familiar, even when it isn't.

I thought the point about Lisp was that it wasn't supposed to have that much of a syntax?

I now find Scheme syntax very comfortable, to the extent that when I try to code in Haskell or *ML I can sometimes "see" the Scheme constructs that are hidden by the syntactic sugar. Pattern matching and data constructors/destructors are very convenient replacements for some of the most common Scheme idioms, for instance.

<statement obviousness="bleeding">What you lose is the advantages of having both all programs and all possible data structures represented by S-expressions, and the ease of code generation and transformation that provides.</statement>

Personally I don't miss it, but that's because I've never used it before. For others, it's a way of life...

(let ((x 5)) (* x 2))

{x = 5; x * 2}

To be fair, there's no better syntax. Both syntaxes have their pros and cons. I do think though that when all programmers would be exprerienced in both syntaxes, that only the good programmers would choose the S-expressions syntax.

[1] I will not get into a Lisp syntax discussion.
[2] I will not get into a Lisp syntax discussion.
[3] I will not get into a Lisp syntax discussion.
...
[500] I will not get into a Lisp syntax discussion.


I am cured.

I doubt it; I know lots of PL researchers who are good programmers (and obviously know Scheme) but prefer ML/Algol-like syntax.

The argument that s-expressions are suited for metaprogramming is completely bogus, and is mainly promulgated by people who don't (want to) understand parsing, and cannot distinguish between syntax and semantics---incidentally the same sort of people who think that expressing something in XML magically makes it "reflective" or "introspective". If there's something about Scheme syntax that promotes metaprogramming, it's quasiquotation, and there's nothing about quotation which depends on s-expressions.

A Scheme-like language is somewhat easier to extend with new syntax, but that's partly because it forces the programmer who is writing code to do things like precedence parsing mentally, at least if what he's got in his head is "in ML-like syntax". That burden is partly made up for by the fact that it's easier to to extend the syntax, but conversely there is less often a need to define new syntax in an ML-like language.

Personally, though I lean towards ML syntax, I don't really care a whole lot about the issue itself; I care more about the fact that other people care so much about it, because it's so pointlessly divisive.

OTOH, I have the feeling that I could more easily convince (using reason, not rhetoric) fans of s-expressions to use ML-like syntax than the other way around, and so I think the point of convergence, if there is one, is going to be on the ML side.

The argument that s-expressions are suited for metaprogramming is completely bogus...

I suppose that people who do "understand parsing" might feel that parsing isn't real work (or that the amount of work is trivial compared to the benefits it brings), but it's still work of some kind, and work you don't have to do if you stick with s-expressions. So yes, in the longer term this is arguably a false economy, and yes, the "real" work - which would have to do with semantics - undoubtedly remains to be done whatever the syntax chosen, but no I don't think it's entirely bogus to point to the utility of s-expression syntax in a "LISt Programming" language...

You can get a nice overview of the design space for metaprogramming systems at Tim Sheard's web page:

http://www.cse.ogi.edu/~sheard/staged.html

So in 2001 I attended the LL1 workshop, and got a chance to see a presentation by Waldemar Horwat, and after the talk I had a chance to chat briefly with him. In the course of our conversation, he mentioned to me that he had invented a denotational semantics for Javascript, implemented it in Common Lisp, and written a pretty-printer that generated an HTML version of the semantics as a reference.

I expressed some surprise that he would go to such lengths for such a pragmatic, industrial language. He replied that his use of formal semantics was entirely defensive and pragmatic: whenever someone on the JS mailing list asked for a new (and usually ill-conceived) language feature, he would implement it, and then use that to come up with bad interactions. Offering concrete examples of problem cases was usually enough to convince people to drop the idea, whereas simply saying it was a bad idea just encouraged them to argue.

I left in some awe of his project management kung-fu. :)

Only inasmuch as you don't have to write those primitives yourself. You can get the same benefit from providing a standard AST library. If the language is any good, then providing those functions in a library will be indistinguishable from building them into the language.

and that getting an s-expression representation of any such structure is also directly supported by the interpreter.

Yeah, via quotation.

Ralpha wrote: Well, if metaprogramming is important (we've all read Paul Graham's "Beating the Averages"), and there's nothing special about quasiquotation that depends on s-expressions, then why don't more languages support it?

First, Neel answered this quite well.

Second, metaprogramming is only a means to an end. I avoid it whenever I can do as good or better a job without it. If you take higher-order functions and static typing seriously, if you really exploit them, then in practice that's pretty often. (Static typing lets you force the user to follow a certain pattern which would otherwise be enforced via a grammar. HOFs let you assign a semantics to such a pattern.)

For example, YACC is a kind of metaprogram, but I hardly ever use it, preferring instead to use parser combinators. (And BTW almost every program I write includes such a parser.)

Third, not all of us here (well, specifically me) subscribe to Graham's creed. Graham probably makes ubiquitous use of macros because, in LISP, he has to or maybe because that's the only way he's ever learned to solve those problems; I dunno. It's pretty hard to tell really, since he gives not a single example in "Beating the Averages".

Here's what he says:

The source code of the Viaweb editor was probably about 20-25% macros. Macros are harder to write than ordinary Lisp functions, and it's considered to be bad style to use them when they're not necessary. So every macro in that code is there because it has to be.

And you take him at his word, just like that? If I wrote a C program and told you, it is 20-25% macros and all of them have to be there, there ought to be a red flag going up in your brain saying, "Waitaminute, if I have to farm out a quarter of my program to another language, the preprocessor, then C can't be too hot..." (And lest you say, "But in this case both languages are LISP!": no, one language is LISP minus macros, and the second language is LISP plus macros. In other words, the computational core of LISP is inadequate.)

Here's the conclusion that Graham draws instead:

What that means is that at least 20-25% of the code in this program is doing things that you can't easily do in any other language.

Now, if you've read more than one of Graham's articles and you have some experience with non-mainstream languages, then you've probably noticed that Graham has a particularly parochial view of the programming language design space: there's LISP, and all that other crap. Graham's assurance that you can't easily do what he does in other languages is not very convincing to me.

Other languages provide safer, more reliable and more direct ways to solve many problems which can only be tackled by macros in LISP; he just doesn't know about them, because he never bothered to look.

Also, why do ML-like languages have less of a need to extend the syntax than other languages?

Most ML-like languages support a mild form of syntactic extension whereby the user can define new infix operators, and define their precedences and associativity. It turns out that this is sufficient to comfortably embed several sorts of domain-specific languages. Famous examples are parsing and pretty-printing libraries; we have a couple available here.

It's not perfect, but it's tractable.

First, for anyone on this board who may have somehow missed my incessant posts about BeyondJS, a higher-order programming extension to JavaScript, please check it out.

Or you may want to wait a couple of days as I plan to upload a major revision and extension of that library. Here is a teaser:

File.StdIn.collect(function(line) { return line.split(",").reverse(); }).feed(File.StdOut);

reads coma delimited data from the standard input, one line and a time and feeds it to the standard output. This code now works both in Windows HTA and WSF files as well as on the JVM using Rhino.

You may also want to check out the numerous code samples I've posted on LtU (especially as code samples is almost all the documentation there currently is).

BTW, comparing JavaScript to LISP misses JavaScript's OO nature. Yes you can do OO in LISP but then you can do most anything in LISP. For JavaScript, OO is core to its nature. Indeed, while JavaScript (at least without BeyondJS ;-) isn't pure functional, it certainly is pure OO - everything is an object (including functions :-).

Personally I wasn't interested in Common Lisp before I read PAIP, but afterwards I had to try programming in it, and have been doing so regularly ever since.

You'll understand it even better when you write and attempt to debug a large, multi-module application and discover that your macros are being executed at the wrong time phase, are duplicating your computations, inadvertantly introduce unbound variables, capture free variables and generally produce gibberish. Then, when you try writing the application as a DSL in Haskell, you'll be amazed at the burden you've shrugged off.

Luke: Frank, have you read Norvig's Paradigms of Artificial Intelligence Programming?

No, I haven't but maybe I will. Why don't you have a look here (the source code for his book) and tell me which program best exploits the qualities unique to LISP? Maybe, if I can understand it, I'll reimplement it in Haskell or ML.

You'll understand it even better when you write and attempt to debug a large, multi-module application and discover that your macros are being executed at the wrong time phase,

are duplicating your computations,

inadvertantly introduce unbound variables, capture free variables and generally produce gibberish. Then, when you try writing the application as a DSL in Haskell, you'll be amazed at the burden you've shrugged off.

(And lest you say, "But in this case both languages are LISP!": no, one language is LISP minus macros, and the second language is LISP plus macros. ...)

That's not really accurate: there is no Common Lisp without macros. Even when writing macros, you have the full facility of defmacro at your disposal.

It reminds me of a sig I saw once on comp.lang.lisp: "Will write code that writes code that writes code that writes code for money." Nothing stops you from defmacro'ing some defmacros that themselves defmacro. "Lisp minus macros" and "Lisp plus macros" is a false dichotomy; at most, the difference between the two is stylistic, like the difference between writing imperative or functional code in ML.

Jeremy

That said, I would be duly impressed to see a rewrite of Norvig's prolog compiler (prologc.lisp and friends) in another language, preserving the way it generates host-language code directly for many things and doesn't just do everything with a run-time system / interpreter. I genuinely don't know if that is possible in other languages, and if it is I'd like to know how it's done.

Rather read this paper: Matthew Flatt. "Composable and Compilable Macros: You Want it When?" Proc. ICFP '02.

Isn't [duplicating computations] a problem only on non-pure languages?

First, no, it isn't, for performance reasons.

Second, I'm talking about LISP and Scheme, and they're impure.

Isn't [variable capture, etc.] a problem of non-hygienic macros only?

Right, but LISP doesn't have hygienic macros, and Scheme's hygienic macro system is rather limited. The general issue of how to safely manipulate higher-order syntax is still an open problem, as you will see if you do a CiteSeer search for "higher-order abstract syntax".

I mean Template Haskell can do the work of a macro system and AFAICT doesn't suffer from these problems.

It absolutely does suffer from these problems. TH is a very modest attempt at macros for Haskell; it doesn't attempt to treat the hard problems.

I'm just trying to figure out if macro systems are inherently tricky or it's just an implementation problem.

It's inherent. Higher-order syntax is intrinsically more complicated than first-order syntax, just as nested datatypes are intrinsically more complicated than regular datatypes.

Jeremy: That's not really accurate: there is no Common Lisp without macros.

Sure there is; it just doesn't happen to have a name. If you write a program which makes no use of macros, then you're writing in that sublanguage. Saying there is no LISP without macros is like saying there are no subsets of the natural numbers, N.

Even when writing macros, you have the full facility of defmacro at your disposal.

I'm fully aware of this.

My point was that the fact that people like Graham think macros are so great suggests that the computational core of LISP, that is, the sublanguage without macros, is inadequate for writing large programs. You may say, "So what? As long as you have recourse to macros, who cares?" But my position is that macros aren't a good way of doing many things, so they aren't a satisfactory antidote for the problems with the core language.

Hm, if I understand you correctly I think I would need a quotation mechanism for that, like in MetaML. However, have a look at demos/prolog in the Hugs distribution. (It installs to share/hugs/demos/prolog.) It's not in DSL form, though.

I'm sure you could define a minimal subset of Haskell into which all Haskell programs could be translated, and call that the "computational core" of Haskell; but I wouldn't want to program in it. I'm not sure that I see how Lisp macros are less a part of Lisp than the do syntax for sequencing monadic actions is part of Haskell.

Oh my god! My LISP is on fire! My macros are inexplicably taking on a life of their own, duplicating work, kidnapping poor defenseless variables, and pillaging the whole program! Whoever would have thought that one could write higher-order syntax (woohoo! another smarty pants math-man phrase I can add to my vocabulary!) with bugs in it!?

"And lest you say, "But in this case both languages are LISP!": no, one language is LISP minus macros, and the second language is LISP plus macros."

You mean it's all LISP with quotation? (Well, and a reader written in LISP - but wait a second! There's that circularity - it really is all LISP and macros).

"Hm, if I understand you correctly I think I would need a quotation mechanism for that, like in MetaML."

In other words, the computational core of ML is inadequate. :)

What I think this boils down to is the fact that macros provide the flexibility to design your own computational features (that are "hard-coded" in the specifications of other, more "computationaly able," languages), but of course with power comes a price and a responsibility. This debate is turning out a lot like the arguments about continuations (which, btw, Paul Graham implements in CL using macros, described in On Lisp, and which he used extensively in his Viaweb app).

Err, sorry to veer so far off topic (but I can never resist a good macro debate). BeyondJS is something I'll definitely be checking out. Neel's post, which indicates that denotational semantics does actually have a use (!), is making me consider looking at said semantics more seriously.

Thanks, but I would recommend you wait a bit. I have an extensively modified version I need to upload but have been rather busy of late. Hopefully it will go up sometime next week.

Neither would I. But, the analogy:

LISP minus macros : LISP :: core Haskell : Haskell

is not correct. The reason is that the translation from Haskell to core Haskell only boils down the surface syntax, while the translation from LISP to LISP minus macros also adds new expressive power. I'm not sure exactly what sort of expressive power is (and that's part of the problem), but it's something to do with staging.

I have no problem with macros used to change surface syntax; for example, the way derived expressions forms are described in Scheme.

And I have no problem, obviously, with the idea that a feature adds expressive power.

However, LISP-style macros conflate the two, and I think they should be kept orthogonal. The fact that the two don't have to be intermingled is demonstrated by languages like MetaML, which supports staging but not syntax extension.

Vlad: Oh my god! My LISP is on fire! My macros are inexplicably taking on a life of their own, duplicating work, kidnapping poor defenseless variables, and pillaging the whole program! Whoever would have thought that one could write higher-order syntax (woohoo! another smarty pants math-man phrase I can add to my vocabulary!) with bugs in it!?

You must be from Slashdot.

Well, Vlad, here's another smarty pants math-man phrase for you: abstraction. One of the purposes of abstraction, of course, is to be able to reuse a component in multiple contexts, to increase productivity and reliability.

Now, if you'd ever written an interpreter or compiler, you'd have recognized that many of the problems which occur with macros, for example, variable capture and duplication of computations, are precisely the tricky problems which are dealt with in a compiler, problems which novices typically become aware of only through trial-and-error, if ever.

The problem with LISP-style macros is that they force the user to solve those problems over again. But, if the interpreter/compiler writer has already done that, why should they have to? Why can't they reuse that functionality?

To put it another way, the problem is that LISP doesn't sufficiently abstract from the way programs are represented. It forces you to work with surface syntax, represented as trees of atoms, when in fact a program has a great deal more structure.

For example, it ignores the distinction between free and bound variables; this is why variable capture is a problem. It ignores the fact that not every s-exp is syntactically legal; this is why you can produce gibberish. It also ignores the semantics of a piece of syntax: this is why it's so easy to duplicate computations and violate the call-by-value semantics (problematic, for example, because it breaks abstraction---the user must know if he is calling a procedure or a macro).

Treating programs as s-expressions is as sloppy and error-prone as using a list where a data abstraction like a set is required. If you use a list, then the burden is on the user to ensure that any procedure which processes the list does not distinguish lists which are equal as sets. For instance, if f takes [1,2,3] to some value, then it must also take [3,2,1] and [1,1,2,3] to that value. In fact, the problem with programs is far more severe, because the divide between programs and their textual representation is much greater than that between sets and lists. (This is, after all, precisely why interpreters and compilers are valuable!)

The alternatives to macros, things like DSLs and staged languages like MetaML, avoid many or all of these problems (though I imagine they impose some limitations as well). For example in a DSL you're co-opting the built-in binding syntax of higher-order functions to sidestep the variable capture problem; variable capture simply can't happen, because the compiler writer already solved that problem for you.

You mean it's all LISP with quotation? (Well, and a reader written in LISP - but wait a second! There's that circularity - it really is all LISP and macros).

I don't see your point. Anyway, it's irrelevant how the reader is implemented.

In other words, the computational core of ML is inadequate. :)

Yes, I do believe that the computational core of ML (actually, I was talking about Haskell) is inadequate, but because it lacks semantic quotation (or at least something akin to it), not because it lacks syntactic quotation.

To explain this remark, let me first observe that, actually, I've been conflating two distinct things with the word quotation.

"Quotation" of the first sort is a syntactic convenience; like in camlp4 and Template Haskell, it's just a way of abbreviating values of some datatype representing an AST. LISP's sort of quotation is pretty much the same, except that it uses s-expressions as the AST datatype. (Scheme is a bit better; hygienic macros actually construct an abstract `syntax' datatype.) You can do metaprogramming with this, but for all the reasons I mentioned earlier, it's unsatisfactory.

"Quotation" of the second sort is a semantic feature, as in MetaML and MetaOcaml. This kind of quotation is different, because it really respects the structure of programs. In MetaML, for example, quoted programs are values of a special abstract type, code, and it's impossible to construct values which represent ill-formed, or even ill-typed, programs.

IMO, it doesn't make any sense to regard syntactic quotation---LISP's sort---as part of the computational core, precisely because it's a syntactic, and not computational, mechanism. There are computations going on, of course, but they're effectively in another process, the recursively invoked interpreter, which just happens to send its output to the current interpreter.

Now, back to the question of doing a Norvig-style Prolog compiler in Haskell.

I could do it with Template Haskell, of course; but that wouldn't prove anything, would it? Because it's just syntactic quotation again, as in LISP.

I think I could do a Prolog interpreter as a DSL in non-Template Haskell. The way I'd do it is to start with a monadic back-tracking parser, and generalize it to operate on trees rather than lists, and to do unification rather than matching. But that's an interpreter rather than a compiler.

Perhaps I could do something like in UU_Parsing; they effectively compile a grammar at the beginning of a parse. But I'm not sure.

A MetaML-like mechanism seems like the most straightforward way, since it's been demonstrated how you can turn an interpreter into a compiler by staging it using MetaML.

What I think this boils down to is the fact that macros provide the flexibility to design your own computational features (that are "hard-coded" in the specifications of other, more "computationaly able," languages), but of course with power comes a price and a responsibility.

What it boils down to, Vlad, is that macros are just a slightly more convenient way of piping text from one application to another, the second of which happens to be an interpreter. Macros don't handle the difficult part of program transformation, because they don't treat programs as programs, they treat them as text (or s-expressions, if you will). Macros let you extend LISP's computational features only inasmuch as Lex lets you extend C with regular expressions, or YACC lets you extend it with LALR(1) parsers.

One of the things I hope to add to Arrow, eventually, is the ability to do such rewriting. At the moment, though, I only know how to do it for very simple kinds of programs, programs which are not only terminating but also reversible, and so far from Turing-complete.