var spices = [
  "Zimt",
  "Kreuzkümmel",
  "Koriander",
  "Gewürznelke",
  "Kardamom, am besten sowohl grün als auch schwarz",
  "Schwarze Pfefferkörner",
  "Rote Chilischoten oder Chilipulver",
  "Ingwerpaste oder frischen Ingwer, kein Ingwerpulver",
  "Garam Masala",
  "Kurkuma"
]
var base = [
  "Glasig angebratene Zwiebeln",
  "Naturjoghurt mit Crème fraîche versetzt",
  "Kokosnussmilch"
]
var ingredients = [
  "Geflügel",
  "Lamm",
  "Blumenkohl und Kartoffeln",
  "Paneer",
  "Auberginen"
]

console.log("Curry benötigt zunächst eine feuchte Basis. Ich schlage vor, folgende Basis zu benutzen:\n")
console.log("* ", base[Math.floor(Math.random() * base.length)], "\n")
console.log("Die Gewürze werden in einer Pfanne aromageröstet. Als mögliche Gewürze bieten sich an:\n")

for (var i = 0; i < 5; i++) {
  console.log("* ", spices[Math.floor(Math.random() * spices.length)], "\n")
}

console.log("Wir kommen jetzt zur Hauptzutat. Bei unserem Curry ist das\n")

console.log("* ", ingredients[Math.floor(Math.random() * ingredients.length)], "\n")

console.log("Die Hauptzutat wird in einer gesonderten Pfanne bei hoher Hitze angebraten und dann mit der flüssigen Basis und den Gewürzen zusammen bei niedriger Hitze schmoren lassen, bis das Curry gut eingekocht und servierfertig ist.\n")
console.log("Guten Appetit!")

function shuffle (a) {
  var rand
  var index = 0
  var shuffled = []
  a.forEach(function (value) {
    rand = Math.floor(Math.random() * ++index)
    shuffled[index - 1] = shuffled[rand]
    shuffled[rand] = value
  })
  return shuffled
}

var random_sample = function (x, l) {
  return shuffle(l).slice(0, x);
}

var pick = function (l) {
  return function (x) {
    return random_sample(x, l).map(function (x) { console.log("* ", x, "\n")})
  }
}

var spices = [
  "Zimt",
  "Kreuzkümmel",
  "Koriander",
  "Gewürznelke",
  "Kardamom, am besten sowohl grün als auch schwarz",
  "Schwarze Pfefferkörner",
  "Rote Chilischoten oder Chilipulver",
  "Ingwerpaste oder frischen Ingwer, kein Ingwerpulver",
  "Garam Masala",
  "Kurkuma"
]
var base = [
  "Glasig angebratene Zwiebeln",
  "Naturjoghurt mit Crème fraîche versetzt",
  "Kokosnussmilch"
]
var ingredients = [
  "Geflügel",
  "Lamm",
  "Blumenkohl und Kartoffeln",
  "Paneer",
  "Auberginen"
]

console.log("Curry benötigt zunächst eine feuchte Basis. Ich schlage vor, folgende Basis zu benutzen:\n")

pick(base)(1)

console.log("Die Gewürze werden in einer Pfanne aromageröstet. Als mögliche Gewürze bieten sich an:\n")

pick(spices)(5)

console.log("Wir kommen jetzt zur Hauptzutat. Bei unserem Curry ist das\n")

pick(ingredients)(1)

console.log("Die Hauptzutat wird in einer gesonderten Pfanne bei hoher Hitze angebraten und dann mit der flüssigen Basis und den Gewürzen zusammen bei niedriger Hitze schmoren lassen, bis das Curry gut eingekocht und servierfertig ist.\n")
console.log("Guten Appetit!")

var showReductions = true;

//needed for free variable lists - removes ele from array
function remove (ele, arr) {
  return arr.filter(function (a) { return a !== ele; });
}

