이 글은 코드스피츠 채널에 올라온 영상을 보고 정리한 내용입니다.
프로그램
정확히 말하면 프로그램은 코드가 아니다. 실행 파일(.exe등)은 디스크에 저장되어 있는 파일일 뿐이다. 파일을 실행해서 OS가 명령과 값의 형태로 메모리에 적재한 상태가 프로그램이다. 메모리에 적재된 명령을 순차적으로 실행하고 나면 프로그램은 종료된다.
명령은 실행되기 위해 CPU로 올라온다. 보통 명령은 메모리를 이용해서 실행된다. CPU의 연산유닛은 제어 정보를 참고해서 메모리에 있는 값을 데이터유닛으로 불러온다. 연산유닛에서 어떤 연산할 때는 메모리에서 불러온 값과 명령을 사용해서 프로그램을 실행하고, 그 결과가 다시 메모리로 전파된다.
메모리에 명령과 값을 적재하는 과정을 로딩이라고 부른다. 명령(instruction)을 fetch해서 CPU로 가져와 디코딩하여 실행하는 것이 프로그램의 기본적인 구조다. '프로그램'이라고 하면 떠올려야 하는 것은 메모리에 명령과 값이 적재되어 있고 프로그램이 실행되면서 값이 계속해서 갱신되는 것을 떠올려야 한다.
아무리 복잡해보여도 고작 프로그램이라는 것은 명령을 소비하면서 값을 갱신해나가는 과정의 반복이다.
명령은 메모리에 있는 값을 참조해서 다시 값을 갱신하는 것
Lexical Grammer
- Control character 제어문자
- White space 공백문자
- Line Terminators 개행문자
Line Feed / Carriage Return - Comments 주석
- Keyword 예약어
- Literals 리터럴
boolean을 표현할 때 true/false 이외에 다른 값으로 boolean을 표현할 수 없는 것처럼 어떤 값을 표현하기 위한 최소 단위를 말한다. Java에서 실수나 long값을 표현할 때 F나 L을 뒤에 붙이는 것도 리터럴이다. 리터럴은 시대가 변하고 언어가 진화하면서 계속해서 확장된다. Javascript의 화살표 함수(=>)를 만드는 것도 리터럴이다.
Language Element
A -> B -> C언어는 상호보완하면서 확장되었기 때문에 비슷한 면이 많다. 함수형 언어를 제외하면 대부분 이 ABC언어의 자기장 안에 있다. ABC언어는 세 가지로 이루어져 있다.
- Statement 문
컴파일러가 해석한 뒤 명령으로 바꾼다. - Expression
컴파일러가 해석한 뒤 값으로 바꾼다 - Identifier
어느 값이 어느 위치에 들어있는 지에 마킹해두는 것이 식별자다.
Flow Control
일반적으로 제어문(Control Statement)이 제어하는 것은 흐름(Flow)이다. 흐름이란, 명령이 실행되는 흐름이다. 흐름은 위에서 아래로 실행되지만, 우리는 이것을 제어할 수 있다. 제어 명령 중에는 명령의 위치를 이동시키는 명령이 내장되어 있다. 1 -> 2-> 3으로 실행되어야 하는 프로그램에서 제어 명령을 이용해서 1 -> 2 -> 1로 돌려보낼 수 있다. 메모리에 있는 값이 CPU 데이터 유닛에에 들어와서 임시적으로 사용하는 공간을 레지스터라고 한다. 레지스터에 있는 값이 무엇이냐에 따라 명령을 어디로 분기할 것인지에 대한 분기 제어라는 것이 있고, 분기에 따라 어떤 명령을 실행할 것인지 결정한다. 그 명령 중에서 다른 명령의 위치로 이동시켜주는 명령을 지정할 수 있다.
Flow는 순서대로 실행되는 것이 기본이지만, 의도적으로 제어하는 것을 flow control이라고 부른다.
sub flow
서브 플로우는 함수다. 함수는 반복될 수 있는 Flow로 이동시켜서 반복을 끝내고 (함수를)호출했던 다음 번 위치로 이동하는 것을 말한다.
Sub Routine flow
서브 루틴은 플로우를 이동해서 특정 플로우를 실행하고 다시 제자리로 돌아와서 다음 명령을 실행한다. 너무 당연하게 생각해서 간과하지만 우리는 서브 루틴을 호출할 때 돌아올 포인트까지 알려주기 때문에 제자리로 돌아올 수 있다.
실습
1부터 10까지 더하는 함수를 만들어보자.
let accumulator = 0;
for(let i = 1; i <=10; i++)
accumulator += i;
accumulator덧셈을 구하라고 하면 이 생각부터 난다. 왜일까? 두 가지 이유가 있다.
- 불안감
어떤 불안감이냐면, 전지적인 시점에서 덧셈 과정 전체를 관조하고 싶다는 느낌.
어떤 경우에 재귀을 써야 하고, 어떤 경우에 for을 써야 하는 지 알아야 한다. for는 iteration상황, 그것도 계약조건이 명확한 iteration상황을 말한다. for문은 반복 조건을 확정짓고 쓸 때 for문을 쓴다. for가 들어가는 반복문은 모두 마찬가지다. 얼만큼 반복할 지 알고 있는 상태에서 for문을 사용한다. 재귀은 그렇지 않다. 반복이 진행되면서 얼마나 반복할 지 잘 모를 경우에 쓴다.그럼 이제 왜 for문부터 생각하는 지 알 수 있다. 얼만큼 돌 지 미리 예측할 수 있기 때문에 불안감을 덜 수 있기 때문에 우리는 for문부터 생각한다. - 정리하자면, 얼만큼 반복할 지 알고 있다면 for. 모른다면 재귀.
이런 미묘한 뉘앙스를 알아야 코드를 잘 짤 수 있다. 모든 코드에는 이유가 있다. 프로그래밍 언어의 네이티브 스피커가 되어야 한다. 즉, 문맥과 뉘앙스에 맞게 프로그래밍 언어를 사용해야 한다는 것이다. - accumulator
accumulator를 보면 for문 바깥에 있다. 이 얘기는 바깥 쪽에다가 안에 있는 내용을 리포팅 해주는 방법으로 해결하고 싶다는 전형적인 로직이다. 이렇게 코드를 배웠기 때문에 나의 컨트롤를 벗어나는 코드를 짤 수 없다. 이렇게 컨트롤문으로 짤 수 있는 로직은 구구단 정도다.
for문으로 내가 원하는 로직을 통제할 수 있다는 것은 알량한 착각이다.
또 다른 방법은 뭘까? 1~10까지 더하는 것을 이런 패턴으로 볼 수도 있다.
45 + 10 = 55
(36 + 9) + 10
(28 + 8) + 9 + 10
(20 + 7) + 8 + 9 + 10
(13 + 6) + 7 + 8 + 9 + 10
(7 + 5) + 6 + 7 + 8 + 9 + 10
(2 + 4) + 5 + 6 + 7 + 8 + 9 + 10
(1 + 3) + 4 + 5 + 6 + 7 + 8 + 9 + 10
(((((((1 + 2) + 4) + 5) + 6) + 7) + 8) + 9) + 10const sum = v=> v > 1 ? v + sum(v - 1) : 1;
sum(10); //55문제를 for문으로 한 번에 해결하려고 하는 것은 오만한 태도다. 우리에겐 for문으로 문제를 해결할 능력이 없다. 단지 값 하나를 판단하는 실력밖에 없다.. v가 1보다 크냐 안 크냐, 1보다 크다면 이런 일을 하겠어, 정도가 우리가 할 수 있는 일이다.
이보다 더 중요한 일은 떠넘기는 것이다. 내가 할 수 있는 일만 하고 할 수 없는 일은 최대한 빨리 남에게 미뤄야 한다.
12345라는 일이 있고, 내가 12 정도를 할 수 있다면 즉시 345는 할 수 없다고 떠넘겨야 한다. 떠넘기는 대상이 미래의 내가 될 수도 있지만 일단 떠넘겨라. 그래야 어려운 문제를 풀 수 없다.
하지만 자꾸 떠넘기다보면 메모리 Stack이 쌓이기 때문에 Overflow 날 확률이 있다. 이 말은 위에서 만든 sum()에 들어가는 숫자가 높아지면 StackOverflow가 날 수도 있다는 뜻이다.
실제로 이렇게 오버플로우가 난다.
각각의 함수들이 호출 포인트로 돌아가기 위해서 서브 루틴이 끝나기를 기다리기 때문이다. 그렇다면 함수 내의 서브루틴에게 최초 호출 포인트를 알려주면 함수가 일을 끝내고 그 위치로 돌아갈 수 있을 것이다. 최초 호출 포인트를 새로 호출된 함수가 알고 있으니 R2함수를 호출한 R1함수가 R2함수가 끝나길 기다리지 않고 메모리에서 내려올 수 있을 것이다. R2함수도 마찬가지로 되돌아 갈 포인트를 R3한테 넘기고 종료시킬 수 있다. 그러면 Stack을 쌓지 않아도 된다. 하지만 이것은 모든 언어가 지원하는 것은 아니다. 꼬리물기 최적화(Tail Call Optimization, TCO) 또는 Tail Recursion라고 한다.
const sum = v => v > 1 ? v + sum(v - 1) : 1;이 코드는 꼬리물기 최적화를 할 수 없다. 꼬리물기 최적화를 하려면 호출하고 나서 뒷정리할 게 없어야 한다. 돌아와서 v+결과를 실행해야 하기 때문이다. 이 문제를 인자를 통해 해결한다. 함수를 호출하고 갔다 와서 할 일이 있다면 인자로 바꿔야 한다.
const _sum = (v, acc) => v > 1 ? _sum(v - 1, acc + v) : acc + 1;
const sum = v => _sum(v, 0);
sum(100);
sum(10);
_sum(10, 0);
_sum(9, 19);
_sum(8, 27);
_sum(7, 34);
_sum(6, 40);
_sum(5, 45);
_sum(4, 49);
_sum(3, 52);
_sum(2, 54);
_sum(1);
최종 결과 : 55이 코드는 크롬 v8엔진에서는 작동하지 않는다. ECMA6에서는 꼬리물기 최적화를 지원해야 한다고 명시하고 있지만 꼬리물기 최적화가 되는 브라우저는 아직까지 Safari뿐이다.
위 코드를 기계적으로 for문으로 바꿔보자.
const v = 10;
let acc = 0;
for (let i = v; i > 1; i--) acc += i;
acc += 1;꼬리물기 최적화가 되어 있는 코드는 기계적으로 for문으로 바꿀 수 있다. 컴파일러가 해줄 수도 있을 만큼 기계적이다. 우리는 이런 기계적이지만, 한 번에 for문으로 짜는 것보다는 훨씬 쉬운 방식으로 굉장히 어려운 for문을 만들 수도 있다.
숟가락 얹기 재귀 -> 꼬리물기 재귀 -> for문으로 기계적 번역
앞으로 고작 이 정도의 과정으로 복작합 for를 짤 수 있을 것이다.
왜 재귀로 한 것을 for로 고쳐야 하는가? 재귀에 가장 큰 문제점은 StackOverflow가 떴을 때 고칠 방법이 없다는 것이다. 코드는 정상인데, 프로그램이 받아주지 않아서 SO가 나면 고칠 방법이 없다. 큰 규모의 생산성 있는 코드를 짜려면 for문으로 만들어야 한다.
최종 버전의 sum코드는 이런 모습이다.
const sum = v => {
let acc = 0;
for(let i = v; i > 1; i--)
acc += i;
acc += 1;
return acc;
}숟가락 얹기 재귀 -> 꼬리물기 재귀 -> for문으로 기계적 번역
이런 과정을 거치지 않아도 위와 같은 코드를 짤 수 있지만, 문제가 복잡해지면 복잡해질수록 이 방법을 이용해야 한다.
이런 방법을 통해 최종적으로 직접 JSON.stringify()를 구현할 수 있을 것이다.
변수
변수에는 용도가 있다. 모든 프로그램의 목적은 메모리의 값을 갱신하기 위한 것이다. 메모리를 어떻게 사용하느냐, 가 flow control의 핵심이다. 변수는 크게 속성이 두 가지가 있다.
- life cycle
되도록이면 짧게 유지한다. 우리가 멍청해서 오래 기억할 수 없다. - scope
되도록 좁게 유지. 멍청 + 다른 놈(일주일 뒤에 나)이 건드릴까봐
const v = 10;여기서 v는 상수다. 상수란 컨텍스트(해결하려는 문제) 하에서 미리 주어진 값이다. 함수 입장에서 보자면 인자가 상수일 가능성이 높다.
let acc = 0;이것은 저장소/스토리지라고 부른다. 저장소는 알고리즘이 진행되면서 결과값을 누적하거나 저장해야 할 값을 보관하는 변수를 말한다.
for(let i = v; i > 1; i--)여기서 i는 제어변수다. 제어변수는 여러 목적이 있는데, i는 카운터다.
프로그램을 잘 짜려면 변수를 사용하는 목적을 정확하게 이해해야 한다. 이 변수를 왜 썼는지. 이 변수는 무슨 역할인지. 이유를 명확히 하고 사용해야 한다. 그것만으로도 프로그램을 쉽게 짤 수 있다. 변수 사용법만 정확히 안다면 조금만 응용해서 아래와 같은 함수도 금방 만들 수 있다.
const reverseRange = v => {
const acc = [];
for (let i = v; i > 1; i--) acc.push(i);
acc.push(1);
return acc;
}
reverseRange(10);
//결과
(10) [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]끝.
과제
1차원 배열의 합 재귀, 꼬리 재귀 -> 번역한 for 만들기