posted by 아겔-_- 2009.02.14 16:46
Concatenative Language

Concatenative Language

  • 이 문서는
  • ...
    • 프로그래밍 언어의 다양한 카테고리
    • 그중 하나로서 서로 대조
      • applicative
        • 함수에 인자로 적용(apply)함으로서 평가됨
        • C, Python, ML, Java등 거의 대부분의 언어
      • concatenative
        • 여러 함수의 조합이 하나의 데이터에 대해 작용(operate)하여 평가됨
        • 함수에서 함수로 넘어가며 하나의 데이터가 변화되어감
        • 이 데이터를 보통 '스택'으로
        • 이러한 함수의 조합을 'concatenating'
        • Forth, Joy, PostScript, Cat, Factor등의 언어
  • Concatenative, Stack-based language
    • 둘은 비슷하지만 같은 언어는 아님
    • 그럼에도 대부분의 경우 둘은 동일함
    • 스택은 CS에서 기본적인 개념
      • 많은 언어들이 내부적으로 스택을 이용하여 구현
      • 재귀호출을 지원하는 언어라면 call stack을 이용하거나 할거임
      • 이들은 어디까지나 내부적이고 구현에 관한 내용임
      • 프로그래머에게 직접적으로 노출된건 아니니까
        • 물론 first-class continuation을 지원하는 언어는 그렇게하지만
    • 스택기반언어를 차별화하는건 뭘까?
      • multiple stack
        • 모든 스택기반언어는 call stack을 통해 재귀호출을 지원
        • 그리고 data stack을 별도로 갖고 있음
          • 또는 operand stack
          • 함수간의 값을 전달하는데 이용하는 스택
        • data stack이 stack language programmer들이 말하는 'stack'임
    • 널리 쓰이는 applicative language
      • 언어의 중심개념은 함수호출
        • 인자들에 대해서 함수를 적용(apply)
        • 인자들은...
          • 상수이거나
          • 어떤 변수이거나
          • 또는 인자들이 어떤 함수의 결과이기도
    • stack language에서는
      • 함수호출은 단순히 함수의 이름을 통해서
        • 인자전달은 묵시적으로 이루어짐
          • 이들은 그전에 스택에 들어가 있어야함
        • 함수의 결과는 스택에 넣어짐
        • 그리고 다음 함수는 다시 이 스택에 넣어진 결과를 이용해 작동
        • ...그렇게 계속...
        • 함수는 추가적인 문법없이 그냥 이름만으로 호출
          • 그래서 "word"라고 불림
          • 그리고 문법적으로 정말로 "word"이기도 하고
  • 하나의 mutable 스택? 또는 functions from stacks to stacks?
    • 관점1

      • word은 스택에 push, pop한다
      • 직관적이고
      • 실제로 대부분의 구현이 이렇게

      관점2

      • ('concatenative language'을 선호하는 관점)
      • word은 스택을 입력으로해서, 스택을 출력으로 한다
      • 좀 더 일반화된 관점 (more amenable to formal reasoning)
      • function이 pure하다면 rule이나 type system을 재작성하기 쉽겠지

      However, these two points of view are equivalent: because in a given thread of execution, only one stack is "live" at any given point in time, updating the stack in-place has the same semantics as the purely functional world view. More details about this can be found in Manfred von Thun's paper Mathematical Foundations of Joy.

  • concatenative language의 기초
    • 코드에 이름을 붙이기 (값이 아니라)
      • 스택언어에서는 프로그램은 word와 literal의 조합
        • literal은 평가할때 바로 스택에 들어가는 값
        • word은 primitive이거나 다른 워드나 리터럴로 구성된 서브루틴
      • 값은 워드들간에 전달될때 이름을 갖지 않음
        • 또한 직접적인 참조도 없음 (기본적으로는)
      • 값은 원하는대로 복잡하고 다양할수있음
        • 팩터는 실제로 다양한 자료구조를 지원 (배열, 해쉬테이블 등등등)
        • 거기에 사용자정의 클래스라던지 뭐 그런것까지
        • 어쨌든 그럼에도 값은 LISP나 자바와 같은 형태의 이름을 갖지 않음
      • 팩터에서는 다음과 같은것들에 이름을 붙일수있음
        • word (functions)
        • 클래스
        • 슬롯(slots, 클래스의 인스턴스 변수)
        • 전역변수
        • 그리고 기타...
        • 그런데도 word에 전달한 인자에는 이름을 붙이지 않음
      • 왜냐하면 프로그램은 word와 리터럴들이기 때문에
        • 어떤 워드와 리터럴의 조합도
        • "factored out"하여 새로운 word로 쪼갤수있기때문
      • 어떠한 부분도 쪼개져서(factored out) 이름을 붙일수있기 때문에
      • applicative language에서는
        • 어떤 부분을 쪼개서 다른 함수로 만들기 어려울때가 많음
        • 가능한 경우라도 종속적인 변수들을 정리하는 작업이 필요
        • 또는 상태를 전달하거나 하는 복잡한 작업이 필요
        • 현대의 Java IDE에서는 이를 "extract method"와 같은것으로 지원
        • 그런데 stack-language에서는 단순히 cut-paste하면 됨
    • 다음과 같은 pseudo C코드를 보면
      • var x = ...;
        foo(x);
        bar(x);
      • 이런게 패턴이리라고는 생각도 하지 않았겠죠
      • 또 그래서 이게 추상화해야할 부분이고 이름을 주는게 귀찮다고 생각하진 않았겠죠
      • 팩터에서는 이러한것을 위한 combinator(higher-order function)이 있어요
        • bi라고 불리죠
        • 딱 그런 작업을 하는
        • 하나의 값을 받아서
        • 두개의 quotation(anonymous function)에 각각 전달해서
        • 그 두개의 결과를 스택에 쌓아요
      • [ foo ] [ bar ] bi
        • x을 foo에 적용하고
        • 똑같은 x을 bar에 적용하고
        • (x의 값은 스택에 이미 넣었다고 가정하고요.)
    • 또 다른 패턴을 보면...
      • var x = ...;
        bar(x,foo(x));
      • 팩터에서는 x의 값이 스택에 있다고 가정하면
      • dup foo bar
        • x을 foo에 적용하고, 그 결과랑 x을 bar에 적용
    • 이제 좀 더 복잡한 예를 들어봐요
      • infix "." 연산자

        • 보통 인스턴스 변수에 접근하거나 메서드 호출에 사용하죠

        var customer = ...;
        var price = customer.orders[0].price;

        팩터에서는 이런 표현은 정말 자연스럽게 이루어져요

        • 객체를 그냥 스택에 먼저 넣고서
        • 접근자를 통해서 하나씩 밟아 나가면 되니까요
        • customer객체가 스택에 있다고 가정하면
        • orders>> first price>>
          • 이렇게 간단히 표현할수있어요
          • 팩터에서 슬롯에 대한 접근자는 slot>> 처럼 이름지어요

        var customer = ...;
        var orders = (customer == null ? null : customer.orders);
        var order = (orders == null ? null : order[0]);
        var price = (order == null ? null : price);

        • 보통 이런코드로 null인 객체에 접근을 조심스럽게하죠
        • (foo == null ? null : foo.bar)
        • 위와 같은 패턴이 계속되고
        • 추상화하기 힘든 패턴이죠
        • 그루비 같은 언어에서는 이런걸 위한 별도의 문법이 따로 있기도 하죠

        팩터에서는 다음처럼 하면 되요

        • dup [ orders>> ] when dup [ first ] when dup [ price>> ] when
        • 스택의 값을 복사하고, 그 같이 null(f)이 아니면 [ ... ]의 quotation을 실행하고, 계속해서 그런 패턴인거죠

        또 이를 다음처럼 매크로로 만들수도 있겠죠

        • MACRO: maybe ( quots -- ) [ '[ dup _ when ] ] map [ ] join ;
        • 사용
          • { [ orders>> ] [ first ] [ price>> ] } maybe
    • 결론적으로
      • '디자인패턴' 따위가 필요없다는걸 알게되고
      • 새로운 문법을 설계할 필요가 없죠
      • 불필요한 코드를 작성할 필요가 없죠
      • 스택기반언어에서 언제나 나오는 일상적인 예제
      • 스택기반언어를 사용하면 불필요한 코드를 작성할 필요가 없어요
  • 여러값의 리턴
    • 스택기반언어에서는 multiple return values은 정말 간단
      • 그냥 스택에 여러개의 값을 넣으면 되니까
    • applicative language에서는 보통
      • 여러값을 튜플에 넣거나해서 되돌리죠
      • 스택기반에서도 이렇게 할수있긴해요
        • 하나의 단위로 여러개의 값을 취급하고 싶을때 좋죠
        • 그럼에도 그냥 스택에 값을 넣는게 더 쉽죠
    • 팩터의 대부분의 word들은 되돌림값이 없거나 하나
      • 여러개의 값을 되돌리는 word가 있기도 하고
      • 대부분 쉽게 사용할수있음
      • 예를 들어
        • 해쉬테이블에 접근하는 at word
        • 해쉬테이블과 키값을 인자로해서
          • 검색에 성공하면 키에 해당하는 값을
          • 없으면 f을 되돌림
        • 여기까진 자바나 파이썬이랑 유사
        • 팩터엔 at*이란 워드도 있음
          • 값이 있으면 값과 t을 되돌리고
          • 없으면 f f을 되돌림
          • 실제로 at word의 구현은 다음과 같음
          • : at ( key assoc -- value ) at* drop ;
        • 하스켈의 패턴매칭이나 커먼리습의 multiple values지원을 같은 방식으로 구현하기 쉬움
      • 더 흥미로운 예제는 조건문에서
        • 각각의 분기(branch)에서 2개의 출력값을 가질때
          • [ foo ] [ bar ] if +
          • foo, bar 모두 2개의 출력을 할때
          • +은 2개의 출력을 소비
          • applicative language에서는 좀 tricky하죠?
      • 그리고 약간 일반적이지 않은 예제는 'modifiers'
        • do-this, do-that, do-it과 같은 word을 갖고 있다고 가정
        • 그리고 모두 같은 x, y, z을 인자로 받는다고 가정
        • 그리고 3개의 x, y, z을 인자로 받고 이들을 조합해서 결과를 산출하는 frob
        • 결국 조합은 다음처럼
          • do-this
          • do-that
          • do-it
          • frob do-this
          • frob do-that
          • frob do-it
        • 실제로는 4개의 연산만을 정의했음에도
      • 실제적인 예를 들어보면
        • 팩터에는 subsequence을 추출하는 두개의 word
          • subseq
          • <slice>
          • 둘 다 인자는 똑같이
            • 시작 index
            • 끝 index
            • 그리고 sequence
          • 차이점은
            • subseq
              • subsequence을 '복사'해서 새로 생성
            • <slice>
              • subsequence에 대한 '가상 sequence'을 생성
              • '가상 sequence'에 변형을 가하면 원래의 시퀀스도 영향을 받겠지
              • 그리고 추가적인 메모리도 필요없고
          • (head), (tail)
            • 인자로는 시작 인덱스와 시퀀스를 인자로
            • 결과로는 시작 인덱스와 끝 인덱스, 그리고 같은 시퀀스
            • (head)
              • 언제나 결과 시작 인덱스는 0
            • (tail)
              • 언제나 결과 끝 인덱스는 sequence의 길이
          • from-end modifier
            • 끝으로부터 n개의 인자를 되돌리는

              이를 이용하여 다음과 같은 조합

              : head ( seq n -- subseq ) (head) subseq ;
              : tail ( seq n -- subseq ) (tail) subseq ;
              : head* ( seq n -- subseq ) from-end head ;
              : tail* ( seq n -- subseq ) from-end tail ;
              : head-slice ( seq n -- slice ) (head) <slice> ; inline
              : tail-slice ( seq n -- slice ) (tail) <slice> ; inline
              : head-slice* ( seq n -- slice ) from-end head-slice ; inline
              : tail-slice* ( seq n -- slice ) from-end tail-slice ; inline

        • short modifier
          • It implements the case where you want the first, say, 5 elements of a sequence, but if the sequence is shorter than 5 elements, you want the whole sequence, instead of an out of bounds error. It is implemented as follows; it is a modifier for the words above:

            : short ( seq n -- seq n' ) over length min ; inline

            short modifier까지 있으니 총 16개의 조합이 가능하고 실제로 구현한 연산은 6개

  • Concatenation은 조합
    • 스택언어의 기본적인 속성
      • 두개의 프로그램 X, Y을 조합
      • X의 결과를 Y에 전달해서 Y의 결과가 최종결과로
      • 결과적으로 공통적인 quoation 패턴은 명쾌하게 작성
    • 예를 들어
      • 팩터에서 시퀀스의 내용을 걸러내는 filter combinator
        • { 1 2 3 4 5 6 7 8 } [ even? ] filter .
        • 결과: { 2 4 6 8 }
      • 그 반대의 값들만을 원하면
        • { 1 2 3 4 5 6 7 8 } [ even? not ] filter .
        • 결과: { 1 3 5 7 }
      • 부분적용(partial application)도 간단히
        • { 1 2 3 4 5 6 7 8 } [ 4 > ] filter .
        • 결과: { 5 6 7 8 }
      • 위의 세개의 quotation을 비교해보면
        • [ even? ]
        • [ even? not ]
        • [ 4 > ]
        • 다른 applicative language의것들과 비교해봐도 간단
        • 커먼리습과 비교를 해봐도
          • (function evenp)
          • (lambda (x) (not (evenp x)))
          • (lambda (x) (> x 4))
        • concatenative language의 경우엔 인자에 이름을 붙일 필요가 없으니까
          • (locals vocabulary은 잠깐 접어두고)
    • 팩터에서 quotation은 객체의 sequence임
      • 예를 들어, [ 2 2 + ]은
        • 세개의 요소를 갖는다
        • integer, 2
        • integer, 2
        • word, +
        • 맨 마지막은 그 자체로 평가/introspected
      • sequence연산을 이용해서 quotation을 구성할수있음
    • 또 다른 quotation 기본적인 연산은 composition
      • 예를 들어 [ 2 + 0 > ]은
        • [ 2 + ]
        • [ 0 > ]
        • ...의 조합으로 구성할수있음
    • 기본적인 기초적인 연산
      • curry
        • ( scratchpad ) 5 [ + ] curry .
          결과: [ 5 + ]
        • 다른 언어였다면...
          * (let ((x 5)) (lambda (y) (+ x y)))
          #<FUNCTION (LAMBDA (Y)) {11682335}>
      • compose
        • ( scratchpad ) [ 3 = ] [ not ] compose .
          [ 3 = not ]

          * (let ((f (lambda (x) (= x 3)))) (lambda (y) (not (funcall f y))))
          #<FUNCTION (LAMBDA (Y)) {11680B3D}>

      • 바로 보이듯이 훨씬 자연스럽죠
  • Left->Right evaluation
    • concatenative language의 평가규칙은 단순
      • quotation에 대해서 왼쪽에서 오른쪽으로 읽어나가기
      • 리터럴은 스택에 쌓아넣고
      • 워드라면 그 선언을 실행
    • single-stepping debugger을 만들기 단순하게해줌
      • C++같은 언어와는 다르게
        • 모든 문장이 묵시적인 함수호출의 지뢰밭
        • 그리고 모두 명확한게 없죠
      • concatenative language에서 디버거는 단순히 왼쪽에서 오른쪽으로 스텝을 밟아나가면됨
    • 팩터의 'walker'툴
      • (ui-listener에서 Control-w을 눌러서 접근)
      • 이것도 그런 원리를 이용한
      • 간단히 continuation을 이용해 구현하였음
      • side-effects가 없다면 step backward도 가능하다는
  • Keyword parameters
    • 커먼리습, 스몰톡 같은 언어들은 이름 붙은 인자를 지원
      • (send-email
         :from "jack@aol.com"
         :to (list "jill@aol.com")
         :subject "Hello there"
         :body body)

    • 팩터에서 가장 비슷한것은 튜플과 슬롯을 선언해서 이를 다른 word에 전달하는것
      • 이는 정말 자연스러움

        slot setter은 그 값을 그대로 스택에 보존하기 때문

        이렇게 하여 chainning

        • jQuery나
        • Haskell의 모나드처럼

        stack-shuffling이 필요없이

        <email>
           "jack@aol.com" >>from
           { "jill@aol.com" } >>to
           "Hello there" >>subject
           body >>body
        send-email

    • 이렇게 하더라도 추가적인 언어적인 지원이나 기능이 필요없음
  • Rest parameters
    • 커먼리습등은 다음과 같은 다양한 수의 인자를 취할수있음
      • (+ a)
        (+ a b)
        (+ a b c)
        (apply #'+ list)
    • 그런데 스택의 인자가 몇개인지 알려줄 방법이 없음
      • 예를 들어, + 워드는 단 2개의 인자만을 스택에 취함
    • 이를 해결하려면
      • 새로운 워드를 만들거나
      • generailizations vocab을 이용하여 이를 해결
        • "a" 1 narray
          "a" "b" 2 narray
          "a" "b" "c" 3 narray
      • 또 다른 방법은 시퀀스를 이용해 다수의 값을 묶기
        • { 1 } sum
          { 1 2 } sum
          { 3 4 } sum
  • Pipeline style
    • A, B, C, D의 함수를 서로 연계하려면
      • concatenative language에서는
        • A B C D
      • applicative language에서는
        • (D (C (B (A x))))
        • 순서의 거꾸로로 보이죠?
        • 하스켈의 composition을 이용하더라도
        • D . C . B . A
      • 팩터 커뮤니티에서는 이런 코드를 pipeline code라고함
    • pipeline code은 스택언어에서 가장 단순한 idiom
      • word의 sequence은 스택으로부터 값을 취해서 결과를 다시 스택에 넣고, 그걸 또 연계하는 word가 취함
      • Unix shell의 명령들처럼 서로 chain
        • "/etc/passwd" ascii file-lines
          [ "#" head? not ] filter
          [ ":" split first ] map
        • cat /etc/passwd | grep -v '^#' | sed -e 's/:.*//'
    • 이러한 pipeline code은 ui framework에도 적용가능
  • Concision
    • concatenative language은 간결/명쾌하다
      • 왜냐하면 함수간 연계(glue)가 최소한만으로 이루어지니까
      • 그저 공백문자만으로
      • concatenative language의 6개 word을 호출하는 프로그램은
        • 다른 언어의 여섯줄의 코드정도일것
        • 파라메터 이름과 변수선언이 생략되니까
    • concatenative language은
      • 짧은 선언을 유도
      • 새로운 word을 만드는데 있어서 아주 적은 오버헤드만 있으니까
        • 어떤 word도 "factored out"하여 새로운 선언으로 분리가능
      • 주된 오해는
        • 짧은 선언을 만들도록 강제한다는것
          • 사실이 아님
        • 차라리 재사용 가능하도록 합니다
      • 실용적으로
        • 대부분의 프로그래머는 짧은 선언을 선택할것
        • 코드 재사용
        • 코드 문서화
        • 더 확실히 단위테스트 가능
    • 어쨌던 프로그램안에 중복된 코드가 있을 이유가 없음
      • 선언이 짧아져서
        • 높은 재가용성
        • 가독성이 높아지고
        • 괴상한 문법트릭을 쓸 필요가 없고
      • applicative language와 반대
        • 예를 들어, syntax-heavy한 perl같은 언어
    • 짧은 선언은
      • 더 효과적
      • concatenative language와 함께 더 많은 공통분모
        • 효과적인 코드
        • 간결/명벽한 코드
  • Simplicity
    • 좋은 concatenative code은 심플해요
    • 초보자가 처음 시작할때는 보통 stack-shuffler나 불필요하게 복잡한 코드에서 길을 잃죠
    • 팩터 커뮤니티는 초보자가 코드를 pastebin에 포스팅 하고 리뷰 받기를 권장합니다
      • ~ paste.factorcode.org
      • idioms
      • abstractions
      • library words
        • 더 짧은 코드
        • 더 단순한 코드
        • 더 가독성이 높은 코드
    • 팩터 소스코드에서 shuffle word, combinator의 빈도를 찾기
    • 복잡한 shuffler은 조금만 나타나야함
    • 좋은 코드는
      • 단순한 데이터 흐름
      • 괴상한 스택조작이 필요없음
    • 팩터의
      • 최적화컴파일러
      • 웹프레임웍
      • ui툴킷
      • 모두 복잡한 shuffler가 필요치 않음
      • 모두해도 (현재) 3만줄 정도의 코드
  • Meta-programming
    • Joy, Factor와 같은 언어
      • higher-order concatenative languages
    • quotation
      • anonymous function
      • 그저 list로 표현
        • 리스트 조작 연산을 통해 조작
        • 그렇게 조작하여 새로운 프로그램을 만들거나 실행할수도
    • 팩터에서
      • 컴파일러가 매크로를 통해 확장가능
      • 그를 통해 프로그램은 컴파일시간에 구성될수있음
      • LISP, Scheme에서의 매크로를 통한 메타프로그래밍과 유사
        • 강력한 매크로가 리습계열언어에서 괄호-문법의 존재이유(raison d'être)라고 알려져있기도
        • concatenative language은 이런 레벨의 표현력을
          • 더 평면적이고
          • 더 간단한 프로그램으로 성취
    • 쉽게 메타프로그래밍을 적용하는 덕분에
      • concatenative programming은 다양한 패러다임을 쉽게 수용/흡수
    • 그러한 예로서 팩터는 많은 패러다임을 포함
      • functional programming
      • object-oriented programming
      • dataflow programming
    • 명시적인 언어적인 지원이 없어도 고수준의 코드를 작성
      • 더 선언적인 코드
      • 언어가 더 fluid하니까
        • expression도 없고
        • statement도 없고
        • 프로그램은 그저 word의 순열
      • 프로그램의 모든 구조는
        • 컨벤션으로부터 오거나
        • word의 의미로부터
        • 언어의 문법으로부터가 아니라
        • 그러므로 프로그래머는 자유롭게 자신만의/원하는 수준의 추상화를 하는 convention을 만들수있음
  • Continuations
    • 원래는 Scheme으로 기원하는 기능
    • 이해하기 어렵고, 신비로운것으로 알려져있으나
    • concatenative language에서는 정말 단순
      • 단순히 스택의 snapshot
    • 팩터에서 continuation은
      • 각각의 스택을 나타내는 슬롯들을 갖는 튜플의 인스턴스
      • TUPLE: continuation data call retain name catch ;
      • continuation을 구체화하면
        • 스택의 복사본을 생성
        • 그리고 이를 다시 상태복원
      • 사실 다음과 같은것들을 구현하는데 필요한 유일한 primitive
        • exception handling
        • coroutines
        • co-operative threads
        • backtracking
  • Interactive development
    • 대화식개발/실험에 적합
    • 스택에 값들을 넣고 연산을 적용해보고
    • 단순히 listener에 정확한 입력을 주기만 한다면
    • 결과를 되돌려주니까
      • 그리고 그게 바로 프로그램이 되구요
    • 단위테스팅도 같은 패턴을 적용해볼수있심
      • 결과값과
      • 테스트할 quotation을 제공하면됨
      • 예를 들어 실제 팩터의 tools.test vocab의 예제는
        • [ "Hello world" ] [ "Hello " "world" append ] unit-test
신고

'삽질+돈되는짓 > FactorLanguage' 카테고리의 다른 글

Factor에서 개발하기  (0) 2009.02.15
Factor History & Features  (0) 2009.02.14
concatenative language?  (1) 2009.02.14
FAQ/Vocabulary  (0) 2009.02.13
코딩스타일  (0) 2009.02.13
팩터를 어떻게 공부해야할까요?  (0) 2009.02.13