LISP

5. LISP

 

  리습은 인공지능을 할때 쓰이는 프로그래밍 언어 중 하나이다. 최초로 1958년 MIT의 존 매카시가 개발하였다. 리스프는(LISP)란 이름은 List Processing (리스트 처리) 의 줄임말 이다. 리스프는 여타의 다른 언어들과는 상당히 다르다. 람다 계산법(Lambda Calculus)에 바탕을 두고, 기호 데이터(Symbolic data)를 다루는 문제 풀이에 알맞은 언어로 설계되어 있어 있어, 아톰(Atom)이나 리스트(list) 같은 전혀 새로운 데이터를 쓰고 있다. 리스프는 최초의 개발자 존 매카시가 모든 것을 한꺼번에 개발 한 언어가 아니다. 초창기의 리스프는 산술 계산같은 것이 느린 단점을 지니고 있었고, 사용하기가 조금더 복잡하였다. 하지만, 세월이 지나면서 자신들이 필요한 부분을 보완하고 추가 해가며 발전해 와, 이제는 인공지능에서는 매우 중요한 언어로 자리잡고 있다. 이때문에, 리스프는 대단히 많은 변종들이 존재하며 (ZetaLisp, Franz Lisp, InterLisp 등) , 일반적으로 리스프 라고 하면, 이러한 변종들을 통칭하여 가리킨다.

 

 - Symbolic Expression

 

  위에서도 언급했듯이, Lisp은 전혀 새로운 데이터 타입을 사용한다. Atom 과 List 가 바로 그것이다. 그리고, 이러한 2개를 가리켜 Symbolic Expression 이라고 한다. 그렇다면 이들이 무엇인지 한번 알아보자.

 

1) Atom : Letters(문자 - 영문으로 대소문자 모두)

             Numbers (숫자)

             Characters (*, &, %, ...)

  

2) List : 공백에 의해 구분되는 Atom 또는 다른 리스트들이 괄호 안에 들어가 있는것

            (  (1 2 3 4) , (1 (2 3) 4 ),  ......)

 

  이렇게 2개의 자료형을 사용자가 입려가면, 리스프의 인터프리터(Inerpreter) 는 해당 결과를 화면에 출력한다. Atom을 입력하면, 있는 그대로를 출력하고, List를 입력하면 가장 처음에 나와있는 function definition 을 참조하여, 그에 알맞는 결과를 출력한다.

 

입력 : ( * 10 9 )                         출력 : 90

입력 :  (- (* 10 9 ) ( * 8 10))        출력 : 10

입력 : (list a b c d e)                 출력 : (a b c d e)

