Tiny Lambda Expression processor in D

tinylambda.d

import std.algorithm,
       std.format,
       std.string,
       std.array,
       std.stdio;

interface Term {
  string toString();
  Term apply(Term);
  Term apply();
}

class BoundVar : Term {
  string name;
  this (string name) { this.name = name; }
  override string toString() { return this.name; }
  Term apply(Term x) { writeln("-> ", x); return x; }
  Term apply()       { writeln("-> ", this); return this; }
}

class FreeVar : Term {
  string name;
  this (string name) { this.name = name; }
  override string toString() { return this.name; }
  Term apply(Term x) { writeln("-> ", x); return x; }
  Term apply()       { writeln("-> ", this); return this; }
}

class Abstraction : Term {
  Term[] args;
  Term[] _body;

  this (Term[] args, Term[] _body) {
    this.args = args;
    this._body = _body;
  }

  Term apply() { writeln("-> ", this); return this; }

  Term apply(Term arg) {
    if (this.args.length) {
      string key = {
        Term t = this.args[0];
        if (cast(BoundVar)t is null) {
          throw new Error("Given term is not a BoundVar");
        }

        return (cast(BoundVar)t).name;
      }();

      if (this.args.length == 1) {
        this.args = [];
      } else {
        this.args = this.args[1..$];
      }

      foreach (ref term; this._body) {
        if ((cast(BoundVar)term) !is null) {
          string k = (cast(BoundVar)term).name;

          if (k == key) {
            term = arg;
          }
        } else if ((cast(App)term) !is null) {
          Term eval(Term term) {
            App a = cast(App)term;
            Term ta = a.a,
                 tb = a.b;

            foreach (t; [&ta, &tb]) {
              if ((cast(BoundVar)*t) !is null) {
                string k = (cast(BoundVar)*t).name;

                if (k == key) {
                  *t = arg;
                }
              } else if ((cast(App)*t) !is null) {
                *t = eval(*t);
              }
            }
            
            return new App(ta, tb);
          }

          term = eval(term);
        }
      }

      writefln("->[%s := %s] %s", key, arg, this.toString);

      return this;
    } else {
      throw new Error("Ω＼ζ°)ﾁｰﾝ");
    }
  }

  override string toString() {
    return "(%s%s)".format(this.args.map!(term => "\\%s.".format(term.toString)).join,
                            this._body.map!(term => term.toString).join(" "));
  }

  void dumpinfo() {
    writeln("this.args  : ", this.args);
    writeln("this._body : ", this._body);
  }
}

class App : Term {
  Term a, b;

  this (Term a, Term b) { this.a = a; this.b = b; }
  override string toString() {
    return "(%s %s)".format(a.toString, b.toString);
  }
  Term apply(Term x) { writeln("->", x); return x; }
  Term apply() {
    auto ret = this.a.apply(b);
    writeln("-> ", ret);
    return ret;
  }
}

Term finalize(Term term) {
  if ((cast(Abstraction)term) !is null) {
    Abstraction abst = cast(Abstraction)term;
    if (abst.args.length == 0) {
      foreach (ref t; abst._body) {
        if ((cast(App)t) !is null) {
          App app = cast(App)t;
          t = t.apply;
        }
      }

      return abst;
    } else {
      return term;
    }
  } else {
    return term;
  }
}

void main() {
  // \x.\y.x
  auto abst = new Abstraction([new BoundVar("x"), new BoundVar("y")], [new BoundVar("x")]);

  abst.writeln;
  // (\x.\y.x) (\z.z) b
  abst.apply(new Abstraction([new BoundVar("z")], [new BoundVar("z")]))
      .apply(new FreeVar("b"))
      .apply
      .finalize
      .writeln;


  writeln("----");
  // \x.\y.\z.x z (y z)
  auto abst2 = new Abstraction(
      cast(Term[])[new BoundVar("x"), new BoundVar("y"), new BoundVar("z")],
      cast(Term[])[new BoundVar("x"), new BoundVar("z"), new App(new BoundVar("y"), new BoundVar("z"))]
      );

  abst2.writeln;
  // (\x.\y.\z.x z (y z)) a (\x.\y.x) c
  abst2.apply(new FreeVar("a"))
       .apply(new Abstraction([new BoundVar("x"), new BoundVar("y")], [new BoundVar("x")]))
       .apply(new FreeVar("c"))
       .apply
       .finalize
       .writeln;


  writeln("----");
  // \x.\y.x
  auto abst3 = new Abstraction([new BoundVar("x"), new BoundVar("y")], [new BoundVar("x")]);
  // \x.x x c
  auto t = new Abstraction(
      cast(Term[])[new BoundVar("x")],
      cast(Term[])[new BoundVar("x"), new BoundVar("x"), new FreeVar("c")]);
  // (\x.\y.x) a ((\x.x x c) (\x.x x c))
  abst3.apply(new FreeVar("a"))
       .apply(new App(t, t))
       .apply
       .finalize
       .writeln;


  writeln("----");  
  // (\m.\n.\s.\z.m s (n s z))
  auto abst4 = new Abstraction(
      cast(Term[])[new BoundVar("m"), new BoundVar("n"), new BoundVar("s"), new BoundVar("z")],
      cast(Term[])[new BoundVar("m"), new BoundVar("s"), new App(new App(new BoundVar("n"), new BoundVar("s")), new BoundVar("z"))]);
  abst4.writeln;
  //(\m.\n.\s.\z.m s (n s z)) (\x.\y.x (x y)) (\x.\y.x (x (x y)))
  abst4.apply(new Abstraction(cast(Term[])[new BoundVar("x"), new BoundVar("y")],
                              cast(Term[])[new BoundVar("x"), new App(new BoundVar("x"), new BoundVar("y"))]))
       .apply(new Abstraction(cast(Term[])[new BoundVar("x"), new BoundVar("y")],
                              cast(Term[])[new BoundVar("x"), new App(new BoundVar("x"),
                                                                      new App(new BoundVar("x"), new BoundVar("y")))]))
       .apply
       .finalize
       .writeln;
}