람다 대수(Lamda calcuus)란 무엇인가

람다 대수

• 수학자 알론조 처치가 순전히 수학적 방식으로 계산 개념을 설명하기 위해 개발한 형식 체계
• 수행 중인 작업을 명시적으로 정의할 필요 없음 즉 함수를 정의하고 바로 적용하는 방법론

람다식(Lamda expression)

람다식은 익명 함수를 정의하기 위한 식이다.

• 람다식은 [[일급 객체(first class)]]이다.
  • 즉 인자로 사용 될 수 있다.
  • 반환 값으로 사용 될 수 있다
    아래는 람다를 BNF (Backus-Naur Form)로 나타낸 것이다

람다식은 보다시피 상수, 변수, 함수 정의, 함수 적용이 가능한다.
함수형 언어에서 람다식에 관심을 두는 이유는 문법이 간단하기 때문이다.

보통의 프로그래밍 언어는 구문 뿐만아니라 의미까지 분석을 해서 생각해야 한다.
함수형 언어에서는 문법이 너무 간단해서 의미론적으로 고민할 필요가 없다

람다 대수 사용 방법

람다 대수에서 함수 정의와 함수 적용은 다음과 같이 표현됩니다. 여기서는 변수 x, y를 사용합니다.

함수 정의

함수 정의는 람다 식을 사용해 표현합니다. 람다 대수에서 함수 정의는 다음과 같이 표현됩니다.

λx. expression

이 식은 x라는 변수를 인자로 받아 expression을 계산하는 함수를 정의합니다.

λx. (x+1) 
λx. (x*x) 
λx. (x+y)

λx. λy. (x*y)  
λy. λx. (x+y) 
λz. (x + 2*y + z)

True = λx. λy. x  
False = λx. λy. y  
Not = λb. b (λx. λy. y) (λx. λy. y) = λb. b False True

함수 적용

함수 적용은 함수와 인자를 함께 표현하여 함수를 호출하는 것입니다. 람다 대수에서 함수 적용은 다음과 같이 표현됩니다.

(λx. expression) y

여기서 (λx. expression)은 함수를 정의하는 람다 식이고, y는 함수에 전달되는 인자입니다.

(λx. (x+1)) 2 = 2 + 1 = 3 
(λx. (x*x)) 3 = 3 * 3 = 9 
(λx. (x+y)) 3 = 3 + y
 
(λx. λy. (x*y)) 3 2 = λy. (3*y) 2 = 3 * 2 = 6 
(λy. λx. (x+y)) 3 2 = λx. (x+3) 2 = 3 + 2 = 5 
(λz. (x + 2*y + z)) 5 = x + 2*y + 5
 
(λb. b False True) True = True False True = False 
(λb. b False True) False = False False True = True

True | False 계산

람다 대수에서 함수는 ‘λ’ 기호로 표시되며, 이어서 인자(argument)와 함수 본문(body)이 옵니다.
여기서 주어진 람다 표현식들은 불리언(Boolean) 값을 나타내고 있습니다.

1. True = λx. λy. x : 참을 나타내는 함수입니다. 두 개의 인자 x와 y를 받아서 x를 반환합니다.
2. False = λx. λy. y : 거짓을 나타내는 함수입니다. 두 개의 인자 x와 y를 받아서 y를 반환합니다.
3. Not = λb. b False True : 부정(Not) 연산을 나타내는 함수입니다.
   • 하나의 불리언 인자 b를 받아서, b가 True일 경우 False를 반환하고, b가 False일 경우 True를 반환합니다.

Not에 대해 더 생각해보자

Not = λb. b False True 는 조건문이라기보다는 불리언 값을 부정하는 함수입니다.

조건문이란 일반적으로 if-then-else 구문처럼 어떤 조건을 검사한 후, 참일 경우와 거짓일 경우에 대한 다른 동작을 수행하는 구문입니다.
반면에 Not 함수는 참이면 거짓을 반환하고, 거짓이면 참을 반환하는 간단한 불리언 연산자입니다.

Not 함수의 작동 원리를 살펴보겠습니다.

1. b가 True인 경우: True False True = (λx. λy. x) False True = False
2. b가 False인 경우: False False True = (λx. λy. y) False True = True

따라서 Not 함수는 입력된 불리언 값에 대해 반대 값을 반환합니다.
이것은 조건문이 아니라 불리언 연산을 수행하는 함수로 이해할 수 있습니다.

람다 대수 베타 축약

람다 대수의 베타 축약(Beta-reduction)은 람다 대수에서 함수 적용을 수행하는 과정입니다. 베타 축약은 함수와 인자를 결합하여 하나의 표현식으로 줄이는 과정으로, 계산의 기본 단위입니다.

베타 축약의 기본 규칙은 다음과 같습니다:

(λx. E1) E2 → E1[x := E2]

여기서 E1과 E2는 표현식이고, x는 함수의 매개변수입니다.
위의 규칙은 함수 (λx. E1)에 인자 E2를 적용하여 결과 표현식 E1[x := E2]를 생성한다는 것을 의미합니다. E1[x := E2]는 표현식 E1에서 모든 x를 E2로 치환한 결과입니다.

베타 축약의 예시

(λx. x + 1) 2

여기서 E1 = x + 1, x = x, E2 = 2 입니다. 베타 축약을 적용하면 다음과 같습니다:

(2 + 1) = 3

베타 축약은 계산을 수행하는 방법을 정의하며, 람다 대수에서 프로그램의 실행을 모델링합니다.
베타 축약을 반복하여 수행하다 보면, 주어진 람다 표현식이 최종 결과값으로 축약됩니다.
이 과정에서 중첩된 함수 적용이나 람다 표현식이 포함된 복잡한 표현식도 단순한 형태로 축약될 수 있습니다.

레퍼런스

• [[람다 대수 - 원본]]