Lambda.scala

sealed trait Lambda

case class Var(name: String) extends Lambda {
  override def toString: String = s"{$name}"
}

case class Abs(name: String, lambda: Lambda) extends Lambda {
  override def toString: String = s"λ{$name}(${lambda.toString})"
}

case class Tr(lft: Lambda, rgt: Lambda) extends Lambda {
  override def toString: String = s"(${lft.toString}${rgt.toString})"
}

object S extends Lambda {
  override def toString: String = "S"
}

object K extends Lambda {
  override def toString: String = "K"
}

object I extends Lambda {
  override def toString: String = "I"
}

object Consts {
  val B: Lambda = Tr(Tr(S, Tr(K, S)), K) // S(KS)K

  val C: Lambda = Tr(Tr(S, Tr(Tr(B, B), S)), Tr(K, K)) // S(BBS)(KK)
}

Main.scala

object Main {
  def main(args: Array[String]): Unit = {
    println(translate(Abs("x", Abs("y", Tr(Var("y"), Tr(Var("y"), Var("x")))))))
    // ((((S(KS))K)(SI))((((S(KS))K)(((S((((S(KS))K)((S(KS))K))S))(KK))I))I))
  }

  def translate(lambda: Lambda): Lambda = {
    lambda match {
      case Var(name) => Var(name)
      case S => S
      case K => K
      case I => I
      case Tr(lft, rgt) => Tr(translate(lft), translate(rgt))
      case Abs(x, lambda) =>
        val outerVar = Var(x)
        if(free(lambda, outerVar)) {
          return Tr(K, translate(lambda))
        }

        lambda match {
          case Var(nestedName) =>
            if(x.equals(nestedName)) {
              I
            } else {
              throw new IllegalStateException("single var reduction did not match I")
            }

          case Abs(y, nestedLambda) =>
            if(refersTo(nestedLambda, outerVar)) {
              translate(Abs(x, translate(Abs(y, nestedLambda))))
            } else {
              throw new IllegalStateException("x was not free in nested expr")
            }


          case S => S
          case K => K
          case I => I

          case Tr(lft, rgt) => {
            var freeLft = free(lft, outerVar)
            var freeRgt = free(rgt, outerVar)

            if (freeLft && !freeRgt) {
              Tr(Tr(Consts.B, translate(lft)), translate(Abs(x, rgt)))
            } else if(!freeLft && freeRgt) {
              Tr(Tr(Consts.C, translate(Abs(x, lft))), translate(rgt))
            } else {
              Tr(Tr(S, translate(Abs(x, lft))), translate(Abs(x, rgt)))
            }
          }
        }
    }
  }

  private def free(lambda: Lambda, needle: Var): Boolean = !refersTo(lambda, needle)

  private def refersTo(lambda: Lambda, needle: Var): Boolean = {
    lambda match {
      case Var(name) => name.equals(needle.name)
      case Abs(name, nested) => name.equals(needle.name) || refersTo(nested, needle)
      case Tr(lft, rgt) => refersTo(lft, needle) || refersTo(rgt, needle)
      case _ => false
    }
  }
}