* Sub Program 구현 방향
- 서브프로그램이 "Linkage(연계=call과 return)"에 대한 것이 원할하게 이뤄지게 구현해야한다.
* 최초의 Sub-Program을 지원한 FORTRAN 77(Passing Method:Call by Reference)
- FORTRAN77은 Sub-Program을 지원하기 위해서 다음의 과정을 밟았다.
ⓐ 서브프로그램을 실행하기 위해서는 함수를 호출하는(call)과 서브프로그램이 종료되어
되돌려 받는(return)이라는 2가지 step이 존재하는 것을 알게되었다.
ⓑ 각각 Step에서는 다음과 같은 순서로 세분화 된다.
1) Call step
① 호출하는 자신(caller)은 자신의 현 상태를 저장한다.
② 호출과 동시에 Parameter passing은 어떻게하느냐에 따라 다르게 진행된다.
③ return시 되돌아가야할 주소의 위치를 저장한다.
④ 위 과정이 모두 완료되면 callee에게 제어권을 인수한다.
2) Return step
① 변화된 파라미터의 값을 전달해주어야 한다.
(Parameter Passing Method : Pass by value-result와 Pass by result 일때)
② 만약, 서브프로그램이 프로시져가아닌 함수라면 함수의 결과값을 전달해주어야 한다.
③ caller의 상태를 복구해야한다.
④ caller에게 제어권을 인수한다.
ⓒ 각각의 스탭을 살펴본 결과 빨간 글씨를 저장할 필요가 생겼다. 이로 인해 활성화 레코드가 탄생한다.
※ Activation Record(활성화 레코드)
- caller와 callee는 정해진 양식을 통해서 서로 정보를 교환하는데,
그 교환이 되는 매개체, 양식(다른말로 Layout)을 활성화레코드라고 한다.
- FORTRAN에서의 activation record
- 포트란77에서는 하나의 subProgram은 단 하나의 activation record instance를 가진다.
> 이 말은, 자바에서 하나의 클래스는 단 하나의 객체만 만들수 있다는 것과 같은 말로
Activation Record의 위치를 컴파일시 Static하게 저장한다는 것이다.
(컴파일시 인스턴스는 위 그림에서 제공되는 것처럼 2가지 방법중 하나로 하여 생성할 것이다.)
> 재귀적 호출 불가능!
* ALGOL의 Sub-Program지원 방식ⓐ
- ALGOL은 포트란과의 언어적 차이점을 가지고 있다.
ⓐ Parameter Passing Method가 2가지라는 것(Call by reference, Call by value)
ⓑ 지역 변수를 Dynamic하게 할당과 반납을 해준다는 것
ⓒ 재귀적 호출이 가능해야 한다는 것
ⓓ Static Scope방식을 따른다는 것
- ALGOL에서의 Activation Record Design
※ Static Link
- 자신의 정적부모의 Activation Record의 바닥
> ⓓ번의 문제해결을 위해서(Scope문제)
※ Dynamic Link
- 자신을 부른 호출자의 Activation Record의 상단
> ⓒ번의 문제해결을 위해서(재귀적 호출가능)
- 상단에는 함수 값이 있어 바로 연계가 가능
※ Dynamic chain(call chain)
- 호출의 순서를 담고 있는 별도 저장공간
- 위의 Activation Record에서 특정 서브프로그램의 로컬변수를 지정하는 방법
> 모든 Sub-Program의 Activation Record는 기본적으로 3가지의 정보를 가지고 있다.
(Return Address, Static Link, Dynamic Link) : 편의상 각각 1Byte씩 차지한다고 생각하자.
> 자신이 받거나 넘기는 Parameter의 개수도 알고 있다.
> 위의 두가지 사실을 이용하면 Local variable의 시작 변수 위치를 참조 할수 있다
= Activation Record의 시작주소+ 3(기본적인 정보) + 파라미터의 개수
예 )
* ALGOL의 Sub-Program지원 방식 : 변수가 나의 Local에 없는 경우
- 이 경우 다음과 같은 과정을 따른다.
ⓐ 정확한 activation record instance를 찾는다.
ⓑ 그 위치에서의 local변수를 찾는다. => 위에 나온 방식대로 "시작주소 + 3 + parameter개수" 로 구한다.
- 위 과정에서 ⓐ를 해결하는데 문제가 발생한다. 알골의 프로그램에서는 실행할 서브프로그램을 프로그램 안에
구현하므로 자신이 찾으련느 변수는 상위 scope에 존재함을 가정으로 한다. 다음의 방식으로 구현을 한다.
ⓐ Static Chains : Static Link를 묶어 놓은 것.
ⓑ Display
※ display 방식은 비용대비 효과가 낮아 사용도가 낮다. 거의 소멸된 상태이다.
* Static Chains
- main이 a를 호출시 a의 static link는 main이다. 이를 이용하여 자신의 모든 정적 조상을 찾을 수 있다.
(알골의 프로그램에서는 실행할 서브프로그램을 프로그램 안에 구현하므로 )
- static chains : (chain_offset, local_offset)
> static_depth : sup Program이 얼마나 main에서 중첩되어 있는가?
> chain_offset(=nesting_depth) : 해당 변수가 사용되는 곳의 static_depth - 선언된 곳의 static_depth
Activation을 볓번 쫒아가는 가를 알려주는 지표의 역할을 한다.
> local_offset : "시작주소 + 3 + parameter개수 + 자신의 번째"
ex) Static한 scope를 따르므로 컴파일시 이 모든 값을 결정할 수 있다.
- Static Chain의 문제점
> chain_offset 값이 커질 수록 속도가 느려지고 비효율적이다.
※ 프로그래머가 작성하는 chain_offset의 최대는 2~3정도이다. 따라서 신경쓰지 않아도 됨.
> Time critical code에 비적합 : 참조 시간이 각 변수마다 chain_offset에 따라 다르므루...
※ Time critical code를 작성하기 위해 생긴것이 Display방식
: 모든 것을 register에 넣어서 사용하여 바로바로 변수를 가져올 수 있다.
* Implementing Blocks
- static한 다른 예로 block이 존재한다.
- block은 그것 자체로 scope를 나누고, 그에 따라 정적인 scope가 정해진다.
- 위에서 사용한 static chain에서 함수 단위가 아닌 블럭 단위로 변화만 하면 된다.
> block는 파라미터가 없는 sub Program이다. 또한 지속적인 사용을 하기 편하게 stack형식으로 쭉 쌓는다.
- 또한, 프로그램 실행시 서로 같은 레벨의 블럭끼리는 메모리를 따로 쌓을 필요가 없다.
ex)
- 서브프로그램이 "Linkage(연계=call과 return)"에 대한 것이 원할하게 이뤄지게 구현해야한다.
* 최초의 Sub-Program을 지원한 FORTRAN 77(Passing Method:Call by Reference)
- FORTRAN77은 Sub-Program을 지원하기 위해서 다음의 과정을 밟았다.
ⓐ 서브프로그램을 실행하기 위해서는 함수를 호출하는(call)과 서브프로그램이 종료되어
되돌려 받는(return)이라는 2가지 step이 존재하는 것을 알게되었다.
ⓑ 각각 Step에서는 다음과 같은 순서로 세분화 된다.
1) Call step
① 호출하는 자신(caller)은 자신의 현 상태를 저장한다.
② 호출과 동시에 Parameter passing은 어떻게하느냐에 따라 다르게 진행된다.
③ return시 되돌아가야할 주소의 위치를 저장한다.
④ 위 과정이 모두 완료되면 callee에게 제어권을 인수한다.
2) Return step
① 변화된 파라미터의 값을 전달해주어야 한다.
(Parameter Passing Method : Pass by value-result와 Pass by result 일때)
② 만약, 서브프로그램이 프로시져가아닌 함수라면 함수의 결과값을 전달해주어야 한다.
③ caller의 상태를 복구해야한다.
④ caller에게 제어권을 인수한다.
ⓒ 각각의 스탭을 살펴본 결과 빨간 글씨를 저장할 필요가 생겼다. 이로 인해 활성화 레코드가 탄생한다.
※ Activation Record(활성화 레코드)
- caller와 callee는 정해진 양식을 통해서 서로 정보를 교환하는데,
그 교환이 되는 매개체, 양식(다른말로 Layout)을 활성화레코드라고 한다.
- FORTRAN에서의 activation record
- 포트란77에서는 하나의 subProgram은 단 하나의 activation record instance를 가진다.
> 이 말은, 자바에서 하나의 클래스는 단 하나의 객체만 만들수 있다는 것과 같은 말로
Activation Record의 위치를 컴파일시 Static하게 저장한다는 것이다.
(컴파일시 인스턴스는 위 그림에서 제공되는 것처럼 2가지 방법중 하나로 하여 생성할 것이다.)
> 재귀적 호출 불가능!
* ALGOL의 Sub-Program지원 방식ⓐ
- ALGOL은 포트란과의 언어적 차이점을 가지고 있다.
ⓐ Parameter Passing Method가 2가지라는 것(Call by reference, Call by value)
ⓑ 지역 변수를 Dynamic하게 할당과 반납을 해준다는 것
ⓒ 재귀적 호출이 가능해야 한다는 것
ⓓ Static Scope방식을 따른다는 것
- ALGOL에서의 Activation Record Design
※ Static Link
- 자신의 정적부모의 Activation Record의 바닥
> ⓓ번의 문제해결을 위해서(Scope문제)
※ Dynamic Link
- 자신을 부른 호출자의 Activation Record의 상단
> ⓒ번의 문제해결을 위해서(재귀적 호출가능)
- 상단에는 함수 값이 있어 바로 연계가 가능
※ Dynamic chain(call chain)
- 호출의 순서를 담고 있는 별도 저장공간
- 위의 Activation Record에서 특정 서브프로그램의 로컬변수를 지정하는 방법
> 모든 Sub-Program의 Activation Record는 기본적으로 3가지의 정보를 가지고 있다.
(Return Address, Static Link, Dynamic Link) : 편의상 각각 1Byte씩 차지한다고 생각하자.
> 자신이 받거나 넘기는 Parameter의 개수도 알고 있다.
> 위의 두가지 사실을 이용하면 Local variable의 시작 변수 위치를 참조 할수 있다
= Activation Record의 시작주소+ 3(기본적인 정보) + 파라미터의 개수
예 )
* ALGOL의 Sub-Program지원 방식 : 변수가 나의 Local에 없는 경우
- 이 경우 다음과 같은 과정을 따른다.
ⓐ 정확한 activation record instance를 찾는다.
ⓑ 그 위치에서의 local변수를 찾는다. => 위에 나온 방식대로 "시작주소 + 3 + parameter개수" 로 구한다.
- 위 과정에서 ⓐ를 해결하는데 문제가 발생한다. 알골의 프로그램에서는 실행할 서브프로그램을 프로그램 안에
구현하므로 자신이 찾으련느 변수는 상위 scope에 존재함을 가정으로 한다. 다음의 방식으로 구현을 한다.
ⓐ Static Chains : Static Link를 묶어 놓은 것.
ⓑ Display
※ display 방식은 비용대비 효과가 낮아 사용도가 낮다. 거의 소멸된 상태이다.
* Static Chains
- main이 a를 호출시 a의 static link는 main이다. 이를 이용하여 자신의 모든 정적 조상을 찾을 수 있다.
(알골의 프로그램에서는 실행할 서브프로그램을 프로그램 안에 구현하므로 )
- static chains : (chain_offset, local_offset)
> static_depth : sup Program이 얼마나 main에서 중첩되어 있는가?
> chain_offset(=nesting_depth) : 해당 변수가 사용되는 곳의 static_depth - 선언된 곳의 static_depth
Activation을 볓번 쫒아가는 가를 알려주는 지표의 역할을 한다.
> local_offset : "시작주소 + 3 + parameter개수 + 자신의 번째"
ex) Static한 scope를 따르므로 컴파일시 이 모든 값을 결정할 수 있다.
- Static Chain의 문제점
> chain_offset 값이 커질 수록 속도가 느려지고 비효율적이다.
※ 프로그래머가 작성하는 chain_offset의 최대는 2~3정도이다. 따라서 신경쓰지 않아도 됨.
> Time critical code에 비적합 : 참조 시간이 각 변수마다 chain_offset에 따라 다르므루...
※ Time critical code를 작성하기 위해 생긴것이 Display방식
: 모든 것을 register에 넣어서 사용하여 바로바로 변수를 가져올 수 있다.
* Implementing Blocks
- static한 다른 예로 block이 존재한다.
- block은 그것 자체로 scope를 나누고, 그에 따라 정적인 scope가 정해진다.
- 위에서 사용한 static chain에서 함수 단위가 아닌 블럭 단위로 변화만 하면 된다.
> block는 파라미터가 없는 sub Program이다. 또한 지속적인 사용을 하기 편하게 stack형식으로 쭉 쌓는다.
- 또한, 프로그램 실행시 서로 같은 레벨의 블럭끼리는 메모리를 따로 쌓을 필요가 없다.
ex)