prolog help, search, noob question

7a4c677bc0c2c8a770c5cc4689f73296
0
asgard103 101 Mar 31, 2009 at 12:06

hey there i have a some data about the london underground that i have wrote in prolog its a little like this;

link(paddington, bayswater, circle).
link(bayswater, notting_hill_gate, circle).
link(notting_hill_gate, high_street_kensington, circle).
link(high_street_kensington, gloucester_road, circle).
link(gloucester_road, south_kensington, circle).
link(south_kensington, sloane_square, circle).

i am trying to make its so if i say the station ?- paddington- sloane_square
it will print out the line i need to use so circle and all the stations in between,

can anyone help with this question :)

thanks for any help

21 Replies

Please log in or register to post a reply.

8676d29610e6c98d6dd2d9c38528cd9c
0
alphadog 101 Mar 31, 2009 at 14:14

Do I detect the scent of “Homework no. 5”?

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Mar 31, 2009 at 14:39

can anyone help with this question

What question? You didn’t use any question marks, nor any capitals for that matter. With such carelessness you’ll never become a decent programmer.

And for getting around London I would simply use the Planner :excl:

If it’s a homework assignment, you really should be solving the problems on your own. You won’t have help from forums on your exam either. Take the handbook and/or lecture notes and figure out the logic. You’ll thank me on graduation day. :lol:

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Mar 31, 2009 at 18:31

I will help him! :)

You need to code a recursive search predicate.

findLink(StationSource, StationDestination, StationsInBetweenList)

This predicate might look like:

findLink(Src,Dst,[]) :- link(Src,Dst,circle);
findLink(Src,Dst,[Station | List]) :- link(Src, Station, circle), findLink(Station, Dst, List).

now call:

findLink(paddington, sloane_square, Stations)

to get the stations on the path to sloane_square.

7a4c677bc0c2c8a770c5cc4689f73296
0
asgard103 101 Apr 02, 2009 at 16:55

Thanks Mihail121,

I got it sorted in the end found my own way of doing it,

route(X,Y,Path,CP,Line,[L|T]):-connect(X,Y,L), \+(member(Y,CP)),Path=[Y|CP],Line=[L|T].
route(X,Y,Path,CP,Line,CL):-connect(X,Y,L), \+(member(Y,CP)),\+(member(L,CL)),Path=[Y|CP],Line=[L|CL].

route(X,Y,Path,CP,Line,[L T]):-connect(X,Z,L),\+(member(Z,CP)),route(Z,Y,Path,[Z CP],Line,[L T]).
route(X,Y,Path,CP,Line,CL):-connect(X,Z,L),\+(member(Z,CP)),\+(member(L,CL)),route(Z,Y,Path,[Z CP],Line,[L CL]).
member(X,[X _]).
member(X,[_ T]):-member(X,T).

connect(X,Y,L):-link(X,Y,L).
connect(X,Y,L):-link(Y,X,L).

rev2(L, RL):- % init accumulator
rev2(L, RL, []).
([H|T], RL, CL):-
rev2(T, RL, [H|CL]).
rev2([], RL, CL):- % base
RL=CL.

cango(Y,X,R1,L1):- route(X,Y,R1,[X],L1,[]).

3c5be51fdeec526e1f232d6b68cc0954
0
Sol_HSA 119 Apr 02, 2009 at 17:13

What’s it with these prolog threads all of a sudden?

8676d29610e6c98d6dd2d9c38528cd9c
0
alphadog 101 Apr 02, 2009 at 19:07

Collateral spill-over from the growing interest in Scala/Erlang, which itself is collateral spillover from the “multicore/programmer-end-of-the-world-is-nigh” meme.

Also, Prolog is a language favored by universities. And, as the end of the year approaches, and final projects come due, it’s crazy time…

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Apr 02, 2009 at 21:50

@alphadog

Collateral spill-over from the growing interest in Scala/Erlang, which itself is collateral spillover from the “multicore/programmer-end-of-the-world-is-nigh” meme.

You’re confusing functional programming languages and logic programming languages. The former can facilitate multi-core programming, the latter requires a PhD. to write code that runs faster than can be solved by hand.

