Programming Language/Theory

[PLT/프로그래밍언어론] 08. 중간 정리

lumana 2024. 12. 22. 00:50

PLT 중간 정리 1

#PLT

컴퓨터에서 프로그램이 동작하고, 이 프로그램을 작성할 때 PL이 필요하다.
PL을 설계하거나 PL로 프로그램을 개발하기 위해 컴퓨터가 어떻게 작동하는지 알아야 한다.

PL 실행 시 고려해야할 것

Data Type
- 적용 가능한 computation은 데이터 타입에 따라 달라진다.
- 연산의 정확성을 verify하고 올바른 computation을 choose하기 위해 고려
Operator
- 내부적으로 컴퓨터가 어떻게 처리하는지 알 필요는 없다.
- PL은 우리에게 익숙한 computation을 지원하는 operator를 제공한다.
Control of Execution
- 컴퓨터는 연산의 실행을 제어하고, 원하는 결과를 얻으려면 의도한 대로 연산을 실행해야 함.
Control of Data
- 메모리에서 값을 레지스터로 가져와서 계산한 뒤 메모리에 저장하는 데이터 흐름을 제어.
Memory Management
- 프로그램 실행을 위해서는 프로그램을 메모리에 로드해야 하고, 계산할 때도 메모리를 쓴다.
- 메모리에서 데이터를 로드하고 제거하기 위해 Memory Management가 필요하다.
Input and Output
- 컴퓨터는 PL에 I/O 기능을 제공하는데, I/O는 처리 시간이 오래 걸려 효율적으로 처리해야 함.

Turing Machine

계산의 속성을 증명하기 위해 발명된 이론적인 가상 기계
current state를 보고 symbol을 읽는다. 이에 맞는 operation을 하고 이동.

Turing Completeness

모든 computational problem은 turing machine으로 해결할 수 있다고 알려져있다.
튜링 머신을 시뮬레이션하는데 사용될 수 있다면, 이 시스템은 Turing Complete이다.
Turing Complete system은 튜링 머신과 동등한 연산 능력을 가지고 있다. 이는 PL의 이론적 계산 능력이다.

PL을 만드는 방법

새로운 PL의 목적에 유용한 common concepts을 구현해야 한다. drawback을 최소화하면서 목적을 달성.

언어 디자인 기준 3가지

Readability : 언어를 얼마나 쉽게 읽고 이해할 수 있는지?
Writability : 원하는 프로그램을 얼마나 쉽게 작성할 수 있는 언어인지?
Reliability : 언어가 항상 예상대로 작동하는지?

언어 특성

Orthogonality : component를 independently하게 사용할 수 있는지
- PL의 소수의 기본 구성으로 복잡한 프로그램을 만들 수 있다.
- 장점: small set of constructs and rules만 알아도 언어를 사용할 수 있다.
- 단점 : combination 한게 legal 할 지라도, 원하는대로 동작하지 않을 수 있다.
Aliasing : 동일한 객체를 다른 이름으로 참조할 수 있는지
- 프로그래머가 하나 변수값을 바꿀 때 참조 변수가 뭐뭐있는지 다 기억해야 한다. Reliability에 영향
Type Safety, Null Safety, Compatibility, Easy to use/learn, Performance

PL을 구현하는 방법

인간 : High-level, 컴퓨터 : machine instruction
High level language를 low level language로 translating 해야 한다. compiler나 interpreter가 수행
-> PL 구현은 compiler, interpreter 구현과 동일하다.

컴파일러

high level의 complete code -> target machine에서 executable한 program로 변환
object(target) language로 코드를 생성한다. 이걸 Object file 이라고 한다.
Object file은 하나의 실행 프로그램으로 결합된다.
exe의 성능과 효율성에 집중한다. 코드와 실행을 연결하기가 여려움. 컴파일 시 오류를 체크

컴파일 단계

Lexical Analysis : source code를 일련의 tokens로 convert한다.
- int(keyword), a(identifeir), =(operator), 10(number liternal), ;(symbol) 요렇게
Syntax Analysis : sequence of tokens이 correct syntax를 따르는지 확인
- “Parsing”이라고도 함.
- syntatic 구조를 나타내는Concrete Syntax Tree / Parse Tree / Derivation Tree 생성
- a=2+5. ➞ . 이에 맞게 bottom up
- code mean에 대해서 신경쓰지 않음. 단순히 syntax 따르는지
Semantic Analysis: parse tree가 “annotated” or “decorated” 된다.
- 여기서 정보를 수집해서 코드 생성에 사용한다.
- meaning of code를 figure out(파악)하고 evaluate 한다.
Intermediate Code Generation: 타겟 machine에 independent한 intermediate code를 생성
- 컴파일러의 final outcome이 machine dependent 해서, machine independent code optimizations를 하기에 좋지 않기 때문
Code Optimization: exe를 만들기 전에 코드 최적화 해서 코드 개선.
- 인터프리터랑 비교했을 때 가장 중요한 장점 중 하나. 인터프리터는 앞으로 올 코드를 모르니..
- a=ij+k; b=ijk; ➞ tmp=ij; a=tmp+k; b=tmp*k;
Code Generation: Intermediate 코드를 입력받아 equivalent target program 생성
- correct하고, target machine의 리소스를 효율적으로 사용, 효율적으로 코드 generator가 작동

인터프리터

