[PL] CH9. Subprograms (Module)

1. intro

(1) Two fundamental abstraction facilities

 - 프로세스 추상화 : subprogram

  -> process call : 명령문의 집합의 추상화

 

 - 데이터 추상화 : abstract data type (ex. stack)

 

- 추상화 대상: 서브프로그램 안의 코드, 알고리즘

- 추상화 결과: 서브프로그램의 이름, 파라미터 리스트

 

(2) 명령문의 집합은 다시 사용되어 메모리의 기계어 집합으로 끝남

 - 메모리 공간 절약, 코딩 시간 절약

 

(3) 이런 재사용은 만약 collection을 "call"하는 명령문에 의해 collection이 프로그램에 존재하게 되면 하나의 추상화가 됨

 - 몇몇 계산이 수행되는 방법을 설명하는 것 대신, 해당 설명 (명령문의 집합)은 "call" 명령문에 의해 수행되며, 이는 세부사항을 효과적으로 추상화함

 

 

- caller vs. calle

- Procedure vs. Macro

 

 

2. Fundamentals of Subprograms

(1) General subprograms Chracteristics

 - Basic characteristics of subprograms

  : 각 subprograms는 single entry poing를 가짐

  : calling program unit은 called subprogram이 수행되는 동안 suspend되어 있으며, 주어진 시간에 오직 하나의 subprogram이 수행되는 것을 의미

  : Control은 subprogram 수행이 종료되면 항상 caller로 돌아감

 

(2) Basic definition

 - subprogram definition: subprogram의 추상화의 action을 묘사

 - subprogram call은 subprogram이 수행되도록 하는 explicit request

 - 호출 후에  subprogram이 수행을 시작했지만 아직 완료하지 못했으면 active상태

 

 - subprogram header : definition의 첫번째 줄 

   -> objectives : 다음의 syntactic unit이 subprogram definition임을 지정

                     : subprogram의 이름을 제공

                     : 선택적으로 파라미터의 리스트를 지정

 

 - C : 오직 한 종류의 subprogram을 가짐 -> function

      : header는 context에 의해 인식

subprogram p와 변수 p

 

(3) Parameters ; subprogram이 data에 access하는 방법

  1. direct access to nonlocal variables (global variables)

  

  2. parameter passing

   : a parameterized computation -> subprogram이 어떤 computation을 할 지는 parameter에 의해 결정됨

 

void main(void) {
	int i, num = 0;
    
    for(i=1; i<1001; i++) {
    	sum = sum + factorial(i); // actual parameter
    }
}

int factorial(int n) {
	if(n==1) return 1;
    else return (n*factorial(n-1));
}

 

- 데이터보단 computation을 서브 프로그램의 파라미터로 전송하는게 편리할 수도 있음 ex) operator, subprogram 이름

 

- Formal parameters : 서브 프로그램 헤더에서의 파라미터

- Actual parameters : 서브 프로그램의 formal 파라미터로 바인딩될 서브프로그램 호출에서의 파라미터 리스트

 

- Parameter passing

 - Positional parameters : 단순한 위치에 의해 실행됨

 - Keyword  parameters : 이름으로 바인딩

 

keyword parameter

서브 프로그램의 유저는 반드시 formal parameter의 이름을 알고 있어야함

 

- C++, Ada에서 formalparameter는 default 값을 가질 수 있음

 -> formal parameter로 넘겨주는 actual parameter가 없으면 디폴트 값이 넘어감

 

caller가 넘겨주는 게 없으면 1을 넘겨줌 -> default parameter

 

 

- 호출 시 actual parameter의 수가 서브프로그램의 헤더에서의 formal parameter의 수와 맞아야함

(C 제외)

 

(4) Procedures and Functions

- Procedure ; return 값 없음

  : parameterized computation을 정의하는 statement의 집합

  : caller에게 결과 값을 전달 -> by changing visible variables (formal parameter 제외), by changing formal parameters (caller에게 데이터를 전송)

 

- Functions ; return 값 있음, 항상 결과가 존재

  : 함수들은 표현식에서 필요한 actual parameter와 함께 이름으로 호출됨 (user defined operator)

  : 함수의 실행으로 생성된 값은 calling code로 반환되며, 호출 자체를 효과적으로 대신함

 

3. Design issues for Subprograms

(1) Issues

 - actual parameter의 타입이 formal parameter의 타입에 대해 확인되는지 -> type checking, 개수 check

 - 로컬 변수가 statically / dynamically 하게 할당되는지

  : 서브 프로그램 안의 선언된 변수들이 수행되기 전에 storage에 미리 할당? 

  : 수행 도중에 할당? => recursion이 허용되면 미리 할당, 허용되지 않으면 호출시 할당됨

- 파라미터로 전달된 서브프로그램의 referencing된 환경은 무엇?

- 만약 서브 프로그램이 파라미터로 전달될 때, 파라미터의 타입은 전달된 서브 프로그램에 대한 호출에서 확인됨?

- 서브 프로그램이 overload? (같은 이름의 서브 프로그램이 여러 개)

- 서브 프로그램이 generic? (여러 종류의 데이터 타입을 처리)

- separate / independent compilation이 가능한 지

 

 

 

 

4. Local Referencing Environments

