Prolog递归过程的说明 [英] Explanation of Prolog recursive procedure

问题描述

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

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.

这篇关于Prolog递归过程的说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！