감명 깊었던 programming language principles 4- 기계 중심 언어

기계 중심의 언어

초기에 컴퓨터 사이언스는 튜링 머신이나 람다 컬큐러스를 기반으로 컴퓨터와 프로그래밍 언어를 만드는 것에 의의가 있었고, 그러다 보니 자연스럽게 기계 자체를 동작시키는데 가장 큰 목적이 있었습니다.

그 당시는 이제 시작 단계라서 어떻게 프로그래밍 언어를 디자인해야 하는지 무엇이 문제일지가 드러나지 않은 상태 였습니다.

 처음에 기대했던, 기계중심의 언어는 이런것이다.!! 라고 간단하게 정의 되어있을 것이라 기대하고 읽기 시작 하실 것입니다.

그러나, 내용은 사실 그렇게 명쾌하게 나오지 않습니다. 언어가 어떤 수학적 정의를 바탕으로 설계가 되었고, 

그 한계가 무엇인지는 프로그래밍 언어의 요소들을 하나 하나 살펴보면서  짚어갈 수 밖에 없습니다.

예를 들면 변수란 무엇인가? 함수는 무엇인가? 재귀 호출이 무엇인가?  하는 것들이죠. 이미 프로그램 개발 경험이 많고, 여러가지 프로그래밍 언어 교제들을 통해서, 다들 알고 있는 개념들입니다.

하지만 그것들이 무엇인지 정확하게 수학적으로 어떤 의미가 있고, 그래서 어떤것이 미흡한지에 대한 이해와는 다를 것입니다.

언어의 요소들에 대해서 깊이있게 이해하고 새로운 시각을 갖기 위한 과정이 이 programming language principles  입니다. 

"옆에 컴퓨터가 있다, 사용해야 한다, 컴퓨터에게 시킬 일을 편하게 정의할 수 있는 방법을 고안하자." 이렇게 해서 C언어를 만들었던 과정은 .....

아.주. 상식적인 과정(현재에서 바라봤을때)을 밟았습니다.

이 과정들에는 현재 불합리한 부분들도 있고, 이런 과정을 바탕으로 프로그래밍 언어의 발전에서 살아남은 것들도 있습니다. 

우리는 이 살아남은 것들은 앞으로도 살아남을 가능성이 매우큰 것들이고, 우리는 이런 것들을 확인하고 이해해둔다면,  프로그래밍 언어와 컴퓨터 사이언스 부분에 대한 이해의 폭이 넓고 깊어질 것이라 보입니다.

어쩌면 현재의 바람직한 프로그래밍 기술 및 기법들은 미래에 보면 어설픈 모습으로 보일 가능성이 있습니다.

주어진 기계 - 메모리, 중앙처리장치, 입출력이 가능하다.

중앙 처리장치는 기초적인 기계어 명령들을 처리하는 실행기 입니다. 실행할 수 있는 기계어 명령의 갯수는 유한하고 고정되어 있습니다. 

(매우 작은 전기줄로 구성되어있고...)

그 기계는 폰 노이만 머신(Von Neuman machine) 입니다.        

"기계가 실행할 명령문들이 메모리에 보관될 수 있다. 그 기계는 명령문 하나 하나를 메모리에서 읽어와서 실행한다. 명령문 들에 따라 그 기계는 다른 일을 한다" 그 명령문들이 프로그램이죠.

이렇게 기계를 구동시키는 명령어들을 다루는 방식을 좀더 편리하게 사용해보자... 언어입니다. 기계어 보다 좀더 상위의 언어를 고안해봅시다. (사실은 이미 있는 것을 밟아나가갔던 과정을 지나가봅시다.)

1. 변수 : 메모리 주소에 이름 붙이기

 "명령문 여러개가 순서대로 실행된다. 반복이 있다. 입출력이 있다. 조건에 따라 명령이 구분되어 실행된다."

이런 기초적인 조건들을 갖는 기초적인 문법의 언어가 있습니다.

명령문

Command\quad C\quad \rightarrow \quad skip \\

\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad|\quad x:=E\\

\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad|\quad C;C \\

\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad|\quad if \quad E \quad then \quad C \quad else \quad C \\

\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad|\quad while\quad E \quad do \quad C\\

\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad|\quad for  \quad x:=E\quad to \quad E \quad do \quad C\\

\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad|\quad read \quad x \\

\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad|\quad write \quad E

식

프로그램

                                      

각 명령문과 식의 의미를 정확히 정의할 필요가 있습니다.

우선 의미를 정의해갈 때 사용할 원소 semantic object들이 어느 집합(의미공간) semantic domain 의 원소들인지를 정해야 합니다. 

1. 값은 정수거나 참/거짓이다.- 값의 집합은 정수집합이거나 참 거짓의 집합이다.

2. 메모리는 기계적으로는 전기줄에 매달린 트랜지스터 이겠지만, 좀더 추상화 시키면, 논리 게이트, 더 추상화 시키면 주소에서 값으로 가는 테이블 입니다.

3. 테이블은 수학적으로는 하나의 함수입니다. - 정의 구역은 메모리 주소, 공변역은 값.

