2강 : 꼬리재귀, 매개변수 다형성, 사용자 정의 타입
3강 : 커링, 스테이징, map, filter, fold
오늘은 함수형 프로그래밍이 활용되는 곳을 두가지(컴파일러와 프로그램 분석) 소개할 것이다. 일단 컴파일러부터 보자.
함수형 프로그래밍을 아주아주 싫어하는 사람이라도 인정하는게 한가지 있다. 함수형 언어는 컴파일러 개발에 아주아주 적합하다는 것이다.
컴파일러는 간단히 말해 프로그램을 다른 형태로 변환시키는건데, 함수형 언어에선 타입 검사, 패턴매칭, 사용자 지정 타입 등의 기능으로 인해 이걸 자연스럽게 할 수 있다.
1. 컴파일러
컴파일러란, 한 프로그래밍 언어로 쓰여진 텍스트를 다른 프로그래밍 언어로 변환하는 프로그램이다. 인터프리터는 컴파일러와 비슷한 개념으로, 프로그램을 입력값으로 받아서 바로 실행하는 프로그램이다.
이처럼 인터프리터를 컴파일 한 후에 바로 프로그램을 실행하는것으로도 생각할 수 있다.
내가 컴파일러에 대해 들은 신기한것 중 하나는 바로 프로그래밍 언어는 자기 자신으로 구현될 수 있다는 것이다.
예를 들어 PyPy는 파이썬을 파이썬으로 구현한 인터프리터고, smlnj 컴파일러는 SML로 쓰여졌으며, 러스트 컴파일러도 러스트로 쓰여졌다.
다만 무에서 유를 창조하듯 하는건 아니라 컴파일러를 맨 처음 개발할때 쓰이진 않는다. 우선 이미 존재하는 컴파일러로 SML 컴파일러를 만든 뒤, 그 SML 컴파일러로 제2의 SML 컴파일러를 개발하는 것이다. 이걸 부트스트래핑(bootstrapping) 기법이라고 한다.
컴파일러는 보통 다음과 같은 단계를 거친다.
(1) 렉싱(어휘 분석) (lexing : string -> token list) 단계에서 프로그램을 토큰으로 변환한다. 토큰이 뭘 하는지 비유를 들자면, 글을 읽을때 자음 모음 하나하나 읽진 않지 않은가? 대신 단어를 기준으로 하나하나 읽는다. 토큰은 단어에 해당한다.
(2) 파싱(구문 분석) (parsing : token list -> AST) 단계에서는 토큰을 받아서 추상 구문 트리(abstract syntax tree, AST)로 변환시킨다.
(3) 중간코드 생성(Intermediate Representation generation : AST ->IR) 단계에선 AST를 어셈블리로 변환하기 전에 IR이라는 최적화하기 좋은 형태로 바꾼다.
(4) 최적화 (optimization : IR -> IR )단계에서는 IR를 최대한 최적화시킨다.
(5) 코드 생성 (code generation : IR -> assembly) 단계에선 실제 어셈블리어로 변환한다.
이 단계들이 어떻게 적용되는지 보기 위해 간단한 SML 프로그램을 생각해 보자.
코드를 긴 문자열로 생각하면, 렉싱은 다음과 같이 의미있는 단어 단위로 분리하는 작업이다.
이 "의미있는 단어"를 토큰이라고 한다. 토큰은 간단하게 다음과 같이 구현될 수 있다. 길이가 길 뿐이지 문법의 최소 단위를 분리해내는거라고 생각하자.
이제 파싱으로 가보자. (1 - 2) + 3 이라는 표현식은 다음과 같이 트리로 나타낼 수 있다.
이 트리는 괄호를 포함할 필요가 없다! 트리 밑에 있는 연산자가 더 먼저 실행된다는걸 내포하고 있기 때문이다.
비슷하게, 프로그램도 트리로 변환될 수 있다. 불필요한 걸 저장하지 않고 프로그램의 의미만 보존하는 트리이며 따라서 “추상” 구문 트리(Abstract Syntax Tree, AST) 라고 부른다.
이 프로그램을 AST로 바꾸면 다음과 같이 된다.
SML로 이 트리의 타입을 정의하면 다음과 같다.
파싱을 하는 프로그램을 파서(parser) 라고 하며 그중 하나가 재귀 하향 파서(recursive-descent parser)이다.
재귀 하향 파서는 여러 상호재귀 함수로 이루어져 있으며, 각 함수는 토큰 리스트로부터 하나의 문법을 파싱하는걸 담당한다 (표현식, 패턴, 변수선언 등).
parseDec는 변수/함수/타입 선언을 파싱해서 트리로 만드는 함수이며 재귀 하향 파서의 일부이다.
변수 선언은 val <pat> = <exp> 형태니까 패턴매칭을 해서 val, pat, =, exp를 분리하고 위에 선언했던 ValDec 타입으로 만든다. 이렇게 AST형태로 변환해 나가는 것이다.
사실 코드를 잘 보면 매우 간단한 형태라는걸 알 수 있다. 그냥 패턴매칭을 아주 많이 하는것 뿐이다. 따라서 보통 이렇게 파서를 직접 코딩하진 않고 yacc이라는 프로그램을 써서 자동으로 파서를 만들 수 있다 (렉싱 단계도 마찬가지로 lex라는 프로그램을 쓴다).
이제 우리에게 주어진 AST로 좀더 신기한 작업을 할 수 있다. AST를 똑같은 의미를 같지만 다른 형태의 AST로 변환시키는 것이다. 이렇게 컴파일러는 트리에 대한 변환과 연산을 주로 하는 프로그램이다.
예를 들어, 타입 검사를 할 수 있다.
이 typecheck 함수는 그저 트리를 인자로 받는 재귀함수이다. Int노드를 만나면 IntTy를 리턴하고, e1과 e2를 자식으로 갖는 Plus노드를 만나면 e1과 e2의 타입에 따라 뭘 할지 정하는 식이다.
AST가 주어지면 우리는 똑같은 의미를 갖지만 좀더 간단한 형태의 AST로 만드는, 그러니까 최적화 작업도 할 수 있다.
왼쪽의 트리를 생각해보자. 이건 val x = 2 - 1을 나타낸 AST이다. 이건 val x = 1과 의미가 같다. 따라서 오른쪽의 트리로 나타내도 상관이 없다.
이렇게 상수 연산을 컴파일 타임에 실행하는것을 상수 폴딩(constant folding)이라고 하며, 다음과 같이 어렵지 않게 구현이 가능하다.
실제로는 이보다 더 간단하게 축약할 수 있지만 넘어가자.
이렇게 상수 폴딩을 해도, 최적화 할것들이 많이 남아있다. 어셈블리어에 좀더 가까워져 보자.
여기서부턴 SML 대신 파이썬을 쓰겠다. 파이썬이 설명하기 더 쉽기도 하고, 중요한건 중간코드 생성 단계에서 뭘 하는지에 대한 감을 잡는 것이니까.
다음과 같은 코드는
이렇게 중간코드(IR)로 변환한다. 중간코드는 어셈블리와 비슷하지만 더 추상화된 버전이다. 레지스터같은걸 건드릴 필요도 없다.
다만 중간코드에선 표현식을 내포할 수 없고 하나하나 따로따로 써야 한다. 그렇다면 if나 함수 호출처럼 복잡한 제어흐름을 가진 코드는 중간코드로 어떻게 표현할까?
바로 제어 흐름 그래프(control flow graph)라는걸 이용해 나타낸다. 다음과 같은 코드가 있으면,
대충 다음과 같이 변환이 된다 (실제로는 더 복잡하다).
이렇게 제어 흐름 그래프가 있으면 간단한 무한루프가 있는지 검사할 수 있다. 위의 예시에선 그래프에 사이클이 있으니 그 부분을 검사하면 된다.
또한 제어 흐름 그래프는 최적화가 불가능할때, 또는 어떤 변수가 이후에 사용되는지도 더 명확하게 해준다.
이제 중간코드를 진짜 어셈블리어로 변환해야 한다. 중간코드와 어셈블리어의 차이점 중 하나는 중간코드는 무한히 많은 임시 변수를 할당하게 해준다는 것이다. 하지만 실제로는 데이터를 저장할 곳이 겨우 몇곳밖에 없다. 이걸 레지스터 할당 문제라고 한다.
깊게 들어가진 않겠지만 대충 어떤 느낌인지 알려주기 위해 비유를 들겠다.
인싸인 당신은 현재 8번째 생일을 맞이하였지만 생일파티 장소에 자리가 8곳밖에 없다. 당신은 아주아주 많은 친구들이 있으며, 특정 시간에 와서 일정 시간동안 머무르고 나갈 것이다. 예를 들어 친구 A는 4시 반에 오면 무조건 2시간동안 머무르다 갈 것이다. 어떻게 하면 모든 친구들이 와서 파티를 즐길 수 있게 스케줄을 짤 수 있을까?
이게 거의 레지스터 할당 문제이다. Chaitin et al.이 그래프 색칠 문제를 레지스터 할당 문제로 환산가능하다는걸 증명해서 NP-complete이다. 다만 휴리스틱을 사용하면 실제로 꽤 빠르게 문제가 풀린다고 한다.
어쨌든 굉장히 많은 부분을 생략했지만 이게 컴파일러가 대충 작동하는 방식이다. 함수형 언어가 컴파일러 개발에 적합한 이유를 되돌아보며 끝내겠다.
(1) 컴파일러는 결국 트리를 변환하는 프로그램이다.
(2) 컴파일러는 절대 에러가 나면 안된다. 정확성이 보장되어야 하기 때문에 함수형 언어가 적합하다.
(3) 컴파일러는 순수 함수이다. 가변성이 필요하지 않고 같은 텍스트에 대해 항상 같은 어셈블리를 출력한다.
2. 프로그램 분석
이제 주제를 바꿔서 프로그램 분석에 대해 이야기해 보자. 코드를 짤때 프로그래머가 최우선으로 생각할 것은 바로 코드가 원하는대로 동작하는지, 버그가 없는지 이다.
하지만 요즘들어 챗지피티가 손쉽게 코드를 자동생성할 수 있게 되어 코딩의 진입장벽이 매우 크게 낮춰져서, 코드의 정확성을 신경쓰지 않는 프로그래머들이 많아졌다. 이러한 불안정한 코드가 우리 삶을 지탱하는 곳에 쓰인다고 하자 (은행, 대중교통, 발전소 등). 그러면 안될 것이므로 버그에 대해 더 잘 알아야 할 것이다.
버그의 종류로는 문법 오류라던지, 오타라던지 하는 컴파일 타임에 나타나는 버그와, 런타임에 나타나는 버그가 있다.
버그는 컴파일 시간에 나타나면 나타날수록 좋다. 다음 상황을 상상해보자.
당신은 머신러닝 엔지니어이고 지난 6개월간 최신 언어모델을 개발하는데 밤낮으로 일했으며 드디어 프로그램을 실행할 순간이 왔다. 학습에 시간이 며칠 걸리기 때문에 당신은 프로그램을 실행하고 2주간 여행을 다녀왔다. 하지만 2주 후에 당신은 다음의 에러 메세지와 함께 모델이 실패했다는걸 보았다.
프로그래머는 항상 실수한다는것이 핵심이다. 이런 버그들을 컴파일 시간에 최대한 잡아낼 수 있는 방법이 없을까?
이때 등장하는것이 프로그램 분석이다. 프로그램 분석은 프로그램이 원하지 않은 행동을 하는걸 자동으로 잡아내는 것을 연구하는 학문이다.
동적 프로그램 분석은 프로그램을 직접 실행시켜 버그를 잡아내는 것인데, 대표적인 기법으로 fuzzing(프로그램에 많은 양의 랜덤생성된 인풋을 넣어보는것)과 profiling(특정 인풋에 시간이 얼마나 걸리는지 측정하거나 테스트를 쓰는것 등) 이 있다. 하지만 동적 프로그램 분석은 만약 프로그램이 100일 걸리면 분석도 100일 걸린다는 단점이 있다.
그에 비해 정적 프로그램 분석은 프로그램의 성질을 프로그램을 실행시키지 않고 알아내는 기법이다. 방금 컴파일러를 공부하면서 설명했듯이 프로그램은 추상 구문 트리(AST)로 변환될 수 있다. 따라서 AST를 분석함으로써 프로그램도 분석할 수 있다.
정적 프로그램 분석은 보안 분야에 활용될 수 있고 (static application security testing(SAST)), syntax highlighting으로 코드를 예쁘게 보이게 만들거나, 자동 포매팅이 되게 하거나, 타입 검사를 할 수 있다.
다만 우리 앞에 아주 작은 문제가 하나 있다. 완벽한 프로그램 분석은 이론적으로 불가능하다는 것이다. 라이스의 정리에 따르면, 유한 시간 안에 프로그램의 어떤 속성을 명확하게 예/아니오로 파악하는것은 불가능하다 (여기서 불가능하다라는건 결정불가능하다(undecidable) - 문제를 푸는 튜링머신이 없음 - 을 말한다). 난 라이스의 정리를 안배워서 잘은 모르겠지만 정지문제에서 도출될 수 있다고 한다.
이건 수학적인 정리이므로 어떻게 해볼 수 없다! 다만 돌아가는 것은 가능하다. 바로 우리의 눈높이를 조금 낮추는 것이다.
명확하게 파악할 수 있지만 유한시간 안에 못끝낼 수 있다고 하면 가능하다! (이 유형을 Type A 프로그램 분석이라 한다). 예를 들어 SML은 1 div 0이 컴파일 되지만, 이걸 컴파일 시간에 잡아낼 수 있는 언어가 존재한다. 이걸 dependently typed language라고 한다. 하지만 이 언어들은 타입 검사를 할때 무한루프에 빠질수 있다는 단점이 있다.
이와 반대로 속성을 명확하게 예/아니오로 파악하는게 불가능하지만, 틀려도 된다고 해도 가능하다 (이건 Type B 프로그램 분석이라 한다). 근사치를 구하는 것이다. 1 div 0이 담긴 프로그램을 컴파일 시간에 잡아내고 싶다고 하자. 그렇다면 프로그램에 div라는 단어가 담겼다면 에러가 나게 만드는 방식은 Type B에 해당한다. 유한 시간안에 되고, 가끔씩 무고한 프로그램까지 잡아내지만, 에러를 잡아낼땐 잡아낸다.
Type A와 Type B 둘중 뭐가 더 나을까? 정답은 둘다 장단점이 있다 이다. 참고로 실무에선 1 div 0을 잡아내려고 신경을 쓰지 않는다. 이건 Type C라고 부른다 (더 간단한 버전의 문제를 푸는것이다. 1 div 0까지 잡아내지 못하더라도 일반적인 타입검사를 하는게 여기 해당한다). 실무에선 Type A, 무한루프를 별로 좋아하지 않아서 보통 Type B나 Type C로 관심이 쏠린다.
3. 데이터 흐름 분석
Type B 프로그램 분석의 일종으로 데이터 흐름 분석(Dataflow Analysis)이 있다. 유한 시간 내에 근사해를 구한다고 보면 된다.
컴파일러할때 잠시 했던 제어 흐름 분석(CFG)를 이용해 프로그램의 모든 상수를 찾는 데이터 흐름 분석을 해보자.
각 줄마다 변수의 상태를 나타내는 집합을 생각한다.
그래프를 따라가다 보면 x에 3이 저장되어있고 y에는 2가 저장되어있다. 이때 노란색 블럭으로 향하는 집합을 생각해보자. x값이 다른 초록색으로 표시된 두 집합이 모두 노란색 블럭으로 향한다. 이건 모순이므로 x는 상수가 아니다. 이걸 top을 나타내는 ⊤로 표시한다.
top인 이유는 x = 1 또는 3일때는 x가 상수인지 아닌지 불명확한 상태여서 더 개선의 여지가 있었는데, x = ⊤일때는 개선의 여지 없이 x는 상수가 아니기 때문이다. 여기서 더 “위로” 올라갈 수는 없기 때문에 top이라 부른다.
혹시 단조증가 함수를 알고있다면 “위로”만 올라갈 수 있는 이 구조가 친숙하게 보일 것이다. 이 구조는 격자(lattice)라고 부르며, 격자를 써서 CFG를 분석하는게 데이터 흐름 분석이다.
방금 우리가 한 상수 찾기의 격자 구조는 다음과 같다. 밑의 공집합에서 시작해 CFG를 거닐며 “위로 올라갈 수 밖에 없다”.
데이터 흐름 분석 기법은 일반적으로 아주 유용한 기법이며 다음의 분석에 활용된다.
(1) 중복된 연산 최적화하기
(2) 변수가 주어진 위치에 도달할 수 있는지 확인하기
(3) 어떤 변수가 미래에 필요한지 확인하기, 불필요한 코드 제거
(4) 원치 않는 소스의 데이터가 프로그램의 핵심 위치에 도달할 수 있는지 확인하기 (보안 분야에서 매우 유용함. taint tracking이라고 부른다.)
4. Semgrep
사실 데이터 흐름 분석은 함수형 프로그래밍하고 관계가 없다. 함수형 언어가 잘 다룰 수 있는 추상 구문 트리(AST) 단계보다 한단계 낮은 중간코드 단계에서 분석을 하기 때문이다. 하지만 만약 AST 단계에서 분석을 한다면 어떨까?
Semgrep이라는 OCaml로 쓰여진 오픈소스 프로그램이 이 일을 한다. 코드를 언어에 상관없이 통합된 AST로 변환하고, 이 과정에서 버그 고치기에 유용하지 않은 문법은 제외한다.
다음 코드를 생각해보자.
이 코드에는 문제점이 있다. append_to(2)를 첫번째로 호출할땐 [2]여서 정상적으로 작동되는것 같지만, 두번째로 호출할땐 [2, 2]가 된다. to는 함수가 생성될때 같이 생성되고 초기화되지 않기 때문이다.
이런 버그는 굳이 CFG 단계까지 않아도 잡을 수 있다. 오히려 AST단계에서 이러한 문제를 더 쉽게 찾을 수 있다. 사실 버그라고 하긴 좀 뭐하고 코딩할때 가지면 좋은 스타일에 더 가깝다.
Semgrep는 이렇게 스타일 “버그” 라던지, 일반적인 버그라던지, 보안 취약점등을 찾을 수 있게 커스터마이징을 할 수 있는 프로그램 분석 툴이다.
Semgrep는 grep에서 이름을 따왔는데, grep는 그냥 ctrl+F이라고 보면 된다. ctrl+F는 텍스트를 검색하지만 Semgrep는 유저가 찾고 싶은 부분을 주면 프로그램에서 그 AST 트리가 나타나는 곳을 찾아준다.
다음의 예시를 보자. 왼쪽은 유저가 준 인풋이고 오른쪽은 우리가 분석할 프로그램이다.
일반적인 ctrl+F라면 문자열 안의 print까지 매칭할 것이다. 하지만 Semgrep는 더 똑똑해서 유저가 명시한 부분만 하이라이트한다.
오른쪽에 print문자열이 아닌 print문만 매칭된걸 확인할 수 있다.
또한 다음과 같이 패턴매칭을 할수도 있다. ref $X 처럼 생긴 구문을 자동으로 찾아준다. 이 경우엔 2를 하이라이팅 할 것이다.
이제 이 코드에서 to=[]를 매칭하는 Semgrep 구문을 작성해보자.
이렇게 …를 쓰면 간단하게 패턴매칭 할 수 있다.
저 사진의 강사는 제작년에 학부를 졸업하고 Semgrep 회사에 다닌다. 이 마지막 강의에서 자신이 왜 Semgrep에 지원했는지 말해줬는데, 함수형 언어로 최대한 많은 이들에게 도움이 될 수 있는 곳이라서 라고 말했다.
앞으로 코딩을 하는사람들이 많아졌으면 많아졌지 줄어들지는 않을 것이다. 그만큼 에러가 나는 코드, 정상적으로 작동하지 않는 코드도 늘어날 것이다. 이런 코드들이 우리 삶을 지탱하지 않도록, 버그를 더 빨리 찾을 수 있도록 2년동안 10명가량의 프로그래머가 고민하고 땀흘린 끝에 탄생한게 Semgrep이다. 오픈소스에 1인 버전은 무료로 풀려있어서 누구든 사용할 수 있다.
...어쩌다 보니 Semgrep 광고처럼 되어버렸는데 내가 전달하려던건 그게 아니고 함수형 언어의 쓰임새가 이런곳이 있다고 말하려 했다.
2주정도의 시간동안 정보글 많이 써서 따라오기 힘들었을텐데 그럼에도 불구하고 0강부터 봐준 사람들이 있다면 정말 고맙다. 혹은 미래에 이 글을 보는 누군가에게도 정말 고맙다고 전하고 싶다. 혼자서는 공부가 잘 안됐는데 이렇게 주기적으로 정보글로 만들어서 올리니까 학습효과도 있는것 같다.
긴 글 읽어줘서 항상 고맙고 조만간 새로운 주제로 돌아오겠다.
