Computer Science & Engineering

메모리에서 변수를 저장하는 부분은 static 영역과 dynamic 영역으로 나뉜다. static영역은 프로그램이 시작될 때부터 종료될 때까지 메모리 공간을 차지하고 있는 전역변수가 저장되어 있다. dynamic 영역에는 local 변수들이 저장되어 있다. dynamic 영역은 stack 영역과 heap 영역으로 나뉜다. 그렇다면 어떤 변수들이 stack영역으로, 어떤 변수들이 heap 영역에 저장될까?

1. Stack-dynamic variable

    스택 다이나믹 변수는 프로그램에서 함수가 호출되어 실행될 때 아래의 그림과 같이 함수의 지역 변수들이 stack 영역에 저장된다.

func1에서 func2를 호출하고 func2에서 func3을 호출한 경우 위의 그림과 같이 stack영역에 저장된다. func3함수가 종료한 경우 stack영역에서 pop하게 된다. 그 다음 func2가 종료할 경우 stack 영역에는 func1의 지역 변수만 남게 된다. stack-dynamic 변수는 선언문이 수행될 때 storage binding이 일어난다. 즉 컴파일하는 시간에 메모리가 할당되는 것이 아니라 런타임에 storage binding이 일어난다는 것이다. 하지만 type binding은 프로그램이 실행되기 전에 static하게 일어난다.

2. Heap-dynamic variable

    힙 다이나믹 변수에는 두 가지가 있다. 첫 번째는 explicit heap-dynamic variable이고 다른 하나는 implicit heap-dynamic variable이다.

    Java의 경우 모든 객체를 heap 영역에 저장하므로 implicit(암묵적) 힙 다이나믹을 사용한다. implicit heap dynamic은 말 그대로 메모리를 할당이 자동적으로 된다. 배정문(assignment statement)가 실행될 때 heap storage에 binding된다.

    explicit(명시적) heap-dynamic 변수의 경우 프로그래머가 직접 메모리를 할당해주게 된다. 아래는 C언어의 explicit heap-dynamic의 예시이다.

