如何在类型系统中将类型字段限制为 2 的幂？

Question

在某些 JavaScript 代码中有这个：

function allocate(bits) {
  if ((bits & (bits - 1)) != 0) {
    throw "Parameter is not a power of 2";
  }
  ...
}

本质上，输入bits有一个约束，即它是2的幂。或者不称其为“约束”，您可以说输入是 2 的幂的验证。

旁注，我在 SQL 中看到您可以执行这些约束：

CREATE TABLE dbo.Payroll 
    (
     ID int PRIMARY KEY, 
     PositionID INT, 
     Salary decimal(9,2),
     SalaryType nvarchar(10),  
     CHECK  (Salary > 10.00 and Salary < 150000.00) 
    );

ALTER TABLE dbo.Payroll WITH NOCHECK  
  ADD  CONSTRAINT CK_Payroll_SalaryType_Based_On_Salary
  CHECK  ((SalaryType = 'Hourly' and Salary < 100.00) or
          (SalaryType = 'Monthly' and Salary < 10000.00) or
          (SalaryType = 'Annual'));

但在 SQL 和 JavaScript 示例中，此代码在运行时执行以检查其是否有效。我确定 JS，不完全确定 SQL，但我想这是运行时的事情。

我想知道的是如何在 TypeScript 或其他一些 programming language with types 等健壮的类型系统中表达这种“二次方”约束。理想情况下，它是一个编译时约束。这可能吗？如果是这样，它是如何用某种语言完成的？任何语言都可以，主要是寻找如何在具有自己的类型系统的自定义语言中实现这一点的灵感。不完全确定这将如何作为编译时约束工作。是一个“类型”，“两个整数的幂的类型”，但不知道怎么表达。

Answer 1

没有一种最好的方法可以解决这个问题，因为存在多种权衡取舍的方法。以下是 Haskell.

中使用的几种主要样式

“构造更正”

与其接受像 Int 这样更通用的类型并在事后尝试对其进行约束，不如引入一种仅表示有效的 2 的幂的类型，或者通过封装验证：

allocate :: PowerOfTwo -> …

module PowerOfTwo
  ( PowerOfTwo  -- Abstract type
  , powerOfTwo  -- Smart constructor
  , toInt
  ) where

newtype PowerOfTwo = PowerOfTwo Int

powerOfTwo :: Int -> Maybe PowerOfTwo
powerOfTwo n
  | isPowerOfTwo n = Just (PowerOfTwo n)
  | otherwise = Nothing

toInt :: PowerOfTwo -> Int
toInt (PowerOfTwo n) = n

或者根据使无效状态不可表示的原则，这有时可以按照惯例完成：

-- | @'allocate' n@ allocates @2^n@ bits…
allocate :: Word -> …

或结构上：

allocate :: PowerOfTwo -> …

-- | This type can /only/ represent 2^n.
-- (Ignore for the moment that it’s quite inefficient!)
data PowerOfTwo
  = One
  | Twice PowerOfTwo

toInt :: PowerOfTwo -> Int
toInt One = 1
toInt (Twice n) = 2 * n

证明和单例

与输入一起，需要证明输入已经已经被调用者验证；证明只是一个值，只有执行验证才能构造。

在最简单的情况下，这与上面的 newtype 解决方案相同：PowerOfTwo 是一对 Int 和一个已被验证的隐式证明。

但是您也可以将这些证明显式化，这通常在依赖类型的语言中完成，但可以在任何具有表示存在类型的方式的语言中完成，如 singletons library or Ghosts of Departed Proofs 样式：

-- A type-level proposition that n is a power of 2.
data IsPo2 n

-- A classification of whether a value is a power of 2.
data WhetherPo2 n
  = Po2 (Proof (IsPo2 n))
  | NotPo2 (Proof (Not (IsPo2 n)))

-- Assertion that proposition ‘p’ is true.
data Proof p = TrustMe

-- Encapsulated validation, like above,
-- but now it gives back a “proof” value.
validate :: Named n Int -> WhetherPo2 n
validate (Named n)
  | isPowerOfTwo n = Po2 TrustMe
  | otherwise = NotPo2 TrustMe

为了调用“allocate”，您必须提供您验证输入的证明：

allocate
  :: Named n Int
  -> Proof (IsPo2 n)
  -> …

获得一个的唯一途径是 validate:

-- ‘name’ from the paper gives a type-level name to a value.
name 64 $ \ n -> case validate n of

  -- If we got a proof, we can proceed.
  Po2 p -> allocate n p

  -- Calling ‘allocate’ would be a type error here.
  NotPo2 np -> …

像 Idris 和 ATS 这样的依赖类型语言经常使用这种风格，使用像隐式参数这样的语法糖来帮助减少传递这些证明值的噪音。

改进

LiquidHaskell 等一些语言和工具包含 细化类型 的求解器，这些类型 Int 用命题关于他们。在这里，allocate 的输入可以被赋予类似 { n:Int | isPowerOfTwo n } 的类型，这是对上述证明进行编码的更紧凑的方式。

精化类型检查器通常结合使用显式证明、隐式流敏感分析和数值求解 (SMT) 来验证您是否已经测试了确保命题成立的条件。这种风格的优点是易于阅读，但不幸的是，很难预测基于启发式求解器的复杂命题验证何时会失败。

我喜欢所有这些样式的一点是它们不需要重复执行验证；一旦你有一个 proof 某些不变量持有，无论是作为结构不变量还是文字证明对象，那么你可以 assume 它持有，并使用更高效的代码，否则将是不安全的。

如何在类型系统中将类型字段限制为 2 的幂？

How to constrain a type field to a power of two in a type system?

haskell

type-systems

constraints

coq

typescript

“构造更正”

证明和单例

改进