将字符串转换为整数并检查溢出

Question

当我尝试将一个非常长的整数转换为Int时，我惊讶地发现没有错误被抛出：

Prelude> read "123456789012345678901234567890" :: Int
-4362896299872285998

Text.Read模块中的readMaybe函数可以产生相同的结果。

有两个问题：

• 我应该调用哪个函数来执行安全转换？
• 地球上最类型安全的语言怎么会允许出现这样不安全的事情？

更新1:

这是我尝试编写一个检查边界的版本的read函数:

{-# LANGUAGE ScopedTypeVariables #-}

parseIntegral :: forall a . (Integral a, Bounded a) => String -> Maybe a
parseIntegral s = integerToIntegral (read s :: Integer) where
  integerToIntegral n | n < fromIntegral (minBound :: a) = Nothing
  integerToIntegral n | n > fromIntegral (maxBound :: a) = Nothing
  integerToIntegral n = Just $ fromInteger n

这是我能做到的最好吗？

- ZhekaKozlov

Answer 1

背景：为什么未检查的溢出实际上是好事

Haskell 98明确规定了溢出行为未指定，这对于实现者来说是好事，但对于其他人则不然。Haskell 2010在两个部分中讨论了它——在从Haskell 98继承的部分中，它被明确规定为未指定，而在Data.Int和Data.Word的部分中，则被指定了。这种不一致性希望最终能够得到解决。

GHC很友善地明确规定了它：

所有算术运算都在模2^n下执行，其中n是类型中位数。

这是一个非常有用的规范。特别地，它保证了Int、Word、Int64、Word32等形成环，甚至是主理想环，在加法和乘法下。这意味着算术将始终正确地工作——你可以以许多不同的方式转换表达式和方程，而不破坏物品。在溢出时抛出异常会破坏所有这些属性，使编写和推理程序变得更加困难。你真正需要小心的时候只有当你使用比较运算符如<和compare——定宽整数不形成有序群，因此这些运算符有点棘手。

为什么不检查读取是有道理的

读取一个整数涉及许多乘法和加法。它还需要快速完成。检查读取是否“有效”并不容易快速实现。特别地，虽然很容易找出加法是否溢出，但是不容易找出乘法是否溢出。我能想到的唯一合理的用于Int的检查读取方式是：

1. 先作为Integer读取，再进行检查，然后转换。 Integer算术比Int算术显著昂贵。对于像Int16这样的较小的内容，可以使用Int进行读取，检查Int16溢出，然后缩小。这更便宜，但仍然不免费。

2. 在读取时将数字十进制与maxBound（或对于负数，minBound）进行比较。这似乎更有可能是相当有效的，但仍然会有一些成本。正如本答案的第一部分所解释的那样，溢出本身并没有固有的问题，因此不清楚抛出错误是否实际上比给出2^n模下的答案更好。

- dfeuer

---

一些小的注释：说“读取”需要快有点奇怪，因为“读取”通常被认为是相当慢的。在Haskell中很难检查任意乘法是否溢出，但乘以十应该很容易检查（只需查看符号是否改变）。 - Daniel Wagner

确实，Int 是一种模数算术类型，但通常人们选择它作为更高效的整数类型，或者因为它是列表函数使用的类型，而不是因为他们真正想要模数算术行为。 - Reid Barton

@dfeuer 我认为关于 Int/Int16 的说法不正确 - 除非你已经知道你的 String 在 Int 的范围内，否则你必须通过 lnteger 绕路 - 这里有一个例子 read (show $ 2 * (fromIntegral (maxBound :: Int) :: Integer)) :: Int 这是一个 Int 溢出，但在流动 -2 后在 Int16 的范围内。 - epsilonhalbe

@epsilonhalbe，我想我写的内容非常不清晰。实际上，你可以手动执行读取（逐位数字），累加一个Int值，并在此过程中检查溢出。因此，您读取一个数字，将累加器乘以十，加上该数字，然后测试累加器是否在Int16范围内。反复洗涤。这避免了读取Integer值所涉及的所有分配（并且，糟糕的是，提醒我真的需要组合一个PR来实现Bertram Felgenhauer改进的“Integer”读取技术）。 - dfeuer

啊，现在我明白了！虽然我从没听说过Felgenhauer ;) - epsilonhalbe

Answer 2

如果不是“不安全”的话，这个问题的行为就不会是未定义的。（它是完全定义好了的，只是可能不是你想要的。）例如，unsafeWriteAray 是不安全的，如果你在使用它时出现错误，它会将数据写入任意内存位置，导致你的应用程序崩溃，或者仅仅使其自身的内存损坏，导致它以任意未定义的方式运行。

至于为什么没有溢出检查...有时候你实际上想让一个数字溢出。（例如，你可能会将其转换为 Word8，而不显式地 AND 出底部 8 位。）无论如何，每个可能的算术操作都可能溢出（例如，maxBound + 1 = minBound，这只是普通的加法。）你真的希望每个单独的算术操作都有一个溢出检查，在每一步都减慢你的程序吗？

在 C、C++ 或 C# 中，你得到的是完全相同的行为。我想区别在于，在 C# 中我们有 checked 关键字，可以让你自动检查溢出。也许有人已经为 Haskell 编写了一个进行检查的算术包...但现在，最简单的方法可能就是自己实现这个检查。

- MathematicalOrchid

---

它是不安全的。请给我一个现实世界应用程序的例子，其中“123456789012345678901234567890”应该解析为“-4362896299872285998”？ 没有这样的应用程序。在C#中行为完全相同吗？ 这绝对不是真的。 在C＃中，Convert.ToInt32会抛出OverflowException。 在Java中，Integer.ParseInt会抛出NumberFormatException。 - ZhekaKozlov

@ZhekaKozlov 1. 没有人在使用C#中的“Int32”或Haskell中的“Int”等限定类型时，会使用“12345678901234567890”（至少在处理需要安全性的代码时）。2. 这种行为绝对且完全是类型安全的，因为类型安全并不自动强制语义正确性。例如，您可以创建类型类的实例，然后进行类型检查，但不强制执行所述类的实例定义的规则。 - ThreeFx

“不正确”和“不安全”并不是同一个意思。如果程序输出错误的答案，那么它是错误的（"incorrect"）。只有当程序可能会导致整个应用程序崩溃或损坏主内存以致于应用程序中其他无关部分出现故障时，它才被认为是不安全（"unsafe"）。 - MathematicalOrchid

通常来说，错误比“错误”更糟糕，因为至少如果你得到一个错误，你知道出了什么问题。真正的未定义行为原则上可能看起来像成功执行，如果你不幸的话，但通常只会导致崩溃。 - Reid Barton

@ZhekaKozlov 在C#中，调用 Convert.ToInt32() 会抛出异常。然而，(int)myLong 不会抛出任何异常。（一个是方法调用，另一个是类型转换。方法进行范围检查；类型转换不进行检查。）但是你是对的，例如 int.TryParse() 进行范围检查。也许为了Haskell的read方法（仅限），添加此检查会有所帮助... - MathematicalOrchid