Term substitutions 
Author Message
 Term substitutions

I am looking for a way to substitute occurrences of a variable in a complex
term but still I want keep the unmodified term as well. Is there a possibilty
to achieve this without using assert/retract?

At the moment I am using code which looks something likes this:

substitute(Term, _SubstitutedTerm) :-
        % do the substitutions
        assert(substituted_term(Term)), fail.
substitute(_Term, SubstitutedTerm) ;-
        retract(substituted_term(SubstitutedTerm)).

It works allright as long as the substitutions are deterministic.

By the way: I use SICStus3.
--
---------------------------------------------------------------------------
             Stephan Tobies, Student of Computer Science
            University of Kent, UK / RWTH Aachen, Germany
-- There is much pleasure to be gained from useless knowledge (M. Minsky) -



Mon, 20 Jul 1998 03:00:00 GMT  
 Term substitutions

Quote:

> I am looking for a way to substitute occurrences of a variable in a complex
> term but still I want keep the unmodified term as well. Is there a possibilty
> to achieve this without using assert/retract?

This idea is due to Guy Barry and David Beaver. It is
contained in Cooper, Lewin and Black's code in
lecture notes for Computational Semantics, Dept. Artificial Intelligence,
University of Edinburgh.

subst(Val, Var, InTerm, OutTerm) :-
                         bagof(Term, Var^(Var=Val,Term=InTerm), [OutTerm]).

--
Sebastian Millies
Universitaet des Saarlandes    phone:    +49 (681) 302 4497
FR 8.7 / Computerlinguistik      fax:    +49 (681) 302 4351



Tue, 21 Jul 1998 03:00:00 GMT  
 Term substitutions

Quote:

>I am looking for a way to substitute occurrences of a variable in a complex
>term but still I want keep the unmodified term as well. Is there a possibilty
>to achieve this without using assert/retract?
>At the moment I am using code which looks something likes this:
>substitute(Term, _SubstitutedTerm) :-
>    % do the substitutions
>    assert(substituted_term(Term)), fail.
>substitute(_Term, SubstitutedTerm) ;-
>    retract(substituted_term(SubstitutedTerm)).
>It works allright as long as the substitutions are deterministic.
>By the way: I use SICStus3.

Guess you are looking for copy_term/2.  This is available in many modern
Prolog dialects, including SICStus3 as far as I know.

        ---- Jan
--
Jan Wielemaker



Tue, 21 Jul 1998 03:00:00 GMT  
 Term substitutions

Quote:

>This idea is due to Guy Barry and David Beaver. It is
>contained in Cooper, Lewin and Black's code in
>lecture notes for Computational Semantics, Dept. Artificial Intelligence,
>University of Edinburgh.
>subst(Val, Var, InTerm, OutTerm) :-
>                         bagof(Term, Var^(Var=Val,Term=InTerm), [OutTerm]).

This ONLY works in Prolog systems which are very careful to preserve
variables in bagof/3.  I might add that preserving variables is hard
and costly.  The recursive version I posted stands a good chance of
being faster.

I further note that the code above can be simplified to

        subst(Old, New, OldTerm, NewTerm) :-
            bagof(OldTerm, Old=Term, [NewTerm]).

If you have copy_term/2, and there is only one variable,
        copy_term(Old-OldTerm, New-NewTerm)
will do the job.

Of course, the *real* problem is to ask "why do this"?  What's the real
problem to which this is an attempted solution?

(Oh yes, how does one get those lecture notes?)

--
"conventional orthography is ... a near optimal system for the
 lexical representation of English words." Chomsky & Halle, S.P.E.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.



Fri, 24 Jul 1998 03:00:00 GMT  
 Term substitutions

Quote:

>I am looking for a way to substitute occurrences of a variable in a complex
>term but still I want keep the unmodified term as well.

Well, it should be in the library that came with your Prolog.
It's certainly in the Quintus library.

Quote:
>Is there a possibilty
>to achieve this without using assert/retract?

Not only that, it is very hard to do it WITH assert/retract.
(What about the _other_ variables?)

        % subst(Old, New, OldTerm, NewTerm)
        % unifies NewTerm with a copy of OldTerm in which
        % all subterms identical to Old have been replaced by New.

        subst(Old, New, OldTerm, NewTerm) :-
            (   OldTerm == Old ->
                NewTerm = New
            ;   var(OldTerm) ->
                NewTerm = OldTerm
            ;   functor(OldTerm, F, N),
                functor(NewTerm, F, N),
                subst_args(Old, New, OldTerm, NewTerm, N)
            ).

        subst_args(Old, New, OldTerm, NewTerm, N) :-
            (   N =:= 0 ->
                true
            ;/* N > 0 */
                arg(N, OldTerm, OldArg),
                arg(N, NewTerm, NewArg),
                subst(Old, New, OldArg, NewArg),
                M is N - 1,
                subst_args(Old, New, OldTerm, NewTerm, N)
            ).

Note that this also lets you replace constants, not just variables.
--
"conventional orthography is ... a near optimal system for the
 lexical representation of English words." Chomsky & Halle, S.P.E.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.



Fri, 24 Jul 1998 03:00:00 GMT  
 Term substitutions
: Of course, the *real* problem is to ask "why do this"?  What's the real
: problem to which this is an attempted solution?

: (Oh yes, how does one get those lecture notes?)

I am a student, yes, but it is no homework but something I need for my final
year project. It is part of a system to compile Strand into SICStus which
employs decision trees. To build the decision tree it is very handy to
instatiate some of the variables in the parsed code. (BTW, to parse I use
your tokeniser and you read predicate) Once the tree is build I thought it
would be easier to start the assemblation with uninstatiated variables but in
the meantime it turned out that it is easier to continue with the instatiated
terms...

Thank to everybody who offered help!

Stephan Tobies

--
---------------------------------------------------------------------------
             Stephan Tobies, Student of Computer Science
            University of Kent, UK / RWTH Aachen, Germany
-- There is much pleasure to be gained from useless knowledge (M. Minsky) -



Sat, 25 Jul 1998 03:00:00 GMT  
 Term substitutions
OOps. One coffee later my substitute3 looked rather silly. (Not that
I said anything false, just silly.) By the way the difference between
Richard o'Keefe's version (what I called substitute1) and my version
substitute2 can be seen even more simply by looking at the following
three tests, only the first of which both substitutes agree on:

| ?- substitute1(A,B,B,C).

C = A ?

yes
| ?- substitute2(A,B,B,C).

C = A ?

yes
| ?- substitute1(A,B,A,C).

C = A ?

yes
| ?- substitute2(A,B,A,C).

C = B ?

yes
| ?- substitute1(A,B,C,D).

D = C ?

yes
| ?- substitute2(A,B,C,D).

B = A ?

yes
| ?-
For the first example Richard's gives the right result (`right' in terms
of what the Barry-Beaver hack was originally intended for). The `value'
A is substituted for all occurences of the variable B in the expression
A, to give the resulting expression C = A. For the remaining examples
substitute1 gives incorrect behaviour.

David



Wed, 05 Aug 1998 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Term Substitutions

2. Term prcedence and stream terms

3. Has anyone written symbolic substitution subprogram?

4. ISREDIT vars substitution

5. font substitution in J v3.03b

6. Substitution in a specific field

7. substitution can't deal with multibyte?

8. bug: @^ pattern substitution

9. help with variable substitution

10. Sed like substitutions

11. tr, sed, and substitution speed

12. substitutions

 

 
Powered by phpBB® Forum Software