\n 10 =;

"------------" str 0 \n str;
"Computing primes up to : " str;
n in =;

if(n 2 >=) {
    2 out " " str;
    
    n 1 + [crible];
    i 0 =;

    while(i n <=) {
        i [crible] 1 =;
        i i 1 + =;
    }

    i 3 =;

    while(i i * n <=) {
        if(i [crible]) {
            i out " " str;

            j i =;
            max n i / =;

            while(j max <=) {
                i j * [crible] 0 =;
                j j 2 + =;
            }            
        }
        i i 1 + =;
    }

    if(i 2 %) {
        min i =;
    }

    else {
        min i 1 + =;
    }

    i min =;

    while(i n <=) {
        if(i [crible]) {
            i out " " str;
        }

        i i 2 + =;
    }
}

0 \n str "------------" str 0 \n str;

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "constant.h"
#include "operation.h"

int readSource(FILE* source, char** dest);
int extractStatement(char* programme,char** statement, int *type);
int exploit(char* statement);
void initContext();



int main(int argc, char* argv[])
{
    char* sourceFile = NULL;
    char* programme = NULL;
    char* statement = NULL;
    FILE* source = NULL;
    initContext();
    int statementLength = 1, position = 0, type;
    if(argc == 2)
    {
        sourceFile = argv[1];
        printf("source file: %s\n", sourceFile);
    }
    else
        printf("no source file specified\n");
    source = fopen(sourceFile, "r");
    if(source== NULL)
        printf("specified file not found\n");
    readSource(source, &programme);
    statementLength = extractStatement(programme + position, &statement, &type);
    while(statement)
    {

        printf("res>> %d\n", exploit(statement));
        free(statement);
        statement = NULL;
        position += statementLength;
        statementLength = extractStatement(programme + position, &statement, &type);
    }
    return 0;
}


int readSource(FILE* source, char** dest)
{
    char c, pre = '\0';
    int i = 0;
    fseek(source, 0, 2);  /*2 go to the end of file*/
    *dest = calloc((ftell(source)+1),sizeof(char));/*ftell gives us the file length*/
    rewind(source);
    while((c = fgetc(source)) != EOF)
    {
        if(c == ' ' && pre == ' ')  //suppression des espaces superflux
            continue;
        else if(c == '\n')
            (*dest)[i] = ' ';
        else
        {
            (*dest)[i] = c;
            i++;
        }
        pre = c;
    }
    return 1;
}

int extractStatement(char* programme,char** statement, int *type)
{
    int nbOfPar = 0, i = 1, statementLength = 0;
    if(programme[0] == '(')  //si on a un statement (commence par un '(')
    {
        nbOfPar = 1;
        while(nbOfPar != 0)
        {
            if(programme[i] == ')') nbOfPar--;
            else if(programme[i] == '(') nbOfPar++;
            else if(programme[i] == '\0') return 0; //ici on trouve la longueur du statement
            i++;
        }
        (*statement) = calloc(i+1, sizeof(char));
        statementLength = i;
        while(i)
            (*statement)[i] = programme[--i]; //on la copie
        *type = STATEMENT;
        return statementLength;
    }
    if(programme[0] >= 48 && programme[0] <= 58) //si on a un chiffre
    {
        int i = 0, j = 0;
        while(programme[i] >= 48 && programme[i]<= 58)
        {
            i++;
        }
        statementLength = i;
        j = i;
        (*statement) = calloc(i+1, sizeof(char));
        while(i)
        {
            (*statement)[--j] = programme[--i];
        }

        *type = NUMBER;
        return statementLength;
    }
    if((programme[0] >= 65 && programme[0] <= 90) ||(programme[0] >= 97 && programme[0] <= 122)) //si c'est un nom de variable (des lettres uniquement)
    {

        int i = 0, j = 0;
        while((programme[i] >= 65 && programme[i] <= 90) ||(programme[i] >= 97 && programme[i] <= 122))
        {
            i++;
        }
        statementLength = i;
        j = i;
        (*statement) = calloc(i+1, sizeof(char));
        while(i)
        {
            (*statement)[--j] = programme[--i];
        }

        *type = LITTERAL;
        return statementLength;
    }
    return 0;
}

int exploit(char* statement)
{
    int res = 0, i = 0;
    char c = statement[1];
    while(c == ' ') c = statement[i++];//on trouve l'opération et on appelle op_*
    if(c == '+')
        res = op_Add(statement);
    else if(c == '-')
        res = op_Sub(statement);
    else if(c == '*')
        res = op_Mul(statement);
    else if(c == '/')
        res = op_Div(statement);
    else if(c == 'l' && statement[i+2] == 'e' && statement[i+3] == 't' && statement[i+4] == ' ')
        res = op_Let(statement, globalContext);
    else return 0;
    return res;
}

void initContext()
{
    int i = 0;
    globalContext = malloc(sizeof(context));
    globalContext->length  = 0;
    while(i<100)
    {
        globalContext->var[i++] = NULL;
    }
}

#ifndef OPERATION
#define OPERATION



int op_Add(char* stat);
int op_Sub(char* stat);
int op_Div(char* stat);
int op_Mul(char* stat);
int op_Let(char* stat, context* c);

#endif

#include "constant.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int op_Add(char* stat)
{
    int tmp = 0, offset = 3, res = 0, len = 0;

    int type = 0;
    char* statement;
    do
    {
        int i = 0;
        tmp = extractStatement(stat+offset, &statement, &type); // on commence après le signe de l'opération (offset)
        len = tmp-1;
        if(type == STATEMENT) // si on a un statement on l'exploit
            res += exploit(statement);
        else if(type == LITTERAL)// si c'est un litteral (variable) on le retrouve
        {
            while(i<globalContext->length && !strcmp(statement, globalContext->var[i++]->name));
            i--;
            if(i == globalContext->length)
            {
                printf("undeclared var near:%s\n", stat);
                return 0;
            }
            else
                res += globalContext->var[i]->value;
        }
        else// enfin, on le converti en chiffre (int)
        {
            while(len+1)
            {
                res += (statement[len]-48) * pow(10, i);
                i++;
                len--;
            }
        }
        offset += tmp;
        while(stat[offset] == ' ')
            offset++;
    }while(stat[offset] != ')'); // et on fait ça tant qu'on a pas fini
    return res;
}

