From 3a88ab1dea7db2189cbe9b72f2ec17986b8d199d Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sun, 17 Oct 2010 14:42:56 -0400 Subject: [PATCH] code cleanup Signed-off-by: Jim Pryor --- code/lambda.js | 353 +++++++++++++++++++++++++++++---------------------------- code/parse.js | 3 + code/tokens.js | 20 ++-- 3 files changed, 191 insertions(+), 185 deletions(-) diff --git a/code/lambda.js b/code/lambda.js index 0eea4c92..89bd21b5 100644 --- a/code/lambda.js +++ b/code/lambda.js @@ -453,178 +453,181 @@ try { -// 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))); -// } +/* 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/parse.js b/code/parse.js index 08ac5f04..5cdeb40e 100644 --- a/code/parse.js +++ b/code/parse.js @@ -140,6 +140,9 @@ var make_parse = function () { 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() { diff --git a/code/tokens.js b/code/tokens.js index 921040d2..c6630fa5 100644 --- a/code/tokens.js +++ b/code/tokens.js @@ -12,8 +12,8 @@ // Comments of the ; type are ignored. // Operators are by default single characters. Multicharacter -// operators can be made by supplying a string of prefix and -// suffix characters. +// operators can be made by supplying a string of multi_start and +// multi_continue characters. // characters. For example, // '<>+-&', '=>&:' // will match any of these: @@ -22,7 +22,7 @@ /*jslint onevar: false */ -String.prototype.tokens = function (prefix, suffix) { +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. @@ -51,13 +51,13 @@ String.prototype.tokens = function (prefix, suffix) { return; } -// If prefix and suffix strings are not provided, supply defaults. +// If multi_start and multi_continue strings are not provided, supply defaults. - if (typeof prefix !== 'string') { - prefix = ''; + if (typeof multi_start !== 'string') { + multi_start = ''; } - if (typeof suffix !== 'string') { - suffix = ''; + if (typeof multi_continue !== 'string') { + multi_continue = ''; } @@ -153,12 +153,12 @@ String.prototype.tokens = function (prefix, suffix) { // multi-char operator. - } else if (prefix.indexOf(c) >= 0) { + } else if (multi_start.indexOf(c) >= 0) { str = c; i += 1; while (i < length) { c = this.charAt(i); - if (suffix.indexOf(c) < 0) { + if (multi_continue.indexOf(c) < 0) { break; } str += c; -- 2.11.0