Assignment for university

Help! Predicate
1

Dear swi prolog community,

i have an assignment for my university class in prolog. If you can help me in anyway, i would appreciate it.

First of all the task.
We have to write a ‘function’ which sums up the flight time of route numbers. the route numbers are given in a list. If the destination of an route differs from the startpoint of the following route, we need to add 3 hours to the flight time because the aircraft needs to remove itself to the new startpoint.

For example: if we have the list [1,2], it means we have an aircraft flying from FRA to LHR and after this from FCO to FRA. So the total flight time would be 210 minutes ( it is okay to output it as minutes ), but we have to add another 3 hours to it, because the landingpoint LHR differs from the following startpoint FCO. So in total we would have 390 minutes.

If anyone knows how to do it or can help me in anyway, I would really appreciate it.

This is the data we have

image
image628×686 76 KB

Currently i am thinking about something like

sumlist([],0).
sumlist([H|T],Sum):-
sumlist(T,SumRest), Sum is H + SumRest.

but i don’t know how to solve the problem if the startpoint and landing point are different.

Many thanks

2

I think the beauty of logic programming is that it allows you to describe the problem in a logical way and then translate that essentially, one to one, into a program.

Here is an example:

Suppose you have a list of 5 numbers and you want to know if there exists a number that is greater than N. In logic you would write:

There exists X such that X is greater than N.

This translates to Prolog as so:

a_number(1).
a_number(2).
a_number(3).
a_number(4).
a_number(5).


exists_greater_than_n(X, N) :-
       a_number(X),                               % there exists a number X
      X >N.                                              % where X is greater than N

Prolog will do the search for you across the numbers, until it finds one where X > N, or it would fail, telling you that there isn’t such a number.

Prolog does this by looking up a_number(X), finding the first, and binding X with 1, and testing if X>N, and if not backtrack to lookup the next number, setting X=2 and so forth.

The combination of the predicate a_number(X), and the condition X>N, in the body of exists_greater_than(X), is essentially causing Prolog to executing a"lookup" loop, until the condition X>N succeeds, or no more number exists to lookup, and then it fails to find such a number – hence such an X does not exist.

hope this helps,

Dan

3

Dear dan,

is there anyway i can contact you via discord or pm?

4

Hi,

Lets try to explore this here a bit.

Consider a simplified version, of the table, just to get the core logic worked out.

Suppose you have a simplified route table such as below – that shows the minutes of the flight, so no need to translate time, just to add minutes. Also, no need to for this problem to include the type or aircraft.

The simplified table would be something like this:

route(1, fra, lhr, 110).
route(2, fco, fra, 100).
route(3, fra, atl, 710).
route(4, atl, fra, 390).

Now, I am wondering, how would you describe a breakdown of the problem to someone else – suppose you break down the problem into smaller steps – pin down the different sub-problem cases you would be identifying and dealing with, if you were to do this on paper with pencil.

If you want write it down here in English, first, not in Prolog.

Let me mention that in my opinion this isn’t a simple introductory problem because, at least the solution approach i am thinking about, uses three Prolog idioms one learns from experience (at least in my case) and that help think about the encoding of the problem into Prolog solution description

  1. auxiliary predicate – where you create another helper predicate to solve the main predicate – typically, the helper predicate has one or more additional arguments – that help in solving the problem
  2. context arguments, where you use an (additional) argument in the (auxiliary) predicate to pass information from one recursive loop to the next
  3. case analysis: where you add predicate clauses (i.e. duplicate a predicate, and give it a different condition in the body) based on different cases you deal with

And, there is the more common idiom to add a clause with an empty list, to conclude a recursion – which you have in your sample code as well.

Dan

1 Like
5

Hello,

this is the first solution i came up with:

route(1,‘FRA’,‘LHR’,15:10,18:30,‘DE-AAB’).
route(2,‘LHR’,‘FRA’,20:45,13:50,‘DE-AAB’).
route(3,‘FRA’,‘ATL’,05:50,17:00,‘DE-AAA’).
route(4,‘TXL’,‘FRA’,21:30,23:50,‘DE-AAA’).

flighttime(1,200).
flighttime(2,1025).
flighttime(3,770).
flighttime(4,140).
flighttime(0,0).

totalduration([Head|Tail],R):- (totalduration(Tail,T),flighttime(Head,M), R is M+T)

The breakdown of the problem would be something like

  1. step is to sum up the times of the different routes
  2. step is to add the total of 3 hours if the airports are different.

For the 2nd step I was thinking about adding more clauses like all the possibilites with different airports to make a test if I have to add the 3 hours or just the flight duration.

differentairports(1,2). the numbers are the nr / id of the routes
differentairports(1,3).
differentairports(1,4).
differentairports(1,1).
differentairports(2,2).
differentairports(2,4).
differentairports(3,1).
differentairports(3,2).
differentairports(3,3).
differentairports(4,2).
differentairports(4,4).

So I could do something like

totalduration([Head|Tail],R):- (totalduration(Tail,T),flighttime(Head,M), R is M+T)
and if i have differentairports(H,???) i would have to add another +180.
The problem I am facing here is that I don’ get the 2nd argument for differentairports.
I tried something with
([Head,Head2|Tail],Sum):- append([Head2],Tail,L)
to get the 2nd element of the list, so I can fulfill differentairports, but it didn’t work. I although thought I would have to append the 2nd element again before the recursion occurs

