Transcript value

CSC 310 – Procedural Programming
Languages, Spring, 2009
Chapters 7 and 8: Python Data Types,
Subroutines and Control Abstraction
Definition of Types
• Denotational type system
– A type is a set of possible values.
• Constructive – type system is a union of:
– Built-in (primitive or predefined) types;
– Composite, constructed types.
• Abstraction-based
– Interface consisting of a set of constants and
operations
Python’s Dynamic Type System
• Python uses dynamic typing. There is no type for
parameters, variables and fields. Each value has a
type tag.
>>> a = 3
>>> type(a)
<type 'int'>
>>> a = 3.0
>>> type(a)
<type 'float'>
>>> a = 'this is a string‘
>>> type(a)
<type 'str'>
Types are run-time values
• Compare types for equality.
>>> type(a) == str # Some built-in types have built-in names.
True
>>> import types # See 'types' module in PY Ch. 13
>>> type(a) == types.StringType # all built-in object types
True
>>> t = type(type(a))
>>> t
<type 'type'>
>>> type(t)
<type 'type'>
Dynamic versus static type checking
Weak versus strong type checking
• Python is dynamically and strongly typed.
– A value (a.k.a. object) carries a type tag.
– Values must be type compatible within
operations.
• The source-to-bytecode compiler checks
syntax, but it does not check type.
• Lack of static type checking puts a heavier
burden on testing to verify type compatibility.
Type equivalence
• Structural equivalence compares the composite
construction of two types.
• Name equivalence is based on lexical occurrence of
type definitions. Python uses name equivalence.
>>> type(3)
<type 'int'>
>>> type(3) == type(4)
True
>>> from types import *
>>> type(3) == IntType
True
Aliased types
• Some languages have strict name equivalence for aliased
types. Each name is a distinct type.
• Python has loose name equivalence, because what matters is
the type’s value.
>>> int
<type 'int'>
>>> mytype = int
>>> mytype == int
True
>>> mytype(3.7)
3
>>> mytype("5")
5
Explicit type conversion
• Conversion uses a type name to cast a value
from one type to another.
>>> i = 3
>>> type(i)
<type 'int'>
>>> i = float(i)
>>> type(i)
<type 'float'>
Implicit type coercion
• Mixed type arithmetic promotes to float.
>>> value = 3 + 4 * 2.0
>>> value
11.0
Integer overflow promotes to extended precision
long.
>>> i = 1 << 30 ; i
1073741824
>>> i = i << 1 ; i
2147483648L
Most conversions are explicit
• Most conversions must be explicit type casts
>>> value = 3.0 + ' units'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'float' and 'str'
>>> value = str(3.0) + ' units' ; value
'3.0 units'
>>> value = 3.0 + float("-4.5") ; value
-1.5
No C-like non-converting types casts
• C/C++ supports non-converting casts
float fval = 1.3125 ; int ival = *((int *) &fval);
printf("float value %f gives bit pattern 0x%x\n",
fval, ival);
float value 1.312500 gives bit pattern 0x3fa80000
• Python’s struct module can convert to a bit pattern
format, then back to Python.
from struct import pack, unpack
>>> '%x' % (unpack('i', pack('f', 1.3125))[0])
'3fa80000'
Polymorphism
• A single body of code works with objects of multiple types.
• Implicit parametric polymorphism in Python.
>>> def summer(termlist):
... mysum = termlist[0]
... for term in termlist[1:]:
...
mysum = mysum + term
... return mysum
...
>>> summer([3, 5, 7])
15
>>> summer(('cat ', 'dog ', 'beaver '))
'cat dog beaver '
Abstraction-based types
• Python type compatibility is determined
largely by the operators that combine values.
• Subtype polymorphism takes the form of
related derived classes with alternative
method definitions. The methods determine
type compatibility.
• Operator overloading and make methods look
syntactically like operators.
Subtype polymorphism in Python
>>> class baseclass(object):
... def f(self, param):
...
raise Exception, "not implemented"
>>> class derived1(baseclass):
... def f(self, param):
...
return int(param)
>>> class derived2(baseclass):
... def f(self, param):
...
return float(param)
>>> d1 = derived1() ; d2 = derived2()
>>> d1.f(3)
RETURNS
>>> d2.f(3)
RETURNS
>>> d1.f(-3.2)
RETURNS
>>> d2.f(-3.2)
RETURNS
3
3.0
-3
-3.2000000000000002
Additional explicit type check
operations for objects
>>> baseclass
<class '__main__.baseclass'>
>>> derived1
<class '__main__.derived1'>
>>> type(derived1)
<type 'type'>
>>> type(int)
<type 'type'>
>>> isinstance
<built-in function isinstance>
>>> isinstance(d1, baseclass)
True
>>> isinstance(d1, derived1)
True
>>> isinstance(d1, derived2)
False
>>> issubclass(derived1,
baseclass)
True
>>> issubclass(derived1,
derived1)
True
>>> issubclass(derived1,
derived2)
False
Python composite types
• Strings are a built-in type with extensive support.
• List type supports heterogeneous sequences.
• >>> l = [1, 'a', None] ; print l
• [1, 'a', None]
• Tuple acts like an immutable list.
• >>> t = (1, 'a', None, l) ; print t
• (1, 'a', None, [1, 'a', None])
• Dictionary is a mapping. Key is immutable.
• >>> d = {'a' : 1, 'b' : 2} ; print d['b']
• 2
• Set or frozenset is an unordered collection.
• >>> s = set([1, 'a', None]) ; print s
• set(['a', 1, None])
No support for explicit parametric
polymorphism
• No C++ or Java-like “list of int” generic types.
• >>> print type(l) ; print type(t) ; print type(d) ; print
type(s)
• <type 'list'>
• <type 'tuple'>
• <type 'dict'>
• <type 'set'>
• A Python container can hold a mix of types.
Missing types
• No standard array type.
• List indexing is similar to arrays.
• Module array (PY 15) stores primitive type objects.
• No subranges or enumeration types.
• No fixed or variant contiguous records.
• No struct or union as in C/C++.
• Class objects can be used as records.
• No private, etc. access protection on fields.
• __field__ naming convention denotes private.
• Programmers can create their own types via the
C/C++ or Java (for Jython) extension APIs.
Class objects as records
• >>> r = record()
• print r.a ; r.b = "a value" ; print r.b
• None
• a value
• Methods use self.a or self.b to access fields.
• Parameter self is an explicit, first parameter to
object methods.
• Equivalent to this in C++ or Java.
Values and References
• Python uses values for primitives,
references for composite types.
• Every datum is an object.
• >>> from copy import copy, deepcopy ;
print l
• [1, 'a', None]
• >>> l2 = l
• >>> l3 = copy(l) # shallow copy
• >>> l4 = deepcopy(l)
• >>> l2 == l
• True
>>> l3 == l
True
>>> l4 == l
True
>>> l2 is l
True
>>> l3 is l
False
>>> l4 is l
False
Pointers and Recursive Types
• Object references are notational.
•
•
•
•
•
•
•
•
•
•
•
•
There are no explicit pointers. A reference is a pointer.
>>> l
[1, 'a', None]
>>> l.append(l)
>>> l
[1, 'a', None, [...]]
>>> l[3] == l
True
>>> l[3] is l
True
>>> l[3][3][3][3] is l
True
Binary tree in a list
>>> t = []
>>> def insert_into_binary_tree(tree, value):
... if (not tree): # 'null pointer' beyond a leaf
...
tree.extend([value, [], []])
...
return tree
... elif (tree[0] == value):
...
return tree
... elif (value < tree[0]):
...
return(insert_into_binary_tree(tree[1],
value))
... else:
...
return(insert_into_binary_tree(tree[2],
value))
>>> insert_into_binary_tree(t, 5)
>>> insert_into_binary_tree(t, 4)
>>> insert_into_binary_tree(t, 1)
>>> insert_into_binary_tree(t, 2)
>>> insert_into_binary_tree(t, 17)
>>> insert_into_binary_tree(t, -5)
>>> t
[5, [4, [1, [-5, [], []], [2, [], []]], []], [17, [], []]]
>>> t
[5,
[4,
[1,
[-5, [], []],
[2, [], []]], []],
[17, [], []]]
No dangling references or uncollected
objects (no garbage)
• Python uses a garbage collector.
• Reference counting tracks most objects.
• Every variable binding adds a reference.
• Additional garbage collection for circular
structures.
•
•
•
•
May be mark and sweep.
May be stop and copy.
May be generational collection.
Details not specified by the language.
Subroutines and Control Abstraction
• Python supports functions / procedures,
object methods, generators (iterators) and
closures (function + static environment).
• Primitive parameters are values.
• Object parameters are references.
• Immutable objects (e.g. tuples) cannot be changed.
• Functions and methods are first class objects.
• Reflection supports interactive inspection of
functions.
Python’s call stack
• The call stack occupies contiguous memory.
• >>> from sys import getrecursionlimit, setrecursionlimit
• getrecursionlimit()
• 1000
• Each stack frame points to dynamic data
structures.
• Both static (lexical) and dynamic bindings
resides in dynamic data structures.
Parameters are values for primitives,
references for objects
>>> def modl(l):
... l = [1, 2, 3]
... print "modl sees
" + str(l)
>>> gl = [4, 5, 6]
>>> modl(gl)
modl sees [1, 2, 3]
>>> print gl
[4, 5, 6]
>>> def modelem(l):
... l[1] = 111
... l.append('appended
string')
... print "modelem sees " +
str(l)
>>> gl = [4, 5, 6]
>>> modelem(gl)
modelem sees [4, 111, 6,
'appended string']
>>> print gl
[4, 111, 6, 'appended string']
>>> modelem(tuple(gl))
Traceback (most recent call last):
TypeError: 'tuple' object does not support
item assignment
A closure both sees its lexical
environment and saves it as well!
>>> def outer(vala):
... def inner(valb):
...
return vala + valb
... return inner
...
>>> f = outer(5)
>>> f
<function inner at 0x9ad70>
>>> f(6)
11
Closures in Python
>>> dir(outer)
['__call__', … 'func_closure', …]
>>> dir(f)
['__call__', … 'func_closure', …]
>>> print outer.func_closure
None
>>> print f.func_closure
(<cell at 0xa4430: int object at 0x668c0>,)
Uncovering the static link in a closure
•
•
•
•
•
•
>>> print f.func_closure[0]
<cell at 0xa4430: int object at 0x668c0>
>>> print type(f.func_closure[0])
<type 'cell'>
>>> dir(f.func_closure[0])
['__class__', '__cmp__', '__delattr__', '__doc__',
'__getattribute__', '__hash__', '__init__', '__new__',
'__reduce__', '__reduce_ex__', '__repr__',
'__setattr__', '__str__', 'cell_contents']
• >>> f.func_closure[0].cell_contents
• 5
Both positional and keyword
parameters supported
• Positional, if any, come first in a call.
• Default values come last in a definition.
•
•
•
•
•
•
•
•
•
•
•
•
>>> def sum(a, b=3):
... return a + b
>>> sum(2)
5
>>> sum(2,7)
9
>>> sum(b=8, a=9)
17
>>> sum(4, a=9)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: sum() got multiple values for keyword argument 'a'
Apply allows processes to construct
function calls at run time.
>>> f = sum
>>> keywordargs = {'a': 3, 'b': 4}
>>> apply(f,(),keywordargs)
7
>>> apply(f,(7, 6), {})
13
>>> eval("sum(4,5)") # eval() evaluates text
9
Variable number of *positional and
**keyword arguments
• A trailing *param is a tuple of variable-length positional
parameters. A trailing **param is a dictionary of keyword
parameters.
• >>> def sum(*terms):
• ... mysum = terms[0]
• ... for t in terms[1:]:
• ...
mysum += t
• ... return mysum
• ...
• >>> sum(1, 2, 3, 4, 5)
• 15
Exception handling
• Exceptions are class objects, similar to C++ and Java.
• Finally and except clauses cannot appear in the same try
statement. Use nested try.
>>> try:
... i = int('dog')
... except ValueError, estring:
... print "exception says: " + str(estring)
...
exception says: invalid literal for int() with base 10: 'dog‘
• Use raise to throw an exception.
Generators are Pythons iterators
>>> def g(start, end):
... for v in range(start,end):
...
yield v
...
>>> gen = g(1,4)
>>> gen.next()
1
>>> gen.next()
2
>>> gen.next()
3
>>> gen.next()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration