함수 호출 예

(1)

7 3 함수/프로시저 구현

7.3 함수/프로시저 구현

(2)

함수 호출 구현 함수 호출 구현

함수 호출 예

fun int max (int x, int y) = if x > y then return x

else return y else return y

… c = max(a, b);

…

함수 호출 구현을 위해 필요한 사항

매개변수 전달 메커니즘

지역 변수 메모리 할당

호출자로의 반환 (return)에 필요한 반환 값 , 반환 주소 저장

피호출자 (callee)에 제어 이전

비지역 변수 접근 메커니즘

(3)

함수 호출 구현 함수 호출 구현

재귀 함수 호출 예 재귀 함수 출 예

fun int fact(int n) =

if n < 2 then return 1

else return n * fact(n-1)

…

v fact(3);

v = fact(3);

(4)

함수 반환에 필요한 사항 함수 반환에 필요한 사항

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

반환 값 저장

호출자로의 반환

(5)

함수/프로시저 구현 방법 함수/프로시저 구현 방법

컴파일러 사용 컴파일러 사용

프로그램 실행을 위한 Hardware Machine Model

레지스터, 코드, 스택, 힙

컴파일 후 기계어 코드가 실행된다 .

코드 생성

변수를 위한 기억공간 할당

지역변수, 매개변수, 전역변수, 동적변수, …

함수 호출 구현을 위한 코드 생성

인터프리터 사용

인터프리터 내에서 해석하여 실행한다 .

인터프리터 내에서 함수 호출도 구현한다 .

(6)

Simplified Machine Model Simplified Machine Model

Registers Code(Text) Registers Code(Text)

Runtime Stack

Program g Counter

Heap Environment

Pointer

Data

(7)

Memory Layout Memory Layout

Registers Program counter

Registers, Program counter

Code(Text) segment g

Machine instructions (read-only, sharable)

Stack

local(automatic) variables, temporary variables,

return address, caller's environment (registers)

Environment pointer

points to current stack position

Block entry: add new activation record to stack Block exit: remove most recent activation record

(8)

Memory Layout Memory Layout

Data segment g

Static & Global variables

Initialized data segment

e.g. int maxcount = 99; (initialized)

Uninitialized data segment

e g

long sum[1000];

e.g. long sum[1000];

Heap

dynamic memory allocation

malloc() in C, new() in Pascal, Java

(9)

어떤 실행 환경이 필요할까?

실행시간 스택 실행시간 택 (Runtime stack) ( )

스택 -기반 실행 환경

함수 호출될 때마다

새로운 활성 레코드(호출에 필요한 정보 포함)가 생성된다.

함수가 반환될 때마다

그 활성 레코드를 없앤다

그 활성 레코드를 없앤다.

Why ?

함수의 활성 레코드를 정적으로 할당할 수 없다

리커전이 가능함으로 끝나기 전에 다시 호출될 수 있다 .

새로운 활성 레코드는 함수 호출마다 생성되어야 한다

새로운 활성 레코드는 함수 호출마다 생성되어야 한다 .

(10)

활성 레코드(Activation record) 활성 레코드(Activation record)

활성 레코드 역할

_{R t} _l

활성 레코드 역할

프로시저 호출/반환에 필요한

정보를 저장하는 자료 구조 Control link Return value

스택 프레임(frame)

활성 레코드 내용

Return address Parameters

활성 레 내용

매개변수를 위한 기억공간

지역변수를 위한 기억공간 반환 주소

Local variables

_lastentry

반환 주소

반환 값

동적 링크(제어 링크)

호출자의 활성 레코드

기타…호출자의 실행 상태 정보

Environment

Pointer

(11)

Function call Function call

C t l li k max(3,5) max(3,5)

fun max(x, y) =

if x > y then return x

Control link

x 3

ep

Return addr

if x > y then return x

else return y

…

y

x 3

5

^lastentry

c = max(3,5);

(12)

Example Example

Return value

Function

fun fact(n) =

if n <= 1 then return 1 Control link

Return value

t e etu

