From UBC Wiki
Jump to: navigation, search

Authors: Jimmy Lin, David Bole Ma

What is the problem?

Suppose you want to write a poem (eg. a Haiku) and you some bag of words that describe the topic of the poem. You want to arrange these words in such a way that follows the rules of a poem. In other words, how can we arrange the bag of words to be semantically correct and maybe somewhat meaningful?

What is the something extra?

Prolog serves as a good tool for representing some basic structures of the english language and we can extend this application to also ensure that results conform to what constitutes a poem format specified.



What did we learn from doing this?

While prolog is really good for verifying constraints, the backtracking isn't a golden hammer to problem solving.

I started the project off by specifying all the problem constraints and combined them in hopes of Prolog being able to magically spit out arbitrary valid solutions. Instead, prolog ran out of memory while traversing the infinite problem space. I then broke down some constraints and bound the problem space into something finite. Prolog was still unbearably slow. I rewrote constraints that could be used on sub-problems to do intermediate verifications to narrow the problem space further. It's runs better now...

...but turns out verifying english grammar is one of the constraints that can't be done on subproblems, since often invalid substrings can be part of a larger valid string. Thus, unless you have a trivially small dictionary, generating grammatically correct sentences is terribly slow and there doesn't appear to be a good heuristic for this.

In conclusion: You use Prolog for it's conciseness in expressing and performing verification tasks. However, for hard problems where performance is an issue it doesn't make things any easier than other languages.