Re: are dylan macros Turing-complete?

[address@hidden (Neelakantan Krishnaswami)]

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