입력 : (nth 2 '(a b c))                 출력 : c               (어퍼스트로피 빼먹지 않게 주의)

 

위의 마지막 예제에서 '(a b c) 처럼, 어퍼스트로피가 쓰였다. 이는 (quote (a b c)) 랑 같은 것으로, 괄호 안을 함수로 취급하지 말고 있는 그대로 사용하라(또는 출력하라) 라는 뜻이다. 아래의 예제를 보면 이해가 쉽게 될 것이다.

 

입력 : (quote (+ 1 6))                  출력 : (+ 1 6)

입력 : ( '(a b) )                          출력 : (a b)

 

 

 - Function Definition

 

 리스프도 다른 여타의 언어와 마찬가지로 함수를 정의 하고, 사용 할 수 있다. 함수의 정의법은 아래와 같다.

 

(함수이름 / 함수 변수 목록/ 함수 내에서 수행할 계산)

 

예를드련, 인자 x를 받아서, x의 제곱을 리턴하는 함수는

 

(defun double(x) (* x x)) : x를 인자로, 받고 x를 제곱해서 리턴한다.

 

 

- Condition

 

 조건문으로, 형태는 (cond ( (조건1) (Action)) ( (조건2)(Action)) ( (조건3....

 이런식으로 나간다.

 

 (cond ((< x 0 )(-x)) (t x))  : 만약 x가 0보다 작으면 - x를 출력하고, 0보다 크거나 같으면 그냥 x를 리턴하라.

 (defun (absoulute-value (x) (if(< x 0) ( -x) x)) : absolute-value 라는  함수를 선언한다. 만약 0보다 작으면 - x로 리턴

                                                                     그렇지않으면 그냥 x를 리턴하라. 

 

 

- Binding Variables

 

   (setq <symbol> <form>) : symbol 은 form의 값을 갖게 한다. (단, symbol은 계산 되지 않는다. 어퍼스트로피가 붙은 상황)

   (set <place> <form>) : symbolic expression  <place>를 <form>으로 바꾼다. (<place>는 계산된다.)

   (setf <place> <form>) : <place>가 <symbol>이면 setq와 같이 동작하고, 그렇지 않으면 set과 같이 동작 한다.

 

(setq x 1) = 1

(set a 2 ) = ERROR  (a cannot be evaluated)

(set 'a 2) = 2

(+ x a ) = 3

(setq 1 '(a b)) = (a b)

(set (car 1) p) = p

1 = (p b)                          //(car 1) = a이고, a는 p로 치환되었으므로,  1 = (p, b) 이다.

 

위의 예제를 그대로 setf로 바꾸면 아래와 같다.

 

(setf x 1) = 1

(setf a 2) = 2

(+ a x) = 3

(setf 1 '(a b)) = (a b)

(setf (car1) p) = p

1 = (p b)

 

 

let( (<Symbol> <function>)  (<Symbol2><function2>)(<symbol3 .....)

 

   let은 괄호 안에에서 여러개의 변수를 다른 값에 할당할때에 사용한다.

 

 

- Else

 

  car - return the first element.

  cdr - return the rest element

  cons - constructing a list by its parameter (받은 파라미터들로, 리스트를 새로 만든다.)

  append - attach each parameter to make lise (받은 파라미터들을 연결하여 리스트를 만든다.)

 

  (car  '(a b c d)) : a

  (cdr  '(a b c d)) : b c d

  (first '(a b c d)) : a

  (second '(a b c d)) : b

  (cons 'a '(b c)) : (a b c)

  (cons '(a b) '(c d)) : ( (a b) c d)

  (append '(a b) '(c d)) : (a b c d)

 

 

- Recursion

 

 리습은 함수형 언어 이기때문에, 특정 문제를 풀기 위해서는 recursion을 통해 계속해서 함수를 호출 해 줘야 한다. 하지만, 실제로 해보면 알 수 있듯이 recursion을 만드는 것이 그리 쉬운 것 만은 아니다. 그래서, 재귀의 형태를 만들기 쉽도록 하는 몇가지 방법에 대해서 알아 보자.

 

1) Double-Test Tail Recursion

 

기본 형태는  (Defunc func(x) (cond (endtest_1 endvalue_1)(endtest_2 endvalue_2)(T (func reduced-x))))

 

예제를 보자. 다음의 예제는 인풋으로 들어온 list 또는 atom이 짝수를 포함하고 있는지를 보는 함수 이다.

 

defun anyEvenP(x) ( cond ((null x) nil)((even (car x) T)((t (anyEvenP(cdr x)))))

 

만약, 리스트가 비었으면, nil을 리턴, 그렇지 않고, 리스트의 가장 처음 x가 짝수이면, T(true)를 리턴, 그것도 아니라면 리스트의 맨처음 을 제외한 나머지 부분을 다시 anyEvenP 함수를 재귀적으로 호출한다.

 

 

2) Single-Test Tail Recursion

 

  위에서 했던, Doble-Test Tail 이 2개의 조건으로 체크를 했다면, 이것은 한개로 체크를 하는 것이다. 따로 예제는 들지 않겠다.

 

3) Single-Test Augmenting Recursion (한개의 테스트로 값을 늘려가는)

 

  조건은 한개지만, 리커션이 호출될 때 마다, 특정값이 증가 하도록 만드는 리커션이다. 흔히 1+2+3+4+ ... 를 리커션으로 구할때 각 +와 + 사이의 값이 1씩 증가 하나. 이처럼 리커션이 호출될 때마다 해당 항의 값이 증가하는 재귀함수를 가리킨다.

 

4) Conditional Augmentaton (조건부 값 상승)

 

  조건에 따라서, 리커션의 각 항을 값을 늘리거나 늘리지 않을때 사용하는 리커션이다. 함수 howManyNum 이라는 것이 있을때, 리스트에서 숫자의 갯수를 리턴한다고 하자. 그러면, 리스트가 {A,B, 3, 5} 일때 값을 2를 리턴해야 한다. 이때에 조건으로 숫자일때에는 값을 증가시키고, 숫자가 아닐때에는 값을 증가시키지 않는 방식을 취한다.