2015.06.13 02:45

What is Forth? (포스란 무엇이냐)

이 글은 python for fun의 forth 편을 번역한 것이다,

뒷부분은 번역이 조금 안되었지만 이해에는 별 문제가 없을 것으로 본다.
lisp의 거울상처럼 움직이는게 신기해서 한번 이해해 보려는 시도의 하나였다.


2015.6.12 -현재 버전 0.7


What is Forth? (포스란 무엇이냐)


알맹이만 말하자면 포스는 컴파일러와 인터프리터를 조합한 것이다.  컴파일러는 이전의 챕터에서 본것 처럼 소스코드를 기계어코드로 바꾸어주는 것이 아니라 "가상"기계의 명령어로 바꾸어주며 우리는 이를 "pcode"라고 부른다. 같은 아이디어가 자바나 파이선 같은 언어에서 쓰이고 특히 최신의 동적언어에서는 특히 그렇다. 

그러나 포스에서 우리는  pcode  레벨에서 프로그램하고 이것이 가상 기계의 어셈블리어라고 부를 수 있는 것이다. 그러나 이 언어어는 동적인 특성이 강하고 흥미롭운 방법으로 확장할 수 있는 언어다. 



포스에서 "snippets of computation"라고 할수 있는  "words"를 가지고 푸시다운 데이타스택을 조작하거나 이들을 다시 연결해서 새로운 "words"를 만들어(compile ) 한단계 더 높은 레벨에서 같은 일을 할 수 있다. 

더 이상 흔하게 쓰이지는 않지만 포스는 공부할 가치가 있는 특징들이 있다. 이 언어는 예제 코드의 공부를 통해서만 얻어질 수 있는 대단한 미니멀리즘이 있다.

포스는 어셈블러에 비해 프로그램을 비교적 쉽게 작성할 수 있는 좋은 타협이며 놀랄만큼 작은 메모리를 사용하고 놀랄만큼 빠르다.  내장된 컴파일러와 인터프리터를 가지고 동시적인 스레드를 갖는 어플리케이션 코드까지 만드는데 몇 킬로 바이트의 메모리와 어셈블러의 1/2 속도를 내는 시스템을 만든적이 있다.

위키백과에 따르면 포스는 부트로더나 임베디드 시스템 , 우주선 어플리케이션에 사용되며 GNU 프로젝트의 활발한 구현도 있다.

이 장에서 우리는 작은 포스  compiler/interpreter 시스템을 만들어 자세하 살펴볼 것이다.
우리의 구현은 매우 작고 기본적인 것이다.  (floats and ints) 숫자만이 기본 데이터 타입이며 IO는  오로지 터미널을 통해서만 일어난다.

나중에 위에서 말한 어플맅케이션을 간단히 보기로 한다. 신문의 메일룸을 공정제어하는 시스템이다, 이제 의자에 앉아 즐겨보자.

인용하는 단어에 대해 이야기하자. 모두 대눈자를 사용하는 단어가 있다면 그거는 포스의 단어다. 우리의 포스는 실제로는 대소문자 구별이 없지만 전통적으로 포스 프로그램은 대문자로 작성되었다.  대소문자가 섞인 것들은 파이선 코드이다. TOS 는 top-of-stack이다. 다른  단어들은 스스로를 나타낼 때 인용부호가 붙을 것이다.

Using the Data Stack

"데이터스택(data stack)"은 중요한 기능이다. 부억의 화로와 같다.  이 기능을 직접 이용하는 것으로 언어의 제약점이 줄어든다.  반드시 후위연산(postfix)과 편해져야 한다. 


이제 예제로 점프해 보자. 포스의 코드는 여기에  Click Here to access forth.py
$ python forth.py
Forth> 5 6 + 7 8 + * .
165


이제 두합의 곱 "(5+6)*(7+8)"을 계산해보자. 여기서는 인픽스 표기법으로 적었으며곱셈이 덧셈의 뒤에 일어나야 한다는 것을 확실하게 만들기 위해  괄호가 필요하다.  리스프 언어처럼 프리픽스 표기법으로 적는다면 괄호 하나가 더 필요하다. 하지만 포스에서 처럼 포스트픽스 연산을 한다면 괄호는 아주 간단히 불필요하게 돈다. 연산자는가 계산에 필요한 위치에 자리잡으면 끝나는 것이다
 
