Assignment 10: Prolog for Fun and Profit and Spampede v2.0
Due Monday, Nov 16 by 11:59 pm

Submission and pair programming

For this problem, you will submit (at least) two things:

• Spampede.java for the Spampede v2.0 problem (plus any and all support files).  [individual]
• logic.pl for the Knights/Knaves problem [pair or individual]

Part 1: Spampede version 2.0! (50 points) [Individual]

In this part of the assignment you will improve the design and the functionality of your  spampede program. Your tasks are the following:

1. In a file called part1.txt, write a few sentences about the main design weaknesses in your original program.  Your reasoning does not have to be detailed, but should refer to some aspect of good coding style (e.g., my functions were too long, I used too many magic numbers, my lack of incremental design made my code very un-modular, etc.)
   
   
2. Improve your design. Almost all code has room for improvement in its design, even if the grutors did not take off points. Identify a number of ways that your design could be improved and make those changes to your code. Detail and justify your changes in the part1.txt file. The exact number of changes will depend on your original design, but I am looking for somewhere around 2-3. However, note that the quality of your improvements and your justification is more important than the quantity.
   
   If you are really stuck on what to improve, come talk to me.  In rare cases, the original code was really so good that there's nothing substantial to improve in the design.


3. Improve your functionality: Fix any problems with the functionality of your program that you or the grutors encountered. Document those changes in your part1.txt file. If you did not have any errors in functionality, add one significant bonus feature to the play of your game.

This assignment is intentionally (slightly) vague to help get you thinking about the issues in real-world software design. Keep in mind the following elements of good programming as you do this part of the assignment:

