9 ms·
Mal – Make a Lisp, in 68 languages
- deleted 9y ago[deleted]
- falcolas 9y agoThis is a fantastic way to "waste" a weekend, and there's so much learning to be had. The radically simple implementation of TCO really surprised me.
- gbacon 9y agoSee the design narrative at “Step 5: Tail call optimization”[0] in The Make-A-Lisp Process[1]. [0]: https://github.com/kanaka/mal/blob/master/process/guide.md#step-5-tail-call-optimization https://github.com/kanaka/mal/blob/master/process/guide.md#s... [1]: https://github.com/kanaka/mal/blob/master/process/guide.md https://github.com/kanaka/mal/blob/master/process/guide.md
- yosyp 9y agoCould someone explain this gem in the C version? https://github.com/kanaka/mal/blob/master/c/types.c#L170 https://github.com/kanaka/mal/blob/master/c/types.c#L170
- gbacon 9y agoIn struct MalVal[0], the values f0 through f20, where each holds a pointer-to-functions of the corresponding arity, live in a big (multifacted?) union. Using arg_cnt, the switch assigns func to the appropriate value in mv->val using the appropriate cast. For example, when arg_cnt is 2, mv->val.f2 receives func converted to void * (* )(void* , void* ), that is, pointer to a function that accepts two parameters of type pointer-to-void and returns pointer-to-void. [Weird spacing to effectively escape the asterisks that would otherwise be treated as italicizing markup.] C permits conversion between pointer-to-function of one type to pointer-to-function of another type. The inverse is also defined, and the resulting pointer will compare equal to the original. However, calling a function through a pointer-to-function where the types do not match invokes undefined behavior. [0]: https://github.com/kanaka/mal/blob/master/c/types.h#L85 https://github.com/kanaka/mal/blob/master/c/types.h#L85
- copx 9y agoThis could be made massively less ugly and more readable by typedef'ing the function pointer types by the way. Then one could just write: case 13: mv->val.f13 = (F13)func; break; As a C programmer I got to say people in general don't use typedef for function pointer types often enough. The types are so ugly and verbose, they should be typedef'ed by default.
- kanaka 9y agoI look forwards to your pull request! One challenge you'll run into is that (as I recall) the Boehm GC linkage no longer works with newer versions of Boehm.
- gizmo385 9y agoI think the primary argument that I've heard against typedefing function pointers is you can end up obfuscating what is happening and end up making the code less readable/harder to maintain in the future.
- deleted 9y ago[deleted]
- kazinator 9y agoThis code could take advantage of the fact that the type is a union. One can bend the rules of prim-and-proper well-defined ISO C just a little bit and assign to the simplest function pointer, taking advantage of all function pointers having the same representation on every machine known to mortal hacker, and all being overlaid by the union. Thus all the cases collapse down to this: mv->val.u.f0 = (void (*)(void)) func; done. Now if this is 13 arguments, then strictly speaking, accessing mv->val.uf13 is not well-defined behavior. That's only going to be problem when it actually doesn't work, though. A big problem, then. :)
- gbacon 9y agoI can respect the author taking the trouble to avoid undefined behavior. Technically correct is the best kind of correct.
- kazinator 9y agoIn TXR Lisp, I did the grunt work and wrote separate constructor functions for different function signatures: http://www.kylheku.com/cgit/txr/tree/lib.c#n5525 http://www.kylheku.com/cgit/txr/tree/lib.c#n5525 These functions are only used from within C code; they are not the basis for any intrinsic functions. The call to each of these functions knows exactly the type of function it wants to make. There is a notation in the naming. Firstly, the leading 'f' denotes functions with an environment value, whereas 'n' denotes non-environment functions. Then there is a number indicating the number of arguments. Then an optional letter which is 'o' if the function has optional arguments, or 'v' if it is variadic. Both can be present in which case we have 'ov. Thus for example func_n2ov(some_c_function, 1) will create a variadic function with 2 fixed arguments, of which 1 is required (so one optional). some_c_function has to have the type signature val (* )(val, val, varg). No casting is required because func_n2ov just assigns this to the correct union member. If we pass a function with an incorrect signature, we get a C compile error. The func_n2ov constructor is used when registering the unique function in eval.c: reg_fun(intern(lit("unique"), user_package), func_n2ov(unique, 1)); We intern the string "unique" in the user package ("usr"), and use that symbol to register a function createdy by hoisting the C function unique into the Lisp domain with func_n2ov. I wrote TXR in a way that is easy to understand and maintain. It is only implemented in C, though. If you want to study how to make a Lisp interpreter in C. Yet, it is production code for real work.
- ertucetin 9y agoWhy?
- bpicolo 9y agoEdification / amusement. I had a go in Rust recently. Was a great way to learn new things about Rust and also some interpreter concepts.
- deleted 9y ago[deleted]
- flavio81 9y agoWriting an interpreter (or compiler) greatly enhances one's programming skills.
- rjsw 9y agoWhy not work on improving an existing one ?
- phoe-krk 9y agoIn order to learn and build up a base of skills.
- chriswarbo 9y agoWhile we're at it, why don't we replace high school math tests with one question: "Solve the Riemann hypothesis". We can replace the physics curriculum with "Unify quantum mechanics with general relativity", and throw out computing courses in favour of "Prove whether or not P = NP". It's important to re-do things which others have already worked out, in order to reach a greater understanding :)
- rjsw 9y agoWhatever. I learned how to implement Lisp by reading the source code for multiple compilers. Started with Franz Lisp, then KCL and CMUCL. I don't feel that a toy interpreter is going to teach the same things.
- omginternets 9y agoWriting/understanding a lisp interpreter is a longstanding item on my TODO list. Question: how do I go from tackling this to tackling compilers?
- pjmlp 9y agoMake it generatem a simple bytecode format, that you can map into Assembler macros. Choose a good Macro Assembler like NASM or YASM, and implement the bytecodes as macros. It won't win any benchmark, but you will get native executables. Or use Lisp macros to generate the code. Here is a Scheme based tutorial. http://icem-www.folkwang-hochschule.de/~finnendahl/cm_kurse/doc/schintro/schintro_142.html http://icem-www.folkwang-hochschule.de/~finnendahl/cm_kurse/...
- kazinator 9y agoMake a very decent interpreter for a language that is good for writing compilers (without a question, a Lisp of some sorts, of course, ha). Then, write the compiler in that language. The compiler walks the code just like the interpreter, but instead of interpreting, it spits out a translation. Spitting out some kind of translation into something isn't a very high bar; the difficulties are all in optimization: things like analyzing lexical scopes for the presence of closures which escape, so as to be able to stack-allocate environments that aren't captured by closures. Plus all those other difficult things: like turning a program into a graph of basic blocks and doing flow analysis; register allocation, selection of instructions for a myriad target machines, debugging suport, and so on. Any of these requirements can be excluded from a compiler, yet it's still a compiler. The "Lisp in 500 lines of C" (plus accopmanying .lisp) file implemented a compiler. The complete source is hard to find, but here is a derivative project: https://github.com/jackpal/lisp5000 https://github.com/jackpal/lisp5000 A chunk of init500.lisp implements compilation to C. Search the file for terms like "compile" and also "deftransform". If you've ever written a macro, you've written a piece of a compiler. Macros take an input syntax tree and spit out a new one. Many actions traditionally associated with a compiler (by Lisp-unaware computer scientists) can be done by macros or in the macro expander. Basic compiling is a lot like macro expansion. It can actually be Lisp-to-Lisp even; the transformers can spit out a Lisp data structure representing a target language. (Heck GCC spits out a Lisp-like data structure for intermediate code. Of course; it was originally a project started by Stallman.)
- hdhzy 9y agoAlso check out miniMAL [0] - lisp in JSON form! [0]: https://github.com/kanaka/miniMAL https://github.com/kanaka/miniMAL
- chc4 9y agoI got decently far in my implementation, but probably wouldn't suggest you use this. The actual guide is pretty sloppily written and doesn't outline all that much, along with not explicitly saying what you have to define at each step. It doesn't define what the different cases of the mal Lisp value type should be, for example, or when to implement pretty much all of the "optional" extensions it mentions in the first or second chapter. Most of the forms in each chapter get a sentence explanation of what they do, at most, and I hit several snags where I read an explanation and thought I implemented it correctly, only to find out there was something subtly wrong with the obvious implementation. Also, writing a Lisp in a purely functional language isn't the best :X Things like by-reference function environments and atoms are hard to implement if you're not Haskell, at least if you try in the method that the guide outlines...
- sassy_samurai 9y agoThere is a similar project called "Build Your Own Lisp"[0] (BYOL), which is a book that walks one through making a Lisp in C. Has anybody here done BYOL? How does it compare to MAL? If you had to choose one to learn how to create a Lisp, which would you choose? [0]: http://www.buildyourownlisp.com/ http://www.buildyourownlisp.com/
- kanaka 9y agoBYOL is targeted at implementing Lisp in C and focuses on learning C. There is a fair bit more hand-holding and example code in C for most of the steps than in the mal guide. BYOL is more polished and written in the form of a short book whereas the mal guide intentionally tries to be more concise and informal in style. I would read through the first couple of sections of both and decide based on your own goals and preferences.
- mouldysammich 9y agoI used build your own lisp to learn C (along with other stuff) I liked it, except I dont think its the best way to learn to develop languages.
- z29LiTp5qUC30n 9y agoActually you might like stage0 http://git.savannah.nongnu.org/cgit/stage0.git/ http://git.savannah.nongnu.org/cgit/stage0.git/ It literally goes from a 280byte hex monitor all the way through a compacting garbage collected lisp and FORTH Without the assumption that any other software exists
- earenndil 9y agoI looked at BYOL a while ago, but was turned off by the fact that the author wants you to use his parser. I don't know why, but I didn't like that. I feel like there's value in using a pre-existing, widely-used parser like yacc/lex, for no other reason than that it already exist and is widely used.
- sassy_samurai 9y agoOh man, that's a bummer. I think one of the great joys in constructing your own compiler or interpreter is making your own lexer and parser. Doesn't using a pre-made lexer/parser kind of defeat the purpose of making your own compiler/interpreter?
- faaq 9y agoWhat is the smallest Mal implementation? OCalm?
- kanaka 9y agoImplementation size is hard to compare accurately across languages (bytes? lines of code? exclude comments? excluding leading spaces?). Also, the mal implementations were created by many different people so individual style plays a large role in concision/verbosity. However, that being said, the following implementations are "smallish" (in both lines of code and bytes): mal itself (self-hosted), Clojure, factor, Perl 6, Ruby. The following are "largish": Awk, PL-pgSQL, C, PL-SQL, Chuck, Swift 2, Ada. OCaml is in the "smallest" third of the implementations.
- Sjenk 9y agoI am curious why is hackernews always so happy and obsessed with lisp, there is almost daily a lisp post on the frontpage. I dont really care/mind but I am just curious as why people love lisp so much. The only thing that I notice about Lisp are the bracket jokes and memes.
- kovrik 9y agoBecause lisps are unique and cool. Really, they are quite special.
- tombert 9y agoLisp is one of those languages that, once I learned it (Clojure in my case), I started wondering why every language wasn't more like it. Once you get used to the parentheses and whatnot, it's actually an incredibly beautiful language that gives you the ability to augment the language without waiting for updates via its elegant macro system.
- jdmoreira 9y agoLisps have properties that are not so common in other languages: - Homoiconicity: Code and data are the same (s-expressions) - Lisp code is basically the AST in itself - It's trivial to implement lisp in lisp (eval) - Continuations (call/cc) - Macros - etc... It's a truly fascinating language. I never really did any Lisp coding outside some university projects and I still obsess and read about Scheme all the time.
- deleted 9y ago[deleted]
- metaobject 9y agoPaul Graham and Robert Morris built one of the first web applications (that's a PG claim, btw) that allowed users to build their own, separate websites that had shopping carts, custom UI, etc. They wrote the app in Common Lisp and claimed that it was their secret weapon which allowed them to iterate faster and stay ahead of their competition. They ended up selling their company (ViaWeb) to Yahoo for $50 million (IIRC). PG also authored two books on Lisp, and HN is written in Arc (a Lisp built on top of Racket). Around 2005 I was doing a lot of Lisp programming and I was really interested in what PG had to say. He was writing a lot of essays then and giving lots of talks, etc. Unfortunately, I don't get the opportunity to use Lisp as much as I used to, but I'm doing a lot of Python and even played around with Hy (Lisp on top of Python). So I'm interested in Lisp as I find it to be an incredibly powerful language that is really fun to use.
- arunc 9y agoI tried finding the lines of code in each language with cloc. C/C++ Header contains a sum of C and CPP header files. Python has been used across different language dirs as wrapper script or so, otherwise, it's own implementation is probably 1350 lines at max. This would also probably include bugs in cloc. github.com/AlDanial/cloc v 1.70 T=2.86 s (433.6 files/s, 67570.0 lines/s) -------------------------------------------------------------------------------- Language files blank comment code -------------------------------------------------------------------------------- Visual Basic 36 1569 132 8036 Swift 36 1199 1606 7951 SQL 36 956 649 7594 Pascal 19 704 951 6253 Ada 28 1975 380 5856 Elm 19 1619 226 5647 awk 16 290 15 5169 Lisp 37 825 256 4562 VHDL 17 434 32 4228 C# 20 658 346 4175 Python 37 574 394 4018 make 89 1244 873 4010 C 19 466 392 3499 Perl 35 413 171 3450 Go 17 281 148 3397 Rust 18 304 130 3331 JavaScript 43 449 247 3235 Forth 18 516 158 3228 C++ 18 568 71 2986 Java 17 325 135 2938 D 17 363 10 2938 Racket 35 480 385 2740 TypeScript 17 284 56 2740 Markdown 8 714 0 2730 Rexx 17 283 47 2713 Bourne Shell 30 390 315 2692 Tcl/Tk 17 284 43 2416 Dart 16 255 41 2303 F# 20 337 13 2298 Objective C 17 285 150 2189 Erlang 17 277 191 2185 MATLAB 26 184 128 2165 Haxe 19 254 79 2161 Crystal 18 417 58 2146 vim script 17 242 50 2076 Haskell 17 331 99 2000 PHP 18 249 120 1955 Lua 18 248 87 1874 Scala 16 221 113 1816 Elixir 19 366 35 1809 JSON 28 246 0 1765 R 17 201 100 1612 Groovy 17 170 98 1582 Kotlin 17 312 0 1554 Julia 17 189 126 1405 Nim 16 320 36 1397 lex 18 209 0 1355 Ruby 17 167 87 1264 OCaml 15 109 98 1211 PowerShell 11 128 71 1146 ClojureC 15 257 129 1053 CoffeeScript 17 195 126 1037 CSS 6 150 132 792 C/C++ Header 22 266 44 752 HTML 2 36 35 486 Bourne Again Shell 47 1 4 135 YAML 2 6 10 86 Maven 1 2 7 85 Clojure 2 8 12 65 ClojureScript 1 1 0 2 -------------------------------------------------------------------------------- SUM: 1242 24806 10447 158293 --------------------------------------------------------------------------------
- tekknolagi 9y agoNot to toot my own horn too much, but I have also written a tutorial[0] aimed at building a Lisp in OCaml. I wrote it to teach as much as learn how to go about it. [0](https://bernsteinbear.com/blog/lisp/ https://bernsteinbear.com/blog/lisp/)
- suzuki 9y agoThere is another Lisp implemented in 42 languages (including Ceylon, Dylan, Oz, Pike, Scratch, Smalltalk, SML etc.): https://github.com/zick/ZickStandardLisp https://github.com/zick/ZickStandardLisp The benchmark results of 42 implementations are very impressive: http://blog.bugyo.tk/lyrical/wp-content/uploads/2014/12/stage1.png http://blog.bugyo.tk/lyrical/wp-content/uploads/2014/12/stag... http://blog.bugyo.tk/lyrical/wp-content/uploads/2014/12/stage2.png http://blog.bugyo.tk/lyrical/wp-content/uploads/2014/12/stag... http://blog.bugyo.tk/lyrical/wp-content/uploads/2014/12/stage3.png http://blog.bugyo.tk/lyrical/wp-content/uploads/2014/12/stag... which are discussed in Japanese at: http://blog.bugyo.tk/lyrical/archives/2024 http://blog.bugyo.tk/lyrical/archives/2024