프로그래밍언어론 2nd edition Tucker and Noonan

Presentation on theme: "프로그래밍언어론 2nd edition Tucker and Noonan"— Presentation transcript:

1 프로그래밍언어론 2nd edition Tucker and Noonan
10장 함수의 구현 “이론적으로 이론과 실제의 차이는 없다. 그러나 실제로는 그렇지 않다.”  작자미상

2 목차 10.1 Clite에서의 함수의 선언과 호출 10.2 Clite 타입 체계의 완성 10.3 함수 호출과 복귀의 의미구조
10.4 타입과 의미구조의 정형적인 표현

3 10.1 함수의 선언과 호출 Clite 예제 프로그램 그림 10.1 int h, i; void B(int w) {
10.1 함수의 선언과 호출 int h, i; void B(int w) { int j, k; i = 2*w; w = w+1; } void A(int x, int y) { bool i, j; B(h); int main() { int a, b; h = 5; a = 3; b = 2; A(a, b); Clite 예제 프로그램 그림 10.1

4 10.1.1 구체 구문구조 함수와 전역 변수 (새로 추가된 요소는 밑줄 표시)
구체 구문구조 함수와 전역 변수 (새로 추가된 요소는 밑줄 표시) Program  { Type Identifier FunctionOrGlobal } MainFunction Type  int | boolean | float | char | void FunctionOrGlobal  ( Parameters ) { Declarations Statements } | Global Parameters  [ Parameter { , Parameter } ] Global  { , Identifier } ; MainFunction  int main ( ) { Declarations Statements }

5 구체 구문구조 (계속) 함수 호출 (새로 추가된 요소는 밑줄 표시)
Statement  ; | Block | Assignment | IfStatement | WhileStatement | CallStatement | ReturnStatement CallStatement  Call ; ReturnStatement  return Expression ; Factor  Identifier | Literal | ( Expression ) | Call Call  Identifier ( Arguments ) Arguments  [ Expression { , Expression } ]

6 10.1.2 추상 구문구조 Program = Declarations globals; Functions functions
추상 구문구조 Program = Declarations globals; Functions functions Functions = Function* Function = Type t; String id; Declarations params, locals; Block body Type = int | boolean | float | char | void Statement = Skip | Block | Assignment | Conditional | Loop | Call | Return Call = String name; Expressions args Expressions = Expression* Return = Variable target; Expression result Expression = Variable | Value | Binary | Unary | Call

7 Clite 프로그램을 위한 추상 구문구조 개요 Fig 10.4
Program Clite 프로그램을 위한 추상 구문구조 개요 Fig 10.4 globals body Declarations Functions Function h i int main Function Call void A a b A(a,b); Function x y i j void B params locals body Block w j k i = 2 * w; w = w + 1;

8 10.2 Cliet 타입 체계의 완성 타입 규칙 10.1 모든 함수와 전역적인 식별자는 유일해야 한다.
타입 규칙 모든 함수와 전역적인 식별자는 유일해야 한다. 예) h, i, A, B, main 은 유일 타입 규칙 모든 함수의 매개변수와 지역변수는 서로 유일한 id를 가져야 한다. 예) 함수 A 내의 매개변수와 지역변수 이름- x와 y, i, j -이 중복되어 사용되지 못하도록 한다. 타입 규칙 10.3 각 함수 내의 모든 문장은 함수의 지역변수, 매개변수, 접근 가능한 전역변수에 대하여 합법적이어야 한다. 참고: 6장의 서로 다른 문장 종류에 대한 타입 규칙에 부합되어야 함.

9 Type Rules for Call and Return
타입 규칙 결과 타입이 void 가 아닌 모든 함수들은 main을 제외하고는 반환(return)문을 포함해야 하며, 반환되는 값을 나타내는 식은 해당 함수의 타입과 같아야 한다. 타입 규칙 10.5 void 함수에서는 return문이 나올 수 없다. 타입 규칙 10.6 모든 함수 호출 문장은 void 함수를 명시해야 하며, 모든 함수 호출식은 void가 아닌 함수를 명시해야 한다. 타입 규칙 10.7 모든 함수 호출은 명시된 함수의 매개변수의 개수와 같은 수의 인수값들을 사용해야 하며 각각의 인수값은 왼쪽부터 오른쪽으로 각각 대응하는 매개변수와 같은 타입이어야 한다. 타입 규칙 10.8 함수 호출의 타입은 호출된 함수의 타입이 되며 함수 호출을 나타낸 식은 타입 규칙 6.5와 6.6에 대하여 타당하여야 한다.

10 예제 프로그램의 타입 규칙 준수 타입 규칙 10.4 main 함수에는 return문이 없음
타입 규칙 A와 B에는 return문이 없음 타입 규칙 Call 문장인 A(a,b) 는 void 함수인 void A(int x, int y)를 명시하고 있음 타입 규칙 10.7 Call 문장인 A(a,b) 는 두개의 인수값을 가지며 이들의 타입은 각각 매개변수 x, y와 일치함 타입 규칙 은 적용되지 않음.

11 void가 아닌 함수의 예 피보나치수의 계산 Fig 10.5 int fibonacci (int n) {
int fib0, fib1, temp, k; fib0 = 0; fib1 = 1; k = n; while (k > 0) { temp = fib0; fib0 = fib1; fib1 = fib0 + temp; k = k - 1; } return fib0; int main () { int answer; answer = fibonacci(8);

12 피보나치 프로그램의 타입 규칙 준수 타입 규칙 10.4 int fibonacci (int n) 함수 안에 return fib0;문장이 있음. 타입 규칙 10.5 은 적용 안됨. 타입 규칙 10.6 함수 호출 fibonacci(8)은 void가 아닌 함수 int fibonacci (int n)를 명시함 타입 규칙 10.7 함수 호출 fibonacci(8) 은 하나의 인수값을 가지며 이 타입은 매개변수 n과 일치함 타입 규칙 함수 호출 fibonacci(8)이 포함된 계산식은 타당함.

13 10.3 Semantics of Call and Return
다음과 같은 단계로 수행된다: 1. 새로운 활성 레코드를 만들고 f의 매개변수들과 지역변수들을 위치시킨다. 2. c의 인수값들을 계산하고 그 값을 f의 활성 레코드의 대응하는 매개변수에 저장한다. 3. 함수가 void 타입이 아닐 경우 활성 레코드에 함수의 이름과 타입이 일치하는 결과 변수를 추가한다. 4. 만들어진 활성 레코드를 실행 시간 스택에 추가(push)한다. 5. f 함수 몸체의 명령문들을 수행한다. 6. 실행 시간 스택으로부터 활성 레코드를 제거(pop)한다. 7. 만약 함수가 void 타입이 아닐 경우 결과 변수의 값을 함수 호출에 반환한다.

14 프로그램 실행 추적의 예(그림 10.6) 함수호출 복귀 가시 상태
함수호출 복귀 가시 상태 main <h,undef>, <i,undef>, <a,undef>, <b,undef> A <h,5>, <x,3>,<y,2>,<i,undef>, <j,undef> B <h,5>, <i,undef>,<w,5>,<j,undef>, <k,undef> B <h,5>, <i,10>,<w,6>,<j,undef>, <k,undef> A <h,5>, <x,3>,<y,2>,<i,undef>, <j,undef> main <h,5>, <i,10>, <a,3>, <b,2>

15 void 타입이 아닌 함수들 의미 규칙 10.2 반환문의 의미는 활성 레코드 내의 결과 변수(호출된 함수의 이름을 가진)의 값을 결과 계산식의 값으로 대치함으로써 수행된다. 의미 규칙 10.3 블록의 의미는 현재 변수 상태에서 첫 반환문을 만나기 전까지 수행된 블록 내의 명령문들의 합쳐진 의미를 가진다. 중첩된 블록이 있을 경우 첫 번째로 만난 반환문은 가장 바깥쪽 블록의 종료를 가져오게 된다. 참고 : 반환문을 만나면 함수의 몸체는 종료한다.

16 프로그램 실행 추적의 예(그림 10.7) 함수호출 복귀 가시 상태 main <answer,undef>
함수호출 복귀 가시 상태 main <answer,undef> fibonacci <n,8>, <fib0,undef>,<fib1,undef>, <temp,undef>,<k,undef>, <fibonacci,undef> fibonacci <n,8>, <fib0,21>,<fib1,34>, <temp,13>, <k,0>, <fibonacci,undef> main <answer,21>

17 10.3.2 부작용에 대한 추가적인 사항 Clite에서 부작용(side effects)의 발생
부작용에 대한 추가적인 사항 Clite에서 부작용(side effects)의 발생 그림 10.1에서 B에 대한 호출은 전역 변수 i의 값을 변경함 만약 B가 void 반환이 아니라면 부작용은 B(h)+i와 같은 계산식에 부차적으로 영향을 줄 수 있음 Clite 언어의 의미 정의에서 이진 연산의 계산은 왼쪽부터 수행된다. 따라서 B(h)+i의 계산 결과는 항상 일정하며 i+B(h)와 다른 결과를 생성한다. 부작용은 수학과 프로그래밍의 차별성을 생성한다. 예를 들어 Clite의 더하기 계산식은 교환법칙이 성립하지 않는다.

18 10.4 타입과 의미구조의 정형적인 표현 함수 f의 타입 맵은 두 원소 쌍과 세 원소 쌍들의 집합으로 정의되는데, 각각의 원소는 전역변수(tmG), 전역 함수(tmF) 그리고 매개변수 또는 지역변수를 나타낸다 예 : 그림 10.1의 프로그램을 위한 타입맵

19 함수의 타입지정 함수의 타입 지정은 전역변수집합 G와 함수 집합 F를 가진 프로그램 내의 각각의 함수 f를 위한 타입 맵을 생성한다.

20 Clite 프로그램의 유효성 주어진 프로그램은 그 전역변수와 함수의 선언이 모두 유효하고, 모든 함수들이 그 타입 맵에 대하여 유효할 때 유효하다. 예: 예제 프로그램에 대해서는 다음을 보여야 한다.

21 Clite 함수의 유효성 프로그램 내의 한 함수가 유효하기 위해서는 1) 함수의 매개변수와 지역변수가 서로 다른 이름을 가지고 있어야 하고, 2) 함수 몸체 내의 문장은 그 함수의 타입 맵에 대하여 유효하여야 하며 3) void 타입이 아닌 함수는 최소한 하나의 반환문을 포함해야 하고 void 타입의 함수(또는 main함수)는 반환문을 포함하지 않아야 한다.

22 Clite 호출과 복귀의 유효성 대부분 Clite 문장의 유효성에 대해서는 6장에서 기술되었으며 호출과 복귀에 대한 규칙은 아래와 같다.

23 Clite 의미구조의 정형화 메모리 (), 환경 (), 상태 ():
함수 f 의 상태 f 는 f    a의 쌍이다. a : 실행시간 스택의 최상위(top)주소  : 주소-값 쌍들의 집합 f : f 내에서 가시적인 변수들과 그 주소

24 Allocate와 Deallocate 함수

25 void 반환 함수의 호출 의미 규칙 10.1의 함수 형태 정의에서 반환 결과를 임시적으로 생략

26 void 타입이 아닌 함수의 호출과 복귀 호출문은 값(Value)을 반환하며 Return 문이 반환값을 나타낸다 :

27 블록의 의미 블록은 Return문을 포함할 수 있으므로 복귀문을 만날 경우 즉시 블록을 빠져나오게 된다. (의미 규칙 10.3). 이에 대한 함수형태의 정의는 다음과 같다.