Sublime Repl with scheme

개발툴 2015/08/10 14:54

Repl 을 이용하여 scheme 을 세팅한다.

서브라임의 packageInstall 을통해 먼저 SublimeRepl 을 설치. 


먼저 CLI 가 존재하는 스킴컴파일러를 적절히 (여기서는 SCM) 설치한다. 


http://people.csail.mit.edu/jaffer/SCM.html

(in windows)


다음 파일에서 scm 을 이용하도록 수정

%AppData%\Sublime Text 2\Packages\SublimeREPL\config\Scheme\Main.sublime-menu



"cmd": {"linux": ["scheme"],

          "osx": ["scheme"],

          "windows": ["scm"]},


혹은, ["scm", "-f", "$file_basename"] 을 지정하여 파일을 바로 넘길수 있다. 이때에는 repl 창이 계속해서 생성되는 불편함이 있지만.. #<unspecified> 같은 불편한 문자가 반복되지 않는다.. 


편의를 위해 단축키 설정. 같은 경로에 Default.sublime-keymap 생성, 적당한 단축키를 repl 프롬프트를 열기위한 값으로 설정한다.


[

{ "keys": ["alt+,"], "command": "run_existing_window_command", "args": {"id": "repl_scheme", "file": "config/Scheme/Main.sublime-menu"}}

]



서브라임이 구문분석을 할 수 있게 하기위해, Scheme.tmLanguage 파일을 생성한다. (경로는 main.sublime-menu 에 지정되어 있다. 기본값은 다음과 같음)


Packages\sublime-scheme-syntax\Scheme.tmLanguage


파일의 syntax 를 scheme 으로 설정하여 toos > evel in repl 을 통해 평가.

기본 단축키는 

ctrl + ,,F

( ctrl 과 ,를 함께 누르고 뗀후 f )



저작자 표시 비영리 변경 금지

'개발툴' 카테고리의 다른 글

Sublime Repl with scheme  (0) 2015/08/10
[SVN] change list  (0) 2014/08/19
[Sublime Text 2] C# 에서 주석처리가 되지 않을때  (0) 2014/08/18
SublimeText Tabs > space  (0) 2014/08/13
python 콘솔등에서 출력 텍스트 컬러  (0) 2014/07/25
Mac Os Terminal Color  (0) 2014/07/24

2.3.4 Huffman Encoding Trees

허프만 인코딩 트리





이 절에서는 리스트 구조와 set 과 tree 를 다루기 위한 데이터 추상화를 연습해 보았다.

컴퓨터에서는 데이터를 나타내기 위해 0, 1 의 연속된 값을 사용하는데, 

아스키코드가 각의 문자를 7개 비트를 활용하여 표현하는 것이 그 예라 할 수 있다.


7 비트를 사용하면 2^7 개의 데이터를 구분할 수 있다, 


일반적으로 n 개를 표현하기 위해 개의 비트가 필요하다


고정길이 인코딩 방식


예를 들면 문자를 표현하기 위해


A 000 C 010 E 100 G 110

B 001 D 011 F 101 H 111


와 같이 표현할 수 있다.

 

이를 따를때, 

BACADAEAFABBAAAGAH

는 다음과 같이 인코딩 된다 


001000010000011000100000101000001001000000000110000111 (54비트)


이런 코드방식을 각각의 심볼이 같은 개수의 비트로 구성되어 있으므로, fixed-length (고정길이) 코드라고 부른다.


고정 길이 대신 가변 방식의 코딩도 쓸모 있을때가 있다. 


가변길이 인코딩 방식


빈도가 월등히 높은 문자에 대해 좀더 적은 비트수를 할당하여, 데이터를 좀더 효율적으로 메시지를 인코딩 할 수 있다.


위 고정길이 인코딩방식의 예를 variable-length (가변길이) 인코딩 방식으로 다음과 같이 재정의해보자.

A 0 C 1010 E 1100 G 1110

B 100 D 1011 F 1101 H 1111


이제, 같은 문자를 다음과 같이 인코딩한다.

100010100101101100011010100100000111001111 (42비트)

고정 길이 인코딩 방식과 비교했을때 20% 가량의 공간절약 효과를 얻을 수 있다.


이런 가변길이 인코딩방식에도 문제가 있는데, 바로 어떤 지점에서 하나의 심볼이 종료된 것인지 알기가 어렵다는 것이다. 

모스코드는 이런문제를 특별한 구분자(seperator code) 를 두는 것으로 해결 했다. 또 다른 해결책은, 

어떤 심볼도 다른 문자의 인코딩 값을 시작 코드값으로 가질 수 없도록 디자인 하는 것이다.

A를 0 이라고 정한 위 예의 경우, 어떤 문자도 0으로 시작할 수 없다. 


가변길이 인코딩 방식의 문제점

* 특정 심볼 종료 지점을 알기가 어렵다


solution

1. separator code

