람다 대수 알아보기

람다 표현식을 단순한 익명 함수 문법이 아니라 추상화와 계산의 형식 체계로 설명한다. 가격과 수량을 연산하는 일상 문제를 치환식으로 바꾼 뒤 람다 표현식, 함수 적용, beta reduction으로 옮긴다. 이름 충돌과 alpha conversion을 거쳐 Church numeral로 숫자와 사칙 연산까지 함수만으로 표현하는 흐름을 따라간다.

핵심 포인트

람다 대수는 name, function, application 세 요소만으로 추상화한 대상을 만들고 구체적인 값을 적용한다.
beta reduction은 함수 본문의 bound variable을 전달된 표현식으로 치환해 계산을 진행한다.
치환 과정에서 자유 변수와 묶인 변수의 이름이 충돌할 수 있어 alpha conversion으로 bound variable의 이름을 바꿔야 한다.
identity, constant, plus-one 같은 익숙한 함수도 람다 표현식으로 나타낼 수 있다.
Church numeral은 함수가 적용되는 횟수로 자연수를 표현하고 SUCC, PLUS, MULT를 조합해 산술을 만든다.

상세 정리

추상화 출발: 사과 가격과 개수를 곱하는 문제에서 사과라는 구체 대상을 제거하고 cost, items, operator라는 이름만 남긴다.
연산자 분리: cost op items로 식을 일반화하면 op에 곱셈을 넣어 총액을, 나눗셈을 넣어 개당 가격을 계산할 수 있다.
람다 문법: name은 추상화 대상이고 function은 λname.body 형태로 대상을 식에 도입한다. application은 함수 표현식에 인자 표현식을 적용하는 구조다.
중첩 함수: 연산자·가격·개수를 차례로 받는 식은 λop.λcost.λitems.(op cost items)처럼 표현된다. 각 λ가 다음 값을 받을 함수를 반환한다.
beta reduction: 곱셈, 10, 2를 순서대로 적용하면 op, cost, items가 차례로 치환되고 최종적으로 곱셈 10 2만 남는다.
이름 충돌: 함수 내부에 있던 y와 인자로 들어온 y는 기원이 다르지만 단순 치환하면 같은 이름처럼 보일 수 있다. 계산 의미가 바뀌는 위험이다.
alpha conversion: 충돌 가능성이 있는 bound variable을 다른 이름으로 바꾸고 본문의 참조도 함께 변경해 의미를 보존한다.
기본 함수: λx.x는 입력을 그대로 돌려주는 identity 함수이고 λx.1은 입력과 무관하게 1을 반환하는 상수 함수다.
변수 구분: λy의 본문에서 y는 bound variable이다. λ로 도입되지 않은 x는 free variable이며 치환 시 포획되지 않게 주의해야 한다.
자기 적용: 함수를 자기 자신에 적용하는 표현식도 만들 수 있다. 람다 대수에서는 함수가 값인 동시에 다른 함수의 입력이 된다.
Church numeral: 0은 λf.λx.x, 1은 f를 한 번, 2는 f를 두 번 적용하는 식으로 표현한다. 본문에 반복되는 f의 수가 자연수가 된다.
후속자: SUCC는 기존 Church numeral이 f를 적용한 결과에 f를 한 번 더 적용해 n+1을 만든다.
덧셈과 곱셈: PLUS는 SUCC를 반복 적용하고 MULT는 PLUS를 반복 적용한다. 원시 숫자나 내장 산술 없이 함수 조합만으로 계산을 구성한다.
의미: 숫자와 연산까지 람다 표현식으로 환원하는 과정은 함수형 프로그래밍에서 고차 함수와 합성이 왜 핵심인지 보여준다.