프로그래밍언어론 (중간고사 필기정리)

이 필기는 학교에서 듣는 프로그래밍 언어론 수업 시험대비를 위한 필기입니다.

중요한 내용보다는 제가 처음 본 내용과 교수님이 어렵다고 강조하신 용어 위주로 정리할 예정입니다.

 

Orthogonality : Every possible combination of constructs is legal (연산자나 표현 등이 다른 요소들에도 적용할 수 있는지)

Aliasing : 같은 메모리를 reference하는 이름이 여러 개 존재할 수 있는지

Binding : Entity (변수, 함수, 클래스 등)의 Attribute (타입, 값 등)가 결정되는 것

Binding Time

 -Static bindng : 런타임 이전에 결정되고 실행 중에 변경되지 않음

 -Dynamic binding : 런타임에 결정되거나 변경됨

 

Variable Type binding

Explicit / Implicit Declaration + type inferencing

Strong / Weak Typing : 타입 에러를 모두 잡아내면(런타임에서라도) Strong typing이다. static/dynamic typing이랑은 다르다.

 -coercion : 묵시적인 형변환 (Implicit conversion)으로, 이를 지원하는 언어들이 있다.

 -Name Equivalence : 두 변수의 자료형의 이름이 똑같아야 같은 형으로 취급

 -Structural Equivalence : 두 변수의 자료 형태가 같으면 같은 형으로 취급

 

Variable Lifetime(memory)

Static : 실행 이전에 변수의 주소공간을 미리 정해둠

Stack-dynamic : 변수의 크기는 정해져있지만, 시작주소가 스택에 의해 결정되기 때문에 주소공간이 런타임에서 정해짐

Explicit Heap-dynamic : 변수의 크기 및 위치가 실행 중에 결정됨. 하지만 해제도 함께 해줘야함

Implicit Heap-dynamic : 위와 같지만 명시적으로 new delete 등을 하지 않아도 됨

 

Variable Scope

Static : 소스코드에서 scope가 정해짐. 가장 가까운 이름을 사용하며 더 상위 scope의 이름이 가려질 수 있음

Dynamic : 실행 순서에 따라 scope가 정해짐 > 그렇기 때문에 static type check가 불가능함

 

Data Types

Primitive data types : 다른 데이터 타입으로 구성되지 않은 가장 하드웨어에 근접한 데이터 타입

 -Character types : 대부분 ASCII를 사용하며, 16bit Unicode나 32bit Unicode를 사용하기도 함

 -Ordinal data types : 양수로 표현될 수 있는 데이터 종류 ( int, char, bool, enum)

 -Character string types : character의 배열로, primitive type으로 하거나 배열로 만든다. 고정or가변젹 길이의 형태를 취한다.

 -Array Types : 동종의 자료의 집합으로 위치를 통해 접근할 수 있음. 마찬가지로 크기를 static/dynamic하게 정하도록 돼있다. 타입이 다른 자료를 모을 수 있는 언어도 있다. 또 2차원배열이 jagged형태가 되는 경우와 무조건 직사각형 모양을 하는 경우도 있다. key/value 형태로 사용할 수 있는 자료구조를 지원하기도 한다.

 -Union Type : 하나의 변수에 다른 타입을 저장할 수 있는 기능으로, Type checking을 지원하지 않는 경우도 있다.

 

Pointer Types : 변수의 주소를 값으로 가지며, 힙 영역에서 동적으로 할당된 메모리를 가리키는 용도로 많이 쓰인다.

포인터는 Dangling pointer(포인터가 해제된 메모리를 가리킴)와 Dangling Object( or garbage, 할당된 메모리의 주소를 잊어버림)와 같은 문제가 있다.

위 문제를 해결하기 위해 Reference counter(참조 횟수 기록) 기능이나 Mark-sweep(여러 공간을 한번에 해제) 기능을 지원하기도 한다.

 

Expressions and Statement

Expression은 value를, Statement는 effect를 위해서 사용합니다.

 

Operator Precedence : 연산자 우선순위

Associativity Rules :  같은 우선순위일 경우의 연산 순서 (대부분 왼쪽에서 오른쪽)

 

Side Effects : Expression을 작성했는데 해당 Expression의 함수나 연산으로 인해 부수적인 효과가 나타나는 경우