/*
pour op_Sub et les autres on fait apreil, excépté qu'il faut faire gaffe a pas faire -1 -2 pour (- 1 2)
*/
int op_Sub(char* stat)
{
    int tmp = 0, offset = 3, res = 0, len = 0, first = 1;
    int type = 0;
    char* statement;
    do
    {
        int i = 0;
        tmp = extractStatement(stat+offset, &statement, &type);
        len = tmp-1;
        if(type == STATEMENT && first)
            res = exploit(statement);
        else if(type == STATEMENT && !first)
            res -= exploit(statement);
        else if(type == LITTERAL && first)
        {
            while(i<globalContext->length && !strcmp(statement, globalContext->var[i++]->name));
            i--;
            if(i == globalContext->length)
            {
                printf("undeclared var near:%s\n", stat);
                return 0;
            }
            else
                res = globalContext->var[i]->value;
        }
        else if(type == LITTERAL && !first)
        {
            while(i<globalContext->length && !strcmp(statement, globalContext->var[i++]->name));
            i--;
            if(i == globalContext->length)
            {
                printf("undeclared var near:%s\n", stat);
                return 0;
            }
            else
                res -= globalContext->var[i]->value;
        }
        else
        {
            while(len+1)
            {
                if(first)
                    res += (statement[len]-48) * pow(10, i);
                else
                    res -= (statement[len]-48) * pow(10, i);
                i++;
                len--;
            }
        }
        first = 0;
        offset += tmp;
        while(stat[offset] == ' ')
            offset++;
    }while(stat[offset] != ')');
    return res;
}
int op_Div(char* stat)
{
    int tmp = 0, offset = 3, res = 0, len = 0, first = 1, op = 0;
    int type = 0;
    char* statement;
    do
    {
        int i = 0;
        tmp = extractStatement(stat+offset, &statement, &type);
        len = tmp-1;
        if(type == STATEMENT && first)
            res = exploit(statement);
        else if(type == STATEMENT && !first)
            op = exploit(statement);
        else if(type == LITTERAL && first)
        {
            while(i<globalContext->length && !strcmp(statement, globalContext->var[i++]->name));
            i--;
            if(i == globalContext->length)
            {
                printf("undeclared var near:%s\n", stat);
                return 0;
            }
            else
                res = globalContext->var[i]->value;
        }
        else if(type == LITTERAL && !first)
        {
            while(i<globalContext->length && !strcmp(statement, globalContext->var[i++]->name));
            i--;
            if(i == globalContext->length)
            {
                printf("undeclared var near:%s\n", stat);
                return 0;
            }
            else
                op = globalContext->var[i]->value;
        }
        else
        {
            while(len+1)
            {
                if(first == 1)
                    res += (statement[len]-48) * pow(10, i);
                else
                    op += (statement[len]-48) * pow(10, i);
                i++;
                len--;
            }
        }
        if(!first && op != 0)
            res /= op;
        else if (!first && op == 0)
        {
            printf("ERROR: divide by zero near: %s\n", stat);
            return 0;
        }
        op = 0;
        first = 0;
        offset += tmp;
        while(stat[offset] == ' ')
            offset++;
    }while(stat[offset] != ')');
    return res;
}
int op_Mul(char* stat)
{
    int tmp = 0, offset = 3, res = 0, len = 0, first = 1, op = 0;
    int type = 0;
    char* statement;
    do
    {
        int i = 0;
        tmp = extractStatement(stat+offset, &statement, &type);
        len = tmp-1;
        if(type == STATEMENT && first)
            res = exploit(statement);
        else if(type == STATEMENT && !first)
            op = exploit(statement);
        else if(type == LITTERAL && first)
        {
            while(i<globalContext->length && !strcmp(statement, globalContext->var[i++]->name));
            i--;
            if(i == globalContext->length)
            {
                printf("undeclared var near:%s\n", stat);
                return 0;
            }
            else
                res = globalContext->var[i]->value;
        }
        else if(type == LITTERAL && !first)
        {
            while(i<globalContext->length && !strcmp(statement, globalContext->var[i++]->name));
            i--;
            if(i == globalContext->length)
            {
                printf("undeclared var near:%s\n", stat);
                return 0;
            }
            else
                op = globalContext->var[i]->value;
        }
        else
        {
            while(len+1)
            {
                if(first == 1)
                    res += (statement[len]-48) * pow(10, i);
                else
                    op  += (statement[len]-48) * pow(10, i);
                i++;
                len--;
            }
        }
        if(!first)
            res *= op;
        op = 0;
        first = 0;
        offset += tmp;
        while(stat[offset] == ' ')
            offset++;
    }while(stat[offset] != ')');
    return res;
}

int op_Let(char* stat, context *c)
{
    int i = 0, j = 0, k = 0, type = 0, len = 0;
    char *statement = NULL;
    while(stat[5 + i++] != ' '); // on va au nom de variable(5 pour '(let ')
    variable *x = malloc(sizeof(variable));
    x->name = calloc(i+1, sizeof(char));
    for(j = 0; j<i-1; j++)
        x->name[j]= stat[j+5];
    len = extractStatement(stat+i+5, &statement, &type); // puis on prend la valeur
    if(type == NUMBER)
        while(len)
        {
            x->value += (statement[len-1]-48) * pow(10, k);
            len--;
            k++;
        }
    else if(type == STATEMENT)
        x->value = exploit(statement);
    c->var[c->length] = x;
    c->length++;
    return x->value;
}

#define STATEMENT 1
#define NUMBER 2
#define STRING 3
#define LITTERAL 4

typedef struct variable{
    char* name;
    int value;
    }variable;

typedef struct context{
    int length;
    variable *var[100];
    }context;

context* globalContext;

trait Instruction

  case class Program(insts: List[Instruction])

  case class Literal[α](v: α) extends Instruction

  case class UnOp(op: Char, inst: Instruction) extends Instruction

  case class BinOp(op: Char,
                   inst1: Instruction,
                   inst2: Instruction) extends Instruction

  case class If(cond: Instruction,
                thenInst: Instruction,
                elseInst: Instruction) extends Instruction

  case class Print(inst: Instruction) extends Instruction

  case class Define(name: Literal[String], value: Instruction) extends Instruction

type Parser = List[Char] => Option[(Instruction, List[Char])]

  def skipSpaces(s: List[Char]): List[Char] =
    s.dropWhile(_.isWhitespace)

  def unOp(c: Char) = List('~', '!') contains c

  def arithOp(c: Char) = List('+', '*', '-', '/') contains c

  def logOp1(c: Char) = List('<', '>', '=') contains c

  def logOp2(c: Char) = List('&', '|') contains c

  def logOp(c: Char) = logOp1(c) || logOp2(c)

  def binOp(c: Char) = arithOp(c) || logOp(c)

  def isOp(c: Char) = unOp(c) || binOp(c)