//creates a fresh variable name
var gensymcount = 0;
function gensym () {
  gensymcount = gensymcount + 1;
  return "#x" + gensymcount;
}

//lambda prototype for function abstraction
function Lambda (binder, body) {
  this.binder = binder;
  this.body = body;
}

//toString - prints λ binder → body
//reduce - reduces the body, and creates a new abstraction with the reduced body
//substitute - if old is binder, everything is done
//           - if new is free in body - create fresh name, substitute binder for fresh, and afterwards new for old
//           - else substitute in body
//free - FV(λ x → e) = FV(e) \ x
//binder keeps the name of the binder
//body keeps the body term
Lambda.prototype.toString =
  function () {
    return "λ " + this.binder + " → " + this.body.toString();
  };
Lambda.prototype.reduce =
  function () { return new Lambda(this.binder, this.body.reduce()); };
Lambda.prototype.substitute =
  function (o, n) {
    if (this.binder === o) //Verschattung
      return this;
    else if (n.free().indexOf(this.binder) !== -1) { //free ist später implementiert
      //Bezeichner mit gleichem Namen, also zuerst einen frischen erzeugen
      var ns = gensym(); //gensym ist später implementiert
      //und die gebundene Variable zuerst ersetzen
      return new Lambda(ns, this.body.substitute(this.binder, new Variable(ns)).substitute(o, n));
    } else
      //Normalfall: Delegation der Ersetzung an den Funktionsrumpf
      return new Lambda(this.binder, this.body.substitute(o, n));
  };
Lambda.prototype.free =
  function () { return remove(this.binder, this.body.free()); };

//prototype for applications

function Application (left, right) {
  this.left = left;
  this.right = right;
}

//toString - prints left side and right side, separated by a whitespace
//reduce - reduces right hand side (argument), reduces left hand side
//         if left hand is a lambda, substitute binder with reduced right hand side
//         afterwards reduces result
//substitute - applies substitution on the left and on the right
//free - FV(M N) = FV(M) u FV(N)
//right and left contain the terms of right and left hand side
Application.prototype.toString =
  function () {
    var l = this.left.toString();
    var r = this.right.toString();
    if (this.left instanceof Lambda)
      l = "(" + l + ")";
    if (this.right instanceof Lambda || this.right instanceof Application)
      r = "(" + r + ")";
    return l + " " + r;
  };
Application.prototype.reduce =
  function () {
    var nr = this.right.reduce();
    var nl = this.left.reduce();
    if (nl instanceof Lambda) {
      var r = nl.body.substitute(nl.binder, nr);
      if (showReductions)
        console.log(new Application(nl, nr).toString() + " ⟿  " + r.toString());
      var s = r.reduce();
      return s;
    } else
      return new Application(nl, nr);
  };
Application.prototype.substitute =
  function (o, n) {
    return new Application(this.left.substitute(o, n), this.right.substitute(o, n));
  };
Application.prototype.free =
  function () { return this.left.free().concat(this.right.free()); };


function Variable (name) {
  this.name = name;
}

//toString - just its name
//reduce - no operation
//substitute - if it is us to be replaced, we replace us
//free - ourselves (the name), as an array
Variable.prototype.toString =
  function () { return this.name; };
Variable.prototype.reduce = function () { return this; };
Variable.prototype.substitute =
  function (o, n) {
    if (this.name === o)
      return n;
    else
      return this;
  };
Variable.prototype.free = function () { return [this.name]; };



//should live somewhere else....


//zero - the number zero, in church encoding λ f → (λ x → x)
var z = new Lambda("s", new Lambda("z", new Variable("z")))

// conversion from JS numbers to church numbers
//church :: Integer -> Church Integer
//church 0 = \f -> \x -> x
//church n = \f -> \x -> f (church (n-1) f x)

function toChurch (n) {
  if (n === 0)
    return z
  else {
    var rec = toChurch(n - 1)
    return new Lambda("s", new Lambda("z", new Application(new Variable("s"), new Application(new Application(rec, new Variable("s")), new Variable("z"))))).reduce()
  }
}

//looks neat on paper, but reality is different
//namely, no arbitrary JS expressions in our lambdas!
//unchurch :: Church Integer -> Integer
//unchurch n = n (\x -> x + 1) 0
//luckily we can count the amount of Applications
function toJS (church) {
  if (church instanceof Lambda) { // ist church eine Funktionsabstraktion?
    var name = church.binder;
    if (church.body instanceof Lambda) { // ist church.body eine Funktionsabstraktion?
      return countNestedApplications(church.body.body, name);
    }
  }
}

function countNestedApplications (expression, binder) {
  if ((expression instanceof Application) && expression.left.name === binder)
    return 1 + countNestedApplications(expression.right, binder);
  else
    return 0;
}

//identity function, λ a → a
var id = new Lambda("a", new Variable("a"))

//example1: (λ b → (λ a → b a)) (λ a → a), should evaluate to (λ a → a)
new Application(new Lambda("b", new Lambda("a", new Application(new Variable("b"), new Variable("a")))), new Lambda("a", new Variable("a"))).reduce().toString()

//example2: (λ b → (λ a → b a)) a, should introduce a fresh variable and evaluate to (λ tmpX → a tmpX)
new Application(new Lambda("b", new Lambda("a", new Application(new Variable("b"), new Variable("a")))), new Variable("a")).reduce().toString()

//zero - the number zero, in church encoding λ f → (λ x → x)
var z = new Lambda("f", new Lambda("x", new Variable("x")))
//successor function for natural church numbers -  λ n → (λ f → (λ x → f (n f x)))
var succ = new Lambda("n", new Lambda("f", new Lambda("x", new Application(new Variable("f"), new Application(new Application(new Variable("n"), new Variable("f")), new Variable("x"))))))

//successor new Applicationlied to zero - result is one: λ f → (λ x → f x)
// (λ n → λ f → λ x → (f) (((n) (f)) (x))) (λ f → λ x → x)
new Application(new Lambda("n", new Lambda("f", new Lambda("x", new Application(new Variable("f"), new Application(new Application(new Variable("n"), new Variable("f")), new Variable("x")))))), new Lambda("f", new Lambda("x", new Variable("x")))).reduce().toString()
//same thing: λ f → (λ x → f x)
new Application(succ, z).reduce().toString()

//plus is just m times new Applicationlication of f to n
// λ m → (λ n → (λ f → (λ x → m f (n f x))))
var plus = new Lambda("m", new Lambda("n", new Lambda("f", new Lambda("x", new Application(new Application(new Variable("m"), new Variable("f")), new Application(new Application(new Variable("n"), new Variable("f")), new Variable("x")))))))

//which is the very same as m times succ
// λ m → (λ n → m SUCC n)
var plusp = new Lambda("m", new Lambda("n", new Application(new Variable("m"), new Application(succ, new Variable("n")))))

//multiplication is m ^ n f new Applicationlied
// λ m → (λ n → (λ f → m (n f)))

//multiplying m and n is the same as repeating the add n function m times and then new Applicationlying it to zero
// λ m → (λ n → m (PLUS n) 0)

//predecessor
// λ n → (λ f → (λ x → n (λ g → (λ h → h (g f))) (λ u → x) (λ u → u)

//subtraction
// λ m → (λ n → (n pred) m)


//a test if a number is zero
//prerequisite is false and true...
// λ n → n (λ x → F) T




//pairs - a pair is (x, y) - so two values.
//valuable functions are: construction, first and second projection

// pair = λ x → (λ y → (λ z → z x y))
// fst = λ p → p (λ x → λ y → x)
// snd = λ p → p (λ x → λ y → y)