소스 코드를 직접 읽고 평가하여 결과를 얻는다. 가상 컴퓨터를 구현한 다음 거기서 코드를 실행하기도 함.
구현이 쉽고 메모리 덜차지하지만 속도 느림(최적화가 어려움). 런타임 오류가 코드에 연결됨. 일부만 실행 가능

REPL : Read-Eval-Print Loop
인터프리터가 3가지 작업을 반한다. 전체 프로그램이 필요없고, 읽은 것만 평가한다. 런타임에 코드 작성 가능.

Syntax vs. Semantics vs. Pragmatics

Syntax : form of programs
Semantics : meaning of programs. 쥐가 고양이를 찬다?
Pragmatics : certain context에서 meaning of program 쥐가 제리, 고양이가 톰.

Formal Langauge

프로그램의 form. PL이 right/wrong? 올바르게 작성됬는지? 문법 오류가 있는지?를 어케 결정?

Formal Language는 PL의 general 특성들을 abstraction 한 것
set of symbols과 symbol 들이 combined되는 규칙들로 구성됨.
- 이런 것들은 formal language의 grammer로 정의된다.
예시*
E → E + E | E * E | N, N → 0N | 1N | λ
E 변수(lhs)를 E + E(rhs)로 Replace
| 는 OR 기호
람다는 empty string을 의미
E => E + E => N + E => 0N + E => 0 + E => 0 + 1
- 이 문법, 규칙은 binary number equation으로 나타낼 수 있다.Backus Naur Form(BNF)(원래 Normal Form이였는데, Backus-Naur Form으로 바뀜. Normal From이 아님.)
BNF는 context-free grammer를 위한 notiation technique(표기법)이다.
- (context-free grammer : 프로그래밍 언어의 문법을 정의하기 위해 사용됨)
(Language syntax description으로 BNF와 비슷한 방법이 사용된다.)
Variable(or nonterminals): 꺾쇠 괄호 <, >로 둘러싸인다.
- 예시: <expression>, <term>, <operator>
Terminal symbols: 아무런 표식 없이 나타낸다.
- 예시: int, void, for
->를 대신 ::=를 사용해 표현한다. (Entailment라고 생각하면 될 듯)
- 예시: A->B; 를 <A> ::= <B>;로 나타낸다
|는 ‘or’을 나타낸다.
- 예시: <bool-literal> ::= true | false는 파이썬에서 True | False임.

Real Number BNF

<real-num> ::= <int-part>.<frac-part>
<int-part> ::= <digit> | <int-part><digit>
<frac-part> ::= <digit> | <digit><frac-part>
- (<frac-part> ::= <digit> | <frac-part><digit>으로 나타내도 결과는 똑같다.)
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
이 예시에서 start nonterminal는 <real-num>이다. start nonterminal를 string of terminals로 변환하는 과정을 파생(derivation)라고 한다.

Left-most Derivation

둘 이상의 논터미널이 있는 경우 항상 가장 왼쪽의 논터미널을 교체
예시: 3.14

<real-num> ⇒ <int-part>.<frac-part> // 왼쪽 int-part
          ⇒ <digit>.<frac-part> // 왼쪽 digit
          ⇒ 3.<frac-part>
          ⇒ 3.1<frac-part>
          ⇒ 3.14

Right-most Derivation

예시: (()) derivation
(프로그래밍 언어에서 { { } } 요런거에 해당. 우측 괄호 하나만 빠져도 문법적 오류가 발생한다.)

 <balanced> ::= (<balanced>)<balanced> | ε 
                                // or의 왼쪽거는 ( ( ) ) ( ( ) )에 해당
                                // 입실론은 람다(empty string)라고 생각하면 된다.
  <balanced> ⇒ (<balanced>)<balanced>
             ⇒ (<balanced>)ε
             ⇒ (<balanced>)
             ⇒ ((<balanced>)<balanced>)
             ⇒ ((<balanced>)ε)
             ⇒ ((<balanced>))
             ⇒ ((ε))
             ⇒ (())

Extended BNF(EBNF)

BNF보다 간단함. 표기법 몇 개가 추가됨.

{X}: X를 0번 이상 반복한다.
예시:

<statements> ::= {<statement>;} // 아래 3가지 케이스를 요거 하나로 합칠수 있음.
<statements> =>* <statements>; ... <statements>; // x번 반복
<statements> =>* <statements>; // 1번 반복
<statements> =>* ε

[X]: X는 선택적이다. 정규 표현식 스타일로 '?'를 사용할 수 있다.
예시:

<signed> ::= [‘-’]<num>
<signed> ::= ‘-’?<num>
<num> ::= 1|2|3|4
이거로부터 아래 숫자들이 파생된다.
<singed> =>* 1 
<signed> =>* -1
<singed> =>* 2 
<signed> =>* -4
...

* 또는 +와 같은 정규 표현식도 사용할 수 있다.
*: 0번 이상 반복
+ : 최소 1번 반복
(굳이 요건 외울 필요는 없음)

예시:

<digits> ::= <digit>* // *: repeat 0 or more
<digits> ::= {<digit>}
첫 번째랑 두 번재는 EBNF로 표기함. 둘 다 동등한 표현임.
    <digits> =>* ε
    <digits> =>* <digit><digit>....<digit>
세 번째랑 네 번째는 파생 가능한 경우를 말하고 있다.
----------------------------------------------
<digits> ::= <digit>+ // +: repeat at least once
위에랑 동등한 표현이 아래이다.
<digits> ::= <digit>{<digit>} // <digit> 1번 + {<digit>} 0번 이상 = 1번 이상

