I need help prolog recursion problem

I’m so glad! I have such a soft spot for Prolog because it is so different than all the standard programming languages in use these days, and I love getting to help people learn more about it. I hope you enjoy whatever you end up doing with it, and feel free to come back and ask if you have any other questions!

1 Like

There’s an easier way of doing this:

The maplist/3 predicate does the iteration over a list for you. You merely have to define the predicate to apply to each value:

mult_by(Factor, X, XtimesFactor) :- XtimesFactor is X * Factor.

mfactor(Xs, Factor, Results) :-
    maplist(mult_by(Factor), Xs, Results).

I think, the Factor has to come first … in the argument to define the closure.

Btw, i took the factor example from the Crafts book – to illustrate how a list can be constructed.

I guess, these are two styles – the meta call approach and what O’Keefe, I think, calls unfolding where you remove map like calls to improve performance.

In my work i tend to remove maps to improve performance …

Dan

Yes. I edited my answer.

And there’s another way of doing lists, using DCG notation:

mfactor([], _) --> [].
mfactor([X|Xs], Factor) -->
     { Y is X * Factor },
     [Y],
     mfactor(Xs, Factor).

?- phrase(mfactor([1,2,3], 10), Zs).
Zs = [10, 20, 30].
3 Likes

And one more way, using DCG notation:

:- use_module(library(dcg/high_order)).

mult_by(Factor, X) -->
    { XtimesFactor is X * Factor },
    [XtimesFactor].

mfactor(Xs, Factor, Ys) :-
    phrase(sequence(mult_by(Factor), Xs), Ys).
1 Like

Higher order logic is the coolest thing in the world. These two examples you gave are awesome while I try to grasp definite clause grammars. Thank you.

Perhaps, I am nitpicking here but, what I like about the recursive solution is that it makes the inductive definition of factor visible.

a factor list is a list with the first element factored appended to a factored rest list.

What would the declarative / mathematical reading of map be …

A factored list is a list with each element factored … i guess, its easier to “see” the solution in the calling context when its made explicit – with the map solution you have to look up the closure predicate

Dan

Similar to the declarative/mathematical reading of the predicate that gives the recursion explicitly rather than using maplist/3.

When I was programming a lot in Python, I noticed that there was a minority who were very comfortable with writing list comprehensions and a majority who preferred the more verbose for-loop and use of “append” (this resulted in section 2.7.4 in https://google.github.io/styleguide/pyguide.html; a style-guide rule that I hate).
Perhaps there’s a similar divide between people who are comfortable with Prolog-style recursion and unification and those who prefer the imperative/iterative style. (And another divide between people who like maplist/3, foldl/4, convlist/3, etc. and those who prefer to write it out explicitly.) I wonder if it’s just a matter of familiarity … I know that I had to force myself to use the meta-programming style until I became comfortable with it.

1 Like

I was just asked by an experienced programmer, and friend, who is introducing himself to Prolog, and who has difficulties getting his head around – how to think – the Prolog way – and in particular about loops when defining predicates.

Loops come natural to him in imperative languages, but in Prolog he seemed to stumble in how to think about them.

I suggested to him to stop thinking about loops and start thinking inductively and mathematically in term of definitions – and more specifically, in terms of the relationship that holds between arguments of a predicate – and see this relationship formalized in the body of the predicate.

I then asked him to write out the predicate that defines a factor list and think in terms of a definition such as a factor list is a list where the first element is multiplied by a factor and the rest is a factor list.

This naturally lead him to write out the factor program i posted here earlier, together with the base condition and it seems to have helped him do it naturally without getting bogged down into loop thinking.

It seems to me that a loop is an implementation artifact and loop thinking is imperative thinking – in logic, so it seems, its about the effect that loops entail – and implied by the forall quantifier that defines an invariant.

Is the map implementation in this sense more implementation oriented –

Edit:

If you analyze the “units of thoughts” that go into the use of meta-programming, then you end up with:

a) the idea of a closure – that becomes an auxiliary predicate
b) the idea of applying an argument to a closure thereby completing a call
c) the idea of a “maplist” operator that successively takes an argument a closure and an argument from a list and an output variables, and makes a call of the combined “on the fly” created predicate
d) an “implicit” output variable that is appended during successive calls into an output list

