LISP으로 함수형 프로그래밍 맛보기

4.1 ~ 4.5

 

4.1 유틸리티는 어떻게 생겨났을까

 

상향식 프로그래밍을 한다는건 누군가 만들어놓은(역자주:내가 만들었을 수도 있고, 남이 만든걸 가져온 것일 수도 있는) 리습을 앞으로 어떻게 쓸지 생각하는 것과 같습니다. (역자주:어떤 리습 구현체를 받아서 씁니다. 거기에 라이브러리나 우리가 만든 코드를 추가하면 새로운 리습이 됩니다. 또 그걸 어떻게 써먹으면 좋을지 생각하고 또 새로운 코드를 추가해서 새로운 리습을 만듭니다. 그렇게 확장하는걸 상향식 프로그래밍이라고 말하고 있습니다.)우리가 리습으로 프로그램을 만들면, 그와 동시에 우리가 만들 프로그램을 좀더 쉽게 만들기위해 새로운 연산자를 리습에 추가하게 됩니다. 이런 새로 추가된 연산자들이 유틸리티입니다.

유틸리티라는 단어에 대한 정확한 정의는 없습니다. 어떤 코드가 너무 작아서 하나의 프로그램이 될 수 없거나, 너무 범용적이라서 어떤 프로그램의 일부분이라고 말할 수 없을 때 유틸리티라고 부릅니다. 데이터베이스 프로그램은 유틸리티가 될 수 없습니다. 하지만 리스트를 가지고 하나의 연산을 하는 함수 하나는 유틸리티라고 부를 수 있습니다. 대부분의 유틸리티는 리습에 포함된 함수나 매크로와 같아 보입니다. 많은 커먼 리습의 내장 연산자들도 사실 처음에는 유틸리티로 만들어졌었습니다. 리스트에서 특정 조건을 만족하는 항목들만 뽑아내는 remove-if-not함수도 커먼 리습에 포함되기 한참 전에는 일반 프로그래머들이 만든 함수였습니다.

유틸리티 만들기를 배운다는 것은 어떤 방법을 배운다기 보다는 만드는 습관을 배우는 것이라고 하는게 더 좋은 설명이 될것 같습니다. 상향식 프로그래밍은 프로그램을 만드는 동시에 프로그래밍 언어를 만드는 것입니다. 더 잘하기위해서 해야할 일은 프로그램에 부족한 연산자가 뭔지를 파악하는 감각을 기르는 것입니다. 프로그램을 보고 프로그램이 궁극적으로 뭘 하려는 것인지를 알 수 있어야합니다.

다음에서 nicknames 함수가 하나의 이름을 받아서 그 이름에서 만들어질 수 있는 별명들의 리스트를 만드는 함수라고 해봅시다. 어떻게하면 이 함수를 이용해서 이름들의 리스트에서 나올 수 있는 모든 별명들을 모을 수 있을까요? 리습을 조금 배운 사람은 다음과같은 함수를 만들 것입니다.

 

(defun all-nicknames (names)
  (if (null names)
      nil
    (nconc (nicknames (car names))
       (all-nicknames (cdr names)))))

 

더 경험이 많은 리습 프로그래머는 이 함수를 보고 이 함수가 진짜 하려던게 결국 mapcan과 같다는걸 알아챌 수 있습니다. 결국 어떤 사람들의 별명을 알아내기위한 새로운 함수를 정의하고 호출하는대신에 다음과 같은 한문장만을 사용할 수 있습니다.

 

