프로그래밍 언어론 제 8 장 함수와 프로시져 함수의 원소 재귀 함수(Recursive Functions) 프로시져

Presentation on theme: "프로그래밍 언어론 제 8 장 함수와 프로시져 함수의 원소 재귀 함수(Recursive Functions) 프로시져"— Presentation transcript:

1 프로그래밍 언어론 제 8 장 함수와 프로시져 함수의 원소 재귀 함수(Recursive Functions) 프로시져
형식 매개변수의 명세 매개변수로 전달되는 배열 매개변수로 전달되는 프로시져 함수의 리턴값 중복정의 포괄 프로시져

2 procedure 프로시져 이름(매개변수리스트)
8.3 프로시져 부프로그램(function 또는 procedure) - 프로그램 모듈화의 단위 일반적인 부프로그램의 특성 각 프로시져는 단일 진입점을 갖는다 호출프로그램(caller)은 호출된 프로그램(callee)의 실행동안 중단 부프로그램의 실행 종료시 제어는 호출프로그램에게 돌아감 프로시져의 구성 프로시져 이름 매개변수(parameter) 리스트 몸체(body) 환경(environment) procedure 프로시져 이름(매개변수리스트) 선언부(declarations) 몸체(body) end 프로시져 이름

3 프로시져(2) 프로시져의 식별자 종류 프로시져에 관한 연구 주제 형식 매개 변수 지역 변수 비지역 변수
구체적인 문법 구조(syntax) 형식매개 변수의 명세: 무엇을 어떻게 정의하는가? 매개 변수의 평가와 전달 함수와 프로시져 사이의 구분

4 8.3.1 프로시져내의 영역과 수명 형식 매개변수와 지역 변수의 영역은 자신들이 선언된 프로시져 내부이다. 프로시져 내에서 선언된 포인터는 프로시져를 영역으로 가지게 될 것이다. 그러나 가리켜진 값을 유지하기 위한 기억 장소는 익명의 이름을 가지고 프로시져의 액티베이션을 초과하는 수명을 가진다. 지역 변수는 적재 시간에 정적으로, 혹은 프로시져가 호출될 때 동적으로 기억 장소에 결합되기도 한다. 만일 정적 변수이면, 기억 장소는 호출 시간에 할당되고, 프로시져를 벗어날 때 해제된다. 재귀 함수나 프로시져는 재귀 호출을 위한 각 지역 변수의 별도의 사본이 요구될 때, 동적으로 할당된 지역 변수를 가져야 한다. 동적으로 할당된 변수들은 일반적으로 실행시간 스택(run-time stack)에 위치한다.

5 8.3.2 실 매개변수와 형식 매개변수의 결합 형식 매개 변수와 실매개 변수 실 매개 변수
서브 프로그램으로 전달하기 위하여 호출 시 사용된 식 또는 이름 형식 매개 변수 서브 프로그램이 실행될 때, 실 매개 변수를 대신하여 사용되는 이름 프로시져의 정의부에서 명명되어 일반적으로 지역 변수 역할 최근 경향 : 매개 변수 명세 제공 형식매개변수 이름, 자료형, 바인딩 방법 등등

6 (1) Left-to-Right 규칙 (1) 위치에 따른 결합(positional association)
- 형식 매개 변수와 실 매개 변수가 순서대로 대응 - 예) procedure TEST(A, B : in REAL; C : in INTEGER); TEST(0.1, 100.0, 50); - 매개변수가 서로 바뀔 수 있음 (2) 키워드를 이용한 결합 - 실 매개 변수에서 대응되는 형식 매개 변수 이름을 키워드로 사용 TEST (A => 0.1, C => 50, B => 100.0); (3) 위치에 따른 결합 방식과 키워드를 이용한 결합 방식을 함께 사용 Ada 언어 예 : 병행 사용 (위 procedure 선언문에서 위와 다음 경우 모두 동일) TEST (0.1, C => 50, B => 100.0); TEST (0.1, 100.0, 50);

