Prolog predicates work in different ways depending on how you use them. A simple example is the append predicate. One may say that append is used to get the result of appending two lists. For example:
?- append([1,2,3], [4,5,6], NewList).
NewList = [1, 2, 3, 4, 5, 6].But we can also use append to get the prefix of a list given a suffix.
?- append(Prefix, [5,6], [1,2,3,4,5,6]).
Prefix = [1, 2, 3, 4] ;Or we can get all the possible combinations of lists that can concatenated produce a specified list:
?- append(First, Second, [1,2,3,4,5,6]).
First = [],
Second = [1, 2, 3, 4, 5, 6] ;
First = [1],
Second = [2, 3, 4, 5, 6] ;
First = [1, 2],
Second = [3, 4, 5, 6] ;
First = [1, 2, 3],
Second = [4, 5, 6] ;
First = [1, 2, 3, 4],
Second = [5, 6] ;
First = [1, 2, 3, 4, 5],
Second = [6] ;
First = [1, 2, 3, 4, 5, 6],
Second = [] ;This is a powerful concept that is accomplished by Prolog's execution mecanism which involves unification, resolution and backtracking. This mechanism tries to find a way to bind free variables so the goal makes sense.
Recently, I found an example of this behavior while writing some quick experiments with a JavaScript parser I'm working on (which deserves a separate post).
It all started while trying to define a predicate to translate from a JavaScript switch statement to an equivalent sequence of if/else statements. An example of this conversion it's take the following statement:
switch(myVar) {
case 1:
print('one');
break;
case 2:
print('two');
break;
}And convert it to something like:
if (myVar == 1) {
print('one');
} else if (myVar == 2) {
print('two');
}A simple version of a predicate that performs this conversion is the following:
switch_if(js_switch(js_identifier(Variable, _),
Cases,
_),
IfStat) :-
switch_if_cases(Variable, Cases, IfStat).
switch_if_cases(Variable,
[js_case(Value, Body, _)|Rest],
js_if(Comparison,
js_block(NoBreakBody, _),
RestIf,
_)) :-
value_comparison(Comparison, Variable, Value),
body_with_no_break(Body, NoBreakBody),
switch_if_cases(Variable, Rest, RestIf).
switch_if_cases(Variable,
[js_default( Body, _)],
js_block(NoBreakBody, _)) :-
body_with_no_break(Body, NoBreakBody).
value_comparison(js_binary_operation(
equals_op,
js_identifier(Variable, _),
Value,
_),
Variable, Value).
body_with_no_break([js_break(_)], []).
body_with_no_break([Stat|Rest1], [Stat|Rest2]) :-
body_with_no_break(Rest1, Rest2)Here's an example of using the switch_if predicate to convert a small code snippet. The input contains a switch statement. The result is unified in the IfString variable.
?- parse_js_stat_string("switch(w) {
case 1:
print('first');
break;
case 2:
print('second');
break;
default:
print('Nothing');
break;
}", SwitchAst), switch_if(SwitchAst, IfAst), print_js_ast_to_string(IfAst, IfString), writef(IfString).
if (w == 1) {
print('first', );
} else if (w == 2) {
print('second', );
} else {
print('Nothing', );
}
SwitchAst = js_switch(...),
IfString = "if (w == 1) {\n print('first', );\n} else if (w == 2) {\n print('second', );\n} else {\n print('Nothing', );\n}"
The parse_js_stat_string predicate parses a string containing a statement. On success this predicate generates a simple AST representation of the input element as a Prolog term. For example:
?- parse_js_stat_string("switch(w) {
case 1:
print('first');
break;
case 2:
print('second');
break;
default:
print('Nothing');
break;
}", SwitchAst).
SwitchAst = js_switch(js_identifier([119], lex_info(1, [])), [js_case(js_literal(number, [49], lex_info(2, [ws(19, false)])), [js_expr_stat(js_call(js_identifier([112, 114|...], lex_info(3, [ws(..., ...)])), js_arguments([js_literal(string, [...|...], lex_info(..., ...))], lex_info(3, [], 3, [])), null)), js_break(lex_info(4, [ws(43, true)]))], lex_info(2, [ws(11, true)])), js_case(js_literal(number, [50], lex_info(5, [ws(63, false)])), [js_expr_stat(js_call(js_identifier([112|...], lex_info(6, [...])), js_arguments([js_literal(..., ..., ...)], lex_info(6, [], 6, [])), null)), js_break(lex_info(7, [ws(..., ...)]))], lex_info(5, [ws(55, true)])), js_default([js_expr_stat(js_call(js_identifier([...|...], lex_info(..., ...)), js_arguments([...], lex_info(..., ..., ..., ...)), null)), js_break(lex_info(10, [...]))], lex_info(8, [ws(100, true)]))], lex_info(1, []))
Going the other way
An awesome surprise it's that the switch_if predicate can be used in "the order direction" without any modification. That is, we can specify an if AST and get a switch version of it. Of course this can only be done if the conversion makes sense. For example:
?- parse_js_stat_string("
if (x == 10) {
print('10 val');
} else if (x == 20) {
print('20 val');
} else {
print('None');
}", IfAst), switch_if(SwitchAst, IfAst), print_js_ast_to_string(SwitchAst, SwitchString), writef(SwitchString).
switch(x) {
case 10:
print('10 val', );
break;
case 20:
print('20 val', );
break;
default:
print('None', );
break;
}
IfAst = js_if(js_binary_operation(equals_op,...),
SwitchAst = js_switch(...),
SwitchString = "switch(x) {\n case 10:\n print('10 val', );\n break;\n case 20:\n print('20 val', );\n break;\n default:\n print('None', );\n break;\n}\n"
Several alternatives for converting between switch and if
One of the most intriguing characteristics of Prolog is the posibility of giving different valid results for a given goal.
For example we can give another posibility to the value_comparison predicate:
value_comparison(js_binary_operation(
equals_op,
js_identifier(Variable, _),
Value,
_),
Variable, Value).
value_comparison(js_binary_operation(
equals_op,
Value,
js_identifier(Variable, _),
_),
Variable, Value).By doing this what we are saying is that either x == 1 and 1 == x are valid possibilities for the condition of the if statement replacing a case section.
If we do this we can get more alternatives:
?- quick_switch_if_test("switch(w) {
case 1:
print('first');
break;
case 2:
print('second');
break;
default:
print('Nothing');
break;
}").
if (w == 1) {
print('first', );
} else if (w == 2) {
print('second', );
} else {
print('Nothing', );
}
true ;
if (w == 1) {
print('first', );
} else if (2 == w) {
print('second', );
} else {
print('Nothing', );
}
true ;
if (1 == w) {
print('first', );
} else if (w == 2) {
print('second', );
} else {
print('Nothing', );
}
true ;
if (1 == w) {
print('first', );
} else if (2 == w) {
print('second', );
} else {
print('Nothing', );
}
true ;
false.
Code for this post can be found here.
