Home > Archive > Prolog > January 2006 > short prolog program enclosed, need a review please
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
short prolog program enclosed, need a review please
|
|
| mneuhaber22@berlin.com 2006-01-15, 7:12 pm |
| Greetings!
I am learning Prolog and would appreciate your critique of this
program. I use SWI-Prolog.
Questions - how could have this program been rewritten more
efficiently. Why is REClist sufficiently instantiated, I am not sure I
can explain it... I was expecting that I'd get "REClist not
sufficiently instantiated" error. Please provide the shortest and most
efficient solutions in place of mine and some explanations if you can.
----- begins ---------
% find primes efficiently?
is_prime(2).
is_prime(3).
is_prime(P) :- N is sqrt(P), F is floor(N), gen_primes(F, List),
has_no_factors(P, List).
% get next smaller odd number or 2
decrem(3, Next) :- Next is 2.
decrem(P, Next) :- P > 3, (P mod 2 =:= 1 -> D is 2; D is 1), Next is P
- D.
% given a number To return all primes less than To in List
gen_primes(2, Olist) :- Olist = [2].
gen_primes(To, Olist) :- 2 < To, decrem(To, Next),
(is_prime(To) -> Rlist = [To]; Rlist = []),
append(Rlist, REClist, Olist), % why is REClist sufficiently
instantiated here??
gen_primes(Next, REClist).
has_no_factors(_, []).
has_no_factors(P, [H|T]) :- P mod H =\= 0, has_no_factors(P, T).
print_primes(P) :- gen_primes(P, List), print_list(List).
print_list([]).
print_list([H|T]) :- writeln(H), print_list(T). % change order of these
to get numbers in reverse
main :- print_primes(10000).
----- ends --------
| |
| Bart Demoen 2006-01-15, 7:12 pm |
| mneuhaber22@berlin.com wrote:
> append(Rlist, REClist, Olist), % why is REClist sufficiently
> instantiated here??
Let's lift this out of the context of your program.
Take the query:
?- append([1,2,3],R,Out).
Clearly, the second argument of append is not instantiated - it is free.
Still, this query makes sense and executes fine.
Try it at home and tell us what you find weird about the answer to the
query.
You also ask about more efficient versions of generating primes ...
google for Erathostenes (sieve and Prolog might narrow things down).
Cheers
Bart Demoen
| |
| mneuhaber22@berlin.com 2006-01-15, 7:12 pm |
| Thanks for the query you posed.
The answer is [1,2,3|_G321] which I understand to mean that once the
values in _G321 become known then Out will have the correct values.
However, in another similar program I was getting "insufficiently
instantiated variables" error which I found hard to debug even with the
graphical debugger.
Is it correct to say that the only time ever that error is produced is
when an attempt is made to apply (list, arithmetic, etc.) operations on
it before its value is known such as [H|T] = [_G321] or floor(_G321)?
As far as efficient processing is concerned I did not mean in the
algorithmic sense but efficiency from Prolog point of view, such as
tail recursion.
Also would an expert Prolog programmer use the syntax
expression -: statement1, statement2,
(condition -> expr_for_true; expr_for_false),
statement3
or rewrite it some other way?
| |
| Bart Demoen 2006-01-16, 3:57 am |
| mneuhaber22@berlin.com wrote:
> Thanks for the query you posed.
> The answer is [1,2,3|_G321] which I understand to mean that once the
> values in _G321 become known then Out will have the correct values.
> However, in another similar program I was getting "insufficiently
> instantiated variables" error which I found hard to debug even with the
> graphical debugger.
>
> Is it correct to say that the only time ever that error is produced is
> when an attempt is made to apply (list, arithmetic, etc.) operations on
> it before its value is known such as [H|T] = [_G321] or floor(_G321)?
[H|T] = [_G] is fine (unless you are not using a proper Prolog system).
Arithmetic on free variables is not allowed, neither is using (lots of) built-ins
with arguments that are not enough instantiated, like ?- functor(X,a,Y).
or ?- findall(X,X,X). etc.
> Also would an expert Prolog programmer use the syntax
>
> expression -: statement1, statement2,
> (condition -> expr_for_true; expr_for_false),
> statement3
>
> or rewrite it some other way?
>
Most people would use some form of indentation that makes it easier for a human to
parse the clauses. E.g.:
expression :-
stat1,
stat2,
(condition ->
truebranch
;
falsebranch
),
stat3.
Cheers
Bart Demoen
|
|
|
|
|