바인딩, 메모리관리 SANGJI University Kwangman Ko ()
속성 (attributes) 속성 (attributes) ~ 특성 (properties) 들의집합 ~ 변수의위치 (location) 값이저장될수있는공간, 컴퓨터메모리주소 ~ 값 (value) 저장가능한대상 ~ 타입 (data type) 저장되는값의범위 (range) 결정 ~ 명칭 (= 식별자 = identifiers) ~ 영역 (scope) ~ 존속기간 (life-time) ~ 2
const int n = 5 ; ~ Q) 명칭 n 의의미를결정하는것? ~ A) 속성 double func ( int n ) { } ~ 매개변수수, 매개변수이름, 매개변수자료형 ~ 반환자료형 (return type), double ~ 함수호출시실행되는코드부분 int *y; (in C), y=new int; (in C++) ~ 의미? ~ 기억공간의구조를그림의표현? 3
바인딩 (Binding)? 정의 ~ 어떠한대상 ( 변수와같은 ) 과성질 ( 변수의값과같은 ) 의연결 ~ 이름에어떤속성을연결하는과정 ~ 속성과개체의결합, 연산과기호의결합, ~ 프로그램의기본단위에이단위가택할수있는여러속성중에서일부를선정하여결정하는행위 4
종류 ~ 정적바인딩 (static binding) 이름과대상의연결작업이실행시간이전에일어나는바인딩. ~ 동적바인딩 (dynamic binding) 이름과대상의연결작업이실행시간에일어나는바인딩 바인딩이발생되는시점? 5
Example of Binding // C++ example int x, *y; x = 2; y = new int(3); x y Type: integer Value: 2 Type: integer pointer Value: 3 6
바인딩시간 (binding time) 바인딩시간 (binding time) ~ 실제로바인딩이일어나는시간 바인딩시간의분류 (categories) ~ 정적바인딩 (static binding) 실행시간이전에일어나는바인딩 ~ 동적바인딩 (dynamic binding) 실행시간에일어나는바인딩 7
Further Refined Binding Time ~ Language definition time ~ Language implementation time ~ Program translation time ~ Link time, Load time ~ Execution time (run time) 8
수식 (expression) 의값 ~ execution time if it contains variables ~ translation time if it is a constant expression 명칭 (identifier) 에대한자료형 ~ translation time in a compilation system C, C++, C#, Java, ~ execution time in an interpreter LISP, APL, SNOBOL4, 9
정수 (integer) ~ language definition time, 정수의부분집합 ~ language implementation time, 최대및최소범위 변수의위치 (location) ~ load time for static variables (static in C) ~ execution time for dynamic variables (auto in C) 10
구문문제 이름결정규칙 ~ 어휘규칙 (Lexical rules) 에의하여이름형태가결정. ~ 예 ) C/Clite 언어등 문자로시작, 대소문자구분 (Case sensitivity) ~ C언어류 : yes ~ 초기의언어들 : no ~ PHP: 부분적으로구분또는비구분 11
예약어 (reserved words), 지정어 (keywords) ~ 특별한의미를가지는명칭 ~ 일반적인명칭 ( 변수이름, 함수이름등 ) 으로사용할수없음 예약어 ~ 미리정의된식별자의예 : 라이브러리함수명 명칭의재정의, 예약어 ~ 해로울까? Or 해롭지않을까? ~ 예 ) C : typedef int Integer 12
Symbol Table and Environment 심볼테이블 (symbol table) ~ 번역 / 실행되는동안명칭에적절한의미정보부여 / 관리 ~ 바인딩정보를저장하고있는언어번역기의자료구조. ~ Mathematically, a function SymbolTable: Names Attributes 13
컴파일시스템 ~ 다양한속성이다양한함수에의해유지 심벌테이블 : Names (Some) 정적속성 환경 : Names 메모리위치 (locations) 메모리 : Locations Values 해석 (interpretation) 시스템 ~ 정적및동적속성이모두실행시간에계산 ~ 심벌테이블과환경이조합 환경 : Names Attributes 14
선언 (declarations) 선언 : 바인딩을구성하는중요한방법 ~ 묵시적 (implicit) 바인딩 ~ 명시적 (explicit) 바인딩, 명확한지정 ~ Example( in C ) int x; the type binding is an explicit binding the location binding is an implicit binding 초기값 15
묵시적선언 ~ 명칭사용규칙 (naming convention) ~ FORTRAN example the variable whose name starts with I, J, K, L, M, or N is implicitly an integer ~ BASIC example ~ the trailing % of variable means an integer, $ means a string 16
Different Terms for Declarations 정의 (definition) ~ a declaration that binds all potential attributes ~ 모든잠재적인속성을바이딩하는선언 선언 (declaration) ~ a declaration that binds only a part of attributes ~ 속성일부분만을바인딩하는선언 17
함수선언 ( in C ) double f(int x) ; ~ 원형 (prototype) 함수 f 의데이터타입 ( 매개변수타입, 반환형 ) 만기술 구현몸체는기술하지않음. binds only the type (the interface) of the function 18
블록과지역성 블록 (block) ~ 선언과문장들의연속으로구성된언어구조 ~ 할당의단위 (unit of allocations) 선언과참조의지역성 (locality) ~ 지역적 (local): 명칭에대한선언과참조가동일블록으로제한 ~ 비지역적 (non-local) the declaration of a name is not in the block which contains the reference for the name 19
void p (void) { double r, z; /* p 블록 */ { int x, y; /* 내포된블록 */ x = 2; y = 0; x += 1; } } 20
블록구조화 (Block-Structured) 블록구조화프로그램 ~ 중첩될수있는여러개의블록으로구성된프로그램 ~ Algol60에서시도 ~ 후손언어에서블록구조를다양한방법으로제공 ~ 순차블록 : Pascal ~ 비순차블록 : Ada, C -- Ada example declare x: integer; begin end (* Pascal example *) program ex; var x: integer begin end 21
구조화자료형 (Structured Data Type) ~ a type declaration which contains declarations 내포된선언 (nested declaration) ~ 구조체 in C, 클래스 in C++, Java, Smalltalk 모듈 (Module) or 패키지 (Package) ~ a collection of declarations ~ the collection itself is not a declaration Ada: package and task Java: package ML and Haskell: module C++: namespace 22
영역, 스코프 (Scope) 바인딩의영역 (Scope of a Binding) ~ 바인딩이유지되는범위, 위치가중요정보 ~ 선언에의해결정된바인딩이동일영역유지, 선언의영역 이름의영역 (Scope of a Name) ~ 동일이름이중복되어선언될수있음 => 위험 ~ these different declarations of the same name should be differentiated 23
영역규칙 (Scope Rules) 정적 (static) 영역규칙 ~ 블록영역이선언을포함하고있는블록내부로제한 ~ 대부분의블록구조프로그램은정적영역규칙을따름 동적 (dynamic) 영역규칙 ~ 바인딩영역이실행경로 (path) 에따라결정 ~ 심볼테이블이동적으로정보를유지 24
Lexical Scope Example (C) int x; void p(void) { char y;... } /* p */ y In C, the declaration before use rule apply. void q(void) { double z;... } /* q */ z p x q main() { int w[10];... } w main 25
Scope Holes 영역구멍 (scope hole)? ~ 명칭의지역선언은동일한이름의이전 (prior) 선언을마스크 (mask) 함. ~ 마스크된선언은해당블록전체에대해영역구멍을갖음. 가시성 (visibility) ~ 선언된명칭의바인딩이적용되는부분 ( 영역구멍배제 ) 영역 (scope) ~ 바인딩이존재하며가시성이숨겨진영역포함 ( 영역구멍포함 ) 26
int x; void p(void) { char x; x = a ; /* char x 에배정 */ } /* p */ main() { x = 2; /* 전역 x 에배정 */... } 27
Scope Resolution Operator // C++ example int x; void p(void) { char x; x = 'a'; // local x ::x = 42; // global x... } /* p */ main() { x = 2;... } // global x The global integer variable x has a scope hole in the body of p. In C, the global x cannot be referenced in p. In C++, the global x can be referenced in p using a scope resolution operator ::. Ada also has a scope resolution operator.. 28
File Scope in C File Scope ~ In C, a global name can be turned into a file scope name by attaching the keyword static. ~ A file scope name can only be referenced in that file. File 1 extern int x;... x... int x;... x... File 2 File 3 static int x;... x... 29
Java Scope Example public class Scope { public static void f() { System.out.println(x); } public static void main(string[] args) { int x = 3; f(); } } public static int x = 2; 30
클래스선언 ( in Java ) ~ 선언의영역을클래스전체 출력되는값? ~ the above code prints 2. ~ under dynamic scope rule, the code would print 3. 31
동적스코프 (dynamic scope) 동적스코드의단점 (disadvantages) ~ 선언의영역이정적으로결정되지않음. ~ 선언의영역을결정하기위해 Hand-simulation 수행. ~ 명칭의자료형이정적으로결정될수없음. ~ 정적자료형검사 (static type-checking) 불가능 Next chapters 32
Symbol Table Maintenance 심볼테이블이란? ~ 명칭에연관된모든속성을저장하는공간 ~ 효율적인삽입, 검색, 삭제연산방법 ~ 효율적접근과유지를위한자료구조 해쉬테이블, 트리, 연결리스트, 정적영역 (lexically scoped languages) ~ 심볼테이블이스택과같은방법으로운영 블록진입시모든선언을처리하여대응하는바인딩추가 블록진출시선언에의해제공된모든바인딩제거, 복구 ~ 심볼테이블운영이실행경로 ( 순서 ) 와무관. 33
ST under Lexical Scope int x; char y; void p(void) { double x;... { /* block b */ int y[10];... }... } void q(void) { int y;... } main() { char x;... } x x x y y y p p p q q main main double local double local double int into p to local global global int to p global int char local global char to main int[10] global char local char b global to q global char global void function void void function function void function void function void function void function void function int function int function int global int global int global int global char global 34
ST under Dynamic Scope #include <stdio.h> int x = 1; char y = 'a'; x double=2.5 char='b' int=1 local global local to to main p char int=1 global void p(void) { double x = 2.5; printf("%c\n",y) { /* block b */ int y[10]; } } void q(void) { int y = 42; printf("%d\n",x); p(); } main() { char x = 'b'; q(); return 0; } y p q main Output int=42 char='a' local global to q void function void function int function 98 * char='a' global ASCII value of 'b' ASCII 42 = 'b' 35
동적영역 (dynamically scoped languages) ~ 가장바깥쪽의명칭의바인딩이구성. ~ 바인딩이프로그램실행경로에따라유지 비지역변수참조에대해적용된실행순서추적방법? 비지역변수의참조가실행이전에예측할수없음. 36
다중적재 (overloading) 다중적재? ~ 서로다른엔티티에대해명칭을재사용 ~ 같은이름을사용하여프로그램의다른대상을참조 ~ 3+4 vs. 3.0+4.0 어셈블리언어 : ADDI, ADDF 번역기는피연산자의자료형을참고 ~ 연산자중복 (operator overloading) C++ ~ 함수중복 (function overloading) C++, Java 37
the operator + is overloaded ~ integer addition (say, ADDI) ~ floating point number addition (say, ADDF) How about mixed-type expression? ~ 2 + 3.2 ~ C/C++ : promotion (implicit type conversion). ~ Ada : Error. Signature ~ 반환형, 매개변수개수, 매개변수자료형 38
int max(int x, int y) // max #1 { return x > y? x : y; } double max(double x, double y) // max #2 { return x > y? x : y; } int max(int x, int y, int z) // max #3 { return x > y? (x > z? x : z) : (y > z? y : z); } Name resolution ~ max(2,3) // calls max #1 ~ max(2.1,3.2) // calls max #2 ~ max(1,3,2) // calls max #3 39
Overload Resolution Issues 묵시적자료형변환은모호한 (ambiguous) 호출 ~ max(2.1, 3) // max??? ~ C++: too many candidates (max #1 or max #2) ~ Ada: no candidates ~ Java: 묵시적자료형변환은정보손실이없는경우로제한 다중적재에서반환형의고려여부? ~ 함수의반환형을함수호출정보로포함할것인가? ~ C++, Java: not included ~ Ada: included 40
Function Overloading in Ada procedure overload is function max(x: integer; y: integer) -- max #1 return integer is begin... end max; function max(x: integer; y: integer) -- max #2 return float is begin... end max; a: integer; b: float; begin -- max_test a := max(2,3); -- call to max # 1 b := max(2,3); -- call to max # 2 end overload; In Ada, the return type is included in the calling context. 41
Operator Overloading in C++ #include <iostream> using namespace std; typedef struct { int i; double d; } IntDouble; bool operator < (IntDouble x, IntDouble y) { return x.i < y.i && x.d < y.d; } IntDouble operator + (IntDouble x, IntDouble y) { IntDouble z; z.i = x.i + y.i; z.d = x.d + y.d; return z; } int main() { IntDouble x = {1, 2.1}, y = {5, 3.4}; if (x < y) x = x + y; else y = x + y; cout << x.i << " " << x.d << endl; return 0; } 42
Operator Overloading in Ada procedure opover is type IntDouble is record i: Integer; d: Float; end record; function "<" (x,y: IntDouble) return Boolean is... function "+" (x,y: IntDouble) return IntDouble is... x, y: IntDouble; begin x := (1,2.1); y := (5,3.4); if (x < y) then x := x + y; else y := x + y; end if; put(x.i); put(" "); put(x.d); new_line; end opover; 43
명칭의재사용 Reusing names for different kinds of entities ~ Separate name space for each kind is needed. ~ These kinds of reusing is not an overloading. C example typedef struct A A; struct A { int data; A * next; }; structure tag name type name Java example class A { A A(A A) { A: for(;;) } } Which is which? class name method name parameter name label name { if (A.A(A) == A) break A; } return A; 44
실행환경 (Environment) 환경 ~ 명칭과위치 (location) 를연결시키는것. 환경결정시간 ~ 정적환경 : FORTRAN ~ 동적환경 : LISP ~ 혼합 (mixture) : most Algol-style languages 모든명칭이환경에연결되는것은아님. ~ 상수 ~ Const int MAX = 10; 45
변수에대한기억장소할당시간 ~ 전역변수 (global variable) ~ 정적기억장소할당 ~ 로딩시간 (load time) 에기억장소할당 ~ 지역변수 ~ 동적기억장소할당 ~ 제어가도달할때선언된변수에대한기억장소할당 46
전형적인실행환경의구조 정적영역 (static area) ~ static allocation 스택영역 (stack) ~ LIFO-style dynamic allocation ~ 정적기억장소할당 힙영역 (heap) ~ on-demand dynamic allocation ~ 동적기억장소할당 47
활성화레코드 (Activation Record) 활성화 (Activation) ~ 부프로그램호출을호출하면? ~ 각부프로그램호출 (invocation or activation) 에대해각부프로그램에대한환경에구축되어야함. 활성화레코드 (Activation Record; AR) ~ 부프로그램호출에대해할당되는메모리공간 ~ subprogram environment + bookkeeping information 48
실행시간스택 (Run-Time Stack) ~ 블록의진입과진출이 LIFO 방식으로운용 ~ 프로시쥬어호출과반환이 LIFO 방식으로운용 ~ 활성화레코드들이실행시간스택에저장. 49
Run-Time Stack Manipulation A: { int x; point 1 char y; B: { double x; int a; } /* end B */ C: { char y; int b; D: { int x; double y; } /* end D */ } /* end C */ } /* end A */ 50
Run-Time Stack Manipulation A: { int x; char y; B: { double x; int a; } /* end B */ C: { char y; int b; D: { int x; double y; } /* end D */ } /* end C */ } /* end A */ point 2 51
Run-Time Stack Manipulation A: { int x; char y; B: { double x; int a; } /* end B */ C: { char y; int b; D: { int x; double y; } /* end D */ } /* end C */ } /* end A */ point 3 52
Run-Time Stack Manipulation point 4 A: { int x; char y; B: { double x; int a; } /* end B */ C: { char y; int b; D: { int x; double y; } /* end D */ } /* end C */ } /* end A */ 53
Run-Time Stack Manipulation point 5 A: { int x; char y; B: { double x; int a; } /* end B */ C: { char y; int b; D: { int x; double y; } /* end D */ } /* end C */ } /* end A */ 54
힙 (heap) 메모리영역관리 힙메모리 (Free Store) 할당 ~ 객체 (objects) 의할당에대해지원되는메모리구역 (pool) 환경에서선언처리의결과로생기는할당된기억장소구역 ~ 동적메모리공간 힙메모리반환 (deallocation) ~ 사용을마친힙메모리구역에대한반환함수또는연산자사용 free() in C, delete in C++, Ada. ~ 자동반환 (automatic deallocation) garbage collector 사용 안전하기는하지만속도저하의문제점, in Java 55
Pointer and Dereferencing 포인터 ~ 다른객체의위치 (= 주소 ) 를값으로갖는객체. ~ int *x = NULL; x는할당된객체를가리키기위해수동으로객체할당 x = ( int * ) malloc( sizeof( int ) ) ; 참조인출 (dereferencing) ~ 주소 (pointer value) 를통한객체참조. 56
/* C example */ int *x; // pointer declaration x = (int*)malloc(sizeof(int)); // memory allocation *x = 5; // dereferencing printf( %d\n, *x); free(x); // deallocation /* C++ example */ int* x = new int; *x = 2; cout << *x << endl; delete x; /* Java example */ Integer x = new Integer(2); System.out.println(x); // delete 연산이필요없음. 57
생명시간 (Lifetime) 객체 (storable object) ~ a chunk of memory cells ~ 환경에서할당되는기억장소구역 (area of storage) 객체의생명시간 (lifetime or extent) ~ 환경에서기억장소가할당되어소멸까지의소요시간 58
생명시간 (lifetime) vs. 영역 (scope) ~ 변수에대한생명시간과영역은밀접한관련은있지만동일하지않음. ~ local static variables in C/C++ 영역 : local, global 생명시간 : static, dynamic 59
Local Static Variable Example (C) int p(void) { static int p_count = 0; p_count += 1; return p_count; } main() { int i; for (i = 0; i < 10; i++) { if ( p() % 3 ) printf("%d\n", p() ); } return 0; } 60
변수와상수 변수 (variable) ~ 실행시간동안변환되는값을저장하는객체 (= 기억공간 ) ~ 명칭이실제메모리주소로변환 ( 언제 : ). 상수 (constants) ~ 생명시간동안변하지않는객체의값 ~ an object whose value does not change for its lifetime 리터럴 (literals) ~ 명칭에의해값이명확하게정해지는객체 61
Diagrams for Variables Schematic Representation Box-Circle Diagram 62
L-value and R-value L-value and R-value ~ l-value (LHS value): the location ~ r-value (RHS value): the value stored ~ X=10( ), x=y( ), 100 = z ( ). 63
배정 (assignment) 배정 ~ 변수의값을변경하는가장기본적인방법 ~ variable assingmentopertor expression ( 중위법 ) ~ 값의복사 (value-copying) 에의한배정 ~ 포인터에의한배정 (pointer semantics) 공유에의한배정 (shallow copying) 복제에의한배정 (deep copying) 복제 (cloning) 객체를메모리에정확히복사 64
Assignment by Value-Copying 변수의값이복사. ~ x = y 65
공유 (sharing) 에의한배정 변수의위치 (location) 가복사. ~ x = y ~ 변수 y의위치가 x에바인딩. 66
복제 (cloning) 에의한배정 변수의값 (value) 과위치 (location) 가복제. ~ x = y ~ 새로운위치를할당하여 y의값을복사 ~ 새로할당된위치를 x에바인딩 67
Java Example Java supports ~ 공유에의한배정 assignment of object variables ~ 값-복사에의한배정 assignment of simple data ~ 복제에의한배정 메소드복제 (method clone.) 68
A closer view of object assignment in Java ~ x = y 69
상수 (constant) Semantics 상수다이어그램 상수의의미 (semantics) ~ 바인딩이결정되면실행중변화가없음. ~ 상수의위치는참조되지않음. 값만유지하고위치속성을갖지않음. 70
상수의분류 리터널 and Named Constants ~ literals: 값을표현하는명칭 ~ named constants: 값의의미에대한명칭 Named Constants 분류 ~ 정적상수 ( = 상수 ) 실행이전에값이계산될수있는상수 컴파일시간 (compile-time) 정적상수, 적재시간 (load-time) 정적상수 ~ 동적상수 실행하는동안에만값이계산되는상수 71
상수초기화 C ~ the initial value of a static constant (or a static variable) should be computed from literals only C++ ~ the above restriction is removed #include <stdio.h> #include <time.h> const int a = 2; const int b = 27+2*2; /* legal in C */ const int c = (int) time(0); /* illegal C code! */ int b = 27+a*a; /* also illegal in C */ 72
별칭 (Aliases) 별칭 (aliases) ~ 동일객체에대해동시에두개이상의명칭을접근 ~ 프로그램판독성저하 ~ 부작용 (harmful side effects) 발생 부작용 (side effect) ~ 문장의실행이후에변수의값이변경되는것. 잠정적으로해로운부작용 ~ 부작용을작성된문장을통해서는결정하기어려움 ~ 실행되는문장의앞부분을참고해야알수있음. 73
An Example of Harmful Aliases main() { int *x, *y; x = (int *) malloc(sizeof(int)); *x = 1; y = x; /* *x and *y now aliases */ *y = 2; printf("%d\n",*x); return 0; } 74
별칭의발생요인? 별칭의발생요인? ~ 포인터배정문 (pointer assignment) ~ 참조에의한매개변수전달 (call-by-reference parameters) ~ 공유에의한배정 (assignment by sharing) class ArrTest { public static void main(string[] args) { int[] x = { 1, 2, 3}; int[] y = x; x[0] = 42; System.out.println( y[0] ); } } // int[] y = (int[]) x.clone(); 75
허상참조 (dangling references) 허상참조 ~ 할당된기억장소반환, 접근경로 (= 포인터 ) 존재. ~ 객체에대해환경에서수명종료, 접근경로존재 ~ Dangerous! 허상참조를만드는요인? ~ pointer assignment and explicit deallocation ~ pointer assignment and implicit deallocation by block exit by function exit 76
Example of Dangling References main(){ int *x, *y; x = (int *) malloc(sizeof(int)); *x = 1; y = x; /* *x and *y now aliases */ free(x); /* *y now a dangling reference */ printf("%d\n",*y); /* illegal reference */ return 0; } 77
쓰레기 (Garbage) Garbage (Dangling Objects) ~ 할당된기억장소는존재하지만접근경로가없음. ~ 할당된기억장소가너무늦게반환 ~ 메모리낭비발생, but 해롭지는않음. 쓰레기는만드는요인? ~ 명확한 (explicit) 기억장소할당, 접근경로분실 Assignment deallocation of the access point 78
An Example of Garbage main() { int *x; x = (int *) malloc(sizeof(int)); x = 1; /* OOPS! */... return 0; } 79
Garbage Collection 언어시스템 ~ automatically reclaims garbage. 함수언어, 객체지향언어 ~ using garbage collectors. See you in Memory management section!! 80