Here i like to explain about small "interpreter of lisp using python" . first lets go to language interpreter . its a process to convert a language into execution state
using syntax and semantics rules simply say compiler .
a compiler have many parts but we focus on parsing and execution
Parsing means convert a program into sequence of characters based on syntax rules and execution means internal representation then processed based on semantic rules .
Representation of an interpreter
This is done in python and JavaScript to see the code : click here
Before explaining this we have to look at the working of the program for this
using syntax and semantics rules simply say compiler .
a compiler have many parts but we focus on parsing and execution
Parsing means convert a program into sequence of characters based on syntax rules and execution means internal representation then processed based on semantic rules .
Representation of an interpreter
This is done in python and JavaScript to see the code : click here
Before explaining this we have to look at the working of the program for this
1: >> program = "(begin (define r 3) (* 3.141592653 (* r r)))"
2: >>> parse(program)
3: ['begin', ['define', 'r', 3], ['*', 3.141592653, ['*', 'r', 'r']]]
4: >>> eval(parse(program))
5: 28.274333877
just look parse section convert the lisp program into list of number and strings in python and evaluation gives the final output
execution :
Mainly have two parts evaluation and Environment .
Evaluation means there are nine cases in lisp that is evaluated using function eval taking two argument that expression x,environment env.
1: def eval(x, env=global_env):
2: "Evaluate an expression in an environment."
3: if isa(x, Symbol): # variable reference
4: return env.find(x)[x]
5: elif not isa(x, list): # constant literal
6: return x
7: elif x[0] == 'quote': # (quote exp)
8: (_, exp) = x
9: return exp
10: elif x[0] == 'if': # (if test conseq alt)
11: (_, test, conseq, alt) = x
12: return eval((conseq if eval(test, env) else alt), env)
13: elif x[0] == 'set!': # (set! var exp)
14: (_, var, exp) = x
15: env.find(var)[var] = eval(exp, env)
16: elif x[0] == 'define': # (define var exp)
17: (_, var, exp) = x
18: env[var] = eval(exp, env)
19: elif x[0] == 'lambda': # (lambda (var*) exp)
20: (_, vars, exp) = x
21: return lambda *args: eval(exp, Env(vars, args, env))
22: elif x[0] == 'begin': # (begin exp*)
23: for exp in x[1:]:
24: val = eval(exp, env)
25: return val
26: else: # (proc exp*)
27: exps = [eval(exp, env) for exp in x]
28: proc = exps.pop(0)
29: return proc(*exps)
30: isa = isinstance
31: Symbol = str
Environment
Environments are mappings of variable names (symbols) to the values (data objects) held by them
for a function definition there two section first definition second procedure call
when define a function we have the output
1: >> program = "(define area (lambda (r) (* 3.141592653 (* r r)))"
2: >>> parse(program)
3: ['define', 'area', ['lambda', ['r'], ['*', 3.141592653, ['*', 'r', 'r']]]]
4: >>> eval(parse(program))
5: None
In this evaluation we take the branch if x[0] == 'define', under which Python sets var to 'area' and exp to ['lambda', ['r'], ['*', 3.141592653, ['*', 'r', 'r']]]. Python then modifies the env (which at this point is the global environment), adding a new variable, 'area', and setting it to the result of evaluating exp. To evaluate exp, we follow the elif x[0] == 'lambda' in eval, branch, assigning the three variables (_, vars, exp) to the corresponding elements of the list x (and signalling an error if x is not of length 3). We then create a new procedure that, when called, will evaluate the expression ['*', 3.141592653 ['*', 'r', 'r']], in the environment formed by binding the formal parameters of the procedure (in this case there is just one parameter, r) to the arguments supplied in the procedure call, and in addition using the current environment for any variables not in the parameter list (for example, the variable *). The value of this newly-minted procedure is then assigned as the value of area in global_env.
Now what happens when we evaluate (area 3)? Since area is not one of the special form symbols, this must be a procedure call (the last else: of eval), and the whole list of expressions is evaluated, one at a time. Evaluating area yields the procedure we just created; evaluating 3 yields 3. We then (according to the last line of eval) call the newly-created procedure with the argument list [3]. this means evaluating exp, which is ['*', 3.141592653 ['*', 'r', 'r']], in the environment where r is 3 and the outer environment is the global environment, and therefore * is the multiplication procedure.
We have an Env class which gives appropriate value for variables
1: class Env(dict):
2: "An environment: a dict of {'var':val} pairs, with an outer Env."
3: def __init__(self, parms=(), args=(), outer=None):
4: self.update(zip(parms,args))
5: self.outer = outer
6: def find(self, var):
7: "Find the innermost Env where var appears."
8: return self if var in self else self.outer.find(var)
This process of looking first in inner environments and then in outer ones is called lexical scoping. Env.find finds the right environment according to lexical scoping rules.
some build in procedure is added to env
1: def add_globals(env):
2: "Add some Scheme standard procedures to an environment."
3: import math, operator as op
4: env.update(vars(math)) # sin, sqrt, ...
5: env.update(
6: {'+':op.add, '-':op.sub, '*':op.mul, '/':op.div, 'not':op.not_,
7: '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq,
8: 'equal?':op.eq, 'eq?':op.is_, 'length':len, 'cons':lambda x,y:[x]+y,
9: 'car':lambda x:x[0],'cdr':lambda x:x[1:], 'append':op.add,
10: 'list':lambda *x:list(x), 'list?': lambda x:isa(x,list),
11: 'null?':lambda x:x==[], 'symbol?':lambda x: isa(x, Symbol)})
12: return env
13: global_env = add_globals(Env())
Parsing:parse and read
parsing is two section : tokenized to separate into tokens
join token based on syntax rules and build internal structure
1: >>> program = "(set! twox (* x 2))"
2: >>> tokenize(program)
3: ['(', 'set!', 'twox', '(', '*', 'x', '2', ')', ')']
4: >>> parse(program)
5: ['set!', 'twox', ['*', 'x', 2]]
now just look at parsing function
1: def read(s):
2: "Read a Scheme expression from a string."
3: return read_from(tokenize(s))
4: parse = read
5: def tokenize(s):
6: "Convert a string into a list of tokens."
7: return s.replace('(',' ( ').replace(')',' ) ').split()
8: def read_from(tokens):
9: "Read an expression from a sequence of tokens."
10: if len(tokens) == 0:
11: raise SyntaxError('unexpected EOF while reading')
12: token = tokens.pop(0)
13: if '(' == token:
14: L = []
15: while tokens[0] != ')':
16: L.append(read_from(tokens))
17: tokens.pop(0) # pop off ')'
18: return L
19: elif ')' == token:
20: raise SyntaxError('unexpected )')
21: else:
22: return atom(token)
23: def atom(token):
24: "Numbers become numbers; every other token is a symbol."
25: try: return int(token)
26: except ValueError:
27: try: return float(token)
28: except ValueError:
29: return Symbol(token)
Finally we'll add a function, to_string, to convert an expression back into a Lisp-readable string, and a function repl, which stands for read-eval-print-loop, to form an interactive Lisp interpreter:
1: def to_string(exp):
2: "Convert a Python object back into a Lisp-readable string."
3: return '('+' '.join(map(to_string, exp))+')' if isa(exp, list) else str(exp)
4: def repl(prompt='lis.py> '):
5: "A prompt-read-eval-print loop."
6: while True:
7: val = eval(parse(raw_input(prompt)))
8: if val is not None: print to_string(val)
Now we can check final output:
1: >>> repl()
2: lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))
3: lis.py> (area 3)
4: 28.274333877
5: lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
6: lis.py> (fact 10)
7: 3628800
8: lis.py> (fact 100)
9: 9332621544394415268169923885626670049071596826438162146859296389521759999322991
10: 5608941463976156518286253697920827223758251185210916864000000000000000000000000
11: lis.py> (area (fact 10))
12: 4.1369087198e+13
13: lis.py> (define first car)
14: lis.py> (define rest cdr)
15: lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))
16: lis.py> (count 0 (list 0 1 2 3 0 0))
17: 3
18: lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))
19: 4
No comments:
Post a Comment