//lists - a cons contains head and tail -- so the very same as a pair!
// cons = pair
// head = fst
// tail = snd
// nil = F
// isnil = λ l → l (λ h → λ t → λ d → F) T

//where the last definition is a special case of the general (foldl!)
// process-list = λ l → l (λ h → λ t → λ d → head-and-tail-clause) nil-clause

//church booleans
//true: λ w → (λ f → w)
var wahr = new Lambda("w", new Lambda("f", new Variable("w")))
//false: λ w → (λ f → f)
var falsch = new Lambda("w", new Lambda("f", new Variable("f")))
//the logical and: λ p → (λ q → p q p)
var and = new Lambda("p", new Lambda("q", new Application(new Application(new Variable("p"), new Variable("q")), new Variable("p"))))

//t & t = t
new Application(new Application(and, t), t).reduce().toString()
//t & f = f
new Application(new Application(and, t), f).reduce().toString()
//f & t = f
new Application(new Application(and, f), t).reduce().toString()
//f & f = f
new Application(new Application(and, f), f).reduce().toString()

//t & _ = t --> λ q → q
new Application(and, t).reduce().toString()

//logical or: λ p → (λ q → p p q)
var or = new Lambda("p", new Lambda("q", new Application(new Application(new Variable("p"), new Variable("p")), new Variable("q"))))
//partial - voila da ist es irrelevant, was als q gegeben wird!
var ort = new Application(or, t).reduce().toString()
//und hier kommt das q was reingegeben wird, einfach zurueck!
var orf = new Application(or, f).reduce().toString()

//conditional - gets a predicate p, executes a if true, otherwise b!
//IFTHENELSE = λ p → λ a → λ b → p a b

//U combinator
//λ f → f (f)

//Y combinator
//λ g → (λ x → g (x x)) (λ x → g (x x))

// Copyright (C) 2007 Chris Double.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
// FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
// DEVELOPERS AND CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//

function foldl(f, initial, seq) {
    for(var i=0; i< seq.length; ++i)
        initial = f(initial, seq[i]);
    return initial;
}

var memoize = true;

function ParseState(input, index) {
    this.input = input;
    this.index = index || 0;
    this.length = input.length - this.index;
    this.cache = { };
    return this;
}

ParseState.prototype.from = function(index) {
    var r = new ParseState(this.input, this.index + index);
    r.cache = this.cache;
    r.length = this.length - index;
    return r;
}

ParseState.prototype.substring = function(start, end) {
    return this.input.substring(start + this.index, (end || this.length) + this.index);
}

ParseState.prototype.trimLeft = function() {
    var s = this.substring(0);
    var m = s.match(/^\s+/);
    return m ? this.from(m[0].length) : this;
}

ParseState.prototype.at = function(index) {
    return this.input.charAt(this.index + index);
}

ParseState.prototype.toString = function() {
    return 'PS"' + this.substring(0) + '"';
}

ParseState.prototype.getCached = function(pid) {
    if(!memoize)
        return false;

    var p = this.cache[pid];
    if(p)
        return p[this.index];
    else
        return false;
}

ParseState.prototype.putCached = function(pid, cached) {
    if(!memoize)
        return false;

    var p = this.cache[pid];
    if(p)
        p[this.index] = cached;
    else {
        p = this.cache[pid] = { };
        p[this.index] = cached;
    }
}

function ps(str) {
    return new ParseState(str);
}

// 'r' is the remaining string to be parsed.
// 'matched' is the portion of the string that
// was successfully matched by the parser.
// 'ast' is the AST returned by the successfull parse.
function make_result(r, matched, ast) {
        return { remaining: r, matched: matched, ast: ast };
}

var parser_id = 0;

// 'token' is a parser combinator that given a string, returns a parser
// that parses that string value. The AST contains the string that was parsed.
function token(s) {
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;

        var r = state.length >= s.length && state.substring(0,s.length) == s;
        if(r)
            cached = { remaining: state.from(s.length), matched: s, ast: s };
        else
            cached = false;
        savedState.putCached(pid, cached);
        return cached;
    };
}

