이 글은 python for fun의 forth 편을 번역한 것이다,
What is Forth? (포스란 무엇이냐)
Using the Data Stack
$ python forth.py Forth> 5 6 + 7 8 + * . 165
Forth> 5 dump 6 dump + dump 7 dump 8 dump + dump * dump ds = [5] ds = [5, 6] ds = [11] ds = [11, 7] ds = [11, 7, 8] ds = [11, 15] ds = [165] Forth>
Built in primitive words for data stack manipulation
데이타 스택 조작을 위한 기초단어 만들기
- DUP 은 스택의 탑을 복제한다 (TOS)
- SWAP 은 맨위의 두개를 바꿔치기한다
- DROP 은 TOS 를 뽑아서 버린다t
- "." TOS에서 데이타를 팝하고 인쇄
- "=" 은 두 데이타를 팝해서 비교한 후 같으면 스택의 꼭대기에 1을 올려놓고 아니면 0을 올려놓는다.
Forth> # Lets square and print the TOS Forth> 25 dup * . 625 Forth> # Lets negate the TOS and print it Forth> 42 0 swap - . -42 Forth>
def rAdd (cod,p) : b=ds.pop(); a=ds.pop(); ds.append(a+b) def rMul (cod,p) : b=ds.pop(); a=ds.pop(); ds.append(a*b) def rSub (cod,p) : b=ds.pop(); a=ds.pop(); ds.append(a-b) def rDiv (cod,p) : b=ds.pop(); a=ds.pop(); ds.append(a/b) def rEq (cod,p) : b=ds.pop(); a=ds.pop(); ds.append(int(a==b)) def rGt (cod,p) : b=ds.pop(); a=ds.pop(); ds.append(int(a>b)) def rLt (cod,p) : b=ds.pop(); a=ds.pop(); ds.append(int(a<b)) def rSwap(cod,p) : a=ds.pop(); b=ds.pop(); ds.append(a); ds.append(b) def rDup (cod,p) : ds.append(ds[-1]) def rDrop(cod,p) : ds.pop() def rOver(cod,p) : ds.append(ds[-2]) def rDump(cod,p) : print "ds = ", ds
def rDot (cod,p) : print ds.pop()
Defining new words
새로운 워드를 정의
Forth> : negate 0 swap - ; Forth> 5 negate . -5 Forth> : sqr dup * ; Forth> 6 sqr . 36 Forth>
Compiling Words to Pcode
워드를 PCODE로 컴파일
>>> import forth
>>> forth.tokenizeWords("5 6 + . # this is a comment")
>>> forth.words
['5', '6', '+', '.']
>>>
>>> forth.compile() Forth> 5 6 + . [<function rPush at 0x9bdf5a4>, 5] >>> forth.compile() [<function rPush at 0x9bdf5a4>, 6] >>> forth.compile() [<function rAdd at 0x9bdf1ec>] >>> forth.compile() [<function rDot at 0x9bdf48c>] >>> forth.words [] >>>
def compile() : pcode = []; prompt = "Forth> " while 1 : word = getWord(prompt) # get next word cAct = cDict.get(word) # Is there a compile time action ? rAct = rDict.get(word) # Is there a runtime action ? if cAct : cAct(pcode) # run at compile time elif rAct : if type(rAct) == type([]) : pcode.append(rRun) # Compiled word. pcode.append(word) # for now do dynamic lookup else : pcode.append(rAct) # push builtin for runtime else : # Number to be pushed onto ds at runtime pcode.append(rPush) try : pcode.append(int(word)) except : try: pcode.append(float(word)) except : pcode[-1] = rRun # Change rPush to rRun pcode.append(word) # Assume word will be defined if not cStack : return pcode prompt = "... "
>>> forth.compile() Forth> : negate 0 swap - ; []
>>> forth.rDict['negate'] [<function rPush at 0x9fbe5a4>, 0, <function rSwap at 0x9fbe374>, <function rSub at 0x9fbe25c>] >>>
>>> forth.compile() Forth> 6 negate [<function rPush at 0x9fbe5a4>, 6] >>> forth.compile() [<function rRun at 0x9fbe56c>, 'negate'] >>>
def cColon (pcode) : if cStack : fatal(": inside Control stack: %s" % cStack) label = getWord() cStack.append(("COLON",label)) # flag for following ";" def cSemi (pcode) : if not cStack : fatal("No : for ; to match") code,label = cStack.pop() if code != "COLON" : fatal(": not balanced with ;") rDict[label] = pcode[:] # Save word definition in rDict while pcode : pcode.pop()
So now let's look at other word groups that also use the cStack, forcing deferred compilation.
BEGIN ... UNTIL Control structure
>>> import forth >>> forth.main() Forth> 5 begin dup . 1 - dup 0 = until 5 4 3 2 1 Forth>
def cBegin (pcode) : cStack.append(("BEGIN",len(pcode))) # flag for following UNTIL def cUntil (pcode) : if not cStack : fatal("No BEGIN for UNTIL to match") code,slot = cStack.pop() if code != "BEGIN" : fatal("UNTIL preceded by %s (not BEGIN)" % code) pcode.append(rJz) pcode.append(slot)
# fact1.4th : fact # n --- n! replace TOS with its factorial 0 swap # place a zero below n begin dup 1 - dup 1 = until # make stack like 0 n ... 4 3 2 1 begin dump * over 0 = until # multiply till see the zero below answer swap drop ; # delete the zero
>>> import forth >>> forth.main() Forth> @fact1.4th Forth> 5 fact . ds = [0, 5, 4, 3, 2, 1] ds = [0, 5, 4, 3, 2] ds = [0, 5, 4, 6] ds = [0, 5, 24] 120 Forth>
IF, ELSE, THEN Control Structure
condition IF true-clause THEN or condition IF true-clause ELSE false-clause THEN
def cIf (pcode) : pcode.append(rJz) cStack.append(("IF",len(pcode))) # flag for following Then or Else pcode.append(0) # slot to be filled in def cElse (pcode) : if not cStack : fatal("No IF for ELSE to match") code,slot = cStack.pop() if code != "IF" : fatal("ELSE preceded by %s (not IF)" % code) pcode.append(rJmp) cStack.append(("ELSE",len(pcode))) # flag for following THEN pcode.append(0) # slot to be filled in pcode[slot] = len(pcode) # close JZ for IF def cThen (pcode) : if not cStack : fatal("No IF for ELSE for THEN to match") code,slot = cStack.pop() if code not in ("IF","ELSE") : fatal("THEN preceded by %s (not IF or ELSE)" % code) pcode[slot] = len(pcode) # close JZ for IF or JMP for ELSE
# fact2.4th Recursive factorial # n --- n!
: fact dup 1 > if # if 1 (or 0) just leave on stack
dup 1 - fact # next number down - get its factorial
dump * then # and mult - leavin ans on stack
;
Forth> @fact2.4th Forth> 5 fact . ds = [5, 4, 3, 2, 1] ds = [5, 4, 3, 2] ds = [5, 4, 6] ds = [5, 24] 120 Forth>
Variables, Constants and the Heap
변수 상수 그리고 힙
heap = [0]*20 # The data heapheapNext = 0 # Next avail slot in heap def rCreate (pcode,p) : global heapNext, lastCreate lastCreate = label = getWord() # match next word (input) to next heap address rDict[label] = [rPush, heapNext] # when created word is run, pushes its address def rAllot (cod,p) : global heapNext heapNext += ds.pop() # reserve n words for last create
>>> import forth >>> forth.main() Forth> create v1 1 allot Forth> create v2 3 allot Forth> create v3 1 allot Forth> dump ds = [] Forth> v1 v2 v3 dump ds = [0, 1, 4] Forth>
>>> import forth >>> forth.main() Forth> create v1 1 allot Forth> create v2 3 allot Forth> create v3 1 allot Forth> ^D >>> print forth.heapNext, forth.heap 5 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] >>> forth.main() Forth> 22 v2 ! # set v2[0] = 22 Forth> 23 v2 1 + ! # set v2[1] = 23 Forth> v2 @ . # print v2[0] 22 Forth> ^D >>> print forth.heapNext, forth.heap 5 [0, 22, 23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] >>> forth.rDict['v3'] # See definition of v3 [<function rPush at 0x8ba0454>, 4]
>>> forth.main() Forth> : varzero create 0 , ; Forth> varzero xyz Forth> xyz @ . 0
Forth> : constant create , ; Forth> 2009 constant thisYear Forth> thisYear @ . 2009
That's fine, but there is nothing to prevent you from simply "!"ing thisYear to another value. It's the same as any variable. But if we instead do the following
Forth> : constant create , does> @ ; Forth> 2009 constant thisYear Forth> thisYear . 2009 Forth> ^D >>> forth.rDict['thisyear'] [<function rPush at 0x9865454>, 3, <function rAt at 0x9865534>] >>>
then you can see how a call to rAt has been attached to thisYear's runtime. There is no need to use an "@" to retrieve its value and "!" cannot be used to change its value.
With these builtins, it is not difficult to make arrays, including multidimensional ones. We can even make primitive structs (like C) assigning constants for field offsets.
Like C, however, there is not much memory protection. If an array reference is out of bounds, it will simply write into something else. Of course, in this model, this will stay within our heap but in a C adaptation of this code, even that would be lost.
We'll end this section with a final factorial program, this time using variables. The code looks more like a traditional language, albeit in postfix
# fact3.4th
: variable create 1 allot ; # --- create var and init to TOS
variable m
variable answer
: fact # n --- n! replace TOS with factorial
m ! # set m to TOS
1 answer ! # set answer = 1
begin
answer @ m @ dump * answer ! # set answer = answer * m
m @ 1 - m ! # set m = m-1
m @ 0 = until # repeat until m == 0
answer @ # return answer
;
15 fact . # compute 15! and print
And now, let's run it
Forth> @fact3.4th ds = [1, 15] ds = [15, 14] ds = [210, 13] ds = [2730, 12] ds = [32760, 11] ds = [360360, 10] ds = [3603600, 9] ds = [32432400, 8] ds = [259459200, 7] ds = [1816214400, 6] ds = [10897286400L, 5] ds = [54486432000L, 4] ds = [217945728000L, 3] ds = [653837184000L, 2] ds = [1307674368000L, 1] 1307674368000 Forth>
Since our model is built in Python, we inherit its nice automatic switch to long integers.
Notice that the variables "m" and "answer" are defined outside the "fact" definition. We don't have private local variables within a definition.
Other Issues
As mentioned earlier, Forth can be very efficient both with memory and CPU time. Consider the following bits of PDP-11 assembler code. It is a recreation of a little bit of our first Forth expression "5 6 +".
stack:
... ; more space here for the stack to grow
6 ; <--- r4 stack pointer (stack is upside down)
5
ds: 0 ; base of stack
rPush ; <--- r3 tracks the pcode thread
5
rPush
6
rAdd
.
. ; thread continues ...
rPush: mov (r3)+, -(r4) ; ds.append[pcode[p]]; p += 1
jmp @(r3)+ ; return to thread
rAdd: add (r4)+, (r4) ; tmp=ds.pop(); ds[-1] += tmp
jmp @(r3)+ ; return to thread
rDup: mov (r4),-(r4) ; ds.append(ds[-1])
jmp @(r3)+ ; return to thread
This should look somewhat familiar from the assembler model in the previous chapter. We have the data stack on top, a bit of "threaded" code in the middle and 3 builtins. The threaded code (the name will be obvious in a minute) is essentially the same as our "pcode" array in the Python model. Machine register r3 is our "p" indexe to the next word in the pcode. The program counter, PC jumps between the builtins. The instruction "jmp @(r3)+" loads the program counter with the memory word indexed by r3 and then increments r3 to point at the next word. The program execution weaves through the threaded code out of one builtin (rPush) and into the next (rAdd). Register r4 is the ds index. On the PDP-11 the stack grew downward and lower machine addresses were actually higher on the stack. The instruction "mov (r3)+,-(r4)" pushes the next word in the thread (5 say) onto the data stack, first decrementing r4 to the next higher stack location.
Now if we were writing this in assembler we might do the following
mov #5, -(r4) ; push 5 onto stack
mov #6, -(r4) ; push 6 onto stack
add (r4)+,(r4) ; add in stack
But if we add up the memory use and execution cycles, only the "jmp @(r3)+" instructions, the needle, if you will, that sews the code together are missing. These jumps constitute very little overhead.
In the early 1980's I developed a process control system for a newspaper mailroom that tracked bundles of newspapers on conveyor belts. Each bundle had a specific chute designation which would deliver it to a truck being loaded. We put together a small Forth system in less than 1000 lines of assembler. This system was concurrent having a special word so that one thread could yield control of the cpu to another. Like Forth itself, this application was divided into tiny pieces sewn back together. One pcode thread for example monitored keyboard input from one of the terminals. Another output messages to all the screens which included echoing input from either keyboard. Still other threads would handle a sensor on a belt or update a light display. Each thread had its own data stack but they shared variables on the heap and of course word definitions. There were no locking problems because the threads themselves yielded control only when safe to do so. Such a system was possible because throughput was only at human speed.
One final point. We used recursion in the second factorial example. This is unusual in Forth. Normally a word must be defined before being used in another definition. But in our compile function the last "except" clause allows us to build an rRun to an undefined word with the assumption that it will be defined before it is actually used. But this in turn leads to another issue. Our rRun runs a word dynamically, that is, it looks up the definition in rDict just before running it. Most Forths would not do that. It's expensive when the computation for most words is usually so small. So rather than following a pcode entry "rRun" with the name of a word, it would be reference to the words pcode and the dictionary lookup is avoided. This also has an interesting implication. If you redefine a word that has been used in the definition of other words, those other words do not change their behaviour. They are still locked to the old code. The programmer might well find this unexpected.
Prev
Rss Feed
