0강 : 준비

1강 : 기본 문법

2강 : 꼬리재귀, 매개변수 다형성, 사용자 정의 타입

3강 : 커링, 스테이징, map, filter, fold

4강 : 컨티뉴에이션 패싱 스타일(CPS)

4.5강 : n-Bishops 문제

5강 : 예외처리, 모듈, 함자  

5.5강 : 레드-블랙 트리 구현

6강 : 시퀀스 자료구조와 병렬성


다음의 코드를 생각해보자. 

fun foo (x, y) = x
foo(1, 1 div 0)


이 코드는 에러가 난다. SML은 코드를 즉시 연산(eager evaluation) 하기 때문에 파라미터 값이 먼저 계산되기 때문이다. (엄격한 계산, strict evaluation이라고도 불린다. 다만 즉시 연산이 더 직관적이라 이 글에선 즉시 연산이라 하겠다.)


이걸 고칠 수 있는 방법이 없을까? foo 함수는 두번째 인자는 아예 필요로 하지도 않는다.


하나의 예시를 더 들겠다. map f [1, 2, …, 1000]을 계산한다고 치자. SML은 즉시 연산을 하기 때문에 1000개의 원소에 f를 전부 호출할 것이다. 


하지만 계산된 리스트의 첫번째와 두번째 원소만 필요로 한다면? 우리는 필요 이상으로 계산을 한게 되버린다.


원하는 인자만, 원하는 시간에 계산할 수 있는 방법이 없을까?




1. 지연된 연산


지연된 연산(lazy evaluation)은 즉시 연산의 반대되는 개념으로, 표현식을 바로 계산하지 않고 값이 필요할때만 계산한다. (게으른 연산, 느긋한 계산법이라고도 불린다.)


즉시 연산에선 변수에 값이 바인딩되어야 하지만, 지연된 연산을 지원하는 언어에선 변수에 표현식이 바인딩되며 필요할때 연산을 강제하여(forcing) 값으로 만든다.


지연된 연산에는 단점이 하나 있는데, 바로 코드를 예측하기 더 어려워진다는 것이다. 


int list를 리턴하는 함수가 있다 치자. 지연된 연산에선 [raise Div, raise Div, raise Div] 을 리턴해도 문제가 바로 생기지 않는다. 


누군가가 저 리스트를 사용할때 raise가 강제되어 에러가 나므로 잠재적 시한폭탄과도 비슷하다고 볼 수 있다. 


같은 이유로 시간복잡도를 계산할때도 굉장히 머리가 아파진다. val x = map f L은 O(1)이 걸린다. map을 바로 계산하지 않기 때문이다. 다만 x를 사용할때 추가적으로 시간이 걸린다.


하지만 SML은 즉시 연산을 하는 언어가 아닌가? 왜 지연된 연산을 배워야 할까? 그만큼 원할때 계산을 한다는 장점이 크기 때문이다. 


또한 SML에서 지연된 연산을 구현할 수 있으며, 프로그래머가 필요할때만 연산을 지연시킬 수 있다. 따라서 즉시 연산과 지연된 연산의 장점을 모두 가질 수 있다.


그렇다면 SML에서 지연된 연산을 어떻게 구현할까? 전에 람다식을 배울때, 함수는 일급 객체다, 함수는 값이다 라는 말이 기억나는가?


val x = map f L

이란 값이 있으면 이걸 람다식에 넣어서 

val x = fn () => map f L 

로 만들 수 있다. 함수는 값이기 때문에 map f L은 계산되지 않는다. x()로 호출해야만 그 값이 계산된다. 람다식을 서스펜션(suspension)처럼 사용하는 것이다.


이걸 썽크(thunk)라고도 부른다. 정확히는 썽크는 unit -> t 타입의 값을 말하고 서스펜션이라고도 한다.


*공부하다보니 지연된 연산을 하는 언어(예를 들면 Haskell)에서 즉시 연산을 어떻게 구현하는지 궁금해졌다. 조금 찾아보니 f (g x)를 즉시 연산하고 싶으면 f $! (g x) 처럼 $! 연산자를 쓰면 된다고 한다. 난 Haskell을 모르니 틀리면 댓글로 말해주면 좋겠다.


이제 이 아이디어를 코드로 구현해보자.

