Chapter9 Subprogram Control

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를 계산하는 과정은 다음 두 과정으로 구성된다.
  
  1. X를 포함하는 AR을 찾음
  2. 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)
  1. D를 B에 넣는다.(그러나 D는 A의 변수에 접근을 하지 못한다.)
  2. 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, 에이다, 자바스크립트)는 스택 동적 로컬 변수를 사용하고 하위 프로그램을 중첩할 수 있습니다.
• 관찰: 비로컬에 액세스될수 있는 모든 변수는 스택의 일부 활성화 레코드 인스턴스에 있습니다.
• 비로컬 참조를 찾는 과정
  1. 올바른 activation record 인스턴스를 찾아라.
  2.  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를 가리켜야 합니다 (대부분의 상황에서)

두가지 방법

1. 정적 부모의 첫 번째 ari가 발견될 때까지 동적 체인을 검색-쉽지만 느리다.
2. 변수 참조 및 정의와 같은 프로시저 호출 및 정의를 처리 (컴파일러가 중첩 깊이 또는 호출자와 호출된 프로시저를 선언한 프로시저 사이의 둘러싸는 범위의 수를 계산하도록 하라. 이 중첩 깊이를 저장하고 호출과 함께 보낸다)
   call 요청에서, 중첩 깊이와 같은 링크 수를 호출자의 정적 체인 아래로 이동하세요.
3. 예를 들어. 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와 비슷)

 

---