Stefanie Schirmer, Hannes Mehnert, Jens Ohlig
1.Auflage Juni 2013
ISBN 978-3-86899-369-1
208 Seiten, gebundene Ausgabe
erschienen bei O’Reilly
Im Alltag der imperativen Programmierung mit JavaScript bringen ungeplante Programmänderungen die gewohnten Abstraktionsmechanismen mitunter an ihre Grenzen. In diesem Buch wird ein Einstieg in die funktionale Programmierung geboten, deren Ansatz sich von den übrigen Arten der Programmierung unterscheidet und die zu Unrecht als schwierig zu verstehen gilt.
Es geht um die praktischen Grundlagen des funktionalen Programmierens, ergänzt durch Analogien zum Kochen eines Currys, denn gutes Programmieren ist wie gutes Kochen. Bekannte funktionale Programmiersprachen sind Lisp, Haskell oder ML. Oft entstammen diese einer akademischen Welt und sind besonders dort verbreitet. Im Gegensatz dazu verwendet dieses Buch JavaScript, die Basis der offenen Web-Standards. Die auffälligste Besonderheit bei der funktionalen Programmierung ist, dass Programmfunktionen wie mathematische Funktionen oder auch Kochrezepte aufgefasst werden.
In den ersten Kapiteln kann direkt in die funktionale Programmierung eingestiegen werden, ein sanfter Paradigmenwechsel ohne das Erlernen einer neuen Programmiersprache. Ein wichtiger Aspekt beim funktionalen Programmieren sind Funktionen höherer Ordnung. Dabei handelt es sich um Funktionen, die wiederum Funktionen als Argumente erhalten. Die Leserinnen und Leser lernen diese als Grundlage kennen, um dann Funktionen höherer Ordnung auf Arrays anzuwenden. Anschließend führt die kulinarische Reise zu dem Thema Rekursion, bevor die event-basierte Programmierung und Continuations behandelt werden.
In den anschließenden Kapiteln wird die theoretische Seite beleuchtet; zunächst das Lambda-Kalkül, die Grundlage fast aller funktionaler Programmiersprachen. Datentypen und Monaden, mit denen in rein funktionalen Programmiersprachen Seiteneffekte gekapselt werden, tauchen auf. Abgerundet wird alles durch einen Ausblick auf weitere Sprachen. In Nebenrollen haben Vindaloo-Curry, Auberginen und ein Mango-Lassi ihren Auftritt. Namaste und guten Appetit!
Namensnennung - Nicht-kommerziell - Weitergabe unter gleichen Bedingungen
CC BY-NC-SA
Diese Lizenz erlaubt es, dieses Werk zu verbreiten, zu remixen, zu verbessern und darauf aufzubauen, allerdings nur nicht-kommerziell und solange die Urhebenden des Originals genannt werden und die auf diesem Werk basierenden neuen Werke unter denselben Bedingungen veröffentlicht werden. Eine mögliche Namensnennung und Angabe der Lizenz könnte etwa so aussehen: „Das Curry-Buch - Funktional programmieren lernen mit JavaScript von Stefanie Schirmer, Hannes Mehnert, Jens Ohlig. Erschienen bei O'Reilly. CC BY-NC-SA 2.0 Deutschland“.
Die "License Deed" ansehen | Den rechtsverbindlichen Lizenzvertrag ansehen
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())
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 }Danke an Klaus Böttcher für das Finden dieses Fehlers.
function length(head) { if (head == null) return 0; else return 1 + length(head.tail()); }Danke an Axel Rose für das Finden dieses Fehlers.