7.1 함수 정의 7.2 매개변수 전달 7.3 함수 구현 7.4 인터프리터에서 함수 구현 Reading Chap 8 제7장 함수 구현 7.1 함수 정의 7.2 매개변수 전달 7.3 함수 구현 7.4 인터프리터에서 함수 구현 Reading Chap 8 ©숙대 창병모

7.1 함수 정의 및 호출 ©숙대 창병모

프로시저/함수? 프로시저(Procedure) 함수(Function) 한 그룹의 계산과정을 추상화하는 메커니즘으로 반환 값 없으며 매개변수나 비지역 변수를 변경한다. 함수(Function) 반환 값이 있으므로 식에 나타날 수 있고 매개변수나 비지역 변수 값 변경은 선택사항 © 숙대 창병모

프로시저/함수 선언 헤더(Header) 본체(Body) 선언 예 in S in C 호출 예 명세 혹은 인터페이스(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; } © 숙대 창병모

함수 선언 선언 예 호출 예 int max (int x, int y) { return x > y ? x : y; } 호출 예 c = max(a, b); fun int max (int x, int y) : if x > y then return x else return y © 숙대 창병모

사례 연구 C, C++, Java, S Ada Modula-2 오직 함수만 있고 프로시져는 반환 타입이 void 이다. procedure 와 function를 구분한다. Modula-2 모두 프로시저이다. 함수는 반환 값이 있는 프로시저이다. © 숙대 창병모

7.2 매개변수 전달 ©숙대 창병모

매개변수 전달 실 매개변수(Actual parameter) 형식 매개변수(Formal parameter) 매개변수 전달 호출에서 사용된 매개변수로 인자(argument)라고도 한다. 형식 매개변수(Formal parameter) 선언에서 사용된 매개변수 매개변수 전달 호출 시에 실 매개변수와 형식 매개변수를 매칭하는 것 © 숙대 창병모

매개변수 전달 방법 값 전달(pass by value) 참조 전달(pass by reference) 값-결과 전달(pass by value-result) 이름 전달(pass by name) © 숙대 창병모

값 전달(pass by value) 값 전달 과정 호출 예 1. 식(expression)인 실 매개변수 값들을 계산한다. 2. 계산된 값들을 대응되는 형식 매개변수에 전달 (복사 혹은 초기화)한다. 3. 본체를 실행한다. 호출 예 max(10, 2 + 3); x = 10; y = 5; // 값 전달 if x > y then return x else return y // 본체 실행 및 반환 © 숙대 창병모

값 전달의 문제점 ? intswap(a,b) © 숙대 창병모

참조 전달 참조 전달 방법 형식 매개변수 사용 실 매개변수와 형식 매개변수의 이명(aliasing) 실 매개변수의 위치(주소)가 계산되어 형식 매개변수에 전달된다. 따라서 실 매개변수는 할당된 위치가 있는 변수이어야 한다. 형식 매개변수 사용 자동 주소 참조(dereferencing)가 이루어져 실 매개변수를 접근 형식 매개변수를 변경하면 자동적으로 실 매개변수가 변경된다. 실 매개변수와 형식 매개변수의 이명(aliasing) © 숙대 창병모

참조 전달 예(C++) 선언 사용 void intswap(int& x, int& y) // 명세 { // 본체 { // 본체 int t = x; x = y; y = t; } 사용 intswap(a, b); © 숙대 창병모

C에서 참조 전달 효과 내기 기본 아이디어 사실상 프로그래머가 참조전달을 구현한다. 참조전달 효과 포인터 값(위치/주소)을 명시적으로 전달하여 낼 수 있다. 주소 참조(dereferencing) 함수 내에서 주소참조는 프로그래머가 명시적으로 해야 한다. 사실상 프로그래머가 참조전달을 구현한다. © 숙대 창병모

예제 intswap의 C 버전 사용 void intswap(int *px; int *py) { int t; t = *px; *px = *py; *py = t; } 사용 int a, b; intswap(&a, &b); © 숙대 창병모