(X): grouping을 위해 사용된다. 기호들은 그룹 전체에 적용된다.
(그루핑 : 괄호 안의 패턴을 하나의 단위로 묶음)

<eq> ::= <digits>(‘+’<digits>|-<digits>)+(‘ = ’<eq>)*

주의! ’+’와 그냥 +를 구분하자. terminal symbol인지!

'+', '-'는 0번 이상 반복된다.(반복이 0번임. 1번은 등장하고.)
각 반복 시, + 또는 -를 선택할 수 있다.

<digits> + <digits> - <digits> + <digits>...

그 후, 또 다른 <eq>와 =으로 연결된 다른 식으로 계속할 수 있다.

예시:

<digits>+<digits> = <eq> = <eq>...

+ 만 있어도 valid
+ = 만 있어도 valid
+ = = 만 있어도 valid

EBNF로 Real Number 나타내기

BNF로 나타내면

  <real-num> ::= ‘-’<num>|<num>
  <num> ::= <digits>|<digits>.<digits>
  <digits> ::= <digit>|<digit><digits>
  <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

EBNF로 나타내면

  <real-num> ::= [‘-’] <digit>+ [‘.’<digit>+]
  <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

실수를 나타낼 때 정수부에 최소 1개의 숫자는 필요하기 때문에 뒤에 +가 붙는다.
소수부 .뒤에 나오는 뒤에 +가 붙는 이유도 마찬가지
```
<real-num> ::= ‘-’? <digit>+ (‘.’<digit>+)?
```
요렇게도 나타낼 수 있다.

Parsing

지금까지는 derivation에 대해 살펴봤다. valid한지도 검사를 해봐야 한다.
Parsing은 w ∈ L(G)가 어떻게 유도되는지에 대한 sequence of productions를 찾는 과정이다.
(w가 G에 의해 유도될 수 있는가?)

Parse Tree

expression이 주어진 문법으로 유도될 수 있는지 체크하기 위해 Parse Tree를 만들 수 있다.

모든 터미널 노드(리프 노드)는 터미널이거나 𝜀이어야 한다.
모든 중간 노드는 nonterminal이어야 한다.
각 nonterminal은 lhs 규칙에 위치하며, rhs 규칙에 있는 항목들은 nonterminal의 자식 노드가 된다.
루트 노드는 start nonterminal 이다

ex) 3.14*

<int-part><digit>.<frac-part>는 3.14를 만족하지 못한다. <digit>.<frac-part>를 사용

<real-num> ⇒ <int-part>.<frac-part>
           ⇒ <digit>.<frac-part>
           ⇒ 3.<frac-part>
           ⇒ 3.<digit><frac-part>
           ⇒ 3.1<frac-part>
           ⇒ 3.1<digit>
           ⇒ 3.14

Top-down Parsing

start nonterminal로 부터 시작한다.
각 라운드에서 nonterminal에 적용할 수 있는 모든 규칙을 확인한다. 위에서 정수 두가지 케이스 본 것.
- 그래서 exhaustive search parsing(모든 가능성을 시도하는 parsing)이라고도 한다.

문제점

모든 가능성을 다 시도 -> 비효율적.
Non-termination. 주어진 문자열이 주어진 문법으로 유도될 수 없을 때, 파싱이 끝나지 않을 수 있다.

Bottom-up Parsing

주어진 문자열의 terminal을 nonterminal로 줄여나가는 방식이다 (reduce terminal)
3.14 ⇐ <digit>.14처럼 터미널을 non터미널로 줄여나간다. 왼쪽-> 오른쪽으로 진행. 컴파일러 방식

ex) 3.14

  3.14 ⇐ <digit>.14 ⇐ <int-part>.14 ⇐ <int-part>.<frac-part>

<digit> 을 <int-part>로 바꿀 때 애매한 점이 존재한다. 아래에서 자세히 알아보고, 일단 먼저 과정을 쭉 살펴보자

<int-part> ::= <digit> | <int-part><digit>
<frac-part> ::= <digit> | <digit><frac-part>

Ambiguity

만약 두 개 이상의 생성 규칙이 존재할 때, 어느 규칙을 적용해야 할까?
예시: 3.14에서 <digit>은 두 가지 비터미널로 축소될 수 있다.

  <int-part> ::= <digit> | <int-part><digit>
  <frac-part> ::= <digit> | <digit><frac-part>

예시:

<expr> ::= <expr> + <expr> | <expr> * <expr> | a | b | c

a + b * c를 구문 분석할 때, 먼저 <expr> + <expr>를 적용할지 <expr> * <expr>를 적용할지에 따라 두 개의 구문 분석 트리가 생긴다.

만약 PL이 같은 input에 대해 1개보다 많은 Parse tree를 가진다면, ‘ambigous’ 라고 부른다
예시에서 a + b * c의 경우, 연산자 우선순위를 고려해야 한다.
- 이 방식은 syntax가 아닌 semantics에 속하며, syntactically correct *문장이 *semeantically correct하게도 설계되어야 한다.

모호성을 해결하는 한 가지 방법은 문법을 재작성하는 것이다

a + b * c 예시를 다시 생각해보자.

<expr> ::= <expr> + <expr>
        | <expr> * <expr>
        | a | b | c

우리는 +와 * 중 어떤 것을 먼저 고려해야 할 지에 따라서 이 표현식이 두 개의 parse tree를 가지는 것을 안다.

