Lecture 9: Function Implementation

카테고리 없음

Lecture 9: Function Implementation

용학사 2024. 12. 3. 00:11

9-1)함수 호출 구현 원리

언어 S의 구문법

먼저 함수를 정의해야 한다. 함수 정의는 키워드 fun으로 시작하고 리턴 타입(<type>), 함수 이름(id), 매개변수 리스트(<params>), 실행할 문장(<stmt>)으로 구성된다. 함수 호출은 함수 이름과 인자(<expr>)들로 구성된다. 함수 호출은 값을 리턴하지 않는 경우에는 하나의 문장이 될 수 있으며, 값을 리턴하는 함수 호출을 수식 내에서 하나의 인수(<factor>)로 사용될 수 있다.

함수 반환을 위해 필요한 사항들

-지역 변수, 매개변수 등을 위한 기억공간 해제

-반환 값 저장

-호출자로의 반환

(재귀 호출은 몇 번 호출될 지 미리 알

수 업서서 함수 호출을 구현하기 위해 호출될 때마다 호출을 구현하기 위한 자료구조를 구성해야 한다.)

실행시간 스택

주로 함수 호출을 구현하기 위해서 사용되는 기억공간으로 실행시간 스택(runtime stack)이 사용된다.

실행시간 스택에는 함수 호출에 필요한 지역 변수, 매개변수, 반환 값, 반환주소 등을 위한 기억공간이 할당된다.

활성 레코드

함수 호출을 구현하기 위한 자료구조는 활성 레코드(activation record) 혹은 스택 프레임(stack frame)이라고 한다.

실행시간 스택을 이용한 함수 호출 구현

-함수 호출될 때마다 새로운 프레임(호출에 필요한 정보 포함)을 스택에 생성한다.

-함수가 끝날(반환될) 때마다 호출할 때 만든 프레임을 제거한다.

예제3
fun int max(int x, int y)
	if(x > y) then
    	return x;
    else
    	return y;
    print max(3,5);

재귀 함수 fact에 대한 호출

fun int fact(int n)
	if (n == 1) then
    	return 1;
    else return n * fact(n-1);
print fact(3);

fact(3)형태로 호출했을 때 스택에 만들어지는 프레임들을 살펴보자

1. fact(3) 호출은 끝나기 전에 fact(2)를 호출한다. 따라서 fact(3)를 위한 프레임 위에 fact(2)를 위한 프레임이 만들어진다.

2.또한 fact(2)는 끝나기 전에 fact(1)을 호출하므로 fact(2)를 위한 프레임 위에 fact(1)를 위한 프레임이 만들어진다.

3. 이제 fact(1) 호출이 끝나면 그 반환 값이 fact(1)를 위한 프레임 내의 RV:fact(1)기억장소에 저장되고 그 프레임은 제거된다.

4. 이제 이 반환 값을 가지고 계산하여 fact(2) 호출이 끝나면 그 반환 값이 fact(2)를 위한 프레임 내의 RV:fact(2) 기억장소에 저장되고 그 프레임은 제거된다.

5. 비슷하게 이 반환 값을 가지고 계산하여 fact(3) 호출이 끝나면 그 반환 값이 fact(3)를 위한 프레임 내의 RV:fact(3) 기억장소에 저장되고 그 프레임은 제거된다.

9-2)인터프리터에서 함수 구현

인터프리터에서 함수를 구현하기 위해서 상태(State)를 실행시간 스택 형태로 유지 관리하는데 이 인터프리터는 함수 정의를 먼저 만나고 나중에 함수 호출을 만날 것이다. 이 인터프리터는 함수 정의를 만나면 그 함수의 실행 코드를 AST 형태로 기억한다. 왜냐면 나중에 함수 호출을 만났을 때 이 함수를 실행해야하기 때문이다.

함수 호출을 인터프리터로 구현하기 위한 기본 아이디어를 정리

-상태(State) 스택을 실행시간 스택으로 사용한다.

-함수 정의를 만나면(함수 이름, 함수의 AST)를 push한다.

-함수 호출을 만나면 호출을 위한 새로운 스택 프레임을 구성한다.

-함수 반환을 만나면 스택 프레임을 제거한다.

함수 정의

1. 그 함수의 실행 코드를 기억하기 위해서 실행시간 스택에 함수 이름과 함수의 AST를 push한다.

함수호출

1. 스택에서 호출된 함수의 실행코드(AST)를 찾는다.

