3-1공부/프로그래밍언어론

기말2] 함수

KGW2027 2022. 6. 4. 02:14
728x90
반응형

 

함수 ( Function )

 

 함수는 프로그램의 추상화를 위해 필수적인 도구이다.

 

 

 

함수의 정의

함수가 값을 반환하는가?

  • Value Returning : Non-void Function / Methods .....
  • Non-Value Returning : Procedures (Ada) / Subroutines (Fortran) / Void Function ...
  • 값을 반환하는 함수는 식으로, 반환하지 않는 함수는 문으로 해석한다.

 

함수를 호출하면서 값을 전달하는 변수를 '인수(Argument)'라고 한다.
함수가 실행되면서 값을 전달받는 변수를 '매개변수(Parameter)'라고 한다.

void A(int x, int y) { // x, y는 매개변수(Parameter)다.
	// do Somethings
}

void main() {
	A(7, 9); // 7, 9는 인수(Argument)다.
}


이 때, 인수를 매개변수로 전달하는 방식이 여러 가지 있다.

  • Pass by Value : 매개변수는 인수의 값만 전달받는다.
    - 매개변수에 대한 수정이 인수에 영향을 주지 않는다.

  • Pass by Reference : 매개변수는 인수의 메모리 주소를 전달받는다.
    - 매개변수에 대한 수정이 인수에 영향을 준다.

  • Pass by Result : 함수 종료 시 매개변수의 값을 인수로 전달한다.
    - 매개변수에 대한 수정 결과를 인수에 적용한다.
    • Pass by Value-Result 
      - 함수 실행 시 인수의 값을 매개변수로 복사하고, 함수 종료 시 매개변수의 값을 인수로 복사한다.

  • Pass by Name : 매개변수가 실제로 사용될 때, 인수의 값으로 대체된다.
    - Algol60에서 처음 사용되었으며, Lazy Evalution 방식으로 불린다.
    - 일반적인 Swap함수를 사용할 수 없으며, Pass by Name의 대표적인 예시로 Jensen's Device가 있다.
    - Pass by Name 방식은, 함수 호출 예제 없이 그 함수를 완전히 이해하는 것이 불가능하다.

 

 

 

 

함수의 의미구조

 함수가 선언된다는 것은, 기존 CLite가 int main()함수만을 고려했던 것과 달리 더 큰 단위로 해석해야함을 말한다.

즉, 구체 구문구조가 변경되어야 한다.

 ※ 함수 선언 : Type Identifier ( Parameters ) { Declarations Statements }

 

 

1. CLite의 함수 체계

활성 레코드(Activation Record)란,
각 실행구간 별로 접근할 수 있는 변수들과 정적인 부모에 접근할 수 있는 링크의 집합이다.

 

  • 활성 레코드의 구조
    - 전역변수에 대한 타입맵 : TypeMap-GlobalVariable '<VarName, VarType>'
    - 전역함수에 대한 타입맵 : TypeMap-GlobalFunction '<FuncName, ReturnType, ParamList>'
      위의 'TypeMap-GlobalVariable'과 'TypeMap-GlobalFunction'을 유니온한것을 'TM-G'로 정한다.

    -     개별 함수에 대한 타입맵 : TypeMap-FuncName 'TM-G <Onion> 인수와 지역변수의 타입맵'

    - 활성 레코드의 수는 정적일까?
     정적 할당의 경우, 함수 실행에 따라 이전 함수의 활성 레코드가 Override될 가능성이 있으므로 동적으로 Runtime Stack에 쌓아서 사용한다.


  • 함수의 호출
    1. 1. 함수가 호출된다.
    2. 2. 활성레코드가 제작되고, 함수의 매개변수와 지역변수를 위치시킨다.
    3. 3. 인수를 매개변수에 저장한다.
    4. 4. 반환 타입을 확인한다.
      1. 4-1) void 타입일 경우 : 6번으로 진행한다.
      2. 4.2) void 타입이 아닌 경우 : 5번으로 진행한다.
    5. 5. 활성레코드에 함수의 이름과 반환 타입이 같은 변수를 추가한다.
    6. 6. 활성레코드를 스택에 푸시한다.
    7. 7. 함수 안의 문장을 실행한다.
    8. 8. 활성레코드를 스택에서 팝한다.
    9. 9. 반환 타입을 확인한다.
      1. 9-1) void 타입인 경우 : 함수를 종료한다.
      2. 9-2) void 타입이 아닌 경우 : 결과 값을 레코드의 함수 이름 변수의 값으로 설정하여 반환한다.

  • 함수의 복귀
    1. 1. 종료된 함수의 활성 레코드에서 지역변수 정보를 제거한다.
    2. 2. 지역변수가 제거된 활성 레코드와 상위 활성 레코드를 Onion한다.
// 함수 호출 및 복귀의 과정에 따른 Activation Record의 동작을 살펴보자.
class FunctionTest {
	
    int x, y;
    
    float funcA(float y, float z) {
    	float temp;
        temp = y;
        y = z;
        z = y;
        return temp;
    }
    
    void main() {
    	x = 5; y = 10;
        float a1 = 20; float b1 = 40;
        float c1 = funcA(a1, b1);
    }

}

// 0. 프로그램 시작 이전
TM-GV : {<x, int>, <y, int>}
TM-GF : {<funcA, int, {<y, int>, <z, int>}>, <main, void, {}>}
TM-funcA : {<x, int>, <y, float>, <z, float>, <temp, float>, TM-GF} - y가 Onion됨
TM-main : {<x, int>, <y, int>, <a1, float>, <b1, float>, <c1, float>, TM-GF}

// 1. main 실행
Visible State : {<x, 5>, <y, 10>, <a1, 20.0>, <b1, 40.0>, <c1, undef>}

// 2. funcA 실행
타입맵에는 <funcA, float>가 추가됬다.
Visible State : {<x, 5>, <y, 20.0>, <z, 40.0>, <temp, 20.0>, <funcA, undef>}

// 3. funcA 종료
Visible State[funcA] : {<x, 5>, <y, 20.0>, <z, 40.0>, <temp, 20.0>, <funcA, 20.0>}
Visible State[main] : {<x, 5>, <y, 10>, <a1, 20.0>, <b1, 40.0>, <c1, 20.0>}

 

  • 반환문의 의미 : 활성 레코드 내의 결과 변수의 값을 결과 계산식의 값으로 대치한다.
  • 블록의 의미 : 현재 변수 상태에서 첫 반환문을 만나기 전까지 수행된 명령문들의 합집합이다.
  • 가시 상태(Visible State) : 호출이 수행되는 동안 접근 가능한 변수들의 목록이다.

 

함수식이 포함된 계산식은 교환법칙이 성립되지 않는다.
'func(a) + a'와 'a + func(a)'의 결과가 다를 수 있다.

 



메모리 μ, 환경 γ, 상태 σ, 런타임 스택의 최상위 주소 a에서, 함수 f의 상태 'σf = γf * μ * a'

 

allocate(data1, data2, ..., datak, σ) = γ' * μ' * a' // k개의 변수를 상태에 추가한다.
 γ' = γ (Union) {<d1.var.id, a>, <d2.var.id, a+1>, ..., <dk.var.id, a+k-1>}
μ' = μ (Onion) {<a, undef>, <a+1, undef>, ..., <a+k-1, undef>}

a' = a + k

 

deallocate(data1, data2, ..., datak, σ) = γ' * μ' * a' // k개의 변수를 상태에서 제거한다.
 γ' = γ (Union) {<dk.var.id, a>, <dk-1.var.id, a-1>, ..., <d1.var.id, a-k+1>}
μ' = μ (Onion) {<a, unused>, <a-1, unused>, ..., <a-k+1, unused>}

a' = a - k

 

 

 

2. 함수의 구문구조

함수가 들어간 코드를 분석하기 위해서는 구문구조가 필요하다.

  • 구체 구문구조
    • Program -> {Type Identifier FunctionOrGlobal} MainFunction
    • Type -> int | boolean | float | char | void
    • FunctionOrGlobal -> ( Parameters ) { Delcarations Statements } | Global
    • Parameters -> [ Parameter ( , Parameter ) ]
    • Parameter -> Type Identifer
    • Global -> { , Identifier } ;
    • MainFunction -> int main ( ) { Declarations Statements }
    • Statement -> ; | Block | Assignment | IfStatement | WhileStatement | CallStatement | ReturnStatement
    • CallStatement -> Call ;
    • ReturnStatement -> return Expression ;
    • Factor -> Identifier | Literal | ( Expression ) | Call
    • Arguments -> [ Expression { , Expression } ]

 

// 코드 진행과정을 구체 구문구조로 분석

// [Program] Start

int x; // Type Identifier ; ( Global )
int y; // Type Identifier ; ( Global )

// Type Identifier [FunctionOrGlobal] ( Parameter , Parameter ) {
float funcA(float y, float z) { // ( Type Identifier , Type Identifier ) { 
	// [Declarations]
	float temp; // Type Identifer ;
    
	// [Statements]
	temp = y; // [Assignment] Identifier = Expression ;
	y = z; // [Assignment] Identifier = Expression ;
	z = y; // [Assignment] Identifier = Expression ;
	return temp; // [ReturnStatements] return Expression ;
    
} 
// } [close FunctionOrGlobal]

