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

Resources for Amateur Compiler Writers

c9x.me

Post reply on HN
Print view View original

41–50 of 75 posts

Re: Resources for Amateur Compiler Writers

#41

Post by _RPM »

1021203121 wrote: post #38
chrisseaton wrote: post #20

Earlier quoted context omitted.

I never understood why recursion causes anyone any problems, because recursion is the absence of a special case limitation. If I tell you that a function may call any function, then you already know everything you need to know for recursion. If we didn't have recursion, only then would I need to qualify what I just told you with the restriction that a function can only be active once. When I show students recursion I…

This is not about understanding recursion, it is about implementing recursion correctly. Recursion is likely to expose bugs in the calling convention if you're writing your first compiler.

Thank you. I wasn't sure if he understood that I was implementing it.

Re: Resources for Amateur Compiler Writers

#42

Post by ericbb »

chrisseaton wrote: post #37
ericbb wrote: post #32

Earlier quoted context omitted.

I definitely struggled to find a satisfying approach to recursion in my own current language project. What I'm doing right now is passing the closure value of the callee as a hidden first argument to every call. Nonrecursive functions just ignore that argument but recursive functions can always call themselves via that hidden argument. It doesn't allow you to support syntactic mutual recursion but it's easy to do and…

Do you not have any kind of registry of functions in your language where you can look up a function from a name and then call it? Then you don't need to pass in the current function to itself as it can look itself up in the registry, like any other function could (again, no special cases needed). There shouldn't be any need for recursive calls to be a special kind of call. They caller shouldn't need to know that it i…

That's an excellent question! :)

In my language, there is no special global scope for variables; every program is basically one giant (extended and sugared) lambda calculus expression.

I do use lambda-lifting so that in the C code I generate, there is a C function in the global C namespace that is called to execute an object-language function but object-language functions also have closure environments so any kind of self-reference needs to include both the global C function and the closure environment for that particular closure.

Note that my language does support modularity (breaking programs into multiple files, basically). However, the mechanism for referring to "packages" (stuff in other files) uses a separate name system.

I agree that languages that bind all functions in a global scope can easily use that global scope to resolve recursive references. It's also easier when your language supports variable assignment and destructive updates of data structures. But my language doesn't support those things either. :)

Addendum: By the way, you mentioned Java, Python, and Ruby, which are all object-oriented. Of course, the recursion among methods in those languages arises in a way that's very similar to passing a callee as a hidden argument. In OO languages, the hidden argument is "self" or "this"!

Re: Resources for Amateur Compiler Writers

#43

Post by zzzcpan »

Frankly, I don't see anything interesting in that list, especially for amateurs.

As an amateur compiler writer you would probably want to make something useful in a few weeks, not waste a year playing around. And it's a very different story. It's essentially about making a meta DSL, that compiles into another language and plays well with existing libraries, tooling, the whole ecosystem, but also does something special and useful for you. So, you should learn parsing, possibly recursive descend for the code and something else for expressions, a bit about working with ASTs and that's pretty much it.

Re: Resources for Amateur Compiler Writers

#44

Post by catnaroek »

Drup wrote: post #10
tikhonj wrote: post #9

Earlier quoted context omitted.

I'm not the OP, but I sympathize. The specific details covered in a "classical" compilers course are heavy weight and not super-relevant right now. These days you don't have to understand LR parsing or touch a parser-generator, you don't have to worry about register coloring... etc. Courses still use the Dragon Book which is older than I am and covers a bunch of stuff only relevant to writing compilers for C on resou…

So, the TAPL ? :) https://www.cis.upenn.edu/~bcpierce/tapl/

Not really. TAPL is a very useful book, but it won't teach you how to write a compiler, unless the only part of a compiler you actually care about is the type checker. The interpreters it describes (in the chapters titled “An ML implementation of ”) are ridiculously inefficient.

Re: Resources for Amateur Compiler Writers

#45

Post by chrisseaton »

_RPM wrote: post #41
1021203121 wrote: post #38

Earlier quoted context omitted.

This is not about understanding recursion, it is about implementing recursion correctly. Recursion is likely to expose bugs in the calling convention if you're writing your first compiler.

Thank you. I wasn't sure if he understood that I was implementing it.

I did, and I think my comment still makes sense in that context.

