달력

3

« 2024/3 »

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
2017. 4. 22. 14:40

03. Reduction Programming Language/Lambda Calculus2017. 4. 22. 14:40

1. Reduction이란?

: λ Calculus에서 식을 줄여서 간단한 형태로 만드는 것. 식을 변형시키는 것.




2. Beta, Alpha Eta Reduction


2-1. Beta Reduction

: 아마, 가장 직관적이지 않을까 싶다. β reduction이란,  함수를 적용한 결과를 계산하는 절차를 말한다. 본질적으로, 직접 대체하는데 다음 식을 보자.


((λ (x).BODY) a)   ->β   BODY[a\x] = BODY                              ->β는 β reduction을 의미한다.


식이 변하는 과정을 단계별로 보면, 


1)  ((λ (x).BODY) a)

: x는 받은 인자이며, BODY에 넘겨진다. 지금 상황은 이 함수에 a를 넘기려는 상황이다.


2) ->β   BODY[a\x] = BODY

: BODY[a\x]는, 'BODY에 있는 모든 x를 a로 대체한다'는 의미다. BODY에 x가 없다면,

아무 변화가 없으므로 그냥 BODY가 된다.



β reduction으로 식을 줄이는 예제들

1) (λ z.f z)b  ->β  (f z)[b\z] = (f b)

2) (λ z.y)c  ->β  y[c\z] = y 

3) (λ y.c)((λ z.f z) b)  ->β  (λ y.c)((f z)[b\z])

= (λ y.c)(f b)

->β  c[(f b)\y]

= c 



2-2. Alpha Reduction

: 식을 많이 줄이진 못한다. Renaming이라고 부르기도 한다. Alpha Reduction을 할때, 주의할 점이 있는데 변수의 Scope를 바꾸면 안된다는 것이다. 다음 식을 보자.


(λ (x) (+ x y))


 위의 식에서, x는 함수의 부분으로 쓰이고 있다. 이걸 'x는 Lambda식의 Scope에 Bound되었다'라고 표현하며 'y는 free'고 표현한다. (λ (x) (+ x y))를 다음과 같이 적을수도 있다.


(λ (x) (+ x y))  ->α  (λ (z) (+ z y))


Alpha Reduction 전후는 동일하다. 그냥 변수의 이름을 바꿨을 뿐이다. Alpha Reduction을 적용할때... 변수의 Scope를 바꾸지 않도록 주의해야 하는데, 다음 식을 보자.


(λ (x) (+ x y))  ->α  (λ (y) (+ y y))


 y는 처음에 Unbound였으므로, Alpha Reduction후에 y의 의미가 바뀌었다. 이걸 Name Conflict라고 부른다. Alpha Reduction전에는 y의 Scope가 Global이었으나 Alpha Reduction후에 Local로 바뀌었다.



2-3. Eta Reduction

: Abstractions에서 쓸모없는 변수들을 제거하기 위해 쓴다. 다음 식을 보자.


((λ (x).BODY) x)  ->η  BODY


 위의 Function Abstraction에서, 함수가 쓰일때마다 인자는 그저 BODY에 전달될 뿐이다. 따라서 BODY와 동일하다. 이전의 Alpha Reduction과 비슷하게, Eta Reduction도 Name Conflict가 없어야 한다. 그래서 x는 BODY에서 free이면 Eta Reduction을 적용하면 안된다. Name Conflict를 피하기 위해, 먼저 Alpha Reduction을 하는 것도 좋다.




3. Reference

λ Calculus tutorial

- haskell wiki

'Programming Language > Lambda Calculus' 카테고리의 다른 글

04. Evaluation Strategies  (0) 2017.05.23
02. Lambda Calculus의 Syntax  (0) 2017.04.16
01. Lambda Calculus란?  (0) 2017.04.15
:
Posted by syjdev