Question about example in A Beginner's Guide to Visual Prolog

Discussions related to Visual Prolog
Mike Wernicki
Posts: 10
Joined: 16 Jan 2012 5:54

Question about example in A Beginner's Guide to Visual Prolog

Unread post by Mike Wernicki » 30 Jun 2020 1:41

This is the command that calls the procedure add1:

Code: Select all

listmanager::add1([1,2,3,4], NewList),
please note the NewList variable is unbound.

The following add1 procedure adds 1 to each element of the input list [1,2,3,4]. It stores the information in the output list NewList.

Code: Select all

clauses     add1([], []). /* boundary condition */     add1([Head|Tail],[NewHead|NewTail]):- /* separate the head from the rest of the list */         NewHead = Head+1, /* add 1 to the first element */         add1(Tail, NewTail). /* call element with the rest of the list */
There is no explicit assignment of NewTail and NewHead to the output list.

I ran this code through the debugger. It works. The head of the input list is bound and 1 is added. The last step add1([],[]) the output list has all the elements +1 of the input list.

I don't see any assignment to NewTail. I don't see how NewHead is assigned in add1.

User avatar
Thomas Linder Puls
VIP Member
Posts: 1683
Joined: 28 Feb 2000 0:01

Re: Question about example in A Beginner's Guide to Visual Prolog

Unread post by Thomas Linder Puls » 30 Jun 2020 14:49

You don't actually ask any question, but I guess you wonder how the code works?
Or alternatively that you wonder why you can't follow the expected behavior in the debugger?

Conceptual behavior

The second parameter of add1 is an output parameter.

If I introduce a Result variable in the second clause, it may be easier to understand what goes on:

Code: Select all

    add1([Head | Tail], Result) :-         NewHead = Head + 1,         add1(Tail, NewTail),         Result = [NewHead | NewTail].
When calling this with [1, 2, 3, 4] as input, then:
  1. Head will be 1
  2. Tail will be [2,3,4]
  3. NewHead will be 2
  4. and when calling add1 NewTail will be/become [3,4,5] (i.e. the result of adding 1 to each of the elements in [2,3,4]).
  5. and then Result will be [2, 3, 4, 5]
Actual/optimized behavior

However code like this is tail call optimized and therefore the program has a somewhat different way of reaching the result.

An output parameter is actually a pointer to the place where the result should be put.

The following code is clearly not Prolog code, but it illustrates how things works:

Code: Select all

    add1([Head | Tail], ResultAddress) :-         NewHead = Head + 1,         ResultAddress = allocateListCell(),         ResultAddress.head <- NewHead,         NewTailAddress = addressOf(ResultAddress.tail),         add1(Tail, NewTailAddress).
The second argument of add1 is the address of where the result should be placed. The result is going to be a new list cell (line 3), and the head of that list cell is going to be NewHead (line 4), and the tail of this list cell should be the result of calling add1 on the Tail. So we obtain the address of the tail in the new cell and call add1 with that as second parameter (line 5 and 6).

The call to add1 in line 6 is performed with tail call optimization and due to that you will not actually see any returns. When your predicate eventually returns from clause 1 it will return directly to the place where add1 was originally called from.

It is for this reason you can't see "that many" things in the debugger.

See also Debugging tips: nothing
Regards Thomas Linder Puls
PDC

Mike Wernicki
Posts: 10
Joined: 16 Jan 2012 5:54

Re: Question about example in A Beginner's Guide to Visual Prolog

Unread post by Mike Wernicki » 30 Jun 2020 15:54

To some extent, it provides the information I needed.

The boundary condition:

add1([],[]).

Is another part of the question. I see how the first list ultimately resolved to the empty list. How does the output list resolve to the empty list? Unbound variable gets assigned the empty list []?

Is there some way I can in general structure the code to illustrate what is actually happening?

Martin Meyer
VIP Member
Posts: 309
Joined: 14 Nov 2002 0:01

Re: Question about example in A Beginner's Guide to Visual Prolog

Unread post by Martin Meyer » 30 Jun 2020 16:43