char* explicit = (char*(malloc(sizeof(char)*10);
explicit = "hello\n";
printf("%s", explicit);
free(explicit);

malloc을 이용해 explicit 변수가 사용할 힙 영역을 크기 10만큼 동적할당한다. 저 동적할당문이 실행될 때 메모리가 할당된다. 프로그래머는 동적할당을 받은 변수를 사용한 다음 명시적으로 메모리를 반환해줘야한다. C언어에서는 free를 이용하여 반환해줬다. 만약 free하지 않고 메모리를 가리키는 포인터를 없애는 경우 Garbage 메모리가 생길 수 있다. 또 메모리를 해제하였지만 그 메모리를 가리키고 있는 또 다른 포인터는 그대로 있는 경우가 발생할 수 있다. 그런 포인터를 dangling pointer라고 한다. dangling pointer의 경우 가리키고 있는 엉뚱한 메모리를 읽거나 써서 프로그램에 문제를 발생시킬 수 있으므로 굉장히 조심해야 한다.

    변수의 Life time은 프로세스가 실행되었을 때 데이터인 변수가 메모리를 할당받고 저장되어 공간을 차지하고 있는 시간을 말한다. 전역변수는 프로그램 어디에서든 접근이 가능해야한다. 따라서 프로그램의 시작부터 종료까지 메모리를 차지하고 있어야하고 프로그램이 시작될 때부터 종료될 때까지가 전역변수의 life time이다. 지역 변수는 전역 변수와 달리 함수나 블록 내부에서 선언된다. 그렇기 때문에 그 블록을 나가게 되면 더 이상 필요가 없기 때문에 메모리를 반환하고 사라지게 된다. 따라서 지역변수의 life time은 함수나 블록 내부에서 선언되어 메모리에 할당되는 순간부터 그 지역변수를 감싸는 블록이 끝나 메모리에서 해제되는 순간까지이다. 

    변수의 Scope는 변수에 접근할 수 있는 범위를 말한다. 이는 변수의 Life time과 밀접하게 연관된다. 메모리에 변수가 존재해야 접근할 수 있기 때문이다. 변수의 종류는 크게 2가지가 있다. 하나는 Global 변수, 다른 하나는 Local 변수이다. 이 2가지에 추가하여 언어가 함수의 nesting을 허용을 하는 경우 non-local이 존재하기도 한다. 함수의 nesting은 함수 안에 함수를 선언하는 것을 말한다. 아래의 python코드와 같이 말이다.

def out_func(int a):
	a += 10
	def in_func(int b):
    	b += a

이 코드에서 out_func 안에 in_func이 존재한다. 이때 out_func는 부모가 되고 in_func은 자식이 된다. 자식 함수는 부모 함수의 지역변수를 접근할 수 있다. 이때 부모 함수의 지역변수를 non-local 변수라고 부른다.

    변수의 Scope는 크게 두 가지가 있다. 하나는 static scope 다른 하나는 dynamic scope이다. static scope는 프로그램의 구조상 결정이 된다. static scope에서 접근할 수 있는 변수는 전역변수, 지역변수, nesting이 허용된 언어의 경우 non-local변수까지 존재한다. 지역변수는 그 함수나 블록 내에서만 사용 가능하고 전역변수는 모든 함수에서 접근 할 수 있다. 우리는 코드를 보고 어떤 변수는 어디서 접근 가능한지 알 수 있다. 위의 코드를 보고 우리는 구조적으로 in_func은 out_func의 자식 함수이므로 out_func의 지역변수에 접근할 수 있다는 것을 알 수 있다. 우리가 아는 언어들 C언어, C++, python, Java는 모두 static scope이다. 

    dynamic scope는 우리가 코드를 보고 구조적으로 알 수 없다. dynamic scope는 프로그램이 실행되는 runtime에 결정된다. 예를 들어 아래와 같은 실행이 있다고 하자. 

        1. main -> func1 -> func2 -> func3

        2. main -> func3

static scope에서는 1번과 2번 모두 func3가 사용할 수 있는 변수가 동일하다. nesting이 허용 되지 않았다고 한다면 전역번수, func3의 지역변수. 하지만 dynamic scope에서는 1번과 2번에서 func3가 사용할 수 있는 변수의 범위가 다르다.

1번에서는 전역변수, main 지역변수, func1 지역변수, func2 지역변수, func3 지역변수를 사용 가능하고 2번에서는 전역변수, main 지역변수, func3 지역변수를 사용할 수 있다. 즉 자신을 호출한 함수의 변수까지 사용할 수 있는 것이다. 그렇기 때문에 우리는 프로그램 구조상 접근할 수 있는 변수를 알지 못한다. 접근할 수 있는 변수는 runtime에 결정되기 때문이다.

    전역 변수에 대하여 더 이야기 하자면 static scope에서 전역변수는 가급적 사용을 지양한다. 전역변수로 선언 시 프로그램 전체에서 쉽게 접근할 수 있어 편리하지만 module간의 coupling 즉 결합도가 높아지면 전역변수를 공유함으로써 의도와는 다르게 다른 module에 영향을 주어 결과 값이 예상과 다를 수 있기 때문이다. 마지막으로  지역변수와 전역변수가 같은 이름으로 생성될 수도 있다. 이러한 경우 전역변수를 hidden variable이라고 부른다. 이렇게 지역변수와 같은 이름의 다른 변수를 사용하고자 하는 경우 scope operator를 사용할 수 있다. C++에서는 scope operator로 :: 기호를 사용한다.

    그렇다면 C언어에서 static으로 선언한 변수는 어떻게 될까? 그런 변수는 scope는 지역 변수 성격을 가지고 있지만 life time은 전역 변수 성격을 가지고 있는 변수가 된다.

    Binding이란 attribute와 entity의 결합을 말한다. 예를 들면 변수와 type이나 value가 결합되는 것이나 연산자와 기호가 결합되는 것이 있다. 이때 Binding이 언제 이루어지냐에 따라 compile binding, run time binding으로 나눌 수 있다.

compile binding은 static binding이라고도 부르며 프로그램을 컴파일 하는 과정에서 binding이 이루어지고 프로그램이 실행하는 동안 바뀌지 않는 것을 말하고 run time bindng 은 dynamic binding이라고도 부르며 프로그램이 실행되고 있는 runtime에 binding이 이루어지고 프래그램이 실행되는 동안 변할 수 있는 것을 말한다. static binding을 하는 언어들은 C기반 언어 등이 있고 dynamic binding을 하는 언어로는 python, ruby, javascript, php등이 있다.

    변수는 프로그램에서 언급되기 전에 data type에 bind되어야 한다. Type binding은 다음 두 가지에 의해 결정된다.

1. 어떻게 type이 명시되어 있는 지

2. 언제 binding이 이루어지는지

    static binding에선 변수의 type을 선언한다. 선언된 type은 프로그램이 끝날 때까지 변하지 않는다. C언어의 다음 예시를 생각해보자.

#include <stdio.h>

int main() {
    int a;
    a = 10;
    //a = "hello";
    printf("%d", a);
    
    return 0;
}

우리는 변수 a를 정수형으로 사용하기 위해서는 위와 같이 a를 integer형으로 선언해야한다. 만약 int형으로 선언한 a에 주석처리를 한 것과 같이 문자열을 넣는다면 컴파일 에러가 날 것이다. integer형으로 선언한 a는 프로그램이 끝날 때까지 int형으로만 사용할 수 있다.

    dynamic binding에서는 변수의 type을 선언하지 않는다. 이런 변수는 어떤한 type의 값도 설정할 수 있다. 변수의 type은 변수에 값을 넣는 assignment statement(배정문)에서 결정되고 bind된다. 다음 python 코드를 보자

b = 10
#b = hello
print(b)

python에서는 변수의 type을 선언하지 않는다 b = 10라는 줄이 실행될 경우 b는 integer형으로 자동적으로 binding된다. 만약 배정문이 b = hello일 경우 b는 str형으로 자동적으로 binding된다. 

그렇다면 프로그래머 입장에서는 dynamic type binding이 더 편리한 것 아닐까? 굳이 변수를 타입에 맞춰서 선언할 필요도 없고 편리하다고 생각이 든다. 하지만 dynamic type binding의 가장 큰 단점은 비용이 크다는 것이다. 프로그램이 실행되는 run time에 binding되므로 실행 시간이 static type binding에 비해 길다. 그렇기 때문에 dynamic type binding은 대부분 compiler 방식이 아니라 interpreter 방식을 사용한다. 또한 static type binding의 compiler에 비해 error checking 능력이 떨어진다. 자유로운 형 변환이 가능하기 때문에 integer형 변수였던 i에 double형 값을 중간에 넣고 이를 까먹었을 경우 프로그래머가 원하는 결과가 나오지 않을 수 있다. interpreter는 int형 변수에 double형을 넣은 줄을 보고 에러를 발생시키지 않기 때문에 프로그래머가 이러한 오류를 직접 찾아야한다. 굉장히 큰 프로그램일 경우 이 오류를 찾는 것은 너무 힘든 일일 것이다. 이렇게 dynamic binding은 어떠한 type으로도 쉽게 바꾸고 사용할 수 있는 편리하다는 장점이 있지만 오류가 발생하였을 때 오류를 찾는데 어려움이 있고 실행 시간이 오래걸린다는 단점도 존재한다. 이렇게 장단점이 다르기 때문에 어떤 목적으로 프로그램을 사용할 것인가에 따라 언어를 선택하는 것도 굉장히 중요하다.

    Backus-Naur Form을 알아보기 전에 CFG가 무엇인지 알아야 한다. CFG는 Context-Free Grammar로 단어 그대로 해석해보면 "문맥으로부터 자유롭다"는 것이다. 아래 문장을 봐보자.

나는 배를 먹었더니 배가 아프다.

    이 문장을 보고 우리는 앞의 배는 먹는 배, 뒤의 배는 우리 신체를 가리키는 것을 문맥을 보고 알 수 있다. "배를 먹는다"로부터 먹는 배를, "배가 아프다"로부터 신체임을 우리는 문맥상으로 파악해야한다. 이러한 언어를 "Context Sensitive 하다"고 한다. 프로그래밍 언어가 이렇게 Context Sensitive하다고 생각해보자. 그렇다면 프로그래밍한 코드를 컴퓨터가 해석하게 만드는 것은 굉장히 어려울 것이다. 그렇기 때문에 프로그래밍 언어는 앞뒤 단어에 따라 의미가 달라지지 않는  CFG를 사용한다.

    BNF는 John  Backus가 ALGOL 58언어의 문법을 표기하기 위해 만들었고 이후 Peter Naur가 ALGOL60언어의 내용으로 보완하여 발표하였다. 처음엔 사람들에게 수용되지 않았지만 지금까지도 프로그래밍 언어 구문을 확실하게 표기하는 방법으로 여겨진다. 

    Grammar는 Rule들의 집합이다.  BNF에서 이러한 Rule들은 아래와 같이 3가지 기호로 이루어져 있다.

1. -> : Rule(production)
2. <> : Non-terminal
3. | : Or

    1번째 표현은 규칙을 나타내는 표현으로 rule이나 production으로 불린다. 화살표의 왼쪽은 LHS(Left Hand Side)라고 하며 정의될 개념이 존재한다. 화살표의 오른쪽은 RHS(Right Hand Side)라고 하며 기호와 개념들로 이루어진 정의가 존재한다. 따라서 LHS는 RHS로 정의된다고 할 수 있다.

    2번째 표현은 Non-terminal Symbol로 <>사이에 정의될 원하는 개념을 적는다. nonterminal symbol은 rule의 왼편에 위치하여 lexeme과 token등 terminal이나 또 다른 Non-terminal들에 의해 정의된다. 또한 Non-terminal symbol은 두 개 이상의 정의를 가질 수 있다.

    3번째 표현은 OR로 2번의 Non-terminal이 두 개 이상으로 정의될 때 rule의 오른편에서 이 '|' 기호를 이용해 각 정의들을 구분하여 한 번에 rule을 표현할 수 있게 한다. 예를 들어 아래와 같이 하나의 Non-terminal symbol에 여러 개의 rule이 존재할 경우 아래와 같이 나타낼 수 있다.

<expression> -> <var> + <var>
<expression> -> <var> - <var>
<expression> -> <var> * <var>
<expression> -> <var> / <var>

<expression> -> <var> + <var> | <var> - <var> | <var> * <var> | <var> / <var>

우리가 프로그래밍을 할 때 사칙연산을 사용할 경우 컴파일러는 위의 rule들 중에 동일한 문법이 존재하지 않는지 판단하여 문법이 맞는지 확인할 수 있다. 만약 존재하지 않을 경우 syntax에러를 주며 컴파일 에러가 발생하게 된다.

폰 노이만 아키텍처는 최근 60년 중 가장 인기있고 널리 사용된 컴퓨터 구조이다.

우선 그림으로 나타내자면 다음과 같다.

    데이터와 명령어, 프로그램 코드는 모두 같은 메모리(위)에 저장되고 CPU(아래)는 메모리와 분리된 구조이다. 이러한 구조 때문에 메모리에 저장되어있는 instruction과 data는 CPU로 pipelining을 통해 전송된다. 이렇게 전송되는 것을 fetch라고 한다. 그리고 CPU에서 이루어진 연산의 결과는 다시 메모리에 저장된다. CPU와 메모리가 인접해 있고 다음 명령어의 위치를 알려주는 PC(Program Counter)값만 바꾸어 branch하면 되기 때문에 반복되는 연산이 굉장히 빠르다. 따라서 이 구조에서는 재귀보다 반복이 더 빠르다.

    앞서 말한 fetch를 통해 전송된 instruction에 있는 opcode를 CPU에 있는 Decoder가 확인하여 어떤 연산을 수행할지 결정한다. 이러한 실행으로 생기는 것이 바로 아래 그림인 fetch-excution(decode) cycle이다.

그렇게 결정된 Control Unit의 값에 따라서 ALU에서 레지스터(register)에 저장된 값을 가지고 연산이 수행된다. 그 결과는 다시 메모리에 저장된다. 이때, 실행되는 명령어의 주소를 가리키는 PC 레지스터는 1이 늘어나 다음 명령어를 실행할 준비를 한다. 만약 instruction이 jump일 경우는 PC 레지스터 값이 jump하여 이동한 명령어의 주소로 바뀌게 된다.