def parseInt: List[Char] => (Literal[Int], List[Char]) = l => {
    val (l1, l2) = skipSpaces(l).span(_.isDigit)
    (Literal(l1.foldLeft(0)((acc, x) => acc * 10 + x.asDigit)), skipSpaces(l2))
  }

  // parse un identificateur
  def parseId: List[Char] => (Literal[String], List[Char]) = l => {
    val (l1, l2) = skipSpaces(l).span(_.isLetterOrDigit)
    (Literal(l1.foldLeft("")(_ + _)), skipSpaces(l2))
  }

  def parseInst: Parser = s => skipSpaces(s) match {
    case Nil => None
    case '(' :: s1 => skipSpaces(s1) match {
      case op :: s2 if isOp(op) => parseInst(s2) match {
        case None => None
        case Some((inst, ')' :: r)) if unOp(op) =>
          Some((UnOp(op, inst), skipSpaces(r)))
        case Some((inst1, r)) => parseInst(r) match {
          case Some((inst2, ')' :: r)) if binOp(op) =>
            Some((BinOp(op, inst1, inst2), skipSpaces(r)))
          case _ => None
        }
        case _ => None
      }
      case 'p' :: 'r' :: 'i' :: 'n' :: 't' :: xs => parseInst(xs) match {
        case Some((inst, ')' :: r)) => Some((Print(inst), skipSpaces(r)))
        case _ => None
      }
      case 'i' :: 'f' :: xs => parseInst(xs) match {
        case None => None
        case Some((cond, r)) => parseInst(r) match {
          case None => None
          case Some((inst1, r1)) => parseInst(r1) match {
            case Some((inst2, ')' :: r2)) => Some((If(cond, inst1, inst2), skipSpaces(r2)))
            case _ => None
          }
        }
      }
      case 'd' :: 'e' :: 'f' :: 'i' :: 'n' :: 'e' :: xs =>
        val (name, r) = parseId(xs)
        parseInst(r) match {
          case Some((inst, ')' :: r)) => Some((Define(name, inst), skipSpaces(r)))
          case _ => None
        }
      case _ => None
    }
    case c :: s1 if c.isDigit => Some(parseInt(s))
    case c :: s1 if c.isLetter => Some(parseId(s))
    case _ => None
  }

  def parseProg(s: String): Program = {
    var l = List.empty[Instruction]
    var i = 1
    var beg = 0
    var end = 0
    var p = false
    val s1 = skipSpaces(s.trim().toList)
    if (s1(0) != '(')
      throw new Exception("Erreur")
    for (c <- s1.tail) {
      end += 1
      if (c == '(') {
        i += 1
        p = false
      }
      else if (c == ')')
        i -= 1
      if (i == 0 && !p) {
        l ::= (parseInst(s1.drop(beg).take(end + 1)) match {
          case Some((inst, _)) => inst
          case _ => throw new Exception("Erreur")
        })
        beg = end + 1
        p = true
      }
    }
    if (beg != end + 1)
      throw new Exception("Erreur")
    else
      Program(l)
  }

def evalInst(context: scala.collection.mutable.Map[String, Any], inst: Instruction): Any = inst match {
    case Literal(x: Int) => x
    case Literal(x: String) =>
      if (context.contains(x))
        context(x)
      else
        throw new Exception("Variable introuvable: " + x)
    case UnOp('~', e) => evalInst(context, e) match {
      case v: Int => -v
      case _ => new Exception("Erreur de type")
    }
    case UnOp('!', e) => evalInst(context, e) match {
      case b: Boolean => !b
      case _ => new Exception("Erreur de type")
    }
    case BinOp(op, e1, e2) if arithOp(op) =>
      val m: Map[Char, (Int, Int) => Int] = Map(
        '+' -> (_ + _),
        '-' -> (_ - _),
        '*' -> (_ * _),
        '/' -> (_ / _)
      )
      (evalInst(context, e1), evalInst(context, e2)) match {
        case (e1: Int, e2: Int) => m(op)(e1, e2)
        case _ => new Exception("Erreur de type")
      }
    case BinOp(op, e1, e2) if logOp1(op) =>
      val m: Map[Char, (Int, Int) => Boolean] = Map(
        '<' -> (_ < _),
        '>' -> (_ > _),
        '=' -> (_ == _)
      )
      (evalInst(context, e1), evalInst(context, e2)) match {
        case (e1: Int, e2: Int) => m(op)(e1, e2)
        case _ => new Exception("Erreur de type")
      }
    case BinOp(op, e1, e2) if logOp2(op) =>
      val m: Map[Char, (Boolean, Boolean) => Boolean] = Map(
        '&' -> (_ && _),
        '|' -> (_ || _)
      )
      (evalInst(context, e1), evalInst(context, e2)) match {
        case (e1: Boolean, e2: Boolean) => m(op)(e1, e2)
        case _ => new Exception("Erreur de type")
      }
    case If(cond, e1, e2) => evalInst(context, cond) match {
      case b: Boolean => if (b) evalInst(context, e1) else evalInst(context, e2)
      case n: Int => if (n != 0) evalInst(context, e1) else evalInst(context, e2)
    }
    case Print(e) => println(evalInst(context, e))
    case Define(Literal(n), e) => context(n) = evalInst(context, e)
    case _ => throw new Exception("Syntax error")
  }

  def run(prg: String) {
    val ctxt = scala.collection.mutable.Map.empty[String, Any]
    parseProg(prg).insts.reverse.map(evalInst(ctxt, _))
  }

val n = 3