signature LAZY = 
sig
  type 'a t (* 지연된 연산을 하고싶은 타입의 썽크 *)
  val lazy : (unit -> 'a) -> 'a t
  val force : 'a t -> 'a
end
structure Lazy :> LAZY =
struct
  type 'a t = unit -> 'a
  fun lazy f = f
  fun force f = f ()
end


lazy 함수는 아무것도 안하는것처럼 보이는데, 그게 맞다. 인터페이스와 구현을 분리하기 위해 lazy란 이름을 부여한것 뿐이다. 이렇게 하면 유저가 개념적으로 지연된 코드와 즉시 연산할 코드를 분리할 수 있다.


val L = List.tabulate (100, fn i => lazy (fn () => i * i))

이 코드는 길이 100의 리스트를 생성하지만 각 원소를 바로 계산하지 않는다.


또한 Haskell같은 지연된 연산을 하는 언어들은 계산할때 메모이제이션을 한다고 한다. 동일한 지연된 값을 두번 계산할 경우, 첫번째에서 값을 저장하고 두번째는 저장한 값을 갖다쓴다.




2. 무한 자료구조


모든 정수를 구하려면 어떻게 해야할까? 다음의 코드는 어떨까? 

fun integers n = n :: ~n :: integers (n + 1)
val all_integers = 0 :: integers 1


참고로 이제서야 알려주지만 SML에서는 음수를 구하려면 -대신 ~를 써야한다.


이론적으로 all_integers는 [0, 1, -1, 2, -2, 3, …]가 되지 않을까? 그렇다. 물론 프로그램이 영원히 끝나지 않겠지만. 


하지만 지연된 연산을 쓰면 무한루프에 빠지지 않고 무한한 값을 “저장”할 수 있다.


다음의 list’ 타입은 우리가 흔히 아는 리스트이다. Nil은 빈 리스트이고 Cons는 ::연산자의 또다른 이름이다 (역사적인 이유로). 

datatype 'a list' = Nil | Cons of 'a * 'a list'


우리는 리스트를 저장하는 대신 리스트의 썽크를 저장해서 llist (lazy list) 타입을 정의할 것이다.

datatype 'a llist = Nil | Cons of 'a * (unit -> 'a llist)


이제 모든 자연수를 구하는 llist를 보여주겠다. 

fun natsFrom n = Cons (n, fn () => natsFrom (n + 1))
val nats = natsFrom 0 


nats 변수에 모든 자연수의 정보가 담긴 샘이다. 


이번에는 tabulate의 llist 버전을 보자. 

(* lazyTabulate : (int -> 'a) -> 'a llist *)
fun lazyTabulate' f i = Cons(f i, fn () => lazyTabulate' f (i + 1))
fun lazyTabulate = lazyTabulate' f 0
(* raise Div *)
val x = lazyTabulate (fn i => 1024 div i)


여기서 문제점이 발생한다. x는 raise Div가 되어 예외가 발생한다는 것이다.


llist의 정의를 다시 보면,

datatype 'a llist = Nil | Cons of 'a * (unit -> 'a llist)


Cons of ‘a * …이므로 ‘a는 무조건 계산이 되어야 한다는걸 알 수 있다. 이건 우리가 추구하는 지연된 연산과는 거리가 있다. 


llist는 리스트를 만드는 것만 지연했는데, 리스트 안의 원소를 계산하는것조차 지연하려면 어떻게 해야 할까?




3. 스트림


필요할때까지 원소를 구하는걸 최대한 지연시키는 자료구조를 최대지연적이다(maximally lazy) 라고 하겠다.


최대지연적 자료구조중 하나인 스트림을 보자.

datatype 'a stream = Stream of unit -> 'a front
and 'a front = Nil | Cons of 'a * 'a stream


and 키워드는 상호재귀적인 타입을 정의할때 쓴다. 스트림(stream)에는 프론트(front)가 담겨있고 프론트에는 스트림이 담겨있다는걸 알 수 있다.


스트림은 프론트가 지연된거고, 프론트는 스트림이 노출된것이라고 생각하자. 스트림 상태일때는 박스에 커버가 씌워져 있어 내용물을 모르고, 프론트 상태에서는 박스안의 내용물 하나와 또다른 박스가 있다.


인터페이스는 다음과 같으므로 유저 입장에서는 스트림을 노출시키면 프론트가 나온다는것만 안다.


signature STREAM = 
sig
  type 'a stream
  datatype 'a front = Nil | Cons of 'a * 'a stream
  (* delay f는 썽크 f를 스트림으로 만든다. *)
  val delay : (unit -> 'a) -> 'a stream
  
  (* expose S는 S를 강제하여 내제된 프론트를 노출시킨다. *)
  val expose : 'a stream -> 'a front
  (* ... *)
end
structure Stream :> STREAM
struct
  datatype 'a stream = Stream of (unit -> 'a front)
  and 'a front = Nil | Cons of 'a * 'a stream
  fun delay f = Stream f
  fun expose (Stream f) = f ()
end


이제 스트림으로 한번 모든 자연수를 구해보자. 

fun nats (i : int) : int stream = delay (fn () => nats' i)
and nats' (i : int) : int front = Cons (i, nats (i + 1))


nats 는 스트림을 생성하는 역할을, nats’는 프론트를 생성하는 역할을 맡는다. 잠시 시간을 두고 생각해보자. 상호재귀적인 함수를 코딩하는건 직관적이지 않으니까.


또는 한줄로 이렇게 할수도 있다.

fun nats i = delay (fn () => Cons (i, nats (i + 1)))


이번에는 tabulate를 스트림 버전으로 구해보자. 

fun tabulate' f i = delay (fn () => tabulate'' f i)
and fun tabluate'' f i = Cons(f i, tabulate' f (i + 1))
fun tabulate f = tabluate' f 0

아까와 같이 tabulate'는 스트림을, tabulate''는 프론트를 생성하는 역할을 맡는다. 


map을 스트림 버전으로 구해보자. 

(* map : ('a -> 'b) -> 'a stream -> 'b stream *)
fun map f S = delay (fn () => map' f (expose S))
(* map' : ('a -> 'b) -> 'a front -> 'b front *)
and map' f Nil = Nil
  | map' f (Cons(x, S')) = Cons(f x, map f S')

map과 map2중 하나는 최대지연적이다. 한번 잘 생각해보자.

fun map2 f S = 
  (case expose S of
    Nil => delay (fn () => Nil)
  | Cons(x, S') => delay (fn () => Cons (f x, map2 f S')))


답은 map2이다. map2는 썽크에 넣기 전 expose S를 호출하기 때문에 프론트의 원소가 계산이 되는 반면, map은 썽크에 바로 넣어서 모든게 지연된다. 미묘한 차이지만 알아두자.


예외가 나거나 무한루프에 빠지는 스트림을 구분하기위해 단어를 하나 정의하겠다. 생산적인 스트림이란 expose S가 항상 Nil 값이거나 Cons(x, S’) (S’는 생산적)값이 되는 스트림 S를 말한다. 정의에 의해 생산적인 스트림은 expose를 할때 예외나 무한루프에 빠지지 않고 항상 값을 가지게 된다.





4. 소수 구하기

소수가 무한히 많다는걸 우리 모두는 안다. 하지만 정말일까? 스트림을 이용해 모든 소수를 구하는 함수를 만들어보자!


우선 기본적인 보조함수를 작성하자. filter는 여러번 봤으니 뭐하는지 함수인지 감이 잡힐 것이다.

fun dividedBy x y = y mod x = 0
fun filter p S = delay (fn () => filter' p (expose S))
and filter' p Nil = Nil
  | filter' p (Cons (x, S')) = 
      if p x then Cons (x, filter p S))
      else filter p S


이제 핵심 함수를 구현해보자. 모든 소수를 구하기 위해서 먼저 모든 2의 배수를 지우고, 3의 배수를 지우고, 4의 배수를 지우고… 하는 식으로 할것이다. 에라토스테네스의 체라고 하는 방법이다.

fun sieve S = delay (fn () => sieve' (expose S))
and sieve' Nil = raise Fail "this shouln't happen"
  | sieve' (Cons (x, S')) = 
      Cons (x, sieve (filter (not o (dividedBy x)) S'))


sieve는 그냥 스트림을 프론트로 노출해서 sieve’를 호출한다음 다시 스트림으로 만든다.


sieve’는 Cons(x, S’) 이 주어졌을때 x로 나눠지지 않는 모든 수만 프론트에 남긴채 sieve를 다시 호출한다. o는 고차함수를 다룰때 잠깐 봤었는데 합성함수를 만드는 함수이다.


[2, 3, 4, …, ]의 스트림에 저 sieve함수를 호출하면 모든 소수가 담긴 스트림을 만들 수 있다.

val naturalsFrom2 = tabulate (fn x => x + 2)
val primes = sieve naturalsFrom2


이렇게 모든 소수가 담긴 스트림을 만들었다! 만약 소수를 더 구하고 싶을때는 expose primes로 프론트 형식으로 만든 다음 패턴매칭을 통해 다음 소수를 얻을 수 있다. 



궁금하거나 이해 잘 안되는거 있으면 댓글로 물어보면 내가 아는선에서 최대한 답변해줄테니 많이 물어봐라.


다음에는 SML에서 명령형 프로그래밍 하는법을 다뤄보도록 하겠다.


+) 추가로, 지연된 연산은 참조 투명성이란게 언어에서 보장되어야 가능하다. 참조 투명성을 지원하는 언어에선 표현식이 그 값으로 치환되어도 같은 "의미"를 갖는다. 다른 말로 함수를 같은 인자로 몇번이고 호출해도 같은 값을 갖는다. 지연된 연산을 해서 표현식의 계산이 나중으로 미뤄지면 그 값은 표현식을 즉시 계산한것과 같아야 할 것이다. 만약 참조 투명성을 지원하지 않는 언어에서 지연된 연산을 한다면 지연된 연산을 하고 안하고에 따라 코드가 다른 일을 할 수 있다. (참고로 참조 투명성은 분석철학에서 기원된 개념으로, Wilard Quine이란 사람이 창시했다. 이 사람의 이름을 따서, 자기 자신의 소스코드를 출력하는 프로그램을 콰인이라고 부른다.)


8강 : 명령형 프로그래밍

9강(完) : 컴파일러와 프로그램 분석


참고자료 1

참고자료 2

참고자료 3