{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:53:01Z","timestamp":1776891181997,"version":"3.51.2"},"reference-count":2,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"2","license":[{"start":{"date-parts":[[2016,8,10]],"date-time":"2016-08-10T00:00:00Z","timestamp":1470787200000},"content-version":"unspecified","delay-in-days":9263,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[1991,4]]},"abstract":"<jats:p>Programming languages which are capable of interpreting themselves have been fascinating computer scientists. Indeed, if this is possible then a \u2018strange loop\u2019 (in the sense of Hofstadter, 1979) is involved. Nevertheless, the phenomenon is a direct consequence of the existence of universal languages. Indeed, if all computable functions can be captured by a language, then so can the particular job of interpreting the code of a program of that language. Self-interpretation will be shown here to be possible in lambda calculus.<\/jats:p>\n                  <jats:p>\n                    The set of\n                    <jats:italic>\u03bb-terms<\/jats:italic>\n                    , notation \u039b, is defined by the following abstract syntax\n                  <\/jats:p>\n                  <jats:p>\n                    <jats:disp-formula>\n                      <jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0956796800020062_Uequ1\"\/>\n                    <\/jats:disp-formula>\n                  <\/jats:p>\n                  <jats:p>where<\/jats:p>\n                  <jats:p>\n                    is the set {v, v\u2032, v\u2033, v\u2032\u2033,\u2026} of\n                    <jats:italic>variables<\/jats:italic>\n                    . Arbitrary variables are usually denoted by x, y,z,\u2026 and\n                    <jats:italic>\u03bb<\/jats:italic>\n                    -terms by M,N,L,\u2026. A\n                    <jats:italic>redex<\/jats:italic>\n                    is a\n                    <jats:italic>\u03bb<\/jats:italic>\n                    -term of the form\n                  <\/jats:p>\n                  <jats:p>\n                    <jats:disp-formula>\n                      <jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0956796800020062_Uequ2\"\/>\n                    <\/jats:disp-formula>\n                  <\/jats:p>\n                  <jats:p>\n                    that is, the result of substituting N for (the free occurrences of) x in M. Stylistically, it can be said that\n                    <jats:italic>\u03bb<\/jats:italic>\n                    -terms represent functional programs including their input. A\n                    <jats:italic>reduction machine<\/jats:italic>\n                    executes such terms by trying to reduce them to normal form; that is, redexes are continuously replaced by their contracta until hopefully no more redexes are present. If such a normal form can be reached, then this is the output of the functional program; otherwise, the program diverges.\n                  <\/jats:p>","DOI":"10.1017\/s0956796800020062","type":"journal-article","created":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T18:01:05Z","timestamp":1558116065000},"page":"229-233","source":"Crossref","is-referenced-by-count":23,"title":["Theoretical Pearls:\n                    <i>Self-interpretation in lambda calculus<\/i>"],"prefix":"10.46298","volume":"1","author":[{"given":"Henk","family":"Barendregt","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2016,8,10]]},"reference":[{"key":"S0956796800020062_ref001","volume-title":"G\u00f6del, Escher, Bach: an Eternal Golden Braid","author":"Hofstadter","year":"1979"},{"key":"S0956796800020062_ref002","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-36-00227-2"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796800020062","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:17:48Z","timestamp":1776889068000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796800020062\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,4]]},"references-count":2,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,4]]}},"alternative-id":["S0956796800020062"],"URL":"https:\/\/doi.org\/10.1017\/s0956796800020062","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,4]]}}}