~('define __ 'x __ ('* __ n __ n))
~('print __ 'x)
~('if __ ('> __ 'x __ 2) __ 
     ('print __ 2) __ 
     ('print __ 'x)))

9
2

object Part {
    val context = scala.collection.mutable.Map.empty[String, Any]
  }

  trait Part {
    def __(that: Part) = (this, that) match {
      case (Exp(l1), _) => Exp(l1 ++ List(that))
      case _ => Exp(List(this, that))
    }

    def toInstr: Instruction = this match {
      case Sym(x) => Literal(x.toString)
      case IntL(v) => Literal(v)
      case Exp(List(Sym(op), e1, e2)) if binOp(op.toString().apply(1)) =>
        BinOp(op.toString().apply(1), e1.toInstr, e2.toInstr)
      case Exp(List(Sym(op), e)) if unOp(op.toString().apply(1)) =>
        UnOp(op.toString().apply(1), e.toInstr)
      case Exp(List(Sym('define), Sym(x), e)) => Define(Literal(x.toString), e.toInstr)
      case Exp(List(Sym('print), e)) => Print(e.toInstr)
      case Exp(List(Sym('if), c, e1, e2)) => If(c.toInstr, e1.toInstr, e2.toInstr)
      case _ => throw new Exception("Erreur")
    }
    def unary_~ = evalInst(Part.context, this.toInstr)
  }

  case class Sym(s: Symbol) extends Part

  case class IntL(v: Int) extends Part

  case class Exp(l: List[Part]) extends Part

  implicit def symbolToSym(s: Symbol): Sym = Sym(s)

  implicit def intToIntL(v: Int): IntL = IntL(v)

def parseExp: Parser = (e: ParseRes) => elseNone(e) {

    case Some((insts, '(' :: s)) =>
      elseNone(parseExp(Some((Nil, s)))) {
        case Some((List(i: Instruction), ')' :: s1))  =>
          Some((i :: insts, s1))
      }

    case Some((insts, op :: s)) if unOp(op) =>
      elseNone(parseExp(Some((Nil, s)))) {
        case Some((List(i), ')' :: s1)) => Some((UnOp(op, i) :: insts, s1))
      }

    case Some((insts, op :: s)) if binOp(op) =>
      val e1 = (parseExp o parseExp)(Some((Nil, s)))
      elseNone(e1) {
        case Some((List(i2, i1), ')' :: s1)) => Some((BinOp(op, i1, i2) :: insts, s1))
      }

    case Some((insts, 'p' :: 'r' :: 'i' :: 'n' :: 't' :: ' ' :: xs)) =>
      elseNone(parseExp(Some((Nil, xs)))) {
        case Some((List(inst), r)) => Some((Print(inst) :: insts, r))
      }

    case Some((insts, 'i' :: 'f' :: ' ' :: s)) =>
      val e1 = (parseExp o parseExp o parseExp)(Some((Nil, s)))
      elseNone(e1) {
        case Some((List(i2, i1, cond), s1)) => Some((If(cond, i1, i2) :: insts, s1))
      }

    case Some((insts, 'd' :: 'e' :: 'f' :: 'i' :: 'n' :: 'e' :: ' ' :: s)) =>
      val e1 = (parseId o parseExp)(Some((Nil, s)))
      elseNone(e1) {
        case Some((List(inst, id: Var), s1)) => Some((Define(id, inst) :: insts, s1))
      }

    case Some((insts, s@(c :: _))) if c.isDigit =>
      elseNone(parseInt(Some((Nil, s)))) {
        case Some((List(inst), s1)) => Some((inst :: insts, s1))
      }

    case Some((insts, s@(c :: _))) if c.isLetter =>
      elseNone(parseId(Some((Nil, s)))) {
        case Some((List(inst), s1)) => Some((inst :: insts, s1))
      }
  }

object LispParser {

  trait Expression

  trait Atom extends Expression

  trait Instruction extends Expression

  case class Program(insts: List[Instruction])

  case class Literal[α](v: α) extends Atom

  case class Var(nom: String) extends Atom

  case class UnOp(op: Char, inst: Expression) extends Instruction

  case class BinOp(op: Char,
                   inst1: Expression,
                   inst2: Expression) extends Instruction

  case class If(cond: Expression,
                thenInst: Expression,
                elseInst: Expression) extends Instruction

  case class Print(inst: Expression) extends Instruction

  case class Define(name: Var, value: Expression) extends Instruction

  def skipSpaces(s: List[Char]): List[Char] =
    s.dropWhile(_.isWhitespace)

  def unOp(c: Char) = List('~', '!') contains c

  def arithOp(c: Char) = List('+', '*', '-', '/') contains c

  def logOp1(c: Char) = List('<', '>', '=') contains c

  def logOp2(c: Char) = List('&', '|') contains c

  def logOp(c: Char) = logOp1(c) || logOp2(c)

  def binOp(c: Char) = arithOp(c) || logOp(c)

  def isOp(c: Char) = unOp(c) || binOp(c)

  def isAtom(e: Expression) = e match {
    case e: Atom => true
    case _ => false
  }

  def elseNone[T, U](x: Option[T])
                    (f: PartialFunction[Option[T], Option[U]]) =
    if (f.isDefinedAt(x)) f(x) else x match {
      case None => None
      case _ => println(x) ; None
    }

  type ParseRes = Option[(List[Expression], List[Char])]

  type ParseFunc = ParseRes => ParseRes

  class Parser(val f: ParseFunc) extends ParseFunc {
    override def apply(x: ParseRes) = elseNone(x) {
      case Some((l1, l2)) => f(Some((l1, skipSpaces(l2))))
    }

    def o(that: Parser): Parser = new Parser(x =>
      elseNone(x) {
        case Some((l, _)) => elseNone(this(x)) {
          case Some((l2, s2)) => that(Some((l2 ++ l, skipSpaces(s2))))
        }
      })
  }

  implicit def funcToParser(f: ParseFunc): Parser = new Parser(f)

  def parseInt: Parser = (e: ParseRes) => elseNone(e) {
    case Some((insts, w)) =>
      val (l1, l2) = w.span(_.isDigit)
      Some((insts ++ List(Literal((0 /: l1)(_ * 10 + _.asDigit))), l2))
  }

  def parseId: Parser = (e: ParseRes) => elseNone(e) {
    case Some((insts, w@(c :: _))) if c.isLetter =>
      val (l1, l2) = skipSpaces(w).span(_.isLetterOrDigit)
      Some((insts ++ List(Var(("" /: l1)(_ + _))), l2))
  }

  def parseExp: Parser = (e: ParseRes) => elseNone(e) {
    case Some((insts, '(' :: s)) =>
      elseNone(parseExp(Some((Nil, s)))) {
        case Some((List(i: Instruction), ')' :: s1))  =>
          Some((i :: insts, s1))
      }
    case Some((insts, op :: s)) if unOp(op) =>
      elseNone(parseExp(Some((Nil, s)))) {
        case Some((List(i), ')' :: s1)) => Some((UnOp(op, i) :: insts, s1))
      }
    case Some((insts, op :: s)) if binOp(op) =>
      val e1 = (parseExp o parseExp)(Some((Nil, s)))
      elseNone(e1) {
        case Some((List(i2, i1), ')' :: s1)) => Some((BinOp(op, i1, i2) :: insts, s1))
      }
    case Some((insts, 'p' :: 'r' :: 'i' :: 'n' :: 't' :: ' ' :: xs)) =>
      elseNone(parseExp(Some((Nil, xs)))) {
        case Some((List(inst), r)) => Some((Print(inst) :: insts, r))
      }
    case Some((insts, 'i' :: 'f' :: ' ' :: s)) =>
      val e1 = (parseExp o parseExp o parseExp)(Some((Nil, s)))
      elseNone(e1) {
        case Some((List(i2, i1, cond), s1)) => Some((If(cond, i1, i2) :: insts, s1))
      }
    case Some((insts, 'd' :: 'e' :: 'f' :: 'i' :: 'n' :: 'e' :: ' ' :: s)) =>
      val e1 = (parseId o parseExp)(Some((Nil, s)))
      elseNone(e1) {
        case Some((List(inst, id: Var), s1)) => Some((Define(id, inst) :: insts, s1))
      }
    case Some((insts, s@(c :: _))) if c.isDigit =>
      elseNone(parseInt(Some((Nil, s)))) {
        case Some((List(inst), s1)) => Some((inst :: insts, s1))
      }
    case Some((insts, s@(c :: _))) if c.isLetter =>
      elseNone(parseId(Some((Nil, s)))) {
        case Some((List(inst), s1)) => Some((inst :: insts, s1))
      }
  }

  def parse(s: String) = parseExp(Some((Nil, s toList)))
}

trait Lexeme

  trait BinOperator extends Lexeme

  trait UnOperator extends Lexeme

  trait ArithOperator extends BinOperator

  trait BoolOperator extends BinOperator

  trait CompOperator extends BinOperator

  trait Other extends Lexeme

  case object Plus extends ArithOperator

  case object Minus extends ArithOperator

  case object Times extends ArithOperator

  case object Less extends CompOperator

  case object LessOrEqual extends CompOperator

  case object Greater extends CompOperator

  case object GreaterOrEqual extends CompOperator

  case object Equals extends CompOperator

  case object NotEquals extends CompOperator

  case object And extends BoolOperator

  case object Or extends BoolOperator

  case object Neg extends UnOperator

  case object Not extends UnOperator

  case class Str(name: String) extends Other

  case class Integer[T](x: Int) extends Other

  case object OpPar extends Other

  case object CloPar extends Other

  case object Error extends Other

def lexemes(w: List[Char]): List[Lexeme] = w match {
    case Nil => Nil
    case c :: w1 if c.isWhitespace => lexemes(w1)
    case '(' :: w1 => OpPar :: lexemes(w1)
    case ')' :: w1 => CloPar :: lexemes(w1)
    case '+' :: w1 => Plus :: lexemes(w1)
    case '-' :: w1 => Minus :: lexemes(w1)
    case '*' :: w1 => Times :: lexemes(w1)
    case '<' :: '=' :: w1 => LessOrEqual :: lexemes(w1)
    case '<' :: w1 => Less :: lexemes(w1)
    case '>' :: '=' :: w1 => GreaterOrEqual :: lexemes(w1)
    case '>' :: w1 => Greater :: lexemes(w1)
    case '!' :: '=' :: w1 => NotEquals :: lexemes(w1)
    case '=' :: w1 => Equals :: lexemes(w1)
    case '!' :: w1 => Not :: lexemes(w1)
    case '~' :: w1 => Neg :: lexemes(w1)
    case 'a' :: 'n' :: 'd' :: c :: w1 if c.isWhitespace =>
      And :: lexemes(w1)
    case 'o' :: 'r' :: c :: w1 if c.isWhitespace =>
      Or :: lexemes(w1)
    case c :: w1 if c.isDigit =>
      val (l1, l2) = w.span(_.isDigit)
      // (x /: l)(f) == l.foldLeft(x)(f)
      Integer((0 /: l1)(_ * 10 + _.asDigit)) :: lexemes(l2)
    case c :: w1 if c.isLetter =>
      val (l1, l2) = w.span(_.isLetterOrDigit)
      Str(("" /: l1)(_ + _)) :: lexemes(l2)
    case _ => List(Error)
  }

def parseExp: Parser1[Expression] = (lex: List[Lexeme]) => lex match {
    case OpPar :: lex1 => parseExp.parse(lex1) {
      case (Some(e), CloPar :: lex2) if !isAtom(e) => (e.s, lex2)
    }
    case (b: BinOperator) :: lex1 => (parseExp >> parseExp).parse(lex1) {
      case (Some((e1, e2)), lex2) => (BinOp(b, e1, e2).s, lex2)
    }
    case (u: UnOperator) :: lex1 => parseExp.parse(lex1) {
      case (Some(e1), lex2) => (UnOp(u, e1).s, lex2)
    }
    case Str("define") :: Str(n) :: lex1 => parseExp.parse(lex1) {
      case (Some(e), lex2) => (Define(Var(n), e).s, lex2)
    }
    case Str("print") :: lex1 => parseExp.parse(lex1) {
      case (Some(e), lex2) => (Print(e).s, lex2)
    }
    case Str("if") :: lex1 => (parseExp >> parseExp >> parseExp).parse(lex1) {
      case (Some(((b, e1), e2)), lex2) => (If(b, e1, e2).s, lex2)
    }
    case Integer(x) :: lex1 => (Literal(x).s, lex1)
    case Str(n) :: lex1 => (Var(n).s, lex1)
    case _ => (None, lex)
  }

object LispParser {

  trait Lexeme

  trait BinOperator extends Lexeme

  trait UnOperator extends Lexeme

  trait ArithOperator extends BinOperator

  trait BoolOperator extends BinOperator

  trait CompOperator extends BinOperator

  trait Other extends Lexeme

  case object Plus extends ArithOperator

  case object Minus extends ArithOperator

  case object Times extends ArithOperator

  case object Less extends CompOperator

  case object LessOrEqual extends CompOperator

  case object Greater extends CompOperator

  case object GreaterOrEqual extends CompOperator

  case object Equals extends CompOperator

  case object NotEquals extends CompOperator

  case object And extends BoolOperator

  case object Or extends BoolOperator

  case object Neg extends UnOperator

  case object Not extends UnOperator

  case class Str(name: String) extends Other

  case class Integer[T](x: Int) extends Other

  case object OpPar extends Other

  case object CloPar extends Other

  case object Error extends Other

  def lexemes(w: List[Char]): List[Lexeme] = w match {
    case Nil => Nil
    case c :: w1 if c.isWhitespace => lexemes(w1)
    case '(' :: w1 => OpPar :: lexemes(w1)
    case ')' :: w1 => CloPar :: lexemes(w1)
    case '+' :: w1 => Plus :: lexemes(w1)
    case '-' :: w1 => Minus :: lexemes(w1)
    case '*' :: w1 => Times :: lexemes(w1)
    case '<' :: '=' :: w1 => LessOrEqual :: lexemes(w1)
    case '<' :: w1 => Less :: lexemes(w1)
    case '>' :: '=' :: w1 => GreaterOrEqual :: lexemes(w1)
    case '>' :: w1 => Greater :: lexemes(w1)
    case '!' :: '=' :: w1 => NotEquals :: lexemes(w1)
    case '=' :: w1 => Equals :: lexemes(w1)
    case '!' :: w1 => Not :: lexemes(w1)
    case '~' :: w1 => Neg :: lexemes(w1)
    case 'a' :: 'n' :: 'd' :: c :: w1 if c.isWhitespace =>
      And :: lexemes(w1)
    case 'o' :: 'r' :: c :: w1 if c.isWhitespace =>
      Or :: lexemes(w1)
    case c :: w1 if c.isDigit =>
      val (l1, l2) = w.span(_.isDigit)
      Integer((0 /: l1)(_ * 10 + _.asDigit)) :: lexemes(l2)
    case c :: w1 if c.isLetter =>
      val (l1, l2) = w.span(_.isLetterOrDigit)
      Str(("" /: l1)(_ + _)) :: lexemes(l2)
    case _ => List(Error)
  }


  trait Expression {
    def s = Some(this)
  }

  trait Atom extends Expression

  trait Instruction extends Expression

  case class Program(insts: List[Instruction])

  case class Literal[α](v: α) extends Atom

  case class Var(nom: String) extends Atom

  case class UnOp(op: UnOperator, inst: Expression) extends Instruction

  case class BinOp(op: BinOperator,
                   inst1: Expression,
                   inst2: Expression) extends Instruction

  case class If(cond: Expression,
                thenInst: Expression,
                elseInst: Expression) extends Instruction

  case class Print(inst: Expression) extends Instruction

  case class Define(name: Var, value: Expression) extends Instruction


  def isAtom(e: Expression) = e match {
    case e: Atom => true
    case _ => false
  }

  type Parser[T] = List[Lexeme] => (Option[T], List[Lexeme])

  def seq[T, U](p: Parser[T], q: Parser[U]): Parser[(T, U)] = l => p(l) match {
    case (Some(r1), l1) => q(l1) match {
      case (Some(r2), l2) => (Some((r1, r2)), l2)
      case _ => (None, l1)
    }
    case _ => (None, l)
  }

  class Parser1[T](val p: Parser[T]) extends Parser[T] {
    def >>[U](q: Parser1[U]) = new Parser1[(T, U)](seq(p, q.p))

    override def apply(l: List[Lexeme]) = parse(l) {
      case x => x
    }

    def parse[U](l: List[Lexeme]) =
      (f: PartialFunction[(Option[T], List[Lexeme]),
        (Option[U], List[Lexeme])]) =>
        if (f.isDefinedAt(p(l))) f(p(l)) else (None, l)
  }

  implicit def parserToParser1[T](p: Parser[T]) = new Parser1(p)

  def parseExp: Parser1[Expression] = (lex: List[Lexeme]) => lex match {
    case OpPar :: lex1 => parseExp.parse(lex1) {
      case (Some(e), CloPar :: lex2) if !isAtom(e) => (e.s, lex2)
    }
    case (b: BinOperator) :: lex1 => (parseExp >> parseExp).parse(lex1) {
      case (Some((e1, e2)), lex2) => (BinOp(b, e1, e2).s, lex2)
    }
    case (u: UnOperator) :: lex1 => parseExp.parse(lex1) {
      case (Some(e1), lex2) => (UnOp(u, e1).s, lex2)
    }
    case Str("define") :: Str(n) :: lex1 => parseExp.parse(lex1) {
      case (Some(e), lex2) => (Define(Var(n), e).s, lex2)
    }
    case Str("print") :: lex1 => parseExp.parse(lex1) {
      case (Some(e), lex2) => (Print(e).s, lex2)
    }
    case Str("if") :: lex1 => (parseExp >> parseExp >> parseExp).parse(lex1) {
      case (Some(((b, e1), e2)), lex2) => (If(b, e1, e2).s, lex2)
    }
    case Integer(x) :: lex1 => (Literal(x).s, lex1)
    case Str(n) :: lex1 => (Var(n).s, lex1)
    case _ => (None, lex)
  }

  def parse(s: String) = parseExp(lexemes(s toList))
}

(seq 
  (define (xor a b)
    (or (and a (! b)) (and (! a) b)))
  (print (xor true true))
  (print (xor true false))
  (print (xor false true))
  (print (xor false false))
 )



(seq 
  (define (compose f g x) (f (g x)))
  (define (g x) (* 2 x))
  (define (f x) (+ 10 x))
  (print (compose f g 1))
  (print (compose g f 1))
    
  (define (fact n)
    (if (= n 0)
    	1
    	(* n (fact (- n 1)))))
    (print (fact 5)))
)

implicit def parserMonadInstance: Monad[Parser] = new Monad[Parser] {

    // "return" en Haskell, retourne "a" sans rien consommer
    def pure[A](a: => A) = Parser(s => (a, s) :: Nil) 

    // applique f aux cas où p réussit à parser quelque chose 
    def bind[A, B](p: Parser[A], f: A => Parser[B]) = Parser { 
      s =>
        p parse s flatMap { case (a, s1) => f(a) parse s1 }
    }
  }

  implicit def parserMonoidInstance[A]: Monoid[Parser[A]] = new Monoid[Parser[A]] {

    // le parser qui échoue toujours ...
    val zero: Parser[A] = Parser(_ => Nil) 

    // résultat non déterministe de p | q. À l'utilisation on écrit p |+| q.
    def append(p: Parser[A], q: => Parser[A]) = Parser(s => (p parse s) ++ (q parse s))
  }

def |(that: Parser[A]): Parser[A] = Parser(s =>
      (this |+| that) parse s match {
        case Nil    => Nil
        case x :: _ => List(x)
      })

def parseInt: Parser[Expression] = for {
    r <- satisfy {
      case Integer(_) => true
      case _          => false
    }
    Integer(n) = r
  } yield Literal(n)
  
  def parseDefine: Parser[Expression] = for {
    _ <- lex(Str("define"))
    x <- parseVar.as[Var]
    exp <- parseExp
  } yield Define(x, exp)

  def parseBinOp: Parser[Expression] = {
    val operators = List(Lexing.Plus, Minus, Times, Less, LessOrEqual,
      Greater, GreaterOrEqual, Equals, NotEquals, And, Or)
    for {
      op <- (operators.map(lex(_)).reduceLeft(_ | _)).as[BinOperator]
      expr <- parseExp
      exprs <- many1(parseExp)
    } yield BinOp(op, expr :: exprs)
  }

  def parseExp1: Parser[Expression] = parseProg | parseDefine | parseUnOp | parseBinOp |
    parseIf | parsePrint | parseFuncDef | parseFunc 

  def parseFuncDef: Parser[Expression] =
    for {
      _ <- lex(Str("define"))
      _ <- lex(OpPar)
      name <- parseVar.as[Var]
      args <- many(parseVar.as[Var])
      _ <- lex(CloPar)
      body <- parseExp
    } yield DefFunc(name, args, body)

   // ....

object Lexing {

  trait Lexeme
  trait BinOperator extends Lexeme
  trait UnOperator extends Lexeme
  trait ArithOperator extends BinOperator
  trait BoolOperator extends BinOperator
  trait CompOperator extends BinOperator
  trait Other extends Lexeme

  case object Plus extends ArithOperator
  case object Minus extends ArithOperator
  case object Times extends ArithOperator
  case object Div extends ArithOperator

  case object Less extends CompOperator
  case object LessOrEqual extends CompOperator
  case object Greater extends CompOperator
  case object GreaterOrEqual extends CompOperator
  case object Equals extends CompOperator
  case object NotEquals extends CompOperator

  case object And extends BoolOperator
  case object Or extends BoolOperator

  case object Neg extends UnOperator
  case object Not extends UnOperator

  case class Str(name: String) extends Other
  case class Integer[T](x: Int) extends Other
  case object OpPar extends Other
  case object CloPar extends Other
  case object Error extends Other

  def lexemes(w: List[Char]): List[Lexeme] = w match {
    case Nil                       => Nil
    case c :: w1 if c.isWhitespace => lexemes(w1)
    case '(' :: w1                 => OpPar :: lexemes(w1)
    case ')' :: w1                 => CloPar :: lexemes(w1)
    case '+' :: w1                 => Plus :: lexemes(w1)
    case '-' :: w1                 => Minus :: lexemes(w1)
    case '*' :: w1                 => Times :: lexemes(w1)
    case '/' :: w1                 => Div :: lexemes(w1)
    case '<' :: '=' :: w1          => LessOrEqual :: lexemes(w1)
    case '<' :: w1                 => Less :: lexemes(w1)
    case '>' :: '=' :: w1          => GreaterOrEqual :: lexemes(w1)
    case '>' :: w1                 => Greater :: lexemes(w1)
    case '!' :: '=' :: w1          => NotEquals :: lexemes(w1)
    case '=' :: w1                 => Equals :: lexemes(w1)
    case '!' :: w1                 => Not :: lexemes(w1)
    case '~' :: w1                 => Neg :: lexemes(w1)
    case 'a' :: 'n' :: 'd' :: c :: w1 if c.isWhitespace =>
      And :: lexemes(w1)
    case 'o' :: 'r' :: c :: w1 if c.isWhitespace =>
      Or :: lexemes(w1)
   case c :: w1 if c.isDigit =>
      val (l1, l2) = w.span(_.isDigit)
      Integer((0 /: l1)(_ * 10 + _.asDigit)) :: lexemes(l2)
    case c :: w1 if c.isLetter =>
      val (l1, l2) = w.span(_.isLetterOrDigit)
      Str(("" /: l1)(_ + _)) :: lexemes(l2)
    case _ => List(Error)
  }

  val keywords = List("define", "if")

}

object AST {

  trait Expression 
  case class Sequence(insts: List[Expression]) extends Expression
  case class Literal[A](v: A) extends Expression
  case class Var(nom: String) extends Expression
  case class UnOp(op: Lexing.UnOperator,
                  inst: Expression) extends Expression
  case class BinOp(op: Lexing.BinOperator,
                   insts: List[Expression]) extends Expression
  case class If(cond: Expression,
                thenInst: Expression,
                elseInst: Expression) extends Expression
  case class Print(inst: Expression) extends Expression
  case class Define(name: Var, value: Expression) extends Expression
  case class DefFunc(name: Var, args: List[Var], body: Expression) extends Expression
  case class Func(name: Var, args: List[Expression]) extends Expression

}

object Parsing {
  import scalaz._
  import Scalaz._

  import Lexing._
  import AST._

  case class Parser[A](parse: List[Lexeme] => List[(A, List[Lexeme])]) {
    def |(that: Parser[A]): Parser[A] = Parser(s =>
      (this |+| that) parse s match {
        case Nil    => Nil
        case x :: _ => List(x)
      })
    def as[T] = this.asInstanceOf[Parser[T]]
  }

  val item = Parser {
    case Nil     => Nil
    case c :: s1 => (c, s1) :: Nil
  }

  implicit def parserMonadInstance: Monad[Parser] = new Monad[Parser] {
    def pure[A](a: => A) = Parser(s => (a, s) :: Nil)

    def bind[A, B](p: Parser[A], f: A => Parser[B]) = Parser {
      s =>
        p parse s flatMap { case (a, s1) => f(a) parse s1 }
    }
  }

  implicit def parserMonoidInstance[A]: Monoid[Parser[A]] = new Monoid[Parser[A]] {
    val zero: Parser[A] = Parser(_ => Nil)

    def append(p: Parser[A], q: => Parser[A]) = Parser(s => (p parse s) ++ (q parse s))
  }

  def satisfy(predicat: Lexeme => Boolean): Parser[Lexeme] =
    for {
      c <- item
      r <- if (predicat(c)) c.pure[Parser] else mzero[Parser[Lexeme]]
    } yield r

  def lex(l: Lexeme) = satisfy(l ==)
  def many[A](p: Parser[A]): Parser[List[A]] = many1(p) | List.empty[A].pure
  def many1[A](p: Parser[A]): Parser[List[A]] =
    for { r <- p; rs <- many(p) } yield (r :: rs)

  def parseVar: Parser[Expression] = for {
    r <- satisfy {
      case Str(_) => true
      case _      => false
    }
    Str(x) = r
  } yield Var(x)

  def parseInt: Parser[Expression] = for {
    r <- satisfy {
      case Integer(_) => true
      case _          => false
    }
    Integer(n) = r
  } yield Literal(n)
  
  def parseTrue: Parser[Expression] = for {
    _ <- lex(Str("true")) 
  } yield Literal(true)

  def parseFalse: Parser[Expression] = for {
    _ <- lex(Str("false")) 
  } yield Literal(false)

  def parseDefine: Parser[Expression] = for {
    _ <- lex(Str("define"))
    x <- parseVar.as[Var]
    exp <- parseExp
  } yield Define(x, exp)

  def parseUnOp: Parser[Expression] =
    for {
      op <- (lex(Neg) | lex(Not)).as[UnOperator]
      expr <- parseExp
    } yield UnOp(op, expr)

  def parseBinOp: Parser[Expression] = {
    val operators = List(Lexing.Plus, Minus, Times, Less, LessOrEqual,
      Greater, GreaterOrEqual, Equals, NotEquals, And, Or)
    for {
      op <- (operators.map(lex(_)).reduceLeft(_ | _)).as[BinOperator]
      expr <- parseExp
      exprs <- many1(parseExp)
    } yield BinOp(op, expr :: exprs)
  }

  def parseIf: Parser[Expression] =
    for {
      _ <- lex(Str("if"))
      cond <- parseExp
      then <- parseExp
      else_ <- parseExp
    } yield If(cond, then, else_)

  def parsePrint: Parser[Expression] =
    for {
      _ <- lex(Str("print"))
      expr <- parseExp
    } yield Print(expr)

  def parseExp: Parser[Expression] =
    (for {
      _ <- lex(OpPar)
      r <- parseExp1 | parseExp
      _ <- lex(CloPar)
    } yield r) | parseInt | parseTrue | parseFalse | parseVar

  def parseExp1: Parser[Expression] = parseProg | parseDefine | parseUnOp | parseBinOp |
    parseIf | parsePrint | parseFuncDef | parseFunc 

  def parseProg: Parser[Expression] =
    for {
      _ <- lex(Str("seq"))
      exprs <- many1(parseExp.as[Expression])
    } yield Sequence(exprs)

  def parseFuncDef: Parser[Expression] =
    for {
      _ <- lex(Str("define"))
      _ <- lex(OpPar)
      name <- parseVar.as[Var]
      args <- many(parseVar.as[Var])
      _ <- lex(CloPar)
      body <- parseExp
    } yield DefFunc(name, args, body)

  def parseFunc: Parser[Expression] =
    for {
      name <- parseVar.as[Var]
      args <- many(parseExp)
    } yield Func(name, args)
}

object Semantics {
  import AST._
  import Lexing._

  type Env = List[(String, Any)]

  val arith = Map[ArithOperator, (Int, Int) => Int] (
    Plus -> (_ + _),
    Minus -> (_ - _),
    Times -> (_ * _),
    Div -> (_ / _))

  val comp = Map[CompOperator, (Int, Int) => Boolean] (
    Less -> (_ < _),
    LessOrEqual -> (_ <= _),
    Greater -> (_ > _),
    GreaterOrEqual -> (_ >= _),
    Equals -> (_ == _),
    NotEquals -> (_ != _))

  val bool = Map[BoolOperator, (Boolean, Boolean) => Boolean] (
    And -> (_ && _),
    Or -> (_ || _))

  def eval(exp: Expression, env: Env): Either[String, (Any, Env)] =
    exp match {
      case Literal(x) => Right(x, env)
      case Var(x) =>
        val l = (env dropWhile (_._1 != x))
        if (l.isEmpty)
          Left("Unbound variable: " + x)
        else Right(l.head._2, env)

      case UnOp(Neg, exp1) => eval(exp1, env) match {
        case Right((v: Int, env1)) => Right(-v, env1)
        case _                     => Left("Type error: " + exp1)
      }

      case UnOp(Not, exp1) => eval(exp1, env) match {
        case Right((v: Boolean, env1)) => Right(!v, env1)
        case _                         => Left("Type error: " + exp1)
      }

      case BinOp(op: ArithOperator, exprs) =>
        val values = exprs.map (eval(_, env))
        if (!values.forall(_.isInstanceOf[Right[String, (Int, Env)]]))
          Left("Type error: " + exprs.dropWhile (eval(_, env).isInstanceOf[Right[String, (Int, Env)]]))
        else Right(values.map{ case Right((v: Int, _)) => v } reduceLeft arith(op), env)

      case BinOp(op: CompOperator, exprs) =>
        val values = exprs.map (eval(_, env))
        if (!values.forall(_.isInstanceOf[Right[String, (Int, Env)]]))
          Left("Type error: " + exprs.dropWhile (eval(_, env).isInstanceOf[Right[String, (Int, Env)]]))
        else
          Right(values.map{ case Right((v: Int, _)) => v }
            .sliding(2).map(c => comp(op)(c(0), c(1))).forall(_ == true), env)

      case BinOp(op: BoolOperator, exprs) =>
        val values = exprs.map (eval(_, env))
        if (!values.forall(_.isInstanceOf[Right[String, (Boolean, Env)]]))
          Left("Type error: " + exprs.dropWhile (eval(_, env).isInstanceOf[Right[String, (Int, Env)]]))
        else
          Right(values.map{ case Right((v: Boolean, _)) => v }.reduceLeft(bool(op)), env)

      case If(cond, exp1, exp2) => eval(cond, env) match {
        case Right((c: Boolean, env1)) => if (c) eval(exp1, env1) else eval(exp2, env1)
        case _                         => Left("Type error: " + cond)
      }

      case Print(expr) => eval(expr, env) match {
        case Right((e, env1)) => Right(println(e), env1)
        case l                => l
      }
      case Define(Var(x), exp) => eval(exp, env) match {
        case Right((v, env1)) => Right((), (x, v) :: env1)
        case l                => l
      }

      case Sequence(exprs) =>
        val u: Any = ()
        Right((exprs.foldLeft((u, env)) ((acc, e) => eval(e, acc._2) match { case Right(r) => r })._1, env))

      case DefFunc(Var(name), args, body) => Right((), (name, (args map { case Var(x) => x }, body)) :: env)
      case Func(name, eff_args) => eval(name, env) match {
        case Right(((form_args: List[String], body: Expression), env1)) =>
          if (eff_args.size == form_args.size) {
            val def_args: List[Expression] = form_args.zip(eff_args map (eval(_, env1) match { case Right(c) => c._1 }))
              .map { case (n, e) => Define(Var(n), Literal(e)) }
            val s = Sequence(def_args ++ List(body))
            eval(s, env1)
          } else Left("Wrong number of parameters to function " + name)
        case l => l
      }
    }
}