새로운 nonterminal을 도입하여 모호성을 해결할 수 있다.

<expr> ::= <expr> + <term> | <term>
<term> ::= <term> * <var> | <var>
<var> ::= a | b | c

Name

: 단순히 다른 객체를 표현하거나 나타내는 일련의 문자. PL에서는 identifier의 형태
name과 object는 같은 것이 아니다. 하나의 이름이 여러 다른 객체, 하나의 객체가 다른 이름을 가질 수 있다.

Denotable Object

: 이름을 부여할 수 있는 객체들

사용자가 부여 : 변수, 매개변수, 함수….
PL 부여 : primitive types, primitive operations, pre-defined constnats

Binding

: Association(연관성) between a name and a denoted object.
다양한 시점에서 생성될 수 있다
static : 디자인, 프로그램 작성, 컴파일타임
Dynamic : Runtime

Language Design Bindings

: primitive type, primitive operations. 같은 연산이 다른 언어에서 다른 이름으로 표현됨.

Binding Times(바인딩 시점)

Program Writing: 프로그래머가 식별자를 선택하는데, 이는 바인딩의 일부 정의에 해당한다. 이러한 바인딩은 나중에 완성된다.
- ex) int x = 0; x에 해당하는 메모리 공간이 프로그램 실행 시 할당되고 0이 저장딘다.
Compile Time: 컴파일하는 동안, 컴파일러는 글로벌 변수와 같은 일부 데이터 구조에 메모리를 할당
Runtime: 아직 생성되지 않은 모든 바인딩을 완료.
- 지역 변수, 포인터 변수 등등

Referencing Enviornment

: 런타임 중 특정 시점에서 name과 Object 사이의 바인딩 집합
우리는 보통 language definition에서 설정하지 않은 것들에 대한 바인딩만 참조한다.

Declaration

: env에서 binding을 도입(introducing)하는 것

예: int x;, // variable declaration. “x가 integer variable의 이름이다” 바인딩
int func() { return 0; }, // 이 함수가 실행되는 말든 특정 환경에서 우리는 함수 이름에 대한 바인딩을 introducing 한다.
public class Foo;

Single Name - Different Objects

public class Example {
    public int sum;
    public int method() {
        int sum = 0;
        return sum;
    }
}

Single Object - Different Names in Different Environments

서로 다른 env에서는 훨씬 흔하다. Call by reference를 생각하자.

메서드 put() 내부에서, 변수 list는 동일한 ArrayList 객체를 나타낸다. 이 변경은 strings에도 영향을 미친다.

Call by Value는?

값을 복사하여 메서드에 전달한다. 그래서 단일 이름 또는 서로 다른 이름이 나타내는 다른 객체 간의 케이스다.

메서드 put() 내에서 변수 oldStr은 main()의 str과 동일한 값을 가지는 다른 객체를 나타낸다.

Single Object - Different Names in the Same Environment

하나의 객체가 다른 이름을 가지는 경우를 aliasing이라고 하며, 서로 다른 이름들을 별칭(aliases)이라고 함.

)

Block

env를 이해하기 위해서 먼저 {… }를 생각해보자.

block은 시작과 끝을 나타내는 기호로 식별되는 프로그램의 텍스트 영역이다.
해당 region에만 유효한 local declarations을 포함할 수 있다. (외부 영역에는 invalid일 수 있다.)
블록은 여러 방식으로 표현될 수 있다.
보통 블록에 들어가거나 나올 때마다 환경이 변경된다.
블록은 nested(중첩)될 수 있다.
블록의 겹침(overlapping)은 허용되지 않는다.
- 즉, 이전에 열린 블록을 닫기 전까지 마지막으로 연 블록을 닫을 수 없다.
  )
보통 블록 내부에서 우리는 지역 환경을 고려한다.
블록이 겹치면 매우 복잡해지므로, 이는 어떤 프로그래밍 언어에서도 허용되지 않는다.
그러나 블록 중첩 규칙은 각 프로그래밍 언어에 따라 조금씩 다를 수 있다.

Types of Environment

Local environment은 블록 내에서 선언된 이름들에 대한 바인딩 집합이다.
Non-local enviornment은 블록 내에서 선언되지 않았지만 보이는 이름들에 대한 바인딩 집합이다.
```
{
  b
  {
      // b가 여기에 선언되어 있지는 않았지만 사용할 수 있다 : Non-local environment
  }
}
```
Global environment은 프로그램이 시작될 때 생성된 바인딩 집합이다.

Visibility Rules

informal 한 개념임. 특정 블록 내에서 이름이 보일지 여부를 결정하는 규칙. 어떤 바인딩이 유효한지 결정

블록 내의 local declaration은 그 블록과 해당 블록 내부의 모든 다른 블록에서 visible하다
동일한 이름의 새로운 선언이 블록 내에서 이루어지면, 그 새로운 선언이 이전 선언을 hide

current block이 바뀌면 env도 바뀌기 때문에, same name이 다른 object에 연결될 수 있다.
a: 모든 블럭에서 보임. 첫번째 b는 1,2,3에서 보임. 두 번째 b는 2에서만. 두번째 b가 첫번째 b를 숨기므로, 블록 2에서는 항상 두번째 변수 b만 나타난다. 블록3에서는 두번째 b가 안보임. 첫번째 b가 보인다.

Environments

