Type of primitive functions in lazy evaluation
I want to know what the exact type of primitive functions in lazy functional programming languages like Haskell is.
Let's say thunks are evaluated to objects of weak head normal form. Then, what should be the type of primitive functions in strict languages like C?
My guesses are:
primitive1 : (thunk, thunk, ...) -> thunk
primitive2 : (thunk, thunk, ...) -> object
I think primitive functions should be passed thunks as arguments because they may not need some of them. But, I don't know if they should return a thunk or evaluated object while the later one must be wrapped with some function like the below to make it lazy.
lazy : ((thunk, thunk, ...) -> object) -> ((thunk, thunk, ...) -> thunk)
In GHC, a Haskell primitive function (sometimes called a PrimOp) is called with a mixture of pointers (to "heap objects") and unboxed types (including C-style ints, doubles, etc). The Haskell type system ensures that PrimOps always get the number, order, and types of the pointers and unboxed values that they are expecting. It's important to note, though, that where a primitive is expecting a pointer to a specific type of heap object, say a String , it is expecting a pointer to a heap object that may either be a list constructor (since a Haskell String is a list of characters) or a thunk that can be evaluated to a list constructor.
So, the "strict" type of a Haskell PrimOp doesn't differentiate between thunks and non-thunks. If there was a primitive function to get a list's length, for example (there isn't), it would likely have type, using your notation, of:
primitiveLength : (list_object) -> unboxed_int
where the list_object would be a pointer to either a list constructor or a thunk that can yield a list constructor.
This is really the only sensible approach. A PrimOp can't control whether its argument is still a thunk or has been partially (or fully!) evaluated by some previous computation, so it has to be ready to accept either.
Similarly, if a Haskell PrimOp returns a heap object, that object could technically either be a thunk or non-thunk, and the choice would have no effect on the primitive's "strict" type signature.
In practice, it's not very useful for a PrimOp to return a thunk. In a lazy language, the fact that the primitive is being called implies that its return value is needed. If it returns a thunk, that thunk will need to be evaluated right away, so why return a thunk?
(Edited to add:) By the way, there's nothing really specific to PrimOps above: user-defined Haskell functions are also called with a mixture of pointers and unboxed types, too (and they never return thunks).
链接地址: http://www.djcxy.com/p/42990.html上一篇: 什么是Haskell的严格点？
下一篇: 惰性评估中原始函数的类型