else return n * fact(n-1)

R t l

Return address

Parameters

Return value

location to put fact(n) Local variables

Parameter

set to value of n by calling sequence

Environment sequence

Pointer

(13)

Function call Function call

fact(k)

fact(k) fun fact(n) =

if n <= 1 then return 1

Control link Return addr

k

ep

else return n * fact(n-1)

fact(k-1)

n k

lastentry

(14)

Function call/return Function call/return

fact(3) Control link

fun fact(n) =

if n <= 1 then return1

else return n * fact(n 1) fact(3) Control link

n

Return addr

3 else return n * fact(n-1)

…

c = fact(3);

Control link

fact(2) fact(2) 2

n

Return addr

2 fact(1)

Control link

R dd

fact(1) 1

ep

n

Return addr

1

lastentry

(15)

동적 링크와 정적 링크 동적 링크와 정적 링크

제어 링크 (Control link)

동적 링크(Dynamic link)

호출자의 활성레코드(바로 전 활성

레코드)에 대한 포인터 Control link

Return result

레코드)에 대한 포인터

접근 링크 (Access link)

정적 링크(Static link) Return address Access link

비지역변수 접근을 위한 포인터

호출된 프로시저의 바깥 프로시저 의 활성 레코드에 대한 포인터

Local variables Parameters

차이점

Control link depends on

dynamic behavior of program

Local variables

dynamic behavior of program

Access link depends on static form of program text

Environment Pointer

(16)

접근 링크를 이용한 정적 스코프 접근 링크를 이용한 정적 스코프

l i 1

let int x=1,

fun g(z) = return x+z,

fun f(y) = x 1

fun f(y) =

let int x = y+1 in

return g(y*x) f(3) access link control link end

in f(3)

x 4

y 3

f(3);

end z 12

g(12) control link

access link

(17)

지역 변수 접근 지역 변수 접근

지역 변수가 사용된다는 것은

이를 선언한 프로시저가 현재 호출 되어 있음을 의미한다 .

따라서 ep가 해당 프로시저의 활성 레코드를 가리키고 있다.

지역 변수의 주소

(ep) + offset

프레임 포인터가 가리키는 주소 + 상대위치

(18)

비지역 변수 접근 비지역 변수 접근

기본 아이디어

정적 링크(접근 링크)를 사용한다.

호출된 프로시저의 바로 바깥 프로시저 즉

호출된 프로시저를 선언한 프로시저를 가리킨다.

접근 체인 (access chaining)

비지역 변수를 찾기 위해 접근 링크를 따라간다

비지역 변수를 찾기 위해 접근 링크를 따라간다.

비지역 변수 x의 주소 addr(x)

접근 체인에 의해 도달한 활성 레코드 주소 + 변수 x의 상대 위치

몇 번 접근 링크를 따라 가야 하는가 ?

변수 x를 사용하는 프로시저의 중첩 레벨 변수 x를 선언한 프로시저

변수 x를 사용하는 프로시저의 중첩 레벨 – 변수 x를 선언한 프로시저 의 중첩 레벨

(19)

7 4 인터프리터에서 함수 구현

7.4 인터프리터에서 함수 구현

(20)

함수 구현: 언어 S 함수 구현 언어 S

Syntax

S → …

| let t x = E in S end

| l t f t f(t { t }) S i S d

| let fun t f(t x {,t x}) = S in S end

| return E t Æ int | bool t Æ int | bool

…

F Æ … | f(E {,E})

함수 구현

함수 선언

:

fun t f(t x {,t x}) = S

함수 호출

:

^{f(E { E})}

함수 호출

:

^{f(E {,E})}

함수 반환

:

^{return E}

(21)

예제 예제

let int a = 0, int b = 0, int c = 0, , , ,

fun int max(int x, int y) = if x > y then return x else return y in (read a;

read b;

c = max(a b);

c = max(a,b);

print c )

end

(22)

HW #5: 함수 구현 HW #5 함수 구현

함수 선언

심볼 테이블에 함수 이 과 시작 위치 저장