(1) 서브 프로그램 안에 선언된 변수들은 local 변수라고 함

  -> 로컬 변수에 대한 access는 그들이 선언한 서브 프로그램에 대해 제한적 -> scope of local variables

  - Stack-dynamic local variables

    : 서브 프로그램이 수행을 시작할 때 storage에 바인딩되고, 실행이 종료되면 storage로부터 unbound

    : recursive 서브 프로그램을 허용, storage sharing

    : 각 호출에 대한 변수를 할당, 초기화, 할당 해제하는 시간이 많이 듦, indirect referencing(slow), history-sensitive procedure(그 전 값을 유지)를 허용하지 않음

 

 

- Stack local variables

  : 전체 프로그램이 수행을 시작할 때 storage를 바운딩

  : 빠른 referencing, history-sensitive procedures

  : recursion x

  : ALGOL, 로컬 변수들은 default stack-dynamic에 의함

 

adder (list, listlen)
int list[], listlen ; 
{   static int sum = 0 ; /*  static local variable */ //데이터 영역
    int count ; /*  stack dynamic local variable */
    for (count = 0 ; count < listlen ; count++) 
    	sum = sum + list[count] ;
    return sum ;
}

 

 

sub() {
	static int i; // 함수가 끝나도 i의 값을 유지, 메모리의 data 안에 저장 -> stack-dynamic
    char c; // sub() 함수의 scope안에서 존재하며 메모리의 스택에 저장됨 
    ...
}

main() {
	sub(); // recursion o -> 수행 도중에 호출
    sub(); // 위의 sub()의 i 값이 넘어옴
}

 

global vs static : 둘은 life time이 같음 (프로그램의 시작~끝)

하지만 scope이 다름 -> global은 전체 프로그램, static은 변수가 선언된 함수 내에서

 

 

5. Parameter-Passing Methods

(1) Semantics Models of Parameter Passing

 - Formal parameter는 세가지 semantics model 중 하나에 의해 구체화됨

1. in-mode : caller->callee로 정보가 들어옴, formal parameter가 상응하는 actual parameter로 부터 데이터를 받음, C언어

2. out-mode : callee->caller로 계산 결과를 넘김, formal parameter가 상응하는 actual parameter로 데이터를 전송

3. inout mode : 둘다, call by reference

 

- 데이터 전송에서 파라미터 전송이 발생하는 방법

 1. actual value는 물리적으로 이동됨

 2. access pass(pointer)가 전달됨

 

 

(2) Implementation Models of Parameter Passing

 1. Pass-by-Value (call-by-value)

  - actual parameter의 값은 일치하는 formal parameter를 초기화하며, 서브 프로그램에서 로컬 변수로 사용됨

  - in-mode semenctics를 제공

  - actual data transfer에 의해 수행됨 -> mem copy

 

memory copy

- 파라미터가 긴 배열과 같은 큰 object일 때, extra storage와 move operation은 비용이 많이 들 수 있음

 

 

2. Pass-by-Result ; 끝날 때 caller로 actual parameter를 copy

 - out-mode 파라미터의 구현 -> 서브 프로그램으로 전달되는 value 없음

 - 상응하는 formal parameter가 로컬 변수로 수행되지만, caller로 다시 control이 전달되기 직전에 해당 값이 caller의 actual parameter로 다시 전송됨, variable이어야함 -> sub(x,y) (o) // sub(3, 7) (x)

 - 문제점: extra storage와 move operation이 문제가 될 수 있고, actual parameter의 collision이 발생할 수 있음

 

subroutine sub(x,y){
    x=3 ;
    y=5;
}

main() {
    int p1;
    sub(p1, p1);
    p1???
}

 

- implementor가 actual parameter의 주소를 평가하기 위해 2개의 시간을 고를 수 있음

int index, list[10];
subroutine sub(a){
    index = 5;
    a = 3;
}
main() {
    index = 3;
    sub(list[index]);
}

index[3] or index[5] ? 

 

call by value --> list[3]의 값이 넘어감

call by result --> 받을 곳의 주소를 언제 결정? 받을 때: list[5], 호출 전에 미리 주소 계산: list[3]

 

 

3. Pass-by-Value-Result (pass-by-copy)

- actual value가 이동하는 inout-mode 파라미터 구현

- actual parameter의 값이 상응하는 formal parameter를 초기화하기 위해 사용되며, 로컬 변수로 사용됨

 서브 프로그램 종료 시, formal parameter의 값이 다시 actual parameter로 전송됨

- 마지막에 결과 값을 copy back 해주므로 비정상적으로 프로그램이 종료되면 결과 값을 copy back하지 않음

 

4. Pass-by-Reference

- inout-mode 파라미터 구현

- 주소인 access path를 호출된 프로그램으로 전송 -> actual parameter는 호출된 서브프로그램과 공유됨

- No copying overhead, no duplicate space

- 문제점

 : formal parameter의 access는 indirect addressing이기 때문에 느림

 : actual parameter에 부주의하고 잘못된 변화가 생길 수 있음

 : aliases가 만들어짐 (한 메모리 셀에 대해 여러 개가 access)

 

- 주소 값을 넘겨줘서 업데이트 하므로 중간중간 마다 그 과정을 따라서 값이 변경됨