// Like 'token' but for a single character. Returns a parser that given a string
// containing a single character, parses that character value.
function ch(c) {
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;
        var r = state.length >= 1 && state.at(0) == c;
        if(r)
            cached = { remaining: state.from(1), matched: c, ast: c };
        else
            cached = false;
        savedState.putCached(pid, cached);
        return cached;
    };
}

// 'range' is a parser combinator that returns a single character parser
// (similar to 'ch'). It parses single characters that are in the inclusive
// range of the 'lower' and 'upper' bounds ("a" to "z" for example).
function range(lower, upper) {
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;

        if(state.length < 1)
            cached = false;
        else {
            var ch = state.at(0);
            if(ch >= lower && ch <= upper)
                cached = { remaining: state.from(1), matched: ch, ast: ch };
            else
                cached = false;
        }
        savedState.putCached(pid, cached);
        return cached;
    };
}

// Helper function to convert string literals to token parsers
// and perform other implicit parser conversions.
function toParser(p) {
    return (typeof(p) == "string") ? token(p) : p;
}

// Parser combinator that returns a parser that
// skips whitespace before applying parser.
function whitespace(p) {
    var p = toParser(p);
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;

        cached = p(state.trimLeft());
        savedState.putCached(pid, cached);
        return cached;
    };
}

// Parser combinator that passes the AST generated from the parser 'p'
// to the function 'f'. The result of 'f' is used as the AST in the result.
function action(p, f) {
    var p = toParser(p);
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;

        var x = p(state);
        if(x) {
            x.ast = f(x.ast);
            cached = x;
        }
        else {
            cached = false;
        }
        savedState.putCached(pid, cached);
        return cached;
    };
}

// Given a parser that produces an array as an ast, returns a
// parser that produces an ast with the array joined by a separator.
function join_action(p, sep) {
    return action(p, function(ast) { return ast.join(sep); });
}

// Given an ast of the form [ Expression, [ a, b, ...] ], convert to
// [ [ [ Expression [ a ] ] b ] ... ]
// This is used for handling left recursive entries in the grammar. e.g.
// MemberExpression:
//   PrimaryExpression
//   FunctionExpression
//   MemberExpression [ Expression ]
//   MemberExpression . Identifier
//   new MemberExpression Arguments
function left_factor(ast) {
    return foldl(function(v, action) {
                     return [ v, action ];
                 },
                 ast[0],
                 ast[1]);
}

// Return a parser that left factors the ast result of the original
// parser.
function left_factor_action(p) {
    return action(p, left_factor);
}

// 'negate' will negate a single character parser. So given 'ch("a")' it will successfully
// parse any character except for 'a'. Or 'negate(range("a", "z"))' will successfully parse
// anything except the lowercase characters a-z.
function negate(p) {
    var p = toParser(p);
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;

        if(state.length >= 1) {
            var r = p(state);
            if(!r)
                cached =  make_result(state.from(1), state.at(0), state.at(0));
            else
                cached = false;
        }
        else {
            cached = false;
        }
        savedState.putCached(pid, cached);
        return cached;
    };
}

// 'end_p' is a parser that is successful if the input string is empty (ie. end of parse).
function end_p(state) {
    if(state.length == 0)
        return make_result(state, undefined, undefined);
    else
        return false;
}

// 'nothing_p' is a parser that always fails.
function nothing_p(state) {
    return false;
}

