D-Goon's Doc

htdp:chapter_6 - [Compound]

dgoon — Fri, 17 Feb 2012 00:02:54 +0900

HTDP

Chapter 6

Code

http://git.dgoon.net/?p=kata.git;a=tree;f=HTDP/chapter-06

python:requests

dgoon — Thu, 09 Feb 2012 16:05:36 +0900

Requests는 파이썬으로 쓰인 HTTP 라이브러리이다. 관련 페이지는 http://docs.python-requests.org/en/latest/index.html 여기에 있다. 파이썬 빌트인 httplib, urllib 보다 사용하기 쉬우며, gevent(http://www.gevent.org/)가 설치된 경우 비동기 동작을 할 수 있다. requests, gevent 모두 pip(http://pypi.python.org/pypi/pip)로 설치할 수 있다.

Basic GET

기본적인 사용법은 아주 간단하다. GET메소드로 주어진 URL을 가지고 오는 것은,

import requests
r = requests.get(URL)

이렇게 끝난다. 예를 들어, http://cfs7.tistory.com/upload_control/download.blog?fhandle=YmxvZzUzNDk3QGZzNy50aXN0b3J5LmNvbTovYXR0YWNoLzAvMDcwMDAwMDAwMDAwLnBuZw%3D%3D 이 이미지를 저장한다고 하면,

import requests
URL="http://cfs7.tistory.com/upload_control/download.blog?fhandle=YmxvZzUzNDk3QGZzNy50aXN0b3J5LmNvbTovYXR0YWNoLzAvMDcwMDAwMDAwMDAwLnBuZw%3D%3D"
r = requests.get(URL)
with open("test.png", "wb") as f:
    f.write(r.content)

이렇게 하면 된다. 응답을 들고 있는 객체 r 에서 r.text, r.content, r.headers, r.status_code 등의 값을 사용할 수 있다. 요청에 대해서 타임아웃을 주고 싶을 때에는 get 메소드에 timeout=0.01 처럼 초 단위로 타임아웃을 지정해 줄 수 있다.

worklog - [삽질기록]

dgoon — Thu, 09 Feb 2012 14:11:32 +0900

Work log

디군의 잡다한 작업/스터디/발표 기록들. 잊기 전에 정리하자 - 정신으로 쓰여진 날림 문서들이다. ~~일종의 Tools and Tips 라고 볼수도…~~ 최소한 하나의 페이지 정도를 요구하는 삽질의 기록.

삽질기록

TRAC+SVN+SSL 설정
HowToMakeADebianPackage - Getting started
SSH 터널링 - 가끔 정말 유용하게 쓰인다
InstallRedmine - 레드마인 설치부터 디플로이까지
config - 클로져
dwiki
MergeVideoFiles
StockInfo
CaptureDVB
FFMpeg0.8API
WebInPython
Python에서 MySQL에 접근하기
lxml - Handle XML document in python
파이썬 데코레이터:살짝 들여다보기
파일 정보 읽기
파이썬 유닛테스트 간단한 입문
Time<->String
Profiling
초 간단한 위챗 봇 만들기 입문
binding - Python-C/C++ 바인딩
ssl - SSL 위에서 통신하기
requests

발표기록

LaTeX - 정말정말 심플한 LaTeX 시작하기 @ SICP Studygroup 6월모임(2008) 발표
Map/Reduce 초간단발표 @ SICP Studygroup 9월모임(2008) 발표
DHT/Chord

private:책목록 - [비문학]

dgoon — Sat, 29 Oct 2011 14:32:58 +0900

디군의 책 리스트

별도의 관리 툴을 만들기 전까지, 일단 목록이라도 있어야 할 것 같아서 정리. 전공서적의 경우 번역서는 별도 표시, 그 외의 경우는 원서를 별도 표기. 둘 다 있는 경우는 둘다 써서 구분. 원서는 가능한 경우 제목도 해당 언어로.

- 상자에서 안꺼낸 책들 어쩔꺼야 ㅠㅠ

전공

TAOCP Vol.1
TAOCP Vol.2
TAOCP Vol.3
TAOCP Fascicles 0, 1, 2, 3, 4 of Vol.4
Concrete mathematics
SICP
Beyond the C++ Standard Library
C++ Standard library
Data Mining
Artificial Intelligence
유닉스 시스템 프로그래밍 SVR 4(번역)
실용주의 프로그래머
이펙티브 STL
Pro Android 2 (EBOOK)
Agile Web Development with Rails (EBOOK)
Programming Erlang (EBOOK)
Programming in Clojure (EBOOK)
프로토타이핑
프로그램 디자인 어떻게 할 것인가

CS 관련(?) 비전공

사랑하지 않으면 떠나라
고약한 문제, 합당한 해결
G.E.B. (원서)

문학

파우스트 1/2
기형도 전집
이상한 나라의 앨리스
거울 나라의 앨리스
時をかける少女(시간을 달리는 소녀) (원서)
꿈꾸는 책들의 도시 1/2
폐도 1/2/3
아서 클라크 단편 전집
미인계
천개의 찬란한 태양
눈먼 자들의 도시
한 권으로 읽는 잃어버린 시간을 찾아서
차라투스트라는 이렇게 말했다
전도서에 바치는 장미
키리냐가
지식의 역사
지식의 단련법
성의 패러독스

비문학

전략의 탄생
한용운의 채근담 강의
Lewis Carol and Alice
듀이 (clover3leaf → 디군 → 하프리)
The Secret
이기주의를 위한 변명
교과서가 죽인 책들
여행의 기술
함께 읽으면 즐겁습니다
러셀의 행복론
나는 왜 기독교인이 아닌가
게으름에 대한 찬양
파인만의 또 다른 물리학 강의
워킹 푸어, 빈곤의 경계에서 말하다
정의란 무엇인가
최초의 신화 길가메쉬 서사시
소크라테스의 변명
공부는 내 인생에 대한 예의다
홀가분
지식의 단련법

NT류

공의 경계 상/중/하 (원서)
공의 경계 상/하 (번역)
하루카 천공의 야마타이국
하루카 염천의 야마타이국 (완결)
잘린머리 사이클
목조르는 로맨티스트
목매다는 하이스쿨
사이코로지컬 상/하

만화

3月のライオン 1~5 (원서)
3월의 라이온 1~5 (번역)
카페알파 전권(1~14) (번역)
허니와 클로버 전권(0~10) (번역)
마이걸 1~3 (번역)
Nabi 1~8
Nabi 단편집
Fly
맑은 봄빛 사랑 이야기 - 모모네
별의 목소리
버스 달리다
멸망한 짐승들의 바다
블루홀 1/2
문로스트 1/2
소용돌디 1~3
예스터데이를 노래하며 1~7 (번역)
Tom Sawyer (번역)
신부 이야기 1,2 (번역)
치키타 구구 1~8 (번역)
문화 콘텐츠의 이해
마니마니
붉은 딸기 흰 딸기
진격의 거인 1,2,3,4 (번역)
토끼 드롭스 1~6
스트로보라이트

예술

강병규 지리산 사진집
연필 하나로 시작하는 스케치 연습장
Life & Nature - 내셔널 지오그래픽전 대도록

sicp:exercise_ch5.4 - [Ex 5.30]

dgoon — Tue, 04 Oct 2011 21:07:19 +0900

SICP

Exercises on Chapter 5.4

Ex 5.23

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.