10 ms·
Writing Your Own Programming Language
- simono 10y agoWhy do bloggers focus on lexing and parsing? These things should not take up 80% of the article about creating a programming language. This fascination with "how" to build something, without considering "what" and "why", seems to be an issue that gets repeated time after time again.
- lmm 10y agoI found http://hokstad.com/compiler http://hokstad.com/compiler a lot easier to understand than any other compiler tutorial I've seen. Writing a compiler the way you'd write any other program. It does end up with e.g. a distinct parser, but only when the reasons that might be a good idea become apparent.
- vidarh 10y agoThanks :) Though in retrospect I think it should have been two separate series (and I need to write a few more parts; I'm very close to having it compile itself as of last night). I think it'd have been better to evolve the initial simple language into an equivalently simple language to parse, and kept the long slog towards compiling Ruby as a separate thing. Especially as that has complicated things enough to be in severe need of various refactoring (which I'm avoiding until it will compile itself, at which point I'll start cleaning it up while insisting on keeping it able to compile itself..). The parser itself started out conceptually quite clean, for example, but the Ruby grammar is horribly complex, and I keep having to add exeptions that's turned it quite convoluted. I don't doubt it can be simplified with some effort once I have the full picture, but it's not great for teaching.
- jarmitage 10y agoHow about making your comment useful by enlightening the community as to the relative unimportance of these aspects of contemporary PL design, and suggest some other aspects for would-be designers to focus on instead? Just imagine: you could even link to resources for the latter!
- jedimastert 10y agoWhat is the problem there? I'm confused by your comment
- kd0amg 10y agoOne problem is that syntax is just one (rather shallow) part of the design of a programming language, but it's one that gets a lot of attention because everyone who's used two programming languages can tell that it's a point where languages differ. Semantics (rules about what blobs of syntax mean) is a much more interesting way for languages to differ, but most "build a language" tutorials I (and probably GP) have seen don't seem aware that there are even decisions to be made there. The "your own" bit in the title is also a bit upsetting for a post that hands the reader a language and its implementation instead of talking about something of the reader's own design.
- mamcx 10y agoThis is a fair complain. I have read dozens of articles on the matter and honestly, parsing and lexing is the less significant aspect of this: https://news.ycombinator.com/item?id=10793054 https://news.ycombinator.com/item?id=10793054 https://www.reddit.com/r/coding/comments/2ocw2r/how_to_create_a_programming_language/cmy71xn/ https://www.reddit.com/r/coding/comments/2ocw2r/how_to_creat... Exactly. I'm in the pursuit of build one. My first questions? How make a REPL, a debugger, how implement pattern matching, type checking, if a interpreter can be fast enough, if possible to avoid to do a whole VM for it, etc... Exist a LOT of practical questions that are left as "a exercise for the reader" that need clarifications. In the end, the parsing steps can be summarized as: - Do lisp/forth if wanna do the most minimal parsing and do a lisp Or: - Use a parse generator, if not care about the quality of this Or: - Use a top-down parsing by hand, if wanna some control ANY OTHER OPTION is non-optimal, and will divert from the task, EXCEPT if you wanna do something novel. If will let aside the parsing stuff, we can put more in the hard and more rewarding aspects.
- vidarh 10y agoI agree, which is why I started my own series, as lmm mentioned, with showing simple ways of (ab)using gcc to figure out how to do simple/primitive code-generation, and built up from that, instead of building down from lexing/parsing. Lexing/parsing is important of course, but it's been done to death, and for most of the simple types of languages people tend to use for teaching, it's a simple problem. Code generation, on the other hand, is still pretty poorly covered, in my opinion, and something people tend to struggle with a lot more, even if you resort to tools like LLVM (and that's fine if that's what you want, but I'd argue you should try a lower level approach at least once to understand some of the challenges)
- bloaf 10y agoIf I were going to write a programming language for myself, I would lay out the following challenge to myself: > You are only allowed to store the AST and variable names found by parser. The input to the lexer is not allowed to be persistent. To do this, your lexer would need to be in some sense invertible, capable of both producing a source-code-representation of an AST given some naming metadata, as well as converting that source-code-representation back to names+AST. I think that would make the lexing + parsing task worthy of an 80% article.
- astrange 10y agoI think it's just because they run out of steam after doing the "first part", and there are backends like LLVM available. The Red Dragon book has the same issue, except they spend 800 pages on basic parsing and only end up making it sound terrifying and mathy. Definitely recommend against reading it. Maybe a different place to start would be making your own bytecode?
- drusepth 10y agoHonest question: why do tutorials in this topic seem to always use functional languages/syntax as examples? Our compilers class at MST had us re-implement a lisp compiler, but didn't touch on why we used lisp specifically (other than the professor liking it; we were a largely C++ school). Do they think functional languages are simpler / less complex / easier to understand? Is there something inherently easier to implementing a functional language instead of something more imperative?
- tel 10y agoModeling a pipeline of transformations of a well-understood data type it sort of whatever comes right after "hello world" in functional programming. A compiler is a very scaled up version of this, but it certainly fits naturally with the standard ideas of FP.
- marcosdumay 10y agoThe simplest languages around are all functional. And most of them are Lisp idioms. Besides, when writing a compiler, it's always great if you can ignore the possibility of some value changing. It makes implementation much simpler even more if you go into optimizations. And while you can't completely ignore value mutation on Lisp, it is always explicit, what makes an implementer's life easier.
- lmm 10y agoNot having to deal with a statement/expression distinction makes it a lot easier. Functional languages often have a simpler syntax with fewer special cases. (Though there are other languages like this e.g. Smalltalk)
- vidarh 10y agoI agree in general. Though Wirth-ian languages, like Pascal, Modula-II and Oberon are good examples of languages that are very simple to parse despite not being functional. Though they are slightly more complx than some functional languages, you can prototype a hand-written parser for them in a day if you've got a bit of experience.. E.g. the Oberon-07 grammar takes up 1.5 pages of BNF [1]of which the first third of a page or so represent the lexer symbols (you don't need a separate lexer module for most of these languages). [1] Page 166 and 17 of the language report (which incidentally only spends 17 pages to describe the entire language...) https://www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Report.pdf https://www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Repor...
- TurboHaskal 10y agohttps://raw.githubusercontent.com/marciok/Mu/master/WriteYourLanguage.playground/Pages/Interpreter.xcplaygroundpage/Resources/simple-ast.png https://raw.githubusercontent.com/marciok/Mu/master/WriteYou... (Beavis and Butthead laugh)
- deleted 10y ago[deleted]
- bediger4000 10y agoPeter 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.
- deleted 10y ago[deleted]
- psewell 10y agoNo. First, understand what the language is for (if nothing, stop here...). Second, make the main design choices (expressiveness of type system, level of control of mutability or lack thereof, etc.). Third, design the type system, with a view to type inference. Fourth, design and define the semantics. Do those last two in a way that will let you test your implementation against these definitions automatically. Fifth, think about sufficiently efficient implementation strategies. Sixth, pick a syntactic style that will be familiar to most of your users. Seventh, design the actual syntax. Eighth, implement it. Ninth, try it out on users and go back to the start. Tenth, rest.
- uiri 10y agoThere are a TON of resources like this which focus on lexing and parsing which is all fine and dandy but interpreting the resulting Abstract Syntax Tree will be extremely slow. Are there any resources on the code generation side of things? Even getting from a high level language down to SSA seems like a big leap (nevermind going from SSA to assembly).
- munificent 10y ago> Are there any resources on the code generation side of things? Cooper and Torczon's "Engineering a Compiler" is mostly focused on the back end. I liked it a lot.
- xutopia 10y agoI have a friend who wrote this book: http://createyourproglang.com/ http://createyourproglang.com/ Jeremy Ashkenas created CoffeeScript after reading that book. I can't recommend it enough for someone going down this road.
- k__ 10y agoAh, I searched this link for a while, thanks.
- hota_mazi 10y agoI'm confused, the article says the language uses a postfix operator and then shows examples like `(s 2 3)`. Isn't that a prefix operator?
- morbidhawk 10y agoI took a university course where we built an interpreter for MicroScheme. It was a difficult project but was also really awesome and rewarding. I'd like to go back and do it again without deadlines to really understand it better. I think functional programming languages can be a great choice for implementing an interpreter since metaprogramming is their forte and Racket's match function helped a lot, it's like the most powerful thing I've ever seen[1] [1] https://docs.racket-lang.org/reference/match.html https://docs.racket-lang.org/reference/match.html