// 'sequence' is a parser combinator that processes a number of parsers in sequence.
// It can take any number of arguments, each one being a parser. The parser that 'sequence'
// returns succeeds if all the parsers in the sequence succeeds. It fails if any of them fail.
function sequence() {
    var parsers = [];
    for(var i = 0; i < arguments.length; ++i)
        parsers.push(toParser(arguments[i]));
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached) {
            return cached;
        }

        var ast = [];
        var matched = "";
        var i;
        for(i=0; i< parsers.length; ++i) {
            var parser = parsers[i];
            var result = parser(state);
            if(result) {
                state = result.remaining;
                if(result.ast != undefined) {
                    ast.push(result.ast);
                    matched = matched + result.matched;
                }
            }
            else {
                break;
            }
        }
        if(i == parsers.length) {
            cached = make_result(state, matched, ast);
        }
        else
            cached = false;
        savedState.putCached(pid, cached);
        return cached;
    };
}

// Like sequence, but ignores whitespace between individual parsers.
function wsequence() {
    var parsers = [];
    for(var i=0; i < arguments.length; ++i) {
        parsers.push(whitespace(toParser(arguments[i])));
    }
    return sequence.apply(null, parsers);
}

// 'choice' is a parser combinator that provides a choice between other parsers.
// It takes any number of parsers as arguments and returns a parser that will try
// each of the given parsers in order. The first one that succeeds results in a
// successfull parse. It fails if all parsers fail.
function choice() {
    var parsers = [];
    for(var i = 0; i < arguments.length; ++i)
        parsers.push(toParser(arguments[i]));
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached) {
            return cached;
        }
        var i;
        for(i=0; i< parsers.length; ++i) {
            var parser=parsers[i];
            var result = parser(state);
            if(result) {
                break;
            }
        }
        if(i == parsers.length)
            cached = false;
        else
            cached = result;
        savedState.putCached(pid, cached);
        return cached;
    }
}

// 'butnot' is a parser combinator that takes two parsers, 'p1' and 'p2'.
// It returns a parser that succeeds if 'p1' matches and 'p2' does not, or
// 'p1' matches and the matched text is longer that p2's.
// Useful for things like: butnot(IdentifierName, ReservedWord)
function butnot(p1,p2) {
    var p1 = toParser(p1);
    var p2 = toParser(p2);
    var pid = parser_id++;

    // match a but not b. if both match and b's matched text is shorter
    // than a's, a failed match is made
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;

        var br = p2(state);
        if(!br) {
            cached = p1(state);
        } else {
            var ar = p1(state);

            if (ar) {
              if(ar.matched.length > br.matched.length)
                  cached = ar;
              else
                  cached = false;
            }
            else {
              cached = false;
            }
        }
        savedState.putCached(pid, cached);
        return cached;
    }
}

// 'difference' is a parser combinator that takes two parsers, 'p1' and 'p2'.
// It returns a parser that succeeds if 'p1' matches and 'p2' does not. If
// both match then if p2's matched text is shorter than p1's it is successfull.
function difference(p1,p2) {
    var p1 = toParser(p1);
    var p2 = toParser(p2);
    var pid = parser_id++;

    // match a but not b. if both match and b's matched text is shorter
    // than a's, a successfull match is made
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;

        var br = p2(state);
        if(!br) {
            cached = p1(state);
        } else {
            var ar = p1(state);
            if(ar.matched.length >= br.matched.length)
                cached = br;
            else
                cached = ar;
        }
        savedState.putCached(pid, cached);
        return cached;
    }
}


// 'xor' is a parser combinator that takes two parsers, 'p1' and 'p2'.
// It returns a parser that succeeds if 'p1' or 'p2' match but fails if
// they both match.
function xor(p1, p2) {
    var p1 = toParser(p1);
    var p2 = toParser(p2);
    var pid = parser_id++;

    // match a or b but not both
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;

        var ar = p1(state);
        var br = p2(state);
        if(ar && br)
            cached = false;
        else
            cached = ar || br;
        savedState.putCached(pid, cached);
        return cached;
    }
}