Also, Prolog is a language favored by universities. And, as the end of the year approaches, and final projects come due, it’s crazy time…

I guess they favor it because it’s like Latin and ancient Greek. Nobody actually uses it but it makes the professors feel smarter than the students. It’s a vicious circle. :surrender

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Apr 02, 2009 at 22:23

I always wondered why they call prolog a programming language. It’s just as much of a programming language as SQL is. Well, of course it *is* Turing complete.

4413189eb92ecb0c72aa193596bda383
0
Trap_D 101 Apr 06, 2009 at 10:20

@.oisyn

I always wondered why they call prolog a programming language. It’s just as much of a programming language as SQL is. Well, of course it *is* Turing complete.

:no:
I don’t know a lot about SQL, but can you parse grammars, write internet servers and web pages, solve constraint problems with it ?
you should take a look at SWI-Prolog : http://www.swi-prolog.org/

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Apr 06, 2009 at 10:44

I would hardly call parsing grammars and solving constraint problems ‘programming’. And of course you can write programs with it - as said, it’s turing complete and using implementor’s extensions you could probably do everything you like. But that really isn’t the core essense of prolog, which is querying logic questions given a set of definitions.

The C++ template language is turing complete as well, and given a compiler that exposes a compile-time library you could write whole programs in it that execute during compile-time. Yet I have never heard people calling C++ templates a programming language.

4413189eb92ecb0c72aa193596bda383
0
Trap_D 101 Apr 06, 2009 at 11:18

What is your defintion of programming ?

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Apr 06, 2009 at 11:37

The act of writing a program using a programming language, and not the more generic term ‘writing something in a defined language that can be understood by a computer program’. Needless to say, the word ‘programming’ in a sentence like ‘programming your VCR to record something’ has a different meaning imho. Setting up a formal grammar definition (whether you do that in a DSL such as an EBNF dialect or using prolog) does not fall under the category ‘programming’.

8676d29610e6c98d6dd2d9c38528cd9c
0
alphadog 101 Apr 06, 2009 at 18:15

@Nick

You’re confusing functional programming languages and logic programming languages. The former can facilitate multi-core programming, the latter requires a PhD. to write code that runs faster than can be solved by hand.

Well, no, I’m not confusing them. Neither did I mean to imply they are in the same category, but I can see how my poor writing would imply that.

What I meant was that the excitement/fad for Erlang has caused a symbiotic renewal for Prolog. I hear that Erlang was apparently born out of and/or first ran over Prolog.
@Nick

I guess they favor it because it’s like Latin and ancient Greek. Nobody actually uses it but it makes the professors feel smarter than the students. It’s a vicious circle. :surrender

I don’t think it’s bad to teach Prolog and have student do something else than think in procedural-favoring languages. I do hate it when they place excessive emphasis on it outside of a “languages overview” kind of class.

4413189eb92ecb0c72aa193596bda383
0
Trap_D 101 Apr 07, 2009 at 13:14

I don’t think it’s good to know only procedural languages.
There are other ways : functionnal programming, logic programming and I think that a good programmer should know this ways.
I practice C over 20 years (for fun and sometimes professionally) and Prolog opened my eyes. Another way of thinking, it’s very good !

9cd1fa8d4bb45c93065544fe45c285ce
0
Rubicon 101 Apr 07, 2009 at 21:20

But we’re talking about game development. Or at least we should be.

I’ve released at least 40 titles over the last 25 years and never once needed anything more than various assemblers, C and later C++.

I’ve learned a few other task-specific languages like php and python, but only to do specific jobs and none of them game related.

The real world is lots different from academe and I often wonder why that is. Glad I didn’t waste several years learning “background” stuff when I was instead learning my trade.

8676d29610e6c98d6dd2d9c38528cd9c
0
alphadog 101 Apr 07, 2009 at 21:32

I think too many people make the need for Ivory Towers, or the destruction of, too black-and-white.

There’s nothing wrong with good, formal learning. I’ve said it before that I wish I didn’t have to watch “self-taught” programmers reinvent the wheel on classic algorithms. It’s painful to see them waste their time…

