What is State Saving Interpreter?
State Saving Interpreter (SSI) is different from List Prolog Interpreter (LPI), which relies on SWI-Prolog's handling of choice points, which are returned to when previous choice points fail or for results of the algorithm because it manually adds, deletes and manipulates choice points itself.
The interpreter is called in any of the forms:
lucianpl(Debug,Query,Functions1,Result).
international_lucianpl([lang,Lang],Debug,Query,Functions1,Result).
international_lucianpl([lang,Lang],Debug,Query,TypeStatements,ModeStatements,Functions1,Result).
where:
- Debug, which determines whether the interpreter shows the algorithm's lines' input and output, is on or off.
Query is in the form [[n,function],[1,1,[v,c]]] for example. The prefix "n," signifies that function is the name of a predicate, to make the distinction from variables, particularly in definite clause grammars. This query is equivalent to the SWI-Prolog query function(1,1,C).
Functions1 contains the algorithm to run, for example:
[
[[n,function],[[v,a],[v,b],[v,c]],":-",
[
[[n,+],[[v,a],[v,b],[v,d]]],
[[n,+],[[v,d],1,[v,c]]]
]
]
]
This algorithm is equivalent to the SWI-Prolog algorithm:
function(A,B,C) :- D is A+B, C is D+1.
- Result is [[[[v,c], 3]]] for example, equivalent to C=3. There is one set of brackets for multiple variables and another set of brackets for multiple sets of answers, given possible non-deterministic results of the algorithm.
- Lang is the language code (from https://github.com/soimort/translate-shell), for example "en" determining which language the built-in commands referred to in the query and algorithm need to be in. The language code "en2" represents for example commands in the format "concatenate strings" instead of string_concat (without brackets), with whole words that may be easier to remember.
- TypeStatements is for example, from a different example from the previous one: [[[n,function],[[t,number],[t,number],[t,number]]]] In this case, the predicate function takes three numbers as arguments.
- ModeStatements is for example: [[[n,function],[input,input,output]]] In this case, the predicate takes two inputs and gives one output.
Like LPI, SSI loads the language database for the required language specified in the query to run the interpreter.
Like LPI, SSI can call a number of predicates or commands directly in a query. This is achieved by creating a predicate that contains the query.
Like LPI, SSI converts any Definite Clause Grammars (DCGs) into predicates by changing DCGs in the form, for example:
[[n,compound],[[v,t],[v,u]],"->",
["[",[[n,compound21],[[v,t],[v,v]]],"]",
[[n,compound213],[[v,v],[v,u]]]]]
into the form with the Prolog code:
compound(Vgp1,Vgp2,T,U):- grammar_part("[",Vgp1,Vgp3),compound21(Vgp3,Vgp4,T,V),grammar_part("]",Vgp4,Vgp5),compound213(Vgp5,Vgp2,V,U).
where grammar_part has the following definition:
grammar_part(A,B,C):- string_concat(A,C,B).
In SSI, the algorithm has line numbers added to each line to prepare for creating a finite state machine of the algorithm, where the process of creating the finite state machine requires these line numbers as they may be referred to many times in the finite state machine.
SSI finds the predicate numbers from the algorithm for creating a non-deterministic finite state machine with predicate numbers of predicates referred to in the finite state machine x algorithm***.
When creating the finite state machine, the interpreter takes the hierarchical structure of each predicate and transforms them into a linear state machine, processing them recursively with initial -2 true return and -3 false return values.
For each body structure function given, the following are the true and false return values:
[[Number,[n,"[]"],[Statements1|Statements1a]]|Statements2]:
[Statements1],[exit_function,Number],[fail_function,Number]
[Statements1a],[exit_function,Number],[fail_function,Number]
[Statements2],Return_true,Return_false
***For each body structure function, the following are state machine values for on_true, go_after, on_false and go_to_predicates (on a call):
[Number,[on_true,Statements1_number],[go_after,Statements2_number],[on_false,Return_false],[go_to_predicates,-],[n,"[]"]]
(Statements1_number etc. are the first line number in Statements1).
And so on:
[[Number1,[n,not],Statement]|Statements2]:
[Statement],[exit_function,Number1],[fail_function,Number1]
[Statements2],Return_true,Return_false
[Number1,[on_true,Statement_number],[go_after,Return_line_false],[on_false,Statements2_number],[go_to_predicates,-],[n,not]]
[[Number,[n,or],[Statements1,Statements2]]|Statements3]:
[Statements1],[exit_function,Number],Statements2_number
[Statements2],[exit_function,Number],Return_line_false
[Statements3],Return_line_true,Return_line_false
[Number,[on_true,Statements1_number],[go_after,Statements3_number],[on_false,Return_line_false],[go_to_predicates,-],[n,or]]
[[Number,[n,"->"],[Statements1,Statements2]]|Statements3]:
[Statements1],Statements2_number,Return_line_false
[Statements2],[exit_function,Number],Return_line_false
[Statements3],Return_line_true,Return_line_false
[Number,[on_true,Statements1_number],[go_after,Statements3_number],[on_false,Return_line_false],[go_to_predicates,-],[n,"->"]]
[[Number,[n,"->"],[Statements1,Statements2,Statements2a]]|Statements3]:
[Statements1],Statements2_number,Statements2a_number
[Statements2],[exit_function,Number],Return_line_false
[Statements2a],[exit_function,Number],Return_line_false
[Statements3],Return_line_true,Return_line_false
[Number,[on_true,Statements1_number],[go_after,Statements3_number],[on_false,Return_line_false],[go_to_predicates,-],[n,"->"]]
[[Number,[n,findall],[Statements1,Statements2,Statements2a]]|Statements3]:
Note: Statements1,Statements2 are not needed as they are put directly into the state machine below.
Statements2a,[findall_exit_function,Number],findall_exit_function,Number
Statements3,Return_line_true,Return_line_false
[Number,[Dbw_on_true,Statements2a_number],[Dbw_go_after,Statements3_number],[Dbw_on_false,Return_line_false],[Dbw_go_to_predicates,-],[Dbw_n,Dbw_findall],[Statements1,Statements2]]
[Number,[Dbw_n,Name1],Arguments]:
(this is a predicate call or command)
Other features of the state machine are that functional calls or commands (where variables may contain predicate names and be called as predicates) are treated as predicate names. If there is a call or command represented as a variable name, Pred_numbers2 is (*), meaning that for example the predicates to go to are determined by the interpreter when the predicate name is worked out from the variable name by the interpreter.
-1, -2 and -3 in predicates and lines in SSI predicate
If the line number is -1 in the ssi predicate then a new predicate will be called, if the line number is -2, the line or predicate has been exited successfully, and if the line number is -3 then the line or predicate has failed.
Virtual Predicates
The term virtual predicates refers to some commands (for example member and string_concat) being computed the first time they are run and choice points returning to them using the results from this first time.
Call Command
The call command (optionally including type and mode statements and its own algorithm) calls the predicate or command it is given with debug turned off and in an ssi shell, with type and mode statements, the language variable and the predicate numbers globals being returned to their previous values afterwards.
Notable bug fixes
In the case of the line number being -3 for a predicate failing, a notable bug fix is finding the link between the current and previous predicates IDs (i.e. not predicate numbers, which are the numbers of the predicates in the algorithm, but the instances of the same predicates as they are repeatedly called).
A bug fix which solved the longer test cases, including 13, 15 and 17 was defining Query2 = [|] in line number = -3 for a line failing before finding the next possible predicate or line choice point to return to, eliminating the choice points with Query2 = (-), and amazingly causing the difficult tests to pass.
To enable Functional List Prolog (FLP), a bug fix separated cases in which the call was to a predicate or command.
Nested Findall Algorithm:
(In the ssi predicate:)
If the current line is findall_exit_function
Then if there is an unfinished findall statement and a choice point since it
Then process the choice point (process_cp)
Append the value of the format vars to the findall vars
Go to the last unfinished choice point (ssi predicate)
Else end_nested_findall
Append the value of the format vars to the findall vars
If there is not an unfinished findall statement and a choice point since it
Then
Delete the recent findall statement and all choice points since it
Go to end_nested_findall
Else if there is an unfinished findall statement and a choice point since it
Then go to process_cp
Else
exit_findall_line - recursively leave findalls, finding the results on the way
Delete choice points since findall
Go to the next line in ssi
- Why is this work important? State saving interpreter is important because it manually processes choice points (if-then constructs as predicate and command calls) in findall, member and string_concat commands. It also features a grammar interpreter (which helps parse strings with hierarchical grammars), functionalism (calling predicate names contained in variables) as found in Haskell, strong types (breaking variable values down and checking them against given hierarchical data types) and hierarchical term unification (matching lists of lists, etc. of variables and values) as found in Green's List Prolog Interpreter.
- How was it done? Green used many commands, including those for hierarchical term unification from List Prolog Interpreter (https://github.com/luciangreen/listprologinterpreter) and replaced LPI's interpreter code with code that manually processed choice points (added a choice point to the stack whenever a predicate with multiple clauses or a command with multiple possible solutions was called), with cut (deletes future choice points in the predicate) and nested findall (assigns values to variables according to predicates and commands that have choice points, and can have nested findalls for lists of these results of findall) commands.
- What were the results? The test cases from LPI were all correctly computed by SSI. These included tests with grammars, functionalism, types, call, nested findall, string_concat, member and other LPI commands.
- What do those results mean? These results demonstrate that even without a complete ISO Prolog Command Set yet, SSI can run sophisticated algorithms such as a grammar interpreter (test 15, at https://github.com/luciangreen/listprologinterpreter/blob/master/lpiverify4.pl). It is noted that cut doesn't currently work in findall in LPI but does in SSI. Later SSI may be expanded to help write algorithms needed by Green.
Author: Lucian Green
SSI: https://github.com/luciangreen/SSI
Top comments (0)