// A parser combinator that takes one parser. It returns a parser that
// looks for zero or more matches of the original parser.
function repeat0(p) {
    var p = toParser(p);
    var pid = parser_id++;

    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached) {
            return cached;
        }

        var ast = [];
        var matched = "";
        var result;
        while(result = p(state)) {
            ast.push(result.ast);
            matched = matched + result.matched;
            if(result.remaining.index == state.index)
                break;
            state = result.remaining;
        }
        cached = make_result(state, matched, ast);
        savedState.putCached(pid, cached);
        return cached;
    }
}

// A parser combinator that takes one parser. It returns a parser that
// looks for one or more matches of the original parser.
function repeat1(p) {
    var p = toParser(p);
    var pid = parser_id++;

    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;

        var ast = [];
        var matched = "";
        var result= p(state);
        if(!result)
            cached = false;
        else {
            while(result) {
                ast.push(result.ast);
                matched = matched + result.matched;
                if(result.remaining.index == state.index)
                    break;
                state = result.remaining;
                result = p(state);
            }
            cached = make_result(state, matched, ast);
        }
        savedState.putCached(pid, cached);
        return cached;
    }
}

// A parser combinator that takes one parser. It returns a parser that
// matches zero or one matches of the original parser.
function optional(p) {
    var p = toParser(p);
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;
        var r = p(state);
        cached = r || make_result(state, "", false);
        savedState.putCached(pid, cached);
        return cached;
    }
}

// A parser combinator that ensures that the given parser succeeds but
// ignores its result. This can be useful for parsing literals that you
// don't want to appear in the ast. eg:
// sequence(expect("("), Number, expect(")")) => ast: Number
function expect(p) {
    return action(p, function(ast) { return undefined; });
}

function chain(p, s, f) {
    var p = toParser(p);

    return action(sequence(p, repeat0(action(sequence(s, p), f))),
                  function(ast) { return [ast[0]].concat(ast[1]); });
}

// A parser combinator to do left chaining and evaluation. Like 'chain', it expects a parser
// for an item and for a seperator. The seperator parser's AST result should be a function
// of the form: function(lhs,rhs) { return x; }
// Where 'x' is the result of applying some operation to the lhs and rhs AST's from the item
// parser.
function chainl(p, s) {
    var p = toParser(p);
    return action(sequence(p, repeat0(sequence(s, p))),
                  function(ast) {
                      return foldl(function(v, action) { return action[0](v, action[1]); }, ast[0], ast[1]);
                  });
}

// A parser combinator that returns a parser that matches lists of things. The parser to
// match the list item and the parser to match the seperator need to
// be provided. The AST is the array of matched items.
function list(p, s) {
    return chain(p, s, function(ast) { return ast[1]; });
}

// Like list, but ignores whitespace between individual parsers.
function wlist() {
    var parsers = [];
    for(var i=0; i < arguments.length; ++i) {
        parsers.push(whitespace(arguments[i]));
    }
    return list.apply(null, parsers);
}

// A parser that always returns a zero length match
function epsilon_p(state) {
    return make_result(state, "", undefined);
}

// Allows attaching of a function anywhere in the grammer. If the function returns
// true then parse succeeds otherwise it fails. Can be used for testing if a symbol
// is in the symbol table, etc.
function semantic(f) {
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;
        cached = f() ? make_result(state, "", undefined) : false;
        savedState.putCached(pid, cached);
        return cached;
    }
}

// The and predicate asserts that a certain conditional
// syntax is satisfied before evaluating another production. Eg:
// sequence(and("0"), oct_p)
// (if a leading zero, then parse octal)
// It succeeds if 'p' succeeds and fails if 'p' fails. It never
// consume any input however, and doesn't put anything in the resulting
// AST.
function and(p) {
    var p = toParser(p);
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;
        var r = p(state);
        cached = r ? make_result(state, "", undefined) : false;
        savedState.putCached(pid, cached);
        return cached;
    }
}

