How to identify wasteful representations of Prolog

What is the Prolog predicate that helps to show wasteful representations of Prolog terms?

Supplement

In a aside of an earlier Prolog SO answer, IIRC by mat, it used a Prolog predicate to analyze a Prolog term and show how it was overly complicated.

Specifically for a term like

[op(add),[[number(0)],[op(add),[[number(1)],[number(1)]]]]]

it revealed that this has to many [].

I have searched my Prolog questions and looked at the answers twice and still can't find it. I also recall that it was not in SWI-Prolog but in another Prolog so instead of installing the other Prolog I was able to use the predicate with an online version of Prolog.

If you read along in the comments you will see that mat identified the post I was seeking.

What I was seeking

I have one final note on the choice of representation. Please try out the following, using for example GNU Prolog or any other conforming Prolog system:

| ?- write_canonical([op(add),[Left,Right]]). 
'.'(op(add),'.'('.'(_18,'.'(_19,[])),[]))

This shows that this is a rather wasteful representation, and at the same time prevents uniform treatment of all expressions you generate, combining several disadvantages.

You can make this more compact for example using Left+Right, or make all terms uniformly available using for example op_arguments(add, [Left,Right]), op_arguments(number, [1]) etc.

Evolution of a Prolog data structure

If you don't know it already the question is related to writing a term rewriting system in Prolog that does symbolic math and I am mostly concentrating on simplification rewrites at present.

Most people only see math expressions in a natural representation

x + 0 + sin(y)

and computer programmers realize that most programming languages have to parse the math expression and convert it into an AST before using

add(add(X,0),sin(Y))

but most programming languages can not work with the AST as written above and have to create data structures See: Compiler/lexical analyzer, Compiler/syntax analyzer, Compiler/AST interpreter

Now if you have ever done more than dipped your toe in the water when learning about Prolog you will have come across Program 3.30 Derivative rules, which is included in this, but the person did not give attribution.

If you try and roll your own code to do symbolic math with Prolog you might try using is/2 but quickly find that doesn't work and then find that Prolog can read the following as compound terms

 add(add(X,0),sin(Y))

This starts to work until you need to access the name of the functor and find functor/3 but then we are getting back to having to parse the input, however as noted by mat and in "The Art of Prolog" if one were to make the name of the structure accessible

 op(add,(op(add,X,0),op(sin,Y)))

now one can access not only the terms of the expression but also the operator in a Prolog friendly way.

If it were not for the aside mat made the code would still be using the nested list data structure and now is being converted to use the compound terms that expose the name of the structure. I wonder if there is a common phrase to describe that, if not there should be one.

Anyway the new simpler data structure worked on the first set of test, now to see if it holds up as the project is further developed.

Try it for yourself online

Using GNU Prolog at tutorialspoint.com enter

:- initialization(main).
main :- write_canonical([op(add),[Left,Right]]).

then click Execute and look at the output

sh-4.3$ gprolog --consult  file main.pg  
GNU Prolog 1.4.4 (64 bits)  
Compiled Aug 16 2014, 23:07:54 with gcc  
By Daniel Diaz  
Copyright (C) 1999-2013 Daniel Diaz  
compiling /home/cg/root/main.pg for byte code...  
/home/cg/root/main.pg:2: warning: singleton variables [Left,Right] for main/0  
/home/cg/root/main.pg compiled, 2 lines read - 524 bytes written, 9 ms  
'.'(op(add),'.'('.'(_39,'.'(_41,[])),[]))| ?-

Clean vs. defaulty representations

From The Power of Prolog by Markus Triska

When representing data with Prolog terms, ask yourself the following question:

Can I distinguish the kind of each component from its outermost functor and arity?

If this holds, your representation is called clean. If you cannot distinguish the elements by their outermost functor and arity, your representation is called defaulty, a wordplay combining "default" and "faulty". This is because reasoning about your data will need a "default case", which is applied if everything else fails. In addition, such a representation prevents argument indexing, and is considered faulty due to this shortcoming. Always aim to avoid defaulty representations! Aim for cleaner representations instead.

回答1:

Please see the last part of:

https://stackoverflow.com/a/42722823/1613573

It uses write_canonical/1 to display the canonical representation of a term.

This predicate is very useful when learning Prolog and helps to clear several misconceptions that are typical for beginners. See for example the recent question about hyphens, where it would have helped too.

Note that in SWI, the output deviates from canonical Prolog syntax in general, so I am not using SWI when explaining Prolog syntax.

回答2:

You could also programmatially count how many subterms are a single-element list using something like this (not optimized);

single_element_list_subterms(Term, Index) :-
    Term =.. [Functor|Args],
    (   Args = []
    ->  Index = 0
    ;   maplist(single_element_list_subterms, Args, Indices),
        sum_list(Indices, SubIndex),
        (   Functor = '.', Args = [_, []]
        ->  Index is SubIndex + 1
        ;   Index = SubIndex
        )
    ).

Trying it on the example compound term:

| ?- single_element_list_subterms([op(add),[[number(0)],[op(add),[[number(1)],[number(1)]]]]], Count).

Count = 7

yes
| ?-

Indicating that there are 7 subterms consisting of a single-element list. Here is the result of write_canonical:

| ?- write_canonical([op(add),[[number(0)],[op(add),[[number(1)],[number(1)]]]]]).
'.'(op(add),'.'('.'('.'(number(0),[]),'.'('.'(op(add),'.'('.'('.'(number(1),[]),'.'('.'(number(1),[]),[])),[])),[])),[]))

yes
| ?-