Referential Transparency : 어떤 표현을 같은 값을 가지는 다른 표현으로 대체할 수 있으면 referential transparency가 지켜졌다고 합니다. 이를 위해선 side effect가 없어야합니다. fun(a)+fun(a);와 t=fun(a), t+t 가 같은 결과를 가진다는 의미입니다.  fun 함수에서 a의 값을 바꾸는 등 side effect가 있다면 referential transparency가 지켜지지 않습니다.

 

Short Circuit Evaluation : 표현의 일부분으로 전체 표현의 답을 알 수 있다면 계산을 하지 않는 방법으로, C언어에선 &&와 ||에 사용됩니다. 하지만 이 또한 side effect가 있는 expression이 포함돼있다면 원하는 결과가 나오지 않을 수도 있습니다.

 

변수가 L-value일 땐 변수의 storage를 의미하고, R-value일 땐 변수의 값을 의미합니다.

 

언어에 따라 Assignment가 Expression으로 사용될 수 있는 언어가 있습니다.(C)

 

 

추상화 : Separate essentials (what) from details (how)

Control Abstraction

모든 알고리즘은 분기문(selection)와 반복문(pretest logical loop)으로 표현될 수 있기 때문에, 대부분의 언어는 두 종류의 control statment를 지원합니다.

루프에는 counter-controlled loops와 logically-controlled loop가 있습니다. 또 언어별로 Iteration based on data structures를 지원합니다. 이걸 사용자가 정의할 수 있게 만든 기능이 Generator(yield) 기능입니다.

 

Procedural Abstraction

Procedure : 여러 문장을 한 단위로 만들어 놓은 것

Subprogram

-진입점(entry point)가 하나뿐이며, 호출한 프로그램은 subprogram의 실행이 끝날 때까지 기다리며, subprogram이 끝나면 호출위치로 돌아갑니다.

 

Generic Subprogram : 템플릿을 이용해 다양한 자로형에 대해 실행할 수 있는 subprogram

Closure : runtime에 만들어지는 subprogram

 

Declaration vs Definition : declation은 인터페이스만 선언한 것, definition은 인터페이스 + 구현 내용을 모두 정의한 것

 

Formal parameter : subprogram의 헤더에 정의된 dummy varaible (subprogram에서만 사용함)

Actual parameter:  subprogram 호출 시 실제로 전달되는 data, variable

 

Procedures vs Functions : function은 side effect가 없는 수학적 함수를 의미하며, 우리가 프로그래밍에서 쓰는 함수는 대부분 Procedure을 의미한다.

 

Parameter passing

Parameter passing의 3종류 : In mode는 subprogram이 parameter을 받기만하고, Out mode는subprogram이 caller에게 데이터를 입력하고, In-out mode는 서로 데이터를 교환하는 방식입니다.

 

Pass by value (In mode) : parameter의 값을 formal parameter에게 전달함. 주로 복사를 하며 레퍼런스를 주는 경우도 있음

Pass by result (Out mode) : callee의 local variable(formal)을 이용해 callee의 변수 값을 지정함. sub(p1,p1), sub(list[p],p) 등으로 호출 시 대입 순서가 정해지지 않는 문제가 있음

Pass by value-result (Inout mode): 위 두개를 합친 형태로 두 단점을 모두 가짐

Pass by reference (Inout mode) : 레퍼런스를 전달해 copy비용이 들지 않음. aliasing이 발생하기 때문에 side effect가 일어날 수 있음

Pass by name (Inout mode) : parameter가 caller에서 입력한 값을 계산할 수 있는 함수(thunk)로 대체되어 사용됨 

 

Data Abstraction

abstract data type (ADT) : user defined type으로 기능들의 protocol과 type을  하나의 문법적 단위에 정의할 수 있어야하고(Encapsulation), 사용자에게 객체의 정보들이 노출되지 않게 있어야함(Information hiding).

 

데이터 추상화는 코드의 모듈화를 위해 필요하며, 수정하기 쉽고 신뢰도를 높일 수 있습니다.

 

Parameterized ADT (Generic class) : 특정 타입에 구애받지 않고 아무 타입이든 이용할 수 있게 해주며, dynamic class를 지원하는 언어에선 필요없다.