I need help prolog recursion problem

Help!
1

I’m using: SWI-Prolog version ???

SWI-Prolog version 7.6.4 for amd64

I am a prolog beginner. I am trying to build a word generator for a made up language to test my prolog capabilities. Here is my code:

generic_consonant(
    ['ሀ', 'ለ', 'ሐ', 'መ', 'ረ', 'ሰ',
    'ቀ', 'በ', 'ተ', 'ኀ', 'ነ', 'ከ', 
    'ꬣ', 'ጠ', '፷', 'ጸ', 'ዂ', 'ፈ', 
    'ፐ', 'ዱ', 'ዳ', 'ዴ', 'ዶ']).

vowel(['ቈ', 'ቊ', 'ቋ', 'ቌ', 'ቍ', 'ኋ', 'ኊ']).

nasal_consonant(['ጙ', 'ዷ', 'ድ', 'ዲ', 'ደ']).

uvular_consonant(['ሠ', 'ወ', 'ዐ', 'ዘ', 'ጙ']).

syllablegen(1, Syllable) :-
    uvular_consonant(Uvular), vowel(Vowel),
    random(0, 7, VowelIndex), random(0, 5, UvularIndex),
    nth0(UvularIndex, Uvular, UvularChar), 
    nth0(VowelIndex, Vowel, VowelChar),

    Syllable = [UvularChar, VowelChar].

syllablegen(2, Syllable) :-
    generic_consonant(Consonant), uvular_consonant(Uvular), vowel(Vowel),
    random(0, 23, ConsonantIndex), 
    random(0, 7, VowelIndex), 
    random(0, 5, UvularIndex),
    nth0(ConsonantIndex, Consonant, ConsonantChar), 
    nth0(UvularIndex, Uvular, UvularChar), 
    nth0(VowelIndex, Vowel, VowelChar),

    Syllable = [ConsonantChar, UvularChar, VowelChar].

wordgen([], _).
wordgen(SyllableNums, Word) :-
    SyllableNums = [Head|Tail],
    syllablegen(Head, Syllable),
    append(Word, Syllable, NewWord),
    wordgen(Tail, NewWord).

All the syllablegen predicates are working when I call “syllablegen(1, X).” and “syllablegen(2, X).”, but a problem occurs when I am calling wordgen and it gives me an unexpected output which is this:

?- wordgen([1, 2],  X).
X = [] ;
X = [_2898] ;
X = [_2898, _2910] ;
X = [_2898, _2910, _2922] ;
X = [_2898, _2910, _2922, _2934]

The behavior I was expecting was an output like this:

?- wordgen([1, 2],  X).
X = [ዐ,ኊ,ለ,ዐ,ቌ] ;

or a derivative of it as randomness exists in this program.

I been working on this for past 12 or so hours and I just cannot figure it out for the life of me. Any help would be greatly appreciated.

Thanks

2

Hi,

I am not fully clear what the purpose of the [1,2] list is … and how [1,2] maps onto 5 elements in the expected output.

Glancing at the code, i noticing that there might be a bit a confusion in the wordgen/2 goal.

I guess Word is used as an output variable - so you probably want to have NewWord there.

Dan

3

This is cross posted on StackOverflow.

Problems with prolog list matching

4

Hi there, @scaladev, welcome! I love your sample program, my wife also likes to make conlang generators when she’s learning new programming languages :grinning_face_with_smiling_eyes:

The core problem you’re facing is that you’re trying to use the parameter Word to wordgen as both input and output at the same time, but the way you’re calling it (with an unbound X) you’re expecting it to be output-only. To see what’s going on here, first change Word to be an input value by calling wordgen as wordgen([1,2], []), and redefine the sentinel clause of wordgen as:

wordgen([], Word) :- print(Word), nl.

This obviously isn’t going to work like you want it to, because at the core you’re trying to get these new words back as a value. So instead of trying to perform double duty with a single argument, split it up into wordgen(SyllableNums, OldWord, NewWord) (or, to use a slightly more Prolog-ish naming convention, wordgen(SyllableNums, Word0, Word)). You’ll be calling it as wordgen([1,2], [], X), because Word0 in this case means “whatever parts of the word you’re generating came before the SyllableNums you’ve requested”. You could generate a word with a prefix by passing the prefix in as the second argument: wordgen([1,2], ['ጙ','ዷ'], X), like if you’re generating the name of a noble and all nobles have names beginning with ጙዷ, just as a for example.

You’ll need to modify wordgen to compensate for the three-argument version, of course. I’ll leave that for you as an exercise, though I’ll give you the hint that your sentinel clause should probably look like wordgen([], X, X).

That said, you’ve actually made yourself a perfect little toy for learning about DCGs (Definite Clause Grammars, though I always have to look up what the acronym stands for myself). Go to Swish and look up the “English grammar” example program, play around with that, see if you can figure out what’s going on there. Then, if you’re feeling confident, take a look at this word-generator again and see if you can rewrite it using DCGs.

If you run into any trouble or if anything isn’t clear, feel free to come on back and ask about it. Welcome to Prolog, and have fun!

2 Likes
5

Here is, btw, the idom for generating an output list:

The follow code gets a list of integers and outputs the list multipled by factor:

e.g.
?- mfactor([1,2,3], 2, L).
L = [2, 4, 6].

mfactor([], _Factor, []).

mfactor([FirstIn | LastIn], Factor, [FirstOut | LastOut]) :-
	FirstOut is FirstIn * Factor,
	mfactor(LastIn, Factor, LastOut).

You can see how output list is "appended’ through recursive calls rather than an append/3 call.

Also, note that LastOut is used as an output Variable … its the output of the last recursive call as well as the mfactor/3 goal itself in context of the list that is created [FirstOut | LastOut].

And, this is how it looks like if one does uses an append:

mfactor2([], _Factor, []).

mfactor2([FirstIn | LastIn], Factor, LastOut) :-
	FirstOut is FirstIn * Factor,
	mfactor2(LastIn, Factor, LastOut0),
	append([FirstOut], LastOut0, LastOut).

Edit:

Btw, the following is essentially equivalent, but doing the pattern matching in the clause head is how its usually done, unless there is a specific reason to do the unification in the body.

mfactor(InList, Factor, [FirstOut | LastOut]) :-
             InList = [FirstIn | LastIn]
1 Like
6

This helped me tremendously once I figured out the example you gave me. Just Brilliant!!! Thanks.

1 Like
7

You made my day with this comment. Incredibly helpful and insightful.

1 Like
8

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
9

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).
10

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

11

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
12

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
13

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.

14

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

15

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 styleguide | Style guides for Google-originated open-source projects; 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
16

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

18

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

21

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
23

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

26

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