FORTH in Python (py4th.py)
recaialkan at gmail.com
recaialkan at gmail.com
Wed Jul 18 18:05:24 EDT 2012
7 Aralık 1994 Çarşamba 05:04:22 UTC+2 tarihinde Nick Seidenman yazdı:
> Just for fun I sat down and started writing a forth interpreter in
> python. I got as far as putting in control structs and decided I';d
> better get back to my real job. It does make a nice little example of
> many of the cooler features of the language. I hearby bequeath its
> current incodation to the net.
>
> No arguments, now! ;)
>
> ---------------<cut here>-------------
> #!/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
> ## nick at 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):
> print
>
> 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()
Thank you for the code. How can i import stack? Where is the code for it?
More information about the Python-list
mailing list