// [MainFunction] int main ( ) {
int main() {
	// [Declarations]
	float a1 = 20; // [Delcaration] Type Identifier = Expression ;
	float b1 = 40; // [Delcaration] Type Identifier = Expression ;
    
	// [Statements]
	funcA(a1, b1); // [CallStatement] Identifier ( Expression , Expression ) ;
	x = 5; // [Assignment] Identifier = Expression ;
	y = 10; // [Assignment] Identifier = Expression ;
} 
// } [close MainFunction]

 

 

  • 추상 구문구조
    • 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

 

// 코드 진행과정을 추상 구문구조로 분석

// [Program] global, functions

// Declarations global = {<x, int>, <y, int>};
int x; 
int y; 

//Functions functions = {<float, funcA, funcADecls, funcABody>, <int, main, mainDecls, mainBody>}
float funcA(float y, float z) {

    // Declartions funcADecls = {<y, float>, <z, float>, <temp, float>}
	float temp; 
    
    // Block funcABody = {'temp = y;', 'y=z;', 'z=y;', 'return temp;'}
	temp = y;
	y = z;
	z = y;
	return temp;
    
} 

int main() {

	// Declarations mainDecls = {<a1, float>, <b1, float>};
	float a1 = 20; 
	float b1 = 40; 
    
	// Block mainBody = {'funcA(a1, b1);', 'x=5;', 'y=10;'}
	funcA(a1, b1);
	x = 5;
	y = 10;
    
} 

// Block 안의 코드들은 Statement로 분해해야 하나, 길이가 너무 길어질거 같아서 줄임.

 

  • 프로그램의 유효성 검사 ( Validation Check )
    • '전역변수와 함수의 선언' & '함수의 타이핑'가 유효한가?

    • 함수 유효 조건
      - 매개변수와 지역변수의 이름이 서로 유일하다.
      - 함수 내 문장이 타입맵에 대해 유효하다.
      - 함수 내에 반환문이 조건에 맞게 존재한다.

    • 호출 유효 조건
      - 함수가 타입맵에 들어있다.
      - 인수와 매개변수의 수와 타입이 같다.

    • 반환 유효 조건
      - 반환할 식의 타입이 함수의 타입과 같다.

 

 

 

3. 타입 규칙

함수 호출 중에 타입오류가 발생하는 것을 방지하기 위한 규칙들

  • 1. 모든 함수와 전역적인 식별자는 유일해야 한다.
    - 전역 변수 'int x'가 있을 때, 함수 x()가 존재해서는 안된다.

  • 2. 모든 함수의 매개변수와 지역변수는 서로 유일해야 한다.
    - 매개 변수 'int x'가 있을 때, 지역변수 '[Any Type] x'를 선언해서는 안된다.

  • 3. 각 함수 내의 모든 문장은 함수의 가시 상태에 대해 유효해야 한다.
    - 위의 코드 예시에서, funcA 함수 내에서 main의 지역변수인 a1, b1등에 접근하려고 하면 안된다.

  • 4. 반환 타입이 void가 아니면서 main이 아닌 모든 함수는 반환문을 포함해야 한다. 또한, 반환되는 값의 타입은 해당 함수의 타입과 같아야 한다.
    - 위의 코드 예시에서, funcA 함수는 반드시 return문을 가져야 하며, 함수의 반환 타입이 float인데 'return "Test";'같이 일치하지 않는 타입을 반환해서는 안된다.

  • 5. 반환 타입이 void인 함수에서는 반환문을 포함해서는 안된다.
    - void funcB() 라는 함수가 있다면, 이 함수 내에서는 return문을 사용할 수 없다.

  • 6. 반환 타입이 void면 함수 호출 문장, void가 아니라면 함수 호출식으로 구분된다.
    - void funcB()는 함수 호출문장이다.
    - float funcA()는 함수 호출식이다.

  • 7. 모든 함수 호출은 명시된 매개변수와 같은 수와 타입의 인수를 사용해야 한다.
    - void funcD(int d1, String d2); 라는 함수가 있을 때,
     funcD(); // 인수의 개수 부족
     funcD(3, 5); // 두 번째 매개변수의 타입과 두 번째 인수의 타입이 일치하지 않는다.
     funcD(3, "Test"); // 정상 작동

  • 8. 함수 호출식의 타입은 호출된 함수의 타입이 된다.
    - 'a + funcA()' 에서, funcA()는 float 타입이다.

 

728x90
반응형