Yhc/Notes

AUTHOR: Neil Mitchell & Tom Shackell
DATE: 1 Nov 2005

An instant message conversation, contains details about yhc bytecode
--

Neil: can i ask a few questions on yhc bytecode?
Tom: sure.
Neil:     PUSH_ARG 0          1 <["218"] | {"218"}>
what is the 218 for?
also, bcodecompile, mem, flatten, rel - what is the order of these stages?
Tom: in order to do stack and argument zapping it's necessary to know what variables are live at any time.
Neil: so they are annotations?
Tom: IIRC the [218] says variable with id 218 is needed at this point and {218} says that 218 is the only live variable at this point.
Neil: cool
(will make sure i convert all the stuff in this irc into documentation...)
and the bit before the < | > is the stack depth?
Tom: the order is first it compiles the expressions into code, then it does memory analysis, then it flattens the call graph into jumps and then it turns the jumps into relative jumps.
Neil: cool
Tom: yes that's the stack depth.
Neil: eval is evaluate to whnf i guess
Tom: yup.
Neil: mk_ap?
what are the numbers, and does it use the stack?
Tom: builds an application node in the heap, using the arguments on the stack.
Neil: application to what?
Tom: you'd need to show me an example for me to tell you what the numbers were :-)
Neil: FUN Main;fac{189}(2/0) ["v218","v219"]
 STACK 3
   {
    PUSH_ARG 0          1 <["218"] | {"218"}>
    EVAL                1 <[] | {}>
    INT_CASE {1 -> L_2, _ -> L_4}               1 <[] | {}>
L_2                     1 <[] | {}>
    POP 1               0 <[] | {}>
    PUSH_ARG 1          1 <["219"] | {"219"}>
    EVAL                1 <[] | {}>
    JUMP L_3            1 <[] | {}>
L_4                     1 <[] | {}>
    POP 1               0 <[] | {}>
    JUMP L_0            0 <[] | {}>
L_3                     1 <[] | {}>
    JUMP L_1            0 <[] | {}>
L_0                     0 <[] | {}>
    PUSH_ARG 1          1 <["219"] | {"219"}>
    PUSH_ARG 0          2 <["218"] | {"218"}>
    MK_AP 0 2           1 <[] | {}>
    PUSH_INT 1          2 <[] | {}>
    PUSH_ARG 0          3 <["218"] | {"218"}>
    MK_AP 1 2           2 <[] | {}>
    MK_AP 2 2           1 <[] | {}>
    EVAL                1 <[] | {}>
L_1                     1 <[] | {}>
    RETURN              1 <[] | {}>
   }

the first mk_app 0 2
Tom: mk_app using the function described in constant table item 0, with 2 arguments.
Neil: oh! constraint table
Tom: constant table :-)
Neil: yeah, thats obvious now - forgot abou tit
and push_int is just a specialised version of push with the constant 1?
http://thread.gmane.org/gmane.comp.lang.haskell.glasgow.user/8827
Tom: indeed.
Neil: was reading that thread, and wanted to see what yhc gives for it
see if we can beat ghc for factorial :)
Tom: something completely different, because yhc is based on a stack machine :-)
Neil: i released hoogle and hugs in beta today
Tom: very unlikely :-)
Neil: so i need a new project
using yhc to beat ghc for speed in at least one ridiculous microbenchmark might be it!
Tom: ehehe I wouldn't bother :-)
Neil: we'll see
i feel i should know more about yhc's details
Sent at 4:32 pm on Tuesday
Tom: feel free to read the source code or ask questions :-)
Neil: i was going to write up a document on the bytecode
as a way to learn
and for documentation
Tom: sounds good :-)
Neil: possibly an executable spec....
Tom: you won't like the source code for the backend of the compiler though :-)
Neil: i know, too many monads!
zap is purely for gc issues, right?
Tom: no zapping is to prevent memory leaks.
Neil: what does zap'ing something do?
Tom: zapping the nth stack item replaces it with a reference to a runtime-known object, same with zapping an argument.
Neil: and that argument is fixed, so gc can collect the argument that was there?
kind of like setting a pointer to null, so gc can clean up?
Tom: yup exactly that idea.
Neil: cool
ok, now going to "execute" it in my head, and see where i get, cheers
Tom: np :-)
Neil: return_eval ?
and end_code
i guess return_eval is eval then return
does something have a special return register?
Tom: return_eval is indeed eval,return although it's more clever about that stack. No it returns on the top of the stack.
Neil: so is return just equivalent to push?
or does it pop the elements beneath the result off
Tom: no ... it removes the top frame from the stack aswell.
Neil: so it removes the elements beneath the result?
Tom: so if the stack before was

X,Y,Z,Frame1,A,B,C,Frame2

then after it is

X,A,B,C,Frame2
Neil: where C is the result returned
Tom: where X was the result returned sorry.
Neil: sorry, reading it the wrong direction...
Tom: (my frames go that way :-))
Neil: Frame1 is the arguments to the function?
Tom: a frame is used to record 3 peices of information:
- the code pointer to return to at the end of the current function call
- the node under evaluation to use when returning
- the address of the previous frame


Neil: ok, got it
and END_CODE?
Tom: end_code is a marker to make sure the program doesn't end up outside the code, for example if the compiler forgot to generate a return or got a jump destination wrong or something.
Neil: cool, i guessed that
fantastic, cheers
Tom: it's actually useful having someone else document something you wrote :-) because then they don't skip over the bits you consider to be obvious :-)
Neil: indeed
and for laziness, is only eval lazy?
i.e. it runs linearly, until it gets to an eval which might cause it to invoke a mk_ap ?
Tom: no ... how much do you know about how functional programs are implemented in general?
Neil: a bit....
will just assume "neil" semantics, and might ask for more help in person
i guess that's a hard bit :)
Tom: okay, well laziness is dealt with using thunks. A thunk is a piece of memory that says 
a) which function to call
b) which arguments to call it with.

MK_AP produces a thunk for a given function. When an EVAL instruction is used either a constructor is on the top of the stack or a thunk is. If it's a constructor EVAL is a NOP. if it's a thunk EVAL calls the function named by the thunk with the arguments inside the thunk.
Neil: ok, i get that
so all code is "simple linear time" apart from eval
i.e. once you do the first instruction, you do to the end
Tom: yup, apart from jumps :-)
Neil: i got that :)
Tom: but yes, another interesting property is that there are no backward jumps./
Neil: oh...
i'm going to have a go at hand optimising fac
and see if you could have yhc -o or something...
why does fac eval before returning?
surely it could just return a thunk
oh, i get it
Tom: no function should ever return a WHNF.
since that function must have been called by EVAL.
Neil: so every function should return a WHNF
Tom: no it should always return a HNF.
i.e. evaluated.
Neil: i.e. at least HNF => WHNF ?
it must return fully evaluted expressions?
Tom: it must either return
a) a constructor of some sort
b) an application that does not have enough arguments to be evaluated further (a so called 'partial application).
Neil: ok, so WHNF for constructors
or partial apps
Tom: a constructor is a HNF, not a WHNF. WHNF = thunk.
Neil: hmm, i use WHNF for a constructor at teh root
so my WHNF is your HNF
(i may well be wrong...)
Tom: ehehe well most people generally view a constructor as a head normal form ;-)
Neil: i think i got it off wikipedia...
Tom: In the lambda calculus, a term is in beta normal form if no beta reduction is possible ... . A term is in head normal form if there is no beta-redex in head position.
a constructor has no redex in the head position, because it's fully evaluated.
Neil: ok
Sent at 5:06 pm on Tuesday