ST的状态是否需要保持不变才能在runST中执行?

huangapple go评论57阅读模式
英文:

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如何定义STIO,但我认为你对所看到的内容的含义存在误解。你试图以实现方式来推理,就好像它与State是相同的东西。鉴于使用了类似State#的名称和定义的一般结构,这是可以理解的:

type STRep s a = State# s -> (# State# s, a #)

这看起来确实像State类型的背后思想,但这非常具有误导性。要理解原因,你需要查看State#的文档,它以关键句子结束:“它根本不被表示为任何东西。”

没有类型为State# RealworldState# s的值。具有像STRep s a这样类型的函数实际上是一个零参数函数(State# s参数根本不被表示为任何东西),返回一个类型为a的单个值(不包装的一对根本不被表示为任何东西和一个a值)。

这在GHC的实现中非常神奇。 你不能创建这样的类型。(我发现现在有足够多的这种类型,GHC实际上已经暴露了创建自己的工具。但它们远非标准的Haskell。)编译器必须识别它并支持处理它的所有特殊情况。那么为什么要这样做呢?因为它用于桥接Haskell函数和机器代码过程之间的表示差异。在Haskell(好吧,GHC核心)级别进行的所有优化都看到一个常规的Haskell函数,它执行令牌传递。令牌传递用于序列化执行,以便在进行优化时,GHC不能重新排序操作。但当GHC核心转换为本机代码生成后端的C--或LLVM后端的LLVM IR时,所有State#值都被剥离,以便在低级别上,你不再具有GHC核心表示所建议的那种无用的令牌传递。

因此,你不知道如何创建State#值的原因是它们根本不存在。它们永远不会更新,因为STState的工作方式完全不同,尽管它们在内部具有表面相似性。

英文:

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.

huangapple
  • 本文由 发表于 2023年4月4日 13:17:30
  • 转载请务必保留本文链接:https://go.coder-hub.com/75925737.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定