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

61–70 of 75 posts

Re: Resources for Amateur Compiler Writers

#61

Post by infraruby »

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…

For a program without recursive calls the students can get away with believing that local variables are statically allocated, but for a program with recursive calls the students must understand that local variables are allocated on the stack; that what appears (lexically) to be one variable in the source may be many variables at runtime!

Re: Resources for Amateur Compiler Writers

#62

Post by danbolt »

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'd love to do some project like this to give me a better understanding of webpage performance.

The high-level abstractions of HTML/CSS are really powerful, but it would be cool to have an understanding of the implications of such designs when writing web applications.

Re: Resources for Amateur Compiler Writers

#63

Post by qznc »

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…

> Show it in BASIC with GOTO statements.

That should happen naturally, if you implement a compiler to native code. A "call" instruction is just a "goto/branch/jump" with some extra stack fiddling.

Also, I don't think pure functions are so easy mentally either. Try to understand "call with current continuation". ;)

Re: Resources for Amateur Compiler Writers

#64

Post by jfoutz »

Dybvig's dissertation is great. [1] People might disagree that it's a compiler, it targets a fairly high level vm rather than a native machine. But it's got everything you need. Really, you can fire up dr racket, type it in and have a great framework in an afternoon.

Anyway, it's very readable.

[1] http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf

Re: Resources for Amateur Compiler Writers

#65

Post by drfuchs »

chrisseaton wrote: post #24
drfuchs wrote: post #22

Earlier quoted context omitted.

Doesn't a modern JIT collapse JVM locals into a smaller actual stack frame already? Compilers have been doing this for local variables with non-overlapping liveness for decades.

The JVM can't do this because of debugging. If you attach a JVM debugger and examine a local variable which has had the storage reused what would you see? Junk from some other local variable. It's one cost of always on debugging. Normally the cost isn't too bad and of course they're spilled to the stack not kept in registers, but if the language you are implementing has thousands of locals you may even reach the limi…

In the JVM, the start_pc/length of each LocalVariableTable entry lets you have more than one name for a given index in the stack frame, exactly so as to be able to reuse indexes for variables that don't overlap in liveness. So the debugging and non-JIT objections don't pertain.

But if you're really running into the 64k limit on max_locals even with index reuse, then you're out of luck.

Re: Resources for Amateur Compiler Writers

#66

Post by ww520 »

_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…

Recursion call should be exactly the same as an ordinate function call. The following is an example of asm code gen for function definition and recursive function call. Code gen to VM code should be similar. Hope it help.

Assume the following AST.

  FN_DEF: { NAME: foo, PARAMS: [int4 param1, int4 param2] }
    LOCAL_VARS: [int4 var1, int4 var2, int4 var3]
    ...
    ASSIGN: { var1, CONST: 0x1 }
    ASSIGN: { var2, ADD:{ 0x2, param1 } }
    ...
    var3 = FN_CALL: { foo, ARGS: [var1, var2] }
    ...
    RETURN: { var3 }
The generated code would be (all numbers are 10-based instead of hex for simplicity):

  fn_foo:
    push ebp          ; save the caller's old frame pointer
    mov ebp, esp      ; the new frame pointer to current stack ptr
    sub esp, 20       ; make new space in stack for params and locals
                      ; EBP points to the base of the current frame
                      ; the frame has 20 bytes in the stack
                      ; var1 at [ebp-4]
                      ; var2 at [ebp-8]
                      ; var3 at [ebp-12]
                      ; param1 at [ebp-16]
                      ; param2 at [ebp-20]
    ...
    mov [ebp-4], 1    ; assign 0x1 to var1
    mov [ebp-8], 2    ; assign 0x2 to var2
    add [ebp-8], [ebp-16] ; add param1 to var2
    ...
    push [ebp-4]      ; push var1 for the function call
    push [ebp-8]      ; push var2 for the function call
    call fn_foo       ; call function foo at address fn_foo
                      ; the current EIP is saved in stack
                      ; the return value will be in EAX
    mov [ebp-12], eax ; save function return value to var3
    ...

    mov eax, [ebp-12] ; set function return value from var3
    mov esp, ebp      ; pop frame
    pop ebp           ; restore old EBP to previous frame
    ret               ; return to the caller by popping the
                      ; caller's address from stack into EIP.
                      ; Execution will continue at the restored EIP address.

Re: Resources for Amateur Compiler Writers

#67

Post by qwertyuiop924 »

_RPM wrote: post #19

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

If you don't evaluate the function's body when it's declared, and your language is lexical, than your function should always be evaluated in a context where its own name is bound. If your language has dynamic scope, than the above still basically works until somebody defines a local var to the name of your function.

The only situation where recursion wouldn't work is where all of your vars are static.

As for compiling Lexical scoping, I can't help you there, although I've heard it's not too hard, if you don't care about optimization. Dynamic scoping is dead simple to compile, though.

As for tail call optimization, if your target is an assembler with a goto instruction that in any way resembles a real instruction set, the only slightly tricky bit is figuring out what function is in the tail position. Once you've done that, it shouldn't be too hard. Lambda, The Ultimate Declaritive has details, IIRC.

Re: Resources for Amateur Compiler Writers

#68

Post by qwertyuiop924 »

If you're interested in getting started with interpreters, which are easier, you might want to look into Daniel Holden's excellent Build Your Own Lisp (And Learn C). Although it has been criticized for many reasons, it's a great book, and if you find interpreters and compilers totally magic, it's a good place to start.

Also, after reading What every compiler writer should know about programmers, I finally understand why people hate C. Because this just shows definitively that C compiler writers have been in their own little world for the past few decades.

Man, now I want a C compiler that wasn't written by a bunch of mindless jerks that will be the first up against the wall when the revolution comes...

Re: Resources for Amateur Compiler Writers

#69

Post by nickpsecurity »

catnaroek wrote: post #44
Drup wrote: post #10

Earlier quoted context omitted.

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.

You have a link to a good guide for beginners on designing and efficiently implementing type checkers?

Re: Resources for Amateur Compiler Writers

#70

Post by chrisseaton »

drfuchs wrote: post #65
chrisseaton wrote: post #24

Earlier quoted context omitted.

The JVM can't do this because of debugging. If you attach a JVM debugger and examine a local variable which has had the storage reused what would you see? Junk from some other local variable. It's one cost of always on debugging. Normally the cost isn't too bad and of course they're spilled to the stack not kept in registers, but if the language you are implementing has thousands of locals you may even reach the limi…

In the JVM, the start_pc/length of each LocalVariableTable entry lets you have more than one name for a given index in the stack frame, exactly so as to be able to reuse indexes for variables that don't overlap in liveness. So the debugging and non-JIT objections don't pertain. But if you're really running into the 64k limit on max_locals even with index reuse, then you're out of luck.

But that's my point - the person emitting the bytecode needs to be the one doing the work to re-use local variable indices. And the algorithm for doing that is register allocation. So even if you target the JVM you may still need to know how to do register allocation, and it isn't some historical piece of trivia.

For every local variable index, the JVM needs to keep the value live for the duration of the method because that's what the debugger will show.

And yes we have seen the 64k limit blown by real programs in the wild that aren't designed to be awkward (I'm in the VM research group at Oracle).

Post reply on HN