7 (3) 디폴트 매개변수(Default Paramter)
C++와 Ada와 같은 언어에서는 디폴트 값이 인자에 지정될 수 있으므로, 형식 매개변수보다 더 적은 수의 실 매개변수가 가능 Ada의 경우 다중 매개변수를 가지는 프로시져는 매개변수의 일부 혹은 전부에 대해 디폴트값을 가질 수 있다. procedure SQUARE_AND_SUM(X1, X2, X3, X4: integer := 0) is begin put(X1**2 + X2**2 + X3**2 + X4**2); end SQUARE_AND_SUM; SQUARE_AND_SUM을 0부터 네 개까지의 실 매개변수를 가지고 호출 가능, 명시하지 않은 매개변수는 디폴트값인 0 SQUARE_AND_SUM; 이 출력 SQUARE_AND_SUM(5); 가 출력 SQUARE_AND_SUM(3, 1); 이 출력 SQUARE_AND_SUM(4, 2, 5); 가 출력 SQUARE_AND_SUM(8, 9, 2, 3); 이 출력

8 디폴트 매개변수(2) C++에서 정수를 입력받으면, 그 값을 출력하는 함수 print( )를 구현한다고 가정하자. 이 함수가 일반적인 기능을 가지기 위해 매개변수로 출력되기를 원하는 값과 실제로 출력되는 값의 기수(radix)를 전달한다고 가정하자. 함수 선언 void print_integer(int value, int radix) 그러나 출력의 대부분이 10진수라면, 이 함수를 호출할 때마다 두 번째 매개변수 10을 매번 전달해야 하는 번거로움이 있다. 이러한 번거로움을 해결하는 방법은 10진수 전용 출력 함수와 범용 출력 함수를 별도로 가지는 두 가지 방법이 있으나 이런 방법은 좋은 해결책이 되지 못하므로, C++에서는 이러한 경우를 적절하게 처리하기 위해 디폴트 매개변수를 지원한다. 디폴트 매개변수는 함수를 호출할 때 특정 매개변수를 전달하지 않으면 자동적으로 미리 정해진 값으로 넘겨주는 기능이다.

9 디폴트 매개변수(3) 다음과 같이 구현될 수 있다.
void print_integer(int value, int radix=10) //두 번째 매개변수가 없을 때 10이 전달 main( ) { print_integer(45, 10); print_integer(45); //print_integer(45, 10)과 같다. print_integer(45, 8); print_integer(45, 16); } C++에서 디폴트 매개변수는 함수 매개변수 선언에서 뒷 부분에만 올 수 있다. 즉, 디폴트 매개변수 뒤에 오는 매개변수는 모두 디폴트 매개변수이어야 한다. int f(int, int=0, char); // 에러 int f(int, int=0, char='a'); // 적법 int f(int=10, int=0, char=‘ '); // 적법

10 8.4 형식 매개변수의 명세 실 매개변수와 형식 매개변수의 정적 형 검사 요구 형식 매개변수의 명세 형식 매개변수의 명세
8.4 형식 매개변수의 명세 실 매개변수와 형식 매개변수의 정적 형 검사 요구 형식 매개변수의 명세 형식 매개변수의 명세 - 데이터 형, 전달 기법, 초기값, 대응 관계 등 각종 언어의 형식 매개변수의 명세 Pascal : 데이터 형, 전달 기법( 값 전달 기본, var 선언 - 참조 전달, 값-결과 전달) Algol 60 : 전달 기법(이름 전달 기본, value 선언 - 값 전달) Ada : 전달 기법 - 예약어 in(값 전달), out(결과 전달), in out (값-결과 전달)

11 8.4.1 call-by-value 형식 매개 변수의 지역 변수화 실 매개 변수 값을 복사 특징 - 실 매개 변수 값 불변
다음과 같은 프로그램을 가정하자. 여기에서 x, y는 형식 매개변수이고, a, b는 실 매개변수이다. procedure P(x,y) ... end P(a,b)

12 procedure p (x, y) call p (a, b)
Call-by-value (2) procedure p (x, y) call p (a, b) 복사 실 매개변수의 사본이 생성 실 매개변수의 수가 많을 경우 비용 문제 실 매개변수는 결코 변경되지 않음 실 매개변수의 r-값이 프로시져로 전달 C는 call-by-value 이용

13 Call-by-value (3) C에서는 기본적으로 call-by-value로 매개변수가 전달되므로 다음의 결과는?
void swap(int x, int y) { int z; z = x; x = y; y = z; } 다음과 같이 수정하는 이유는? void swap(int *px, int *py) // 호출은 swap(&a, &b) z = *px; *px = *py; *py = z;

14 8.4.2 call-by-reference 실 매개변수 주소를 대응되는 형식 매개변수에 보내는 방법
procedure p (x, y) call p (a, b) caller는 실 매개 변수의 주소를 callee에게 전달

