In the first three parts of this series (ALGOL, Simula, and Smalltalk), we've tracked the evolution of structured programming into object-oriented programming. Occasionally along the way, I've mentioned that languages inherited a feature or two from Lisp. We're now going to retrace our steps to 1958, to one of the first-ever high-level languages, and one which still provides a lot of inspiration to language designers: Lisp.
Lisp was the very first programming language to provide automatic garbage collection, based on a stop-the-world mark-and-sweep model. Periodically, the collector would interrupt the program, stop its running, follow every pointer from a small set of roots, and then collect all memory that it hadn't managed to reach.
By modern standards, this design is very primitive; modern Lisp implementations use concurrent generational garbage collection, as do other languages such as Java. For the time, however, that first garbage collection approach was innovative. The programmer didn't have to think about memory allocation; he just had to put up with occasional (brief) pauses.
It's interesting to note that garbage collection is seen as a fairly heavy feature in modern languages, when the original Lisp implementation ran on a machine that only supported about 30,000 words of memory.