• Magic numbers (don't use them)
• Modular design (i.e. code doesn't have a lot of interwoven dependencies)
• Getters and setters
• Good variable and function names
• Small methods
• Public vs. private
• Good comments
• Abstraction and code reuse
• Code distribution between classes
• Spacing and code readability

For this part, you should submit your part1.txt file as well as all of the files needed to play your Spampede game.  You should also put your new Spampede game on the web just like you did before.  Note that while you can submit Spampede.java as a homework file, ALL OTHER FILES SHOULD BE SUBMITTED AS SUPPORT FILES.

Part 2: The Island of Knights and Knaves! (50 Points) [Pair or Individual]

For this problem, your task is to create a prolog program that can identify (id) the possible speakers of statements you overhear on the Island of Knights and Knaves. Your file should be named logic.pl.

On that island, there are three kinds of inhabitants:

• knights, who speak only true statements.
• knaves, who speak only false statements.
• and humans, who can speak both true and false statements (and may not know which one!)

For this problem, write a Prolog predicate

id( Expr, Speaker )

knight
knave
human

Possible Expressions:

Although the Expr input to your id rule will always be a fully-instantiated list as far as Prolog is concerned, it will represent an arbitrary parse tree for a logical expression that may contain compositions of the following items:

• The literal truth values t (meaning true) and f (meaning false)



• The logical operators and, or, not, iff, ifthen. You are familiar with and, or, not. As for the other two:
  • [iff, L, R] is true when the truth values of L and R are the same.
  • [ifthen, L, R] is true when "L implies R," that is, when L is false or R is true.


• Of these five logical operators, not is unary and forms logical parse trees via
  • [not, T], where T is a logical parse tree or literal or literal integer (see below).
  
  The other four operators, and, or, iff, ifthen are binary and form logical parse trees via
  • [and, L, R]
  • [or, L, R]
  • [iff, L, R]
  • [ifthen, L, R]


• Also, literal integers 1, 2, 3, ... may be present in Expr. If such a literal integer is present, it represents a logical variable that may take on either the value t or f. If the same integer appears in more than one place in an Expr, any substitution of t or f for one instance of that integer must also be substituted identically for all other instances of that integer. There are some examples of subst rule below that will help clarify this.
  
  Warning! These integers represent logical variables in the parse tree, represented by a fully-instantiated Prolog list. They are not Prolog variables in that list. Although it might seem tempting to use Prolog variables as logical variables, mixing the implementation language with the logical language leads to trouble, rather than to efficiency!

Examples    The examples will help clarify the format of

• the logical parse trees
• the way in which literal integers can represent logical (but not Prolog) variables within those logical parse trees
• the way id works (and a few examples of moderate-sized tautologies)
• one way that subst might be written -- you are free to decompose this problem as you see fit, but a few possiblities are listed after these examples.

   id( t, Who ).
   Who = human ;
   Who = knight % need not wait for all repetitions of this - hit Enter
   Yes 
   
   id( [ifthen, f, 1], Who ).
   Who = human ;
   Who = knight % need not wait for all repetitions of this - hit Enter
   Yes 
   
   id( [ifthen, 1, [ifthen, 2, 1]], Who ).
   Who = human ;
   Who = knight % need not wait for all repetitions of this - hit Enter
   Yes 
   
   id( [iff, [ifthen, [and, 1, 2], 3], [ifthen, 1, [ifthen, 2, 3]]], Who ).
   Who = human ;
   Who = knight % need not wait for all repetitions of this - hit Enter
   Yes 
   
   id( [iff, 1, [not, 1]], Who ).
   Who = human ;
   Who = knave % need not wait for all repetitions of this - hit Enter
   Yes 
   
   id( [and, 1, 2], Who ).
   Who = human ;
   No
   

  It's not a good idea to use setof to test your knight/knave identifier. This is because it's possible to write the id in such a way that there are many repeats of a single result, and setof will try to generate them all. This can take too long!

Possible helper rules:

This problem does not require a lot of code, but it does require some careful thinking about

• how to check whether an expression Expr contains a literal integer representing a logical variable
• how to determine whether an expression, even containing only leaves of t and f, is a tautology or unsatisfiable or neither
• how to substitute t or f into such an expression, yielding a new expression -- there are a couple examples of this above
• how to avoid having Prolog head off infinitely searching for bindings that will not be helpful

• noVars( Expr ) true if Expr has no logical variables, i.e., literal integers
  
  Here is a subset of the code we wrote in class, which you may want to adapt:

   noVars( t ).
   noVars( f ).
   noVars( [_, L, R] ) :- noVars( L ), noVars( R ).
   

  Note that you'll need to handle not, as well.
  
  
• getVar( Expr, N ) true if N is an integer representing a variable that is currently contained in Expr. Here is a slight variant (that adds speed/efficiency!!) to the code we wrote in class:

   getVar( N, N ) :- number( N ).
   getVar( [_, L, R], N ) :- getVar( L, N ); (noVars(L), getVar( R, N )). 
   

  Notice that this variant only descends the second branch if there are no variables in the first branch! This will make the expansion much more succinct and, thus, faster and memory-efficient. Be sure to use this (the code may not complete in the time/memory available otherwise!)
  
  Also remember to handle not here as well.
  
  That said, it's worth mentioning that the above code for getVar will not bind to more than one variable in a single invokation. For example,

   ?- getVar([ifthen, 1, 2], X).
   X = 1 ;
   No
   

  Although this may seem like a problem, once you substitute a truth value for 1, the next call to getVar will happily return the 2. And did we mention it's much faster?
  
  
• taut( Expr ) would be true if Expr is a tautology (check for no logical variables first...)
• unsat( Expr ) would be true if Expr is unsatisfiable (check for no logical variables first...)
• subst( N, TorF, OldExpr, NewExpr ) would be true if N is an integer representing a variable that is currently contained in OldExpr, and TorF is t or f, and NewExpr is identical to OldExpr, except that all instances of N have been replaced with the literal value of TorF.
  
  Here is an example of how subst might work:

   subst( 1, t, [and, [not, 1], 1], NewExpr ).
  
   NewExpr = [and, [not, t], t]
   

Submit this problem as logic.pl.

Optional Extra Credit (Individual)

• ec.txt: A file describing what you are submitting for extra credit.  Be sure to include (1) what the original problem was, (2) what you missed the first time, and (3) what you have improved this time around.  
• All files needed to run your extra credit submission (as support files).