Basic data types and related functions used in SNAKES

Function cross

def cross (sets) :

Cross-product of some iterable collections (typically, list or set).

>>> list(cross([[1, 2], [3, 4, 5]]))
[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)]
>>> list(cross([[1, 2], [3, 4, 5], [6, 7, 8, 9]]))
[(1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 3, 9), (1, 4, 6), (1, 4, 7),
 (1, 4, 8), (1, 4, 9), (1, 5, 6), (1, 5, 7), (1, 5, 8), (1, 5, 9),
 (2, 3, 6), (2, 3, 7), (2, 3, 8), (2, 3, 9), (2, 4, 6), (2, 4, 7),
 (2, 4, 8), (2, 4, 9), (2, 5, 6), (2, 5, 7), (2, 5, 8), (2, 5, 9)]
>>> list(cross([[], [1]]))
[]

Call API

• iterable sets: the sets of values to use
• return generator: an iterator over the tuples in the cross-product

Function iterate

def iterate (value) :

Like Python's builtin iter but consider strings as atomic.

>>> list(iter([1, 2, 3]))
[1, 2, 3]
>>> list(iterate([1, 2, 3]))
[1, 2, 3]
>>> list(iter('foo'))
['f', 'o', 'o']
>>> list(iterate('foo'))
['foo']

Call API

• object value: any object
• return generator: an iterator on the elements of value if is is iterable and is not string, an iterator on the sole value otherwise

Class WordSet

class WordSet (set) :

A set of words being able to generate fresh words.

Method WordSet.fresh

def fresh (self, add=False, min=1, base="",
           allowed="abcdefghijklmnopqrstuvwxyz") : ...

Create a fresh word (ie, which is not in the set).

>>> w = WordSet(['foo', 'bar'])
>>> list(sorted(w))
['bar', 'foo']
>>> w.fresh(True, 3)
'aaa'
>>> list(sorted(w))
['aaa', 'bar', 'foo']
>>> w.fresh(True, 3)
'baa'
>>> list(sorted(w))
['aaa', 'baa', 'bar', 'foo']

Call API

• bool add: add the created word to the set if add=True
• int min: minimal length of the new word
• str base: prefix of generated words
• str allowed: characters allowed in the new word

Class MultiSet

class MultiSet (hdict) :

Set with repetitions, ie, function from values to integers.

MultiSets support various operations, in particular: addition (+), substraction (-), multiplication by a non negative integer (*k), comparisons (<, >, etc.), length (len).

Method MultiSet.__init__

def __init__ (self, values=[]) :

Initialise the multiset, adding values to it.

>>> MultiSet([1, 2, 3, 1, 2])
MultiSet([...])
>>> MultiSet()
MultiSet([])

Call API

• object values: a single value or an iterable collection of values (strings are not iterated)

Method MultiSet.copy

def copy (self) :

Copy a MultiSet

>>> m1 = MultiSet([1, 2, 3, 1, 2])
>>> m2 = m1.copy()
>>> m1 == m2 and m1 is not m2
True

Call API

• return MultiSet: a copy of the multiset

Method MultiSet.add

def add (self, values, times=1) :

Add values to the multiset.

>>> m = MultiSet()
>>> m.add([1, 2, 2, 3], 2)
>>> list(sorted(m.items()))
[1, 1, 2, 2, 2, 2, 3, 3]
>>> m.add(5, 3)
>>> list(sorted(m.items()))
[1, 1, 2, 2, 2, 2, 3, 3, 5, 5, 5]

Call API

• object values: the values to add or a single value to add
• int times: the number of times each value should be added (must be non-negative)

Exceptions

• ValueError: when times is negative

Method MultiSet.remove

def remove (self, values, times=1) :

Remove values to the multiset.

>>> m = MultiSet([1, 2, 2, 3] * 2)
>>> list(sorted(m.items()))
[1, 1, 2, 2, 2, 2, 3, 3]
>>> m.remove(2, 3)
>>> list(sorted(m.items()))
[1, 1, 2, 3, 3]
>>> m.remove([1, 3], 2)
>>> list(sorted(m.items()))
[2]

Call API

• object values: the values to remove or a single value to remove
• int times: the number of times each value should be removed (must be non negative)

Exceptions

• ValueError: when times is negative

Method MultiSet.__call__

def __call__ (self, value) :

Number of occurrences of value.

>>> m = MultiSet([1, 1, 2, 3, 3, 3])
>>> m(1), m(2), m(3), m(4)
(2, 1, 3, 0)