변수 a가 전역 변수라고 가정하자.
그러면 a는 모든 블록에서 보이며, 전역 환경의 일부가 된다.
블록 1의 경우, a의 바인딩은 global 및 non-local environment의 일부가 된다.

local env의 name은 inner block에서 보이지만, outer block에서는 보이지 않는다.
non-local env의 name은 local env의 같은 name에 의해 숨겨진다.
- 더 정확히는, 첫 번째 변수 b의 바인딩은 블록 2의 지역 환경에서 비활성화(deactivated)된다.
이런 것들은 PL마다 다르다. 자바에서는 중복 지역 변수가 안되고, 전역 변수 오버라이드는 됨.

Scope Rule

Visibility rule을 scope rule 이라고도 부른다.

Static vs Dynamic

Static scope(또는 lexical scope)는 오직 프로그램의 syntatic 구조에만 의존한다.
- 따라서 env는 컴파일러에 의해 완전히 결정될 수 있다.
Dynamic scope는 프로그램의 실행 과정을 되돌아가며(backward) binding을 결정한다.
- 따라서 runtime에 결정될 수 있다.

Static Scope Rule

: 가장 가까운 중첩된 스코프의 규칙(the rule of the nearest nested scope)으로 볼 수 있다.

블록 내의 선언은 해당 블록의 지역 환경을 정의한다.
블록 내에서 이름이 사용되면, 해당 이름의 유효한 바인딩은 지역 환경에 있는 것이다. 만약 없다면, 가장 가까운 외부 블록의 것을 찾는다.
- local env에서 먼저 찾고 없으면 가장 neartest outer block에서 찾는다는 것.
블록 자체가 이름과 연관될 수 있으며, 이 이름들은 블록의 지역 환경의 일부가 된다.

Rule 1: Local Declaration

지역적으로 선언된 변수는 지역 환경을 정의한다.

지역적으로 선언된 변수는 지역 환경을 정의한다.
블록 1의 경우, 오직 변수 b만이 이 블록에서 선언되었다.
다른 변수들은 보이거나 보이지 않거나, 보이더라도 지역 환경에 포함되지 않는다.
- a는 block 1에서 non-local임

Rule 2: Nearest Nested Scope

블록 3에서 변수 a가 참조된다.
하지만 이 블록에서는 선언되지 않았다.
규칙 2에 따라, 우리는 먼저 블록 1을 찾는다.
여전히 찾지 못하면 블록 0을 찾는다 ➞ 여기에서 a가 선언되었다.
주의할 점은, 우리는 "중첩된(“nested”)” 블록만을 검색하기 때문에 블록 2는 건너뛴다.

Rule 3: Names assigned to Block

자바 코드에서, 메서드 이름 put, 매개변수 list와 str은 실제로 블록 내에 있지 않다.
그러나 이들은 지역 환경으로 제공된다.
또한, 이들은 외부 블록에서 보이지 않는다. 왜냐하면 지역 환경의 일부이기 때문이다.
- put()은 예외로, 이는 선언이 포함된 블록에 보이는 절차이기 때문이다.

Static Scope의 장점

모든 정적 스코프 규칙은 pre-defined이고, 코드의 syntatic 구조에만 의존한다.
컴파일러는 사용된 이름의 모든 바인딩을 deduce(추론)할 수 있다.
이 사실은 큰 장점을 제공한다:
- 우리는 프로그램을 더 잘 이해할 수 있다.
- 컴파일러는 올바름 검사를 수행할 수 있다.
- 컴파일러는 상당한 최적화를 수행할 수 있다.
  - 변수 바인딩을 예측할 수 있으므로

정리하자면 Static은 지역 환경 -> 가장 가까운 outer block + 블록에 이름이 할당되는 규칙

Dynamic Scope

프로그램의 특정 지점 P에서 이름 X의 유효한 바인딩은 X의 가장 최근에 생성된 바인딩(the most recently created binding)이다.
X는 여전히 지점 P에서 활성 상태여야 한다.

)

static scope rule을 사용하여 코드를 고려해보자:
- 1번째 줄의 x는 전역 변수이다.
- 10번째 줄에서 함수 bar가 호출된다.
- bar는 함수 foo를 호출한다.
- 함수 foo는 3번째 줄에서 1을 출력한다 ➞ 1번째 줄의 x를 사용한다.
- 그런 다음 11번째 줄에서 다시 x를 출력한다 ➞ x는 4번째 줄에서 변경되었다.
  - 따라서 2를 출력한다.

헷갈리지 말자. 중첩되서 선언된게 아님. foo에서 bar의 local x를 볼 수 없음.

Dynamic scope rule을 사용하여 코드를 봐보자.
동적 스코프에서는 이 스크립트의 실제 출력은 다음과 같다:
- 3 (3번째 줄에서 출력됨)
- 1 (11번째 줄에서 출력됨)
- 3번째 줄에서는 이름 x의 가장 최근 바인딩이 7번째 줄에 있다.
  - 따라서 3을 출력한다.
- 11번째 줄에서는 x의 가장 최근 바인딩(4번째 줄의 2)은 이미 사라졌다.
  - (디테일하게 말하면 foo와 bar는 이미 call stack에서 pop 되버림.)
  - bar가 이미 끝남
  - x가 local로 바인딩 된 곳에 2가 저장됬고, 이 로컬이 bar()가 끝나면서 사라짐.
- 따라서 1을 출력한다.

