Last active
December 30, 2023 04:36
-
-
Save hugobowne/1d98f504f81fa89aa15ac3c6c6ea9cca to your computer and use it in GitHub Desktop.
Dave Beazley had us implement a mini-scheme like interpreter in Python today: this is what we came up with.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # scheme.py | |
| # | |
| # Challenge: Can you implement a mini-scheme interpreter (program that's running another program) capable of | |
| # executing the following code (now at bottom of file): | |
| def seval(sexp, env): | |
| if isinstance(sexp, (int, float)): | |
| return sexp | |
| elif isinstance(sexp, str): #Symbols | |
| return env[sexp] #Evaluate symbol names in the 'env' | |
| elif isinstance(sexp, tuple): | |
| # Special forms | |
| if sexp[0] == 'define': | |
| name = sexp[1] | |
| value = seval(sexp[2], env) | |
| env[name] = value | |
| return | |
| if sexp[0] == 'if': | |
| # (if test consequence alternative) | |
| if seval(sexp[1], env): | |
| return seval(sexp[2], env) | |
| else: | |
| return seval(sexp[3], env) | |
| if sexp[0] == 'lambda': | |
| # (lambda (parameters) body) | |
| parameters = sexp[1] # names | |
| body = sexp[2] # expression | |
| def proc(*args): | |
| localenv = dict(env) | |
| # Bind names (this is wrong wrt SICP & principle of substitution) | |
| for name, arg in zip(parameters, args): | |
| localenv[name] = arg | |
| return seval(body, localenv) | |
| return proc | |
| # (x, y, z) | |
| proc = seval(sexp[0], env) | |
| args = [ seval(a, env) | |
| for a in sexp[1:]] | |
| return proc(*args) | |
| env = { | |
| # Make some builtin functions | |
| '+' : lambda x,y: x + y, | |
| '*' : lambda x,y: x * y, | |
| '-' : lambda x,y: x - y, | |
| '<' : lambda x,y: x < y, | |
| '=' : lambda x,y: x == y, | |
| '>' : lambda x,y: x > y | |
| } | |
| # # A function definition expressed as a S-expression (in tuples) | |
| # fact = ('define', 'fact', | |
| # ('lambda', ('n',), ('if', ('=', 'n', 1), 1, ('*', 'n', ('fact', ('-', 'n', 1)))))) | |
| # | |
| # # Some test code | |
| # seval(fact, env) | |
| # seval(('define', 'n', 5), env) | |
| # result = seval(('fact', 'n'), env) | |
| # assert result == 120 |
note that the above is wrong wrt the principle of substitution, as introduced in SICP, because it doesn't explicitly substitute values into functions before evaluation. see here for an interpreter that performs the substitution also.
Then try this:
expr = ('*', 'x', 'x')
substitute(expr, 'x', 42)
from @jasonamyers:
The binding of name and values in the initial solution really wasn't in the spirit SICP which really focuses on evaluation via the substitution method.
Essentially, in the new version linked in previous comment, we're replacing symbols instead of binding values to names in the env dict (args to params).
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
to test out your new interpreter, execute
python -i scheme.pyin your terminal & try out the followingseval(42, env)seval('+', env)env['x'] = 23; seval('x', env)seval(('+',2,3), env)(try multiplication also!)seval(('if', ('>', 2, 3), 42, 37), env)seval(('lambda',('x',), ('*', 'x', 'x')), env)p = seval(('lambda',('x',), ('*', 'x', 'x')), env); p(4)expr = ('*', 'x', 'x')Another cool things you can do is define a function then evaluate it like this: