while language interpreter

while.scala

/* 
            Kuba 'lambdaofgod Bartczuk 
            basically completed 10.01.2015
            while language interpreter


            syntax: 
            V - variables
            N - numbers
            Prim = N | V
            Expr = Arithmetic | Boolean
            Boolean = true | false | Boolean or Boolean | Boolean and Boolean| Arithmetic < Arithmetic
            Arithmetic = Prim | V + V | V * V
            Statement = V := Expr 
                        | Statement ; Statement 
                        | if Statement then {Statement} else {Statement}
                        | while Boolean do Statement
            (didn't include parens, but who cares about parens)
*/

object While {

// now we need to implement bindings

    

    trait WhileExpr 
    
    case class NoValueException(msg : String) extends Exception(msg)

	trait Expr extends WhileExpr {
        def evalArithmExp( env : Environment ) : Number 
    }

	case class Variable(name : String) extends Expr {
	    override def toString() = name
        def evalArithmExp( env : Environment ) : Number = env.get(this) match {
            case Some(n) => n 
            case None => throw NoValueException("variable " + name + " not found") 
        }
    }
	case class Number(num : Int) extends Expr {
	    override def toString() = num.toString 
        def evalArithmExp( env : Environment) : Number = this 
    }

	abstract class Binary(left : Expr, right : Expr) extends Expr {
    }

	case class Add(left : Expr, right : Expr) extends Binary (left,right) {
	    override def toString = ExpToString(this) 
        def evalArithmExp( env : Environment ) : Number = {
            Number(left.evalArithmExp(env).num + right.evalArithmExp(env).num)
        }
	}
	case class Mult(left : Expr, right : Expr) extends Binary (left,right) {
	    override def toString = ExpToString(this) 
	    def evalArithmExp( env : Environment ) : Number = {
            Number(left.evalArithmExp(env).num * right.evalArithmExp(env).num)
        }
    }
	case class Sub(left : Expr, right : Expr) extends Binary (left,right) {
	    override def toString = ExpToString(this) 
	    def evalArithmExp( env : Environment ) : Number = {
            Number(left.evalArithmExp(env).num - right.evalArithmExp(env).num)
        }
    }
	case class Div(left : Expr, right : Expr) extends Binary (left,right) {
	    override def toString = ExpToString(this) 
	    def evalArithmExp( env : Environment ) : Number = {
            Number(left.evalArithmExp(env).num / right.evalArithmExp(env).num)
        }
    }

	// this kinda violates DRY but I have no idea how to get it clean
	def ExpToString(ex : Expr) : String = {
	    def parenthesize(ex : Expr) = ex match {
		case ex : Binary =>
		    "(" + ExpToString(ex) + ")" 
		case _ => ex.toString
	    }
	    
	    ex match { 
	    case ex : Binary => {
		ex match { 
		    case Add(left,right) => parenthesize(left) + " + " + parenthesize(right)
		    case Mult(left,right) => parenthesize(left) + " * " + parenthesize(right)
		    case Sub(left,right) => parenthesize(left) + " - " + parenthesize(right)
		    case Div(left,right) => parenthesize(left) + " / " + parenthesize(right)
		    }
	    }

	    case _ => ex.toString
	   } 
	}

	// logic 'n such
	trait Bool extends WhileExpr {
         def evalBoolExp(env : Environment) : TruthValue  
    }

	case class TruthValue(bool : Boolean) extends Bool {
	    override def toString = bool.toString
        def evalBoolExp(env : Environment) : TruthValue = this  
    }
	   
	abstract class BoolOp(left : Bool, right : Bool) extends Bool

	case class And(left : Bool, right : Bool) extends BoolOp (left,right){
	    override def toString = BoolToString(this)
	    def evalBoolExp( env : Environment ) : TruthValue = {
            TruthValue( left.evalBoolExp(env).bool && right.evalBoolExp(env).bool )
        }
    }
	case class Or(left : Bool, right : Bool) extends BoolOp (left,right){
	    override def toString = BoolToString(this)
	    def evalBoolExp( env : Environment) : TruthValue = {
             TruthValue( left.evalBoolExp(env).bool || right.evalBoolExp(env).bool )   
        }
    }
	case class Comp(left : Expr, right : Expr, op : String) extends Bool {
	    override def toString = BoolToString(this)
	    def evalBoolExp( env : Environment ) : TruthValue = {
            def toFun(s : String) : (Int,Int) => Boolean = {
                if (s == "<")
                    (x,y) => (x<y)
                else 
                    (x,y) => (x>y)
            }
            TruthValue( toFun(op)(left.evalArithmExp(env).num, right.evalArithmExp(env).num)) 
        }
    }

	def BoolToString(ex : Bool) : String = {
	    def parenthesize(ex : Bool) = ex match {
		case ex : BoolOp =>
		    "(" + BoolToString(ex) + ")" 
		case Comp(left,right,op) =>
		    "(" + ExpToString(left) + op + ExpToString(right) + ")" 
		case _ => ex.toString
	    }
	    
	    ex match { 
	    case ex : BoolOp => {
		ex match { 
		    case And(left,right) => parenthesize(left) + " and " + parenthesize(right)
		    case Or(left,right) => parenthesize(left) + " or " + parenthesize(right)
		    }
	    }
	    case ex : Comp => 
		parenthesize(ex)
	    case ex : TruthValue =>
            ex.toString
	   } 
	}

	// control
	trait Stmt extends WhileExpr

