lambda->combinators.scala

/* 
    Kuba 'lambdaofgod Bartczuk
    lambda calculus to combinatory logic (and back)

    Warning : if you want to check out the idea itself you'll be better off 
    reading solution in Haskell.

    TO DO
    - de Bruijin notation
    - parsing for some reasonable concrete syntax
*/
    trait LambdaExpression

    case class Var(name : String) extends LambdaExpression {
        override def toString() = 
            name.toString
        override def equals(other : Any) : Boolean = other match {
            case Var(nm) => nm == name
            case _ => false
        }
    }
    
    case class App(function : LambdaExpression, argument : LambdaExpression) extends LambdaExpression {
        override def toString() = {
            val p1 = function match {
                case Var(_) => 
                    function.toString()
                case _ => "(" + function.toString() + ")"
            }
            val p2 = argument match {
                case Var(_) => 
                    " " + argument.toString()
                case _ => "(" + argument.toString() + ")"
            }

            p1 + p2
        }

        override def equals(other : Any) : Boolean = other match {
            case App(f,arg) => f == function && arg == argument
            case _ => false
        }
    }

    case class Abs(vrbl : Var, body : LambdaExpression) extends LambdaExpression {
        override def toString() = {
            val standard = "\\" + vrbl.toString + "." + body.toString
            body match {
            // we'll need to change it to print combinators themselves
            // need to pattern-match against basic combinators
            case Abs(vrbl1, bdy1) =>
                if (bdy1 == vrbl)
                    "K"
                else
                    bdy1 match {
                        case Abs(vrbl2, bdy2) => 
                            if (bdy2 == App(vrbl, App(vrbl1,vrbl2)))
                                "B"
                            else if (bdy2 == App( App(vrbl,vrbl2), App(vrbl1,vrbl2)))
                                "S" 
                            else
                                standard   
                        case _ => 
                            standard
                    }   

            case _ =>
                if (vrbl == body)
                    "I"
                else
                    standard
            }
        }
        override def equals(other : Any) : Boolean = other match {
            case Abs(f,arg) => f == vrbl && arg == body 
            case _ => false
        }

    }

   def freeVars(exp : LambdaExpression) : List[Var] = exp match {
            case Var(ch) => List( Var(ch) )
            case Abs(vr,bd) =>  freeVars(bd) filterNot(_ == vr)
            case App( f, arg) => freeVars(f) ++ freeVars(arg)
    }

 
    def applyFunction(f : Abs, arg : LambdaExpression) = {
                // need to rename bound variables
        def substitute(exp : LambdaExpression, vr : Var, subst : LambdaExpression) : LambdaExpression = exp match {
            case Var(nm) => 
                if (nm == vr.name)
                   subst 
                else
                    exp
            case Abs(variable, body) =>
                if (vr.name == variable.name)
                    exp
                else
                    Abs(variable, substitute(body,vr,subst))
            case App(f, arg) => 
            {
                f match {
                    case Abs(vrbl, body) => 
                        val freeOccurences = freeVars(arg)
                        if (! freeOccurences.contains(vrbl) )
                            App(substitute(f,vr,subst) , substitute(arg,vr,subst))
                        else
                        {
                            // this is shifty but I think it works - we check for free variables every time
                            val newVar = Var("x"+(freeOccurences.length+1).toString)
                                    App( Abs(newVar,substitute(body, vrbl, newVar)), substitute(arg,vr,subst))
                        }
                    case _ => App(substitute(f,vr,subst) , substitute(arg,vr,subst))
                }
            }
        }
        substitute(f.body, f.vrbl, arg)
    }

    def reduceOneStep(exp : LambdaExpression) : LambdaExpression = exp match {
        case App(f, arg) =>
            f match { 
                case Abs(v, bdy) => applyFunction( Abs(v, bdy) ,arg) 
                case _ => App(reduceOneStep(f),arg) 
            }
        case _ => exp
    }

    def etaOneStep(exp : LambdaExpression) : LambdaExpression = exp match {
        case Abs(a,value) =>
            if (! freeVars(value).contains(a) )
                value 
            else
                exp
        case App(a,b) => App(etaOneStep(a),etaOneStep(b))
        case _ => exp
    }
    
    def etaReduce(exp : LambdaExpression) : LambdaExpression = { 
        val reduced = etaOneStep(exp)  
        if (reduced == exp)
            exp
        else
            etaReduce(reduced)
    }

    def reduce(exp : LambdaExpression) : LambdaExpression = {
        val reduced = reduceOneStep(etaReduce(exp))
        // this may of course not terminate - 
        if (exp == reduced)
            etaReduce(exp)
        else
            reduce(reduced)
    }

    // COMBINATORY LOGIC
    // we treat comb. logic as subset of \-calculus
    // primitives
    val x = Var("x")
    val y = Var("y")
    val z = Var("z")
    val t = Var("t")
    val f = Var("f")
    val g = Var("g")
    val K = Abs(x,Abs(y,x))
    val S = Abs(x, Abs(y,Abs(z, App( App(x,z), App(y,z)))))
    val B = Abs(f, Abs(g, Abs(x, App(f, App(g,x)))))
    val C = Abs(f, Abs(x, Abs(y, App(App(f,y), x))))
    val I = Abs(x,x) 
   
    // FUCK IT we'll do another datatype for CL
    trait CombinatoryExpression
    
    case class CVar(name : String) extends CombinatoryExpression {
        override def toString() =  
            name
    }
    
    case class CApp( exp1 : CombinatoryExpression, exp2 : CombinatoryExpression) extends CombinatoryExpression {
        override def toString() = {
            val p1 = exp1 match {
                case CVar(n) => 
                    n
                case _ =>  exp1.toString() 
            }
            val p2 = exp2 match {
                case CVar(n) => 
                    " " + n
                case _ =>  exp2.toString() 
            }

            "(" + p1 + p2 + ")"
        }
    }
     
    def Ic = CVar("I")
    def Kc = CVar("K")
    def Sc = CVar("S")
    def Cc = CVar("C")
    def Bc = CVar("B")

    def primitive(comb : CombinatoryExpression) = 
            (comb == Ic || comb == Kc || comb == Sc || comb == Cc || comb == Bc)
    
    def combinatoryToLambda(exp : CombinatoryExpression) : LambdaExpression = { 
        if (exp == Ic)
            I
        else if (exp == Kc)
            K
        else if (exp == Sc)
            S
        else
            exp match {
                case CVar(n) => Var(n)
                case CApp(e1,e2) => App(combinatoryToLambda(e1),combinatoryToLambda(e2))
            }
    }

    def lambdaToCombinatory(exp : LambdaExpression) : CombinatoryExpression = {
        val reduced = etaReduce(exp)
        reduced match {
        case Var(x) => CVar(x) 
        case App(exp1, exp2) => CApp(lambdaToCombinatory(exp1),lambdaToCombinatory(exp2))
        case Abs(variable1, body) => {
            \\ T[(\x.M)] = K T[M]
            if (! freeVars(body).contains(variable1))
                CApp(Kc, lambdaToCombinatory(etaReduce(body)))
            else if (variable1 == body)
                Ic
            else 
            {
                val bd = etaReduce(body)
                bd match {
                    case Abs(variable2, body2) =>
                        if (body2 == variable1)
                            Kc
                        else body2 match {
                            case Abs(variable3, body3) =>
                            {
                                // getting basic combinators
                                if (body3 == App( App(variable1,variable3), App(variable2,variable3)))
                                    Sc
                                else if (body3 == App(App(variable1,variable2),variable3))
                                    Cc
                                else if (body3 == App(variable1, App(variable2,variable3)))
                                    Bc
                                else
                                    // T[\x\y.M] = T[\x. T[\y. M]]
                                    lambdaToCombinatory( etaReduce(Abs(variable1, combinatoryToLambda(lambdaToCombinatory(Abs(variable2,body2))))))
                            }
                            case _ => lambdaToCombinatory( etaReduce(Abs(variable1, combinatoryToLambda(lambdaToCombinatory(etaReduce(Abs(variable2,body2)))))))
                        }
                    case App(m, n) =>  
                        //T[λx.(E₁ E₂)] => (S T[λx.E₁] T[λx.E₂]) (if x is free in both E₁ and E₂)
                        if ( freeVars(m).contains(variable1) && freeVars(n).contains(variable1))
                            CApp( 
                                CApp(Sc, lambdaToCombinatory(etaReduce(Abs(variable1,m)))),
                                lambdaToCombinatory(etaReduce(Abs(variable1,n))))
                        //T[λx.(E₁ E₂)] => (C T[λx.E₁] T[E₂]) (if x is free in E₁ but not E₂)
                        else if (freeVars(m).contains(variable1))
                            CApp(
                                CApp(Cc,lambdaToCombinatory(etaReduce(Abs(variable1,m)))),
                                lambdaToCombinatory(n))
                        else
                        //T[λx.(E₁ E₂)] => (B T[E₁] T[λx.E₂]) (if x is free in E₂ but not E₁)
                            CApp( 
                                CApp(Bc, lambdaToCombinatory(m)),
                                lambdaToCombinatory(etaReduce(Abs(variable1,n))))

                }
            }
        }
        }
    }

    // tests
    val v = Var("v")
    val f = Var("f")
    val g = Var("g")
    val OmF = Abs(x, App(f, App(x,x)))
    val Y = Abs(f, App(OmF, OmF))
    val zv = App(z,v)
    val t2 = Abs(x, Abs(y, App(y, Abs(z, Abs(t, App( App(z, Abs(x,x)), x))))))

    val comp = App( App(K,zv),x)