Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing Your Own Programming Language

github.com

Post reply on HN
Print view View original

61–70 of 95 posts

Re: Writing Your Own Programming Language

#61

Post by johnbender »

drusepth wrote: post #3

Honest 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 impl…

I've built interpreters for both a subset of Java and a full Lisp. Here's my take.

> Is there something inherently easier to implementing a functional language instead of something more imperative?

Other answers have focused on the parsing of the language (that is, the production of an AST) which is much easier to cover instructionally for a Lisp because it's basically the AST already.

To my mind the semantics' of imperative languages is the real issue. In particular when defining and/or implementing the semantics for an imperative language, eventually store (memory) management comes up and everything gets much more complicated instantly.

[edit] And to go along with the store there are often more forms for which you need to define the semantics (statements, expressions, classes, etc).

In contrast functional languages can frequently be implemented using term rewriting which can deal directly with the AST itself.

More broadly, this is why I wish students were required to implement an interpreter of an imperative language. The act of debugging programs becomes more difficult for the same reason the semantics is more difficult to define and implement: it's more complex and there are more nuts and bolts to consider.

Re: Writing Your Own Programming Language

#62

Post by JoelMcCracken »

bediger4000 wrote: post #19

Peter Norvig's "(How to Write a (Lisp) Interpreter (in Python))" ( 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.

You don't need to knock the project to praise Norvig. Thank you for the link though.

Re: Writing Your Own Programming Language

#63

Post by Homunculiheaded »

k__ wrote: post #55
bediger4000 wrote: post #19

Peter Norvig's "(How to Write a (Lisp) Interpreter (in Python))" ( 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.

When I think about writing my own language, I think of something with as few parenthesis as possible and all the examples use Lisp.

At 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.

Re: Writing Your Own Programming Language

#64

Post by cardiffspaceman »

k__ wrote: post #55
bediger4000 wrote: post #19

Peter Norvig's "(How to Write a (Lisp) Interpreter (in Python))" ( 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.

When I think about writing my own language, I think of something with as few parenthesis as possible and all the examples use Lisp.

The 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 (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.

Re: Writing Your Own Programming Language

#66

Post by kazinator »

cardiffspaceman wrote: post #64
k__ wrote: post #55

Earlier quoted context omitted.

When I think about writing my own language, I think of something with as few parenthesis as possible and all the examples use Lisp.

The 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 func…

And 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.

Re: Writing Your Own Programming Language

#67

Post by acchow »

protomikron wrote: post #44
acchow wrote: post #41

Earlier quoted context omitted.

But most compilers have a parser. Scheme doesn't need one ;) http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...

Why is it so often stated, that Scheme doesn't need a parser? I mean the AST is simpler then in other languages, but at the end of the day, you have to parse SEXPs, don't you? I mean let's say you evaluate > (+ 2 3) You have to parse the string "(+ 2 3)" and will then evaluate it to 5?

we mean it doesn't need a parser in the traditional sense of a LR or LL grammar (or more complicated) with generated table or even a hand-rolled parser with lookahead.

Sure, it needs a "parser" in the sense of a FSA + a stack.

Re: Writing Your Own Programming Language

#68

Post by emp »

johnbender wrote: post #61
drusepth wrote: post #3

Honest 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 impl…

I've built interpreters for both a subset of Java and a full Lisp. Here's my take. > Is there something inherently easier to implementing a functional language instead of something more imperative? Other answers have focused on the parsing of the language (that is, the production of an AST) which is much easier to cover instructionally for a Lisp because it's basically the AST already. To my mind the semantics' of im…

I agree, but would add I wish student had to build compilers/interpreters for 3 languages: Forth, Lisp and something like C. As a student we went right into C: BNFs, lex, yacc, emitting machine code, optimizations, etc. Very interesting but the beauty of simplicity is lost in it all. Forth at first is baffling - there is no syntax! It's amazing how little you need to get going. Lisp, to just get right to the parse tree. And you already have intuition on the interpreter part. And finally C or Java for all the upfront complexity required.

Re: Writing Your Own Programming Language

#69

Post by ced »

johnbender wrote: post #61
drusepth wrote: post #3

Honest 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 impl…

I've built interpreters for both a subset of Java and a full Lisp. Here's my take. > Is there something inherently easier to implementing a functional language instead of something more imperative? Other answers have focused on the parsing of the language (that is, the production of an AST) which is much easier to cover instructionally for a Lisp because it's basically the AST already. To my mind the semantics' of im…

In particular when defining and/or implementing the semantics for an imperative language, eventually store (memory) management comes up and everything gets much more complicated instantly.

Why? Isn't C-like "call malloc" simpler than the GC which is required for most (all?) functional languages?

Re: Writing Your Own Programming Language

#70

Post by astrange »

simono wrote: post #2

Why 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.

I 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?

Post reply on HN