동적 스코프는 함수 호출 시점에서 가장 가까운 스코프에서 결정됨(call stack). 정적 스코프는 함수가 정의된 시점에서 스코프가 결정된다. Local 먼저 찾고 그다음 가까운 outer로 간다. 코드 레벨.

동적 스코프의 장점

프로그램 재작성 없이 동작을 쉽게 수정할 수 있다.
단점 : 코드 이해가 굉장히 어려워진다.

Memory Management

인터프리터의 주요 기능. 프로그램이 실행되는 동안 다양한 정보(지역변수, 임시값..)가 생성/로드/저장
PL에서는 메모리 접근 처리 방법을 결정해야 한다.

Subprogram(a.k.a procedure, routine, function)

함수, 루틴, 프로시저 다 같은 의미로 사용하겠다. 이론적으로는 반환 값이 있는 것을 subprogram이라고 함.

Stack

데이터를 쌓는 자료구조. LIFO 구조. 데이터 push/pop

Stack and Procedure

스택은 프로시저에 적합하다. 프로시저 또한 LIFO 구조로 호출/종료되기 때문. Env도 이 방식으로 처리 가능

Heap(자료구조 아님)

힙은 pq나 힙 정렬과 관련된 자료구조이지만, PL에서는 프로그램이 allocated 될 수 있는 특정 메모리 공간

Static Management

프로그램 실행 전에 compiler에 의해 performed된다.
Statically allocate objects는 고정된 메모리 영역에 위치하고, 프로그램 실행 동안 그자리에 머무름.

Which can be allocated statically?

Global Variable: 프로그램 전체에서 사용 가능.
Object Code: 컴파일러에 의해 생성된 machine instruction
Constants: 컴파일 시점에서 그 값이 결정될 수 있을 때만
Compiler-generated Tables: 런타임중 프로그램의 support를 위해 사용됨.

Without Recursion(재귀가 없는 경우)

재귀가 없으면 두 개 이상의 프로시저가 동시에 활성화될 수 없음 -> PL의 다른 components를 정적으로 처리
ex) local variable(동일한 지역 변수는 스택에서 한 번만 나타남), argument, 임시 값, r.v, return address…

Dynamic Management

Static Management 만으론 충분하지 않다. 런타임 이전에 모든 component를 결정할 수 없음.
스택과 힙을 사용해서 Dynamic memory management를 할 수 있다.

Dynamic Management - Stack

procedure activation or inline block에 할당된 각 메모리 공간을 activation record or frame이라 한다.
- activation : 프로시저나 인라인 블록을 실행하는 것
activation records를 담고 있는 스택을 runtime stack이라고 한다.

Activation Record

Inline block의 activation records는 procecure activation records의 부분집합. 빨간색이 공통인 것들.
(적어도 빨간색은 외워둬야 하지 않을까)

Activation Record - Dynamic Link

activation record에는 local variable이랑 intermediate result가 들어간다.
Dynamic Link는 스택에서 이전 activation record의 시작부분을 가리킨다.
- activation record 크기가 각각 다르기 때문에 필요함
시작부분부터 특정 local variable을 찾으려고 local offset을 사용할 수 있다.

Activation Record - 나머지

Return Address : 프로시저 호출이 끝난 후 실행될 다음 명령어 주소
Address for Return Value : Return value는 caller의 frame에 저장된다
- a가 b를 호출한다면, 리턴 값이 저장될 주소를 b에게 알려주고, a에 리턴 값이 저장된다.
Parameter : Caller 로 부터 전달된 값

Stack Management

A(caller)와 B(callee)는 runtime stack에서 Activation Record를 저장/삭제한다.

Activation Record Pointer: frame pointer 또는 current environment pointer라고 불림
Stack Top Pointer: 스택에서 “free space”의 시작 지점을 가리킨다.

Procedure Call

Calling Sequence는 컴파일러에 의해 프로시저 호출 직전과 직후(immdediately before and after)에 삽입된다.
Prologue와 Epilogue는 프로시저 실행 전 후(before and after)에 삽입된다.
위에서 말한 3가지의 코드 fragment는 컴파일러와 implementation마다 다르다.
코드 크기의 최적화를 위해서 callee에게 대부분 코드가 할당된다.
- calling sequence는 컴파일 시간에 여러 번 추가되지만, Prologue, Epilogue는 definition할 때 한 번만 삽입되므로, call마다 여러 번 추가할 필요가 없다.

Tasks before Procedure Call : Calling sequence & Prologue

Program Counter Modification
Stack Space Allocation
Activation Record Pointer Modification
Parameter Passing
Register Save
Initialize Code Execution

Tasks after Procedure Call : Epilogue & Calling sequence

Update Program Counter
Value Return
Return of Registers
Finalize Code Execution
Stack Space Deallocation

Heap - Dynamic Management

스택 말고도 힙이 필요하다. 일부 PL이 explicit memory allocation을 허용하는 stataement 때문

Explicit Memory Allocation

explicit memory allocation에는 LIFO가 적용되지 않는다.
위 예시만 봐도 p가 먼저 할당되고 먼저 해제됨. 스택이라면 p를 q보다 먼저 해제할 수 없음.

Heap Management

Heap management method는 memory block을 다루는 방법에 따라 두 가지로 나뉜다.

Fixed Length Blocks
Variable Length Blocks

Heap Management - Fixed Length Block

