In 1958, John McCarthy was thinking about a symbolic differentiation program in a programming language that was later to become Lisp. He was concerned about the “erasure problem”: no-longer-needed list structure needs to be recycled for future use. In subsequent languages, such problems were handled either by the structure of the program being restricted to trees (stack allocation of data and its trivially automatic deallocation through stack popping) or by explicit allocation and deallocation (malloc/free). His comment on erasure / explicit deallocation:
The recursive definition of differentiation made no provision
for erasure of abandoned list structure. No solution
was apparent at the time, but the idea of complicating
the elegant definition of differentiation with explicit
erasure was unattractive.-John McCarthy
It’s worth a pause to notice the style of research described. McCarthy and his colleagues were trying to design a programming language. Part of their methodology was to write the program they thought should be able to do the job and not the program that a compiler or execution system would require to make the program run well. In fact, the beauty of the program was foremost in their minds, not correctness down to the last detail. Beauty. Remember that word.
Eventually the first Lisp implementers decided to ignore the bug—the fault of not explicitly erasing abandoned list cells, causing the error of unreachable cells accumulating in memory, leading to a failure to locate a free cell when one is expected—until the failure occurred and to repair it then. This avoided the problem of entangling a common set of functionality (keeping available all the memory that should be) with a pure and clear program (symbolic differentiation). The failure the fault eventually caused was repaired, along with a lot of other similar errors in a process named at the time and still called garbage collection.
What are you waiting for read the whole thing. It's awesome and will make you think about how we can write better software. The garbage collection story put a smile on my face. "Beauty. Remember that word." I couldn't have said it better. We should always strive for beauty in our designs.