Common Lisp 中的依赖 types/Parametric 多态性？
Dependent types/Parametric polymorphism in Common Lisp?
我想编写一些处理反射群的通用代码，因此需要设置一些反映数学结构的类型（向量 space、仿射 space、...）。因为我真的很想在类型中忠实地反映这些结构，所以我需要一种方法来定义某种参数类型。
所以特别是，我希望能够编写以下代码
(defclass RealVectorSpace ()
((V :accessor underlying-set
:type Set)
(vector-add :accessor add
:type (function ((set-as-type V) (set-as-type V)) (set-as-type V)))
(scalar-mult :accessor s-mult
:type (function (real (set-as-type V)) (set-as-type V)))
它应该指定一个新类型 RealVectorSpace ，它将由一个三元组（V vector-add 标量）给出，其中 V 可以是任何东西，而 vector-add 是一个函数，它采用两个 V 类型（原文如此）的参数来评估类型 V.
当然，这种类型不会完全忠实地反映实向量的概念 space，因为向量加法和标量乘法仍需要满足一些其他属性。但即使将上面的 'dream' 变成真正的代码，我也无法理解。
编辑：针对sds的回答，让我对我原来的问题提出以下澄清：简而言之，我似乎需要 Lisp 中的依赖类型 ，这与仅要求参数 类 不同。事实上，Haskell 有参数类型但没有（至少它不是以明显的方式内置的）依赖类型。例如 Haskell 中缺少依赖类型 here.
1.谁能帮我把梦想变成代码？
2。我在某处听说由于 Lisp 宏，您在 Lisp 中不需要参数 类 。如果那是真的，有人能解释一下你如何在 Common Lisp 中使用 defmacro 来 implement/fake 参数化 类 吗？
我怀疑你想要的东西是否有意义，
但作为宏（滥用）使用的示例，您可以：
(defmacro define-real-vector-space (type &optional name)
`(defclass ,(or name (intern (format nil "REAL-VECTOR-SPACE-~A" type))) ()
((V :reader underlying-set :initform ',type)
(vector-add :accessor add
:type (function ((x ,type) (y ,type)) => ,type))
(scalar-mult :accessor s-mult
:type (function ((x real) (v ,type) => ,type))))))
;; sample underlying set:
(deftype 3d () (array real (3)))
;; use it:
(macroexpand-1 '(define-real-vector-space 3d))
==>
(DEFCLASS REAL-VECTOR-SPACE-3D NIL
((V :READER UNDERLYING-SET :INITFORM '|3D|)
(VECTOR-ADD :ACCESSOR ADD :TYPE (FUNCTION ((X |3D|) (Y |3D|)) => |3D|))
(SCALAR-MULT :ACCESSOR S-MULT :TYPE #'((X REAL) (V |3D|) => |3D|))))
(define-real-vector-space 3d)
回复评论：
如果你想要一个单身real-vector-spaceclass，你基本上是，
要求 vector-add 和 scalar-mult 插槽具有类型 which
取决于 V 插槽的值。
这意味着 (setf (underlying-set rvs) some-new-type) 会
必须检查 (add rvs) 和 (s-mult rvs) 必须适当
键入 some-new-type。
本质上，这意味着类型的每个对象
real-vector-space 是不可变的，所有的插槽都被修改
同时。
前一种选择可以通过明智的使用来实现
MOP。
我不确定后者在 Lisp 中是否可行。
您可以阅读 LIL，Lisp 接口库，在 LIL：CLOS 达到高阶, 流出身份
并从 Faré Rideau 那里获得了变革性的经验。 github page 有更多详细信息。
基本上，LIL 试图通过一个额外的参数（接口，它类似于一个类型 class）来表达参数多态性，这要归功于动态范围。
另一方面，使用 OCaml 模块很容易表达您想要表达的内容，因此根据您的需要，您最好遵循 Rainer Joswig 的建议（使用另一种语言）。
module type VectorSpace =
functor (S : sig val dimension : int end)
(F : sig type scalar val zero : scalar end) ->
sig
type vector = F.scalar array
val add : vector -> vector -> vector
val mul : F.scalar -> vector -> vector
end
至于属性（如评论中所要求），您可能需要使用更复杂的类型系统（Coq？）。
Common Lisp 如何很好地抽象事物的一个例子是 Gábor Melis's MGL-CUBE.
我们开始：部分 answer/solution 我的问题（为什么部分？见下文）。非常感谢 sds 帮我解决了这个问题！
首先让我澄清一下。当我最初提出问题时，我不准确地使用了术语 'parametric type'，只考虑了一个模糊的定义 'a type depending parameters'。我基本上想要一些小工具允许我编写以下 pseudo-code（在 pseudo-language 中）：
class List<T> {
//implementation
};
l = new List<string>;
l.push("Hello World!");
理解上面的内容 pseudo-code 很不错 straight-forward（参见 sds 的回答）。然而，如果开始怀疑表达式 List<T> 和 List 本身是否应该有意义，就会出现歧义。事实上，例如在 C++ 中，表达式将是未定义的，因为模板定义的效果
template <typename T>
class List {
public:
T car;
List<T> *cdr;
};
就好像是分别定义，每个类型T，一个类型List<T>。相反，在像 Java 这样实现了 泛型类型 的语言中，表达式 List<T> （其中 T 是一个自由变量）是有意义的并且表示类型，即 some 类型 T 上的列表的泛型类型，因此可以例如写一个像
这样的多态函数
T car(List<T> l) {
return l.car;
}
简而言之，在 C++ 中，我们只有所有类型的（无限）集合 List<T>，其中 T 遍历所有类型，而在 Java 中，这个集合本身作为一个语言中的对象，作为通用类型 List<T>.
现在是我提出的部分解决方案，在编写实际的 Lisp 代码之前，我将简要地用文字概括一下。该解决方案基于 type families 和此类 families 的 dependent sum，即我们将解释一个参数类型，例如 [=24] =] 作为一个参数的函数 List，其值是类型，我们将 Java-style 泛型类型 List<T> 伪造为 依赖总和类型 DepSum(List)，它仅由对 (a,b) 组成，其中 a 是某种类型，b 是 List(b).
类型
回到在集合X上定义实数向量space的例子，我想写类似
的东西
(defclassfamily RealVectorSpaceOver (X) ()
((add :initarg :add
:reader add
:type (function (X X) X))
(s-mult :initarg :s-mult
:reader s-mult
:type (function (real X) X)))
为我定义一个函数 RealVectorSpaceOver，给定一个 class A，return 一个 class 就好像由
手动定义一样
(defclass RealVectorSpaceOverA ()
((add :initarg :add
:reader add
:type (function (A A) A))
(s-mult :initarg :s-mult
:reader s-mult
:type (function (real A) A)))
基本上，我可以copy-n-paste这里解决sds问题，但是这有两个问题。首先，结果不会是 (side-effect-free) 函数，例如表单
(typep (make-instance (RealVectorSpaceOver A)
:add (lambda (x y) nil)
:s-mult (lambda (x y) nil))
(RealVectorSpaceOver A))
的计算结果为 nil，因为这里有两次调用 RealVectorSpaceOver，每次调用都会创建一个新的（因此不同的）class。因此，我们需要将此函数包装在一些代码中，以便在第一次调用时缓存结果。
另一个问题是，使用 defclass 以编程方式创建 classes 具有更改 class 名称 space 的效果，可能会重新定义现有的 class是的。为了避免这种情况，可以通过实例化元 class standard-class 来直接创建新的 classes。例如
(make-instance 'standard-class
:name (intern "B")
:direct-superclasses '(A)
:direct-slots '((x :initargs (:x) :readers (x))))
等同于
(defclass B (A)
((x :initarg :x :reader x)))
但不会重新定义任何 pre-existing class B。请注意，:direct-slots 参数的格式与用于定义插槽的 defclass 格式略有不同。使用将后者转换为前者的辅助函数canonicalize-direct-slot-defs（取自书'The Art of the Metaobject Protocol'），宏defclassfamily可以实现如下：
(defmacro defclassfamily (name variables superclasses slot-defs)
(let ((stripped-variables (strip-variables variables))
(variable-types (types-of-variables variables))
(type-decls (type-decls-from-variables variables)))
`(flet ((f ,stripped-variables
(make-instance 'standard-class
:name (intern (format nil "~S<~S>" ',name (list ,@stripped-variables)))
:direct-superclasses ,superclasses
:direct-slots ,(canonicalize-direct-slots slot-defs))))
(let ((g (cache-function #'f)))
(defun ,name ,stripped-variables
,@type-decls
(the standard-class (funcall g ,@stripped-variables)))
(defmethod argument-signature ((x (eql #',name)))
',variable-types)))))
上面的代码首先定义了一个代表所需类型族的函数 f，然后使用辅助函数 cache-function（插入您的自己的实现），然后使用 defun 在名称 space 中定义一个新函数，强制参数的类型（defclassfamily 接受类似于 defmethod 的类型化参数，因此(defclassfamily F ((X Set) Y) ... 将定义一个包含两个参数的家族 F，第一个参数是 Set) 类型，return 是 class 家族的值。此外，还有一些简单的辅助函数 strip-variables、types-of-variables 和 type-decls-from-variables 可以转换给定类型族变量（上例中的 (X Set) Y）的表达式。它们的定义如下：
(defun strip-variables (specialized-lambda-list)
(mapcar (lambda (x)
(if (consp x)
(car x)
x))
specialized-lambda-list))
(defun types-of-variables (var-declarations)
(mapcar (lambda (var-declaration) (if (consp var-declaration) (second var-declaration) t)) var-declarations))
(defun type-decls-from-variables (var-declarations)
(mapcar (lambda (var-declaration)
(if (consp var-declaration)
`(declare (type ,(second var-declaration) ,(first var-declaration)))
`(declare (type t ,var-declaration))))
var-declarations))
最后，我们用argument-signature的方法记录下我们家的参数类型，这样
(argument-signature (defclassfamily F ((X Set) Y) ... ))
计算结果为 (Set t)。
一个参数类型族的依赖和通过以下代码实现：
(defclass DepSum (standard-class)
((family :initarg :family :reader family)
(arg-type :initarg :arg-type :reader arg-type)))
(defmethod make-instance :before ((sum-class DepSum) &key pr1 pr2)
(assert (and (typep pr1 (arg-type sum-class))
(typep pr2 (funcall (family sum-class) pr1)))))
(defmethod sb-mop:validate-superclass ((class DepSum) (super-class standard-class))
t)
(defun depsum (f)
(let ((arg-type (car (argument-signature f))))
(make-instance 'DepSum
:name (intern (format nil "DepSum_{x:~A} ~A(x)" arg-type f))
:direct-superclasses ()
:direct-slots `((:name pr1 :initargs (:pr1) :readers (pr1) :type ,arg-type)
(:name pr2 :initargs (:pr2) :readers (pr2)))
:direct-slots `((:name pr1 :initargs (:pr1) :readers (pr1)))
:family f
:arg-type arg-type)))
这样我们就可以使用
定义类型RealVectorSpace
(let ((rvs-type (depsum #'RealVectorSpaceOver)))
(deftype RealVectorSpace ()
rvs-type))
并写
(make-instance (depsum #'RealVectorSpaceOver) :pr1 X :pr2 some-rvs-over-X)
创建类型为 RealVectorSpace 的对象。上面的代码通过创建一个 meta-class（即 standard-class 的 subclass）DepSum 来工作，它代表所有依赖的类型总和，其实例是特定家庭的相关总和。通过 (defmethod make-instance :before ((sum-class DepSum ... 挂钩 (make-instance (depsum #'RealVectorSpaceOver) ...) 等调用来强制执行类型安全。不幸的是，我们似乎不得不依赖 assert 来进行这种类型检查（我无法弄清楚如何让它与 declare 一起工作）。
最后，代码 (defmethod sb-mop:validate-superclass ... 是 implementation-dependent（在这种情况下对于 SBCL）并且是为了能够实例化所必需的DepSum 的实例如 (depsum #'RealVectorSpaceOver).
为什么这只是部分答案？ 因为我没有将向量 space 公理作为 RealVectorSpaceOver 类型的一部分（或 RealVectorSpace).事实上，这样的事情需要给出 这些公理的实际证明 作为调用 (make-instance (RealVectorSpaceOver X) ... 的数据的一部分。这样的事情在像 Coq 这样的奇特语言中当然是可能的，但在 Common Lisp 那个古老而又可爱的混乱中似乎完全 out-of-reach。
我想编写一些处理反射群的通用代码，因此需要设置一些反映数学结构的类型（向量 space、仿射 space、...）。因为我真的很想在类型中忠实地反映这些结构，所以我需要一种方法来定义某种参数类型。
所以特别是，我希望能够编写以下代码
(defclass RealVectorSpace ()
((V :accessor underlying-set
:type Set)
(vector-add :accessor add
:type (function ((set-as-type V) (set-as-type V)) (set-as-type V)))
(scalar-mult :accessor s-mult
:type (function (real (set-as-type V)) (set-as-type V)))
它应该指定一个新类型 RealVectorSpace ，它将由一个三元组（V vector-add 标量）给出，其中 V 可以是任何东西，而 vector-add 是一个函数，它采用两个 V 类型（原文如此）的参数来评估类型 V.
当然，这种类型不会完全忠实地反映实向量的概念 space，因为向量加法和标量乘法仍需要满足一些其他属性。但即使将上面的 'dream' 变成真正的代码，我也无法理解。
编辑：针对sds的回答，让我对我原来的问题提出以下澄清：简而言之，我似乎需要 Lisp 中的依赖类型 ，这与仅要求参数 类 不同。事实上，Haskell 有参数类型但没有（至少它不是以明显的方式内置的）依赖类型。例如 Haskell 中缺少依赖类型 here.
1.谁能帮我把梦想变成代码？
2。我在某处听说由于 Lisp 宏，您在 Lisp 中不需要参数 类 。如果那是真的，有人能解释一下你如何在 Common Lisp 中使用 defmacro 来 implement/fake 参数化 类 吗？
我怀疑你想要的东西是否有意义， 但作为宏（滥用）使用的示例，您可以：
(defmacro define-real-vector-space (type &optional name)
`(defclass ,(or name (intern (format nil "REAL-VECTOR-SPACE-~A" type))) ()
((V :reader underlying-set :initform ',type)
(vector-add :accessor add
:type (function ((x ,type) (y ,type)) => ,type))
(scalar-mult :accessor s-mult
:type (function ((x real) (v ,type) => ,type))))))
;; sample underlying set:
(deftype 3d () (array real (3)))
;; use it:
(macroexpand-1 '(define-real-vector-space 3d))
==>
(DEFCLASS REAL-VECTOR-SPACE-3D NIL
((V :READER UNDERLYING-SET :INITFORM '|3D|)
(VECTOR-ADD :ACCESSOR ADD :TYPE (FUNCTION ((X |3D|) (Y |3D|)) => |3D|))
(SCALAR-MULT :ACCESSOR S-MULT :TYPE #'((X REAL) (V |3D|) => |3D|))))
(define-real-vector-space 3d)
回复评论：
如果你想要一个单身real-vector-spaceclass，你基本上是，
要求 vector-add 和 scalar-mult 插槽具有类型 which
取决于 V 插槽的值。
这意味着 (setf (underlying-set rvs) some-new-type) 会
必须检查 (add rvs) 和 (s-mult rvs) 必须适当
键入 some-new-type。
本质上，这意味着类型的每个对象
real-vector-space 是不可变的，所有的插槽都被修改
同时。
前一种选择可以通过明智的使用来实现
MOP。
我不确定后者在 Lisp 中是否可行。
您可以阅读 LIL，Lisp 接口库，在 LIL：CLOS 达到高阶, 流出身份 并从 Faré Rideau 那里获得了变革性的经验。 github page 有更多详细信息。
基本上，LIL 试图通过一个额外的参数（接口，它类似于一个类型 class）来表达参数多态性，这要归功于动态范围。
另一方面，使用 OCaml 模块很容易表达您想要表达的内容，因此根据您的需要，您最好遵循 Rainer Joswig 的建议（使用另一种语言）。
module type VectorSpace =
functor (S : sig val dimension : int end)
(F : sig type scalar val zero : scalar end) ->
sig
type vector = F.scalar array
val add : vector -> vector -> vector
val mul : F.scalar -> vector -> vector
end
至于属性（如评论中所要求），您可能需要使用更复杂的类型系统（Coq？）。 Common Lisp 如何很好地抽象事物的一个例子是 Gábor Melis's MGL-CUBE.
我们开始：部分 answer/solution 我的问题（为什么部分？见下文）。非常感谢 sds 帮我解决了这个问题！
首先让我澄清一下。当我最初提出问题时，我不准确地使用了术语 'parametric type'，只考虑了一个模糊的定义 'a type depending parameters'。我基本上想要一些小工具允许我编写以下 pseudo-code（在 pseudo-language 中）：
class List<T> {
//implementation
};
l = new List<string>;
l.push("Hello World!");
理解上面的内容 pseudo-code 很不错 straight-forward（参见 sds 的回答）。然而，如果开始怀疑表达式 List<T> 和 List 本身是否应该有意义，就会出现歧义。事实上，例如在 C++ 中，表达式将是未定义的，因为模板定义的效果
template <typename T>
class List {
public:
T car;
List<T> *cdr;
};
就好像是分别定义，每个类型T，一个类型List<T>。相反，在像 Java 这样实现了 泛型类型 的语言中，表达式 List<T> （其中 T 是一个自由变量）是有意义的并且表示类型，即 some 类型 T 上的列表的泛型类型，因此可以例如写一个像
T car(List<T> l) {
return l.car;
}
简而言之，在 C++ 中，我们只有所有类型的（无限）集合 List<T>，其中 T 遍历所有类型，而在 Java 中，这个集合本身作为一个语言中的对象，作为通用类型 List<T>.
现在是我提出的部分解决方案，在编写实际的 Lisp 代码之前，我将简要地用文字概括一下。该解决方案基于 type families 和此类 families 的 dependent sum，即我们将解释一个参数类型，例如 [=24] =] 作为一个参数的函数 List，其值是类型，我们将 Java-style 泛型类型 List<T> 伪造为 依赖总和类型 DepSum(List)，它仅由对 (a,b) 组成，其中 a 是某种类型，b 是 List(b).
回到在集合X上定义实数向量space的例子，我想写类似
(defclassfamily RealVectorSpaceOver (X) ()
((add :initarg :add
:reader add
:type (function (X X) X))
(s-mult :initarg :s-mult
:reader s-mult
:type (function (real X) X)))
为我定义一个函数 RealVectorSpaceOver，给定一个 class A，return 一个 class 就好像由
(defclass RealVectorSpaceOverA ()
((add :initarg :add
:reader add
:type (function (A A) A))
(s-mult :initarg :s-mult
:reader s-mult
:type (function (real A) A)))
基本上，我可以copy-n-paste这里解决sds问题，但是这有两个问题。首先，结果不会是 (side-effect-free) 函数，例如表单
(typep (make-instance (RealVectorSpaceOver A)
:add (lambda (x y) nil)
:s-mult (lambda (x y) nil))
(RealVectorSpaceOver A))
的计算结果为 nil，因为这里有两次调用 RealVectorSpaceOver，每次调用都会创建一个新的（因此不同的）class。因此，我们需要将此函数包装在一些代码中，以便在第一次调用时缓存结果。
另一个问题是，使用 defclass 以编程方式创建 classes 具有更改 class 名称 space 的效果，可能会重新定义现有的 class是的。为了避免这种情况，可以通过实例化元 class standard-class 来直接创建新的 classes。例如
(make-instance 'standard-class
:name (intern "B")
:direct-superclasses '(A)
:direct-slots '((x :initargs (:x) :readers (x))))
等同于
(defclass B (A)
((x :initarg :x :reader x)))
但不会重新定义任何 pre-existing class B。请注意，:direct-slots 参数的格式与用于定义插槽的 defclass 格式略有不同。使用将后者转换为前者的辅助函数canonicalize-direct-slot-defs（取自书'The Art of the Metaobject Protocol'），宏defclassfamily可以实现如下：
(defmacro defclassfamily (name variables superclasses slot-defs)
(let ((stripped-variables (strip-variables variables))
(variable-types (types-of-variables variables))
(type-decls (type-decls-from-variables variables)))
`(flet ((f ,stripped-variables
(make-instance 'standard-class
:name (intern (format nil "~S<~S>" ',name (list ,@stripped-variables)))
:direct-superclasses ,superclasses
:direct-slots ,(canonicalize-direct-slots slot-defs))))
(let ((g (cache-function #'f)))
(defun ,name ,stripped-variables
,@type-decls
(the standard-class (funcall g ,@stripped-variables)))
(defmethod argument-signature ((x (eql #',name)))
',variable-types)))))
上面的代码首先定义了一个代表所需类型族的函数 f，然后使用辅助函数 cache-function（插入您的自己的实现），然后使用 defun 在名称 space 中定义一个新函数，强制参数的类型（defclassfamily 接受类似于 defmethod 的类型化参数，因此(defclassfamily F ((X Set) Y) ... 将定义一个包含两个参数的家族 F，第一个参数是 Set) 类型，return 是 class 家族的值。此外，还有一些简单的辅助函数 strip-variables、types-of-variables 和 type-decls-from-variables 可以转换给定类型族变量（上例中的 (X Set) Y）的表达式。它们的定义如下：
(defun strip-variables (specialized-lambda-list)
(mapcar (lambda (x)
(if (consp x)
(car x)
x))
specialized-lambda-list))
(defun types-of-variables (var-declarations)
(mapcar (lambda (var-declaration) (if (consp var-declaration) (second var-declaration) t)) var-declarations))
(defun type-decls-from-variables (var-declarations)
(mapcar (lambda (var-declaration)
(if (consp var-declaration)
`(declare (type ,(second var-declaration) ,(first var-declaration)))
`(declare (type t ,var-declaration))))
var-declarations))
最后，我们用argument-signature的方法记录下我们家的参数类型，这样
(argument-signature (defclassfamily F ((X Set) Y) ... ))
计算结果为 (Set t)。
一个参数类型族的依赖和通过以下代码实现：
(defclass DepSum (standard-class)
((family :initarg :family :reader family)
(arg-type :initarg :arg-type :reader arg-type)))
(defmethod make-instance :before ((sum-class DepSum) &key pr1 pr2)
(assert (and (typep pr1 (arg-type sum-class))
(typep pr2 (funcall (family sum-class) pr1)))))
(defmethod sb-mop:validate-superclass ((class DepSum) (super-class standard-class))
t)
(defun depsum (f)
(let ((arg-type (car (argument-signature f))))
(make-instance 'DepSum
:name (intern (format nil "DepSum_{x:~A} ~A(x)" arg-type f))
:direct-superclasses ()
:direct-slots `((:name pr1 :initargs (:pr1) :readers (pr1) :type ,arg-type)
(:name pr2 :initargs (:pr2) :readers (pr2)))
:direct-slots `((:name pr1 :initargs (:pr1) :readers (pr1)))
:family f
:arg-type arg-type)))
这样我们就可以使用
定义类型RealVectorSpace
(let ((rvs-type (depsum #'RealVectorSpaceOver)))
(deftype RealVectorSpace ()
rvs-type))
并写
(make-instance (depsum #'RealVectorSpaceOver) :pr1 X :pr2 some-rvs-over-X)
创建类型为 RealVectorSpace 的对象。上面的代码通过创建一个 meta-class（即 standard-class 的 subclass）DepSum 来工作，它代表所有依赖的类型总和，其实例是特定家庭的相关总和。通过 (defmethod make-instance :before ((sum-class DepSum ... 挂钩 (make-instance (depsum #'RealVectorSpaceOver) ...) 等调用来强制执行类型安全。不幸的是，我们似乎不得不依赖 assert 来进行这种类型检查（我无法弄清楚如何让它与 declare 一起工作）。
最后，代码 (defmethod sb-mop:validate-superclass ... 是 implementation-dependent（在这种情况下对于 SBCL）并且是为了能够实例化所必需的DepSum 的实例如 (depsum #'RealVectorSpaceOver).
为什么这只是部分答案？ 因为我没有将向量 space 公理作为 RealVectorSpaceOver 类型的一部分（或 RealVectorSpace).事实上，这样的事情需要给出 这些公理的实际证明 作为调用 (make-instance (RealVectorSpaceOver X) ... 的数据的一部分。这样的事情在像 Coq 这样的奇特语言中当然是可能的，但在 Common Lisp 那个古老而又可爱的混乱中似乎完全 out-of-reach。