A Gentle Introduction To Symbolic Computation: http://www.cs.cmu.edu/~dst/LispBook/
읽으면서 정리해보자
서문 ¶
- 리스프는 인공지능 연구의 주요 언어로 유명하다
- 염두에 둔 독자: 프로그래밍 입문하는 학생 / 심리학자, 언어학자, 컴퓨터 과학자 등 인공지능에 관심 있는 사람들 / 취미로 컴퓨터 하는 사람
- 책의 구성
- 1, 2장: 상자, 화살표 표기로 기초적인 함수, 함수 합성 설명
- 3장: EVAL 표기
- 8장까지는 부수효과 없는 프로그래밍
- 9장: 입출력
- 10장: ordinary variables, generalized variables, destructive sequence operations.
- 11장: 반복(DO, DO*)
- 12장: 구조
- 13장: 배열, 해시테이블, property list
- 14장: 매크로, 컴파일, lexical scoping과 dynamic scoping의 차이
- 1, 2장: 상자, 화살표 표기로 기초적인 함수, 함수 합성 설명
- 간략화
- Common Lisp는 복잡한 언어라 적당히 간략화한 것들이 있다
- 1+와 1-는 이름이 혼란스러워 뺐다
- EQUAL을 주로 사용. EQ, EQL, EQUALP, =는 고급 주제에서 논의
- 잘 알려지지 않은 PUSHNEW 같은 원시형을 사용하느니 함수를 좀 더 풀어쓴 것이 몇 군데 있다
- 가장 고급 주제인 multiple value나 package system은 다루지 않는다
- Common Lisp는 복잡한 언어라 적당히 간략화한 것들이 있다
1장 요약 ¶
- 산술 함수: +, -, *, /, ABS, SQRT
- 숫자형: 정수(integer), 부동소수점수(floating number), 비율수(ratio)
- 정수로 산술 연산을 하면 결과는 정수 또는 비율수다.
- 3/6 = 1/2 <- 이게 ratio
- 3/6.0 = 0.5
- 정수로 산술 연산을 하면 결과는 정수 또는 비율수다.
- 심볼: 숫자 이외의 또다른 자료형
- 특수 심볼: T는 참 또는 긍정, NIL은 거짓 또는 부정
- T 또는 NIL을 반환하는 함수는 술어식(predicate)
- 특수 심볼: T는 참 또는 긍정, NIL은 거짓 또는 부정
- 기본적인 내장 함수들
- NUMBERP: 데이터가 숫자형인가?
- SYMBOLP: 데이터가 심볼인가?
- 숫자형 전용 술어식들: ZEROP(영), ODDP(홀수), EVENP(짝수)
- 크기 비교: <. >
- 항등 비교: EQUAL
- 내장 함수들은 원시 함수(primitive function) 또는 그냥 primitive라고 부른다
- 입력에서 1을 더하거나 빼는 1+, 1- 함수가 있지만 이 책에선 쓰지 않겠다. 헷갈림
- 부정: NOT(NIL은 T로, NIL이 아닌 모든 것은 NIL으로)
- 그럼 NOT(NOT(5))는 5가 아니라 T인가?
- 그럼 NOT(NOT(5))는 5가 아니라 T인가?
- NUMBERP: 데이터가 숫자형인가?
- 함수의 인자 개수
- ODDP의 인자는 딱 1개, EQUAL은 2개
- +, -, *, /의 인자 개수는 여러 개
- +의 인자가 2, 3, 4면 2랑 3부터 더하고 여기에 4를 더한다
- -, /의 인자가 하나인 경우
- -의 인자가 n이면 결과는 0에서 n 뺀 거
- /의 인자가 n이면 결과는 1에서 n 나눈 거
- -의 인자가 n이면 결과는 0에서 n 뺀 거
- 타 언어는 산술 연산이 이항 연산이고 2+3+4는 단순히 (2+3)+4로 처리되는데
- 리스프는 + 자체가 n항 연산이 될 수 있다는 건가???
- +의 인자가 2, 3, 4면 2랑 3부터 더하고 여기에 4를 더한다
- ODDP의 인자는 딱 1개, EQUAL은 2개
- 오류: 3이랑 FRED를 더할 수 없고, EQUAL의 인자를 한 개만 넘기면 안 되고, 0으로 나누면 안 되고.
1장 고급 주제 ¶
- 리스프의 역사
- 1956년 Dartmouth 대학에서 여름에 열린 인공지능 관련 연구 모임에서 존 매카시가 "list processing"이란 기법을 배웠다
- 1950년대에는 어셈블리어로 프로그래밍을 했지
- "list processing"을 발표한 사람들은 심볼과 리스트를 다루는 보다 추상적인 IPL이란 언어를 만들었다
- 그 문법이 어셈블리어에 가까워서 괴상했다
- 1950년대에는 어셈블리어로 프로그래밍을 했지
- 한편 수치적 계산에 특화된 FORTRAN이 개발되고 있었다
- 어셈블리어는 Y = (X + 5) * 10 하려면 LOAD Y, X -> ADD Y, 5 -> MULT Y, 10 라고 써야 하는데
- FORTRAN은 그냥 Y = (X + 5) * 10 이라고 쓰면 된다. 표현식(expression)의 작성이 가능하다는 뜻
- 그 당시에는 이 개념이 혁명이였다더라
- 존 매카시: 나도... 나도 이런 거 만들 거야!
- FORTRAN에 리스트 조작을 위한 특별한 하위루틴들을 추가하면 어떨까?
- IBM의 Herbert Gelerntner와 Carl Gerberich가 이 아이디어를 따와 FLPL을 만듦
- 매카시는 IPL, FORTRAN, FLPL을 토대로 LISP를 설계
- FORTRAN에 리스트 조작을 위한 특별한 하위루틴들을 추가하면 어떨까?
- 어셈블리어는 Y = (X + 5) * 10 하려면 LOAD Y, X -> ADD Y, 5 -> MULT Y, 10 라고 써야 하는데
- Lisp 1.5는 처음으로 널리 퍼진 리스프 방언
- 1960년대 중반부터 온갖 리스프 방언이 생기기 시작
- MacLisp, Interlisp, Stanford Lisp 1.6, UCI Lisp...
- 모두 Lisp 1.5을 확장한 것. 하지만 서로 호환이 하나도 안 된다
- MacLisp, Interlisp, Stanford Lisp 1.6, UCI Lisp...
- 1970년대: ALGOL계 언어의 특징들과 리스프의 문법을 결합한 Scheme이 나왔어요
- 그리고 또다시 Scheme의 방언들이 우후죽순 생겨나기 시작했다
- 그리고 또다시 Scheme의 방언들이 우후죽순 생겨나기 시작했다
- 1980년대: 널리 쓰이는 리스프 방언만 해도 수두룩한데... 뭘 써야 하지?
- 만국공용어를 만들자!!!
- 1984년 Common Lisp 초안 발표
- 학술계에서도 산업계에서도 빠르게 주류로 성장
- 지금은 Common Lisp 때문에 Scheme 빼고 거진 다 죽었지렁
- 만국공용어를 만들자!!!
- 1956년 Dartmouth 대학에서 여름에 열린 인공지능 관련 연구 모임에서 존 매카시가 "list processing"이란 기법을 배웠다
- 많은 프로그래밍 아이디어가 리스프에서 출발할 것
- 인터프리터 함수와 컴파일 함수의 결합
- 함수 재귀 호출
- 소스 수준 추적 & 디버깅
- 문법 지향 편집기
- 오늘날의 리스프는 함수형, 객체지향, 병렬 프로그래밍 연구의 선두 주자
- 인터프리터 함수와 컴파일 함수의 결합
2장 요약 ¶
- Lisp는 List Processor라는 뜻
- 리스트는 가장 다재다능한(versatile) 타입이다
- 집합, 테이블, 그래프, 영어 문장 등 뭐든지 표현 가능
- 함수도 리스트로 표현 가능
- 집합, 테이블, 그래프, 영어 문장 등 뭐든지 표현 가능
- 모든 리스트는 두 가지 형태를 가진다
- printed representation
- 사람이 키보드로 쓰기 편한 형식
- 사람이 키보드로 쓰기 편한 형식
- internal representation
- 실제로 메모리에 거주하는 형식
- 실제로 메모리에 거주하는 형식
- 리스트의 예:
(RED GREEN BLUE),(AARDVARK),(2 3 5 7 11 13 17)
- 메모리에서의 실제 형태: 셀(cell)마다 원소를 가리키는 포인터, 다음 셀을 가리키는 포인터를 가진다
- 마지막 셀은 NIL을 가리킨다
[PNG image (5.19 KB)]
- 포인터는 대개 4바이트이므로 셀은 8바이트
- 중첩 리스트
((BLUE SKY) (GREEN GRASS) (BROWN EARTH))
[PNG image (13.3 KB)]
- 리스트의 길이: 원시 함수 LENGTH를 이용
- 빈 리스트는 NIL로 표현
- 사실 NIL은 ()다. NIL과 빈 리스트는 동치
- NIL은 심볼이자 리스트인 유일한 존재
- 리스트의 원소 얻기
- FIRST, SECOND, THIRD 함수: 첫 번째, 두 번째, 세 번째 원소
- REST 함수: 첫 번째를 제외한 나머지 리스트
- FIRST는 CAR와 같고 REST는 CDR과 같다.
- CAR, CDR이라는 이름은 리스프가 처음에 트랜지스터도 없어서 진공관 쓰는 컴퓨터에서 작동할 때 쓴 말
- CAR: Contents of Address portion of Register
- CDR: Contents of Decrement portion of Register (카우더cou-der라고 발음)
- 요즘 컴퓨터에는 맞지 않지만 아직도 쓴단다
- CADR: CDR 다음에 CAR (kae-der라고 발음)
- CDAR: CAR 다음에 CDR (cou-dar)
- CADDR: CDR 다음에 CDR 다음에 CAR (ka-dhi-der)
- 이게 뭐야 ㅡㅡ
[PNG image (46.71 KB)]
- CAR와 CDR에 NIL을 입력하면 NIL이 출력된다
- 에러가 아니구요???
- 이게 더 좋대
- 에러가 아니구요???
- CAR, CDR이라는 이름은 리스프가 처음에 트랜지스터도 없어서 진공관 쓰는 컴퓨터에서 작동할 때 쓴 말
- FIRST, SECOND, THIRD 함수: 첫 번째, 두 번째, 세 번째 원소
- 리스트 생성
- CONS는 한 데이터와 리스트를 받아서 그 데이터를 첫 번째 원소로 끼워넣은 리스트를 반환한다
- x = CONS of (CAR of x) and (CDR of x)
- LIST는 임의 개수의 원소를 받아 그것들의 리스트를 생성한다
- CONS는 한 데이터와 리스트를 받아서 그 데이터를 첫 번째 원소로 끼워넣은 리스트를 반환한다
- 리스트 술어식
- LISTP: 입력이 리스트인가?
- CONSP: 입력이 cons cell인가?
- LISTP와 비슷하지만, NIL은 리스트인 반면 cons cell이 아니다
- LISTP와 비슷하지만, NIL은 리스트인 반면 cons cell이 아니다
- ATOM: 입력이 cons cell이 아닌가? (CONSP의 부정)
- NULL: 입력이 NIL이면 T 반환. NOT과 동치.
- 논리 연산에는 NOT을, 리스트 연산에는 NULL을 사용하는 관례가 있다
- 논리 연산에는 NOT을, 리스트 연산에는 NULL을 사용하는 관례가 있다
- LISTP: 입력이 리스트인가?
- printed representation
2장 고급 주제 ¶
- 리스트를 이용한 1진법 산술
- 0 = NIL, (X) = 1, (X X) = 2, (X X X) = 3...
- REST는 1 빼기. 단 0 빼기 1은 0
- LENGTH는 실제 숫자로 변환
- 이걸 어따 써먹죠
- 0 = NIL, (X) = 1, (X X) = 2, (X X X) = 3...
- 진리스트(proper list)는 NIL로 끝나는 리스트
- NIL로 안 끝나는 리스트는? dotted list
- A와 B의 CONS :
(A .<- dotted pair.png "B)")
- LIST는 진리스트만 생성 가능. CONS는 Dotted list를 만들 수 있다
- NIL로 안 끝나는 리스트는? dotted list
- 순환 리스트(circular list)도 있다
- 원소 A, B, C가 있는데 C를 포함하는 cell이 다시 A를 포함하는 cell을 가리키면?
- sharp-equal notation:
#1=(A B C . #1#)라고 표기한다
- 원소 A, B, C가 있는데 C를 포함하는 cell이 다시 A를 포함하는 cell을 가리키면?
- (A B C . D)의 LENGTH는 4가 아니라 3
- 순환 리스트의 LENGTH는 무한 루프