Call API

• object value: the value the count
• return int

Method MultiSet.__iter__

def __iter__ (self) :

Iterate over the values, including repetitions. Use MultiSet.keys to ignore repetitions.

>>> list(sorted(iter(MultiSet([1, 2, 3, 1, 2]))))
[1, 1, 2, 2, 3]

Call API

• return generator: an iterator on the elements

Method MultiSet.items

def items (self) :

Return the list of items with repetitions. The list without repetitions can be retrieved with MultiSet.key.

>>> m = MultiSet([1, 2, 2, 3])
>>> list(sorted(m.items()))
[1, 2, 2, 3]
>>> list(sorted(m.keys()))
[1, 2, 3]

Call API

• return list: list of items including repetitions

Method MultiSet.__str__

def __str__ (self) :

Return a simple string representation of the multiset

>>> str(MultiSet([1, 2, 2, 3]))
'{...}'

Call API

• return str: simple string representation of the multiset

Method MultiSet.__repr__

def __repr__ (self) :

Return a string representation of the multiset that is suitable for eval

>>> repr(MultiSet([1, 2, 2, 3]))
'MultiSet([...])'

Call API

• return str: precise string representation of the multiset

Method MultiSet.__len__

def __len__ (self) :

Return the number of elements, including repetitions.

>>> len(MultiSet([1, 2] * 3))
6

Call API

• return int

Method MultiSet.size

def size (self) :

Return the number of elements, excluding repetitions.

>>> MultiSet([1, 2] * 3).size()
2

Call API

• return int

Method MultiSet.__add__

def __add__ (self, other) :

Adds two multisets.

>>> MultiSet([1, 2, 3]) + MultiSet([2, 3, 4])
MultiSet([...])

Call API

• MultiSet other: the multiset to add
• return MultiSet

Method MultiSet.__sub__

def __sub__ (self, other) :

Substract two multisets. The second multiset must be smaller than the first one.

>>> MultiSet([1, 2, 3]) - MultiSet([2, 3])
MultiSet([1])
>>> MultiSet([1, 2, 3]) - MultiSet([2, 3, 4])
Traceback (most recent call last):
...
ValueError: not enough occurrences

Call API

• MultiSet other: the multiset to substract
• return MultiSet

Exceptions

• ValueError: when the second multiset is not smaller

Method MultiSet.__mul__

def __mul__ (self, other) :

Multiplication by a non-negative integer.

>>> MultiSet([1, 2]) * 3 == MultiSet([1, 2] * 3)
True

Call API