2. 스택에 프레임을 구성하고 인자 값을 곗나해서 매개변수에 전달한다.

3. 호출된 함수의 본체를 실행한다.

4. 함수가 반환되면 스택 탑에 반환 값이 저장되어 있다.

5. 함수 호출이 끝난 후 프레임을 제거한다.

함수 반환

1. 반환할 수식의 값을 계산하고 이 값을 스택 탑에 저장한다.

함수 정의 구현

함수 정의를 만나면 함수 이름과 그 함수의 AST를 스택에 저장한다.

State Eval(Command p, State state){
 ...
 	if(p instanceof Fuction) {
		Function f = (Function) p;
        //state.push(f.id, new Value(f));
        return state;
    }
}

함수 정의도 하나의 값처럼 사용되어 상태 스택에 저장될 수 있다. 따라서 Value 클래스도 함수 정의를 하나의 값으로 포함하도록 다음과같이 확장되어야 한다. 뿐만 아니라 값으로 저장된 함수 정의를 추출하는 메소드 funValue도 제공한다.

class Value extends Expr {
 // Value = int value | ... | function value
 protected boolean undef = true;
 Object value;
 Value(Type t) { 
type = t;
 }
 Value(Object v) {
 ... // 이미구현된부분
if (v instanceof Function) type = Type.FUN; 
value = v; undef = false;
 }
 
Function funValue() {
	if (value instanceof Fuction)
    	return (Function) value;
    else return null;
  }
   ...
}

함수 호출 구현

함수 호출 id(<expr>{,<expr>})

1. 스택에 저장된 함수의 AST를 가져온다.

2. 스택에 프레임을 구성하고 인자 값을 계산해서 매개변수에 전달한다.

3. 호출된 함수의 본체를 실행한다.

4. 함수가 반환되면 스택 탑에 반환 값이 저장되며 이를 제거한다.

5. 프레임을 제거한다.

Value V(Call c, State state){ 
	Value v= state.get(c.fid);
    Function f = v.funValue();      //호출된 함수의 AST 가져온다.
    State s = newFrame(state, c, f);//호출된 함수의 프레임을 스택에 추가
    s = Eval(f.stmt, s);            //호출된 함수의 본체를 실행
    Value v = s.pop().val;          //반환 값 제거
    s = deleteFrame(s, c, f);       //스택에서 프레임 제거
    return v;                       //반환 값 리턴
}

반환 값이 없는 함수 호출을 구현하는 Eval()함수는 반환 값을 제외하고는 위와 같을 것이다.

State Eval(Call c, State state) {
//반환 값이 없는 함수 구현
}

인터프리터는 스택 프레임을 반환 주소나 제어링크 없이 매개변수, 지역변수, 반환 값 등으로 구성 가능하다.

AST형태의 코드를 가지고 있으므로 호출된 함수의 본체(f.stmt)를 직접 수행(Eval)할 수 있으므로 반환 장소를 저장하지 않고도 구현 가능하다.

제어링크가 없어도 함수의 코드를 보고 매개변수나 지역 변수 개수만큼 해당 기억공간을 제거할 수 있다.

프레임 구성과 매개변수 전달

1. 인자 값들을 계산한다.

2. 매개변수들을 위한 기억공간 할당한다.

3. 인자 값들을 매개변수에 복사한다.

4. 수식의 값을 계산하고 이 값을 스택 탑에 저장한다.

 State newFrame (State state. Call c. Function f) {
 Value val[] = new Value[f.params.size()]; 
int i = 0
 // 인자 값을 계산하여 그 값을 valn에 저장한다. 
for (Expr e: c.args)
 val[i + + ] = V(e,state);
 
 
 	// 현재 상태에 매개변수 기억공간 할당(allocate 사용)
 	// 인자의 값을 매개변수에 전달
	// 상태 반환
}

State deleteFrame(State state, Call c, Function f) {
 	//상태로부터 매개변수를 위한 기억공간 제거(free 사용)
    //상태 반환
}

함수반환return <expr>

수식의 값을 계산하고 이 값을 스택 탑에 저장

State Eval(Return r, State state) {
//수식의 값을 계산하고 그 값을 상태 스택에 추가
//상태 반환
}

유효범위 규칙 구현

