The concepts for frame system are described here. The examples are based on a slightly different and more complicated code base than used in these exercises.

These exercises use a simpler frame system, called MOPs for Memory Organization Packages. The system is part of the cs325 download.

(ql:quickload "mops")

The MOP system defines two packages:

The MOPs referrred to examples below are in the file mop-examples.txt. They are loaded by the test cases. They can be loaded manually:

(in-package :mop-tests)
    (load-kb *mop-file*)

MOPs: has-slots-p

Test package: mop-tests

Tests: (run-tests has-slots-p)

Code package: mops

Function name: has-slots-p

MOPs bundle

Define (has-slots-p mop slots) to take the name of a MOP and a list of role-filler pairs, and return true if the MOP has or inherits those slots. This can include slots with more specific fillers. For example,

(has-slots-p 'jumbo-1 '((color gray) (name "Jumbo")))

returns true because the Jumbo-1 MOP has the slot (name "Jumbo") and inherits the slot (color gray) from elephant.

(has-slots-p 'event-1 '((actor elephant) (action ingest)))

returns true because the Event-1 MOP has the slot (actor clyde-1), and Clyde-1 is an elephant, and inherits the slot (action ingest).

MOPs: linearize

Test package: mop-tests

Tests: (run-tests pedalo)

Code package: mops

Function name: linearize

MOPs bundle

The linearize function in mops.lisp produces an unintuitive answer for the navigation zone in the Pedalo example. (get-filler 'pedalo 'navzone) returns 100, but the zone for either of its parents is 5.

Change the way linearizations are merged to use one of the two algorithms described here. The algorithm merges a list of linearizations by repeatedly finding a "ready" MOP, saving that MOP in the merger, and removing it from the input linearizations, until there are no MOPs left to merge. A MOP is ready if it appears as the first element of one or more input linearizations, and never somewhere else. The two algorithms differ primarily in the addition of an extra list to handle some tricky cases.

Test package: mop-tests

Tests: (run-tests mop-search)

Code package: mops

Function name: mop-search

MOPs bundle

mop-search is the memory retrieval part of the MOP system. It is analogous to ask in the deductive retriever, or graph-search in the semantic triples system.

mop-search doesn't use variables. (mop-search mop slots) returns a list of all MOPs in memory that are specializations of mop and have the given slots, as defined by has-slots-p.

In our small example memories, you can just scan and collect all MOPs that work. That would not be practical for a realistically large memory, nor is it be cognitively plausible. Human memory appears to be good at combining specific details with general contextual concepts to retrieve specific versions of those general concepts. Human is not so great at enumerating all specializations of a general concept.

So, to model that kind of behavior, implement mop-search by having it create and use a filler-based index. This is just a table -- an association list or hashtable -- that maps each slot filler value to a list of the mops that have that value as the filler of some slot.

For example, in the sample memory, the table entry for clyde-1 would have the list (event-1 state1) because clyde-1 appears as a filler in slots in both of those MOPs.

mop-search should use the index table to get candidate MOPs to check. Many of the candidate MOPs won't work, either the MOP is not a specialization of the MOP being searched for, or because the filler appeared in a different slot, e.g., the object rather than the actor. But the number of MOPs to check will be much smaller than all of memory.

Before returning its final list of answers, mop-search should remove redundant answers. This includes not only duplicates, but also any MOPs that are abstractions of other MOPs in the list. It is redundant to return ingest-event if you are also returning one or more instances of an ingest-event.

Indexing can make mop-search fast, especially compared to complete search in a large memory, but it will also miss many things. It will tend to do better with more specific cues. For example,

(mop-search 'event '((actor elephant)))

will return NIL because in the sample memory there is nothing that has a slot with the filler elephant, so there is no index entry for it. But the same search with clyde-1 will correctly return event-1.

MOPs: Parsing (DMAP)

Test package: mop-tests

Tests: (run-tests dmap-tests)

Code package: mops

Function names: dmap, references, set-phrases

MOPs bundle

For background on direct memory access parsing and the algorithm to be implemented, see the DMAP reading.

The test cases use three functions that you have to define. Exactly what those functions do and return is up to you, as long as the test cases pass.

The current test cases are minimal proofs of concept. Your code should do what you think the above algorithm intends, not the minimum necessary to make the few tests pass.

(set-phrases phrases) associates phrases to MOPs. It takes a list of lists, where each list has the form (mop-name . phrase), e.g.,

(change-event (variable) are (direction))

See the tests for examples.

(dmap sentence [ parse-state ]) takes a sentence, in the form of a list of symbols, e.g., (clyde ate peanuts), "parses" the sentence as described above, and returns a parse-state. A parse state is some representation you design to capture what MOPs DMAP has seen so far and what phrases it has waiting for further input. If a parse state is passed as the second argument, dmap starts from that state.

(references parse-state) takes a parse state and returns a list of all MOP instances that have been referenced so far. This is used in the test cases to see what concepts your parser found for a given text. See the tests for the items that must be returned, in some order.

A parse state can be anything as long as you can use it to process text in fragments. For example, parsing a list of words text one by one with

text.reduce((history, word) => (dmap (list word) history), nil)

should produce the same result as

(dmap text)