각각의 구분자를 심볼종료시점에 넣는 인코딩 방식

2. prefix code

어떤 문자도 다른 문자를 시작코드 값으로 가질 수 없는 인코딩 방식 


일반적으로 가변길이 prefix 인코딩 방식을 적절히 사용하면 상당한 이점을 볼수있다. 

이런 인코딩의 한 scheme 이 huffman 인코딩 방식이며, 허프만인코딩은 바이너리 트리로 표현되어 심볼을 인코드 할 수 있다.


허프만 인코딩


허프만 인코드는

* 각각의 리프가 아닌 트리의 노드는 자기 자식 노드들의 심볼을 모두 포함하고 있다. 

* 리프노드는 상대적 빈도에 따른 가중치가 부여 되어있다.

* 리프가 아닌 노드는 자기 자식 노드들의 가중치 값의 합을 가지고 있다. 

* 이 가중치는 인코딩/디코딩 과정 모두에 사용 된다.  


허프만트리에서 각 리프는 상대빈도와 나타내고자하는 문자가 함께 표시되어 있다. 

어떤 심볼이든 root 에서 시작하여 리프로 도달하여야 문자가 있음을 확인할 수 있다. 

아래로 내려갈때, 왼쪽 가지로 가는경우 0을 추가하고, 반대로 오른쪽으로 이동하면 1을 추가한다. 

D 의 경우 1011 이 된다.


비트열을 허프만 트리를 통해 decode 하고자 하면, root 에서 시작하여 비트열의 숫자를 보고 트리를 쫗아가면 된다.

리프에 도달할때마다 심볼을 알아낸 것이되고, 다시 다음 심볼을 알아내기위해 root 로 돌아가면 된다. 


허프만 트리의 생성


알파벳과 상대빈도가 주어져있으면, 어떻게 코드를 만드는게 최선일까? 

다음 예제를 살펴보자. 





알고리즘은 간단하다. 

가장 적은 상대빈도를 지닌 심볼이 가장 멀리 위치하는 것이다.

리프노드의 집합으로부터 시작하여 가장 빈도수가 낮은 두개의 노드를 찾아 이를 왼쪽노드, 오른쪽노드로 갖는 

부모노드를 만들며, 이 노드가 두 가중치의 합을 갖게끔한다.

두 노드를 set 에서 제거하고, 대신 이 새 노드로 대체한다. 이제 이 과정을 반복한다. 

노드가 단 하나만 남을때까지 이 과정을 반복한다. 


다음과 같은 과정으로 진행된다 .


Initial leaves {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}

