allbet登录网址:逻辑式编程语言极简实现(使用C#) - 3. 运行原理

admin 4个月前 (07-07) 科技 49 1

本系列前面的文章:

  • 逻辑式编程语言极简实现(使用C#) - 1. 逻辑式编程语言先容
  • 逻辑式编程语言极简实现(使用C#) - 2. 一道逻辑题:谁是凶手

第二天,好为人师的老明继续开讲他的私人课堂。

“今天讲NMiniKanren的运行原理。”老明敲了敲白板,最先涂画代码,“我们从一个喜闻乐见的例子最先。”

KRunner.PrintResult(KRunner.Run(null, (k, q) =>
{
    var x = k.Fresh();
    var y = k.Fresh();
    return k.All(
        k.Any(k.Eq(x, 1), k.Eq(x, 2)),
        k.Any(k.Eq(y, x), k.Eq(y, "b")),
        k.Eq(q, k.List(x, y)));
}));

“这题我会了!”小皮在例子下边写下谜底:

[(1 1), (1 b), (2 2), (2 b)]

看到小皮没把昨天的知识忘光,老明略感欣慰:“不错。你这个谜底是怎么算出来的呢?”

“呃……就是谁人……”小皮溘然卡壳了。这种问题就好比几何证实题,明显一眼就能看出来的两条垂直线,真下手证实却发现还挺不容易。小皮抓了几把头发,总算理出一缕思绪:“也许就是找出所有条件可能的组合……然后算一下解……”小皮一边说,一边在白板上写着:

  • x == 1
    • y == x => (x y) == (1 1)
    • y == "b" => (x y) == (1 "b")
  • x == 2
    • y == x => (x y) == (2 2)
    • y == "b" => (x y) == (2 "b")

“嗯,实在你已经知道怎么算出谜底来了。只是对于其中的细节还不甚明晰。我们接下来要做的事要理清晰这个盘算历程,获得一个每一步都可以由盘算机明确执行的算法。

“这个算法实在就是你所说这样,找出所有可能的条件组合。每组条件组合可以求出一个解,也可能自相矛盾从而无解。由于NMiniKanren中的条件都是相等条件,以是一组条件组合可以看作一个替换(Substitution)。一个替换能发生一个解,或者无解。

“因此,只需解决下面两个问题:

  1. 要在什么数据结构上根据什么顺序遍历替换
  2. 若何从替换中算出一个解,或者判断其无解。”

遍历分支

首先,我们要从代码组织出一个数据结构(实在就是一张图)。这个数据结构能够根据一定的顺序举行遍历,并依次天生替换。

例子中的代码使用到了EqAnyAll这三种组织目的的方式。下面划分探讨怎样从这三种方式组织出我们需要的数据结构来。

Eq

k.Eq(a, b)组织的目的是什么意思呢?”老明以一个看似通俗的问题开头。

“简朴,意思就是a要即是b这个条件。”

“孤立地看,是这样。然则考虑到上下文,更精确地说应该是,在上下文的基础上追加a即是b这个条件。”

小皮有点不解:“emm……多了‘追加’有什么差别呢?”

“从文字上看,多了‘追加’后,目的的注释从一种名词(一组条件)酿成了动词(追加条件)。这样一来,目的不仅表达了一组条件,同时也表达了这些条件若何跟上下文连系。就Eq的情形来说,这个连系方式是‘追加’。而AnyAll会有其他连系方式。”

“虽然还不是很明了,我想这个要等AnyAll的情形一起对比才气清晰起来。我还另外有个问题,上下文指的是什么?”

“狭义地说,上下文是注释器运行到这一条代码时,已执行的代码天生的替换。

上下文 <-> 一个替换 <-> 一组条件

“广义上看,上下文还应该包罗回溯分支等控制信息,不外现在我们先忽略这些。

“综合起来,根据对Eq目的的注释,我们可以用下图来示意这个目的。”

Any(或)

“接着看Any。根据上面的讨论,我们要怎么注释Any目的呢?”老明继续发问。

注释目的要说清晰两个方面:名词(什么条件)和动词(若何与上下文连系)。以一最先的例子中的k.Any(k.Eq(x, 1), k.Eq(x, 2))为例。名词方面自然就是x即是1和x即是2两个条件了,不外这两个条件是‘或’的关系。动词方面,应该是从上下文分岔出两个分支,一个分支追加x即是1这个条件,另一个分支追加x即是2这个条件。”

“很好。也就是说,和Eq差别,Any操作和上下文连系后,会天生多个替换。”老明赞许地址颔首,“它把参数的分支都放在一起,就像加法似的。用图示意的话,就像下面这样。”

All(与)

“最后是All……”

“这个我也会了!”小皮打断老明,“k.All(a, b)名词上示意条件a且条件b;动词上示意上下文先追加a,再追加b。”

“你说的太笼统了。ab可能都有多个分支,这种情形下怎么做?”老明接着问道。

小皮想了想一最先做的例子,答道:“这种情形要取所有组合,也就是a的分支和b的分支两两组合!最后分支数目即是a分支数目乘以b分支数目。”

“很好。若是Any类比加法,那么All类比的是乘法。下面这图形貌了开头例子中的All方式的连系历程。

这是个有向图,每条边示意一次追加条件的历程。每条从最先节点(上下文)到末端的路径,上面的节点组合起来就是一个替换。遍历所有路径,我们就遍历了所有替换。而遍历的顺序,就是注释器输出效果的顺序。

Anyi

接下来我们还可以来看看Anyi

通俗的Any使用的通俗的树结构遍历顺序:

Anyi以交替的顺序遍历分支:

Alli类似接纳交替的顺序遍历,这里就不再画了(主要是不好画,懒)。

再看目的(Goal)

上一篇主要从组织目的的角度出发,先容了差别方式组织出来的目的。为了实现NMiniKanren的注释器,我们需要加倍深入地领会在注释器的实现中,Goal是什么类型。

在前面的讨论中,我们知道,目的的寄义是对上下文/一个替换根据某种方式追加一些条件,返回零个、一个或多个替换——Eq返回一个;AnyAll可能返回多个;另外前面没讨论到的Fail会返回零个。

从这个形貌不难看出,最利便表述目的类型的是一个单参数函数,其参数是一个替换,返回值是替换的枚举,相当于C#中的Enumerable<替换>,也可以说是一个替换的流(Stream)。

Goal: (替换) -> Stream<替换>

Goal(替换)这个函数挪用的寄义是把Goal包罗的条件,追加到替换上,返回一系列(由于可能有分支,就会酿成多个)的替换。

“为什么不直接用List呢?”小皮又发问了。

“由于许多情形下,分支数目会许多,甚至是无限多,而我们只需要挨个取前面几个效果就够了。这种情形下使用List会极大降低注释器效率,甚至造成死循环。”

递归的情形

“略。”

“啥?”小皮瞪了下眼。

“懒得画,留着思索吧。”

替换求解

“天生替换后,剩下的就是求解了。

“替换求解的方式很简朴,就是应用一下小学时学过的代入消元法。来,看看这个怎么解。”老明一边说一边写下例题:

(1) y == x
(2) q == (x y)
(3) x == 1

毕竟是小学难度的问题,小皮看了一眼,马上就有领会法:“x即是1是确定的了,把(3)代入(1)后,y也即是1。把(1)和(3)都代入(2),获得q即是(1 1)。”

“解是求出来了,不外你以为你这个步骤有通用性吗?”老明虚着眼说,“盘算性能自觉地使用你这个蛇皮顺序吗?”

“呃……”小皮陷入沉思。判断代入顺序的规则似乎还挺贫苦的。或者简朴粗暴根据所有顺序都代入一遍?

“实在没想象中庞大,按顺序代入一遍,再反过来代入一遍,就OK了。”

按顺序代入

把(1)代入(2)(3):

(1) y == x
(2) q == (x x)
(3) x == 1

把(2)代入(3):

(1) y == x
(2) q == (x x)
(3) x == 1

在注释器实现中,条件是一条一条追加上来的。可以每次追加条件的时刻,将已有的条件代入新条件,这样就把这一步化解到天生替换的历程中了。

加入条件(1) y == x:

(1) y == x

加入条件(2) q == (x y):

(1) y == x
(2) q == (x x)

加入条件(3) x == 1:

(1) y == x
(2) q == (x x)
(3) x == 1

按相反顺序代入

把(3)代入(2)(1):

(1) y == 1
(2) q == (1 1)
(3) x == 1

把(2)代入(1):

(1) y == 1
(2) q == (1 1)
(3) x == 1

搞定!

这只是个简朴的例子。实际情形还可能会泛起无解、自由变量以及死循环等情形。这里就不多赘述了。

再议“非”运算

“现在能看出NMiniKanren为什么不支持‘非’运算了吗?”

小皮认真想了一会,说:“岂止不支持‘非’,‘大于’和‘小于’这些也不行吧。根据代入消元法,NMiniKanren只支持相等条件。”。

“那若是要支持这些运算应该怎么做呢?”

“要拓展条件的类型。除了相等条件,还要有不相等条件等。响应的求解算法也要有所转变。”

“没错。改动虽然不大,然则代码看起来会混乱得多。以是以教学为目的的话,就不支持这些了。”

小结

不知不觉时间已到了喜闻乐见的午餐时间,于是老明总结道:“虽然还没有落地成代码,但运行原理算是弄清晰了。要害点就两个:

  1. 要在什么数据结构上根据什么顺序遍历替换。
  2. 若何从替换中算出一个解,或者判断其无解。

“第一点,我们从代码组织了一张图。该图的每条路径对应一个替换,遍历路径的顺序就是遍历替换的顺序。同时也明确了目的Goal的类型。

“第二点,我们使用代入消元法,往返两遍代入解出了所有未知量。”

“接下来可以写代码实现NMiniKanren注释器了吧。”理解了原理后,小皮的十条手指已经饥渴难耐,蚯蚓似的扭动着。

“不着急,下昼还要先讲一个编程小技巧,然后就可以开搞了。”

,

欧博官网手机

欢迎进入欧博官网手机(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

皇冠体育声明:该文看法仅代表作者自己,与本平台无关。转载请注明:allbet登录网址:逻辑式编程语言极简实现(使用C#) - 3. 运行原理

网友评论

  • (*)

最新评论

  • 环球UG充值 2020-07-07 01:26:46 回复

    常州新闻网常州新闻网是隶属于常州市人民政府的权威性新闻网站,内容包括走进常州、新闻中心、政务公开、政民互动等多类有深度、有质量的地方新闻栏目,另外还开设栏目导航,分类不同领域和形式的信息内容,为常州市人民提供最新一手可靠新闻。这里有最权威的发布和解度政策和形势动向专家,深度解读、清晰梳理新闻脉络,确保每一条消息动态都真实可靠,是常州人自己的新闻网站。先码,再看

    1

文章归档

站点信息

  • 文章总数:675
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1245
  • 评论总数:251
  • 浏览总数:6693