From 4c0a1c3216548fbf3ec25af58fcadf7eced3dac3 Mon Sep 17 00:00:00 2001 From: bryan newbold Date: Tue, 18 Mar 2014 16:49:30 -0400 Subject: simple -> minimal --- howto.txt | 2 +- minimal.py | 158 ++++++++++++++++++++++++++++++++++++++ minimal.scm | 250 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ simple.py | 158 -------------------------------------- simple.scm | 250 ------------------------------------------------------------ 5 files changed, 409 insertions(+), 409 deletions(-) create mode 100644 minimal.py create mode 100644 minimal.scm delete mode 100644 simple.py delete mode 100644 simple.scm diff --git a/howto.txt b/howto.txt index 1a29af2..dde4890 100644 --- a/howto.txt +++ b/howto.txt @@ -1,5 +1,5 @@ -### How to implement a simple scheme? +### How to implement a minimal scheme? Potentially need an AST-like data structure representing the parsed expression. This is the s-expression. Well represented as a pair with value types: diff --git a/minimal.py b/minimal.py new file mode 100644 index 0000000..a34941c --- /dev/null +++ b/minimal.py @@ -0,0 +1,158 @@ +""" + null -> None + pair -> + boolean (true/false) -> True/False + number -> number + identifier/symbol -> string + + + const (atomic values) + lambda + quote (s-expr "one level down") + identifier (a symbol to be looked up in the context) + cond (conditional expression) +""" + +def is_atom(x): + return x is () or type(x) not in (None, tuple, list, dict) + +def is_boolean(x): + return x in (True, False) + +def is_number(x): + return type(x) in (int, float, long) + +def is_zero(x): + return x == 0 + +def is_null(x): + return x is () + +def is_eq(a, b): + return a == b + +def is_builtin(x): + return x in ('lambda', 'quote', 'cond', 'else', 'cons', 'car', 'cdr', + 'null?', 'eq?', 'atom?', 'zero?', 'number?', + '+', '-', '*', '/') + +# because python does not allow circular function definitions, and action +# functions call out to meaning(), which depends on some actions, we'll use an +# "action lookup table" to handle function references ourself. +# A more "pythonic" way to do this might be to use an object. +actions = dict() + +def meaning(x, ctx): + action = None + if is_atom(x): + if is_number(x) or is_boolean(x) or is_builtin(x): + action = actions['identity'] + else: # an identifier + action = actions['lookup'] + elif type(x) is tuple: + if x[0] is 'quote': + action = actions['quote'] + elif x[0] is 'cond': + action = actions['cond'] + elif x[0] is 'lambda': + action = actions['lambda'] + elif type(x[0]) is tuple: + action = actions['apply'] + else: # some other identifier, either builtin or not + action = actions['apply'] + else: + raise ValueError("Unexpected expression: %s" % x) + return action(x, ctx) + +def meaning_list(l, ctx): + return tuple([meaning(x, ctx) for x in l]) + +def identity_action(x, ctx): + return x +actions['identity'] = identity_action + +def lookup_action(x, ctx): + if not x in ctx: + ValueError("Unknown identifier: %s" % x) + else: + return ctx[x] +actions['lookup'] = lookup_action + +def quote_action(x, ctx): + if len(x) != 2: + ValueError("Improper quote usage: %s" % x) + return x[1] +actions['quote'] = quote_action + +def cond_action(x, ctx): + for line in x[1:]: + if line[0] == 'else': + return meaning(line[1], ctx) + elif meaning(line[0], ctx): + return meanint(line[1], ctx) + else: + # "unspecified" + return None +actions['cond'] = cond_action + +def lambda_action(x, ctx): + return ('procedure', x[1], x[2:], ctx.copy()) +actions['lambda'] = lambda_action + +def apply_action(x, ctx): + if is_builtin(x[0]): + args = meaning_list(x[1:], ctx) + if x[0] is 'cons': + return (args[0], ) + args[1] + elif x[0] is 'car': + return args[0][0] + elif x[0] is 'cdr': + return args[0][1] + elif x[0] is 'null?': + return is_null(args[0]) + elif x[0] is 'eq?': + return is_eq(args[0], args[1]) + elif x[0] is 'atom?': + return is_atom(args[0]) + elif x[0] is 'zero?': + return is_zero(args[0]) + elif x[0] is 'number?': + return is_number(args[0]) + elif x[0] is '+': + return args[0] + args[1] + elif x[0] is '-': + return args[0] - args[1] + elif x[0] is '*': + return args[0] * args[1] + elif x[0] is '/': + return args[0] / args[1] + else: + raise Exception("Unexpected builtin: %s" % x[0]) + elif type(x[0]) is tuple: + proc = meaning(x[0], ctx) + if proc[0] is not 'procedure': + raise Exception("Not applicable: %s" % str(proc)) + variables = proc[1] + body = proc[2] + closure = proc[3].copy() + args = meaning_list(x[1:], ctx) + for i in range(len(variables)): + closure[variables[i]] = args[i] + for expr in body: + ret = meaning(expr, closure) + return ret + else: + raise Exception("Unexpected... thing...: %s" % str(x[0])) +actions['apply'] = apply_action + +def value(x): + return meaning(x, dict()) + +def test(): + # ((lambda (x) (+ 1 x)) 5) ; 6 + v = value( (('lambda', ('x',), ('+', 1, 'x')), 5) ) + print(v) + assert(v is 6) + +if __name__=='__main__': + test() diff --git a/minimal.scm b/minimal.scm new file mode 100644 index 0000000..6e4c3c4 --- /dev/null +++ b/minimal.scm @@ -0,0 +1,250 @@ + +; cyclic dependency graph (sigh) +; +; meaning +; expression-to-action +; list-to-action +; *application +; meaning +; +; actions + +; ### preliminaries, utilities, shorthand + +; check if something is an atom vs {null, collection} +(define atom? + (lambda (x) + (and (not (pair? x)) (not (null? x))))) + +; need a list or tuple type; tuples prefered +(define first + (lambda (p) (car p))) + +(define second + (lambda (p) (car (cdr p)))) + +(define third + (lambda (p) (car (cdr (cdr p))))) + +(define build + (lambda (a b) (cons a (cons b (quote ()))))) + +(define text-of second) + +; test functions +(define add1 (lambda (x) (+ x 1))) +(define sub1 (lambda (x) (- x 1))) + +; table operations +(define new-entry build) + +(define lookup-in-entry + (lambda (name entry entry-f) + (lookup-in-entry-help name + (first entry) + (second entry) + entry-f))) + +(define lookup-in-entry-help + (lambda (name names values entry-f) + (cond + ((null? names) (entry-f name)) + ((eq? (car names) name) (car values)) + (else (lookup-in-entry-help name (cdr names) (cdr values) entry-f))))) + +(define extend-table cons) + +(define lookup-in-table + (lambda (name table table-f) + (cond + ((null? table) (table-f name)) + (else (lookup-in-entry name + (car table) + (lambda (n) + (lookup-in-table n (cdr table) table-f))))))) + +(define initial-table + (lambda (name) + (car (quote ())))) + +;(lookup-in-entry 'fish +; '((teach a man to fish) +; (1 2 3 4 5)) +; (lambda (x) x)) + +;(lookup-in-table 'fish +; (extend-table '((teach a man to fish) +; (1 2 3 4 5)) +; (quote ())) +; (lambda (x) x)) + +; ### specific types/helpers +(define builtin? + (lambda (l) + (eq? (first l) (quote builtin)))) + +(define non-builtin? + (lambda (l) + (eq? (first l) (quote non-builtin)))) + +(define else? + (lambda (x) + (cond + ((atom? x) (eq? x (quote else))) + (else #f)))) + +(define table-of first) +(define formals-of second) +(define body-of third) +(define question-of first) +(define answer-of second) +(define cond-lines-of cdr) +(define function-of car) +(define arguments-of cdr) + +; need generic true/false booleans, a number type, and a symbol type +; also need a mutable "table" collection +(define *const + (lambda (e table) + (cond + ((number? e) e) + ((eq? e #t) #t) + ((eq? e #f) #f) + (else (build (quote builtin) e))))) +;(*const 'asdf '()) ; (builtin asdf) + +(define *lambda + (lambda (e table) + (build (quote non-builtin) (cons table (cdr e))))) +;(*lambda '(lambda (a b) (cond ((eq? a b) b) (else a))) '( ((1 2 3) (a b c)))) +; (non-builtin ((((1 2 3) (a b c))) (a b) (cond ((eq? a b) b) (else a)))) + +(define *quote + (lambda (e table) + (text-of e))) +;(*quote '(quote stuff) '()) ; stuff + +(define *identifier + (lambda (e table) + (lookup-in-table e table initial-table))) +;(*identifier 'asdf '()) ; error +;(*identifier 'a '( ((1 2 3 a b c) (first second third 1 2 3)))) ; 1 + +(define *cond + (lambda (e table) + (evcon (cond-lines-of e) table))) + +(define :atom? + (lambda (x) + (cond + ((atom? x) #t) + ((null? x) #f) + ((eq? (car x) (quote builtin)) #t) + ((eq? (car x) (quote non-builtin)) #t) + (else #f)))) + +; ### now we start the meat! + +(define atom-to-action + (lambda (e) + (cond + ((number? e) *const) + ((eq? e #t) *const) + ((eq? e #f) *const) + ((eq? e (quote cons)) *const) + ((eq? e (quote car)) *const) + ((eq? e (quote cdr)) *const) + ((eq? e (quote null?)) *const) + ((eq? e (quote eq?)) *const) + ((eq? e (quote atom?)) *const) + ((eq? e (quote zero?)) *const) + ((eq? e (quote add1)) *const) + ((eq? e (quote sub1)) *const) + ((eq? e (quote number?)) *const) + (else *identifier)))) +;(atom-to-action 'number?); *const + +(define list-to-action + (lambda (e) + (cond + ((atom? (car e)) (cond + ((eq? (car e) (quote quote)) *quote) + ((eq? (car e) (quote lambda)) *lambda) + ((eq? (car e) (quote cond)) *cond) + (else *application))) + (else *application)))) +;(list-to-action '(lambda (x) x)) ; *lambda +;(list-to-action '(cond ((eq? 1 2) #f) (else #t))) ; *cond + +(define expression-to-action + (lambda (e) + (cond + ((atom? e) (atom-to-action e)) + (else (list-to-action e))))) +;(expression-to-action '#f) ; *const +;(expression-to-action '(lambda (x) x)) ; *lambda + +(define evcon + (lambda (lines table) + (cond + ((else? (question-of (car lines))) + (meaning (answer-of (car lines)) table)) + ((meaning (question-of (car lines)) table) + (meaning (answer-of (car lines)) table)) + (else (evcon (cdr lines) table))))) + +(define evlis + (lambda (args table) + (cond + ((null? args) (quote ())) + (else (cons (meaning (car args) table) + (evlis (cdr args) table)))))) +;(evlis '(cons #f 4) '()) ; ((builtin cons) #f 4) + +(define *application + (lambda (e table) + (apply2 + (meaning (function-of e) table) + (evlis (arguments-of e) table)))) + +; basic, low-level, non-compound functions +(define apply-builtin + (lambda (name vals) + (cond + ((eq? name (quote cons)) (cons (first vals) (second vals))) + ((eq? name (quote car)) (car (first vals))) + ((eq? name (quote cdr)) (cdr (first vals))) + ((eq? name (quote null?)) (null? (first vals))) + ((eq? name (quote eq?)) (eq? (first vals) (second vals))) + ((eq? name (quote atom?)) (:atom? (first vals))) + ((eq? name (quote zero?)) (zero? (first vals))) + ((eq? name (quote add1)) (add1 (first vals))) + ((eq? name (quote sub1)) (sub1 (first vals))) + ((eq? name (quote number?)) (number? (first vals)))))) + +; for compound functions +(define apply-closure + (lambda (closure vals) + (meaning (body-of closure) + (extend-table (new-entry (formals-of closure) vals) + (table-of closure))))) + +; this is "how apply would be implemented"; it isn't used in this file +(define apply2 + (lambda (fun vals) + (cond + ((builtin? fun) (apply-builtin (second fun) vals)) + ((non-builtin? fun) (apply-closure (second fun) vals))))) + +; find the value of an s-expression in the context of an environment +(define meaning + (lambda (e table) + ((expression-to-action e) e table))) +;(meaning '(lambda (x) (cons x y)) '(((y z) ((8) 9)))) +; (non-primative ((((y z) ((8) 9)))) (x) (cons x y)) + +; and finally, helper to find values in a starting environment +(define value + (lambda (e) + (meaning e (quote ())))) +;(value '((lambda (a b) (a (add1 b))) (lambda (c) (add1 c)) 4)) ; 6 diff --git a/simple.py b/simple.py deleted file mode 100644 index a34941c..0000000 --- a/simple.py +++ /dev/null @@ -1,158 +0,0 @@ -""" - null -> None - pair -> - boolean (true/false) -> True/False - number -> number - identifier/symbol -> string - - - const (atomic values) - lambda - quote (s-expr "one level down") - identifier (a symbol to be looked up in the context) - cond (conditional expression) -""" - -def is_atom(x): - return x is () or type(x) not in (None, tuple, list, dict) - -def is_boolean(x): - return x in (True, False) - -def is_number(x): - return type(x) in (int, float, long) - -def is_zero(x): - return x == 0 - -def is_null(x): - return x is () - -def is_eq(a, b): - return a == b - -def is_builtin(x): - return x in ('lambda', 'quote', 'cond', 'else', 'cons', 'car', 'cdr', - 'null?', 'eq?', 'atom?', 'zero?', 'number?', - '+', '-', '*', '/') - -# because python does not allow circular function definitions, and action -# functions call out to meaning(), which depends on some actions, we'll use an -# "action lookup table" to handle function references ourself. -# A more "pythonic" way to do this might be to use an object. -actions = dict() - -def meaning(x, ctx): - action = None - if is_atom(x): - if is_number(x) or is_boolean(x) or is_builtin(x): - action = actions['identity'] - else: # an identifier - action = actions['lookup'] - elif type(x) is tuple: - if x[0] is 'quote': - action = actions['quote'] - elif x[0] is 'cond': - action = actions['cond'] - elif x[0] is 'lambda': - action = actions['lambda'] - elif type(x[0]) is tuple: - action = actions['apply'] - else: # some other identifier, either builtin or not - action = actions['apply'] - else: - raise ValueError("Unexpected expression: %s" % x) - return action(x, ctx) - -def meaning_list(l, ctx): - return tuple([meaning(x, ctx) for x in l]) - -def identity_action(x, ctx): - return x -actions['identity'] = identity_action - -def lookup_action(x, ctx): - if not x in ctx: - ValueError("Unknown identifier: %s" % x) - else: - return ctx[x] -actions['lookup'] = lookup_action - -def quote_action(x, ctx): - if len(x) != 2: - ValueError("Improper quote usage: %s" % x) - return x[1] -actions['quote'] = quote_action - -def cond_action(x, ctx): - for line in x[1:]: - if line[0] == 'else': - return meaning(line[1], ctx) - elif meaning(line[0], ctx): - return meanint(line[1], ctx) - else: - # "unspecified" - return None -actions['cond'] = cond_action - -def lambda_action(x, ctx): - return ('procedure', x[1], x[2:], ctx.copy()) -actions['lambda'] = lambda_action - -def apply_action(x, ctx): - if is_builtin(x[0]): - args = meaning_list(x[1:], ctx) - if x[0] is 'cons': - return (args[0], ) + args[1] - elif x[0] is 'car': - return args[0][0] - elif x[0] is 'cdr': - return args[0][1] - elif x[0] is 'null?': - return is_null(args[0]) - elif x[0] is 'eq?': - return is_eq(args[0], args[1]) - elif x[0] is 'atom?': - return is_atom(args[0]) - elif x[0] is 'zero?': - return is_zero(args[0]) - elif x[0] is 'number?': - return is_number(args[0]) - elif x[0] is '+': - return args[0] + args[1] - elif x[0] is '-': - return args[0] - args[1] - elif x[0] is '*': - return args[0] * args[1] - elif x[0] is '/': - return args[0] / args[1] - else: - raise Exception("Unexpected builtin: %s" % x[0]) - elif type(x[0]) is tuple: - proc = meaning(x[0], ctx) - if proc[0] is not 'procedure': - raise Exception("Not applicable: %s" % str(proc)) - variables = proc[1] - body = proc[2] - closure = proc[3].copy() - args = meaning_list(x[1:], ctx) - for i in range(len(variables)): - closure[variables[i]] = args[i] - for expr in body: - ret = meaning(expr, closure) - return ret - else: - raise Exception("Unexpected... thing...: %s" % str(x[0])) -actions['apply'] = apply_action - -def value(x): - return meaning(x, dict()) - -def test(): - # ((lambda (x) (+ 1 x)) 5) ; 6 - v = value( (('lambda', ('x',), ('+', 1, 'x')), 5) ) - print(v) - assert(v is 6) - -if __name__=='__main__': - test() diff --git a/simple.scm b/simple.scm deleted file mode 100644 index 6e4c3c4..0000000 --- a/simple.scm +++ /dev/null @@ -1,250 +0,0 @@ - -; cyclic dependency graph (sigh) -; -; meaning -; expression-to-action -; list-to-action -; *application -; meaning -; -; actions - -; ### preliminaries, utilities, shorthand - -; check if something is an atom vs {null, collection} -(define atom? - (lambda (x) - (and (not (pair? x)) (not (null? x))))) - -; need a list or tuple type; tuples prefered -(define first - (lambda (p) (car p))) - -(define second - (lambda (p) (car (cdr p)))) - -(define third - (lambda (p) (car (cdr (cdr p))))) - -(define build - (lambda (a b) (cons a (cons b (quote ()))))) - -(define text-of second) - -; test functions -(define add1 (lambda (x) (+ x 1))) -(define sub1 (lambda (x) (- x 1))) - -; table operations -(define new-entry build) - -(define lookup-in-entry - (lambda (name entry entry-f) - (lookup-in-entry-help name - (first entry) - (second entry) - entry-f))) - -(define lookup-in-entry-help - (lambda (name names values entry-f) - (cond - ((null? names) (entry-f name)) - ((eq? (car names) name) (car values)) - (else (lookup-in-entry-help name (cdr names) (cdr values) entry-f))))) - -(define extend-table cons) - -(define lookup-in-table - (lambda (name table table-f) - (cond - ((null? table) (table-f name)) - (else (lookup-in-entry name - (car table) - (lambda (n) - (lookup-in-table n (cdr table) table-f))))))) - -(define initial-table - (lambda (name) - (car (quote ())))) - -;(lookup-in-entry 'fish -; '((teach a man to fish) -; (1 2 3 4 5)) -; (lambda (x) x)) - -;(lookup-in-table 'fish -; (extend-table '((teach a man to fish) -; (1 2 3 4 5)) -; (quote ())) -; (lambda (x) x)) - -; ### specific types/helpers -(define builtin? - (lambda (l) - (eq? (first l) (quote builtin)))) - -(define non-builtin? - (lambda (l) - (eq? (first l) (quote non-builtin)))) - -(define else? - (lambda (x) - (cond - ((atom? x) (eq? x (quote else))) - (else #f)))) - -(define table-of first) -(define formals-of second) -(define body-of third) -(define question-of first) -(define answer-of second) -(define cond-lines-of cdr) -(define function-of car) -(define arguments-of cdr) - -; need generic true/false booleans, a number type, and a symbol type -; also need a mutable "table" collection -(define *const - (lambda (e table) - (cond - ((number? e) e) - ((eq? e #t) #t) - ((eq? e #f) #f) - (else (build (quote builtin) e))))) -;(*const 'asdf '()) ; (builtin asdf) - -(define *lambda - (lambda (e table) - (build (quote non-builtin) (cons table (cdr e))))) -;(*lambda '(lambda (a b) (cond ((eq? a b) b) (else a))) '( ((1 2 3) (a b c)))) -; (non-builtin ((((1 2 3) (a b c))) (a b) (cond ((eq? a b) b) (else a)))) - -(define *quote - (lambda (e table) - (text-of e))) -;(*quote '(quote stuff) '()) ; stuff - -(define *identifier - (lambda (e table) - (lookup-in-table e table initial-table))) -;(*identifier 'asdf '()) ; error -;(*identifier 'a '( ((1 2 3 a b c) (first second third 1 2 3)))) ; 1 - -(define *cond - (lambda (e table) - (evcon (cond-lines-of e) table))) - -(define :atom? - (lambda (x) - (cond - ((atom? x) #t) - ((null? x) #f) - ((eq? (car x) (quote builtin)) #t) - ((eq? (car x) (quote non-builtin)) #t) - (else #f)))) - -; ### now we start the meat! - -(define atom-to-action - (lambda (e) - (cond - ((number? e) *const) - ((eq? e #t) *const) - ((eq? e #f) *const) - ((eq? e (quote cons)) *const) - ((eq? e (quote car)) *const) - ((eq? e (quote cdr)) *const) - ((eq? e (quote null?)) *const) - ((eq? e (quote eq?)) *const) - ((eq? e (quote atom?)) *const) - ((eq? e (quote zero?)) *const) - ((eq? e (quote add1)) *const) - ((eq? e (quote sub1)) *const) - ((eq? e (quote number?)) *const) - (else *identifier)))) -;(atom-to-action 'number?); *const - -(define list-to-action - (lambda (e) - (cond - ((atom? (car e)) (cond - ((eq? (car e) (quote quote)) *quote) - ((eq? (car e) (quote lambda)) *lambda) - ((eq? (car e) (quote cond)) *cond) - (else *application))) - (else *application)))) -;(list-to-action '(lambda (x) x)) ; *lambda -;(list-to-action '(cond ((eq? 1 2) #f) (else #t))) ; *cond - -(define expression-to-action - (lambda (e) - (cond - ((atom? e) (atom-to-action e)) - (else (list-to-action e))))) -;(expression-to-action '#f) ; *const -;(expression-to-action '(lambda (x) x)) ; *lambda - -(define evcon - (lambda (lines table) - (cond - ((else? (question-of (car lines))) - (meaning (answer-of (car lines)) table)) - ((meaning (question-of (car lines)) table) - (meaning (answer-of (car lines)) table)) - (else (evcon (cdr lines) table))))) - -(define evlis - (lambda (args table) - (cond - ((null? args) (quote ())) - (else (cons (meaning (car args) table) - (evlis (cdr args) table)))))) -;(evlis '(cons #f 4) '()) ; ((builtin cons) #f 4) - -(define *application - (lambda (e table) - (apply2 - (meaning (function-of e) table) - (evlis (arguments-of e) table)))) - -; basic, low-level, non-compound functions -(define apply-builtin - (lambda (name vals) - (cond - ((eq? name (quote cons)) (cons (first vals) (second vals))) - ((eq? name (quote car)) (car (first vals))) - ((eq? name (quote cdr)) (cdr (first vals))) - ((eq? name (quote null?)) (null? (first vals))) - ((eq? name (quote eq?)) (eq? (first vals) (second vals))) - ((eq? name (quote atom?)) (:atom? (first vals))) - ((eq? name (quote zero?)) (zero? (first vals))) - ((eq? name (quote add1)) (add1 (first vals))) - ((eq? name (quote sub1)) (sub1 (first vals))) - ((eq? name (quote number?)) (number? (first vals)))))) - -; for compound functions -(define apply-closure - (lambda (closure vals) - (meaning (body-of closure) - (extend-table (new-entry (formals-of closure) vals) - (table-of closure))))) - -; this is "how apply would be implemented"; it isn't used in this file -(define apply2 - (lambda (fun vals) - (cond - ((builtin? fun) (apply-builtin (second fun) vals)) - ((non-builtin? fun) (apply-closure (second fun) vals))))) - -; find the value of an s-expression in the context of an environment -(define meaning - (lambda (e table) - ((expression-to-action e) e table))) -;(meaning '(lambda (x) (cons x y)) '(((y z) ((8) 9)))) -; (non-primative ((((y z) ((8) 9)))) (x) (cons x y)) - -; and finally, helper to find values in a starting environment -(define value - (lambda (e) - (meaning e (quote ())))) -;(value '((lambda (a b) (a (add1 b))) (lambda (c) (add1 c)) 4)) ; 6 -- cgit v1.2.3