Created
January 29, 2012 15:10
-
-
Save palopezv/1699211 to your computer and use it in GitHub Desktop.
Forth implementation in python
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
| #!/usr/Util/bin/python | |
| # | |
| # @(#)py4th.py 1.1 94/12/06 | |
| # | |
| # Forth in Python (py4th). | |
| # | |
| ## This module implements a postfix interpreter class that | |
| ## can be instantiated as the inner interpreter or as a forth-ish | |
| ## interactive interpreter. The inner interpreter has two methods | |
| ## called p_compile and p_interp that are the core methods. Compile | |
| ## takes a string argument and returns a list that is executable by | |
| ## the p_interp method. | |
| ## | |
| ## As of this version (12/6/94) there are a few important features | |
| ## that need to be added, namely if-else-then and do-loop structures. | |
| ## Doing so may require that the "for" construct used in p_interp | |
| ## be replaced by a while loop that iterates over the program with | |
| ## a program counter instead of the nice, clean, pc-less way it's done | |
| ## now. I had thought about implementing these as follows: | |
| ## | |
| ## for IF-ELSE-THEN: | |
| ## | |
| ## given -- IF wordlist1 ELSE wordlist2 THEN | |
| ## wordlist1 and wordlist2 would be compiled as embedded | |
| ## lists within the current list. For example: | |
| ## | |
| ## a @ if dup * else dup dup * * then | |
| ## | |
| ## would compile into | |
| ## | |
| ## ['a', '@', 'if', ['dup', '*'], 'else', [ 'dup', 'dup', | |
| ## '*', '*']] | |
| ## | |
| ## so that p_interp could then treat the wordlists as single | |
| ## words and pass then to recursive invocations of itself. | |
| ## | |
| ## I have a similar scheme in mind for DO-LOOPs. | |
| ## | |
| ## 10 0 do i . cr loop | |
| ## | |
| ## would become | |
| ## | |
| ## ['10', '0', 'do', ['i', '.', 'cr', 'loop']] | |
| ## | |
| ## One way to do it might be to have a prepass before | |
| ## p_interp and after p_compile. Since these control structures | |
| ## are only allowed inside definitions, perhaps p_semicolon | |
| ## could be where this happens. It could then build the | |
| ## sublists and add the code required for loop increments | |
| ## and proper skipping (else over if) and handling of omitted | |
| ## parts (if without else or then). | |
| ## | |
| ## Loops use the variable name 'I' for the reference count. | |
| ## The prepass mentioned above would generate code to store | |
| ## the current value of 'I' (if any) as some internally known | |
| ## variable (e.g., '__I__2371') and restore it once the loop | |
| ## was finished. | |
| ## | |
| ## I have already put the skeleton code in for doing this. It's a | |
| ## bit of a hack at this point but you can get the gist of what I have | |
| ## in mind from in. | |
| ## | |
| ## Author: Nick Seidenman | |
| ## SAIC | |
| ## n...@osg.saic.com | |
| import string | |
| import math | |
| import sys | |
| import stack | |
| StackUnderflow = 'StackUnderflow' | |
| ExitNonError = 'ExitNonError' | |
| InnerInterpreterError = 'InnerInterpreterError' | |
| # InnerInterpreter takes a postfix expression in the form of | |
| # a python list object and 'executes it'. It has it's own | |
| # dictionary, which is initialized with the py4thon primatives and a few | |
| # Operational modes. | |
| Execution = 'Execution' | |
| Definition = 'Definition' | |
| Forgetting = 'Forgetting' | |
| Comment = 'Comment' | |
| Variable = 'Variable' | |
| class InnerInterpreter: | |
| def __init__(self): | |
| # Create a new stack and dictionary for this interpreter instance. | |
| self.__stack = stack.Stack() | |
| self.__rstack = stack.Stack() | |
| self.__vocabulary = {} | |
| self.__ulist = [] | |
| self.__vars = {} | |
| self.__vlist = [] | |
| self.__mode = Execution | |
| self.__lastmode = Execution | |
| self.__runlevel = 0 | |
| # Initialize the new dictionary with words for the primitive | |
| # functions. | |
| self.__vocabulary['.'] = self.p_dot | |
| self.__vocabulary['cr'] = self.p_cr | |
| self.__vocabulary['+'] = self.p_plus | |
| self.__vocabulary['-'] = self.p_minus | |
| self.__vocabulary['*'] = self.p_multiply | |
| self.__vocabulary['/'] = self.p_divide | |
| self.__vocabulary['uminus'] = self.p_uminus | |
| self.__vocabulary['^'] = self.p_exponent | |
| self.__vocabulary['variable'] = self.p_variable | |
| self.__vocabulary['!'] = self.p_assign | |
| self.__vocabulary['@'] = self.p_dereference | |
| self.__vocabulary['dup'] = self.p_dup | |
| self.__vocabulary['swap'] = self.p_swap | |
| self.__vocabulary['bye'] = self.p_bye | |
| self.__vocabulary['forget'] = self.p_forget | |
| self.__vocabulary[':'] = self.p_colon | |
| self.__vocabulary[';'] = self.p_semicolon | |
| self.__vocabulary['('] = self.p_lparen | |
| self.__vocabulary[')'] = self.p_rparen | |
| self.__vocabulary['vlist'] = self.p_vlist | |
| # Initialize dictionary with control structures. | |
| self.__vocabulary['if'] = self.c_if | |
| self.__vocabulary['else'] = self.c_else | |
| self.__vocabulary['then'] = self.c_then | |
| self.__vocabulary['do'] = self.c_do | |
| self.__vocabulary['loop'] = self.c_loop | |
| self.__vocabulary['+loop'] = self.c_plusloop | |
| # Initialize the control structures prepass table. | |
| self.__ctl_struct = {} | |
| self.__ctl_struct['do'] = self.c_pp_do | |
| self.__ctl_struct['loop'] = self.c_pp_loop | |
| self.__ctl_struct['+loop'] = self.c_pp_plusloop | |
| self.__ctl_struct['if'] = self.c_pp_if | |
| self.__ctl_struct['else'] = self.c_pp_else | |
| self.__ctl_struct['then'] = self.c_pp_then | |
| # Primitive functions (all begin with 'p_'. Primitive | |
| # is defined as a function that must directly manipulate | |
| # the interpreter stack. Defined functions do not do this. | |
| def p_dot(self): | |
| result = self.__stack.pop() | |
| sys.stdout.write (result + ' ') | |
| def p_cr (self): | |
| def p_plus(self): | |
| y = string.atof(self.__stack.pop()) | |
| x = string.atof(self.__stack.pop()) | |
| self.__stack.push (`y + x`) | |
| def p_minus (self): | |
| y = string.atof(self.__stack.pop()) | |
| x = string.atof(self.__stack.pop()) | |
| self.__stack.push(`y - x`) | |
| def p_multiply (self): | |
| y= string.atof(self.__stack.pop()) | |
| x = string.atof(self.__stack.pop()) | |
| self.__stack.push(`y * x`) | |
| def p_divide (self): | |
| y = string.atof(self.__stack.pop()) | |
| x = string.atof(self.__stack.pop()) | |
| self.__stack.push( `b / a`) | |
| def p_exponent (self): | |
| y = string.atof(self.__stack.pop()) | |
| x = string.atof(self.__stack.pop()) | |
| self.__stack.push( `math.pow(x, y)`) | |
| def p_uminus (self): | |
| x = string.atof(self.__stack.pop()) | |
| self.__stack.push (`- x`) | |
| def p_assign (self): | |
| word = self.__stack.pop() | |
| value = self.__stack.pop() | |
| if self.__vars.has_key (word): | |
| self.__vars[word] = value | |
| else: | |
| raise InnerInterpreterError, word | |
| def p_dereference (self): | |
| word = self.__stack.pop() | |
| try: | |
| self.__stack.push(self.__vars[word]) | |
| except KeyError, x: | |
| raise InnerInterpreterError, word | |
| def p_dup(self): | |
| val = self.__stack.pop() | |
| self.__stack.push(val) | |
| self.__stack.push(val) | |
| def p_swap(self): | |
| a = self.__stack.pop() | |
| b = self.__stack.pop() | |
| self.__stack.push(a) | |
| self.__stack.push(b) | |
| def p_def (self): | |
| word = self.__stack.pop() | |
| prog = self.__stack.pop() | |
| ## print 'defining', word, 'as', prog | |
| self.__vocabulary[word] = prog | |
| self.__ulist.append(word) | |
| def p_colon (self): | |
| if self.__mode == Execution: | |
| self.__mode = Definition | |
| self.__colon = [] | |
| else: | |
| raise InnerInterpreterError, 'nested colon' | |
| def p_semicolon (self): | |
| if self.__mode == Definition: | |
| # Perhaps put prepass in here to scan for | |
| # IF-ELSE-THEN and DO-LOOP and create sublists | |
| # from these? | |
| prog = self.__colon[1:] | |
| self.__stack.push(prog) | |
| self.__stack.push(self.__colon[0]) | |
| del self.__colon | |
| self.p_def() | |
| self.__mode = Execution | |
| else: | |
| raise InnerInterpreterError, 'nested semicolon' | |
| def p_forget (self): | |
| self.__mode = Forgetting | |
| def p_bye (self): | |
| raise ExitNonError | |
| def p_compile (self, text): | |
| return string.split(text) | |
| def p_lparen (self): | |
| if self.__mode != Comment: | |
| self.__lastmode = self.__mode | |
| self.__mode = Comment | |
| def p_rparen (self): | |
| if self.__mode == Comment: | |
| self.__mode = self.__lastmode | |
| else: | |
| raise InnerInterpreterError, ')' | |
| def do_forget (self, word): | |
| if self.__vocabulary.has_key(word) or self.__vars.has_key(word): | |
| i = self.__ulist.index(word) ## Should be in here. | |
| ul = len(self.__ulist) | |
| for j in range (i, ul): | |
| if self.__vocabulary.has_key(self.__ulist[i]): | |
| del self.__vocabulary[self.__ulist[i]] | |
| elif self.__vars.has_key(self.__ulist[i]): | |
| del self.__vars[self.__ulist[i]] | |
| else: | |
| raise InnerInterpreterError, 'system error' | |
| del self.__ulist[i] | |
| else: | |
| raise InnerInterpreterError, 'system error' | |
| self.__mode = Execution | |
| def p_variable (self): | |
| self.__lastmode = self.__mode | |
| self.__mode = Variable | |
| def do_variable (self, varName): | |
| self.__vars[varName] = self.__stack.pop() | |
| self.__ulist.append(varName) | |
| self.__mode = self.__lastmode | |
| def p_vlist (self): | |
| vlist = self.__vocabulary.keys() | |
| vlist.sort() | |
| for k in vlist: | |
| sys.stdout.write (k + ' ') | |
| ### | |
| ### Control structures (if then else, do loop, etc). | |
| ### | |
| def c_if (self): | |
| if self.__runlevel == 0: | |
| raise InnerInterpreterError, 'if' | |
| def c_else (self): | |
| if self.__runlevel == 0: | |
| raise InnerInterpreterError, 'else' | |
| def c_then (self): | |
| if self.__runlevel == 0: | |
| raise InnerInterpreterError, 'then' | |
| def c_do (self): | |
| if self.__runlevel == 0: | |
| raise InnerInterpreterError, 'do' | |
| def c_pp_do (self, scan): | |
| self.__rstack.push(scan[0:]) | |
| scan = [] | |
| scan.append ('do') | |
| return scan | |
| def c_pp_if (self, scan): | |
| self.__rstack.push(scan[0:]) | |
| scan = [] | |
| scan.append ('if') | |
| return scan | |
| def c_loop (self): | |
| if self.__runlevel == 0: | |
| raise InnerInterpreterError, 'loop' | |
| def c_pp_loop (self, scan): | |
| scan.append('loop') | |
| result = self.__rstack.pop() | |
| result.append(scan) | |
| return result | |
| def c_pp_plusloop (self, scan): | |
| scan.append('+loop') | |
| result = self.__rstack.pop() | |
| result.append(scan) | |
| return result | |
| def c_pp_else (self, scan): | |
| scan.append('else') | |
| result = self.__rstack.pop() | |
| result.append(scan) | |
| return result | |
| def c_pp_then (self, scan): | |
| scan.append('then') | |
| result = self.__rstack.pop() | |
| result.append(scan) | |
| return result | |
| def c_plusloop (self): | |
| if self.__runlevel == 0: | |
| raise InnerInterpreterError, '+loop' | |
| def c_prepass (self, prog): | |
| self.__rstack.flush() | |
| scan = [] | |
| for word in prog: | |
| if self.__ctl_struct.has_key(word): | |
| scan = self.__ctl_struct[word](scan) | |
| else: | |
| scan.append(word) | |
| return scan | |
| # This is the inner interpreter itself. It will execute the | |
| # code body passed in the form of a python list as 'prog'. | |
| def p_interp (self, prog): | |
| for word in prog: | |
| # Are we in comment mode? | |
| if self.__mode == Comment: | |
| if word == ')': | |
| self.p_rparen() | |
| continue | |
| # Are we in execution mode or definition mode? | |
| elif self.__mode == Definition: | |
| if word == ';': | |
| self.p_semicolon() | |
| else: | |
| self.__colon.append(word) | |
| continue | |
| elif self.__mode == Variable: | |
| self.do_variable (word) | |
| continue | |
| # See if this is a word we are supposed to forget. | |
| elif self.__mode == Forgetting: | |
| self.do_forget (word) | |
| continue | |
| # If it isn't in the dictionary to begin with, then it must | |
| # be a constant: push it on the stack | |
| if type(word) != type([]) and not self.__vocabulary.has_key(word): | |
| self.__stack.push(word) | |
| continue | |
| # It is in the dictionary, but it may be a defined word | |
| # rather than a primitive. Chase it down to either a | |
| # primitive, a constant, or another code body. In the | |
| # latter case, recurse with the new code body. | |
| else: | |
| current_word = word | |
| try: | |
| while self.__vocabulary.has_key (self.__vocabulary[current_word]): | |
| current_word = self.__vocabulary[current_word] | |
| except TypeError, x: | |
| pass # Ok, since this is probably because the | |
| # it's a list, or a primative. | |
| # If what we have is another program (non-primative word) | |
| # then we run interp recursively to execute the word's text. | |
| if type(current_word) == type([]): | |
| self.__runlevel = self.__runlevel + 1 | |
| self.p_interp(current_word) | |
| self.__runlevel = self.__runlevel - 1 | |
| elif type(self.__vocabulary[current_word]) == type([]): | |
| self.__runlevel = self.__runlevel + 1 | |
| self.p_interp(self.__vocabulary[current_word]) | |
| self.__runlevel = self.__runlevel - 1 | |
| elif type(self.__vocabulary[current_word]) == type (self.p_def): | |
| self.__vocabulary[current_word]() | |
| # Whatever it is at this point just gets pushed onto | |
| # the stack. It should be some sort of constant. | |
| else: | |
| self.__stack.push(self.__vocabulary[current_word]) | |
| # Simple outter interpreter for Py4th. I envision this as being | |
| # augmented with thread support to allow multiple instances of | |
| # the interpreter to provide a multitasking "forth" environment. | |
| class Py4th: | |
| def __init__(self, input=sys.stdin): | |
| self.input = input | |
| self.interpreter = InnerInterpreter () | |
| def go (self): | |
| try: | |
| while 1: | |
| try: | |
| input = self.input.readline () | |
| code = self.interpreter.p_compile (input) | |
| self.interpreter.p_interp (code) | |
| if self.input.isatty () and self.interpreter.__mode == Execution: | |
| print 'OK' | |
| except InnerInterpreterError, err_str: | |
| if err_str != 'stack underflow': | |
| print err_str, '?' | |
| else: | |
| print err_str | |
| self.interpreter.__stack.flush() | |
| except ExitNonError: | |
| if self.input.isatty (): | |
| print 'goodbye' | |
| pass | |
| # ---------------------------------------------------------- | |
| # Test driver. Add to this as functionality is augmented. | |
| # ---------------------------------------------------------- | |
| def test (): | |
| ## # Compile and run a simple program. | |
| ## | |
| ## print '***** Testing simple postfix program' | |
| ## s = '2 3 + . 3 4 ^ .' | |
| f = InnerInterpreter() | |
| ## t = f.p_compile (s) | |
| ## print s, '->', t | |
| ## f.p_interp (t) | |
| ## | |
| #### This section predated the implementation of ':-;' and is no longer | |
| #### needed. | |
| #### ------------------------------ | |
| #### # Now add program as a new word to the dictionary, then invoke it. | |
| #### | |
| #### f.__stack.push(t) | |
| #### f.__stack.push('junk') | |
| #### f.p_def() | |
| #### f.p_interp (['junk']) | |
| ## | |
| ## # Test assignment (!) word. | |
| ## | |
| ## print '***** Testing VARIABLE ! and @' | |
| ## s = '19 variable a 3 a @ * . cr' | |
| ## t = f.p_compile(s) | |
| ## print s, '->', t | |
| ## f.p_interp(t) | |
| ## | |
| ## try: | |
| ## s = 'b @ . cr' | |
| ## t = f.p_compile(s) | |
| ## f.p_interp(t) | |
| ## except InnerInterpreterError, x: | |
| ## print 'This should fail' | |
| ## | |
| ## # Test dup and swap | |
| ## | |
| ## print '***** Testing dup and swap' | |
| ## s = '20 dup . cr . cr' | |
| ## t = f.p_compile(s) | |
| ## print s, '->', t | |
| ## print 'should see 20\\n20\\n' | |
| ## f.p_interp(t) | |
| ## | |
| ## s = '5 10 swap . cr . cr' | |
| ## t = f.p_compile(s) | |
| ## print s, '->', t | |
| ## print 'should see \\n5\\n10\\n' | |
| ## f.p_interp(t) | |
| ## | |
| ## # Test : , ;, and forget | |
| ## | |
| ## print '***** Testing colon definitions and FORGET' | |
| ## s = ': sq dup * ; 2 sq 3 sq 100 sq . cr . cr . cr' | |
| ## t = f.p_compile(s) | |
| ## print s, '->', t | |
| ## print 'Should see 10000\\n9\\n4\\n' | |
| ## f.p_interp(t) | |
| ## | |
| ## print 'forgetting sq' | |
| ## f.p_interp(f.p_compile('4 variable d 5 variable e')) | |
| ## f.p_interp(f.p_compile('d @ e @ . cr . cr')) | |
| ## f.p_interp(f.p_compile('forget sq')) | |
| ## try: | |
| ## print f.__vocabulary['sq'] # It better not find this. | |
| ## except KeyError, k: | |
| ## print 'sq forgotten' # Exception is ok. | |
| ## | |
| ## try: | |
| ## print f.__vars['d'] # It better not find this. | |
| ## except KeyError, k: | |
| ## pass # Exception is ok. | |
| ## | |
| ## try: | |
| ## print f.__vars['e'] # It better not find this. | |
| ## except KeyError, k: | |
| ## print 'FORGET works' # Exception is ok. | |
| ## | |
| ## # Everything defined since sq is also forgotten - good! | |
| s = ': nestor 10 variable i 10 0 do i @ if . cr else dup 2 * loop 1 2 3 10 5 do . cr 2 +loop + + . cr ;' | |
| t = f.p_compile (s) | |
| print t | |
| u = f.c_prepass (t) | |
| print u | |
| f.p_interp(u) | |
| ## print f.__vocabulary | |
| f.p_interp(f.c_prepass(f.p_compile('nestor'))) | |
| # Run the test program when called as a script | |
| if __name__ == '__main__': | |
| test() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment