Manage multiple matching in prolog

0
votes

Suppose you get in input a description of a graph, something like "A is near B" and you want to update your knowledge base.

Using Prolog I've decided to use this solution:

:- dynamic edge/2.

store(Desc):- Desc=[A,is,near,B],
          assert(edge(A,B)),
          write(A-B).


store(Desc):- Desc=[A,is,near,B,that,is,near,C],
          write(A-B),nl,
          write(B-C),
          assert(edge(A,B)),
          assert(edge(B,C)).

I'd like to extend the parsing to potential infinite sentences, like: '1 is near 2 that is near 3 that is near 4 etc', so what I'd like to do is something like (Idea expressed in pseudocode-like-notation):

  procedure store(Sentence)
  begin
  foreach 'X is near Y' in Sentence  assert edge(X,Y).
  foreach 'X that is near Y' in Sentence assert edge(X,Y).
  end

How can I achieve this in Prolog?

2
prolog
You should consider writing a predicate like extract_edges(Sentence, Edges) first instead of working directly with the database. It would be easier to implement and easier to trace / debug also. - Tudor Berariu

2 Answers

1
votes

First, you can do pattern matching and unification in a single step. Second, you need to make your predicate recursive. Consume the first words in that sentence (i.e. the first elements of the list) and let the recursive goal handle the rest:

store([A, is, near, B]):-
    assert_edge(A, B).
store([A, is, near, B, that|Other]):-
    assert_edge(A, B),
    store([B|Other]).

assert_edge(A, B):-
    ...

Another way to do that is to use setof/3 and a built-in predicate for lists like append/3:

?- L = [a, that, is, near, b, that, is, near, c, that, is, near, d],
   setof(A-B, L1^L2^append(L1,[A, that, is, near, B|L2], L), Edges).

L = [a, that, is, near, b, that, is, near, c|...],
Edges = [a-b, b-c, c-d].
1
votes

A DCG approach could work well here:

store --> [A], is_near(B), { assertz(edge(A, B)) }, and_near(B).

and_near(_) --> [].
and_near(A) --> [that], is_near(B), { assertz(edge(A, B)) }, and_near(B).

is_near(A) --> [is, near, A].

store(L) :- phrase(store, L).

Then you'd use the query:

| ?- store([a, is, near, b, that, is, near, c, that, is, near, d]).

true ? ;

no
| ?- listing(edge).

% file: user_input

edge(a, b).
edge(b, c).
edge(c, d).

yes
| ?-

You can also use a DCG to extract to a list:

extract([edge(A,B)|Edges]) --> [A], is_near(B), and_near(B, Edges).

and_near(_, []) --> [].
and_near(A, [edge(A,B)|Edges]) --> [that], is_near(B), and_near(B, Edges).

is_near(A) --> [is, near, A].

extract(L, Edges) :-
    phrase(extract(Edges), L).

| ?- extract([a,is,near,b,that,is,near,c,that,is,near,d], Edges).

Edges = [edge(a,b),edge(b,c),edge(c,d)] ? a

no
| ?-