Prolog Assignment
Sample testing code is in app/tester.pl.
Solution code is expected to be in lib/due190307.pl .
Note: all the predicates defined in this file start with the prefix test_ you are not allowed to reference any of these predicates in your own solution. Ie test_ cannot be used in the lib/due190307.pl file (even in a comment or string constant).
Table of Contents for this document: 1) Running the assignment
2) Automating the testing of your prolog 3) New Regular Expression Notation
4) Phase 1 tester.pl code
4.1) Preliminary Comments on Task 4.2) The Testing Code
5) PHASE 1 Summary
6) Hint on Using Prolog with Phase 1 of this assignment
1) Running the assignment
One brings together the testing and solution by typing:
gprolog –consult lib/due190307.pl –consult app/tester.pl
This puts you in the prolog interpreter where you can explore your code.
At the final stage of checking my phase 1 solution, a session with the interpreter might look like:
| ?- test_count_successful_tests(N). test_count_successful_tests(N).
N=2
(3 ms) yes
| ?- test_example_run_tests(S). test_example_run_tests(S).
S = [[97],letter concat (letter star),my_succeed] ? ; ;
S = [[97],letter concat (letter star),my_succeed] ?
(2 ms) yes
| ?- exit.
exit.
uncaught exception: error(existence_error(procedure,exit/0),top_level/0) | ?- quit.
quit.
uncaught exception: error(existence_error(procedure,quit/0),top_level/0) | ?- C-c C-c
Prolog interruption (h for help) ? e
e
2) Automating the testing of your prolog
Of course, hopefully by now you know the benefits of being able to automate your testing rather than retype it over and over. The following works:
echo ‘test_count_successful_tests(A).’ | gprolog –consult lib/due190307.pl – -consult app/tester.pl
I found the following predicates useful while testing and so provide them to you:
• test_count_successful_tests(N) which tells you how many of your tests succeeded
• test_example_run_tests(Status) which shows you which tests succeeded
• test_debug_run_tests(Status) which shows you which tests succeeded and what the NFA
was that you built as well as what the input string was transformed to (this latter being done by my provided code).
In the test file, I had to write something that would match a string against an NFA.
• test_nfa_match(String, nfa(start(State),X,Y)) matches a string against an NFA
• test_nfa_match_helper(String, nfa(start(State),X,Y), State) makes test_nfa_match easier
to write by adding a specification of which state to start the match from (so matching
substrings is like matching the whole string, just with different starts)
• test_categorize converts strings to lists of categories
• test_category converts a character to a category
• test_category_helper converts all the characters to categories except those going to the
category undefined
The actual test cases are presented like:
test_case(“a”,letter concat (letter star), my_succeed).
In the test_case , my_fail is used when the match should fail and my_succeed is used when the match should succeed.
3) New Regular Expression Notation
You will notice that the regular expression notation is as follows. This is because Prolog handles the conversion from infix notation to a tree for us. Consider the following:
unix: cat directives.pl
:- op(300, yfx, ‘concat’).
:- op(500, yfx, ‘or’).
:- op(400, yf, ‘plus’).
:- op(400, yf, ‘star’).
:- op(400, yf, ‘optional’).
unix: gprolog –consult directives.pl GNU Prolog 1.4.5 (64 bits)
…
| ?- X = letter concat ( letter
X = letter concat ( letter star
no
| ?- X = letter concat ( letter X = letter concat ( letter star
X = letter concat (letter star) Y = letter
Z = letter star
yes
| ?- X = letter concat ( letter X = letter concat ( letter star
X = letter concat (letter star) Y = letter
Z = letter
(1 ms) yes
| ?- X = letter concat ( letter X = letter concat ( letter star
W = letter
X = letter concat (letter star) Y = letter
Z = letter star
yes
star ), X = concat(Y,Z).
), X = concat(Y,Z).
star ), X = concat(Y,star(Z)). ), X = concat(Y,star(Z)).
star ), X = concat(Y,Z), Z = star(W). ), X = concat(Y,Z), Z = star(W).
star ), X = concat(Y).
), X = concat(Y).
So, basically, using the ops directives in directives.pl (which are also in the provided tester.pl), when I type
letter concat ( letter star )
prolog is automatically converting it into a tree notation of
concat(letter, star(letter))
The prolog tree notation looks a lot like the prefix lisp notation except that the operator is just before the associated parenthesis contained parameters rather than being the first item in the parenthesis list. In prolog language this is a complex term. In prolog notation being derived from infix, concat takes two parameters. However, prolog also handles associativity of binary operators so
| ?- X = a concat b concat c, X = concat(Y,Z). X = a concat b concat c, X = concat(Y,Z).
X = a concat b concat c Y = a concat b
Z=c
(1 ms) yes
| ?- X = a concat b concat c, X = concat(concat(A,B),C).
X = a
A=a B=b C=c X = a
yes | ?-
You can use parenthesis as you normally would in the infix version and they will disappear in the complex term version (although they will have, in the process, guided the shape of the complex term).
The operators to be supported in the assignment are:
:- op(300, yfx, ‘concat’) this is . in the Ruby assignment restricted to binary form (binds tighter than other operators)
:- op(500, yfx, ‘or’) this is | in the Ruby assignment restricted to binary form (binds looser than other operators)
:- op(400, yf, ‘plus’) this is + in the Ruby assignment as a suffix operator binding between concat and or
:- op(400, yf, ‘star’) this is * from the textbook as a suffix operator binding between concat and or
:- op(400, yf, ‘optional’) this is ? from the textbook as a suffix operator binding between concat and or
concat b concat c, X = concat(concat(A,B),C).
concat b concat c
The leaves of our regular expressions in this assignment will be
epsilon
letter
digit
white_space (new handling ” ” and “\n”) question_mark
exclamation_mark
period
comma
colon
semicolon (new handling “;”) minus_sign
plus_operator binary_operators left_parenthesis right_parenthesis
equal
less_than
greater_than
undefined
Prolog’s operator notation takes care of creating trees for regular expressions for us, so phase 1 starts with considering how to convert a regular expression tree to an NFA. Testing is done by seeing if the resulting NFAs except the same strings as the regular expressions would have.
4) Phase 1 tester.pl code Included in the .zip file.
4.1) Preliminary Comments on Task
% % % % %
% % % % % % %
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
note:
all the predicates defined in this file start with the prefix test_ you are not allowed to reference any of these predicates in your own solution. if test_ appears anywhere in your lib/due190307.pl file (even in a comment or string constant), it will be assumed you are trying to compromise the testing process and marked accordingly.
A scanner will be defined as a list of scanner terms
where a scanner term is scanner(Token, RegularExpression)
a
a
Start is a state
States is a list of state terms Transitions is a list of next terms
state term has the form state(Name, Status) where Name is a name given the state
Status is either
not_accepting if it is not an accepting state
Token if it is an accepting state, when which Token
has been matched at this point. next term has the form next(From, To, Category)
where From is a state term in States
To is a state term in States
Category is a character category or the term epsilon
the categories will be
letter
digit
white_space
question_mark exclamation_mark
period
comma
colon
semicolon
minus_sign
plus_operator binary_operators for * / % ^ left_parenthesis right_parenthesis
equal
less_than
greater_than
undefined
where
where
Token is the name the scanner returns if RegularExpression matches an input string. if there are multiple such matches, the Token in the first scanner term in the list to match is the one that should match.
RegularExpression is a regular expression term defined later.
from NFA definition in text:
corresponds to term nfa(Start, States, Transitions)
the regular expression operators will be:
% concat for concatenation as a binary infix operator
% plus for one or more copies of its parameter as a postfix operator
% star for zero or more copies of its parameter as a postfix operator
% opertional for zero or one copies of its parameter as a postfix operator % or for from one or the other as a binary infix operator
% (they are suffixed with underscore to avoid conflicts with existing operators)
These were notes I wrote before doing the implementation and so have drifted a bit from the actual testing code, however, the nfa term still has three parts:
o The first part however, is not a State, but the term start(State) where State is filled in with the `name’ of the start state. This structure is used by my test_nfa_match predicate to find the start of the automata that is being matched against.
o The States list maps nicely to the book definition of an NFA. However, my testing code never checks directly to see what you put in there. Keeping a list of state(Name,Status) values there would work fine, but it is over-specification in the sense that you could store other structures there that could also work fine. The main thing is that somewhere there has to be the information that allows your accepting predicate to tell if a given state is an accepting state or not. And in phase 2 (and 3), for the accepting states, you also need to know what token type they are accepting.
o The transitions() structure matters and is used by test_nfa_match_helper to explore paths thru the nfa.
o As to the structure of a state name, all it has to be is something that = works with. In an instance of an nfa, I would expect it to be grounded, i.e., having no free variables.
4.2) The Testing Code
:- op(300, yfx, ‘concat’). :- op(500, yfx, ‘or’).
:- op(400, yf, ‘plus’).
:- op(400, yf, ‘star’).
:- op(400, yf, ‘optional’).
test_categorize([], []).
test_categorize([H_in|T_in], [H_result| T_result]) :- test_category(H_in, H_result), test_categorize(T_in, T_result).
test_category(X,Y) :- test_category_helper(X,Y). test_category(X,undefined) :- \+ test_category_helper(X,_).
test_category_helper(Char, letter) :- [ACode] = “a”, ACode @=< Char, [ZCode] = "z", Char @=< ZCode.
test_category_helper(Char, letter) :- [ACode] = "A", ACode @=< Char, [ZCode] = "Z", Char @=< ZCode.
test_category_helper(Char, digit) :- [ZeroCode] = "0", ZeroCode @=< Char, [NineCode] = "9", Char @=< NineCode.
test_category_helper(Char, white_space) :- [Char] = " ". test_category_helper(Char, white_space) :- [Char] = "\n". test_category_helper(Char, question_mark) :- [Char] = "?". test_category_helper(Char, exclamation_mark) :- [Char] = "!". test_category_helper(Char, period) :- [Char] = ".". test_category_helper(Char, comma) :- [Char] = ",". test_category_helper(Char, colon) :- [Char] = ":". test_category_helper(Char, semicolon) :- [Char] = ";". test_category_helper(Char, minus_sign) :- [Char] = "-". test_category_helper(Char, plus_operator) :- [Char] = "+". test_category_helper(Char, binary_operators) :- [Char] = "*". test_category_helper(Char, binary_operators) :- [Char] = "/". test_category_helper(Char, binary_operators) :- [Char] = "%". test_category_helper(Char, binary_operators) :- [Char] = "^". test_category_helper(Char, left_parenthesis) :- [Char] = "(". test_category_helper(Char, right_parenthesis) :- [Char] = ")". test_category_helper(Char, equal) :- [Char] = "=". test_category_helper(Char, less_than) :- [Char] = "<". test_category_helper(Char, greater_than) :- [Char] = ">“.
test_count_successful_tests(N) :- setof(A, test_example_run_tests(A), L), length(L,N).
test_example_run_tests(Status) :-
test_case(InputString, RegularExpression, my_succeed),
Result = my_succeed, regular_expression_to_nfa(RegularExpression, NFA), test_categorize(InputString, TransformedString), test_nfa_match(TransformedString, NFA),
Status = [InputString, RegularExpression, Result].
test_example_run_tests(Status) :-
test_case(InputString, RegularExpression, my_fail),
Result = my_fail, regular_expression_to_nfa(RegularExpression, NFA), test_categorize(InputString, TransformedString), \+ test_nfa_match(TransformedString, NFA),
Status = [InputString, RegularExpression, Result].
test_debug_run_tests(Status) :-
test_case(InputString, RegularExpression, my_succeed),
Result = my_succeed, regular_expression_to_nfa(RegularExpression, NFA), test_categorize(InputString, TransformedString), test_nfa_match(TransformedString, NFA),
Status = [InputString, RegularExpression,
TransformedString, NFA, Result].
test_debug_run_tests(Status) :-
test_case(InputString, RegularExpression, my_fail),
Result = my_fail, regular_expression_to_nfa(RegularExpression, NFA), test_categorize(InputString, TransformedString), \+ test_nfa_match(TransformedString, NFA),
Status = [InputString, RegularExpression,
TransformedString, NFA, Result].
test_nfa_match(String, nfa(start(State),X,Y)) :- test_nfa_match_helper(String, nfa(start(State),X,Y), State).
test_nfa_match_helper(“”, NFA, State) :- epsilon_closure(State, NFA, Closure),
member(PossibleFinish, Closure), accepting(NFA, PossibleFinish).
test_nfa_match_helper([H|T], nfa(X,Y, transitions(Transitions)), State) :- member(next(State, NextState, H), Transitions), test_nfa_match_helper(T, nfa(X,Y, transitions(Transitions)), NextState).
test_nfa_match_helper(String, nfa(X,Y,transitions(Transitions)), State) :- epsilon_closure(State, nfa(X,Y,transitions(Transitions)), Closure), member(NextState, Closure),
NextState \= State,
member(next(State, NextState, epsilon), Transitions),
test_nfa_match_helper(String, nfa(X,Y,transitions(Transitions)), NextState).
test_case(“a”,letter concat (letter star), my_succeed). test_case(“a”,letter concat letter star, my_fail).
% test_case(“a”,(letter concat letter) star, my_fail).
% identical to previous test case after operator processing and so doesn’t % show up as distinct in count of tests passed.
5) PHASE 1 Summary
What you are writing in due190307.pl for phase 1 is the definition of the predicates
regular_expression_to_nfa(RegularExpression, NFA) epsilon_closure(State, NFA, Closure) accepting(NFA, State)
The value of RegularExpression will be bound before the predicate is invoked by the regular expression notation described earlier. Again, what your definitions are supposed to do is to cause my code to do what it is supposed to do, i.e., successfully match on the NFA what would successfully match the RegularExpression and fail to match the NFA what would fail to match the RegularExpression.
accepting is true if State is an accepting state in NFA.
Here the restrictions are on the shape of the complex term that represents an NFA. Specifically, it looks like:
nfa(start(State),Y,transitions(Transitions))
where Transitions is a list of next terms so that I can do:
member(next(State, NextState, H), Transitions) member(next(State, NextState, epsilon), Transitions)
and Closure that epsilon_closure produces is also a list that supports:
member(NextState, Closure)
6) Hint on Using Prolog with Phase 1 of this assignment
• Note, prolog builtins used in the test code are: • :-
•,
• op
•=
• \=
• []
• [|]
• [,]
• % comments
• \+
• “string”
• @=<
• setof
• length
member
• Note the prolog builtins used in my solution code for phase 1 were:
• :- •, •_
•=
• \=
• []
• [,]
• [|]
• is
• +
• 1
• append
• sort
• member
evaluates complex term
if functor of complex term evaluates to addition evaluates to 1
findall sortof that leaves in duplicates
• The builtins are defined in http://www.gprolog.org/manual/gprolog.html . A lot of other stuff is in there too. Most of it bad for an assignment like this one, but useful for other more complicated tasks. Remember prolog is about separating logic from control and in this assignment there should be very little reason to specify control (hence most of the classic impure parts of prolog are not listed among the builtins above.