Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.

McCarthy, J. (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM, 3(4), 184-195.

Type

Journal article

Intellectual base

Primary research

Year

1960

Volume

3

Issue

4

Pages

184-195

DOI

10.1145/367177.367199

DOI registrant

Association for Computing Machinery

Link

https://doi.org/10.1145/367177.367199

Cited from

computer_science, linguistics_semiotics

Cited by

4 citations across 4 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Garbage Collection
  • The declared root set is the precise structural commitment — the machine registers, the call stack, and the global variables, the stipulated entry points from which all legitimate access begins.

    This sourceIntroduces the mark-and-sweep garbage collector, with roots in registers, stack, and globals and a transitive mark of all reachable cells; tracing reclaims cycles reference counting cannot.

    Supported in partVerified against the work's full text

    McCarthy's fixed set of base registers is the root set from which reachability is traced; the paper does not name the call stack or global variables as roots.

    “accessible to the program is accessible because it can be reached from one or more of the base registers by a chain of car and edr operations”

    Read by an automated reader; not a human review. How support was checked

• Meta-Symbolic Reflection
  • ) enabled programs to manipulate programs; Lisp's homoiconicity (McCarthy 1960

    SupportedVerified against the work's full text

    McCarthy translates Lisp functions into S-expressions, the same list form as data, and defines a universal apply/eval over them; the word homoiconicity is not used.

    “to be able to use S-functions for making certain computations with S-functions”

    Read by an automated reader; not a human review. How support was checked

• Recursion
  • The function-defined-in-terms-of-itself structure

    SupportedVerified against the work's full text

    McCarthy defines functions recursively, adding the label notation so an expression can refer to the function itself, and notes that recursive routines call themselves.

    “the routine for a recursive function uses itself as a subroutine.”

    Read by an automated reader; not a human review. How support was checked

Mechanisms

• Tracing Mark-Sweep Cycle
  • The technique traces back to John McCarthy's original garbage collector for Lisp.

    This sourceIntroduces Lisp’s garbage collector, including tracing accessible list structure and reclaiming inaccessible cells, in McCarthy’s original 1960 paper.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 3 of 4 citations: 2 supported, 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:d31779e054b6 · see in the full table