agda 程序一定会终止吗?

2023-12-08

有几个地方指出所有 agda 程序都会终止。不过我可以构造一个这样的函数:

stall : ∀ n → ℕ
stall 0 = 0
stall x = stall x

语法荧光笔似乎不喜欢它,但没有编译错误。

计算范式stall 0结果是0。计算结果stall 1导致 Emacs 挂起,看起来很像一个非终止循环。

这是一个错误吗?或者 Agda 有时可以永远运行吗?还是有更微妙的事情发生?


事实上,存在编译错误。这agda可执行文件发现错误并将该信息传递给agda-mode在 Emacs 中,它会进行语法突出显示,让您知道存在错误。我们可以看看如果我们使用会发生什么agda直接地。这是我正在使用的文件:

module C1 where

open import Data.Nat

loop : ℕ → ℕ
loop 0 = 0
loop x = loop x

现在,我们调用agda -i../lib-0.7/src -i. C1.agda(不要介意-i参数,它们只是让可执行文件知道在哪里寻找标准库),我们得到错误:

Termination checking failed for the following functions:
  loop
Problematic calls:
  loop x
    (at D:\Agda\tc\C1.agda:7,10-14)

这确实是编译错误。此类错误使我们无法import从其他模块中获取此模块或编译它。例如,如果我们将这些行添加到上面的文件中:

open import IO

main = run (putStrLn "")

并使用编译模块C-c C-x C-c, agda-mode抱怨:

You can only compile modules without unsolved metavariables
or termination checking problems.

其他类型的编译错误包括类型检查问题:

module C2 where

open import Data.Bool
open import Data.Nat

type-error : ℕ → Bool
type-error n = n
__________________________

D:\Agda\tc\C2.agda:7,16-17
ℕ !=< Bool of type Set

when checking that the expression n has type Bool

阳性检查失败:

module C3 where

data Positivity : Set where
  bad : (Positivity → Positivity) → Positivity
__________________________

D:\Agda\tc\C3.agda:3,6-16
Positivity is not strictly positive, because it occurs to the left
of an arrow in the type of the constructor bad in the definition of
Positivity.

或未解决的元变量:

module C4 where

open import Data.Nat

meta : ∀ {a} → ℕ
meta = 0
__________________________

Unsolved metas at the following locations:
  D:\Agda\tc\C4.agda:5,11-12

现在,您正确地注意到有些错误是“死胡同”,而其他错误则让您继续编写程序。这是因为有些错误比其他错误更严重。例如,如果您得到未解决的元变量,很可能您只需填写缺失的信息即可,一切都会好起来的。

至于挂起编译器:检查或编译模块不应导致agda循环。让我们尝试强制类型检查器循环。我们将在模块中添加更多内容C1:

data _≡_ {a} {A : Set a} (x : A) : A → Set a where
  refl : x ≡ x

test : loop 1 ≡ 1
test = refl

现在,检查一下refl是该类型的正确表达,agda必须评估loop 1。然而,由于终止检查失败,agda不会展开loop(并最终陷入无限循环)。

然而,C-c C-n真正的力量agda尝试评估表达式(你基本上告诉它“我知道我在做什么”),所以很自然地你会进入无限循环。


顺便说一句,你可以使agda如果禁用终止检查,则循环:

