루프와 재귀
루프와 재귀 (Loops and Recursions)
다른 ocaml.org 문서와 마찬가지로, 여기 코드 예시는 직접 테스트해 볼 수 있는 코드이거나 코드를 어떻게 쓰는지 보여주는 예시예요. CLI 프롬프트 #로 시작하고 ;;로 끝나며 명확한 출력이 있는 코드 조각은 OCaml toplevel(ocaml이나 utop)에서 테스트하거나 OCaml 플레이그라운드에 붙여넣을 수 있어요. 코드가 #로 시작하지 않고 ;;로 끝나지 않는다면, 그것은 코드를 어떻게 쓰는지 보여주는 예시예요.
출처: OCaml 공식 문서
본문
for 루프와 while 루프 (For Loops and While Loops)
OCaml은 친숙한 for 루프의 상당히 제한된 형태를 지원해요.
for variable = start_value to end_value do
expression
done
for variable = start_value downto end_value do
expression
done
LablGtk에서 가져온 간단하지만 실제 예시예요.
for i = 1 to n_jobs () do
do_next_job ()
done
OCaml에서 for 루프는 아래처럼 쓰는 것의 약어일 뿐이에요.
let i = 1 in
do_next_job ();
let i = 2 in
do_next_job ();
let i = 3 in
do_next_job ();
...
let i = n_jobs () in
do_next_job ();
()
OCaml은 for 루프에서 일찍 빠져나오는 개념을 지원하지 않아요. 즉 break, continue, last 문이 없어요. (예외를 던지고 밖에서 잡을 수도 있는데, 빠르게 동작하지만 종종 어색해 보여요.)
OCaml for 루프 안의 표현식은 unit으로 평가되어야 하고(그렇지 않으면 경고가 나와요), for 루프 표현식 전체는 unit을 반환해요.
# for i = 1 to 10 do i done;;
Line 1, characters 20-21:
Warning 10 [non-unit-statement]: this expression should have type unit.
- : unit = ()
함수형 프로그래머는 명시적 루프보다 재귀를 쓰는 경향이 있어요. 그리고 for 루프는 아무것도 반환할 수 없으므로 의심스럽게 보는 게 현명해요. 그래서 OCaml의 for 루프가 상대적으로 힘이 없는 거죠. 재귀는 아래에서 다룰게요.
OCaml의 while 루프는 이렇게 써요.
while boolean-condition do
expression
done
for 루프와 마찬가지로 언어는 예외를 던지는 경우를 제외하고는 while 루프에서 빠져나오는 방법을 제공하지 않아요. 그래서 while 루프의 용도는 상당히 제한적이에요. 다시 강조하지만, 함수형 프로그래머는 재귀를 좋아하므로 OCaml에서 while 루프는 2등 시민이에요.
while 루프를 잠시 생각해 보면, 우리의 오랜 친구 reference와 함께 쓸 때를 제외하면 실제로는 거의 쓸모가 없다는 걸 알 수 있어요. 잠시 OCaml에 reference가 없다고 상상해 보죠.
let quit_loop = false in
while not quit_loop do
print_string "Have you had enough yet? (y/n) ";
let str = read_line () in
if str.[0] = 'y' then
(* how do I set quit_loop to true ?!? *)
done
quit_loop는 진짜 "변수"가 아니라는 것을 기억하세요. let 바인딩은 그냥 quit_loop를 false의 약어로 만들어 줄 뿐이에요. 이것은 while 루프 조건이 항상 true여서 루프가 영원히 돈다는 뜻이에요!
다행히 OCaml에는 reference가 있으므로, 원한다면 위 코드를 이렇게 쓸 수 있어요. !(느낌표)가 C/Java에서처럼 "부정"을 뜻한다고 혼동하지 마세요. 여기서는 "포인터 역참조"를 뜻하며, 사실 Forth와 비슷해요. !를 "get"이나 "deref"로 읽는 게 더 낫습니다.
let quit_loop = ref false in
while not !quit_loop do
print_string "Have you had enough yet? (y/n) ";
let str = read_line () in
if str.[0] = 'y' then quit_loop := true
done;;
리스트 반복 (Looping Over Lists)
리스트를 반복하고 싶다면 명령형 프로그래머처럼 믿음직한 리볼버인 Mr. For Loop에 손을 대지 마세요! OCaml에는 리스트를 반복하는 더 좋고 더 빠른 방법들이 있고, 그것들은 모두 List 모듈에 있어요. 사실 List에는 수십 개의 좋은 함수가 있지만, 이 장에서는 가장 유용한 것들만 다룰게요.
먼저 사용할 리스트를 정의해 볼게요.
# let my_list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10];;
val my_list : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
리스트의 모든 요소에 함수를 한 번씩 호출하고 싶다면 List.iter를 사용해요.
# let f elem =
Printf.printf "I'm looking at element %d now\n" elem
in
List.iter f my_list;;
I'm looking at element 1 now
I'm looking at element 2 now
I'm looking at element 3 now
I'm looking at element 4 now
I'm looking at element 5 now
I'm looking at element 6 now
I'm looking at element 7 now
I'm looking at element 8 now
I'm looking at element 9 now
I'm looking at element 10 now
- : unit = ()
사실 뇌가 for 루프를 쓰라고 신호를 보낼 때마다 가장 먼저 생각해 볼 것이 List.iter예요.
리스트의 각 요소를 변환하고 싶다면 — 예를 들어 각 요소를 두 배로 늘리는 경우 — List.map을 사용해요.
# List.map (( * ) 2) my_list;;
- : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
List.filter 함수는 리스트에서 어떤 조건을 만족하는 요소들만 모아요. 예를 들어 리스트의 모든 짝수를 반환하는 경우예요.
# let is_even i =
i mod 2 = 0
in
List.filter is_even my_list;;
- : int list = [2; 4; 6; 8; 10]
리스트에 어떤 요소가 있는지 확인하려면 List.mem(member의 줄임말)을 사용해요.
# List.mem 12 my_list;;
- : bool = false
List.for_all와 List.exists는 명제 논리의 "forall"과 "exist" 연산자와 같아요.
두 리스트에 동시에 연산을 하려면 이 함수들 중 일부의 "-2" 변형이 있어요. 바로 iter2, map2, for_all2, exists2예요.
map과 filter 함수는 리스트의 각 요소에 개별적으로 동작하는 반면, Fold는 더 특이한 연산이에요. "리스트의 각 요소 사이에 연산자를 삽입하는 것"이라고 생각하는 게 가장 좋아요. 리스트의 모든 숫자를 더하고 싶다고 가정해 보죠. 대충 말하면 리스트의 요소들 사이에 더하기(+) 기호를 삽입하고 싶은 거예요.
# 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10;;
- : int = 55
fold 연산이 바로 이것을 해요. 다만 정확한 세부 사항은 조금 더 까다로워요. 우선 빈 리스트를 더하려 하면 에러 대신 답이 0이면 좋겠어요. 하지만 리스트의 곱을 구하려고 하면 답이 1인 게 더 나아요. fold에는 어떤 종류의 "기본값" 인자를 제공하는 게 필요해요. 두 번째 문제는 +와 * 같은 단순 연산자에서는 생기지 않아요. 사용하는 연산자가 결합적이지 않으면, 즉 (a op b) op c가 a op (b op c)와 같지 않으면 어떻게 될까요? 그런 경우 리스트의 왼쪽 끝에서 시작해 오른쪽으로 가는지, 오른쪽에서 시작해 왼쪽으로 가는지가 중요해져요. 그런 이유로 fold에는 List.fold_left(왼쪽에서 오른쪽으로 동작)와 List.fold_right(오른쪽에서 왼쪽으로 동작하고, 덜 효율적) 두 버전이 있어요.
List.fold_left로 정수 리스트의 sum과 product 함수를 정의해 볼게요.
# let sum = List.fold_left ( + ) 0;;
val sum : int list -> int = <fun>
# let product = List.fold_left ( * ) 1;;
val product : int list -> int = <fun>
# sum my_list;;
- : int = 55
# product my_list;;
- : int = 3628800
쉽죠! 우연히 수학적 팩토리얼을 하는 방법을 찾아냈네요.
# let fact n = product (range 1 n);;
val fact : int -> int = <fun>
# fact 10;;
- : int = 3628800
(이 팩토리얼 함수는 정수를 오버플로해서 아주 작은 n 값에서도 틀린 답을 주기 때문에 그렇게 유용하지 않다는 점을 주의하세요.)
문자열 반복 (Looping Over Strings)
String 모듈에도 문자열 관련 유용한 함수가 수십 개 있어요. 그중 일부는 문자열을 반복하는 것과 관련돼요.
String.copy는 strdup처럼 문자열을 복사해요. List.iter처럼 동작하지만 문자열의 문자들에 대해 동작하는 String.iter 함수도 있어요.
재귀 (Recursion)
이제 어려운 주제로 왔네요: 재귀예요. 함수형 프로그래머는 재귀 함수 사랑으로 정의된다고 할 수 있어요. 그리고 여러 면에서 함수형 프로그래밍의 재귀 함수는 명령형 프로그래밍의 루프에 해당해요. 함수형 언어에서 루프는 2등 시민인 반면, 재귀 함수는 최고의 지원을 받아요.
재귀 함수를 작성하는 것은 for 루프와 while 루프를 작성하는 것과는 사고방식의 전환이 필요해요. 그래서 이 절은 소개와 몇 가지 예시 정도로만 할게요.
첫 번째 예시에서 파일 전체를 메모리로(긴 문자열로) 읽어볼게요. 본질적으로 세 가지 가능한 접근법이 있어요.
접근법 1 (Approach 1)
파일의 길이를 얻어 really_input 메서드로 한 번에 모두 읽어요. 가장 간단하지만 실제 파일이 아닌 채널(예: 키보드 입력 읽기)에서는 동작하지 않을 수 있어요. 그래서 다른 두 접근법이 있는 거죠.
접근법 2 (Approach 2)
명령형 접근법은 예외로 빠져나오는 while 루프를 사용해요.
접근법 3 (Approach 3)
재귀 루프가 다시 예외로 재귀에서 빠져나와요.
여기서 몇 가지 새 개념을 소개할게요. 두 번째, 세 번째 접근법에서는 확장 가능한 버퍼인 Buffer 모듈을 사용할 거예요. 끝에 텍스트를 효율적으로 덧붙일 수 있는 문자열이라고 생각하면 돼요. 또한 입력 함수들이 입력의 끝에 도달하면 던지는 End_of_file 예외를 잡을 거예요. 마지막으로 첫 번째 명령줄 매개변수를 얻기 위해 Sys.argv.(1)을 사용할 거예요.
(* Read whole file: Approach 1 *)
open Printf
let read_whole_chan chan =
let len = in_channel_length chan in
let result = (Bytes.create len) in
really_input chan result 0 len;
(Bytes.to_string result)
let read_whole_file filename =
let chan = open_in filename in
read_whole_chan chan
let main () =
let filename = Sys.argv.(1) in
let str = read_whole_file filename in
printf "I read %d characters from %s\n" (String.length str) filename
접근법 1은 동작하지만 완전히 만족스럽진 않아요. read_whole_chan이 키보드 입력이나 소켓 같은 비파일 채널에서 동작하지 않기 때문이에요. 접근법 2는 while 루프를 포함해요.
(* Read whole file: Approach 2 *)
open Printf
let read_whole_chan chan =
let buf = Buffer.create 4096 in
try
while true do
let line = input_line chan in
Buffer.add_string buf line;
Buffer.add_char buf '\n'
done;
assert false (* This is never executed
(always raises Assert_failure). *)
with
End_of_file -> Buffer.contents buf
let read_whole_file filename =
let chan = open_in filename in
read_whole_chan chan
let main () =
let filename = Sys.argv.(1) in
let str = read_whole_file filename in
printf "I read %d characters from %s\n" (String.length str) filename
접근법 2의 핵심은 중심 while 루프를 보는 거예요. 기억하세요. while 루프에서 일찍 빠져나오는 유일한 방법은 예외예요. 그리고 그것이 바로 여기서 하고 있는 일이에요. 아직 예외를 다루지 않았지만, 위 코드에서 input_line이 파일의 끝에 도달할 때 던지는 End_of_file 예외를 이해하는 데는 별 문제가 없을 거예요. 버퍼 buf가 파일 내용을 쌓아 두고, 파일 끝에 도달하면 그걸 반환해요(Buffer.contents buf).
한 가지 흥미로운 점은 while 루프 바로 뒤의 겉보기에 불필요해 보이는 문(assert false)이에요. 이것은 무엇을 위한 걸까요? while 루프는 for 루프처럼 그냥 표현식이고 unit 객체(())를 반환한다는 것을 기억하세요. 하지만 OCaml은 try 안의 반환 타입이 잡히는 각 예외의 반환 타입과 일치하기를 요구해요. 이 경우 End_of_file이 string을 결과로 내므로, try의 본문도 string을 "반환"해야 해요. (무한 while 루프 때문에 그 문자열이 실제로 반환될 수는 없지만요.) assert false는 다형적 타입을 가지므로 with 분기가 반환하는 어떤 값과도 통일될 수 있어요.
재귀 버전이에요. 접근법 2보다 짧지만 (적어도 명령형 프로그래머에게는) 이해하기가 그렇게 쉽지 않다는 걸 주목하세요.
(* Read whole file: Approach 3 *)
open Printf
let read_whole_chan chan =
let buf = Buffer.create 4096 in
let rec loop () =
let line = input_line chan in
Buffer.add_string buf line;
Buffer.add_char buf '\n';
loop ()
in
try loop () with
End_of_file -> Buffer.contents buf
let read_whole_file filename =
let chan = open_in filename in
read_whole_chan chan
let main () =
let filename = Sys.argv.(1) in
let str = read_whole_file filename in
printf "I read %d characters from %s\n" (String.length str) filename
다시 무한 루프가 있지만, 이 경우에는 재귀로 이루어져요. loop는 함수 끝에서 자기 자신을 호출해요. input_line이 End_of_file 예외를 던지면 무한 재귀가 깨져요.
특히 큰 파일을 주면 접근법 3이 스택을 오버플로할 것처럼 보일 수 있지만, 그렇지 않아요! 꼬리 재귀(아래에서 다룸) 덕분에 컴파일러가 재귀 loop 함수를 진짜 while 루프(!)로 바꿔서 항상 일정한 스택 공간에서 실행돼요.
다음 예시에서는 재귀가 특정 종류의 자료구조, 특히 트리를 만들거나 조사하는 데 얼마나 훌륭한지 보여줄게요. 파일시스템의 파일을 나타내는 재귀 타입을 만들어 볼게요.
# type filesystem = File of string | Directory of filesystem list;;
type filesystem = File of string | Directory of filesystem list
opendir와 readdir 함수는 디렉터리를 열고 디렉터리에서 요소를 읽는 데 사용돼요. readdir가 디렉터리의 끝에 도달하면 던지는 성가신 End_of_file 예외를 숨기는 편리한 readdir_no_ex 함수를 정의할게요.
# #load "unix.cma";;
# open Unix;;
# let readdir_no_ex dirh =
try
Some (readdir dirh)
with
End_of_file -> None;;
val readdir_no_ex : dir_handle -> string option = <fun>
readdir_no_ex의 타입은 이렇게 돼요. 아까 null 포인터에 대해 한 논의를 기억해 보세요.
# readdir_no_ex;;
- : dir_handle -> string option = <fun>
또한 filesystem 타입을 (예를 들어) 출력하기 위해 문자열로 변환하는 데 쓸 수 있는 간단한 재귀 함수를 정의할게요.
# let rec string_of_filesystem fs =
match fs with
| File filename -> filename ^ "\n"
| Directory fs_list ->
List.fold_left (^) "" (List.map string_of_filesystem fs_list);;
val string_of_filesystem : filesystem -> string = <fun>
fold_left와 map의 사용을 주목하세요. map은 리스트의 각 filesystem을 (재귀적으로) string으로 변환하는 데 사용돼요. 그런 다음 fold_left (^) ""가 리스트를 하나의 큰 문자열로 이어 붙여요. 패턴 매칭의 사용도 주목하세요. (라이브러리는 본질적으로 fold_left (^)와 동등하지만 더 효율적으로 구현된 String.concat이라는 함수를 정의해요.)
이제 디렉터리 구조를 재귀적으로 읽어 재귀 filesystem 자료구조를 반환하는 함수를 정의해 볼게요. 이 함수를 단계별로 보여주고, 이 절의 끝에서 전체 함수를 출력할게요. 먼저 함수의 개요예요.
let rec read_directory path =
let dirh = opendir path in
let rec loop () =
(* ..... *) in
Directory (loop ())
opendir 호출은 주어진 경로를 열고 dir_handle을 반환하며, 나중에 readdir_no_ex로 그 핸들에서 이름을 읽을 수 있어요. 함수의 반환 값은 Directory fs_list가 될 거예요. 그래서 함수를 완성하려면 filesystem의 리스트를 반환하는 함수 loop만 작성하면 돼요. loop의 타입은 다음과 같아요.
loop : unit -> filesystem list
loop를 어떻게 정의할까요? 다시 단계별로 볼게요.
let rec loop () =
let filename = readdir_no_ex dirh in
(* ..... *)
먼저 디렉터리 핸들에서 다음 파일 이름을 읽어요. filename은 타입이 string option이에요. 즉 None이거나 Some "foo"일 수 있는데, foo는 디렉터리의 다음 파일 이름이에요. 또한 "."과 ".." 파일(즉 현재 디렉터리와 부모 디렉터리)을 무시해야 해요. 이 모든 것을 멋진 패턴 매칭으로 처리할 수 있어요.
let rec loop () =
let filename = readdir_no_ex dirh in
match filename with
| None -> []
| Some "." -> loop ()
| Some ".." -> loop ()
| Some filename ->
(* ..... *)
None 경우는 쉽네요. (재귀적으로!) 생각해 보면 loop가 호출되었는데 디렉터리의 끝에 도달했다면, loop는 항목들의 리스트를 반환해야 해요. 항목이 없으므로 빈 리스트([])를 반환해요.
"."과 ".."의 경우에는 파일을 무시하고 loop를 다시 호출하면 돼요.
loop가 실제 파일 이름을 읽으면(아래의 Some filename 매치) 무엇을 할까요? pathname을 파일의 전체 경로라고 하죠. 파일을 'stat'해서 정말 디렉터리인지 확인해요. 만약 디렉터리라면 read_directory를 재귀 호출해서 Directory something을 반환하는 this를 설정해요. read_directory의 전체 결과가 Directory (loop ())라는 점을 주목하세요. 파일이 정말 파일(디렉터리가 아님)이라면 this를 File pathname으로 두죠. 다음으로 영리한 일을 해요: this :: loop ()를 반환해요. 이것은 남은 디렉터리 구성원(리스트)을 계산하기 위한 loop ()의 재귀 호출이고, 그 앞에 this를 붙여요.
# let rec read_directory path =
let dirh = opendir path in
let rec loop () =
let filename = readdir_no_ex dirh in
match filename with
| None -> []
| Some "." -> loop ()
| Some ".." -> loop ()
| Some filename ->
let pathname = path ^ "/" ^ filename in
let stat = lstat pathname in
let this =
if stat.st_kind = S_DIR then
read_directory pathname
else
File pathname
in
this :: loop ()
in
Directory (loop ());;
val read_directory : string -> filesystem = <fun>
꽤 복잡한 재귀이지만, 이건 만들어낸 예시임에도 실제 함수형 프로그램에서 발견되는 복잡한 재귀 패턴과 상당히 흡사해요. 여기서 얻을 수 있는 두 가지 중요한 교훈은 다음과 같아요.
리스트를 만드는 데 재귀를 사용하기:
let rec loop () =
match data with (* Could also be an if statement *)
| base case -> []
| recursive case -> element :: loop ()
이것을 앞의 range 함수와 비교해 보세요. 재귀 패턴이 정확히 같아요.
let rec range a b =
if a > b then [] (* Base case *)
else a :: range (a + 1) b (* Recursive case *)
트리를 만드는 데 재귀를 사용하기:
let rec read_directory path =
(* blah blah *)
if file_is_a_directory path then
read_directory path_to_file
else
Leaf file
이것을 동작하는 프로그램으로 만드는 데 남은 것은 read_directory를 호출하고 결과를 표시하는 약간의 코드예요.
let path = Sys.argv.(1) in
let fs = read_directory path in
print_endline (string_of_filesystem fs)
재귀 예시: 리스트의 최대 요소 (Recursion Example: Maximum Element in a List)
리스트에 대한 기본 재귀 패턴을 기억하세요.
let rec loop () =
a match or if statement
| base case -> []
| recursive case -> element :: loop ()
여기서 핵심은 실제로 match / base case / recursive case 패턴의 사용이에요. 이 예시(리스트에서 최대 요소 찾기)에서는 기본 case가 두 개, 재귀 case가 하나 있을 거예요. 하지만 코드로 건너뛰기 전에 잠시 물러나서 문제를 생각해 보죠. 문제를 생각하면 해결책이 마법처럼 나타날 거예요. (진짜예요!)
우선 리스트의 최대 요소는 그냥 가장 큰 것이라는 걸 분명히 하자면, 예를 들어 리스트 [1; 2; 3; 4; 1]의 최대 요소는 4예요.
물론 예외가 있어요. 빈 리스트 []에는 최대 요소가 없어요. 빈 리스트를 전달받으면 에러를 던질 거예요.
[4] 같은 단일 요소 리스트의 최대 요소는 무엇일까요? 쉬워요! 그냥 요소 자신이에요. 그래서 list_max [4]는 4를 반환해야 하고, 일반적인 경우 list_max [x]는 x를 반환해야 해요.
일반적인 리스트 x :: remainder의 최대 요소는 무엇일까요? (이것은 리스트의 "cons" 표기이고, remainder는 꼬리 — 역시 리스트예요.)
잠시 생각해 보세요. remainder의 최대 요소가, 예를 들어 y라고 알고 있다고 가정해 보죠. x :: remainder의 최대 요소는 무엇일까요? x > y인지 x <= y인지에 달려 있어요. x가 y보다 크면 전체 최대는 x이고, 반대로 x가 y보다 작으면 전체 최대는 y예요.
이게 정말 동작할까요?
[1; 2; 3; 4; 1]을 다시 생각해 보죠. 이것은 1 :: [2; 3; 4; 1]이에요. 이제 나머지 [2; 3; 4; 1]의 최대 요소는 4예요. 그래서 우리가 관심 있는 건 x = 1과 y = 4예요. 머리 요소 x = 1은 y = 4가 더 크므로 중요하지 않아요. 전체 리스트의 최대는 y = 4예요.
이제 위의 규칙들을 코드로 만들어 동작하는 함수를 얻어 볼게요.
# let rec list_max xs =
match xs with
| [] -> (* empty list: fail *)
failwith "list_max called on empty list"
| [x] -> (* single element list: return the element *)
x
| x :: remainder -> (* multiple element list: recursive case *)
max x (list_max remainder);;
val list_max : 'a list -> 'a = <fun>
우리가 정한 규칙/특수 case들이 실제로 코드 줄과 어떻게 대응하는지 보이도록 주석을 달았어요.
동작할까요?
# list_max [1; 2; 3; 4; 1];;
- : int = 4
# list_max [];;
Exception: Failure "list_max called on empty list".
# list_max [5; 4; 3; 2; 1];;
- : int = 5
# list_max [5; 4; 3; 2; 1; 100];;
- : int = 100
제안된 해결책이 (a) 명령형 for-루프 해결책과 아주 다르고, (b) 문제 명세와 훨씬 더 밀접하게 연결되어 있다는 점을 주목하세요. 함수형 프로그래머들은 함수형 스타일이 명령형 스타일보다 훨씬 높은 수준이므로 더 좋고 더 쉽다고 말할 거예요. 그 말을 믿을지는 당신에게 달려 있어요. 함수형 버전이 논리적으로 추론하기 훨씬 단순하다는 것은 확실해요. list_max가 올바르다는 것을 형식적으로 증명하고 싶다면 유용하죠. ("올바르다"는 프로그램이 증명 가능하게 버그가 없다는 뜻이고, 우주 왕복선, 원자력 발전소, 그리고 전반적으로 더 높은 품질의 소프트웨어에 유용해요.)
꼬리 재귀 (Tail Recursion)
range 함수를 또다시 살펴볼게요.
# let rec range a b =
if a > b then []
else a :: range (a+1) b;;
val range : int -> int -> int list = <fun>
프로그램의 구조를 더 명확하게 하기 위해 약간 다시 쓸게요. (그래도 같은 함수예요.)
# let rec range a b =
if a > b then [] else
let result = range (a+1) b in
a :: result;;
val range : int -> int -> int list = <fun>
호출해 볼게요.
# List.length (range 1 10);;
- : int = 10
# List.length (range 1 1000000);;
Stack overflow during evaluation (looping recursion?).
흠 ... 언뜻 보면 재귀 프로그래밍, 나아가 함수형 프로그래밍 전체의 문제처럼 보여요! 코드를 반복적으로가 아니라 재귀적으로 쓰면 큰 입력에서 필연적으로 스택 공간이 고갈되잖아요, 그렇죠?
사실 틀렸어요. 컴파일러는 특정 종류의 재귀 함수에 간단한 최적화를 수행해 while 루프로 바꿀 수 있어요. 이 특정 종류의 재귀 함수는 따라서 항상 일정한 스택 공간에서 실행되고, 명령형 while 루프와 동등한 효율을 가져요. 이런 함수를 꼬리 재귀 함수(tail-recursive functions)라고 불러요.
꼬리 재귀 함수에서는 재귀 호출이 맨 끝에서 일어나요. 위의 loop () 함수들을 기억하세요? 그것들은 모두 다음과 같은 형태였어요.
let rec loop () =
(* do something *)
loop ()
loop ()에 대한 재귀 호출이 마지막에 일어나기 때문에 loop는 꼬리 재귀적이고, 컴파일러는 전체를 while 루프로 바꿔요.
아쉽게도 range는 꼬리 재귀적이지 않아요. 위의 더 긴 버전이 그 이유를 보여줘요. range에 대한 재귀 호출이 아주 마지막 일로 일어나지 않아요. 사실 마지막 일은 ::(cons) 연산이에요. 결과적으로 컴파일러는 재귀를 while 루프로 바꾸지 않고, 함수는 스택 공간 사용에 비효율적이에요.
누적 인자 또는 accumulator를 사용하면 위의 range 같은 함수를 꼬리 재귀적인 방식으로 작성할 수 있어요. 그러면 효율적이고 큰 입력에서도 제대로 동작해요. "지금까지의 결과"를 저장할 누적 인자를 사용해 다시 작성한 range 함수를 계획해 볼게요.
let rec range2 a b accum =
(* ... *)
let range a b =
range2 a b []
accum 인자는 결과를 누적할 거예요. "지금까지의 결과"인 거죠. 빈 리스트("지금까지 결과 없음")를 전달해요. 쉬운 case는 a > b일 때예요.
let rec range2 a b accum =
if a > b then accum
else
(* ... *)
a > b이면(즉 재귀의 끝에 도달했으면) 멈추고 결과(accum)를 반환해요.
이제 요령은 else 절을 작성하고 range2에 대한 호출이 우리가 하는 아주 마지막 일이도록 만드는 거예요. 그래야 함수가 꼬리 재귀적이 되죠.
# let rec range2 a b accum =
if a > b then accum
else range2 (a + 1) b (a :: accum);;
val range2 : int -> int -> int list -> int list = <fun>
이 함수에는 작은 문제가 하나 있어요. 리스트를 거꾸로 만든다는 거예요! 하지만 range를 이렇게 다시 정의하면 쉽게 고칠 수 있어요.
# let range a b = List.rev (range2 a b []);;
val range : int -> int -> int list = <fun>
이번엔 동작해요. 다만 백만 개 요소가 든 리스트를 정말 만들어야 하기 때문에 실행이 조금 느려요.
# List.length (range 1 1000000);;
- : int = 1000000
다음 구현은 리스트를 뒤집을 필요가 없기 때문에 이전 것보다 두 배 빠르게 동작해요.
# let rec range2 a b accum =
if b < a then accum
else range2 a (b - 1) (b :: accum);;
val range2 : int -> int -> int list -> int list = <fun>
# let range a b =
range2 a b [];;
val range : int -> int -> int list = <fun>
이상 꼬리 재귀에 대한 간략한 개요였어요. 하지만 실전 상황에서 함수가 꼬리 재귀적인지 판단하는 것은 꽤 어려울 수 있어요.
여기서 정말 배운 건 무엇일까요?
한 가지는 재귀 함수가 경험이 부족한 프로그래머에게 위험한 함정이라는 거예요. 함수가 작은 입력에서는(테스트 중에) 동작하는 것처럼 보일 수 있지만, 큰 입력에 노출되는 실제 상황에서는 치명적으로 실패할 수 있어요. 이것은 재귀 함수를 쓰지 말라는 논거 하나예요. 가능하면 명시적 while 루프를 대신 사용하세요.
가변 record, reference(다시!), 그리고 배열 (Mutable Records, References (Again!) and Arrays)
앞에서 record를 지나가며 언급했어요. record는 C의 struct와 비슷해요.
# type pair_of_ints = {a : int; b : int};;
type pair_of_ints = { a : int; b : int; }
# {a = 3; b = 5};;
- : pair_of_ints = {a = 3; b = 5}
# {a = 3};;
Line 1, characters 1-8:
Error: Some record fields are undefined: b
또 다른 흥미로운 기능으로 넘어가 볼게요. OCaml record는 가변 필드를 가질 수 있어요. 보통 {a = 3; b = 5} 같은 표현식은 불변이고 상수인 객체예요. 하지만 record에 가변 필드가 있다면, record 안의 그 필드를 바꾸는 방법이 있어요. 이것은 OCaml의 명령형 기능이에요. 함수형 언어는 보통 가변 객체(또는 곧 살펴볼 reference나 가변 배열)를 허용하지 않으니까요.
아래는 객체가 접근된 횟수를 세는 데 사용되는 가변 필드로 정의된 객체예요. 캐싱 스킴에서 어떤 객체를 메모리에서 쫓아낼지 결정하는 데 쓰일 수 있다고 상상해 볼 수 있어요.
# type name = {name : string; mutable access_count : int};;
type name = { name : string; mutable access_count : int; }
name 필드를 출력하고 가변 access_count 필드를 증가시키는 이름에 대한 함수예요.
# let print_name name =
print_endline ("The name is " ^ name.name);
name.access_count <- name.access_count + 1;;
val print_name : name -> unit = <fun>
print_name의 이상하고(그리고 매우 비함수적인) 특징을 주목하세요. 그것은 자신의 access_count 매개변수를 수정해요. 이 함수는 "순수"하지 않아요. OCaml은 함수형 언어이지만, 함수형 프로그래밍을 억지로 강요할 정도는 아니에요.
어쨌든 print_name이 동작하는 걸 볼게요.
# let n = {name = "Richard Jones"; access_count = 0};;
val n : name = {name = "Richard Jones"; access_count = 0}
# n;;
- : name = {name = "Richard Jones"; access_count = 0}
# print_name n;;
The name is Richard Jones
- : unit = ()
# n;;
- : name = {name = "Richard Jones"; access_count = 1}
# print_name n;;
The name is Richard Jones
- : unit = ()
# n;;
- : name = {name = "Richard Jones"; access_count = 2}
명시적으로 mutable로 표시된 필드만 <- 연산자로 대입할 수 있어요. 가변이 아닌 필드에 대입하려고 하면 OCaml이 허용하지 않아요.
# n.name <- "John Smith";;
Line 1, characters 1-23:
Error: The record field name is not mutable
이제쯤 익숙할 reference는 가변 contents 필드를 가진 record로 구현돼요. Stdlib의 정의를 확인해 보세요.
type 'a ref = {mutable contents : 'a}
그리고 OCaml toplevel이 reference의 값으로 무엇을 출력하는지 자세히 보세요.
# let r = ref 100;;
val r : int Stdlib.ref = {Stdlib.contents = 100}
배열은 OCaml이 제공하는 또 다른 종류의 가변 구조예요. OCaml에서 일반 리스트는 연결 리스트로 구현되고, 연결 리스트는 어떤 종류의 연산에 대해 느려요. 예를 들어 리스트의 머리를 얻거나, 각 요소에 어떤 연산을 수행하기 위해 리스트를 반복하는 것은 꽤 빠르지만, 리스트의 n번째 요소로 점프하거나 리스트에 무작위로 접근하려고 하면 둘 다 느린 연산이라는 걸 알게 돼요. OCaml의 Array 타입은 진짜 배열이라 무작위 접근이 빠르지만, 요소의 삽입과 삭제는 느려요. Array는 가변이기도 해서 요소를 무작위로 바꿀 수도 있어요.
배열의 기본은 간단해요.
# let a = Array.create 10 0;;
Line 1, characters 9-21:
Alert deprecated: Stdlib.Array.create
Use Array.make/ArrayLabels.make instead.
val a : int array = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]
# for i = 0 to Array.length a - 1 do
a.(i) <- i
done;;
- : unit = ()
# a;;
- : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]
배열을 쓰는 문법을 주목하세요: [| element; element; ... |]
OCaml 컴파일러는 무거운 수치 처리를 염두에 두고 설계됐어요. (전통적으로 FORTRAN이 쓰이던 그런 종류요.) 그래서 숫자 배열, 벡터, 행렬을 위한 다양한 최적화를 포함해요. 다음은 조밀 행렬 곱셈을 하는 벤치마크 코드예요. for-루프를 사용하고 전반적으로 스타일이 매우 명령형이라는 점을 주목하세요.
# let size = 30;;
val size : int = 30
# let mkmatrix rows cols =
let count = ref 1
and last_col = cols - 1
and m = Array.make_matrix rows cols 0 in
for i = 0 to rows - 1 do
let mi = m.(i) in
for j = 0 to last_col do
mi.(j) <- !count;
incr count
done;
done;
m;;
val mkmatrix : int -> int -> int array array = <fun>
# let rec inner_loop k v m1i m2 j =
if k < 0 then v
else inner_loop (k - 1) (v + m1i.(k) * m2.(k).(j)) m1i m2 j;;
val inner_loop : int -> int -> int array -> int array array -> int -> int =
<fun>
# let mmult rows cols m1 m2 m3 =
let last_col = cols - 1
and last_row = rows - 1 in
for i = 0 to last_row do
let m1i = m1.(i) and m3i = m3.(i) in
for j = 0 to last_col do
m3i.(j) <- inner_loop last_row 0 m1i m2 j
done;
done;;
val mmult :
int -> int -> int array array -> int array array -> int array array -> unit =
<fun>
# let () =
let n =
try int_of_string Sys.argv.(1)
with Invalid_argument _ -> 1
and m1 = mkmatrix size size
and m2 = mkmatrix size size
and m3 = Array.make_matrix size size 0 in
for i = 1 to n - 1 do
mmult size size m1 m2 m3
done;
mmult size size m1 m2 m3;
Printf.printf "%d %d %d %d\n" m3.(0).(0) m3.(2).(3) m3.(3).(2) m3.(4).(4);;
Exception: Failure "int_of_string".
상호 재귀 함수 (Mutually Recursive Functions)
서로를 호출하는 두 함수를 정의하고 싶다고 가정해 보죠. 사실 아주 흔한 일은 아니지만, 때로는 유용할 수 있어요. 여기 인위적인 예시가 있어요(Ryan Tarpine에게 감사). 숫자 0은 짝수예요. 0보다 큰 다른 숫자는 그 전임자가 홀수이면 짝수예요. 따라서:
# let rec even n =
match n with
| 0 -> true
| x -> odd (x - 1);;
Line 4, characters 10-13:
Error: Unbound value odd
위 코드는 컴파일되지 않아요. 아직 함수 odd를 정의하지 않았기 때문이에요! 하지만 그건 쉬워요. 0은 홀수가 아니고, 0보다 큰 다른 숫자는 그 전임자가 짝수이면 홀수예요. 그래서 완성하려면 그 함수도 필요해요.
# let rec even n =
match n with
| 0 -> true
| x -> odd (x - 1);;
Line 4, characters 10-13:
Error: Unbound value odd
# let rec odd n =
match n with
| 0 -> false
| x -> even (x - 1);;
Line 4, characters 10-14:
Error: Unbound value even
유일한 문제는... 이 프로그램이 컴파일되지 않는다는 거예요. even 함수를 컴파일하려면 이미 odd의 정의가 필요하고, odd를 컴파일하려면 even의 정의가 필요해요. 그래서 두 정의를 서로 바꿔도 도움이 안 돼요.
OCaml에는 (C에서 파생된 언어들처럼) "순방향 프로토타입"이 없지만, odd와 even 같은 두 개 이상의 상호 재귀 함수 집합을 정의하는 특수 문법이 있어요.
# let rec even n =
match n with
| 0 -> true
| x -> odd (x - 1)
and odd n =
match n with
| 0 -> false
| x -> even (x - 1);;
val even : int -> bool = <fun>
val odd : int -> bool = <fun>
상호 재귀 클래스 정의와 모듈을 작성할 때도 비슷한 문법을 사용할 수 있어요.