Unlambda-Interpreter


Nachdem ich schon einmal Brainfuck implementiert habe, nun eine Schwenk ins wirklich Bizarre: Unlambda ist eine faszinierende, verwirrende Sprache, die ich noch nicht ganz verstehe. Alles ist eine Funktion, Dinge wie Daten, Variablen oder irgendwelche Kontrollfluss-Konstrukte sucht man vergeblich.

Auch die Funktionsweise des sehr übersichtlichen Java-Interpreters verstehe ich nicht wirklich. Aber das hat mich nicht daran gehindert, den Code nach Scala zu portieren und nach allen Regeln der Kunst zu obfuscaten:

/* Unlambda Interpreter
 * based on David A. Madore's Java-Interpreter contained in
 * ftp://quatramaran.ens.fr/pub/madore/unlambda/unlambda-2.0.0.tar.gz
 * licensed under GPL2
 * uses Scala 2.8
 */
package unlambda

trait DFunction
trait Task extends Function0[Task]
trait Func extends Function2[Func, Cont, Task]
trait Expr extends Function1[Cont, Task]
trait Cont extends Function1[Func, Task]

class ProgramOverException(s: String) extends Exception
class UsageException(s: String) extends Exception
class ParseException(s: String) extends Exception

object Execute {

  implicit def fn2func(fn: Function2[Func, Cont, Task]): Func = new Func{
    def apply(f:Func, c:Cont):Task = fn(f,c)
  }
  implicit def fn2expr(fn: Function1[Cont, Task]): Expr = new Expr{
    def apply(c:Cont):Task = fn(c)
  }
  implicit def fn2cont(fn: Function1[Func, Task]): Cont = new Cont{
    def apply(f:Func):Task = fn(f)
  }
  implicit def fn2Task(fn: Function0[Task]):Task = new Task {
    def apply():Task = fn()
  }

  var output:java.io.PrintStream = _
  var input: java.io.InputStream = _
  var inCh = -1

  def i(rand: Func, cont: Cont) = cont(rand)
  def dot(ch:Char)(rand: Func, cont: Cont) = {
    output.print(ch)
    output.flush()
    cont(rand)
  }
  def k(rand: Func, cont: Cont):Task = cont((r: Func, c: Cont) => c(rand))
  def contFunc(cont:Cont)(value: Func, c: Cont):Task = cont(value)
  def c(rand: Func, cont: Cont):Task = appTask(rand, contFunc(cont) _ , cont) _
  def d1(promise: Expr)(rand: Func, cont: Cont):Task = {
    val ncont: Cont = delCont(rand, cont) _
    evalTask(promise, ncont) _
  }
  def e(rand: Func, cont: Cont):Task = finalTask _
  def at(rand: Func, cont: Cont):Task = {
    try {
      inCh = input.read()
    } catch {
      case _:java.io.IOException => inCh = -1
    }
    val bval:Func = if (inCh != -1) i _ else v
    appTask(rand, bval, cont) _
  }
  def pipe(rand: Func, cont: Cont):Task = {
    val bval:Func = if(inCh != -1) dot(inCh.toChar) _ else v
    appTask(rand, bval, cont) _
  }
  def ques(ch: Char)(rand: Func, cont: Cont):Task =  {
    val bval:Func = if(ch == inCh) i _ else v
    appTask(rand, bval, cont) _
  }
  def s(rand: Func, cont: Cont):Task = {
    def s1(x: Func)(rand: Func, cont: Cont):Task = {
      def s2(x: Func, y: Func)(rand: Func, cont: Cont):Task =  {
        val rande:Expr = funcExpr(rand) _
        evalTask(appExpr(appExpr(funcExpr(x) _, rande) _,
                         appExpr(funcExpr(y) _, rande) _) _, cont)_
      }
      cont(s2(x, rand) _)
    }
    cont(s1(rand) _)
  }
  def v = new Func { def apply(rand: Func, cont: Cont):Task = cont(this) }
  def d = new Func with DFunction {
    def apply(rand: Func, cont: Cont):Task = cont(d1(funcExpr(rand) _) _)
  }

  def funcExpr(fun: Func)(cont: Cont):Task = cont(fun)
  def appExpr(rator: Expr, rand: Expr)(cont: Cont):Task = {
    val ncont: Cont = app1Cont(rand, cont) _
    evalTask(rator, ncont) _
  }

  def delCont(rand: Func, cont: Cont)(value: Func):Task =  appTask(value, rand, cont) _
  def appCont(erator: Func, cont: Cont)(value: Func):Task = appTask(erator, value, cont) _
  def app1Cont(rand: Expr, cont: Cont)(value: Func):Task = app1Task(value, rand, cont) _
  def finalCont(value: Func):Task = finalTask _

  def evalTask(expr: Expr, cont: Cont)():Task = () => expr(cont)
  def appTask(erator: Func, erand: Func, cont: Cont)():Task = () => erator(erand, cont)
  def app1Task(erator: Func, rand: Expr, cont: Cont)():Task = () =>
  if ( erator.isInstanceOf[DFunction]) cont(d1(rand) _)
  else {
    val ncont:Cont = appCont(erator, cont) _
    rand(ncont)
  }
  def finalTask():Task = () => throw new ProgramOverException("Execution terminated.")

  class Parser(input: java.io.InputStream) {

    def parse(): Expr = {
      var ch = -1
      do {
        ch = input.read()
        if (ch == '#')
          while ( ch != '\n' && ch != -1 )
            ch = input.read()
      } while ( " \n\r\t".contains(ch))
      if(ch == -1) throw new ParseException("Unexpected end of file")
      else ch.toChar.toLower match {
        case '`' => appExpr(parse(), parse()) _
        case 'i' => funcExpr(i _) _
        case 'k' => funcExpr(k _) _
        case 's' => funcExpr(s _) _
        case 'v' => funcExpr(v) _
        case 'd' => funcExpr(d) _
        case 'c' => funcExpr(c _) _
        case 'e' => funcExpr(e _) _
        case 'r' => funcExpr(dot('\n') _) _
        case '.' => val ch2 = input.read()
          if (ch2 == -1) throw new ParseException ("Unexpected end of file")
          else funcExpr(dot(ch2.toChar) _) _
        case '@' => funcExpr(at _) _
        case '?' => val ch2 = input.read()
          if (ch2 == -1) throw new ParseException ("Unexpected end of file")
          else funcExpr(ques(ch2.toChar) _) _
        case  '|' => funcExpr(pipe _) _
        case _ => throw new ParseException("Character not recognized")
      }
    }
  }

  def main (args: Array[String]) {
    if(args.length > 1) throw new UsageException("Expected zero or one argument")
    val parser = new Parser(
      if (args.length == 0) java.lang.System.in
      else new java.io.FileInputStream(args(0))
    )
    input = java.lang.System.in
    output = java.lang.System.out
    try {
      def loop(task:Task):Task = loop(task())
      loop(evalTask(parser.parse(), finalCont _) _)
    } catch {
      case _:ProgramOverException =>  // So what?
    }
  }
}

Bisher liefen alle getesteten Beispiele (Fibonacci-Zahlen, Hello-World-Schleife, kürzester Quine) ohne Probleme. Das heisst natürlich noch lange nicht, dass dieses Monster tasächlich bugfrei ist…

Ob es angesichts der verwirrend vielen Unterstriche und der impliziten Konvertierungen wirklich eine gute Idee war, die Klassen Function, Task, Expression, Continuation mit Scala-Funktionen zu realisieren? Für Anregungen aller Art wäre ich dankbar.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s