def map_sum(self, expr):
        sum_kind = None

        term_kind_matrix = intern("matrix")
        term_kind_vector = intern("vector")
        term_kind_scalar = intern("scalar")

        result = 0
        for child in expr.children:
            rec_child = self.rec(child)

            if is_zero(rec_child):
                continue

            if isinstance(rec_child, np.ndarray):
                if self.is_kind_matrix(rec_child):
                    term_kind = term_kind_matrix
                elif self.is_kind_vector(rec_child):
                    term_kind = term_kind_vector
                else:
                    raise RuntimeError("unexpected array rank")
            else:
                term_kind = term_kind_scalar

            if sum_kind is None:
                sum_kind = term_kind

            if term_kind != sum_kind:
                raise RuntimeError("encountered %s in sum of kind %s"
                        % (term_kind, sum_kind))

            result = result + rec_child

        return result

    def __init__(self, next_attr_name=None, prev_attr_name=None):
        """Initializes this list.

        next_attr_name: The name of the attribute that holds a reference
                        to the next item in the list.

        prev_attr_name: the name of the attribute that holds a reference
                        to the previous item in the list.
        """

        # Keep an interned version of the attribute names. This should
        # speed up the process of looking up the attributes.
        self.next_name = intern(next_attr_name)
        self.prev_name = intern(prev_attr_name)

    def __init__(self, **kwargs):
        kwargs["name"] = intern(kwargs.pop("name"))

        target = kwargs.pop("target", None)

        dtype = kwargs.pop("dtype", None)

        if 'for_atomic' in kwargs:
            for_atomic = kwargs['for_atomic']
        else:
            for_atomic = False

        from loopy.types import to_loopy_type
        dtype = to_loopy_type(
                dtype, allow_auto=True, allow_none=True, for_atomic=for_atomic,
                target=target)

        import loopy as lp
        if dtype is lp.auto:
            warn("Argument/temporary data type for '%s' should be None if "
                   "unspecified, not auto. This usage will be disallowed in 2018."
                    % kwargs["name"],
                    DeprecationWarning, stacklevel=2)

            dtype = None

        kwargs["dtype"] = dtype

        ImmutableRecord.__init__(self, **kwargs)

def normalize_chromosome(c):
    try:
        return NORMALIZE_CHROMOSOME_CACHE[c]
    except KeyError:
        pass

    if not (is_string(c) or is_integer(c)):
        raise TypeError("Chromosome cannot be '%s' : %s" % (c, type(c)))

    result = str(c)
    if result == "0":
        raise ValueError("Chromosome name cannot be 0")
    elif result == "":
        raise ValueError("Chromosome name cannot be empty")

    # only strip off lowercase chr since some of the non-chromosomal
    # contigs start with "CHR"
    if result.startswith("chr"):
        result = result[3:]

    # just in case someone is being lazy, capitalize "M", "MT", X", "Y"
    result = result.upper()

    # standardize mitochondrial genome to be "MT"
    if result == "M":
        result = "MT"

    # interning strings since the chromosome names probably get constructed
    # or parsed millions of times, can save memory in tight situations
    # (such as parsing GTF files)
    result = intern(result)

    NORMALIZE_CHROMOSOME_CACHE[c] = result

    return result

def memoize_method(method):
    """Supports cache deletion via ``method_name.clear_cache(self)``.

    .. note::
        *clear_cache* support requires Python 2.5 or newer.
    """

    cache_dict_name = intern("_memoize_dic_"+method.__name__)

    def wrapper(self, *args, **kwargs):
        if kwargs:
            key = (_HasKwargs, frozenset(six.iteritems(kwargs))) + args
        else:
            key = args

        try:
            return getattr(self, cache_dict_name)[key]
        except AttributeError:
            result = method(self, *args, **kwargs)
            setattr(self, cache_dict_name, {key: result})
            return result
        except KeyError:
            result = method(self, *args, **kwargs)
            getattr(self, cache_dict_name)[key] = result
            return result

    def clear_cache(self):
        delattr(self, cache_dict_name)

    if sys.version_info >= (2, 5):
        from functools import update_wrapper
        new_wrapper = update_wrapper(wrapper, method)
        new_wrapper.clear_cache = clear_cache

    return new_wrapper

