Merge branch 'working'
authorChris <chris.barker@nyu.edu>
Thu, 5 Feb 2015 19:07:44 +0000 (14:07 -0500)
committerChris <chris.barker@nyu.edu>
Thu, 5 Feb 2015 19:07:44 +0000 (14:07 -0500)
_rosetta1.mdwn [moved from _rosetta.mdwn with 100% similarity]
code/json2.js [new file with mode: 0644]
code/lambda.js [new file with mode: 0644]
code/lambda_evaluator.mdwn [new file with mode: 0644]
code/lambda_library.mdwn [new file with mode: 0644]
code/parse.js [new file with mode: 0644]
code/tokens.js [new file with mode: 0644]
rosetta1.mdwn
topics/week1_advanced_notes.mdwn

similarity index 100%
rename from _rosetta.mdwn
rename to _rosetta1.mdwn
diff --git a/code/json2.js b/code/json2.js
new file mode 100644 (file)
index 0000000..deb88ec
--- /dev/null
@@ -0,0 +1,489 @@
+/*
+    json2.js
+    2014-02-04
+
+    Public Domain.
+
+    NO WARRANTY EXPRESSED OR IMPLIED. USE AT YOUR OWN RISK.
+
+    See http://www.JSON.org/js.html
+
+
+    This code should be minified before deployment.
+    See http://javascript.crockford.com/jsmin.html
+
+    USE YOUR OWN COPY. IT IS EXTREMELY UNWISE TO LOAD CODE FROM SERVERS YOU DO
+    NOT CONTROL.
+
+
+    This file creates a global JSON object containing two methods: stringify
+    and parse.
+
+        JSON.stringify(value, replacer, space)
+            value       any JavaScript value, usually an object or array.
+
+            replacer    an optional parameter that determines how object
+                        values are stringified for objects. It can be a
+                        function or an array of strings.
+
+            space       an optional parameter that specifies the indentation
+                        of nested structures. If it is omitted, the text will
+                        be packed without extra whitespace. If it is a number,
+                        it will specify the number of spaces to indent at each
+                        level. If it is a string (such as '\t' or '&nbsp;'),
+                        it contains the characters used to indent at each level.
+
+            This method produces a JSON text from a JavaScript value.
+
+            When an object value is found, if the object contains a toJSON
+            method, its toJSON method will be called and the result will be
+            stringified. A toJSON method does not serialize: it returns the
+            value represented by the name/value pair that should be serialized,
+            or undefined if nothing should be serialized. The toJSON method
+            will be passed the key associated with the value, and this will be
+            bound to the value
+
+            For example, this would serialize Dates as ISO strings.
+
+                Date.prototype.toJSON = function (key) {
+                    function f(n) {
+                        // Format integers to have at least two digits.
+                        return n < 10 ? '0' + n : n;
+                    }
+
+                    return this.getUTCFullYear()   + '-' +
+                         f(this.getUTCMonth() + 1) + '-' +
+                         f(this.getUTCDate())      + 'T' +
+                         f(this.getUTCHours())     + ':' +
+                         f(this.getUTCMinutes())   + ':' +
+                         f(this.getUTCSeconds())   + 'Z';
+                };
+
+            You can provide an optional replacer method. It will be passed the
+            key and value of each member, with this bound to the containing
+            object. The value that is returned from your method will be
+            serialized. If your method returns undefined, then the member will
+            be excluded from the serialization.
+
+            If the replacer parameter is an array of strings, then it will be
+            used to select the members to be serialized. It filters the results
+            such that only members with keys listed in the replacer array are
+            stringified.
+
+            Values that do not have JSON representations, such as undefined or
+            functions, will not be serialized. Such values in objects will be
+            dropped; in arrays they will be replaced with null. You can use
+            a replacer function to replace those with JSON values.
+            JSON.stringify(undefined) returns undefined.
+
+            The optional space parameter produces a stringification of the
+            value that is filled with line breaks and indentation to make it
+            easier to read.
+
+            If the space parameter is a non-empty string, then that string will
+            be used for indentation. If the space parameter is a number, then
+            the indentation will be that many spaces.
+
+            Example:
+
+            text = JSON.stringify(['e', {pluribus: 'unum'}]);
+            // text is '["e",{"pluribus":"unum"}]'
+
+
+            text = JSON.stringify(['e', {pluribus: 'unum'}], null, '\t');
+            // text is '[\n\t"e",\n\t{\n\t\t"pluribus": "unum"\n\t}\n]'
+
+            text = JSON.stringify([new Date()], function (key, value) {
+                return this[key] instanceof Date ?
+                    'Date(' + this[key] + ')' : value;
+            });
+            // text is '["Date(---current time---)"]'
+
+
+        JSON.parse(text, reviver)
+            This method parses a JSON text to produce an object or array.
+            It can throw a SyntaxError exception.
+
+            The optional reviver parameter is a function that can filter and
+            transform the results. It receives each of the keys and values,
+            and its return value is used instead of the original value.
+            If it returns what it received, then the structure is not modified.
+            If it returns undefined then the member is deleted.
+
+            Example:
+
+            // Parse the text. Values that look like ISO date strings will
+            // be converted to Date objects.
+
+            myData = JSON.parse(text, function (key, value) {
+                var a;
+                if (typeof value === 'string') {
+                    a =
+/^(\d{4})-(\d{2})-(\d{2})T(\d{2}):(\d{2}):(\d{2}(?:\.\d*)?)Z$/.exec(value);
+                    if (a) {
+                        return new Date(Date.UTC(+a[1], +a[2] - 1, +a[3], +a[4],
+                            +a[5], +a[6]));
+                    }
+                }
+                return value;
+            });
+
+            myData = JSON.parse('["Date(09/09/2001)"]', function (key, value) {
+                var d;
+                if (typeof value === 'string' &&
+                        value.slice(0, 5) === 'Date(' &&
+                        value.slice(-1) === ')') {
+                    d = new Date(value.slice(5, -1));
+                    if (d) {
+                        return d;
+                    }
+                }
+                return value;
+            });
+
+
+    This is a reference implementation. You are free to copy, modify, or
+    redistribute.
+*/
+
+/*jslint evil: true, regexp: true */
+
+/*members "", "\b", "\t", "\n", "\f", "\r", "\"", JSON, "\\", apply,
+    call, charCodeAt, getUTCDate, getUTCFullYear, getUTCHours,
+    getUTCMinutes, getUTCMonth, getUTCSeconds, hasOwnProperty, join,
+    lastIndex, length, parse, prototype, push, replace, slice, stringify,
+    test, toJSON, toString, valueOf
+*/
+
+
+// Create a JSON object only if one does not already exist. We create the
+// methods in a closure to avoid creating global variables.
+
+if (typeof JSON !== 'object') {
+    JSON = {};
+}
+
+(function () {
+    'use strict';
+
+    function f(n) {
+        // Format integers to have at least two digits.
+        return n < 10 ? '0' + n : n;
+    }
+
+    if (typeof Date.prototype.toJSON !== 'function') {
+
+        Date.prototype.toJSON = function () {
+
+            return isFinite(this.valueOf())
+                ? this.getUTCFullYear()     + '-' +
+                    f(this.getUTCMonth() + 1) + '-' +
+                    f(this.getUTCDate())      + 'T' +
+                    f(this.getUTCHours())     + ':' +
+                    f(this.getUTCMinutes())   + ':' +
+                    f(this.getUTCSeconds())   + 'Z'
+                : null;
+        };
+
+        String.prototype.toJSON      =
+            Number.prototype.toJSON  =
+            Boolean.prototype.toJSON = function () {
+                return this.valueOf();
+            };
+    }
+
+    var cx,
+        escapable,
+        gap,
+        indent,
+        meta,
+        rep;
+
+
+    function quote(string) {
+
+// If the string contains no control characters, no quote characters, and no
+// backslash characters, then we can safely slap some quotes around it.
+// Otherwise we must also replace the offending characters with safe escape
+// sequences.
+
+        escapable.lastIndex = 0;
+        return escapable.test(string) ? '"' + string.replace(escapable, function (a) {
+            var c = meta[a];
+            return typeof c === 'string'
+                ? c
+                : '\\u' + ('0000' + a.charCodeAt(0).toString(16)).slice(-4);
+        }) + '"' : '"' + string + '"';
+    }
+
+
+    function str(key, holder) {
+
+// Produce a string from holder[key].
+
+        var i,          // The loop counter.
+            k,          // The member key.
+            v,          // The member value.
+            length,
+            mind = gap,
+            partial,
+            value = holder[key];
+
+// If the value has a toJSON method, call it to obtain a replacement value.
+
+        if (value && typeof value === 'object' &&
+                typeof value.toJSON === 'function') {
+            value = value.toJSON(key);
+        }
+
+// If we were called with a replacer function, then call the replacer to
+// obtain a replacement value.
+
+        if (typeof rep === 'function') {
+            value = rep.call(holder, key, value);
+        }
+
+// What happens next depends on the value's type.
+
+        switch (typeof value) {
+        case 'string':
+            return quote(value);
+
+        case 'number':
+
+// JSON numbers must be finite. Encode non-finite numbers as null.
+
+            return isFinite(value) ? String(value) : 'null';
+
+        case 'boolean':
+        case 'null':
+
+// If the value is a boolean or null, convert it to a string. Note:
+// typeof null does not produce 'null'. The case is included here in
+// the remote chance that this gets fixed someday.
+
+            return String(value);
+
+// If the type is 'object', we might be dealing with an object or an array or
+// null.
+
+        case 'object':
+
+// Due to a specification blunder in ECMAScript, typeof null is 'object',
+// so watch out for that case.
+
+            if (!value) {
+                return 'null';
+            }
+
+// Make an array to hold the partial results of stringifying this object value.
+
+            gap += indent;
+            partial = [];
+
+// Is the value an array?
+
+            if (Object.prototype.toString.apply(value) === '[object Array]') {
+
+// The value is an array. Stringify every element. Use null as a placeholder
+// for non-JSON values.
+
+                length = value.length;
+                for (i = 0; i < length; i += 1) {
+                    partial[i] = str(i, value) || 'null';
+                }
+
+// Join all of the elements together, separated with commas, and wrap them in
+// brackets.
+
+                v = partial.length === 0
+                    ? '[]'
+                    : gap
+                    ? '[\n' + gap + partial.join(',\n' + gap) + '\n' + mind + ']'
+                    : '[' + partial.join(',') + ']';
+                gap = mind;
+                return v;
+            }
+
+// If the replacer is an array, use it to select the members to be stringified.
+
+            if (rep && typeof rep === 'object') {
+                length = rep.length;
+                for (i = 0; i < length; i += 1) {
+                    if (typeof rep[i] === 'string') {
+                        k = rep[i];
+                        v = str(k, value);
+                        if (v) {
+                            partial.push(quote(k) + (gap ? ': ' : ':') + v);
+                        }
+                    }
+                }
+            } else {
+
+// Otherwise, iterate through all of the keys in the object.
+
+                for (k in value) {
+                    if (Object.prototype.hasOwnProperty.call(value, k)) {
+                        v = str(k, value);
+                        if (v) {
+                            partial.push(quote(k) + (gap ? ': ' : ':') + v);
+                        }
+                    }
+                }
+            }
+
+// Join all of the member texts together, separated with commas,
+// and wrap them in braces.
+
+            v = partial.length === 0
+                ? '{}'
+                : gap
+                ? '{\n' + gap + partial.join(',\n' + gap) + '\n' + mind + '}'
+                : '{' + partial.join(',') + '}';
+            gap = mind;
+            return v;
+        }
+    }
+
+// If the JSON object does not yet have a stringify method, give it one.
+
+    if (typeof JSON.stringify !== 'function') {
+        escapable = /[\\\"\x00-\x1f\x7f-\x9f\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g;
+        meta = {    // table of character substitutions
+            '\b': '\\b',
+            '\t': '\\t',
+            '\n': '\\n',
+            '\f': '\\f',
+            '\r': '\\r',
+            '"' : '\\"',
+            '\\': '\\\\'
+        };
+        JSON.stringify = function (value, replacer, space) {
+
+// The stringify method takes a value and an optional replacer, and an optional
+// space parameter, and returns a JSON text. The replacer can be a function
+// that can replace values, or an array of strings that will select the keys.
+// A default replacer method can be provided. Use of the space parameter can
+// produce text that is more easily readable.
+
+            var i;
+            gap = '';
+            indent = '';
+
+// If the space parameter is a number, make an indent string containing that
+// many spaces.
+
+            if (typeof space === 'number') {
+                for (i = 0; i < space; i += 1) {
+                    indent += ' ';
+                }
+
+// If the space parameter is a string, it will be used as the indent string.
+
+            } else if (typeof space === 'string') {
+                indent = space;
+            }
+
+// If there is a replacer, it must be a function or an array.
+// Otherwise, throw an error.
+
+            rep = replacer;
+            if (replacer && typeof replacer !== 'function' &&
+                    (typeof replacer !== 'object' ||
+                    typeof replacer.length !== 'number')) {
+                throw new Error('JSON.stringify');
+            }
+
+// Make a fake root object containing our value under the key of ''.
+// Return the result of stringifying the value.
+
+            return str('', {'': value});
+        };
+    }
+
+
+// If the JSON object does not yet have a parse method, give it one.
+
+    if (typeof JSON.parse !== 'function') {
+        cx = /[\u0000\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g;
+        JSON.parse = function (text, reviver) {
+
+// The parse method takes a text and an optional reviver function, and returns
+// a JavaScript value if the text is a valid JSON text.
+
+            var j;
+
+            function walk(holder, key) {
+
+// The walk method is used to recursively walk the resulting structure so
+// that modifications can be made.
+
+                var k, v, value = holder[key];
+                if (value && typeof value === 'object') {
+                    for (k in value) {
+                        if (Object.prototype.hasOwnProperty.call(value, k)) {
+                            v = walk(value, k);
+                            if (v !== undefined) {
+                                value[k] = v;
+                            } else {
+                                delete value[k];
+                            }
+                        }
+                    }
+                }
+                return reviver.call(holder, key, value);
+            }
+
+
+// Parsing happens in four stages. In the first stage, we replace certain
+// Unicode characters with escape sequences. JavaScript handles many characters
+// incorrectly, either silently deleting them, or treating them as line endings.
+
+            text = String(text);
+            cx.lastIndex = 0;
+            if (cx.test(text)) {
+                text = text.replace(cx, function (a) {
+                    return '\\u' +
+                        ('0000' + a.charCodeAt(0).toString(16)).slice(-4);
+                });
+            }
+
+// In the second stage, we run the text against regular expressions that look
+// for non-JSON patterns. We are especially concerned with '()' and 'new'
+// because they can cause invocation, and '=' because it can cause mutation.
+// But just to be safe, we want to reject all unexpected forms.
+
+// We split the second stage into 4 regexp operations in order to work around
+// crippling inefficiencies in IE's and Safari's regexp engines. First we
+// replace the JSON backslash pairs with '@' (a non-JSON character). Second, we
+// replace all simple value tokens with ']' characters. Third, we delete all
+// open brackets that follow a colon or comma or that begin the text. Finally,
+// we look to see that the remaining characters are only whitespace or ']' or
+// ',' or ':' or '{' or '}'. If that is so, then the text is safe for eval.
+
+            if (/^[\],:{}\s]*$/
+                    .test(text.replace(/\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4})/g, '@')
+                        .replace(/"[^"\\\n\r]*"|true|false|null|-?\d+(?:\.\d*)?(?:[eE][+\-]?\d+)?/g, ']')
+                        .replace(/(?:^|:|,)(?:\s*\[)+/g, ''))) {
+
+// In the third stage we use the eval function to compile the text into a
+// JavaScript structure. The '{' operator is subject to a syntactic ambiguity
+// in JavaScript: it can begin a block or an object literal. We wrap the text
+// in parens to eliminate the ambiguity.
+
+                j = eval('(' + text + ')');
+
+// In the optional fourth stage, we recursively walk the new structure, passing
+// each name/value pair to a reviver function for possible transformation.
+
+                return typeof reviver === 'function'
+                    ? walk({'': j}, '')
+                    : j;
+            }
+
+// If the text is not JSON parseable, then a SyntaxError is thrown.
+
+            throw new SyntaxError('JSON.parse');
+        };
+    }
+}());
diff --git a/code/lambda.js b/code/lambda.js
new file mode 100644 (file)
index 0000000..83ae7c4
--- /dev/null
@@ -0,0 +1,634 @@
+/*jslint bitwise: true,
+    eqeqeq: true,
+    immed: true,
+    newcap: true,
+    nomen: true,
+    onevar: true,
+    plusplus: true,
+    regexp: true,
+    rhino: true,
+    browser: false,
+    undef: true,
+    white: true,
+
+    evil: false,
+    regexp: false,
+    sub: true,
+    laxbreak: true,
+    onevar: false,
+    debug: true */
+
+
+// DeBruijn terms
+// substitution and translation algorithms from Chris Hankin, An Introduction to Lambda Calculi for Comptuer Scientists
+//
+function Db_free(variable) {
+    this.variable = variable;
+    this.subst = function (m, new_term) {
+        return this;
+    };
+    this.renumber = function (m, i) {
+        return this;
+    };
+    // we assume that other will have variable iff it's a Db_free
+    this.equal = function (other) {
+        return other.variable && this.variable.equal(other.variable);
+    };
+    this.contains = this.equal;
+}
+
+function Db_index(i) {
+    this.index = i;
+    this.subst = function (m, new_term) {
+        if (this.index < m) {
+            return this;
+        } else if (this.index > m) {
+            return new Db_index(this.index - 1);
+        } else {
+            return new_term.renumber(this.index, 1);
+        }
+    };
+    this.renumber = function (m, i) {
+        if (this.index < i) {
+            return this;
+        } else {
+            return new Db_index(this.index + m - 1);
+        }
+    };
+    // we assume that other will have index iff it's a Db_index
+    this.equal = function (other) {
+        return this.index === other.index;
+    };
+    this.contains = this.equal;
+}
+
+function Db_app(left, right) {
+    this.left = left;
+    this.right = right;
+    this.subst = function (m, new_term) {
+        return new Db_app(this.left.subst(m, new_term), this.right.subst(m, new_term));
+    };
+    this.renumber = function (m, i) {
+        return new Db_app(this.left.renumber(m, i), this.right.renumber(m, i));
+    };
+    // we assume that other will have left iff it's a Db_app
+    this.equal = function (other) {
+        return other.left && this.left.equal(other.left) && this.right.equal(other.right);
+    };
+    this.contains = function (other) {
+        if (other.left && this.left.equal(other.left) && this.right.equal(other.right)) {
+            return true;
+        } else {
+            return this.left.contains(other) || this.right.contains(other);
+        }
+    };
+}
+
+function Db_lam(body) {
+    this.body = body;
+    this.subst = function (m, new_term) {
+        return new Db_lam(this.body.subst(m + 1, new_term));
+    };
+    this.renumber = function (m, i) {
+        return new Db_lam(this.body.renumber(m, i + 1));
+    };
+    // we assume that other will have body iff it's a Db_lam
+    this.equal = function (other) {
+        return other.body && this.body.equal(other.body);
+    };
+    this.contains = function (other) {
+        if (other.body && this.body.equal(other.body)) {
+            return true;
+        } else {
+            return this.body.contains(other);
+        }
+    };
+}
+
+
+// lambda terms
+// substitution and normal-order evaluator based on Haskell version by Oleg Kisleyov
+// http://okmij.org/ftp/Computation/lambda-calc.html#lambda-calculator-haskell
+//
+function Variable(name, tag) {
+    this.name = name;
+    this.tag = tag || 0;
+    this.to_string = function () {
+        // append count copies of str to accum
+//         function markup(accum, count) {
+//             if (count === 0) {
+//                 return accum;
+//             } else {
+//                 return markup(accum + "'", count - 1);
+//             }
+//         }
+//         return markup(this.name, this.tag);
+               var s = this.name;
+               for (var count = 0; count < this.tag; count += 1) {
+                       s += "'";
+               }
+               return s;
+    };
+    this.equal = function (other) {
+        return (this.tag === other.tag) && (this.name === other.name);
+    };
+    // position of this in seq
+    this.position = function (seq) {
+        for (var i = 0; i < seq.length; i += 1) {
+            if (this.equal(seq[i])) {
+                return new Db_index(i + 1);
+            }
+        }
+        return new Db_free(this);
+    };
+}
+
+// if v occurs free_in term, returns Some v' where v' is the highest-tagged
+// variable with the same name as v occurring (free or bound) in term
+//
+function free_in(v, term) {
+    var res = term.has_free(v);
+    return res[0] && res[1];
+}
+
+function subst(v, new_term, expr) {
+    if (new_term.variable && new_term.variable.equal(v)) {
+        return expr;
+    } else {
+        return expr.subst(v, new_term);
+    }
+}
+
+function equal(expr1, expr2) {
+    return expr1.debruijn([]).equal(expr2.debruijn([]));
+}
+
+function contains(expr1, expr2) {
+    return expr1.debruijn([]).contains(expr2.debruijn([]));
+}
+
+
+function Lambda_var(variable) {
+    this.variable = variable;
+    this.debruijn = function (seq) {
+        return this.variable.position(seq);
+    };
+    this.to_string = function (as_atom) {
+        return this.variable.to_string();
+    };
+    this.has_free = function (v) {
+        if (v.name !== this.variable.name) {
+            return [false, v];
+        } else if (v.tag === this.variable.tag) {
+            return [true, v];
+        } else {
+            return [false, this.variable];
+        }
+    };
+    this.subst = function (v, new_term) {
+        if (this.variable.equal(v)) {
+            return new_term;
+        } else {
+            return this;
+        }
+    };
+    this.check_eta = function () {
+        return this;
+    };
+    this.eval_loop = function (stack, eta) {
+        function unwind(left, stack) {
+//             if (stack.length === 0) {
+//                 return left;
+//             } else {
+//                 var x = stack[0];
+//                 var xs = stack.slice(1);
+//                 return unwind(new Lambda_app(left, x.eval_loop([], eta)), xs);
+//             }
+                       var res = left, x;
+                       while (stack.length) {
+                               x = stack.shift();
+                               // res = new Lambda_app(res, x.eval_loop([], eta));
+                               res = new Lambda_app(res, reduce(x, eta, false));
+                       }
+                       return res;
+        }
+        // return unwind(this, stack);
+               // trampoline to, args
+               return [null, unwind(this, stack)];
+    };
+    this.eval_cbv = function (aggressive) {
+        return this;
+    };
+}
+
+function Lambda_app(left, right) {
+    this.left = left;
+    this.right = right;
+    this.debruijn = function (seq) {
+        return new Db_app(this.left.debruijn(seq), this.right.debruijn(seq));
+    };
+    this.to_string = function (as_atom) {
+        var base;
+        if (this.left.left) {
+            base = this.left.to_string() + " " + this.right.to_string(true);
+        } else {
+            base = this.left.to_string(true) + " " + this.right.to_string(true);
+        }
+        if (as_atom) {
+            return "(" + base + ")";
+        } else {
+            return base;
+        }
+    };
+    this.has_free = function (v) {
+        var left_res = this.left.has_free(v);
+        var right_res = this.right.has_free(v);
+        var left_bool = left_res[0];
+        var right_bool = right_res[0];
+        var left_tag = left_res[1].tag;
+        var right_tag = right_res[1].tag;
+        var res;
+        if (left_tag > right_tag) {
+            res = left_res[1];
+        } else {
+            res = right_res[1];
+        }
+        return [left_bool || right_bool, res];
+    };
+    this.subst = function (v, new_term) {
+        return new Lambda_app(subst(v, new_term, this.left), subst(v, new_term, this.right));
+    };
+    this.check_eta = function () {
+        return this;
+    };
+    this.eval_loop = function (stack, eta) {
+        var new_stack = stack.slice(0);
+        new_stack.unshift(this.right);
+        // return this.left.eval_loop(new_stack, eta);
+               // trampoline to, args
+               return [this.left, new_stack, eta];
+    };
+    this.eval_cbv = function (aggressive) {
+        var left = this.left.eval_cbv(aggressive);
+        var right = this.right.eval_cbv(aggressive);
+        if (left.body) {
+            return subst(left.bound, right, left.body).eval_cbv(aggressive);
+        } else {
+            return new Lambda_app(left, right);
+        }
+    };
+}
+
+
+//     (* if v occurs free_in term, returns Some v' where v' is the highest-tagged
+//      * variable with the same name as v occurring (free or bound) in term *)
+
+
+function Lambda_lam(variable, body) {
+    this.bound = variable;
+    this.body = body;
+    this.debruijn = function (seq) {
+        var new_seq = seq.slice(0);
+        new_seq.unshift(this.bound);
+        return new Db_lam(this.body.debruijn(new_seq));
+    };
+    this.to_string = function (as_atom) {
+        var base = "\\" + this.to_dotted();
+        if (as_atom) {
+            return "(" + base + ")";
+        } else {
+            return base;
+        }
+    };
+    this.to_dotted = function () {
+        if (this.body.to_dotted) {
+            return this.bound.to_string() + " " + this.body.to_dotted();
+        } else {
+            return this.bound.to_string() + ". " + this.body.to_string();
+        }
+    };
+    this.has_free = function (v) {
+        if (this.bound.equal(v)) {
+            return [false, v];
+        } else {
+            return this.body.has_free(v);
+        }
+    };
+    this.subst = function (v, new_term) {
+        function bump_tag(v1, v2) {
+            var max;
+            if (v1.tag > v2.tag) {
+                max = v1.tag;
+            } else {
+                max = v2.tag;
+            }
+            return new Variable(v1.name, max + 1);
+        }
+        function bump_tag2(v1, v2) {
+            if (v1.name !== v2.name) {
+                return v1;
+            } else {
+                return bump_tag(v1, v2);
+            }
+        }
+        if (this.bound.equal(v)) {
+            return this;
+        } else {
+            var res = free_in(this.bound, new_term);
+            // if x is free in the inserted term new_term, a capture is possible
+            if (res) {
+                // this.bound is free in new_term, need to alpha-convert
+                var uniq_x = bump_tag2(bump_tag(this.bound, res), v);
+                var res2 = free_in(uniq_x, this.body);
+                if (res2) {
+                    uniq_x = bump_tag(uniq_x, res2);
+                }
+                var body2 = subst(this.bound, new Lambda_var(uniq_x), this.body);
+                return new Lambda_lam(uniq_x, subst(v, new_term, body2));
+            } else {
+                // this.bound not free in new_term, can substitute new_term for v without any captures
+                return new Lambda_lam(this.bound, subst(v, new_term, this.body));
+            }
+        }
+    };
+    this.check_eta = function () {
+        if (this.body.right && this.body.right.variable && this.bound.equal(this.body.right.variable) && !free_in(this.bound, this.body.left)) {
+            return this.body.left;
+        } else {
+            return this;
+        }
+    };
+    this.eval_loop = function (stack, eta) {
+        if (stack.length === 0) {
+                       // var term = new Lambda_lam(this.bound, this.body.eval_loop([], eta));
+                       var term = new Lambda_lam(this.bound, reduce(this.body, eta, false));
+                       if (eta) {
+                               return [null, term.check_eta()];
+                       } else {
+                               return [null, term];
+                       }
+        } else {
+            var x = stack[0];
+            var xs = stack.slice(1);
+            // return subst(this.bound, x, this.body).eval_loop(xs, eta);
+                       // trampoline to, args
+                       return [subst(this.bound, x, this.body), xs, eta];
+        }
+    };
+    this.eval_cbv = function (aggressive) {
+        if (aggressive) {
+            return new Lambda_lam(this.bound, this.body.eval_cbv(aggressive));
+        } else {
+            return this;
+        }
+    };
+    this.to_int = function (sofar) {
+//         if (this.body.body && this.body.body.variable && this.body.bound.equal(this.body.body.variable)) {
+//             return 0 + sofar;
+//         } else if (this.body.variable && this.bound.equal(this.body.variable)) {
+//             return 1 + sofar;
+//         } else if (this.body.body && this.body.body.left && this.body.body.left.variable && this.bound.equal(this.body.body.left.variable)) {
+//             var new_int = new Lambda_lam(this.bound, new Lambda_lam(this.body.bound, this.body.body.right));
+//             return new_int.to_int(1 + sofar);
+//         } else {
+//             return "not a church numeral";
+//         }
+               var res = 0, s = this.bound, z, cursor;
+               if (this.body.variable && s.equal(this.body.variable)) {
+                       return 1;
+               } else if (this.body.bound) {
+                       z = this.body.bound;
+                       cursor = this.body.body;
+                       while (cursor.left && cursor.left.variable && s.equal(cursor.left.variable)) {
+                               res += 1;
+                               cursor = cursor.right;
+                       }
+                       if (cursor.variable && z.equal(cursor.variable)) {
+                               return res;
+                       }
+               }
+               return "not a church numeral";
+    };
+}
+
+
+
+///////////////////////////////////////////////////////////////////////////////////
+
+// cbv is false: use call-by-name
+// cbv is 1: use call-by-value, don't descend inside lambda
+// cbv is 2: applicative order
+function reduce(expr, eta, cbv) {
+    if (cbv) {
+        return expr.eval_cbv(cbv > 1);
+    } else {
+        // return expr.eval_loop([], eta);
+               // using trampoline to reduce call stack overflows
+               var to_eval = expr, res = [[], eta];
+               while (to_eval !== null) {
+                       res = to_eval.eval_loop.apply(to_eval, res);
+                       to_eval = res.shift();
+               }
+               return res[0];
+    }
+}
+
+function make_var(name) {
+    return new Variable(name);
+}
+function make_app(aa, bb) {
+    return new Lambda_app(aa, bb);
+}
+function make_lam(a, aa) {
+    return new Lambda_lam(a, aa);
+}
+
+try {
+    if (console && console.debug) {
+        function print() {
+            console.debug.apply(this, arguments);
+        }
+    }
+} catch (e) {}
+
+
+
+
+/* Chris's original
+
+// Basic data structure, essentially a LISP/Scheme-like cons
+// pre-terminal nodes are expected to be of the form new cons(null, "string")
+function cons(car, cdr) {
+  this.car = car;
+  this.cdr = cdr;
+}
+
+// takes a stack of symbols, returns a pair: a tree and the remaining symbols
+function parse(split) {
+  if (split == null) return (new cons (null, null));
+  if (split.length == 0) return (new cons (null, null));
+  var token = split.shift();
+  if (token == ")") return (new cons (null, split));
+  var next = parse(split);
+  if (token == "(") {
+       var nextnext = parse(next.cdr);
+       return (new cons ((new cons (next.car, nextnext.car)),
+                                         nextnext.cdr));
+  }
+  return (new cons ((new cons ((new cons (null, token)),
+                                                          next.car)),
+                                       next.cdr))
+}
+
+// substitute arg in for v in tree
+function sub(tree, v, arg) {
+  if (tree == null) return (null);
+  if (tree.car == null) if (tree.cdr == v) return (arg);
+  if (tree.car == null) return (tree);
+
+  // perform alpha reduction to prevent variable collision
+  if (isBindingForm(tree)) 
+       return (new cons (tree.car, 
+                                         sub(sub(tree.cdr,         // inner sub = alpha reduc.
+                                                         tree.cdr.car.cdr, 
+                                                         fresh(tree.cdr.car.cdr)),
+                                                 v,
+                                                 arg)));
+
+  return (new cons ((sub (tree.car, v, arg)),
+                                       (sub (tree.cdr, v, arg))))
+}
+
+// Guaranteed unique for each call as long as string is not empty.
+var i = 0;
+function fresh(string) {
+  i = i+1;
+  if (typeof(string) != "string") return (string);
+  return (new cons (null,  
+                                       string.substring(0,1) + (i).toString()));
+}
+
+// Keep reducing until there is no more change
+function fixedPoint (tree) {
+  var t2 = reduce(tree);
+  if (treeToString(tree) == treeToString(t2)) return (tree);
+  return (fixedPoint (t2));
+}
+
+// Reduce all the arguments, then try to do beta conversion on the whole
+function reduce(tree) {
+  if (tree == null) return (tree);
+  if (typeof(tree) == "string") return (tree);
+  return (convert (new cons (reduce (tree.car), mapReduce (tree.cdr))));
+}
+
+// Reduce all the arguments in a list
+function mapReduce(tree) {
+  if (tree == null) return (tree);
+  if (tree.car == null) return (tree);
+  return (new cons (reduce (tree.car), mapReduce(tree.cdr )));
+}
+
+// If the list is of the form ((lambda var body) arg), do beta reduc.
+function convert(tree) {
+       if (isLet(tree)) {
+         return (sub(tree.cdr.car, tree.car.cdr.car.cdr, tree.car.cdr.cdr.car));}
+       else 
+         if (isConvertable(tree)) {
+               return (sub(tree.car.cdr.cdr.car, tree.car.cdr.car.cdr, tree.cdr.car));}
+         else return(tree);
+} 
+
+// Is of form ((let var arg) body)?
+function isLet(tree) {
+  if (tree == null) return (false);
+  if (!(isBindingForm(tree.car))) return (false);
+  if (tree.car.car.cdr != "let") return (false);
+  if (tree.cdr == null) return (false);
+  if (tree.cdr.car == null) return (false);
+  return(true);
+}  
+
+// Is of form ((lambda var body) arg)?
+function isConvertable(tree) {
+  if (tree == null) return (false);
+  if (!(isBindingForm(tree.car))) return (false);
+  if (tree.car.car.cdr != "lambda") return (false);
+  if (tree.cdr == null) return (false);
+  if (tree.cdr.car == null) return (false);
+  return(true);
+}  
+
+// Is of form (lambda var body)?
+function isBindingForm(tree) {
+  if (tree == null) return (false);
+  if (tree.car == null) return (false);
+  if (tree.car.car != null) return (false);
+  if ((tree.car.cdr != "lambda") 
+         && (tree.car.cdr != "let")
+         && (tree.car.cdr != "exists")
+         && (tree.car.cdr != "forall")
+         && (tree.car.cdr != "\u03BB")
+         && (tree.car.cdr != "\u2200")
+         && (tree.car.cdr != "\u2203")
+        )
+       return (false);
+  if (tree.car.cdr == null) return (false);
+  if (tree.cdr.car == null) return (false);
+  if (tree.cdr.car.car != null) return (false);
+  if (tree.cdr.cdr == null) return (false);
+  return (true);
+}
+
+function treeToString(tree) {
+  if (tree == null) return ("")
+  if (tree.car == null) return (tree.cdr)
+  if ((tree.car).car == null) 
+       return (treeToString(tree.car) + " " + treeToString(tree.cdr))
+  return ("(" + treeToString(tree.car) + ")" + treeToString(tree.cdr))
+}
+
+// use this instead of treeToString if you want to see the full structure
+function treeToStringRaw(tree) {
+  if (tree == null) return ("@")
+  if (typeof(tree) == "string") return (tree);
+  return ("(" + treeToStringRaw(tree.car) + "." + 
+                               treeToStringRaw(tree.cdr) + ")")
+}
+
+// Make sure each paren will count as a separate token
+function stringToTree(input) {
+  input = input.replace(/let/g, " ( ( let ");
+  input = input.replace(/=/g, " ");
+  input = input.replace(/in/g, " ) ");
+  input = input.replace(/\(/g, " ( ");
+  input = input.replace(/\)/g, " ) ");
+  input = input.replace(/;.*\n/g," ");
+  input = input.replace(/\^/g, " ^ ");
+  input = input.replace(/[\\]/g, " lambda ");
+  input = input.replace(/\u03BB/g, " lambda ");
+  return ((parse(input.split(/[ \f\n\r\t\v]+/))).car)
+}
+
+// Adjust spaces to print pretty
+function formatTree(tree) {
+  output = treeToStringRaw (tree);
+  output = output.replace(/^[ \f\n\r\t\v]+/, "");
+  output = output.replace(/[ \f\n\r\t\v]+$/, "");
+  output = output.replace(/[ \f\n\r\t\v]+\)/g, ")");
+  output = output.replace(/\)([^)(])/g, ") $1");
+  output = output.replace(/lambda/g, "\\");
+//  output = output.replace(/lambda/g, "\u03BB");
+//  output = output.replace(/exists/g, "\u2203");
+//  output = output.replace(/forall/g, "\u2200");
+  return (output)
+}
+
+function mytry(form) { 
+  i = 0;
+  form.result.value = formatTree((stringToTree(form.input.value)));
+  // form.result.value = formatTree(fixedPoint(stringToTree(form.input.value)));
+}
+
+*/
+
diff --git a/code/lambda_evaluator.mdwn b/code/lambda_evaluator.mdwn
new file mode 100644 (file)
index 0000000..d39086f
--- /dev/null
@@ -0,0 +1,144 @@
+This lambda evaluator will allow you to write lambda terms and evaluate (that is, normalize) them, and inspect the results.
+(This won't work in Racket, because Racket doesn't even try to represent the internal structure of a function in a human-readable way.)  
+
+*Lambda terms*: lambda terms are written with a backslash, thus: `((\x (\y x)) z)`.  
+
+If you click "Normalize", the system will try to produce a normal-form lambda expression that your original term reduces to (~~>). So `((\x (\y x)) z)` reduces to `(\y z)`.
+
+*Let*: in order to make building a more elaborate set of terms easier, it is possible to define values using `let`.
+In this toy system, `let`s should only be used at the beginning of a file.  If we have, for intance,
+
+    let true = (\x (\y x)) in
+    let false = (\x (\y y)) in
+    ((true yes) no)
+
+the result is `yes`.
+
+*Comments*: anything following a semicolon to the end of the line is ignored.
+Blank lines are fine.
+
+*Abbreviations*: In an earlier version, you couldn't use abbreviations. `\x y. y x x` had to be written `(\x (\y ((y x) x)))`. We've upgraded the parser though, so now it should be able to understand any lambda term that you can.
+
+*Constants*: The combinators `S`, `K`, `I`, `C`, `B`, `W`, `T`, `M` (aka <code>&omega;</code>) and `L` are pre-defined to their standard values. Also, integers will automatically be converted to Church numerals. (`0` is `\s z. z`, `1` is `\s z. s z`, and so on.)
+
+*Variables*: Variables must start with a letter and can continue with any sequence of letters, numbers, `_`, `-`, or `/`. They may optionally end with `?` or `!`. When the evaluator does alpha-conversion, it may change `x` into `x'` or `x''` and so on. But you should not attempt to use primed variable names yourself.
+
+
+<textarea id="INPUT" style="border: 2px solid black; color: black; font-family: monospace; height: 3in; overflow: auto; padding: 0.5em; width: 100%;">
+let true = \x y. x in
+let false = \x y. y in
+let and = \l r. l r false in
+(
+       (and true true yes no)
+       (and true false yes no)
+       (and false true yes no)
+       (and false false yes no)
+)
+</textarea>
+<input id="PARSE" value="Normalize" type="button">
+<input id="ETA" type="checkbox">do eta-reductions too
+<noscript><p>You may not see it because you have JavaScript turned off. Uffff!</p></noscript>
+<script src="/code/lambda.js"></script>
+<script src="/code/tokens.js"></script>
+<script src="/code/parse.js"></script>
+<script src="/code/json2.js"></script>
+<pre id="OUTPUT">
+</pre>
+<script>
+/*jslint evil: true */
+
+/*members create, error, message, name, prototype, stringify, toSource,
+    toString, write
+*/
+
+/*global JSON, make_parse, parse, source, tree */
+
+// Make a new object that inherits members from an existing object.
+
+if (typeof Object.create !== 'function') {
+    Object.create = function (o) {
+        function F() {}
+        F.prototype = o;
+        return new F();
+    };
+}
+
+// Transform a token object into an exception object and throw it.
+
+Object.prototype.error = function (message, t) {
+    t = t || this;
+    t.name = "SyntaxError";
+    t.message = message;
+    throw t;
+};
+
+
+(function () {
+    var parse = make_parse();
+
+    function go(source) {
+        var string, tree, expr, eta;
+        try {
+            tree = parse(source);
+ //           string = JSON.stringify(tree, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
+                       expr = tree.handler();
+            // string = JSON.stringify(expr, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'tag', 'variable', 'left', 'right', 'bound', 'body' ], 4);
+//                     string = expr.to_string() + "\n\n~~>\n\n";
+                       string = '';
+                       eta = document.getElementById('ETA').checked;
+                       string = string + reduce(expr, eta, false).to_string();
+        } catch (e) {
+            string = JSON.stringify(e, ['name', 'message', 'from', 'to', 'key',
+                    'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
+        }
+        document.getElementById('OUTPUT').innerHTML = string
+            .replace(/&/g, '&amp;')
+            .replace(/[<]/g, '&lt;');
+    }
+
+    document.getElementById('PARSE').onclick = function (e) {
+        go(document.getElementById('INPUT').value);
+    };
+}());
+
+</script>
+
+
+
+Under the hood
+---------------
+
+The interpreter is written in JavaScript and runs inside your browser.
+So if you decide to reduce a term that does not terminate (such as `((\x (x x)) (\x (x x)))`), it will be your 
+browser that stops responding, not the wiki server.
+
+The main code is [here](http://lambda.jimpryor.net/code/lambda.js). Suggestions for improvements welcome.
+
+The code is based on: 
+
+*      Chris Barker's JavaScript lambda calculator
+*      [Oleg Kiselyov's Haskell lambda calculator](http://okmij.org/ftp/Computation/lambda-calc.html#lambda-calculator-haskell).
+*      The top-down JavaScript lexer and parser at <http://javascript.crockford.com/tdop/index.html>.
+
+Improvements we hope to add:
+
+*      detecting some common cases of non-normalizing terms (the problem of determining in general whether a term will normalize is undecidable)
+*      returning results in combinator form (the evaluator already accepts combinators as input)
+*      displaying reductions one step at a time
+*      specifying the reduction order and depth
+*      allow other binders such as &forall; and &exist; (though these won't be interpreted as doing anything other than binding variables)
+
+<a name="other_evaluators"></a>
+Other Lambda Evaluators/Calculutors
+-----------------------------------
+
+*      [Peter Sestoft's Lambda Calculus Reducer](http://www.itu.dk/people/sestoft/lamreduce/index.html): Very nice! Allows you to select different evaluation strategies, and shows stepwise reductions.
+*      [Chris Barker's Lambda Tutorial](http://homepages.nyu.edu/~cb125/Lambda)
+*      [Penn Lambda Calculator](http://www.ling.upenn.edu/lambda/): Pedagogical software developed by Lucas Champollion, Josh Tauberer and Maribel Romero.  Linguistically oriented. Requires installing Java (Mac users will probably already have it installed).
+*      [Mike Thyer's Lambda Animator](http://thyer.name/lambda-animator/): Graphical tool for experimenting with different reduction strategies. Also requires installing Java, and Graphviz.
+*      [Matt Might's Lambda Evaluator](http://matt.might.net/articles/implementing-a-programming-language/) in Scheme (R5RS and Racket).
+
+See also:
+
+*      [Jason Jorendorff's Try Scheme](http://tryscheme.sourceforge.net/about.html): Runs a miniature Scheme interpreter in Javascript, in your browser.
+
diff --git a/code/lambda_library.mdwn b/code/lambda_library.mdwn
new file mode 100644 (file)
index 0000000..e170dcf
--- /dev/null
@@ -0,0 +1,392 @@
+Here are a bunch of pre-tested operations for the untyped lambda calculus. In some cases multiple versions are offered.
+
+Some of these are drawn from:
+
+*      [[!wikipedia Lambda calculus]]
+*      [[!wikipedia Church encoding]]
+*      Oleg's [Basic Lambda Calculus Terms](http://okmij.org/ftp/Computation/lambda-calc.html#basic)
+
+and all sorts of other places. Others of them are our own handiwork.
+
+
+**Spoilers!** Below you'll find implementations of map and filter for v3 lists, and several implementations of leq for Church numerals. Those were all requested in Assignment 2; so if you haven't done that yet, you should try to figure them out on your own. (You can find implementations of these all over the internet, if you look for them, so these are no great secret. In fact, we'll be delighted if you're interested enough in the problem to try to think through alternative implementations.)
+
+
+       ;; booleans
+       let true = \y n. y  in ; aka K
+       let false = \y n. n  in ; aka K I
+       let and = \p q. p q false  in ; or
+       let and = \p q. p q p  in ; aka S C I
+       let or = \p q. p true q  in ; or
+       let or = \p q. p p q  in ; aka M
+       let not = \p. p false true  in ; or
+       let not = \p y n. p n y  in ; aka C
+       let xor = \p q. p (not q) q  in
+       let iff = \p q. not (xor p q)  in ; or
+       let iff = \p q. p q (not q)  in
+
+       ;; tuples
+       let make_pair = \x y f. f x y  in
+       let get_fst = \x y. x  in ; aka true
+       let get_snd = \x y. y  in ; aka false
+       let make_triple = \x y z f. f x y z  in
+
+
+       ;; Church numerals
+       let zero = \s z. z  in ; aka false
+       let one = \s z. s z  in ; aka I
+       let succ = \n s z. s (n s z)  in
+       ; for any Church numeral n > zero : n (K y) z ~~> y
+       let iszero = \n. n (\x. false) true  in
+
+       let add = \m n. m succ n  in ; or
+       let add = \m n s z. m s (n s z)  in
+       let mul = \m n. m (\z. add n z) zero  in ; or
+       let mul = \m n s. m (n s)  in
+       let pow = \b exp. exp (mul b) one  in ; or
+       ; b succ : adds b
+       ; b (b succ) ; adds b b times, ie adds b^2
+       ; b (b (b succ)) ; adds b^2 b times, ie adds b^3
+       ; exp b succ ; adds b^exp
+       let pow = \b exp s z. exp b s z  in
+
+       ; three strategies for predecessor
+       let pred_zero = zero  in
+       let pred = (\shift n. n shift (make_pair zero pred_zero) get_snd)
+               ; where shift is
+               (\p. p (\x y. make_pair (succ x) x))  in ; or
+       ; from Oleg; observe that for any Church numeral n: n I ~~> I
+       let pred = \n. iszero n zero
+                                       ; else
+                                       (n (\x. x I ; when x is the base term, this will be K zero
+                                                         ; when x is a Church numeral, it will be I
+                                               (succ x))
+                                         ; base term
+                                         (K (K zero))
+                                       )  in
+       ; from Bunder/Urbanek
+       let pred = \n s z. n (\u v. v (u s)) (K z) I  in ; or
+
+       ; inefficient but simple comparisons
+       let leq = \m n. iszero (n pred m)  in
+       let lt = \m n. not (leq n m)  in
+       let eq = \m n. and (leq m n) (leq n m)  in ; or
+
+       ; more efficient comparisons, Oleg's gt provided some simplifications
+       let leq = (\base build consume. \m n. n consume (m build base) get_fst)
+                       ; where base is
+                       (make_pair true junk)
+                       ; and build is
+                       (\p. make_pair false p)
+                       ; and consume is
+                       (\p. p get_fst p (p get_snd))  in
+       let lt = \m n. not (leq n m)  in
+       let eq = (\base build consume. \m n. n consume (m build base) get_fst)
+                       ; 2nd element of a pair will now be of the form (K sthg) or I
+                       ; we supply the pair being consumed itself as an argument
+                       ; getting back either sthg or the pair we just consumed
+                       ; base is
+                       (make_pair true (K (make_pair false I)))
+                       ; and build is
+                       (\p. make_pair false (K p))
+                       ; and consume is
+                       (\p. p get_snd p)  in
+
+
+       ; -n is a fixedpoint of \x. add (add n x) x
+       ; but unfortunately Y that_function doesn't normalize
+       ; instead:
+       let sub = \m n. n pred m  in ; or
+       ; how many times we can succ n until m <= result
+       let sub = \m n. (\base build. m build base (\cur fin sofar. sofar))
+                               ; where base is
+                               (make_triple n false zero)
+                               ; and build is
+                               (\t. t (\cur fin sofar. or fin (leq m cur)
+                                               (make_triple cur true sofar) ; enough
+                                               (make_triple (succ cur) false (succ sofar)) ; continue
+                               ))  in
+       ; or
+       let sub = (\base build consume. \m n. n consume (m build base) get_fst)
+                       ; where base is
+                       (make_pair zero I) ; see second defn of eq for explanation of 2nd element
+                       ; and build is
+                       (\p. p (\x y. make_pair (succ x) (K p)))
+                       ; and consume is
+                       (\p. p get_snd p)  in
+
+
+       let min = \m n. sub m (sub m n)  in
+       let max = \m n. add n (sub m n)  in
+
+
+       ; (m/n) is a fixedpoint of \x. add (sub (mul n x) m) x
+       ; but unfortunately Y that_function doesn't normalize
+       ; instead:
+       ; how many times we can sub n from m while n <= result
+       let div = \m n. (\base build. m build base (\cur go sofar. sofar))
+                               ; where base is
+                               (make_triple m true zero)
+                               ; and build is
+                               (\t. t (\cur go sofar. and go (leq n cur)
+                                               (make_triple (sub cur n) true (succ sofar)) ; continue
+                                               (make_triple cur false sofar) ; enough
+                               ))  in
+    ; what's left after sub n from m while n <= result
+    let mod = \m n. (\base build. m build base (\cur go. cur))
+                ; where base is
+                (make_pair m true)
+                ; and build is
+                (\p. p (\cur go. and go (leq n cur)
+                        (make_pair (sub cur n) true) ; continue
+                        (make_pair cur false) ; enough
+                ))  in
+
+       ; or
+       let divmod = (\base build mtail. \m n.
+                                       (\dhead. m (mtail dhead) (\sel. dhead (sel 0 0)))
+                                                       (n build base (\x y z. z junk))
+                                                       (\t u x y z. make_pair t u) )
+                               ; where base is
+                               (make_triple succ (K 0) I) ; see second defn of eq for explanation of 3rd element
+                               ; and build is
+                       (\t. make_triple I succ (K t))
+                               ; and mtail is
+                               (\dhead d. d (\dz mz df mf drest sel. drest dhead (sel (df dz) (mf mz))))  in
+       let div = \n d. divmod n d get_fst  in
+       let mod = \n d. divmod n d get_snd  in
+
+
+       ; sqrt n is a fixedpoint of \x. div (div (add n (mul x x)) 2) x
+       ; but unfortunately Y that_function doesn't normalize
+
+
+       ; (log base b of m) is a fixedpoint of \x. add (sub (pow b x) m) x
+       ; but unfortunately Y that_function doesn't normalize
+       ; instead:
+       ; how many times we can mul b by b while result <= m
+       let log = \m b. (\base build. m build base (\cur go sofar. sofar))
+               ; where base is
+               (make_triple b true 0)
+               ; and build is
+               (\t. t (\cur go sofar. and go (leq cur m)
+                          (make_triple (mul cur b) true (succ sofar)) ; continue
+                          (make_triple cur false sofar) ; enough
+               ))  in
+
+
+       ;; fixed point combinators
+       ; Curry/Rosenbloom's
+       let Y = \f. (\h. f (h h)) (\h. f (h h))  in
+       ; Turing's
+       let Theta = (\u f. f (u u f)) (\u f. f (u u f))  in
+
+
+       ; now you can search for primes, do encryption :-)
+       let gcd = Y (\gcd m n. iszero n m (gcd n (mod m n)))  in ; or
+       let gcd = \m n. iszero m n (Y (\gcd m n. iszero n m (lt n m (gcd (sub m n) n) (gcd m (sub n m)))) m n)  in
+       let lcm = \m n. or (iszero m) (iszero n) 0 (mul (div m (gcd m n)) n)  in
+
+
+       ;; version 1 lists
+       let empty = make_pair true junk  in
+       let make_list = \h t. make_pair false (make_pair h t)  in
+       let isempty = \lst. lst get_fst  in
+       let head = \lst. isempty lst err (lst get_snd get_fst)  in
+       let tail_empty = empty  in
+       let tail = \lst. isempty lst tail_empty (lst get_snd get_snd)  in
+
+       let length = Y (\length lst. isempty lst 0 (succ (length (tail lst))))  in
+       let fold = Y (\fold lst f z. isempty lst z (f (head lst) (fold (tail lst) f z)))  in
+       let map = \f. Y (\map lst. isempty lst empty (make_list (f (head lst)) (map (tail lst))))  in
+       let filter = \f. Y (\filter lst. isempty lst empty (f (head lst) (make_list (head lst)) I (filter (tail lst))))  in
+
+
+       ;; version 3 (right-fold) lists
+       let empty = \f z. z  in
+       let make_list = \h t f z. f h (t f z)  in
+       let isempty = \lst. lst (\h sofar. false) true  in
+       let head = \lst. lst (\h sofar. h) err  in
+       let tail_empty = empty  in
+       let tail = \lst. (\shift. lst shift (make_pair empty tail_empty) get_snd)
+                               ; where shift is
+                               (\h p. p (\t y. make_pair (make_list h t) t))  in
+       let length = \lst. lst (\h sofar. succ sofar) 0  in
+       let map = \f lst. lst (\h sofar. make_list (f h) sofar) empty  in
+       let filter = \f lst. lst (\h sofar. f h (make_list h sofar) sofar) empty  in ; or
+       let filter = \f lst. lst (\h. f h (make_list h) I) empty  in
+       let singleton = \x f z. f x z  in
+       ; append [a;b;c] [x;y;z] ~~> [a;b;c;x;y;z]
+       let append = \left right. left make_list right  in
+       ; very inefficient but correct reverse
+       let reverse = \lst. lst (\h sofar. append sofar (singleton h)) empty  in ; or
+       ; more efficient revappend, reverse
+       ; revappend [a;b;c] [x;y] ~~> [c;b;a;x;y]
+       ; make_left_list a (make_left_list b (make_left_list c empty)) ~~> \f z. f c (f b (f a z))
+       let revappend = (\make_left_lst left right. left make_left_list right) (\h t f z. t f (f h z))  in
+       ; from Oleg, of course it's the most elegant
+       let revappend = \left. left (\hd sofar. \right. sofar (make_list hd right)) I  in
+       let rev = \lst. revappend lst empty  in
+       ; zip [a;b;c] [x;y;z] ~~> [(a,x);(b,y);(c,z)]
+       let zip = \left right. (\base build. reverse left build base (\x y. reverse x))
+                                          ; where base is
+                                          (make_pair empty (map (\h u. u h) right))
+                                          ; and build is
+                                          (\h sofar. sofar (\x y. isempty y
+                                                                                          sofar
+                                                                                          (make_pair (make_list (\u. head y (u h)) x)  (tail y))
+                                          ))  in
+       let all = \f lst. lst (\h sofar. and sofar (f h)) true  in
+       let any = \f lst. lst (\h sofar. or sofar (f h)) false  in
+
+
+       ;; left-fold lists
+       let make_list = \h t f z. t f (f h z)  in
+       let head = \lst. lst (\h sofar. (K (sofar (K h))) ) (\k. k err) I  in
+       let tail = \lst. (\shift. lst shift (\a b. a tail_empty) I I)
+                               (\h p. p (\j a b. b empty) (\t a b. b (\f z. f h (t f z))) )  in
+
+
+       ;; version 5 (CPS right-fold) lists
+       ; [] is \f z c a. c z
+       ; [1] is \f z c a. f 1 z c a
+       ; [1;2] is \f z c a. f 2 z (\z. f 1 z c a) a
+       ; [1;2;3] is \f z c a. f 3 z (\z. f 2 z (\z. f 1 z c a) a) a
+       let empty = \f2 z continue_handler abort_handler. continue_handler z  in
+       let isempty = \lst larger_computation. lst
+                       ; here's our f2
+                       (\hd sofar continue_handler abort_handler. abort_handler false)
+                       ; here's our z
+                       true
+                       ; here's the continue_handler for the leftmost application of f2
+                       larger_computation
+                       ; here's the abort_handler
+                       larger_computation  in
+       let make_list = \h t. \f2 z continue_handler abort_handler.
+               t f2 z (\sofar. f2 h sofar continue_handler abort_handler) abort_handler  in
+       let head = \lst larger_computation. lst
+                       ; here's our f2
+                       (\hd sofar continue_handler abort_handler. continue_handler hd)
+                       ; here's our z
+                       err
+                       ; here are our continue_handler and abort_handler
+                       larger_computation unused  in
+       let tail_empty = empty  in
+       let tail = \lst larger_computation. lst
+                       ; here's our f2
+                       (\h sofar continue_handler abort_handler. continue_handler (sofar (\t y. make_pair (make_list h t) t)))
+                       ; here's our z
+                       (make_pair empty tail_empty)
+                       ; here are our continue_handler and abort_handler
+                       (\sofar. sofar (\x y. larger_computation y)) unused  in
+
+       ;; CPS left-fold lists
+       ; [] is \f z c a. c z
+       ; [1] is \f z c a. f 1 z  (\z. c z) a
+       ; [1;2] is \f z c a. f 1 z (\z. f 2 z (\z. c z) a) a
+       ; [1;2;3] is \f z c a. f 1 z (\z. f 2 z (\z. f 3 z (\z. c z) a) a) a
+       let make_right_list = make_list  in
+       let make_list = \h t. \f2 z continue_handler abort_handler.
+               f2 h z (\z. t f2 z continue_handler abort_handler) abort_handler  in
+       let head = \lst larger_computation. lst
+                       ; here's our f2
+                       (\hd sofar continue_handler abort_handler. abort_handler hd)
+                       ; here's our z
+                       err
+                       ; here are our continue_handler and abort_handler
+                       larger_computation larger_computation  in
+       let tail = \lst larger_computation. lst
+                       ; here's our f2
+                       (\h sofar continue_handler abort_handler. continue_handler (sofar (\j a b. b empty) (\t a b. b (make_right_list h t)) ) )
+                       ; here's our z
+                       (\a b. a tail_empty)
+                       ; here are our continue_handler and abort_handler
+                       (\sofar. sofar larger_computation larger_computation) unused  in
+
+
+
+       true
+
+<!--
+
+       ; numhelper 0 f z ~~> z
+       ; when n > 0: numhelper n f z ~~> f (pred n)
+       ; compare Bunder/Urbanek pred
+       let numhelper = \n. n (\u v. v (u succ)) (K 0) (\p f z. f p)  in
+
+       ; accepts fixed point combinator as a parameter, so you can use different ones
+       let fact = \y. y (\self n. numhelper n (\p. mul n (self p)) 1)  in
+
+
+
+       fact Theta 3  ; returns 6
+-->
+
+<!--
+       ; my original efficient comparisons
+       let leq = (\base build consume. \m n. n consume (m build base) get_fst (\x. false) true)
+                       ; where base is
+                       (make_pair zero I) ; supplying this pair as an arg to its 2nd term returns the pair
+                       ; and build is
+                       (\p. p (\x y. make_pair (succ x) (K p))) ; supplying the made pair as an arg to its 2nd term returns p (the previous pair)
+                       ; and consume is
+                       (\p. p get_snd p)  in
+       let lt = \m n. not (leq n m)  in
+       let eq = (\base build consume. \m n. n consume (m build base) true (\x. false) true)
+                       ; where base is
+                       (make_pair zero (K (make_pair one I)))
+                       ; and build is
+                       (\p. p (\x y. make_pair (succ x) (K p)))
+                       ; and consume is
+                       (\p. p get_snd p)  in ; or
+-->
+
+<!--
+       gcd
+       pow_mod
+
+
+       show Oleg's definition of integers:
+               church_to_int = \n sign. n
+               church_to_negint = \n sign s z. sign (n s z)
+
+               ; int_to_church
+               abs = \int. int I
+
+               sign_case = \int ifpos ifzero ifneg. int (K ifneg) (K ifpos) ifzero
+
+               negate_int = \int. sign_case int (church_to_negint (abs int)) zero (church_to_int (abs int))
+
+       for more, see http://okmij.org/ftp/Computation/lambda-calc.html#neg
+
+
+-->
+
+<!--
+let list_equal =
+    \left right. left
+                ; here's our f
+                (\hd sofar.
+                    ; deconstruct our sofar-pair
+                    sofar (\might_be_equal right_tail.
+                        ; our new sofar
+                        make_pair
+                        (and (and might_be_equal (not (isempty right_tail))) (eq? hd (head right_tail)))
+                        (tail right_tail)
+                    ))
+                ; here's our z
+                ; we pass along the fold a pair
+                ; (might_for_all_i_know_still_be_equal?, tail_of_reversed_right)
+                ; when left is empty, the lists are equal if right is empty
+                (make_pair
+                    true ; for all we know so far, they might still be equal
+                    (reverse right)
+                )
+                ; when fold is finished, check sofar-pair
+                (\might_be_equal right_tail. and might_be_equal (isempty right_tail))
+
+; most elegant
+let list_equal = \left. left (\hd sofar. \right. and (and (not (isempty right)) (eq hd (head right))) (sofar (tail right))) isempty
+
+-->
+
diff --git a/code/parse.js b/code/parse.js
new file mode 100644 (file)
index 0000000..5cdeb40
--- /dev/null
@@ -0,0 +1,347 @@
+// Parser for lambda with let written in Simplified JavaScript
+//      by Jim Pryor 2010-09-22
+//      Stripped down from Top Down Operator Precedence : parse.js
+//      http://javascript.crockford.com/tdop/index.html
+//      Douglas Crockford 2010-06-26
+
+//      See also http://effbot.org/zone/simple-top-down-parsing.htm
+
+
+/*jslint onevar: false
+ */
+
+/*   members create, error, message, name, prototype, stringify, toSource,
+    toString, write
+*/
+
+/*global make_var, make_app, make_lam, Lambda_var */
+
+var make_parse = function () {
+    var symbol_table = {};
+    var token;
+    var tokens;
+    var token_nr;
+
+    var advance = function (id) {
+        var a, o, t, v;
+        if (id && token.id !== id) {
+            token.error("Expected '" + id + "'.");
+        }
+        if (token_nr >= tokens.length) {
+            token = symbol_table["(end)"];
+            return;
+        }
+        t = tokens[token_nr];
+        token_nr += 1;
+        v = t.value;
+        a = t.type;
+        if (a === "name") {
+            o = symbol_table[v];
+            if (!o || typeof o === 'function') {
+                o = symbol_table["(name)"];
+            } else {
+                a = o.arity || "keyword";
+            }
+        } else if (a ===  "number") {
+            o = symbol_table["(number)"];
+                       a = "literal";
+        } else if (a === "operator") {
+            o = symbol_table[v];
+            if (!o) {
+                t.error("Unknown operator.");
+            }
+            a = "keyword";
+        } else {
+            t.error("Unexpected token.");
+        }
+        token = Object.create(o);
+        token.from  = t.from;
+        token.to    = t.to;
+        token.value = v;
+        token.arity = a; // will be: name, keyword, literal
+        return token;
+    };
+
+    var original_symbol = {
+        handler: function () {
+            this.error("Undefined.");
+        }
+    };
+
+       /*
+       try {
+               if (console && console.debug) {
+                       function print() {
+                               console.debug.apply(this, arguments);
+                       }
+               }
+       } catch (e) {}
+       */
+
+    var symbol = function (id) {
+        var s = symbol_table[id];
+        if (!s) {
+            s = Object.create(original_symbol);
+            s.id = s.value = id;
+            symbol_table[id] = s;
+        }
+        return s;
+    };
+
+    var var_table;
+    var name_table;
+
+    var name_handler = function () {
+        var n = name_table[this.value];
+        if (!n) {
+            n = make_var(this.value);
+            var_table[this.value] = n;
+            n = new Lambda_var(n);
+            name_table[this.value] = n;
+        }
+        if (this.first) {
+            return make_app(this.first.handler(), n);
+        } else {
+            return n;
+        }
+    };
+
+    var branch_handler = function () {
+        var n = this.second.handler();
+        if (this.first) {
+            return make_app(this.first.handler(), n);
+        } else {
+            return n;
+        }
+    };
+
+    var lambda_handler = function () {
+        var body = this.second.handler();
+        var n, v;
+        while (this.first.length) {
+            n = this.first.pop().value;
+            v = var_table[n];
+            if (!v) {
+                v = make_var(n);
+                var_table[n] = v;
+                name_table[n] = new Lambda_var(v);
+            }
+            body = make_lam(v, body);
+        }
+        return body;
+    };
+
+    symbol("(end)");
+    symbol("(name)").handler = name_handler;
+    symbol("let").handler = lambda_handler;
+    symbol("=").handler = branch_handler;
+    symbol("in");
+    symbol(")").handler = branch_handler;
+    symbol("(");
+    symbol("\\").handler = lambda_handler;
+    symbol("lambda").handler = lambda_handler;
+    symbol("\u03bb").handler = lambda_handler;
+    // symbol("\u2203").handler = exists_handler;
+    // symbol("\u2200").handler = forall_handler;
+    symbol(".");
+
+       function make_constants() {
+
+               function make_lam2(a, b, aa) {
+                       return make_lam(a, make_lam(b, aa));
+               }
+               function make_lam3(a, b, c, aa) {
+                       return make_lam(a, make_lam(b, make_lam(c, aa)));
+               }
+               function make_app3(aa, bb, cc) {
+                       return make_app(make_app(aa, bb), cc);
+               }
+               var u = make_var("u");
+               var v = make_var("v");
+               var x = make_var("x");
+               var s = make_var("s");
+               var z = make_var("z");
+               var uu = new Lambda_var(u);
+               var vv = new Lambda_var(v);
+               var xx = new Lambda_var(x);
+               var ss = new Lambda_var(s);
+               var zz = new Lambda_var(z);
+               var_table = { u: u, v: v, x: x, s: s, z: z};
+               name_table = {u: uu, v: vv, x: xx, s: ss, z: zz};
+               number_table = {};
+
+               // constants have their own id and arity = literal
+               // numbers have id = "(number)" and arity = literal
+               symbol("(number)").handler = function () {
+                       var n = this.value;
+                       var res = number_table[n];
+                       if (!res) {
+                               res = zz;
+                               while (n > 0) {
+                                       n -= 1;
+                                       res = make_app(ss, res);
+                               }
+                               res = make_lam2(s, z, res);
+                               number_table[this.value] = res;
+                       }
+                       if (this.first) {
+                               return make_app(this.first.handler(), res);
+                       } else {
+                               return res;
+                       }
+               }
+
+               var constant = function (s, v) {
+                       var x = symbol(s);
+                       x.handler = function () {
+                               this.value = symbol_table[this.id].value;
+                               if (this.first) {
+                                       return make_app(this.first.handler(), this.value);
+                               } else {
+                                       return this.value;
+                               }
+                       };
+                       x.arity = "literal";
+                       x.value = v;
+                       return x;
+               };
+
+               constant("S", make_lam3(u, v, x, make_app3(uu, xx, make_app(vv, xx))));
+               constant("K", make_lam2(u, v, uu));
+               constant("I", make_lam(x, xx));
+               constant("B", make_lam3(u, v, x, make_app(uu, make_app(vv, xx))));
+               constant("C", make_lam3(u, v, x, make_app3(uu, xx, vv)));
+
+               // trush \uv.vu = CI
+               constant("T", make_lam2(u, v, make_app(vv, uu)));
+               // mockingbird \u.uu = SII
+               constant("M", make_lam(u, make_app(uu, uu)));
+               // warbler \uv.uvv = C(BM(BBT) = C(BS(C(BBI)I))I
+               constant("W", make_lam2(u, v, make_app3(uu, vv, vv)));
+               // lark \uv.u(vv) = CBM = BWB
+               constant("L", make_lam2(u, v, make_app(uu, make_app(vv, vv))));
+               // Y is SLL
+
+       }
+       make_constants();
+
+    var expression = function (in_let) {
+        var t, n;
+        if (token.id === "\\" || token.id === "lambda") {
+            token.value = "lambda";
+            t = token;
+            advance();
+            n = token;
+            if (n.arity !== "name") {
+                n.error("Expected a variable name.");
+            }
+            advance();
+            if (token.id === "(") {
+                t.first = [n];
+                advance();
+                t.second = expression(false);
+                advance(")");
+                return t;
+            } else {
+                t.first = [];
+                while (token.arity === "name" || token.id === "\\") {
+                   if (token.id !== "\\") {
+                      t.first.push(n);
+                      n = token;
+                   }
+                    advance();
+                }
+                               if (token.arity === "literal" && t.first.length === 0) {
+                                       t.first.push(n);
+                                       t.second = token;
+                                       advance();
+                               } else if (token.id === ".") {
+                    t.first.push(n);
+                    advance();
+                    t.second = expression(in_let);
+                } else if (t.first.length === 1) {
+                    t.second = n;
+                } else {
+                    t.first.push(n);
+                    t.error("Can't parse lambda abstract.");
+                }
+                return t;
+            }
+        } else {
+            n = null;
+            while (token.id === "(") {
+                advance();
+                t = expression(false);
+                token.first = n;
+                token.second = t;
+                n = token;
+                advance(")");
+                if (in_let && token.id === "let" || token.id === "(end)" || token.id === ")") {
+                    return n;
+                }
+            }
+            while (true) {
+                               if (n && (in_let && token.id === "in" || token.id === "(end)" || token.id === ")")) {
+                    return n;
+                } else if (token.id === "(") {
+                    advance();
+                    t = expression(false);
+                    token.first = n;
+                    token.second = t;
+                    n = token;
+                    advance(")");
+                } else {
+                    if (token.arity !== "name" && token.arity !== "literal") {
+                        token.error("Expected a variable name or literal.");
+                    }
+                    token.first = n;
+                    n = token;
+                    advance();
+                }
+            }
+        }
+       };
+
+    return function (source) {
+        tokens = source.tokens();
+        token_nr = 0;
+        advance();
+        
+        // let n = c in b
+        // (\n. b) c
+
+        var t = null, eq, c, base = {};
+        var target = base;
+
+        while (token.id === "let") {
+            t = token;
+            advance();
+            if (token.arity !== "name") {
+                token.error("Expected a variable name.");
+            }
+            t.first = [token];
+            advance();
+            eq = token; // token.id === "="
+            advance("=");
+            c = expression(true);
+
+                       eq.first = t;
+                       eq.second = c;
+                       target.second = eq;
+
+//             c.first = eq;
+//             eq.second = t;
+//             target.second = c;
+
+            target = t;
+            advance("in");
+        }
+    
+        target.second = expression(false);
+
+        advance("(end)");
+        return base.second;
+    };
+
+};
+
diff --git a/code/tokens.js b/code/tokens.js
new file mode 100644 (file)
index 0000000..c6630fa
--- /dev/null
@@ -0,0 +1,180 @@
+// Based on tokens.js
+//      2009-05-17
+//      (c) 2006 Douglas Crockford
+
+//      Produce an array of simple token objects from a string.
+//      A simple token object contains these members:
+//           type: 'name', 'string', 'number', 'operator'
+//           value: string or number value of the token
+//           from: index of first character of the token
+//           to: index of the last character + 1
+
+//      Comments of the ; type are ignored.
+
+//      Operators are by default single characters. Multicharacter
+//      operators can be made by supplying a string of multi_start and
+//      multi_continue characters.
+//      characters. For example,
+//           '<>+-&', '=>&:'
+//      will match any of these:
+//           <=  >>  >>>  <>  >=  +: -: &: &&: &&
+
+/*jslint onevar: false
+ */
+
+String.prototype.tokens = function (multi_start, multi_continue) {
+    var c;                      // The current character.
+    var from;                   // The index of the start of the token.
+    var i = 0;                  // The index of the current character.
+    var length = this.length;
+    var n;                      // The number value.
+    var q;                      // The quote character.
+    var str;                    // The string value.
+
+    var result = [];            // An array to hold the results.
+
+    var make = function (type, value) {
+
+// Make a token object.
+
+        return {
+            type: type,
+            value: value,
+            from: from,
+            to: i
+        };
+    };
+
+// Begin tokenization. If the source string is empty, return nothing.
+
+    if (!this) {
+        return;
+    }
+
+// If multi_start and multi_continue strings are not provided, supply defaults.
+
+    if (typeof multi_start !== 'string') {
+        multi_start = '';
+    }
+    if (typeof multi_continue !== 'string') {
+        multi_continue = '';
+    }
+
+
+// Loop through this text, one character at a time.
+
+    c = this.charAt(i);
+    while (c) {
+        from = i;
+
+// Ignore whitespace.
+
+        if (c <= ' ') {
+            i += 1;
+            c = this.charAt(i);
+
+// name.
+
+        } else if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
+            str = c;
+            i += 1;
+            for (;;) {
+                c = this.charAt(i);
+                if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
+                        (c >= '0' && c <= '9') || c === '_' || c === '-' || c === '/') {
+                    str += c;
+                    i += 1;
+                               } else if (c === '?' || c === '!') {
+                               // should only be terminal
+                    str += c;
+                    i += 1;
+                                       c = this.charAt(i);
+                               // make sure next character is not an identifier
+                                       if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
+                                               (c >= '0' && c <= '9') || c === '_' || c === '-' || c === '/' || c === '?' || c === '!') {
+                                               str += c;
+                                               i += 1;
+                                               make('name', str).error("Bad identifier");
+                                       }
+                               } else {
+                    break;
+                }
+            }
+            result.push(make('name', str));
+
+// number.
+
+// A number cannot start with a decimal point. It must start with a digit,
+// possibly '0'.
+
+        } else if (c >= '0' && c <= '9') {
+            str = c;
+            i += 1;
+
+// Look for more digits.
+
+            for (;;) {
+                c = this.charAt(i);
+                if (c < '0' || c > '9') {
+                    break;
+                }
+                i += 1;
+                str += c;
+            }
+
+// Make sure the next character is not a letter.
+
+            if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c === '_') {
+                str += c;
+                i += 1;
+                make('number', str).error("Bad number");
+            }
+
+// Convert the string value to a number. If it is finite, then it is a good
+// token.
+
+            n = +str;
+            if (isFinite(n)) {
+                result.push(make('number', n));
+            } else {
+                make('number', str).error("Bad number");
+            }
+
+// comment.
+
+        } else if (c === ';') {
+            for (;;) {
+                c = this.charAt(i);
+                if (c === '\n' || c === '\r' || c === '') {
+                    break;
+                }
+                i += 1;
+            }
+
+// multi-char operator.
+
+        } else if (multi_start.indexOf(c) >= 0) {
+            str = c;
+            i += 1;
+            while (i < length) {
+                c = this.charAt(i);
+                if (multi_continue.indexOf(c) < 0) {
+                    break;
+                }
+                str += c;
+                i += 1;
+            }
+            result.push(make('operator', str));
+
+// single-character operator.
+
+        } else {
+            i += 1;
+            result.push(make('operator', c));
+            c = this.charAt(i);
+        }
+    }
+    return result;
+};
+
+
index 5e9c052..4576a9b 100644 (file)
@@ -39,9 +39,13 @@ These block comments also nest. Another form of block comments is `#;( ... )`. T
 
 
 
-### Variable names
+### Variables
 
-% Haskell's division into letter-based vs operators. Each can be "flagged" to temporarily behave as though it belonged to the other syntactic category (see below).
+Our [[syntax for variables|topics/week1#variables]] in Kapulet is close to that in the other languages. Haskell and OCaml differ only in that they do not permit trailing `?` or `!`; however, they do permit trailing `'`s (and even permit `'`s *in the middle* of a variable too, which Kapulet does not). Scheme permits all of these characters, plus many more punctuation symbols as well, to occur anywhere in a variable. Scheme also permits variables to begin with capital letters, or to consist solely of the single character `_`; but the other languages reserve these terms for special purposes.
+
+In addition to the variables made of letters (more properly, of alphanumerics), Haskell and OCaml and Kapulet also permit some variables made exclusively of punctuation symbols, like `<` or Haskell's `>=>` and `<$>`. In Haskell, these always have infix syntax, and the variables made of letters never do. (But the former can have their infix syntax suppressed with parentheses, and the latter can be "flagged" to temporarily take on infix syntax, as we'll discuss below.)
+
+In OCaml and Kapulet, some variables made of letters also have infix syntax, such as `comp` in Kapulet or `mod` in OCaml. I haven't presented to you the complex mechanisms needed to declare this.
 
 
 
@@ -56,9 +60,9 @@ not:
 
     + 1 2
 
-Although all three of these languages permits you to enclose an infix operator in parentheses to make a *section*, which no longer has infix syntax. In Kapulet, `( + )` is the same as &lambda; `(x, y). x + y`, whereas in OCaml and Haskell it's a *curried* function, which we can write (in Kapulet syntax) as &lambda; `x y. x + y`.
+Although all three of these languages permits you to enclose an infix operator in parentheses to make a *section*, which no longer has infix syntax. In Kapulet, `( + )` is the same as &lambda; `(x, y). x + y`, whereas in OCaml and Haskell it's a *curried* function, which we can write (in Kapulet syntax) as &lambda; `x y. x + y`. We'll discuss sections and curried functions below.
 
-Kapulet and OCaml have some operators spelled with letters also taking infix syntax, such as `comp` in Kapulet or `mod` in OCaml. In Haskell, this is never the case: variables that are made of letters are only treated as function terms being applied to arguments *when they're at the start* of a list of expressions; and variables that are made of punctuation symbols, and not enclosed in parentheses, will only be treated as infix operators. However, Haskell permits you to temporarily "flag" a letter-made function term to behave like an infix operator, by enclosing it in `` ` `` marks. Thus in Haskell you can write:
+Kapulet and OCaml have some operators spelled with letters also taking infix syntax, such as `comp` in Kapulet or `mod` in OCaml. In Haskell, this is never the case: variables that are made of letters are only treated as function terms being applied to arguments *when they're at the start* of a list of expressions; and variables that are made of punctuation symbols, and not enclosed in parentheses, will only be treated as infix operators. However, Haskell permits you to temporarily "flag" a  function term made of letters to behave like an infix operator, by enclosing it in `` ` `` marks. Thus in Haskell you can write:
 
     3 `mod` 2
 
@@ -72,13 +76,16 @@ and the like. Moreover, in Scheme parentheses are never optional and never redun
 
     ((+) 3 2)
 
-what that would mean is that `+` is first being applied to *zero* arguments, which is different from not applying it all. (In Kapulet, OCaml, and Haskell, one would write that `f` is being applied to "zero arguments" like this: `f ()`.) Scheme helpfully defines the result of applying `+` to zero arguments to be `0`. So `((+) 3 2)` would evaluate to whatever `(0 3 2)` does, and that's an error, because `0` is not a function.
+what that would mean is that `+` is first being applied to *zero* arguments, which is different from not applying it all. (In Kapulet, OCaml, and Haskell, one would write that `f` is being applied to "zero arguments" like this: `f ()`. FIXME) Scheme helpfully defines the result of applying `+` to zero arguments to be `0`. So `((+) 3 2)` would evaluate to whatever `(0 3 2)` does, and that's an error, because `0` is not a function.
 
-Note that `(0 3 2)`, although it *is*, qua expression, a list of numbers, does not evaluate to a list. To get an expression that *evaluates to* that list, you'd have to use `(list 0 3 2)` or `'(0 3 2)`. (Notice the initial `'`.)
+Note that `(0 3 2)`, although it *is*, qua expression, a list of numbers, does not evaluate to a list. To get an expression that *evaluates to* that list, you'd have to use `(list 0 3 2)` or `'(0 3 2)`. (Notice the initial `'`.) FIXME
 
 In Scheme, you can also write `(+ 3 2 10)`, and so on. You only have to write `(+ (+ 3 2) 10)` if you really want to.
 
-% Parentheses have other roles in Scheme, too.
+Parentheses have many other roles in Scheme, as well; they're a ubiquitous part of the syntax, and don't always express function application. You might sometimes feel they are overused.
+
+You may sometimes see `[ ... ]` being used instead of `( ... )`. This is just a stylistic variant, they work exactly the same. The official Scheme standard doesn't permit that, but most Scheme implementations do. It can help keep track of which closing `]` or `)` goes with which opening `[` or `)`. The opening and closing symbols always have to correspond.
+
 
 In Scheme, the default style for defining functions is as taking several arguments simultaneously, that is the *uncurried* style. In OCaml and Haskell, the default style is to define them *curried*. Curried functions can easily be partially applied:
 
@@ -112,12 +119,13 @@ Here the last displayed line will fail, because `add` expects as its argument a
 
 Kapulet essentially works like OCaml and Haskell; though for pedagogical reasons I started out by introducing uncurried definitions, rather than the *curried* definitions those other languages predominantly use.
 
-As we mentioned, in Kapulet, OCaml, and Haskell, there is a shorthand that enables you to write things like:
+[[As we mentioned|topics/week1_advanced_notes#sections]], in Kapulet, OCaml, and Haskell, there is a shorthand that enables you to write things like:
 
     # Kapulet
     let
       ten_minus match lambda x. 10 - x;
-      and_ys    match lambda x. x & ys
+      and_ys    match lambda x. x & ys;
+      plus      match lambda (x, y). x + y
     in (ten_minus, and_ys)
 
 like this:
@@ -125,7 +133,8 @@ like this:
     # Kapulet
     let
       ten_minus match (10 - );
-      and_ys    match ( & ys)
+      and_ys    match ( & ys);
+      plus      match ( + )
     in (ten_minus, and_ys)
 
 There are just minor differences between these languages. First, OCaml doesn't have the `( + 10)` or `(10 + )` forms, but only the `( + )`. Second, as a special case, OCaml doesn't permit you to do this with its list-consing operator `::`. You have to write `fun x xs -> x :: xs`, not `( :: )`. Whereas in Kapulet `( & )`, `(x & )`, and `( & xs)` are all sections using its sequence-consing operator `&`; and in Haskell, `( : )`, `(x : )`, and `( : xs)` are the same.
@@ -156,13 +165,23 @@ I know all these languages fairly well, and I still find this last issue difficu
 
 The relation that's written `==` in Kapulet is also written that way in Haskell. That symbol means something else in OCaml, having to do with mutable reference cells; to get the same notion in OCaml one writes just a single `=`. The negation of this notion is written `!=` in Kapulet, `/=` in Haskell, and `<>` in OCaml. (Again, `!=` means something else in OCaml.)
 
-The relations that are written `and`, `or`, and `not` are written in Haskell and OCaml as `&&`, `||`, and `not`. (Haskell uses `and` and `or` to express functions that form the conjunction or disjunction of every `Bool` value in a List of such. OCaml permits `or` as an old synonym for `||`, but discourages using that spelling. OCaml also permits `&` as an old, discouraged synonym for `&&`.)
+The relations that are written `and`, `or`, and `not` in Kapulet are written the same way in Scheme. Note that in Scheme the first two can take zero or more arguments:
+
+    ; Scheme
+    (and)
+    (and bool1)
+    (and bool1 bool2)
+    (and bool1 bool2 bool3)
+
+As you'd expect `(and bool1)` evaluates the same as plain `bool1`; similarly with `(or bool1)`. What do you think `(and)` with no arguments should evaluate to? How about `(or)`?
 
-Scheme %%
+These relations are written in Haskell and OCaml as `&&`, `||`, and `not`. (Haskell uses `and` and `or` to express functions that form the conjunction or disjunction of every `Bool` value in a List of such. OCaml permits `or` as an old synonym for `||`, but discourages using that spelling. OCaml also permits `&` as an old, discouraged synonym for `&&`.)
 
 The values that are written `'true` and `'false` in Kapulet are written in Haskell as `True` and `False`, and in OCaml as just `true` and `false`. They're written `#t` and `#f` in Scheme, but in Scheme in many contexts any value that isn't `#f` will behave as though it were `#t`, even values you might think are more "false-ish", like `0` and the empty list. Thus `(if 0 'yes 'no)` will evaluate to `'yes`.
 
-Scheme recognizes the values `'true` and `'false`, but it treats `'false` as distinct from `#f`, and thus as a "true-ish" value, like all of its other values that aren't `#f`.
+Some Scheme implementations, such as Racket, permit `#true` and `#false` as synonyms for `#t` and `#f`.
+
+Scheme also recognizes the values `'true` and `'false`, but it treats `'false` as distinct from `#f`, and thus as a "true-ish" value, like all of its other values that aren't `#f`. Kapulet essentially took Scheme's `boolean` values and collapsed them into being a subtype of its `symbol` values. FIXME also with chars.
 
 
 
@@ -216,8 +235,8 @@ Here are some list functions in Kapulet:
     dropwhile
     reverse
     # new functions
-    concat       # converts [[10, 20], [30], [], [40, 50]]
-                 # to [10, 20, 30, 40, 50] (only merging a single layer of []s)
+    join         # converts [[10, 20], [30], [], [40, 50]]
+                 # to [10, 20, 30, 40, 50] (but only "joining" a single layer of []s)
     (mem)        # infix syntax, 2 mem [1, 2, 3] == 'true
     nth          # nth [10, 20, 30] 1 == 20, because the first element
                  # is at position 0; fails if index is out of bounds
@@ -241,11 +260,12 @@ Here are the corresponding functions in Haskell:
     map
     zipWith  {- zip handles the special case where f is the function that forms ordered pairs
                 both zipWith and zip stop with the shortest list -}
-    unzip    -- doesn't take an f argument, assumes (\(x, y) -> (x, y))
+    unzip    {- unlike unmap2, doesn't take an explicit f argument
+                just assumes it's (\(x, y) -> (x, y)) -}
     takeWhile
     dropWhile
     reverse
-    concat
+    concat   -- corresponding to join
     elem     -- not infix syntax, but often written as: 2 `elem` [1, 2, 3]
     (!!)     -- infix syntax: [10, 20, 30] !! 1 == 20; fails if index is out of bounds
     all p xs
@@ -269,14 +289,14 @@ Here they are in OCaml:
     List.split   (* like Haskell's unzip, doesn't take an f argument *)
     (* no function corresponding to takewhile or dropwhile *)
     List.rev
-    List.concat  (* also List.flatten, which still only merges a single layer of []s *)
+    List.concat  (* also List.flatten, which still only "joins" a single layer of []s *)
     List.mem     (* not infix syntax *)
     List.nth     (* List.nth [10; 20; 30] 1 = 20; fails if index is out of bounds *)
     List.for_all p xs
     List.exists p xs
 
 
-How does all this look in Scheme? Well, Scheme has a notion they call a (proper) `list`, and also a notion they call a `vector`. There are also what Scheme calls "improper" `list`s, with `(cons 1 'nonlist)` or `'(1 . nonlist)`, where `'nonlist` is any non-list (here it's a `symbol`) being a special case. Let's ignore the improper `list`s. Scheme's (proper) `list`s and `vector`s each has a claim to correspond to Kapulet's sequences, Haskell's Lists, and OCaml's `list`s. Each is also somewhat different. The dominant differences are:
+How does all this look in Scheme? Well, Scheme has a notion they call a (proper) `list`, and also a notion they call a `vector`. There are also what Scheme calls "improper" `list`s, with `(cons 1 'nonlist)` or `'(1 . nonlist)`, where `'nonlist` is any non-list (here it's a `symbol`) being a limiting case. Let's ignore the improper `list`s. Scheme's (proper) `list`s and `vector`s each has a claim to correspond to Kapulet's sequences, Haskell's Lists, and OCaml's `list`s. Each is also somewhat different. The dominant differences are:
 
 1.  these structures in Scheme can contain heterogenously-typed elements, including further `list`s and `vector`s in some positions but not in others
 2.  in the official Scheme standard, `list`s and `vector`s are both *mutable* containers, that is, one and the same persisting `list` structure can have different
@@ -320,7 +340,7 @@ Here are the `list` functions in Scheme corresponding to the functions listed in
                       ; can take one or more list arguments
     ; no official function corresponding to unmap2 or takewhile or dropwhile
     reverse
-    ; no official function corresponding to concat
+    ; no official function corresponding to join/concat
     member            ; corresponds to Kapulet's (mem) and Haskell's elem
     (list-ref xs k)   ; corresponds to Kapulet's `nth xs k`
     ; no official function corresponding to all or any
@@ -329,9 +349,382 @@ All of the functions listed as missing from the official Scheme standard can be
 
 
 
+### Pattern-matching
+
+The complex expression that's written like this in Kapulet:
+
+    # Kapulet
+    case some_expression of
+      0 then result0;
+      1 then result1;
+      x then resultx
+    end
+
+is written very similarly in Haskell:
+
+    -- Haskell
+    case some_expression {
+      0 -> result0;
+      1 -> result1;
+      x -> resultx
+    }
+
+Unlike the other languages we're discussing, Haskell pays special attention to the whitespace/indentation of what you write. This permits you to omit the `{`, `;`, and `}`s in the above, if you've got the indentation right. And that's how you will often see Haskell code displayed. On this website, though, I propose to always include the `{`s and so on when displaying Haskell code, because the indentation rules aren't 100% intuitive. It's easy to read properly-indented Haskell code, but until you've learned and practiced the specific rules, it's not always easy to write it.
+
+This is written only a little bit differently in OCaml:
+
+    (* OCaml *)
+    match some_expression with
+      0 -> result0 |
+      1 -> result1 |
+      x -> resultx
+
+Note there is no closing `end` or `}`. You can enclose the whole expression in parentheses if you want to, and when embedding it in some larger expressions (like another `match` expression), you may need to. Sometimes the `|` dividers are written at the start of a line, and you are allowed to include an extra one before the first line, so you could also see this written as:
+
+    (* OCaml *)
+    match some_expression with
+      | 0 -> result0
+      | 1 -> result1
+      | x -> resultx
+
+The syntax for [[guards|topics/week1_advanced_notes#guards]] and [[as-patterns|topics/week1_advanced_notes#as-patterns]] also only varies slightly between these languages:
+
+    # Kapulet
+    case some_expression of
+      pat1   when guard             then result1;
+      pat1   when different_guard   then result2;
+      ((complex_pat) as var, pat4)  then result3
+    end
+
+    -- Haskell
+    case some_expression {
+      pat1 | guard              -> result1;
+           | different_guard    -> result2;
+      (var@(complex_pat), pat4) -> result3
+    }
+
+    (* OCaml *)
+    match some_expression with
+      pat1   when guard             -> result0 |
+      pat1   when different_guard   -> result1 |
+      ((complex_pat) as var, pat4   -> result3
+
+
+The official Scheme standard only provides for a limited version of this. There is a `case` construction, available since at least "version 5" of the Scheme standard (r5rs), but it only accepts literal values as patterns, not any complex patterns containing them or any patterns containing variables. Here is how it looks:
+
+    ; Scheme
+    (case some_expression
+      ((0) 'result0)
+      ((1) 'result1)
+      ((2 3 5) 'smallprime)
+      (else 'toobig))
+
+The results can be complex expressions; I just used bare symbols here for illustration. Note that the literal patterns in the first two clauses are surrounded by an extra pair of parentheses than you might expect. The reason is shown in the third clause, which begins `(2 3 5)`. This does not mean to match a list containing the values `2` `3` and `5`. Instead it means to match the simple value `2` *or* the simple value `3` *or* the simple value `5`. The final `else` clause is optional.
+
+The patterns here can be any literal value (what the Scheme standards call a "datum"). Numbers are permitted, as are boolean literals (`#t` and `#f`) and symbolic atoms (`'alpha` and the like, though inside a pattern position in a `case`-expression, you omit the initial `'`). You can also use the list literal `'()` (again, omit the initial `'` when writing it as a pattern). Some implementations of Scheme allow more complex list patterns, matching literal lists like `'(alpha 0 () #t)`; others don't.
+
+There are various add-on libraries to Scheme that will permit you to pattern-match in more ambitious ways, approximating what you can do in Kapulet, OCaml, and Haskell. We will explain some of these later, after we've introduced you to the notion of *datatypes*.
+
+What programmers using standard Scheme tend to do instead is to use *predicates* that query the type and/or structure of an unknown value, and then take separate evaluation paths depending on the result. This can be done with an `if...then...else...` construction, or with Scheme's more general `cond` construction. In Scheme, these two are equivalent:
+
+    ; Scheme
+    (if test1 'result1
+              (if test2 'result2
+                        (if test3 'result3 'somethingelse)))
+
+    (cond
+      (test1 'result1)
+      (test2 'result2)
+      (test3 'result3)
+      (else  'somethingelse))
+
+The tests tend to use predicates like `null?` (are you the empty list?), `pair?` (are you a non-empty list, whether proper or improper?), `list?` (are you a proper list, whether empty or not?), `symbol?`, `boolean?`, `number?`, `zero?` (you get the idea). But you can also use more complex tests you write on the spot, or use antecedently-defined functions:
+
+    ; Scheme...in case the parens left any doubt
+    (define smallprime? (lambda (x) (if (= x 2) #t (if (= x 3) #t (if (= x 5) #t #f)))))
+
+    (cond
+      ((= x 0) 'infant)
+      ((smallprime? x) 'myfavorite)
+      ((and (> x 10) (< x 20)) 'teenaged)
+      (else 'unknown))
+
+Remember that in Scheme, an expression doesn't have to evaluate to `#t` to be treated as "truth-like". *Every* value other than `#f` is treated as truth-like. So `(if 0 'zero 'nope)` evaluates to `'zero`.
+
+You may sometimes see Scheme `cond` constructions written with this kind of clause:
+
+    (cond
+      ...
+      (test-expression => function-value)
+      ...)
+
+That's the same as the following:
+
+    (cond
+      ...
+      (test-expression (function-value test-expression))
+      ...)
+
+Except that it only evaluates the test-expression once.
+
+The clauses in Scheme's `cond` expressions can contain *multiple* expressions after the test. This only becomes useful when you're working with mutable values and side-effects, which we've not gotten to yet. The `if` expressions only take a single expression for the "then" branch and a single expression for the "else" branch. You can turn a complex series of expressions, which may involve side-effects, into a single expression by wrapping it in a `(begin ...)` construction. The `(begin ...)` construction as a whole evaluates to whatever the last expression it contains does.
+
+Scheme standards after r5rs also provide two further conditional constructions, which are for the situations where you want to perform a meaningful action only on the "then" branch, or only on the "else" branch:
+
+    (when test-expression
+       result-expression1...)
+
+    (unless test-expression
+       result-expression2...)
+
+If the test-expression evaluates to `#f`, then the `when` expression evaluates to a special "void" value; mutatis mutandis for the `unless` expression. This is analogous to `()` in OCaml, Haskell, and Kapulet.
+
+In the last three languages, the expressions in the then-branch and the else-branch of a conditional have to have the same type. You can't say `if test-expression then 0 else []`. Also, they expect the test-expression to evaluate specifically to a boolean value, not merely to `'false` or *anything else*. They are stricter about types here than Scheme is.
+
+In the special case where both a then-branch and an else-branch evaluate to `()`, and the else-branch involves no complex expression but merely the literal `()`, then OCaml permits you to omit the else-branch. So in OCaml you can write this:
+
+     if test-expression then then-result
+
+instead of
+
+     if test-expression then then-result else ()
+
+This is similar to Scheme's `when`-expression. Kapulet and Haskell have no analogue.
+
+
+
+### Lambda expressions
+
+In Kapulet you write &lambda;-expressions (sometimes called "anonymous functions") with a prefix of either &lambda; or the spelled-out `lambda`. That's followed by one or more patterns, separated by spaces, then a period, then a single expression which makes up the body of the function. When there are multiple patterns, the function expressed is *curried*, thus:
+
+    lambda (x, y) z. result
+
+means the same as:
+
+    lambda (x, y). (lambda z. result)
+
+The parentheses could have been omitted around `lambda z. result`; they're just there to focus your attention.
+
+Haskell and OCaml are very similar to this, they just use some slightly different notation. In Haskell you'd write:
+
+    -- Haskell
+    \(x, y) z -> result
+
+and in OCaml you'd write:
+
+    (* OCaml *)
+    fun (x, y) z -> result
+
+You may sometimes see &lambda;-expressions in OCaml written using `function` instead of `fun`. These overlap somewhat in their usage. The difference is that `function` only allocates a position for *one* argument pattern, so can't define curried functions. On the other hand, `function` can take multiple *variant* patterns for that single position. Thus with `function` you can say:
+
+    (* OCaml *)
+    function []    -> result1 |
+             x::xs -> result2
+
+whereas with `fun` you'd have to write:
+
+    (* OCaml *)
+    fun ys -> match ys with
+                []    -> result1 |
+                x::xs -> result2
+
+In Scheme, lambda expressions are written like this:
+
+    ; Scheme
+    (lambda (vars...) body-expressions...)
+
+Scheme only permits simple variables as its argument patterns here, and the lambda-expression can be defined with zero or more arguments:
+
+    ; Scheme
+    (lambda () ...)
+    (lambda (x) ...)
+    (lambda (x y) ...)
+    (lambda (x y z) ...)
+
+There is special syntax for defining functions that may take varying numbers of arguments (recall `and` and `+`), to have them bind a single variable to a list containing all of their arguments (or all of the arguments after the third...). I won't explain that syntax here.
+
+
+
+### Let, Letrec, and Define
 
+Kapulet has the syntax:
 
-<!--
+    # Kapulet
+    let
+      pat1  match expr1;
+      pat2  match expr2;
+      pat3  match expr3
+    in result
+
+which is equivalent to:
+
+    # Kapulet
+    let
+      pat1  match expr1
+    in let
+      pat2  match expr2
+    in let
+      pat3  match expr3
+    in result
+
+There is also a `letrec` form. In `let`, the bindings in `pat1` are in effect for the evaluation of all of `expr2`, `expr3`, and `result` (but not any further, if this is part of a more complex expression); similarly for the bindings in `pat2` and `pat3`. In `letrec`, all of the bindings on the left-hand side are in effect for all of the right-hand side expressions, as well as for the result.
+
+OCaml only has the second, more verbose form of this, and writes it a bit differently:
+
+    (* OCaml *)
+    let
+      pat1  = expr1
+    in let
+      pat2  = expr2
+    in let
+      pat3  = expr3
+    in result
+
+If you want to define some mutually recursive functions with `letrec`, there's a special syntax for that, using `letrec ... and ... in ...`:
+
+    (* OCaml *)
+    letrec
+      even  = fun x -> if x = 0 then true else odd x
+    and
+      odd   = fun x -> if x = 0 then false else even x
+    in ...
+
+Haskell has both of the syntactic forms that Kapulet does, though like OCaml, it uses `=` rather than `match`. And it wraps all multiple patterns with `{ ... }` (see earlier remarks about Haskell and whitespace/indentation FIXME):
+
+    -- Haskell
+    let {
+      pat1  = expr1;
+      pat2  = expr2;
+      pat3  = expr3
+    } in result
+
+Also, in Haskell `let` always means `letrec`. There is no term in Haskell that means what simple `let` does in Kapulet and OCaml.
+
+Scheme has *four or five* syntactic forms here, including `let`, `let*`, `letrec`, and `letrec*`. The difference between the last two [is subtle](http://stackoverflow.com/questions/13078165) and only arises in the presence of continuations; you can just use `letrec` for ordinary purposes. I won't try to explain the difference between `let` and `let*` here, except to say this:
+
+1.  When there's only a single pattern-binding clause, as in `(let ((var expression)) result)`, `let` and `let*` work the same.
+2.  When there are multiple pattern-binding clauses, as in `(let ((var1 expression1) (var2 expression2)) result)`, then they work somewhat differently and `let*` is probably the one that works like you're expecting.
+
+The `let*` form is the one that corresponds to `let` in Kapulet. I recommend you get in the habit of just always using `let*` (or `letrec`) in Scheme.
+
+When you're at the "toplevel" of your program, or of a library/module/compilation-unit (the terminology differs), there is also another syntactic form possible. In Kapulet, you'd write:
+
+    # Kapulet
+    let
+      pat1  match expr1;
+      ...
+    end
+    ... # rest of program or library
+
+Notice that this form ends with `end`, not with `in result`. The above is roughly equivalent to:
+
+    # Kapulet
+    let
+      pat1  match expr1;
+      ...
+    in ... # rest of program or library
+    
+That is, the bindings initiated by the clauses of the `let`-expression remain in effect until the end of the program or library. They can of course be "hidden" by subsequent bindings to new variables spelled the same way. The program:
+
+    # Kapulet
+    let
+      x  match 0
+    end
+    let
+      x  match 1
+    end
+    x
+
+evaluates to `1`, just like:
+
+    # Kapulet
+    let
+      x  match 0
+    in let
+      x  match 1
+    in x
+
+does. There's a similar form for `letrec`.
+
+OCaml can do the same:
+
+    let
+      x = 0;;
+    let
+      x = 1;;
+    x
+
+The double-semicolons are hints to OCaml's "toplevel interpreter" that a syntactic unit has finished. In some contexts they're not needed, but it does no harm to include them if you're not sure.
+
+Haskell's "toplevel interpreter" (ghci) permits a syntactic form that looks superficially quite like these:
+
+    let x = 2
+    x
+
+but under the covers something quite different is happening (you're working "inside the IO Monad", except that simple expressions like `x` that don't evaluate to monadic values are also evaluated, as a special case). If you're writing in a *file* that you want Haskell to interpret or compile, on the other hand, you have to do something a bit different (which you can't easily also do inside ghci). [[Recall|topics/week1_advanced_notes#funct-declarations]] the shortcut by which we permitted:
+
+    # Kapulet
+    let
+      f  match lambda pat1. body1;
+      g  match lambda pat2 pat3. body2;
+      ...
+
+to be written more concisely as:
+
+    # Kapulet
+    let
+      f pat1      = body1;
+      g pat2 pat3 = body2;
+      ...
+
+OCaml and Haskell permit that same shorthand. And what Haskell permits at the toplevel of *files* are just the bare binding clauses of such expressions, that is, without the surrounding `let` and `in ...`. That is, a Haskell file can look like this:
+
+    -- Haskell file.hs
+    f pat1      = body1
+
+    g pat2 pat3 = body2
+    ...
+
+Note there are no semicolons here. These are called "declarations" of the functions `f` and `g`. Note that a single function can have multiple declarations (within a single scoping context), using different patterns:
+
+    -- Haskell file.hs
+    f [] = 0
+    f (x:xs) = 1 + f xs
+
+defines `f` as a function that returns the length of a single List argument. (You can also do this *within* Haskell's `let`-constructions, too.) This is what corresponds *in Haskell files* to `let ... end` in Kapulet.
+
+Scheme has a version of `letrec ... end`, which it writes as `define`. Thus in Scheme this:
+
+    ; Scheme
+    (define var1 expr1)
+    ... ; rest of program
+
+evaluates the same as this:
+
+    ; Scheme
+    (letrec ((var1 expr1))
+            ... ; rest of program
+                )
+
+Some versions of Scheme permit you also to include `define` inside some (but not all) complex expressions. Thus you can write:
+
+    (lambda (x)
+      (define var1 expr1)
+      ...)
+
+instead of:
+
+    (lambda (x)
+      (letrec ((var1 expr1))
+      ...))
+
+There is no analogue to this in the other languages.
+
+
+
+
+
+FIXME
 
 symbol=?
 
@@ -355,7 +748,6 @@ Kapulet's `swap` (defined in homework) is Haskell's `Data.Tuple.swap`.
 
 Kapulet's `dup` isn't predefined in Haskell but can be easily expressed as `\x -> (x, x)`.
 
--->
 
 
 
@@ -363,6 +755,17 @@ Kapulet's `dup` isn't predefined in Haskell but can be easily expressed as `\x -
 
 (This page is being worked on...)
 
+
+
+### Further Installments ...
+
+We will expand these comparisons (on separate web pages) as we introduce additional ideas in the course, such as types and monads and continuations.
+
+
+
+
+
+
 FIXME
 
 
index dd143fc..99d8a8b 100644 (file)
@@ -47,7 +47,7 @@ In OCaml, there are no until-the-end-of-the-line comments. The only comments sta
 
 I agree it's annoying that these conventions are so diverse. There are plenty other commenting conventions out there, too.
 
-
+<a id=funct-declarations></a>
 ### Matching function values ###
 
 A function value doesn't have any structure---at least none that's visible to the pattern-matching system. You can only match against simple patterns like `_` or the variable `f`.