5 ms·
Peter Norvig's "(How to Write a (Lisp) Interpreter (in Python))" (http://norvig.com/lispy.html http://norvig.com/lispy.html) covers a superset of this material
by bediger4000 10y ago
Peter Norvig's "(How to Write a (Lisp) Interpreter (in Python))" (http://norvig.com/lispy.html http://norvig.com/lispy.html) covers a superset of this material and makes more sense, and actually has a portable implementation you can run yourself. If you're going to do this, use Norvig as a guide.
- k__ 10y agoWhen I think about writing my own language, I think of something with as few parenthesis as possible and all the examples use Lisp.
- cle 10y agoHave you considered that the two might be correlated?
- k__ 10y agoCould you elaborate?
- gmantastic 10y agoSimple lisps have very little, very regular syntax making them popular choices for "write your first interpreter" tutorials.
- Homunculiheaded 10y agoAt a high level, compilers just translate one programming language to another. A key part of this translation is the Abstract Syntax Tree (AST), which represents the programming language transformed into a tree of computation independent of the syntax of the language. Once you have the AST, you can then step through it and translate the tree to anther language like java bytecode, ASM, CIL, etc. When compiling the AST sits in the middle of the whole process. The first part deals with parsing your language into the AST the second part deals with transforming the AST to the target language (including possible optimizations of the tree). Lisp is effectively the raw AST, which is where its power comes from. The use of parentheses is the cleanest way to directly represent a raw tree that you can interact with. This means that you can use Lisp to cut the language design process in half from either direction: On the one hand, if you are worried about parsing your language, then you can simply transform it into lisp, which is virtually identical to creating the AST, and then you can use a lisp interpreter/compiler for the second half. On the other hand, if you're interested in writing the interpreter/compiler for a language and don't want to stress about parsing, you can write it for lisp and not have to worry about parsing a complex language. If you follow the Norvig code you can extend that example to a language devoid of parenthesis by writing the parser for it. Even if you want to do both it's not a terrible idea to prototype both halves using Lisp and then perform the minimal work pull out the Lisp code and replace it with some other implementation of the AST.
- spynxic 10y agoSurely a left-field type of question but here goes. Given the current state of machine learning, could an AST be generated to accommodate a given language? And more importantly, can the form of an AST cause a difference in performance of the overall program?
- skissane 10y ago> Given the current state of machine learning, could an AST be generated to accommodate a given language? No machine learning required. It is certainly possible to automatically generate an AST based on a grammar. The more interesting question is whether you can automatically generate a grammar based on samples of the language - https://en.wikipedia.org/wiki/Grammar_induction https://en.wikipedia.org/wiki/Grammar_induction - although it is unclear why you'd bother trying for a programming language (as opposed to natural language). > And more importantly, can the form of an AST cause a difference in performance of the overall program? If you are compiling to machine code, or to bytecode for some VM, or transpiling to another source language (e.g. JavaScript): not really. The form of an AST could make a difference to compilation speed or the ease of implementing later stages of the compiler, but I can't see how it would directly make any difference to the performance of the compiled program. However, if you are doing tree-based interpretation: Yes, differences in choice of AST can make a significant difference to runtime performance.
- cardiffspaceman 10y agoThe reason for LISP or SCHEME as the tutorial is that parsing is easy and doesn't call for Flex/Bison. There is a level of semantics also that if you don't strain yourself on edge cases you can do a decent interpreter or compiler pretty quickly. Without making this post long I could "tempt" or encourage you by suggesting that if you take the outermost paren pair off an s-expression, you sortof have a language of function application: defun fact n = if (< n 2) 1 (* n (fact (- n 1))) I think there is an SRFI for Scheme that proposes something like that plus offside rule to get rid of parens. You could get rid of more parens by adding operator precedence to the syntax (and that offside rule would help too), but now you're making the parsing interesting instead of making the execution interesting.
- kazinator 10y agoAnd the reason you don't want to drag in Flex and Yacc/Bison is that then the bulk of the course will revolve around the banal issues surrounding syntax, rather than semantics: high in heat, low in light. Not even the smarter side of syntax (abstract syntax), but rather character-and-token level syntactic sugaring.
- aidenn0 10y agoA recursive decent parser for a prefix language is not significantly complicated by using C style function calls.
- kazinator 10y agoLisp representations can be used internally even if you have such a syntax. Recent GCC commit: https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=28251d450e034f06fc52244c26ef65f64185dc59 https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=28251d450e034f... GCC has some Lisp-like data structures inside, and those give a language to the commit comment also, making it easy to comprehend what is going on with the abstract syntax.
- wtbob 10y ago> When I think about writing my own language, I think of something with as few parenthesis as possible Just swap [] with (), then they're a lot easier to hit. It's weird that parentheses are shifted but square brackets are not: the former are a lot more common in English text than the latter, as well as in many programming languages.
- nickpsecurity 10y agoYou can make the LISP do something other than parenthesis. An early example was Dylan language. You can also use LISP to power the compiler as both intermediate and executable language like Julia did. Outwardly, it's a powerful, pleasant language many people would like. On inside, its power came from that fact that the syntax was immediately translated to & manipulated in femtolisp. My favorite use of LISP to bootstrap a language is this presentation [that could also be done without parentheses]: https://news.ycombinator.com/item?id=9699065 https://news.ycombinator.com/item?id=9699065
- kazinator 10y agoRe: early example, CGOL was two decades before Dylan. https://en.wikipedia.org/wiki/CGOL https://en.wikipedia.org/wiki/CGOL
- nickpsecurity 10y agoIt's a little weird in syntax but definitely an improvement in the side-by-side examples. Thanks for telling me about it.
- JoelMcCracken 10y agoYou don't need to knock the project to praise Norvig. Thank you for the link though.
- gillygize 10y agoThanks for the link! One nice thing about the original post is that it runs inside of a Swift playground, which, for those with Xcode (or an iPad) can be a fast way of learning and experimenting. I could see someone starting with this project and then easily expanding their knowledge by modifying it using resources like the one you linked to.