108:
143:
65:
312:. Indexing was a subtractive process on the 704, hence the value to be loaded into an index register was called a "decrement". The 704 hardware had special instructions for accessing the address and decrement fields in a word. As a result it was efficient to use those two fields to store within a single word the two pointers needed for a list.
655:
of a cons cell need not be a list. In this case, most other languages provide different primitives as they typically distinguish pair structures from list structures either typefully or semantically. Particularly in typed languages, lists, pairs, and trees will all have different accessor functions
281:
stand for "Contents of the
Address Register" and "Contents of the Decrement Register" does not quite match the IBM 704 architecture; the IBM 704 does not have a programmer-accessible address register and the three address modification registers are called "index registers" by IBM.
109:
144:
66:
946:
767:. The reference identifies the IBM 704 and correctly explains the address and decrement part of a cons cell, but then it omits the "part of" in McCarthy's explanation.
907:
308:
separated by a 3-bit tag. The first 15-bit field was the operand address and the second held a decrement or count. The tag specified one of three
927:
892:
651:, etc. In Lisp, however, the cons cell is not used only to build linked lists but also to build pair and nested pair structures, i.e. the
351:
each of which took a machine address as an argument, loaded the corresponding word from memory, and extracted the appropriate bits.
1019:
1000:
836:
1077:
780:
1029:
923:
795:
525:
The prefix and tag parts were dropped in the early stages of Lisp's design, leaving CAR, CDR, and a two-argument CONS.
986:
958:
757:
908:
http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf
877:
657:
297:
163:
596:
289:
709:
159:
893:
https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf
942:
825:
McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985),
305:
497:# C( C ) → C( Decrement of AC ) # Clears AC and loads Index Register C into the Decrement of AC
429:# C( C ) → C( Decrement of AC ) # Clears AC and loads Index Register C into the Decrement of AC
616:
452:# C( Decrement of JLOC ) → C( C ) # Loads the Decrement of location JLOC into Index Register C
384:# C( Decrement of JLOC ) → C( C ) # Loads the Decrement of location JLOC into Index Register C
747:
219:
28:
799:
1033:
620:
533:
467:# C( 0 - C( C ) ) → C( AC ) # The AC register receives the start address of the list
399:# C( 0 - C( C ) ) → C( AC ) # The AC register receives the start address of the list
35:
24:
20:
8:
363:
1056:
1034:"Recursive functions of symbolic expressions and their computation by machine, Part I."
862:
215:
842:, page 36, describes cons cells as words with 15-bit "address" and "decrement" fields.
781:
http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf
1015:
996:
950:
832:
826:
753:
360:
544:
can be given short and more or less pronounceable names of the same form. In Lisp,
482:# C( Decrement of AC ) → C( C ) # Loads the Decrement of AC into Index Register C
1060:
1048:
990:
563:
319:
of the
Register". The term "register" in this context refers to "memory location".
118:
83:
49:
414:# C( Address of AC ) → C( C ) # Loads the Address of AC into Index Register C
815:, pp. 26–27) discusses registers on the free list and in garbage collection.
309:
301:
223:
1071:
293:
954:
851:
242:
of the list. For this reason, the operations are sometimes given the names
155:
1052:
627:
as a basic data structure, and provide primitives or functions similar to
978:
624:
592:
599:, systematically define all variations of two to four compositions of
1012:
Land of Lisp : learn to program in Lisp, one game at a time!
938:
685:
267:
863:
A Fortran-Compiled List-Processing
Language; HTML transcription
286:
133:
98:
575:
55:
824:
572:
151:
127:
92:
831:(second ed.), Cambridge, Massachusetts: MIT Press,
341:("contents of the prefix part of register number"), and
300:
formats, one of which, the Type A, had a short, 3-bit,
335:("contents of the decrement part of register number"),
619:
languages and languages influenced by the functional
569:
124:
89:
52:
329:("contents of the address part of register number"),
130:
95:
566:
121:
86:
676:when dealing with a pair type. Exact analogues of
1069:
856:
347:("contents of the tag part of register number"),
752:, Cambridge University Press, pp. 28–29,
170:operation extracts the first pointer, and the
1014:. San Francisco, CA: No Starch Press, Inc.
852:A Fortran-Compiled List-Processing Language
610:
790:
788:
902:
900:
878:http://t3x.dyndns.org/LISP/QA/carcdr.html
779:704 - electronic data-processing machine
775:
773:
1028:
812:
794:
745:
315:Thus, "CAR" is "Contents of the Address
785:
502:A machine word could be reassembled by
322:Precursors to Lisp included functions:
266:Lisp was originally implemented on the
1070:
1009:
985:
947:MIT Artificial Intelligence Laboratory
935:CSAIL Publications and Digital Archive
897:
872:
870:
770:
214:When cons cells are used to implement
16:Programming language construct in Lisp
1047:(4). ACM New York, NY, USA: 184–195.
976:
887:
885:
906:CODING for the MIT-IBM 704 COMPUTER
979:"The origin of CAR and CDR in LISP"
922:
867:
845:
656:with different type signatures: in
13:
933:. RLE and MIT Computation Center.
882:
684:are thus rare in other languages.
285:The 704 and its successors have a
14:
1089:
765:Innovations in the Design of Lisp
749:Concepts in Programming Languages
162:. A cons cell is composed of two
928:"Writing and Debugging Programs"
876:Portions from NILS' LISP PAGES-
562:
117:
82:
48:
528:
174:operation extracts the second.
818:
806:
738:
150:) are primitive operations on
1:
731:
615:Many languages (particularly
506:, which took four arguments (
354:
273:The popular explanation that
270:computer, in the late 1950s.
828:LISP 1.5 Programmer's Manual
635:. These are named variously
434:The 704 assembler macro for
261:
7:
1078:Lisp (programming language)
977:Faase, Frans (2006-01-10).
591:. Most Lisps, for example
234:element of the list, while
222:and other more complicated
10:
1094:
746:Mitchell, John C. (2003),
712:, on the other hand, uses
585:(car (car '((1 2) (3 4))))
296:. These computers had two
18:
1041:Communications of the ACM
160:Lisp programming language
611:Other computer languages
440:
372:
1010:Barski, Conrad (2010).
304:prefix and two 15-bit
230:operation returns the
154:cells (or "non-atomic
1053:10.1145/367177.367199
558:(caar '((1 2) (3 4)))
548:is the equivalent of
177:Thus, the expression
158:") introduced in the
29:CADR (disambiguation)
550:(car (cdr '(1 2 3)))
292:length and a 15-bit
36:computer programming
25:CDR (disambiguation)
21:CAR (disambiguation)
19:For other uses, see
216:singly linked lists
891:MIT AI Lab Memo 6
744:See, for example,
625:singly linked list
1021:978-1-59327-281-4
1002:978-0-13-370875-2
995:. Prentice Hall.
945:, Massachusetts:
838:978-0-262-13011-0
800:"History of Lisp"
583:) is the same as
1085:
1064:
1038:
1025:
1006:
992:ANSI Common Lisp
982:
973:
971:
969:
963:
957:. Archived from
932:
910:
904:
895:
889:
880:
874:
865:
860:
854:
849:
843:
841:
822:
816:
810:
804:
803:
792:
783:
777:
768:
762:
742:
727:
723:
719:
715:
707:
703:
699:
695:
691:
683:
679:
675:
671:
667:
663:
654:
650:
646:
642:
638:
634:
630:
606:
602:
590:
586:
582:
581:
578:
577:
574:
571:
568:
559:
555:
551:
547:
543:
539:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
437:
430:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
379:
376:
369:
346:
340:
334:
328:
210:
204:
193:
187:
149:
148:
147:
146:
139:
136:
135:
132:
129:
126:
123:
114:
113:
112:
111:
104:
101:
100:
97:
94:
91:
88:
79:
71:
70:
69:
68:
61:
58:
57:
54:
45:
1093:
1092:
1088:
1087:
1086:
1084:
1083:
1082:
1068:
1067:
1036:
1022:
1003:
967:
965:
961:
930:
914:
913:
905:
898:
890:
883:
875:
868:
861:
857:
850:
846:
839:
823:
819:
811:
807:
793:
786:
778:
771:
763:, Section 3.4,
760:
743:
739:
734:
725:
721:
717:
713:
705:
701:
697:
693:
689:
681:
677:
673:
669:
665:
661:
660:, for example,
652:
648:
644:
640:
636:
632:
628:
613:
604:
600:
588:
587:; its value is
584:
565:
561:
557:
553:
552:; its value is
549:
546:(cadr '(1 2 3))
545:
541:
537:
531:
500:
499:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
435:
432:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
386:
383:
380:
377:
374:
367:
357:
344:
338:
332:
326:
310:index registers
264:
206:
195:
189:
178:
142:
141:
120:
116:
107:
106:
85:
81:
77:
64:
63:
51:
47:
43:
32:
17:
12:
11:
5:
1091:
1081:
1080:
1066:
1065:
1030:McCarthy, John
1026:
1020:
1007:
1001:
983:
974:
924:Russell, Steve
919:
918:
912:
911:
896:
881:
866:
855:
844:
837:
817:
813:McCarthy (1960
805:
798:(1979-02-12).
796:McCarthy, John
784:
769:
758:
736:
735:
733:
730:
612:
609:
530:
527:
441:
373:
356:
353:
349:
348:
342:
336:
330:
302:operation code
263:
260:
15:
9:
6:
4:
3:
2:
1090:
1079:
1076:
1075:
1073:
1062:
1058:
1054:
1050:
1046:
1042:
1035:
1031:
1027:
1023:
1017:
1013:
1008:
1004:
998:
994:
993:
988:
984:
980:
975:
964:on 2017-07-06
960:
956:
952:
948:
944:
940:
936:
929:
925:
921:
920:
916:
915:
909:
903:
901:
894:
888:
886:
879:
873:
871:
864:
859:
853:
848:
840:
834:
830:
829:
821:
814:
809:
801:
797:
791:
789:
782:
776:
774:
766:
761:
759:9781139433488
755:
751:
750:
741:
737:
729:
711:
687:
659:
626:
622:
618:
608:
598:
594:
580:
556:. Similarly,
535:
526:
523:
521:
517:
513:
509:
505:
439:
371:
365:
362:
352:
343:
337:
331:
325:
324:
323:
320:
318:
313:
311:
307:
303:
299:
295:
294:address space
291:
288:
283:
280:
276:
271:
269:
259:
257:
253:
249:
245:
241:
237:
233:
229:
225:
221:
218:(rather than
217:
212:
209:
205:evaluates to
202:
199:
192:
188:evaluates to
185:
182:
175:
173:
169:
165:
161:
157:
156:S-expressions
153:
145:
138:
110:
103:
75:
67:
60:
41:
37:
30:
26:
22:
1044:
1040:
1011:
991:
987:Graham, Paul
966:. Retrieved
959:the original
934:
858:
847:
827:
820:
808:
764:
748:
740:
614:
560:(pronounced
534:Compositions
532:
529:Compositions
524:
519:
515:
511:
507:
503:
501:
433:
358:
350:
321:
316:
314:
284:
278:
274:
272:
265:
255:
251:
247:
243:
239:
238:returns the
235:
231:
227:
213:
207:
200:
197:
190:
183:
180:
176:
171:
167:
73:
39:
33:
724:instead of
716:instead of
704:instead of
692:instead of
593:Common Lisp
298:instruction
196:(cdr (cons
179:(car (cons
732:References
617:functional
355:704 macros
224:structures
943:Cambridge
941:, no. 6.
361:assembler
262:Etymology
1072:Category
1032:(1960).
989:(1996).
968:July 20,
955:35415961
937:(Memo).
722:butfirst
623:) use a
621:paradigm
359:The 704
164:pointers
1061:1489409
939:AI Memo
686:Clojure
668:become
658:Haskell
268:IBM 704
226:), the
1059:
1018:
999:
953:
835:
756:
597:Scheme
306:fields
287:36-bit
194:, and
166:; the
27:, and
1057:S2CID
1037:(PDF)
962:(PDF)
931:(PDF)
917:Notes
714:first
690:first
688:uses
637:first
438:was:
370:was:
364:macro
244:first
232:first
220:trees
140:
105:
62:
1016:ISBN
997:ISBN
970:2017
951:OCLC
833:ISBN
754:ISBN
720:and
710:Logo
702:rest
698:next
696:and
680:and
672:and
664:and
649:tail
647:and
645:head
641:rest
639:and
631:and
603:and
595:and
540:and
504:cons
446:JLOC
378:JLOC
366:for
317:part
290:word
277:and
256:tail
254:and
252:head
248:rest
246:and
240:rest
152:cons
72:and
1049:doi
726:cdr
718:car
708:.
706:cdr
700:or
694:car
682:cdr
678:car
674:snd
670:fst
666:cdr
662:car
653:cdr
633:cdr
629:car
605:cdr
601:car
576:ɑːr
542:cdr
538:car
536:of
522:).
485:PXD
470:PDX
455:CLA
443:LXD
436:cdr
417:PXD
402:PAX
387:CLA
375:LXD
368:car
345:ctr
339:cpr
333:cdr
327:car
279:CDR
275:CAR
250:or
236:cdr
228:car
172:cdr
168:car
115:or
80:) (
78:cdr
74:CDR
56:ɑːr
44:car
40:CAR
34:In
1074::
1055:.
1043:.
1039:.
949:.
926:.
899:^
884:^
869:^
787:^
772:^
728:.
643:,
607:.
573:eɪ
258:.
211:.
203:))
186:))
134:ər
99:ər
46:)
38:,
23:,
1063:.
1051::
1045:3
1024:.
1005:.
981:.
972:.
802:.
589:1
579:/
570:k
567:ˈ
564:/
554:2
520:t
518:,
516:p
514:,
512:d
510:,
508:a
494:4
491:,
488:0
479:4
476:,
473:0
464:4
461:,
458:0
449:4
426:4
423:,
420:0
411:4
408:,
405:0
396:4
393:,
390:0
381:4
208:y
201:y
198:x
191:x
184:y
181:x
137:/
131:d
128:ʊ
125:k
122:ˈ
119:/
102:/
96:d
93:ʌ
90:k
87:ˈ
84:/
76:(
59:/
53:k
50:/
42:(
31:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.