我正在研究一个高阶定理证明器,其中统一似乎是最困难的子问题.
如果Huet的算法仍然被认为是最先进的,那么是否有任何人有任何与其解释的链接,这些解释是由程序员而不是数学家所理解的？
或者甚至是它的工作原理和通常的一阶算法的例子都没有？
在ISO Prolog中,仅针对NSTO(不受发生检查)的情况定义统一.背后的想法是涵盖那些主要用于程序并且实际上得到所有Prolog系统支持的统一案例.更具体地说,ISO/IEC 13211-1:1995读取:
7.3.3发生检查(STO)但不受
发生检查(NSTO)
如果存在通过
Herbrand算法的步骤以便
发生7.3.2g 的方式,则一组方程(或两个项)是"经历发生 - 检查"(STO).
如果没有办法继续
Herbrand算法的步骤使得7.3.2g发生,则一组方程(或两个项)"不受发生检查"(NSTO)
....
此步骤7.3.2 g读取:
克)如果存在形式的公式X =吨这样
即X是一个变量,吨是非可变术语
包含该变量,然后用失败(退出不
unifiable,正发生检查).
完整的算法被称为Herbrand算法,并且通常被称为Martelli-Montanari统一算法 - 其基本上通过以非确定性方式重写方程组来进行.
请注意,引入了新的方程式:
d)如果存在形式为f(a 1,a 2,... a N)=
f(b 1,b 2,... b N)的等式,则将其替换为等式集
a i = b 我.
这意味着具有相同算符但具有不同arity的两个复合词将永远不会对STO-ness做出贡献.
这种非确定性使得STO测试难以实现.毕竟,仅仅测试是否需要发生检查是不够的,但为了证明对于执行算法的所有可能方式,这种情况永远不会发生.
这是一个案例来说明情况:
?- A/B+C*D = 1/2+3*4.
统一可以从A = 1,也可以是任何其他对开始,并以任何顺序继续.为了确保NSTO属性,必须确保没有可能产生STO情况的路径.考虑一个对当前实现没有问题的情况,但仍然是STO:
?- 1+A = …我正在为一种新的函数式编程语言实现一种类型的系统,我目前正在编写这两种函数来统一它.有两种情况考虑:
+---------+---------+-------------------------------------------------------+
| k1 | k2 | action |
+=========+=========+=======================================================+
| var | var | k1 := k2 ^ k2 := k1 |
+---------+---------+-------------------------------------------------------+
| var | non var | if (!occurs(k1, k2)) k1 := k2 |
+---------+---------+-------------------------------------------------------+
| non var | var | if (!occurs(k2, k1)) k2 := k1 |
+---------+---------+-------------------------------------------------------+
| non var | non var | ensure same name and arity, and unify respective args |
+---------+---------+-------------------------------------------------------+
k1和k2变数然后他们被实例化给对方.k1一个变量时,它被实例化为k2iff …ocaml haskell functional-programming type-inference unification
我以为我理解Scala和Haskell中的模式匹配与Prolog中的统一不同,但我对Prolog的误解很大.一个无法通过另一个解决的简单问题是什么？谢谢
任何人都可以告诉我如何访问prolog列表中的特定成员？比方说,我需要访问传递给规则的列表的第3或第4个元素？
我正在通过我的AI教科书工作,我已经完成了我的部分的最后一个作业问题:
"以您选择的任何语言实施第69页概述的统一算法."
在页69,您有统一算法的以下伪代码:
function unify(E1, E2);
begin
case
both E1 and E2 are constants or the empty list:
if E1 = E2 then return {}
else return FAIL;
E1 is a variable:
if E1 occurs in E2 then return FAIL
else return {E2/E1}
E2 is a variable
if E2 occurs in E1 then FAIL
else return {E1/E2}
either E1 or E2 are empty then return FAIL
otherwise:
begin
HE1 := first element of E1;
HE2 := first element of E2; …我发现自己一直想通过一个Func在地方的一个回报,没有输入Action,例如
Func<int> DoSomething = ...;
Task.Run(DoSomething);
在哪里,我真的不在乎的回报价值DoSomething.
但是,这些类型并不统一,我最终包装了这个调用
Task.Run(() => { DoSomething(); });
有没有办法让这些类型统一而不包装？另外,有没有很好的设计理由为什么他们不统一？
我试图在这里理解SICP中描述的统一算法
特别是,在"尽可能扩展"的过程中,有一个检查(标有星号"*"的第一个地方),它检查右手"表达式"是否是已经绑定到某个东西的变量.当前帧:
(define (extend-if-possible var val frame)
(let ((binding (binding-in-frame var frame)))
(cond (binding
(unify-match
(binding-value binding) val frame))
((var? val) ; *** why do we need this?
(let ((binding (binding-in-frame val frame)))
(if binding
(unify-match
var (binding-value binding) frame)
(extend var val frame))))
((depends-on? val var frame)
'failed)
(else (extend var val frame)))))
相关评论指出:
"在第一种情况下,如果我们尝试匹配的变量没有绑定,但我们试图匹配它的值本身就是一个(不同的)变量,有必要检查该值是否绑定,并且如果是的话,要匹配它的价值.如果比赛的双方都没有约束,我们可能会绑定到另一方."
但是,我想不出这实际上是必要的情况.
我认为,它正在谈论的是你目前可能有以下框架绑定的地方:
{?y = 4}
然后要求"extendIfPossible"绑定从？z到？y.
当出现"*"检查时,当被要求用"？y"扩展"？z"时,我们看到"？y"已经绑定到4,然后递归地尝试将"？z"与"4"统一,这导致我们用"？z = 4"扩展框架.
没有检查,我们最终只用"？z =？y"扩展框架.但在这两种情况下,只要？z还没有被其他东西绑定,我就没有看到问题.
请注意,如果- Z 就已经被绑定到别的东西,然后代码没有达到部分标有"*"(我们早就递归到什么？ž统一已经匹配).
经过深思熟虑之后,我意识到可能存在某种形式的争论,即生成一个"最简单"的MGU(Most General Unifier).例如,您可能希望MGU具有引用其他变量的最少数量的变量...也就是说,我们宁愿生成替换{？x = 4,？y …
给出了Haskell函数:
head . filter fst
现在的问题是如何手动"手动"找到类型.如果我让Haskell告诉我我得到的类型:
head . filter fst :: [(Bool, b)] -> (Bool, b)
但是我想了解它是如何工作的,只使用已定义如下的已使用函数的签名:
head :: [a] -> a
(.) :: (b -> c) -> (a -> b) -> a -> c
filter :: (a -> Bool) -> [a] -> [a]
fst :: (a, b) -> a
编辑:这么多很好的解释......选择最好的一个并不容易!
我正在实施Hindley-Milner类型推理算法,遵循Mark Jones和Oleg Kiselyov的教程.这两个都有一个"应用绑定"操作,其大致类型的形式
applyBindings :: TyEnv -> Type -> Type
它将tyvar -> ty绑定应用于TyEnv给定的Type.我发现在我的代码中忘记调用是一个常见的错误,我applyBindings从Haskell的类型系统中得不到任何帮助,因为ty它的类型相同applyBindings tyenv ty.我正在寻找一种方法来在类型系统中强制执行以下不变量:
在进行类型推断时,必须在返回"最终"结果之前应用绑定
在对单形对象语言进行类型推断时,有一种自然的方法可以强制执行此操作,正如在thornton的unification-fd包中实现的那样:我们为Types 定义了两种数据类型:
-- | Types not containing unification variables
type Type = ... -- (Fix TypeF) in wren's package
-- | Types possibly containing unification variables
type MutType = ... -- (MutTerm IntVar TypeF) in wren's package
并给出applyBindings类型
-- | Apply all …