지연Lazy 평가를 이해하기 위해 필요한 용어

단어의 사전적인 뜻만 알아도 이해할 수 있을 것 같은데, 실제 용어가 의미하는 걸 정확히 알면 하스켈의 동작을 이해하는데 도움이 됩니다.

※ 지금까지 본 번역 중엔 지연 평가가 가장 입에 붙긴 하는데, 의미상으로 보면, “필요할 때 평가”가 더 직관적이지 않을까 합니다. 반드시 명사형으로 이루어진 용어만 된다는 편견만 없다면, 이런 번역도 좋아 보이긴 합니다. 그런데 나중에 어차피 영어 문서를 같이 읽어야 하니, 뜻이 완전 다르게 보이는 건 또 비효율적일 것 같다는 생각도 듭니다. 그런 것까지 고려하면, 현재까진 “지연 평가”가 가장 적당해 보입니다.

평가evaluate

보통 평가라는 말은 무언가의 가치를 매길 때 썼던 단어인데, evaluate를 평가로 번역하는게 딱 자연스럽진 않습니다. 코드의 가치를 매긴다고 말해도 돌아 돌아 맞는 뜻이긴 한데, reduce(참고 - 람다 대수 용어)가 일어난다는 의미로 바로 와닿지 않는 건 사실입니다. 하지만, 다르게 번역한 걸 찾아볼 수 없을 정도로 이미 굳어진 용어처럼 보입니다. 수학에서 reduce를 프로그래밍에선 evaluate로 표현하는데 우리말로는 각 각 축약, 평가로 번역합니다.

1 + 1

을 계산해서          
을 evaluate해서
을 풀어서         ->   2를 구한다.
을 reduce해서
을 실행해서

이 말들이 모두 같은 뜻으로 쓰입니다. 당장 evaluate를 대체할 단어가 떠오르지도 않고, 또 널리 퍼져있기 때문에 여기에서도 evaluate를 평가로 번역하겠습니다.

wikibooks haskell laziness

필요한 때가 되면 평가evaluation하는 전략을 지연Lazy 평가라 합니다. 지연 평가를 잘 활용하면 논리적으로 더 단순한 코드를 만들 수 있긴 한데, 퍼포먼스가 문제가 될 때가 있습니다. Lazy 동작을 잘 이해하고 때론 Strict로 바꿔야 합니다.

Strict, Non-Strict, Lazy, Eager

haskell wiki Lazy vs. Non-Strict

Strict와 Non-Strict는 reduce 방향에 따른 용어입니다.
프로그래밍 언어가 Strict하다는 말은 다음을 의미합니다. “함수를 실행하기 전에, 인자들은 항상 평가가 끝난 상태여야 한다.” = 수학 스타일로 말하면 “식 안에 있는 것부터 reduce한 후 바깥을 reduce한다.” 이걸 Strict하다고 말합니다. (어떤 것도 모호하게 두고 다음으로 넘어가지 않는다는 뜻에서 Strict를 쓴게 아닐까요?)

Non-Strict는 “함수에 들어오는 인자는 평가가 되지 않은 상태여도 상관 없다.” = “식 바깥부터 reduce하고, 그 다음 안에 있는 걸 reduce 한다.”

2023-01-06 추가:
위에 reduce 절차가 이루어지는 방향으로 설명하는 건 틀린 설명이라 합니다. (공식 위키에 틀린 내용이 올라가 있다니…) Strictness는 Bottom을 받았을 때 어떻게 동작하냐로 봐야 한다고 합니다. Bottom을 받고 Bottom을 내 뱉으면 Strict하다 말하고, Bottom을 받고도 정상 동작 후 값을 내뱉으면 Non-Strict라고 합니다. (나중에 Bottom이 평가되면 예외가 발생할 겁니다.)