4. 정의 구역은 메모리 주소 집합중에서 유한한 집합이다.

5. 주소는 프로그래머가 사용하는 이름들의 집합으로 정의한다.

의미공간( semantic domain) 들은 아래와 같습니다.

프로그램의 의미는 논리 시스템의 증명 규칙들로 정의 된됩니다.

MㅏC=>M' 와 MㅏE=>v 를 증명하는 규칙들이 될것 입니다. 이러한 증명이 불가능 한 C와 E는 의미 없는 것이 됩니다.

이름은 메모리 주소가 됩니다.

이름이 하는 역할에 대해서 대해서 살펴보자. 이름은 2가지 의미를 가집니다.

1. 메모리 주소

2. 때로는 메모리 주소에 있는 값

이렇게 이름이 뜻하는 두개의 값을 L-value 와 R-value라고 부릅니다.  

x:=E의 왼쪽과 오른쪽에 대한 정의가 다름을 의미합니다. 왼쪽은 메모리 주소, 오른쪽은 메모리 주소에 보관된 값 입니다.

깊이있게 들어와서 변수가 뜻하는 의미가 모호해 지는 것이 싫다면, 두가지를 다르게 표현 하는 방법도 있습니다.

메모리 주소의 값을  뜻할때 이름 앞에 !를 표시 하는 것으로 합시다. 그러면 다음과 같아집니다.

x:=x+1 은 x:=!x+1 과 같이 사용되게 됩니다. x+y+1 대신 !x+!y+1 로 사용해야 합니다.

이름은 기계중심의 언어에서는 변수(variable)이라고 부릅니다.

프로그래머가 메모리 주소에 이름을 짓기 시작하면서 문제가 생깁니다. 

같은 이름을 다른 용도로 사용 하고 싶을때, 같은 이름을 다른 메모리 주소를 위해 재사용 하고 싶을때 , 프로그램이 커지다 보면 이런 경우들이 발생하게 됩니다.

항상 다른 이름을 사용해야 한다면, 프로그래머의 불편은 클 것입니다.

우리가 서두에서 정의한 언어는 같은 이름을 다른 메모리 주소로 사용할 수 없습니다. 때문에 매번 다른 이름을 사용해야 합니다.

이를 해결하기 위한 방안은 이미 있습니다. 수학이나 모든 엄밀한 논술에서 사용하는 방안입니다. 이름의 유효범위를 정하는 것입니다.

유효범위가 겹치지 않는다면, 같은 이름을 다른 메모리 주소로 사용할 수 있습니다. 

그 유효범위는 어떻게 표시 할것인가? 수학에서 사용하는 방식을 빌려옵니다.(이 방식은 수학에서 이미 지난 2000년간 사용해온 믿을만한 방식입니다.)

프로그램의 텍스트의 범위로 이름의 유효 범위를 결정하는 것입니다.

                                                      

x라는 이름은 새로운 메모리 주소이고 이는 명령문 C 안에서만 유효합니다. let 구문에 의한 유효범위가 일부만 겹치는 경우는 없습니다.  포함되거나 별개이거나...

같은 이름으로 다른 것을 지칭 할 수 있도록 하기 위해서는 위와 같은 규칙을 정확히 드러내야 합니다. 

환경(Environment)

환경이라는 것을 가지고 의미구조를 정확히 정의 할 수 있습니다.

환경은 이름의 실체를 정의한 함수입니다. 

- 환경(시그마)은 이름들에서 주소들로 가는 유한한 함수 입니다.

- 메모리는 주소들에 값들을 대응시키는 유한한 함수입니다.

- 주소는 더이상 프로그램에 나타나는 이름이 될 수 없습니다. (주소는 다른 집합이 될것입니다.)

설탕 구조 - 패스

프로시져(Procedure)

메모리 주소 뿐아니라 명령문에도 이름을 붙일 수 있도록 하자.!!!! 명령문을 반복적으로 사용하지 않고 이름 만으로 그 명령문을 수행 할 수 있도록,...

  let f(x) = C in C'

1. 프로시져 이름 은 f, 인자 이름은 x, f는 명령문 C의 이름 입니다.

2. x는 프로시져가 사용될 때의 인자값을 보관하는 메모리 주소의 이름입니다.

     x의  유효 범위는 C 입니다.

3. f의 유효범위는 C'. 재귀호출이 가능한 프로시져를 위해서는 f의 유효범위는 C' 뿐 아니라 C까지 포함되어야 합니다.

4. f(E) 는 f로 이름붙은 명령문을 실행합니다.

   그런데 E 값을 인자로 사용하라는 것인데, 의미를 정확히 해보자면, 

   우선 환경을 확장할 필요가 있습니다. 

동적으로 결정되는 이름의 유효범위(Dynamic scope)

정의 :Procedure = Id x Command

(이렇게 해보자)

두 집합 A, B가 있을 때 AxB는 두집합의 원소들으 쌍으로 구성된 집합입니다.

- 프로시져가 선언되면 프로시져 이름의 실체는 해당 명령문과 인자 이름이 됩니다.

