[HN Gopher] Coding Guidelines for Prolog (2011)
___________________________________________________________________
Coding Guidelines for Prolog (2011)
Author : tosh
Score : 100 points
Date : 2023-09-23 12:20 UTC (10 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| [deleted]
| gilcot wrote:
| I've been doing Prolog without knowing there's a coding
| guidelines. Thanks.
| izwasm wrote:
| I remember using this language in the AI class, i thought it was
| an old, deprecated language as people now use python mainly,
| really cool to see it again
| rhelz wrote:
| I forget who said it, but a good programming language should
| have two features:
|
| 1. Make simple problems easy.
|
| 2. Make difficult problems possible.
|
| Python is an _outstanding_ language on both scores.
|
| Prolog, alas, is much better at #2 than it is at #1. For
| example, prolog is a great choice for writing domain-specific
| languages, and modern implementations (like scryer prolog,
| mentioned in a comment above), can generate very efficient code
| for them.
|
| Prolog's "killer ap" is how well it does on a third feature:
|
| 3. It makes virtually impossible tasks "merely" very difficult
| ;-)
|
| And it has a steep learning curve; it took me years to really
| "get" it, and I only persevered because I was facing one of
| those category #3 problems.
|
| Its not a deprecated language, but alas, it is destined to be a
| niche language. But for those niches, it is still the best,
| hands-down.
| bacteria wrote:
| Can you tell us about the problem you've encountered in #3?
| I'm really interested
| ngruhn wrote:
| I guess this is rather category #2 than #3, but my favorite
| example is Advent of Code 2021, day 24:
| https://adventofcode.com/2021/day/24. I think many people
| consider this one of the hardest AOC problems ever and at
| the time many people didn't even code up a complete
| solution but solved in manually (me included). However,
| with Prolog it's almost trivial. So many of Prologs
| strengths come together here: writing parsers, writing
| interpreters, solving integer constraints, and in
| particular "reasoning backwards".
| guessbest wrote:
| I think it is undergoing a resurgence due to the LLM
| prolifereating, but I haven't seen how Prolog is being used in
| the LLM creation. Of course, I don't really understand the
| whole process of the creation. I do remember someone on a
| academic/programmer forum stating Prolog regarding research was
| big in academics in Europe whereas Lisp was more popular in
| America academics for research. It would make sense as Richard
| Stallman was big into AI Lisp as a consultant.
| triska wrote:
| Very interesting! Let's consider for example the definition of
| sum_list/2 which is shown in Fig. 1, Fig. 2 and Fig. 3:
| %% sum_list(+Number_List, ?Result) % Unifies Result with
| the sum of the numbers in Number_List; % calls error/1 if
| Number_List is not a list of numbers.
| sum_list(Number_List, Result) :-
| sum_list(Number_List, 0, Result). %
| sum_list(+Number_List, +Accumulator, ?Result)
| sum_list([], A, A). % At end: unify with accumulator.
| sum_list([H|T], A, R) :- % Accumulate first and recur.
| number(H), !, B is A + H,
| sum_list(Rest, B, R). sum_list(_, _A, _R) :- % Catch ill-
| formed arguments. error('first arg to sum_list/2
| not a list of numbers').
|
| Compiling it with Scryer Prolog, I get a warning:
| $ scryer_prolog sum_list.pl Warning: singleton variables
| T, Rest at line 4 of sum_list.pl true.
|
| A singleton variable often indicates a mistake in the code. And
| indeed, the sample code uses Rest where it apparently meant to
| use T (or vice versa). So, I change the second clause of
| sum_list/3 to: sum_list([H|T], A, R) :-
| number(H), !, B is A + H,
| sum_list(T, B, R).
|
| And now we're ready to use the predicate! Let's ask Prolog the
| most general query: _Which answers are there in general?_ So, a
| query where all arguments are logic variables:
| ?- sum_list(Ls, R). Ls = [], R = 0 ;
| error(existence_error(procedure,error/1),error/1).
|
| The existence error is due to the use of the non-standard
| predicate error/1 in the code sample. The predicate apparently
| meant to throw an exception telling us: first
| arg to sum_list/2 not a list of numbers
|
| But _the query did not restrict the first argument at all_ , so
| it may just as well be a list of numbers! The predicate probably
| meant to say that the argument is _not sufficiently
| instantiated_. In that case, it should have thrown an
| _instantiation error_. The standard predicate (is) /2 throws such
| an instantiation error for us in such cases. Also, it throws
| _type errors_ for us! A type error is categorically different
| from an instantiation error: From a logical perspective, a type
| error can be replaced by silent failure, but an instantiation
| error can not.
|
| We can therefore write the second clause as:
| sum_list([H|T], A, R) :- B is A + H,
| sum_list(T, B, R).
|
| and also remove the third clause entirely. We now get:
| ?- sum_list(Ls, R). Ls = [], R = 0 ;
| error(instantiation_error,(is)/2).
|
| From a logical perspective, that's OK: The predicate tells us
| that too little is known to make any statement, and a more
| specific query may yield solutions.
|
| Also, this version correctly distinguishes between type and
| instantiation errors, and we now get for example:
| ?- sum_list("abc", R).
| error(type_error(evaluable,a),(is)/2).
|
| As I see it, a key attraction of logic programming is that we are
| able to reason logically about our code. This holds as long as
| certain logical properties are preserved. The paper hints at such
| properties for example with the concept of _steadfastness_ ,
| which it defines in Section 5.1: A predicate " _must work
| correctly if its output variable already happens to be
| instantiated to the output value_ ". How can we tell though which
| variables are output variables, and also why even distinguish a
| particular variable as "output variable"? Should this not hold
| for _all_ variables?
|
| A particularly important logical property is called
| _monotonicity_ : Generalizing a query (or program) can at most
| add solutions, never remove them. With monotonic predicates,
| debugging is very nice: For instance, if a predicate unexpectedly
| fails, then we can _generalize_ it by removing goals, and if the
| remaining fragment _still_ fails unexpectedly, then there must be
| a mistake _in that fragment_. Scryer Prolog provides
| library(debug) for this approach of _declarative debugging_ :
|
| https://www.scryer.pl/debug
|
| In Scryer Prolog, we can define the specific case of arithmetic
| over integers with _constraints_ over integers, for example like
| this: :- use_module(library(clpz)). :-
| use_module(library(lists)). :-
| use_module(library(lambda)). list_sum(Is, S) :-
| foldl(\I^S0^S^(S #= S0 + I), Is, 0, S).
|
| Higher-order predicates such as maplist/N and foldl/N retain
| logical properties of the predicates that occur as arguments.
|
| The most general query now works as expected:
| ?- list_sum(Is, Sum). Is = [], Sum = 0 ; Is =
| [Sum], clpz:(Sum in inf..sup) ; Is = [_A,_B],
| clpz:(_A+_B#=Sum) ; Is = [_A,_B,_D], clpz:(_A+_B#=_C),
| clpz:(_C+_D#=Sum) ; ... .
|
| The predicate does not terminate, _as expected_ , because we
| expect solutions for lists of _all lengths_ :
| ?- list_sum(Is, Sum), false. loops.
|
| And other cases are simply specific _instances_ of the most
| general query: ?- list_sum([1,2,3], Sum).
| Sum = 6.
|
| Note that I have changed the predicate name from sum_list/2 to
| list_sum/2, because the list is the _first_ argument, and the sum
| is the _second_ argument. So, I am now using "sum" no longer as
| a _verb_ , but as a _noun_ , because that seems more appropriate
| for code that is declarative, not imperative: We describe what is
| true, not what must be done, and our code works in all directions
| and also with different execution strategies. integers_sum/2 may
| be an even better name in this case.
|
| One other naming convention I like to use is to append an "s" for
| logic variables that stand for lists, such as "Is" for a list of
| integers.
| rhelz wrote:
| Great post, showing how these coding guidelines are showing
| their age. So much boilerplate comments, which clearly are not
| pulling their weight. A simple coding guideline like "eliminate
| all singleton variable warnings" would serve better, and it is
| enforced automatically to boot.
|
| One thing we have learned is that if a coding guideline is
| mandatory, it just has to be automatically checkable and
| enforceable.
| Avshalom wrote:
| >does not terminate, as expected
|
| okay but generally we want things to terminate. An infinite
| list of useless solutions is almost never what people want in
| an actual program.
|
| which also ties into the definition of "the output variable",
| which is the information we wanted when we wrote the predicate.
| crabbone wrote:
| > okay but generally we want things to terminate.
|
| Not in this case. In this case the author claims that if
| there are infinitely many solutions, the predicate should
| give infinitely many solutions. It's similar to how you want
| functions in languages that use functions to fail
| _predictably_. Eg. you want to receive ENOENT exit code if
| you try to open a file that doesn 't exist. Or, you want to
| block forever if you join a thread that runs an infinite
| loop.
|
| Do you want to have any of those behaviors in your program?
| -- rarely, and sometimes not at all. But you want your
| program to fail in such a way that would indicate that you
| coded it in a particular way that should result in such an
| error.
| ngruhn wrote:
| I think he's just using it as a test here. He forces infinite
| backtracking by adding false
|
| to the query. You wouldn't do that in an actual program.
| abecedarius wrote:
| I'm not sure if this example is meant to be a great one -- they
| introduce it to illustrate different ways of typesetting.
|
| _The Craft of Prolog_ by one of the authors gave similar
| general advice to yours, as I remember it. (Good book.)
|
| I've only glanced over this paper.
| Andrew018 wrote:
| [dead]
___________________________________________________________________
(page generated 2023-09-23 23:00 UTC)