Lazy와 eager는 reduce를 하는 타이밍과 관련된 말입니다.
당장 필요하지 않아도 redex를 만나면 항상 reduce를 하고 넘어가는 reduce 전략을 즉시eager 평가라 하고,
꼭 필요할 때까진 건드리지 않는 걸 지연Lazy 평가라 합니다.

Strict가 eager와 같은 작업 모양을 가리키고,
Non-Strict가 Lazy와 같은 작업 모양을 가리키지만 완전 동의어들은 아닙니다.

이렇게 자세한 뜻은 차이가 있지만, 거의 동의어처럼 쓰이긴 합니다.

여러 자료들이 마치 Strict vs Lazy처럼 오해하도록 만드는데, Strict vs Non-Strict 이고, 완전히 반대의 의미를 가지고 있지 않지만 eager vs Lazy로 말합니다.

최근 verse 언어 관련 소식을 들으며 lenient란 평가 전략을 택했다는 말을 들었는데, 이 게 Strict하게 동작하는 평가 방식 중 하나라고 합니다.
lenient 전략을 볼 수 있는 논문 https://www.cs.cmu.edu/~seth/papers/schauser-fplca95.pdf

다른 곳에 이리 나오는 곳은 없지만, 용어들이 지칭하는 대상들의 관계를 그림으로 그려보면 아래쯤 되는 걸로 보입니다.

구어체로 말하자면
Redex를 만나는 족족 평가해 버리면 Eager
bottom을 주면 바로 터져버리면 Strict
바로 바로 평가하니 bottom을 먹고도 바로 터지는 게 당연한데,
bottom 먹고 터진다고 다 Eager라고 할 수는 없다.
Lenient같은 것도 그렇다.

평가 전략과 Strictness는 아무런 연관이 없고, 우연히 같은 결과를 보여 줄 뿐입니다.

Thunk

번역하면 덩어리인데, 의미를 살펴보지 않고 그냥 뭉뚱그려서 보는 코드 덩어리입니다. 여기선 코드 덩어리로 번역하거나 그냥 thunk로 적겠습니다. 실제 구현은 메모리 어딘가에 있는 코드를 가리키는 포인터일 겁니다. 추측

하스켈에서 Thunk가 evaluate되기 시작하는 때

“필요한 때”가 두가지 형태로 나타납니다. 하나는 패턴 매칭이고, 하나는 primitive IO 함수 안에 있을 때입니다. 감싸고 있는 함수의 값을 구하려면 인자나, 안에 있는 함수의 값을 먼저 구해야 되니, 그때 평가되기 시작한다고 쓰지 않고, 콕 찝어서 패턴 매칭과 IO라 했을까요?

-- 다 같은 add인데 편의상 번호를 붙이겠습니다.
add1 (add2 1 2) (add3 3 4)

add1 값을 구하려면 add2와 add3 값을 알아야 하는데, 어디 패턴 매칭과 IO가 있다는 말일까요?
add1이 왜 값을 알아야 되는 상황이 될까요? 위 식은, 처음엔 add1도 드러나지 않는, 전체가 그냥 thunk로 남아 있습니다. 그러다 다른 IO안에서 add1을 부르던가, 어디서 패턴 매칭이되면 그제서야 add1이 평가될 필요가 생기고, 연쇄적으로 add2, add3가 평가될 필요가 생깁니다. 그래서 thunk를 평가하는 가장 시작점을 패턴 매칭과 IO라고 말한 겁니다.

Weak Head Normal Form

별도 포스트 참고 - WHNF에서 head의 뜻

Lazy 함수, Strict 함수

length [1]
show [1] -- 1을 show, []을 show

length 함수는 thunk : [] 까지만 reduce해도 1이라는 값을 구할 수 있습니다. show 는 thunk를 남기지 않고, 모두 reduce 해야 합니다. 이럴 때 show 함수가 length보다 더 Strict하다고 말합니다. 인자로 들어온 값을 한 단계라도 WHNF로 만들면 Strict 함수라 부릅니다. 아예 한 단계도 reduce하지 않는 함수를 Lazy 함수라 부릅니다.

