Personal tools

Yhc/Notes

From HaskellWiki

< Yhc(Difference between revisions)
Jump to: navigation, search
 
 
(One intermediate revision by one user not shown)
Line 1: Line 1:
AUTHOR: Neil Mitchell & Tom Shackell
 
DATE: 1 Nov 2005
 
   
An instant message conversation, contains details about yhc bytecode
+
== Yhc Bytecode ==
--
 
   
Neil: can i ask a few questions on yhc bytecode?
+
AUTHOR: Neil Mitchell & Tom Shackell
Tom: sure.
+
DATE: 1 Nov 2005
Neil: PUSH_ARG 0 1 <["218"] | {"218"}>
+
what is the 218 for?
+
An instant message conversation, contains details about yhc bytecode
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?
+
Neil: can i ask a few questions on yhc bytecode?
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: sure.
Neil: cool
+
Neil: PUSH_ARG 0 1 <["218"] | {"218"}>
(will make sure i convert all the stuff in this irc into documentation...)
+
what is the 218 for?
and the bit before the < | > is the stack depth?
+
also, bcodecompile, mem, flatten, rel - what is the order of these stages?
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: in order to do stack and argument zapping it's necessary to know what variables are live at any time.
Neil: cool
+
Neil: so they are annotations?
Tom: yes that's the stack depth.
+
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: eval is evaluate to whnf i guess
+
Neil: cool
Tom: yup.
+
(will make sure i convert all the stuff in this irc into documentation...)
Neil: mk_ap?
+
and the bit before the < | > is the stack depth?
what are the numbers, and does it use the stack?
+
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: builds an application node in the heap, using the arguments on the stack.
+
Neil: cool
Neil: application to what?
+
Tom: yes that's the stack depth.
Tom: you'd need to show me an example for me to tell you what the numbers were :-)
+
Neil: eval is evaluate to whnf i guess
Neil: FUN Main;fac{189}(2/0) ["v218","v219"]
+
Tom: yup.
STACK 3
+
Neil: mk_ap?
{
+
what are the numbers, and does it use the stack?
PUSH_ARG 0 1 <["218"] | {"218"}>
+
Tom: builds an application node in the heap, using the arguments on the stack.
EVAL 1 <[] | {}>
+
Neil: application to what?
INT_CASE {1 -> L_2, _ -> L_4} 1 <[] | {}>
+
Tom: you'd need to show me an example for me to tell you what the numbers were :-)
L_2 1 <[] | {}>
+
Neil: FUN Main;fac{189}(2/0) ["v218","v219"]
POP 1 0 <[] | {}>
+
STACK 3
PUSH_ARG 1 1 <["219"] | {"219"}>
+
{
EVAL 1 <[] | {}>
+
PUSH_ARG 0 1 <["218"] | {"218"}>
JUMP L_3 1 <[] | {}>
+
EVAL 1 <[] | {}>
L_4 1 <[] | {}>
+
INT_CASE {1 -> L_2, _ -> L_4} 1 <[] | {}>
POP 1 0 <[] | {}>
+
L_2 1 <[] | {}>
JUMP L_0 0 <[] | {}>
+
POP 1 0 <[] | {}>
L_3 1 <[] | {}>
+
PUSH_ARG 1 1 <["219"] | {"219"}>
JUMP L_1 0 <[] | {}>
+
EVAL 1 <[] | {}>
L_0 0 <[] | {}>
+
JUMP L_3 1 <[] | {}>
PUSH_ARG 1 1 <["219"] | {"219"}>
+
L_4 1 <[] | {}>
PUSH_ARG 0 2 <["218"] | {"218"}>
+
POP 1 0 <[] | {}>
MK_AP 0 2 1 <[] | {}>
+
JUMP L_0 0 <[] | {}>
PUSH_INT 1 2 <[] | {}>
+
L_3 1 <[] | {}>
PUSH_ARG 0 3 <["218"] | {"218"}>
+
JUMP L_1 0 <[] | {}>
MK_AP 1 2 2 <[] | {}>
+
L_0 0 <[] | {}>
MK_AP 2 2 1 <[] | {}>
+
PUSH_ARG 1 1 <["219"] | {"219"}>
EVAL 1 <[] | {}>
+
PUSH_ARG 0 2 <["218"] | {"218"}>
L_1 1 <[] | {}>
+
MK_AP 0 2 1 <[] | {}>
RETURN 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
   
the first mk_app 0 2
+
== Factorial optimisation ==
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
+
AUTHOR: Neil Mitchell
+
DATE: 01 Nov 2005
then after it is
+
+
Thoughts on how to optimise factorial
X,A,B,C,Frame2
+
--
Neil: where C is the result returned
+
Tom: where X was the result returned sorry.
+
====== BCode after flattening::
Neil: sorry, reading it the wrong direction...
+
FUN Main;fac{189}(2/0) ["v218","v219"]
Tom: (my frames go that way :-))
+
STACK 3
Neil: Frame1 is the arguments to the function?
+
{
Tom: a frame is used to record 3 peices of information:
+
L_5
- the code pointer to return to at the end of the current function call
+
NEED_HEAP 4
- the node under evaluation to use when returning
+
PUSH_ARG 0
- the address of the previous frame
+
EVAL
+
L_2
+
INT_SWITCH {1 -> L_1, _ -> L_4}
Neil: ok, got it
+
L_1
and END_CODE?
+
NEED_HEAP 3
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.
+
POP 1
Neil: cool, i guessed that
+
PUSH_ZAP_ARG 1
fantastic, cheers
+
RETURN_EVAL
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 :-)
+
L_4
Neil: indeed
+
NEED_HEAP 16
and for laziness, is only eval lazy?
+
POP 1
i.e. it runs linearly, until it gets to an eval which might cause it to invoke a mk_ap ?
+
PUSH_ZAP_ARG 1
Tom: no ... how much do you know about how functional programs are implemented in general?
+
PUSH_ARG 0
Neil: a bit....
+
MK_AP 0 2
will just assume "neil" semantics, and might ask for more help in person
+
PUSH_INT 1
i guess that's a hard bit :)
+
PUSH_ZAP_ARG 0
Tom: okay, well laziness is dealt with using thunks. A thunk is a piece of memory that says
+
MK_AP 1 2
a) which function to call
+
MK_AP 2 2
b) which arguments to call it with.
+
RETURN_EVAL
+
END_CODE
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
+
---- ConstTable ---------------
so all code is "simple linear time" apart from eval
+
0 FUN Prelude;Prelude.Num.Prelude.Int.*{216}
i.e. once you do the first instruction, you do to the end
+
1 FUN Prelude;Prelude.Num.Prelude.Int.-{215}
Tom: yup, apart from jumps :-)
+
2 FUN Main;fac{189}
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
+
1 ######################################
and see if you could have yhc -o or something...
+
why does fac eval before returning?
+
Lets convert this into friendlier syntax
surely it could just return a thunk
+
and drop the GC relevant bits
oh, i get it
+
Tom: no function should ever return a WHNF.
+
main.fac(a, b)
since that function must have been called by EVAL.
+
push a
Neil: so every function should return a WHNF
+
eval
Tom: no it should always return a HNF.
+
switch (1 -> L1, _ -> L2)
i.e. evaluated.
+
L1
Neil: i.e. at least HNF => WHNF ?
+
pop
it must return fully evaluted expressions?
+
push b
Tom: it must either return
+
eval
a) a constructor of some sort
+
return
b) an application that does not have enough arguments to be evaluated further (a so called 'partial application).
+
L2
Neil: ok, so WHNF for constructors
+
pop
or partial apps
+
push b
Tom: a constructor is a HNF, not a WHNF. WHNF = thunk.
+
push a
Neil: hmm, i use WHNF for a constructor at teh root
+
app * 2
so my WHNF is your HNF
+
push 1
(i may well be wrong...)
+
push a
Tom: ehehe well most people generally view a constructor as a head normal form ;-)
+
app - 2
Neil: i think i got it off wikipedia...
+
app fac 2
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.
+
eval
a constructor has no redex in the head position, because it's fully evaluated.
+
return
Neil: ok
+
Sent at 5:06 pm on Tuesday
+
  +