Heap을 여러 개의 fixed length blocks으로 나눈다.
free block list을 관리하기 위해 free list를 사용한다.
request마다 first free block이 할당되고, 할당된 block은 free list에서 제거된다.
free list의 pointer는 리스트에 있는 first block을 가리킨다.
)
블록이 해제되면 블록이 다시 free list에 추가됩니다.
request를 충족하기 위해 여러 블럭이 할당될 수 있다.
- ex) 만약 한 칸이 4KB이고, 15KB만큼 요청이 오면 16KB를 할당해야 한다

Heap Management - Variable Length Blocks

n > k 이고 n < m이라서, third free block에 할당된다.
애도 free list를 사용하지만, block의 크기가 다를 수 있다. 요청된 크기에 맞는 block을 할당해준다.

Variable Length Blocks -> Fragmentation

가변 길이 -> fragmentation을 유발할 수 있다.
fragmentation 때문에 메모리 공간이 낭비될 수 있고, 프로그램 성능도 저하될 수 있다.

Internal Fragmentation

m > n이면, d = m - n 만큼 낭비된다.
할당된 블록 크기가 요청된 크기보다 큰 경우, 공간이 남아서 낭비된다.

External Fragmentation

m + k > n 이지만 consecutive(연속적)이지 않아 할당을 못하고 있다.
free block들이 흩어져 있어 요청된 메모리를 할당할 수 없는 경우를 말한다.

결론: fragmentation은 heap managemet method을 고려할 때 중요한 요소이다.

Solution1: Using Single Free List

)

크기 n의 메모리 할당 요청이 있을 때, free list를 직접 사용하자.

First Fit: 크기 n보다 큰 첫 번째 블록을 할당
Best Fit: 크기 n 이상이며, 가장 작은 차이(d=k-n)를 가진 블록을 할당
- Internal Fragmentation 최소화하는데 사용되는 방법
Free Memory Compaction(압축): 힙의 끝에 도달하면 모든 activation block을 힙의 끝으로 이동
- 여전히 할당한 공간이 없다면, 런타임 에러가 발생한다(힙 공간 부족)
- External Fragment을 해결하기 위한 방법

Solution2: Multiple Free Lists : Buddy System

)

2의 제곱 크기에 해당하는 free list 여러 개를 사용한다.
크기가 n인 요청이 오면, 먼저 2^k >= n인 블록을 2^k free list에서 찾는다.
- 만약 available block이 없으면 2^(k+1) free list에서 찾는다.
2^(k+1) free list에서 찾으면 그 블럭을 두 개의 2^k로 split한다.
- 2^k 하나는 할당되고, 나머지 하나는 2^k free list에 연결된다
할당된 block이 해제되면, 분할된 buddy를 찾아서 결합 -> 2^(k+1) free list에 attach 된다
- Fibonacci Heap : 2^n 단위 사이즈 대신 피보나치 수열의 수를 block size로 사용

Scope Rule Implementation

Static Scope Rule Implementation

)

주의 ) A: B:는 프로시저가 아님!

Static Scope Rule 구현은 스택 사용보다 많은 관리가 필요하다
ex) 프로시저 foo에서 변수 x는 블록 B의 x를 참조하지만(선언 기준), dynamic link로 foo에 연결된 activation record는 블록 C입니다. (실행 기준이니까)
block을 즉시 둘러싼 block에 대한 link가 필요하다. (선언 기준인 정적 스코프를 위해서)
-> static link를 사용해서 둘러싼 block의 activation record를 가리킨다.
static scope를 관리할 때는 dynamic link 대신 static link를 사용한다.

Static scope - static link - 선언 기준 : 값을 가져올 때 선언 기준
Dynamic scope - 값을 가져올 때 call stack 기준

Dynamic link - Stack, Heap - 실행 기준

Static Link

Activation record가 stack에 추가될 때, static link의 주소를 결정해야 한다(내부에 포함되어 있으니)
- 즉 static link로 어떤 활성화 레코드를 가리켜야 할 지 정해야 한다.
일반적으로는 caller가 link를 계산해서 callee에게 전달한다.
두 가지 케이스로 나뉜다.

Static Link Example: Case1 - Callee가 Caller 외부에 있을 때

Block B랑 C는 Block A 내부에서 선언되어 있다. D와 E는 C 내부에 있다.
A->B->C->D->E->C 순으로 호출한다고 해보자.

예시: E가 C를 호출하지만, C는 E의 외부에 있다

callee(C)는 visibility rule에 따라 caller(E)의 block 외부에 있어야 한다.
- callee(C)의 activation record는 이미 stack에 있다.
C가 E랑 static link를 맺는게 아니라, C의 direct outside block인 A와 Static Link를 한다.
static link를 backtrace하여 new block을 위한 new link를 찾을 수 있다.

결론 : Callee가 Caller 외부에 있으면 Callee는 direct outside block(선언기준)과 static link를 한다.

Static Link Example: Case2 - Callee가 Caller 내부에 있을 때

예시: C가 D를 호출하는데, D는 C 내부에 있다

visibility rule에 따라 callee가 caller 블럭 내부에 선언되어 있다.
따라서 단순하게 Static link를 caller에게 해주면 된다.

Display

