In the C language, there are often several different ways to write the same type. For example, the following two types are equivalent:
int const unsigned * const volatile const unsigned int * volatile const
Write a Prolog predicate same_c_type(A, B) that succeeds if A and B are Prolog lists of C keywords and tokens that represent the same C type. For example, the goal:
same_c_type([int, const, unsigned, *, const, volatile], [const, unsigned, int, *, volatile, const])
should succeed. Use the Prolog atoms '(' and ')' to represent C parentheses.
You may assume that the first argument of same_c_type/2 is a ground term, i.e., that it does not contain any logical variables. However, the second argument can contain logical variables, and if it does then same_c_type/2 should backtrack through all solutions. For example, same_c_type([unsigned,const,*], T) should backtrack through all possible solutions for T. The behavior should be something like the following.
| ?- same_c_type([unsigned,const,*], T).
T = [const,int,unsigned,*] ? ;
T = [const,unsigned,*] ? ;
T = [const,unsigned,int,*] ? ;
T = [int,const,unsigned,*] ? ;
T = [int,unsigned,const,*] ? ;
T = [unsigned,const,*] ? ;
T = [unsigned,const,int,*] ? ;
T = [unsigned,int,const,*] ? ;
T = [const,int,unsigned,'(',*,')'] ? ;
T = [const,unsigned,'(',*,')'] ?
yes
Note that the user got tired of seeing more answers here; there are actually an infinite number of answers. The order that solutions are backtracked through is not important, so long as all the correct solutions are backtracked through, and so long as the same solution isn't generated more than once.
For the purpose of this assignment, limit yourself to the following subset of the full C grammar for type names:
In this grammar, nonterminals are in italics, whereas keywords and other symbols are in sample case. The "opt" subscript means the preceding nonterminal is optional. Alternatives are listed on separate lines.
Two pointer types are equivalent if they have the same qualifiers and both point to equivalent types. For example, int const * const volatile is equivalent to const int * volatile const.
Parenthesization of abstract declarators does not affect the resulting type. For example, int * (**) and int ** (*) are both equivalent to int ***.
The order that keywords appear within a type specifier group or type qualifier list does not affect the resulting type. For example, int const unsigned is equivalent to unsigned int const.
A type specifier group's type specifiers must be one of the following. The order of the type specifiers does not matter; for example, unsigned int is the same as int unsigned. Also, the type specifiers need not be adjacent and can be separated by type qualifiers; for example, int const unsigned is equivalent to unsigned int const. Also, types on the same line are equivalent; for example, short is equivalent to signed short. (C actually uses the keywords _Bool, _Complex, and _Imaginary, but for convenience we use bool, complex, and imaginary instead.)
void char signed char unsigned char short ≡ signed short ≡ short int ≡ signed short int unsigned short ≡ unsigned short int int ≡ signed ≡ signed int unsigned ≡ unsigned int long ≡ signed long ≡ long int ≡ signed long int unsigned long ≡ unsigned long int long long ≡ signed long long ≡ long long int ≡ signed long long int unsigned long long ≡ unsigned long long int float double long double bool float complex double complex long double complex float imaginary double imaginary long double imaginary
Note that char is equivalent to neither signed char nor unsigned char.
Unlike type specifiers, type qualifiers may occur at most once within a type specifier group or a type qualifier list. (C allows them to appear multiple times, but the duplicate occurrences are ignored, so we take the more restrictive approach here.)
To turn in your assignment, submit a file hw4.prolog containing your definition of same_c_type/2 along with any other auxiliary definitions.