FORTH in Python (py4th.py)

recaialkan at gmail.com recaialkan at gmail.com
Thu Jul 19 00:05:24 CEST 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