(사족이지만 만약 독자가 일본어를 안다면 포스트픽스로 생각하는 것이 부자연 스럽지 않다는 것을 알것이다,)

일의 진행을 조금 명백히 보여주기 위해 포스의 워드인  "dump"를 사용하여 그때 그때의 데이타 스택의 값을 보여준다. 이제 조금 더  진행하여 각각의 단일한 수행마다 데이타 스택의 변화를 구경하자. 
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

데이타 스택 조작을 위한 기초단어 만들기

가감승제말고도 스택을 만지기 위한 기본 내장워드들이 있다. 

Along with add, subtract, multiply and divide there are other basic builtin words that manipulate the stack as well.

  • DUP 은 스택의 탑을 복제한다 (TOS)
  • SWAP 은 맨위의 두개를 바꿔치기한다
  • DROP 은 TOS 를 뽑아서 버린다t
  • "."  TOS에서 데이타를 팝하고 인쇄
  • "=" 은 두 데이타를 팝해서 비교한 후 같으면 스택의 꼭대기에 1을 올려놓고 아니면 0을  올려놓는다.

이들은 총명한 방법으로 조합될 수 있고 다음에 두 예제를 보자.

These can all be combined in clever ways. Here are two examples.

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> 

 forth.py 에 있는 기본 런타임 파이선 코드들을 보인다. 데이타 스택은 단순히 "ds"라고 불리는 파이선 리스트이다.   리스트의 "append" 메소드로 아이템을 밀어넣고   "pop" 메소드로 맨위의  아이템을 얻는다. ( 그리고 버린다)  그리고 기본워드는 작은 함수로 두개의 인자가 있다,  우리가 이 인자를 이용할 것은 아니지만 나중에 런타임함수들은 이 인자를 이용할 것이다. 

 
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()

이들은 물론 더 효율적으로 구현될 수도 있으나 명료함을 위해 이번에는 이런 방식으로 하자.  그리고 나누기와 빼기의 순서를 눈여겨보자. 그리고 나누기에서 파이선의 / 를 이용하므로 두 인자중의 하나가 float 이면 결과도  같은 형식이라는 것도.  만약 두 인자가 정수라면 정수의 나누기가 이루어진다.

이 함수들의 참조는  "rDict" 의 룩업테이블에서 일어난다.  "+"는 함수 (rAdd) 에 매치되는 식이다. 이 사전의 항목들은 단순명료하다. 


Defining new words

새로운 워드를 정의


새로운 워드 NEGATE를 정의하여 tos 를  원래 값의 음의 값으로 바꿔보자. 모든 워드 정의는 ":"로 시작하요 정의할 단어가 바로 따라온다.  그리고 ";"가 나오기 전까지 뭔가가 줄줄이 붙고 이것이  워드 정의의 몸체다. 그래서 negate를 정의하고 태스트 하고 다음에 같은 일을 sqr에도 해보자




Forth> : negate 0 swap - ;
Forth> 5 negate .
-5
Forth> : sqr dup * ;
Forth> 6 sqr .
36
Forth> 

Compiling Words to Pcode

워드를 PCODE로 컴파일 

컴파일의 첫번째 단계는 문법적파싱이고 포스에서는 아주 간단하다.  "tokenize" 함수가  커멘트를 제거하는데 "#" 로 시작해서 줄의 끝까지 모든 것을 제거한다.  그리고 텍스트를 화이트스페이스 기준으로 워드의 리스트로 분리한다. 이것을 이제 파이선 프롬프트에서 확인하자.


>>> import forth
>>> forth.tokenizeWords("5 6 + .  # this is a comment")
>>> forth.words
['5', '6', '+', '.']
>>> 

만약 컴파일러가 워드를 정의하는 도중이 아니거나 나중에 보듯이 새로운 제어구조를 형성하는 도중이 아니라면 "immediate mode" 라고 부르는 중간 모드에 있다.  한개의 워드가 컴파일되고 되돌아온다. 


>>> 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
[]
>>> 

