Your boss at JCN wants to find more instances of copied Scheme code in TDP's operating system. JCN's legal project has been having problems using the Scheme-oriented pattern matchers: they're fast, but the pattern language isn't flexible enough, and JCN is not finding enough instances of copied code in TDP's OS. So your boss has decided to write a new set of pattern matchers in Prolog. These matchers will be integrated into the overall project, which is mostly written in Scheme. You are assigned the task of writing a converter from Scheme programs to Prolog representations for those programs, and back again.
For the purpose of this assignment, we'll use only the following subset of R5RS §7.1.2:
<datum> → <simple datum> | <compound datum>
<simple datum> → <boolean> | <symbol>
<boolean> → #f | #t
<symbol> → <identifier>
<compound datum> → <list>
<list> → ( <datum>* ) | ( <datum>+ . <datum> ) | <abbreviation>
<abbreviation> → <abbrev prefix> <datum>
<abbrev prefix> → '
Your boss decides to model the Scheme external representation as a token list, i.e., a list of Prolog atoms. The Prolog atoms '.', '''' (i.e., single apostrophe), '(', ')', '#f', and '#t' represent the corresponding Scheme tokens; the Prolog atom [] is not allowed as a token; all other Prolog atoms represent the corresponding Scheme symbol.
For example, the Scheme external representation (append '(#f a ((bb) '(car) . d)) 'e) is modeled by the Prolog term ['(', append, '''', '(', '#f', a, '(', '(', bb, ')', '''', '(', car, ')', '.', d, ')', ')', '''', e, ')'].
Write a Prolog predicate scheme_term(L,S) that succeeds if L is a list of Prolog symbols that model the Scheme external representation for S, and that fails otherwise. You may assume that either the first or the second argument to scheme_term/2 is a ground term, that is, it does not contain any logical variables. Your program may not use any side effects like assert, retract, or I/O; however, it may use cuts.
scheme_term(L,S) may need to backtrack if S is a ground term that has multiple representations. If this happens with L is initially a variable, the first success should bind L to the preferred representation for S. The preferred representation for a proper list is the representation without the internal period, and the preferred representation for an abbreviation uses ' rather than quote.
To turn in your assignment, submit a file hw2.pl containing your predicate definitions. The first line of hw2.pl should be a comment containing your name and student ID. Make sure that your definitions work with gprolog, the Prolog implementation installed on SEASnet.
In these examples, the programmer repeatedly typed ";" in order to backtrack through all possible solutions. Your program does not need to return the answers in the same order as shown below, except that the first answer for each query must be as shown. Also, your program's final response need not agree with the yes and ; no responses in the examples shown below.
$ gprolog
GNU Prolog 1.2.16
By Daniel Diaz
Copyright (C) 1999-2002 Daniel Diaz
| ?- consult('hw2.pl').
compiling hw2.pl for byte code …
yes
| ?- scheme_term([], R).
no
| ?- scheme_term([a], R).
R = a ? ;
no
| ?- scheme_term([[]], R).
no
| ?- scheme_term(['(', ')'], R).
R = [] ? ;
no
| ?- scheme_term(['(', a, a, a, ')'], R).
R = [a,a,a] ? ;
no
| ?- scheme_term(['(', a, a, '.', b, ')'], R).
R = [a,a|b] ? ;
no
| ?- scheme_term(['(', a], R).
no
| ?- scheme_term([a, ')'], R).
no
| ?- scheme_term([a, b], R).
no
| ?- scheme_term(['(', '(', '(', '(', '(', a, ')', ')', ')', ')', ')'], R).
R = [[[[[a]]]]] ? ;
no
| ?- scheme_term(['(', append, '''', '(', '#f', a, '(', '(', bb, ')',
'''', '(', car, ')', '.', d, ')', ')', '''', e, ')'],
R).
R = [append,[quote,['#f',a,[[bb],[quote,[car]]|d]]],[quote,e]] ? ;
no
| ?- scheme_term(['(', '(', a, ')', '.', '(', b, ')', ')'], R).
R = [[a],b] ? ;
no
| ?- scheme_term(['(', '(', a, ')', b, ')'], R).
R = [[a],b] ? ;
no
| ?- scheme_term(L, [[a],b]).
L = ['(','(',a,')',b,')'] ? ;
L = ['(','(',a,')',b,'.','(',')',')'] ? ;
L = ['(','(',a,')','.','(',b,')',')'] ? ;
L = ['(','(',a,')','.','(',b,'.','(',')',')',')'] ? ;
L = ['(','(',a,'.','(',')',')',b,')'] ? ;
L = ['(','(',a,'.','(',')',')',b,'.','(',')',')'] ? ;
L = ['(','(',a,'.','(',')',')','.','(',b,')',')'] ? ;
L = ['(','(',a,'.','(',')',')','.','(',b,'.','(',')',')',')'] ? ;
no
| ?- scheme_term(['''', a], R), scheme_term(L, R).
L = ['''',a]
R = [quote,a] ? ;
L = ['(',quote,a,')']
R = [quote,a] ? ;
L = ['(',quote,a,'.','(',')',')']
R = [quote,a] ? ;
L = ['(',quote,'.','(',a,')',')']
R = [quote,a] ? ;
L = ['(',quote,'.','(',a,'.','(',')',')',')']
R = [quote,a] ? ;
no