[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: are dylan macros Turing-complete?
Colin Walters <walters@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.
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