| << Prev | - Up - |
Implementation of finite state transducers in Prolog.
In implementing finite state transducers in Prolog, we will follow the same strategy that we used for FSAs: we represent an FST as a static data structure that other programs manipulate.
Here is how we represent our first transducer, the a to b translator (found in a2b.pl ).
:- op(250,xfx,:).
start(a2b,1).
final(a2b,1).
trans(a2b,1,1,a:b). To be able to write a:b as the label of the arc, we have to define : as an infix operator as is done by the operator definition.
Our second transducer, the a doubler (adoubler.pl ), looks like this in Prolog representation:
:- op(250,xfx,:).
start(adoubler,1).
final(adoubler,1).
trans(adoubler,1,2,a:a).
trans(adoubler,2,1,'#':a).
Now, we need a program that can manipulate these data structures and carry out the transduction. We will extend recognize1 from Section 2.1.1 to work as a transducer (see trans.pl ).
The base case is that both tapes are empty and the FSA is in a final state. In Prolog:
transduce(A,Node,[],[]) :-
final(Node). In the recursive case, we make a transition from one node to another which is licensed by some trans definition in the database. As in the last chapter we define a predicate traverse/6 to check that the transition is indeed licensed.
transduce(A,Node1,Tape1,Tape2) :-
trans(Node1,Node2,Label),
traverse(A,Label,Tape1,NewTape1,Tape2,NewTape2),
transduce(A,Node2,NewTape1,NewTape2).
traverse(A,L1:L2,[L1|RestTape1],RestTape1,[L2|RestTape2],RestTape2). Finally, we define the following driver predicate testtrans/3. It can be called with both arguements instantiated, only one of them instantiated, or both uninstantiated -- depending on which mode we want to use the transducer in.
testtrans(A,Tape1,Tape2) :-
start(Node),
transduce(A,Node,Tape1,Tape2).
We can use this program to transduce as to bs with our first transducer. To be able to use the second transducer, the a doubler, as well, we need a program that can handle transitions involving jumps. What do we have to change for that? Well, the only thing that changes is the way that the tapes are treated when making a transition. This is taken care of by the traverse predicate and this is all we have to adapt. (Remember that when extending the recognizer of the last chapter to handle jump arcs, we also only changed the traverse predicate.)
So, what are the possibilites how a tape can be affected by a transition? There are four:
We have to jump on both tapes.
We have to jump on the first but not on the second tape.
We have to jump on the second but not on the first tape.
We have to jump on neither tape (this is what the clause of traverse/6 given above does).
The Prolog definition of traverse therefore has four clauses:
traverse('#':'#',Tape1,Tape1,Tape2,Tape2).
traverse('#':L2,Tape1,Tape1,[L2|RestTape2],RestTape2).
traverse(L1:'#',[L1|RestTape1],RestTape1,Tape2,Tape2).
traverse(L1:L2,[L1|RestTape1],RestTape1,[L2|RestTape2],RestTape2).| << Prev | - Up - |