compile 함수를 수행하다보면 자동으로 프롬프트가 나오는 것에 유의하라.

컴파일된 코드가 리스트에 나온다. 숫자는 정수이건 실수형이건 수자를 "rPush"를 통해 데이타 스택으로 들어간다.  "+" 와 "." 도 각각 해당하는 런타임 함수로 컴파일된다. 이제 파이선의 "compile" 함수를 구경하자.


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 = "... "

부분적으로는 애매할 것이다. 기본적으로 우리는 다음 단어를 "getWord" 를 사용해서 가져온다. 입력이 더 필요하면 프롬프트 할 것이다. 이  "compile" 함수는 프롬프트가  "Forth> "  또는 "... "일지를 제어한다. 만약 워드이름이 기본 런타임 동작으로 "rDict" 에 있는 것이라면 그 함수를 부르는 것으로 번역될 것이다. 
만약 워드가 정수나 실수형으로 만들어질수 있는 것이라면 "rPush" (역시 내장형) 로 번역되고 그 다음에 데이터 스택으로 푸시될 실제 숫자가 온다.   immediate mode에서는 단일한 입력 워드가 컴파일되고 리턴된다. 

이제 새로운 단어를 컴파일해보자.


>>> forth.compile()
Forth> : negate 0 swap - ;
[]

아무 pcode도 리턴되지 않았다, 그러나 재미있는 부차적 효과(side effect)가 생겼다.

>>> forth.rDict['negate']
[<function rPush at 0x9fbe5a4>, 0, <function rSwap at 0x9fbe374>, 
 <function rSub at 0x9fbe25c>]
>>> 


이제 새로 들어온 넘은 rDict에 있고 내장함수처럼 쓸 수 있다. 
>>> forth.compile()
Forth> 6 negate
[<function rPush at 0x9fbe5a4>, 6]
>>> forth.compile()
[<function rRun at 0x9fbe56c>, 'negate']
>>> 

이제  위의 "compile" 함수에서  cAct 가 cDict 에 있는지 체크한다. 이는 컴파일 타임 함수를 찾는 것이다. 이 함수들은 컴파일과정을 위한 헬퍼 함수다. ":" 와 ";" 는 모두 컴파일 타임 워드들이다. 이제 이들의 해당 파이선 함수를 보자.


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()

이제 cStack에 ":" 로 시작하면서 밀어 널고 나중에 ";"으로 뽑아내야 한다는 것을 보았다.  ":"  워드는 입력으로 부터 라벨을 받고  만약 여의치 않으면 "..."로 프롬프트한다. 이 라벨은  저장되어 ";"워드가 컴파일된 코드와 연결되어 rDict에 하나의 엔트라를  만들도록 한다. 이렇게 되면 코드는 지워진다. 이제 이 기간동안 cStack은 비워져 있지 않다. ":"로 컴파일이 시작되면  ";"에 매치되는 곳까지 진행되어야 한다.  이제 우리는 컴파일러가 "deferred(지연된)" 모드로 들어갔다고 말한다. 

이제 cStack을 같이 사용하고 있는 다른 워드 그룹을 보자 . 이들은 지연된 컴파일을 강제한다. 

So now let's look at other word groups that also use the cStack, forcing deferred compilation.

BEGIN ... UNTIL Control structure

 BEGIN 과 UNTIL 은 반복 루프를 설정한다. UNTIL은 TOS에서 팝을 한다. 만약 0 이라면  제어는 begin 다음으로 돌아간다.  아래에 예제가 있다. 

Thewords set up an iterative loop. UNTIL will pop the TOS and, if it is zero, will return control to the word following BEGIN. Here is an example

>>> import forth
>>> forth.main()
Forth> 5 begin dup . 1 - dup 0 = until
5
4
3
2
1
Forth> 

우리는 5를  스택에 넣는 것으로 시작하여 인쇄한후 1을 빼는 작업을 0 이 될때까지 반복한다.  DUP을 두번 쓴 이유는 카운트 다운 뿐만이 아니라  안쇄하고 0이 되는가를 체크하기 위해서도 필요하다.
BEGIN 과 UNTIL은 모두 컴파일 타임 워드이며 아래에 해당 파이선 함수를 보인다.

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)