The conceptual behavior, which Thomas has explained in particular, is also described in the Language Reference in general. It often helps me to look up things there. The reference says that unification takes place in two different situations:
When a predicate is called the arguments from the call are unified with the terms in the head of each clause.
...
It also takes place when two terms are compared for equality.
Regards Martin

Martin Meyer
VIP Member
Posts: 309
Joined: 14 Nov 2002 0:01

Re: Question about example in A Beginner's Guide to Visual Prolog

Unread post by Martin Meyer » 30 Jun 2020 17:13

That means, variables can be bound solely through the head of a called clause, without having to use "=". Like for example in:

Code: Select all

class predicates     inverse : (integer, integer [out]). clauses     inverse(Num, -Num).   clauses     run() :-         inverse(3, X),         stdio::write("X = ", X).
Predicate inverse/2 contains no "=", its clause has no body at all. But the call binds X to -3.
Regards Martin

Martin Meyer
VIP Member
Posts: 309
Joined: 14 Nov 2002 0:01

Re: Question about example in A Beginner's Guide to Visual Prolog

Unread post by Martin Meyer » 30 Jun 2020 22:18

To track the computation you could (besides using the debugger) simply insert calls to write into the code which will produce a 'log'. To try that paste the below in file main.pro of a new console project:

Code: Select all

class listmanager   predicates     add1 : (integer*, integer* [out]).   end class listmanager   %---   implement listmanager   clauses     add1([], []) :-         stdIO::write("entered add1([], [])\n\n").       add1([Head | Tail], [NewHead | NewTail]) :-         stdIO::write("entered add1([Head | Tail], [NewHead | NewTail])\n with Head is ", Head, ", Tail is ", Tail,             ", and NewHead and NewTail to be computed\n"),         NewHead = Head + 1,         stdIO::write("unified NewHead and Head + 1  =>  NewHead is bound to ", NewHead, "\n"),         stdIO::write("call add1(Tail, NewTail) with Tail is ", Tail, " to compute NewTail...\n\n"),         add1(Tail, NewTail).   end implement listmanager   %===   implement main   clauses     run() :-         stdIO::write("call add1([1, 2, 3, 4], NewList) to compute NewList...\n\n"),         listmanager::add1([1, 2, 3, 4], NewList),         stdio::write("NewList = ", NewList).   end implement main   goal     console::runUtf8(main::run).
Running it produces the output:

Code: Select all

call add1([1, 2, 3, 4], NewList) to compute NewList...   entered add1([Head | Tail], [NewHead | NewTail])  with Head is 1, Tail is [2,3,4], and NewHead and NewTail to be computed unified NewHead and Head + 1  =>  NewHead is bound to 2 call add1(Tail, NewTail) with Tail is [2,3,4] to compute NewTail...   entered add1([Head | Tail], [NewHead | NewTail])  with Head is 2, Tail is [3,4], and NewHead and NewTail to be computed unified NewHead and Head + 1  =>  NewHead is bound to 3 call add1(Tail, NewTail) with Tail is [3,4] to compute NewTail...   entered add1([Head | Tail], [NewHead | NewTail])  with Head is 3, Tail is [4], and NewHead and NewTail to be computed unified NewHead and Head + 1  =>  NewHead is bound to 4 call add1(Tail, NewTail) with Tail is [4] to compute NewTail...   entered add1([Head | Tail], [NewHead | NewTail])  with Head is 4, Tail is [], and NewHead and NewTail to be computed unified NewHead and Head + 1  =>  NewHead is bound to 5 call add1(Tail, NewTail) with Tail is [] to compute NewTail...   entered add1([], [])   NewList = [2,3,4,5]
Regards Martin

Mike Wernicki
Posts: 10
Joined: 16 Jan 2012 5:54

Re: Question about example in A Beginner's Guide to Visual Prolog

Unread post by Mike Wernicki » 3 Jul 2020 18:27

The write statements in the reply are an admirable way of illustrating how the input list is processed in the tail recursive example. The debugger also shows how the input list is processed.