// The opposite of 'and'. It fails if 'p' succeeds and succeeds if
// 'p' fails. It never consumes any input. This combined with 'and' can
// be used for 'lookahead' and disambiguation of cases.
//
// Compare:
// sequence("a",choice("+","++"),"b")
//   parses a+b
//   but not a++b because the + matches the first part and peg's don't
//   backtrack to other choice options if they succeed but later things fail.
//
// sequence("a",choice(sequence("+", not("+")),"++"),"b")
//    parses a+b
//    parses a++b
//
function not(p) {
    var p = toParser(p);
    var pid = parser_id++;
    return function(state) {
        var savedState = state;
        var cached = savedState.getCached(pid);
        if(cached)
            return cached;
        cached = p(state) ? false : make_result(state, "", undefined);
        savedState.putCached(pid, cached);
        return cached;
    }
}

eval(require('fs').readFileSync("Lambda.js", "utf8"))
eval(require('fs').readFileSync("jsparse.js", "utf8"))

var variable = whitespace(range("a", "z")); //ein Buchstabe in Kleinschreibung
var a = action(variable, function (ast) { return new Variable(ast); });


var A = function (state) { return A(state); };
var S = function (state) { return S(state); };

var A = action(repeat1(choice(a, action(wsequence(expect(token("(")), S, expect(token(")"))),
                                        function (ast) { return ast[0]; }))),
               function (ast) { return ast.reduce(function (a, b) { return new Application(a, b); }); });
var S = choice(A, action(wsequence(expect(token("λ")), variable, expect(token("→")), S),
                         function (ast) { return new Lambda(ast[0], ast[1]); }));

eval(require('fs').readFileSync("parser.js", "utf8"))

console.log("parsing identity λ x → x: ", S(ps("λ x → x")).ast.toString())

console.log("parsing nested λ x → λ x → x x: ", S(ps("λ x → λ x → x x")).ast.toString())

console.log("parsing nested application (λ x → λ x → x x) y: ", S(ps("(λ x → λ x → x x) y")).ast.toString())

console.log("parsing (λ x → x) y, expecting (λ x → x) y: ", S(ps("(λ x → x) y")).ast.toString())

console.log("reducing (λ x → x) y, expecting y: ", S(ps("(λ x → x) y")).ast.reduce().toString())

console.log("reducing nested application (λ x → λ x → x x) y, expecting λ x → x x: ", S(ps("(λ x → λ x → x x) y")).ast.reduce().toString())

console.log("reducing nested application (λ x → λ y → x y) y, expecting λ #x1 → y #x1: ", S(ps("(λ x → λ y → x y) y")).ast.reduce().toString())

console.log("negation λ p → p (λ w → λ f → f) (λ w → λ f → w): ", S(ps("λ p → p (λ w → λ f → f) (λ w → λ f → w)")).ast.toString())
console.log("negate false, expect true: ", S(ps("(λ p → p (λ w → λ f → f) (λ w → λ f → w)) (λ w → λ f → f)")).ast.reduce().toString())

console.log("und (λ p → λ q → p q p): ", S(ps("λ p → λ q → p q p")).ast.toString())

console.log("und falsch falsch: ", S(ps("(λ p → λ q → p q p) (λ w → λ f → f) (λ w → λ f → f)")).ast.reduce().toString())

console.log("und2 λ p → λ q → q p q: ", S(ps("λ p → λ q → q p q")).ast.toString())

console.log("und2 falsch falsch: ", S(ps("(λ p → λ q → q p q) (λ w → λ f → f) (λ w → λ f → f)")).ast.reduce().toString())

console.log("iff wahr wahr falsch -> wahr: ", S(ps("(λ p → λ c → λ a → p c a) (λ w → λ f → w) (λ w → λ f → w) (λ w → λ f → f)")).ast.reduce().toString())

console.log("inkrement 0 -> eins: ", S(ps("(λ n → λ s → λ z → s (n s z)) (λ s → λ z → z)")).ast.reduce().toString())