Next: , Previous: Sequence Type, Up: Programming Types   [Contents][Index]


2.3.6 ¥³¥ó¥¹¥»¥ë¤È¥ê¥¹¥È·¿

¥³¥ó¥¹¥»¥ë¡Êcons cell¡Ë¤È¤Ï¡¢ CAR¥¹¥í¥Ã¥È¤ª¤è¤ÓCDR¥¹¥í¥Ã¥È¤È¸Æ¤Ð¤ì¤ë 2¤Ä¤Î¥Ý¥¤¥ó¥¿¤«¤éÀ®¤ë¥ª¥Ö¥¸¥§¥¯¥È¤Ç¤¹¡£ ³Æ¥¹¥í¥Ã¥È¤Ï¡¢Ç¤°Õ¤ÎLisp¥ª¥Ö¥¸¥§¥¯¥È¤ò»Ø¤¹¤³¤È¤¬¤Ç¤­¤Þ¤¹¡£ ¤Þ¤¿¡¢¸½ºßCAR¥¹¥í¥Ã¥È¤¬»Ø¤·¤Æ¤¤¤ë¥ª¥Ö¥¸¥§¥¯¥È¤¬¤Ê¤ó¤Ç¤¢¤ì¡¢ ¡Ø¥³¥ó¥¹¥»¥ë¤ÎCAR¤Ï¡Ù¤È¤¤¤Ã¤¿¤¤¤¤Êý¤ò¤·¤Þ¤¹¡£ CDR¤Ë¤Ä¤¤¤Æ¤âƱÍͤǤ¹¡£

¥ê¥¹¥È¡Êlist¡Ë¤Ï¥³¥ó¥¹¥»¥ë¤¬Ï¢¤Ê¤Ã¤¿¤â¤Î¤Ç¤¢¤ê¡¢ ³Æ¥³¥ó¥¹¥»¥ë¤ÎCDR¥¹¥í¥Ã¥È¤Ï¡¢ ¸å³¤Î¥³¥ó¥¹¥»¥ë¤ò»Ø¤¹¤«¶õ¥ê¥¹¥È¤ò»Ø¤·¤Þ¤¹¡£ ¥ê¥¹¥È¤ËºîÍѤ¹¤ë´Ø¿ô¤Ë¤Ä¤¤¤Æ¤Ï¡¢See Lists¡£ ¤Û¤È¤ó¤É¤Î¥³¥ó¥¹¥»¥ë¤Ï¡¢¥ê¥¹¥È¤Î°ìÉôʬ¤È¤·¤Æ»È¤ï¤ì¤ë¤Î¤Ç¡¢ ¥ê¥¹¥È¹½Â¤¡Êlist structure¡Ë¤È¤¤¤¦ÍѸì¤Ï¡¢ ¥³¥ó¥¹¥»¥ë¤«¤éÀ®¤ëǤ°Õ¤Î¹½Â¤¤Î¤³¤È¤ò°ÕÌ£¤·¤Þ¤¹¡£

CAR¤äCDR¤È¤¤¤¦Ì¾¾Î¤Ï¡¢Lisp¤ÎÎò»Ë¤ËͳÍ褷¤Þ¤¹¡£ ºÇ½é¤ÎLisp¤ÏIBM 704¤Çưºî¤·¤Æ¤¤¤Þ¤·¤¿¡£ ¤³¤Î·×»»µ¡¤Ç¤Ï¡¢¥ï¡¼¥É¤ò2¤Ä¤ÎÉôʬ¡¢¡ØÈÖÃϡ١Êaddress¡ËÉôʬ¡¢ ¡Ø¸º¿ô¡Ù¡Êdecrement¡ËÉôʬ¤È¸Æ¤Ð¤ì¤ë¤â¤Î¤Ëʬ¤±¤Æ¤¤¤Þ¤·¤¿¡£ CAR¤Ï¥ì¥¸¥¹¥¿¤ÎÈÖÃÏÉôʬ¤ÎÆâÍÆ¡ÊContents of Address Register¡Ë¤ò ¼è¤ê½Ð¤¹Ì¿Îá¤Ç¤¢¤ê¡¢ CDR¤Ï¥ì¥¸¥¹¥¿¤Î¸º¿ôÉôʬ¤ÎÆâÍÆ¡ÊContents of Decrement Register¡Ë¤ò ¼è¤ê½Ð¤¹Ì¿Îá¤Ç¤·¤¿¡£ °ìÊý¡¢¡Ø¥³¥ó¥¹¥»¥ë¡Ù¤È¤¤¤¦Ì¾¾Î¤Ï¡¢ ¤³¤ì¤é¤òºîÀ®¤¹¤ë´Ø¿ôcons¤«¤é¤­¤Æ¤¤¤Þ¤¹¡£ ¤³¤Î´Ø¿ô̾¤Ï¡¢¤½¤ÎÌÜŪ¡¢¥»¥ë¤òºî¤ë¡Êconstruction of cells¡Ë¤«¤é¤­¤Æ¤¤¤Þ¤¹¡£

