/* ------------------------------------------------------------------ A List of the Predicates Defined Below (In Order Of Definition): 1] hal_9000(Sentence, Response) 2] test_hal 3] test_hal_some_more 4] ask_hal(Sentence) 5] evaluate(ParseTree, Value) 6] tokenize(Sentence, Tokens) 7] first_word(Sentence, TheWord, RestOfSentence) is a helper for tokenize and has its own helper build_first_word(Sentence, WordSoFar, TheWord, RestOfSentence) 8] delimiter(Character) 9] append(First, Second, Third) 10] reverse(List, Reverse) which has the helper reverse_helper(ListNotYetReversed, ReverseSoFar, Reverse) 11] evaluate_number(StringNumber, Value) which has the helper evaluate_backward_number(BackwardStringNumber, Value) 12] digit_value(Character, Value) 13] debug(Message) */ /* ------------------------------------------------------------------ 1] hal_9000(Sentence, Response) is the start of construction of the program for the HAL 9000 computer. This first step is meant to compute numeric responses to simple English questions. Samples of the kinds of questions we are trying to handle are: How much is 3? How much is the sum of 3 and 4? How much is the sum of 3, 4, and 5? How much is the product of 12 and 5? How much is the product of 1, 2, 3, 4, and 5? How much is the sum of 1, 2, the product of 3 and 4, and 5? The above six questions are wellformed under the following rules. Each question begins with "How much is" and ends with a question mark. In general wherever a number could occur a sum or product could also occur. You can sum or product two or more numbers. If two numbers, then they are separated by `and'. If more than two numbers, then each number before the `and' is followed by a comma. Anything that is not well formed under the above is not well formed and an attempt to parse it will fail. For a competing implementation that taking a different approach, see 3001 by Arthur C. Clarke: Talk to HAL 9000 */ hal_9000(Sentence, Response) :- tokenize(Sentence, Tokens), parse(Tokens, question(ParseTree)), evaluate(ParseTree, Response). /* ------------------------------------------------------------------ 2] test_hal is a way of seeing how HAL 9000 will respond to a collection of test sentences. When run it looks like: # :- test_hal. "In response to: How much is 3?" hal_says(3) "In response to: How much is the sum of 3 and 4?" hal_says(7) "In response to: How much is the sum of 3, 4, and 5?" hal_says(12) "In response to: How much is the product of 12 and 5?" hal_says(60) "In response to: How much is the product of 1, 2, 3, 4, and 5?" hal_says(120) "In response to: How much is the sum of 1, and 2?" "In response to: How much is the sum of 1, 2, the product of 3 and 4, and 5?" hal_says(20) no Notice that in the case of an improperly formed question, such as How much is the sum of 1, and 2? there is no hal_says(). Instead, test_hal simply moves on to the next question. */ test_hal :- ask_hal("How much is 3?") . test_hal :- ask_hal("How much is the sum of 3 and 4?") . test_hal :- ask_hal("How much is the sum of 3, 4, and 5?") . test_hal :- ask_hal("How much is the product of 12 and 5?") . test_hal :- ask_hal("How much is the product of 1, 2, 3, 4, and 5?") . test_hal :- ask_hal("How much is the sum of 1, and 2?") . test_hal :- ask_hal("How much is the sum of 1, 2, the product of 3 and 4, and 5?") . /* 3] test_hal_some_more is a collection of other test questions for HAL 9000. */ test_hal_some_more :- ask_hal("How much is 2001 ?") . test_hal_some_more :- ask_hal("How much is the sum of 1, 2 and 3?") . test_hal_some_more :- ask_hal("How much is the sum of 1, 2, , and 3?") . test_hal_some_more :- ask_hal("How much is the sum of the product of 2 and 3 and 4?") . test_hal_some_more :- ask_hal("How much is the sum of 1, the product of 2, 3, and 4, and 5?") . test_hal_some_more :- ask_hal("How much is ?") . test_hal_some_more :- ask_hal("How much is the sum of 1 and 2 and 3?") . test_hal_some_more :- ask_hal("How much is the sum of 1, 2, and 3, ?") . test_hal_some_more :- ask_hal("How much is 2??") . test_hal_some_more :- ask_hal("How much is sum of 1 and 2?") . test_hal_some_more :- ask_hal("How much is the product of 2, and 3?") . test_hal_some_more :- ask_hal("Can computers think?") . /* ------------------------------------------------------------------ 4] ask_hal(Sentence) prints HAL 9000's response to Sentence and then fails. */ ask_hal(Sentence) :- append("In response to: ", Sentence, Introduction), print(Introduction), nl, hal_9000(Sentence, Response), print(hal_says(Response)), nl, false. /* ------------------------------------------------------------------ 5] evaluate(ParseTree, Value) calculates the Value that corresponds to ParseTree in a manner similar to Section 11.1 of the Prolog text [An Introduction to Logic Programming through Prolog by Michael Spivey]. */ evaluate(number(Number), Number) :- . evaluate(sum(First, Second), Third) :- evaluate(First, FirstValue), evaluate(Second, SecondValue), plus(FirstValue, SecondValue, Third). evaluate(product(First, Second), Third) :- evaluate(First, FirstValue), evaluate(Second, SecondValue), times(FirstValue, SecondValue, Third). /* ------------------------------------------------------------------ 6] tokenize(Sentence, Tokens) says whether or not Tokens is the list of words that form Sentence. It can't find the Sentence for given Tokens, but it can find the Tokens for a given Sentence. Since this program is processing English, tokens are the same as words. A word can be a delimiter or a sequence of characters that contains neither a space nor a delimiter, but is followed by a space, a delimiter, or the end of the list. */ tokenize(nil, nil) :- . tokenize(Sentence, TheWord:Tokens) :- not Sentence = nil, first_word(Sentence, TheWord, RestOfSentence), tokenize(RestOfSentence, Tokens). /* ------------------------------------------------------------------ 7] first_word(Sentence, TheWord, RestOfSentence) separates a list of characters called Sentence into a list of characters TheWord corresponding to the first word in Sentence and a list of characters called RestOfSentence which are the characters that come after TheWord. It does this by using the helping predicate build_first_word(Sentence, WordSoFar, TheWord, RestOfSentence) A word can be a delimiter or a sequence of characters that contains neither a space nor a delimiter, but is followed by a space, a delimiter, or the end of the list. */ first_word(Sentence, TheWord, RestOfSentence) :- build_first_word(Sentence, nil, TheWord, RestOfSentence). build_first_word(nil, nil, nil, nil) :- . build_first_word(nil, WordSoFar, TheWord, nil) :- not WordSoFar = nil, reverse(WordSoFar, TheWord). build_first_word(' ':RestOfSentence, WordSoFar, TheWord, RestOfSentence) :- not WordSoFar = nil, reverse(WordSoFar, TheWord). build_first_word(' ':RemainderOfSentence, nil, TheWord, RestOfSentence) :- build_first_word(RemainderOfSentence, nil, TheWord, RestOfSentence). build_first_word(FirstCharacter: RestOfSentence, WordSoFar, TheWord, FirstCharacter:RestOfSentence) :- delimiter(FirstCharacter), not WordSoFar = nil, reverse(WordSoFar, TheWord). build_first_word(FirstCharacter:RestOfSentence, nil, FirstCharacter:nil, RestOfSentence) :- delimiter(FirstCharacter). build_first_word(FirstCharacter: RemainderOfSentence, WordSoFar, TheWord, RestOfSentence) :- not FirstCharacter = ' ', not delimiter(FirstCharacter), build_first_word(RemainderOfSentence, FirstCharacter:WordSoFar, TheWord, RestOfSentence). /* ------------------------------------------------------------------ 8] delimiter(Character) is true iff Character is '?' or ','. */ delimiter('?') :- . delimiter(',') :- . /* ------------------------------------------------------------------ 9] append(First, Second, Third) appends two lists (First and Second) to produce a Third. Given any two of these, it will find the other. */ append(nil, Second, Second) :- . append(FirstOfFirst:RestOfFirst , Second, FirstOfFirst:Combined) :- append(RestOfFirst, Second, Combined). /* ------------------------------------------------------------------ 10] reverse(List, Reverse) associates a List with the Reverse of that list. To do its work more efficiently, it uses reverse_helper(ListNotYetReversed, ReverseSoFar, Reverse). If presented with the Reverse and asked for the List, it will find the List and then when it tries to see if there is a different list with the same reversal it goes into an infinite loop and runs out of memory. */ reverse(List, Reverse) :- reverse_helper(List, nil, Reverse). reverse_helper(nil, ReverseSoFar, ReverseSoFar) :- . reverse_helper(First:YetToReverse, ReverseSoFar, FullReverse) :- reverse_helper(YetToReverse, First:ReverseSoFar, FullReverse). /* ------------------------------------------------------------------ 11] evaluate_number(StringNumber, Value) associates the numeric Value that corresponds to the StringNumber string. If given the numeric value, this will compute the corresponding string; however, there is more than one such string and so it will return many responses. To simplify conversion, it reverses the StringNumber and then uses evaluate_backward_number(BackwardStringNumber, Value) to do the work. */ evaluate_number(StringNumber, Value) :- reverse(StringNumber, BackwardStringNumber), evaluate_backward_number(BackwardStringNumber, Value). evaluate_backward_number(nil, 0) :- . evaluate_backward_number(Digit:Rest, Value) :- evaluate_backward_number(Rest, ValueOfRest), digit_value(Digit, DigitValue), times(10, ValueOfRest, ValueOfRestTimes10), plus(DigitValue, ValueOfRestTimes10, Value). /* ------------------------------------------------------------------ 12] digit_value(Character, Value) associates the numeric Value that corresponds to the Character, which is a single digit. */ digit_value('0', 0) :- . digit_value('1', 1) :- . digit_value('2', 2) :- . digit_value('3', 3) :- . digit_value('4', 4) :- . digit_value('5', 5) :- . digit_value('6', 6) :- . digit_value('7', 7) :- . digit_value('8', 8) :- . digit_value('9', 9) :- . /* ------------------------------------------------------------------ 13] debug(Message) prints the message followed by a new line. This is convenient when you want to put in trace messages for debugging. always remember to remove any usage of debug from your code before handing it in. */ debug(Message) :- print(Message), nl.