Command Palette
Search for a command to run...
Search for a command to run...
먼저 Lambda Calculus에 대해 설명하기 전에 튜링머신을 짚고 넘어가야 한다. 대부분의 코딩이 튜링머신 기반이기 때문이다. 개념을 잡기위해 꺼냇으나, 앞으로는 튜링 머신을 다룰일 없으니 편하게 읽기 바란다.
목차:
아마 대학교때 컴퓨터공학, 소프트웨어학과 및 컴퓨터 관련 학과를 다녔거나, 개발자로 취준하기 위해 CS 또는 컴퓨터구조론 관련 책을 읽어봤다면 "튜링 머신"에 대해 들어봤을 것이다.
현재 일반적으로 접할 수 있는 모든 컴퓨터는 튜링머신 이론을 기반으로 작동한다. 하지만 튜링머신, 오토마타만이 유일한 계산 이론은 아니다.
아마 대학교를 나왔다면 오토마타, 계산이론때 튜닝머신을 배웠을 것이다. 혹시나 비전공자이고, 프로그래밍의 밑바닥을 한번 훓고 싶다면 Kocw에서 <오토마타 및 계산이론>를 찾아보자.
이쪽을 이해하기 시작하면 정규식의 전개까지도 바로 눈에 잡히게 된다.
람다 대수이라는 또 다른 계산 이론이 존재한다. (이하 람다 계산법이라고 부름)
튜링 머신은 대입 (Write / 상태 전이) 을 기초로 움직인다. 그에 비해 람다 계산법은 치환 (Subsitutation / Reduction) 을 기초로 항을 계산한다.
이것을 기반으로 한 프로그래밍 방식을 Imperative Programming (명령적 프로그래밍) 과 Functional Programming (함수형 프로그래밍) 이라고 부른다. 그리고 대개 명령적 프로그래밍만을 배웠을 것이다.
함수형 언어는 lambda calculus를 기반으로 한 언어이고, 함수형 계산법도 람다 계산법과 의미적으로 동일하다고 생각하면 된다.
튜링 머신으로 풀 수 있는 문제는 람다 계산법으로도 풀 수 있다. 반대로 람다 계산법으로 문제를 풀 수 있다면, 튜링 머신으로도 문제를 풀어 낼 수 있다.
비록 현대의 CPU는 튜링 머신을 기반으로 되어있고, 람다 계산법에 따른 CPU는 존재여부 마저 불분명하다. 하지만, 튜링 머신 위에서 람다 계산법을 적용할 수 있다. 그리고 실제로도 야금야금 적용되고 있다.
특히 웹 개발 진영에서는 React와 같은 도구를 필두로 하여금 알게 모르게 람다 계산법이 많이 적용되어 있다.
Promise도 알고보면 모나드이다. 클로저 함수 등등도 람다 계산법 쪽에서 흘러 들어온 개념이라 할 수 있다. (튜링 머신의 개념이라고 보긴 어렵다.)
이 글의 범위 밖이므로, 간략히 설명을 하고 넘어가고자 한다.
튜링 머신은 길게 늘어진 저장공간(테이프) 과 현재 위치를 가리키는 헤드, 그리고 상태(state) 로 이루어진 계산 모델이다. 현재 위치의 값을 읽고, 지금 상태를 확인한 다음, 정해진 규칙에 따라 아래 행위를 반복한다.
위 행동을 반복하다 보면 계산이 완료되어 있다.
튜링 머신은 메모리의 값을 바꾸고 다음 단계로 넘어가는 방식으로 계산을 진행한다. 즉, 모든것이 "읽을 메모리의 위치"를 제어하고, 메모리의 값을 바꾸는것을 기조로 설계되어 있다.
명령형 프로그래밍이라는 말도 여기서 튀어 나왔다. 결국 메모리의 위치와 값을 제어하기 위해 명령하는 방식이다. 즉, 메모리를 어떻게 접근해서 수정하는가가 명령형 프로그래밍의 관심사이다.
현대의 컴퓨터에는 메모리(RAM)이 끼어져있다. 하지만 튜링머신 이론속에서는 메모리 대신 테이프라고 부른다. 이 테이프를 잘 조작하는게 명령형 프로그래밍의 핵심이다.
카세트, 비디오 테이프, 또는 스카치 테이프를 보면 1자로 쭈우우욱 이어저있다. 이 공간에 1cm 씩 공간을 나눴다고 하자. 그러면 개념상 TAPE[전체 길이 / 1cm] 의 배열이 생긴 셈이다.
카세트, 비디오 테이프를 예시로 들려다가, 요즘 친구들은 보지도 못했을것 같아서 스카치·유리 테이프를 들고 나왔다. 어쨋든 1차원 배열이라는데 신경쓰면 된다.
이 배열에는 심볼(Symbol)이 들어가 있다. 대충 명령어나 값(변수 int 등등), 그 외 필요한 모든 데이터라고 생각하면 된다 (심볼과 의미상 값은 다르다). 놀랍게도 이 테이프를 좌로 우로 옮기다 보면 계산이 완료된다.
GPT가 적어준 예시를 보자:
아래의 테이프(통짜 메모리 배열)가 있다고 하자
... | 0 | 1 | 1 | 0 | _ | ...
^
헤드
헤드는 현재 한 칸을 보고 있고, 그 칸의 값을 읽을 수 있다. 그리고 필요하다면 그 값을 다른 값으로 덮어쓸 수도 있다.
예를 들어 "1을 만나면 0으로 바꾸고 오른쪽으로 간다" 라는 규칙이 있다면, 위 테이프를 규칙에 따라 0으로 바꾸고 전진해야 한다:
... | 0 | 1 | 0 | 0 | _ | ...
^
별거 없어 보이지만, 계산이라는 것은 원래 이런 사소한 동작의 반복이다. 더하기도, 비교도, 조건문도, 반복문도, 결국 끝까지 내려가면 어딘가의 값을 읽고, 바꾸고, 다음 위치로 이동하는 과정 으로 환원된다.
이제 이걸 현실의 CPU로 내려보자.
현대 CPU도 튜링머신 이론에 따라 메모리와 레지스터의 값을 읽고, 명령어에 따라 값을 바꾸고, 다음 명령으로 이동한다.
예를 들어 CPU에는 대충 이런 명령어들이 있다.
이 명령어들을 보고 있으면, 결국 하는 일은 비슷하다.
아래의 예시코드를 참고해보자:
int x = 10; // TAPE[100MB] 공간에 1에 올라감
x = x + 1; // MOV AX, [100MB] -> ADD AX, 1 -> MOV [100MB], AX
테이프의 헤드는 명령어가 메모리에 올라간(적재된) 위치에 있을것이다. 위 내용대로라면 아래와 같이 테이프 전이를 생각해볼 수 있을것이다
프로그램이 로딩된 직후:
(100MB 시점)
... | 10 | MOV AX, [100MB] | ADD AX, 1 | MOV [100MB], AX | _ | ...
^
MOV AX, [100MB] 에 따라서 레지스터의 AX가 TAPE[100]으로 채워지고, 규칙에 따라 테이프가 오른쪽으로 전진
(100MB 시점)
... | 10 | MOV AX, [100MB] | ADD AX, 1 | MOV [100MB], AX | _ | ...
^
ADD 규칙에 따라서 AX에 1을 더함
(100MB 시점)
... | 10 | MOV AX, [100MB] | ADD AX, 1 | MOV [100MB], AX | _ | ...
^
MOV 규칙에 따라서 AX 값을 TAPE[100MB]에 저장
(100MB 시점)
... | 11 | MOV AX, [100MB] | ADD AX, 1 | MOV [100MB], AX | _ | ...
^
간략히 표현해서 이렇게 단순하게 적혔지만, JMP (Jump)나 IF에 따라서 분기되는 모습을 보면 더욱 알기 쉽다.
물론, 현실에서는 보안을 위해 명령어 공간과 값 공간은 분리되어 있다. 쓰기를 잘못해서 명령어 공간을 침범한다면 SIGFAULT가 발생할 것이다. (단, 악성 바이러스나 보안이 중요한 프로그램은 실행하면서 스스로의 코드를 바꾸기도 한다)
다시금 말하지만, 현재 메모리의 위치(헤드)와 값을 잘 바꾸도록 하는게 핵심이다. 그래서 명령형 프로그래밍 이라고 불린다. 클래스, 메서드, 그 외 모든것들은 개발자가 코딩을 편리하게 하기위한 문법적(언어적) 도구에 불과하다. 결국 핵심은 메모리를 어떻게 잘 접근해서 어떻게 바꾸는지 지시하는 것이다.
이에 비해서 Lambda Calculus는 항의 치환으로 이루어진다.
튜링 머신이 메모리의 값을 바꾸며 앞으로 나아간다면, 람다 계산법은 식을 다른 식으로 바꾸어가며 계산을 진행한다. 즉, "어디 메모리를 읽고 어떤 값을 덮어쓸 것인가" 보다는, 이 식을 어떤 규칙으로 더 간단한 식으로 바꿀 것인가가 관심사이다.
우리 교수님은 명령형 프로그래밍은 How-To-do를, 함수형 프로그래밍은 What-To-do를 표현하는것이라 말씀하셨었다.
명령형 프로그래밍은 "어떻게 할지" 를 단계별로 지시한다. 반면 함수형 프로그래밍은 "무엇을 계산할지" 를 식으로 써 놓으면 (declartive), 실제 계산은 그 식을 해석하고 줄이는 쪽에서 진행된다.
튜링 머신 파트에서는 메모리의 값을 바꾸는 것이 핵심이었다. 하지만 람다 계산법은 그렇게 보지 않는다.
람다 계산법에서는 값을 저장해 둔 메모리 칸 이 먼저 떠오르는 것이 아니라, 계산해야 할 식 자체 가 먼저 나온다. 마치 아래와 같은 식만이 나온다:
(λx. x + 1) 10
^ ^
함수 파라메터
위 식은 (λx. x + 1)에 10을 넣는 함수이다. 처음이니까 익숙한 표현으로 쓰자면 아래와 비슷하다:
fn 익명함수(var x) {
return x + 1;
} (10)
untyped lambda calcus이기 때문에, ᅟarguement에 type을 표기할 필요가 없다. 또한, +는 binary 함수이다.
위 람다식은 아래 처럼 줄여진다:
(λx. x + 1) 10
→ 10 + 1 # x자리가 10이 치환됨 Term[x:=10]
→ 11 # 식이 줄여짐
여기서 x 자리에 10 을 넣는 것이 치환(Subsituation) 이고, 더 간단한 형태로 줄이는게 축약 (Reduction) 이다
위 방법을 확장하면 if문, 루프(news.ycombinator.com의 Y Combinator가 여기서 튀어나온다!) 그 외 모든 계산을 수행할 수 있다. 다만에, Side-effect 가 있는 함수는 별개의 시스템으로 빠져 나온다.
그러면 What-to-do를 기술했다면, 실제 계산은 누가 해 주는가? 이것은 시스템이 알아서 해 준다. 마치 명령어를 쭈우우욱 쓰면 CPU가 계산하는것 마냥, 별도의 외부 시스템이 식을 계산한다. 지금으로서는 Haskell이 가장 유명할 것이다.
React에서 Functional Component로 항목을 작성했다고 하자. 우리는 html이 잘 보이기만 하면 된다. React 시스템이 내부적으로 알아서 잘~ 처리를 해 준다. 이와 동일하다.
Lambda-Calclus는 같은 문제라도 여러 방법으로 전개해 나갈 수 있다. 푸는 방법이 다양하더라도 결과가 동일함을 보장할 수 있다.
여러 방법으로 전개한다는 내용은 추후 Confluent또는 Church-Rosser 파트에서 설명할 예정이다.
즉, 명령형 프로그래밍처럼 개발자가 "1번 하고, 그 다음 2번 하고, 그 다음 3번 해" 라고 일일이 순서를 강하게 박아 넣는 것이 아니라, 문제의 구조를 식으로 표현해 두면 계산 규칙이 알아서 전개해 나간다 는 느낌으로 이해하면 된다.
덕분에 컴파일러가 최적화를 할 수 있는 여지가 많아진다. 현대의 컴파일러는 "무엇을 하려는지 알아내면 그에 맞춰서 최적화된 명령어"를 만들어준다. 하지만 "코드에서 특별한 의도" (=섯불리 최적화를 했다간 오류가 날 수 있으면)가 느껴진다면 최적화를 포기한다. Side-effect 없이 무엇을 하려는지 표기하는 방식(declaretive)은 컴파일러에게 무엇을 할지를 정확히 알려주고, 더 나아가서 컴파일러가 더욱 적극적으로 개입할 수 있도록 한다.
대개 low-code가 많을 수록 컴파일러는 코드 최적화에 손대기 힘들어한다. 오히려 더 높은 high level로 표기할 수록 컴파일러는 더 똑똑하게 코드 최적화를 수행한다.
물론 개발자가 일일히 low-level code를 작성해서 최적화를 유도할 수도 있겠지만, 대부분 시스템에 맞겨도 충분할 정도로 최적화를 잘 해내준다.
튜링 머신 쪽이 메모리와 상태를 직접 만지작거리는 쪽이라면, 람다 계산법 쪽은 함수를 적용하고 식을 전개하는 쪽에 가깝다.
그래서 이 계열의 프로그래밍 스타일을 함수형 프로그래밍 이라고 부른다.
여기서 "함수형" 이라는 말은 단순히 함수를 많이 쓴다는 뜻이 아니다. 관심사가 "메모리를 어떻게 바꿀까" 에서 "이 계산을 어떤 함수와 식으로 표현할까" 로 옮겨간 것이다.
그러기 위해서는 "함수 또한 값이다" (Function is First-Class citizen)라는 개념이 반드시 필요하다. 함수를 값처럼 옮겨서 적용하고 전개할 수 있어야지 진정한 의미로 "함수의 전개에 집중" 할 수 있다.
즉, 클래스, 메서드, 반복문 같은 문법 요소를 중심에 두고 사고하던 것에서 벗어나, 값, 함수, 적용, 치환, 축약 쪽으로 시선이 이동하는 것이다.