6 ms·
Lively Linear Lisp – 'Look Ma, No Garbage!' (1992) [pdf]
- ogogmad 4y agoIs it possible to simulate a Turing machine in Linear Lisp without using exponential memory?
- abecedarius 4y agoCan't you represent the tape as a pair of lists of symbols? Why would that go exponential?
- ogogmad 4y agoI agree, that should work. Thanks.
- ogogmad 4y agoWhat's the difference between PUSH and CONS? Also, what does the free-list register do?
- ravi-delia 4y agoFor 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.
- twic 4y agoPUSH 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).
- mtreis86 4y agoThe 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)
- hayley-patton 4y agoCareful - push is a macro which modifies the value bound to "list", but doesn't modify any of the cons cells in that list.
- mtreis86 4y agoSo no rplaca/d, just cons and setf?
- hayley-patton 4y agoRight.
- ogogmad 4y agoI 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 4y agoI 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.5002&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31...
- ithkuil 4y agoWhy not inserting a call to free automatically instead of forcing you to do it manually?
- southerntofu 4y agoIsn'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 4y agoYou'd use automatic reference counting, as Swift and Nim do.
- southerntofu 4y ago
- dang 4y agoRelated: Lively Linear Lisp – 'Look Ma, No Garbage' (1992) - https://news.ycombinator.com/item?id=20369522 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 https://news.ycombinator.com/item?id=14248419 - May 2017 (18 comments)