BEGIN은 아무 코드도 만들지 않는다. 다만 콘트롤 스택의 다음에 올 워드의  주소(len(pcode)) 만 집어넣는다.  그리고 컴파일러를 지연 모드로 만든다.  UNTIL은 매치되는 BEGIN을 체크하고 rJZ call (Jump if Zero) 을 발생시키며 저장된 주소로 돌아간다.  런타임에는 rJz이 TOS를 팝하고 만약 0이면 점프를 행한다. 

다음에 "포스스러운 (Forth-like)" 팩토리얼 계산의 정의가 있다. 이코드는 파일   "fact1.4th"에 저장되어 있어야 한다. 


# 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

중간의 DUMP는 디버깅을 위한 것이다. 돌려보자.

>>> 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

 BEGIN 과 UNTIL과 친밀한 구조로 보여야 한다.  컴파일 타임 코드에서 IF는 만약  1이라면 ELSE로 가는 rJZ 코드를 발생시키고 아니라면 THEN으로 가는 넘을 만든다. ELSE는  IF 를 위한 점프를 완결시키고 그 다음에는 THEN이 완결되면 가야할 곳으로 무조건 점프를 셋업한다. 
 
다음에 두번째 팩토리얼 워드 정의가 있다.  BEGIN과 UNTIL을   쓰는 대신 우리는 재귀를 사용하고 이 주제는  나중에 심도있게 다른다. 그러고 끝점을 설정하기 위한 플랙을 설정하지 않고 IF THEN을 사용했다. 
# 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
  ;

다시 DUMP는 동작을 보여주기 위해  의도적으로 넣은 코드다.

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 

변수 상수 그리고 힙


이제 우리는 데이타를 데이타 스택의 바깥에 저장해야 하는 시점까지 왔다.  우니는 많은 변수들을 데이타 스택에 아닌 곳에 편하게 저장하기를 원할수도 있으며  데이타를 1차원 또는 다차원의 행렬에 저장하기를 원할지도 모른다. 
포스 시스템은 이러한 목적을 위해 메모리 영역을 따로 만들어 놓았으며  다른 워드를 만들기 위한 내장기능을 갖고 있다. 상당히 깔끔하다. 


우선 이런 내장기능을 살펴보자 . 이번 모델에서 힙은 단순히 20개의 정수이다.  실제와는 조금 다르다. 


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

이제 흥미롭게도 ,  rCreate 와 rAllot 은 런타임 워드다.  rCreate가 돌아갈 때  컴파일러는 즉시모드이며  입력에서 다음에 올 워드 (pcode에서가 아니라)
가 정의될 워드다. 정의된 워드의 런타임 작용은 단순히 예약된(reserved) 힙 주소를 데이타 스택에 옮기는 것이다. ALLOT은 실제로 하나 또는 그 이상의 워드를 예약하는 것이며 heapNext를 진전시켜서 나중의 CREATE가 쓸수 있도록 준비하는 것이다. 이제 예제를 보자.  포스 코드를 실행하고 컴파일 하기 위해 forth.main을 사용할 것이다.



>>> 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> 

여기서 우리는  V1, V2,  V3  세개의 워드를 만들었다. 각각은 해당 힙 주소가 있고 실행시에는 이 주소를 푸시한다.  V2와 V3 사이의 "공간 (space)"을 보자.  V2를 만들때 ALLOT이 사용되었기 때문이다. 
그리고 아래에 힙장소들을 사용하는 방법을 보여준다. "@" and "!" 는 힙에 있는 워드들을 꺼내오고 (fetch) 설정한다 ( set ).  


>>> 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]

이제 2개의 단일 변수  (V1 and V3)  와 3개의 워드를 갖는 V2를 만들었다. 다시 파이선으로 돌아야 우리는 힙이 변경되는 것을 볼 수 있고 다른 변수들의 실시간 정의를 볼 수 있다.
다른 유용한 내장 기능인 "." 도 있다. TOS 에서 팝을 한다음 힙의 다음 자유위치에 푸시한다. 이는 ALLOT을 대신해서 변수를 0으로 초기화하는 대신의 용도로 사용 가능하다. 


