Term and goal expansion feels scary. Is there an alternative?

[hurufu]

Term expansion is applied to all terms as many times as it is applicable¹ in the unspecified order which can lead to highly unpredictable behavior. Goal expansion is better, but still if term expansion is a sledge hammer then goal expansion is a regular hammer. Were ever invented mechanisms that give more control? I know that SICStus for example has additional "tag" that is useful to check which expansions were already applied.

Footnotes

1. If I get terminology right then it is correct to say that term expansion is applied until fixpoint is found. ↩

[triska]

Yes indeed, excellent points! I think it is worth to try add and gain experience with the mechanism implemented in SICStus. I think it would be possible to provide it in addition to what is currently already available in Scryer. In this way, we could try it and see how well it works for the cases needed by Scryer, and if it works well port the existing code to the new mechanism, or an even better one.

[UWN]

The problem is that SICStus' mechanism is relatively new and so far has not been adopted by another system. That is, it is present since SICStus 4 which is after 2005. Also, it seems to be as hard (voir impossible) to codify as the original mechanism since too much of side effects and the like are present.

What might be possible is to have a kind-of inline declaration. Or even unfold. But experience with unfold/fold systems has not escaped their publications. The advantage here is that we at least could formulate some guarantees that have to hold whereas the current as well as SICStus' expansion mechanism just have some opaque operational implementation which in turn could favor some ad hoc expansions for languages that only work with such expansions.

[hurufu]

Good to know that there is research about this! I also thought a little bit about expansion mechanism and came up with such observations:

There are 2 types of expansions:

1. expansions that don't change semantics of expanded terms (like in library(reif)). Mostly used for performance.
2. expansions that do change semantics. Consider DCG as an example. Predicate (-->)/2 on its own doesn't have any useful meaning. For example hello --> "hello". is as good as foo(hello, "hello")., but expansions actually convert it to meaningful predicates.

Those two type must be treated very differently, for example 1st one is optional, but 2nd isn't.

Regarding "inline" and "unfold", there is an idea that is floating in my mind about some sort of stencils for goal expansion, because I've found that a lot of goal expansion is repetitive, so it would be interesting to mark some predicates to be "inlined" et voilà your predicate is automatically inlined. Or you can apply some other useful expansions to it... But at this point it is just an ideas, regarding my goal expansion work I plan just fix it without introducing anything controversial.

[UWN]

There are more such expansions to distinguish. Consider clpz. There it happens that pure Prolog programs are transformed (internally) to impure ones using var/1 and the like. So this would be a very low level of transformation, since the resulting program can no longer be used for declarative diagnosis.

[jjtolton]

Term expansion is applied to all terms as many times as it is applicable1 in the unspecified order which can lead to highly unpredictable behavior. Goal expansion is better, but still if term expansion is a sledge hammer then goal expansion is a regular hammer. Were ever invented mechanisms that give more control? I know that SICStus for example has additional "tag" that is useful to check which expansions were already applied.

Footnotes

1. If I get terminology right then it is correct to say that term expansion is applied until fixpoint is found. ↩

can you possibly provide some examples of what you mean...?

[hurufu]

Maybe somebody will find it useful it is a (simplified) call graph for loader.pl module. The interesting observation is that whole goal expansion code is connected to the rest of compilation via very thin interface predicate.

Legend:

• Green – omitted predicate
• Magenta - exported predicate
• Grey, Green+Grey, Magenta+Grey - duplicated predicate (like catch/3 it is used in many places and every use case has it's own copy in a graph, because otherwise it would bee unreadable)
• Dotted – simplified manually
• Blue – a variable can be any predicate
• ⚫ – always false
• ⚡ – explicitly throws an error

Call graph is partially generated and then manually adjusted to make it readable, "not interesting" predicates were removed manually, to make it readable.

[jjtolton]

omg how did you make that 😍

[hurufu]

I wrote a Prolog program, that uses read_term to read sources and then finds paths between different predicates and handles a tone of special cases... then it is converted to dot format and then I manually adjust it until call graph is "readable".

[jjtolton]

Thank you for that extremely detailed technical explanation 🤣

[hurufu]

Generating call graph is quite simple, but the devil is in the details – it is very hard to make a useful call graph. I will post sources someday, when code will be ready...

[hurufu]

I was recently reading sources from Fifth Generation Computer Systems project, and I found that KL1 language actually supported some sort of macros using (#)/2 term. This is how macro definitions look like:

wrap#( rational#compose(Real,Image,Out)     ) => wrap#( Out= complex(Real,Image) ).
wrap#( rational#complex(Xin)                ) => wrap#( Xin= complex(_,_)  ) .
wrap#( rational#complex(Xin,Real,Image)     ) => wrap#( Xin= complex(Real,Image)  ) .
wrap#( rational#real(Xin,Real)              ) => wrap#( Xin= complex(Real,_)  ) .
wrap#( rational#image(Xin,Image)            ) => wrap#( Xin= complex(_,Image)  ) .
wrap#( rational#compose(S,Numer,Denom,Out)  ) => wrap#( Out= real(S,Numer,Denom) ).
wrap#( rational#rational(Xin)               ) => wrap#( Xin= real(_,_,_) ) .
wrap#( rational#rational(Xin,S,Numer,Denom) ) => wrap#( Xin= real(S1,Numer,Denom), S := S1/\1 ) .
wrap#( rational#numer_denom(Xin,Numer,Denom)) => wrap#( Xin= real(_,Numer,Denom) ) .
wrap#( rational#sign(Xin,S)                 ) => wrap#( Xin= real(S1,_,_), S := S1/\1 ) .
wrap#( rational#numer(Xin,Numer)            ) => wrap#( Xin= real(_,Numer,_) ) .
wrap#( rational#denom(Xin,Denom)            ) => wrap#( Xin= real(_,_,Denom) ) .

I don't know the details, but I can see how it might be implemented from the usages. It looks like during compilation they find occurrences of (#)/2 like rational#numer_denom(Yin,Ny,Dy) and given first argument is a macro name and second is a macro parameter they replace it according to definition.

[hurufu]

Sources main: https://www.ueda.info.waseda.ac.jp/AITEC_ICOT_ARCHIVES/ICOT/Museum/IFS/HomePage-E.html
Actually where I took macros: https://www.ueda.info.waseda.ac.jp/AITEC_ICOT_ARCHIVES/ICOT/Museum/IFS/abst/063.html

[hurufu]

FYI, I have a PoC of a macro system inspired by KL1 in my fork (usage example).

With this macro system you can easily implement: enums, conditional compilation, predicate inlining, etc.

[hurufu]

Important note: My PoC doesn't yet support subterm expansion for example my_predicate(tel#cr) isn't expanded to my_predicate([13]) (as it is done in KL1) there is just a dummy foo/1 predicate to show how it would look like if subterm expansion would've been a thing. Currently there is no elegant way to expand every subterm of every term, but as a workaround you can do:

C = tel#cr,
my_predicate(C)

and it will be expanded to:

C = [13],
my_predicate(C)

There is code that traverses every subterm in loader.pl, but it isn't exposed and is hard to reuse.