인공지능 언어 : L I S P
전문가 시스템 원리와 개발 : 이재규, 최형림, 김현수, 서민수, 주석진, 지원철 공저, 법영사, 1996, Page 169~190
LISP은 LISt Processor와 동의어로서 심볼(Symbol)들로 구성된 리스트(List)들을 쉽게 조작할 수 있는 언어이다. LISP은 MacLISP, Inter LISP, Franz LISP 등의 많은 방언(Dialects)들이 있다. 이들은 기본적인 특성들을 공유하고 있으나 여러 면에서 서로가 상당히 다르다. 지금까지 널리 쓰이고 있는 LISP의 방언으로는 MIT 에서 개발한 MacLISP 과 Bolt, Beranek, Newman 등 세 사람이 Xerox Palo Alto Research Center 와 더불어 개발한 Inter LISP 이 있다. 이외에도 U.C. Berkeley 에서 MacLISP 을 바탕으로 개발한 Franz LISP 등이 있다. 이러한 LISP 방언을 표준화하고자 하는 노력이 수년에 걸쳐 지속되었고, 그 결과 Common LISP이 출현하게 되었다. 이를 계기로 특정 방언으로 씌어진 프로그램은 특정 컴퓨터에서만 수행 가능했었던 문제들이 해결되는 계기가 되었다. 그러나 아직가지 LISP 사용자들이 모두 Common LISP을 사용되고 있지는 않지만 산업, 정부기관, 대학과 연구소 등에서 점차 일반화되는 추세이다.
그러면 우선 다음의 예를 통하여 LISP이 어떻게 사용될 수 있는지 살펴보고, 이어서 LISP에 대해 자세히 살펴보기로 하자. 진술한 바 있는 동물의 특성을 보고 그것이 어떤 동물인지 맞히는 문제를 생각하여 보자. 예를 들어, "날아다니고 알을 낳는다면 어떤 동물인가"라는 물음에 대하여 우리는 그것이 새라는 것을 알 수 있다. 이는 다음과 같은 규칙의 형태로 표현될 수 있다.
IF 난다.
AND
알을 낳는다.
THEN 새이다.
이러한 규칙을 LISP으로는 어떻게 표현할 수 있는가? LISP으로 표현된 다음의 동물식별 규칙베이스는 괄호와 SETQ 등 몇 개의 LISP 구문들로 되어 있다. 후술하는 LISP에 대한 설명을 숙지한 후 이것을 다시 음미해 보기 바란다.
(SETQ
RULES
'((RULE
ID1
(IF
(animal has hair))
(THEN
(animal is mammal)))
(RULE
ID2
(IF
(animal gives milk))
(THEN
(animal is mammal)))
(RULE
ID3
(IF
(animal has feathers))
(THEN
(animal is bird)))
(RULE
ID4
(IF
(animal flies)
(animal lays eggs))
(THEN
(animal is bird)))
(RULE
ID5
(IF
(animal is mammal)
(animal eats meat))
(THEN
(animal is carnivore)))
(RULE ID6
(IF
(animal is mammal)
(animal has pointed teeth)
(animal has claw)
(animal has forward eyes))
(THEN
(animal is carnivore)))
(RULE ID7
(IF
(animal is mammal)
(animal has hoofs))
(THEN
(animal is ungulate)))
(RULE
ID8
(IF
(animal is mammal)
(animal chews cud))
(THEN
(animal is ungulate)))
(RULE
ID9
(IF
(animal is carnivore)
(animal has tawny color)
(animal has dark spots))
(THEN
(animal is cheetah)))
(RULE
ID10
(IF
(animal is carnivore)
(animal has tawny color)
(animal has black stripes))
(THEN
(animal is tiger)))
(RULE
ID11
(IF
(animal is ungulate)
(animal has long neck)
(animal has long legs)
(animal has dark spots))
(THEN
(animal is giraffe)))
(RULE
ID12
(IF
(animal is ungulate)
(animal has black stripes))
(THEN
(animal is zebra)))
(RULE
ID13
(IF
(animal is bird)
(animal does not fly)
(animal has long neck)
(animal has long legs)
(animal is black and white))
(THEN
(animal is ostrich)))
(RULE
ID14
(IF
(animal is bird)
(animal does not fly)
(animal swims)
(animal is black and white))
(THEN
(animal is penguin)))
(RULE
ID15
(IF
(animal is bird)
(animal flys well))
(THEN
(animal is albatross)))))
LISP은 아톰(Atom)과 리스트(List)라는 두 종류의 대상을 다룬다. 아톰은 숫자나 사람, 사물, 개념 등과 같은 대상을 표현할 때 사용되는 심볼(Symbol)을 말한다. 리스트는 괄호로 둘러싸여 있는 원소들로 구성되어 잇으며, 원소는 아톰이거나 리스트로 되어 있다.
1 심볼(Symbol)
심볼의 내부표현은 다음과 같다.
|
심볼명(name) |
|
심볼값(value cell) |
|
함수(function) |
|
속성 리스트(property list) |
|
패키지(package) |
(1) 심볼명(Name)
모든
심볼들은 지칭할 수 잇는 이름을 가지고 있다. 어떤 심볼이 "FOO"라고
하는 이름을 가지고 있다면 이는 심볼명란에 다음과 같이 표현된다.
(2) 심볼값(Value Cell)
심볼값은
심볼에 의해 이름이 붙여진 변수(Variable)의 값을 가리킨다. 다음의 예를 살펴보자.
이하의 예에서 사용되는 "*" 기호는 LISP 인터프리터상의 프롬프트를 의미한다.
(예)
*
FOO
ERROR :
unbounded variable
FOO에 어떤 값도 할당되어 있지 않으므로 unbounded variable이란 에러 메시지가 나온다. 만일 FOO에 elmer라는 값을 할당하려면 다음과 같이 표현하면 된다.
*
(setq foo 'elmer)
ELMER
FOO에 elmer가 할당되었다.
따라서 FOO값을 보면,
*
FOO
ELMER
와 같이 나온다. 이것은 심볼값란에 다음과 같이 표현된다.
(3) 함수(Function)
LISP은
정의된 함수를 가리키는 포인터(Pointer)를 가지고 있다. 예를 들어, "+"라는
심볼이 더하는 기능을 가진 함수로 정의되려면 심볼명에는 "+"로, 그것의
함수는 함수란에서 다음과 같이 정의된다.
(4) 속성 리스트(Property List)
속성
리스트란에는 화일명 등 심볼에 대한 기타의 정보를 저장하고 있다.
(5) 패키지(Package)
패키지에는
커다란 프로그램에 있는 서로 다른 모듈들간에 생길 수 있는 명칭의 혼란을 방지해
주는 정보를 가지고 있다.
2. 숫자(Number)
숫자는 항상 그 자체의 값으로 평가된다. 숫자를 조작할 수 있는 산술함수는 다음과 같은 것들이 있다. 즉, +, -, *, /의 사칙연산과 1+, 1- 등 하나씩 증가시키거나 감소시키는 등 기본연산이 가능한 함수들이다.
(예)
*
(+3 5) =>
8
* (-100 7) =>
93
* (* 2 3) =>
6
* (/ 99 3) =>
33
* (1 + 5) =>
6
* (1 - 5) =>
4
* (+2 (* 4 5)) =>
22
* (/ (* 6 7) (-5.0 2))) =>
14.0
여기서 "+"와 "*"는 인수(Arguments)로 어떤 수도 가능하다. 반면에 "-"와 "/"는 인수(Argument)로 0이 아닌 수가 가능하다.
(예)
*
(+ 1 2 3 4 5) => 15
*
(/ 120 3.0 4 2) => 5.0
1. 함수의 정의 : DEFUN
DEFUN은 새로운 함수를 정의하기 위한 특수형이다. 사실, LISP 프로그램은 정의된 삼수들의 집합으로 볼 수 있다. 따라서 LISP 프로그래밍은 함수를 하나씩 정의하고 테스트하면서 점증적으로 프로그램의 규모가 커지는 방식으로 진행된다. 간단한 예로 "half"라는 함수를 다음과 같이 정의할 수 있다.
(예)
*
(defun half (n) (/ n 2))
여기서, "("는 LISP 표현의 시작, "defun"은 함수를 정의하기 위한 특수형, "half"는 함수명, "(n)"는 인수리스트, "(/ n 2)"는 함수몸체, ")"는 함수의 끝을 가리킨다.
2. 함수의 테스트
위에서 정의된 "half" 함수를 수행시켜 보기로 하자. 다음은 LISP 인터프리터에서 다음과 같이 표현되었을 경우에 수행한 결과이다.
*
(half 8)
4
*
(+ 7 (half 10))
12
변수는 특정 함수 내에서만 효력을 갖는(사용되는) 지역변수와 모든 함수에 걸쳐 효력을 갖는 전역변수로 나눌 수 있다.
1. 지역변수(Local Variable)
함수 half에서 변수 n은 지역변수이다. 왜냐하면 n이 함수 half 내에서만 존재하기 때문이다.
2. 전역변수(Global Variable)
다음의 예에서 "weight"는 전역변수이다.
*
(setq weight 120)
* (defun
eat-a-pie ( )
(setq
weight (1+ weight)) 'yum)
*
weight => 120
*
(eat-a-pie) => yum
*
(eat-a-pie) => yum
*
weight => 122
여기서 함수호출이 계속되는 동안 데이터를 저장하고 잇는 것을 알 수 있다.
"Evaluation" 이란 LISP 표현이 결과값으로 변환되는 과정이다. 예를 들어, 리스트 '(+ 3 5)'는 LISP 표현이고 결과값은 '8'이다. Evaluation 규칙은 다음과 같은 것이 있다.
규칙 1 : 숫자는 항상 그 자체로
evaluation 된다.
(예)
1은 1로 evaluation 된다.
규칙 2 : 심볼은 그것이 가리키는
변수의 값으로 evaluation된다.
(예) (setq x 9)를 evaluation 한 후 x를 보면 9로 evaluation된다.
규칙
3 : quote 된 것은 quote가 빠진 것으로 evaluation 된다.
(예) '(+ 3 5)는 (+ 3 5)로 evaluation 된다.
규칙
4 : 리스트를 evaluation하려면 리스트의 첫번째 원소는 반드시 함수 또는 특수형이
되어야 한다.
(예)
(defun average (n m)
(half (+ n m)))를 정의한 후,
(average (+ 3 5)(* 6 2))는 10으로 evaluation 된다.
1. 포인터(Pointer)란 무엇인가?
Cons Cell이 무엇인지 알기 전에 우선 포인터가 무엇인지 알아보기로 하자. 포인터는 주소(Address)를 나타내며 보통 화살표로 표시한다. 예를 들어, 심볼은 다섯 개의 포인터로 구성되어 있으며 심볼명, 심볼값, 함수, 속성 리스트, 패키지 셀(Cell)에 저장되어 있다. 포인터로 구성된 하나의 LISP 데이터 유형으로 Cons Cell이 있다. Cons Cell은 항상 두 개의 포인터를 지니고 있다.
만일 심볼 ABC와 숫자 100을 가리키는 포인터를 지닌 Cons Cell은 다음과 같이 나타낼 수 있다.
2. Cons Cell 체인(Chain)
Cons Cell 체인이란 Cons Cell이 사슬(Chain)모양으로 연결되어 있는 것을 말한다. Cons Cell 체인은 다음과 같은 특성을 가지고 있다. 첫째, 마지막을 제외한 각 셀의 CDR 부분은 체인에서 다음 셀을 가지고 있다. 첫째, 마지막을 제외한 각 셀의 CDR 부분은 체인에서 다음 셀을 가리킨다. 둘째, 마지막 셀의 CDR은 항상 NIL을 가리킨다. NIL은 보통 LISP에서 체인의 끝을 의미한다. 셋째, 체인에서 각 셀의 CAR 부분은 보통 데이터를 가리킨다.
3. Cons Cell과 관련되 함수
(1) LIST 함수
LIST는
새로운 Cons Cell 체인을 만들기 위한 함수이며 인수의 수에는 제한이 없다. 예를
들어, (list 'foo 'bar 'baz)로 표현된 LIST 함수는 다음과 같은 Cons Cell 체인을
형성한다.
(2) CONS 함수
CONS는
Cons Cell 구조를 만들며 두 개의 인수만을 가질 수 있다. 예를 들어, (cons 'left
'right)로 표현된 CONS 함수는 다음과 같은 Cons Cell을 형성한다.
(3) APPEND 함수
APPEND는
뒤의 체인을 복사하여 앞의 체인에 붙임으로써 긴 체인을 만드는 함수이다. 예를
들어, x가 (here today), y가 (gone tomorrow)라는 라스트라 하면 (append x y)는
(here today gone tomorrow)로 결과값이 나온다.
(4) REVERSE 함수
REVERSE는
Cons Cell 체인을 거꾸로 뒤집는 함수이다. 예를 들어, (reverse '(a b c d))는 (d
c b a)를 결과값으로 출력한다.
(5) LAST 함수
LAST는
마지막 Cons Cell을 내보내는 함수이다. 예를 들어, (last '(a b c d))는 마지막
원소인 "d"의 라스트 (d)를 결과값으로 출력한다.
(6) LENGTH 함수
LENGTH는
Cons Cell 체인의 원소의 개수를 내보내는 함수이다. 예를 들어, (length '(a b c
d))는 Cons Cell 체인 원소의 개수 4를 결과값으로 출력한다.
(7) NTHCDR과 NTH
이들은
리스트의 특정 CDR 또는 원소를 추출해 내는 함수이다. 예를 들어, (nthcdr n x)는
X에 대해 n번의 연속적인 CDR을 적용한 결과값을 출력한다. 즉, (nthcdr 2 '(a b
c d))는 (c d)를 결과값으로 내보낸다. 또한 (nth n x)는 0부터 세어 리스트 x의
n째 원소값을 출력한다. 즉, (nth 2 '(a b c d))는 c를 결과값으로 출력한다.
1. CAR 와 CDR
CAR(일반적으로 "카"로 발음함)와 CDR(일반적으로 "크더"로 발음함) 함수는 Cons Cell에서 각각 car와 cdr 포인터를 끄집어내는 함수이다. 예를 들어, (car '(A B C))는 리스트의 첫번째 원소인 A, (cdr '(A B C))는 첫번째 원소를 제외한 리스트 (B C)를 결과값으로 출력한다. 또한 car와 같은 기능을 가진 함수로 first, cdr과 같은 기능을 가진 함수로 rest가 있다.
2. second~tenth 함수
리스트에서 특정 위치에 있는 원소를 끄집어 내기 위한 것으로 second 부터 tenth 까지의 함수가 있다. second 함수를 first(car)와 rest(cdr)를 사용하여 다음과 같이 정의 할 수 있다.
*
(defun second (x)
(first (rest)))
* (defun
second (x)
(car (cdr x)))
1. IF 특수형
IF 조건문은 다음과 같은 구문을 가지고 있다.
|
(IF test then else) |
예를 들어, 100보다 크면 big,
작으면 small이라는 결과값을 출력하는 함수를 IF문을 사용하여 정의하여 보면 다음과
같다.
*
(defun big-number (x)
(IF
(> x 100) 'big 'small))
*
(big-number 37) => SMALL
*
(big-number 175) => BIG
(IF test then)과 같이 else부분이 생략된 경우는 (IF test then NIL)과 같다.
2. AND/OR 조건문
AND와 OR 조건문은 해당 절(Clause)들을 왼쪽에서 오른쪽으로 한번에 한 개씩 evaluation한다. AND는 절이 NIL로 evaluation되면 멈추며, 이때 NIL 값을 출력한다. 그렇지 않은 경우에는 마지막 절의 값을 출력한다. OR는 첫번째로 NIL이 아닌 값을 찾아 출력한다. 그렇지 않은 경우는 NIL을 출력한다.
3. COND 특수형
COND 조건문은 다음과 같은 구문을 가지고 있다.
|
(COND (cond-1 action-1) |
이것은 조건문을 만족하는 결과값이 여러 가지로 나타날 경우 특정 조건에 따른 결과값을 보고자 할 때 사용된다.
(예)
*
(defun my-where-is (x)
(cond
((equal x 'seoul) 'KOREA)
(equal x 'washington) 'USA)))
*
(my-where-is 'seoul) => KOREA
다음과 같은 cond의 표현을 IF 문으로 표시하면 다음과 같다.
*
(cond (test-1 act-1)
(test-2
act-2)
(t
act-3)))
* (IF test-1 act-1
(IF test-2 act-2 act-3))
4. 조건으로서의 T
t를 가진 절은 그것이 수행될 차례가 되면 반드시 수행된다.
(예)
*
(defun make-even (x)
(cond
((doop x) (1+x)
(t x)))
5. 다중실행문을 가진 절
만일 COND 절이 하나 이상의 실행문을 가진 경우에는 모든 실행문이 evaluation 되고 마지막 실행문의 값을 출력한다.
(예)
*
(defun multi-action (x)
(cond ((eq x 'load)
(setq action-state 1)
'act-1)
((eq x 'unload)
(setq action-state 0)
'act-0)
(t nil)))
*
(multi-action 'load) => act-1
*
action-state => 1
스트림은 데이터의 발생원천이나 종착역할을 하는 것으로 화일과의 연결을 나타낸다.
1. 표준스트림
*standard-input* : 입력함수
READ와 같이 스트림인수가 없을 경우에 사용되는 입력스트림이다.
*standard-output*
: 출력함수 PRINT와 같이 스트림인수가 없을 경우에 사용되는 출력스트림이다.
*eooro-output*
: 에러메시지가 보내지는 스트림이다.
*terminal-io* : 키보드와
항상 연결되어 있는 스트림이다.
*query-io* : 프로그램 수행중에
필요한 경우 사용자에게 질의하기 위한 스트림이다.
2. READ 함수
입력스트림으로부터 LISP으로 표현된 것들을 읽는 함수이다.
*
(read) foo
=> FOO
*
(read) (let us take a break)
=> (let us take a break)
3. 문자열(Character String)
문자열은 항상 " "로 닫혀 있으며 그 자체로 evaluation 된다.
(예)
*
"This is a string" => "This is a string"
*
(stringp "AI") => t
4. FORMAT 함수
FORMAT 함수는 문자열을 만들어 주며, 그것을 스트림으로 만들기도 한다.
(예)
*
(format t "This is a string") This is a string
NIL
* (format nil "This
is a string")
"This
is a string"
여기서 FORMAT문 다음에 t인 경우는 *standard-output* 스트림, nil인 경우는 문자열을 출력한다.
5. ~s 명령어
~s문은 문자열 안에 LISP object를 인쇄한 형태로 집어 넣는다.
(예)
*
(format t "~% see ~s and ~s." 'DICK 'JANE)
*
see DICK and JANE.
* NIL
순환함수란 스스로를 호출하는 함수이다. 예를 들어 다음과 같은 함수의 경우를 보기로 하자.
*
(defun count-down (x)
(cond
((zerop x) 0)
(t
(count-down (1-x)))))
이 함수는 인수(Argument)를 1씩 줄이면서 스스로를 호출하고 있다. 순환 template는 다음과 같은 형식을 갖는다.
|
(DEFUN func (x) |
위의 함수를 대응시켜 보면 다음과 같다.
func :
count-down
end-test :
zerop
end-value :
0
reduce :
1-
1. 순환함수 작성 규칙
순환함수를 작성할 때 유의할 점은 다음과 같다.
|
규칙 1 : 언제 멈추어야 할 것인가를
알아야 한다. |
(예)
*
(defun count-element (x)
(cond ((null x) 0)
(t (+1 (count-element (rest x))))))
*
(count-element '(A B))
매크로는 복잡하게 프로그래밍 될 수 있는 것을 유연하게 표현할 수 있도록 하여준다. 매크로는 두 단계로 나누어 진행된다. 첫단계에서는 수행 가능한 중간형태의 일련의 코드를 생성해 내고, 둘째 단계에서는 이 코드를 evaluation하여 매크로의 결과값으로 만들어 낸다. 즉, LISP 인터프리터가 매크로에서는 두 번 evaluation을 한다고 볼 수 있다.
1. LET 매크로
LET 매크로는 지역변수를 binding 하는데 사용되며, 다음과 같은 구문을 가지고 있다.
|
(LET ((var-1 value-1) |
아래의 예에서 지역변수 y는 rev라는 함수 내에서만 의미가 있다.
*
(defun rev (x)
(let
((y (reverse x)))
(list
(first y) (second y))))
*
(rev '(a b c d))
=>
(d c)
2. LET* 매크로
LET이 병렬로 변수를 binding 하는 데에 대하여 LET* 매크로는 순차적으로 변수를 binding 한다. 다음의 예는 LET과 LET*간의 차이를 보여 주고 있다.
*
(setq x 'grape)
* (let ((a
x)
(b
a))
(list
a b) => ERROR : An unbouned variable
*
(let* ((a x)
(b a))
(list a b)) => (grape grape)
1. DOTIMES 매크로
DOTIMES 매크로는 n번 반복해서 처리하고 싶을 때 사용하며, 구문은 다음과 같다.
|
(DOTIMES (var n result) |
다음은 x번 횟수만큼 Hello하고 Stop!으로 끝을 맺고자 할 때의 예이다.
*
(defun say-hello (x)
(dotimes
(i x 'Stop!)
(format
t "~% Hello ~s" i)))
*
(say-hello 3)
Hello
0
Hello 1
Hello 2
Stop!
2. DOLIST 매크로
DOLIST 매크로는 리스트 안에 있는 원소 하나하나에 대하여 반복적으로 처리를 할 때 사용한다. 다음은 리스트 안에 있는 원소 하나하나에 대하여 Hello하고 마지막에 Stop!이라 출력하는 예이다.
|
(DOLIST (var list result) |
(예)
*
(defun say-hello-to (x)
(dolist (p x 'Stop!)
(format "~% Hello ~s!" p)))
*
(say-hello-to '(Sally Dick Jane))
Hello Sally!
Hello
Dick!
Hello Jane!
Stop!
3. DO 매크로
DO 매크로는 여러 변수에 대해
초기값을 주고 일정 양만큼 증감시키면서 반복처리 할 때 사용하며 구문은 다음과
같다.
|
(DO ((var-1 init-1
step-1) |
다음은 DO를 사용한 예이다.
(예)
*
(defun add-up (list-of-numbers)
(do ((x list-of-numbers (cdr x))
(result nil)
(sum 0 (+sum (car x))))
((null
x) sum)
(push (list
(car x) result))))
만일 연속적인 binding을 하려면 DO 대신 DO*를 사용한다.