Introduction
Subprogram Control
- Sequence Control : call/return
- Data Control: scope rule, parameter transmission
Secuence Control
- Copy Rule: 서브프로그램 호출이 일어나면 서브프로그램 몸체를 그대로 복사한다.
- 고려할 사항: 인수 이름 충돌, 재귀호출
- 호출시 변하지 않는 부분과 변하는 부분 분리
- 변하지 않는 부분 -> code segment -> static segment
- 변하는 부분 -> activation record -> dynamic segment
- Scope Ruels
- Static Scope Rule: 수행 전 변수의 scope 결정
- Dynamic Scope Rule: 수행 중 변수의 scope 결정
Data Control Problems
Activation Record(AR)
- 정적 변수를 제외한 나머지 변수는 모두 AR에 있음
- 서브프로그램 P가 다음과 같은 선언을 포함하고 있다고 하자
var X: integer;
변수 X는 P의 AR에서 찾을 수 있다. 즉 X의 I-value는 특정 AR에서의 상대주소(offset)로 계산 가능하다.
Computing L-Value
- 어떤 변수의 X의 I-value를 계산하는 과정은 다음 두 과정으로 구성된다.
- X를 포함하는 AR을 찾음
- AR의 특정 위치(offset)에서 X의 I-value를 구함
Scope
- 변수의 범위는 볼 수 있는 statements의 범위이다.
- 프로그램단위의 비지역 변수들은 볼수 있지만 그곳에 선언되지 않는다.
- 언어의 범위 규칙은 이름에 대한 참조가 변수와 어떻게 연관되는지 결정합니다.
Scope Rules
Local vs Non-local
- 지역변수(local variable): 변수를 참고하는 문장이 포함된 블록과 변수를 선언한 블록이 같은 경우, 해당 변수는 지연변수
- 비지역변수(non-local variable): 참조 문장이 포함된 블록과 선언한 블록이 다를 경우, 해당 변수는 비지역변수
Static Scope
- 프로그램 텍스트 기반
- 이름 참조를 변수에 연결하려면, (개발자 또는 컴파일러)은 선언을 찾아야 한다.
- 검색 프로세스: 먼저 로컬에서, 점점 더 큰 둘러싸는 범위에서, 주어진 이름에 대해 찾을 때까지 선언을 찾는다.
- 정적 범위(특정 범위)를 둘러싸는 것을 static ancestors(정적 조상)이라고 한다; 가장 가까운 정적 조상은 static parent(정적 부모)라고 불린다.
- 변수는 같은 이름의 "closet" 변수를 사용하여 단위에서 숨길 수 있습니다.
- C++ 과 Ada는 이러한 hidden 변수에 대한 접근을 허용한다.
Review of Static Scope Rule
- P: 서브 프로그램 Q와 T는 P에서 선언되었으므로 Q와 T의 영역은 a의 영역과 같다.
- Q: 서브 프로그램 R과 S는 Q의 지역 서브프로그램이다.
- T: 서브 프로그램 U를 지역적으로 선언하고 있다.
- Scope Hole: P에 선언된 a
Block
프로그램 유닛 안에서 static scopes을 생성하는 메소드 (from ALGOL 60)
Evaluation of Static Scoping
- D가 이제 B의 일부 데이터에 액세스해야 한다고 사양이 변경되었다고 가정해 봅시다.
- sol)
- D를 B에 넣는다.(그러나 D는 A의 변수에 접근을 하지 못한다.)
- D가 필요한 데이터를 B에서 MAIN으로 옮겨라 (하지만 모든 procedures가 접근할 수 있다.)
- Overall: static scoping 지정은 종종 많은 글로벌을 장려한다
Dynamic Scoping
- 텍스트 레이아웃이 아닌 프로그램 단위의 호출 시퀀스를 기반으로 합니다 (시간 대 공간)
- 변수에 대한 참조는 이 시점까지 실행을 강제하는 하위 프로그램 호출 체인을 통해 다시 검색하여 선언과 연결됩니다.
Evaluation of Dynamic Scoping
- 장점: 편리함
- 단점: 가독성 부족
- 범위와 수명은 때때로 밀접한 관련이 있지만, 다른 개념이다!!(C++의 static변수)
Referencing Environment
- statement의 참조 환경은 statement에서 볼 수 있는 모든 이름의 모음이다.
- 정적 범위 언어에서, 그것은 지역 변수와 모든 둘러싸는 범위의 모든 눈에 보이는 변수이다.
- 실행이 시작되었지만 아직 종료되지 않았다면 subprogram이 활성화된다.
- 동적 범위 언어에서, 참조 환경은 지역 변수와 모든 활성 하위 프로그램의 모든 가시적 변수입니다.
Static scoped language example
Dynamic scoped language example
Activation Record Stack
- AR 스택을 어떻게 관리할 것인가?
- Two Pointers:
- Dynamic Link Pointer: caller의 AR을 가리킴. 복귀 후 AR을 회복하기 위해 필요
- Static Link Pointer: static parent의 AR을 가리킴. 정적영역규칙을 구현하기 위해 필요
Activation Record Structure
Example C function(6장)
ALGOL-like LAnguages에서 Subprogram구현(6장)
Activation Record for factorial(6장)
Subprograms in ALGOL-like Languages(6장)
Example of Activation Record Stack
P -> Q -> R -> S 순으로 호출하였을 경우:
Activation Record Example
lvalue = rvalue 형태
lvalue: 표현식 이후에도 사라지지 않는 값. 이름을 지니는 변수.
rvalue: 표현식 이후에는 사라지는 값. 임시 변수.
Nested Subprograms
- 일부 C기반이 아닌 static-scoped 언어(예: 포트란 95, 에이다, 자바스크립트)는 스택 동적 로컬 변수를 사용하고 하위 프로그램을 중첩할 수 있습니다.
- 관찰: 비로컬에 액세스될수 있는 모든 변수는 스택의 일부 활성화 레코드 인스턴스에 있습니다.
- 비로컬 참조를 찾는 과정
- 올바른 activation record 인스턴스를 찾아라.
- activation record 인스턴스 내에서 올바른 오프셋을 결정하라.
The Process of Lacating a Nonlocal Reference
- offset을 찾는 것은 쉽다.
- 올바른 activation record 인스턴스를 찾아라.
- 정적 의미 규칙은 참조할 수 있는 모든 비로컬 변수가 참조가 이루어질 때 스택에 있는 일부 활성화 레코드 인스턴스에 할당되었음을 보장한다.
기술1- Static Chains
- 정적 체인은 특정 activation record 인스턴스를 연결하는 정적 링크 체인이다.
- 하위 프로그램 A에 대한 활성화 레코드 인스턴스의 정적 링크는 A의 정적 부모의 활성화 레코드 인스턴스 중 하나를 가리킨다.
- 활성화 레코드 인스턴스의 정적 체인은 모든 정적 조상에 연결한다.
- 비지역 변수에 대한 참조에 대한 선언을 찾으려면:
- 변수가 있는 활성화 레코드 인스턴스(ari)가 발견될 때까지 정적 체인을 쫓을 수 있으며, 변수 이름이 ari에 저장된 경우 각 ari를 검색할 수 있다.
static_depth
- 그 범위의 중첩 깊이인 정적 범위와 관련된 정수이다.
Chain_offset(nesting_depth)
- 비로컬 참조의 chain_offset 또는 nesting_depth는 참조의 static_depth와 그것이 선언된 범위의 차이이다.
- 참조는 쌍으로 나타낼 수 있다: (chain_offset, local_offset) 여기서 local_offset은 참조되는 변수의 활성화 레코드에서 오프셋이다.
Static Chain Maintenance
- at call(하위 프로그램인 매개 변수가 없고 이름별 매개 변수가 없다고 가정)
- 활성화 레코드 인스턴스가 구축되어야 한다.
- 동적 링크는 오래된 스택 탑 포인터일 뿐이다.
- 정적 링크는 정적 부모의 가장 최근 ari를 가리켜야 합니다 (대부분의 상황에서)
두가지 방법
- 정적 부모의 첫 번째 ari가 발견될 때까지 동적 체인을 검색-쉽지만 느리다.
- 변수 참조 및 정의와 같은 프로시저 호출 및 정의를 처리 (컴파일러가 중첩 깊이 또는 호출자와 호출된 프로시저를 선언한 프로시저 사이의 둘러싸는 범위의 수를 계산하도록 하라. 이 중첩 깊이를 저장하고 호출과 함께 보낸다)
call 요청에서, 중첩 깊이와 같은 링크 수를 호출자의 정적 체인 아래로 이동하세요. - 예를 들어. MAIN_2와 스택 내용을 보세요. SUB3의 SUB1에 대한 호출에서, 이 중첩 깊이는 1이며, 이는 호출과 함께 SUB1로 전송됩니다. SUB1에 대한 새로운 ari의 정적 링크는 호출자(SUB3)의 정적 체인 아래로 이동하여 중첩 깊이(1)의 수, 즉 SUB3의 ari에서 정적 체인의 두 번째 정적 링크를 가리키도록 설정됩니다.
Evaluation of the Static Chain Method-문제점
- 참조와 참조된 변수의 선언 사이의 범위 수가 크면 비로컬 참조는 느립니다.
- 비로컬 참조의 비용이 동일하지 않고 코드 업그레이드 및 수정으로 변경될 수 있기 때문에 시간이 중요한 코드는 어렵습니다.
Static Chain 방법의 단점
- 참조되는 비지역 변수가 선언된 블록의 중첩깊이와 참조 문장을 포함한 중첩깊이의 차이가 크다면 비지역 변수 참조 시간 부담이 커진다.
- 비지역 변수 참조 시간이 변수에 따라 다름: 수행 시간이 중요한(real-time application)에서 사용하기 힘들다.
Display
- 정적영역규칙을 구현하기 위한 다른 방법
- 정적 링크를 별도의 스택에 관리
- 참조 환경의 모든 변수는 이 스택이 가리키는 활성 레코드 내에 존재
참조환경
- 프로그램의 어느 한 문장에서 참조 가능한 모든 이름의 집합
기술2-Display
- 아이디어: 정적 링크를 디스플레이라고 불리는 별도의 스택에 넣으세요. 디스플레이의 항목은 참조 환경에서 변수가 있는 ari에 대한 포인터입니다.
- 참조를 (display_offset, local_offset)로 나타내며, 여기서 display_offset은 chain_offset과 동일합니다.
Mechanics of references
- Display_offset을 사용하여 변수가 있는 아리에 대한 디스플레이에 포인터를 가져오세요.
- local_offset을 사용하여 ari 내의 변수에 도달하세요
Display maintenance(하위 프로그램인 매개 변수가 없고 이름 매개 변수가 없다고 가정)
- Display_offset은 ari가 구축 중인 프로시저의 정적 깊이에만 의존한다는 점에 유의. 그것은 정확히 프로시저의 정적 깊이이다.
- 디스플레이에는 k+1 항목이 있으며, 여기서 k는 현재 실행 중인 단위의 정적 깊이다(k=0은 메인 프로그램을 위한 것이다).
- Static_depth가 k인 프로시저 P를 호출하는 경우
- 새로운 ari에서 k 위치에 디스플레이 포인터의 복사본을 저장하라.
- 디스플레이의 k 위치에 P에 대한 ari 링크를 넣어라.
- exit에서, 저장된 디스플레이 포인터를 ari에서 k 위치의 디스플레이로 다시 이동하라.
이것이 작동하는지 보기 위해
- Psd는 P의 static_depth가 되고, Qsd는 Q의 static_depth가 되도록 하자
- Q가 P를 호출한다고 가정하자
- 세 가지 가능한 경우가 있다:
- Qsd = Psd
- Qsd < Psd
- Qsd > Psd
충분히 있다면, 디스플레이는 레지스터에 보관할 수 있습니다. 접근과 유지 보수 속도를 높입니다.
정적 체인(static chain)과 디스플레이(display) 비교
- locals에 대한 참조: 거의 차이가 없다.
- nonlocal에 대한 참조:
- 만약 한 단계 떨어져 있다면, 둘은 똑같다.
- 그 이상 떨어져 있다면, 디스플레이가 더 빠르다.
- 모든 비로컬 참조 비용이 동일하기 때문에 디스플레이는 시간이 중요한 코드에 더 좋습니다.
- Procedure 호출
- 하나 또는 두단계의 깊이의 경우 static chain이 더 빠르다.
- 그 이상은 display가 더 빠르다.
- Procedure 리턴
- 둘 다 시간이 고정되어 있지만, static chain이 약간 더 빠르다.
- 결론
- 비지역 변수 참조가 빈번하다면 display가 유리하다.
- 비지역 변수 참조가 거의 없다면 static chain 방법이 더 유리하다.
Dynamic Scope Rule
- 서브프로그램의 호출 순서에 따라 비지역 변수를 탐색
- 비교
- Static Scope: spatial relationship(공간적 관계)
- Dynamic Scope: temporal relationship(시간적 관계)
Dynamic Scope 구현
Variable Stack
Central Table
Referencing Environments
하위 프로그램 이름인 매개 변수일 때
- Shallow binding
- 호출된 하위 프로그램을 호출하는 하위 프로그램의 환경
- Dynamic scope와 비슷
- Deep binding
- 호출된 하위 프로그램이 선언된 하위 프로그램의 환경
- static scope와 비슷
- Ad-hoc binding
- 하위 프로그램을 실제 매개 변수로 전달한 호출 문을 포함하는 하위 프로그램의 환경
- 인수로 전달된 SUB3의 static link는 SUB2의 activation record중 오래된 것을 가리키게 됨
SubProgram Control
Parameter and Argument
Parameter
- 매개변수
- 다른 서브프로그램으로부터 전달된 데이터를 보관하기 위한 변수
- 형식인수(formal parameter/argument)라고도 함
Argument
- 인수
- 서브프로그램을 호출할 때 실제로 전달되는 데이터
- 실 인수(actual argument/parameter)라고도 함
통상 parameter, argument는 구분 없이 사용함
구별하고자 할때는 formal~, actual~등의 수식어를 사용하는 것이 바람직함
Parameter passing
인수전달: 실 인수를 형식 매개변수에 전달하는 것
인수전달 구문
- 위치로 구별하여 전달하는 것이 일반적임
- 선언: Procedure P(X:integet, Y:integer);
- 호출: P(A, B+2);
- 형식인수 이름으로 구별하여 전달하기도 함(Ada)
- 호출: P(X => A, Z => 27+3,Y=>B+2);
인수전달 방법: 실 인수와 형식 매개변수와의 관계를 설정
- Call by name
- Call by reference
- Call by value
- Call by result (or value-result)
Language Examples
언어에 따라 인수전달 방법이 다를 수 있음
- ALGOL 68: call-by-name, call-by-value
- Pascal: call-by-value, call-by-reference
- C: call-by-value (포인터를 이용하여 call-by-reference를 흉내낼수 있음)
- ALGOL-W: call-by-result
인수전달 관련 주제들
- 효율성: 빠른 인수 전달
- 전달의미에 따른 인수의 분류
- in parameter: 단순히 전달만 하기 위한 인수
- out parameter: 서브프로그램으로부터 전달받기 위한 인수
- in-out parameter: 두가지 목적을 다 갖춘 인수
Call by Name
전달의미
- 형식인수 대신 실인수로 주어진 식을 그대로 치환하는 의미
- texture substitution과 유사하나 texture substitution과 달리 이름 충돌은 피하는 식으로 이루어짐
Call by Name의 구현
Thunk
- 인수를 받지 않는 함수
- 각 실인수에 대하여, 실인수로 주어진 수식의 L-value와 R-value를 계산하는 thunk를 만듦
- 인수를 사용할 경우 해당 thunk 호출
예
- Call-by-Name 인수 두개를 받는 함수 P(X,Y)에 대하여
- 호출 P(A,B+2)는 다음 thunk들을 생성
- thunk 1 to return L-value(A)
- thunk 2 to return R-value(A)
- thunk 3 to return L-value(B+2)
- thunk 4 to return R-value(B+2)
- X에 저장하려면 thunk1을 호출, X을 읽으려면 thunk2를 호출
Call by Name 은 읽기 힘들다.
- 이름에 의한 인수전달을 이용하면 프로그램을 이해하기 힘들다.
Call by Reference
전달의미
- 실인수의 I-value를 전달
- callee에서 실인수의 r-value와 l-value를 모두 참조할 수 있음
- 즉, 실인수의 내용을 변경할 수도 있음 -> in-out parameter
구현
- P(A, B+2, 27+3)와 같은 호출은 다음과 같이 구현:
Alias
Call by Value
전달의미
- 실인수의 r-value를 전달
- 실인수의 ㄱ밧을 복사하는 것과 같은 의미 -> call by copy라고도 함
구현
Call by Value-Result
전달의미
- call by value처럼 인수의 r-value를 매개변수로 전달
- 서브프로그램에서 복귀시, 매개변수의 r-value를 다시 실인수에 복사
- in-out parameter를 구현하는 다른 방법으로서 aliasing이 발생하지 않음
구현
call by name은 함수호출때 값이 정해지는게 아니라 해당 변수가 나타났을 때 값을 가져온다.(그 외엔 call by value와 비슷)
'Computer Science > 프로그래밍언어론' 카테고리의 다른 글
기말 시험 준비 (0) | 2023.06.15 |
---|---|
Chapter8 Sequence Control (0) | 2023.06.15 |
Chapter7 Inheritance (0) | 2023.06.13 |
Chapter6 Encapsulation (0) | 2023.06.13 |
Chapter5-2 Structured Data Types (0) | 2023.06.12 |