Sunday, March 10, 2019

A quick note about programming in Prolog

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.