{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T11:15:48Z","timestamp":1697886948392},"reference-count":30,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":7576,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1986,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>List compaction, or so\u2010called \u2018cdr\u2010coding\u2019, can greatly reduce the storage needs of list processing languages. However, existing methods do not perform well when several lists are being constructed simultaneously from the same heap, since the non\u2010contiguous nature of the cells being allocated eliminates the opportunity for compaction. This situation arises not only in true parallel systems sharing a common memory, and sequential systems supporting multiple processes, but also quite often in purely sequential systems, where it is not uncommon to build several different lists simultaneously within a single loop. In this paper, a new list compaction method is presented that performs well during both sequential and \u2018parallel\u2019 list generation. The method is essentially a generalization of cdr\u2010coding, in which lists are represented explicitly as linked vectors rather than implicitly as compacted memory. In addition, an encoding scheme is used that is as simple or simpler than all known encodings, and destructive operations are supported with no greater overhead than existing schemes. Performance figures in a simulated environment suggest that the strategy consistently performs better than conventional cdr\u2010coding, with essentially the same complexity.<\/jats:p>","DOI":"10.1002\/spe.4380160206","type":"journal-article","created":{"date-parts":[[2006,11,18]],"date-time":"2006-11-18T04:18:57Z","timestamp":1163823537000},"page":"145-163","source":"Crossref","is-referenced-by-count":8,"title":["A new list compaction method"],"prefix":"10.1002","volume":"16","author":[{"given":"Kai","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Hudak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0406138"},{"key":"e_1_2_1_3_2","unstructured":"G. J.SussmanandG. L.Steele \u2018Scheme: an interpreter for extended lambda calculus\u2019 MIT AI Lab Memo 349 December1975."},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"J. A.ReesandN.Adams IV. \u2018T: a dialect of Lisp or Lambda: the ultimate software tool\u2019 Proc. 1982 ACM Symposium on Lisp and Functional Programming August1982 pp.114\u2013122.","DOI":"10.1145\/800068.802142"},{"key":"e_1_2_1_5_2","volume-title":"Common Lisp \u2014 The Language","author":"Steele G. L.","year":"1984"},{"key":"e_1_2_1_6_2","unstructured":"D.Moon \u2018MacLisp reference manual version 0 Technical Reports\u2019 MIT Laboratory for Computer Science 1978."},{"key":"e_1_2_1_7_2","volume-title":"The Franz LISP Manual","author":"Foderaro J. K.","year":"1982"},{"key":"e_1_2_1_8_2","unstructured":"P.Hudak \u2018ALFL reference manual and programmers guide\u2019 Yale Department of Computer Science Tech. Report YALEU\/DCS\/TR\u2010322 October1984."},{"key":"e_1_2_1_9_2","unstructured":"D. A.Turner \u2018SASL language manual\u2019 University of St. Andrews Technical Report 1976."},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"R.Milner \u2018A proposal for standard ML\u2019 Proc. 1984 ACM Symposium on Lisp and Functional Programming August1984 pp.184\u2013197.","DOI":"10.1145\/800055.802035"},{"key":"e_1_2_1_11_2","series-title":"Lecture Notes in Computer Science","volume-title":"Programming in Prolog","author":"Clocksin W. F.","year":"1981"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/357153.357157"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"P.HudakandL.Smith \u2018Para\u2010functional programming: a paradigm for programming multiprocessor systems\u2019 Yale Department of Computer Science Tech. Report YALEU\/DCS\/TR\u2010390 January1985.","DOI":"10.1145\/512644.512667"},{"key":"e_1_2_1_14_2","unstructured":"E.Shapiro \u2018Systolic programming: a paradigm of parallel processing\u2019 The Weizmann Institute of Science Department of Applied Mathematics TR CS84\u201321 August1984."},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"R. H.Halstead Jr. \u2018Implementation of multilisp: Lisp on a multiprocessor\u2019 Proc. 1984 ACM Symposium on Lisp and Functional Programming August1984 pp.9\u201317.","DOI":"10.1145\/800055.802017"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"R. P.GabrielandJ.McCarthy \u2018Queue\u2010based multi\u2010processing lisp\u2019 Proc. 1984 ACM Symposium on Lisp and Functional Programming August1984 pp.25\u201344.","DOI":"10.1145\/800055.802019"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/363219.363225"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/360881.360920"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/359423.359427"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.226495"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/357073.357081"},{"key":"e_1_2_1_22_2","unstructured":"A.Bawden R.Greenblatt J.Holloway T.Knight D.MoonandD.Weinreb \u2018Lisp machine progress report\u2019 MIT AI Lab. Memo 444 August1977."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1056737.1056738"},{"key":"e_1_2_1_24_2","volume-title":"3600 Technical Summary","author":"Roads C. B.","year":"1983"},{"key":"e_1_2_1_25_2","unstructured":"L. P.Deutsch \u2018A Lisp machine with very compact programs\u2019 Proc. 3rd IJACI 1973 pp.697\u2013703."},{"key":"e_1_2_1_26_2","unstructured":"J. S.Moore \u2018The interlisp virtual machine specification\u2019 Xerox PARC Tech. Report CSL\u201076\u20135 1976."},{"key":"e_1_2_1_27_2","volume-title":"Artificial Intelligence Programming","author":"Charniak E.","year":"1980"},{"key":"e_1_2_1_28_2","doi-asserted-by":"crossref","unstructured":"J. R.Ellis private communication 1984.","DOI":"10.1016\/0025-326X(84)90468-5"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/502874.502878"},{"key":"e_1_2_1_30_2","unstructured":"J. R.Ellis \u2018Bulldog: a compiler for VLIW architectures \u2019 Ph.D. Thesis Yale University February1985."},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/359460.359470"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380160206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380160206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T01:31:39Z","timestamp":1697851899000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380160206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,2]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1986,2]]}},"alternative-id":["10.1002\/spe.4380160206"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380160206","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,2]]}}}