15 Call-by-reference (2) Pascal C++
procedure swap(var x: integer; var y: integer) var z: integer; begin z := x; x := y; y := z; end; … swap(a, b) C++ void swap(int& x, int& y) // 형식 매개변수를 참조형으로 선언 { int z; z = x; // 참조 x, y를 이용하여 실 매개변수를 직접 접근 x = y; y = z; } // 호출은 swap(a, b)

16 8.4.3 Call-by-value-result
실 매개변수의 주소를 기록하고, 실 매개변수의 사본을 만들고 나서 그들을 형식 매개변수에 전달. 종료시에, 지역 형식 매개변수들은 원래의 실 매개변수로 다시 복사. 따라서 때로는 copy-in, copy-out이라고 함. 어떠한 별명도 형성되지 않는다는 것을 제외하고 call-by-reference와 비슷한 결과 별명이 존재할 때만 call-by-reference와 구별됨 다음에서 call-by-reference가 이용되면 ex가 호출된 후의 x는 3이지만, call-by-value-result가 사용되면 ex가호출된 후 x는 2 procedure ex(a, b: integer); begin a := a + 1; b := b + 1; end; x := 1; ex(x, x); end.

17 Call-by-value-result (2)
매개 변수 전달 기법 비교를 위한 또 다른 예 procedure PRINT integer y procedure INCR(x) integer x begin y x x + 2 end y INCR(y) write y 프로그램 실행 후 인쇄 값 (y) call by reference적용 : 3 call by value-result 적용 : 2

18 8.4.4 Algol 60의 Call-by-name 실행 중에 형식 매개변수를 만나면 실 매개변수는 원시 코드상에 대응하는 형식 매개변수와 대치된다. 만일 실 매개변수가 상수이면, call-by-name은 call-by-value와 동일하고, 만일 실 매개변수가 스칼라 변수이면, call-by-name은 call-by-reference와 동일하다. 또는 만일 실 매개변수가 배열의 요소이면, 아래에 보인 것처럼 명백한 유사성이 존재하지 않는다. procedure swap(a,b) real a, b; begin real t; t := a; a := b; b := t; end swap(i, a[i]); comment try i =2, a[1] = 10, a[2] = 20, a[3] = 30; 다음 코드처럼 작동한다. t := i; i := a[i]; a[i] := t;  a[a[i]] := t; a[i]가 세 번째 줄에서 계산될 때까지 i는 앞 줄에서 a[i] 값을 가지고 있고, i=a[i]인 경우에만 원래 i를 첨자로 하는 배열 a에 t가 배정될 것이라는 점을 주목해야 한다.

19 Call-by-name (2) 단점 형식 매개 변수의 이름이 사용될 때마다 그에 대응되는 실 매개 변수
자체가 사용된 것으로 간주 (필요한 r-value 또는 l-value를 매번 계산) 기법 적용 caller - 실 매개 변수의 r-value와 l-value 계산 routine (THUNK 라 칭함) 작성 callee - 사용될 때마다 THUNK를 이용하여 필요한 값( r-value 또는 l-value) 계산 단점 - 구현 난해 - 프로그램 가독성 저해

20 Call-by-name (3) call-by-name이 강력한 메커니즘이 될 수도 있다. Jensen's device는 다음과 같이 식과 관련된 변수를 매개변수로 전달하는 것이다. 즉, 어떤 연산을 전체 배열에 적용하는데 call-by-name을 이용한다. real procedure sigma(x, j, n); value n; real x; integer j, n; begin real s; s := 0; for j := 1 step 1 until n do s := s + x; sigma := s end ... sigma(a(i), i, 10) sigma(a(i)*b(i), i, 10) 앞에서 첫 번째 sigma 호출은 x가 a(i)로 대치됨에 따라 a(1)+a(2)+...+a(10)을 리턴하게 되고, 두 번째 호출은 a(1)*b(1)+a(2)*b(2)+...+a(10)*b(10)을 리턴한다.

21 Call-by-name (4) 예제 호출시 J의 값 J0로 가정 참조 호출 : J0 N(J0 ) 이름 호출 : J N(J0)
procedure EXCHG(X, Y) integer TEMP begin TEMP X X Y Y TEMP end call EXCHG(J, N(J)) 의 해석 integer TEMP begin TEMP J J N(J) N(J) TEMP 호출시 J의 값 J0로 가정 참조 호출 : J N(J0 ) 이름 호출 : J N(J0) N(N(J0 )) J0

