to_delete / dreamcoder /fragmentGrammar.py

Fraser-Greenlee

add dreamcoder codebase

e1c1753 almost 5 years ago

19.8 kB

from dreamcoder.fragmentUtilities import *
from dreamcoder.grammar import *
from dreamcoder.program import *

from itertools import chain
import time


class FragmentGrammar(object):
    def __init__(self, logVariable, productions):
        self.logVariable = logVariable
        self.productions = productions
        self.likelihoodCache = {}

    def clearCache(self):
        self.likelihoodCache = {}

    def __repr__(self):
        return "FragmentGrammar(logVariable={self.logVariable}, productions={self.productions}".format(
            self=self)

    def __str__(self):
        def productionKey(xxx_todo_changeme):
            (l, t, p) = xxx_todo_changeme
            return not isinstance(p, Primitive), -l
        return "\n".join(["%f\tt0\t$_" % self.logVariable] + ["%f\t%s\t%s" % (l, t, p)
                                                              for l, t, p in sorted(self.productions, key=productionKey)])

    def buildCandidates(self, context, environment, request):
        candidates = []
        variableCandidates = []
        for l, t, p in self.productions:
            try:
                newContext, t = t.instantiate(context)
                newContext = newContext.unify(t.returns(), request)
                candidates.append((l, newContext,
                                   t.apply(newContext),
                                   p))
            except UnificationFailure:
                continue
        for j, t in enumerate(environment):
            try:
                newContext = context.unify(t.returns(), request)
                variableCandidates.append((newContext,
                                           t.apply(newContext),
                                           Index(j)))
            except UnificationFailure:
                continue
        if variableCandidates:
            z = math.log(len(variableCandidates))
            for newContext, newType, index in variableCandidates:
                candidates.append(
                    (self.logVariable - z, newContext, newType, index))

        z = lse([candidate[0] for candidate in candidates])
        return [(l - z, c, t, p) for l, c, t, p in candidates]

    def logLikelihood(self, request, expression):
        _, l, _ = self._logLikelihood(Context.EMPTY, [], request, expression)
        if invalid(l):
            f = 'failures/likelihoodFailure%s.pickle' % (time() + getPID())
            eprint("PANIC: Invalid log likelihood. expression:",
                   expression, "tp:", request, "Exported to:", f)
            with open(f, 'wb') as handle:
                pickle.dump((self, request, expression), handle)
            assert False
        return l

    def closedUses(self, request, expression):
        _, l, u = self._logLikelihood(Context.EMPTY, [], request, expression)
        return l, u

    def _logLikelihood(self, context, environment, request, expression):
        '''returns (context, log likelihood, uses)'''

        # We can cash likelihood calculations faster whenever they don't involve type inference
        # This is because they are guaranteed to not modify the context,
        polymorphic = request.isPolymorphic or any(
            v.isPolymorphic for v in environment)
        # For some reason polymorphic caching slows it down
        shouldDoCaching = not polymorphic

        # Caching
        if shouldDoCaching:
            if polymorphic:
                inTypes = canonicalTypes(
                    [request.apply(context)] + [v.apply(context) for v in environment])
            else:
                inTypes = canonicalTypes([request] + environment)
            cacheKey = (tuple(inTypes), expression)
            if cacheKey in self.likelihoodCache:
                outTypes, l, u = self.likelihoodCache[cacheKey]
                context, instantiatedTypes = instantiateTypes(
                    context, outTypes)
                outRequest = instantiatedTypes[0]
                outEnvironment = instantiatedTypes[1:]
                # eprint("request:", request.apply(context), "environment:",
                #        [ v.apply(context) for v in environment ])
                # eprint("will be unified with: out request:",outRequest,"out environment",outEnvironment)
                if polymorphic:
                    context = context.unify(request, outRequest)
                    for v, vp in zip(environment, outEnvironment):
                        context = context.unify(v, vp)
                return context, l, u

        if request.isArrow():
            if not isinstance(expression, Abstraction):
                return (context, NEGATIVEINFINITY, Uses.empty)
            return self._logLikelihood(context,
                                       [request.arguments[0]] + environment,
                                       request.arguments[1],
                                       expression.body)

        # Not a function type

        # Construct and normalize the candidate productions
        candidates = self.buildCandidates(context, environment, request)

        # Consider each way of breaking the expression up into a
        # function and arguments
        totalLikelihood = NEGATIVEINFINITY
        weightedUses = []

        possibleVariables = float(int(any(isinstance(candidate, Index)
                                          for _, _, _, candidate in candidates)))
        possibleUses = {candidate: 1. for _, _, _, candidate in candidates
                        if not isinstance(candidate, Index)}

        for f, xs in expression.applicationParses():
            for candidateLikelihood, newContext, tp, production in candidates:
                variableBindings = {}
                # This is a variable in the environment
                if production.isIndex:
                    if production != f:
                        continue
                else:
                    try:
                        newContext, fragmentType, variableBindings = \
                            Matcher.match(newContext, production, f, len(xs))
                        # This is necessary because the types of the variable
                        # bindings and holes need to match up w/ request
                        fragmentTypeTemplate = request
                        for _ in xs:
                            newContext, newVariable = newContext.makeVariable()
                            fragmentTypeTemplate = arrow(
                                newVariable, fragmentTypeTemplate)
                        newContext = newContext.unify(
                            fragmentType, fragmentTypeTemplate)
                        # update the unified type
                        tp = fragmentType.apply(newContext)
                    except MatchFailure:
                        continue

                argumentTypes = tp.functionArguments()
                if len(xs) != len(argumentTypes):
                    # I think that this is some kind of bug. But I can't figure it out right now.
                    # As a hack, count this as though it were a failure
                    continue
                    #raise GrammarFailure('len(xs) != len(argumentTypes): tp={}, xs={}'.format(tp, xs))

                thisLikelihood = candidateLikelihood
                if isinstance(production, Index):
                    theseUses = Uses(possibleVariables=possibleVariables,
                                     actualVariables=1.,
                                     possibleUses=possibleUses.copy(),
                                     actualUses={})
                else:
                    theseUses = Uses(possibleVariables=possibleVariables,
                                     actualVariables=0.,
                                     possibleUses=possibleUses.copy(),
                                     actualUses={production: 1.})

                # Accumulate likelihood from free variables and holes and
                # arguments
                for freeType, freeExpression in chain(
                        variableBindings.values(), zip(argumentTypes, xs)):
                    freeType = freeType.apply(newContext)
                    newContext, expressionLikelihood, newUses = self._logLikelihood(
                        newContext, environment, freeType, freeExpression)
                    if expressionLikelihood is NEGATIVEINFINITY:
                        thisLikelihood = NEGATIVEINFINITY
                        break

                    thisLikelihood += expressionLikelihood
                    theseUses += newUses

                if thisLikelihood is NEGATIVEINFINITY:
                    continue

                weightedUses.append((thisLikelihood, theseUses))
                totalLikelihood = lse(totalLikelihood, thisLikelihood)

                # Any of these new context objects should be equally good
                context = newContext

        if totalLikelihood is NEGATIVEINFINITY:
            return context, totalLikelihood, Uses.empty
        assert weightedUses != []

        allUses = Uses.join(totalLikelihood, *weightedUses)

        # memoize result
        if shouldDoCaching:
            outTypes = [request.apply(context)] + \
                [v.apply(context) for v in environment]
            outTypes = canonicalTypes(outTypes)
            self.likelihoodCache[cacheKey] = (
                outTypes, totalLikelihood, allUses)

        return context, totalLikelihood, allUses

    def expectedUses(self, frontiers):
        if len(list(frontiers)) == 0:
            return Uses()
        likelihoods = [[(l + entry.logLikelihood, u)
                        for entry in frontier
                        for l, u in [self.closedUses(frontier.task.request, entry.program)]]
                       for frontier in frontiers]
        zs = (lse([l for l, _ in ls]) for ls in likelihoods)
        return sum(math.exp(l - z) * u
                   for z, frontier in zip(zs, likelihoods)
                   for l, u in frontier)

    def insideOutside(self, frontiers, pseudoCounts):
        uses = self.expectedUses(frontiers)
        return FragmentGrammar(log(uses.actualVariables +
                                   pseudoCounts) -
                               log(max(uses.possibleVariables, 1.)), [(log(uses.actualUses.get(p, 0.) +
                                                                           pseudoCounts) -
                                                                       log(uses.possibleUses.get(p, 0.) +
                                                                           pseudoCounts), t, p) for _, t, p in self.productions])

    def jointFrontiersLikelihood(self, frontiers):
        return sum(lse([entry.logLikelihood + self.logLikelihood(frontier.task.request, entry.program)
                        for entry in frontier])
                   for frontier in frontiers)

    def jointFrontiersMDL(self, frontiers, CPUs=1):
        return sum(
            parallelMap(
                CPUs,
                lambda frontier: max(
                    entry.logLikelihood +
                    self.logLikelihood(
                        frontier.task.request,
                        entry.program) for entry in frontier),
                frontiers))

    def __len__(self): return len(self.productions)

    @staticmethod
    def fromGrammar(g):
        return FragmentGrammar(g.logVariable, g.productions)

    def toGrammar(self):
        return Grammar(self.logVariable, [(l, q.infer(), q)
                                          for l, t, p in self.productions
                                          for q in [defragment(p)]])

    @property
    def primitives(self): return [p for _, _, p in self.productions]

    @staticmethod
    def uniform(productions):
        return FragmentGrammar(0., [(0., p.infer(), p) for p in productions])

    def normalize(self):
        z = lse([l for l, t, p in self.productions] + [self.logVariable])
        return FragmentGrammar(self.logVariable - z,
                               [(l - z, t, p) for l, t, p in self.productions])

    def makeUniform(self):
        return FragmentGrammar(0., [(0., p.infer(), p)
                                    for _, _, p in self.productions])

    def rescoreFrontier(self, frontier):
        return Frontier([FrontierEntry(e.program,
                                       logPrior=self.logLikelihood(frontier.task.request, e.program),
                                       logLikelihood=e.logLikelihood)
                         for e in frontier],
                        frontier.task)

    @staticmethod
    def induceFromFrontiers(
            g0,
            frontiers,
            _=None,
            topK=1,
            topk_use_only_likelihood=False,
            pseudoCounts=1.0,
            aic=1.0,
            structurePenalty=0.001,
            a=0,
            CPUs=1):
        _ = topk_use_only_likelihood # not used in python compressor
        originalFrontiers = frontiers
        frontiers = [frontier for frontier in frontiers if not frontier.empty]
        eprint("Inducing a grammar from", len(frontiers), "frontiers")

        bestGrammar = FragmentGrammar.fromGrammar(g0)
        oldJoint = bestGrammar.jointFrontiersMDL(frontiers, CPUs=1)

        # "restricted frontiers" only contain the top K according to the best grammar
        def restrictFrontiers():
            return parallelMap(
                CPUs,
                lambda f: bestGrammar.rescoreFrontier(f).topK(topK),
                frontiers)
        restrictedFrontiers = []

        def grammarScore(g):
            g = g.makeUniform().insideOutside(restrictedFrontiers, pseudoCounts)
            likelihood = g.jointFrontiersMDL(restrictedFrontiers)
            structure = sum(primitiveSize(p) for p in g.primitives)
            score = likelihood - aic * len(g) - structurePenalty * structure
            g.clearCache()
            if invalid(score):
                # FIXME: This should never occur but it does anyway
                score = float('-inf')
            return score, g

        if aic is not POSITIVEINFINITY:
            restrictedFrontiers = restrictFrontiers()
            bestScore, _ = grammarScore(bestGrammar)
            eprint("Starting score", bestScore)
            while True:
                restrictedFrontiers = restrictFrontiers()
                fragments = [f
                             for f in proposeFragmentsFromFrontiers(restrictedFrontiers, a, CPUs=CPUs)
                             if f not in bestGrammar.primitives
                             and defragment(f) not in bestGrammar.primitives]
                eprint("Proposed %d fragments." % len(fragments))

                candidateGrammars = [
                    FragmentGrammar.uniform(
                        bestGrammar.primitives +
                        [fragment]) for fragment in fragments]
                if not candidateGrammars:
                    break

                scoredFragments = parallelMap(CPUs, grammarScore, candidateGrammars,
                                              # Each process handles up to 100
                                              # grammars at a time, a "job"
                                              chunksize=max(
                                                  1, min(len(candidateGrammars) // CPUs, 100)),
                                              # maxTasks: Maximum number of jobs allocated to a process
                                              # This means that after evaluating this*chunk many grammars,
                                              # we killed the process, freeing up its memory.
                                              # In exchange we pay the cost of spawning a new process.
                                              # We should play with this number,
                                              # figuring out how big we can make it without
                                              # running out of memory.
                                              maxtasksperchild=5)
                newScore, newGrammar = max(scoredFragments, key=lambda sg: sg[0])

                if newScore <= bestScore:
                    break
                dS = newScore - bestScore
                bestScore, bestGrammar = newScore, newGrammar
                newPrimitiveLikelihood, newType, newPrimitive = bestGrammar.productions[-1]
                expectedUses = bestGrammar.expectedUses(
                    restrictedFrontiers).actualUses.get(newPrimitive, 0)
                eprint(
                    "New primitive of type %s\t%s\t\n(score = %f; dScore = %f; <uses> = %f)" %
                    (newType, newPrimitive, newScore, dS, expectedUses))

                # Rewrite the frontiers in terms of the new fragment
                concretePrimitive = defragment(newPrimitive)
                bestGrammar.productions[-1] = (newPrimitiveLikelihood,
                                               concretePrimitive.tp,
                                               concretePrimitive)
                frontiers = parallelMap(
                    CPUs, lambda frontier: bestGrammar.rescoreFrontier(
                        RewriteFragments.rewriteFrontier(
                            frontier, newPrimitive)), frontiers)
                eprint(
                    "\t(<uses> in rewritten frontiers: %f)" %
                    (bestGrammar.expectedUses(frontiers).actualUses[concretePrimitive]))
        else:
            eprint("Skipping fragment proposals")

        if False:
            # Reestimate the parameters using the entire frontiers
            bestGrammar = bestGrammar.makeUniform().insideOutside(frontiers, pseudoCounts)
        elif True:
            # Reestimate the parameters using the best programs
            restrictedFrontiers = restrictFrontiers()
            bestGrammar = bestGrammar.makeUniform().insideOutside(
                restrictedFrontiers, pseudoCounts)
        else:
            # Use parameters that were found during search
            pass

        eprint("Old joint = %f\tNew joint = %f\n" %
               (oldJoint, bestGrammar.jointFrontiersMDL(frontiers, CPUs=CPUs)))
        # Return all of the frontiers, which have now been rewritten to use the
        # new fragments
        frontiers = {f.task: f for f in frontiers}
        frontiers = [frontiers.get(f.task, f)
                     for f in originalFrontiers]

        productionUses = bestGrammar.expectedUses(
            [f for f in frontiers if not f.empty]).actualUses
        productionUses = {
            p: productionUses.get(
                p, 0.) for p in bestGrammar.primitives}
        possibleUses = bestGrammar.expectedUses(
            [f for f in frontiers if not f.empty]).possibleUses
        possibleUses = {
            p: possibleUses.get(
                p, 0.) for p in bestGrammar.primitives}

        for p in bestGrammar.primitives:
            eprint("%f / %f\t%s" % (productionUses[p],
                                    possibleUses[p],
                                    p))

        bestGrammar.clearCache()

        grammar = bestGrammar.toGrammar()

        if False and \
           any(productionUses.get(p, 0) < 0.5 for p in grammar.primitives if p.isInvented):
            uselessProductions = [ p for p in grammar.primitives                 
                                   if p.isInvented and productionUses.get(p, 0) < 0.5]
            eprint("The following invented primitives are no longer needed, removing them...")
            eprint("\t" + "\t\n".join(map(str, uselessProductions)))
            grammar = grammar.removeProductions(uselessProductions)

        return grammar, frontiers

	from dreamcoder.fragmentUtilities import *
	from dreamcoder.grammar import *
	from dreamcoder.program import *

	from itertools import chain
	import time


	class FragmentGrammar(object):
	def __init__(self, logVariable, productions):
	self.logVariable = logVariable
	self.productions = productions
	self.likelihoodCache = {}

	def clearCache(self):
	self.likelihoodCache = {}

	def __repr__(self):
	return "FragmentGrammar(logVariable={self.logVariable}, productions={self.productions}".format(
	self=self)

	def __str__(self):
	def productionKey(xxx_todo_changeme):
	(l, t, p) = xxx_todo_changeme
	return not isinstance(p, Primitive), -l
	return "\n".join(["%f\tt0\t$_" % self.logVariable] + ["%f\t%s\t%s" % (l, t, p)
	for l, t, p in sorted(self.productions, key=productionKey)])

	def buildCandidates(self, context, environment, request):
	candidates = []
	variableCandidates = []
	for l, t, p in self.productions:
	try:
	newContext, t = t.instantiate(context)
	newContext = newContext.unify(t.returns(), request)
	candidates.append((l, newContext,
	t.apply(newContext),
	p))
	except UnificationFailure:
	continue
	for j, t in enumerate(environment):
	try:
	newContext = context.unify(t.returns(), request)
	variableCandidates.append((newContext,
	t.apply(newContext),
	Index(j)))
	except UnificationFailure:
	continue
	if variableCandidates:
	z = math.log(len(variableCandidates))
	for newContext, newType, index in variableCandidates:
	candidates.append(
	(self.logVariable - z, newContext, newType, index))

	z = lse([candidate[0] for candidate in candidates])
	return [(l - z, c, t, p) for l, c, t, p in candidates]

	def logLikelihood(self, request, expression):
	_, l, _ = self._logLikelihood(Context.EMPTY, [], request, expression)
	if invalid(l):
	f = 'failures/likelihoodFailure%s.pickle' % (time() + getPID())
	eprint("PANIC: Invalid log likelihood. expression:",
	expression, "tp:", request, "Exported to:", f)
	with open(f, 'wb') as handle:
	pickle.dump((self, request, expression), handle)
	assert False
	return l

	def closedUses(self, request, expression):
	_, l, u = self._logLikelihood(Context.EMPTY, [], request, expression)
	return l, u

	def _logLikelihood(self, context, environment, request, expression):
	'''returns (context, log likelihood, uses)'''

	# We can cash likelihood calculations faster whenever they don't involve type inference
	# This is because they are guaranteed to not modify the context,
	polymorphic = request.isPolymorphic or any(
	v.isPolymorphic for v in environment)
	# For some reason polymorphic caching slows it down
	shouldDoCaching = not polymorphic

	# Caching
	if shouldDoCaching:
	if polymorphic:
	inTypes = canonicalTypes(
	[request.apply(context)] + [v.apply(context) for v in environment])
	else:
	inTypes = canonicalTypes([request] + environment)
	cacheKey = (tuple(inTypes), expression)
	if cacheKey in self.likelihoodCache:
	outTypes, l, u = self.likelihoodCache[cacheKey]
	context, instantiatedTypes = instantiateTypes(
	context, outTypes)
	outRequest = instantiatedTypes[0]
	outEnvironment = instantiatedTypes[1:]
	# eprint("request:", request.apply(context), "environment:",
	# [ v.apply(context) for v in environment ])
	# eprint("will be unified with: out request:",outRequest,"out environment",outEnvironment)
	if polymorphic:
	context = context.unify(request, outRequest)
	for v, vp in zip(environment, outEnvironment):
	context = context.unify(v, vp)
	return context, l, u

	if request.isArrow():
	if not isinstance(expression, Abstraction):
	return (context, NEGATIVEINFINITY, Uses.empty)
	return self._logLikelihood(context,
	[request.arguments[0]] + environment,
	request.arguments[1],
	expression.body)

	# Not a function type

	# Construct and normalize the candidate productions
	candidates = self.buildCandidates(context, environment, request)

	# Consider each way of breaking the expression up into a
	# function and arguments
	totalLikelihood = NEGATIVEINFINITY
	weightedUses = []

	possibleVariables = float(int(any(isinstance(candidate, Index)
	for _, _, _, candidate in candidates)))
	possibleUses = {candidate: 1. for _, _, _, candidate in candidates
	if not isinstance(candidate, Index)}

	for f, xs in expression.applicationParses():
	for candidateLikelihood, newContext, tp, production in candidates:
	variableBindings = {}
	# This is a variable in the environment
	if production.isIndex:
	if production != f:
	continue
	else:
	try:
	newContext, fragmentType, variableBindings = \
	Matcher.match(newContext, production, f, len(xs))
	# This is necessary because the types of the variable
	# bindings and holes need to match up w/ request
	fragmentTypeTemplate = request
	for _ in xs:
	newContext, newVariable = newContext.makeVariable()
	fragmentTypeTemplate = arrow(
	newVariable, fragmentTypeTemplate)
	newContext = newContext.unify(
	fragmentType, fragmentTypeTemplate)
	# update the unified type
	tp = fragmentType.apply(newContext)
	except MatchFailure:
	continue

	argumentTypes = tp.functionArguments()
	if len(xs) != len(argumentTypes):
	# I think that this is some kind of bug. But I can't figure it out right now.
	# As a hack, count this as though it were a failure
	continue
	#raise GrammarFailure('len(xs) != len(argumentTypes): tp={}, xs={}'.format(tp, xs))

	thisLikelihood = candidateLikelihood
	if isinstance(production, Index):
	theseUses = Uses(possibleVariables=possibleVariables,
	actualVariables=1.,
	possibleUses=possibleUses.copy(),
	actualUses={})
	else:
	theseUses = Uses(possibleVariables=possibleVariables,
	actualVariables=0.,
	possibleUses=possibleUses.copy(),
	actualUses={production: 1.})

	# Accumulate likelihood from free variables and holes and
	# arguments
	for freeType, freeExpression in chain(
	variableBindings.values(), zip(argumentTypes, xs)):
	freeType = freeType.apply(newContext)
	newContext, expressionLikelihood, newUses = self._logLikelihood(
	newContext, environment, freeType, freeExpression)
	if expressionLikelihood is NEGATIVEINFINITY:
	thisLikelihood = NEGATIVEINFINITY
	break

	thisLikelihood += expressionLikelihood
	theseUses += newUses

	if thisLikelihood is NEGATIVEINFINITY:
	continue

	weightedUses.append((thisLikelihood, theseUses))
	totalLikelihood = lse(totalLikelihood, thisLikelihood)

	# Any of these new context objects should be equally good
	context = newContext

	if totalLikelihood is NEGATIVEINFINITY:
	return context, totalLikelihood, Uses.empty
	assert weightedUses != []

	allUses = Uses.join(totalLikelihood, *weightedUses)

	# memoize result
	if shouldDoCaching:
	outTypes = [request.apply(context)] + \
	[v.apply(context) for v in environment]
	outTypes = canonicalTypes(outTypes)
	self.likelihoodCache[cacheKey] = (
	outTypes, totalLikelihood, allUses)

	return context, totalLikelihood, allUses

	def expectedUses(self, frontiers):
	if len(list(frontiers)) == 0:
	return Uses()
	likelihoods = [[(l + entry.logLikelihood, u)
	for entry in frontier
	for l, u in [self.closedUses(frontier.task.request, entry.program)]]
	for frontier in frontiers]
	zs = (lse([l for l, _ in ls]) for ls in likelihoods)
	return sum(math.exp(l - z) * u
	for z, frontier in zip(zs, likelihoods)
	for l, u in frontier)

	def insideOutside(self, frontiers, pseudoCounts):
	uses = self.expectedUses(frontiers)
	return FragmentGrammar(log(uses.actualVariables +
	pseudoCounts) -
	log(max(uses.possibleVariables, 1.)), [(log(uses.actualUses.get(p, 0.) +
	pseudoCounts) -
	log(uses.possibleUses.get(p, 0.) +
	pseudoCounts), t, p) for _, t, p in self.productions])

	def jointFrontiersLikelihood(self, frontiers):
	return sum(lse([entry.logLikelihood + self.logLikelihood(frontier.task.request, entry.program)
	for entry in frontier])
	for frontier in frontiers)

	def jointFrontiersMDL(self, frontiers, CPUs=1):
	return sum(
	parallelMap(
	CPUs,
	lambda frontier: max(
	entry.logLikelihood +
	self.logLikelihood(
	frontier.task.request,
	entry.program) for entry in frontier),
	frontiers))

	def __len__(self): return len(self.productions)

	@staticmethod
	def fromGrammar(g):
	return FragmentGrammar(g.logVariable, g.productions)

	def toGrammar(self):
	return Grammar(self.logVariable, [(l, q.infer(), q)
	for l, t, p in self.productions
	for q in [defragment(p)]])

	@property
	def primitives(self): return [p for _, _, p in self.productions]

	@staticmethod
	def uniform(productions):
	return FragmentGrammar(0., [(0., p.infer(), p) for p in productions])

	def normalize(self):
	z = lse([l for l, t, p in self.productions] + [self.logVariable])
	return FragmentGrammar(self.logVariable - z,
	[(l - z, t, p) for l, t, p in self.productions])

	def makeUniform(self):
	return FragmentGrammar(0., [(0., p.infer(), p)
	for _, _, p in self.productions])

	def rescoreFrontier(self, frontier):
	return Frontier([FrontierEntry(e.program,
	logPrior=self.logLikelihood(frontier.task.request, e.program),
	logLikelihood=e.logLikelihood)
	for e in frontier],
	frontier.task)

	@staticmethod
	def induceFromFrontiers(
	g0,
	frontiers,
	_=None,
	topK=1,
	topk_use_only_likelihood=False,
	pseudoCounts=1.0,
	aic=1.0,
	structurePenalty=0.001,
	a=0,
	CPUs=1):
	_ = topk_use_only_likelihood # not used in python compressor
	originalFrontiers = frontiers
	frontiers = [frontier for frontier in frontiers if not frontier.empty]
	eprint("Inducing a grammar from", len(frontiers), "frontiers")

	bestGrammar = FragmentGrammar.fromGrammar(g0)
	oldJoint = bestGrammar.jointFrontiersMDL(frontiers, CPUs=1)

	# "restricted frontiers" only contain the top K according to the best grammar
	def restrictFrontiers():
	return parallelMap(
	CPUs,
	lambda f: bestGrammar.rescoreFrontier(f).topK(topK),
	frontiers)
	restrictedFrontiers = []

	def grammarScore(g):
	g = g.makeUniform().insideOutside(restrictedFrontiers, pseudoCounts)
	likelihood = g.jointFrontiersMDL(restrictedFrontiers)
	structure = sum(primitiveSize(p) for p in g.primitives)
	score = likelihood - aic * len(g) - structurePenalty * structure
	g.clearCache()
	if invalid(score):
	# FIXME: This should never occur but it does anyway
	score = float('-inf')
	return score, g

	if aic is not POSITIVEINFINITY:
	restrictedFrontiers = restrictFrontiers()
	bestScore, _ = grammarScore(bestGrammar)
	eprint("Starting score", bestScore)
	while True:
	restrictedFrontiers = restrictFrontiers()
	fragments = [f
	for f in proposeFragmentsFromFrontiers(restrictedFrontiers, a, CPUs=CPUs)
	if f not in bestGrammar.primitives
	and defragment(f) not in bestGrammar.primitives]
	eprint("Proposed %d fragments." % len(fragments))

	candidateGrammars = [
	FragmentGrammar.uniform(
	bestGrammar.primitives +
	[fragment]) for fragment in fragments]
	if not candidateGrammars:
	break

	scoredFragments = parallelMap(CPUs, grammarScore, candidateGrammars,
	# Each process handles up to 100
	# grammars at a time, a "job"
	chunksize=max(
	1, min(len(candidateGrammars) // CPUs, 100)),
	# maxTasks: Maximum number of jobs allocated to a process
	# This means that after evaluating this*chunk many grammars,
	# we killed the process, freeing up its memory.
	# In exchange we pay the cost of spawning a new process.
	# We should play with this number,
	# figuring out how big we can make it without
	# running out of memory.
	maxtasksperchild=5)
	newScore, newGrammar = max(scoredFragments, key=lambda sg: sg[0])

	if newScore <= bestScore:
	break
	dS = newScore - bestScore
	bestScore, bestGrammar = newScore, newGrammar
	newPrimitiveLikelihood, newType, newPrimitive = bestGrammar.productions[-1]
	expectedUses = bestGrammar.expectedUses(
	restrictedFrontiers).actualUses.get(newPrimitive, 0)
	eprint(
	"New primitive of type %s\t%s\t\n(score = %f; dScore = %f; <uses> = %f)" %
	(newType, newPrimitive, newScore, dS, expectedUses))

	# Rewrite the frontiers in terms of the new fragment
	concretePrimitive = defragment(newPrimitive)
	bestGrammar.productions[-1] = (newPrimitiveLikelihood,
	concretePrimitive.tp,
	concretePrimitive)
	frontiers = parallelMap(
	CPUs, lambda frontier: bestGrammar.rescoreFrontier(
	RewriteFragments.rewriteFrontier(
	frontier, newPrimitive)), frontiers)
	eprint(
	"\t(<uses> in rewritten frontiers: %f)" %
	(bestGrammar.expectedUses(frontiers).actualUses[concretePrimitive]))
	else:
	eprint("Skipping fragment proposals")

	if False:
	# Reestimate the parameters using the entire frontiers
	bestGrammar = bestGrammar.makeUniform().insideOutside(frontiers, pseudoCounts)
	elif True:
	# Reestimate the parameters using the best programs
	restrictedFrontiers = restrictFrontiers()
	bestGrammar = bestGrammar.makeUniform().insideOutside(
	restrictedFrontiers, pseudoCounts)
	else:
	# Use parameters that were found during search
	pass

	eprint("Old joint = %f\tNew joint = %f\n" %
	(oldJoint, bestGrammar.jointFrontiersMDL(frontiers, CPUs=CPUs)))
	# Return all of the frontiers, which have now been rewritten to use the
	# new fragments
	frontiers = {f.task: f for f in frontiers}
	frontiers = [frontiers.get(f.task, f)
	for f in originalFrontiers]

	productionUses = bestGrammar.expectedUses(
	[f for f in frontiers if not f.empty]).actualUses
	productionUses = {
	p: productionUses.get(
	p, 0.) for p in bestGrammar.primitives}
	possibleUses = bestGrammar.expectedUses(
	[f for f in frontiers if not f.empty]).possibleUses
	possibleUses = {
	p: possibleUses.get(
	p, 0.) for p in bestGrammar.primitives}

	for p in bestGrammar.primitives:
	eprint("%f / %f\t%s" % (productionUses[p],
	possibleUses[p],
	p))

	bestGrammar.clearCache()

	grammar = bestGrammar.toGrammar()

	if False and \
	any(productionUses.get(p, 0) < 0.5 for p in grammar.primitives if p.isInvented):
	uselessProductions = [ p for p in grammar.primitives
	if p.isInvented and productionUses.get(p, 0) < 0.5]
	eprint("The following invented primitives are no longer needed, removing them...")
	eprint("\t" + "\t\n".join(map(str, uselessProductions)))
	grammar = grammar.removeProductions(uselessProductions)

	return grammar, frontiers