Courses/CS 460/Fall 2005/Homework/Andre Liv/Oct 29

From CSWiki

[edit] Homework 5

declare
   % provided helper functions
   proc {AllInstantiated Xs Values}
      {ForAll Xs proc {$ X} {IsIn X Values} end}
   end

   proc {Append ?Xs ?Ys ?Zs}
      choice
         Xs = nil 
         Ys = Zs
         [] X Xr in
         Xs = X | Xr
         Zs = X | {Append Xr Ys}
      end
   end

   fun {GetFields Field Elts}
      {Map Elts fun {$ Elt} Elt.Field end}
   end

   fun {IndexOf X Xs}
      fun {IndexOf3 X Xs N}
         case Xs of
	    nil then fail
            [] Y | Rest then
	    if X == Y then N else {IndexOf3 X Rest N+1} end
         end
      end
      in
         {IndexOf3 X Xs 1}
   end

   proc {IsIn ?X Xs} {Append _ X|_ Xs} end

   proc {IsAnElt ?X Elts} {IsIn X {Record.toList Elts}} end

   % Generate thread bombs that ensure that all the members
   % of List are distinct.
      proc {AllDistinct Xs}
         case Xs of X|Xr then
            for Y in Xr do
               thread X==Y = false end
            end
            {AllDistinct Xr}
            else skip end
      end


   proc {NotEqual X Y} thread X == Y = false end end

   proc {Precedes ?X1 ?X2 Xs}
      thread {IndexOf X1 Xs} < {IndexOf X2 Xs} = true end
   end

   fun {Match R1 R2}
      {Record.all
      {Record.zip R1 R2 fun {$ A B} A == B end}
      fun {$ X} X == true end}
   end

   proc {Propagate Condition Result R}
      thread if {Match Condition R} then {UnifyRecs Result R} end end    
   end

   proc {PropagateAll Condition Result Rec}
      {Record.forAll Rec proc {$ R} {Propagate Condition Result R} end}
   end

   proc {UnifyRecs R1 R2}
      {Record.zip R1 R2 fun {$ A B} A = B end _}
   end

local
   Fruits = [bananas apple pear orange]
   Places = [grass rock tree stream]
   
   proc {Clue1 Monkeys}
      %Sam, who doesn't like bananas,   
      {NotEqual Monkeys.sam.fruit bananas}
      % likes sitting on the grass.
      Monkeys.sam.place = grass      
   end
   proc {Clue2 Monkeys}
      %The monkey who sat on the rock ate the apple. 
      {IsAnElt properties(place:rock fruit:apple) Monkeys}
      {NotEqual Monkeys.sam.fruit apple}
      % The monkey who ate the pear didn't sit on the tree branch.
      {NotEqual Monkeys.sam.place tree}
      choice
	 Monkeys.sam.fruit = pear
      []
	 Monkeys.sam.fruit = orange
      end  
   end 
   proc {Clue3 Monkeys}
      % Anna sat by the stream but she didn't eat the pear.
      Monkeys.anna.place = stream
      {NotEqual Monkeys.anna.fruit pear}
      {NotEqual Monkeys.anna.fruit apple}
      choice
	 Monkeys.anna.fruit = orange
      []
	 Monkeys.anna.fruit = bananas
      end
   end
   proc {Clue4 Monkeys}
      % Harriet didn't sit on the tree branch.
      {NotEqual Monkeys.harriet.place tree}
      % Mike doesn't like oranges
      {NotEqual Monkeys.mike.fruit orange}
      choice
	 {IsAnElt properties(place:tree fruit:orange) Monkeys}
      []
	 {IsAnElt properties(place:tree fruit:bananas) Monkeys}
      end
   end

   fun {FourMonkeys}
      Monkeys = {MakeRecord monkeys [sam anna harriet mike]}
      Fs
      Ps
      MonkeyList = {Record.toList Monkeys}
   in
      % Create property records for each sister.
      {Record.forAll Monkeys proc {$ S} S = {Record.make properties [fruit place]} end}

      % Get the list of Fruits and Places variables.
      % Constrain them to be distinct.
      Fs = {GetFields fruit MonkeyList }
      {AllDistinct Fs}
      Ps = {GetFields place MonkeyList }
      {AllDistinct Ps}

      % Run the clues
      {Clue1 Monkeys}
      {Clue2 Monkeys}
      {Clue3 Monkeys}
      {Clue4 Monkeys}
      
      % Ensure that every fruit and place has a value.
      {AllInstantiated Fs Fruits}
      {AllInstantiated Ps Places}

      % Return Monkeys as the answer
      Monkeys
   end
in
   {Browse {SearchAll FourMonkeys}}
end