def memoize_method_nested(inner):
    """Adds a cache to a function nested inside a method. The cache is attached
    to *memoize_cache_context* (if it exists) or *self* in the outer (method)
    namespace.

    Requires Python 2.5 or newer.
    """

    from functools import wraps
    cache_dict_name = intern("_memoize_inner_dic_%s_%s_%d"
            % (inner.__name__, inner.__code__.co_filename,
                inner.__code__.co_firstlineno))

    from inspect import currentframe
    outer_frame = currentframe().f_back
    cache_context = outer_frame.f_locals.get("memoize_cache_context")
    if cache_context is None:
        cache_context = outer_frame.f_locals.get("self")

    try:
        cache_dict = getattr(cache_context, cache_dict_name)
    except AttributeError:
        cache_dict = {}
        setattr(cache_context, cache_dict_name, cache_dict)

    @wraps(inner)
    def new_inner(*args):
        try:
            return cache_dict[args]
        except KeyError:
            result = inner(*args)
            cache_dict[args] = result
            return result

    return new_inner

    def realize_conditional(self, node, context_cond=None):
        scope = self.scope_stack[-1]

        cond_name = intern("loopy_cond%d" % self.condition_id_counter)
        self.condition_id_counter += 1
        assert cond_name not in scope.type_map

        scope.type_map[cond_name] = np.int32

        from pymbolic import var
        cond_var = var(cond_name)

        self.add_expression_instruction(
                cond_var, self.parse_expr(node, node.expr))

        cond_expr = cond_var
        if context_cond is not None:
            from pymbolic.primitives import LogicalAnd
            cond_expr = LogicalAnd((cond_var, context_cond))

            self.conditions_data.append((context_cond, cond_var))
        else:
            self.conditions_data.append((None, cond_var))

        self.conditions.append(cond_expr)

def memoize_method(method):
    """Supports cache deletion via ``method_name.clear_cache(self)``.

    .. note::
        *clear_cache* support requires Python 2.5 or newer.
    """

    return memoize_on_first_arg(method, intern("_memoize_dic_"+method.__name__))

    def make_unique_instruction_id(self, insns=None, based_on="insn",
            extra_used_ids=set()):
        if insns is None:
            insns = self.instructions

        used_ids = set(insn.id for insn in insns) | extra_used_ids

        for id_str in generate_unique_names(based_on):
            if id_str not in used_ids:
                return intern(id_str)

    def __call__(self, based_on="id"):
        based_on = self.forced_prefix + based_on

        for var_name in generate_unique_names(based_on):
            if not self.is_name_conflicting(var_name):
                break

        var_name = intern(var_name)

        self.existing_names.add(var_name)
        return var_name

    def __init__(self, **kwargs):
        kwargs["name"] = intern(kwargs.pop("name"))

        dtype = kwargs.pop("dtype", None)

        if isinstance(dtype, np.dtype):
            from loopy.tools import PicklableDtype
            kwargs["picklable_dtype"] = PicklableDtype(dtype)
        else:
            kwargs["picklable_dtype"] = dtype

        Record.__init__(self, **kwargs)

def parse_if_necessary(insn, defines):
    if isinstance(insn, InstructionBase):
        yield insn.copy(
                id=intern(insn.id) if isinstance(insn.id, str) else insn.id,
                insn_deps=frozenset(intern(dep) for dep in insn.insn_deps),
                groups=frozenset(intern(grp) for grp in insn.groups),
                conflicts_with_groups=frozenset(
                    intern(grp) for grp in insn.conflicts_with_groups),
                forced_iname_deps=frozenset(
                    intern(iname) for iname in insn.forced_iname_deps),
                predicates=frozenset(
                    intern(pred) for pred in insn.predicates),
                ), []
        return
    elif not isinstance(insn, str):
        raise TypeError("Instructions must be either an Instruction "
                "instance or a parseable string. got '%s' instead."
                % type(insn))

    for insn in insn.split("\n"):
        comment_start = insn.find("#")
        if comment_start >= 0:
            insn = insn[:comment_start]

        insn = insn.strip()
        if not insn:
            continue

        for sub_insn in expand_defines(insn, defines, single_valued=False):
            yield parse_insn(sub_insn)

    def cursor_to_dict(cursor):
        """Converts a SQL cursor into an list of dicts.

        Args:
            cursor : The DBAPI cursor which has executed a query.
        Returns:
            A list of dicts where the key is the column header.
        """
        col_headers = list(intern(str(column[0])) for column in cursor.description)
        results = list(
            dict(zip(col_headers, row)) for row in cursor
        )
        return results

    def __setstate__(self, val):
        super(InstructionBase, self).__setstate__(val)

        from loopy.tools import intern_frozenset_of_ids

        if self.id is not None:  # pylint:disable=access-member-before-definition
            self.id = intern(self.id)
        self.depends_on = intern_frozenset_of_ids(self.depends_on)
        self.groups = intern_frozenset_of_ids(self.groups)
        self.conflicts_with_groups = (
                intern_frozenset_of_ids(self.conflicts_with_groups))
        self.within_inames = (
                intern_frozenset_of_ids(self.within_inames))

