An Algebraic Language for the Manipulation of Symbolic Expressions (1958) [pdf]
Postedabout 2 months agoActiveabout 2 months ago
softwarepreservation.computerhistory.orgTechstory
calmpositive
Debate
20/100
LispProgramming LanguagesHistory of Computing
Key topics
Lisp
Programming Languages
History of Computing
A 1958 paper on an algebraic language for symbolic expressions, precursor to Lisp, is shared and discussed, with commenters highlighting its historical significance and connections to modern Lisp features.
Snapshot generated from the HN discussion
Discussion Activity
Light discussionFirst comment
2h
Peak period
3
2-3h
Avg / period
1.6
Comment distribution11 data points
Loading chart...
Based on 11 loaded comments
Key moments
- 01Story posted
Nov 8, 2025 at 9:58 AM EST
about 2 months ago
Step 01 - 02First comment
Nov 8, 2025 at 12:16 PM EST
2h after posting
Step 02 - 03Peak activity
3 comments in 2-3h
Hottest window of the conversation
Step 03 - 04Latest activity
Nov 9, 2025 at 12:32 AM EST
about 2 months ago
Step 04
Generating AI Summary...
Analyzing up to 500 comments to identify key contributors and discussion patterns
ID: 45857045Type: storyLast synced: 11/20/2025, 9:01:20 PM
Want the full context?
Jump to the original sources
Read the primary article or dive into the live Hacker News thread when you're ready.
> Herbert Stoyan's historical work on early Lisp http://www.mcjones.org/dustydecks/archives/2010/07/29/185/ https://web.archive.org/web/20050617031004/http://www8.infor... is probably worth reading if one is seriously interested. (I haven't read much of it myself yet.) McCarthy praised Stoyan's work as better than his own 1979 HOPL paper ( http://www-formal.stanford.edu/jmc/history/lisp/lisp.html ): "Stoyan's reading of the early LISP documents gives a more accurate picture than my own memories turned out to have given." http://www-formal.stanford.edu/jmc/history/
> (As a side-note, I'm pretty sure that the broken, Wayback-beating link to "Lisp references according to Miller" on McCarthy's page is to this http://www.ai.sri.com/~delacaze/alu-site/alu/table/Lisp-Hist... document by Kent Pitman and Brad Miller (see http://www.ai.sri.com/~delacaze/alu-site/alu/table/history.h... ).)
From 2015-2018, "The Mysteries of Lisp -- I: The Way to S-expression Lisp" by Hong-Yi Dai https://arxiv.org/abs/1505.07375 ( https://news.ycombinator.com/item?id=31153702 )
> Despite its old age, Lisp remains mysterious to many of its admirers. The mysteries on one hand fascinate the language, on the other hand also obscure it. Following Stoyan but paying attention to what he has neglected or omitted, in this first essay of a series intended to unravel these mysteries, we trace the development of Lisp back to its origin, revealing how the language has evolved into its nowadays look and feel. The insights thus gained will not only enhance existent understanding of the language but also inspires further improvement of it.
1958-10: AIM-003 (the special form "maplist", i.e. a kind of "forall" iteration)
1958-10: AIM-004 (anonymous function definitions using "lambda"; the special form "select", which already at that early date had better syntax and semantics than the "switch" or "case" statements of later languages; the special form "search")
1959-03-13: AIM-008 (the special form "quote"; the special form "label", for defining anonymous recursive functions; also the special forms "and" and "or", a.k.a. McCarthy AND and McCarthy OR, inherited by many languages, including C)
CAR = Contents of Address Register, corresponding to the head element of a list.
CDR = Contents of Decrement Register, corresponding to a pointer to the "rest" of a list, i.e. to a machine word containing the next link in the list.
This is hinted at in the paper by this:
> "Each computer word of a list in addition to containing a datum also contains the address of the word containing the next element of the list. 0 for the address of the next element indicates the last element. If one element of an expression is a subexpression the word corresponding to this element contains the address of the word containing the first element of the subexpression. In the IBM 704 or 709 whose 36 bit word is divided (for the convenient use of certain machine instructions) into two 15 bit parts (address and decrement) and two 3 bit parts (prefix and tag) lists are represented by storing in the decrement part of a word the address (in our system actually the complement of the address) of the next word or the list."
The choice of names is rather implementation-specific (and if memory serves, this may have been a choice by the person who coded the original LISP interpreter, not McCarthy himself.) But the mapping of the abstract concept of a linked list to a usable machine representation, built into the core of a programming language, was impressive. FORTRAN and COBOL had nothing like this.
"The other main advantage of the algebraic notation for list structure processing was first noticed by Gelernter."
That's one of the authors of the Fortran-compiled List-processing Language (FLPL) in which thef unctions XCARF and XCDRF were introduced.
MacCarthy drops a hint that he actually had something to do with Gelernter's work and his choices:
"Algebraic notation for list processing is not used by Net'Jell, Simon and Shaw, pelhaps beaause to do so is most convenient when a compiler is available, but is used by Gelernter in the geometry program. This was accomplished (on the advice of the present author) by using the Fortran compiler together with a set of machine language coded functions for handling the primitive list processes that go from one element of a list to the next"