- 프로시져 호출이 일어나면, 인자에 대해서는 let 명령문 같은 일이 벌어집니다. 

  새로운 메모리 주소를 프로시져 인자 이름으로 명명하고 그 주소에 인자로 전달할 값을 저장 하고, 프로시져 이름이 지칭하는 명령문을 실행합니다.

- 프로시져 이름이 지칭하는 명령문을 프로시져 몸통이라고 합니다.

아래의 프로그램 실행을 생각해보자.

let x := 0 in      let proc inc(n) = x:=x+n in          let x := 1 in (inc(1); write x)

let x:=10 in

    inc(5);--> 10+5

    inc(6); --> 15+6

    let x:=3 in 

       inc(1)

--- 재귀호출 이죠.

프로시져 호출 inc(1) 의 실행중에 몸통 명령문인 x:=x+n 에 나타나는 x는 무엇이 될까요? 처음 선언된 x? 아니면 두번째 선언된 x ?

위의 의미로는 두번째 선언된 x입니다.

이것이 이상한가요? 다음 C와 문법이 똑 같은 Dynamic scope 으로 동작하는 언어를 생각해봅시다.( 익숙한 것이 이해하기 편하니까요.)

int x = 10;

int test(int a) {    return x + a; }  -> x는 결정되지 않음.

int test2()

{

  int x = 50;

   return test(5);  <-- 50 +5 : main에서 test2가 수행될때 x가 결정됨.

}

void main(void)

{

 int res = test2();   <-- 50 +5 : x가 test2 내부에서 결정 결정됨.

 int res1 = test(5); <-- 10+5 : x는 10 (맨 위에서 global로 선언된 )

 

 int x = 15;

 int res2 = test(5); <-- 15+5 : x는 15 (바로 위에 있는)

}

이렇게 X가 procedure 가 선언 된 시점에 결정 된 것이 아니라, 호출 되는 시점에 결정되는 구조는 프로그램이 실행중에 동작이 바뀐다는 의미가 됩니다. 어려운 프로그램이 되겠죠.

정적으로 결정되는 유효 범위( static scope)

이름의 실체는 실행전에 정의 되어야 하지 않을까요?

프로시저 안에서 어떤 수식을 계산하기 위한 변수들은 프로시저를 정의 하는 시점에 이미 결정되어야 쉬워집니다. 적어도 동적으로 결정되는 것 보다는 말이죠.

이런 방식이 프로그램을 이해하기에 간단하고 쉽습니다. 그리고 이런 방식이 위에서 언급한 2000년간 사용해온 규칙이기도 합니다.

                                                                      

이렇게 되면 프로시져 정의와 호출의 의미가 아래와 같이 정의 됩니다.

                       

프로시져 호출 방법

지금까지 방식은 값 전달 방식(Call by value)이었습니다.

                       

그런데 이름이 뜻하는 메모리 주소를 전달해 줄 방법이 있었으면 한다. 그러기 위해서는 프로시져 호출문의 생김새부터 구분해주자.

주소를 전달해줄 call-by-reference 의 정의는 다음과 같습니다.

                 

이렇게 되면, 다른 이름이 같은 메모리 주소를 지칭할 수 있게 됩니다.. 같은 대상을 지칭하는 다른 두개의 이름들이 생기게됩니다.( 별명:alias)

생각해 볼 문제는..

별명이 많아지면 프로그램을 이해하기가 어려워지지 않을까? 이런 별명들이 프로시져 호출에 의해서 실행중에 만들어진다면, 이런 다이나미즘, 혼돈스럽지 않을까?

이런 복잡한 상황을 지원하는 언어는 바람직한가?

명령문과 식의 통합

프로시져 호출은 명령문이었습니다.( 지금까지 정의한 언어로는 그렇다) 

메모리에 반을을 일으키는 프로시져 호출의 결과로 값이 계산되게 하고 싶으면?, 메모리를 변화시킨후에 최종적으로 어느 값을 결과로 내놓는 식이 있으면 어떤가? 

C에서는 return E 같은 명령문이 이 역할을 합니다. 

그런데 생각해보면, 명령문과 식, 두가지는 과연 다른가요? 

1. 메모리에 값을 쓸수 있는 것과 메모리를 읽기만 하는것. 

2. 결과 값이 없는 것과 결과 값이 있는것. 

3. 식의 실행결과는 항상 어떤 값이 된다.

4. 그리고 식은 메모리 변화를 일으킬 수 도 있다.

하나로 합칠 수 있습니다.

식

프로그램

                                  

프로그래머는 더욱 간단한 언어를 가지고 더욱 자유롭게 프로그래밍을 하게 될 것입니다. 명령문의 개념이 없어지고 모든 것이 식이 되기 때문입니다.

명령문 과 식 두가지 다른 타입의 프로그램 부품을 운용할 필요가 없습니다.

의미 정의는

                           

을 증명하는 규칙들로 통일 됩니다.    명령문 들은 의미없는 빈 값 "." 을 계산한다고 하면,

                      

와 같습니다.

다음 >> 기계중심의 언어 - 메모리 관리와 타입 시스템.