¥³¥ó¥¹¥»¥ë¤ÏLisp¤Î³Ë¿´¤Ê¤Î¤Ç¡¢ ¡Ø¥³¥ó¥¹¥»¥ë¤Ç¤Ï¤Ê¤¤¥ª¥Ö¥¸¥§¥¯¥È¡Ù¤ËÂФ¹¤ë̾¾Î¤â¤¢¤ê¤Þ¤¹¡£ ¤³¤ì¤é¤Î¥ª¥Ö¥¸¥§¥¯¥È¤ò¥¢¥È¥à¡Êatoms¡Ë¤È¸Æ¤Ó¤Þ¤¹¡£

¥ê¥¹¥È¤ÎÆþÎϹ½Ê¸¤Èɽ¼¨É½¸½¤ÏƱ°ì¤Ç¤¹¡£ ³«¤­³ç¸Ì¤Ç»Ï¤Þ¤ê¡¢Ç¤°Õ¸Ä¤ÎÍ×ÁÇ¡¢ÊĤ¸³ç¸Ì¤Ç½ª¤¨¤Þ¤¹¡£

ÆÉ¤ß¼è¤ê»þ¤Ë¤Ï¡¢³ç¸Ì¤ÎÆâ¦¤Î³Æ¥ª¥Ö¥¸¥§¥¯¥È¤¬¡¢ ¥ê¥¹¥È¤Î³ÆÍ×ÁǤˤʤê¤Þ¤¹¡£ ¤Ä¤Þ¤ê¡¢¤³¤ì¤é¤ÎÍ×ÁǤ«¤é¤Ê¤ë¥³¥ó¥¹¥»¥ë¤òºî¤ê¤Þ¤¹¡£ ¥³¥ó¥¹¥»¥ë¤ÎCAR¥¹¥í¥Ã¥È¤ÇÍ×ÁǤò»Ø¤·¤Þ¤¹¡£ Ʊ¤¸¥³¥ó¥¹¥»¥ë¤ÎCDR¥¹¥í¥Ã¥È¤Ç¡¢ ¥ê¥¹¥È¾å¤Î¤Ä¤®¤ÎÍ×ÁǤòÊÝ»ý¤·¤Æ¤¤¤ë¡¢ ¥ê¥¹¥È¤Î¤Ä¤®¤Î¥³¥ó¥¹¥»¥ë¤ò»Ø¤·¤Þ¤¹¡£ ºÇ¸å¤Î¥³¥ó¥¹¥»¥ë¤ÎCDR¥¹¥í¥Ã¥È¤Ïnil¤ò»Ø¤·¤Þ¤¹¡£

¥ê¥¹¥È¤Ï¡¢¥³¥ó¥¹¥»¥ë¤ò1ÂФÎÈ¢¤Çɽ¤·¤Æ¿Þ¼¨¤Ç¤­¤Þ¤¹¡£ ¡ÊLisp¥ê¡¼¥À¤¬¤³¤Î¤è¤¦¤Ê¿Þɽ¼¨¤òÆÉ¤à¤³¤È¤Ï¤Ê¤¤¡£ ¿Í´Ö¤ä·×»»µ¡¤¬Íý²ò¤Ç¤­¤ë¥Æ¥­¥¹¥Èɽµ­¤È°ã¤¤¡¢ È¢¤òÍѤ¤¤¿¿Þɽ¼¨¤Ï¿Í´Ö¤À¤±¤¬Íý²ò¤Ç¤­¤ë¡£¡Ë ¤Ä¤®¤Î¿Þ¤Ï¡¢3¤Ä¤ÎÍ×ÁǤ«¤éÀ®¤ë¥ê¥¹¥È(rose violet buttercup)¤òɽ¤·¤Þ¤¹¡£

    --- ---      --- ---      --- ---
   |   |   |--> |   |   |--> |   |   |--> nil
    --- ---      --- ---      --- ---
     |            |            |
     |            |            |
      --> rose     --> violet   --> buttercup

¤³¤Î¿Þ¤Ç¡¢³ÆÈ¢¤Ï¡¢Ç¤°Õ¤ÎLisp¥ª¥Ö¥¸¥§¥¯¥È¤ò»Ø¤¹¤³¤È¤¬¤Ç¤­¤ë¥¹¥í¥Ã¥È¤òɽ¤·¤Þ¤¹¡£ È¢¤ÎÂФǥ³¥ó¥¹¥»¥ë¤òɽ¤·¤Þ¤¹¡£ ³ÆÌð°õ¤Ï¡¢¥¢¥È¥à¤ä¾¤Î¥³¥ó¥¹¥»¥ë¤Ç¤¢¤ëLisp¥ª¥Ö¥¸¥§¥¯¥È¤ò»Ø¤¹¥Ý¥¤¥ó¥¿¤Ç¤¹¡£

