2004 AI Qual Programming Question


Congratulations! 60-Minute Software ("ready in an hour or it's free") has hired you to write a Semantic Web knowledge interchange tool. A common technique, used in RDF and OWL, is to map user-friendly nested frame structures to flat lists of "subject predicate object" triples, and back. For example, in list form, a publishing event

(publish-event
  (published
    (book (title "The Eat Skin Diet")
          (author (person (name "Carrie N. Eater")))))
  (publisher "Simon's Shoestore")
  (year "2004"))

might be mapped to:

((node100 type publish-event)
 (node100 published node101)
 (node100 publisher "Simon's Shoestore")
 (node100 year "2004")
 (node101 type book)
 (node101 title "The Eat Skin Diet")
 (node101 author node102)
 (node102 type person)
 (node102 name "Carrie N. Eater"))

The order and specific node ID's generated don't matter. Using any language that can support nested list-like structures like the above, wr ite code to (1) map a structure to a set of triples, with ID's generated as necessary, (2) map a set of triples to a nested structure. You can assume that any such set of triples does in fact represent a nested structure.

60MS is most concerned about the core mapping algorithms, not I/O, and code that is as clear and general as possible.