def intern_string(string):
    """Takes a (potentially) unicode string and interns it if it's ascii
    """
    if string is None:
        return None

    try:
        if six.PY2:
            string = string.encode("ascii")

        return intern(string)
    except UnicodeEncodeError:
        return string

def der_parse_OID(derblob):
    oidvals = [0]
    for byte in map(ord, derblob):
        if byte & 0x80 != 0x00:
            oidvals[-1] = (oidvals[-1] << 7) | (byte & 0x7f)
        else:
            oidvals[-1] = (oidvals[-1] << 7) | byte
            oidvals.append(0)
    fst = oidvals[0] // 40
    snd = oidvals[0] % 40
    oidvals = [fst, snd] + oidvals[1:-1]
    retval = '.'.join(map(str, oidvals))
    return intern(retval)

    def __setstate__(self, val):
        super(InstructionBase, self).__setstate__(val)

        from loopy.tools import intern_frozenset_of_ids

        self.id = intern(self.id)
        self.insn_deps = intern_frozenset_of_ids(self.insn_deps)
        self.groups = intern_frozenset_of_ids(self.groups)
        self.conflicts_with_groups = (
                intern_frozenset_of_ids(self.conflicts_with_groups))
        self.forced_iname_deps = (
                intern_frozenset_of_ids(self.forced_iname_deps))
        self.predicates = (
                intern_frozenset_of_ids(self.predicates))

    def __call__(self, based_on="id"):
        based_on = self.forced_prefix + based_on

        counter = self.prefix_to_counter.get(based_on, None)

        for counter, var_name in generate_numbered_unique_names(based_on, counter):
            if not self.is_name_conflicting(var_name):
                break

        self.prefix_to_counter[based_on] = counter

        var_name = intern(var_name)

        self.existing_names.add(var_name)
        return var_name

def first_arg_dependent_memoize_nested(nested_func):
    """Provides memoization for nested functions. Typically used to cache
    things that get created inside a :class:`pyopencl.Context`, e.g. programs
    and kernels. Assumes that the first argument of the decorated function is
    an OpenCL object that might go away, such as a :class:`pyopencl.Context` or
    a :class:`pyopencl.CommandQueue`, and will therefore respond to
    :func:`clear_first_arg_caches`.

    .. versionadded:: 2013.1

    Requires Python 2.5 or newer.
    """

    from functools import wraps
    cache_dict_name = intern("_memoize_inner_dic_%s_%s_%d"
            % (nested_func.__name__, nested_func.__code__.co_filename,
                nested_func.__code__.co_firstlineno))

    from inspect import currentframe
    # prevent ref cycle
    try:
        caller_frame = currentframe().f_back
        cache_context = caller_frame.f_globals[
                caller_frame.f_code.co_name]
    finally:
        #del caller_frame
        pass

    try:
        cache_dict = getattr(cache_context, cache_dict_name)
    except AttributeError:
        cache_dict = {}
        _first_arg_dependent_caches.append(cache_dict)
        setattr(cache_context, cache_dict_name, cache_dict)

    @wraps(nested_func)
    def new_nested_func(cl_object, *args):
        try:
            return cache_dict[cl_object][args]
        except KeyError:
            arg_dict = cache_dict.setdefault(cl_object, {})
            result = nested_func(cl_object, *args)
            arg_dict[args] = result
            return result

    return new_nested_func

    def add_expression_instruction(self, lhs, rhs):
        scope = self.scope_stack[-1]

        new_id = intern("insn%d" % self.insn_id_counter)
        self.insn_id_counter += 1

        from loopy.kernel.data import Assignment
        insn = Assignment(
                lhs, rhs,
                within_inames=frozenset(
                    scope.active_loopy_inames),
                id=new_id,
                predicates=frozenset(self.conditions),
                tags=tuple(self.instruction_tags))

        scope.previous_instruction_id = new_id
        scope.instructions.append(insn)