f x y = length $ show x

이 경우 f는 x를 NF가 될 때까지 fully reduce하고, y는 전혀 손대지 않습니다. 그럼 x에 대해선 Strict하고, y에 대해선 Lazy하다고 말합니다.

Black-box Strictness analysis

번역하면, 블랙 박스 Strictness 분석쯤 될 것 같습니다. 소스를 볼 수 없는 함수의 Strictness를 확인하려면 undefined를 이용하면 됩니다. undefined는 평가되는 순간 에러가 나니 인자로 undefined를 넣어 보면 됩니다.

> length [undefined, undefined, undefined]
3
> head (4 : undefined)
4

2023.3.15 추가

ghci> putStrLn $ (\ x y -> (x,y))    1    ((\z -> undefined) 2) `seq` "ok"
                                  ^^^^^^  ^^^^^^^^^^^^^^^^^^^^^
                                  head x          head y
                               넣을 표현식      넣을 표현식   

seq는 head x와 head y에 넣을 것들을 NF로 만듭니다.
1은 NF이고, y에 넣을 표현식엔 redex가 보입니다. reduce하면 undefined가 됩니다.

ghci> putStrLn $ (\ x y -> (x,y))    1    undefined `seq` "ok"
                 ^^^^^^^^^^^^^^^^ ^^^^^^  ^^^^^^^^^
                      (나)          NF       NF
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                (가)

(가)의 헤드는 모두 NF가 되었습니다. (나)는 관심없습니다.
지금은 1과 undefined로 더이 상 없는 것이 눈에 보이는 상태지만, 만일 표현식이었다면 안쪽은 모르지만 Weak, (가)의 Head는 모두 Normal Form입니다.
“OK”를 출력합니다.

만일, strict 함수면

ghci> :set -XBangPatterns
ghci> putStrLn $ (\ !x !y -> (x,y))    1    undefined `seq` "ok"
                 ^^^^^^^^^^^^^^^^^^ ^^^^^^  ^^^^^^^^^
                        (나)          NF       NF

!x와 !y에 들어갈 값도 평가해야 합니다. undefined를 평가하니 예외가 일어납니다.

GHCi는 IO가 동작한다.

하스켈 repl인 GHCi에서 코드 동작을 확인하는 작업은 모두 IO 위에서 돌아가기 때문에 Lazy여부를 보는게 가끔 헛갈릴 때도 있습니다. IO출력을 위해서 show가 가능한 단계까지 평가가 이루어진다는 말입니다. 다음처럼 결과값을 바로 IO 출력에 물리지 않도록 테스트하면 됩니다.

let (x, y) = undefined in x -- Error
let (x, y) = const (3, 4) undefined in x -- No error (패턴 매칭 중)

const 함수는 에러가 나지 않습니다. undefined를 평가하지 않고, (3,4)를 결과로 뱉습니다.

Lazy 패턴 매칭

별도 포스트 참고 - Lazy Pattern Match

미래에서 값 빌려오기

재미난 표현인 것 같습니다. Lazy평가는 미래의 값을 바꾸거나 하지 않는다면, 미래의 값을 미리 당겨서 쓸 수 있게 합니다.

data Foo a = Foo {value :: a, next :: Foo a}

circularFoo :: Foo Int
circularFoo = x
  where
    x = Foo 1 y
    y = Foo 2 x

생성자도 일반 함수와 똑같이 Lazy하게 평가 됩니다. circularFoo가 평가되기 시작하면, 언제 끝날지 모르지만 다음처럼 힘닿는데까지 갈겁니다.

Foo 1 (Foo 2 (Foo 1 (...)))

하지만 Lazy하게 평가되기 때문에, Foo 데이터 안에 next를 평가할 일이 없으면 다음 상태로 머뭅니다.

thunk -- 처음엔 그냥 thunk
Foo 1 thunk -- 한 단계 평가
Foo 1 (Foo 2 thunk) -- 또 한 단계 평가
...