Fully understanding the "intricacies" of the Prolog code design process

Help!
21

Several difficulties here.

  • You can’t possibly fit the intricacies of multiple programming paradigms in a course.
  • Programming paradigms themselves are usually (always?) pushed way beyond their usefulness.
  • “Declarative Programming” is an oxymoron; here is one post on the topic but please search yourself, the topic pops up regularly.
  • Reading library code is a fundamental part of learning programming.
  • Terribly sloppy to save typing: Programming does not have general laws in the same way that nature does. It is invented by humans and we still don’t understand ourselves well enough.

I understand that this doesn’t answer your question directly.

22

" length(L,_),include(odd,L,[1,3,5]) goes into an infinite loop – I haven’t investigated why."
There are infinitely many lists L satisfying this predicate. Moreover, they are (in a sense) inexpressible as Prolog answers. The documentation says include(:Goal,+List1,?List2), so such queries are excluded and possibly should raise an exception.
Looks like some “backward” queries correctly succeed, some incorrectly fail.
For one/1 defined by single fact one(1),
include(one,[A],[1]) succeeds with A=1 but include(one,[A,B],[1]) fails.

23

This says any list List is the list of its even elements. Thus filter_evens0 is incorrect.

25

Thanks for your insights, @j4n_bur53. Are you a retired professor of Computer Science? (Hope you don’t mind if I ask). Anyways you definitely master your subject :clap:t2:

27

when i was in the university many years ago i was confronted with (in my opinion )
the same kind of prolog exercises, i would say; prolog exercises which would never
occur in real life. but maybe the reason is that for academic reasons
you can confront the students with about anything.

in real life If you would have to filter Even elements from a list you would want it to work
allways without any bugs and the code should be easy to understand for other developers
and it should be possible to easily modify it.

it should allways work because you have to give garanty to your clients.
as soon if you make it bi-directional it will consume too much memory
and bugs can occur.

If you can design a Prolog-exercise which would really occur in real life
then the students would take it seriously

1 Like
28

I also find that Boris’ statement was a strong one, at least for a prolog community, but it didn’t cause such a big reaction maybe because it was interpreted as a joke or a way to be provocative

30

I don’t make silly jokes like that. I have however developed a strong distaste for some of the attitudes that seem to self-emerge in academic circles and in teaching. :grinning:

@Marco the way I see it, as an academic who has not yet been able to avoid having to deal with students, one must make a choice: be a teacher or a gate-keeper. Both are valid choices and have their purpose. It might even be that gate-keeping gives better outcomes, even if only because it is easier. I would love to see some empirical research on the topic.

1 Like
31

I don’t understand what you mean by “gate-keeper”. Do you refer to the bureaucratic side of teaching?

No maybe you were referring to this

33

a good prolog student exercise would be for example to make a DCG grammer and apply it to sentences because that can be used in real life

1 Like
34

People are usually attracted to what is popular…but I find it hard to believe that type theory could ever be such a thing :sweat_smile:

37

Or maybe reading the whole sentence is too difficult? We might never know.

40

Hello @sgodoyc,
I know I’m posting this a bit after the battle ^^ but I did spent a long time thinking about the same subjects. So, here is my take of the problem:

First, I believe your basic exercise contains not one but two rabbit hole ^^:

  1. the declarative aspect of manipulating a list, which is very well spelled out in your original post with the 4 different case.
  2. the declarative aspect of what an even numeric element is.
    • your b1 and b2 cases hints that an even number is a binary mutually excusive test but no more information is given.

So let’s start the thought experiment by spelling out your four cases on the declarative use of list for filtering elements. Let’s admit that we have a even/1 predicate that is a binary mutually exclusive test of an even number:

filter_evens([], []).
filter_evens([X | Rest], Answer) :-
   even(X),
   filter_evens(Rest, Answer).
filter_evens([X | Rest], [X | Answer]) :-
   not(even(X)),
   filter_evens(Rest, Answer).

Next, how should even/1 be coded ? Well, let’s start with the most obvious:

even(X) :-
    (X mod 2) =:= 0.

However, you can’t stop here. You need to ask yourself, what are the different possiblity of X ?
Traditionnaly, in programming, you would want to know the type of a variable.
In our case, it would be relevant to ask what this even/1 test would do if:

  1. X is a number: well, that’s easy, just compute the arithmetic and conditional
  2. X is not a number: there is two possibility here
    i. fail: which mean that filter_evens/2 accepts non numeric entities in List.
    ii. raise a type error: meaning “I don’t know how to handle this, deal with it ^^”

The behavior of prolog arithmetic choose the 2.ii options and raise on non numeric values.
For option 2.i, you need to test the type of X first, which number/1 could do.

But you have another problem in prolog, which is groundness:

  1. X is ground: well, you can just proceed with the type tests.
  2. X is a variable: this means that X could be later instantiated to anything, a number or something else, there’s multiple solutions here:
    i. raise an instantiation error: same as the type, refuse to proceed.
    ii. use constraints: heh, I lied, there is 3 rabbit holes in this problem ^^

