Personal tools

Yhc/Notes

From HaskellWiki

< Yhc(Difference between revisions)
Jump to: navigation, search
 
Line 1: Line 1:
AUTHOR: Neil Mitchell & Tom Shackell
+
AUTHOR: Neil Mitchell & Tom Shackell
DATE: 1 Nov 2005
+
DATE: 1 Nov 2005
+
An instant message conversation, contains details about yhc bytecode
+
An instant message conversation, contains details about yhc bytecode
--
+
--
+
Neil: can i ask a few questions on yhc bytecode?
+
Neil: can i ask a few questions on yhc bytecode?
Tom: sure.
+
Tom: sure.
Neil: PUSH_ARG 0 1 <["218"] | {"218"}>
+
Neil: PUSH_ARG 0 1 <["218"] | {"218"}>
what is the 218 for?
+
what is the 218 for?
also, bcodecompile, mem, flatten, rel - what is the order of these stages?
+
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.
+
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?
+
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.
+
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
+
Neil: cool
(will make sure i convert all the stuff in this irc into documentation...)
+
(will make sure i convert all the stuff in this irc into documentation...)
and the bit before the < | > is the stack depth?
+
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.
+
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
+
Neil: cool
Tom: yes that's the stack depth.
+
Tom: yes that's the stack depth.
Neil: eval is evaluate to whnf i guess
+
Neil: eval is evaluate to whnf i guess
Tom: yup.
+
Tom: yup.
Neil: mk_ap?
+
Neil: mk_ap?
what are the numbers, and does it use the stack?
+
what are the numbers, and does it use the stack?
Tom: builds an application node in the heap, using the arguments on the stack.
+
Tom: builds an application node in the heap, using the arguments on the stack.
Neil: application to what?
+
Neil: application to what?
Tom: you'd need to show me an example for me to tell you what the numbers were :-)
+
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"]
+
Neil: FUN Main;fac{189}(2/0) ["v218","v219"]
STACK 3
+
STACK 3
{
+
{
PUSH_ARG 0 1 <["218"] | {"218"}>
+
PUSH_ARG 0 1 <["218"] | {"218"}>
EVAL 1 <[] | {}>
+
EVAL 1 <[] | {}>
INT_CASE {1 -> L_2, _ -> L_4} 1 <[] | {}>
+
INT_CASE {1 -> L_2, _ -> L_4} 1 <[] | {}>
L_2 1 <[] | {}>
+
L_2 1 <[] | {}>
POP 1 0 <[] | {}>
+
POP 1 0 <[] | {}>
PUSH_ARG 1 1 <["219"] | {"219"}>
+
PUSH_ARG 1 1 <["219"] | {"219"}>
EVAL 1 <[] | {}>
+
EVAL 1 <[] | {}>
JUMP L_3 1 <[] | {}>
+
JUMP L_3 1 <[] | {}>
L_4 1 <[] | {}>
+
L_4 1 <[] | {}>
POP 1 0 <[] | {}>
+
POP 1 0 <[] | {}>
JUMP L_0 0 <[] | {}>
+
JUMP L_0 0 <[] | {}>
L_3 1 <[] | {}>
+
L_3 1 <[] | {}>
JUMP L_1 0 <[] | {}>
+
JUMP L_1 0 <[] | {}>
L_0 0 <[] | {}>
+
L_0 0 <[] | {}>
PUSH_ARG 1 1 <["219"] | {"219"}>
+
PUSH_ARG 1 1 <["219"] | {"219"}>
PUSH_ARG 0 2 <["218"] | {"218"}>
+
PUSH_ARG 0 2 <["218"] | {"218"}>
MK_AP 0 2 1 <[] | {}>
+
MK_AP 0 2 1 <[] | {}>
PUSH_INT 1 2 <[] | {}>
+
PUSH_INT 1 2 <[] | {}>
PUSH_ARG 0 3 <["218"] | {"218"}>
+
PUSH_ARG 0 3 <["218"] | {"218"}>
MK_AP 1 2 2 <[] | {}>
+
MK_AP 1 2 2 <[] | {}>
MK_AP 2 2 1 <[] | {}>
+
MK_AP 2 2 1 <[] | {}>
EVAL 1 <[] | {}>
+
EVAL 1 <[] | {}>
L_1 1 <[] | {}>
+
L_1 1 <[] | {}>
RETURN 1 <[] | {}>
+
RETURN 1 <[] | {}>
}
+
}
+
the first mk_app 0 2
+
the first mk_app 0 2
Tom: mk_app using the function described in constant table item 0, with 2 arguments.
+
Tom: mk_app using the function described in constant table item 0, with 2 arguments.
Neil: oh! constraint table
+
Neil: oh! constraint table
Tom: constant table :-)
+
Tom: constant table :-)
Neil: yeah, thats obvious now - forgot abou tit
+
Neil: yeah, thats obvious now - forgot abou tit
and push_int is just a specialised version of push with the constant 1?
+
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
+
http://thread.gmane.org/gmane.comp.lang.haskell.glasgow.user/8827
Tom: indeed.
+
Tom: indeed.
Neil: was reading that thread, and wanted to see what yhc gives for it
+
Neil: was reading that thread, and wanted to see what yhc gives for it
see if we can beat ghc for factorial :)
+
see if we can beat ghc for factorial :)
Tom: something completely different, because yhc is based on a stack machine :-)
+
Tom: something completely different, because yhc is based on a stack machine :-)
Neil: i released hoogle and hugs in beta today
+
Neil: i released hoogle and hugs in beta today
Tom: very unlikely :-)
+
Tom: very unlikely :-)
Neil: so i need a new project
+
Neil: so i need a new project
using yhc to beat ghc for speed in at least one ridiculous microbenchmark might be it!
+
using yhc to beat ghc for speed in at least one ridiculous microbenchmark might be it!
Tom: ehehe I wouldn't bother :-)
+
Tom: ehehe I wouldn't bother :-)
Neil: we'll see
+
Neil: we'll see
i feel i should know more about yhc's details
+
i feel i should know more about yhc's details
Sent at 4:32 pm on Tuesday
+
Sent at 4:32 pm on Tuesday
Tom: feel free to read the source code or ask questions :-)
+
Tom: feel free to read the source code or ask questions :-)
Neil: i was going to write up a document on the bytecode
+
Neil: i was going to write up a document on the bytecode
as a way to learn
+
as a way to learn
and for documentation
+
and for documentation
Tom: sounds good :-)
+
Tom: sounds good :-)
Neil: possibly an executable spec....
+
Neil: possibly an executable spec....
Tom: you won't like the source code for the backend of the compiler though :-)
+
Tom: you won't like the source code for the backend of the compiler though :-)
Neil: i know, too many monads!
+
Neil: i know, too many monads!
zap is purely for gc issues, right?
+
zap is purely for gc issues, right?
Tom: no zapping is to prevent memory leaks.
+
Tom: no zapping is to prevent memory leaks.
Neil: what does zap'ing something do?
+
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.
+
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?
+
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?
+
kind of like setting a pointer to null, so gc can clean up?
Tom: yup exactly that idea.
+
Tom: yup exactly that idea.
Neil: cool
+
Neil: cool
ok, now going to "execute" it in my head, and see where i get, cheers
+
ok, now going to "execute" it in my head, and see where i get, cheers
Tom: np :-)
+
Tom: np :-)
Neil: return_eval ?
+
Neil: return_eval ?
and end_code
+
and end_code
i guess return_eval is eval then return
+
i guess return_eval is eval then return
does something have a special return register?
+
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.
+
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?
+
Neil: so is return just equivalent to push?
or does it pop the elements beneath the result off
+
or does it pop the elements beneath the result off
Tom: no ... it removes the top frame from the stack aswell.
+
Tom: no ... it removes the top frame from the stack aswell.
Neil: so it removes the elements beneath the result?
+
Neil: so it removes the elements beneath the result?
Tom: so if the stack before was
+
Tom: so if the stack before was
+
X,Y,Z,Frame1,A,B,C,Frame2
+
X,Y,Z,Frame1,A,B,C,Frame2
+
then after it is
+
then after it is
+
X,A,B,C,Frame2
+
X,A,B,C,Frame2
Neil: where C is the result returned
+
Neil: where C is the result returned
Tom: where X was the result returned sorry.
+
Tom: where X was the result returned sorry.
Neil: sorry, reading it the wrong direction...
+
Neil: sorry, reading it the wrong direction...
Tom: (my frames go that way :-))
+
Tom: (my frames go that way :-))
Neil: Frame1 is the arguments to the function?
+
Neil: Frame1 is the arguments to the function?
Tom: a frame is used to record 3 peices of information:
+
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 code pointer to return to at the end of the current function call
- the node under evaluation to use when returning
+
- the node under evaluation to use when returning
- the address of the previous frame
+
- the address of the previous frame
+
+
Neil: ok, got it
+
Neil: ok, got it
and END_CODE?
+
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.
+
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
+
Neil: cool, i guessed that
fantastic, cheers
+
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 :-)
+
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
+
Neil: indeed
and for laziness, is only eval lazy?
+
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 ?
+
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?
+
Tom: no ... how much do you know about how functional programs are implemented in general?
Neil: a bit....
+
Neil: a bit....
will just assume "neil" semantics, and might ask for more help in person
+
will just assume "neil" semantics, and might ask for more help in person
i guess that's a hard bit :)
+
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
+
Tom: okay, well laziness is dealt with using thunks. A thunk is a piece of memory that says
a) which function to call
+
a) which function to call
b) which arguments to call it with.
+
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.
+
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
+
Neil: ok, i get that
so all code is "simple linear time" apart from eval
+
so all code is "simple linear time" apart from eval
i.e. once you do the first instruction, you do to the end
+
i.e. once you do the first instruction, you do to the end
Tom: yup, apart from jumps :-)
+
Tom: yup, apart from jumps :-)
Neil: i got that :)
+
Neil: i got that :)
Tom: but yes, another interesting property is that there are no backward jumps./
+
Tom: but yes, another interesting property is that there are no backward jumps./
Neil: oh...
+
Neil: oh...
i'm going to have a go at hand optimising fac
+
i'm going to have a go at hand optimising fac
and see if you could have yhc -o or something...
+
and see if you could have yhc -o or something...
why does fac eval before returning?
+
why does fac eval before returning?
surely it could just return a thunk
+
surely it could just return a thunk
oh, i get it
+
oh, i get it
Tom: no function should ever return a WHNF.
+
Tom: no function should ever return a WHNF.
since that function must have been called by EVAL.
+
since that function must have been called by EVAL.
Neil: so every function should return a WHNF
+
Neil: so every function should return a WHNF
Tom: no it should always return a HNF.
+
Tom: no it should always return a HNF.
i.e. evaluated.
+
i.e. evaluated.
Neil: i.e. at least HNF => WHNF ?
+
Neil: i.e. at least HNF => WHNF ?
it must return fully evaluted expressions?
+
it must return fully evaluted expressions?
Tom: it must either return
+
Tom: it must either return
a) a constructor of some sort
+
a) a constructor of some sort
b) an application that does not have enough arguments to be evaluated further (a so called 'partial application).
+
b) an application that does not have enough arguments to be evaluated further (a so called 'partial application).
Neil: ok, so WHNF for constructors
+
Neil: ok, so WHNF for constructors
or partial apps
+
or partial apps
Tom: a constructor is a HNF, not a WHNF. WHNF = thunk.
+
Tom: a constructor is a HNF, not a WHNF. WHNF = thunk.
Neil: hmm, i use WHNF for a constructor at teh root
+
Neil: hmm, i use WHNF for a constructor at teh root
so my WHNF is your HNF
+
so my WHNF is your HNF
(i may well be wrong...)
+
(i may well be wrong...)
Tom: ehehe well most people generally view a constructor as a head normal form ;-)
+
Tom: ehehe well most people generally view a constructor as a head normal form ;-)
Neil: i think i got it off wikipedia...
+
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.
+
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.
+
a constructor has no redex in the head position, because it's fully evaluated.
Neil: ok
+
Neil: ok
Sent at 5:06 pm on Tuesday
+
Sent at 5:06 pm on Tuesday

Revision as of 15:52, 8 October 2006

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