%
% CS 430 Module 15 Lab Solution (Dr. Mike Lam)
%

% facts
%
% direct_ancestor(L,A) is read "language L has language A as a direct ancestor"
%
direct_ancestor(scheme, lisp).
direct_ancestor(commonlisp, lisp).
direct_ancestor(haskell, scheme).
direct_ancestor(java, smalltalk).
direct_ancestor(java, cpp).
direct_ancestor(cpp, c).
direct_ancestor(cpp, smalltalk).
direct_ancestor(smalltalk, simula).
direct_ancestor(simula, algol).
direct_ancestor(csharp, java).
direct_ancestor(c, algol).
direct_ancestor(pascal, algol).
direct_ancestor(ada, pascal).
direct_ancestor(algol, fortran).

%
% ancestor(L,A) is read "language L has language A as an ancestor"
%
% a language has an ancestor if it is a direct ancestor
ancestor(Language, Ancestor) :- direct_ancestor(Language, Ancestor).
% ... or if there is an intermediary direct ancestor who has the ancestor (transitivity)
ancestor(Language, Ancestor) :-
    direct_ancestor(Language, Intermediary),
    ancestor(Intermediary, Ancestor).

% infinite loop version (DO NOT ENABLE!)
%ancestor(Language, Ancestor) :- direct_ancestor(Language, Ancestor).
%ancestor(Language, Ancestor) :-
%   ancestor(Intermediary, Ancestor),
%   direct_ancestor(Language, Intermediary).

% languages are cousins if they have an ancestor in common and are unique
cousins(Language, Cousin) :-
    ancestor(Language, Ancestor),
    ancestor(Cousin, Ancestor),
    Language \== Cousin.

% version with a cut (won't generate all answers)
%cousins(Language, Cousin) :-
%   ancestor(Language, Ancestor),
%   ancestor(Cousin, Ancestor),
%   Language \== Cousin, !.

common_ancestor(LanguageA, LanguageB, Ancestor) :-
    ancestor(LanguageA, Ancestor), ancestor(LanguageB, Ancestor).

% a language is a progenitor if it has no ancestors but at least one descendent
% (i.e., some other language has it as an ancestor)
progenitor(Language) :- ancestor(_, Language), \+ ancestor(Language, _).


%
% test routines
%

test_cousins :-
    cousins(java,cpp),
    \+cousins(java,lisp).

test_common_ancestor :-
    common_ancestor(java,cpp,_),
    \+common_ancestor(scheme,cpp,_).

test_progenitor :-
    progenitor(fortran),
    \+progenitor(cpp).

test :- test_cousins,
        test_common_ancestor,
        test_progenitor, !.