Prolog递归过程的说明

本文介绍了Prolog递归过程的说明的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如果可能的话，我希望有人解释一下此过程(摘自《立即学习入门》一书).它需要两个数字并将它们加在一起.

I'd like someone to explain this procedure if possible (from the book 'learn prolog now'). It takes two numerals and adds them together.

add(0,Y,Y). add(s(X),Y,s(Z)) :- add(X,Y,Z).

原则上我理解，但是我有一些问题.可以说我发出查询

In principle I understand, but I have a few issues. Lets say I issue the query

?- add(s(s(0)), s(0), R).

这将导致:

R = s(s(s(0))).

步骤1是与规则2的匹配.现在X变成s(0)，Y仍然是s(0).但是Z(根据书)变成s(_G648)或内部带有未实例化变量的s().为什么是这样?

Step 1 is the match with rule 2. Now X becomes s(0) and Y is still s(0). However Z (according to the book) becomes s(_G648), or s() with an uninstantiated variable inside it. Why is this?

在最后一步，第一个规则被匹配，从而结束了递归.在这里，Y的内容以某种方式最终到达Z的未实例化部分！非常令人困惑，我需要一个简单的英语解释.

On the final step the 1st rule is matched which ends the recursion. Here the contents of Y somehow end up in the uninstantiated part of what was Z! Very confusing, I need a plain english explanation.

推荐答案

第一个前提:

• 我们将s(X)定义为X的后继者，因此基本上s(X)= X + 1
• 跟踪中使用的_G ###表示法是用于递归的内部变量

• We have s(X) defined as the successor of X so basically s(X) = X+1
• The _G### notation is used in the trace for internal variables used for the recursion

让我们首先看一下我发现更直观的继任者的加法的另一种定义:

Let's first look at another definition of addition with successors that I find more intuitive:

add(0,Y,Y). add(s(A),B,C) :- add(A,s(B),C).

这基本上是相同的，但是递归更容易看:

this does basically the same but the recursion is easier to see:

我们问

add(s(s(0)),s(0),R).

现在，第一步的序言中说那等于

Now in the first step prolog says thats equivalent to

add(s(0),s(s(0)),R)

因为我们有add(s(A),B,C) :- add(A,s(B),C)，如果我们看问题A = s(0)和B = s(0).但这仍然没有终止，因此我们必须重新应用A = 0和B = s(s(s(0)))的等价关系，

because we have add(s(A),B,C) :- add(A,s(B),C) and if we look at the question A = s(0) and B=s(0). But this still doesn't terminate so we have to reapply that equivalency with A=0 and B=s(s(0)) so it becomes

add(0,s(s(s(0))),R)

其中，给定add(0,Y,Y).表示

R = s(s(s(0)))

您对add的定义基本上相同，但是有两个递归:

Your definition of add basically does the same but with two recursions:

首先，它将第一个参数减小为0，因此将其减小为add(0，Y，Y):

First it runs the first argument down to 0 so it comes down to add(0,Y,Y):

add(s(s(0)),s(0),R)

其中X = s(0)，Y = s(0)，并且s(Z)= R和Z = _G001

with X=s(0), Y = s(0) and s(Z) = R and Z = _G001

add(s(0),s(0),_G001)

其中X = 0，Y = s(0)和s(s(Z))= s(G_001)= R且Z = _G002

with X = 0, Y=s(0) and s(s(Z)) = s(G_001) = R and Z = _G002

add(0,s(0),_G002)

因此，现在它从定义add(0，Y，Y)知道_G002是s(0)，但必须追溯其步骤，因此_G001是s(_G002)，R是s(_G001)是s(s (_G002))是s(s(s(0))).

So now it knows that _G002 is s(0) from the definition add(0,Y,Y) but has to trace its steps back so _G001 is s(_G002) and R is s(_G001) is s(s(_G002)) is s(s(s(0))).

因此，要想达到定义add(0，Y，Y)的序言，就必须为第一次递归引入内部变量，然后从第二次递归中对R求值.

So the point is in order to get to the definition add(0,Y,Y) prolog has to introduce internal variables for a first recursion from which R is then evaluated in a second one.