{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:05:07Z","timestamp":1779836707946,"version":"3.53.1"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2025,2,5]],"date-time":"2025-02-05T00:00:00Z","timestamp":1738713600000},"content-version":"unspecified","delay-in-days":35,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Functional programmers have many things for which to thank the late David Turner: design decisions he made in his languages SASL, KRC, and Miranda over the last 50 years are still influential and inspirational now. In particular, Turner was a strong advocate of lazy evaluation and of list comprehensions. As an illustration of these techniques, he popularized a one-line recursive \u201csieve\u201d to generate the infinite list of prime numbers.<\/jats:p>\n                  <jats:p>Turner called this algorithm The Sieve of Eratosthenes. In a lovely paper called \u201cThe Genuine Sieve of Eratosthenes\u201d, Melissa O\u2019Neill argued that Turner\u2019s program is not in fact a faithful implementation of the algorithm, and gave a detailed presentation using priority queues of the real thing. She included a variation by Richard Bird, which uses only lists but makes clever use of circular programming. Bird describes his circular program again in his textbook \u201cThinking Functionally with Haskell\u201d, and sets its proof of correctness as an exercise. In particular, why is this circular program productive? Unfortunately, Bird\u2019s hint for a solution is incorrect. So what should a proof look like?<\/jats:p>\n                  <jats:p>One of the last projects Turner worked on was the notion of \u201cTotal Functional Programming\u201d. He observed that most programs are already structurally recursive or corecursive, therefore guaranteed respectively terminating or productive; he conjectured that \u201cwith more practice we will find this is always true\u201d. We explore Bird\u2019s circular Sieve of Eratosthenes as a challenge problem for Turner\u2019s Total Functional Programming.<\/jats:p>","DOI":"10.1017\/s0956796824000194","type":"journal-article","created":{"date-parts":[[2025,2,5]],"date-time":"2025-02-05T04:52:56Z","timestamp":1738731176000},"update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Turner, Bird, Eratosthenes: An eternal burning thread"],"prefix":"10.1017","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8426-9917","authenticated-orcid":false,"given":"JEREMY","family":"GIBBONS","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2025,2,5]]},"reference":[{"key":"S0956796824000194_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/10930755_20"},{"key":"S0956796824000194_ref14","unstructured":"Turner, D. A. (1975) SASL language manual. Technical Report CS\/75\/1. University of St Andrews, Dept of Computational Science. Revised 16\/9\/75."},{"key":"S0956796824000194_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316092415"},{"key":"S0956796824000194_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796804005210"},{"key":"S0956796824000194_ref15","unstructured":"Turner, D. A. (1976) SASL language manual. Technical Report CS\/75\/1. University of St Andrews, Dept of Computational Science. Revised 1\/12\/76."},{"key":"S0956796824000194_ref17","unstructured":"Turner, D. A. (1983) SASL language manual, \u201crevised November 1983 for inclusion of ZF expressions\u201d. Technical report."},{"key":"S0956796824000194_ref13","unstructured":"Tranah, D. (2024) \u201cJFP 622\u201d. Personal communication (email)."},{"key":"S0956796824000194_ref18","first-page":"751","article-title":"Total functional programming","volume":"10","author":"Turner","year":"2004","journal-title":"J. Univers. Comput. Sci."},{"key":"S0956796824000194_ref19","unstructured":"Turner, D. A. (2020) \u201cSASL manual\u201d. Personal communication (email)."},{"key":"S0956796824000194_ref6","unstructured":"Lieberich, F. (2018) \u201cErrata\u201d. Personal communication (email)."},{"key":"S0956796824000194_ref20","volume-title":"Lucid, the Dataflow Programming Language","author":"Wadge","year":"1985"},{"key":"S0956796824000194_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/359636.359715"},{"key":"S0956796824000194_ref8","unstructured":"McIlroy, M. D. (2014) Coroutine prime number sieve. https:\/\/www.cs.dartmouth.edu\/doug\/sieve\/sieve.pdf."},{"key":"S0956796824000194_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30936-1_24"},{"key":"S0956796824000194_ref5","first-page":"993","volume-title":"IFIP Congress","author":"Kahn","year":"1977"},{"key":"S0956796824000194_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796808007004"},{"key":"S0956796824000194_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/289423.289455"},{"key":"S0956796824000194_ref7","volume-title":"Internal report","author":"McIlroy","year":"1968"},{"key":"S0956796824000194_ref11","unstructured":"Sloane, N. (1999) The composite numbers. In The On-Line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/A002808."},{"key":"S0956796824000194_ref2","first-page":"123","article-title":"M\u00e9moire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu\u2019elle renferme","volume":"18","author":"Bertrand","year":"1845","journal-title":"J. l\u2019\u00c9cole Royale Polytech."}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796824000194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:34:55Z","timestamp":1779834895000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796824000194\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":20,"alternative-id":["S0956796824000194"],"URL":"https:\/\/doi.org\/10.1017\/s0956796824000194","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}],"article-number":"e5"}}