# Copyright (c) 2009 Tim Freeman
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.
#
# (This is the standard MIT License, copied from
# http://www.opensource.org/licenses/mit-license.php on 24 Apr 2007.)
#desc General decision procedure for inferring laws of physics given
#desc observations of the world.
import bits
from speed_prior import Speed_prior, prefix_in
from bits import many_bits, Doesnt_match
import traceback

# Simple code for inferring the laws of physics.
# We take as input:
# problem -- a physics problem, probably a subclass of
#    Generic_physics_problem.  It should have generate_explanations and
#    matches methods. 
# error probability bound eps.  We ignore some possibilities, and they
#    have total a-priori probability eps, once we accept that the
#    events we are trying to explain actually happened.  (For the purposes of
#    this program we ignore the possibility of floating point underflow
#    causing eps to be exactly 0.0.)

# We produce the output:
#    A list of candidate laws of physics

# See http://www.idsia.ch/~juergen/coltspeed/node5.html for the idea
# of approximating the speed prior.  The correctness of the
# approximation requires that if a program p computes the right
# answer, we don't try any programs that are p with some more bits
# added to the end.  That makes is possible to apply the Kraft inequality.

def laws_of_physics(problem, eps):
    nmax = None
    n = 0
    all_matches = []
    while nmax is None or n <= nmax:
        minlen = None
        for explanation in problem.generate_explanations(n):
            if not prefix_in(all_matches, explanation):
                try:
                    problem.matches(explanation)
                    all_matches.append(explanation)
                    if minlen is None or minlen > explanation.program_length():
                        minlen = explanation.program_length()
                except Doesnt_match:
                    #traceback.print_exc()
                    pass
        if nmax is None and minlen is not None:
            nmax = n + 2 + minlen - bits.log2(eps)
        n += 1
    return all_matches

class Speed_prior_explanation(object):
    __slots__ = ["explanations", "name"]
    def __init__(self, explanations, name="Unnamed"):
        self.name = name
        self.explanations = explanations
        for e in explanations:
            # Let them all be none if we're making a sham version for
            # using gnerate_explanations.
            if explanations[0] is None:
                assert e is None, (
                    "Bogus explanations is %r" % (explanations,))
            else:
                assert e.__class__ == Speed_prior
    def __str__(self):
        try :
            name = self.name
        except:
            # We can get here if someone takes a subclass and then
            # the subclass's __init__ doesn't call our __init__.
            # Grr, I wish this language was statically typed.
            name = "Unnamed"
        return "%s(%s)" % (self.__class__.__name__, name)
    def __repr__(self):
        return self.__str__()
    def measure(self):
        result = reduce(lambda x,y: x * y,
                        map(lambda x: x.measure(), self.explanations))
        #    print "Total measure is %r" % (result,)
        return result
    def size(self):
        return reduce(lambda x,y: x+y,
                      map(lambda x: x.size(), self.explanations))
    def program_length(self):
        return reduce(lambda x,y: x+y,
                      map (lambda x: x.program_length(), self.explanations))
    def is_prefix(self, other):
        return reduce(lambda x, y: x and y,
                      map(lambda x, y: x.is_prefix(y),
                             self.explanations,
                             other.explanations))
    # To generate the possible explanations with a given size n,
    # make a sham explanation, then call generate_explanations on it.
    def generate_explanations(self, n):
        speed_priors = many_bits(
            n, [Speed_prior.generator]*len(self.explanations))
        return [self.__class__(explanations = e) for e in speed_priors]

class Generic_physics_problem(object):
    def __init__(self, explanation_class):
        self.explanation_class = explanation_class
    # n is the complexity of the explanations that should be generated.
    def generate_explanations(self, n):
        # self.explanation_class is the class we got at init time,
        # so self.explanation_class() instantiates that class.  It
        # isn't a method call, even though it looks kind of like a
        # method call.
        return self.explanation_class().generate_explanations(n)