# should be ambenv.rb

# just jump down to the bottom of the file for the "demo" procedure
# that shows the interesting things you can do with this.

# The algorithm for implementing this was heavily inspired by chapter 14
# of "Teach Yourself Scheme in Finum Days"
# http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-16.html

class NoMoreAlternatives < Exception
end

class AmbEnvironment
  attr :ambfail
  def initialize
    @ambfail = Proc.new { raise NoMoreAlternatives }
  end
  def amb(*choices)
    enumAmb(choices)
  end
  def assert(condition)
    if ! condition
      amb
    end
  end
  def findall
    retval = []
    prevambfail = @ambfail
    if callcc {|k|
	@ambfail = Proc.new {k.call(false);}
	retval.push(yield);
	k.call(true);
      }
      @ambfail.call
    end
    @ambfail = prevambfail
    retval
  end
  def enumAmb(enumerable)
    prevambfail = @ambfail
    callcc {|ambret|
      enumerable.each {|alt|
	callcc {|eachret|
	  @ambfail = Proc.new {
	    @ambfail = prevambfail
	    eachret.call
	  }
	  ambret.call(alt)
	}
      }
      @ambfail.call
    }
  end
end

module Enumerable
  def amb(ambenv)
    ambenv.enumAmb(self)
  end
end

def demo
  ae = AmbEnvironment.new

# amb as map
  squareList = ae.findall {
    j = ae.amb(1,2,3,4,5,6,9)
    j*j
  }

  puts(squareList.inspect)

# Find pythagorean triples the hard way
  ae.findall {
    j = (1..25).amb(ae)
    k = (j..25).amb(ae)
    l = Math.sqrt(j*j + k*k)
    ae.assert(l.ceil == l.floor)
    puts ([j,k,l.floor].inspect)
  }

#  This problem was lifted from Teach Yourself Scheme in Fixnum Days,
#  who lifted it from J A H Hunter's "Mathematical Brain-Teasers".

#  The Kalotans are a tribe with a peculiar quirk. Their males always
#  tell the truth. Their females never make two consecutive true
#  statements, or two consecutive untrue statements.

#  An anthropologist (let's call him Worf) has begun to study
#  them. Worf does not yet know the Kalotan language. One day, he
#  meets a Kalotan (heterosexual) couple and their child Kibi. Worf
#  asks Kibi: ``Are you a boy?'' Kibi answers in Kalotan, which of
#  course Worf doesn't understand.

#  Worf turns to the parents (who know English) for explanation. One
#  of them says: ``Kibi said: `I am a boy.' '' The other adds: ``Kibi
#  is a girl. Kibi lied.''

#  Solve for the sex of the parents and Kibi.

  ae.findall {

    parentGender1 = ae.amb("M", "F")
    parentGender2 = ae.amb("M", "F")
    kibiGender = ae.amb("M", "F")
    kibiSaid = ae.amb("M", "F")
    kibiLied = ae.amb(true, false)
    
    ae.assert(parentGender1 != parentGender2)
    
    if kibiGender == "M"
      ae.assert(! kibiLied )
    end
    if kibiLied
      ae.assert( kibiSaid != kibiGender )
    else
      ae.assert( kibiSaid == kibiGender )
    end
    
    if parentGender1 == "M"
      ae.assert( kibiSaid == "M" )
    end

    if parentGender2 == "M"
      ae.assert( kibiGender == "F" )
      ae.assert( kibiLied )
    else
      ae.assert( (kibiGender == "F") ^ kibiLied )
    end
    
    [ parentGender1, parentGender2, kibiGender, kibiSaid, kibiLied ]
  }
end