You will often find prolog code that treats variables as another type. For example, number/1 fails when given a variable. But from prolog point of view, this is not a pure declarative stance.

So I believe that without using constraints, you should either keep the previous definition of even/1 or if you want to be able to handle non-numeric ground elements, modifiy to this:

even(X) :-
    (  var(X)
    -> instantiation_error(X)
    ;  true
    ),
    number(X),
    (X mod 2) =:= 0.
41

The solution I proposed in my earlier post has a major drawback:

It doesn’t work and raise on uninstantiated List or uninstantiated elements of List.

This is specifically what constraints are for :slight_smile:
It is actually possible to very cleanly resolve this problem with a single freeze/2 predicate that delays evaluation until a variable is binded to.
However, I would like to present another solution than the one proposed by @peter.ludemann.
The main difference would be to apply freeze on the list rather than only on the evenness test.

So again, case by case analysis:

  1. List is variable: let’s delay the evaluation of List until it is binded to, because if we don’t know what List is, you won’t know what Answer is.
  2. List is not a variable:
    1. which mean it can be an empty list List = [], then we know that Answer must also be []
    2. or it is a partial list List = [X | Rest]
      1. X is a variable: delay evaluation until X is binded to because we don’t know what should be the next element of Answer
      2. X is not a variable: proceed with the evenness test

Here is how I would implement this:

filter_evens(List, Answer) :-
   freeze(List, filter_evens_(List, Answer)).
filter_evens_([], []).
filter_evens_([X | Rest], Answer) :-
   freeze(X, filter_evens__(X, Rest, Answer)).
filter_evens__(X, Rest, Answer) :-
   (  number(X), X mod 2 =:= 0
   -> filter_evens(Rest, Answer)
   ;  Answer = [X | FilteredRest],
      filter_evens(Rest, FilteredRest)
   ).

Notice that the last filter_evens__ uses a imperative style if/else constructs with no loss of logical purity because we are guaranted that X is not a variable here.
I believe, this is a fully pure and complete implementation of your initial problem.
It mainly resolve many common painpoints of prolog codes:

  1. query that do not terminates and you go all what the heck is going on :roll_eyes:
  2. succeed for variables, while they can be later binded to contradictory values
  3. cut short possible additional solutions
42

Morality, prolog code design is helluva complicated :exploding_head:

1 Like
43

Hi @kwon-young,

Fascinating answer!
First of all, I thank you for taking the time to explain. It doesn’t matter if late, but these are apparently simple questions that a student new to prolog wil sooner or later make, and they are not at all easy to answer.

I understand your examples and argumentation, but maybe you can understand that, when you teach something like Prolog programming, you must (ought) to advance in well-defined stages. Obviously, variable constraints are a later stage than designing unconstrained predicates.

That is why I am struggling to explain to my students in a way each stage is sufficiently clear so students can tackle exercises on their own. But it seems not easy at all…

44

I fully understand and agree with your will to search for a more structured design process.
I tried to structure my answer as pedagogically as possible.
Is there anything I could improve in my answers ? or maybe some things are unclear ?
I really did not want to sound like a highly knowledgeable professor or something like that, but just try to spell out my own thought process.

By the way, about constraints being a later stage things, that’s why I made two answers, as something like a two stage answer ^^

45

I believe the magic is about coming up with the different cases for analysis.
For that, you need to know about a lot of things in prolog like:

  • prolog basic types: atoms, numbers, terms etc
  • groundness: variables and partially instantiated terms
  • the difference between failure and exceptions
  • etc

That’s why it is so hard for a student to come up with theses cases, I think.
There are also loads of traps, with a lot of standard predicates not being fully pure, arithmetics being the first culprits ^^

46

@kwon-young ,

I agree your anwer is very well structured, and I don´t think you need to change anything.

After meditating a lot, I came to understand that I have still to find an adequate balance between what I explain (the first time I explain some concepts) and what students should find by themselves. It is not clearly defined anywhere, so must find my own version of that balance…
:face_with_monocle:

47

He, I never did any prolog teaching, so you should know about these things better than me ^^

Now that we have a good understanding of the problem, maybe we could come up with a list of prerequisite that could enable any student to come up with the correct case by case analysis and code ?

Maybe something like:

  1. lists: so, linked lists, head and tails, yaddy yadda
  2. predicates: that’s an obvious one, the basic , is AND and clauses are OR
  3. unification: very complicated to explain… but this explains what are variables and all
  4. prolog arithmetics: don’t just say that + is + but also explains the limit of basic prolog arithmetic in respect to pure prolog code
  5. success and failure through backtracking
  6. exceptions ?

That’s a half-semester course ^^

48

That is not a bad idea, however, I think the list should be structured from the simplest concepts to the more complex ones. So terms, logic operators and variables should go before unification, and unification should go before lists, etc.

Let me work a little on it and come back tomorrow with a clear sugestion…

And then you can comment on it…