Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import scala.annotation.tailrec
sealed abstract class Var {
def walk(subst: Subst): Var = {
@tailrec
def go(v: Var, stack: List[Var], acc: Option[Var]): Var =
v match {
case Unbound(k) =>
subst.get(k) match {
case None => acc.fold(v)(u => Cons(u, v))
case Some(v) => go(v, stack, acc)
}
case Cons(h, t) =>
go(h, t :: stack, acc)
case _ =>
stack match {
case Nil => acc.fold(v)(u => Cons(u, v))
case x :: xs => go(x, xs, acc.map(u => Cons(u, v)).orElse(Some(v)))
}
}
go(this, Nil, None)
}
}
case class Bound(value: Any) extends Var
case class Unbound(id: Long) extends Var
case class Cons(head: Var, tail: Var) extends Var
@halcat0x15a

This comment has been minimized.

Copy link
Owner Author

@halcat0x15a halcat0x15a commented Jan 10, 2016

def walk(subst: Subst): Var = {
    //@tailrec                                                                                                                                                                                                     
    def go(v: Var, cont: Var => Var): Var =
      v match {
        case Unbound(k) =>
          subst.get(k) match {
            case None => cont(v)
            case Some(v) => go(v, cont)
          }
        case Cons(h, t) => go(h, h => go(t, t => cont(Cons(h, t))))
        case _ => cont(v)
      }
    go(this, v => v)
  }
@lyricallogical

This comment has been minimized.

Copy link

@lyricallogical lyricallogical commented Jan 10, 2016

trait Subst { def get(v: Long): Option[Var] }

type GoType = (Var, (Var => Var)) => Var
def fix(f: GoType => GoType)(v: Var, cont: Var => Var): Var = {
  f(fix(f))(v, cont)
}

def walk(subst: Subst): Var = {
  @scala.annotation.tailrec
  def go(self: (Var, (Var => Var)) => Var)(v: Var, cont: Var => Var): Var = {
    v match {
      case Unbound(k) =>
        subst.get(k) match {
          case None => cont(v)
          case Some(v) => go(self)(v, cont)
        }
      case Cons(h, t) => go(self)(h, h => self(t, t => Cons(h, t)))
      case _ => cont(v)
    }
  }

  fix(go)(this, Id)
}
@lyricallogical

This comment has been minimized.

Copy link

@lyricallogical lyricallogical commented Jan 10, 2016

      case Cons(h, t) => go(self)(h, h => self(t, t => Cons(h, t)))

継続内の self は普通にメソッド呼び出しするのでスタック深くなっちゃうけど、そんな大量に Cons ないでしょ、というつもりで、とりあえず他の箇所は goto になるようにコンパイラを言いくるめました。
Cons だらけだと普通にスタックあふれます。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment