1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
|
"""An example TripletStructure for solving a letter analogy problem.
Throughout this codebase we use the shorthand `tc` to represent the
TripletStructure being operated on, and `rt` to represent the Runtime operating on
that TripletStructure. I have also standardized to upper-case function names to
differentiate the "front-end" code using ts_lib from the "plumbing" code that
actually implements the DSL. These decisions can be undone if no one else likes
them.
"""
import string # pylint: disable=deprecated-module
from timeit import default_timer as timer
from ts_lib import TripletStructure
from ts_utils import RegisterPrototype, RegisterRule
from runtime.runtime import TSRuntime
from mapper import MapperCodelet
from letter_tactics import SolveLetterAnalogy
def Main(verbose=True):
"""Initialize the structure and solve the letter analogy.
"""
# This will hold our facts and nodes (including the rules and tactics!).
ts = TripletStructure()
# Add rules describing common letter relations, eg. 'Successor.'
LetterRelations(ts)
# Add (standardized) rules describing how to map/make analogies/join
# sub-structures. This can handle eg. abc -> bcd and lmn -> mno being
# 'abstracted' to x_1x_2x_3 -> y_1y_2y_3 with Succ(x_1, y_1), etc.
MapperCodelet(ts)
# Add three letter analogies, describing the problem to be solved. None
# indicates that the 'solution' should go there (it's indicated by marking
# the corresponding node with TOP).
LetterAnalogy(ts, ":Analogy_abc_bcd", "abc", "bcd")
LetterAnalogy(ts, ":Analogy_lmn_mno", "lmn", "mno")
LetterAnalogy(ts, ":Analogy_def_top", "def", None)
# Now that we have a structure (ts) which fully describes our problems,
# rules, and heuristics, we can initialize a TSRuntime to modify the
# structure according to the rules.
rt = TSRuntime(ts)
SolveLetterAnalogy(rt, verbose=verbose)
solution = ExtractLetterGroup(ts, ts["/:Analogy_def_top:To:_"])
if verbose:
print(f"Proposed solution: {solution}")
return solution
def ExtractLetterGroup(ts, letter_group):
"""Tries to extract a string representation of the letter group.
This is not always successful, as the representation might be invalid (eg.
cycles, or more than one NextPair:Right). In such cases it returns None.
"""
try:
# NOTE: These may be ambiguous, to be sure we should have a few
# assert(len(...) == 1)s here.
letter_group = letter_group.full_name
head_map = ts.lookup(None, letter_group, "/:HeadPair:Container")[0][0]
head = ts.lookup(head_map, None, "/:HeadPair:Head")[0][1]
letters = ""
visited = set()
while True:
if head in visited:
return None
visited.add(head)
for letter in string.ascii_lowercase + string.ascii_uppercase:
is_letter = ts.lookup(None, head, Letter(ts, letter).full_name)
if is_letter:
letters += letter
break
else:
letters += "?"
next_map = ts.lookup(None, head, "/:NextPair:Left")
if not next_map:
break
next_map = next_map[0][0]
head = ts.lookup(next_map, None, "/:NextPair:Right")[0][1]
return letters
except IndexError:
return None
def LetterAnalogy(ts, name, analogy_from, analogy_to):
"""Adds nodes describing a particular letter analogy.
@name should be a unique node prefix, while @analogy_from and @analogy_to
should be strings describing the word analogy.
"""
with ts.scope(name):
LetterGroup(ts, analogy_from, ts.scope(":From"))
LetterGroup(ts, analogy_to, ts.scope(":To"))
ts[":AnalogyMap"].map({
ts[":From:_"]: ts["/:Analogy:From"],
ts[":To:_"]: ts["/:Analogy:To"]
})
def LetterGroup(ts, letters, scope):
"""Adds nodes describing a string of letters (eg. one side of an analogy).
The entire group is represented by a node scope[:_] which is marked as the
owner of all other nodes.
"""
with scope:
if letters is None:
ts[":IsTopMap:??"].map({ts[":_"]: ts["/:Mapper:TOP"]})
return
nodes = []
for i, letter in enumerate(letters):
node = ts[":Letter{}_{}".format(i, letter)]
nodes.append(node)
ts[":IsLetterMap:??"].map({node: Letter(ts, letter)})
ts[":IsOwned:??"].map({
scope[":_"]: ts["/:Owner"],
node: ts["/:Owned"],
})
for left_node, right_node in zip(nodes[:-1], nodes[1:]):
ts[":LRMap:??"].map({
left_node: ts["/:NextPair:Left"],
right_node: ts["/:NextPair:Right"],
})
def Letter(ts, letter):
"""Returns a reference to the node corresponding to character @letter.
This is sort of the "Platonic conception" of @letter.
"""
return ts["/:Letter:{}".format(letter)]
def LetterRelations(ts):
"""Adds relations and rules describing strings of letters.
"""
# Declaring these is not strictly necessary, as they will be created when
# first referenced, but I am listing them here for reference.
# pylint: disable=pointless-statement
with ts.scope(":NextPair"):
ts[":Left, :Right"]
with ts.scope(":SuccessorPair"):
ts[":Predecessor, :Successor"]
with ts.scope(":UpperPair"):
ts[":Lower, :Upper"]
with ts.scope(":HeadPair"):
ts[":Container, :Head"]
Headify(ts)
for predecessor, successor in zip(string.ascii_lowercase[:-1],
string.ascii_lowercase[1:]):
SuccessorPrototype(ts, predecessor, successor)
SuccessorPrototype(ts, predecessor.upper(), successor.upper())
for letter in string.ascii_lowercase:
UpperPrototype(ts, letter, letter.upper())
def SuccessorPrototype(ts, predecessor, successor):
"""Rules that identify and concretize successor pairs.
Note that this approach will create 3 rules for each pair (a, b); one that
creates Successor(a, b) from a and b, one that creates `a` given
Successor(a, b) and b, and one that creates `b` given Successor(a, b) and
`a`.
An alternative approach is to define three "Generic Binary Prototype"
rules, and then expose these as "examples" that that rule then maps
against. I think this is a more straight-forward approach for now, though
in the future (or if there's too much overhead with parsing the rules) we
can look at the other option.
"""
with ts.scope(":Successor{}To{}".format(predecessor, successor)):
ts[":MA"].map({ts[":A"]: Letter(ts, predecessor)})
ts[":MB"].map({ts[":B"]: Letter(ts, successor)})
ts[":PairMap"].map({ts[":A"]: ts["/:SuccessorPair:Predecessor"]})
ts[":PairMap"].map({ts[":B"]: ts["/:SuccessorPair:Successor"]})
RegisterPrototype(ts, dict({
":ConcretizePredecessor": {ts["/INSERT"]: [ts[":MA"]]},
":ConcretizeSuccessor": {ts["/INSERT"]: [ts[":MB"]]},
":ConcretizePair": {ts["/INSERT"]: [ts[":PairMap"]]},
}), equal=[])
def UpperPrototype(ts, lowercase, uppercase):
"""Rules for identifying and concretizing Upper pairs.
See SuccessorPrototype for notes on this implementation.
"""
with ts.scope(":Upper{}To{}".format(lowercase, uppercase)):
ts[":MA"].map({ts[":A"]: Letter(ts, lowercase)})
ts[":MB"].map({ts[":B"]: Letter(ts, uppercase)})
ts[":PairMap"].map({ts[":A"]: ts["/:UpperPair:Lower"]})
ts[":PairMap"].map({ts[":B"]: ts["/:UpperPair:Upper"]})
RegisterPrototype(ts, dict({
":ConcretizePredecessor": {ts["/INSERT"]: [ts[":MA"]]},
":ConcretizeSuccessor": {ts["/INSERT"]: [ts[":MB"]]},
":ConcretizePair": {ts["/INSERT"]: [ts[":PairMap"]]},
}), equal=[])
def Headify(ts):
"""Rules that identify the head letter of a letter group.
"""
with ts.scope("/:HeadOfContainer"):
with ts.scope(":MustMap") as exist:
ts[":IsLeftOf"].map({ts[":LeftMost"]: ts["/:NextPair:Left"]})
ts[":IsMember"].map({
ts[":Container"]: ts["/:Owner"],
ts[":LeftMost"]: ts["/:Owned"],
})
with ts.scope(":NoMap"):
ts[":IsRightOf"].map({exist[":LeftMost"]: ts["/:NextPair:Right"]})
with ts.scope(":TryMap:Insert"):
ts[":IsHead"].map({
exist[":Container"]: ts["/:HeadPair:Container"],
exist[":LeftMost"]: ts["/:HeadPair:Head"],
})
RegisterRule(ts)
if __name__ == "__main__":
start = timer()
Main()
print(timer() - start)
|