예제(C++) int a; void ack(int& x, int& y) { x = 2; a = 4; y = 3; } . . . ack(a, a); © 숙대 창병모

참조 전달의 문제점 ? © 숙대 창병모

값-결과 전달 기본 아이디어 참조 전달과 뭐가 다른가 ? 호출할 때 반환할 때 copy-in, copy-out이라고도 한다. 실 매개변수 값은 형식 매개변수에 전달(복사) 한다. 반환할 때 형식 매개변수 값을 실 매개변수에 역으로 전달(복사) 한다. copy-in, copy-out이라고도 한다. 참조 전달과 뭐가 다른가 ? © 숙대 창병모

값-결과 전달: 예제 선언 사용 void intswap(int x, int y) // 명세 { // 본체 int t = x; { // 본체 int t = x; x = y; y = t; } 사용 intswap(a, b); © 숙대 창병모

값-결과 전달: 예제 void p(int x, int y) { x++; y++; } main() int a = 1; p(a,a); … © 숙대 창병모

이름 전달 기본 아이디어 방법 1 방법 2 함수형 언어의 지연 계산(delayed evaluation)에서 사용된다. 게으른 계산 ! 사용될 때까지 버틴다. 방법 1 실 매개변수는 대응 형식 매개변수가 사용될 때까지 계산되지 않고 형식 매개변수가 사용될 때 비로소 계산된다. 방법 2 형식 매개변수를 실 매개변수 이름으로 대치하고 실행한다고 생각할 수 있다. 함수형 언어의 지연 계산(delayed evaluation)에서 사용된다. © 숙대 창병모

이름 전달: 예제 int i; int a[10]; void p(x) { i = i + 1; x = x + 1; } main() p(a[i]); © 숙대 창병모

이름 전달: 예제 선언 사용 void intswap(int x, int y) // 명세 { // 본체 int t = x; { // 본체 int t = x; x = y; y = t; } 사용 intswap(a, b); intswap(i, a[i]); © 숙대 창병모

사례 연구 Ada C C++, Pascal, Modula-2 Java FORTRAN in 매개변수: 값 전달 in out 매개변수: 값-결과 전달 C 값 전달 포인터를 이용한 참조 전달 효과 C++, Pascal, Modula-2 참조 전달 Java 기초 타입(primitive type)은 값 전달 객체는 참조 전달 FORTRAN © 숙대 창병모

7.3 함수/프로시저 구현 ©숙대 창병모

함수 호출 구현 함수 호출 예 함수 호출 구현을 위해 필요한 사항 fun int max (int x, int y) : if x > y then return x else return y … c = max(a, b); 함수 호출 구현을 위해 필요한 사항 매개변수 전달 메커니즘 지역 변수 메모리 할당 호출자로의 반환에 필요한 반환 값, 반환 주소 저장 피호출자(callee)에 제어 이전 비지역 변수 접근 메커니즘 © 숙대 창병모

함수 호출 구현 재귀 함수 호출 예 fun int fact(int n) : if n <= 1 then return 1 else return n * fact(n-1) … v = fact(3); © 숙대 창병모

함수 반환에 필요한 사항 지역 변수, 매개변수 등을 위한 기억공간 해제 반환 값 저장 호출자로의 반환 © 숙대 창병모

함수/프로시저 구현 방법 컴파일러 사용 인터프리터 사용 프로그램 실행을 위한 Hardware Machine Model 레지스터, 코드, 스택, 힙 컴파일 후 기계어 코드가 실행된다. 코드 생성 변수를 위한 기억공간 할당 지역변수, 매개변수, 전역변수, 동적변수, … 함수 호출 구현을 위한 코드 생성 인터프리터 사용 인터프리터 내에서 해석하여 실행한다. 인터프리터 내에서 함수 호출도 구현한다. © 숙대 창병모

