def get_msg_list(expr):
     if expr.has_form('MessageName', 2):
         expr = Expression('List', expr)
     if expr.get_name() == 'All':
         all = True
         messages = []
     elif expr.get_name() == 'None':
         all = False
         messages = []
     elif expr.has_form('List', None):
         all = False
         messages = []
         for item in expr.leaves:
             if item.has_form('MessageName', 2):
                 symbol = item.leaves[0].get_name()
                 tag = item.leaves[1].get_string_value()
                 if symbol and tag:
                     messages.append((symbol, tag))
                 else:
                     raise ValueError
             else:
                 raise ValueError
     else:
         raise ValueError
     return all, messages

        def yield_match(vars, rest):
            if rest is None:
                rest = ([], [])
            if 0 < len(rest[0]) + len(rest[1]) == len(expression.get_leaves()):
                # continue
                return
            options = {}
            for name, value in list(vars.items()):
                if name.startswith('_option_'):
                    options[name[len('_option_'):]] = value
                    del vars[name]
            new_expression = self.do_replace(expression, vars, options, evaluation)
            if new_expression is None:
                new_expression = expression
            if rest[0] or rest[1]:
                result = Expression(expression.get_head(), *(
                    rest[0] + [new_expression] + rest[1]))
            else:
                result = new_expression

            # Flatten out sequences (important for Rule itself!)
            result = result.flatten_pattern_sequence()
            if return_list:
                result_list.append(result)
                # count += 1
                if max_list is not None and len(result_list) >= max_list:
                    # return result_list
                    raise StopGenerator_BaseRule(result_list)
            else:
                raise StopGenerator_BaseRule(result)

 def apply(self, items, evaluation):
     'Times[items___]'
     
     items = items.numerify(evaluation).get_sequence()
     number = mpz(1)
     leaves = []
     for item in items:
         if isinstance(item, Number):
             if get_type(item.value) == 'z' and item.value == 0:
                 return Integer('0')
             number = mul(number, item.value)
         elif leaves and item == leaves[-1]:
             leaves[-1] = Expression('Power', leaves[-1], Integer(2))
         elif leaves and item.has_form('Power', 2) and leaves[-1].has_form('Power', 2) and item.leaves[0].same(leaves[-1].leaves[0]):
             leaves[-1].leaves[1] = Expression('Plus', item.leaves[1], leaves[-1].leaves[1])
         elif leaves and item.has_form('Power', 2) and item.leaves[0].same(leaves[-1]):
             leaves[-1] = Expression('Power', leaves[-1], Expression('Plus', item.leaves[1], Integer(1)))
         elif leaves and leaves[-1].has_form('Power', 2) and leaves[-1].leaves[0].same(item):
             leaves[-1] = Expression('Power', item, Expression('Plus', Integer(1), leaves[-1].leaves[1]))
         else:
             leaves.append(item)
     if get_type(number) == 'z':
         if number == 1:
             number = None
         elif number == -1 and leaves and leaves[0].has_form('Plus', None):
             leaves[0].leaves = [Expression('Times', Integer(-1), leaf) for leaf in leaves[0].leaves]
             number = None
     if number is not None:
         leaves.insert(0, Number.from_mp(number))
     if not leaves:
         return Integer(1)
     elif len(leaves) == 1:
         return leaves[0]
     else:
         return Expression('Times', *leaves)

    def apply(self, expr, evaluation):
        'Variables[expr_]'

        variables = set()

        def find_vars(e):
            if e.to_sympy().is_constant():
                return
            elif e.is_symbol():
                variables.add(e)
            elif (e.has_form('Plus', None) or
                  e.has_form('Times', None)):
                for l in e.leaves:
                    find_vars(l)
            elif e.has_form('Power', 2):
                (a, b) = e.leaves  # a^b
                if not(a.to_sympy().is_constant()) and b.to_sympy().is_rational:
                    find_vars(a)
            elif not(e.is_atom()):
                variables.add(e)

        exprs = expr.leaves if expr.has_form('List', None) else [expr]
        for e in exprs:
            find_vars(from_sympy(e.to_sympy().expand()))

        variables = Expression('List', *variables)
        variables.sort()        # MMA doesn't do this
        return variables

    def apply(self, z, evaluation):
        '%(name)s[z__]'

        args = z.get_sequence()

        if len(args) != self.nargs:
            return

        # if no arguments are inexact attempt to use sympy
        if all(not x.is_inexact() for x in args):
            result = Expression(self.get_name(), *args).to_sympy()
            result = self.prepare_mathics(result)
            result = from_sympy(result)
            # evaluate leaves to convert e.g. Plus[2, I] -> Complex[2, 1]
            result = result.evaluate_leaves(evaluation)
        else:
            prec = min_prec(*args)
            with mpmath.workprec(prec):
                mpmath_args = [sympy2mpmath(x.to_sympy()) for x in args]
                if None in mpmath_args:
                    return
                try:
                    result = self.eval(*mpmath_args)
                    result = from_sympy(mpmath2sympy(result, prec))
                except ValueError, exc:
                    text = str(exc)
                    if text == 'gamma function pole':
                        return Symbol('ComplexInfinity')
                    else:
                        raise
                except ZeroDivisionError:
                    return
                except SpecialValueError, exc:
                    return Symbol(exc.name)

 def apply(self, f, x, xstart, xstop, y, ystart, ystop, evaluation, options):
     'DensityPlot[f_, {x_Symbol, xstart_, xstop_}, {y_Symbol, ystart_, ystop_}, OptionsPattern[DensityPlot]]'
     
     x = x.get_name()
     y = y.get_name()
     
     color_function = self.get_option(options, 'ColorFunction', evaluation, pop=True)
     color_function_scaling = self.get_option(options, 'ColorFunctionScaling', evaluation, pop=True)
     
     color_function_min = color_function_max = None
     if color_function.get_name() == 'Automatic':
         color_function = String('LakeColors')
     if color_function.get_string_value():
         func = Expression('ColorData', color_function.get_string_value()).evaluate(evaluation)
         if func.has_form('ColorDataFunction', 4):
             color_function_min = func.leaves[2].leaves[0].get_real_value()
             color_function_max = func.leaves[2].leaves[1].get_real_value()
             color_function = Expression('Function', Expression(func.leaves[3], Expression('Slot', 1)))
         else:
             evaluation.message('DensityPlot', 'color', func)
             return
     if color_function.has_form('ColorDataFunction', 4):
         color_function_min = color_function.leaves[2].leaves[0].get_real_value()
         color_function_max = color_function.leaves[2].leaves[1].get_real_value()
         
     color_function_scaling = color_function_scaling.is_true()
         
     try:
         xstart, xstop, ystart, ystop = [value.to_number(n_evaluation=evaluation) for value in
             (xstart, xstop, ystart, ystop)]
     except NumberError, exc:
         expr = Expression('DensityPlot', f, Expression('List', x, xstart, xstop),
             Expression('List', y, ystart, ystop), *options_to_rules(options))
         evaluation.message('DensityPlot', 'plln', exc.value, expr)
         return

    def importer(self, filename, evaluation):

        path = filename.to_python()
        if not (isinstance(path, basestring) and path[0] == path[-1] == '"'):
            evaluation.message('Import', 'chtype', filename)
            return Symbol('$Failed')
        path = path.strip('"')

        if path.startswith("ExampleData"):
            path = ROOT_DIR + 'data/' + path

        if not os.path.exists(path):
            evaluation.message('Import', 'nffil')
            return None

        filetype = Expression('FileFormat', path).evaluate(evaluation=evaluation)

        assert isinstance(filetype, String)
        filetype = filetype.to_python().strip('"')
        assert filetype in IMPORTFORMATS

        result = {}
        if filetype == 'Text':
            with open(path, 'r') as f:
                plaintext = f.read()
                textlines = filter(lambda x: x != '', plaintext.split('\n'))
                textwords = filter(lambda x: x != '', plaintext.split())
                result['Plaintext'] = plaintext
                result['Lines'] = textlines
                result['Words'] = textwords
                result['String'] = plaintext
                result['Data'] = textlines

        return result

    def format_output(self, expr, format=None):
        if format is None:
            format = self.format

        if isinstance(format, dict):
            return dict((k, self.format_output(expr, f)) for k, f in format.items())

        from mathics.core.expression import Expression, BoxError

        if format == 'text':
            result = expr.format(self, 'System`OutputForm')
        elif format == 'xml':
            result = Expression(
                'StandardForm', expr).format(self, 'System`MathMLForm')
        elif format == 'tex':
            result = Expression('StandardForm', expr).format(
                self, 'System`TeXForm')
        else:
            raise ValueError

        try:
            boxes = result.boxes_to_text(evaluation=self)
        except BoxError:
            self.message('General', 'notboxes',
                         Expression('FullForm', result).evaluate(self))
            boxes = None
        return boxes

 def apply(self, items, evaluation):
     '%(name)s[items__]'
     
     items_sequence = items.get_sequence()
     all_numeric = all(item.is_numeric() and item.get_precision() is None for item in items_sequence)
     if all_numeric and any(not isinstance(item, Number) for item in items_sequence):
         # All expressions are numeric but exact and they are not all numbers,
         # so apply N and compare them.
         items = items_sequence
         n_items = []
         for item in items:
             if not isinstance(item, Number):
                 # TODO: use $MaxExtraPrecision insterad of hard-coded 50
                 n_expr = Expression('N', item, Real(50)) 
                 item = n_expr.evaluate(evaluation)
             n_items.append(item)
         items = n_items
     else:
         items = items.numerify(evaluation).get_sequence()
     wanted = operators[self.get_name()]
     prev = None
     for item in items:
         if item.get_real_value() is None and not item.has_form('DirectedInfinity', None):
             return
         if prev is not None and do_cmp(prev, item) not in wanted:
             return Symbol('False')
         prev = item
     return Symbol('True')

    def apply(self, f, args, h, evaluation):
        'Thread[f_[args___], h_]'

        args = args.get_sequence()
        expr = Expression(f, *args)
        threaded, result = expr.thread(evaluation, head=h)
        return result

    def apply(self, expr, evaluation):
        'Variables[expr_]'

        variables = find_all_vars(expr)
        
        variables = Expression('List', *variables)
        variables.sort()        # MMA doesn't do this
        return variables

    def apply(self, items, evaluation):
        'Times[items___]'

        #TODO: Clean this up and optimise it        

        items = items.numerify(evaluation).get_sequence()
        number = (sympy.Integer(1), sympy.Integer(0))
        leaves = []

        prec = min_prec(*items)
        is_real = all([not isinstance(i, Complex) for i in items])

        for item in items:
            if isinstance(item, Number):
                if isinstance(item, Complex):
                    sym_real, sym_imag = item.real.to_sympy(), item.imag.to_sympy()
                else:
                    sym_real, sym_imag = item.to_sympy(), sympy.Integer(0)

                if prec is not None:
                    sym_real = sym_real.n(dps(prec))
                    sym_imag = sym_imag.n(dps(prec))

                if sym_real.is_zero and sym_imag.is_zero and prec is None:
                    return Integer('0')
                number = (number[0]*sym_real - number[1]*sym_imag, number[0]*sym_imag + number[1]*sym_real)
            elif leaves and item == leaves[-1]:
                leaves[-1] = Expression('Power', leaves[-1], Integer(2))
            elif leaves and item.has_form('Power', 2) and leaves[-1].has_form('Power', 2) and item.leaves[0].same(leaves[-1].leaves[0]):
                leaves[-1].leaves[1] = Expression('Plus', item.leaves[1], leaves[-1].leaves[1])
            elif leaves and item.has_form('Power', 2) and item.leaves[0].same(leaves[-1]):
                leaves[-1] = Expression('Power', leaves[-1], Expression('Plus', item.leaves[1], Integer(1)))
            elif leaves and leaves[-1].has_form('Power', 2) and leaves[-1].leaves[0].same(item):
                leaves[-1] = Expression('Power', item, Expression('Plus', Integer(1), leaves[-1].leaves[1]))
            else:
                leaves.append(item)
        if number == (1, 0):
            number = None
        elif number == (-1, 0) and leaves and leaves[0].has_form('Plus', None):
            leaves[0].leaves = [Expression('Times', Integer(-1), leaf) for leaf in leaves[0].leaves]
            number = None

        if number is not None:
            if number[1].is_zero and is_real:
                leaves.insert(0, Number.from_mp(number[0], prec))
            elif number[1].is_zero and number[1].is_Integer and prec is None:
                leaves.insert(0, Number.from_mp(number[0], prec))
            else:
                leaves.insert(0, Complex(from_sympy(number[0]), from_sympy(number[1]), prec))

        if not leaves:
            return Integer(1)
        elif len(leaves) == 1:
            return leaves[0]
        else:
            return Expression('Times', *leaves)

 def compare(e1, e2):
     result = Expression(p, e1, e2).evaluate(evaluation)
     if result.is_true():
         result = Expression(p, e2, e1).evaluate(evaluation)
         if result.is_true():
             return 0
         else:
             return -1
     else:
         return 1

    def apply_elements(self, filename, expr, elems, evaluation, options={}):
        "Export[filename_, expr_, elems_List?(AllTrue[#, NotOptionQ]&), OptionsPattern[]]"

        # Check filename
        if not self._check_filename(filename, evaluation):
            return Symbol('$Failed')

        # Process elems {comp* format?, elem1*}
        leaves = elems.get_leaves()

        format_spec, elems_spec = [], []
        found_form = False
        for leaf in leaves[::-1]:
            leaf_str = leaf.get_string_value()

            if not found_form and leaf_str in EXPORTERS:
                found_form = True

            if found_form:
                format_spec.append(leaf_str)
            else:
                elems_spec.append(leaf)

        # Infer format if not present
        if not found_form:
            assert format_spec == []
            format_spec = self._infer_form(filename, evaluation)
            if format_spec is None:
                evaluation.message('Export', 'infer', filename)
                return Symbol('$Failed')
            format_spec = [format_spec]
        else:
            assert format_spec != []

        # First item in format_spec is the explicit format.
        # The other elements (if present) are compression formats

        if elems_spec != []:        # FIXME: support elems
            evaluation.message(
                'Export', 'noelem', elems, String(format_spec[0]))
            return Symbol('$Failed')

        # Load the exporter
        exporter_symbol, exporter_options = EXPORTERS[format_spec[0]]

        stream_options, custom_options = _importer_exporter_options(
            exporter_options.get("System`Options"), options, evaluation)

        exporter_function = Expression(
            exporter_symbol, filename, expr, *list(chain(stream_options, custom_options)))

        if exporter_function.evaluate(evaluation) == Symbol('Null'):
            return filename
        return Symbol('$Failed')

 def post_parse(self, expression):
     leaves = [leaf.post_parse() for leaf in expression.leaves]
     expression = Expression(expression.head.post_parse(), *leaves)
     if expression.has_form('Optional', 2) and expression.leaves[0].get_name():
         sub = expression.leaves[1]
         if sub.has_form(('Pattern', 'Optional'), 2):
             return Expression('Optional', Expression('Pattern', expression.leaves[0], sub.leaves[0]), sub.leaves[1])
         else:
             return Expression('Pattern', *[leaf.post_parse() for leaf in expression.leaves])
     else:
         return expression

 def apply(self, list, expr, evaluation):
     'Select[list_, expr_]'
     
     if list.is_atom():
         evaluation.message('Select', 'normal')
         return
     new_leaves = []
     for leaf in list.leaves:
         test = Expression(expr, leaf)
         if test.evaluate(evaluation) == Symbol('True'):
             new_leaves.append(leaf)
     return Expression(list.head, *new_leaves)

 def eval_color(x, y, v):
     v_scaled = (v - v_min) / v_range
     if color_function_scaling and color_function_min is not None and color_function_max is not None:
         v_color_scaled = color_function_min + v_scaled * color_function_range
     else:
         v_color_scaled = v
     v_lookup = int(v_scaled * 100 + 0.5)     # calculate and store 100 different shades max.
     value = colors.get(v_lookup)
     if value is None:
         value = Expression(color_func, Real(v_color_scaled))
         value = value.evaluate(evaluation)
         colors[v_lookup] = value
     return value

