7 ms·
Lisp in fewer than 200 lines of C
- krat0sprakhar 9y agoReally cool! A more complete implementation in 1000 lines of C for getting started: http://www.buildyourownlisp.com http://www.buildyourownlisp.com
- whistlerbrk 9y agoCan't recommend it enough, I learned a lot from this tutorial. I hope to go back and add a lot more languages features.
- asveikau 9y agoNo calls to free() to match calloc(), no overflow checking in gettoken() and then I read this: > a program with missing or unmatched parenthesis, unresolved symbols, etc will likely just result in something like a segmentation fault. I understand this is just a fun thing to hack on, but this is an irresponsible way to write software. I hope no one here is reading this and thinking it's how they should be writing C.
- ythn 9y agoIf people always wrote software responsibly we'd have a great deal fewer interesting projects on GitHub
- tree_of_item 9y agoWould it really be so hard to do this exact same thing in a memory safe language? Would that stifle the author's creativity in any way?
- wyager 9y agoWriting Lisp in 200 lines of Haskell wouldn’t be nearly as interesting. The whole point is (presumably) that it’s fun to code golf in C because it’s not very expressive. Relax, no one is going to use the OP’s code to run a pacemaker.
- macintux 9y agoPeople often do what they love with the tools they love. Complaining that someone wrote a hobby project with C is akin to complaining that your neighbor made a decorative baseball bat with her lathe instead of a 3D printer.
- _RPM 9y agoDude, if you used Rust, you wouldn’t have that problem.
- fsloth 9y ago"but this is an irresponsible way to write software" Segfault is a totally safe way to terminate a process on a modern desktop os. Besides - there is no 'correct' way to write software.
- asveikau 9y agoSorry, this is wrong. A segfault means you got lucky and your bad memory access hit an unmapped or otherwise invalid page. Other times the program will keep running with incorrect results. Many such issues represent exploitable bugs. In any case it's a bad issue and should not be a normal failure mode for a syntax error.
- fsloth 9y ago"Other times the program will keep running with incorrect results. Many such issues represent exploitable bugs." None of which matter if it's a prototype, running on a developers machine. If you want memory safety you run the program through valgrind anyway with a large input dataset. And write unit tests. And integration tests. And so on. The baggage of production quality software development environment is so high it easily stifles the joy of quick and dirty prototypes. The main use of prototype is to facilitate understanding. This is the most critical constraint, whose needs drive over anything else. Besides, who on earth is going to exploit a few hundreds of lines of code a developer runs on his or her own machine?
- asveikau 9y agoI don't know if you noticed this but C hackers are a minority on here. Thus it's not unreasonable to think people get an impression of how C is done from submissions here. We owe it to the craft to serve as good examples. It's not as burdensome as you suggest.
- fsloth 9y agoI see your point, but respectfully disagree that an incomplete implementation should stop a submitter from sharing his or her discoveries. This is an aesthetic position - I think interesting ideas are more important than clean implementations (It is left as an exercise to the reader... is an ok position, IMO).
- ac2u 9y agoThe author isn't responsible if people read it and think it's how they should be writing C, especially when the objective of writing lisp in as little C as possible is communicated. So why is it fair to label it irresponsible?
- chii 9y agoit's not irresponsible, but copy/paste proliferation does exist, and happens surprisingly often with code posted online like this. When you write code for posting online, you'd want to consider this problem.
- sillysaurus3 9y agoIf you have to worry about the entire world whenever you do anything, you'll never get anything done.
- DSMan195276 9y agoI would add that there is already hundreds of implementations of Lisp in C and hundreds of little tutorials that are extremely similar to this online anyway, it's not like one more is going to make a difference. Yes, his C code could be a lot better, but at the end of the day it really doesn't matter and nobody is going to be using this for anything important.
- asveikau 9y ago> The author isn't responsible if people read it and think it's how they should be writing C, Seems we disagree on the basic premise then. If someone learns the wrong thing based on my example I view myself as responsible. (I have not been a perfect example all the time either. We owe it to ourselves and others to always improve on that front.)
- DonaldFisk 9y agoIt's a lot longer if it's done properly. You should use an array of dotted pairs to store your list elements, out of which you build a free list, from which you allocate by calling cons. To garbage collect, you mark all objects in use (on the stack, or accessible from the symbol table) and then you add the unmarked conses to the free list. You should not be using malloc or calloc at all, certainly not to implement cons. Below is some of the relevant code in C/C++ from the virtual machine of Emblem (the Lisp dialect I'm using to implement inter alia my visual dataflow language, Full Metal Jacket). To keep things short I haven't included initialization or the garbage collector. cons_op takes the top two stack entries (one on the stack, the other in tos), conses them, and returns it in tos. ------------------- typedef struct ListStruct { void *head; void *tail; } *List; static struct ListStruct consTable[NUM_CONSES]; static List freeStore; #define hd(X) (((List)(X))->head) #define tl(X) (((List)(X))->tail) #define NIL (void *)&consTable[0] #define null(X) ((X) == NIL) static void **stack; static void *tos; /* Top of stack register. */ static long sp; static void cons_op() { List x; if (null(freeStore)) { cons_gc(); } x = freeStore; freeStore = (List)tl(freeStore); hd(x) = stack[sp++]; tl(x) = tos; tos = x; } ---------------------- Alternatively, instead of C you could use a garbage collected language such as Java, C#, or Go, and then not have to worry about memory management.
- denisehilton 9y agonever knew svg could be so beneficial. It can literally optimize your image processing requirements.
- anonfunction 9y agoWrong thread?
- drdrey 9y agoLook at "denisehilton"'s post history, it's all spam
- luckydata 9y agosomebody's machine learning algorithms need better training.
- SonOfLilit 9y agoIf you like short interpreter implementations, you might like this: http://code.jsoftware.com/wiki/Essays/Incunabulum http://code.jsoftware.com/wiki/Essays/Incunabulum
- agumonkey 9y agoI love how it demonstrates how recursion/loops and shape/dimension based programming can be both thin, fast and generic
- tromp 9y agoor this interpreter of a lazy lambda calculus based language in 25 lines of (obfuscated) C: http://www.ioccc.org/2012/tromp/tromp.c http://www.ioccc.org/2012/tromp/tromp.c http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- piinbinary 9y agoAfter reading Peter Norvig's post about a lisp implementation [0], I decided to write one in Python. I got something working in 65 lines [1] [0] http://norvig.com/lispy.html http://norvig.com/lispy.html [1] https://gist.github.com/jmikkola/b7c6c644dff1c07891c698f0a527a890 https://gist.github.com/jmikkola/b7c6c644dff1c07891c698f0a52...
- Wohlf 9y agoThanks for this, I recently did the same and it's nice to have others work to compare to.
- Areading314 9y agoThis is more of historical interest than of technological interest...
- ColinWright 9y agoI think you are mistaken. There is much to learn from implementations such as this, and the techniques used form the basis of much more complex systems. The technology remains very relevant. FWIW, I didn't downvote you, as I don't downvote someone simply because I believe they're wrong, or because I disagree with them.
- sparkie 9y agoWhile I agree that it's not just historical interest - there's still much that can be learned from Lisp - this implementation is certainly not the place to learn it. There's no garbage collection, which is really the biggest concern of a proper lisp implementation in a language like C. Without GC, it's a gimmick implementation. There's no practical use for it.
- ColinWright 9y agoThere is much to be learned from incomplete, toy implementations. Not least, the interested reader can see if they can extend the existing implementation to include the missing features. Insisting that learners/students should only ever read and study complete, perfect implementations is, I think, a mistake. I've learned a great deal from studying, and subsequently improving and extending, implementations that are imperfect and incomplete.
- Trump4America 9y agoI'd be surprised if it was C in 200 lines of Lisp.
- akashakya 9y agoIf you like this, you might like Lisp interpreter written in assembly in a single file. It is one of the best commented code ever written imo. https://github.com/marcpaq/arpilisp https://github.com/marcpaq/arpilisp
- sparkie 9y agoAnother small lisp implementation: http://piumarta.com/software/lysp/ http://piumarta.com/software/lysp/ Also, another, more interesting Lisp by the same author: (http://piumarta.com/software/maru/ http://piumarta.com/software/maru/). Maru is basically a lisp where some of the core functions like eval and apply are extensible from user code. There's basically a global map of types to evaluators and applicators, with some functions for you to register your own types and get the evaluation behavior you want.
- fasquoika 9y agoIt seems like arpilisp is inspired by jonesforth[0]. Although not directly stated, the style is similar and the acknowledgements mentions Richard Jones. Anyone interested in implementing simple programming languages might also want to take a look at jonesforth. [0]: https://github.com/nornagon/jonesforth https://github.com/nornagon/jonesforth
- marcpaq 9y agoArpilisp author here. Yes, jonesforth definitely inspired and influenced me; that's why Jones is first in the Acknowledgements section. If you're curious, I keep a list of single-file implementations of programming languages (including jonesforth): https://github.com/marcpaq/b1fipl https://github.com/marcpaq/b1fipl
- _sdegutis 9y agoSince this is written in assembly is it much faster than a C version since this one can manage its own stack frames and stack variables and such? I always imagined that’s the case and that a lisp implemented fully in assembly would be the trick to a super fast lisp that can complete with Go.
- sago 9y agoWriting your own Lisp-ette is a brilliant evening or weekend project, regardless of the language. It's some of the simplest non-toy parsing you can attempt, a bit of light data structure work, and understanding eval/apply is 80% of the work in implementing it. I would highly recommend anyone to have a go, and try not to follow existing code too closely: figure out the problems in your language of choice. The post identifies some of it's own weaknesses (memory handling, errors), which are quite C specific. Or at least easier to handle in other languages, where you can punt those issues to the host language runtime. But it will be a fun extension to fix them (a job for the second evening / weekend of coding ;) ) But, imho, the beauty of writing a Lisp is that there are a bunch of things you can do from there, some more difficult, but several are achievable step-by-step in a day or a few days each. I'd first add a few special forms more than the OP (quote, if, progn, math operations), then my suggestions: 1. Defining names (if you haven't already), both let and define special forms. 2. Lambdas. 3. Tail call optimisation (I suggest this not because it's an optimisation, this Lisp doesn't need optimising, but because TCO is a bite-sized extension.) 4. Lexical scoping of lambdas. 5. Continuations. call/cc 6. And if you're really brave (or skilled, or just masochistic), macros. I was encouraged to do this as a new grad student, and it was one of the most fun and educational experiences I remember. I didn't get as far as macros back then, but implementing call/cc was a definite pivot point in my programming competence.
- quotemstr 9y agoLexical scoping is essential if you want to use the Lisp for anything essential. If you start with dynamic scope for everything and the system develops any real complexity, then switching to lexical scoping becomes very painful. Best to do it right the first time.
- tree_of_item 9y agoIf you go with (hygenic) fexprs instead of macros, they're both easier to implement and more expressive, at the expense of performance. Check out John Shutt's thesis for more information on hygenic fexprs: https://web.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf https://web.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr...
- Kenji 9y agoIf Lisp is so easy so implement, is it also easy to learn? (I am familiar with Haskell)
- jstanley 9y agoWhile this is very cool, it has at least one buffer overflow vulnerability. There is no bounds checking in gettoken(). Also, the talk about pointers being aligned to "8 bit boundaries" I think means 8 byte boundaries. Memory is not bit-addressable (at least, not in C, on anything popular). But I don't mean to detract from the project! It is very cool nonetheless :)
- raphlinus 9y agoSee also Ben Lynn's implementation[1] in about 100 lines of Haskell. Admittedly it's not a totally fair comparison because it's relying on Haskell's runtime, but it's still an excellent demonstration of Haskell's power and expressiveness compared with a lower level language. [1]: https://crypto.stanford.edu/~blynn/lambda/lisp.html https://crypto.stanford.edu/~blynn/lambda/lisp.html
- vog 9y agoTo be fair, it is not just that Haskell is a "high-level language", but that it is a language in the ML family of languages. ML means "Meta Language" and was specifically designed to be used to implement (other) languages.
- BMorearty 9y agoThat's fun. Here's Jisp, my Lisp implementation in a tiny bit of JavaScript. It supports declaring functions, interop with JavaScript, quoting a list, variable arg lists, and more: http://www.ducklet.com/jisp/ http://www.ducklet.com/jisp/.
- TimTheTinker 9y agoHave you taken a look at ClojureScript? You might find it interesting.
- lisper 9y agoLisp with full lexical closures in ~100 lines of Python: http://www.flownet.com/ron/lisp/l.py http://www.flownet.com/ron/lisp/l.py The interpreter itself is 48 lines.
- petethepig 9y agoFor everyone interested in learning about these types of things, check out Make-A-Lisp project [0]. There's more lines of code, but also more features. The guide is awesome and split into several self-contained steps. [0] https://github.com/kanaka/mal/blob/master/process/guide.md https://github.com/kanaka/mal/blob/master/process/guide.md
- woadwarrior01 9y agoReminds of this book[1] I’d read a couple of years ago. [1]: http://www.buildyourownlisp.com/ http://www.buildyourownlisp.com/
- rurban 9y agoIn the eval the dynamic intern("if") ... for all interned symbols should be moved to compile-time global storage of those interns. Otherwise it looks good. In reality one would use more tag bits, no just one. Typically 3.
- oneplane 9y agoBut what about the other way around? Would it be possible to get a C compiler written in Lisp in ~200 lines as well? I mean, not a linker and macro processor etc, just the compiler to get objects.
- kindfellow92 9y agoOof, all the macros are broken: #define is_space(x) (x == ' ' || x == '\n') #define is_parens(x) (x == '(' || x == ')') Should be #define is_space(x) ((x) == ' ' || (x) == '\n') #define is_parens(x) ((x) == '(' || (x) == ')') Probably doesn’t matter in practice for this. It could end up being a nasty source of bug later on in the project.
- geofft 9y agoThat still evaluates x twice, which can also be a source of bugs. I usually take one of two approaches: either decide that this is a weekend hack and using the macros whenever the expansion isn't obvious in my head is a sign of too much complexity, or use this GCC extension: #define is_space(x) ({ typeof(x) y = x; y == ' ' || y = '\n'; }) (Or in this case, turn it into an actual function and let the compiler figure out optimization.)
- kindfellow92 9y agoGCC extensions make my brain hurt :( Should just use C++ at that point: template<class T> bool is_space(const T & x) { return x == ‘ ‘ || x == ‘\n’; }
- pjmlp 9y agoEven better if you make it: template<class T> constexpr bool is_space(const T & x) { return x == ' ' || x == '\n'; } Debuggable, type safe and same performance as straight C code.
- IvanVergiliev 9y agoAnd throw an `inline` in there just to be more likely to end up with something macro-like.
- atilaneves 9y ago`constexpr` is implicitly `inline`: http://en.cppreference.com/w/cpp/language/inline http://en.cppreference.com/w/cpp/language/inline
- raldi 9y agoToward the end of `print_obj()`, we see: if (is_pair(cdr(ob))) { printf(" "); print_obj(cdr(ob), 0); } How could this `if` statement ever evaluate to false? We already verified that `cdr(ob) != 0`, and the CDR can never be a plain old string, so isn't this `if` superfluous?
- orodley 9y agoI don't know about this implementation in particular, but in general a cons cell is just an object with two slots in it. You can use it to represent a list (by putting another cons or nil in the cdr), but you can also use it to represent other things. For example, a pair, by putting an arbitrary object in the car and cdr. This is a pretty common technique, see "a-list" for one application.
- rurban 9y agoNope. It still can be an atom. Only if it's a pair (i.e. a cons with two cells, not just one) it prints the next.
- raldi 9y agoEven if that were possible (and with this codebase, I don't think it is), I don't see any code in this function that would print the atom in such a case. It seems like it would just print nothing.
- mweibel 9y agoAwesome article, thanks for that. As someone who almost never even looks at C code, this was very understandable with the inline comments. What's the reason for using macros instead of real functions? Is this an optimization because macros get inlined at compile time? Does this really bring a lot of value?
- klmr 9y ago> Does this really bring a lot of value? In this particular case, none whatsoever. It’s egregious abuse of macros.
- agrafix 9y agoThis motivated me to hack together a Haskell implementation, but with a little better error handling :) https://github.com/agrafix/micro-lisp https://github.com/agrafix/micro-lisp
- mar77i 9y agoThings that bugs me: cast to (long) when they should use intptr_t. EDIT: And gettoken() should check against buffer: index < sizeof token. EDIT 2: And I'd store the tag in a separate variable, because bit abuse in a pointer is plain and simply asking for problems.
- Sir_Cmpwn 9y agoOof, this is full to the brim of bad C practices. Use macros way less liberally, don't do this ridiculous pointer tagging thing, and leverage more of the stdlib.
- sigjuice 9y agoNice project that I will spend some time studying. However, fewer than 200 lines is not really a virtue, IMHO.
- martyalain 9y agoYou could also have a look at this essay, http://lambdaway.free.fr/workshop/?view=lambdacode http://lambdaway.free.fr/workshop/?view=lambdacode, following Peter Norvig's lispy, written in less than 300 lines of plain Javascript and working in any web browser. Your opinion is welcome. Alain Marty