OTOH, if you fill your curriculum with too much theory, you produce students unable to function at the outset of their career.

Exposure to Prolog is not harmful. In fact, learning it broadly does “something” to your mind that is useful for a professional developer. (As opposed to a game development hobbyist.)

But, that doesn’t mean one should make it a whole class out of it…

9cd1fa8d4bb45c93065544fe45c285ce
0
Rubicon 101 Apr 07, 2009 at 21:58

I’ll take your word on that given I’ve never seen any prolog code myself, but it does seem to me to be literally a waste of time. I’ve hired a number of grads over the years and the only decent ones were those who were writing hobby games in their free time - their formal training was almost useless and they knew it as well as I did. They need a degree so they do one and that’s that.

Your point about classic algorithms is a good one, and learning general “stuff” is not my problem. It’s just that whilst students are learning the syntax for a practically dead language, they could be learning instead about how to optimise C for better compiler output, or dig a little deeper into how a java garbage collector works or something. All useful stuff designed to broaden thinking, but with something intrinsically useful at the end of it too.

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Apr 08, 2009 at 07:35

@.oisyn

I would hardly call … and solving constraint problems ‘programming’.

Look, .oisyn, don’t use it if you don’t need to in your field, but go ask at your local airline company if it’s a big one, what they use for scheduling flights, calculating fuel and optimal routes. It would either be Prolog, ASP or CSP. Sure, Prolog is not about ehmm.. programming, but for querying answers from problem descriptions which I would also call programming. Sure you can do that in C++, no problem, but if I’m to ask you “code me something that generates me answers from problem descriptions” then you would probably code me a Prolog interpreter, although in C++. Now I don’t argue that it’s mostly used in academica, but that’s partly because huge areas of the industry are run by dumb people. Although you guys speak about _efficiency_ of the programs/scripts, I doupt you’ve even looked at the results of recent SAT/ASP competitions. The solvers are designed to solve fast and not just convince university people that stuff are T-complete.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Apr 08, 2009 at 07:55

Whoa, hold it right there. You’re jumping to conclusions. BIG TIME!

If someone would ask me to set up a database I wouldn’t do that in C++ either, but in an RDBMS using SQL. DSLs are A Good Thingtm. I’m only stating that I don’t think Prolog is a programming language. I have never said that it wasn’t useful in the process of software engineering! And yes, there’s a big difference between programming and software engineering. Programming is just a part of the latter. If I say that I think such and such is not programming, I do not think it’s lesser than programming or that it’s something I won’t be bothered with. I simply mean that such and such is not programming. Literally. No strings attached.

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Apr 08, 2009 at 09:22

Ok, fair enough, I fully agree with the standpoint.

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Apr 08, 2009 at 11:26

In case anyone’s interested, here’s a great book that covers the relationship between all programming languages: Concepts, Techniques, and Models of Computer Programming. It also includes Prolog, but aside from a few examples in a narrow context it doesn’t go into much detail about how to use it in the real world (phew).

The ideas behind declarative, logic and relational programming are definitely very interesting. And it makes you a better programmer in procedural languages as well because it teaches you how to convert a set of ‘requirements’ into procedures, in a very structured way. Usually any experienced programmer can do this automatically and eventually you learn the exact same skills, but knowing the theoretical background can save you from wasting time using hit-or-miss strategies.

Anyway, what I absolutely hate about Prolog is that it knows only one paradigm. Even when the procedural approach is trivial you’re forced to think backward to turn it into logic statements. Performance is also extremely low, since really everything you do is a sort of brute-force search. The separation between the programming language and how the CPU executes things is huge.

And that’s why I love multi-paradigm languages like C++. With a bit of care you can do functional programming and logic programming with it. As noted before the latter can be done using template metaprogramming, where the compiler acts as the search engine. Functional programming approaches become extremely useful when doing multi-core programming.

Personally I wouldn’t teach Prolog in-depth, but a course based on the above book is definitely very valuable and a bit of attention to template meta-programming in C++ wouldn’t hurt either.