The mystery is finally solved! Yes, the code works.
#!/usr/bin/env swipl --quiet
:- use_module(library(clpfd)).
% ORIGINAL LYRICS:
% Looking for
% Girls who want boys
% Who like boys to be girls
% Who do boys like they're girls
% Who do girls like they're boys
% Always should be someone you really love
% - "Girls and Boys," Blur, 1994
% DSL CONVERSION:
% girls who like boys
% who like boys (who are girls)
% who like boys (who get done like they're girls)
% who like girls (who get done like they're boys)
% TREE STRUCTURE:
% group(female, none, none, group(
% male, female, none, group(
% male, none, female, group(
% female, none, male, none)))).
% USAGE:
% 1. Get all possible lyrics up to a max depth:
% ?- group_maxdepth(G, 4), group_string(G, S).
% 2. Get the tree structure of some lyrics (pass a max depth to avoid unbounded recursion):
% ?- group_maxdepth(G, 4), group_string(G, 'boys who like girls').
% 3. Get the lyrics from a tree structure:
% ?- group_string(group(male, none, none, group(female, none, none, none)), S).
% 4. Fill in the blanks with all possibilities:
% ?- group_depth(G, 3),
% phrase(group_sentence(G), Tokens),
% append([[girls, who, like], X, [who, like], Y], Tokens),
% atomic_list_concat(Tokens, ' ', S).
% Genders
gender(male).
gender(female).
% gender_altgender(G, G2)
% Valid relation between gender and alternative genders (isGender and
% PerformGender) in the same group.
gender_altgender(G, none) :-
gender(G).
gender_altgender(G, G2) :-
gender(G),
gender(G2),
dif(G, G2).
% Group(Gender, IsGender, PerformGender, LikeGroup).
% All arguments but Gender are optional.
% Represents a demographic that can like and can be a target of liking.
group(Gender, IsGender, PerformGender, none) :-
gender(Gender),
gender_altgender(Gender, IsGender),
gender_altgender(Gender, PerformGender).
group(Gender, IsGender, PerformGender, group(Gender2, IsGender2, PerformGender2, Group)) :-
group(Gender, IsGender, PerformGender, none),
group(Gender2, IsGender2, PerformGender2, Group).
% DCG to produce a phrase from a group.
% Example:
% ?- phrase(group_sentence(group(male, none, none, group(female, none, none, group(male, none, none, group(male))))), Tokens).
% Tokens = [boys, who, like, girls, who, like, boys, who, like, boys].
group_sentence(group(Gender, IsGender, PerformGender, none)) -->
{ group(Gender, IsGender, PerformGender, none) },
gender_phrase(Gender),
group_info_phrase(IsGender, PerformGender).
group_sentence(group(Gender, IsGender, PerformGender, Group)) -->
{ dif(Group, none) },
group_sentence(group(Gender, IsGender, PerformGender, none)),
[who, like],
group_sentence(Group).
gender_phrase(male) --> [boys].
gender_phrase(female) --> [girls].
isgender_phrase(none) --> [].
isgender_phrase(Gender) --> [are], gender_phrase(Gender).
performgender_phrase(none) --> [].
performgender_phrase(Gender) --> [get, done, like, 'they''re'], gender_phrase(Gender).
% Render isGender and PerformGender within parentheses.
group_info_phrase(none, none) --> [].
group_info_phrase(IsGender, none) -->
{ dif(IsGender, none) },
['(', who], isgender_phrase(IsGender), [')'].
group_info_phrase(none, PerformGender) -->
{ dif(PerformGender, none) },
['(', who], performgender_phrase(PerformGender), [')'].
group_info_phrase(IsGender, PerformGender) -->
{ dif(IsGender, none), dif(PerformGender, none) },
['(', who], isgender_phrase(IsGender), ['and'], performgender_phrase(PerformGender), [')'].
% Relate group and string representation
% ?- group_string(group(male, none, none, group(female, none, none, group(male, none, none, group(male)))), S).
% S = 'boys who like girls who like boys who like boys'
group_string(group(Gender, IsGender, PerformGender, Group), String) :-
phrase(group_sentence(group(Gender, IsGender, PerformGender, Group)), Tokens),
atomic_list_concat(Tokens, ' ', String).
% Relate group and depth
% - group(G0, IG, PG, none) has depth 0
% - group(G0, IG, PG, group(...)) has depth 1
group_depth(group(Gender, IsGender, PerformGender, none), 0) :-
group(Gender, IsGender, PerformGender, none).
group_depth(group(Gender, IsGender, PerformGender, Group), Depth) :-
Depth #> 0,
group(Gender, IsGender, PerformGender, none),
Depth0 #= Depth - 1,
group_depth(Group, Depth0).
% Relate group and all integers larger than its depth.
group_maxdepth(Group, MaxDepth) :-
MaxDepth #>= Depth,
Depth #>= 0,
group_depth(Group, Depth).
