Skip to content

Latest commit

 

History

History
167 lines (160 loc) · 7.74 KB

chap09.md

File metadata and controls

167 lines (160 loc) · 7.74 KB

CHAP 09

함수 구현 원리

함수 호출

  • 함수 호출 구현 위해 필요한 것들
    • 매개변수 메모리 할당
    • 매개변수 전달
    • 지역 변수 메모리 할당
    • 반환 값 기억공간 할당
    • 반환주소를 위한 기억공간 할당 및 저장
    • 피호출자 함수(callee) 시작부분으로 제어 이전(goto)
  • LIFO(Last-In-First-Out)
    • 호출 구현을 위한 자료구조.
    • 실행시간 스택

함수 반환

  • 함수 반환 구현에 필요한 것들
    • 지역변수, 매개변수 등을 위한 기억공간 해제
    • 반환 값 저장
    • 호출자로의 반환

실행시간 스택(Runtime Stack)

  • 함수 호출될 때: 새로운 활성 레코드(호출에 필요한 자료구조; Activation Record)가 생성된다.
  • 함수가 끝날(반환될) 때: 그 활성 레코드를 없앰
  • 함수의 활성 레코드를 정적으로 할당할 수 없음
    • 이유: 리커전이 가능함으로 끝나기 전에 다시 호출될 수 있음 (몇 번 호출될지 알 수 없고 활성 레코드가 몇 개 필요할지 미리 알수도 없음->실행하면서 알 수 있는 것들임)
  • 새로운 활성 레코드는 함수 호출마다 생성되어야 함

활성 레코드(Activation record)

  • 역할: 함수 호출/반환에 필요한 정보를 저장하는 자료 구조. (스택 프레임(frame))
  • 내용
    • 매개변수를 위한 기억 공간
    • 지역변수를 위한 기억 공간
    • 반환주소 (인터프리터에서는 필요 없음!)
    • 반환값
    • 동적 링크(제어 링크): 호출자(caller)의 활성 레코드 (필요한 이유: 활성레코드의 크기가 일정하지 않음)
  • 예시 ppt 참고할 것

인터프리터에서 함수 구현

구현 원리

1. 상태(State) 스택을 실행시간 스택으로 사용
2. 함수 정의를 만나면 (함수이름, 함수의 AST)를 PUSH 
3. 함수 호출을 만나면 스택 프레임을 구성 
* 나머지 설명 PPT 참고

함수 정의

```Java
//fun <type> id(<params>) <stmt> 
State Eval(Command p,State state){
    if (p instanceof Funciton){
        Function f=(function)p; 
        state.push(f.id,new Value(f)); 
        return state; 
    }
}

class Value extends Expr{
    protected boolean undef=true;
    Object value; 
    Value(Object v){
        //이미 구현된 부분 생략
        if (v instanceof Function) type=Type.FUN; 
        value=v; undef=false; 
    }
}
```

함수 호출

```java
Value V(Call c,State state){
    Value v=state.get(c.fid); //호출된 함수의 AST 가져오기 
    Function f=v.funValue(); 

    State s=newFrame(state,c,f); //호출된 함수의 프레임을 스택에 추가 
    s=Eval(f.stmt,s); //호출된 함수의 본체를 실행
    v=s.peek().val; //반환 값 가져오기 
    s=deleteFrame(s,c,f);//스택에서 프레임 제거 
    return v; //반환값 리턴 
}

State Eval(Call c,State state){
    //반환 값이 없는 함수 구현 : 위와 비슷한 형식으로 구현하면 됨.
}
```

스택 프레임

  • 프레임 구성과 매개변수 전달
    1. 인자 값들을 계산한다
    2. 형식 매개변수들을 위한 기억공간 할당한다
    3. 인자 값들을 형식 매개변수에 복사한다
    4. 프레임에 반환 값 엔트리를 매개변수 바로 위에 추가
  • 지역변수 처리-> 신경쓰지 않아도 괜찮음(let문이 알아서 처리)
    • 언어 S의 지역변수는 let문에 의해서 처리됨
    • 프레임 내의 반환 값 위에 지역 변수 엔트리가 만들어지며(allocate)
    • let문이 끝나면 이들을 없어짐(free)
