Generating ASTs with SSU, not working as expected

Help!
1

Some recent topics are noting the use of SSU as generators. Since I use generators often wanted to give generating with SSU a try.

When I converted some normal code that generates ASTs to SSU (no DCGs) only one result was generated for the SSU version.

As this was my first time trying SSU I don’t know if

  • Generating ASTs is something that should be done with SSU?
  • I did the conversion to SSU correctly?
Normal code (Click triangle to expand) 
s(0,[]).

s(I,true) :-
    I >= 1.
s(I,false) :-
    I >= 1.

s(I0,if(T1,T2,T3)) :-
    I0 > 1,
    succ(I,I0),
    s(I,T1),
    s(I,T2),
    s(I,T3).

Example run:

?- s(2,Ast).
Ast = true ;
Ast = false ;
Ast = if(true, true, true) ;
Ast = if(true, true, false) ;
Ast = if(true, false, true) ;
Ast = if(true, false, false) ;
Ast = if(false, true, true) ;
Ast = if(false, true, false) ;
Ast = if(false, false, true) ;
Ast = if(false, false, false) ;
false.
SSU Code (Click triangle to expand) 
s_ssu(0,Ast) =>
    Ast = [].

s_ssu(I,Ast) =>
    I >= 1,
    Ast = true.
s_ssu(I,Ast) =>
    I >= 1,
    Ast = false.

s_ssu(I0,Ast) =>
    I0 > 1,
    succ(I,I0),
    s_ssu(I,T1),
    s_ssu(I,T2),
    s_ssu(I,T3),
    Ast = if(T1,T2,T3).

Example run:

?- s_ssu(2,Ast).
Ast = true.

The SSU code is clearly acting like a cut exist for each clause which is not what is desired but I know from generating ASTs that cuts are to be avoided if the clauses are to seen as an OR condition with backtracking.

2

The SSU mechanism is there first of all to define (usually) deterministic single-moded mappings. I used generative in the sense of DCGs that map (serialize) a term into a list. I thought generative was the correct term, but I’m not sure anymore.

1 Like
3

If the 2nd argument is uninstantiated, this can backtrack; for the SSU code you wrote, there’s no backtracking.

This will do what you want, I think:

s_ssu(I, Ast), I >= 1 => Ast = true ; Ast = false.

I’ve moved the I>=1 into a guard, so you’ll get an error if I is negative; and the Ast=true;Ast=false can backtrack. For efficiency, you might want to write it this way:

s_ssu(0, Ast) => Ast = [].
s_ssu(1, Ast), I >= 1 => true_or_false(Ast).
true_or_false(true).
true_or_false(false).

SSU allows a predicate to fail (it throws an error only if none of the heads, including guards, matches). If you want an error on failure, you should add the directive :-det(s_ssu/2).

4

@peter.ludemann Thanks.

I tried this

s_ssu(0, Ast) => Ast = [].
s_ssu(I, Ast), I >= 1 => true_or_false(Ast).
true_or_false(true).
true_or_false(false).
s_ssu(I0,Ast), I0 > 1 =>
    succ(I,I0),
    s_ssu(I,T1),
    s_ssu(I,T2),
    s_ssu(I,T3),
    Ast = if(T1,T2,T3).

It gave me a different answer but did not duplicate what the normal example did with 10 results.

̯?- s_ssu(2,Ast).
Ast = true ;
Ast = false

Jan W. gave me the information I needed which is that in this post where the idea of generators is conveyed, I was thinking of generators as noted in “The Craft of Prolog” but he noted that the word serialize is more appropriate.

The nice thing is that I will now try to use SSU where appropriate now that I tried them the first time.

5

I am still reluctant to use the SSU construct although it looks like a lot of my code is deterministic (indicated by the cut, after guards, in the body) – mainly due to portability considerations.

While i can’t see myself move away from swi-prolog – that would be inconceivable – I do want to keep the option open to get the code running in a commercial prolog implementation as well …

I am unsure if SSU could in such case simply be term/goal expanded from the → form to the :- form …