변수 x가 한 번은 전역 변수로 선언, 한 버은 함수 f 내에 지역 변수로 선언, 함수 g 내의 3번 줄의 대입문은 어떤 x를 접근하여 그 값을 변경할까? 만약 동적 유효범위 규칙을 이 대입문은 1번 줄에서 선언된 전역 변수 x의 값을 변경할 것이다. 만약 동적 유효범위 규칙을 적용한다면 함수 f 내에서 선언된 변수 x가 함수 g를 호출했을 때도 여전히 유효하므로 이 대입문은 5번 줄에서 선언된 지역 변수 x의 값을 변경할 것이다.

언어S에 정적 유효범위 규칙을 적용하려면 어떻게 구현해야 할까? 언어 S에는 지역 변수와 전역 변수가 존재한다는 점에서 착안하여 다음과 같이 구현할 수 있다.

1. 접근할 변수를 찾을 때는 먼저 최상위 프레임에서 찾는다. 여기서 찾으면 이는 지역 변수이다.

2. 여기서 찾지 못하면 이는 지역 변수가 아니고 전역 변수이므로 전역 변수 영역에서 찾아야 한다.

3. 이를 위해서는 스택 내에 지역 변수가 저장되는 최상위 스택 프레임과 전역 변수가 저장되는 전역 변수 영역을 구분할 수 있어야 한다.

9-3)컴파일러에서 함수 구현

메모리 영역

컴파일러를 이용한 함수 호출을 구현하기 위해서 Register,Code,Stack,Heap이 필요함

코드(텍스트)영역(code segment)

프로그램을 구성하는 기계어 코드를 저장하기 위한 공간이다.

실행시간 스택(Runtime Stack)

함수 호출에 필요한 지역 변수, 매개변수, 반환주소, 임시 변수 등을 위한 기억공간으로 사용된다. 주로 함수 호출을 구현하기 위해서 사용되는 기억공간으로 실행시간 스택(runtime stack)이라고 한다.

데이터 영역(Data segment)

정적 변수(static variable)와 전역 변수(global variable)들을 위한 기억공간으로 사용된다.

이 역역은 보통 초기화된 변수와 초기화 되지 않은 변수들을 저장하기 위한 기억공간으로 각각 나뉘어 관리된다.

초기화 되지 안흔 변수의 예
int maxcount = 99; //초기화된 변수(initialized)
long sum[1000];    //초기화되지 않은 변수(uninitialized)

힙 영역(Heap)

동적 메모리 할당을 위한 기억공간으로 사용된다.

컴파일러:

컴파일러는 위에 메모리 모델을 가정하고 컴파일하여 기계어 코드를 생성한다. 특히 함수 호출을 구현하기 위해서는 앞에서 설명한 실행시간 스택을 사용하는 코드를 생성한다.

즉 함수 호출을 구현하기 위해 매개변수 전달, 지역 변수를 위한 기억장소 할당, 반환 주소 저장 등을 위한 코드를 생성하고 호출되는 함수로 제어를 이전하도록 코드를 생성한다.

인터프리터:
인터프리터는 기게어 코드를 생성하는 것이 아니므로 인터프리터 내에서 프로그램을 해석하여 실행하며 함수 호출도 인터프리터 내에서 구현한다. 보통 인터프리터는 실행시간 스택과 비슷한 역할을 할 수 있는 자료구조를 인터프리터 내에 구성하여 이를 이용하여 함수 호출을 구현한다.

제어링크(control link)

-제어링크는 함수의 호출 관계를 나타내는 링크로 호출자의 활서 레코드(바로 전 활성레코드)에 대한 포인터를 저장한다.

제어 링크는 동적인 호출 관계를 나타내므로 동적 링크라고도 한다.

-이 링크는 함수가 호출되어 활성 레코드가 만들어질 때 호출자의 활성 레코드를 가리키도록 설정되고, 호출이 끝나고 활성 레코드가 삭제될 때에는 이 링크를 이용하여 호출자의 활성 레코드의 시작 위치를 파악하여 FP가 이를 가리키도록 한다.

접근링크(access link)

-정적 유효범위 규칙을 사용하는 경우에 비지역 변수(nonlocal variable)를 접근하는 데 사용되며 정적 링크라고도 한다.

-바깥 블록(혹은 함수)에서 선언된 변수를 함수 내에서 비지역 변수로 사용할 수 있다

-호출된 함수를 위한 활성 레코드 내의 접근 링크는 호출된 함수가 정의된 바깥 블록(혹은 함수)의 활성 레코드를 가리키는 포인터를 갖으며 이 포인터를 이용하여 비지역 변수를 접근할 수 있다.