Simplified Machine Model Registers Code(Text) Runtime Stack Program Counter Heap Environment Pointer Data © 숙대 창병모

Memory Layout Registers, Program counter Code(Text) segment Stack 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 © 숙대 창병모

Memory Layout Data segment Heap Static & Global variables Initialized data segment e.g. int maxcount = 99; (initialized) Uninitialized data segment e.g. long sum[1000]; Heap dynamic memory allocation malloc() in C, new() in Pascal, Java © 숙대 창병모

어떤 실행 환경이 필요할까? 실행시간 스택(Runtime stack) Why ? 스택-기반 실행 환경 함수 호출될 때마다 새로운 활성 레코드(호출에 필요한 정보 포함)가 생성된다. 함수가 끝날(반환될) 때마다 그 활성 레코드를 없앤다. Why ? 함수의 활성 레코드를 정적으로 할당할 수 없다 리커전이 가능함으로 끝나기 전에 다시 호출될 수 있다. 새로운 활성 레코드는 함수 호출마다 생성되어야 한다. © 숙대 창병모

활성 레코드(Activation record) 활성 레코드 역할 프로시저 호출/반환에 필요한 정보를 저장하는 자료 구조 스택 프레임(frame) 활성 레코드 내용 매개변수를 위한 기억공간 지역변수를 위한 기억공간 반환 주소 반환 값 동적 링크(제어 링크) 호출자의 활성 레코드 기타…호출자의 실행 상태 정보 Return value Control link Return address Parameters Local variables Environment Pointer © 숙대 창병모

Example Function Return value Parameter Return value fun fact(n) : if n <= 1 then return 1 else return n * fact(n-1) Return value location to put fact(n) Parameter set to value of n by calling sequence Control link Return address Parameters Local variables Environment Pointer © 숙대 창병모

Function call fun max(x, y) : if x > y then return x else return y Control link fun max(x, y) : if x > y then return x else return y Return addr x 3 y 5 Environment Pointer © 숙대 창병모

Function call fact(k) fact(k) Control link fun fact(n) : if n <= 1 then return 1 else return n * fact(n-1) Return addr n k fact(k-1) Environment Pointer © 숙대 창병모

Function call/return fact(3) Control link fact(2) n Return addr 3 fun fact(n) : if n <= 1 then return1 else return n * fact(n-1) 2 Control link fact(1) n Return addr 2 fact(2) 1 fact(1) Control link Return addr n 1 © 숙대 창병모

동적 링크, 정적 링크 ©숙대 창병모

동적 링크와 정적 링크 제어 링크(Control link) 접근 링크(Access link) Return result 동적 링크(Dynamic link) 호출 관계 호출자의 활성레코드(바로 전 활성레코드)에 대한 포인터 접근 링크(Access link) 정적 링크(Static link) 정적 스코프(Static scope) 구현 프로그램 텍스트의 포함 관계 호출된 함수의 바깥 함수의 활성 레코드에 대한 포인터 비지역변수 접근을 위한 포인터 Return result Control link Access link Return address Parameters Local variables Environment Pointer © 숙대 창병모

접근 링크를 이용한 정적 스코프 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); x 1 x 4 y 3 f(3) access link control link z 12 g(12) control link access link © 숙대 창병모

지역 변수 접근 지역 변수 접근 지역 변수의 주소 지역 변수가 사용된다는 것은 이를 선언한 프로시저가 현재 호출 되어 있음을 의미한다. 따라서 ep가 해당 프로시저의 활성 레코드를 가리키고 있다. 지역 변수의 주소 (ep) + offset 프레임 포인터가 가리키는 주소 + 상대위치 © 숙대 창병모