>>> forth.main()
Forth> : varzero create 0 , ;
Forth> varzero xyz
Forth> xyz @ .
0


Finally, there is a builtin DOES> that works together with CREATE inside a definition. It takes all following words up to the closing ";" and appends them to the rDict entry for the word just created. First consider this definition and usage of a CONSTANT

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.





저작자 표시
신고
Trackback 1 Comment 1
2015.01.06 11:32

스택 머신

예전에 나는 sicp를 설명하면서 레지스터머신을 설명한 적이 있다. 

그런데 레지스터 머신과 항상 경쟁하는 스택머신의 중요성은 그때에는 간과했다. 


FORTH 언어의 생태계는 스택 머신 위에서 움직인다,

lisp의 반대의 표기법을 갖는 포스는 가상 머신의 방식도 반대 

위키 백과에는 스택 머신을 이렇게 설명한다 .


http://en.wikipedia.org/wiki/Stack_machine


쿠프만의 책은 당시나 지금이나 중요하다 


http://users.ece.cmu.edu/~koopman/stack_computers/contents.html


저작자 표시
신고
Trackback 1 Comment 0
2014.12.21 23:38

pisc 분석

당분간 이 프로세서 분석은 알파와 베타 중간 상태다. 

현재 버전 0.0 (2014.12.21)




pisc 분석

이 프로세서는 참으로 특별하다.
너무 간단하게 만들다보니 동작도 이상하고 결함도 많다.
자세한 내요은 번역부분을 읽어라.

명령어는 매번 클럭시마다 사용된다.
매 클럭마다 한번은 fetch라는 명령어가 사용되고 한번은 execute가 시행된다.

원본에는 이렇게 나온다.
a) 레지스터중 하나가 어드레스 버스로 나가고 ALU 의 A 입력이 된다;
b1) 다른 레지스터는 데이터버스로 출력하고 ALU의 B 입력이 되거나; 또는
b2) 메모리로ㅜ터의 데이터가 다른 레지스터의 입력이 된다;
c) ALU의 출력이 A (그리고 아마도 B)에 적용되고 데이터는 첫 번째(address)레지스터에 저장된다,

a) one register is output to the Address bus and the ALU's A input;
b1) another register may be output to the Data bus and the ALU's B input; or
b2) data from memory may be input to another register;
c) an ALU function is applied to A (and perhaps B) and the result is stored in the first (address) register.


 

조건은 다음과 같다.

인스트럭션 레지스터는 외부에 따로 존재하는 것으로 회로도 page2에 74298을 이용하여 구현했다. (Quad 2-line to 1-line multiplexers with storage)

클럭의 하강 에지에 A 또는 B 선택을 한다.

일단 클럭의 상승에지에 clock의 반전입력이 들어가므로 클럭의 상승에지에 D 버스를 캡처하거나 미리 정해진 하드와이어드 코드를 캡처해서 출력한다.

미리 정해진 값은 10 111 111 1 111 00000이다.

그 값은 다음과 같다.
 
사진 참조


이 값의 의미는 다음과 같다.

메모리를 읽어서 r7에 저장하고 데이터라인에도 r7을 내보낸다. D line에는 메모리를 읽은 값이 들어간다. 결국 R7에 쓴다. CY=11로 0이 선택된다. 이 값은 래치된다.

이런 목적으로 74172 dual port ram이 사용되었다, 74182는 2비트 램이다.

74181은 00000이 선택되면 동작은 캐리가 0 인 경우 a+1이 일어난다. a 입력은 A 버스에 연결되어 있다, 결과는 종종 어드레스값에 1을 더하게 된다.


mrd는 rec로 바로 연결된다. 기묘하지만 메모리를 읽지 않는 상태가 듀얼포트를 읽는 것이고 mrd가 High인 경우는 clock의 반전 입력과 nand를 거처 mrd\ 가 된다..
(mwr도 같은 방법) 이것이 IR 이라는 게 신기할 다름이다.

wec\는 mrd와 fetch\의 nand다. 그러니까 메모리는 읽는 상태이고 fetch가 아닌 exec 상태이다. 메모리를 읽지 않으면 쓰여지지 않는거다.

  


저작자 표시
신고
Trackback 0 Comment 0


티스토리 툴바