are dylan macros Turing-complete?
Colin Walters
I'm doing a bit of research on the Dylan macro system, and I must say
I've been very impressed! It certainly seems to capture the vast
majority of transformations that typical Lisp macros do, but in a
clean and elegant fashion.
Anyways, in this paper I'm writing, I claim (without real proof) that
Dylan macros are not Turing-complete. I'd just like to confirm that
this is in fact the case.
If anyone has any actual references to that effect, I'd be very happy;
I haven't been able to find anything of the sort...
Also, is it possible for a Dylan macro to loop infinitely? I'm
thinking of something like:
define macro buggy-macro
{ } => { format-out("buggy macro\n"); };
end;
...but at least the Gwydion Dylan compiler doesn't like that. Perhaps
there is a more clever way to make a macro loop...
Bruce Hoult
Colin Walters <wal...@verbum.org> wrote:
> Anyways, in this paper I'm writing, I claim (without real proof) that
> Dylan macros are not Turing-complete. I'd just like to confirm that
> this is in fact the case.
It's pretty easy to translate Turing machine programs into Dylan using a
list of tokens as the tape and macros as the program.
Dylan macros are definitely Turing-complete...
-- Bruce
Neelakantan Krishnaswami
>
> Anyways, in this paper I'm writing, I claim (without real proof)
> that Dylan macros are not Turing-complete. I'd just like to confirm
> that this is in fact the case.
Dylan macros are definitely Turing complete. Here's an (untested)
lambda calculus implementation as a macro:
define macro equal
{equal([], [])} => {true}
{equal([?:expr], [])} => {false}
{equal([], [?:expr])} => {false}
{equal([?a:expr], [?b:expr])} => {equal(?a, ?b)}
end macro;
define macro test
{test(true, ?cons:expr, ?alt:expr)} => {?cons}
{test(false, ?cons:expr, ?alt:expr)} => {?alt}
end macro;
define macro lookup
{lookup(?n:expr; empty)} => {Crash}
{lookup(?n:expr; ?m:expr, ?denot:expr, ?r:*)} =>
{test(equal(?n, ?m), ?denot, lookup(?n; ?r))}
end macro;
define macro eval
{eval(var(?n:expr); ?r:expr)} => {lookup(?n; ?r)}
{eval(lambda(?n:expr, ?b:expr); ?r:*)} => {closure(?n, ?b, ?r)}
{eval(app(closure(?n1:expr, ?b1:expr, ?r1:*),
closure(?n2:expr, ?b2:expr, ?r2:*)); ?r)} =>
{eval(?b1; ?n1, closure(?n2, ?b2, ?r2), ?r1)}
{eval(app(?f:expr, ?arg:expr); ?r:*)} =>
{eval(app(eval(?f; ?r), eval(?arg; ?r)); ?r)}
end macro;
> Also, is it possible for a Dylan macro to loop infinitely? I'm
> thinking of something like:
>
> define macro buggy-macro
> { } => { format-out("buggy macro\n"); };
> end;
Try this instead:
define macro loop
{loop()} => {loop()}
end macro;
Neel
Colin Walters
> Dylan macros are definitely Turing complete. Here's an (untested)
> lambda calculus implementation as a macro:
Okay, very cool. So the generated code would be your answer.
One related question; the Dylan macro system has no standard way to
perform arbitrary computation in a way that could usefully affect the
compiler process, correct? Stated another way, all you can do is
generate Dylan code, not run it.
An example of a "useful" way of affecting the compiler process would
be to change an in-memory variable, or perform I/O. For this purpose,
looping infinitely is not useful.
I do note that in the Gwydion Dylan implementation, some macros (such
as :=), seem to call functions in the compiler to compute their
expansion:
define macro \:=
{ \:= (?place:expression, ?value:expression) }
=> make-assignment({ ?place }, { ?value })
end;
This is not a standard part of the Dylan macro system, correct? My
reading of the "Templates" section of the DRM seems to suggest so,
but I'm not completely sure.
> Try this instead:
>
> define macro loop
> {loop()} => {loop()}
> end macro;
Aah. Of course. If the macro expansion can be recursive, then you
have an easy way to loop infinitely. Thanks.
Bruce Hoult
Colin Walters <wal...@verbum.org> wrote:
> I do note that in the Gwydion Dylan implementation, some macros (such
> as :=), seem to call functions in the compiler to compute their
> expansion:
>
> define macro \:=
> { \:= (?place:expression, ?value:expression) }
> => make-assignment({ ?place }, { ?value })
> end;
>
> This is not a standard part of the Dylan macro system, correct? My
> reading of the "Templates" section of the DRM seems to suggest so,
> but I'm not completely sure.
That's not part of the Dylan spec, but you've got to generate your parse
tree *somewhere*. In many compilers you'd find almost exactly the same
thing as a parse rule in a yacc file. In Dylan, the parser and macro
expansion interact too much to do that.
-- Bruce
Colin Walters
> That's not part of the Dylan spec, but you've got to generate your
> parse tree *somewhere*. In many compilers you'd find almost exactly
> the same thing as a parse rule in a yacc file. In Dylan, the parser
> and macro expansion interact too much to do that.
Ok, I understand that. I just wanted to make sure that it was in fact
not part of the standard; this is a large conceptual difference
between Lisp macros and Dylan macros.
Bruce Hoult
Colin Walters <wal...@debian.org> wrote:
Really?
What does the "setf" macro expand to in your favourite Lisp compiler?
-- Bruce
Colin Walters
> Really?
>
> What does the "setf" macro expand to in your favourite Lisp compiler?
Sorry. I meant that Lisp's `defmacro' can perform arbitrary
computation in Lisp to compute a macro expansion, while the Dylan
macro system appears to be restricted to recursive pattern matching.
This is an important conceptual difference between the two, I think.
I note in my paper that despite this, the Dylan macro system appears
to be able to express the majority of transformations that defmacro
can.
I'm not talking about the Dylan := macro or CL's `setf' specifically.
Bruce Hoult
Colin Walters <wal...@verbum.org> wrote:
> Bruce Hoult <br...@hoult.org> writes:
>
> > Really?
> >
> > What does the "setf" macro expand to in your favourite Lisp compiler?
>
> Sorry. I meant that Lisp's `defmacro' can perform arbitrary
> computation in Lisp to compute a macro expansion, while the Dylan
> macro system appears to be restricted to recursive pattern matching.
> This is an important conceptual difference between the two, I think.
I agree.
> I note in my paper that despite this, the Dylan macro system appears
> to be able to express the majority of transformations that defmacro
> can.
Perhaps substitute "the majority of transformations that defmacro is
commonly used for"?
There are certainly useful things that you can't do wth Dylan macros,
but perhaps they are uncommon in practice.
Clearly Dylan can duplicate the CL "loop" macro.
Someone suggested a couple of years ago that Dylan can't implement the
"series" macro. I downloaded the source code for "series" but it was so
extensive that I didn't have the time to attempt to translate it.
Something that Dylan macros clearly can't do conveniently is arithmetic.
They can generate expressions that the compiler will
compile-time-evaluate later on, but they can't make decisions or control
loops based on that arithmetic. It's possible to fake that using Church
numerals or Turing Machine methods, but that's a pain. It would be
possible to implement decimal arithmetic within the macro system, but
once again that would be a pain. And somewhat pointless.
I've started going through the newly-released online copy of _On Lisp_,
noting what there can and can't be applied to Dylan. Unfortunately
progress is slow, due to work commitments at the moment.
There is apparently a procedural macro system in
Harlequin/Functional-Objects Dylan, which is used internally in the
system but not documented.
My own philosophy on the use of macros is that they are not for doing
computation, but merely for rearranging the surface syntax so that the
programmer can write something in syntax convenient to their application
domain, and that is transformed into concrete code that implements their
abstraction. If this process requires optimization then that should
take place in the compiler proper.
I find the ability for a single macro to expand into methods added to
any number of Generic Functions to be incredibly powerful. I don't
think this is matched by any other language other than CL. To me this
is key to a large part of the power of Dylan macros and, combined with
Dylan's sealing declarations and a powerful optimizing compiler, can do
many things efficiently that would otherwise require full programmable
code generation such as "aspects".
-- Bruce
Colin Walters
> Perhaps substitute "the majority of transformations that defmacro is
> commonly used for"?
Yes, that's what I meant.
> There are certainly useful things that you can't do wth Dylan macros,
> but perhaps they are uncommon in practice.
One cool thing that I've seen done with CL macros is mixing HTML with
Lisp code. For example, from examples/chat.cl in the allegroserve
source code:
(defun quick-return-master (req ent)
;; quick hack to get us to the master controller while debugging
(if* (null *master-controller*)
then (ancient-link-error req ent)
else (with-http-response (req ent)
(with-http-body (req ent)
(html
(:html
(:body "The master controllers is "
((:a href
(format nil "setup-chat?s=~a"
(secret-key *master-controller*)))
"here"))))))))
I had one experience with programming PHP, and it left me with a very
bad taste in my mouth. Having a real macro system which allows one to
embed languages (e.g. HTML) like this is a huge win, I think.
Can the Dylan macro system express something like this? I can't see
offhand how to implement it...
> I've started going through the newly-released online copy of _On
> Lisp_, noting what there can and can't be applied to Dylan.
> Unfortunately progress is slow, due to work commitments at the
> moment.
That's a great book. He covers Lisp macros *extensively*. I learned
a lot from it.
> My own philosophy on the use of macros is that they are not for
> doing computation, but merely for rearranging the surface syntax so
> that the programmer can write something in syntax convenient to
> their application domain, and that is transformed into concrete code
> that implements their abstraction. If this process requires
> optimization then that should take place in the compiler proper.
I think we're continually discovering new uses for a macro system like
Lisp's. I really do like Dylan's system though too; it is pretty easy
to work with, given that Dylan has a much more complex syntax than
Lisp.
> I find the ability for a single macro to expand into methods added to
> any number of Generic Functions to be incredibly powerful.
Definitely; I do think though that the abstraction gained by generic
functions/object orientation is generally orthogonal to the power
gained by a real macro system. Thus it makes sense that combining
the two would be a win.
Bruce Hoult
Colin Walters <wal...@debian.org> wrote:
It depends what you want this to compile into. If you want all the HTML
elements to become static text then you're out of luck. I can't see any
reason, though, that you can't make a Dylan macro that accepts this sort
of syntax and outputs a suitably nested list, or some code that builds a
tree at runtime. You'd then have a function that walked the tree to
actually emit the HTML.
As far as Syntax goes, S-expressions are pretty much just a rational
format for HTML (and XML) with less typing and redundancy anyway, so you
might well want to keep that aspect.
If you want to see perhaps the best current example of what can be done
with the Dylan macro system, see David Lichteblau implementation of the
"META" parsing library.
-- Bruce
Sean Case
Colin Walters <wal...@verbum.org> wrote:
> Sorry. I meant that Lisp's `defmacro' can perform arbitrary
> computation in Lisp to compute a macro expansion, while the Dylan
> macro system appears to be restricted to recursive pattern matching.
The Dylan macro system seems to owe a lot to Scheme hygienic macros,
which wouldn't be terribly surprising.
Sean Case
--
Sean Case g...@zip.com.au
Code is an illusion. Only assertions are real.
Chris Double
> I can't see any reason, though, that you can't make a Dylan macro
> that accepts this sort of syntax and outputs a suitably nested list,
> or some code that builds a tree at runtime. You'd then have a
> function that walked the tree to actually emit the HTML.
I do exactly this in my Dylanlibs [1] libraries. See the dom-builder
library. Code using it looks like:
with-standard-http-result(stream)
let dom =
with-dom-builder()
(html
(head
(title ["Test HTTP Server"])),
(body
(p ["Testing the Dylan HTTP Server."]),
(p ((a href: "/formtest1") ["Form test 1"])),
(p ((a href: "/formtest2") ["Form test 2"])),
(p ["Counter: "], [*counter* := *counter* + 1])))
end;
print-html(dom, stream);
You can do loops and such:
(p
((table border: 1,
cellpadding: 3)
(tr
(th ["Update Time"]),
(th ["Close Time"]),
(th ["Pool"]),
[for(n from 0 below odds.first.odds-snapshot-dividends.size)
with-dom-builder(*current-dom-element*)
(th [format-to-string("%d", n + 1)])
end with-dom-builder;
end for]),
[for(os in odds, roi in roi-sequence)
with-dom-builder(*current-dom-element*)
(tr
(td [time-to-string(os.odds-snapshot-update-time)]),
(td [time-to-string(os.odds-snapshot-close-time)]),
(td [money-to-string(os.odds-snapshot-pool-size)]),
[for(r in roi)
with-dom-builder(*current-dom-element*)
(td [float-to-formatted-string(r, decimal-places: 3)])
end with-dom-builder;
end for])
end with-dom-builder;
end for]))
It gets a bit unweildy for big things but you can factor things out
into their own functions quite well. I also generate SVG dynamically
from a Dylan web server using this.
with-dom-builder generates a simple document object model with
elements, attributes, etc. I have various 'walkers' that walk through
this model generating HTML, XML, SVG or whatever.
Chris.
--
http://www.double.co.nz/dylan
Andreas Bogk
> Ok, I understand that. I just wanted to make sure that it was in fact
> not part of the standard; this is a large conceptual difference
> between Lisp macros and Dylan macros.
In fact, the big difference between Lisp macros and Dylan macros is
that Dylan is infix. Not supporting procedural macros was an
arbitrary design choice, and Functional Developer acutally mostly
consists of procedural macros. Procedural macros, together with
method combination, are on my wish list for a hypthetical Dylan-NG.
I think the big news of the Dylan macro system is showing that
powerful macros an infix syntax do not contradict each other.
Andreas
--
"In my eyes it is never a crime to steal knowledge. It is a good
theft. The pirate of knowledge is a good pirate."
(Michel Serres)
Andreas Bogk
> Ok, I understand that. I just wanted to make sure that it was in fact
> not part of the standard; this is a large conceptual difference
> between Lisp macros and Dylan macros.
In fact, the big difference between Lisp macros and Dylan macros is
that Dylan is infix. Not supporting procedural macros was an
arbitrary design choice, and Functional Developer acutally mostly
consists of procedural macros. Procedural macros, together with
method combination, are on my wish list for a hypthetical Dylan-NG.
I think the big news of the Dylan macro system is showing that
powerful macros and infix syntax do not contradict each other.
Chris Double
> Procedural macros, together with method combination, are on my wish
> list for a hypthetical Dylan-NG.
I agree with the above. I'd add either removing sealing or changing
the defaults to be open rather than sealed. The number of times I've
wanted to extend something only to find that sealing has prevented
me...
That's not to say that Dylan isn't perfectly usable and effective as
it is right now of course. Functional Developer is an excellent
development environment for Win32 for example. Gwydion Dylan is also
becoming an excellent system.
Chris.
--
http://www.double.co.nz/dylan
Chris Double
> I agree with the above. I'd add either removing sealing or changing
> the defaults to be open rather than sealed. The number of times I've
> wanted to extend something only to find that sealing has prevented
> me...
I should add that this is because the sorts of things I do in Dylan
don't require much speed. I'm sure if I was doing things that required
much optimisation from the compiler then I'd be a big sealing
advocate.
Chris.
--
http://www.double.co.nz/dylan
Rainer Joswig
> Colin Walters <wal...@debian.org> writes:
>
> > Ok, I understand that. I just wanted to make sure that it was in fact
> > not part of the standard; this is a large conceptual difference
> > between Lisp macros and Dylan macros.
>
> In fact, the big difference between Lisp macros and Dylan macros is
> that Dylan is infix. Not supporting procedural macros was an
> arbitrary design choice,
The big difference between Dylan-Macros and Common-Lisp-Macros is
that Dylan-Macros are not procedural.
Rainer Joswig
Bruce Hoult <br...@hoult.org> wrote:
> My own philosophy on the use of macros is that they are not for doing
> computation, but merely for rearranging the surface syntax so that the
> programmer can write something in syntax convenient to their application
> domain, and that is transformed into concrete code that implements their
> abstraction. If this process requires optimization then that should
> take place in the compiler proper.
I see some uses of macros.
For non-top-level macros I often want to manipulate the
identifier names. This is for example not possible
with Scheme-Macros. They are only supporting little
rewriting of list structures - but not for example
of names. Example (pardon the prefix syntax):
(with-foo "bar" (baz)) -> (let ((foo-bar ...)) ... (baz))
In Scheme I can't compute the foo-bar symbol via
macros.
Another thing that's important (especially for top-level
macros) is that Macros can generate compile-time side-effects,
which are controlled by the programmer.
Example
(define-function foo (bar) ...)
Expands to (defun foo (bar) ...)
and could have, for example, the side effect to enter the
function into a database at compile time. This comes very
handy, for example, when you develop new (sub-)languages
on top of CL and want to do some programming environment
stuff on your own. This is also interesting when
you want to lookup definitions at compile-time from
a database (done with FFIs, foreign function interfaces).
Etc.
Bruce Hoult
Rainer Joswig <jos...@lispmachine.de> wrote:
> In article <bruce-E18C63....@copper.ipg.tsnz.net>,
> Bruce Hoult <br...@hoult.org> wrote:
>
> > My own philosophy on the use of macros is that they are not for doing
> > computation, but merely for rearranging the surface syntax so that the
> > programmer can write something in syntax convenient to their application
> > domain, and that is transformed into concrete code that implements their
> > abstraction. If this process requires optimization then that should
> > take place in the compiler proper.
>
> I see some uses of macros.
>
> For non-top-level macros I often want to manipulate the
> identifier names. This is for example not possible
> with Scheme-Macros. They are only supporting little
> rewriting of list structures - but not for example
> of names. Example (pardon the prefix syntax):
>
> (with-foo "bar" (baz)) -> (let ((foo-bar ...)) ... (baz))
>
> In Scheme I can't compute the foo-bar symbol via
> macros.
You can in Dylan.
> Another thing that's important (especially for top-level
> macros) is that Macros can generate compile-time side-effects,
> which are controlled by the programmer.
>
> Example
>
> (define-function foo (bar) ...)
>
> Expands to (defun foo (bar) ...)
That's easy in Dylan.
> and could have, for example, the side effect to enter the
> function into a database at compile time. This comes very
> handy, for example, when you develop new (sub-)languages
> on top of CL and want to do some programming environment
> stuff on your own. This is also interesting when
> you want to lookup definitions at compile-time from
> a database (done with FFIs, foreign function interfaces).
> Etc.
You can't do these things at compile-time in Dylan. You can however do
them at program load time.
There is also a design for adding procedural macros pretty seamlessly to
the current pattern replacement macros. See:
http://www.ai.mit.edu/~jrb/Projects/dexprs.pdf
-- Bruce
Rainer Joswig
Bruce Hoult <br...@hoult.org> wrote:
> > (with-foo "bar" (baz)) -> (let ((foo-bar ...)) ... (baz))
> >
> > In Scheme I can't compute the foo-bar symbol via
> > macros.
>
> You can in Dylan.
What would it look like?
> > Another thing that's important (especially for top-level
> > macros) is that Macros can generate compile-time side-effects,
> > which are controlled by the programmer.
> >
> > Example
> >
> > (define-function foo (bar) ...)
> >
> > Expands to (defun foo (bar) ...)
>
> That's easy in Dylan.
;-) Yeah, the difficult part is described in the paragraph below:
> > and could have, for example, the side effect to enter the
> > function into a database at compile time. This comes very
> > handy, for example, when you develop new (sub-)languages
> > on top of CL and want to do some programming environment
> > stuff on your own. This is also interesting when
> > you want to lookup definitions at compile-time from
> > a database (done with FFIs, foreign function interfaces).
> > Etc.
>
> You can't do these things at compile-time in Dylan. You can however do
> them at program load time.
Which is not really the same.
> There is also a design for adding procedural macros pretty seamlessly to
> the current pattern replacement macros. See:
>
> http://www.ai.mit.edu/~jrb/Projects/dexprs.pdf
Thanks for the reference.
Haven't (yet) read it, what is the approach? Does one have
full Dylan available at compile-time?
Bruce Hoult
Rainer Joswig <jos...@lispmachine.de> wrote:
> In article <bruce-63512A....@copper.ipg.tsnz.net>,
> Bruce Hoult <br...@hoult.org> wrote:
>
> > > (with-foo "bar" (baz)) -> (let ((foo-bar ...)) ... (baz))
> > >
> > > In Scheme I can't compute the foo-bar symbol via
> > > macros.
> >
> > You can in Dylan.
>
> What would it look like?
This, for example:
define macro with-foo
{with-foo ?name ?body end}
=> {let "foo-" ## ?name = ...; ... ?body}
end;
with-foo bar baz() end;
> > > and could have, for example, the side effect to enter the
> > > function into a database at compile time. This comes very
> > > handy, for example, when you develop new (sub-)languages
> > > on top of CL and want to do some programming environment
> > > stuff on your own. This is also interesting when
> > > you want to lookup definitions at compile-time from
> > > a database (done with FFIs, foreign function interfaces).
> > > Etc.
> >
> > You can't do these things at compile-time in Dylan. You can however do
> > them at program load time.
>
> Which is not really the same.
Sometimes it suffices, sometimes not.
> > There is also a design for adding procedural macros pretty seamlessly to
> > the current pattern replacement macros. See:
> >
> > http://www.ai.mit.edu/~jrb/Projects/dexprs.pdf
>
> Thanks for the reference.
>
> Haven't (yet) read it, what is the approach? Does one have
> full Dylan available at compile-time?
When a procedural macro is encountered, it is immediately compiled into
a DLL and then loaded into the compiler. I believe the full language is
available.
-- Bruce
Doug Orleans
> For non-top-level macros I often want to manipulate the
> identifier names. This is for example not possible
> with Scheme-Macros. They are only supporting little
> rewriting of list structures - but not for example
> of names. Example (pardon the prefix syntax):
>
> (with-foo "bar" (baz)) -> (let ((foo-bar ...)) ... (baz))
>
> In Scheme I can't compute the foo-bar symbol via
> macros.
You can't do this with R5RS "syntax-rules", but you can do it with
"syntax-case", which exists in Chez and PLT implementations.
http://www.scheme.com/tspl2d/syntax.html#g2270
http://download.plt-scheme.org/doc/mzscheme/mzscheme-Z-H-11.html#%_sec_11.2.1
I don't know enough about Dylan macros to say if they are more like
"syntax-rules" or "syntax-case"; I suspect they sit somewhere in
between.
Jonathan Bachrach
> Hello,
>
> I'm doing a bit of research on the Dylan macro system, and I must say
> I've been very impressed! It certainly seems to capture the vast
> majority of transformations that typical Lisp macros do, but in a
> clean and elegant fashion.
in keith playford and my paper:
www.jbot.org/Projects/dexprs.pdf
we discuss (among other things) the limits of dylan's macro system,
which we call a rewrite rule only macro system, and propose one
extension, called template calls, that adds a significant amount of
expressiveness and clarity for certain macros (that would otherwise be
clumsy to write).
jonathan
Colin Walters
[ catching up on this newsgroup again ]
Chris Double <ch...@double.co.nz> writes:
> I do exactly this in my Dylanlibs [1] libraries. See the dom-builder
> library. Code using it looks like:
>
> with-standard-http-result(stream)
> let dom =
> with-dom-builder()
> (html
> (head
> (title ["Test HTTP Server"])),
> (body
> (p ["Testing the Dylan HTTP Server."]),
> (p ((a href: "/formtest1") ["Form test 1"])),
> (p ((a href: "/formtest2") ["Form test 2"])),
> (p ["Counter: "], [*counter* := *counter* + 1])))
> end;
> print-html(dom, stream);
That is very, very cool!
The next time I have to do some dynamic web stuff I am definitely
going to look into using your library.