여기 글들은 일종의 질문입니다. 용어 선택도 학계, 업계에서 쓰는 걸로 되어 있지 않고, 틀린 내용이 있을 수도 있습니다.
또 한 번 용어가 찜찜함을 남기네요. 그냥 가장 바깥 생성자나 람다식을 WHNF로 보고 넘어가면 되는데, 왜 이런 용어를 붙였는지가 궁금해서 또 서핑의 늪에 빠져 버렸습니다.
이해한 생각을 정리한 게 아니라, 추측한 내용을 길게 적어 놓았습니다.
우균님의 정규형(normal form), 상위정규형(head normal form), 최상위정규형(weak head normal form)의 차이
포스트 작성 후 보게 되었는데, 잘 못 이해한 건지 HNF부분이 조금 다른 부분이 보입니다. 틀린 내용 정리가 끝나면 수정하도록 하겠습니다. (우균 교수님이 더 많은 글을 공개하시거나 책을 내시면 좋을 것 같은데, 공개 글이 많이 보이진 않아 아쉽습니다.)
NFData (Normal Form Data)의 seq 함수 동작을 보다 보니, 혼동이 왔습니다. 분명 lazy를 잘 못 이해하고 있습니다. lazy는 아무것도 안하고 지나가는게 아니라, 완벽하게 끝내진 않더라도 때에 따라 일정 단계까지는 해석하고 지나갑니다. lazy는 지나가면서 나중에 실행하겠다는 계획만 잡고, 지금은 실행을 하나도 하지 않는다는 뜻이 아닙니다. 이 일정 단계가 바로 WHNF입니다. 표현식은 여러번 reduce를 거쳐 최종 값에 도달하는데, 어느 단계까지 도달했냐에 따라 이름을 붙여놨습니다.
add x y = x + y
( (add 1 2), (add 3 4) ) ------(가) WHNF
= ( (1 + 2), (add 3 4)) ) 또는 ( (add 1 2), (3 + 4) ) ------(나) WHNF
= ( (1 + 2), (3 + 4)) ------(다) WHNF
= (3 , 7) -----(라) WHNF, NFQ: (+)는 \x.\y-> x + y로 여기에 인자를 넣어주는 작업이 beta reduce이고, (+) 매핑은 그냥 reduce라 부르면 될까요? (+ 는 (1,2)와 3을 매핑한 것으로 볼 수 있습니다.)
추측 A: 람다 대수에서는 +의 동작이 별도로 정의된 개념, 형식, 용어로 표현되는 게 아니라, 람다 대수의 abstraction과 application으로 표현됩니다. 람다 대수에서 함수의 실행은 beta reduce로 나타납니다. 그럼 reduce와 beta reduce를 구별할 필요는 없을 것 같습니다.
(가)를 만나면, 어느 단계까지 평가하고 뒤로 미룰까요? 처음엔, 전체를 thunk로 두고 아무 것도 reduce하지 않습니다. 튜플이 필요한 시점이 오면 (thunk, thunk)로 reduce 합니다. 튜플안의 것들이 필요한 시점이 오면 (3, thunk) 또는 (thunk, 7), 둘 모두 필요해지면 최종 (3, 7)에 도달합니다. thunk가 들어간 중간 단계의 모양을 WHNF라 합니다. 왜 이런 이름이 붙었는지 살펴 보겠습니다.
※ 계산 되지 않은 식을 thunk라 부릅니다. 번역하면 수식 덩어리쯤 될까요? 코드 덩어리?
적용할 수 있는 reduction은 모두 적용한 표현식. 모든 단계를 평가해서 얻게 되는 결과입니다. (라)
※ 람다 변수에 (헤드에 있는 매개 변수를 통해) 인자를 넣어, 람다 body에 있는 변수들을 인자로 대체하고 람다 헤드를 없애는 작업을 beta reduce라 합니다. (\x -> x + 1) 2 를 application이란 beta reduce 작업을 하면 2 + 1이 됩니다.
Lambda Calculus 요약 - unc/stotts
※ 그런데, Parallel and Concurrent Programming in Haskell - Simon Marlow 책의 29p Deepseq에서 NFData 클래스 설명 부분을 보면
it isn’t possible to put a function in normal form
이라 말합니다. 람다식이 함수인데, 인자 없는 람다식이 NF이란 말인지 아닌지 헛갈립니다. 함수는 안을 들여다 볼 수 없기 때문에, 안에 redex가 있을지 없을지 모르니 NF라 장담할 수 없습니다.
추측 - 람다 대수에서 보면 값이란 게 없습니다. 모든 대상들은 함수입니다. 수나, 참 거짓등도 모두 함수로 정의되어 있습니다. 람다식을 reduce하고 reduce해서 나온 최종 결과가 값처럼 별도의 개념이 아니라 수나 참 거짓을 의미하는 람다식으로 끝납니다. 람다식들 중 더 이상 reduce 할 수 없는 상태면 function이라 부르지 않는 건 아닐까요?
사실, 여기 head란 말 때문에 이 포스트를 정리하게 됐습니다.
https://en.wikipedia.org/wiki/Beta_normal_form
head 위치에 beta redex가 남아 있지 않은 표현식. 위 사이트 예시를 보면
(위 사이트를 보면 beta redex가 없는 걸 beta normal form 이라 부르는데, 헤드에 beta redex가 없을 땐 head beta normal form이라 부르지 않고 줄여서 head normal form이라 부른다고 합니다.)
𝜆x2. (𝜆x1.A) M1 M2
^^^^^^^^^^^^^
--(ㄱ)𝜆x1,𝜆x2 이런 부분이 head인데, 이 곳에 beta redex가 남아 있다니 무슨 말일까요? M1에 (𝜆x1.A)를 적용할 수 있으니 (ㄱ) (𝜆x1.A) M1이 redex인 건 알겠는데, 여기가 왜 head일까요? 𝜆x2.의 body 아닌가요? 참고 - 람다 대수 용어
application이 abstraction보다 우선 순위가 높음을 적용해서 괄호로 명확한 순서를 표시하면
참고 - Stackoverflow - head position in lambda calculus
...𝜆x2. (((𝜆x1.A) M1) M2) ...
^^^^^^^^^^^^
-- (ㄴ)
-- 위 식이 가질 수 있는 형태 중 단순한 걸 살펴보면
(((𝜆x1.A) M1) M2) M3 head 위치에 beta redex가 있는 표현식이 어떤 게 있을까요? HNF는 head에 넣어 줄 값이 redex가 아니라는 뜻일까요? (이 후 나오는 redex, reduce는 각 각 beta redex, beta reduce를 의미합니다.)
A가 뭔지 모르지만 (ㄴ) ((𝜆x1.A) M1)가 M2, M3를 받는 걸로 봐서 (ㄴ)은 람다 abstraction으로, M2,M3를 받을 변수가 head에 있어야 합니다. (ㄴ) 전체가 head는 아니지만, (ㄴ)을 reduce 하고나면, 헤드가 보일 겁니다. 그래도 (ㄴ) 전체를 head position이라 부르는 건 찜찜합니다.
아마도 람다식의 .의 앞부분 𝜆x를 말하는 head와 다른 걸 말하는 것 같습니다. 연이은 reduce 작업 중 첫 번째란 의미에서 head인 것 같습니다. 일단, 이렇게 가정하고 진행해 보겠습니다. 이 쪽이 하스켈쪽하고도 더 잘 맞아 보입니다.
하스켈에서는 가장 바깥 생성자the outermost constructor를 head라 부릅니다. 왜 그럴까 고민해 봤습니다.
-- 레이어마다 번호를 붙여서 보겠습니다.
M1 (M2 (M3 1))여기서 가장 바깥 M1을 head라 부릅니다. 이 것과 람다 대수쪽 head가 같은 뜻일까 보면
-- M1을 \x1 -> ..., M2를 \x2 -> ..., M3를 \x3 -> ...
= (\x1 -> ...) ((\x2 -> ...) ( (x3 -> ...) 1 ))람다 대수의 헤드와 여러겹 쌓여있는 식의 헤드가 “실행”의 의미로 좇아가면 흐름이 반대입니다.
여기서 용어가 혼동 됩니다. ’reduce’와 값을 구하기 위해 ’함수를, 연산을 실행한다’와 같은 뜻일까요?
값을 구하려면 x3 람다식을 먼저 풀면서 바깥으로 나와야 하는데, reduce는 x1 람다식부터 합니다. reduce란 작업은 람다 변수를 통해 정보를 넣어주고, 람다 변수를 없애는 작업입니다. 할 수 있는 연산을 모두 실행해서 결과값을 얻는게 reduce가 아닙니다.
(\f -> (\x -> f 1 + x)) (\y -> y - 1) 2
^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^ ^^^
(A) (B) (C)
= ( (\f -> (\x -> f 1 + x)) (\y -> y - 1) ) 2
= (\x -> (\y -> y - 1) 1 + x) 2 -- (B)를 (A)의 람다 변수f를 통해 넣고, f를 지웁니다. reduce했다고 말합니다.
^^^^^^^^^^^^^^^
-- 헤드를 reduce하고 나니, 안 쪽에 새로운 redex가 생겼습니다.
-- 안 쪽을 reduce 한다면
-- = (\x -> 0 + x) 2
-- ^^^^^^^^^^^^^^^
-- 하지만 하스켈은 바깥 쪽(헤드)을 reduce 합니다.
= (\y -> y - 1) 1 + 2 -- prefix로 바꿔 쓰면 (+) ((\y -> y - 1) 1) 2
^^^^^^^^^^^^^^^
-- (\a.\b -> a + b) ((\y -> y - 1) 1) 2 를 beta reduce한 상태입니다.
-- 가장 바깥 쪽은 beta reduce를 했지만 안 쪽에 redex가 아직 남아 있습니다. WHNF
= 0 + 2 -- 안 쪽 것도 reduce 했습니다. WHNF
= 2 -- NF실행 순서는 어떻게 될까요?
(A)는 (B)가 실행된 후 만들어진 람다식에 (C)를 넣으면서 실행합니다.
reduce 순서는 어떻게 될까요?
(A)에 (B)를 넣어 beta reduce 하고, 이렇게 나온 람다식에 (C)를 넣어 reduce 합니다.
정리하면, 여러번 reduce를 거쳐야 되는 식이 있고, 여기서 첫 번째 reduce를 하게 되는 식을 head라 부릅니다. 첫 번째 실행되는 식이 아니라, 첫 번째 reduce되는 식을 말합니다.
(이 포스트 첫 부분의 예시 (add,add)는 튜플이 계속 살아 있으니, 헤드가 바뀌지 않지만, 여기 람다식은 헤드를 reduce하고 나면, 그 다음게 헤드가 되는 게 아닐까요?1)
이해한게 맞는지 아직 고민 중입니다. 다른 의견이 있는 분은 댓글 부탁드립니다.
가장 바깥 쪽 redex를 reduce하면, Head Normal Form이 됩니다. head에 redex가 남지 않았다는 뜻입니다. 하스켈쪽에서 보면 가장 바깥 쪽 한 단계만 evaluate했다는 얘기입니다. 용어의 근원을 살피는 건 복잡하지만, 동작 자체는 간단합니다.
인자를 가지고만 있고 reduce하지 않은 함수
가능한 reduction 작업을 모두 적용하지는 않은 상태. 지연lazy 평가를 통해 얻게 되는 결과입니다. 하스켈에서는 인자를 모두, 또는 일부를 아직 적용하지 않은 함수를 말합니다. 아직 적용하진 않았지만, 인자가 없는 상태는 아닙니다.
add x y = x + y 일 때,
add 만 있다면, 인자 없이 더 이상 reduce할 수 없습니다. 안 쪽에 redex가 없는 걸 안다면 HNF , 안 쪽에 뭐가 있을지 모르면 WHNF
add 1 2 람다 대수의 application. 인자를 모두 주었어도 이대로 있으면 redex — (ㄷ)
1 + 2 까지 도달해도 redex
3 이 되면 NF
(ㄷ) add를 \x.(\y -> x + y) 람다 함수에 이름을 붙여 놓은 것으로 보면 \x.(\y -> x + y) 1 2 라고 쓴 상태입니다.
(𝜆x1.A) M1 M2 와 같은 구조입니다. 헤드에 redex가 있으므로 NF,HNF,WHNF 모두 아닙니다. 더 자세한 설명이 아래 쪽에 있습니다.
값 생성자
값 생성자로 싸여 있다는 게 왜 redex가 있을지도 모르는 상태일까요?
생성자도 하나의 함수로 볼 수 있으니, 아직 필요한 인자를 받지 않은 Just 등이 단독으로 있으면 WHNF일 것 같은데, Just 1도 WHNF로 보고, True도 WHNF로 본다고 합니다. 왜 그럴까요? True 안에는 어떤 reduction이 있을 가능성이 있을까요? 이럴 때는 WHNF가 아니라 HNF이며 NF일 것 같이 보입니다.
힌트는 생성자constructor란 말에 있는 것 같습니다. 생성자 자체가 값은 아니라, 값을 만들어 내는 걸 생성자라 부릅니다. 생성자가 값을 만들어내는 절차를 reduction으로 보는 겁니다. 값을 만들어 낼 때 redex가 있을 수도 있다면 WHNF입니다.
Just (1 + 2)가 있을 때, (1 + 2)가 계산reduce되는 시점은 Just를 벗겨 낼 때(패턴 매칭할 때)입니다. 그 전에는 계산되지 않은 WHNF상태로 머물게 됩니다. 가장 바깥쪽 생성자가 안쪽을 가리고 있다고 봐도 됩니다. 우리 눈에는 Just 안 쪽이 보이지만, GHC는 패턴 매칭을 만날 때까지 안 쪽을 보지 않습니다. 안 쪽에 1 + 2 같은 redex가 있을지도 모르니 Weak HNF입니다.
람다 함수
인자를 아직 받지 않은 람다 함수
\x -> x + 1 -- NF, HNF, WHNF이 상태로만 보면 더 이상 reduce할 수 없습니다. 인자를 받아야만 가능합니다.
헤드에 reduce 할게 없으니, HNF, WHNF이고 전체를 봐도 reduce 할게 없으니 NF입니다. 만일, 안 쪽 사정을 모른다면 NF인지는 결정할 수 없고, WHNF라 부릅니다.
(\x -> x + 1 ) 2 -- redex이제 가장 바깥이 redex가 되었습니다. 인자 2가 있어 reduce할 수 있으니 NF, HNF, WHNF 모두 아닙니다.
2 + 1 -- redex가장 바깥에 있던 redex를 reduce했지만, 아직 reduce 단계는 남아 있습니다. NF가 아닙니다.
위 예시 코드를 다시 보면
(\x -> (\y -> y - 1) 1 + x) 2 -- redex헤드(가장 바깥 리덱스)의 2를 안으로 넣어 reduce 하고 나면 HNF가 되고, 그 식에 redex가 없다면 NF입니다.
헤드를 reduce해서 HNF인데, 위처럼 안에 (\y -> y -1) 1 같은 redex가 있을 수도 있습니다. 만일 안 쪽에 redex가 없다면 NF가 되고, 안에 redex가 있는지 없는지 모를 때는 WHNF라고 부릅니다.
NF, HNF, WHNF를 마치 실행 단계에 따라 리니어하게 이름을 붙인 것 같은데 의미상 꼭 그렇진 않습니다. 여러 생성자로 감싸져 있는 값을, 여러 레이어로 감싸져 있다 표현하는데, 헤드는 가장 바깥쪽 레이어를 가리킵니다. 레이어로 이들의 차이를 설명하면,
HNF는 헤드 레이어만 redex가 없으면 됩니다.
NF는 헤드 레이어만 redex가 없는게 아니라, 모든 레이어가 redex가 없어야 합니다.
WHNF는 헤드 레이어는 redex가 없고, 그 외 레이어는 redex가 있을 수도 없을 수도 있습니다.
(있을 수도, 없을 수도 있다는 의미로 Weak를 붙인 게 아닐까요?)헤드만 redex가 없기만 하면 HNF인데, 왜 하스켈에선 HNF는 쓰이지 않는다고 했을까요? 아직 이 말은 이해하지 못했습니다. wikibooks - There is also a ‘head normal form’, but it’s not used in Haskell.
모두 redex가 없는 경우 HNF라 불러도 되고 WHNF라 불러도 됩니다. HNF가 없다기 보다, Lazy를 설명할 때 HNF, 즉 헤드만 보는 게 아니라, 남은 레이어들이 redex가 있을 수도 있다는 가정하에 설명하니 WHNF란 용어만 있으면 된다는 뜻 아닐까요?
참고
남현욱님의 WHNF - 사실, 하스켈에 필요한 WHNF의 실무적 지식은 여기 포스트에 있는 것만 알고 지나가도 됩니다.
Haskell.org WHNF
What is weak head normal form? - stackoverflow
전체 표현식이 NF냐 아니냐가 관심사가 아닙니다. head에 redex가 없는 걸 HNF, 이 중 뒤따라 나오는 식들이 redex가 있든 없든 상관 안하는 걸 특별히 WHNF라 이름을 붙여놨습니다. 하스켈에서 가장 간단한 구별법은 가장 바깥이 application이면 WHNF가 아니고(왜냐 하면 reduce가 되는 redex이니까), 람다 abstraction이나, 값 생성자면 WHNF라 합니다.
(\x -> x + 1) -- reduce할 게 없습니다. NF
(\x -> x + 1) (1 + 3) -- 인자가 있어 reduce할 수 있는 redex이므로 WHNF가 아닙니다.
(\x -> x + 1) 1 -- 인자가 redex냐 아니냐는 구분 요소가 아닙니다.
-- 이 것도 위와 마찬가지로 reduce할 수 있으니 WHNF가 아닙니다.(1 + 1, 2 + 2) -- 가장 바깥쪽이 (,)로 튜플 값 생성자이므로 WHNF
-- (\x.\y -> (x,y)) (1+1) (2+2) redex 상태에서 가장 바깥, 즉 헤드 단계만 beta reduce하면
-- (1 + 1, 2 + 2)
-- 말로 풀면 함수 (,)는 (1+1)과 (2+2)를 인자로 받아 reduce한 결과가 (1 + 1, 2 + 2)란 뜻.
-- 1 + 1 과 2 + 2 는 관심 대상이 아닙니다.
(2,4) -- 안 쪽이 redex이냐 아니냐는 구분 요소가 아닙니다.
-- 위와 마찬가지로 가장 바깥쪽이 튜플 생성자이니 WHNF. 만약 안 쪽까지 관심을 가진다면 NF
3 + 3 -- 가장 바깥쪽이 함수 + application이므로 WHNF가 아닙니다.안에 있는 내용물을 보지 않고, 가장 겉만 보면 ( , ) 값 생성자입니다. 안에 게 reduce 됐든 안됐든 관심이 없습니다. 이 상태는 WHNF입니다. 그런데 패턴 매칭해서 안에까지 들여다 보니 reduce할 게 없는 상태이면 NF입니다. 뒤집어서 따라가면, 모든 NF는 WHNF도 된다는 얘기입니다.
알게 된 용어로 lazy 평가를 설명하면,
lazy평가는 보이는대로 바로 NF로 evaluate하지 않고, WHNF로 머물다가 꼭 필요한 때가 오면, 필요한 단계만큼만 reduce하는 평가 전략을 말합니다.
비유하자면, 단계적으로 가야할 길이 나타나는데, 요건이 맞아야만 길을 따라 갈 수 있습니다.
가야할 길을 찾았고, 요건이 모두 있습니다. redex
요건을 써서 첫 번째 가야할 길을 가고, 다음 단계의 길은 아직 찾지 않습니다. WHNF
다음 단계도 조건이 맞아 또 다음 단계로 가서 길을 찾으니 막다른 골목입니다. NF
WHNF도 NF도 첫 번째(헤드)가 normal form이니 HNF입니다.
헤드란게 가장 바깥 쪽 생성자를 의미한다면 다음과 같은 경우는 어떻게 보면 될까요?
(\x.\y -> x + y) 1 2 ----------(A)
^^^^^^^^^^^^^^^^^^^^여기까지가 헤드(람다식의 헤드가 아니라, 가장 바깥 쪽 식이란 뜻)일텐데, 헤드에 있는 redex를 beta reduce 하면
(\y -> 1 + y) 2 ----------(B) (A)식과 비교해서 헤드에 있던 redex를 reduce했으니 (B)는 WHNF로 보면 되지 않을까요?
전체식이 (A)였는데 중간 과정으로 나타난 (B)는 WHNF라 볼 수 있고, (B)에서부터 시작을 했다면, (B)는 redex로 볼 수 있을 것 같은데, (B)는 WHNF가 아니라고 합니다.
(A)의 헤드를 reduce해서 나온 식이긴 하나, (A)의 헤드가 사라지면, 이 식 자체만 놓고 봐야 합니다. 위에 처음 나온 튜플 예시처럼 헤드가 보인다면 WHNF 가 될 수 있지만, 지금처럼 (A)의 헤드 흔적이 모두 지워지면, 이 식 자체는 redex입니다.
-- beta reduce하면
(((𝜆x1.A) M1) M2) M3
^^^^^^^^^ ------------- (A) 여기가 헤드
((𝜆x2. ... ) M2) M3
^^^^^^^^^^^^^ --------- (B) 헤드(A)를 reduce하면 여기가 헤드
(𝜆x3. ... ) M3
^^^^^^^^^^^^^^^^^^ ----- (C) 헤드(B)를 reduce하면 여기가 헤드