英文:
Should the state of the ST not change in order to be executed by the runST?
问题
type ST s a = ST (s -> (s, a))
runST :: (forall s. ST s a) -> a
runST (ST f) = case (f realWorld) of (_, a) -> a
如您所要求的,这是提供的代码的翻译部分。
英文:
type ST s a = ST (s -> (s, a))
runST :: (forall s. ST s a) -> a
runST (ST f) = case (f realWorld) of (_, a) -> a
If you look closely, there are many errors, but the overall structure of runST
is as above.
So, if you want to apply runST
to a value of type ST s a
, which is identical to s -> (s, a)
, its type s
must be fully parameterized.
Some kinds of functions depending on concrete type can't applied by runST
.
Example of inappropriate function is below.
\s -> (s + s, "hello world") // this won't run cause it depends on (Num) type class.
fun [] = ([], 0)
fun (x : xs) = (xs, length (x : xs)) // this won't run. It depends on ([]) type.
So, functions to be executed by runST should be as follows.
\s -> (s, fun s)
fun = maybe some native code, not haskell.
The point is that s
from (s, a)
term of s -> (s, a)
should always same as s
itself, like an identity.
We call it parametricity.
Currently I know that if s
has RealWorld
in it, even what seems to be an id
can make meaningful calculations. (Although it's not pure Haskell).
To prove what I guessed, I prepared the following experiment.
//given
newMutVar# :: v -> State# s -> (# State# s, MutVar# s v #)
//then (this is pseudo code)
let (# s#, var# #) = newMutVar# "hello world" (State# 0) in
s# == State# 0
and see if the result is True
, which implies that newMutVar#
acts like id
for State#
.
But I can't do this because I don't know how to generate State# s
value. I know how to do it only for RealWorld
, and its meaningless cause RealWorld
only has one value inside so it always be identical no matter what the mapping is.
Also, even if I succeed generating State# 0
, there's no way to compare State# 0
to s#
, cause State# s
doesn't implement Eq
.
答案1
得分: 4
我认为你在某种程度上混淆了State
类型和ST
。我看到你已经深入了解了GHC如何定义ST
和IO
,但我认为你对所看到的内容的含义存在误解。你试图以实现方式来推理,就好像它与State
是相同的东西。鉴于使用了类似State#
的名称和定义的一般结构,这是可以理解的:
type STRep s a = State# s -> (# State# s, a #)
这看起来确实像State
类型的背后思想,但这非常具有误导性。要理解原因,你需要查看State#的文档,它以关键句子结束:“它根本不被表示为任何东西。”
没有类型为State# Realworld
或State# s
的值。具有像STRep s a
这样类型的函数实际上是一个零参数函数(State# s
参数根本不被表示为任何东西),返回一个类型为a
的单个值(不包装的一对根本不被表示为任何东西和一个a
值)。
这在GHC的实现中非常神奇。 你不能创建这样的类型。(我发现现在有足够多的这种类型,GHC实际上已经暴露了创建自己的工具。但它们远非标准的Haskell。)编译器必须识别它并支持处理它的所有特殊情况。那么为什么要这样做呢?因为它用于桥接Haskell函数和机器代码过程之间的表示差异。在Haskell(好吧,GHC核心)级别进行的所有优化都看到一个常规的Haskell函数,它执行令牌传递。令牌传递用于序列化执行,以便在进行优化时,GHC不能重新排序操作。但当GHC核心转换为本机代码生成后端的C--或LLVM后端的LLVM IR时,所有State#
值都被剥离,以便在低级别上,你不再具有GHC核心表示所建议的那种无用的令牌传递。
因此,你不知道如何创建State#
值的原因是它们根本不存在。它们永远不会更新,因为ST
与State
的工作方式完全不同,尽管它们在内部具有表面相似性。
英文:
I think you've conflated the State
type with ST
to some extent. I see that you've looked behind the curtains to see how GHC defines ST
and IO
, but I think you've misinterpreted the meaning of what you see there. You're trying to reason about the implementation as if it was the same thing as State
. That's understandable given the use of names like State#
and the general structure of definitions like this:
type STRep s a = State# s -> (# State# s, a #)
That sure looks like the idea behind the State
type, but that's very misleading. To see why, you need to look at the documentation for State#
which ends with a critical sentence: "It is represented by nothing at all."
There is no such thing as a value of type State# Realworld
or State# s
. A function with a type like STRep s a
up there actually is a 0-argument function (the State# s
argument is represented by nothing at all) that returns a single value of type a
(an unboxed pair of nothing at all and an a
value).
This is very magical within the implementation of GHC. <s>You can't create a type like that.</s> (I've discovered that there are enough such types now that GHC actually does expose tools to create your own. But they're far from standard Haskell.) The compiler has recognize it and support all the special cases for handling it correctly. So why bother? Because it serves to bridge the difference in representation between a Haskell function and a machine code procedure. All the optimizations which take place at the Haskell (well, GHC core) level see a regular Haskell function that's doing token passing. The token passing serves to serialize execution so that GHC can't reorder operations when it's doing optimizations. But then when the GHC core is converted into either C-- for the native code gen backend or LLVM IR for the LLVM backend, all the State#
values get stripped out so that at a low level you don't have all that useless token passing that the GHC core representation suggested is happening.
So the reason you don't know how to create a State#
value is that they don't exist. They're never updated because ST
doesn't work anything like State
, despite the superficial similarities in their internals.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论