5 ms·

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

theseoafs 10y ago
I assure you that "malloc" and "free" don't "provide the illusion of infinite memory". Quite the opposite, in fact.
- stcredzero 10y ago
  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.)
  - Ericson2314 10y ago
    This...is not possible?
    - rntz 10y ago
      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.
      - stcredzero 10y ago
        You win a stcredzero "no-prize!"
- pjmlp 10y ago
  They do if always matched 1:1, it doesn't usually happen, specially in big codebases, thus leading to CVEs.
  - theseoafs 10y ago
    They surely do not. Malloc is specified in such a way such that the request for memory can fail (which leads to returning NULL).
    - rntz 10y ago
      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.
      - amag 10y ago
        Actually there is one reason for malloc to return NULL even with virtual memory, your process can run out of address space.
        roganp 10y ago
        Or run out of room in the paging file. Your addressable memory cannot be larger than physical memory without a backing store.
        prodigal_erik 10y ago
        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).
    - pjmlp 10y ago
      Assuming that the OS APIs used by malloc() do tell the application about OOM.
- MaulingMonkey 10y ago
  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.
pg314 10y ago
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 http://www-formal.stanford.edu/jmc/history/lisp/node3.html [2] https://www.csee.umbc.edu/courses/331/resources/papers/Evolution-of-Lisp.pdf https://www.csee.umbc.edu/courses/331/resources/papers/Evolu...
- rntz 10y ago
  "saving the world to disk and rebooting" sounds like a primitive form of garbage collection to me :)
  - pg314 10y ago
    It is. From that second link: "Such copying back and forth to disk was equivalent to a slow, manually triggered copying garbage collector."
- qwertyuiop924 10y ago
  McCarthy's writing style is highly entertaining. Although I still have no idea what "Pornographic Programming" is...
  - __jal 10y ago
    I'm only guessing, but it seems like he means "impure functions", e.g., side effects.
  - DonHopkins 10y ago
    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 http://lambda-the-ultimate.org/node/3186
panic 10y ago
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.
kazinator 10y ago
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.

theseoafs 10y ago

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

stcredzero 10y ago
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.)
- Ericson2314 10y ago
  This...is not possible?
  - rntz 10y ago
    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.
    - stcredzero 10y ago
      You win a stcredzero "no-prize!"
pjmlp 10y ago
They do if always matched 1:1, it doesn't usually happen, specially in big codebases, thus leading to CVEs.
- theseoafs 10y ago
  They surely do not. Malloc is specified in such a way such that the request for memory can fail (which leads to returning NULL).
  - rntz 10y ago
    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.
    - amag 10y ago
      Actually there is one reason for malloc to return NULL even with virtual memory, your process can run out of address space.
      - roganp 10y ago
        Or run out of room in the paging file. Your addressable memory cannot be larger than physical memory without a backing store.
        prodigal_erik 10y ago
        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).
  - pjmlp 10y ago
    Assuming that the OS APIs used by malloc() do tell the application about OOM.
MaulingMonkey 10y ago
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.

pg314 10y ago

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 http://www-formal.stanford.edu/jmc/history/lisp/node3.html [2] https://www.csee.umbc.edu/courses/331/resources/papers/Evolution-of-Lisp.pdf https://www.csee.umbc.edu/courses/331/resources/papers/Evolu...

rntz 10y ago
"saving the world to disk and rebooting" sounds like a primitive form of garbage collection to me :)
- pg314 10y ago
  It is. From that second link: "Such copying back and forth to disk was equivalent to a slow, manually triggered copying garbage collector."
qwertyuiop924 10y ago
McCarthy's writing style is highly entertaining. Although I still have no idea what "Pornographic Programming" is...
- __jal 10y ago
  I'm only guessing, but it seems like he means "impure functions", e.g., side effects.
- DonHopkins 10y ago
  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 http://lambda-the-ultimate.org/node/3186

panic 10y ago

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.

kazinator 10y ago

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.