Scheme-like ML with macros?

Coming from Scheme to ML, you lose first-class continuations (although some implementations of Standard ML have them) and hygienic macros, and gain an expressive type system. This is a great trade-off in my opinion (if it isn't obvious by now, I'm a static typing fan).

Along with the Camlp4 tool for OCaml, there is Nemerle's macro system and MacroML.

From a programming language perspective, support for syntax transformation doesn't really bring you anything new. There is a lot of research into multi-staging, though, which lets you write code that executes at different times (the real power Lisp macros add to a language is letting you do this to a degree). See MetaOCaml for example.

Quote:

Original post by Rebooted Coming from Scheme to ML, you lose first-class continuations (although some implementations of Standard ML have them) and hygienic macros, and gain an expressive type system. This is a great trade-off in my opinion (if it isn't obvious by now, I'm a static typing fan).

Linkified
Wouldn't OCaml's Ocamlp4 count as a hygienic macro thingy? Or were you strictly talking about ML?

Also, what's the difference between first-class continuations and non-first-class ones? The Wikipedia entry mentions only re-invocable and escapable continuations as classifications.

Quote:

Along with the Camlp4 tool for OCaml, there is Nemerle's macro system and MacroML.

Thanks for the Nemerle link. I've checked out Nemerle before, but strangely enough I disliked the C-like syntax (I'm moving to the dark side, I guess). As for MacroML, I could only find the paper (which is interesting, although I've not finished it yet). Is there no public release of it yet?

Quote:

From a programming language perspective, support for syntax transformation doesn't really bring you anything new.

What matters is that it can automate writing a lot of repititive code--that's the sole purpose of syntax transformation, right?
Are there any other uses for syntax transformation/macros?

Quote:

There is a lot of research into multi-staging, though, which lets you write code that executes at different times (the real power Lisp macros add to a language is letting you do this to a degree). See MetaOCaml for example.

I'm still reading this multi-staging paper, so I don't understand what you're saying. I'll be back when I'm done with the paper.

Quote:

Original post by Muhammad Haggag Quote: Original post by Rebooted Coming from Scheme to ML, you lose first-class continuations (although some implementations of Standard ML have them) and hygienic macros, and gain an expressive type system. This is a great trade-off in my opinion (if it isn't obvious by now, I'm a static typing fan). Linkified Wouldn't OCaml's Ocamlp4 count as a hygienic macro thingy? Or were you strictly talking about ML?

Ocamlp4 isn't hygienic.

e.g.

(* macro.ml *)open Pcaml;;EXTEND  expr: LEVEL "expr1"    [[ "foo"; e1 = expr; "bar" ->          <:expr< let baz = 42 in $e1$ >> ]];END;;

And then:

(* main.ml *)let baz = 69 in  print_int baz  foo print_int baz; bar;

This outputs 6942, because the "baz" symbol inside the macro is the same "baz" symbol used in main.ml. It expands to:

let baz = 69 in  print_int baz  let baz = 42 in    print_int baz;

A hygienic ocampl4 would expand the code using two different "baz" symbols; I'll call them baz0 and baz1.

let baz0 = 69 in  print_int baz0  let baz1 = 42 in    print_int baz0;

In this instance, the output would be 6969, and you'd get a warning about the unused baz1. In a language with unhygienic macros, it's possible to implement a hygienic macro system on top of the unhygienic one. This is left as an exercise for the reader.

Quote:

Also, what's the difference between first-class continuations and non-first-class ones? The Wikipedia entry mentions only re-invocable and escapable continuations as classifications.

A first-class continuation is a continuation that is also a first-class object: you can pass it around like any other object.

Many languages have non-first-class continuation-like objects which can't be copied; the ability to continue them is limited by the scope in which their names appear: examples include named goto, case, and switch and break labels.

There are also non-first-class continuation-like objects which aren't even nameable. These include unnamed switch, break, return and catch targets.

Quote:

Quote: From a programming language perspective, support for syntax transformation doesn't really bring you anything new. What matters is that it can automate writing a lot of repititive code--that's the sole purpose of syntax transformation, right? Are there any other uses for syntax transformation/macros?

Certainly. Macros are particularly useful when they aren't simply automating the writing of a lot of repetitive code. If that's all you wanted, you could use the C preprocessor!

Macros are useful for code compression. Often that means removing repetitive code, but it just as often means removing non-repetitive but predictable code. For example, one could implement OCamlP4 syntax for regular expressions.

Consider this regular expression for URIs:

(?:([^:+]*):)?   # Scheme(?:\/\/          # Authority  (?:([^@]*)@)?  #   User-Info  ([^:\/]*)      #   Host  (?::([^\/]*))? #   Port)?(\/?[^?#]*)      # Path(?:\?([^#]*))?   # Query-Info(?:#(.*))?       # Fragment

This expression should match most URIs of interest, and split them into their components.

If we had to write that by hand in C or C++ (of course, in reality we should use PCRE or something equivalent) the code would be quite a bit longer, probably slow, boring to write, and not particularly easy to write. Figuring out the state machine for a complex regular expression can be quite tricky, but it's nothing a computer can't do for itself in a fraction of a second.

In the case of a simple regular expression, although it's clear we derive great benefit from using a domain-specific language, there's no compelling reason not to compile it into an FSM at runtime.

let x = get_value() inlet y a b = fun -> ... inlet z = SELECT * FROM table WHERE row1 = x and row2 < x or y(row3, x) in  ...;;

This example mixes SQL and OCaml. Depending upon the SQL backend, the call to y might be applied later to those rows where row2 !< x, after the rows where row1 = x have been extracted. When running in an in-process implementation of SQL which supports callbacks, OTOH, calls to y might be executed right then, potentially greatly reducing the amount of data the system has to lug around. Yet another implementation might allow a version of y to be uploaded to the server.

Cω mixes C#, SQL and XML. Browsing the documentation shows examples of expressitivity granted by the mixture. For example, one can apply select statements to normal arrays of structs as well as databases. This allows data representations to be particularly agile: data can be moved from structs into a database, or vice versa, without any of the code which accesses it needing to know it moved.

The particular advantage of macros is that they allow this expressitivity to be added to a language without the compiler needing to be modified.

Thanks a lot for the detailed explanation!
If possible, drop by the workshop every now and then.

Quote:

Original post by Nathan Baum In a language with unhygienic macros, it's possible to implement a hygienic macro system on top of the unhygienic one. This is left as an exercise for the reader.

The solution would be to use a unique symbol generating function in the macro, as in MacLisp's "gensym". Right?

Quote:

Original post by Muhammad Haggag Quote: Original post by Nathan Baum In a language with unhygienic macros, it's possible to implement a hygienic macro system on top of the unhygienic one. This is left as an exercise for the reader. The solution would be to use a unique symbol generating function in the macro, as in MacLisp's "gensym". Right?

That's sufficient far most cases, but for a complete hygienic macro system, macros should capture the lexical environment in which they are declared.

For example:

let x = ref 12;;EXTEND  expr: LEVEL "expr1" ENVIRONMENT env    [[ "FOO"; e1 = expr; ->       <:expr< x := !x + $e1$ >> ]];END;;let x = 42 in  FOO x;;print_int !x;

With hygienic macros, this should output 54. (Without them, it should fail to compile, since there's no way for the macro's expansion - "x := !x + x" - to be valid.) The solution is to replace "x" in the macro definition with the actual value of x. I don't know how to do that with OCamlP4, so the reader gets another exercise.

Quote:

Original post by Rebooted From a programming language perspective, support for syntax transformation doesn't really bring you anything new. There is a lot of research into multi-staging, though, which lets you write code that executes at different times (the real power Lisp macros add to a language is letting you do this to a degree). See MetaOCaml for example.

OK, I seem to be utterly failing at reading this paper. They pack so many foreign terms that it's almost gibberish to me. For example, from the introduction:

Formalizing macros as multi-stage computations also emphasizes that the technical problems associated with macros are genuine: specifying the denotational semantics of macros involves the same advanced tools as the denotational semantics for two-level, multi-level, and multi-stage languages (such as functor categories or topoi). A denotational semantic has particular relevance to realistic compilers, which invariably involves a translation phase. A compositional (denotational) semantic is generally one of the most helpful kinds of semantics in developing and verifying such compilers.

I kept trying to jump over this stuff until I hit references to alpha conversion, at which point I guessed that I'm either a complete ass, or that I should be reading up on lambda calculus from some established reference first.

I'll go with the latter for now and ask: What book(s) would you recommend on the subject, keeping in mind I've had no formal computer science education?

My initial search seems to indicate that The Lambda Calculus (Studies in Logic and the Foundations of Mathematics) is the one I'm looking for. However, I'm really hoping that's not the case, because it's expensive as hell (Seriously, this book would cost me ~1/8 of my salary, and I'm among the highly paid developers in my country!)

Quote:

That's sufficient far most cases, but for a complete hygienic macro system, macros should capture the lexical environment in which they are declared. [snip] With hygienic macros, this should output 54. (Without them, it should fail to compile, since there's no way for the macro's expansion - "x := !x + x" - to be valid.) The solution is to replace "x" in the macro definition with the actual value of x. I don't know how to do that with OCamlP4, so the reader gets another exercise.

I see, thanks. Let us both pretend that I didn't see that reader exercise part though, because the Camlp4 documentation is huge, and I'm trying to finish SICP this year [smile]

Quote:

Original post by Muhammad Haggag As for MacroML, I could only find the paper (which is interesting, although I've not finished it yet). Is there no public release of it yet?

I don't think so.

Quote:

OK, I seem to be utterly failing at reading this paper. They pack so many foreign terms that it's almost gibberish to me. For example, from the introduction: Formalizing macros as multi-stage computations also emphasizes that the technical problems associated with macros are genuine: specifying the denotational semantics of macros involves the same advanced tools as the denotational semantics for two-level, multi-level, and multi-stage languages (such as functor categories or topoi). A denotational semantic has particular relevance to realistic compilers, which invariably involves a translation phase. A compositional (denotational) semantic is generally one of the most helpful kinds of semantics in developing and verifying such compilers. I kept trying to jump over this stuff until I hit references to alpha conversion, at which point I guessed that I'm either a complete ass, or that I should be reading up on lambda calculus from some established reference first.

A denotational semantics assigns mathematical objects to programs, giving them "meaning". This can act as a formal specification that is much more robust than lengthy specifications expressed in English (like the C++ spec). I recall reading that one of the &#106avascript developers created a denotational semantics for &#106avascript, so that he could easily find problems that would be introduced by the addition of features suggested by users (and so give concrete examples for why a suggested feature is not so good). Scheme has a denotational semantics, which is given in the R5RS standard.<br><br>Alpha conversion just expresses that the naming of variables in lambdas is irrelevant, i.e. the following terms are equivalent: \x.x and \y.y.<br><br><!--QUOTE--><BLOCKQUOTE><span class="smallfont">Quote:</span><table border=0 cellpadding=4 cellspacing=0 width="95%"><tr><td class=quote><!--/QUOTE--><!--STARTQUOTE-->I'll go with the latter for now and ask: What book(s) would you recommend &#111;n the subject, keeping in mind I've had no formal computer science education?<!--QUOTE--></td></tr></table></BLOCKQUOTE><!--/QUOTE--><!--ENDQUOTE-->I highly recommend <a href="http://www.amazon.com/Types-Programming-Languages-Benjamin-Pierce/dp/0262162091">Types and Programming Languages</a> as a great text &#111;n lambda calculi and type theory. It doesn't cover denotational semantics, however, but rather operational semantics. The Standard ML definition and the new R6RS Scheme standard give operational semantics.

Quote:

Original post by Rebooted R6RS Scheme

Hot damn! I didn't know that was out. [grin]

Quote:

Original post by Nathan Baum In a language with unhygienic macros, it's possible to implement a hygienic macro system on top of the unhygienic one. This is left as an exercise for the reader.

Can you please explain? I'd be interested to know how this works.

For example, let's imagine a Lisp-1 with defmacro. How do you implement a hygienic macro system on top of this?

Quote:

Original post by The Reindeer Effect Quote: Original post by Nathan Baum In a language with unhygienic macros, it's possible to implement a hygienic macro system on top of the unhygienic one. This is left as an exercise for the reader. Can you please explain? I'd be interested to know how this works. For example, let's imagine a Lisp-1 with defmacro. How do you implement a hygienic macro system on top of this?

Well, my statement was a hasty generalization. You can implement a hygienic macro system given an unhygienic macro system and a few other requirements. You cannot, for example, implement a hygienic macro system on top of the C preprocessor, since it lacks the other requirements.

There are two kinds of variables that present a hygiene problem: bound and free. Bound variables are easier to deal with: analyse the macro form and replace references to bound variables with gensyms:

(defmacro (foo a)  `(let ((x 12))     (+ ,a x)))

In this instance, "x" can be replaced with a gensym and the macro will be perfectly hygienic. Obviously, this needs to happen before arguments are substituted in. Given a code walker with knowledge of binding constructs, all bound variables can be automatically replaced with gensyms in a single pass. The creation of such a walker is not entirely trivial, although it is probably not more than a few hours work for an experienced Lisp hacker.

Free variables are more problematic. A free variable is a variable referenced by an expression, but not declared within that expression. To wit:

(defmacro (foo a)  `(+ ,a x))

"x" is a free variable here. Hygiene demands we use a definition of "x" as visible to the macro expander, and not the place where the macro is expanded.

(let ((x 42))  (defmacro (foo a)    `(+ ,a x)))(let ((x 23))  (println (foo 3)))

This should print 45.

In languages like OCaml, where mutable references are first-class objects, this is a little easier. Something like

(let ((x 42))  (defmacro (foo a)    `(+ ,a ,x))))

will suffice for any constant variables, and can be performed automatically along with the bound variable transformation. But of course

(let ((x 42))  (defmacro (foo a)    `(set! ,x ,a))))

wouldn't work at all, since it would try to set the number 42 to the number 23. Obviously invalid. An ugly but correct solution is to use helper functions:

(let ((x 42))  (let ((set-x! (lambda (v) (set! x v)))        (get-x (lambda () x)))  (defmacro (foo a)    `(,set-x! ,a))))

We have to replace expressions of the form "(set! free-var value)" with "(set-free-var! value)", and any other expression involving "free-var" with "get-free-var". Note that the function itself is inserted into the generated code; this ensures that the x referred to in the function is the correct version of x. Like the preceding transformations, this one can be performed automatically.

A possibly more efficient solution is available if environments are first-class objects:

(let ((x 42))  (defmacro (foo a &environment env)    `(with-environment ,(get-current-lexical-environment)       (set! x (with-environment ,env ,a)))))

In this example, macro invocation passes an environment, accessible via an special &environment parameter, which can be used with with-environment to make sure "a" is evaluated in the right context, whilst the surrounding code is explicitly evaluated in the macro expanders current lexical environment. This transformation can also be applied automatically, but it requires flexible language support for first-class environment objects. I don't know that any non-toy languages have that.

That still doesn't satisfy the general hygiene requirement. You are just constructing a lexical environment that mirrors the environment of the macro definition site; this difference is apparent in a system that allows mutation.

For example, lets say you have a variable defined at the top level, and this variable is a free reference in your macro definition. With standard lexical scope, mutation of this variable from anywhere should be apparent when evaluating any code expanded from this macro. That simply won't be the case with your technique. You can get around this by relying solely on data mutation, but that isn't the same thing as a true hygienic macro system.

Quote:

Original post by The Reindeer Effect That still doesn't satisfy the general hygiene requirement. You are just constructing a lexical environment that mirrors the environment of the macro definition site; this difference is apparent in a system that allows mutation. For example, lets say you have a variable defined at the top level, and this variable is a free reference in your macro definition. With standard lexical scope, mutation of this variable from anywhere should be apparent when evaluating any code expanded from this macro. That simply won't be the case with your technique. You can get around this by relying solely on data mutation, but that isn't the same thing as a true hygienic macro system.

What kinds of changes can be made to Scheme variables which don't involve changing the data with which they are associated?

Quote:

Original post by Nathan Baum Quote: Original post by The Reindeer Effect That still doesn't satisfy the general hygiene requirement. You are just constructing a lexical environment that mirrors the environment of the macro definition site; this difference is apparent in a system that allows mutation. For example, lets say you have a variable defined at the top level, and this variable is a free reference in your macro definition. With standard lexical scope, mutation of this variable from anywhere should be apparent when evaluating any code expanded from this macro. That simply won't be the case with your technique. You can get around this by relying solely on data mutation, but that isn't the same thing as a true hygienic macro system. What kinds of changes can be made to Scheme variables which don't involve changing the data with which they are associated?

Ok, I'll explain it again (sorry, I was a bit vague before).

Let x be a variable in the environment at the point of macro definition.

If you don't close over x, for example

(define x ...)

(defmacro (foo a)
(set! x ,a))

then the x in the macro definition is really a reference whatever x exists in the environment of macro use.

If you do close over x:

(define x ...)

(let ((%x x))
(defmacro (foo a)
(set! ,%x ,a))))

x is defined at the top level. %x is not. There is no way for an outside process to directly modify %x. The problem is simple: you have closed over the value environment; this is the environment that maps variables to values. What you wanted to close over is the syntactic environment, the environment mapping identifiers to their denotations.

Quote:

Original post by The Reindeer Effect Quote: Original post by Nathan Baum Quote: Original post by The Reindeer Effect That still doesn't satisfy the general hygiene requirement. You are just constructing a lexical environment that mirrors the environment of the macro definition site; this difference is apparent in a system that allows mutation. For example, lets say you have a variable defined at the top level, and this variable is a free reference in your macro definition. With standard lexical scope, mutation of this variable from anywhere should be apparent when evaluating any code expanded from this macro. That simply won't be the case with your technique. You can get around this by relying solely on data mutation, but that isn't the same thing as a true hygienic macro system. What kinds of changes can be made to Scheme variables which don't involve changing the data with which they are associated? Ok, I'll explain it again (sorry, I was a bit vague before). Let x be a variable in the environment at the point of macro definition. If you don't close over x, for example (define x ...) (defmacro (foo a) (set! x ,a)) then the x in the macro definition is really a reference whatever x exists in the environment of macro use. If you do close over x: (define x ...) (let ((%x x)) (defmacro (foo a) (set! ,%x ,a)))) x is defined at the top level. %x is not. There is no way for an outside process to directly modify %x. The problem is simple: you have closed over the value environment; this is the environment that maps variables to values. What you wanted to close over is the syntactic environment, the environment mapping identifiers to their denotations.

My post explicitly dealt with what to do in this case...

(define x ...)(let ((set-x! (lambda (v) (set! x v))))  (defmacro (foo a)    `(,set-x! ,a)))

This macro uses the top-level binding of "x", no matter what bindings of "x" are visible at the point the macro is expanded.

Is there some other requirement, not satisfiable by similar means, that you would impose upon hygienic macros? If there is, why do you consider that an essential aspect of hygienic macros?

Quote:

Original post by Nathan Baum My post explicitly dealt with what to do in this case... (define x ...)(let ((set-x! (lambda (v) (set! x v)))) (defmacro (foo a) `(,set-x! ,a))) This macro uses the top-level binding of "x", no matter what bindings of "x" are visible at the point the macro is expanded. Is there some other requirement, not satisfiable by similar means, that you would impose upon hygienic macros? If there is, why do you consider that an essential aspect of hygienic macros?

The example I gave you was bogus (my fault, I don't really have much experience with procedural macro systems). The code you posted is meaningless, defmacro doesnt have that sort of access to the run time environment. Try loading your code into mzscheme, for example. You will need to prefix it with (require (lib "defmacro.ss")). The actual name for defmacro in the defmacro library is define-macro.

Scala is multi-paradigm language that runs on the Java VM. It's strongly typed, has local type inference, is fully object oriented and provides functional programming facilities.

One of it's (many) goals is to be a host language for domain specific languages, and the language is tailored to provide these via libraries (an Erlang-like process model is part of the standard library).

I think it's non-metaprogramming DSL features are very promising. It's worth taking a look at.

Quote:

Original post by The Reindeer Effect The code you posted is meaningless, defmacro doesnt have that sort of access to the run time environment. Try loading your code into mzscheme, for example. You will need to prefix it with (require (lib "defmacro.ss")). The actual name for defmacro in the defmacro library is define-macro.

Quote:

Original post by Nathan Baum You can implement a hygienic macro system given an unhygienic macro system and a few other requirements.

For example, a non-broken defmacro. MzScheme's "define-macro" doesn't have any access to any surrounding environment:

> (define x 12)> (define-macro (foo) x)> (foo)reference to undefined identifier: x

Neither the environment at the definition nor the environment at the expansion point is visible. This cripples define-macro, rendering it useless for many tasks^*, and directly contradicts Scheme's policy of lexical scope.

Gauche features a properly lexically-scoped "define-macro"; my examples work as expected when using that.

* Mainly because as well as variables, user-defined functions and macros are inaccessible. With MzScheme's define-macro implementation, one cannot follow good coding practice and decompose complex logic into simpler parts.

[Edited by - Nathan Baum on March 31, 2007 12:51:01 AM]

Quote:

Original post by Muhammad Haggag Quote: Along with the Camlp4 tool for OCaml, there is Nemerle's macro system and MacroML. Thanks for the Nemerle link. I've checked out Nemerle before, but strangely enough I disliked the C-like syntax (I'm moving to the dark side, I guess).

Most of this topic on Lisp Macros goes over my head but Id just like to point out that this statement is incorrect. Nemerle also has an option to have an identation based ML/python hybrid type syntax. Id point that it has hygienic macros as well. My favourite .NET combo is F# + Nemerle, together they cover most needs.

p.s. i quit scheme because the language was not correct for me. It is much too impure for my needs.

Quote:

Original post by Daerax Quote: Original post by Muhammad Haggag Quote: Along with the Camlp4 tool for OCaml, there is Nemerle's macro system and MacroML. Thanks for the Nemerle link. I've checked out Nemerle before, but strangely enough I disliked the C-like syntax (I'm moving to the dark side, I guess). Most of this topic on Lisp Macros goes over my head but Id just like to point out that this statement is incorrect. Nemerle also has an option to have an identation based ML/python hybrid type syntax. Id point that it has hygienic macros as well. My favourite .NET combo is F# + Nemerle, together they cover most needs.

Thanks for the clarification, I did miss the part about indentation-based syntax.

Quote:

p.s. i quit scheme because the language was not correct for me. It is much too impure for my needs.

Hmm...care to elaborate? Neither ML nor Nemerle is pure, so I assume there's something specific in Scheme that drove you away.