• non-negativeint other`: the integer to multiply
• return MultiSet

Exceptions

• ValueError: when other is negative

Method MultiSet.__eq__

def __eq__ (self, other) :

Test for equality.

>>> MultiSet([1, 2, 3]*2) == MultiSet([1, 2, 3]*2)
True
>>> MultiSet([1, 2, 3]) == MultiSet([1, 2, 3, 3])
False

Call API

• MultiSet other: the multiset to compare with
• return bool

Method MultiSet.__ne__

def __ne__ (self, other) :

Test for difference.

>>> MultiSet([1, 2, 3]*2) != MultiSet([1, 2, 3]*2)
False
>>> MultiSet([1, 2, 3]) != MultiSet([1, 2, 3, 3])
True

Call API

• MultiSet other: the multiset to compare with
• return bool

Method MultiSet.__lt__

def __lt__ (self, other) :

Test for strict inclusion. A multiset A is strictly included in a multiset B iff every element in A is also in B but less repetitions A than in B.

>>> MultiSet([1, 2, 3]) < MultiSet([1, 2, 3, 4])
True
>>> MultiSet([1, 2, 3]) < MultiSet([1, 2, 3, 3])
True
>>> MultiSet([1, 2, 3]) < MultiSet([1, 2, 3])
False
>>> MultiSet([1, 2, 3]) < MultiSet([1, 2])
False
>>> MultiSet([1, 2, 2]) < MultiSet([1, 2, 3, 4])
False

Call API

• MultiSet other: the multiset to compare with
• return bool

Method MultiSet.__le__

def __le__ (self, other) :

Test for inclusion.

>>> MultiSet([1, 2, 3]) <= MultiSet([1, 2, 3, 4])
True
>>> MultiSet([1, 2, 3]) <= MultiSet([1, 2, 3, 3])
True
>>> MultiSet([1, 2, 3]) <= MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3]) <= MultiSet([1, 2])
False
>>> MultiSet([1, 2, 2]) <= MultiSet([1, 2, 3, 4])
False

Call API

• MultiSet other: the multiset to compare with
• return bool

Method MultiSet.__gt__

def __gt__ (self, other) :

Test for strict inclusion.

>>> MultiSet([1, 2, 3, 4]) > MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3, 3]) > MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3]) > MultiSet([1, 2, 3])
False
>>> MultiSet([1, 2]) > MultiSet([1, 2, 3])
False
>>> MultiSet([1, 2, 3, 4]) > MultiSet([1, 2, 2])
False

Call API

• MultiSet other: the multiset to compare with
• return bool

Method MultiSet.__ge__

def __ge__ (self, other) :

Test for inclusion.

>>> MultiSet([1, 2, 3, 4]) >= MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3, 3]) >= MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3]) >= MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2]) >= MultiSet([1, 2, 3])
False
>>> MultiSet([1, 2, 3, 4]) >= MultiSet([1, 2, 2])
False

Call API

• MultiSet other: the multiset to compare with
• return bool

Method MultiSet.domain

def domain (self) :

Return the domain of the multiset, that is, the set of elements that occurr at least once in the multiset.

>>> list(sorted((MultiSet([1, 2, 3, 4]) + MultiSet([1, 2, 3])).domain()))
[1, 2, 3, 4]

Call API

• return set: the set of values in the domain

Class Substitution

class Substitution (object) :

Map names to values or names, equals the identity where not defined.

Substitutions support the + operation (union with consistency check between the two operands) and the * operation which is the composition of functions ((f*g)(x) is f(g(x))).

Several methods (eg, image) return lists instead of sets, this avoids the restriction of having only hashable values in a substitution image.

Method Substitution.__init__

def __init__ (self, *largs, **dargs) :

Initialise using a dictionnary as a mapping.

The expected arguments are any ones acceptables for initializing a dictionnary.

>>> Substitution()
Substitution()
>>> Substitution(x=1, y=2)
Substitution(...)
>>> Substitution([('x', 1), ('y', 2)])
Substitution(...)
>>> Substitution({'x': 1, 'y': 2})
Substitution(...)

Method Substitution.__eq__

def __eq__ (self, other) :

Test for equality.

>>> Substitution(x=1, y=2) == Substitution(y=2, x=1)
True
>>> Substitution(x=1, y=2) == Substitution(y=1, x=1)
False

Method Substitution.__ne__

def __ne__ (self, other) :

Test for inequality.

>>> Substitution(x=1, y=2) != Substitution(y=2, x=1)
False
>>> Substitution(x=1, y=2) != Substitution(y=1, x=1)
True

Method Substitution.items

def items (self) :

Return the list of pairs (name, value) such that the substitution maps each name to the correspondign value.

>>> Substitution(x=1, y=2).items()
[('...', ...), ('...', ...)]

Call API

• return list: a list of pairs (name, value) for each mapped name

Method Substitution.domain

def domain (self) :

Return the set of mapped names.

>>> list(sorted(Substitution(x=1, y=2).domain()))
['x', 'y']

Call API

• return set: the set of mapped names

Method Substitution.image

def image (self) :

Return the list of values associated to the names.

>>> list(sorted(Substitution(x=1, y=2).image()))
[1, 2]

Call API

• return list: the list of values associated to names

Method Substitution.__contains__

def __contains__ (self, name) :

Test if a name is mapped by the substitution.

>>> 'x' in Substitution(x=1, y=2)
True
>>> 'z' in Substitution(x=1, y=2)
False

Call API

• str (usually) name`: the name to test
• return bool: a Boolean indicating whether this name is in the domain or not

Method Substitution.__iter__

def __iter__ (self) :

Iterate over the mapped names.

>>> list(sorted(iter(Substitution(x=1, y=2))))
['x', 'y']

Call API

• return generator: an iterator over the domain of the substitution

Method Substitution.__str__

def __str__ (self) :

Return a compact string representation.

>>> str(Substitution(x=1, y=2))
'{... -> ..., ... -> ...}'

Call API

• return str: a simple string representation

Method Substitution.__repr__

def __repr__ (self) :

Return a string representation suitable for eval.

>>> repr(Substitution(x=1, y=2))
'Substitution(...)'

Call API

• return str: a precise string representation

Method Substitution.dict

def dict (self) :

Return the mapping as a dictionnary.

>>> Substitution(x=1, y=2).dict() == {'x': 1, 'y': 2}
True

Call API

• return dict: a dictionnary that does the same mapping as the substitution