Static Link는 프로시저 호출마다 여러 번 메모리 접근을 해야 한다.
non-local이 k개 블록 떨어져있으면 static link를 k번 따라가야 한다.
보통은 중첩이 많지 않아 큰 문제가 발생하지는 않지만 Display를 쓰면 constant memory accesses (twice)만 필요하다
)
Display라고 불리는 벡터를 사용하는 방법이다.
Display의 k번째 요소는 k번째 중첩 레벨의 현재 activation record pointer를 담고 있다.
non-local name이 레벨 n에서 선언된 경우에 Display n번째 element로 가서 offset을 이용해 name을 찾는다.
프로시저가 k 레벨에서 호출되면, Display의 k번째 요소는 callee의 activation record pointer로 업데이트 한다.
(참고로 Static Link의 레벨을 다루는 거니까 호출 기준이 아니라 선언 기준임.)
만약 같은 레벨에서 프로시저가 호출된다면, 디스플레이의 이전 값을 저장해야 합니다.
블록 C가 2레벨에서 호출되었으므로, 블록 B의 이전 포인터는 C에서 B로 연결된 링크로 저장됩니다.
- 기존에 있는 것을 새로 들어온 얘가 가리킨다.
C가 스택에서 빠져나간 후 이 값을 복원할 수 있습니다.
- C가 스택에서 나갈 때 C가 가리키는 걸 다시 Display에 넣어준다.
  
  callee(블록 D)가 caller(블록 C) 내부에 있을 경우(= 레벨이 증가하는 경우), 디스플레이의 길이를 늘려 다음 요소(3번째 요소)에 포인터를 넣는다.
블록 E가 호출되면, 디스플레이 3번째 요소의 이전 값이 저장됩니다. (같은 레벨이니까)
그런 다음 Display 3에서 블록 E에 대한 포인터가 업데이트됩니다.
변수 x가 블록 C에서 선언되고, 블록 E에서 사용된다고 가정해봅시다.
- 컴파일 시점에 우리는 x가 C에 선언된 것을 알고 있습니다(Static Scope를 통해서).
- 블록 C는 2레벨에 있으므로 디스플레이의 2번째 요소를 확인하고, 로컬 오프셋을 사용해 x의 바인딩을 찾을 수 있습니다.
  
  블록 E에서 블록 C가 호출된다. (더 낮은 레벨이 호출되는 경우)
블록 E에서 선언된 로컬 이름을 블록 C에서는 사용할 수 없다.
이거를 Display로 어떻게 구현할까?
일단 Display의 level2가 새로 호출된 C 활성화 레코드를 가리키도록 한다. 그리고 기존에 있던 C를 새로운 C가 가리킨다.
level2 이후 요소(level3, …)들은 비활성화된다.

Dynamic Scope Rule Implementation

)

Dynamic scope에서 non-local은 활성화된 순서대로 고려된다.
- 따라서 스택을 backward하여 적절한 바인딩을 찾아야 합니다. (call stack)
A, B, C, D 호출을 생각해봅시다. 회색으로 표시된 것은 deactivated된 바인딩을 나타낸다.

Association List

Activation Record에 직접 바인딩을 저장하는 대신, 바인딩을 Association list(A-list)에 별도로 저장할 수 있습니다.
프로그램이 새로운 env에 진입하면, 바인딩이 A-list에 삽입되고, env에서 벗어날 때 제거됩니다.
x: CC end -> x:B
두 가지 단점

Name을 런타임 중 structures(구조체)에 저장해야 합니다.
Name의 위치를 compile time에 추적할 수 없습니다.

런타임에 이름을 검색하는 것은 inefficient일 수 있다. 리스트 전체를 확인해야 할 수도 있다.

Central Referencing Table를 쓰자

Central Referencing Table

이러한 단점을 해결하기 위해 Central Referencing Table, CRT을 사용한다.

프로그램에서 사용된 모든 name이 CRT에 저장됩니다.
각 name에는 activate 또는 inactivate를 나타내는 flag가 있습니다.
name의 유효한 바인딩은 스택에 쌓여 있으며, 비활성화된 바인딩은 그 아래에 있습니다.

)
(왼쪽이랑 오른쪽이랑 다른 예시임)
위를 개선한게 아래. 변수마다 스택 대신 하나의 hidden stack을 사용한다.
inactivate 바인딩은 hidden stack에 저장되며, 다시 activated될 때 복원된다.
세 번째 열은 이름에 해당하는 실제 denotable object 대한 참조를 담고 있다.

A열고 B열고 B닫고 C열고 D열고 D닫고 C닫고 A를 닫는 구조
Enter

env에 있는 변수들이 활성화되어있으면 스택에 이름과 실제 denotable object 참조를 push한다.
그게 아니면 flag 1로 바꿔주고 Reference를 넣어준다.
Exit
나가는 env의 변수 중에서 만약 스택에 존재하는게 있다면 스택에 있는 걸로 원복해준다.
- a,b,c로 넣었다면 스택에는 top부터 c,b,a로 있으므로, c,b,a 순으로 검사해야 함.
스택에 없다면 flag를 0으로 바꿔준다.

'Programming Language > Theory' 카테고리의 다른 글

[PLT/프로그래밍언어론] 10. Object Oriented Paradigm (0)	2024.12.22
[PLT/프로그래밍언어론] 09. PL Paradigms, Scripting Language (0)	2024.12.22
[PLT/프로그래밍언어론] 07. Control Abstraction and Data Types (0)	2024.12.21
[PLT/프로그래밍언어론] 06. Control Structure (0)	2024.12.21
[PLT/프로그래밍언어론] 05. Memory Management (0)	2024.11.20

현재글[PLT/프로그래밍언어론] 08. 중간 정리

Brute force Study

배움을 나누는 공간 https://github.com/DawnGlow

Today :
Yesterday :

« 2024/12 »
일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31