¤³¤ÎÎã¤Ç¤Ï¡¢ºÇ½é¤Î¥³¥ó¥¹¥»¥ë¤ÎCAR¤òɽ¤¹ºÇ½é¤ÎÈ¢¤Ï¡¢ rose¡Ê¥·¥ó¥Ü¥ë¡Ë¤ò»Ø¤·¤Æ¤¤¤Þ¤¹¡£ ¤¢¤ë¤¤¤Ï¡¢rose¡Ê¥·¥ó¥Ü¥ë¡Ë¤ò¡Ø´Þ¤ó¤Ç¤¤¤ë¡Ù¤È¤â¤¤¤¤¤Þ¤¹¡£ ºÇ½é¤Î¥³¥ó¥¹¥»¥ë¤ÎCDR¤òɽ¤¹2ÈÖÌܤÎÈ¢¤Ï¡¢ ¤Ä¤®¤Î1ÂФÎÈ¢¡¢2ÈÖÌܤΥ³¥ó¥¹¥»¥ë¤ò»Ø¤·¤Æ¤¤¤Þ¤¹¡£ 2ÈÖÌܤΥ³¥ó¥¹¥»¥ë¤ÎCAR¤Ïviolet¤Ç¤¢¤ê¡¢ ¤³¤Î¥³¥ó¥¹¥»¥ë¤ÎCDR¤Ï3ÈÖÌܤΥ³¥ó¥¹¥»¥ë¤Ç¤¹¡£ 3ÈÖÌܤΡʺǸå¤Î¡Ë¥³¥ó¥¹¥»¥ë¤ÎCDR¤Ï¡¢nil¤Ç¤¹¡£

Ʊ¤¸¥ê¥¹¥È(rose violet buttercup)¤ò Ê̤ÎÊýË¡¤Ç¿Þɽ¼¨¤¹¤ë¤È¤Ä¤®¤Î¤è¤¦¤Ë¤Ê¤ê¤Þ¤¹¡£

 ---------------       ----------------       -------------------
| car   | cdr   |     | car    | cdr   |     | car       | cdr   |
| rose  |   o-------->| violet |   o-------->| buttercup |  nil  |
|       |       |     |        |       |     |           |       |
 ---------------       ----------------       -------------------

ÆâÉô¤ËÍ×ÁǤò»ý¤¿¤Ê¤¤¥ê¥¹¥È¤Ï¡¢¶õ¥ê¥¹¥È¡Êempty list¡Ë¤Ç¤¹¡£ ¤³¤ì¤Ï¥·¥ó¥Ü¥ënil¤ÈƱ°ì¤Ç¤¹¡£ ¤¤¤¤¤«¤¨¤ì¤Ð¡¢nil¤Ï¥·¥ó¥Ü¥ë¤Ç¤â¤¢¤ê¥ê¥¹¥È¤Ç¤â¤¢¤ê¤Þ¤¹¡£

Lisp¤Î¹½Ê¸¤Ç½ñ¤­É½¤·¤¿¥ê¥¹¥È¤ÎÎã¤ò¼¨¤·¤Þ¤¹¡£

(A 2 "A")            ; 3Í×ÁǤΥꥹ¥È
()                   ; Í×ÁǤò»ý¤¿¤Ê¤¤¥ê¥¹¥È¡Ê¶õ¥ê¥¹¥È¡Ë
nil                  ; Í×ÁǤò»ý¤¿¤Ê¤¤¥ê¥¹¥È¡Ê¶õ¥ê¥¹¥È¡Ë
("A ()")             ; ʸ»úÎó"A ()"¤À¤±¤Î1Í×ÁǤΥꥹ¥È
(A ())               ; A¤È¶õ¥ê¥¹¥È¤«¤éÀ®¤ë2Í×ÁǤΥꥹ¥È
(A nil)              ; ¾å¤ÈƱ¤¸
((A B C))            ; 1Í×ÁǤΥꥹ¥È
                     ;   ¡Ê¤½¤ÎÍ×ÁǤÏ3Í×ÁǤΥꥹ¥È¡Ë

¥ê¥¹¥È(A ())¤ä¡¢¤³¤ì¤ÈƱ¤¸(A nil)¤ò È¢¤ÈÌð°õ¤Ç½ñ¤¯¤È¤Ä¤®¤Î¤è¤¦¤Ë¤Ê¤ê¤Þ¤¹¡£

    --- ---      --- ---
   |   |   |--> |   |   |--> nil
    --- ---      --- ---
     |            |
     |            |
      --> A        --> nil