Method Substitution.copy

def copy (self) :

Return a distinct copy of the mapping.

>>> s1 = Substitution(x=1, y=2)
>>> s2 = s1.copy()
>>> s1 == s2 and s1 is not s2
True

Call API

• return Substitution: a copy of the substitution

Method Substitution.__setitem__

def __setitem__ (self, var, value) :

Assign an entry to the substitution

>>> s = Substitution()
>>> s['x'] = 42
>>> s
Substitution(x=42)

Call API

• str var: the name of the variable
• object value: the value to which var is bound

Method Substitution.__getitem__

def __getitem__ (self, var) :

Return the mapped value.

>>> s = Substitution(x=1, y=2)
>>> s['x']
1
>>> try : s['z']
... except DomainError : print(sys.exc_info()[1])
unbound variable 'z'

Call API

• str (usually) var`: the name of the variable
• return object: the value that var maps to

Exceptions

• DomainError: if var does not belong to the domain

Method Substitution.__call__

def __call__ (self, var) :

Return the mapped value or var itself if it is not mapped.

>>> s = Substitution(x=1, y=2)
>>> s('x')
1
>>> s('z')
'z'

Call API

• str (usually) var`: the name of the variable
• return object: the value that var maps to or var itself if it does not belong to the domain

Method Substitution.__add__

def __add__ (self, other) :

Add two substitution. Fails with DomainError if the two substitutions map a same name to different values.

>>> s = Substitution(x=1, y=2) + Substitution(y=2, z=3)
>>> s('x'), s('y'), s('z')
(1, 2, 3)
>>> try : Substitution(x=1, y=2) + Substitution(y=4, z=3)
... except DomainError : print(sys.exc_info()[1])
conflict on 'y'

Call API

• Substitution other: another substitution
• return Substitution: the union of the substitutions

Exceptions

• DomainError: when a name is inconsistently mapped

Method Substitution.__mul__

def __mul__ (self, other) :

Compose two substitutions. The composition of f and g is such that (f*g)(x) is f(g(x)).

>>> f = Substitution(a=1, d=3, y=5)
>>> g = Substitution(b='d', c=2, e=4, y=6)
>>> h = f*g
>>> h('a'), h('b'), h('c'), h('d'), h('e'), h('y'), h('x')
(1, 3, 2, 3, 4, 6, 'x')

Call API

• Substitution other: another substitution
• return Substitution: the composition of the substitutions

Method Substitution.restrict

def restrict (self, domain) :

Restrict the substitution to domain, ie remove all elements that are not in domain. Note that domain may include names that are not in the substitution, they are simply ignored.

>>> s = Substitution(a=1, b=2, c=3, d=4).restrict(['a', 'b', 'z'])
>>> list(sorted(s.domain()))
['a', 'b']

Call API

• iterable domain: the new domain as a set/list/... of names
• return Substitution: the restricted substitution

Class Symbol

class Symbol (object) :

A symbol that may be used as a constant

Method Symbol.__init__

def __init__ (self, name, export=True) :

If export is True, the created symbol is exported under its name. If export is False, no export is made. Finally, if export is a string, it specifies the name of the exported symbol. Exporting the name is made by adding it to the caller's global dict.

Call API

• str name: the name (or value of the symbol)
• str or bool or None export: the name under which the symbol is exported

>>> Symbol('foo')
Symbol('foo')
>>> foo
Symbol('foo')
>>> Symbol('egg', 'spam')
Symbol('egg', 'spam')
>>> spam
Symbol('egg', 'spam')
>>> Symbol('bar', False)
Symbol('bar', False)
>>> bar
Traceback (most recent call last):
 ...
NameError: ...

Method Symbol.__eq__

def __eq__ (self, other) :

Test for equality of two symbols, which is the equality of their names.

>>> Symbol('foo', 'bar') == Symbol('foo')
True
>>> Symbol('egg') == Symbol('spam')
False

Method Symbol.__ne__

def __ne__ (self, other) :

Test for inequality.

>>> Symbol('foo', 'bar') != Symbol('foo')
False
>>> Symbol('egg') != Symbol('spam')
True

Method Symbol.__str__

def __str__ (self) :

Short string representation

>>> str(Symbol('foo'))
'foo'

Method Symbol.__repr__

def __repr__ (self) :

String representation suitable for eval

>>> Symbol('foo')
Symbol('foo')
>>> Symbol('egg', 'spam')
Symbol('egg', 'spam')
>>> Symbol('bar', False)
Symbol('bar', False)