As described in one of the replies, the boundary condition (add1([], [].) rather than doing a comparison, as is the case of the input list, does an assignment. So it appears, the output list is assigned the empty list ([]) rather than acting as a comparison in the boundary condition.

Clearly, NewHead is given an assignment in the body of the main clause. What is not clear is how this assignment propagates to the output list. The only place this seems to be done is in the head of the main clause ( add1([Head | Tail], [NewHead | NewTail] ). The head of the main clause is also where NewTail appears.

What is not clear how to go from the assignment of the empty list in the boundary condition to the output list which is described in the head of the main clause. Perhaps I should spend more time examining the clearly not prolog code in one of the replies. I was a little uncomfortable not going outside the context of prolog to understand prolog.

The question remains the same how is the output list assigned values?

Martin Meyer
VIP Member
Posts: 309
Joined: 14 Nov 2002 0:01

Re: Question about example in A Beginner's Guide to Visual Prolog

Unread post by Martin Meyer » 4 Jul 2020 2:16

What you call "assignment" and "comparison" is in Visual Prolog (and any Prolog) accomplished by nothing else but the unification of terms. Formally speaking:

A variable can be, and can only be, bound by a unification of terms. A unification can succeed or fail.

Binding a variable to a value in a unification has the same effect as an assignment in most other programming languages. Evaluating whether a unification succeeds or fails has same effect as a comparison for equality in most other programming languages.

So, to your 1st question "NewHead is given an assignment ... how this assignment propagates to the output list": The output variable in the call to add1/2, i.e. the second argument, is unified with
[NewHead | NewTail] resp. in the final call with []. Both variables NewHead and NewTail are at this point (in the conceptual behavior) already bound to values: NewHead has been bound by the unification NewHead = Head + 1 and NewTail has been bound in the call add1(Tail, NewTail).

That also answers your 2nd question "how to go from the assignment of the empty list in the boundary condition to the output list": The output variable in the call to add1/2 is unified with [].


To make things easier to see, Thomas pulled unifications apart a bit by rewriting the second clause from

Code: Select all

    add1([Head | Tail], [NewHead | NewTail]) :-         NewHead = Head + 1,         add1(Tail, NewTail).
to

Code: Select all

    add1([Head | Tail], Result) :-         NewHead = Head + 1,         add1(Tail, NewTail),         Result = [NewHead | NewTail].
Likewise first clause could be rewritten from

Code: Select all

    add1([], []).
to

Code: Select all

    add1([], Result) :-         Result = [].
In the rewritten form Result is first unified with [NewHead | NewTail] in the second clause resp. with [] in the first clause. By the unification Result will be bound to a value (in conceptual behavior). Eventually the output variable in the call to add1/2 is unified with Result, i.e. with the value to which Result has been bound.
Regards Martin

Martin Meyer
VIP Member
Posts: 309
Joined: 14 Nov 2002 0:01

Re: Question about example in A Beginner's Guide to Visual Prolog

Unread post by Martin Meyer » 4 Jul 2020 10:31

The recursion is not the relevant point for your question "how do outputs propagate". When I remove the recursion from the example, the "propagation" becomes more obvious.

The situation of the outermost call then is:

Code: Select all

class predicates     add1 : (integer*, integer* [out]). clauses     add1([], []). % this clause head will not match       add1([Head | Tail], [NewHead | NewTail]) :-         NewHead = Head + 1,         NewTail = [3, 4, 5].   clauses     run() :-         add1([1, 2, 3, 4], NewList),         stdIO::write(NewList).
The output argument NewList will be unified with [NewHead | NewTail], i.e. it will be unified with [2, 3, 4, 5].

And the situation of the innermost call is:

Code: Select all

class predicates     add1 : (integer*, integer* [out]). clauses     add1([], []).       add1([Head | Tail], [NewHead | NewTail]) :- % this clause head will not match         <some clause body> % the clause body is irrelevant because the head will not match anyway   clauses     run() :-         Tail = [],         add1(Tail, NewTail),         stdIO::write(NewTail).
The output argument NewTail will be unified with [].
Regards Martin

Post Reply