I have some questions about the implementation of haskell... what does it mean to apply 'seq' to a function? how does one place an abstraction in WHNF? it seems that the ONLY thing one can do to a function is apply it to some argument so does seq need to apply the function to a dummy argument or something? similarly, how does seq work on polymorphic types? without knowing what the unboxed representation is for a type, it seems tricky to know how to place it in WHNF... John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john@foo.net ---------------------------------------------------------------------------
hello, John Meacham wrote:
I have some questions about the implementation of haskell...
what does it mean to apply 'seq' to a function? how does one place an abstraction in WHNF? it seems that the ONLY thing one can do to a function is apply it to some argument so does seq need to apply the function to a dummy argument or something? it depends on what you mean by "mean" here :-)
the thing is that not all values of a function type are abstractions... e.g. notAbstraction :: a -> b notAbstraction = notAbstraction is the definition of something of a function type that is not an abstraction. in normal circumstances you couldn't tell this apart from bot x = undefined because the only way to observe functions is to apply them, and both of those behave the same when applied. however in haskell we have "seq", which is an efficiency hack, that can tell those two apart, as seq notAbstraction 1 does not terminate while seq bot 1 terminates with result 1 so operationally when you "seq" something the interpreter starts evaluating it until WHNF is reached, updates the closure appropriately, and returns the second argument of seq. if everything terminated, this would be completely transparent, but since some expresions don't have a normal form things get a little funny.
similarly, how does seq work on polymorphic types? without knowing what the unboxed representation is for a type, it seems tricky to know how to place it in WHNF... well, one doesn't need type information to evaluate haskell programs, so i don't think there is a problem there.
hope this helped, and sorry for the long email bye iavor -- ================================================== | Iavor S. Diatchki, Ph.D. student | | Department of Computer Science and Engineering | | School of OGI at OHSU | | http://www.cse.ogi.edu/~diatchki | ==================================================
This seems to be contrary to how i thought haskell was implemented in ghc (and probably other systems). I was under the impression that thunks in ghc were opaque except for the code address at the begining of them. in order to evaluate something you just jump to the address stored in it. so i guess my question is, when seq'ing a function, how does one keep it from trying to pull an argument off the stack (and evaluating it if the function is strict)? are there multiple entry points for thunks, one which means 'evaluate to WHNF' and another which actually returns the result? if so, how is this information passed to polymorphic functions which call seq. it seems that you would have to do something different for abstractions and boxed values.. John On Wed, Feb 12, 2003 at 05:32:33PM -0800, Iavor S. Diatchki wrote:
John Meacham wrote:
I have some questions about the implementation of haskell...
what does it mean to apply 'seq' to a function? how does one place an abstraction in WHNF? it seems that the ONLY thing one can do to a function is apply it to some argument so does seq need to apply the function to a dummy argument or something? it depends on what you mean by "mean" here :-)
the thing is that not all values of a function type are abstractions... e.g. notAbstraction :: a -> b notAbstraction = notAbstraction is the definition of something of a function type that is not an abstraction.
in normal circumstances you couldn't tell this apart from bot x = undefined
because the only way to observe functions is to apply them, and both of those behave the same when applied. however in haskell we have "seq", which is an efficiency hack, that can tell those two apart, as seq notAbstraction 1 does not terminate while seq bot 1 terminates with result 1
so operationally when you "seq" something the interpreter starts evaluating it until WHNF is reached, updates the closure appropriately, and returns the second argument of seq. if everything terminated, this would be completely transparent, but since some expresions don't have a normal form things get a little funny.
similarly, how does seq work on polymorphic types? without knowing what the unboxed representation is for a type, it seems tricky to know how to place it in WHNF... well, one doesn't need type information to evaluate haskell programs, so i don't think there is a problem there.
-- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john@foo.net ---------------------------------------------------------------------------
On Fri, 14 Feb 2003, John Meacham wrote:
This seems to be contrary to how i thought haskell was implemented in ghc (and probably other systems). I was under the impression that thunks in ghc were opaque except for the code address at the begining of them. in order to evaluate something you just jump to the address stored in it.
so i guess my question is, when seq'ing a function, how does one keep it from trying to pull an argument off the stack (and evaluating it if the function is strict)? are there multiple entry points for thunks, one which means 'evaluate to WHNF' and another which actually returns the result?
What difference is there between "evaluate to WHNF" and "return a result"?
if so, how is this information passed to polymorphic functions which call seq. it seems that you would have to do something different for abstractions and boxed values.. John
-- Dean
John Meacham wondered: | what does it mean to apply 'seq' to a function? how | does one place an abstraction in WHNF? it seems that | the ONLY thing one can do to a function is apply it to | some argument so does seq need to apply the function | to a dummy argument or something? Here is a simple example: funs :: [Int -> Int] funs = [ \x -> x + i | i <- [1..] ] f :: Int -> Int f = funs !! 1000000 Calculating f, without applying it to arguments, really takes some time. Hope this helps, /Koen -- Koen Claessen http://www.cs.chalmers.se/~koen Chalmers University, Gothenburg, Sweden.
participants (4)
-
Dean Herington -
Iavor S. Diatchki -
John Meacham -
Koen Claessen