[HN Gopher] Lively Linear Lisp - 'Look Ma, No Garbage!' (1992) [...
___________________________________________________________________
Lively Linear Lisp - 'Look Ma, No Garbage!' (1992) [pdf]
Author : Tomte
Score : 75 points
Date : 2022-08-08 11:33 UTC (11 hours ago)
(HTM) web link (dl.acm.org)
(TXT) w3m dump (dl.acm.org)
| ogogmad wrote:
| Is it possible to simulate a Turing machine in Linear Lisp
| without using exponential memory?
| abecedarius wrote:
| Can't you represent the tape as a pair of lists of symbols? Why
| would that go exponential?
| dang wrote:
| Related:
|
| _Lively Linear Lisp - 'Look Ma, No Garbage' (1992)_ -
| https://news.ycombinator.com/item?id=20369522 - July 2019 (39
| comments)
|
| _Lively Linear Lisp - 'Look Ma, No Garbage' (1991)_ -
| https://news.ycombinator.com/item?id=14248419 - May 2017 (18
| comments)
| ogogmad wrote:
| I must be missing something because I don't see how this is an
| advance over anything. You have a FREE function, so use-after-
| free at runtime is still possible. Why not just have malloc and
| free together then, and program in C but without any lexical
| scoping so that "Look ma no garbage"?
|
| [edit]
|
| I see why C without scoping would still produce garbage:
| int* foo = malloc(sizeof(int)); foo = null;
|
| Linear Lisp forces you to clean up memory. It doesn't allow
| complex data structures to be assigned to variables without
| moving the existing contents of those variables elsewhere where
| they can be disposed of later.
| kryptiskt wrote:
| I don't know about Linear Lisp, but if you do linear types as
| in Wadler's "Linear Types Can Change the World"[0] then the
| absence of the call to free would be a compilation error.
|
| [0]
| https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31...
| ithkuil wrote:
| Why not inserting a call to free automatically instead of
| forcing you to do it manually?
| whateveracct wrote:
| 1. When you call free matters - it does something after
| all!
|
| 2. You can build abstractions that call free for you. The
| common withX callback-style function can be better typed
| with linear types and call free for you, for instance.
| southerntofu wrote:
| Isn't that exactly why Rust needs lifetime annotation and
| Drop trait implementations? How could you achieve the same
| result without that, or without a garbage collector
| alternatively?
| shirleyquirk wrote:
| You'd use automatic reference counting, as Swift and Nim
| do.
| southerntofu wrote:
| Good point! I had previously assumed this was considered
| a form of "garbage collector" although not tracing.
| pjmlp wrote:
| Because it is based on linear types, not affine types.
|
| With affine types, like Rust, you can use a type zero or one
| times, with linear types you must use it exactly once.
|
| So not calling free() as per all possible dataflow analysis,
| would be a compilation error.
|
| By the way, this is the approach adopted by Haskell with Linear
| Haskell extensions.
| ogogmad wrote:
| What's the difference between PUSH and CONS?
|
| Also, what does the free-list register do?
| twic wrote:
| PUSH is just an alias for CONS, useful for emphasising that
| you're working with a stack.
|
| The free list holds all the cons cells not in use. Note that in
| this machine, there is no way to create or destroy cons cells -
| that's the whole point! Rather, when you need to cons some
| values, you pull a cell off the free list and populate it (see
| the implementation of CONS), and when you want to throw a cons
| cell away, you put it back on the free list (see the
| implementations of POP and FREE).
| ravi-delia wrote:
| For the former, "push x list" is to "cons x list" as "var += 7"
| is to "var + 7". It's just syntactic sugar to modify a
| variable.
| mtreis86 wrote:
| The main difference, in Common Lisp at least, is that push
| modifies the list to add the new cell. Cons returns a new list
| with the cell added so the old list remains untouched.
| CL-USER> (let ((list (list 1 2 3 4))) (cons 5
| list) list) (1 2 3 4) CL-
| USER> (let ((list (list 1 2 3 4))) (push 5
| list ) list) (5 1 2 3 4)
___________________________________________________________________
(page generated 2022-08-08 23:01 UTC)