2 ######################################
  +
  +
Stack motion, pop; push x is equivalent to push x; push y at the previous push
  +
push x; pop; push x is just push x
  +
  +
main.fac(a, b)
  +
push b
  +
push a
  +
eval
  +
switch (1 -> L1, _ -> L2)
  +
L1
  +
pop
  +
eval
  +
return
  +
L2
  +
app * 2
  +
push 1
  +
push a
  +
app - 2
  +
app fac 2
  +
eval
  +
return
  +
  +
  +
3 ######################################
  +
  +
Determine by strictness analysis that fac is strict in both arguments
  +
This is relatively easy - look down each path, either all arguments are eval'd
  +
Or its a recursive call, hence all arguments are always eval'd
  +
Its easier because its Int, therefore eval is full eval
  +
  +
This allows us to move eval b to the common part
  +
  +
main.fac(a, b)
  +
push b
  +
eval
  +
push a
  +
eval
  +
switch (1 -> L1, _ -> L2)
  +
L1
  +
pop
  +
return
  +
L2
  +
app * 2
  +
push 1
  +
push a
  +
app - 2
  +
app fac 2
  +
eval
  +
return
  +
  +
4 ######################################
  +
  +
Since simple analysis now gives us that * and + are applied to strict arguments
  +
lets convert that into call, instead of app
  +
  +