def _norm_calc(head, u, v, evaluation):
    expr = Expression(head, u, v)
    old_quiet_all = evaluation.quiet_all
    try:
        evaluation.quiet_all = True
        expr_eval = expr.evaluate(evaluation)
    finally:
        evaluation.quiet_all = old_quiet_all
    if expr_eval.same(expr):
        evaluation.message('Norm', 'nvm')
        return None
    else:
        return expr_eval

    def apply(self, filename, expr, elems, evaluation):
        "Export[filename_, expr_, elems_List]"

        # Check filename
        if not self._check_filename(filename, evaluation):
            return Symbol('$Failed')

        ## Process elems {comp* format?, elem1*}
        leaves = elems.get_leaves()

        format_spec, elems_spec = [], []
        found_form = False
        for leaf in leaves[::-1]:
            leaf_str = leaf.get_string_value()

            if not found_form and leaf_str in EXPORTERS:
                found_form = True

            if found_form:
                format_spec.append(leaf_str)
            else:
                elems_spec.append(leaf)

        # Infer format if not present
        if not found_form:
            assert format_spec == []
            format_spec = self._infer_form(filename, evaluation)
            if format_spec is None:
                evaluation.message('Export', 'infer', filename)
                return Symbol('$Failed')
            format_spec = [format_spec]
        else:
            assert format_spec != []

        # First item in format_spec is the explicit format.
        # The other elements (if present) are compression formats

        if elems_spec != []:        # FIXME: support elems
            evaluation.message(
                'Export', 'noelem', elems, String(format_spec[0]))
            return Symbol('$Failed')

        # Load the exporter
        exporter_symbol = EXPORTERS[format_spec[0]]

        exporter_function = Expression(exporter_symbol, filename, expr)

        if exporter_function.evaluate(evaluation) == Symbol('Null'):
            return filename
        return Symbol('$Failed')

 def add(self, expression, evaluation):
     expr = Expression('System`Private`ManipulateParameter', expression).evaluate(evaluation)
     if expr.get_head_name() != 'System`List':  # if everything was parsed ok, we get a List
         return False
     # convert the rules given us by ManipulateParameter[] into a dict. note: duplicate keys
     # will be overwritten, the latest one wins.
     kwargs = {'evaluation': evaluation}
     for rule in expr.leaves:
         if rule.get_head_name() != 'System`Rule' or len(rule.leaves) != 2:
             return False
         kwargs[strip_context(rule.leaves[0].to_python()).lower()] = rule.leaves[1]
     widget = kwargs['type'].get_string_value()
     del kwargs['type']
     getattr(self, '_add_%s_widget' % widget.lower())(**kwargs)  # create the widget
     return True