정규형(normal form), 상위정규형(head normal form), 최상위정규형(weak head normal form)의 차이

함수형 언어 프로그래밍 관련하여 글을 읽다보면 정규형(NF: normal form), 상위정규형(HNF: head normal form), 최상위정규형(WHNF: weak head normal form)이라는 말이 나온다. 도대체 무슨 뜻일까?

세 용어 모두 수식을 계산하는 과정에서 나타나는 용어로서 정규형은 수식을 모두 계산한 형태를 뜻한다. 즉 더 이상 계산할 것이 없는 상태를 뜻한다. 예컨대 Python 람다 표기법을 사용하면 아래와 같은 람다 수식은 정규형이다.

lambda a, b: a + b

수식 자체가 함수로 계산되는데 함수의 인수가 없으므로 정규형이다. 이는 상위정규형도 되고 최상위정규형도 된다. 

그런데 아래와 같이 인수가 주어진다면 더 이상 정규형이 아니다.

(lambda a, b: a + b)(2, 3)

이를 계산하면 5가 되는데, 바로 이 5가 정규형이다. 

이처럼 수식을 정규형을 계산해 나가는 과정을 함수형 언어에서는 축약(reduction)이라고 부른다. 즉 정규형은 축약 가능한 수식(redex: reducible expression)이 전혀 포함되어 있지 않은 형태를 뜻한다.

그럼 상위정규형(HNF)이나 최상위정규형(WHNF)은 무슨 뜻일까? 사실 이 두 용어의 한글 용어를 생각해 내느라 나름 고심했는데, 이 두 용어는 수식을 지연 계산(lazy evaluation)할 때 사용한다. 지연 계산이란 실제로 필요할 때까지 계산을 미루는 계산 방식을 말한다. 실제로 필요할 때란 해당 수식을 출력해야 한다든지 다른 수식을 계산할 때 해당 수식의 값이 필요하다든지 하는 상황을 뜻한다. 이 때에도 필요한 만큼만 계산하므로 해당 수식이 함수 형태(lambda abstraction)라면 더 이상 계산하지 않는다. 그래서 위 람다 수식이 NF이자 HNF, WHNF이라고 말한 것이다. 

그럼 HNF과 WHNF의 차이는 무엇일까? HNF는 수식의 왼편(head)을 축약할 수 있다면 가능한 만큼 축약한 형태이다. 즉 람다 함수의 본체(body)에서도 왼편을 축약할 수 있으면 이를 축약해야 HNF이 된다. 하지만 WHNF은 맨 바깥 수식이 람다 함수라면 본체 내부의 축약 여부는 고려하지 않는다. 예컨대 다음과 같은 람다 함수들의 리스트가 주어졌다고 하자.

fs = [lambda a, b: a + b, lambda a, b: a - b]

이 때 다음과 같은 수식이 있다면

lambda a: fs[0](a, a)

이는 WHNF이다. 왜냐하면 수식의 맨 바깥 부분이 람다 형태(즉 함수)이므로 더 이상 축약하지 않아도 되기 때문이다. 하지만 HNF은 아니다. HNF이 되려면 람다 형태의 내부에서도 왼편 수식(함수에 해당하는 부분)이 축약 가능하면 안 되는데, 위 수식의 경우 fs[0]는 축약 가능하기 때문이다. 따라서 HNF으로 만들려면 fs[0]를 적용하여 다음과 같이 축약해야 한다.

lambda a: a + a

수식을 트리 형태로 그리다 보면 HNF과 WHNF은 트리의 루트(root) 부분, 즉 상위 부분과 관련이 깊은데, WHNF은 최상위가 더 이상 축약되지 않는 형태이며 HNF은 최상위를 포함하여 상위 왼편 부분이 더 이상 축약되지 않는 형태이다.

여기까지는 베타 축약(beta reduction)만 고려하여 설명한 것이며 에타 축약(eta reduction)을 고려하면 더 복잡해진다. 에타 축약은 아래와 같은 형태라도 축약 가능한 수식으로 보기 때문이다.

lambda a: f a

에타 축약에 따르면 위 수식은 f로 축약되어야 한다. 혹시 위의 HNF이 아래와 같은 형태였다면 

lambda a: 2 * a

에타 축약을 고려할 때 위 수식은 HNF이 아니고 아래와 같이 축약되어야 한다.

lambda a:  2 * a
→ (2 *)

물론 Python에서는 (2 *)와 같은 수식이 허용되지 않으므로 이렇게 축약할 수는 없다. 그런데 Haskell에서는 섹션(section)이라고 하여 이런 수식을 허용한다. 하지만 현재 버전(Haskell Platform 8.0.1)의 GHC(Glasgow Haskell Compiler)도 에타 축약까지 고려하여 WHNF으로 값을 구하고 있는 것은 아닌 것으로 보인다. 현재로서는 특별한 확장기능(Thomas Yaeger의 Lambdabot)을 설치한 경우에만 에타 축약을 허용하는 것으로 알려져 있다.