main.fac(a, b)
  +
push b
  +
eval
  +
push a
  +
eval
  +
switch (1 -> L1, _ -> L2)
  +
L1
  +
pop
  +
return
  +
L2
  +
call * 2
  +
push 1
  +
push a
  +
call - 2
  +
call fac 2
  +
return
  +
  +
5 ######################################
  +
  +
Now we have a tailcall, since fac 2 already has a and b on the stack
  +
and since they are both fully evaluated, we can skip that bit
  +
it appears the order in the call is wrong though, so lets fix that by swapping them
  +
  +
main.fac(a, b)
  +
push b
  +
eval
  +
push a
  +
eval
  +
L0
  +
switch (1 -> L1, _ -> L2)
  +
L1
  +
pop
  +
return
  +
L2
  +
call * 2
  +
push 1
  +
push a
  +
call - 2
  +
swap
  +
goto L0
  +
  +
  +
6 ######################################
  +
  +
That's as good as the bytecode can go, I think, but now lets head off to a C generator
  +
plus a wrapper for the boxing/unboxing
  +
  +
  +
main.fac(a, b)
  +
{
  +
L0:
  +
if (a == 1)
  +
{
  +
return b
  +
}
  +
else
  +
{
  +
int ta = a - 1
  +
int tb = a * b
  +
a = ta
  +
b = tb
  +
goto L0
  +
}
  +
}
  +
  +
7 ######################################
  +
  +
goto, urgh - lets hoist it into a loop
  +
  +
main.fac(a, b)
  +
{
  +
while (a != 1)
  +
{
  +
int ta = a - 1
  +
int tb = a * b
  +
a = ta
  +
b = tb
  +
}
  +
return b
  +
}
  +
  +
8 ######################################
  +
  +
and lets get rid of those temporaries
  +
  +
main.fac(a, b)
  +
{
  +
while (a != 1)
  +
{
  +
b *= a--
  +
}
  +
return b
  +
}
  +
  +
9 #####################################
  +
  +
Done, and I'm certain GHC doesn't do any better!

Latest revision as of 15:53, 8 October 2006

[edit] 1 Yhc Bytecode

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