	case class Assgnmt(vrbl : Variable, ex : Expr) extends Stmt {
	    override def toString = vrbl + " := " + ex.toString
	}
	case class Then(st1 : Stmt, st2 : Stmt) extends Stmt {
	    override def toString = st1.toString + " ; " + st2.toString
	}
	case class IfThenElse(cond : Bool, st1 : Stmt, st2 : Stmt) extends Stmt {
	    override def toString = "if (" + cond.toString + " then " + st1.toString + " else " + st2.toString
	}
	case class WhileDo(cond : Bool, st : Stmt) extends Stmt {
	    override def toString = "while (" + cond.toString + ") do " + st.toString 
	}

// interpreter
// start small for ex. with assignment and Aexprs

    type Environment = scala.collection.mutable.Map[Variable, Number]

    def eval(exp : WhileExpr, env : Environment) : WhileExpr = exp match {
        case exp : Expr =>
            exp.evalArithmExp(env)
        case exp : Bool => exp.evalBoolExp(env)
        case Assgnmt(vrbl, assigned) => {
            env(vrbl) = assigned.evalArithmExp(env)
            exp
            }
        case Then(st1,st2) => {
            eval(st1,env)
            eval(st2,env)
        }
        case IfThenElse(cond, st1, st2) => {
            if ( cond.evalBoolExp(env).bool ) 
                eval(st1,env)
            else
                eval(st2,env)
        }
        case WhileDo(cond,st) => {
            while ( cond.evalBoolExp(env).bool ) 
                eval(st,env)
            TruthValue(true)
        }
    }
   
// parser itself
    import scala.util.parsing.combinator._

    object WhileParser extends JavaTokenParsers {

        def whileExp : Parser[WhileExpr] =  stmt | bool | arithmExp   

        def exp : Parser[Expr] = arithmExp 
            
            def variable : Parser[Variable] = ident ^^ { Variable(_) }
            def num : Parser[Number] = floatingPointNumber ^^ { x => Number(x.toInt) }

            def arithmExp : Parser[Expr] = term ~ rep(("+" | "-") ~ term)  ^^ { case t1 ~ lst  => lst.foldLeft(t1)( (t2,t3) => if (t3._1 == "+") Add(t2, t3._2) else Sub(t2,t3._2)) }
            def term : Parser[Expr] = factor ~ rep( ("*" | "/") ~ factor) ^^ { case t1 ~ lst  => lst.foldLeft(t1)( (t2,t3) => if (t3._1 == "*") Mult(t2, t3._2) else Div(t2,t3._2)) } 
            def factor : Parser[Expr] = variable |
                num |
                "("~> arithmExp <~")"

            def bool : Parser[Bool] = and ~ rep("or" ~ and) ^^ { case t1 ~ lst  => lst.foldLeft(t1)( (t2,t3) => Or(t2, t3._2)) } 
            def and : Parser[Bool] = prim ~ rep("and" ~ prim) ^^ { case t1 ~ lst  => lst.foldLeft(t1)( (t2,t3) => And(t2, t3._2)) } 
            def prim : Parser[Bool] = tvalue ^^ { x => TruthValue(x) } |
                rel  |
                "(" ~> bool <~ ")"
            def tvalue : Parser[Boolean] = ("true" | "false") ^^ { x => x == "true" } 
            def rel : Parser[Comp] = arithmExp ~ relOp ~ arithmExp ^^ { case e1 ~ op ~ e2 => Comp(e1,e2,op)  }
            def relOp : Parser[String] = ("<" | ">") ^^ { x => x }

            
            def stmt : Parser[Stmt] = compStmt ~ ";"~ compStmt ^^ { case s1 ~ op ~ s2 => Then(s1,s2) } | compStmt 
            def compStmt : Parser[Stmt] = ident ~ ":=" ~ arithmExp ^^ { case v1 ~ _ ~ exp1 => Assgnmt( Variable(v1),exp1) } |  
            "if" ~ bool ~ "then" ~ basicStmt ~ "else" ~ basicStmt ^^ { case _ ~ cond ~ _ ~ s1 ~ _ ~ s2 => IfThenElse(cond,s1,s2)} |
            "while"~bool~"do"~basicStmt ^^ { case _ ~ cond ~ _ ~ s1 => WhileDo(cond, s1) } 
            def basicStmt : Parser[Stmt] = "{"~>stmt<~"}" 

        }


    def main(args: Array[String]) {
        println("Welcome to while language interpreter")
        println("Please input your formulae, or write \"exit\" to quit")

        var env : Environment = scala.collection.mutable.Map()        
       
        print(">")
        var input = readLine()
        var parsedValue : WhileExpr = TruthValue(true)// = WhileParser.parseAll(WhileParser.whileExp, input).get
        var interpretation : WhileExpr = TruthValue(true) // = eval(parsedValue,env) 
       
        // the repl! 
        while ( input != "exit" )
        {
           parsedValue = WhileParser.parseAll(WhileParser.whileExp, input).get
           // we need that damn patternmatching to make sure that undefined variables don't crash repl
           parsedValue match {
                case Variable(name) => try {
                    eval(parsedValue,env)
                    println( eval(parsedValue,env))
                }
                catch {
                    case e : NoValueException =>
                        println("undefined variable " + name)
                }
                finally {
                }
                case _ => {
                    interpretation = eval(parsedValue,env)
                    interpretation match {
                        case Assgnmt(vrbl, num) => println("defined variable " + vrbl.toString)
                        case interpretation : Stmt => print("")
                        case _ => println(interpretation)}
                }
           }
           print(">")
           input = readLine()
        }

        println("Goodbye, have a nice day")
    }
}