Exercise 8: Language transformations algorithm

Summary

Create a web application to allow a user to type a statement or question and have the system respond.

If at any time the system doesn't understand, no response should be given. (Only debug output: See below)

If a question is asked, and the system understands, the system should respond with the value that answers the question. If the system understands but doesn't know the answer, it should respond with "I don't know [...]", and fill in the square brackets with the path to the requested property. For example: "I don't know [speaker.age]". At this time, only questions that can be answered with a value are permitted.

If a statement is entered, and the system understands, it should update its data structure and respond with "Ok: ...", and fill in the appropriate assignment. For example: "Ok: speaker.age = 27".

A link will be provided named "Show details", which will show a hidden pane. This pane will show debug output, which is described later on.

A link will be provided to a second page entitled "Brain state" which will contain three large text areas. The first text area will contain a dump of the brain's core state. The text area can be edited and a "Save" button clicked to update the brain state. Likewise, there should be text areas for editing the word-to-entity mappings as well as the transformations.

Applying transformations

The core of this exercise is to create an algorithm that, given a statement or question, determines which sequence of transformations to apply to end up with a representation that can be directly interpreted.

The first step is to transform a list of words into a list of EntityTrees. Each tree represents the is_a relationships of the word it corresponds to. Rather than storing the tree, however, it should be converted into a flat list using the GetList() method. We'll call this list of lists the entityTypeLists structure.

The next step is to permute the lists to arrive at all possible combinations of entity types. For example, taking the first entity type from each list arrives at one combination. Taking the second entity type from the first list and first entity type from the rest of the lists arrives at another combination, etc. We'll call this the permutedEntityTypes list.

The core algorithm iterates over the permutedEntityTypes list. Each permutation of entity types consists of a list of entity types. Taking the first two entity types, we determine which transformations can be applied. To determine this, we need an indexed structure that allows us to get all applicable transformations given two sequential entity types. For example, we could use a two-deep hash.

Once we have determined what transformations we can apply, we go ahead and apply each one separately. (If there are no transformations to apply, then we need to look for transformations that can be applied starting at the second token, etc.) For each application, we have to ask ourselves whether the resultant fragment is complete. ie. In a format that can be directly interpreted. If it is, we add it to a list of interpretations. If it is not, we add it back onto the permutedEntityTypes stack.

Note that because transformations take Fragments as their input and produce Fragments as their output, the permutedEntityTypes list needs to be a list of Fragments. Thus we'll call it the unresolvedFragments list.

The class that orchestrates this process should be called TransformationSearch.

Debug output

The debug output will be displayed if the "View details" link is clicked. The primary purpose of the debug output is to see what happened when unexpected response was given.

For each word, the list of possible entities will be listed. Format:
word1: entity1, entity2, entity3, etc.
etc.

The initial list of permuted fragments will be listed.

If a fragment is clicked, the list of applicable transformations will be listed.

If one of the applicable transformations is clicked, the resultant fragments and outputs will be listed.

This is effectively a recursive process that allows the user to drill down into the search space.

Test cases

Click here

Solution

Click here

Web UI

Click here