11 ms·
Bone Lisp – Lisp Without Garbage Collection
- hkjgkjy 10y agoSince ulisp (lisp for Arduino) came up on HN the other day, I've been trying to implement a lisp in C with garbage collection that will run on my x86 machine (your usual macbook). It being my first ever "real" c program, I'm not quite there yet. Very curious to read more source code of small languages, preferably things that are implemented in one file only.
- gte525u 10y agoHave you looked at scheme from scratch[1]? [1] http://peter.michaux.ca/articles/scheme-from-scratch-introduction http://peter.michaux.ca/articles/scheme-from-scratch-introdu...
- rjsw 10y agoHave you looked at lisp500 ?
- codezero 10y agoHave a look at this if you want a guide: http://www.buildyourownlisp.com http://www.buildyourownlisp.com
- baldfat 10y agoLook here is a Racket (My Favorite Lisp) https://github.com/fraimondi/racket-asip https://github.com/fraimondi/racket-asip A Racket client for the Arduino Service Interface Protocol (ASIP)
- drhodes 10y agoNorvig's lispy (lisp in python) is a good one, http://norvig.com/lispy.html http://norvig.com/lispy.html
- RodgerTheGreat 10y agoPerhaps you'd enjoy some of my old Forth projects. I designed a portable VM with a Forth-based development toolchain and standard library. Included among the programs I wrote using this system were a variety of compilers and interpreters. FiDo, a tiny JIT compiler: https://github.com/JohnEarnest/Mako/blob/master/demos/FiDo.fs https://github.com/JohnEarnest/Mako/blob/master/demos/FiDo.f... A Logo interpreter: https://github.com/JohnEarnest/Mako/blob/master/demos/Loko/Loko.fs https://github.com/JohnEarnest/Mako/blob/master/demos/Loko/L... A garbage collector used by a number of games and programs: https://github.com/JohnEarnest/Mako/blob/master/lib/Algorithms/Garbage.fs https://github.com/JohnEarnest/Mako/blob/master/lib/Algorith... A custom systems programming language targeting the VM (Java) https://github.com/JohnEarnest/Mako/tree/master/tools/Stroyent https://github.com/JohnEarnest/Mako/tree/master/tools/Stroye...
- DonHopkins 10y agoWow, a full blown Logo interpreter written in Forth! Very cool! Nice looking code. Thanks for sharing!
- RodgerTheGreat 10y agoLoko (and many of the other programs) can be run interactively here: http://johnearnest.github.io/Mako.js/?rom=Loko http://johnearnest.github.io/Mako.js/?rom=Loko Unfortunately some browsers have decided that backspace should navigate back, which makes typing at the Loko REPL rather awkward.
- erik14th 10y agohttps://github.com/JeffBezanson/femtolisp https://github.com/JeffBezanson/femtolisp
- akkartik 10y agohttp://akkartik.name/post/wart http://akkartik.name/post/wart
- munificent 10y agoIf you just want a GC, here's a tiny one I wrote: https://github.com/munificent/mark-sweep https://github.com/munificent/mark-sweep And an article I wrote about it: http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar... This was the inspiration for uLisp's GC (http://www.ulisp.com/show?1AWG http://www.ulisp.com/show?1AWG). :) If you want a more full-featured but still small language in C, you could take a look at Wren: http://wren.io/ http://wren.io/ https://github.com/munificent/wren https://github.com/munificent/wren
- hkjgkjy 10y agoI am using your blog post about the mark and sweep-GC for my program! Thank you for publishing it! Very informative, entertaining and to-the-point. Thank you!
- munificent 10y agoYou're welcome! I'm glad you enjoyed it. It was a lot of fun to write.
- kxyvr 10y agoDepending on how neurotic you want to get, Andrew Appel spent years working on SML and other functional programming language compilers and has written a few books about how to do it well. Namely, Compiling with Continuations: http://www.amazon.com/Compiling-Continuations-Andrew-W-Appel/dp/052103311X http://www.amazon.com/Compiling-Continuations-Andrew-W-Appel... and Modern Compiler Implementation in ML: https://www.cs.princeton.edu/~appel/modern/ml/ https://www.cs.princeton.edu/~appel/modern/ml/ There's a certain kind of equivalence between continuations and SSA. Mostly, I bring that up because if you go down the rabbit hole of designing a compiler in C, you'll find talk of SSA, but continuations are somewhat advantageous for designing functional compilers. If you're just looking to design an interpreter, Ben Pierce's book Types and Programming Languages does a good job at showing how to put together a simple functional language both theoretically and practically: https://www.cis.upenn.edu/~bcpierce/tapl/ https://www.cis.upenn.edu/~bcpierce/tapl/
- sesquipedalian 10y agoVery bare-bones implementation in one source file (+ 1 header) https://github.com/pedro-onate/eva/tree/84a62881c610ef23f9f1ac9e6199bca105d5acb9 https://github.com/pedro-onate/eva/tree/84a62881c610ef23f9f1.... Later versions include GC, and bytecode compiler + VM. Edit: I highly recommend SICP (dense, but elegant), and Matt Might's blog as resources.
- e12e 10y agoAll the other comments here are good. You might also want to take some advice from the SICL-project -- don't bootstrap from C, bootstrap from (a) lisp. If not Common Lisp, maybe Racket? (Not that writing a lisp is a bad way to learn C of course!) [1] "A Modern Implementation of the Common Lisp LOOP Macro", European Lisp Symposium https://www.youtube.com/watch?v=ZJr81DtSwUc https://www.youtube.com/watch?v=ZJr81DtSwUc https://github.com/robert-strandh/SICL https://github.com/robert-strandh/SICL
- amelius 10y agoIt would be cool if the garbage collector could be written in the language itself.
- openasocket 10y agoIn this case a garbage collector is unnecessary. In this Lisp, list structures are immutable, which means it is impossible to create a list with a cycle. Thus, the interpreter can use basic reference counting without fear that anything will leak.
- amelius 10y agoHow about closures? Don't they allow cycles to be formed?
- agentgt 10y agoI think because everything is immutable and because lexical scoping I can't figure how this would happen other than a direct cycle which I think the reference counting might be able to figure out. I am curious as well though. Maybe you could show an example?
- pklausler 10y agoIn Haskell, data are immutable and yet cyclic structures are possible. allOnes = 1 : allOnes
- openasocket 10y agoThis is possible in Haskell because it allows for lazy evaluation. In a strict language, immutability means you can't form cycles.
- pklausler 10y agoWhile non-strict evaluation helps with forming cyclic structures in general, in this specific example it is not required. You just need a language that allows names to appear in their bindings, such as in C: struct node { int x; struct node *next; } allOnesList = { 1, &allOnesList }, *allOnes = &allOnesList;
- michaelfeathers 10y agoThis makes me wonder whether it would be worthwhile to design languages with no garbage collection or manual deallocation. Non-stack memory can be allocated but never freed, and memory exhaustion would be fatal. We might be at the point where this is an acceptable simplification for very fine grained processes and services. Has anyone explored this model?
- openasocket 10y agoThis project uses reference counting to deallocate memory, so memory is being freed when it is no longer used. However, the paradigm you're referring to is interesting. Short-living processes that allocate little memory could work. Also, servers could use this model: create a slab of memory for each request, and allocate memory on that slab when processing the request. When the request is completed, you can free the entire slab at once. I know the Ur language does something like this.
- pjmlp 10y agoThis is called regions and was quite common a few decades ago.
- Kristine1975 10y agoWhich are used by Bone Lisp: It uses explicit regions instead of garbage collection. Explicit regions are both very simple and very fast, but how far can one get with them? I want to find out, so I am developing this interpreter. So we've come full circle.
- pjmlp 10y agoTo come full circle we would need people to accept the great research done at Burroughs, DEC/Olivetti, Royal Navi, Xerox PARC, Genera, ETHZ, MSR... in what concerns safe systems programming.
- 10y ago
- awt 10y agoGarbage collection should be in the hardware.
- toolslive 10y agoIntel tried this in the early 80s: https://en.wikipedia.org/wiki/Intel_iAPX_432 https://en.wikipedia.org/wiki/Intel_iAPX_432
- adrianratnapala 10y agoWow, the iAPX 432 sounds really cool. It contains a lot of ideas that I wish had taken off. Pity it failed. That failure might prove that those ideas were bad. But I think it just proves that MS-DOS compatibility is really, really important. Weep for humanity.
- awt 10y agoAnd SMBX.
- johnhattan 10y agoAs someone who hasn't dealt with Lisp since the 1980's, help me out here. Immutable structures and Lisp seems to be incompatible, as Lisp's lists are about the most mutable things you'll ever see. If, for example, I want to put a value into the middle of a list, would I be doing something akin to. . . MyList = MyList.firstHalf + NewValue + MyList.secondHalf? And how doesn't this become a horrible bottleneck?
- gosub 10y agostructural sharing is what clojure does. But you can have immutable data structures in old lisps if you only use cons, car and cdr, avoiding set-car and set-cdr.
- bch 10y agoI wonder if you could use ropes[0]. [0] https://en.wikipedia.org/wiki/Rope_%28data_structure%29 https://en.wikipedia.org/wiki/Rope_%28data_structure%29
- sklogic 10y agoDo not put a value into a middle of a list. Read Chris Okasaki, "Purely functional data structures" for better options.
- rrradical 10y agoGenerally you build the new list using the tail of the old list (which is unchanged), your inserted value, and each of the values in front inserted onto that. So, immutability is preserved. Any existing references will not see their values changed. And the new references will share some memory with the old ones (how much depends on where in the list the value was inserted). You can learn more in Okasaki's great book: http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...
- mwfunk 10y agoI may be misreading this, but isn't that an example of lists being immutable rather than pervasive mutability?
- 10y ago