# tail recursion modulo cons

## tail recursion modulo cons

(programming, compiler)
A generalisation of tail recursion introduced by D.H.D. Warren. It applies when the last thing a function does is to apply a constructor functions (e.g. cons) to an application of a non-primitive function. This is transformed into a tail call to the function which is also passed a pointer to where its result should be written. E.g.

f [] = [] f (x:xs) = 1 : f xs

is transformed into (pseudo C/Haskell):

f [] = [] f l = f' l allocate_cons

f' [] p = { *p = nil; return *p } f' (x:xs) p = { cell = allocate_cons; *p = cell; cell.head = 1; return f' xs &cell.tail }

where allocate_cons returns the address of a new cons cell, *p is the location pointed to by p and &c is the address of c.

[D.H.D. Warren, DAI Research Report 141, University of Edinburgh 1980].
Site: Follow: Share:
Open / Close
{"ft_lang_label":"__label__en","ft_lang_prob":0.8142833,"math_prob":0.8612267,"size":1258,"snap":"2019-35-2019-39","text_gpt3_token_len":369,"char_repetition_ratio":0.115629986,"word_repetition_ratio":0.71311474,"special_character_ratio":0.32511923,"punctuation_ratio":0.17090909,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9893147,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-09-19T12:42:36Z\",\"WARC-Record-ID\":\"<urn:uuid:be49944b-42c9-435a-a83f-0c181b808ca9>\",\"Content-Length\":\"39662\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:9a79f54a-b6f4-48d9-8816-1b0c79e09552>\",\"WARC-Concurrent-To\":\"<urn:uuid:280512fb-4ae0-4838-b91e-a4a00d6d4045>\",\"WARC-IP-Address\":\"85.195.124.227\",\"WARC-Target-URI\":\"https://encyclopedia2.thefreedictionary.com/tail+recursion+modulo+cons\",\"WARC-Payload-Digest\":\"sha1:ABDVSG4U7LLPHMBCQX22ZG4EUWLJP67I\",\"WARC-Block-Digest\":\"sha1:AGCDJ6RV52NWR4EHA26XMR2T6PXXFVZS\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-39/CC-MAIN-2019-39_segments_1568514573519.72_warc_CC-MAIN-20190919122032-20190919144032-00455.warc.gz\"}"}