22 8.4.5 매개변수 전달 방법의 비교 var i : integer; A: array [1..3] of integer;
procedure test(f, g: integer); begin g := g+1; f := 5*i; end begin for i :=1 to 3 do A[i] := i; i := 2; test(A[i], i); print(i,A[1],A[2],A[3]); end; 매개변수 전달 방법의 비교 전달 방법 i A[1] A[2] A[3] call-by-value call-by-reference call-by-value-result call-by-name

23 매개변수 전달 방법의 비교(2) 예 제 다음 Algol 형태의 프로그램에서 매개 변수 전달 방법이 아래
(a), (b), (c), (d) 기법으로 사용되었을 경우, 프로그램이 실행된 후의 v[3]과 v[4]의 최종값을 구하여라(단, 미확정될 수도 있음). (a) call by reference (b) call by value (c) call by value result (d) call by name

24 매개변수 전달 방법의 비교 (3) begin integer k integer array v procedure P(a)
a  a + 1 v[k]  5 k  3 a  a + 1 end v[3]  6 v[4]  8 k  4 call P(v[k])

25 8.5 매개변수로 전달되는 배열 일반적으로 배열은 call-by-reference로 전달 program main type simple = array[1..3] of integer; var a, b : simple; i : integer; procedure test(c :simple; var d : simple); var i : integer begin c[2] := c[2] + 10; d[2] := d[2] + 10; for i := 1 to 3 do write (c[i]); for i := 1 to 3 do write (d[i]); end; a[1] := 6; a[2] := 7; a[3] := 8; b[1] := 6, b[2] := 7; b[3] := 8; test(a, b); for i := 1 to 3 do write (a[i]); for i := 1 to 3 do write (b[i]); end test로부터 프린트되는 결과는 c = 6, 17, 8; d = 6, 17, 8 이고, main으로부터 프린트되는 결과는 a = 6, 7, 8; b = 6, 17, 8 이다.

26 8.8 중복 정의(overloading) 중복 정의(overoading)
한 개체(식별자, 함수 이름, 연산자 등)가 두 가지 이상의 개념으로 사용되는 것

27 중복 정의(2) 사용 이유 중복정의 사용시 구별법 자연스러운 원래의 일반적인 표기 사용을 지원
동일한 이름이나 연산자를 여러 프로그래머들이 중복 사용하여 하나의 프로그램으로 합쳐도 혼동되지 않음 (문맥에 의한 구별) 중복정의 사용시 구별법 의미 확정을 문맥에서 알 수 있으면 컴파일러가 수행 문맥으로 구별이 될 수 없는 경우 사용자가 제약 조건을 규정

28 중복 정의 (3) 사용 예 - “*” 연산자를 행렬 곱셈에 중복 표현 (사용자 정의)
사용 예 - “*” 연산자를 행렬 곱셈에 중복 표현 (사용자 정의) function "*"(X, Y : MATRIX) return MATRIX ; 이항 연산자(binary operator) “*” - 행렬 곱셈 연산자로 정의 자료형 MATRIX는 별도 선언 MATRIX 형 검사 - Ada 시스템에서 수행 A := B * C ; B, C가 MATRIX 형 - 위 함수 정의대로 수행 B, C가 integer 형 - 정수 곱셈 B, C가 real 형 - 실수 곱셈 문맥으로 검사

29 중복 정의(4) Ada에서의 중복 정의 예 procedure MAIN is package P is
... package P is function F(X : REAL) return RANGE ; P.F function G(X : DOMAIN) return REAL ; P.G function K(X : DOMAIN) return BOOLEAN ; -- P.K end P; function F(X : BOOLEAN) return RANGE ; MAIN.F function G(X : DOMAIN) return BOOLEAN ; -- MAIN.G function K(X : DOMAIN) return REAL ; MAIN.K S : DOMAIN ; T : RANGE ; U : BOOLEAN ; V : REAL ; use P; begin T := F(V) ; -- P.F(V)를 의미 T := F(U) ; -- MAIN.F(U)를 의미 T := F(K(S)) ; -- MAIN.F(P.K(S))인지 P.F(MAIN.K(S))인지 애매 모호함 T := F(G(S)) ; -- MAIN.F(MAIN.G(S))인지 P.F(P.G(S))인지 애매 모호함 end