If I give you a list of requirements for a programming language that I want you to implement and it includes 'a function must be able to call any function' then you have recursion. You don't need additional separate requirement for 'and that function may be itself', as long as you've fully implemented the first requirement. In fact you'd need an extra requirement to prevent recursion, not to allow it.

That's what I mean by you shouldn't need to consider recursion as a special case.

Re: Resources for Amateur Compiler Writers

#46

Post by chrisseaton »

ericbb wrote: post #42
chrisseaton wrote: post #37

Earlier quoted context omitted.

Do you not have any kind of registry of functions in your language where you can look up a function from a name and then call it? Then you don't need to pass in the current function to itself as it can look itself up in the registry, like any other function could (again, no special cases needed). There shouldn't be any need for recursive calls to be a special kind of call. They caller shouldn't need to know that it i…

That's an excellent question! :) In my language, there is no special global scope for variables; every program is basically one giant (extended and sugared) lambda calculus expression. I do use lambda-lifting so that in the C code I generate, there is a C function in the global C namespace that is called to execute an object-language function but object-language functions also have closure environments so any kind of…

> Of course, the recursion among methods in those languages arises in a way that's very similar to passing a callee as a hidden argument. In OO languages, the hidden argument is "self" or "this"!

Self or this allows you to refer to the same object. You don't need to refer to the same object to wind up calling the same method. You could have two different objects that just have the same method. Maybe they share a class, or a mixin, or whatever. So I'm not sure self is relevant here.

Re: Resources for Amateur Compiler Writers

#47

Post by zaptheimpaler »

tikhonj wrote: post #9
reymus wrote: post #6

Earlier quoted context omitted.

"frankly in 2016 I am afraid the average undergrad compiler course is part of the problem as much as the solution." What do you mean by that?

I'm not the OP, but I sympathize. The specific details covered in a "classical" compilers course are heavy weight and not super-relevant right now. These days you don't have to understand LR parsing or touch a parser-generator, you don't have to worry about register coloring... etc. Courses still use the Dragon Book which is older than I am and covers a bunch of stuff only relevant to writing compilers for C on resou…

Hi, this seems like a good place for my newbie compiler question.

I'm trying to write a compiler for LISP - i wrote a simple interpreter already (mostly just to learn how compilers work). Definitely did not need anything complicated for tokenizing,parsing thanks to https://github.com/lihaoyi/fastparse.

What resources are useful now for learning about implementing a type system and the optimizer? You said register coloring etc. arent important - is this because we can target LLVM?

Re: Resources for Amateur Compiler Writers

#48

Post by creatio »

senko wrote: post #30
stijlist wrote: post #27

Earlier quoted context omitted.

There's this great series by mbrubeck which sounds like it might be right up your alley: https://limpet.net/mbrubeck/2014/08/08/toy-layout-engine-1.h...

This looks like a great resource, thanks!

This also might be interestings: http://www.html5rocks.com/en/tutorials/internals/howbrowsers...

Re: Resources for Amateur Compiler Writers

#49

Post by _RPM »

chrisseaton wrote: post #45
_RPM wrote: post #41

Earlier quoted context omitted.

Thank you. I wasn't sure if he understood that I was implementing it.

I did, and I think my comment still makes sense in that context. If I give you a list of requirements for a programming language that I want you to implement and it includes 'a function must be able to call any function' then you have recursion. You don't need additional separate requirement for 'and that function may be itself', as long as you've fully implemented the first requirement. In fact you'd need an extra r…

That's a great point. I think there is fundamental flaw in my virtual machine because recursion does not work, but calling other functions from within a function do work.

Re: Resources for Amateur Compiler Writers

#50

Post by fwefeefew »

tikhonj wrote: post #9
reymus wrote: post #6

Earlier quoted context omitted.

"frankly in 2016 I am afraid the average undergrad compiler course is part of the problem as much as the solution." What do you mean by that?

I'm not the OP, but I sympathize. The specific details covered in a "classical" compilers course are heavy weight and not super-relevant right now. These days you don't have to understand LR parsing or touch a parser-generator, you don't have to worry about register coloring... etc. Courses still use the Dragon Book which is older than I am and covers a bunch of stuff only relevant to writing compilers for C on resou…

What's replaced register coloring?
Post reply on HN