. Fortran
. recursive call이 불가능하다.
. caller : 함수를 부르는 측
. callee : 불린 측
. In-line block
. function, procedure와 달리 block내에 block이 있어서 자연스럽게 그 block이 수행됨.
. most simple block(가장 단순한 형태의 block)
. Nested function declaration
. function내에서 function을 선언하는 것
. C, C++에서는 지원하지 않는 다.
(C++에서 Nested class는 지원함)
. Block
. begin, end marker로 표시되는 프로그램 조각(a region of program text)
. block의 시작마다 variable declaration이 있다.
Memory allocation도 한다.
. block의 끝마다 local variable을 없애고 memory를 deallocation시켜 memory를 아낀다.
. nesting되야하고 partially overlap은 안된다.
(if, for 등 모든 것들이 그렇다.)
. 각 block은 Activation Record를 가진다.
. block의 종류
. In-line block
. function
. procedure
. scope : 변수가 visible한 영역
. lifetime : 변수의 수명(allocation에서 deallocation사이)
. scope와 lifetime은 약간 다르다.
. a hole in the scope
. lifetime이 expire되지 않았지만 scope상에서 가려져서 visbiel하지 않음.
. variable
. local variable : 현재 block내에 선언됨
. global variable : 현재 block 바깥에 선언됨
. global variable은 항상 어떤 block의 local variable이다.
. scoping
. global variable의 위치를 결정하는 문제
. static scoping
. 가장 가까운 block의 variable을 이용
. Access Link를 따라가서 변수를 찾음.
. Access link를 몇 단계 따라갈지는 compiler가 정해줌.
. 최근 언어들이 채택하고 있음.
. dynamic scoping
. 가장 가까운 AR의 variable을 이용.
. runtime에 일일히 stack frame을 뒤져 variable이 있는 지 확인함.
. LISP이 채택한 방식
. AR(Activation Record, Stack frame)의 구성요소
. Control link(CL)
. Access link(AL)
. Return address(RA)
. Return value address(RVA)
. Parameter
. local variable
. Intermediate result(Temporary storage)
. 그 외의 구성요소
. Program Counter(PC)
. Environment Pointer(EP)
. Stack Pointer(SP)
. Control Link = Dynamic link
. stack frame의 previous frame을 가리킨다.
. Access Link = static link
. parent block을 가리킨다.
. parent가 recursive call이었을 때는 가장 최근의 parent를 가리킨다.
. (lexical scope에 따라 가리킨다.)
. C는 nested function declaration이 안되므로 AL이 필요없다.
(AL이 모두 global scope을 가리킬 것이므로)
. 예상 시험문제 : 다음 프로그램을 보고 CL, AL 등을 연결하세요.
. Return address
. call이 끝나면 돌아갈 주소(caller의 주소)
. Return value address
. return시 value을 넣어 줄 곳
. Parameter
. caller로 부터 넘어온 value
. Intermediate result
. compiler가 복잡한 expression의 중간 결과를 임의로 저장한 것.
. temporary value를 저장한다.
. Program Counter(PC)
. 현재 code상에서 어느 줄을 수행하고 있는 지 나타낸다.
. environment pointer(frame pointer, EP, FP)
. current stack(run-time stack), 새 activation record(AR)을 가리킨다.
. 항상 index register에 넣어두기로 약속했다.
. stack pointer(SP)
. stack의 top을 가리킴
. 사실 stack은 linked list처럼 생겼다.
. previous node에 해당하는 것을 control link가 가지고 있다.
. 그럼 왜 linked list가 아닌 stack이라는 이름으로 부를까?
. linked list는 중간 원소를 없애거나 추가하기도 하지만
. stack은 항상 top에서만 추가, 삭제를 한다.(LIFO)
. 따라서 우리의 경우에는 top만 바꾸므로 stack으로 구현한다.
. 새 stack을 allocation(push)하는 instruction
. M(SP) <- EP
. EP <- SP
. SP <- SP + sizeof(AR)
. stack을 deallocation(pop)하는 instruction
. SP <- EP
. EP <- M(EP)
. Parameter passing
. formal parameter
. declaration시 자리를 차지하는 것(place holder)
. actual parameter
. function call시 쓰이는 expression
. call-by-value
. actual parameter를 evaluation 한 후 r-value(value, contents fo address)를 복사한다.
. Object가 클 때 비효율(inefficient)적이다.
. call-by-reference
. variable의 l-value(memory address)를 넘긴다.
. object가 아주 작을 때(fit directly on stack) 비효율적이다.
. 문제점 - parameter가 constant이거나 expression이면 이상해 진다.
. aliasing이 생겨서 분석이 어렵다.
. 해결책
1. call-by-reference를 안쓴다.
2. 그냥 내버려둔다. (User의 책임이다.)
3. PL을 잘 design하여 compiler시 error를 낸다.
. Aliasing
. 2개 이상의 name이 같은 object나 location을 가리킬 때
. Compiler의 중요한 임무
. variable의 위치를 알아야 함.
. 위치 : 어느 block(which block)인가 + 몇 번째인가(dispx, displacement x)
. caller가 할 일(AR 만들기)
1. EP를 새 AR로 set
2. RA set(자신의 현재 PC)
. callee의 RA 위치 : EP + sizeof(caller's AR) + 2
3. Actual parameter set
. Actual parameter와 formal parameter의 순서는 동일하다.
4. callee로 jump
. EP + sizeof(AR) = SP
. AR의 위치가 고정적인 이유
. 그렇게 해야 caller가 callee를 부르고 여러 값들을 정확하게 넘길 수 있다.
. CL, AL, RA, RVA, parameter의 크기는 고정적이고 compiler가 알아낼 수 있다.
(caller가 아는 것들, 알아야 되는 것들)
. 그 다음에 local variable, temporary 등 caller가 몰라도 되는 것을 적는 다.
. function and procedure(공통점과 차이점)
. function : value를 return한다.(expression이다.)
. procedure : value를 return하지 않는 다.(statement이다.)
. 공통점 : side effect가 있다.
. 거의 비슷하므로 대충 쓰기로 한다.
. Tail call
. Return시 부른 function의 값을 바꾸지 않고 return하는 것
(without any further computation)
. Tail recursive call
. 자기 자신을 tail call하는 것
. Optimization
. set return value address to that of caller
. control link도 더 위로 돌리자.
. 결국 caller는 자신의 AR을 pop하고 overwrite하면 된다.
. conclusion : iteravion loop와 같아 진다.
. Recursive call은 iterative로 바꿀 수 있지만 쉽지 않다.
하지만 tail recursive call의 경우는 automatic하게 할 수 있다.
. AL 결정하기
. caller가 형제 block을 call할 때는 자신의 Al를 callee의 AL에도 적는 다.
. in-line block일 때는 AL과 CL이 같다.
. 삼촌을 부를 때는 아버지의 AL을 set한다.
. 아버지, 할아버지, 삼촌 이런 정보는 static structure이므로 compiler가 모두 안다.
. first-class function
. http://en.wikipedia.org/wiki/Closure_%28computer_science%29
. declared within any scope
. passed as arguments to other functions
. stored in data structures
. returned as the values of other functions
. functional programming을 구현하기 위해 필요하다.
. higher-order function을 구현하기 위해 필요하다.
. closure
. http://en.wikipedia.org/wiki/Closure_%28computer_science%29
. a function created by a program at run time
. (env, code) : activation record와 function code를 가리킨다.
. function을 넘길 때 closure로 넘긴다.
. C언어에서는 nested function declaration이 안되므로 closure가 필요없다.
. downward funarg problem
. function argument로 function을 넘길 때
. closure로 해결된다.
. 다행히도 가리키는 Access Link는 항상 stack의 윗쪽을 향하므로 별 문제가 안된다.
. upward funarg problem
. = upward fun-result problem
. function의 return value로 function을 넘길 때
. closure를 써야하고 stack도 바꿔야 한다.
. stack discipline fails
. Garbage collection
. Stack discipline이 깨지면 explicit deallocation이 힘들다.
. 쓰이는 지, 안 쓰이는 지 garbage collection으로 판단한다.
. Lisp, Scheme은 nested function declaration, higher-order function 때문에 garbage colection이 거의 필수이지는 C는 그렇지 않다.
. Language feature와 implementation construct의 관계
. Block - Activation record with local memory
. Nested blocks - Control link
. functions and procedures - return address, return-result address
. function with static scope - access link
. function as arguments and results - closures
. functions returned from nested scope - failure of stack deallocation order for activation records
