3

I am studying different language games and trying to implement them in Common Lisp. Currently, I am studying a game which studies the relation between forms and meanings. An agent needs to store the association between these forms and meanings. One form can have multiple meanings (ambiguity) and one meaning can have multiple forms (synonymy). On top of that, the agent needs to keep track of the score of each form-meaning pair in order to decide which ones to use.

Now, I was wondering how I could create a data-structure in Lisp that could hold all of this information. It should be able to search both on meaning and form and also add new form-meaning pairs.

My first idea was the following. Create a struct which holds the form, meaning and score and basically keep a list of all of these struct-instances. This is quite simple to implement, but searching on form or meaning becomes a pain, since I would have to go through each element of the list.

My second idea is based on a table like this:

|          || form1   | form2   | form3   | ...
|----------||---------|---------|---------| ...
| meaning1 || score11 | score12 | score13 | ...
| meaning2 || score21 | score22 | score23 | ...
| meaning3 || score31 | score32 | score33 | ...

where score11 is the score for form-meaning pair (form1 . meaning1). The score_ij would be empty if there is no form-meaning pair (form_i . meaning_j). Would this kind of design make it easier to search on both meanings and forms? Also, I don't quite know what kind of Common Lisp data structure I could use for this.

Suggestions on what data structure to use for this, or other design ideas are welcome.

  • It looks like an array to me. If you need to search on the columns, it's an array and two vectors, or possibly two hashtables if you have a really large number of columns and rows. – Robert Harvey Nov 5 '15 at 15:20
  • A vector for the meanings and a vector for the forms, together with a 2d array for the scores. Is that what you mean? I don't really see how it would work with 2 hashtables. – JNevens Nov 5 '15 at 15:33
  • Yes, that's what I mean. – Robert Harvey Nov 5 '15 at 15:33
5

Typically I would use some embedded relational store for that. Some kind of Prolog in Lisp might do.

A self-written data structure could be like this:

  • a CLOS class for the triple: meaning, form, score
  • a hash-table mapping from a meaning to a list of triples
  • a hash-table mapping from a form to a list of triples

The lists of triples could be sorted by score.

The I would write the retrieval and insert functions for that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.