Right now I am thinking about " IF A then B else C"
so it should be
IF the airports are different then do the recursiv call and do R is M+T+180
else
do R is M+T

Skonnky

6

I think you can take more advantage of Prolog to calculate things for you, rather than try to work things out “manually” in additional data tables.

While this is a good breakdown in principle, on paper you would probably do it a bit differently, if you are given the route [1,2] as a starting point.

You would probably first look up route 1, and you also know that its the beginning of the route, And start tallying the route time.

Then you would look up the second leg: 2, and here you would look back on what the previous destination was, because you want to compare it with the departure, to know if its the same or not, and so on.

Can you try to work / write this out further

Dan

7

My idea would be to store the previous routeNr in a variable, but I think it wouldn’t work for many examples because once a variable is instantiated, it is not possible to override it.

Do you mean that I should sum up the flighttime in the “first loop” and then do another loop where I count the different destination and departures?

I am not sure what you mean by look back. I thought “looking back” is not possible in ProLog.

Skonnky

8

No, i mean that you build up the sum one step at a time, but can use an auxiliary predicate to help you with it.

You can look back if you prepare for it – i.e. if you pass forward to a predicate, the value you want the next predicate to look back at.

The Prolog programming idiom here is called context parameter. Here is a classic example:

Suppose you want to multiply a list of elements by N, you could do it as follows:

multiply([], _, []).
multiply([X|Xs], N, [Y|Ys]) :-
  Y is X * N,
  multiply(Xs, N, Ys).

Here you are passing N along each recursive step. If you were to code this in a procedural language like C, then N would be a local variable that is accessed each time one loops to the next value in an array.

In a similar way, you can pass forward the previous destination, so the next predicate called can look “back” at it.

Dan

10

Just to clarify – accumulators are context arguments that tally things, hence, the name accumulator. Whereas context arguments when the term is used in general can simply pass along values.

Edit: I am using O’Kefee’s terminology here.

12

Thank you for clarifying – i will look it up in O’Keefe’s Crafts book to review again what i saw there.

14

O’Keefe calls section 1.4. Context Arguments and then adds a subsection 1.4.1. Accumulator Passing.

I guess, that’s why i thought that accumulator passing is an example of context argument.

18

Nice – reminds me of the multiply example, where the [Y|Ys] list is built up over the recursion – similarly here a new A2 is created by each recursive call. – i guess, if you want to get the result back to the caller, you’ll have to have a context parameter to do that for you.

19

The terminology is not important for someone learning this. The important thing is that there’s a parameter that explicitly carries “state” through the recursion; for a conventional imperative language, the state is implicit and often not mentioned when iteration is taught.
(Whether the state changes or not is a detail: and there are other kinds of state than “context” or “accumulator”.)

20

That’s what I liked about the O’Keefe first chapter, is all about naming things

“Its easier to think about something, if you have a name for it. The point of this chapter is to give names for some common ways that arguments in Predicates are used in Prolog …” (p7)

23

Yes, rereading it, clearly that is what O’Keefe writes – thanks for clarifying.

Interestingly, it seems that accumulator passing isn’t necessarily to accumulate – but, can also just be to pass stage change of a variable around.

How would you call for example, a key-value structure that gets updated through variable pairs. For an assoc structure this includes adding a key value, replacing the value of a key, and removing a key.

Dan

25

@skonnky

So, if you make a next step in breaking down the problem into sub-problems, while tracing what you do in your mind or on paper, while following the path [1,2], you might notice that the overall route “hop” case decomposes into two broad cases.

  1. a first route hop, which doesn’t have a prior arrival – since its at the beginning – and its distance is the distance of the first identified hop.

and (plus)

  1. a “rest” route hop, which does have a prior arrival – since its an intermediate route step – and its distance depends whether the prior destination and the current departure are equal or not.

Then, you can further break down 2) into two cases:

2.1 a “rest” route hop, which has a prior arrival that equals the current departure.
2.2.a “rest” route hop, which has a prior arrival that does not equal the current departure.

The above gives your descriptions of sub-problems that help you describe the overall solution in terms of the component solutions (predicates).

Dan

26

I need to say that it took me probably 2 years to understand the word Monad – and, why, DCG are essentially Monads.

I think Monad is a term coming from the theory underpinning functions or, perhaps, functional programming.

I think, it would be good to have a generalized term that comes from logic and relations and fits with terminology in logic programming, such as context arguments, accumulator arguments, and perhaps … state threading arguments, or state passing arguments, or successive state argument pairs, or state change argument pairs.

Dan

Dan

27

I guess overwrite within the current choicepoint frame, i.e. it can still backtrack and unwind that over-write

28

So in order to get my task done I should write the steps 1, 2.1 and 2.2 in prolog using accumulators or am I missing something?

29

Yes, give it a try – you can use an accumulator argument to tally the time, and use a context argument to pass along an arrival to the next recursive loop, where the arrival is then compared with the departure to see if its the same or not – and whether the tally needs to add 180 minutes.

the transition from 1 to 2 would be to identify the first arrival in 1, and pass it to (2) where its being checked as cases for 2.1 and 2.2, as a previous_arrival (i.e. a context variable).