Hacker News Reader

Comment by crististm | Hacker News Reader

Garbage collection is not necessary for lisp. Garbage collection only provides the illusion of infinite memory. Just like malloc/free.

View on HN

And the implementation of garbage collection was, on at least two occasions, postponed. Once in the first implementation [1] and a second time in the early MIT Lisp Machines [2] (you just ran the machine until you ran out of memory which could take days or weeks, after which you saved the world to disk and rebooted).

[1] http://www-formal.stanford.edu/jmc/history/lisp/node3.html

[2] https://www.csee.umbc.edu/courses/331/resources/papers/Evolu...

"saving the world to disk and rebooting" sounds like a primitive form of garbage collection to me :)

It is. From that second link: "Such copying back and forth to disk was equivalent to a slow, manually triggered copying garbage collector."

McCarthy's writing style is highly entertaining. Although I still have no idea what "Pornographic Programming" is...

I suspect it has something to do with bondage and discipline.

"... decisions ... later proved unfortunate. These included ... the use of the number zero to denote the empty list NIL and the truth value false. Besides encouraging pornographic programming, giving a special interpretation to the address 0 has caused difficulties in all subsequent implementations." -John McCarthy

Maybe he considered NIL to be his own billion dollar mistake.

Tony Hoare / Historically Bad Ideas: "Null References: The Billion Dollar Mistake" [1]

"Abstract: I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years. In recent years, a number of program analysers like PREfix and PREfast in Microsoft have been used to check references, and give warnings if there is a risk they may be non-null. More recent programming languages like Spec# have introduced declarations for non-null references. This is the solution, which I rejected in 1965." -Tony Hoare

[1] http://lambda-the-ultimate.org/node/3186

I suspect it was more that ()-is-nil-is-false-is-0 is entirely visible to the programmer ("see through") rather than an implementation detail hidden by the language.

I still need the occasional reminder myself that nil is () is nil when writing Common Lisp code, lest I do un-idiomatic things like set a slot's initial value to '().

I'm only guessing, but it seems like he means "impure functions", e.g., side effects.

It's difficult to use malloc/free memory management in a language that supports closures, since ownership becomes very hard to keep track of statically.

I assure you that "malloc" and "free" don't "provide the illusion of infinite memory". Quite the opposite, in fact.

In practice, many programs ignore the fact that malloc can return NULL. As do some OSes and their implementations of malloc, if they support/enable/require overcommit. These are perhaps operating under "the illusion of infinite memory" (in the GC sense): free, in this context, is simply a way of marking data as invalid and no longer to be referenced - a method of poisoning data for debug purposes.

But of course, I've had malloc return NULL - very finite.

They do if always matched 1:1, it doesn't usually happen, specially in big codebases, thus leading to CVEs.

They surely do not. Malloc is specified in such a way such that the request for memory can fail (which leads to returning NULL).

The specification allows for this, yes. However, on some platforms (including linux glibc by default, I believe), malloc() never fails, but allocates virtual memory optimistically; the first you hear of an out of memory condition is when the system slows down due to paging, and the next thing you notice is when the OOM killer nixes a process.

Of course, other platforms, especially embedded ones, behave differently.

Actually there is one reason for malloc to return NULL even with virtual memory, your process can run out of address space.

Or run out of room in the paging file. Your addressable memory cannot be larger than physical memory without a backing store.

Depending on VM_OVERCOMMIT_MEMORY, Linux might give out address space well beyond the size of the pagefile, hoping many of those pages are never written to (e.g., most threads never get anywhere near the bottom of their default stacks).

Assuming that the OS APIs used by malloc() do tell the application about OOM.

Challenge: Write a Turing complete machine using a finite number of registers and a state machine. One or all of the registers can contain a rational number of unlimited precision. (This has already been done, so if you are aware of the existing machines, you have to create a new one.)

This...is not possible?

No, it's possible. The key insight is that a "rational number of unlimited precision" can be used to store an arbitrarily large amount of data; it can emulate a Turing machine's unlimited working tape.

You win a stcredzero "no-prize!"

Some simple problems solved in simple can burn through gigabytes of allocations. Without GC, you are really crippled. Not to mention event processing loops (servers and such) which run indefinitely.

Reply on news.ycombinator.com