ãã®è¨äºã¯Lisp Advent Calendar 2015 ã®10æ¥ç®ã¨ãã¦æ¸ããã¾ããã
![ããã«ã¼ã¨ç»å®¶ ã³ã³ãã¥ã¼ã¿æ代ã®åµé è
ãã¡ ããã«ã¼ã¨ç»å®¶ ã³ã³ãã¥ã¼ã¿æ代ã®åµé è
ãã¡](https://images-fe.ssl-images-amazon.com/images/I/511SV9NXW2L._SL160_.jpg)
ããã«ã¼ã¨ç»å®¶ ã³ã³ãã¥ã¼ã¿æ代ã®åµé è ãã¡
- ä½è : ãã¼ã«ã°ã¬ã¢ã ,Paul Graham,å·åå²æ
- åºç社/ã¡ã¼ã«ã¼: ãªã¼ã 社
- çºå£²æ¥: 2005/01/01
- ã¡ãã£ã¢: åè¡æ¬
- è³¼å ¥: 109人 ã¯ãªãã¯: 4,884å
- ãã®ååãå«ãããã° (582件) ãè¦ã
ハッカーと画家ã§æåãªãã¼ã«ã»ã°ã¬ã¢ã æ°ããã¸ã§ã³ã»ããã«ã¼ã·ã¼ã®1960å¹´ã®Lispã®ãªãªã¸ãã«è«æãCommon Lispã§è§£èª¬ããè¨äºãæ¸ãã¦ãããã¨ã«æè¿ã«ãªã£ã¦æ°ä»ããã
- The Roots of Lisp (www.paulgraham.com) (ソースコード)
ããªãå¤ãè¨äºã§(2002å¹´)ãå 容ã¯Wikipediaの純LISPの項目ã¨éãªãã¨ãããå¤ããããããªããç¾å¨ã§ãé常ã«éè¦ãªè¨äºãªã®ã§ãèªåã®åå¼·ã®ããã«ã訳ããã¨ã«ãããå¥è¨³ã¨ãã¦ã¯lionfan氏による和訳ããããããã¡ãã¯åæ¸ãé¨åã®ã¿ã§ããã
ãã®è¨äºã§ã¯Lispãä¸ããå®ç¾©ãã¦ãevalãå®è£
ããã¨ããã¾ã§ã解説ãã¦ãããã²ã¨ãã³evalãå®è£
ãããã¨ãããã°ã©ã ããããã段éã§è©ä¾¡ã§ããããã«ãªãã®ã§ãããã°ã©ã ãå¤æãã¦ããè©ä¾¡ãããã§ãããããã¯æ§æãæ°ãã«å®ç¾©ãããã¨ã«ä»ãªããªãã®ã§ããã®ä¸ã«ã©ã®ãããªè¨èªã§ãä½ããã¨ãã§ãããã¤ã¾ããæãåºæ¬çãªè¦ç´ ããã¡ã¿ããã°ã©ãã³ã°ã®åå°ãä½ãã¨ããã¾ã§ã解説ãããã¨ãç®çã¨ãªã£ã¦ããã
ãã®è¨äºãç解ã§ããã°ãä»ã®ã©ã®ãããªè¨èªãè¨ç®æ©ã®ä¸ã«ããèªåèªèº«ã§Lispãå®è£
ã§ããããã«ãªããä¸ããããã°ã©ãã³ã°è¨èªãä½ãã¨ããçµé¨ã¯é常ã«éè¦ãªã®ã§ããã²ä¸åº¦èªåèªèº«ã®æã§Lispãä½ã£ã¦ã¿ã¦ã»ããã
Lispã®èµ·æº (The Roots of Lisp)
1960å¹´ãã¸ã§ã³ã»ããã«ã¼ã·ã¼ã¯é©ãã¹ãè«æãçºè¡¨ãããå½¼ã¯ãã®è«æã§ãã¦ã¼ã¯ãªãããå¹¾ä½å¦ã§ãã£ãã®ã¨åããããªãã¨ãããã°ã©ãã³ã°ã®ä¸çã§ãã£ã*1ã å½¼ã¯å°æ°ã®åç´ãªãªãã¬ã¼ã¿ã¨ãé¢æ°ã®ããã®è¨æ³ãä¸ããããããã©ã®ããã«ãã¦ããã°ã©ãã³ã°è¨èªå ¨ä½ãæ§ç¯ã§ãããã示ãããå½¼ã¯ãã®è¨èªããªã¹ãå¦ç(LISt Processing)ã®æå³ãè¾¼ãã¦Lispã¨å¼ãã ããªããªãå½¼ã®ã¢ã¤ãã£ã¢ã®ä¸æ ¸ã®ä¸ã¤ã¯ããªã¹ãã¨å¼ã°ããåç´ãªãã¼ã¿æ§é ãã³ã¼ãã¨ãã¼ã¿ã®ä¸¡æ¹ã®ããã«ä½¿ããã¨ã ã£ãããã ã
ããã«ã¼ã·ã¼ãä½ãçºè¦ããã®ããç解ãããã¨ã¯ããã åã«ã³ã³ãã¥ã¼ã¿å²ä¸ã®ãã¤ã«ã¹ãã¼ã³ã¨ãã¦éè¦ãªã ãã§ãªããä»å¾ããã°ã©ãã³ã°ã¨ãããã®ãã©ã®ããã«çºå±ãã¦ããã®ããèããä¸ã§ã®ã¢ãã«ã¨ãã¦ä¾¡å¤ããããããã¾ã§ã®ã¨ãããæ¬å½ã®æå³ã§æ··ããããªãä¸è²«ãã¦ç¶ç¶ãã¦ããããã°ã©ãã³ã°ã¢ãã«ã¯2系統ããããã«è¦ãããããªãã¡ãCã¢ãã«ã¨Lispã¢ãã«ã ããããã¯ãã®éã«æ²¼å°ãã¯ããã§ãã³ãã2ã¤ã®å±±ã®ããã«è¦ãããã³ã³ãã¥ã¼ã¿ããããã¯ãã«ã«æé·ããã«ã¤ãã¦ãçºå±ãç¶ããæ°ããè¨èªéã¯å¾ã
ã«Lispã®å±±ã®æ¹ãç®æãã¦æ²¼å°ã®ä¸ã移åãã¦ãã¦ããã
éå»20å¹´éãæ°ããããã°ã©ãã³ã°è¨èªãã¤ããã¨ãã®äººæ°ã®ã¬ã·ãã¯ã¨ããã¨ãåºæ¬çã«ã¯Cã¢ãã«ãæ¡ç¨ãã¦ãLispã¢ãã«ããæççã«åçåä»ããã¬ãã¼ã¸ã³ã¬ã¯ã·ã§ã³ã®ãããªãã¼ããåã£ã¦ãã¦ã¯ãã£ã¤ããã¨ãããã®ã ã£ãã
ãã®è¨äºã§ç§ã¯ãå¯è½ãªéãåç´ãªè¨èã§ããã«ã¼ã·ã¼ãä½ãçºè¦ããã®ãã説æããã¤ããã§ãããããã§å¤§äºãªã®ã¯ãåã«èª°ãã40å¹´åã«çºè¦ããèå³æ·±ãçè«çãªçµæã«ã¤ãã¦å¦ã¶ãã¨ã§ã¯ãªããä»ããããã°ã©ãã³ã°è¨èªéãå°æ¥çã«ã©ããç®æãã¦ããã®ãã示ããã¨ã ãLispãå¥å¦ã«è¦ããã®ã¯(å®éã«ã¯ãããLispã®ç¹è³ªã決å®ã¥ãã¦ããã®ã ã)ããLispãLispèªèº«ã«ãã£ã¦æ¸ãããã¨ãããã¨ã ãããã«ãã£ã¦ããã«ã¼ã·ã¼ãä½ã示ããã¨ããã®ããç解ããããã«ãæã ã¯å½¼ã®æ°å¦çè¨æ³ãå®è¡å¯è½ãªCommon Lispã³ã¼ãã«ç½®ãæããªãããå½¼ã®è¶³è·¡ããã©ã£ã¦ãããã¨ã«ãããã
7ã¤ã®åå§ãªãã¬ã¼ã¿
ã¾ãå§ãã«å¼ãå®ç¾©ãããå¼ã¯ã¢ãã ããªã¹ãã®ã©ã¡ããã§ãããã¢ãã ã¯æåã®ä¸¦ã³ã§ãã(ä¾: foo
)ããªã¹ãã¯0å以ä¸ã®å¼ããæãã空ç½ã§åºåãããæ¬å¼§ã§ããããã¦ãããããã§ããã¤ãå¼ã®ä¾ã示ãã
foo () (foo) (foo bar) (a b (c) d)
æå¾ã®å¼(a b (c) d)
ã¯4ã¤ã®è¦ç´ ãæã¤ãªã¹ãã ãã3çªç®ã®è¦ç´ (c)
ã¯ããèªä½ã1ã¤ã®è¦ç´ ãæã¤ãªã¹ãã«ãªã£ã¦ãããã¤ã¾ãããªã¹ãã¯å
¥ãåã«ã§ããã
ç®è¡å¼1 + 1
ãå¤2
ãæã¤ããã«ãæå¹ãªLispå¼ãã¾ãå¤ãæã¤ãå¼eãå¤vãçºçãããã¨ããããããeãvãè¿ããã¨å¼ã¶ãå¼ããå¤ãåãåºããã¨ãè©ä¾¡ã¨å¼ã¶ãä¾ãã°ãå¼eãè©ä¾¡ããçµæãå¤vãå¾ããã®ããã«è¨ãã
次ã®ã¹ãããã¯ãã©ã®ãããªç¨®é¡ã®å¼ãããããããããã¦ããããã©ã®ãããªå¤ãè¿ãããå®ç¾©ãããã¨ã§ããã
ããå¼ããªã¹ãã§ããã¨ãããã®ãªã¹ãã®æåã®è¦ç´ ããªãã¬ã¼ã¿ã¨å¼ã³ããã以éã®è¦ç´ ãå¼æ°ã¨å¼ã¶ãä»ããæã
ã¯7ã¤ã®åå§ãªãã¬ã¼ã¿ãå®ç¾©ãã¦ãããããªãã¡ãquote
ãatom
ãeq
ãcar
ãcdr
ãcons
ãããã¦cond
ã®7ã¤ã ããããã¯æ°å¦ã§ããå
¬çã®ãããªå½¹å²ãæã¤ã
1. quote
(quote x)
ã¯x
ãè¿ããèªã¿ãããã®ããã(quote x)
ã'x
ã¨ç¥è¨ãããã¨ã«ããã
(quote a) ; => a 'a ; => a (quote (a b c)) ; => (a b c)
2. atom
(atom x)
ã¯x
ãã¢ãã ã¾ãã¯ç©ºãªã¹ãã®ã¨ãã«ã¢ãã t
ãè¿ãããã以å¤ã§ã¯ç©ºãªã¹ã()
ãè¿ããLispã§ã¯æ
£ç¿çã«ãççå¤ã表ãéã¯ãã¢ãã t
ãçã¨ãã空ãªã¹ããå½ã¨ããã
(atom 'a) ; => t (atom '(a b c)) ; => () (atom '()) ; => t
ãã¦ãä»ãæã
ã¯ãã®å¼æ°ãè©ä¾¡ããããããªãªãã¬ã¼ã¿atom
ãæã«å
¥ããã®ã§ãquote
ãä½ã®ããã«ä½¿ãããã®ãã示ããã¨ãã§ããããã®ç®çã¨ã¯ããªã¹ããquoteãããã¨ã§ãã®ãªã¹ããè©ä¾¡ããå®ããã¨ã§ãããatomã®ãããªãªãã¬ã¼ã¿ã«ãquoteããã¦ãªããªã¹ããå¼æ°ã¨ãã¦ä¸ããããå ´åãããã¯ã³ã¼ãã¨ãã¦æ±ãããã
(atom (atom 'a)) ; => t
éã«ãquoteããããªã¹ãã¯è©ä¾¡ããå®ããããããåã«ãªã¹ãã¨ãã¦æ±ãããããããã£ã¦ã次ã®å ´åã¯2è¦ç´ ã®ãªã¹ãã«ãªããatomã«ãããã¹ãã®çµæã¯å½ã«ãªãã
(atom '(atom 'a)) ; => ()
ããã¯ã¡ããã©è±èªã«ãããå¼ç¨ç¬¦(quote)ã®ä½¿ãæ¹ã¨ä¼¼ããããªãã®ã ãåã«Cambridgeã¨æ¸ãã¨ããã¯ãããµãã¥ã¼ã»ããå·ã®äººå£9ä¸äººã®è¡ãã ããå¼ç¨ç¬¦ãã¤ãã¦"Cambridge"
ã¨æ¸ããã¨ã§ã9æåã®è±åèªãã«ãªãã®ã ãã¤ã¾ãå
·ä½çãªæå³ãæã¤è¨è¿°å
容ãã表è¨ä¸ã®æååã¸ã¨è¦ç¹ãã·ããããã
ä»ã®ããã°ã©ãã³ã°è¨èªã¯quoteã®ãããªä»çµã¿ãã»ã¨ãã©æããªãã®ã§ãã¡ãã£ã¨ç°è³ªãªæ¦å¿µã«æãããããããªãããããã¯Lispãæã¤æãç¬ç¹ãªç¹å¾´ã®ä¸ã¤ã¨å¯æ¥ã«çµã³ã¤ãã¦ããããã®ç¹å¾´ã¨ã¯ããªãã¡ãã³ã¼ãã¨ãã¼ã¿ããªã¹ãã¨ããåããã¼ã¿æ§é ããåºæ¥ã¦ãããquoteãªãã¬ã¼ã¿ãã³ã¼ãã¨ãã¼ã¿ãåºå¥ããæ¹æ³ã§ããã¨ãããã¨ã ã
3. eq
æ¯è¼ã®ããã®ãªãã¬ã¼ã¿ã(eq x y)
ã¯x
ã¨y
ã®å¤ãåãã¢ãã ãã両æ¹ã¨ã空ãªã¹ãã§ããã¨ãã«t
ãè¿ãããã以å¤ã®ã¨ãã¯()
ãè¿ãã
(eq 'a 'a) ; => t (eq 'a 'b) ; => () (eq '() '()) ; => t
4. car
(car x)
ã¯x
ã®å¤ããªã¹ãã§ããã¨ãã¦ããã®ãªã¹ãã®æåã®è¦ç´ ãè¿ãã
(car '(a b c)) ; => a
5. cdr
(cdr x)
ã¯x
ã®å¤ããªã¹ãã§ããã¨ãã¦ããã®ãªã¹ãã®æåã®è¦ç´ ãé¤ããæ®ãã®å
¨ã¦ã®è¦ç´ ãè¿ãã
(cdr '(a b c)) ; => (b c)
6. cons
(cons x y)
ã¯y
ã®å¤ããªã¹ãã§ããã¨ãã¦ãx
ã®å¤ã«y
ã®å¤ã®è¦ç´ ãç¶ããããªãªã¹ããè¿ãã
(cons 'a '(b c)) ; => (a b c) (cons 'a (cons 'b (cons 'c '()))) ; => (a b c) (car (cons 'a '(b c))) ; => a (cdr (cons 'a '(b c))) ; => (b c)
7. cond
æ¡ä»¶åå²ã®ããã®ãªãã¬ã¼ã¿ã(cond (p1 e1) ... (pn en))
ã¯ä»¥ä¸ã®ããã«è©ä¾¡ããããp1
ããpn
ã¾ã§ã®å¼ãé çªã«è©ä¾¡ããã¦ãããåæ¡ä»¶å¼pi
ã®å¤ãt
ã«ãªã£ãæç¹ã§ãããã¨å¯¾å¿ããei
å¼ãè©ä¾¡ããããã®å¤ãcondå¼å
¨ä½ã®å¤ã¨ãã¦è¿ãããã
(cond ((eq 'a 'b) 'first) ((atom 'a) 'second)) ; => second
7ã¤ã®åå§ãªãã¬ã¼ã¿ã®ãã¡ãquoteã¨condãé¤ã5ã¤ã§ã¯ãã®å¼æ°ã¯å¸¸ã«è©ä¾¡ããã*2ã ãã®ç¨®ã®ãªãã¬ã¼ã¿ãé¢æ°(function)ã¨å¼ã¶ã
é¢æ°ã®è¡¨è¨æ³
次ã«ãæ°ããªé¢æ°ãè¨è¿°ããããã®è¨æ³ãå®ç¾©ãããé¢æ°ã¯(lambda (p1 ... pn) e)
ã®ããã«è¨è¿°ããããããã§p1 ... pn
ã¯ãããããã©ã¡ã¼ã¿ã¨å¼ã°ããã¢ãã ã§ãããe
ã¯ä¸ã¤ã®å¼ã§ããã(åãã©ã¡ã¼ã¿pi
ã¯å¼e
ã®å
é¨ã§åç
§ã§ãã)
((lambda (p1 ... pn) e) a1 ... an)
ã®ããã«ãé¢æ°ããªã¹ãã®æåã®è¦ç´ ã«ç½®ãå¼ãé¢æ°å¼ã³åºãã¨å¼ã¶ããã®å¤ã¯ä»¥ä¸ã®ããã«è¨ç®ããããã¾ãåå¼æ°ai
ãè©ä¾¡ãããã次ã«ãåãã©ã¡ã¼ã¿pi
ã®å¤ã対å¿ããå¼æ°ai
ã®å¤ã«ç½®ãæããããããããé¢æ°æ¬ä½é¨åe
ãè©ä¾¡ãããã
((lambda (x) (cons x '(b))) 'a) ; => (a b) ((lambda (x y) (cons x (cdr y))) 'z '(a b c)) ; => (z b c)
次ã®å¼ã®ããã«ã
(f a1 ... an)
å¼ã®ç¬¬ä¸è¦ç´ ãåå§ãªãã¬ã¼ã¿ã§ãªãã¢ãã f
ã§ãfã®å¤ãé¢æ°(lambda (p1 ... pn) e)
ã§ãããªãããã®å¼ã®å¤ã¯
((lambda (p1 ... pn) e) a1 ... an)
ã®å¤ã¨ãªããè¨ãæ¿ãããªãããã©ã¡ã¼ã¿ã¯å¼ã®ä¸ã§å¼æ°ã¨ãã¦ä½¿ãããã®ã¨åæ§ã«ãªãã¬ã¼ã¿ã¨ãã¦ã使ãããããä¾ãã°ã次ã®å¼ã«ãããf
ã¯ã'a
ãconsããã¨ããé¢æ°ã«ãã£ã¦ç½®ãæãããããªãã¬ã¼ã¿ã¨ãã¦'(b c)
ã«å¯¾ãã¦ä½ç¨ããã
((lambda (f) (f '(b c))) (lambda (x) (cons 'a x))) ; => (a b c) ;; è¨³æ³¨ï¼ ãã®ã³ã¼ããCommon Lispã§åããããã«ã¯fããªãã¬ã¼ã¿ã§ãããã¨ã宣è¨ããããã«funcallãå¿ è¦ã«ãªãã ;; Common Lispã§ã¯ãã©ã¡ã¼ã¿ã¨ãªãã¬ã¼ã¿ã§ã¯åå空éãç°ãªãããã ã ((lambda (f) (funcall f '(b c))) (lambda (x) (cons 'a x)))
ããã¨ã¯ã¾ãå¥ã«ãé¢æ°ãèªåèªèº«ãåç §ã§ããããã«ãã表è¨æ³ããããããã«ãã£ã¦å帰é¢æ°ãå®ç¾©ããã®ã容æã«ãªã*3ã ãã®è¨æ³ã¯æ¬¡ã®ãããªãã®ã ã
(label f (lambda ( p1 ... pn ) e))
ããã¯ä¸ã¤ã®é¢æ°ã表ãã¦ãããåºæ¬çã«ã¯(lambda ( p1 ... pn ) e)
ã®ããã«æ¯ãèãã®ã ããããã«å ãã¦ãf
ãé¢æ°æ¬ä½e
ã®ä¸ã§ãããããã®é¢æ°ã®ãã©ã¡ã¼ã¿ã§ãããã®ããã«ç¾ããã¨ãããã®fã¯ãã®labelå¼èªä½ã¸ã¨è©ä¾¡ãããã¨ããæ§è³ªãæã£ã¦ããã
ä¾ãã°ãå¼x
ãã¢ãã y
ããªã¹ãz
ãå¼æ°ã¨ãã¦åããzä¸ã«(ä»»æã®æ·±ãã§)åºç¾ããyãxã«ç½®ãæãããªã¹ããè¿ãé¢æ°(subst x y z)
ãå®ç¾©ãããã¨ããã
(subst 'm 'b '(a b (a b c) d)) ; => (a m (a m c) d)
ãã®é¢æ°ã¯ä»¥ä¸ã®ããã«è¡¨è¨ã§ããã
(label subst (lambda (x y z) (cond ((atom z) (cond ((eq z y) x) ('t z))) ('t (cons (subst x y (car z)) (subst x y (cdr z)))))))
ããã§ãf = (label f (lambda ( p1 ... pn ) e))
ã次ã®ããã«ç¥è¨ããã
(defun f ( p1 ... pn ) e)
ãããããã¨ã§ãsubstã®å®ç¾©ã¯ãããªãã(è¨³æ³¨ï¼ Common Lispã«ã¯ãã®labelè¨æ³ã¯ãªãã®ã§ãå®éã«åãã®ã¯ä»¥ä¸ã®ã³ã¼ãã¨ãªãããªããsubstã¯çµè¾¼ã¿é¢æ°ã¨ãã¦æ¢ã«å®ç¾©ããã¦ãããããsubst.
ã¨ç½®ãæããããã ãã以ä¸ã§å®ç¾©ãã¦ããevalã®å
é¨ã§ã¯labelè¨æ³ãæ±ãã)
(defun subst. (x y z) (cond ((atom z) (cond ((eq z y) x) ('t z))) ('t (cons (subst. x y (car z)) (subst. x y (cdr z))))))
ã¡ãªã¿ã«ãããã§condå¼ã®ããã©ã«ãç¯ãã©ããã£ã¦æå®ããããåºã¦ãã¦ãããæ¡ä»¶å¼ã't
ã§ãããããªç¯ã¯å¸¸ã«æåãããå¾ã£ã¦ã
(cond (x y) ('t z))
ã¯ä»ã®è¨èªã§ããã¨ããã®if x then y else z
ã¨ç価ã§ããã
ããã¤ãã®è£å©é¢æ°
ããã¾ã§ã«æã
ã¯é¢æ°ã®è¡¨è¨æ³ãæã«å
¥ããã®ã§ã7ã¤ã®åå§ãªãã¬ã¼ã¿ã使ã£ã¦ãæ°ããé¢æ°ãå®ç¾©ãã¦ãããã¨ã«ãããã¾ãã¯ãããã¤ãã®å
±éãããã¿ã¼ã³ã«çç¥å½¢ãå°å
¥ãããã¨ã§ä¾¿å©ã«ãªãã ãããããã§ãcarã¨cdrã®çµåãã«å¯¾å¿ããçç¥å½¢ã¨ãã¦cxxxr
ã使ããããã§xxxã®é¨åã¯aãdã®ä¸¦ã³ã§ãããä¾ãã°ã(cadr e)
ã¯(car (cdr e))
ã®çç¥å½¢ã§ãããe
ã®äºçªç®ã®è¦ç´ ãè¿ãã
(cadr '((a b) (c d) e)) ; => (c d) (caddr '((a b) (c d) e)) ; => e (cdar '((a b) (c d) e)) ; => (b)
ã¾ãã(cons e1 ... (cons en '()) ...)
ã®çç¥å½¢ã¨ãã¦(list e1 ... en)
ã使ãã
(cons 'a (cons 'b (cons 'c '()))) ; => (a b c) (list 'a 'b 'c) ; => (a b c)
ããã«ããã¤ãæ°ããé¢æ°ãå®ç¾©ããããåå§ãªãã¬ã¼ã¿ã¨åºå¥ãããããã¾ãCommon Lispçµè¾¼ã¿ã®é¢æ°ã¨ã®ååè¡çªãåé¿ããããã«ããããã®é¢æ°ã®ååã®æå¾ã«ã¯ããªãªã.
ãä»ãã¦ãããã¨ã«ããã
1. null.
(null. x)
ã¯ãã®å¼æ°x
ã空ãªã¹ããã©ããããã¹ãããã
(defun null. (x) (eq x '())) (null. 'a) ; => () (null. '()) ; => t
2. and.
(and. x y)
ã¯ä¸¡æ¹ã®å¼æ°ãt
ãè¿ãã¨ãã«t
ãè¿ãããã以å¤ã®å ´åã¯()
ãè¿ãã
(defun and. (x y) (cond (x (cond (y 't) ('t '()))) ('t '()))) (and. (atom 'a) (eq 'a 'a)) ; => t (and. (atom 'a) (eq 'a 'b)) ; => ()
3. not.
(not. x)
ã¯ãã®å¼æ°x
ã()
ãè¿ãã¨ãã«t
ãè¿ãããã®å¼æ°x
ãt
ãè¿ãã¨ãã«()
ãè¿ãã
(defun not. (x) (cond (x '()) ('t 't))) (not (eq 'a 'a)) ; => () (not (eq 'a 'b)) ; => t
4. append.
(append. x y)
ã¯2ã¤ã®ãªã¹ããå¼æ°ã«åããããããé£çµãããªã¹ããè¿ãã
(defun append. (x y) (cond ((null. x) y) ('t (cons (car x) (append. (cdr x) y))))) (append. '(a b) '(c d)) ; => (a b c d) (append. '() '(c d)) ; => (c d)
5. pair.
(pair. x y)
ã¯2ã¤ã®åãé·ãã®ãªã¹ããå¼æ°ã«åã£ã¦ãããããã®ãªã¹ãã®å¯¾å¿ããä½ç½®ã«ããè¦ç´ ã®ãã¢ãããªããªã¹ããè¿ãã
(defun pair. (x y) (cond ((and. (null. x) (null. y)) '()) ((and. (not. (atom x)) (not. (atom y))) (cons (list (car x) (car y)) (pair. (cdr x) (cdr y)))))) (pair. '(x y z) '(a b c)) ; => ((x a) (y b) (z c))
6. assoc.
(assoc. x y)
ã¯1ã¤ã®ã¢ãã x
ã¨ãpair.
ã«ãã£ã¦çæãããå½¢å¼ã®ãªã¹ãy
ãå¼æ°ã«åã£ã¦ãyã®è¦ç´ ã®ãªã¹ãã®ãã¡ã第ä¸è¦ç´ ãxã§ãããããªãªã¹ãã®ç¬¬äºè¦ç´ ãå¤ã¨ãã¦è¿ãã
(defun assoc. (x y) (cond ((eq (caar y) x) (cadar y)) ('t (assoc. x (cdr y))))) (assoc. 'x '((x a) (y b))) ; => a (assoc. 'x '((x new) (x a) (y b))) ; => new
ãµãã©ã¤ãºï¼ evalã®å®è£
ããã¾ã§ã®ã¨ããã§ããªã¹ããé£çµããããä¸ã¤ã®å¼ãå¥ã®å¼ã«ç½®ãæãããªã©ã®é¢æ°ãã¨ã¬ã¬ã³ããªè¡¨è¨æ³ã§å®ç¾©ã§ããããã«ãªã£ããããããããä½ã«ãªãã¨ããã®ã ãããï¼
ããã§èªè
ã«ãµãã©ã¤ãºããããå®ã¯ãã®æç¹ã§æ¢ã«æã
ã®è¨èªã®ããã®ã¤ã³ã¿ããªã¿ã¨ãã¦åãé¢æ°ãæ¸ããã¨ãã§ãããã¤ã³ã¿ããªã¿ã¯ä»»æã®Lispå¼ãå¼æ°ã«åã£ã¦ãã®å¤ãè¿ãé¢æ°ã§ããã以ä¸ããã®å®ç¾©ã«ãªãã
(defun eval. (e a) (cond ((atom e) (assoc. e a)) ((atom (car e)) (cond ((eq (car e) 'quote) (cadr e)) ((eq (car e) 'atom) (atom (eval. (cadr e) a))) ((eq (car e) 'eq) (eq (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'car) (car (eval. (cadr e) a))) ((eq (car e) 'cdr) (cdr (eval. (cadr e) a))) ((eq (car e) 'cons) (cons (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'cond) (evcon. (cdr e) a)) ('t (eval. (cons (assoc. (car e) a) (cdr e)) a)))) ((eq (caar e) 'label) (eval. (cons (caddar e) (cdr e)) (cons (list (cadar e) (car e)) a))) ((eq (caar e) 'lambda) (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a))))) (defun evcon. (c a) (cond ((eval. (caar c) a) (eval. (cadar c) a)) ('t (evcon. (cdr c) a)))) (defun evlis. (m a) (cond ((null. m) '()) ('t (cons (eval. (car m) a) (evlis. (cdr m) a)))))
ãã®eval.
ã®å®ç¾©ã¯ãããã¾ã§ã«è¦ã¦ããã©ã®å®ç¾©ãããé·ãã®ã§ãåé¨åãã©ã®ããã«åããã詳細ã«è¦ã¦ãããã
ãã®é¢æ°ã¯2ã¤ã®å¼æ°ãåããe
ã¯è©ä¾¡ãããå¼ã§ãa
ã¯ããã¾ã§ã«é¢æ°å¼ã³åºãã«ããããã©ã¡ã¼ã¿ã¨ãã¦åºç¾ãã¦ããã¢ãã ã¨ãã®å¤ã¨ã®å¯¾å¿ã®ãªã¹ãã§ããããã®ãªã¹ãã¯ç°å¢(environment)ã¨å¼ã°ããpair.
ã«ãã£ã¦çæãããå½¢å¼ã«ãªã£ã¦ãããpair.
ãassoc.
ãæ¸ããã®ã¯ããããã®ãªã¹ããæ§ç¯ããæ¢ç´¢ããçºã ã£ãã®ã ã
eval.
ã®éª¨æ ¼ã¯4ã¤ã®ç¯ãããªãcondå¼ã§ãããå¼ãã©ã®ããã«è©ä¾¡ãããã¯ããã®å¼ãã©ããªç¨®é¡ãã«ããããã®condå¼ã®æåã®ç¯ã¯ã¢ãã ãåãæ±ããããe
ãã¢ãã ãªããç°å¢ã®ä¸ãããã®å¤ãè¦ã¤ãã¦ããã
(eval. 'x '((x a) (y b))) ; => a
2ã¤ç®ã®ç¯ã¯ãa
ãã¢ãã ã¨ãã¦ã(a ...)
ã¨ããå½¢ã«ãªã£ã¦ããå¼ãåãæ±ãããã®å¥ã®condå¼ã«ãªã£ã¦ããããã®condå¼ã¯å
¨ã¦ã®åå§ãªãã¬ã¼ã¿ãå«ãã§ãããããããã«ä¸ã¤ãã¤å¯¾å¿ããç¯ãããã
(eval. '(eq 'a 'a) '()) ; => t (eval. '(cons x '(b c)) '((x a) (y b))) ; => (a b c)
ãããã®ãã¡quoteãé¤ãå
¨ã¦ã§ãå¼æ°ã®å¤ãè¦ã¤ããããã«å帰çã«eval.
ãå¼ãã§ããã
æå¾ã®2ã¤ã®ç¯ã¯ããè¤éã«ãªã£ã¦ãããcondå¼ãè©ä¾¡ããããã«ãè£å©é¢æ°evcon.
ãå¼ãã§ãããevcon.
ã¯condå¼ã®ç¯ã®ãªã¹ãc
ãå帰çã«èª¿ã¹ã¦ãããç¯ã®æåã®è¦ç´ (æ¡ä»¶å¼)ãt
ãè¿ããããªç¯ãè¦ã¤ããäºçªç®ã®è¦ç´ ã®å¤ãè¿ãã
(eval. '(cond ((atom x) 'atom) ('t 'list)) '((x '(a b)))) ; => list
eval.
ã®äºçªç®ã®ç¯ã®æå¾ã®é¨å(ã¤ã¾ã2ã¤ç®ã®condå¼ã®ããã©ã«ãç¯)ã¯ããã©ã¡ã¼ã¿ã¨ãã¦æ¸¡ããã¦ããé¢æ°ã®å¼ã³åºããåãæ±ããããã¯ã(a ...)
ã¨ããå½¢ã®ã¢ãã a
ããã®å¤(lambdaå¼ãlabelå¼ã§ããã¹ã)ã§ç½®ãæãã¦ããã®çµæãè©ä¾¡ãããã¨ã«ãã£ã¦åä½ãããå¾ã£ã¦ã
(eval. '(f '(b c)) '((f (lambda (x) (cons 'a x)))))
ã¯
(eval. '((lambda (x) (cons 'a x)) '(b c)) '((f (lambda (x) (cons 'a x)))))
ã¨ãªã£ã¦ã(a b c)
ãè¿ãã
eval.
ã®æå¾ã®äºã¤ã®ç¯ã¯ãå¼ã®æåã®è¦ç´ ã«lambdaå¼ã¾ãã¯labelå¼ãç´æ¥ç½®ããããªé¢æ°å¼ã³åºããåãæ±ããlabelå¼ã®å ´åãã¾ãé¢æ°åã¨é¢æ°æ¬ä½ã®ãªã¹ããç°å¢ã«è¿½å ããããããlabelå¼å
é¨ã®lambdaå¼ã«ãã£ã¦ãã®labelå¼èªèº«ãç½®ãæãããã®å¼ã«å¯¾ãã¦eval.
ãå¼ã¶ãã¨ã«ããè©ä¾¡ããããã¤ã¾ãã
(eval. '((label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x)))))) y) '((y ((a b) (c d)))))
ã¯
(eval. '((lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))) y) '((firstatom (label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))))) (y ((a b) (c d)))))
ã«ãªããå®éã«ã¯a
ãè¿ãã
æå¾ã«ã((lambda (p1 ... pn) e) a1 ... an)
ã®å½¢ã®å¼ã¯æ¬¡ã®ããã«ãã¦è©ä¾¡ããããã¾ãå¼æ°(a1 ... an)
ã®å¤ã®ãªã¹ã(v1 ... vn)
ãå¾ãããã«evlis.
ãå¼ã³ããããã(p1 v1) ... (pn vn)
ãç°å¢ã®å
é ã«è¿½å ãã¦e
ãè©ä¾¡ãããã ããã
(eval. '((lambda (x y) (cons x (cdr y))) 'a '(b c d)) '())
ã¯
(eval. '(cons x (cdr y)) '((x a) (y (b c d))))
ã«ãªããå®éã«ã¯(a c d)
ãè¿ãã
ã¾ã¨ã
ä»ãæã ã¯evalãã©ã®ããã«ãã¦åãããç解ããã®ã§ãç«ã¡æ»ã£ã¦ãããä½ãæå³ãã¦ããã®ããèãã¦ã¿ãããããã§æã ãå¾ããã®ã¯ãé常ã«ã¨ã¬ã¬ã³ããªè¨ç®ã®ã¢ãã«ã§ãããæã ã¯ããã quoteãatomãeqãcarãcdrãconsãcondã®ã¿ã使ã£ã¦ãeval.ãå®ç¾©ãããã¨ãã§ãããããã¦ããã¯å®éã«æã ã®è¨èªãå®è£ ãããã®ã§ãããããã使ã£ã¦æã ã欲ããã©ã®ãããªè¿½å ã®é¢æ°ãå®ç¾©ãããã¨ãã§ããã
ãã¡ãããæ¢ã«æ§ã ãªè¨ç®ã®ã¢ãã«ã¯åå¨ãã¦ãããæãæåãªãã®ã¯ãã¥ã¼ãªã³ã°ãã·ã³ã ãããã¥ã¼ãªã³ã°ãã·ã³ã®ããã°ã©ã ã¯ãã¾ãèªã¿ããããªãããã«ã¯èãããã¦ããªããããããªããã¢ã«ã´ãªãºã ãè¨è¿°ããããã®è¨èªã欲ãã¦ãããªããè¨è¿°ãããæ½è±¡åããããã®ãªã«ãããã®æ段ã欲ããã¨æãã ãããããã¦ãããããã«ã¼ã·ã¼ãLispãå®ç¾©ããçãã®ä¸ã¤ãªã®ã ã
1960å¹´ã«å®ç¾©ãããè¨èªã«è¶³ããªããã®ã¯å¤ããã¾ãå¯ä½ç¨ãç¡ãããå¯ä½ç¨ã使ãã¨ãã«ä¾¿å©ãªé 次å®è¡ã®ä»çµã¿(ã¤ã¾ãCommon Lispã®prognãSchemeã®begin)ããªããå®ç¨çãªæ°å¤ããªãã*4ããã¤ãããã¯ã¹ã³ã¼ãããªããããããããã®å¶éã¯ãé©ãã»ã©ããããªã³ã¼ãã追å ããã ãã§åãé¤ããã¨ãã§ãããSteeleã¨Sussmanã¯ãããã©ããããã"The Art of the Interpreter"ã¨å¼ã°ããæåãªè«æã§ç¤ºãã*5ã
ããããªããããã«ã¼ã·ã¼ã®evalãç解ããã®ãªããåã«ããã°ã©ãã³ã°è¨èªå²ã®ä¸ã¤ã®ã¹ãã¼ã¸ãç解ããã¨ãã以ä¸ã®ãã®ãç解ãã¦ãããã¨ã«ãªãããããã®ã¢ã¤ãã£ã¢ã¯ä»æ¥ã®Lispã«ããã¦ãæå³è«çãªä¸æ ¸ã§ããããã ãããã«ã¼ã·ã¼ã®å
è«æãç 究ãããã¨ã¯ãããæå³ã§ãLispãæ¬å½ã¯ä½ã§ããã®ããæã
ã«ç¤ºãã¦ããããLispã¯ããã«ã¼ã·ã¼ããã¶ã¤ã³ãããã®ã¨ããããã¯çºè¦ãããã®ã¨ããæ¹ãè¿ããLispã¯æ¬æ¥ã人工ç¥è½ãã©ããããããã¿ã¤ãã³ã°(ãããã¯ä»ã®ãã®ãããªã¬ãã«ã®ã¿ã¹ã¯)ã®ããã®è¨èªã¨ããããã§ã¯ãªããLispã¨ã¯ãè¨ç®ãå
¬çåãããã¨è©¦ã¿ãçµæã¨ãã¦å¾ãããä½ããªã®ã§ããã
é·ãæéãããã¦ãå¹³åçãªããã°ã©ãã«ãã£ã¦ä½¿ãããè¨èªã¯ç¶ç¶ãã¦Lispã«è¿ä»ãã¦ãã¦ãããevalãç解ãããã¨ã«ãã£ã¦ãå°æ¥ã®ä¸»æµãªè¨ç®ã®ã¢ãã«ãã©ããªã£ã¦ããããæ¨æ¸¬ãããã¨ãã§ããã ããã
*1:"Recursive Functions of Symbolic Expressions and Their Computation by Machine, PartI." Communications of the ACM 3:4, April 1960, pp. 184-195.
*2:quoteã¨condã§å§ã¾ãå¼ã¯ç°ãªãè©ä¾¡ã®ããæ¹ããããquoteå¼ãè©ä¾¡ãããã¨ããã®å¼æ°ã¯è©ä¾¡ãããã«ãã®ã¾ã¾quoteå¼å ¨ä½ã®å¤ã¨ãã¦è¿ããããã¾ããæ£ããcondå¼ã§ã¯ãæ¡ä»¶ã«ãããããé¨åå¼ã ããè©ä¾¡ãããcondå¼å ¨ä½ã®å¤ã¨ãã¦è¿ãããã
*3:è«ççã«ã¯ããã®ããã«æ°ãã表è¨æ³ãå®ç¾©ããå¿ è¦ã¯ãªããããã¾ã§ã«å®ç¾©ããè¨æ³ã使ã£ã¦ãYコンビネータã¨å¼ã°ããé¢æ°ãæ±ãé¢æ°ã使ããã¨ã«ãã£ã¦å帰é¢æ°ãå®ç¾©ãããã¨ãã§ãããããã«ã¼ã·ã¼ã¯ãã®è«æãæ¸ããæç¹ã§Yã³ã³ããã¼ã¿ã«ã¤ãã¦ã¯ç¥ããªãã£ããããããªããããªãã§ããlabelè¨æ³ã¯ããèªã¿ãããã
*4:ããã«ã¼ã·ã¼ã®1960å¹´çLispã§ããä¾ãã°æ°å¤nã表ç¾ããã®ã«nåã®ã¢ãã ãæã¤ãªã¹ãã使ããªã©ããã°å¯è½ã§ã¯ãã
*5: Guy Lewis Steele, Jr. and Gerald Jay Sussman, "The Art of the Interpreter, or the Modularity Complex - Parts Zero, One, and Two," MIT AI Lab Memo 453, May 1978.