8 ms·
Lisp interpreter with GC in <750 lines of Odin (and <500 lines of C)
- gritzko 1y agoIt lacks a conclusion, except I can see that 750>500
- krig 1y agoThis is my project! I made the Odin version to learn the language, not to create a 1:1 comparison. I 100% prefer Odin over C and will use it wherever I can where I would have otherwise used C. Also I've moved it from Github to my own Forgejo instance: https://git.liten.app/krig/LISP https://git.liten.app/krig/LISP My impression of Odin is that it's a better C while still very much retaining the same flavor as C. It adds very little (no classes, no runtime) so porting from C is very straightforward, and it fixes a lot of the dark corners of C. It also seems to be pretty much finished as far as the language goes, so no big incompatible changes coming as far as I can tell. I would say though that while the memory management story is vastly better than C^, it's still manual as fuck, so be prepared for that. ^: There's builtin test support, bounds checking and an optional leak detection allocator, plus as far as I know no UB.
- krig 1y agoMaybe the most interesting part is the semi-space garbage collector. The whole thing fits in a single screen: https://git.liten.app/krig/LISP/src/branch/main/komplodin.odin#L92 https://git.liten.app/krig/LISP/src/branch/main/komplodin.od... Andy Wingo has a good summary of how a very similar implementation works: https://www.wingolog.org/archives/2022/12/10/a-simple-semi-space-collector https://www.wingolog.org/archives/2022/12/10/a-simple-semi-s...
- psychoslave 1y agoDoes it get ride of undefined behavior and the tradition of obfuscating the code with monoletter identifiers?
- krig 1y agoYes. There is no undefined behavior in Odin (afaik), and I haven’t seen many monoletter identifiers. There is a slice type and a for … in loop statement so that gets rid of most i:s and j:s.
- tialaramex 1y ago> There is no undefined behavior in Odin This mostly just ends up meaning that Odin's creator Ginger Bill will engage in pointless semantic arguments in which he defines away your problem. There are places where C could reasonably have chosen to define what happens, or to make it Unspecified rather than Undefined, and so that's what Odin chooses, which is a meaningful benefit. However there are plenty of situations left in which what you've written would be UB in C and absolutely anything might happen, while in Odin absolutely anything might happen but Bill insists it isn't UB.
- krig 1y agoWell, without concrete examples this just sounds childish TBH. But I haven’t looked very closely at it myself, hence the afaik qualifier.
- tialaramex 1y agoSo as a concrete example: https://odin.godbolt.org/z/8onn4hxP1 https://odin.godbolt.org/z/8onn4hxP1 This brief example makes a hash map, then it demonstrates that if we call a sub-routine which makes its own distinct hash map, that doesn't change ours, but, once we destroy our hash map and call the sub-routine again, we can still use the variable for our (destroyed) hash map (!) but doing so reveals the contents of that other hash map from the sub-routine instead in the cases I saw. Now, in C or C++ if you do this that's Undefined Behaviour and the symptoms I saw (and which you're likely to see if you follow the link) are just one of arbitrarily many ways that could manifest. In Rust of course the equivalent code won't compile because the hash map is gone so we can't just go around using it after that. And in Odin, well, as Ginger Bill has explained Odin does not have Undefined Behaviour so... this has behaviour which er, Odin has not defined ? Does that make you feel warm and tingly or do you feel like Bill just wasted time arguing semantics?
- fithisux 1y agoAt first look the Odin version seems less verbose. The function/struct definition in C could be placed in a header.
- jll29 1y agoThanks for sharing. Not knowing Odin's syntax yet, having had a quick look at the code, a few things are strange: Are there two types of assignment? p1[0] = 0 ... n := 0 What should this mean? The comma notation usually indicates a pair or left-to-right control flow (Python and C, respectively), but why (appear to) assign a pair to itself? This probably means something else, but it reads odd. car, cdr := car, cdr If Odin is so similar to C, what are the "dark corners" where it outshines it?
- krig 1y ago> Are there two types of assignment? > > p1[0] = 0 > ... > n := 0 >What should this mean? The comma notation usually indicates a pair or left-to-right control flow (Python >and C, respectively), but why (appear to) assign a pair to itself? This probably means something else, but it reads odd. = is assignment and := is assignment and declaration. x := 1 // create a new variable x with the value 1 x = 2 // assign 2 to x y = 3 // error: y does not exist You can explicitly give the variable a type by adding it before the = x : u8 = 1 // a one byte unsigned integer with the value 1 There is also :: for constants. > car, cdr := car, cdr Odin has multiple assignment like Python, so this is a swap without temporary. edit: No, it isn't! Didn't read carefully. Swap would be car, cdr = cdr, car This one is because parameters are immutable in Odin, so to get a mutable copy in the function we have to declare it. > If Odin is so similar to C, what are the "dark corners" where it outshines it? Off the top of my head: - No undefined behaviour - Builtin string type, dynamic array type, slices - Builtin map type - Excellent tooling for 3D math: swizzling, matrix math, array programming - Bounds checking - Tooling for memory management: leak detection, temp allocator, arena allocators - Builtin unit test framework - Tagged unions with exhaustiveness checked switch statement - for ... in loop syntax
- mrweasel 1y agoIs there something inherent to Lisp that allows it to be implemented in so little code? I believe I saw someone demonstrate that almost nothing in a Lisp implementation was written as a "built-in" language feature that required the underlying interpreter to provide the functionality.
- krig 1y agoFirst off, you wouldn’t write an actual interpreter for lisp like this if you wanted to use it for anything serious, it’s very slow. The parser is very simple thanks to the s-expressions, and the only builtin special forms really needed are quote, cond and lambda, that’s pretty much it. The only data structure is a list, so functions are just lists, function calls are lists etc.
- rollcat 1y agoLisp (and similarly, Forth) is closer to a mathematical construct than an actual language. We've had to wrap it in parentheses and named symbols to help make sense of it, to talk about it. Pairs, atoms, GCs, are all an implementation detail.
- giancarlostoro 1y agoI always think of this HN post every few years, as an aside, someone really needs to archive that page it links to because I wont be surprised when that site shuts down or deletes old content: https://news.ycombinator.com/item?id=9699065 https://news.ycombinator.com/item?id=9699065 https://speakerdeck.com/nineties/creating-a-language-using-only-assembly-language https://speakerdeck.com/nineties/creating-a-language-using-o...
- krig 1y agoThis is super cool! I could imagine writing a very basic forth or lisp compiler in assembler, but even that would be quite the project.
- baq 1y agosee previous discussions at https://news.ycombinator.com/item?id=14727881 https://news.ycombinator.com/item?id=14727881 quoting the submission verbatim: The original paper of LISP by John McCarthy http://www-formal.stanford.edu/jmc/recursive.html http://www-formal.stanford.edu/jmc/recursive.html Or the more accessible explanation by Paul Graham http://www.paulgraham.com/rootsoflisp.html http://www.paulgraham.com/rootsoflisp.html
- johnisgood 1y ago> When I posted this to lobste.rs, gingerBill (creator of Odin) was kind enough to make a more direct translation of the C code into Odin. Glad he has helped you. Maybe he listened to me, maybe not, but last time (almost year ago?) I saw an interaction with him on GitHub, he was nothing short of an a**hole, and not in the sense of Linus or Theo. In fact, he was not educational, he was just like "Many problems. I could write this better, GTFO". I saw it on GitHub, so I am reluctant to submit a PR of any sort myself in before he tells me he can implement it better and rejects my PR with this reasoning as he did with someone else. Like yeah, of course you may be able to implement it better, whereas someone new to the language might not, even though I tried it (the rejected PR, which was supposed to end up in vendor/ not the core library, AFAIK) and it was fully functional (and without any leaks), and to my eyes it seemed fine as well, but maybe I do not know Odin enough. In fact, I probably do not know it as much as he does, but by his logic, everything should be implemented by him because he knows better. This experience (albeit not mine) was enough to put me off of Odin. The C3 lead developer, on the other hand, was extremely helpful here on HN and on GitHub as well. I have a feeling he has helped you because of the article and some fame along with it. :) So my comment reflects a negative publicity. I cannot find the GitHub link right now, but it is there as it cannot be deleted, AFAIK. Look around rejected PRs in / for vendor/, I think. I am not logged in to GitHub and I cannot do so at the moment. Just my second-hand experience. Feel free to down-vote but please leave a comment afterwards. Not everyone and everything is sunshine and butterflies. The down-votes DO NOT invalidate anything. Or perhaps Bill's bots / fans are in play here. ;) God forbid someone voices negative experiences with a person. Only positives are allowed! I forgot...
- krig 1y agoSorry to hear that! I haven’t had any such experience, quite the opposite. But I’m also an old. If someone tells me my code is shit, 1) they are probably right, and 2) I don’t really care. I can probably look at their code and find flaws in it. In the end, Odin is Bills project and he decides what goes into it, I’m fine with that.
- johnisgood 1y agoFrom what I remember, it was supposed to land in vendor/ which is not the core standard library though. Additionally, it is one thing to say the code is shit, and another to say "too many things wrong, fuck off", all while the code did work properly! From what I recall the person said he will continue working on it anyway in his own git repository. I think he could have given pointers of these major flaws (I checked the code and I could not find anything either[1]), which could have not been too major if the code worked properly (there were test cases, it did actually work and there were no memory leaks either, FWIW). > In the end, Odin is Bills project and he decides what goes into it, I’m fine with that. Me too. I am just not going to contribute. No big deal. > I haven’t had any such experience, quite the opposite. Just to add some positive, too: I have had positive experiences with other contributors. In any case, I follow the programming language's developers before I contribute, as you may have noticed. [1] But then again, I do not know the language too well either. Those pointers would have helped me and many others.
- nmz 1y ago750 lines and 0 comments.
- krig 1y agoSome day I might write a walkthrough of it, but it’s just a toy really.
- drwu 1y agoThe antivirus program forced to be installed by my company does not allow .odin file to exist, as there is a ransomware which encrypts files into *.odin. Of course, git cloning the ALE plugin (linter + languageserver) for VIM also fails as ALE has an .odin file in its repo.