# I need help prolog recursion problem

**URL:** <https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252>\
**Category:** Help!\
**Tags:** how-to\
**Created:** [August 5, 2021, 4:08am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252 "2021-08-05T04:08:52Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![scaladev](https://avatars.discourse-cdn.com/v4/letter/s/85e7bf/32.png) [@scaladev](https://swi-prolog.discourse.group/u/scaladev)\
**Post date:** [August 5, 2021, 4:08am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/1 "2021-08-05T04:08:52Z")

</div>

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:

```prolog
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:

```prolog
?- 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:

```prolog
?- 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

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [August 5, 2021, 5:07am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/2 "2021-08-05T05:07:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\
**Post date:** [August 5, 2021, 7:43am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/3 "2021-08-05T07:43:18Z")

</div>

This is cross posted on StackOverflow.

[Problems with prolog list matching](https://stackoverflow.com/questions/68658188/problems-with-prolog-list-matching)

---

<div class="post-metadata">

**Author:** ![dmchurch](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/dmchurch/32/3427_2.png) [@dmchurch](https://swi-prolog.discourse.group/u/dmchurch)\
**Post date:** [August 5, 2021, 8:57am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/4 "2021-08-05T08:57:47Z")

</div>

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

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:

```prolog
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!

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [August 5, 2021, 11:55am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/5 "2021-08-05T11:55:10Z")

</div>

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].

```prolog
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:

```prolog
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.

```prolog
mfactor(InList, Factor, [FirstOut | LastOut]) :-
             InList = [FirstIn | LastIn]

```

---

<div class="post-metadata">

**Author:** ![scaladev](https://avatars.discourse-cdn.com/v4/letter/s/85e7bf/32.png) [@scaladev](https://swi-prolog.discourse.group/u/scaladev)\
**Post date:** [August 6, 2021, 4:13am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/6 "2021-08-06T04:13:27Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![scaladev](https://avatars.discourse-cdn.com/v4/letter/s/85e7bf/32.png) [@scaladev](https://swi-prolog.discourse.group/u/scaladev)\
**Post date:** [August 6, 2021, 4:14am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/7 "2021-08-06T04:14:10Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![dmchurch](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/dmchurch/32/3427_2.png) [@dmchurch](https://swi-prolog.discourse.group/u/dmchurch)\
**Post date:** [August 7, 2021, 3:42pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/8 "2021-08-07T15:42:01Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [August 8, 2021, 7:04pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/9 "2021-08-08T19:04:23Z")

</div>

There’s an easier way of doing this:

> [@grossdan](#):
>
> ```prolog
> mfactor([], _Factor, []).
> mfactor([FirstIn | LastIn], Factor, [FirstOut | LastOut]) :-
> FirstOut is FirstIn * Factor,
> mfactor(LastIn, Factor, LastOut).
> 
> ```

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

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

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

```

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [August 8, 2021, 7:34pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/10 "2021-08-08T19:34:18Z")

</div>

> [@peter.ludemann](#):
>
> `mult_by(X, Factor, XtimesFactor) :- XtimesFactor is X * Factor.`

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

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [August 8, 2021, 7:53pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/11 "2021-08-08T19:53:50Z")

</div>

> [@grossdan](#):
>
> I think, the Factor has to come first … in the argument to define the closure.

Yes. I edited my answer.

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

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

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

```

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [August 8, 2021, 8:18pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/12 "2021-08-08T20:18:56Z")

</div>

And one more way, using DCG notation:

```prolog
:- 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).

```

---

<div class="post-metadata">

**Author:** ![scaladev](https://avatars.discourse-cdn.com/v4/letter/s/85e7bf/32.png) [@scaladev](https://swi-prolog.discourse.group/u/scaladev)\
**Post date:** [August 8, 2021, 9:55pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/13 "2021-08-08T21:55:37Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [August 11, 2021, 7:20am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/14 "2021-08-11T07:20:38Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [August 11, 2021, 5:40pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/15 "2021-08-11T17:40:14Z")

</div>

> [@grossdan](#):
>
> What would the declarative / mathematical reading of map be …

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](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.

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [August 11, 2021, 9:48pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/16 "2021-08-11T21:48:11Z")

</div>

> [@peter.ludemann](#):
>
> I know that I had to force myself to use the meta-programming style until I became comfortable with it.

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:

> [@peter.ludemann](#):
>
> force myself

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

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [August 12, 2021, 4:41am UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/18 "2021-08-12T04:41:34Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [August 15, 2021, 2:18pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/21 "2021-08-15T14:18:40Z")

</div>

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:

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

```

"We can [**read this declaratively**](https://www.metalevel.at/prolog/reading#declarative) 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](https://www.metalevel.at/prolog/facets)

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [August 15, 2021, 5:05pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/23 "2021-08-15T17:05:45Z")

</div>

> [@anon95304481](#):
>
> So you have to explain why you would need a Prolog integration of CLP(FD),

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

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [August 15, 2021, 5:42pm UTC](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252/26 "2021-08-15T17:42:07Z")

</div>

> [@anon95304481](#):
>
> Can you explain the [(#\>)/2](https://www.swi-prolog.org/pldoc/doc_for?object=(%23%3E)/2)? Its not part of the mathematical definition.

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

[Next page](https://swi-prolog.discourse.group/t/i-need-help-prolog-recursion-problem/4252.md?page=2)