proomt

Search

Search posts, papers, and topics

Hall of Fame

Hall of FameJohn McCarthy196043 min readpaperadvanced

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

Read on stanford.eduHN 4·1 comments

Summary

This seminal 1960 paper by John McCarthy introduces LISP, a programming system for symbolic expression manipulation. It formalizes recursive functions using S-expressions, S-functions, and the novel concept of conditional expressions, laying the groundwork for functional programming.

  • Introduced LISP (LISt Processor) for symbolic computation, initially for AI's "Advice Taker".
  • Formalized recursive function definitions using "conditional expressions" (e.g., (p1 -> e1, T -> e2)).
  • Defined S-expressions and S-functions as the core computational model, independent of hardware.
  • Described apply as a universal S-function, acting as both a theoretical universal Turing machine and a practical interpreter.

This paper is a foundational text in computer science, essential for anyone interested in the origins of functional programming, AI, and the LISP language.

10/10
functional programminghistoryprogramming languagesrecursionlisplambda calculus

Related reading

  3. Why Functional Programming Matters

    Hughes argues that functional programming’s real power lies in higher‑order functions and lazy evaluation, which act as new kinds of "glue" for modular design. He illustrates this with foldr and examples ranging from list processing to alpha‑beta pruning, showing how these features simplify and reuse code.

    Hall of Famekent.ac.uk38 minpaperHN102103

  4. Article: Your Next DSL Author Is a Language Model

    Typed Domain Grounding (TDG) embeds a DSL inside a mainstream language the LLM already knows (e.g., Kotlin) and uses the host compiler as an oracle. The author describes five building blocks—embedding, choosing a host language with high training‑data frequency, compiler‑driven type safety, a generate‑compile‑repair loop, and an on‑demand teaching tool—and shows measured results from kUML, a Kotli…

    InfoQinfoq.com18 min

  5. Structured Programming with go to Statements

    Knuth's 1974 paper examines the `goto` statement controversy in structured programming, arguing for a balanced view rather than outright abolition. It explores how improved language constructs can reduce `goto` usage, while also considering cases where `goto` or equivalent constructs might be necessary for efficiency or clarity in transformed code.

    Hall of Fameplover.com130 minpaperHN3

  6. Recursive self-improvement of AI research agents

    The paper introduces AIDE², an AI research agent that rewrites its own code, benchmarks each version, and adopts the best performing changes—a process they call recursive self‑improvement. In an 8‑day autonomous run it produced seven improvements that beat a strong human‑engineered baseline on four unseen benchmarks and reduced reward‑hacking from 55 % to 32 %.

    Hugging Face Daily Papersarxiv.org2 minpaper