Lisp - 프로그램을 조각내기

작성, 수정

English: Lisp - breaking a program into pieces

예전에 하스켈로 작은 Lisp 인터프리터를 만들었다. 안에는 define, lambda, cond, '(quote), eq?, car, cdr, cons와 사칙연산 정도만 들어 있다. 내장된 기능이 거의 없어도 작은 함수부터 하나씩 정의하고, 앞서 만든 함수를 조합하여 다음 함수를 만들어 나가면 필요한 도구들을 어렵지 않게 갖추게 된다.

기본 함수

가장 먼저 필요한 것은 빈 리스트인지 확인하는 null?과 논리 부정인 not이다. null?은 인자를 빈 리스트 '()와 eq?로 비교하기만 하면 된다. not은 인자가 #f일 때 #t를, 그 외에는 #f를 반환한다. 이 인터프리터에는 cond에서 흔히 쓰는 else 키워드가 따로 없는데, #f가 아닌 값은 모두 참으로 취급되므로 마지막 절의 조건 자리에 #t를 두면 같은 역할을 한다.

> (define null? (lambda (x) (eq? x '())))
> (null? '())
#t
> (null? '(1))
#f

> (define not (lambda (x) (cond
	((eq? x #f) #t)
	(#t #f))))
> (not #f)
#t
> (not 3)
#f

재귀로 리스트 다루기

리스트를 다루는 함수들은 대체로 같은 모양으로 재귀 호출을 한다. 리스트가 비었으면(null?) 재귀를 멈추고, 비어 있지 않으면 첫 원소(car)를 처리한 뒤 나머지 리스트(cdr)를 같은 함수에 다시 넘긴다.

map은 리스트를 끝까지 순회하면서 각 원소에 함수 fn을 적용한 결과를 cons로 다시 이어 붙인다. filter도 구조는 거의 같지만, fn을 적용한 결과가 참일 때만 해당 원소를 결과 리스트에 남기고 거짓이면 건너뛴다. 앞서 정의한 not과 null?을 조합해 넘기면 리스트에서 빈 리스트가 아닌 원소만 골라낸다.

> (define map (lambda (fn l) (cond
	((null? l) '())
	(#t (cons (fn (car l)) (map fn (cdr l)))))))
> (map (lambda (x) (* x 2)) '(1 2 3))
(2 4 6)
> (define filter (lambda (fn l) (cond
	((null? l) '())
	((fn (car l)) (cons (car l) (filter fn (cdr l))))
	(#t (filter fn (cdr l))))))
> (filter (lambda (x) (not (null? x))) '(1 () (2) () 3))
(1 (2) 3)

특정 위치의 원소를 꺼내는 list-ref도 같은 방식으로 작성한다. 한 단계 재귀할 때마다 리스트의 앞 원소를 하나씩 버리면서 인덱스 n을 1씩 줄여 나가다가, n이 0이 되었을 때 첫 원소를 꺼낸다. 인터프리터에 숫자 비교를 위한 =가 따로 없었기에 여기서는 eq?로 0과 비교했다.

> (define list-ref (lambda (l n) (cond
	((eq? n 0) (car l))
	(#t (list-ref (cdr l) (- n 1))))))
> (list-ref '(11 22 33 44 55 66) 3)
44

2차원 리스트

비슷한 재귀 구조로 값 x를 n번 반복한 리스트를 만드는 replicate를 정의한다. n이 0이 될 때까지 하나씩 줄여 가며 cons로 x를 앞에 계속 붙인다.

> (define replicate (lambda (x n) (cond
	((eq? n 0) '())
	(#t (cons x (replicate x (- n 1)))))))
> (replicate 0 7)
(0 0 0 0 0 0 0)

리스트 안에 리스트를 넣으면 2차원 배열이 된다. 2차원 리스트의 모든 원소에 함수를 적용하는 map-2d를 만들 때에는 처음부터 재귀를 새로 작성할 필요가 없다. 바깥쪽 map이 각 행을 순회하고 안쪽 map이 그 행의 원소들을 순회하도록, 앞서 만든 map을 두 번 겹쳐 정의하면 된다.

> (define map-2d (lambda (fn ll)
	(map (lambda (l) (map fn l)) ll)))
> (map-2d (lambda (x) (* x 10)) '((1 2) (3 4)))
((10 20) (30 40))

replicate도 마찬가지다. (replicate 0 3)으로 만든 한 행 (0 0 0)을 다시 바깥쪽 replicate에 넘기면 0으로 채워진 3×3 크기의 board가 만들어지고, 여기에 map-2d를 적용해 모든 칸의 값을 한 번에 바꾼다.

> (define board (replicate (replicate 0 3) 3))
> board
((0 0 0) (0 0 0) (0 0 0))
> (define board (map-2d (lambda (x) (+ x 9)) board))
> board
((9 9 9) (9 9 9) (9 9 9))