심볼 테이블에 함수 이름과 시작 위치 저장

인터프리터에서 함수 호출 구현

심볼 테이블을 k처럼 이용하여

심볼 테이블을 Runtime stack처럼 이용하여

활성 레코드를 구성하고

호출된 함수를 실행한다.

심볼 테이블의 엔트리

ID (매개) 변수 이름 변수 값

FUNID 함수 이름 함수 시작주소 저장

CL Control link

RA Return address

RV Return value

global.h에 상수 RETURN, FUNID, CL, RA, RV 추가

(23)

함수 선언 구현 함수 선언 구현

void stmt(void) { … switch(token)

{ …

case LET:

pc

case LET:

… if (token == FUN) //함수 선언 fun t

f(t x {,t x}) = S

{ match(FUN);

match(token); // return type if (token==ID) { // 함수 이름

loc = tokenval;

symtable[loc] token = FUNID;

symtable[loc].token = FUNID;

symtable[loc].val = pc;

} matchfun(); // 나머지 선언 부분 skip out

} …

(24)

함수 호출 구현 함수 호출 구현

함수 호출 : f(E {,E}) ( {, })

실 매개변수 값들을 계산하여 임시저장

심볼 테이블에 활성 레코드를 구성(push)하고

Return value(RV) Control link(CL) Return addr(RA)

Return value(RV), Control link(CL), Return addr(RA)

epp

lastentry

Caller’s

AR

ep

CL

RV

RA l t t

Callee’s

호출이 return되면 RV에 return 값 저장되어 있음

RA lastentry

Callee s AR

(25)

함수 호출 구현 함수 호출 구현

int factor(void)

{ int args[10], funstart;

…

else if (token == FUNID)

{ …

loc = tokenval;

funstart = symtable[loc].val; // 함수 시작 위치 token = getToken();

if (token ‘(‘) // 함수 호출 f(E { E}) if (token == ( ) // 함수 호출 f(E {,E}) { match(‘(‘);

args[ ] Å 실매개변수 값 계산;

/* i i d(RV CL RA) i bl

/* setup activation record(RV, CL, RA) in symtable symtable[++lastentry].token = RV;

symtable[lastentry].lexptr = “RV”;

CL 엔트리 Å ep // p control link 저장

ep = lastentry; // ep -> 새로운 AR RA 엔트리 Å pc; // return address 저장

(26)

호출된 함수 실행 호출된 함수 실행

해당 함수의 시작 위치로 GOTO ^funstart

pc = funstart;

token = getToken(); f(t x {,t x}) = S

호출된 함수 실행

형식 매개변수들을 위한 기억공간 할당하고

실 매개변수 값들을 형식 매개변수에 복사

함수 본체 S 실행

ep

CL

RV RA RA

Parameters lastentry

(27)

함수 실행 후 함수 실행 후

심볼 테이블에서 활성 레코드를 제거(pop)하고

return address로 되돌아 간다.

lastentry = ep -1 // pop AR

ep Å CL 값 // caller’s ep

ep Å CL 값 // caller s ep

pc Å RA // 활성 레코드에 저장된 RA로 GOTO

결과 값 (RV) 리턴

ep

Caller’s

CL

RV lastentry

Caller s AR

CL

Callee’s

RA

AR

(28)

함수 호출 구현 함수 호출 구현

/* GOTO (t x {,t x}) = S */

pc = funstart // goto callee; 함수 이름에 저장된 시작 위치 token = getToken();

match(‘(‘);

/* set up formal parameters and pass actual parameters */

while (token == INT || token == BOOL) {

… // 형식 매개변수 엔트리 Å 실매개변수 값;

}}match(‘)’);

match(‘=‘);

stmt(); // 함수 본체 실행 /* return */

lastentry = ep – 1; // pop AR

ep Å CL 값; // p ep -> caller’s ARp pc = symtable[…].val; // return address 회복

token = getToken();

result = symtable[lastentry].val; // RV 값 return result;

return result;

}

(29)

함수 반환 구현 함수 반환 구현

함수 반환 : return E

E 값 계산

RV Å E 값 // AR 내의 Return value에 E 값 저장

(30)

 함수 호출 예

7 3 함수/프로시저 구현

7.3 함수/프로시저 구현

함수 호출 구현 함수 호출 구현

 함수 호출 예

fun int max (int x, int y) = if x > y then return x

else return y else return y

… c = max(a, b);

…

 함수 호출 구현을 위해 필요한 사항

 함수 호출 구현을 위해 필요한 사항

매개변수 전달 메커니즘

지역 변수 메모리 할당

호출자로의 반환 (return)에 필요한 반환 값 , 반환 주소 저장

피호출자 (callee)에 제어 이전

비지역 변수 접근 메커니즘

비지역 변수 접근 메커니즘

함수 호출 구현 함수 호출 구현

 재귀 함수 호출 예 재귀 함수 출 예

fun int fact(int n) =

if n < 2 then return 1

else return n * fact(n-1)

…

v fact(3);

v = fact(3);

함수 반환에 필요한 사항 함수 반환에 필요한 사항

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

 반환 값 저장

 호출자로의 반환

함수/프로시저 구현 방법 함수/프로시저 구현 방법

 컴파일러 사용 컴파일러 사용

프로그램 실행을 위한 Hardware Machine Model

컴파일 후 기계어 코드가 실행된다 .

 인터프리터 사용

인터프리터 내에서 해석하여 실행한다 .

인터프리터 내에서 해석하여 실행한다 .

인터프리터 내에서 함수 호출도 구현한다 .

Simplified Machine Model Simplified Machine Model

Registers Code(Text) Registers Code(Text)

Runtime Stack

Program g Counter

Heap Environment

Pointer

Data

Data

Memory Layout Memory Layout

 Registers Program counter

 Registers, Program counter

 Code(Text) segment g

Machine instructions (read-only, sharable)

 Stack

 Stack

local(automatic) variables, temporary variables,

return address, caller's environment (registers)

 Environment pointer

points to current stack position

points to current stack position

Memory Layout Memory Layout

 Data segment g

Static & Global variables

Initialized data segment

Uninitialized data segment

long sum[1000];

 Heap

dynamic memory allocation

malloc() in C, new() in Pascal, Java

어떤 실행 환경이 필요할까?

어떤 실행 환경이 필요할까?

 실행시간 스택 실행시간 택 (Runtime stack) ( )

스택 -기반 실행 환경

함수 호출될 때마다

함수가 반환될 때마다

 Why ?

함수의 활성 레코드를 정적으로 할당할 수 없다

리커전이 가능함으로 끝나기 전에 다시 호출될 수 있다 .

새로운 활성 레코드는 함수 호출마다 생성되어야 한다

새로운 활성 레코드는 함수 호출마다 생성되어야 한다 .

활성 레코드(Activation record) 활성 레코드(Activation record)

 활성 레코드 역할

 활성 레코드 역할

함수 호출 예

함수 호출 예

함수 호출 구현을 위해 필요한 사항

함수 호출 구현을 위해 필요한 사항

재귀 함수 호출 예 재귀 함수 출 예

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

반환 값 저장

호출자로의 반환

컴파일러 사용 컴파일러 사용

인터프리터 사용

Registers Program counter

Registers, Program counter

Code(Text) segment g

Stack

Stack

Environment pointer

Data segment g

Heap

실행시간 스택 실행시간 택 (Runtime stack) ( )

Why ?

활성 레코드 역할

활성 레코드 역할

활성 레코드 내용

_lastentry

^lastentry

Function

R t l

Return value

Parameter

제어 링크 (Control link)

제어 링크 (Control link)

접근 링크 (Access link)

차이점

지역 변수 접근 지역 변수 접근

지역 변수의 주소

지역 변수의 주소

기본 아이디어

접근 체인 (access chaining)

비지역 변수 x의 주소 addr(x)

몇 번 접근 링크를 따라 가야 하는가 ?

Syntax

함수 구현