30 중복 정의(5) C++에서의 중복 정의 예 extern void f(int); extern void f(int, int);
extern void f(char *); extern void f(double); extern void f(long); main( ) { f(10); // 함수 f(int)가 호출됨. f("a"); // 함수 f(char *)가 호출됨. f(4.2); // 함수 f(double)가 호출됨. f(11L); // 함수 f(long)가 호출됨. f('a'); // 함수 f(int)가 호출됨. } main( ) { int i = 10; f(i); } //f(long)? 아니면 f(double)?, 두 가지 이상의 형 변환이 가능하면 모호성 에러

31 8.9 포괄 프로시져(Generic Procedures)
정의 : 하나 이상의 요소를 매개변수로 받아들여 실 프로시져를 생성할 수 있는 프로시져 틀(procedure templates) 컴파일 시간에 실 매개 변수가 대체되어 실제 프로시져를 발생 장점 코딩의 오류 감소 프로그램의 길이 축소 추상화 개념 제공

32 포괄 프로시져 (2) Ada의 부프로그램이나 패키지에서 사용되는 포괄 기능 매크로(macro)의 확장된 개념
실제 프로시져 : 번역시 정적 생성 (instantiation)

33 포괄 프로시져 (3) Ada에서의 포괄 프로시져의 예 포괄 프로시져를 사용하여 실제 프로시져를 실체화 시키는 방법
generic – 제너릭 명세의 시작 type EXAM is private; - 제너릭 형식 매개변수 procedure CHANGE(A, B : in out EXAM); -제너릭 명세의 끝 procedure CHANGE(A, B : in out EXAM) is T :EXAM ; begin T := B ; B := A ; A := T ; end ; 포괄 프로시져를 사용하여 실제 프로시져를 실체화 시키는 방법 procedure INTCHANGE is new CHANGE(INTEGER) ; procedure REALCHANGE is new CAHNGE(FLOAT) ; 프로시져저의 사용 INTCHANGE(X, Y) ; REALCHANGE(W, Z) ;

34 포괄 프로시져 (4) 포괄 프로시저 CHANGE에 중복 정의를 함께 사용 CHG (X, Y) ; 의 해석
procedure CHG is new CHANGE(INTERGER) ; procedure CHG is new CHANGE(FLOAT) ; procedure CHG is new CHANGE(BOOLEAN) ; procedure CHG is new CHANGE(CHARACTER) ; CHG (X, Y) ; 의 해석 X, Y의 형에 따라 정수형, 문자형, 실수형, 부울형 CHANGE 프로시져 결정

35 포괄 프로시져 (5) C++은 객체 생성시 객체의 멤버의 형을 매개변수로 받아들이는 매개변수화된 클래스(parameterized class)를 지원하고 이를 template이라고 함. 다음은 template를 이용하여 여러 가지 형의 vector 객체를 생성할 수 있는 포괄 vector 클래스 정의 template<class T> class vector { int size; T *p; public: ... vector(int sz) size = sz; p = new T[sz]; } 객체 생성시 매개변수로 T를 받아들여 T형의 vector를 생성해서 그 주소를 p에 지정, 이 vector 클래스를 이용해서 정수형이나 complex 형의 vector 객체를 생성 가능 vector<int> v1(20); vector<complex> v2(10); v2[1] = complex(v1[1], v2[2]);

36 참고: 코루틴(Coroutines) 코루틴 A B
호출된 프로그램의 수행이 완전히 끝나기 전에 타 프로시져(호출 프로시져 포함)로 제어를 넘겼다가 재개(resume)할 수 있는 프로시져 Resume A B Resume B A

37 코루틴(2) 특징 - 코루틴은 제어를 넘겨 받으면 프로시져의 일부만 실행 - 제어의 반환은 실행 일시 정지
- 후에 제어를 받으면 정지된 위치에서 실행 재개(resume) - 프로시져들간의 관계가 주종 관계가 아님

38 코루틴(3) coroutine A에서 resume B 문장 실행 단계
(1) A의 resume 문장 다음 위치를 A의 제어 장소에 기억 (2) coroutine B의 실행 위치를 알기 위하여 B의 제어 장소의 값 참조 (3) B의 제어 장소의 참조된 값으로 제어 분기 코루틴은 이산 체계 시뮬레이션 언어의 범주에서 취급 경우에 따라 자연스러운 알고리즘 제공 기존 언어에서 시뮬레이션으로 간단히 해결

39 연습 문제 3. program test; var i: integer; a: array[1..2] of integer;
procedure p(x, y: integer); begin x := x + 1; i := i + 1; y := y + 1; end; a[1] := 1; a[2] := 1; i := 1; p(a[i], a[i]); writeln(a[1]); writeln(a[2]); end.