비지역 변수 접근 기본 아이디어 접근 체인(access chaining) 비지역 변수 x의 주소 addr(x) 정적 링크(접근 링크)를 사용한다. 호출된 프로시저의 바로 바깥 프로시저 즉 호출된 프로시저를 선언한 프로시저를 가리킨다. 접근 체인(access chaining) 비지역 변수를 찾기 위해 접근 링크를 따라간다. 비지역 변수 x의 주소 addr(x) 접근 체인에 의해 도달한 활성 레코드 주소 + 변수 x의 상대 위치 몇 번 접근 링크를 따라 가야 하는가 ? 변수 x를 사용하는 프로시저의 중첩 레벨 – 변수 x를 선언한 프로시저의 중첩 레벨 © 숙대 창병모

7.4 인터프리터에서 함수 구현 ©숙대 창병모

함수 구현: 언어 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 © 숙대 창병모 © 숙대 창병모 45

예제 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); print c end © 숙대 창병모

HW #5: 함수 구현 함수 선언 인터프리터에서 함수 호출 구현 심볼 테이블의 엔트리 심볼 테이블에 함수 이름과 시작 위치 저장 인터프리터에서 함수 호출 구현 심볼 테이블을 Runtime stack처럼 이용하여 활성 레코드를 구성하고 호출된 함수를 실행한다. 심볼 테이블의 엔트리 ID (매개) 변수 이름 변수 값 FUNID 함수 이름 함수 시작주소 저장 CL Control link RA Return address RV Return value global.h에 상수 FUNID, CL, RA, RV 추가 © 숙대 창병모

함수 선언 구현 void stmt(void) { … switch(token) { … case LET: { … switch(token) { … 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].val = pc; // 현재 위치 pc 값 matchfun(); // 나머지 선언 부분 skip } © 숙대 창병모 48

함수 호출 구현 함수 호출: f(E {,E}) 호출된 함수 실행: T f(T x {,T x}): S 심볼 테이블에 활성 레코드를 구성(push)하고 Return value(RV), Control link(CL), Return addr(RA) 실 매개변수 값들을 계산하여 임시저장 해당 함수의 시작 위치로 GOTO 호출이 return되면 RV에 return 값 저장되어 있음 호출된 함수 실행: T f(T x {,T x}): S 계속해서 형식 매개변수들을 위한 기억공간 할당하고 실 매개변수 값들을 형식 매개변수에 복사 함수 본체 S 실행 ep Control link Return value Local variables Return address Parameters lastentry © 숙대 창병모

함수 호출 구현 int factor(void) Return value { … { … if (token == FUNID) // 함수 호출 f(E {,E}) { loc = tokenval; funstart = symtable[loc].val; // 함수 시작 위치 token = getToken(); if (token == ‘(‘) // 실매개변수 계산 { match(‘(‘); 실매개변수 계산하여 임시저장; } // set up activation record symtable에 RV, CL 엔트리를 만든다; CL 엔트리  현재 ep 값 // control link 저장 ep 값 갱신 // 새로운 AR 가리키도록 symtable에 RA 엔트리를 만든다; RA 엔트리  현재 pc 값; // return address 저장 match(‘)’); ep Control link Return value Local variables Return address Parameters lastentry © 숙대 창병모

함수 호출 구현 // GOTO (T x {,T x}) : S pc = result; // 함수 시작 위치 값(result); token = getToken(); match(‘(‘); 형식 매개변수를 위한 엔트리 생성; 형식 매개변수 엔트리  실매개변수 값; // 매개변수 전달 match(‘)‘); match(‘:’); stmt( ); // 호출된 함수의 본체 문장 실행 // 내부에서 return 문 실행 // pop AR pc = symtable[ep+1].val // return address 회복 lastentry = ep – 1; ep = symtable[ep].val; // ep -> caller’s AR result = symtable[lastentry].val; // RV 값 return result; } © 숙대 창병모

함수 반환 구현 함수 반환: return E E 값 계산 심볼 테이블 RA 엔트리에 값 저장 © 숙대 창병모 52

함수 반환 구현 void stmt(void) { … switch(token) case RETURN: // return E match(RETURN); result = expr(); // 반환 값 계산 symtable[ep-1].val = result; // RV 엔트리에 값 저장(반환) break; } © 숙대 창병모