제 7 장함수구현 7.1 함수정의 7.2 매개변수전달 7.3 함수구현 7.4 인터프리터에서함수구현 Reading Chap 8 숙대창병모 Nov. 2007 1
7.1 함수정의및호출 숙대창병모 Nov. 2007 2
프로시저 / 함수? 프로시저 (Procedure) 한그룹의계산과정을추상화하는메커니즘으로반환값없으며 매개변수나비지역변수를변경한다. 함수 (Function) 반환값이있으므로식에나타날수있고매개변수나비지역변수값변경은선택사항 숙대창병모 Oct. 2007 3
프로시저 / 함수선언 헤더 (Header) 명세혹은인터페이스 (Specification or Interface) 프로시저이름, 매개변수들의타입과이름 반환타입 ( 함수의경우 ) 본체 (Body) 선언예 in S in C fun void intswap(int x, int y) => let int t = x in ( x = y; y = t ) end 호출예 intswap(a, b); void intswap(int x, int y) { int t; t = x; x = y; y = t; } 숙대창병모 Oct. 2007 4
함수선언 선언예 int max (int x, int y) { return x > y? x : y; } fun int max (int x, int y) => if x > y then return x else return y 호출예 c = max(a, b); 숙대창병모 Oct. 2007 5
사례연구 C, C++, Java, S 오직함수만있고 프로시져는반환타입이 void 이다. Ada procedure 와 function 를구분한다. Modula-2 모두프로시저이다. 함수는반환값이있는프로시저이다. 숙대창병모 Oct. 2007 6
7.2 매개변수전달 숙대창병모 Nov. 2007 7
매개변수전달 실매개변수 (Actual parameter) 호출에서사용된매개변수로 인자 (argument) 라고도한다. 형식매개변수 (Formal parameter) 선언에서사용된매개변수 매개변수전달 호출시에실매개변수와형식매개변수를매칭하는것 숙대창병모 Oct. 2007 8
매개변수전달방법 값전달 (pass by value) 참조전달 (pass by reference) 값-결과전달 (pass by value-result) 이름전달 (pass by name) 숙대창병모 Oct. 2007 9
값전달 (pass by value) 값전달과정 1. 식 (expression) 인실매개변수값들을계산한다. 2. 계산된값들을대응되는형식매개변수에전달 ( 복사혹은초기화 ) 한다. 3. 본체를실행한다. 호출예 max(10, 2 + 3); x = 10; y = 5; // 값전달 if x > y then return x else return y // 본체실행및반환 숙대창병모 Oct. 2007 10
intswap(a,b) 값전달의문제점? 숙대창병모 Oct. 2007 11
참조전달 참조전달방법 실매개변수의위치 ( 주소 ) 가계산되어형식매개변수에전달된다. 따라서실매개변수는할당된위치가있는변수이어야한다. 형식매개변수사용 자동주소참조 (dereferencing) 가이루어져실매개변수를접근 형식매개변수를변경하면자동적으로실매개변수가변경된다. 실매개변수와형식매개변수의이명 (aliasing) 숙대창병모 Oct. 2007 12
참조전달예 (C++) 선언 void intswap(int& x, int& y) // 명세 { // 몸체 int t = x; x = y; y = t; } 사용 intswap(a, b); 숙대창병모 Oct. 2007 13
C 에서참조전달효과내기 기본아이디어 C 는원칙적으로값전달만제공하나포인터타입이있다. 참조전달효과 포인터값 ( 위치 / 주소 ) 을명시적으로전달하여낼수있다. 주소참조 (dereferencing) 함수내에서주소참조는프로그래머가명시적으로해야한다. 사실상프로그래머가참조전달을구현한다. 숙대창병모 Oct. 2007 14
예제 intswap 의 C 버전 void intswap(int *px; int *py) { int t; t = *px; *px = *py; *py = t; } 사용 int a, b; intswap(&a, &b); 숙대창병모 Oct. 2007 15
예제 (C++) int a; void ack(int& x, int& y) { x = 2; a = 4; y = 3; }... ack(a, a); 숙대창병모 Oct. 2007 16
참조전달의문제점? 숙대창병모 Oct. 2007 17
값 - 결과전달 기본아이디어 호출할때 실매개변수값은형식매개변수에전달 ( 복사 ) 한다. 반환할때 형식매개변수값을실매개변수에역으로전달 ( 복사 ) 한다. copy-in, copy-out 이라고도한다. 참조전달과뭐가다른가? 숙대창병모 Oct. 2007 18
예제 void p(int x, int y) { x++; y++; } main() { int a = 1; p(a,a); } 숙대창병모 Oct. 2007 19
이름전달 기본아이디어 게으른계산! 사용될때까지버틴다. 방법 1 실매개변수는대응형식매개변수가사용될때까지계산되지않고 형식매개변수가사용될때비로소계산된다. 방법 2 형식매개변수를실매개변수이름으로대치하고실행한다고생각할수있다. 함수형언어의지연계산 (delayed evaluation) 에서사용된다. 숙대창병모 Oct. 2007 20
예제 int i; int a[10]; void p(x) { i = i + 1; x = x + 1; } main() { i = 1; a[1] = 10; a[2] = 20; p(a[i]); } 숙대창병모 Oct. 2007 21
intswap(i, a[i]); 이름전달의문제점? 숙대창병모 Oct. 2007 22
사례연구 Ada in 매개변수 : 값전달 in out 매개변수 : 값-결과전달 C 값전달포인터를이용한참조전달효과 C++, Pascal, Modula-2 값전달참조전달 Java 기초타입 (primitive type) 은값전달 객체는참조전달 FORTRAN 참조전달 숙대창병모 Oct. 2007 23
7.3 함수 / 프로시저구현 숙대창병모 Nov. 2007 24
함수호출예 fun int max (int x, int y) => if x > y then return x else return y c = max(a, b); 함수호출구현 함수호출구현을위해필요한사항 매개변수전달메커니즘지역변수메모리할당호출자로의반환에필요한반환값, 반환주소저장피호출자 (callee) 에제어이전비지역변수접근메커니즘 숙대창병모 Oct. 2007 25
함수호출구현 재귀함수호출예 fun int fact(int n) => if n <= 1 then return 1 else return n * fact(n-1) v = fact(3); 숙대창병모 Oct. 2007 26
함수반환에필요한사항 지역변수, 매개변수등을위한기억공간해제 반환값저장 호출자로의반환 숙대창병모 Oct. 2007 27
함수 / 프로시저구현방법 컴파일러사용 프로그램실행을위한 Hardware Machine Model 레지스터, 코드, 스택, 힙 컴파일후기계어코드가실행된다. 코드생성변수를위한기억공간할당 인터프리터사용 지역변수, 매개변수, 전역변수, 동적변수, 함수호출구현을위한코드생성 인터프리터내에서해석하여실행한다. 인터프리터내에서함수호출도구현한다. 숙대창병모 Oct. 2007 28
Simplified Machine Model Registers Code(Text) Runtime Stack Program Counter Environment Pointer Data Heap 숙대창병모 Oct. 2007 29
Memory Layout Registers, Program counter Code(Text) segment Stack Machine instructions (read-only, sharable) 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 숙대창병모 Oct. 2007 30
Memory Layout Data segment Static & Global variables Initialized data segment e.g. intmaxcount= 99; (initialized) Uninitialized data segment Heap e.g. long sum[1000]; dynamic memory allocation malloc() in C, new() in Pascal, Java 숙대창병모 Oct. 2007 31
어떤실행환경이필요할까? 실행시간스택 (Runtime stack) 스택-기반실행환경함수호출될때마다 새로운활성레코드 ( 호출에필요한정보포함 ) 가생성된다. 함수가끝날 ( 반환될 ) 때마다 그활성레코드를없앤다. Why? 함수의활성레코드를정적으로할당할수없다 리커전이가능함으로끝나기전에다시호출될수있다. 새로운활성레코드는함수호출마다생성되어야한다. 숙대창병모 Oct. 2007 32
활성레코드 (Activation record) 활성레코드역할 프로시저호출 / 반환에필요한정보를저장하는자료구조스택프레임 (frame) 활성레코드내용 매개변수를위한기억공간지역변수를위한기억공간반환주소반환값 동적링크 ( 제어링크 ) 호출자의활성레코드 기타 호출자의실행상태정보 Return value Control link Return address Parameters Local variables Environment Pointer 숙대창병모 Oct. 2007 33
Example Return value Control link Return address Parameters Local variables Function fun fact(n) => if n <= 1 then return 1 else return n * fact(n-1) Return value location to put fact(n) Environment Pointer Parameter set to value of n by calling sequence 숙대창병모 Oct. 2007 34
Function call max(3,5) max(3,5) Control link fun max(x, y) => if x > y then return x else return y Return addr x 3 y 5 Environment Pointer 숙대창병모 Oct. 2007 35
Function call fact(k) fun fact(n) => if n <= 1 then return 1 else return n * fact(n-1) fact(k) Control link Return addr n fact(k-1) k Environment Pointer 숙대창병모 Oct. 2007 36
Function call/return fact(3) Control link Return addr n fact(2) 3 2 fun fact(n) => if n <= 1 then return1 else return n * fact(n-1) fact(2) Control link Return addr n 2 fact(1) 1 fact(1) Control link Return addr n 1 숙대창병모 Oct. 2007 37
동적링크와정적링크 제어링크 (Control link) 동적링크 (Dynamic link) 호출자의활성레코드 ( 바로전활성레코드 ) 에대한포인터 접근링크 (Access link) 정적링크 (Static link) 비지역변수접근을위한포인터 호출된프로시저의바깥프로시저의활성레코드에대한포인터 차이점 Control link depends on dynamic behavior of program Access link depends on static form of program text Return result Control link Access link Return address Parameters Local variables Environment Pointer 숙대창병모 Oct. 2007 38
접근링크를이용한정적스코프 let int x=1, fun g(z) => return x+z, fun f(y) => let int x = y+1 in return g(y*x) end in f(3); end f(3) g(12) x 1 control link access link y 3 x 4 control link access link z 12 숙대창병모 Oct. 2007 39
지역변수접근 지역변수접근 지역변수가사용된다는것은 이를선언한프로시저가현재호출되어있음을의미한다. 따라서 ep가해당프로시저의활성레코드를가리키고있다. 지역변수의주소 (ep) + offset 프레임포인터가가리키는주소 + 상대위치 숙대창병모 Oct. 2007 40
비지역변수접근 기본아이디어 정적링크 ( 접근링크 ) 를사용한다. 호출된프로시저의바로바깥프로시저즉 호출된프로시저를선언한프로시저를가리킨다. 접근체인 (access chaining) 비지역변수를찾기위해접근링크를따라간다. 비지역변수 x의주소addr(x) 접근체인에의해도달한활성레코드주소 + 변수 x의상대위치 몇번접근링크를따라가야하는가? 변수 x를사용하는프로시저의중첩레벨 변수 x를선언한프로시저의중첩레벨 숙대창병모 Oct. 2007 41
7.4 인터프리터에서함수구현 숙대창병모 Nov. 2007 42
함수구현 : 언어 S Syntax S let t x = E in S end let fun t f(t x {,t x}) => S in S end return E t int bool void F f(e {,E}) 함수구현 함수선언 : fun t f(t x {,t x}) => S 함수호출 : f(e {,E}) 함수반환 : return E 숙대창병모 Oct. 2007 43
예제 let inta = 0, intb = 0, intc = 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); print c ) end 숙대창병모 Oct. 2007 44
HW #6: 함수구현 함수선언 심볼테이블에함수이름과시작위치저장 인터프리터에서함수호출구현 심볼테이블을 Runtime stack처럼이용하여 활성레코드를구성하고 호출된함수를실행한다. 심볼테이블의엔트리 ID ( 매개 ) 변수이름변수값 FUNID 함수이름 함수시작주소저장 CL Control link RA Return address RV Return value global.h 에상수 FUNID, CL, RA, RV 추가 숙대창병모 Oct. 2007 45
void stmt(void) { switch(token) { case LET: } } 함수선언구현 if (token = FUN) // 함수선언 fun t f(t x {,t x}) => S { match(fun); } match(id); if (token==id) { } // return type // 함수이름 loc = tokenval; symtable[loc].token = FUNID; symtable[loc].val 현재위치 i값 match(id); // 나머지선언부분 skip out 숙대창병모 Oct. 2007 46
함수호출구현 함수호출 : f(e {,E}) 심볼테이블에활성레코드를구성 (push) 하고 Return value(rv), Control link(cl), Return addr(ra) 실매개변수값들을계산하고해당함수의시작위치로GOTO 호출이 return되면 RV에 return 값저장되어있음 호출된함수실행 : t f(t x {,t x}) => S 계속해서형식매개변수들을위한기억공간할당하고실매개변수값들을형식매개변수에복사함수본체 S 실행 숙대창병모 Oct. 2007 47
함수호출구현 int factor(void) { else if (token == FUNID) { loc = tokenval; result = symtable[loc].val; // 함수시작위치 token = gettoken(); if (token == ( ) // 함수호출 f(e {,E}) { match( ( ); 실매개변수계산 ; symtable에 RV, CL, RA 엔트리를만든다 ; CL 엔트리 현재 ep 값 RA 엔트리 현재 i 값 ; match( ) ); // control link 저장 // return address 저장 } } } // GOTO (t x {,t x}) => S i 함수이름에저장된시작위치값 (result); 형식매개변수를위한엔트리생성 ; 형식매개변수엔트리 실매개변수값 ; 호출된함수의본체문장실행 stmt(); result = symtable[lastentry].val; return result; // 매개변수전달 // RV 값 숙대창병모 Oct. 2007 48
함수반환구현 함수반환 : return E E 값계산 ep Control Link(CL) 값 // caller s ep Return Value(RV) E 값 심볼테이블에서활성레코드를제거 (pop) 한다. 활성레코드에저장된 Return Addr(RA) 로 GOTO 숙대창병모 Oct. 2007 49
함수반환구현 void stmt(void) { switch(token) { case RETURN: // return E match(return); expr 값계산 ; // 반환값계산 ep CL 값 ; // ep -> caller s AR i RA 값 ; // return address 회복 CL, RA, 형식매개변수엔트리 pop; // pop AR symtable[lastentry].val expr 값 ; // RV 엔트리에값저장 ( 반환 ) break; } } 숙대창병모 Oct. 2007 50