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

31–40 of 75 posts

Re: Resources for Amateur Compiler Writers

#31

Post by DigitalJack »

chrisseaton wrote: post #20
_RPM wrote: post #19

I wrote a VM, I still can't get recursion to work. It's hard.

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…

I'll share why I struggled with recursion (as best as I remember):

Most programming I learned was imperative. As I wrote the code, I imagined the execution in my head. This led to a problem where when I was halfway through a function, and it referred to itself, my brain would segfault. How could something I was not yet done writing refer to itself? I hadn't finished yet, so my brain could not comprehend what such a reference would mean.

It was also difficult because I wanted to think of functions as nice neat pieces of code that would take some data, do it's thing, and return a value. I could mentally inline a function call without much effort.

But when recursion is introduced, the floor drops out of my mental inlining. Suddenly my mental effort for such things becomes huge. For me anyway. My brain doesn't like to float around in abstraction land for long, it needs to periodically be anchored in the concrete. Otherwise I quickly lose my sense of direction and orientation... I lose my context.

Declarative languages actually make these easier, for me, because I'm not mentally executing a recipe as I write. I am giving a piece-wise description of what something is. So there is no mental tracing.

I expect the a-ha moment for recursion is different for everyone. But just showing recursion in many different forms would probably help. For example, show fib sequence generation where instead of the function calling itself, each function calls a uniquely named function... such that you concretely demonstrate building the first 5 or so numbers in the sequence...

Then show the similarity of the functions, show what the computer has to keep track of with the nested function calls, and step by step work your way to straight recursion.

Show it in BASIC with GOTO statements.

Finding as many different ways to concretely demonstrate an abstract concept will help reach more people.

Re: Resources for Amateur Compiler Writers

#32

Post by ericbb »

_RPM wrote: post #29
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…

Yes, but I generate the arguments from converting the AST into the internal byte code, so arguments are just a LOAD_NAME, etc. There seems to be a problem when the arguments are coming from the currently executing function's stack (instead of the AST) As I restore the context from current executing function execute data to the previous execute data, and pop the stack once, and push it into the old context's stack as…

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 can be implemented without data modification at any level.

Re: Resources for Amateur Compiler Writers

#34

Post by nickpsecurity »

senko wrote: post #26

IMHO, compiler construction as an advanced excercise for amateurs is at topic that has been beaten to death (as OP suggests, there's tons of available materials and projects ranging from high quality not-so-amateur to quick or fun hacks - I'm guilty of one myself). On the other hand, I would love to see "HTML5 and CSS parsing and rendering for amateurs". Given the state of modern HTML5 and CSS standards, and ignoring…

I agree. It's a topic that should die outside maybe posting that one link that aggregates many useful resources on the topic. You probably know the one.

Re HTML5/CSS

Excellent idea! These slways need more work in some way plus have widedpread impact. Amateurs stumbling on improved algorithms might similarly see their work have great impact.

Re: Resources for Amateur Compiler Writers

#36

Post by ericbb »

Ind007 wrote: post #33

Is there any similar kind of collection for static analysis?

Matt Might's site has some pages on this topic:

http://matt.might.net/articles/books-papers-materials-for-gr...

http://matt.might.net/articles/intro-static-analysis/

http://matt.might.net/articles/partial-orders/

Re: Resources for Amateur Compiler Writers

#37

Post by chrisseaton »

ericbb wrote: post #32
_RPM wrote: post #29

Earlier quoted context omitted.

Yes, but I generate the arguments from converting the AST into the internal byte code, so arguments are just a LOAD_NAME, etc. There seems to be a problem when the arguments are coming from the currently executing function's stack (instead of the AST) As I restore the context from current executing function execute data to the previous execute data, and pop the stack once, and push it into the old context's stack as…

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 is calling itself (again, lack of special casing).

This is how recursion works in languages like Java, Python, Ruby, C.

Re: Resources for Amateur Compiler Writers

#38

Post by 1021203121 »

chrisseaton wrote: post #20
_RPM wrote: post #19

I wrote a VM, I still can't get recursion to work. It's hard.

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.

Re: Resources for Amateur Compiler Writers

#39

Post by akkartik »

DigitalJack wrote: post #31
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…

I'll share why I struggled with recursion (as best as I remember): Most programming I learned was imperative. As I wrote the code, I imagined the execution in my head. This led to a problem where when I was halfway through a function, and it referred to itself, my brain would segfault. How could something I was not yet done writing refer to itself? I hadn't finished yet, so my brain could not comprehend what such a r…

As someone who enjoys teaching programming[1], your comment was my favorite of the day[2]. My learning experience was similar to yours, starting with imperative languages, so you got me to think about how I think about recursion today, given our shared baggage:

1. I do still inline recursive functions, but I've learned to selectively inline just the base case when I first implement recursion. Paradoxically, experience with lisp helped me with recursion in C, particularly Common Lisp's trace facility which taught me to visualize stacks of multiple function calls (whether recursive or not) rather than a single one at a time.

2. I've learned to think declaratively even when I program in C. When writing a C function I might start out with a crisp definition in my head ("this function saves the reverse of the list seen so far in its second argument") so that I can rely on that definition even when the implementation isn't yet complete.

[1] http://akkartik.name/post/mu

[2] https://news.ycombinator.com/favorites?id=akkartik&comments=...

Re: Resources for Amateur Compiler Writers

#40

Post by _RPM »

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…

My language has first class functions, as names are tied to values, and a value can be a function. With the opcode CALL_FUNCTION (in my VM), it does a searching of the hash table for the value.
Post reply on HN