I think so much is going on here that is implicit (and partial)-- which is perhaps the reason why its not so natural and code that is hard to understand.

Dan

This is why language that express intent rather than implementation have a better chance to produce correct results.

I didn’t think about it as a “slogan” but as a key selling point of Prolog’s declarative approach.

If you compare for example Markus Triska’s example of list length and its declarative reading, with its imperative “sibling”, then you can intuit the difference between intent and implementation:

list_length([], 0). 
list_length([_|Ls], N) :-
    N #> 0, 
    N #= N0 + 1, 
    list_length(Ls, N0).

"We can read this declaratively as follows:

  1. The length of the empty list [] is 0.
  2. If the length of the list Ls is N0 and N is N0+1, then the length of [_|Ls] is N. Further, this only holds if N is greater than 0."

https://www.metalevel.at/prolog/facets

1 Like

I think, the example can be rewritten without use of the CLP library, while retaining the same declarative reading, just that the bi-directional is lost due to the is operator – and the procedural reading of Prolog slips in because order then matters.

But, i still see it as a great example of functional intent vs. implementation.

Dan

You can define a function for two ranges a) when list is empty, b) when list is non-empty

We can define intent in various ways – in my doctoral thesis an intent was defined as a goal – i.e. where choice and commitments are open.

In the length example, I define an intent as a mathematical definition – whereas an implementation is an algorithm that when executed computes based on the definition.

In Prolog the description of the definition and of the algorithm are closer aligned because of the declarative and procedural reading of the same code.

I don’t see why you’re trying to define Prolog narrowly.
Would you say I’m not programming in Prolog if I use freeze/2 or dif/2 or when/2 (which date back to about 1985)? What about attributed variables, which are earlier than 1985, and which are used by various constraint solvers?

There have been various “flavors” of Prolog from the very beginning, and I think there’s little point in trying to precisely or narrowly define what “Prolog” means.

1 Like

Certainly it is – length/2 is defined only if the length is a non-negative integer. So, there should also be a test for N being an integer.

I think i am missing something important you have in mind, since the rewrite seem trivial … just use the is operator and change the order … it would still have the declarative flavor offered by Prolog.

I like the #= operator mainly because it can handle deferred compute (via, I guess, attributed variables), and can be used before the recursive call, and because it work bi-directional.

re: executable specification

Terms such as requirements, design, implementation, and the term specification – which is often associated with requirements, have always had fuzzy boundaries – and often they are in the eye of the beholder – i.e. you have to ask who made an embodied decisions - the customer or the implementer – to know if its required or by-design.

An executable specification has the additional benefit that you can more easily validate the specification with the problem owner, by executing it and asking if the observed behavior is the intended one.

O’Kefee describes in his Crafts book how he thinks differently when implementing in C or in Prolog – with the latter evoking a metaphor of many strands that must interrelate just so …

When I am close to the book I can look up the exact quote …

I can understand why you are introducing the area of default knowledge here, but my comment was with a much more narrow scope in mind and much closer to software engineering.

A software system that gets implemented, gets specified first. The specification would then capture functional intents whereas the implementation capture realization of those intents in imperative code.

Absolutely …

Non-Functional Requirements, or so called ,NFRs, are key to the overall success of a solution system.

Clearly, solution systems that implement the same functionality can be designed to address different NFRs – such as a database that is embedded vs. a database that is multi-tenant and on the cloud.

You are right, I was not precise in my phrasing – i meant functional requirements that describe intent …

In my doctoral work I made use of a modeling framework that treated NFRs as goals/intents to be achieved and assisted in clarifying them and exploring the design space for satisficing them (satisfying well enough) in relation to tradeoffs with other NFRs

This was essentially an argumentation framework.

Typically, dealing with NFRs involves architectural decisions, but also more detailed decisions such as related to data structures used …

Dan

Didn’t occur to me to post it here – also, although, i am posting quite extensively here - i do like to keep my identifiable internet footprint low … would be glad to send you a link “off-list” …