Merge {(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}

Merge {(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}

Merge {(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}

Merge {(A 8) (B 3) ({C D} 2) ({E F G H} 4)}

Merge {(A 8) ({B C D} 5) ({E F G H} 4)}

Merge {(A 8) ({B C D E F G H} 9)}

Final merge {({A B C D E F G H} 17)}


이 알고리즘은 항상 유일한 트리를 만드는 것이 아닌데, 여러 노드가 가장 작은 가중치를 가질 수도 있기때문에다. 또한, 어떤 두 노드가 먼저 merge 될지 결정하는 것도 임의기 때문이기도 하다. 



허프만 트리의 표현


이제 허프만트리를 메시지를 인코드/디코드하는데 사용하고, 허프만트리를 생성하는 시스템을 살펴보자.

각 리프들은 leaf 라는 심볼을 포함한 리스트로 표현한다.


(define (make-leaf symbol weight)

(list 'leaf symbol weight))

(define (leaf? object)

(eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))


두 노드를 merge 하게 되면, 두 노드의 union 을 한 심볼의 집합이 된다.

우리의 심볼집합은 리스트로 표현했기 때문에, union 을 위해 append 프로시져를 사용한다.


(define (make-code-tree left right)

(list left

right

(append (symbols left) (symbols right))

(+ (weight left) (weight right))))


- (left right (symbol-l symbol-r) sum-wgt-lr) 와 같은 리스트 구조가 되겠다.


이제 selector 를 정의한다. 


(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)

(if (leaf? tree)

   (list (symbol-leaf tree))

   (caddr tree)))

(define (weight tree)

(if (leaf? tree)

(weight-leaf tree)

(cadddr tree)))


- 위에서 설명한 리스트 형태와 컬러링으로 매칭시켜보면 (left right (symbol-l symbol-r) sum-wgt-lr)


여기서보면 symbols 와 weight selector 들은 leaf 여부에 따라 그 동작이 다르다.

이를 잘 다루기 위해 친숙한 개념인 generic 을 scheme 에서도 사용할 수 있는데, 이는 2.4 절과 2.5절에서 살펴보도록 한다. 


디코딩 프로시저


(define (decode bits tree)

(define (decode-1 bits current-branch)

(if (null? bits)

   '()

   (let ((next-branch

   (choose-branch (car bits) current-branch)))

   (if (leaf? next-branch)

 (cons (symbol-leaf next-branch)

     (decode-1 (cdr bits) tree))

 (decode-1 (cdr bits) next-branch)))))

(decode-1 bits tree))

(define (choose-branch bit branch)

(cond ((= bit 0) (left-branch branch))

  ((= bit 1) (right-branch branch))

           (else (error "bad bit -- CHOOSE-BRANCH" bit))))


- leaf 까지 내려왔으면 그때의 심볼을 다음 디코딩대상 비트들의 결과에 붙인다.


각 요소에 가중치가 있는 set


방금의 트리표현에서, leaf 가 아닌 트리 노드의 경우 리스트로 표현한 심볼의 set 을 구성했었다. (symbol-l symbol-r)

하지만 요전에 알고리즘을 설명했을때 두 가장 작은 아이템을 merge 함으로써 얻어진 leaf 들과 tree 의 집합에 대해 동작할 필요가 있었다.

반복해서 set 에서 가장 작은 아이템들을 찾을 필요가 있었으므로, 순서가 있는 표현 방식을 사용하는것이 좋겠다.


가중치의 순서에 따라 정렬한 리프와 노드의 리스트의 집합을 구성할것이다. 

아래의 adjoin-set 프로시져는 예제 2.61 에 묘사된 것과 비슷하나, weight 를 통해서 비교가 되고 이미 존재하는 요소는 추가되지 않는 다는 점이 다르다.


(define (adjoin-set x set)

(cond ((null? set) (list x))

  ((< (weight x) (weight (car set))) (cons x set))

 (else (cons (car set)

  (adjoin-set x (cdr set))))))


아래의 프로시져는 심볼-빈도 페어리스트를 받아 최초의 leaf 들에 대한 ordered set 을 구성한다. 


(define (make-leaf-set pairs)

(if (null? pairs)

   '()

   (let ((pair (car pairs)))

       (adjoin-set (make-leaf (car pair) ; symbol

      (cadr pair)) ; frequency

  (make-leaf-set (cdr pairs))))))


저작자 표시 비영리 변경 금지

'SICP > 2. Building Abstractions with Data' 카테고리의 다른 글

2.3.4 Huffman Encoding Trees  (0) 2015/08/05
2.1.3 데이터란 무엇인가 ?  (0) 2015/02/07

IO Type

Programming/Haskell 2015/05/20 10:18


IO

Introduction to IO

IO a 

사이드 이펙트를 수행하고, 그 결과로 type a 의 value 를 리턴하는 abstract 타입을 고려할 수 있다.

statements 는 보통 사이드 이펙트를 통해 대부분 communicate 된다. I/O 모나드를 소개함으로써 하스켈에서 statement/action 의 개념을 소개한다. 그러나 이 개념 또한 expression 의 일환이라, 결합이 가능하다. (composition)

IO Char 

어떤 사이드이펙트를 수행하고 결과로 some character 를 리턴

IO ()

이 imperative type 에서도 가장 imperative 한 것이 IO () side effect 만 수행함

getChar :: IO Char
getChar :: () -> Char -- () -> something means trying to simulate laziness
putChar :: Char -> IO ()
return :: a -> IO a  -- 어떤것도 하지 않고 즉시 리턴 

a :: IO (Char, Char)
a = do x <- getChar
        getChar
        y <- getChar
        return (x,y)

standard input 으로 부터 3 문자를 읽어 첫번째, 세번째를 페어로 리턴

오른쪽에는 t 의 IO 가 위치하고 왼쪽에는 t 가 위치하여 두 타입이 다르므로, assign 연산자 대신 <- 를 사용하는 것.

getLine :: IO String
getLine = do x <- getChar
            if x == '\n' then
                return []
            else
                do xs <- getLine
                   return (x:xs)

이번엔 standard output 에 string 을 print 하는 IO 메서드

putStr :: String -> IO ()
putStr [] = return ()
putStr (x:xs) = do putChar x
                   pubStr xs

putStrLn :: String -> IO ()
putStrLn xs = do putStr xs
                 putChar '\n'

imperative code 나 I/O 코드를 다른 함수들과 사용할 수 있다는 데 그 강점이 있다. 특히 String 은 그 자체로 리스트이기때문에, 리스트에 사용되는 함수는 위와같은 방식으로의 활용도가 높다.

strlen :: IO ()
strlen = do putStr "Enter a string: "
            xs <- getLine
            putStr "The string has "
            putStr (show (length xs))
            putStrLn " characters"

pure code 를 작성하여 impure code 에 embeded 한 예라 할 수 있음.

저작자 표시 비영리 변경 금지

'Programming > Haskell' 카테고리의 다른 글

IO Type  (0) 2015/05/20
Parser in Haskell  (0) 2015/05/18
Parser 의 bind  (0) 2015/05/15
1 2 3 4 5 ... 40


티스토리 툴바