(mapcan #’nicknames people)

 

all-nicknames 함수를 만드는건 바퀴를 다시 발명하는 것과 같습니다. 더군다나 범용 연산자 하나로 할 수 있는 일인데도 그 일만 처리하는 전용 함수를 만드는 것도 잘못된 것입니다. (역자주: 바퀴를 다시 발명하는 것은 같은 일을 하는 것을 또 중복해서 만드는 헛수고를 한다는 말입니다. 범용연산자로 할 수 있는 일을 함수로 만들어서 처리한다는 것은 결국 쓸데없는 확장을 한다는 것이기 때문에 나쁘다는 것으로 이해됩니다.)

같은 일을 처리하는 mapcan이 이미 있으므로, mapcan을 아는 개발자라면 all-nicknames를 보고 뭔가 이상하다는 생각을 할 것입니다. 상향식 프로그래밍에 익숙해지기 위해서는 필요한 연산자가 아직 만들어지지 않았을 때도 그렇게 이상하다는 느낌을 받을 수 있어야합니다. 이 프로그램이 궁극적으로 하려는게 x라는 것을 알아내는 것과 동시에, 그 x가 어떻게 만들어져야 할지도 알아낼 수 있어야합니다.

리습 프로그래밍에서 주어진 유틸리티를 이용해서 나에게 필요한 새로운 유틸리티를 뽑아내는 것이 필수입니다. 이번장에서는 그런 유틸리가 어떻게 생겨나는지를 보여드리겠습니다.

towns는 가까운 마을들의 리스트입니다. 가까운 거리순으로 정렬되어있습니다. 그리고 bookshops은 한 마을에 있는 모든 책가게들의 리스트를 반환하는 함수입니다. 만약 가장 가까운 책가게와 그 책가게가 있는 마을을 알고싶다면 다음처럼 만들기 시작할 것입니다.

 

 

(let ((town (find-if #'bookshops towns)))
  (values town (bookshops town)))

 

하지만 좀 불합리한게 있습니다. find-if에서 bookshops를 호출해서 nil이 아닌 항목을 찾습니다. 그런데 bookshops에서 반환한 값은 지워져버리고, 그 다음에 다시 bookshops를 호출해서 값을 얻게됩니다. bookshops가 무거운 함수라고하면 이 코드는 보기도 안좋고 효율적이지도 않은 코드가됩니다. 불필요한 작업을 줄이기위해 다음 함수로 바꿔볼 수 있습니다.

 

(defun find-books (towns)
  (if (null towns)
      nil
      (let ((shops (bookshops (car towns))))
    (if shops
	    (values (car towns) shops)
	    (find-books (cdr towns))))))

 

(find-books towns)를 한번 호출하면 우리가 원하는 값을 얻을 수 있습니다. 그런데 나중에 이와 똑같은 형태의 검색 작업을 또 할일이 있지 않을까요? 여기서 우리가 진짜 원하는건 find-if와 뭔가를 결합해서 테스트 함수로 찾은 값과 그 값에 연관된 다른 값을 반환하는 유틸리티입니다. 그런 유틸리티는 다음처럼 정의될 수 있습니다.

 

(defun find2 (fn lst)
  (if (null lst)
      nil
      (let ((val (funcall fn (car lst))))
    (if val
	    (values (car lst) val)
	    (find2 fn (cdr lst))))))

 

find-books와 find2는 정말 비슷하게 생겼습니다. find2는 find-books에서 조금 수정한 것뿐입니다. 이제 새로운 유틸리트를 가지고 원래하려던 일을 한 명령으로 수행할 수 있습니다.

 

(find2 #’bookshops towns)

 

리습 프로그래밍만의 고유한 특징중에 하나는 함수가 다른 함수의 인자가 될 수 있다는 것입니다. 이것 때문에 리습이 상향식 프로그래밍에 잘 적용될 수 있습니다. 함수의 인자로 처리 조건들을 전달할 수 있게되면 그 함수의 핵심을 잘 감추고 추상화하기 쉽습니다. (역자주: 원서에는 함수의 뼈를 함수 내부에 있는것, 함수의 살을 인자로 전달하는 것으로 비유했습니다. 저는 뼈를 함수의 핵심으로 이해했고, 함수의 살을 변할 수 있는 조건들로 이해했습니다.)

초급 프로그래밍 강좌에서는 강좌 시작부터 추상화를 잘할수록 중복된 수고를 할 필요가 없어진다고 가르칩니다. 강좌에서 처음 배우는 것들중 하나는 특정 행위에 종속되지 말라는 것입니다. 예를 들어 한두개의 조건을 따로 처리하는 두개의 함수를 만드는 대신에, 하나의 함수를 만들고 여러 조건을 인자로 받을 수 있는 하나의 함수를 만들라는 것입니다. (역자주: 1~100사이의 짝수를 더하는 함수와 홀수를 더하는 함수를 따로 만들 수도 있습니다. 하지만, 짝수냐 홀수냐를 인자로 받아서 결과를 반환하는 하나의 함수만을 만들 수도 있습니다. 조건에 따라 행동하는 함수를 조건별로 따로 만드는 것보다는, 하나의 함수를 만들어서 각 조건을 처리하게 만드는게 더 좋다는 이야기입니다.) 리습을 이용하면 이 아이디어를 좀더 발전시킬 수 있습니다. 함수 전체를 인자로 전달할 수 있기 때문입니다. 위에서 본 도서관 예제나 리스트 처리 예제는 둘다 특정한 일만을 하는 함수에서 함수에서 시작해서 함수를 인자로 받는 범용 함수로 발전시켜나갔습니다. 첫번째 예제는 이미 있는 mapcan을 썼고 두번째 예제는 find2라는 새로운 유틸리티를 만들었습니다. 그렇지만 하나의 공통된 원리를 가지고 있습니다. 범용적인 것과 개별적인 것을 섞는게 아니라 범용으로 처리하도록 정의하고 개별적인 사항은 인자로 전달하라는 것입니다.

이 원칙을 잘 적용하면 매우 멋진 프로그램을 만들수 있습니다. 이 원칙은 상향식 디자인의 핵심입니다. 이번 장에 있는 32개의 유틸리티중에 18개가 함수를 인자로 받는 것입니다.

 

 

4.2 추상화하는 것도 투자입니다

 

좋은 소프트웨어의 핵심은 효율성과함께 간결함에 있습니다. 프로그램이 길어질 수록 만드는데 들어가는 수고뿐 아니라 유지보수하는데도 더 많은 수고가 필요합니다. 다른 조건들이 다 같다면 짧은 프로그램일수록 더 좋은 프로그램이 됩니다.

그런 관점에서보면 유틸리티를 만든다는 것은 돈을 투자하는 것과 비슷합니다. find-books를 find2라는 유틸리티로 대체하기위해 우리는 좀더 많은 코드를 썼습니다. 하지만 어떤 면에서보면 프로그램을 좀더 짧게만든거라고도 할 수 있습니다. 왜냐면 유틸리티의 길이가 프로그램의 길이에 들어가지 않아도 되기 때문입니다.

리습을 확장하는걸 투자라고 생각하고 프로그램의 총 길이에 넣지 않는것이 눈속임만은 아닙니다. 유틸리티는 별도의 파일에 저장될 수 있고, 따라서 프로그램을 만들때 걸리적거리지않고 나중에 프로그램을 수정해야할 때도 신경쓰지 않아도 되니까요.

물론 투자기 때문에 유틸리티를 만드는것 자체에 들어가는 수고가 있습니다. 유틸리티를 특별히 잘 만들어야되는 이유가 있습니다. 그것들은 반복해서 사용될 것이고 오류가 있거나 비효율적이라면 반복되는만큼 더 피해가 커집니다. 디자인할때도 더 신경써야합니다. 새로운 유틸리티는 범용적인 경우를 처리하기위해 만들어져야하고, 지금 적용될 프로그램만을 위한게 아니니까요. 또 투자를 할때처럼 서두르지않아야 합니다. 새로운 연산자를 뽑아낼 생각이 들긴하는데 지금 필요한 곳외에 다른 곳에도 적용될지 확신이 안든다면 일단 만들어놓으세요. 대신 지금 그 유틸리티를 사용하는 프로그램과 같이 놔두면 됩니다.나중에 다른 프로그램에서 그 새로운 연산자를 써야할때 그걸 서브루틴에서 유틸리티로 바꾸고 범용적으로 접근가능하도록 만들면됩니다.

find2 유틸리티를 만든건 잘한 투자같습니다. 7줄을 투자한 즉시 7줄이 감소했습니다. 유틸리티는 첫 사용에서부터 투자에 대한 보상을 합니다. Guy Steele는 "프로그래밍 언어는 간결성을 지향하는 우리의 본능을 지원할 수 있어야한다"고 썼습니다. (역자주:이 문단은 완전히 의역을 했습니다. 비용이니 값이 싸다느니하는 표현들을 직역하기가 어려웠습니다.) 우리는 프로그래밍을 위해 타이핑을 많이 하는게 프로그래머에게 안좋다고 믿는 경향이 있습니다. (믿는다고 쓴 이유는 확신은 없지만 무의식적으로 그렇기때문입니다.) 사실 프로그래밍 언어 개발자는 그런 심리적 성향을 잘 알고있어야 합니다. 우리는 addition이라고 쓰기보다는 +라고 한글자만 쓰는걸 더 좋다고 생각합니다. 타이핑하는 노고를 줄여주니까요.

어떤 언어에서든 "간결성을 지향"하는 것은 새로운 유틸리트를 만드는게 허용되지 않는 상황에서는 문제를 일으킬 수밖에 없습니다. 짧은 구문이 효율적인 경우는 거의 없습니다. 어떤 리스트가 다른 리스트보다 긴지를 확인하고 싶을때 기본적인 리습 코드만 쓴다면 다음처럼 쓰게될 것입니다.

(> (length x) (length y))

여러개의 리스트이 있고 각각에 특정 함수를 매핑하고 싶다면 다음처럼 리스트를 하나로 묶은다음 처리하기 쉽습니다.

(mapcar fn (append x y z))

이런 예제들을 보면 우리가 비효율적으로 처리하기 쉬운 상황들을 위한 유틸리티가 필수라는 것을 알 수 있습니다. 좋은 유틸리티를 가진 언어는 좀더 잘 추상화된 프로그램을 만들게 도와줍니다. 이런 유틸리티가 잘 정의되어있다면 더 효율적인 프로그램을 만들도록 해주기도 합니다.

유틸리티를 모아놓은게 있으면 프로그래밍이 쉬워질게 분명합니다. 그런데 그 이상을 할 수도 있습니다. 더 좋은 프로그램을 만들 수도 있기 때문입니다. 예술가들이나 요리사들은 필요한 재료가 생기는 즉시 행동을 합니다. 그래서 예술가들이 최대한 많은 도구와 재료를 작업장에 모아놓으려고 하는 것입니다. 그들은 필요했던게 손에 들어오는 그 때가 뭔가 새로운걸 시작하기 좋은 때라는걸 알고있습니다. 상향식 프로그래밍을 하는 개발자들도 그렇습니다. 새로운 유틸리티를 한번 만들고나면, 써먹으려고했던 곳보다 더 많이 곳에 활용하게 될 것입니다. 다음 장에서는 유틸리티 함수의 몇가지 종류에 대해서 설명할 것입니다. 그것들은 절대 어려분이 리습에 추가할 함수들을 전부가 아닙니다. 하지만 예제에 나오는 유틸리티들 전부가 실수에서 가치를 증명한 것들입니다.

 

 

4.3 리스트를 써봅시다

 

리스트는 리습에서 가장 많이 쓰이는 데이터 구조였습니다. 리습의 LISP라는 이름도 리스트 프로세싱 "LISt Processing"의 줄임말입니다. 하지만 요즘도 그렇다고 생각하면 안됩니다. 리습의 언어적 표현이 리스트이던 시대는 끝났습니다. 잘 최적화된 커먼 리습 프로그램은 리스트를 쓰지 않을 수도 있습니다. 물론 컴파일 할때는 모든게 리스트입니다. 이미 컴파일되서 실행중일때는 리스트를 쓰지 않을 수 있습니다. 하지만 컴파일시에 매크로를 리습 코드로 확장할때는 리스트를 쓸 수밖에 없습니다. 매크로가 많으면 많을 수록 더 리스트를 많이 쓰게됩니다. 최신 리습에서는 리스트를 좀더 적게 사용하지만 아직도 리습 프로그램에서 많은 부분이 리스트 기반 연산일 것입니다.

 

(proclaim '(inline last1 single append1 conc1 mklist))
(defun last1 (lst)
  (car (last lst)))
(defun single (lst)
  (and (consp lst) (not (cdr lst))))
(defun append1 (lst obj)
  (append lst (list obj)))
(defun conc1 (lst obj)
  (nconc lst (list obj)))
(defun mklist (obj)
  (if (listp obj) obj (list obj)))

그림 4.1: 리스트 연산을 위한 소규모 함수들

 

그림 4.1과 4.2에는 리스트를 생성하거나 리스트의 상태를 확인하는 함수들을 모아놨습니다. 그림 4.1에는 작지만 요긴한 유틸리티들이 있습니다. 성능을 위해 유틸리티들을 inline으로 선언했습니다. 

첫번째로보이는 last1은 리스트에서 가장 마지막에 있는 항목을 반환합니다. last함수는 내장함수인데 리스트에 있는 마지막 항목이 아니라 마지막 항목을 포함한 리스트를 반환합니다. (역자주: last는 마지막 데이터의 객체를 반환하는게 아니라 마지막 데이터 객체와 nil이 포함된 리스트를 반환합니다. 따라서 car 함수를 호출해야 데이터 객체를 얻을 수 있습니다.) (car (last ...))는 이미 리스트의 마지막 항목을 찾을 때 흔히 사용하는 코드입니다. 그런 코드를 굳이 새롭게 유틸리티로 만들 필요가 있을까요? 물론입니다. 내장 연산자를 효율적으로 대체할 수 있다면 유틸리티로 만들 필요가 있습니다.

last1에는 에러 처리가 없습니다. 이 책에서 보여주는 모든 코드들은 에러 처리가 없습니다. 예제를 좀더 보기좋게 하려는 이유도 있습니다. 하지만 짧은 유틸리티에 에러 처리를 넣지 않는게 옳기 때문이기도 합니다.

 

 

> (last1 "blub")
>>Error: "blub" is not a list.
Broken at LAST...

 

 

위에서처럼 last1을 호출하면 last 함수에서 에러가 처리됩니다. 작은 유틸리티를 이용한 추상화는 단순해서 그 속이 잘 보입니다. 얇은 얼음을 보면 그 뒤까지 보이는 것처럼, last1같은 유틸리티를 보면 그 속이 잘 보이니까 유틸리티안의 어떤 함수에서 에러가 발생했는지보고 어떤 에러인지 알 수 있습니다.

single함수는 어떤 리스트가 하나의 항목만을 가진 리스트인지를 확인합니다. 리습 프로그램에서 자주 사용되는 테스트입니다. 간단하게 생각하면 이렇게도 만들 수 있을것 같습니다.

(= (length lst) 1)

만들고나니 좀 비효율적인것 같습니다. 리스트의 첫번째 항목을 확인하고 그 다음 항목을 확인하는 방법으로도 원래 알아내려했던걸 알아낼 수 있습니다.

append1과 conc1은 둘다 리스트의 끝에 새로운 항목을 추가하는 것입니다. append1은 아니지만 conc1은 유해합니다. 이런 기능들은 작지만 매우 자주 사용되는 것들이라 함수로 정의해줄 필요가 있습니다. 오래된 리습 구현체중에는 append1을 내장하고 있는 것들도 있습니다.

mklist도 Interlisp 구현체에 이미 포함되어있는 함수입니다. 전달받은 데이터를 확실히 리스트로 만드는 함수입니다. 많은 리습 함수들이 상황에 따라 하나의 값을 반환하기도하고 리스트를 반환하기도 합니다. loookup 함수도 그렇게 하나의 값을 반환할때도 있고 리스트를 반환할 때도 있다고 생각해봅시다. 만약 data라는 리스트에 있는 각 항목들을 lookup 함수로 처리하고, 결과를 하나로 모으고 싶다면 다음처럼 만들어야 합니다.

(mapcan #’(lambda (d) (mklist (lookup d)))
  data)

그림 4.2는 리스트를 처리하는 유틸리티중에 그림 4.1보다 좀더 긴 것들이 있습니다. 처음에 나오는 longer는 추상화와 효율성을 모두 만족하는 함수입니다. 두개의 시퀀스를 비교해서 앞에 것이 더 길때는 참을 반환합니다. (역자주: 시퀀스는 리스트와 벡터를 포함하는 리습의 데이터 타입입니다. 순서가 있는 데이터 객체의 모음이라고 정의되는데, 그에 해당하는 것이 리스트와 벡터입니다. 만약 어떤 함수가 시퀀스 타입의 데이터를 인자로 받는다고 돼있으면, 리스트와 벡터 둘다 처리할 수 있다는 뜻입니다.http://clhs.lisp.se/Body/t_seq.htm) 두개의 리스트의 길이를 비교할 때 다음처럼 하기 쉽습니다.

(> (length x) (length y))

이렇게하면 성능이 떨어지는게 각 리스트의 끝까지 읽어가면서 길이를 계산하기 때문입니다. 하나의 리스트가 다른 것보다 매우 길다면, 리스트를 끝까지 읽어가면서 길이를 재는 것은 시간 낭비입니다. longer처럼 만들면 성능도 빠르고 두개의 리스트의 길이를 동시에 잴 수 있습니다.

longer함수안에 두 리스트의 길이를 비교하는 재귀함수가 포함되어있습니다. longer함수는 length에 인자로 전달될 수 있는 데이터 타입이면 longer함수에서도 처리할 수 있어야 합니다. 하지만 동시에 길이를 비교할 수 있는 것은 리스트뿐이므로 내부 함수는 결국 두 인자가 모두 리스트일때만 호출이 가능합니다.

그 다음에 나오는게 filter 함수입니다. remove-if-not 함수와 find-if 함수의 관계를 알면 filter 함수를 이해하기 쉽습니다. remove-if-not 함수는 어떤 리스트에 대해 find-if 함수를 반복해서 호출하는 것과 같습니다. find-if에 리스트를 전달하면 하나의 값을 찾는데, 찾아진 값의 뒷부분에 있는 리스트에 대해 또 find-if를 호출하는 것입니다. 결국 전체 리스트 중에서 find-if에서 찾아진 항목들만 남게되는 것입니다.

 

 

(defun longer (x y)
  (labels ((compare (x y)
         (and (consp x)
		  (or (null y)
		      (compare (cdr x) (cdr y))))))
    (if (and (listp x) (listp y))
	(compare x y)
	(> (length x) (length y)))))

(defun filter (fn lst)
  (let ((acc nil))
    (dolist (x lst)
      (let ((val (funcall fn x)))
	(if val (push val acc))))
    (nreverse acc)))

(defun group (source n)
  (if (zerop n) (error "zero length"))
  (labels ((rec (source acc)
	     (let ((rest (nthcdr n source)))
	       (if (consp rest)
		   (rec rest (cons (subseq source 0 n) acc))
		   (nreverse (cons source acc))))))
    (if source (rec source nil) nil)))

그림 4.2: 좀더 큰 리스트 처리 함수들

 

 

> (filter #'(lambda (x) (if (numberp x) (1+ x)))
'(a 1 2 b 3 c d 4))
(2 3 4 5)

 

filter 함수에 인자로 함수 하나와 리스트를 전달합니다. 그러면 인자로 받은 함수가 리스트의 각 항목을 받아서 호출되고 결과값이 nil이 아니면 반환되는 리스트에 포함됩니다. filter 함수에서 결과값을 누적하는 방식이 2.8장에 있는 꼬리재귀 함수들과 같은 방식이라는걸 알필요가 있습니다. 사실 꼬리 재귀함수를 만드는 이유가 바로 컴파일러가 filter 함수와 같은 형태의 코드를 생성할 수 있도록 만들기 위해서입니다. filter에서처럼 꼬리 재귀로 함수를 만드는 것보다 단순 반복문으로 만드는게 더 간단합니다. (역자주: 더 간단할 수록 컴파일러가 최적화할 여지가 많겠지요.) filter함수에서와 같이 push와 nreverse를 같이 쓰는 것은 리스트에 값을 누적하기위해 리습에서 흔히 쓰는 방식입니다.

4.2의 마지막은 리스트를 하위 리스트로 쪼개주는 함수입니다. group함수에 리스트 l과 숫자 n을 넘기면 l의 항목들을 길이가 n인 리스트로 쪼개고, 그렇게 만들어진 하위리스트를 하나의 리스트로 반환합니다. 남은 항목들은 마지막 하위 리스트에 저장됩니다. 다음 코드처럼 두번째 인자에 2를 넘겨주면 연관리스트를 만들 수 있습니다. (역자주: 연관리스트란 각 항목안에 키 값과 데이터가 있어서 키를 이용해서 데이터를 찾을 수 있는 항목들의 리스트입니다. 다음 코드에서는 키가 A, C, E, G가 되고 데이터가 B, D, F, nil이 될 수 있습니다. 구현하기에 따라서 그 반대가 될 수도 있습니다.)

 

> (group ’(a b c d e f g) 2)

((A B) (C D) (E F) (G))

 

group함수는 꼬리재귀로 구현하기위해 매우 복잡하게 구현되었습니다. 완성된 프로그램을 만들 때도 그렇지만 함수 하나를 만들때도 미리 간단하게 프로토타입을 만들어보는게 좋습니다. flatten같은 함수를 만들 때도 최대한 쉽게 동작만 하도록 만들어서 점차 개선해나가는게 좋습니다. 간단한 버전이 동작하면 그 다음에 꼬리재귀나 반복문을 쓰는 버전으로 효율성을 개선해나가면 됩니다. 초기 버전이 짧은 편이라면 함수의 주석으로 남겨서 함수를 설명하는데 쓸 수도 있습니다. (원서 389페이지에 그림 4.2와 그림 4.3에 있는 group등 함수의 단순한 버전이 있습니다.)

 

 

group 함수는 약간 특이하게 에러 체크를 한번 합니다. 두번째 인자가 0인지를 확인하는데, 0이면 무한 재귀 호출을 하기 때문입니다. 이 책의 예제들은 보통 실무에서 사용되는 리습코드에 비해 최대한 기본적인 리습 코드로만 구현했습니다. 책의 각 장을 따로 볼 수 있도록 하기위해서입니다. group 함수는 매크로를 활용할 때 같이 쓰면 좋기때문에 예외적으로 다른 챕터에서 몇번 더 사용될 것입니다.

 

그림 4.2에 나온 함수들은 1차원 리스트에 활용됩니다. 그림 4.3에있는 두개의 함수는 중첩 리스트에 적용됩니다. flatten은 Interlisp구현체에 이미 들어가있는 것입니다. 리스트에 있는 모든 항목들을 중첩된 리스트에서 꺼내서 1차원 리스트로 반환합니다. 

 

> (flatten ’(a (b c) ((d e) f)))

(A B C D E F)

 

마찬가지로 그림 4.3에있는 prune 함수는 copy-list에서 remove-if로 특정 조건의 항목들을 빼는 기능을 트리로 구현한 것입니다. 리스트에 들어있는 하위 리스트를 재귀적으로 타고들어갑니다.

 

> (prune #’evenp ’(1 2 (3 (4 5) 6) 7 8 (9)))

(1 (3 (5)) 7 (9))

 

모든 조건을 체크하는 함수가 참을 리턴하는 항목들이 제거됩니다.

 

(defun flatten (x)
  (labels ((rec (x acc)
    	(cond ((null x) acc)
		      ((atom x) (cons x acc))
		      (t (rec (car x) (rec (cdr x) acc))))))
    (rec x nil)))

(defun prune (test tree)
  (labels ((rec (tree acc)
		(cond ((null tree) (nreverse acc))
		      ((consp (car tree))
		       (rec (cdr tree)
			    (cons (rec (car tree) nil) acc)))
		      (t (rec (cdr tree)
			      (if (funcall test (car tree))
				  acc
				(cons (car tree) acc)))))))
    (rec tree nil)))

그림 4.3: 중첩 리스트를 위한 유틸리티

 

4.4 탐색을 만들어 봅시다

 

(defun find2 (fn lst)
  (if (null lst)
      nil
    (let ((val (funcall fn (car lst))))
      (if val
      (values (car lst) val)
	(find2 fn (cdr lst))))))

(defun before (x y lst &key (test #'eql))
  (and lst
       (let ((first (car lst)))
	 (cond ((funcall test y first) nil)
	       ((funcall test x first) lst)
	       (t (before x y (cdr lst) :test test))))))

(defun after (x y lst &key (test #'eql))
  (let ((rest (before y x lst :test test)))
    (and rest (member x rest :test test))))

(defun duplicate (obj lst &key (test #'eql))
  (member obj (cdr (member obj lst :test test))
	  :test test))

(defun split-if (fn lst)
  (let ((acc nil))
    (do ((src lst (cdr src)))
	((or (null src) (funcall fn (car src)))
	 (values (nreverse acc) src))
      (push (car src) acc))))

그림 4.4: 리스트를 탐색하는 함수들

 

리스트를 탐색하는 함수들의 예제를 몇개 보겠습니다. 커먼 리습에는 리스트 탐색 구현에 활용할만한 내장 연산자들이 많이 있습니다. 하지만 어떤 탐색 작업들은 그것만 가지고는 만들기가 어려운 것도 있고, 효율적으로 만들기 어려운 것들도 있습니다. 이전에 all-nicknames 구현에서 그런 상황을 봤었습니다. 그림 4.4에 있는 find2 함수도 그렇게 내장 연산자들이 할 수 없는 일을 하는 함수입니다.

before 유틸리티도 비슷한 이유로 만들어졌는데 하나의 객체가 다른 객체보다 리스트의 앞쪽에 있는 것인지를 알려주는 함수입니다. (역자주: b가 d보다 앞에있으면 b이후에있는 리스트 항목들이 반환되고, 아니면 nil이 반환됩니다.)

 

> (before ’b ’d ’(a b c d))

(B C D)

 

다음처럼 기본 리습 코드들로만 써서 만들수도 있는 쉬운 함수입니다.

 

(< (position ’b ’(a b c d)) (position ’d ’(a b c d)))

 

하지만 그렇게 기본 연산자로 만들면 비효율적이기도하고 에러를 내기도 쉽습니다. 두개의 객체를 다 리스트에서 검색하므로 비효율적입니다. 또 둘중 하나의 객체라도 리스트에 없으면 nil값이 <연산자에 넘어가므로 에러가 발생합니다. before를 쓰게되면 이런 문제들을 방지할 수 있습니다.

before는 member라는 내장 함수와 하는 일도 비슷하고 구현도 비슷합니다. member도 그렇듯이 before함수는 test 인자를 추가로 지정할 수 있는데 기본값이 eql입니다. 또 결과값으로 그냥 t만을 반환하는게 아니라 첫번째 인자로 전달된 객체로 시작되는 리스트를 반환해줘서 상황에 따라 유용하게 쓸 수 있습니다.

 

before는 리스트에서 두번째 인자 이전에 첫번째 인자를 만나면 참을 반환합니다. 그래서 두번째 인자가 리스트에 포함된게 아니라고해도 참이 반환됩니다.

 

> (before ’a ’b ’(a))

(A)

 

after는 두개의 인자가 모두 리스트에 포함되야하는 함수이므로 좀더 정확한 테스트를 수행합니다.

 

> (after ’a ’b ’(b a d))

(A D)

> (after ’a ’b ’(a))

NIL

 

(member o l)을 호출하면 리스트 l에서 o를 찾아냅니다. 반환된 리스트는 l에서 o 다음에 있는 항목들의 리스트입니다. 이 반환값은 중복 값을 검사하는 등에 사용될 수 있습니다. o가 l에 중복되서 포함되어있으면 member의 결과값에 cdr을 호출한 리스트에도 또 o가 들어있을 것입니다. 그렇게 만든게 바로 duplicate 유틸리티입니다.

 

> (duplicate ’a ’(a b c a d))

(A D)

 

중복 데이터를 체크하는 다른 유틸리티들도 같은 방식으로 구현될 수 있습니다. 프로그래밍 언어를 설계하는 분들중에 어떤 분들은 리습에서 nil을 빈 리스트를 표현하는데도 사용하고 거짓을 표현하는데도 사용한다는것을 이상하게 생각할 것입니다. 14.2장에 나오는 것처럼 문제가 될때도 있습니다. 하지만 duplicate같은 함수에서는 편리하게 사용됩니다. 어떤 데이터가 시퀀스에 포함되어있는가를 확인할 때는 비어있는 시퀀스로 거짓을 표현하는게 더 자연스러울 것입니다. (역자주: 시퀀스sequence는 순서가 있는 객체들의 집합을 나타내는 클래스입니다. 벡터와 리스트가 시퀀스의 하위 클래스입니다. http://www.tutorialspoint.com/lisp/lisp_sequences.htm) 

그림 4.4에서 마지막에 있는 함수도 member를 좀더 일반화한 것입니다. member가 리스트에서 특정 항목을 찾고 그 다음 항목들의 리스트를 반환하는데 반해 split-if는 찾은 항목의 앞뒤 리스트를 모두 반환합니다. 어떤 방식이든지 이미 정렬된 리스트에 주로 사용됩니다.

 

> (split-if #’(lambda (x) (> x 4))

’(1 2 3 4 5 6 7 8 9 10))

(1 2 3 4)

(5 6 7 8 9 10)

 

그림 4.5에는 리스트의 항목들을 비교하면서 검색하는 함수들이 있습니다. 첫번째에 있는 most함수는 한번에 하나의 항목씩 조사합니다. 리스트 하나와 점수함수를 인자로 받습니다. 리스트의 각 항목을 점수함수에 전달해서 제일 점수를 내는 항목을 찾습니다. 같은 점수를 내는 항목이 있다면 앞에 있는 항목을 반환합니다.

 

> (most #’length ’((a b) (a b c) (a) (e f g)))

(A B C)

3

 

most는 편의를 위해 검색된 항목의 점수까지도 반환해줍니다.

좀더 일반적인 검색을 할때는 best를 씁니다. 마찬가지로 함수와 리스트 하나를 인자로 받습니다. most와 다른 점은 이 함수가 두개의 인자를 받아서 비교한다는 것입니다. 리스트에 있는 모든 항목 중에서 함수가 비교하고자하는 조건에 가장 잘 맞는 항목을 반환합니다.

 

 

(defun most (fn lst)
  (if (null lst)
      (values nil nil)
    (let* ((wins (car lst))
       (max (funcall fn wins)))
      (dolist (obj (cdr lst))
	(let ((score (funcall fn obj)))
	  (when (> score max)
	    (setq wins obj
		  max score))))
      (values wins max))))

(defun best (fn lst)
  (if (null lst)
      nil
    (let ((wins (car lst)))
      (dolist (obj (cdr lst))
	(if (funcall fn obj wins)
	    (setq wins obj)))
      wins)))

(defun mostn (fn lst)
  (if (null lst)
      (values nil nil)
    (let ((result (list (car lst)))
	  (max (funcall fn (car lst))))
      (dolist (obj (cdr lst))
	(let ((score (funcall fn obj)))
	  (cond ((> score max)
		 (setq max score
		       result (list obj)))
		((= score max)
		 (push obj result)))))
      (values (nreverse result) max))))

그림 4.5: 리스트를 검색하는 함수들

 

 

> (best #’> ’(1 2 3 4 5))

5

 

best를 보면 sort로 처리한 리스트에 car를 실행하는 것과 같아보이지만, best가 더 효율적입니다.(역자주: sort를 호출하면 모든 항목을 정렬합니다. 그럼 최소한 O(nlogn)함수가 되지요. 하지만 best로 가장 큰 값만 찾으면 모든 항목들을 다 정렬할 필요가 없으므로 O(n)함수가 됩니다. 훨씬 더 효율적입니다.) best를 호출할 때 리스트 전체를 정렬하도록 만드는 함수를 전달할 수도 있긴 합니다. 어쨌든 before와 동일하게 조건을 만족하는 항목이 있다면 리스트의 앞에 있는 항목이 반환됩니다.

마지막에 있는 mostn 함수는 하나의 함수와 하나의 리스트를 인자로 받아서, 가장 높은 점수를 내는 항목들의 리스트를 반환합니다. (점수도 같이 반환합니다.)

 

> (mostn #’length ’((a b) (a b c) (a) (e f g)))

((A B C) (E F G))

3

 

4.5 맵핑함수를 써봅시다

 

(역자주: 한 집합에 있는 하나의 값을 다른 집합의 하나 이상의 값에 연결하는 것을 맵핑이라고 합니다. 함수의 수학적 정의와 같습니다.)

 

맵핑관련 함수들도 많이 사용되는 함수의 종류중 하나입니다. 인자들의 시퀀스에 하나의 함수를 적용하는 함수들입니다. 그림 4.6에 새로운 맵핑 함수들의 예제가 몇가지 있습니다. 처음 3가지 함수들은 인자가 리스트가 아니라 특정 범위입니다. 그리고 그 범위에 적용할 함수도 인자로 받습니다. map0-n과 map1-n은 양의 정수로 범위를 지정합니다.

 

> (map0-n #’1+ 5)

(1 2 3 4 5 6)

 

mapa-b라는 함수는 좀더 범용적이어서 어떤 범위도 처리할 수 있습니다. mapa-b을 가지고 위의 두 함수를 구현할 수 있습니다.

 

> (mapa-b #’1+ -2 0 .5)

(-1 -0.5 0.0 0.5 1.0)

 

mapa-b는 자기보다 좀더 일반적인 map->함수로 구현됩니다.(역자주: 리습은 함수 이름에 대한 제한이 거의 없습니다. 그래서 map->가 함수 이름이 될 수 있습니다.) map->함수는 종류에 상관없이 객체들로 이루어진 시퀀스를 만듭니다.. 함수의 두번째 인자로 전달되는 객체는 시퀀스의 첫번째 객체가 됩니다. 그리고 그 시퀀스는 세번째 인자로 전달된 함수가 만든 객체로 끝납니다. 네번째 인자로 전달된 함수는 시퀀스에 들어갈 객체를 생성합니다. map->을 이용하면 숫자들의 시퀀스뿐 아니라 어떤 데이터 구조든지 원하는대로 처리할 수 있습니다. 다음처럼 map->을 이용해서 mapa-b를 만들 수 있습니다.

 

 

(defun mapa-b (fn a b &optional (step 1))
  (map-> fn
     a
	 #'(lambda (x) (> x b))
	 #'(lambda (x) (+ x step))))

 

(defun map0-n (fn n)
  (mapa-b fn 0 n))

(defun map1-n (fn n)
  (mapa-b fn 1 n))

(defun mapa-b (fn a b &optional (step 1))
  (do ((i a (+ i step))
       (result nil))
      ((> i b) (nreverse result))
    (push (funcall fn i) result)))

(defun map-> (fn start test-fn succ-fn)
  (do ((i start (funcall succ-fn i))
       (result nil))
      ((funcall test-fn i) (nreverse result))
    (push (funcall fn i) result)))

(defun mappend (fn &rest lsts)
  (apply #'append (apply #'mapcar fn lsts)))

(defun mapcars (fn &rest lsts)
  (let ((result nil))
    (dolist (lst lsts)
      (dolist (obj lst)
    (push (funcall fn obj) result)))
    (nreverse result)))

(defun rmapcar (fn &rest args)
  (if (some #'atom args)
      (apply fn args)
    (apply #'mapcar
	   #'(lambda (&rest args)
	       (apply #'rmapcar fn args))
	   args)))

 

속도를 위해서 내장함수 mapcan은 유해함수로 구현되어있습니다. 다음처럼 mapcan을 다시 만들 수도 있습니다.
 
(defun our-mapcan (fn &rest lsts)
  (apply #'nconc (apply #'mapcar fn lsts)))

 

 
mapcan은 nconc를 써서 리스트들을 한꺼번에 결합합니다. 그래서 첫번째로 전달되는 리스트는 새로 생성되도록 하는게 좋습니다. 기존의 리스트를 쓰면 그 리스트의 값이 바뀝니다. 그래서 (원서 41페이지에 있는) nicknames함수가 별명의 리스트를 만드는 함수로 구현된 것입니다. nicknames함수가 어딘가에 저장되어있는 리스트를 반환했다면, mapcan을 쓰는게 안전할 수 없습니다. 대신 append로 리스트를 결합해야합니다. 그런 경우를 위해 mapend가 유해하지않은 방식으로 mapcan와 같은 일을 해줍니다.
 
다음에 나오는 유틸리티는 mapcars입니다. 여러개의 리스트에 mapcar를 실행할 수 있습니다. 숫자로된 두개의 리스트가 있고 각 리스트의 값들을 제곱해서 하나의 리스트로 만들고 싶을때 다음처럼 기본 리습 함수들만 사용해서 만들 수 있습니다.
 
(mapcar #’sqrt (append list1 list2))
 
하지만 이렇게하면 불필요하게 리스트를 만드는 동작이 들어갑니다. list1과 list2를 합친 리스를 만들지만 전체 연산이 끝나면 그렇게 합쳐진 리스트는 버려집니다. mapcars를 가지고 다음처럼하면 똑같은 결과를 얻을 수 있습니다.
 
(mapcars #’sqrt list1 list2)
 
그리고 불필요한 리스트 생성도 없습니다.
 
그림 4.6에서 마지막으로 소개하는 함수는 트리를 위한 mapcar함수입니다. rmapcar라는 이름은 "recursive mapcar(재귀용 mapcar)"라는 이름을 줄인 것입니다. mapcar가 1차원적인 리스트를 처리하는게, 이 함수는 트리를 처리할 수 있습니다.
 
> (rmapcar #’princ ’(1 2 (3 4 (5) 6) 7 (8 9)))
123456789
(1 2 (3 4 (5) 6) 7 (8 9))
 
mapcar와 같이 하나 이상의 리스트를 처리할 수 있습니다.
 
> (rmapcar #’+ ’(1 (2 (3) 4)) ’(10 (20 (30) 40)))
(11 (22 (33) 44))
 
이후에 나오는 함수들중에 rmapcar로만 구현되는 함수들이 있습니다. 324페이지에 나오는 rep도 그렇습니다. 몇몇 구현체들 중에는 몇가지 리스트 맵핑함수를 지원하지않고, CLTL 2에 나오는 매크로를 대신 제공하는 것들도 있습니다. (역자주: http://cliki.net/CLTL2 CLTL2는 책 이름입니다. LISP의 ANSI 표준이 나오기전까지 사실상 이 책이 표준역할을 했었습니다.) 예를 들면
 
(mapa-b #’fn a b c)
 
다음 매크로로 대체될 수도 있습니다.
 
(collect (#Mfn (scan-range :from a :upto b :by c)))
 
그래도 어떤 경우에는 맵핑 함수를 써야할 때가 있습니다. 맵핑함수를 써야 더 명확하고 보기 좋은 코드가 될 때가 있습니다. map->으로는 잘 표현이 되는데 series를 쓰면 잘 표현이 안될때도 있습니다. 그리고 맵핑함수는 다른 함수의 인자로 전달될 수도 있습니다. (역자주: 그래서 맵핑함수와 같은 일을 하는 매크로가 있긴 하지만 그래도 맵핑함수가 필요한 이유들입니다.)

댓글

댓글 본문
작성자
비밀번호
버전 관리
gurugio
현재 버전
선택 버전
graphittie 자세히 보기