Term_expansion; order of execution with DCG

Help!
1

Hello,

If in a module I create some term_expansion/2 expansions that contain DCG rules, will that work? Does term_expansion get called repeatedly until, as I understand it, a fix(ed?)-point is reached i.e. the expansion is complete?

This is an area I have only dabbled with many months ago just to get a feel for the concept but now I return with the aim of creating some kind of DSL that can hopefully allow me to express the syntactic requirements of each reserved word in my language rather than having to crack out all the code. The language has over 80 instructions, each with its own rules and forms and I want to leverage as much power as I can get out of the Prolog machine.

I have completed the AST syntax/parse/error checking for a good half-dozen keywords and now the commonalities are beginning to make themselves known and I’d like to capitalise on that.

Any references, examples etc would be great. I have all the major Prolog books, and one of them (I forget which) has an old but understandable DCG implementation which I studied.

Thank you,
Sean.

2

The DCG rules are pre-defined as something like system:term_expansion(Head-->Body, ...).).

When a file is consulted, term_expansion/2 is called on all terms repeatedly until there’s no change (see the description of expand_term/2).

As a trivial example:

term_expansion(foo(X), (foo(X) --> [X], bar(X))).

foo(a). % expanded to foo(a) --> [a], bar(X).
bar(X) --> [X].

and look at the resulting predicates:

?- listing(foo).
foo(a, [a|A], B) :-
    bar(a, A, B).

?- listing(bar).
bar(X, [X|A], A).

If you want something more powerful than DCGs, you might be interested in EDCGs and DCTGs (the latter is described in Logic Grammars by Dahl&Abramson, with an implementation here).

3

Hmmm. Where do you read this? It is not correct, so if you found this somewhere it should be fixed. I think the description of expand_term/2 gives the overall picture. The term expansion mechanism is a pipeline of different translation steps, each of which performs just one rewrite step. The term_expansion/2 hooks are also handled as a pipeline. This starts at the module being loaded, followed by the user and finally the system module.

In contrast, expand_goal/2 is also a pipeline following the same module hierarchy, but each step is executed until fixed point is reached.

2 Likes
4

Thanks Peter!
I checked out EDCG many months back but I have already rolled my own solution for that, it was good learning material though!

Thank you for confirming my thoughts about the repetition etc. I missed expand_term/2 and expand_goal/2 in the excitement!
what a :lemon:

I was deliberating as to the exact -reason- to use term_expansion/2 instead of just creating common code and if you have any advice on that I’ll listen!

Thanks :+1:

5

Oops; I got expand_term/2 mixed up with expand_goal/2.

Back to OP’s question: you can always do something like the following (although it’s not necessary for handling DCGs) to recursively apply term expansion to what you generate, although - unlike expand_goal/2 - you’re responsible for it not getting into an infinite recursion

term_expansion(foo(X), Expanded) :-
    expand_term((foo(X) --> [X], bar(X)), 
                Expanded).