- Up - | Next >> |
Representation of the chart in the prolog database.
There is one key key decision that we have to make before starting to implement the recognizer and that is how we are going to represent the chart, and how we are going to work with it.
Now, there are various options here. For example, we could represent the chart using some sort of structured list. But there is another, more attractive, way to go: represent the chart using the Prolog database, and manipulate the chart (that is, add new edges) using the database manipulation operations. As we are going to be making heavy use of Prolog's database manipulations, let's quickly run through them and remember how they worked.
There are five database manipulation commands that we will using:
assert
retract
asserta
assertz
retractall
How are these used? Suppose we start with an empty database. So if we give the command:
?- listing.
yes
we get a yes --- and the listing (of course) is empty.
Suppose we now give this command:
?- assert(happy(mia)).
yes
It succeeds (the assert/1
commands always succeed). But what is important is not that it succeeds, but the side effect it has on the database, for if we now give the command:
?- listing.
happy(mia).
yes
we get again yes --- but now there is something in the database, namely the fact we asserted.
Suppose we then made four more assert commands:
?- assert(happy(vincent)).
yes
?- assert(happy(marsellus)).
yes
?- assert(happy(butch)).
yes
?- assert(happy(vincent)).
yes
and then ask for a listing. Then we get:
?- listing.
happy(mia).
happy(vincent).
happy(marsellus).
happy(butch).
happy(vincent).
yes
There is an inverse predicate to assert/1
, namely retract/1
. For example, if we go straight on and give the command:
?- retract(happy(marsellus)).
yes
and then list the database we get:
?- listing.
happy(mia).
happy(vincent).
happy(butch).
happy(vincent).
yes
Suppose we go on further, and say
?- retract(happy(vincent)).
yes
and then ask for a listing:
?- listing.
happy(mia).
happy(butch).
happy(vincent).
yes
Note that the first occurrence of happy(vincent) was removed. Prolog removes the first thing in the database that matches the argument of retract
.
?- retract(happy(_)).
yes
?- listing.
happy(butch).
happy(vincent).
yes
The predicate retractall/1
removes everything that matches its argument:
?- retractall(happy(_)).
yes
?- listing.
yes
If we want more control over where the asserted material is placed, there are two variants of assert, namely:
assertz
, which places stuff at the end of the database, and
asserta
, which places stuff at the beginning of the database.
Prolog puts some restrictions on what can be asserted and retracted. More precisely, other predicates are only allowed to remove or retract clauses of predicates that have been declared dynamic . So, if you want to write a predicate which asserts or retracts clauses of the form happy(mia)
, you also have to put the following statement into your file:
:- dynamic happy/1.
Database manipulation is useful when we want to store the results of queries, so that if we need to ask the same question in future, we don't need to redo the work --- we just look up the asserted fact. This technique is called `memoization', or `caching'. And of course, this `memoization' idea is the basic concept underlying chart-parsing: we want to store information about the syntactic structure we find, instead of having to re-compute it all the time.
- Up - | Next >> |