Prolog - Lazy programmer

Author

Lazy programmer

tmp123

2006-01-10, 4:10 am

Hi,

I want to have the rules to add an integer in a sorted list of
integers.

My starting point are the rules to add an integer, and the rules to
check if the list is sorted:

add(Q,I,[I|Q]).
add([H|Q],I,[H|QR]) :- add(Q,I,QR).

sorted([]).
sorted([_]).
sorted([A,B,|Q]) :- A =< B, sorted([B|Q]).

The rule to add an integer in a sorted list to obtain a sorted list
could be:

sorted_add(L,I,R) :- add(L,I,R), sorted(R).

But it is not the most efficient set of rules ;-) . And I do no want to
write manually an improved set of rules.

Thus, the question is: there are references or works in progress about
how to move the restriction ("sorted" in this case) backwards (inside
"add" rules) to obtain in a sistematic and methodological way
"sorted_add"?.

Thanks a lot.

PS: One correct output of the method could be:

sorted_add([],I,[I]).
sorted_add([H|Q],I,[I,H|Q]) :- I =< H.
sorted_add([H|Q],I,[H|QR]) :- I >= H, sorted_add(Q,I,QR).

Bart Demoen

2006-01-10, 4:10 am

tmp123 wrote:
> Hi,
>
> I want to have the rules to add an integer in a sorted list of
> integers.
>
> My starting point are the rules to add an integer, and the rules to
> check if the list is sorted:
>
> add(Q,I,[I|Q]).
> add([H|Q],I,[H|QR]) :- add(Q,I,QR).
>
> sorted([]).
> sorted([_]).
> sorted([A,B,|Q]) :- A =< B, sorted([B|Q]).
>
> The rule to add an integer in a sorted list to obtain a sorted list
> could be:
>
> sorted_add(L,I,R) :- add(L,I,R), sorted(R).
[...]

You have a typical case of a generator and a tester.
In a CLP approach, one would put the test before the generator
and delay goals (like A =< B) until they are sufficiently instantiated.
That's fairly standard, but doesn't give you the end result you want: a
new (and "efficient") Prolog program.

So, the next step would be to automatically move the (potentially)
delayed goals to the earliest program point where they are for sure
sufficiently instantiated. Nothing specific comes to mind, but there has
been a lot of work on this issue. Try papers by (C)LP people in Madrid,
Leuven and Melbourne, and you will for sure find the stuff you want.
Maybe some googling with keywords delay or freeze, program
transformation, analysis (and Prolog) will help you as well.

Cheers

Bart Demoen

tmp123

2006-01-10, 4:10 am

Bart Demoen wrote:
> tmp123 wrote:
> [...]
>
> You have a typical case of a generator and a tester.
> In a CLP approach, one would put the test before the generator
> and delay goals (like A =< B) until they are sufficiently instantiated.
> That's fairly standard, but doesn't give you the end result you want: a
> new (and "efficient") Prolog program.
>
> So, the next step would be to automatically move the (potentially)
> delayed goals to the earliest program point where they are for sure
> sufficiently instantiated. Nothing specific comes to mind, but there has
> been a lot of work on this issue. Try papers by (C)LP people in Madrid,
> Leuven and Melbourne, and you will for sure find the stuff you want.
> Maybe some googling with keywords delay or freeze, program
> transformation, analysis (and Prolog) will help you as well.
>
> Cheers
>
> Bart Demoen

Hello everybody,

Thanks Bart for your answer.

I've googled for something similar during long long time (and thinking
about also). Not only the answer has not appeared, even groups working
the subject doesn't appear. I must be doing something wrong.

It is something confusing. Because the question doesn't seems empty.
The first set of rules is, more or less, a definition of the ideal
concepts involved in the problem. The second set is more or less a
definition of an algorithm (from these last rules, it is easy to
implement a program in any language).

Thus, go from rules "A" to "B" is, in fact, what a programer is doing
during a significative amount of his time. In this way, a
methodological method seems a key for a lot of targets.

Again, any pointer is welcome.

Kind regards.

Sponsored Links