{-# NO_TERMINATION_CHECK #-}
loop : ℕ → ℕ
loop 0 = 0
loop x = loop x

data _≡_ {a} {A : Set a} (x : A) : A → Set a where
  refl : x ≡ x

test : loop 1 ≡ 1
test = refl

最终结果是:

stack overflow

经验法则:如果你能做到agda通过检查(或编译)模块而不使用任何编译器编译指示来循环,那么这确实是一个错误,应该在错误跟踪器。话虽这么说,如果您愿意使用编译器编译指示,则有几种方法可以制作非终止程序。我们已经看到了{-# NO_TERMINATION_CHECK #-},这里还有一些其他方法:

{-# OPTIONS --no-positivity-check #-}
module Boom where

data Bad (A : Set) : Set where
  bad : (Bad A → A) → Bad A

unBad : {A : Set} → Bad A → Bad A → A
unBad (bad f) = f

fix : {A : Set} → (A → A) → A
fix f = (λ x → f (unBad x x)) (bad λ x → f (unBad x x))

loop : {A : Set} → A
loop = fix λ x → x

这个依赖于一种不严格为正的数据类型。或者我们可以强制agda接受Set : Set(也就是说,类型Set is Set本身)并重建罗素悖论:

{-# OPTIONS --type-in-type #-}
module Boom where

open import Data.Empty
open import Data.Product
open import Relation.Binary.PropositionalEquality

data M : Set where
  m : (I : Set) → (I → M) → M

_∈_ : M → M → Set
a ∈ m I f = Σ I λ i → a ≡ f i

_∉_ : M → M → Set
a ∉ b = (a ∈ b) → ⊥

-- Set of all sets that are not members of themselves.
R : M
R = m (Σ M λ a → a ∉ a) proj₁

-- If a set belongs to R, it does not contain itself.
lem₁ : ∀ {X} → X ∈ R → X ∉ X
lem₁ ((Y , Y∉Y) , refl) = Y∉Y

-- If a set does not contain itself, then it is in R.
lem₂ : ∀ {X} → X ∉ X → X ∈ R
lem₂ X∉X = (_ , X∉X) , refl

-- R does not contain itself.
lem₃ : R ∉ R
lem₃ R∈R = lem₁ R∈R R∈R

-- But R also contains itself - a paradox.
lem₄ : R ∈ R
lem₄ = lem₂ lem₃

loop : {A : Set} → A
loop = ⊥-elim (lem₃ lem₄)

(source)。我们还可以写出吉拉德悖论的一个变体,由 A.J.C. Hurkens 简化:

{-# OPTIONS --type-in-type #-}
module Boom where

⊥   = ∀ p → p
¬_  = λ A → A → ⊥
℘_  = λ A → A → Set
℘℘_ = λ A → ℘ ℘ A

U = (X : Set) → (℘℘ X → X) → ℘℘ X

τ : ℘℘ U → U
τ t = λ (X : Set) (f : ℘℘ X → X) (p : ℘ X) → t λ (x : U) → p (f (x X f))

σ : U → ℘℘ U
σ s = s U λ (t : ℘℘ U) → τ t

τσ : U → U
τσ x = τ (σ x)

Δ = λ (y : U) → ¬ (∀ (p : ℘ U) → σ y p → p (τσ y))
Ω = τ λ (p : ℘ U) → ∀ (x : U) → σ x p → p x

loop : (A : Set) → A
loop = (λ (₀ : ∀ (p : ℘ U) → (∀ (x : U) → σ x p → p x) → p Ω) →
  (₀ Δ λ (x : U) (₂ : σ x Δ) (₃ : ∀ (p : ℘ U) → σ x p → p (τσ x)) →
  (₃ Δ ₂ λ (p : ℘ U) → (₃ λ (y : U) → p (τσ y)))) λ (p : ℘ U) →
  ₀ λ (y : U) → p (τσ y)) λ (p : ℘ U) (₁ : ∀ (x : U) → σ x p → p x) →
  ₁ Ω λ (x : U) → ₁ (τσ x)

不过,这确实是一团糟。但它有一个很好的特性,即它只使用依赖函数。奇怪的是,它甚至没有通过类型检查并导致agda循环。分割整体loop术语一分为二有帮助。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

agda 程序一定会终止吗? 的相关文章

  • 如何使用Emacs运行方案?

    我跟着这个tutorial http jeffcjensen net scheme 并成功安装了Emacs STk Quack 问题是我怎样才能像在 Racket 中那样加载我的程序 在 Racket 中 我可以在上方窗口中编辑代码 输入一
  • SBCL初始化文件

    我想知道应该在哪里保存 sbclrc 文件 我尝试将其保存在我的 sbcl 文件夹中 但它似乎不起作用 我使用的是 Windows XP 和 Emacs 版本 23 我正在尝试设置 asdf install 这就是为什么我要修改初始化文件
  • Mac OS High Sierra 下无法打开 pty

    我的问题的本质是 用户程序如何在 Mac OS High Sierra 上打开 pty 例如 dev ptyp0 设备名称的标准 open 似乎不起作用 尽管它的保护是 crw rw rw 上下文是在 Mac OS 下运行 Emacs 在
  • Emacs 启动时出现 24 错误

    我已经使用 emacs snapshot 一段时间了 但最近它崩溃了很多 所以我切换到 Emacs 24 但是一旦我安装并启动它 它就开始显示错误并且不会在我的 init el 中加载任何内容 当我在调试模式下运行它时 我得到了这个 Deb
  • 在 emacs org-mode 中仅延迟加载前 N 行

    有没有办法告诉 org mode 仅加载长文本文件的前 N 行 我想保持整个文件打开以便能够搜索它 但在文件的前 N 行上显示组织模式 这是我编辑新内容的地方 如果您在组织模式下有结构化大纲 则可以使用以下命令设置全局文件可见性 START
  • ess-rdired:我收到此错误“现在没有 ESS 进程与此缓冲区关联”

    To use ess rdired为了浏览对象 我按照 ESS 手册并将以下内容添加到我的 emacs autoload ess rdired ess rdired View R objects in a dired like buffer
  • emacs 中用于 plink (putty) 的新 comint mod:符号的函数定义无效

    我想对 plink putty 使用新的 comint 模式 我将代码放在 init el 中 但是如果 M x run plink 我收到以下错误 let 符号的函数定义为 void comint check proc path defv
  • CSharpRepl emacs 集成?

    我碰巧知道莫诺CSharpRepl http www mono project com CsharpRepl 是否有 emacs csharp 模式使用它在一个窗口中运行 REPL 并像 python 模式一样在另一个窗口中编译 运行 C
  • Emacs 键绑定为“\C-'”

    如何将函数设置为 C 当我尝试这样做时 global set key C myfunct 它给了我 字符串中的修饰符无效 What is C 您希望在输入反斜杠 c 引号时发生一些事情吗 或者你的意思是C 控制 引号 如果是后者 我猜是 那
  • 我应该学习使用 Emacs 吗? [复制]

    这个问题在这里已经有答案了 我使用 IntelliJ IDEA 作为代码编辑器 所以这并不是要取代它 我用vi or vim用于在我们的服务器和标准上进行简单的文本编辑unix用于查找文件 获取目录列表等的命令 同事们对 emacs 赞不绝
  • cygwin bash 在 emacs shell 中无法正确显示

    我正在尝试使用 emacs 来运行 cygwin 我的环境是Windows 7 x64 emacs 24 0 93 1 cygwin 2 769 系统编码为gbk cygwin的编码系统默认为utf 8 emacs的编码系统默认为gbk I
  • 如何在 Emacs shell 缓冲区中获得对“✖”等的支持?

    我正在运行一个进程 如果出现错误 则输出字符 如 Unicode 中定义 但是 如果在 Emacs shell 缓冲区 GNU Emacs 的 Aquamacs 发行版 中运行该进程 我根本看不到错误 使用 braeburn aquamac
  • Emacs java 模式:malabar、jdee 还是 eclim?

    我想使用 emacs 进行 java 编码 但我对使用什么模式进行 java 编码感到困惑 有 jdee 看起来像 ide malabar 据说他比 jdee 更精通 java 1 5 结构 和 emacs eclim 它是 emacs 的
  • 如何在 Emacs 中保存所有文件(或保存所有缓冲区)?

    C x C s saves only the current buffer 如何保存所有文件 或所有缓冲区 Press C x s and then choose for saving all buffers
  • 使用 Emacs 进行 Web 开发? (php/mysql/javascript/css/html

    我是一名网络开发人员 在我决定学习真正的编辑器并开始使用 emacs 之前六个月 我一直在使用各种编辑器和 ide s 进行 Web 开发 php javascript html css 我学习了所有基础知识 使用了入门套件 练习使用缓冲区
  • Emacs 如何确定要撤消的工作单元

    When you enter the command C Emacs undoes some part of your recent changes to a buffer When you enter C again it undoes
  • 如何将 emacs helm-find-file 对目录的默认操作更改为进入目录而不是在 dired 中打开?

    我正在使用 emacs prelude 我最近决定从 ido 转到 helm 所以我启用了helm and helm everywhere在 emacs 前奏中 除了默认行为之外 一切都运行良好helm find file 在伊多 我可以打
  • Emacs JavaScript 缩进有问题

    我正在关注道格拉斯 克罗克福德 Douglas Crockford 的代码约定 http javascript crockford com code html 但我无法在 Emacs 中的 JS 模式下获得正确的缩进 我尝试自定义模式的缩进
  • 如何使Emacs C源目录永久化?

    我是 Emacs 新手 刚刚学习如何使用它 我知道如何设置 Emacs C Source dir 但我不知道如何使此更改永久生效 我想我必须在 emacs 文件中设置它 但我不知道它的命令是什么 有人可以帮忙吗 通常 大多数用户可设置的变量
  • Emacs,如何自动打开 LaTeX 文件的 Flyspell

    我仅使用 Emacs 进行 LaTeX 和 python 编程 有没有办法自动开启flyspell mode当我处理 tex 文件并打开flyspell prog mode当我处理 py 文件时 如何在 emacs 文件中执行此操作 将这些

随机推荐

  • 如何从循环内的函数中中断 Python while 循环

    while True input raw input enter input result useInput input def useInput input if input exit break return 0 quit etc i
  • 设置 PopoverContentSize 时出现问题

    我无法使用 size 650 400 设置 contentsize 但即使我创建具有相同宽度和高度的 popoverController 它也会被创建 不知道什么是担忧 点击 Enter 后显示如下 IBAction setButtonTa
  • THREE.GLTFLoader:未知扩展“KHR_materials_pbrSpecularGlossiness

    我们有一个导出 glb 文件的应用程序 当我尝试使用以下命令将它们加载到 Three js 中时GLTF加载器模型没有显示纹理 我收到此警告THREE GLTFLoader Unknown extension KHR materials p
  • 平滑不同幅度的噪声(第 2 部分)

    好吧 我继续这个问题而不回答 平滑不同幅度的随机噪声 我还有另一个问题 我选择使用形状的轮廓 阴影 翻译 转换 距离其中心有偏移 距离的点列表 该轮廓 阴影比当前路径大 我使用了这个存储库 https github com n yoda u
  • 如何创建未知类型的实例?

    我有几个需要精确参数类型的函数 又名T private
  • Oreo 更新后发生 INSTALL_FAILED_NO_MATCHING_ABIS 错误 [重复]

    这个问题在这里已经有答案了 我实际上正在开发 3 个 Android 应用程序 A B C 在我的所有设备上一切都正常 但是当我将 S7 Edge 更新到 Oreo 时 发生了一些奇怪的事情 2 个应用程序 A B 消失了 我的手机上只剩下
  • 如何获取 Android 设备的当前方向 (ActivityInfo.SCREEN_ORIENTATION_*)?

    我想了解设备的详细方向 最好是其中之一SCREEN ORIENTATION LANDSCAPE SCREEN ORIENTATION PORTRAIT SCREEN ORIENTATION REVERSE LANDSCAPE SCREEN
  • 软漆桶填充:颜色平等

    我正在制作一个小应用程序 孩子们可以用颜色填充预设插图 我已经使用洪水填充算法成功实现了 MS paint 风格的油漆桶 然而 靠近图像元素边缘的像素未填充 因为线条是抗锯齿的 这是因为当前是否填充的条件是colourAtCurrentPi
  • 在 tkinter 中的两个框架之间切换?

    我已经构建了我的前几个脚本 上面有一个漂亮的小 GUI 正如教程所示 但它们都没有解决如何处理更复杂的程序 如果您有一个带有 开始菜单 的东西 用于您的打开屏幕 并且根据用户选择 您移动到程序的不同部分并适当地重绘屏幕 那么执行此操作的优雅
  • AttributeError:“模块”对象没有属性“audio_fadein”

    我已经使用 cx freeze 将 python 项目构建到带有 exe 及其依赖项的单个文件夹中 但是当我运行 exe 时 出现错误 AttributeError module moviepy audio fx all has no at
  • 与 C 语言相比,C++ 有哪些限制? [关闭]

    Closed 这个问题是基于意见的 目前不接受答案 以下是C 的好处 C 提供了他们询问的具体功能 他们的 C 编译器几乎肯定是 C 编译器 因此不存在软件成本问题 C 与 C 一样可移植 C 代码可以与 C 一样高效 或者更高 或者更低
  • printf 的参数数量错误会导致奇怪的结果

    include
  • 如何在MySQL中生成数据?

    这是我的 SQL SELECT COUNT id CONCAT YEAR created at MONTH created at DAY created at FROM my table GROUP BY YEAR created at M
  • 如何使用 python 建立 ssh 连接?

    任何人都可以推荐一些在 python 中建立 ssh 连接的东西吗 我需要它与任何操作系统兼容 我已经尝试过 pyssh 只是为了得到 SIGCHLD 错误 我读过这是因为 Windows 缺少这个 我尝试过让 paramiko 工作 但
  • 如果没有活动事务,CreateQuery 无效

    我正在尝试使用 Spring Transactional 注释 但是当该方法时我遇到问题findAll被调用 我有这个错误 org hibernate HibernateException createQuery is not valid
  • C#使用命名空间语句排序

    我想我在某处读到 排序你的 using 语句并删除未使用的语句会带来某种性能优势 但我似乎找不到任何证据或资源来支持这一点 这有什么道理吗 No the using用于设置命名空间的语句没有性能成本 无论语句的顺序如何 生成的 IL 代码都
  • 查找距离 get.shortest.paths() 的路线距离

    我正在使用igraph在 R 中封装来做一些相当简单的事情 计算网络中两个节点之间的最短距离 有没有一种直接的方法来提取通过计算得出的路径的距离get shortest paths 这是一些可重现的代码 说明了我的问题 reproducib
  • Android 2.2 上的振动设置

    我正在制作一个振动切换小部件 事实上 它的第一个版本已经在市场上 但我在 Android 2 2 的振动设置方面遇到了一些问题 直到 Android 2 1 我都没有问题 当我想禁用振动时我会这样做 am setVibrateSetting
  • 如何获取当前 Subversion 内部版本号?

    如何在 Subversion 中自动导入最新的内部版本 修订号 目标是让该数字像 SO 一样在您的网页页脚上可见 让您的构建过程调用svn版本命令 并将其输出嵌入到生成的 source binaries 中 这不仅会给出当前修订版 就像这里
  • agda 程序一定会终止吗?

    有几个地方指出所有 agda 程序都会终止 不过我可以构造一个这样的函数 stall n stall 0 0 stall x stall x 语法荧光笔似乎不喜欢它 但没有编译错误 计算范式stall 0结果是0 计算结果stall 1导致