Coq 中的部分函数/未定义?

Partial function in Coq / underdefined?

我一直在尝试在 Agda 中编写和验证编译器,使用 Concrete Semantics(这是为 Coq Isabelle/HOL 编写的)作为参考点.我正在为该文本中使用的相同语言定义编译。

上下文我已经完成了编译器的编写,现在处于验证阶段,但是我必须在机器指令执行的定义中对具体语义做出重大改变。这种差异在 Agda 中似乎是必要的,但现在却使验证阶段异常复杂。

在尝试执行具体语义中给出的更简单版本的指令执行时,我遇到了这一行,这可以解释为什么我无法直接将其翻译成 Agda:

Also useful are the head of a list, its first element, and the tail, the rest of the list:

fun hd :: 'a list ⇒ 'a
hd (x # xs) = x

Note that since HOL is a logic of total functions, hd [] is defined, but we do not know what the result is. That is, hd [] is not undefined but underdefined.

hd []未定义是什么意思?这相当于在 Agda 中有一个不完整的模式吗?

汇编指令执行功能严重依赖hd。在我在 Agda 中实现它时,我为多种类型提供了索引,以允许我构建堆栈始终具有最少元素数量的证明,以避免不完整的模式匹配问题。现在我正在尝试验证编译器,证明比具体语义中的证明复杂得多,因为我必须使用这些索引。

我是不是遗漏了什么,或者具体语义学中的证明不完整,hd [] 没有被定义?

hd []在Isabelle/HOL中定义;它有一个值,但你对那个值一无所知。可以证明 hd [] = hd [] 因为 x = x 对所有 x 都成立,但是你将无法证明 hd [].

上的任何其他内容(非平凡的)

Am I missing something or are the proofs in Concrete Semantics incomplete with hd [] not being defined?

它们并非不完整。依赖于 hd 行为的证明很可能假设调用 hd 的列表是非空的,或者根据其他假设证明它是非空的。