D-Goon's Doc

Extend the evaluator to handle derived expressions such as cond, let, and so on (seciton 4.1.2). You may “cheat” and assume that the syntax transformers such as cond→if are available as machine operations.

cond?, cond→if 가 이미 있다는 가정을 하면 아주 쉽다. eceval-operations 에

   ;; Exercise 5.23
   (list 'cond? cond?)
   (list 'cond->if cond->if)

이렇게 두 줄을 추가해준다. cond?, cond→if 의 구현은 4장에서 빌려온다. 그리고 eval-dispatch 에서,

  ;; Exercise 5.23
  (test (op cond?) (reg exp))
  (branch (label ev-cond))
  ;; ----

이렇게 해당 operation을 잡아서 점프를 해 주고, 저것을 받는 ev-cond 를 만들면 된다. ev-cond의 구현은 cond→if 가 된다. exp에 변환된 if 문을 넣은 다음, 이걸 처리하기 위해 ev-if 로 가면 끝.

ev-cond
  (assign exp (op cond->if) (reg exp))
  (goto (label ev-if))

http://study-sicp.googlecode.com/svn/trunk/chapter-05/ex5.23-dgoon.scm

Ex 5.24

Implement cond as a new basic special form without reducing it to if. You will have to construct a loop that tests the predicates of successive cond clauses until you find one that is true, and then use ev-sequence to evaluate the actions of the clause.

위 5.23 의 ev-cond 부분을 cond→if 대신 machine language 로 직접 구현하라는 문제이다. 디버깅이 어려워서 꽤 오래 걸렸다. 풀이 후반에 추가한 print 함수가 아주 큰 도움이 되었다. 일단 아래와 같이 cond 관련 함수들과 print 를 함께 추가하자. print 는,

(perform (op print) (reg exp))

이런 식으로 레지스터의 내용을 찍어볼 수 있고, 없으면 디버깅이 거의 불가하다. … -_-a

(define print (lambda (x) (display x)(newline)))
(define eceval-operations
  (list
    ...
    ...
       ;; Exercise 5.23
   (list 'cond? cond?)
   ;(list 'cond->if cond->if) ;; Exercise 5.24 doesn't use it.
   (list 'cond-clauses cond-clauses)
   (list 'cond-predicate cond-predicate)
   (list 'cond-actions cond-actions)
   ;; for debug
   (list 'print print)
   ))

eval-dispatch 에서는 그냥 ev-cond 로 점프한다.

  ;; Exercise 5.23, 5.24
  (test (op cond?) (reg exp))
  (branch (label ev-cond))
  ;; ----

아래는 ev-cond 로부터 시작되는 실제 구현부이다. 귀찮아서 else 처리는 하지 않았다. 맞는 조건이 하나도 없거나 else 를 만나면 에러가 난다.

;; Exercise 5.24
ev-cond
  (assign exp (op cond-clauses) (reg exp)) ; now exp has clauses
  (save continue)
ev-cond-body
  (save exp)
  (save env)
  (assign continue (label ev-cond-loop))
  (assign unev (op first-exp) (reg exp)) ; unev is now A CLAUSE
  (assign exp (op cond-predicate) (reg unev)) ; exp is now A PREDICATE of A CLAUSE

  ;; (perform (op print) (reg exp)) ;; debug msg

  (goto (label eval-dispatch))
ev-cond-loop
  (restore env)
  (restore exp)
  (test (op true?) (reg val))
  (branch (label ev-cond-out))
  (assign exp (op rest-exps) (reg exp))
  (goto (label ev-cond-body))

ev-cond-out
  ;(restore continue) ;; becasue we'll directly jump into ev-sequence, not ev-begin
  ;(perform (op print) (reg exp)) ;; debug msg

  (assign unev (op first-exp) (reg exp)) ; unev is A CLAUSE which will be returned
  (assign exp (op cond-actions) (reg unev)) ; exp is ACTIONs!

  ;(perform (op print) (reg exp)) ;; debug msg

  (goto (label ev-sequence))
;; -----

http://study-sicp.googlecode.com/svn/trunk/chapter-05/ex5.24-dgoon.scm

Ex 5.25

Modify the evaluator so that it uses normal-order evaluation, based on the lazy evaluator of section 4.2.

Ex 5.26

Use the monitored stack to explore the tail-recursive property of the evaluator (section 5.4.2). Start the evaluator and define the iterative factorial procedure from section 1.2.1:

(define (factorial n)

(define (iter product counter)
  (if (> counter n)
      product
      (iter (* counter product)
            (+ counter 1))))
(iter 1 1))

Run the procedure with some small values of n. Record the maximum stack depth and the number of pushes required to compute n! for each of these values.

a. You will find that the maximum depth required to evaluate n! is independent of n. What is that depth?

앞에 나왔던 monitored stack을 구현하고 위 코드로 1부터 10까지에 대해서 답을 구해 보았다. print-statistics 의 결과만 모아보면 아래와 같다.

(total-pushes = 3 maximum-depth = 3)
(total-pushes = 64 maximum-depth = 10)
(total-pushes = 99 maximum-depth = 10)
(total-pushes = 134 maximum-depth = 10)
(total-pushes = 169 maximum-depth = 10)
(total-pushes = 204 maximum-depth = 10)
(total-pushes = 239 maximum-depth = 10)
(total-pushes = 274 maximum-depth = 10)
(total-pushes = 309 maximum-depth = 10)
(total-pushes = 344 maximum-depth = 10)
(total-pushes = 379 maximum-depth = 10)

처음 한 번은 factorial 함수를 정의할 때이므로 제외하고을 나머지의 스택 깊이는 10으로 일정하다.

b. Determine from your data a formula in terms of n for the total number of push operations used in evaluating n! for any n > 1. Note that the number of operations used is a linear function of n and is thus determined by two constants.

n	2	3	4	5	6	7	8	9	10
# of pushes	99	134	169	204	239	274	309	344	379

n이 1 증가할 때마다 # of pushes 는 35씩 일정하게 증가하고 있다는 것을 알 수 있다. 1차 함수이므로, 1차식을 만들어 표현하면 아래와 같다.

# of pushes = 35n + 29

Ex 5.27

For comparison with exercise 5.26, explore the behavior of the following procedure for computing factorials recursively:

(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

By running this procedure with the monitored stack, determine, as a function of n, the maximum depth of the stack and the total number of pushes used in evaluating n! for n > 1. (Again, these functions will be linear.) Summarize your experiments by filling in the following table with the appropriate expressions in terms of n:

	Maximum depth	Number of pushes
Recursive factorial	5n+3	32n-16
Iterative factorial	10	35n+29

The maximum depth is a measure of the amount of space used by the evaluator in carrying out the computation, and the number of pushes correlates well with the time required.

일단 위와 같이 재귀적인 factorial 에 대해서도 1부터 10까지의 n 을 넣어 print-statistics 의 결과를 뽑아 보았다.

(total-pushes = 3 maximum-depth = 3)
(total-pushes = 16 maximum-depth = 8)
(total-pushes = 48 maximum-depth = 13)
(total-pushes = 80 maximum-depth = 18)
(total-pushes = 112 maximum-depth = 23)
(total-pushes = 144 maximum-depth = 28)
(total-pushes = 176 maximum-depth = 33)
(total-pushes = 208 maximum-depth = 38)
(total-pushes = 240 maximum-depth = 43)
(total-pushes = 272 maximum-depth = 48)
(total-pushes = 304 maximum-depth = 53)

연습문제 5.26과는 다르게 maximum-depth가 계속 증가하는 양상을 보인다. total-pushes는 약간 작은 것 같지만, 그래도 1차 함수처럼 보인다. 손으로 약간 정리해보면,

max-depth = 5n+3

# of pushes = 32n-16

로 정리할 수 있다. 이를 가지고 위 표를 채워 넣었다. Recursive factorial 의 경우 공간/시간복잡도 모두 O(n) 이다.

Ex 5.28

Modify the definition of the evaluator by changing eval-sequence as described in section 5.4.2 so that the evaluator is no longer tail-recursive. Rerun your experiments from exercises 5.26 and 5.27 to demonstrate that both versions of the factorial procedure now require space that grows linearly with their input.

Ex 5.29

Monitor the stack operations in the tree-recursive Fibonacci computation:

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

a. Give a formula in terms of n for the maximum depth of the stack required to compute Fib(n) for n >= 2. Hint: In section 1.2.2 we argued that the space used by this process grows linearly with n.

n의 값을 1부터 12까지 증가시켜가며 print-statistics의 출력을 모아보았다. 역시 첫번째 줄은 함수 정의에서 나온 것으로 두번째 줄부터 시작이다.

(total-pushes = 3 maximum-depth = 3)
(total-pushes = 16 maximum-depth = 8)
(total-pushes = 72 maximum-depth = 13)
(total-pushes = 128 maximum-depth = 18)
(total-pushes = 240 maximum-depth = 23)
(total-pushes = 408 maximum-depth = 28)
(total-pushes = 688 maximum-depth = 33)
(total-pushes = 1136 maximum-depth = 38)
(total-pushes = 1864 maximum-depth = 43)
(total-pushes = 3040 maximum-depth = 48)
(total-pushes = 4944 maximum-depth = 53)
(total-pushes = 8024 maximum-depth = 58)
(total-pushes = 13008 maximum-depth = 63)

maximum-depth는 손쉽게 5씩 증가하는 1차 함수라는 것을 알 수 있다.

b. Give a formula for the total number of pushes used to compute Fib(n) for n >= 2. You should find that the number of pushes (which correlates well with the time used) grows exponentially with n. Hint: Let S(n) be the number of pushes used in computing Fib(n). You should be able to argue that there is a formula that expresses S(n) in terms of S(n - 1), S(n - 2), and some fixed ``overhead'' constant k that is independent of n. Give the formula, and say what k is. Then show that S(n) can be expressed as a Fib(n + 1) + b and give the values of a and b.

힌트에서 주어진대로 fib(n) 을 구하는데 필요한 # of stack pushes 를 S(n) 이라고 하자. fib(n) = fib(n-1) + fib(n-2) 이므로, 당연히 S(n)을 구하는 데에는 S(n-1)과 S(n-2)가 일단 더해지게 된다.

n	1	2	3	4	5	6	7	8	9	10	11	12
S(n)	16	72	128	240	408	688	1136	1864	3040	4944	8024	13008
S(n-1)+S(n-2)			88	200	368	648	1096	1824	3000	4904	7984	12968

이 표를 보면, 거의 자명하게

S(1) = 16
S(2) = 72
S(n) = S(n-1) + S(n-2) + 40 if n>=2

라는 점화식을 만들 수 있다. fib(n) 을 계산하는데 필요한 스택의 push 횟수 역시 피보나치 수를 따라가는 아름다움!

Ex 5.30

Our evaluator currently catches and signals only two kinds of errors – unknown expression types and unknown procedure types. Other errors will take us out of the evaluator read-eval-print loop. When we run the evaluator using the register-machine simulator, these errors are caught by the underlying Scheme system. This is analogous to the computer crashing when a user program makes an error.(footnote) It is a large project to make a real error system work, but it is well worth the effort to understand what is involved here.

a. Errors that occur in the evaluation process, such as an attempt to access an unbound variable, could be caught by changing the lookup operation to make it return a distinguished condition code, which cannot be a possible value of any user variable. The evaluator can test for this condition code and then do what is necessary to go to signal-error. Find all of the places in the evaluator where such a change is necessary and fix them. This is lots of work.

b. Much worse is the problem of handling errors that are signaled by applying primitive procedures, such as an attempt to divide by zero or an attempt to extract the car of a symbol. In a professionally written high-quality system, each primitive application is checked for safety as part of the primitive. For example, every call to car could first check that the argument is a pair. If the argument is not a pair, the application would return a distinguished condition code to the evaluator, which would then report the failure. We could arrange for this in our register-machine simulator by making each primitive procedure check for applicability and returning an appropriate distinguished condition code on failure. Then the primitive-apply code in the evaluator can check for the condition code and go to signal-error if necessary. Build this structure and make it work. This is a major project.

ssl:인증서_만들기 - [SSL]

dgoon — Fri, 12 Aug 2011 18:14:14 +0900

SSL

키 생성, 인증서, 어렵게 들리지만 시스템에 설치된 openssl로 그냥 생성할 수 있다. 별 것 없다. http://www.openssl.org/docs/HOWTO/ 여기 문서를 참고해서 정리한다. 거의 번역&요약 수준이다.

인증서는 공개 키 보안 시스템과 밀접하게 관련된다. 아마도 사전 지식이 있겠지만 공개 키 기반의 보안 시스템에서는 공개 키(Public key)와 개인 키(Private key), 이렇게 두 개의 키가 쌍으로 존재한다. 인증서는 이 중에서 개인 키 와 얽히게 된다.

인증서는 서명에 사용된 개인 키가 크고 훌륭한 믿을 만한 녀석들 의 것이라면 인증서도 믿을만 하다고 볼 수 있다. 이렇게 크고 훌륭한 인증서에 서명을 해주는 기관을 Certificate Authority(CA) 라고 하며, 이 기관들 순전히 인증서를 검토하고 괜찮아 보이면 자기들 개인 키로 서명을 해주고 돈을 받는 장사를 한다. 개인적인 용도나 테스트용도라면 이런 비싼 기관들을 통하지 않고 그냥 믿음직한 나 가 바로 서명을 해서 쓸 수도 있다. 물론, 다른 사람이 볼 때에도 믿음직한지에 대한 문제는 알아서 해결해야 한다.

돈을 내고 공인 기관으로부터 인증서를 받으려면, 인증서 요청 을 생성해서 CA 에게 보내야 한다. 자기가 직접 서명한 인증서 는 바로 생성할 수 있다. 아래의 커맨드는 모두 Debian squeeze/Ubuntu 10.04(LTS) 에서 openssl 패키지를 설치하면 가능하게 된다.

공인 인증기관으로부터 서명을 받는 경우라면, 내가 해본 적이 없으므로 더 찾아보고 프로세스를 알아내어 나에게 알려주면 좋겠다.

Generate certificate request

openssl req -new -key private.pem -out cert.csr

그리고 몇 개의 추가 정보를 입력하면 된다. 인증서 요청과 연결될 나의 개인 키는 private.pem, 그리고 서명해주세요~ 라고 보낼 인증서 요청 파일이 cert.csr 이다.

검색해보면 쉽게 찾을 수 있지만, 귀찮은 사람을 위해 간단하게 확장자를 설명하면,

PEM: Privacy Enhanced Mail - 인증서 내용을 base64 로 인코딩한 것이다. 시작과 끝 줄이 각각 —–BEGIN CERTIFICATE REQUEST—–, —–END CERTIFICATE REQUEST—– 로 표시된다
CSR: Certificate Signing Request 의 약자

인증서 포맷으로는 PEM 이외에도 DER, CER 등이 있다. 궁금하면 찾아보면 된다. 혹 다른 포맷의 키가 필요한 경우 openssl 이 변환도 해 준다. 필요하면 검색해본다. 어? 그런데 난 아직 개인키가 없는데 … … 라는 사람을 위해 잠시 키 생성을 돌아보자.

Generate private key

개인 키는 두 가지가 있다. RSA, DSA 중 하나를 용도에 맞게 고른다. … 그냥 RSA로 하기를 추천한다. 간단하게 RSA 키는 인증/암호화 둘 모두 할 수 있고, DSA 키는 인증-즉, 서명-에만 사용한다고 참고한 HOWTO 에 쓰여 있었다.

RSA Key

openssl genrsa

이렇게 실행하면 화면으로 512 bit RSA 개인 키를 PEM 형식으로 내보낸다.

openssl genrsa 1024 -out private.pem

이렇게 실행하면 1024 bit RSA key를 private.pem 이라는 파일에 쓴다. 위 인증서 생성을 위한건 이걸로 충분하다.

DSA Key

opessl gendsa 만으로는 생성이 되지 않는다. 어떤 파라미터 파일을 필요로 한다는데, 무엇인지 잘은 모르지만 DSA를 위한 파라미터 파일 생성도 openssl 로 할 수 있다.

openssl dsaparam -out dsaparam.pem -genkey 1024
openssl gendsa -out dsa_private.pem dsaparam.pem

이렇게 하면 된다. DSA 키로도 인증서는 생성할 수 있다.

Generate self-signed certificate

뭐 CA까지 갈 게 있나. 테스트 혹은 개인적인 용도로 쓸 인증서라면 자기가 서명해도 된다. 위의 인증서 요청 생성 명령에서 -x509(포맷 지정)과 -days 옵션을(만료기간) 추가하면 된다.

openssl req -new -x509 -key private.pem -out cert.pem -days 1095

공인인증기관에 갈 때는 이렇게 하면 안되겠지만, 물어보는거 일일일 답하거나 엔터 누르기 귀찮으면 뒤에 -batch 를 붙여넣으면 귀찮게 물어보지 않는다. 내가 서명할 거니까 이렇게 스루해도 된다. 이 경우 위의 CSR 과는 달리 —–BEGIN CERTIFICATE—–, —–END CERTIFICATE—– 이렇게 쓰여 있다. REQUEST 가 사라져 있지!

Verify

이렇게 만든 키/인증서들의 내용을 보는 명령은 아래와 같다. ~~하지만 봐도 모른다.~~

openssl x509 -noout -text -in cert.pem
openssl rsa -noout -text -in private.pem
openssl dsa -noout -text -in dsa_private.pem

python:sampleechoserv - 새로 만듦

dgoon — Fri, 12 Aug 2011 18:13:06 +0900

SSL

SSL로 간단하게 메시지를 주고 받는 샘플 코드를 만들어둔다. 이를 위해서는 개인 키(private.pem)와 인증서(cert.pem)가 필요한데, 이미 준비 되었다고 가정한다. 혹시 없다면, 인증서 만들기 를 참고해서 만들면 된다. 여기(http://docs.python.org/library/ssl.html)에 있는 샘플 코드의 Copy&Paste 및 정리이므로 영어가 된다면 저 문서를 읽는게 훨씬 낫다.

키 생성까지 포함해서 http://git.dgoon.net/?p=codesnippets.git;a=tree;f=ssl_wrap 여기에 커밋되어 있다.

퍼포먼스, 스레딩 등은 전혀 고려되지 않은 샘플 코드 조각이므로 위험한 사용은 금할 것.

Echo Server

#-*- encoding: utf-8 -*-

import sys, os, socket, ssl

if '__main__' == __name__:
    host, port = 'localhost', 9999
    if 1 < len(sys.argv): host = sys.argv[1]
    if 2 < len(sys.argv): port = int(sys.argv[2])

    if not (os.path.exists('./cert.pem') and os.path.exists('./private.pem')):
    	print('cert.pem and private.pem should be prepared.')
    	sys.exit(1)

    print('Bind to %s:%d' % (host, port))

    bindsocket = socket.socket()
    bindsocket.bind((host, port))
    bindsocket.listen(5)

    while True:
        sock, fromaddr = bindsocket.accept()

        try:
            conn = ssl.wrap_socket(sock,
                                   server_side=True,
                                   certfile="cert.pem",
                                   keyfile="private.pem",
                                   ssl_version=ssl.PROTOCOL_TLSv1)
            data = conn.read()
            conn.write(data)
            conn.close()
        except:
            pass

Client

#-*- encoding: utf-8 -*-
import sys, socket, ssl, pprint

if '__main__' == __name__:
	if 3 > len(sys.argv):
		print('Usage: %s HOST PORT Messages...' % sys.argv[0])
		sys.exit(1)
	host, port = sys.argv[1:3]
	port = int(port)
	msg = ' '.join(sys.argv[3:]) or 'TEST'

	sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	ssl_sock = ssl.wrap_socket(sock)
	ssl_sock.connect((host, port))

	print("Send << %s" % msg)
	ssl_sock.write(msg)
	recv_msg = ssl_sock.read()
	print("Recv >> %s" % recv_msg)

	ssl_sock.close()