이 장에서는 람다 대수를 소개한다. 람다 대수는 앞으로 이 책에서 함수형 언어와 그 구현체 간에 다리 역할을 한다. 중간 언어로 람다 대수를 소개하는 이유는 다음과 같다.
- 언어가 단순하다.
- 표현력이 풍부하다.
람다 대수는 몇 개의 생성자와 의미 구조만 있어도 되는 단순한 언어이다. 중간 언어가 단순하면 함수형 언어를 구현하는데에 더 집중할 수 있다. 람다 대수는 모든 함수형 프로그램을 표현할 수 있다. 람다 대수로 구현이 가능하다면 어떤 함수형 언어라도 구현할 수 있다.
문법 구조
아래 표현식(expression)은 단순한 람다 대수이다.
(+ 4 5)람다 대수에서 모든 함수 적용식(function applications)은 함수를 인자보다 먼저 적는다(prefix). 예를 들어 함수 +를 인자 4와 5보다 먼저 적는다. 조금 복잡한 식에서는 아래처럼 괄호를 사용한다.
(+ (* 5 6) (* 8 3))구현 관점에서 봤을 때 함수형 프로그램은 평가함으로써 '실행되는' 표현식이어야 한다. 평가(evaluation)는 줄일 수 있는 표현식(reducible expression, redex)을 반복해서 찾고 그것을 줄이는 것이다.
마지막 예제에는 줄일 수 있는 표현식이 두 개 있다.
(* 5 6)(* 8 3)
전체 표현식 (+ (* 5 6) (* 8 3))은 함수 +가 인자로 숫자 두 개를 필요로 하기 때문에 아직 줄일 수 없다. 첫 번째 줄일 수 있는 표현식을 줄이면 다음과 같다.
(+ (* 5 6) (* 8 3)) -> (+ 30 (* 8 3))두 번째 줄일 수 있는 식마저 줄이면 아래와 같다.
(+ 30 (* 8 3)) -> (+ 30 24)표현식을 줄여서 새로운 줄일 수 있는 식이 나왔고 이걸 다시 줄이면 아래와 같다.
(+ 30 24) -> 54함수 적용식과 커링
함수 'f를 인자 x에 적용한다.'라는 말을 표현식으로 적으면 아래와 같다.
f x인자 여러 개를 적용할 때는 보통 (f (x, y))와 같은 식으로 적지만 다른 방식도 있다. '3과 4의 합'을 표현하려면 아래처럼 적는다.
((+ 3) 4)표현식 (+ 3)은 인자에 3을 더하는 함수를 나타낸다. 그래서 전체 표현식은 '함수 +를 인자 3에 적용하고 그 결과 함수를 인자 4에 적용한다.'라는 의미이다. 모든 함수형 프로그래밍 언어가 그렇듯이 람다 대수에서도 함수가 함수를 리턴할 수 있다.
이런 방식은 모든 함수가 인자를 하나만 갖는 것으로 볼 수 있게 해준다. 이 방식을 커링(currying)이라고 부른다.
괄호
수학에서 불필요한 괄호는 없앨 수 있다. 예를 들어 아래와 같은 표현식이 있을 때
다음과 같이 적을 수 있다.
두 번째 표현식이 첫 번째보다 더 읽기 편하지만 이렇게 괄호를 항상 없애기만 할 경우 어떤 것을 먼저 계산할지 모호한 경우가 생길 수 있다. 이럴 때는 함수에 우선 순위를 정해주면 되는데 예를 들어 곱하기를 더하기보다 항상 먼저 계산한다고 약속을 하면 된다.
아래와 같은 경우에는 괄호를 없애면 해석이 달라진다.
이런 약속은 람다 대수에서도 쓸모가 있다. 다음과 같은 표현식이 있을 때
((+ 3) 2)함수 적용식은 항상 왼쪽부터 먼저 계산하자는 약속을 정하면 아래처럼 간단히 다시 적을 수 있다.
(+ 3 2)+ 3 2
복잡한 식으로 예를 들어 다음 식은 최대한 괄호를 많이 적어서 전혀 모호하지 않다.
((f ((+ 4) 3)) (g x))위에서 했던 약속을 적용하면 아래처럼 읽기 편하게 다시 적을 수 있다.
f (+ 4 3) (g x)여기서 괄호를 더 빼면 안 되지만 필요하다고 생각하는 만큼 괄호를 더하는 건 괜찮다.
(f (+ 4 3) (g x))람다 추상화
람다 대수에는 람다 추상화(lambda abstractions)라는 생성자(construct)가 있는데 새로운 함수 표현식을 의미한다. 람다 추상화 예시는 다음과 같다.
(λx . + x 1)먼저 λ를 적고 변수 이름을 적는다. 여기에서는 x이다. 이어서 .을 적고 함수의 본문(body)을 적는다. 여기에서는 (+ x 1)이다. λ는 '지금부터 여기에 함수를 적을 거다.'라는 의미이다. 변수는 형식 인자(formal parameter)라고 부른다. 그래서 위 표현식을 해석하면 '변수 x에 1을 더하는 함수'이다.
람다 추상화는 항상 아래 네 가지 요소로 구성된다.
λ- 형식 인자
.- 본문
람다 추상화는 C언어 같은 언어에서 함수를 정의하는 것과 비슷하다.
int inc(int x)
{
return x + 1;
}람다 추상화의 형식 인자는 C언어 함수의 형식 인자에 대응하고 람다 추상화의 본문은 C언어 함수 본문에 있는 연속된 명령어에 대응한다. C언어 같은 프로그래밍 언어에서는 함수가 inc 같이 꼭 이름을 정해줘야 하지만 요즘은 또 그렇지도 않다. 람다 추상화는 이름이 없는 함수이다.
람다 추상화에서 본문은 최대한 오른쪽 끝까지를 포함한다. 그래서 아래 표현식에서 본문은 +까지가 아니라 (+ x 1)까지이다.
(λx. + x 1) 4아래처럼 괄호를 적어서 더 명확하게 표현할 수 있다.
(λx. (+ x 1)) 4람다 추상화를 단독으로 적을 때는 다음과 같이 괄호를 따로 적지 않는다.
λx. + x 1참고
- The implementation of functional programming languages : Peyton Jones, Simon L.
