5장. 레지스터 머신으로 계산
- CODE 코드 : 컴퓨터 하드웨어와 소프트웨어에 숨어 있는 언어
- Code: The Hidden Language of Computer Hardware and Software
- fact설명
ch5-regsim 커스텀 기계 코드를 정의하고, label 과 register를 가진 실행 머신을 만듬
stack이 레지스터 별로가 아니라 통합이라서 save/restore순서 주의
슬금 슬금 머신 코드를 보여주다가 인터프리터를 돌 릴 수 있는 머신 코드가 나옴
instruction label pc flag stack - save / restore
5.1에서 controller로 의사코드를 보여주면서
5.2에서 make-machine으로 머신을 만들어 구동 load-eceval 파일은 SICP 5.4절에서 정의된 **명시적 제어 평가기(ECEval)**를 로드합니다. ECEval은 Scheme 프로그램을 해석(interpret)하는 인터프리터로, Scheme 코드를 직접 실행할 수 있도록 설계된 가상 머신입니다.
load-eceval-compiler SICP 5.5절에서 다루는 컴파일러와 연동된 ECEval을 로드합니다. 즉, Scheme 코드를 컴파일하여 기계어 수준의 명령어로 변환한 뒤, 이를 ECEval에서 실행할 수 있도록 지원합니다.
eceval - EXPLICIT-CONTROL EVALUATOR FROM SECTION 5.4
TODO
- Computing with Register Machines
- 5장은, 레지스터 머신과 가비지 컬렉터 그리고 컴파일러를 구현한다.
- 레지스터 기계로 계산하기
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
| data path | 레지스터 + 연산 |
| controller | 연산 순서 |
| 네모 | 레지스터 |
| 세모 | 상수 |
| 사다리꼴 | 연산 |
| 원 | 검사 |
a <- b: a에 b값을 덮어쓰기
(data-paths
(registers
((name a)
(buttons ((name a<-b)
(source (register b)))))
((name b)
(buttons ((name b<-t)
(source (register t)))))
((name t)
(buttons ((name t<-r)
(source (operation rem))))))
(operations
((name rem)
(inputs (register a) (register b)))
((name =)
(inputs (register b) (constant 0)))))
(controller
test-b ; label
(test =) ; test
(branch
(label gcd-done)) ; conditional branch
(t<-r) ; button push
(a<-b) ; button push
(b<-t) ; button push
(goto
(label test-b)) ; unconditional branch
gcd-done) ; label
5.1 레지스터 기계 설계하기 5.1.1 레지스터 기계를 묘사하는 언어 5.1.2 기계 디자인에서의 속 내용 감추기(abstraction) 5.1.3 서브루틴
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
;;FIGURE 5.11
(controller
(assign continue (label fact-done)) ; set up final return address
fact-loop
(test (op =) (reg n) (const 1))
(branch
(label base-case))
;; Set up for the recursive call by saving n and continue.
;; Set up continue so that the computation will continue
;; at after-fact when the subroutine returns.
(save continue)
(save n)
(assign n (op -) (reg n) (const 1))
(assign continue
(label after-fact))
(goto
(label fact-loop))
after-fact
(restore n)
(restore continue)
(assign val (op *) (reg n) (reg val)) ; val now contains n(n-1)!
(goto (reg continue)) ; return to caller
base-case
(assign val (const 1)) ; base case: 1!=1
(goto (reg continue)) ; return to caller
fact-done)
** 5.1.4 스택(stack)을 이용해 되돌기(recursion) 구현하기
5.1.5 명령어 정리
5.2 레지스터 기계 시뮬레이터
(define gcd-machine
(make-machine
;; 레지스터 목록
'(a b t)
;; 연산 목록
(list (list 'rem remainder) (list '= =))
;; 컨트롤러
'(test-b
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done)))
(set-register-contents! gcd-machine 'a 206)
(set-register-contents! gcd-machine 'b 40)
(start gcd-machine)
(get-register-contents gcd-machine 'a)
5.2.1 기계 모형 5.2.2 어셈블러 5.2.3 명령에 해당하는 실행 프로시저 만들기
eval/analyze같은 존재 make-execution-procedure
연습문제 5.11 c) **
5.2.4 기계 성능 지켜보기
연습문제 5.17 ** 명령어 바로 앞에 오는 레이블을 출력하 연습문제 5.19 ** breakpoint 구현
5.3 메모리 할당(memory allocation)과 재활용(garbage collection) 5.3.1 벡터로 나타낸 메모리 5.3.2 무한히 많은 메모리인 양 보이기 ?
;; 2장에서 enumerate-interval / filter / accumulate
(define (enumerate-interval low high)
(if (> low high)
nil
(cons low (enumerate-interval (+ low 1) high))))
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(accumulate + 0 (filter odd? (enumerate-interval 0 n)))
계산이 끝나면 enumerate-interval랑 filter로 생성된 리스트는 의미가 없음.
- stop-and-copy
- memory
- working memory
- free memory
- memory
- working memory : 현재 작업 메모리
the-cars[]
the-cdrs[]
- free memory : 여유 메모리
new-cars[]
new-cdrs[]
free - 그림5.14 / 연습문제5.20 에서 다음에 객체(쌍)를 할당할 위치를 가리키는 포인터(index).
할당할때마다 free증가
scan - 새 메모리에서 현재 스캔 중인 쌍의 위치를 가리키는 포인터(index).
gc-loop 루프를 돌며 scan은 free와 같아질때까지 재배치된걸 검색
root - 가비지 컬렉션이 시작되면 root가 가리키는 객체를 새 메모리로 재배치하고, 재배치된 새 위치로 root를 업데이트
이 레지스터는 프로그램이 접근할 수 있는 모든 데이터의 진입점 역할
new - 재배치된 객체의 새 메모리 위치를 저장하는 레지스터.
old - 재배치할 객체의 이전 메모리 위치를 가리키는 포인터
relocate-continue - lable 저장용
메모리 재활용 시점:
- working memory를 다 썼을 시(cons연산이 메모리 벡터끝을 넘어서 free 포인터를 증가시키려 할때)
begin-garbage-collection ; def begin-garbage-collection
(assign free (const 0)) ; free = 0
(assign scan (const 0)) ; scan = 0
(assign old (reg root)) ; old = root
(assign relocate-continue (label reassign-root)) ; relocate-continue = <reassign-root>
(goto (label relocate-old-result-in-new)) ; return <relocate-old-result-in-new>
reassign-root ; def reassign-root
(assign root (reg new)) ; root = new
(goto (label gc-loop)) ; return <gc-loop>
gc-loop ; def gc-loop
(test (op =) (reg scan) (reg free)) ; if (scan == free)
(branch (label gc-flip)) ; return <gc-flip>
(assign old (op vector-ref) (reg new-cars) (reg scan)) ; old = new-cars[scan]
(assign relocate-continue (label update-car)) ; relocate-continue = <update-car>
(goto (label relocate-old-result-in-new)) ; return <relocate-old-result-in-new>
update-car ; def update-car
(perform (op vector-set!) (reg new-cars) (reg scan) (reg new)) ; new-cars[scan] = new
(assign old (op vector-ref) (reg new-cdrs) (reg scan)) ; old = new-cdrs[scan]
(assign relocate-continue (label update-cdr)) ; relocate-continue = <update-cdr>
(goto (label relocate-old-result-in-new)) ; return <relocate-old-result-in-new>
update-cdr ; def update-cdr
(perform (op vector-set!) (reg new-cdrs) (reg scan) (reg new)) ; new-cdrs[scan] = new
(assign scan (op +) (reg scan) (const 1)) ; scan = scan + 1
(goto (label gc-loop)) ; return <gc-loop>
relocate-old-result-in-new ; def relocate-old-result-in-new
(test (op pointer-to-pair?) (reg old)) ; if (pointer-to-pair? old)
(branch (label pair)) ; return <pair>
(assign new (reg old)) ; new = old
(goto (reg relocate-continue)) ; return (relocate-continue)
pair ; def pair
(assign oldcr (op vector-ref) (reg the-cars) (reg old)) ; oldcr = the-cars[old]
(test (op broken-heart?) (reg oldcr)) ; if (broken-heart? oldcr)
(branch (label already-moved)) ; return <already-moved>
(assign new (reg free)) ;new location for pair ; new = free
(assign free (op +) (reg free) (const 1)) ; free = free + 1
(perform (op vector-set!) (reg new-cars) (reg new) (reg oldcr)) ; new-cars[new] = oldcr
(assign oldcr (op vector-ref) (reg the-cdrs) (reg old)) ; oldcr = the-cdrs[old]
(perform (op vector-set!) (reg new-cdrs) (reg new) (reg oldcr)) ; new-cdrs[new] = oldcr
(perform (op vector-set!) (reg the-cars) (reg old) (const broken-heart)) ; the-cars[old] = 'broken-heart
(perform (op vector-set!) (reg the-cdrs) (reg old) (reg new)) ; the-cdrs[old] = new
(goto (reg relocate-continue)) ; return (relocate-continue)
already-moved ; def already-moved
(assign new (op vector-ref) (reg the-cdrs) (reg old)) ; new = the-cdrs[old]
(goto (reg relocate-continue)) ; return (relocate-continue)
gc-flip ; def gc-flip
(assign temp (reg the-cdrs)) ; swap(the-cdrs, new-cdrs)
(assign the-cdrs (reg new-cdrs)) ; ..
(assign new-cdrs (reg temp)) ; ..
(assign temp (reg the-cars)) ; swap(the-cars, new-cars)
(assign the-cars (reg new-cars)) ; ..
(assign new-cars (reg temp)) ; ..
5.4 제어가 다 보이는 실행기 5.4.1 제어가 다 보이는 실행기의 핵심부 5.4.2 시퀀스 계산과 꼬리 되돌기(tail recursion) 5.4.3 조건 식, 덮어쓰기(assignment), 정의
연습문제 5.24 ** if로 변환하지 않고 cond구현. 연습문제 5.25 ** normal-order evaluation 구현.
5.4.4 실행기 돌리기
5.5 번역(compilation) 5.5.1 번역기의 구조 5.5.2 프로그램 식의 번역 5.5.3 조합 식 번역하기 5.5.4 명령줄 한데 합치기 5.5.5 번역된 코드의 예 5.5.6 텍스트에서 변수의 정의를 파악하기(lexical addressing) 5.5.7 번역된 코드를 실행기에 연결하기
(reg ⟨register-name⟩) or (const ⟨constant-value⟩). These instructions were introduced in 5.1.1:
(assign ⟨register-name⟩ (reg ⟨register-name⟩))
(assign ⟨register-name⟩
(const ⟨constant-value⟩))
(assign ⟨register-name⟩
(op ⟨operation-name⟩)
⟨input₁⟩ … ⟨inputₙ⟩)
(perform (op ⟨operation-name⟩)
⟨input₁⟩
…
⟨inputₙ⟩)
(test (op ⟨operation-name⟩)
⟨input₁⟩
…
⟨inputₙ⟩)
(branch (label ⟨label-name⟩))
(goto (label ⟨label-name⟩))
The use of registers to hold labels was introduced in 5.1.3:
(assign ⟨register-name⟩ (label ⟨label-name⟩))
(goto (reg ⟨register-name⟩))
Instructions to use the stack were introduced in 5.1.4:
(save ⟨register-name⟩)
(restore ⟨register-name⟩)
The only kind of ⟨constant-value⟩ we have seen so far is a number, but later we will use strings, symbols, and lists. For example,
(const "abc") is the string "abc",
(const abc) is the symbol abc,
(const (a b c)) is the list (a b c),
and (const ()) is the empty list.
(make-machine ⟨register-names⟩
⟨operations⟩
⟨controller⟩)
(set-register-contents! ⟨machine-model⟩
⟨register-name⟩
⟨value⟩)
(get-register-contents ⟨machine-model⟩
⟨register-name⟩)
(start ⟨machine-model⟩)