[edit] 2 Factorial optimisation

AUTHOR: Neil Mitchell
DATE: 01 Nov 2005

Thoughts on how to optimise factorial
--

======  BCode after flattening::
FUN Main;fac{189}(2/0) ["v218","v219"]
 STACK 3
   {
L_5
    NEED_HEAP 4
    PUSH_ARG 0
    EVAL
L_2
    INT_SWITCH {1 -> L_1, _ -> L_4}
L_1
    NEED_HEAP 3
    POP 1
    PUSH_ZAP_ARG 1
    RETURN_EVAL
L_4
    NEED_HEAP 16
    POP 1
    PUSH_ZAP_ARG 1
    PUSH_ARG 0
    MK_AP 0 2
    PUSH_INT 1
    PUSH_ZAP_ARG 0
    MK_AP 1 2
    MK_AP 2 2
    RETURN_EVAL
    END_CODE
   }
---- ConstTable ---------------
0 FUN Prelude;Prelude.Num.Prelude.Int.*{216}
1 FUN Prelude;Prelude.Num.Prelude.Int.-{215}
2 FUN Main;fac{189}
-------------------------------


1 ######################################

Lets convert this into friendlier syntax
and drop the GC relevant bits

main.fac(a, b)
    push a
    eval
    switch (1 -> L1, _ -> L2)
L1
    pop
    push b
    eval
    return
L2
    pop
    push b
    push a
    app * 2
    push 1
    push a
    app - 2
    app fac 2
    eval
    return


2 ######################################

Stack motion, pop; push x is equivalent to push x; push y at the previous push
push x; pop; push x is just push x

main.fac(a, b)
    push b
    push a
    eval
    switch (1 -> L1, _ -> L2)
L1
    pop
    eval
    return
L2
    app * 2
    push 1
    push a
    app - 2
    app fac 2
    eval
    return


3 ######################################

Determine by strictness analysis that fac is strict in both arguments
This is relatively easy - look down each path, either all arguments are eval'd
Or its a recursive call, hence all arguments are always eval'd
Its easier because its Int, therefore eval is full eval

This allows us to move eval b to the common part

main.fac(a, b)
    push b
    eval
    push a
    eval
    switch (1 -> L1, _ -> L2)
L1
    pop
    return
L2
    app * 2
    push 1
    push a
    app - 2
    app fac 2
    eval
    return

4 ######################################

Since simple analysis now gives us that * and + are applied to strict arguments
lets convert that into call, instead of app

main.fac(a, b)
    push b
    eval
    push a
    eval
    switch (1 -> L1, _ -> L2)
L1
    pop
    return
L2
    call * 2
    push 1
    push a
    call - 2
    call fac 2
    return

5 ######################################

Now we have a tailcall, since fac 2 already has a and b on the stack
and since they are both fully evaluated, we can skip that bit
it appears the order in the call is wrong though, so lets fix that by swapping them

main.fac(a, b)
    push b
    eval
    push a
    eval
L0
    switch (1 -> L1, _ -> L2)
L1
    pop
    return
L2
    call * 2
    push 1
    push a
    call - 2
    swap
    goto L0
    

6 ######################################

That's as good as the bytecode can go, I think, but now lets head off to a C generator
plus a wrapper for the boxing/unboxing


main.fac(a, b)
{
L0:
    if (a == 1)
    {
        return b
    }
    else
    {
        int ta = a - 1
        int tb = a * b
        a = ta
        b = tb
        goto L0
    }
}

7 ######################################

goto, urgh - lets hoist it into a loop

main.fac(a, b)
{
    while (a != 1)
    {
        int ta = a - 1
        int tb = a * b
        a = ta
        b = tb
    }
    return b
}

8 ######################################

and lets get rid of those temporaries

main.fac(a, b)
{
    while (a != 1)
    {
        b *= a--
    }
    return b
}

9 #####################################

Done, and I'm certain GHC doesn't do any better!