State newFrame(State state,Call c, Function f){
    Value val[]=new Value[c.args.size()];
    int i=0;
    for(Expr e:c.args){
        //인자 값을 계산하여 그 값을 val[]에 저장함 
        val[i++]=V(e,state); 
        //현재 상태에 매개변수 기억공간 할당 
        //인자의 값을 매개변수에 전달
        //프레임에 반환 값을 위한 엔트리 추가
        //상태 반환 
    }
}

State deleteFrame(State state,Call c, Function f){
    //프레임에서 반환 값 엔트리 제거
    //프레임에서 매개변수를 위한 기억공간 제거(free 사용)
    //상태 반환 
}

함수 반환

  • return <expr>: 수식의 값을 계산하고 그 값을 프레임에 반환값으로 저장함
State Eval(Return r,State state){
    //수식의 값을 계산하고 그 값을 프레임에 반환값으로 저장
    //상태 반환 
}

유효범위 규칙 구현

  • 유효범위 규칙: 동적 유효범위 규칙 사용
  • 정적 유효범위 규칙 구현
    1. 접근할 변수를 찾을 때는 먼저 스택 탑에 있는 스택 프레임에서 찾는다. 여기서 찾으면 이는 지역변수.
    2. 여기서 찾지 못하면 지역변수가 아니라 전역 변수이므로 전역 변수 영역에서 찾아야함
    3. 이를 위해서 상태 스택 내에 지역변수가 저장되는 스택 프레임과 전역 변수가 저장되는 전역 변수 영역을 구분할 수 있어야 함.

컴파일러에서 함수 구현

함수 구현 방법

  • 컴파일러 사용 : 프로그램 실행을 위한 Hardware Machine Model : 레지스터,코드,스택,힙
    • 컴파일 후 기계어 코드가 실행됨
      • 코드 생성
      • 변수를 위한 기억공간 할당: 지역변수, 매개변수, 비지역변수,동적변수 등
      • 함수 호출 구현을 위한 코드 생성
  • 인터프리터 사용
    • 인터프리터 내에서 해석하여 실행
    • 인터프리터 내에서 함수 호출도 구현

메모리 영역

  • 레지스터
    • Program Counter(PC): 코드 영역에 대한 포인터
    • Frame pointer: 스택에 대한 포인터
  • 코드(텍스트) 영역: 프로그램을 구성하는 기계어 코드를 저장
  • 실행시간 스택: 주로 함수 호출을 구현하기 위해서 사용되는 기억공간. 지역변수,매개변수,반환값,반화주소 등을 위한 기억공간
  • 힙 영역: 동적 메모리 할당을 위한 기억공간.
    • ex. malloc() in C, new() in Pascal,Java
  • 데이터 영역
    • 정적변수, 전역 변수

비지역변수와 정적 링크

  • 제어링크 (Control link)
    • 호출 관계를 나타내는 동적 링크(Dynamic link)
    • 호출자의 활성레코드(바로 전 활성레코드)에 대한 포인터
  • 접근링크(Access link)
    • 정적유효범위 구현을 위한 정적링크(Static link)
    • 비지역변수 접근을 위한 포인터
    • 프로그램 내의 함수 정의의 포함관계
    • 호출된 함수가 정의된 함수의 활성 레코드에 대한 포인터

지역변수 접근

  • 컴파일러에서 지역 변수 접근
    • 지역 변수가 사용된다는 것은 이를 선언한 함수가 현재 호출되어있음을 의미
    • 따라서 fp가 해당 함수의 활성 레코드를 가리키고 있음
  • 지역변수의 주소: (fp)+offset
    • 프레임 포인터가 가리키는 주소+상대위치

비지역변수 접근

  • 컴파일러에서 비지역변수 접근
    • 정적링크(접근 링크) 사용
    • 호출된 함수의 바로 바깥 함수 (즉 호출된 함수를 정의한 함수)를 가리킴
  • 접근 체인(Access chaining): 비지역변수를 찾기 위해 접근 링크를 따라감
  • 비지역변수 x의 주소 addr(x): 접근 체인에 의해 도달한 활성 레코드 주소+ 변수 x의 상대위치
  • 몇 번 접근 링크를 따라가야함?
    • 변수 x를 사용하는 함수의 중첩 레벨 - 변수 x를 선언한 함수의 중첩 레벨