/css" href="style.css" title="style1"> CS1120: Schemer's Guide to Python
cs1120  Spring 2010

cs1120: Computer Science
from Ada and Euclid to Quantum Computing and the World Wide Web


Instructor
Westley Weimer

Teaching Assistants
David Noble
Kinga Dobolyi
Nick Wasilewski
Patrick Mutchler
Rachel Rater
Zak Fry
Email Address
cs1120-staff@cs.virginia.edu

Class Meetings
Mondays and Wednesdays, 3:30-4:45pm in MEC 341
Office & Lab Hours
Mon 12:30-13:30 Small Hall Lab
Mon 13:30-14:00 Olsson 219
Mon 14:00-15:00 Small Hall Lab
Mon 17:00-19:30 Thornton Stacks
Tue 11:00-12:30 Olsson 001
Wed 10:30-13:00 Thornton Stacks
Wed 13:30-14:00 Olsson 219
Thu 10:00-12:30 Thornton Stacks
Sun 13:00-14:30 Olsson 001
Sun 14:30-17:00 Olsson 001

unctions (and procedures). Python is designed for an imperative programming style (although one of the best features of Python is its incorporation of functional programming features). This means most of a Python program is assignments. In Scheme, we use set! to do assignment. In Python, we use the = sign to mean assignment (to do equality comparisons, Python uses ==):
AssignmentStatement ::= Variable = Expression

To evaluate an AssignmentStatement, Python evaluates the Expression and places the value in the place named Variable. (Just like the Scheme evaluation rule for set!). The only difference is if there is not already a place named Variable, Python will create a new place as a result of the assignment statement. Hence, the Python statement x = 1 will act like (define x 1) if there is no place already named x, and like (set! x 1) if there is already a place named x.

An expression in Python is similar to an expression in Scheme — it is a code fragment that evaluates to a value. In Python, expressions use infix notation. The operator is placed between the operands (except for function calls, described below). Python supports most of the standard arithmetic operators. Here are some examples:

SchemePython
(define four 4)
(define two (/ four 2))
(define bigger (< (* four four) 17)
(printf "four: ~a two: ~a bigger: ~a" four two bigger)

four: 4 two: 2 bigger #t

four = 4
two = four / 2
bigger = (four * four) < 17
print "four: %d two: %d bigger: %d" % (four, two, bigger)

four: 4 two: 2 bigger: 1

The parentheses in the assignment to bigger are necessary for grouping oprations. Without them it would mean (* four (< four 17)) instead of (< (* four four) 17).

Python uses 1 to mean true. Python considers the empty string, 0, and the empty list to be false, and (almost) everything else true.

The print procedure takes a string as input followed by a % and a list of values (in parentheses). The values are matched to the % codes in the string. Different % codes are used for printing different types of values. Here, %d is used to print an integer.

Applying Functions

In Python, we apply a function to operands by following the name of the function with a comma-separated list of arguments surrounded by parentheses:
ApplicationStatement ::= Name ( Arguments )
Arguments ::=
Arguments ::= MoreArguments
MoreArguments ::= Argument ,MoreArguments
MoreArguments ::= Argument
Argument ::= Expression
So, Proc (Arguments) in Python is similar to (Proc Arguments) in Scheme (except there are no commas between the arguments in Scheme).

Python only has a few primitive functions, but a very extensive standard library.

Defining Functions

Defining a procedure in Python is similar to in Scheme, except: We define a function using:
FunctionDefinition ::= def Name ( Parameters ): <newline> Statements
Parameters ::=
Parameters ::= MoreParameters
MoreParameters Parameter ,MoreParameters
MoreParameters ::= Parameter
Parameter ::= Variable
For example,
SchemePython
(define square (lambda (x) (* x x)))

(define quadratic (lambda (a b c x)
   (+ (* a (square x)) (* b x) c)))

(display (quadratic 2 3 7 4))

51

def square (x):
   return x * x
def quadratic (a, b, c, x):
   return a * square (x) + b * x + c

print quadratic (2,3,7,4)

51

Note that unlike Scheme, where the procedure body is an expression and the value of an application is the value of that expression (evaluated in the new environment with the parameters bound), in Python, the procedure body is a list of Statements. The special statement,

ReturnStatement ::= return Expression
is used to return a value from a procedure. When execution encounters a return statement, the Expression is evaluated and returned to the caller.

Python also provides a form lambda for making procedures the way you would in Scheme using lambda:

Expression ::= lambda Parameters : Expression
The parameters are defined as above, and the body is the one expression (a return before the expression is implied). For example, (lambda (a b) (+ a b)) would be lambda a, b: a + b. Here's an example:
def makeAdder (a):
   return lambda b: a + b

add5 = makeAdder (5)
print "Adding: " + str(add5(2))

Adding: 7

Note that here we concatenate the string "Adding: " with str(adder(2,2)); str converts the output of adder(2,2) to a string.

Python does not evaluate applications the same way as Scheme, however. In particular, Python does not create a chain of frames for evaluation purposes. Instead, there are only two namespaces (Pythonspeak for frames): the global namespace and the local namespace.

Control Statements

Python also provides several statements similar to Scheme special forms. Two useful ones are if and while which are described below.

If

The if statement is similar to Scheme's if special form:
Statement ::= if (Expression): <newline> Statements
is equivalent to (if Expression (begin Statements)).

Python also supports alternative clauses but uses else to distinguish them:

Statement ::= if (Expression) :
                                Statements1
              else :

                                Statements2
is equivalent to (if Expression (begin Statements1) (begin Statements2)).

While

The while statement repeats a sequence of statements as long as the test expression is true:
Statement ::= while (Expression):
                             Statements
The indentation of the statements determines the statements that are looped.

Here is an example that will print out the first 10 Fibonacci numbers:

i = 1;
a = 1;
b = 1;
while (i <= 10):
  print "Fibonacci %s = %s" % (i,b);
  next = a + b;
  a = b;
  b = next;
  i = i + 1;
print "Done."

Types

Like Scheme, Python has latent (invisible) types that are checked dynamically. The four types you will find most useful are numbers, strings, lists, and dictionaries.

Numbers

Python treats numbers like Scheme, except it does not do exact arithmetic. Instead of using fractions, everything is treated as either an integer or a floating point number. Here are some examples:

SchemePython
(define four 4)
(define pi 3.14159)
(define half 1/2)
four = 4
pi = 3.14159
nothalf = 1/2     (evaluates to 0)
half = 1.0/2.0     (evaluates to .5)

What happened when we defined nothalf?

Unlike Scheme, Python makes a distinction between integer math and floating point math. This normally isn't that important; when we do math between the same types, the result is the same type, and when we do math with a floating point number and an integer, the type returned is a floating point number. However, the result of division of an integer by another integer is not necessarily an integer -- Python will silently discard the fractional part of the answer. By writing the operands with decimal points, we ensure that the operation will return a floating point number. This problem only rarely occurs, but you should always be aware of it when searching for bugs.

Strings

Python treats strings like Scheme: they need quotation marks. You can use single quotes ('), double quoteS ("), or triple quotes ("""). However, there is a very important difference between triple quotes and other quotes; when you use triple quotes you can break lines in the string, but when you use single or double quotes you can not.

You can concatenate (run together) two strings by using the plus sign (+):

name = "Spot"
print "See " + name + " run."
If you want a literal quote to appear in a string you print, use \":
print "My name is \"Spot\"."
The triple quote, """ is an easy way to print large chunks of text that can include double quotes and new lines. For example,
print """
"I find that the harder I work, the more luck I seem to have."
   --- Thomas Jefferson
"""
will print out

"I find that the harder I work, the more luck I seem to have."
  --- Thomas Jefferson

Lists (and Tuples)

Python has its own version of lists; although these have many things in common with Scheme lists, it's best to think of them as a different data type.

The biggest difference between a Scheme list and a Python list is that elements in Python lists are can be accessed directly. This means that we can access any element of the list if we know it's number; we had to write our own function in Scheme to get this functionality.

SchemePython

> (define lst (list 10 20 30))

> (car lst)

10

> (car (cdr (cdr lst)))

30

lst = [10, 20, 30]
print lst[0]

10

print lst[2]

30

Indices in Python are much more powerful than that, however. We can "slice" lists to only look at a subset of the list data.

lst = [10, 20, 40, "string", 302.234]

print lst[0:2]

[10, 20]

print lst[:3]

[10, 20, 40]

print lst[3:]

['string', 302.23399999999998]

(Note that decimal numbers are not exact — we put 302.234 in the list, but the printed value is 302.23399999999998.)

Finally, if we want to iterate over an entire list, we use the for statement:

Statement ::= for VaribleList in ExpressionList : Statements
For example,
def sum (lst):
   total = 0
   for el in lst:
      total = total + el
   return total

print sum([1, 2, 3, 4])

10

Dictionaries

Python also has "dictionaries", referred to as a "hash tables" or "lookup tables" in some other languages.

A dictionary is a list of (key, value) pairs. In Python, the key can be any "immutable" object (tuples, strings, numbers), and the value can be any Python object. We can initialize a dictionary using the initialization expression:

DictionaryInitializationStatment ::= Variable = { InitializationExpressions }
InitializationExpressions ::=
InitializationExpressions ::= InitializationExpression, InitializationExpressions
InitializationExpression ::= Expression : Expression

The expression before the : is the key, and the following expression is the associated value.

We can set the value associated with a key using a set statement:

SetStatement ::= Expression [ Expression ] = Expression
We get the value associated with a key using:
FetchExpression ::= Expression [ Expression ]
The first expression in a fetch expression must evaluate to a dictionary.

Here are some examples:

yellow = { 'red': 255, 'green': 255, 'blue': 0 }
print '(%s, %s, %s)' % (yellow['red'], yellow['green'], yellow['blue'])

(255, 255, 0)

yellow['red'] = 230 print '(%s, %s, %s)' % (yellow['red'], yellow['green'], yellow['blue'])

(230, 255, 0)

Of course, we can put arrays in arrays, just like we can make lists of lists in Scheme. To do something to everything in the array, we first have to use the built-in "keys" method of the dictionary. For example, to reset yellow, we would do:

for key in yellow.keys():
    yellow[key] = 0
There are several other useful operators for dictionaries:

Classes

In Scheme, we defined objects by explicitly packaging procedures and state. Python provides classes as a way to package procedures and state. We will only scratch the surface of Python's object-oriented features here, but it is an integral part of the language.

ClassDefinition ::= class Name:
                                           FunctionDefinitions

These function definitions will form the "methods" of the class. There are lots of special methods, and we can also create our own. The only special method we'll worry about now is the __init__ method that is used when we create an instance of an object. The __init__ method is similar to the make-class methods from Problem Set 6.

Here's an example:

SchemePython

(define (make-object name)
  (lambda (message)
    (case message
      ((class) (lambda (self) 'object))
      ((object?) (lambda (self) #t))
      ((name) (lambda (self) name))
      ((say)
        (lambda (self list-of-stuff)
          (if (not (null? list-of-stuff))
              (display-message list-of-stuff))
          'nuf-said))
      ((install) (lambda (self . args) 'installed))
      (else no-method))))

class my_object:
   def __init__(self, name):
      self._name = name
   def is_object(self):
      return True
   def whatclass(self):
      return type(self)
   def name(self):
      return self._name
   def say(self, lst):
      for x in lst:
         print x
   def install(self, args):
      print "Installed"

Although the differences between the two languages prevent a direct translation (for example, object and class are both reserved words in Python, and we can't have both a data item and a member function titled "name"), it is easy to see the similarities here. We don't have to use application to create a new frame in Python; the language takes care of that for us. The variable _name introduced in __init__ will be stored in a place accessible only to this object. self._name refers to the _name variable inside the object self; self is passed into any method of an object (we'll see how this works below.)

obj = my_object("bob")

obj.name()

"Bob"

obj.is_object()

True

obj.say(["hello, world"])

hello, world

In the first line, we create a new my_object, passing it the value "bob" which will be stored as the _name value; this calls the classes __init__ method. Now, whenever we type obj.method(args), the member function of my_object is called with the first argument obj and the other arguments to the function appended in a frame where this objects variables are defined.

Python provides a convenient mechanism for inheritance:

ClassDefinition ::= class SubClassName ( SuperClassName ) :
                                           FunctionDefinitions
creates a new class named SubClassName that inherits from SuperClassName. Here's an example from PS6:

SchemePython

(define (make-lecturer name)
  (let ((super (make-object name)))
    (lambda (message)
      (if (eq? message 'lecture)
	  (lambda (self stuff)
	    (ask self 'say stuff)
	    (ask self 'say (list "you should be taking notes")))
	  (get-method super message)))))

class lecturer (my_object):
   def lecture(self, stuff):
      self.say (stuff)
      print "you should be taking notes" 

Because of Python's built in support for classes, object-oriented programs in Python are shorter and more elegant than object-oriented programs in Scheme.

Interacting with Web Requests

Producing Output

When a client browser requests a cgi page that is a python program, the web server runs the Python interpreter on that page and sends the output back to the client. The output is everything the page prints, so all you have to do in a Python program to send content back to the client is use print.

The first line of the CGI file should be:

   #!/uva/bin/python
This tells the web server that the rest of the file is a Python program that should be executed to produce the output page.

In order for the output to be interpreted as HTML, we need to print the content type at the beginning of the output:

   print "Content-type:text/html\n"
The \n prints a new line.

Getting Input

CGI is, for a variety of good and bad reasons, extremely complicated. Luckily, Python includes a complete CGI handler that takes care of all of the messy details. Instead, at the beginning of every cgi program that expects data from an HTML form, we can begin that script with:

import cgi
form = cgi.FieldStorage()

This assigns to form a dictionary of form values. For every form element with a name="Name" parameter in your HTML form, form will have a field with the name Name and assign it whatever data the user entered. We can access this with form["Name"].getvalue(). This extra getvalue() is required as opposed to a regular dictionary because of how CGI processes the form.

For the example form:

<FORM METHOD="POST" ACTION="formproc.cgi">
 First name: <INPUT TYPE="TEXT" NAME="FirstName"><BR>
 Last name: <INPUT TYPE="TEXT" NAME="LastName"><BR>
 Comments:<BR>
  <TEXTAREA ROWS="3" NAME="UserComments"></TEXTAREA><BR>
 <INPUT TYPE="SUBMIT"><INPUT TYPE="RESET">
</FORM>

The file listed as ACTION= in the form will process the submitted form. Here's what formproc.cgi contains:
#!/uva/bin/python
import cgi

print "Content-type:text/html\n"
print "<html><head><title>Form Response</title></head>\n"
print "<body>\n"

form = cgi.FieldStorage()

print "Thank you for your information!"
print "<BR>"
print "The keys are: "
print form.keys ()
print "<p>"
print "First name: " + form['FirstName'].value + "<br>"
print "Last name: " + form['LastName'].value + "<br>"
print "Comments: " + form['UserComments'].value + "<br>"

print "</body></html>\n"

You can try it here:

First name:
Last name:
Comments:

Using SQL

Before reading this section, read the SQL Guide.

Python provides procedures for interacting with a database using SQL. You can call these procedures like any other Python procedure. The Python evaluator will send the appropriate commands to the SQL database.

Before using any SQL commands, you'll want to connect to the database server and open a database. To tell Python we're going to be using a MySQL database, we begin the script with

import MySQLdb

Now you can connect to the database with your username and the password you created before, for example:

server = "dbm1.itc.virginia.edu"
username = "dee2b"
password = "quist"
dbName = "dee2b_presidents"

db=MySQLdb.connect(server, username, password, dbName)

In particular, dbm1.itc.virginia.edu is the hostname of ITC's database, username and password are those used to create your account, and dbName is the name of the database you created.

Now that we have a connection to the database we'll need a cursor to actually operate on it. Basically a cursor is just a way of keeping track of where you are in a table or result set. Getting a cursor from the database is simple:

cursor = db.cursor()

Now that we have a cursor to the database, we can execute queries, for instance:

college = "William and Mary"
cursor.execute("""Select lastname, firstname from presidents
                  where college=%s order by lastname""", (college,))

That last part, (college,) probably looks a little funny: this is simply because Python's database interface requires any parameters as a sequence. In general, if you know what you're looking for, you could insert it directly, for instance:

cursor.execute("""Select lastname, firstname from presidents
                  where college='William and Mary'""")

Using %s lets us figure out something to look for based on a variable (for instance, a form field) rather than having to hard-code it. Now that we've executed the database query, if we did a SELECT statement, there are a few things we can do with the cursor:

Alternately, if we executed an INSERT, DELETE, or UPDATE, we need to tell the database to go ahead and save, or commit, our changes:

db.commit()

At the end of your program, you can close the database connection with

db.close()

It's important to make sure you've committed the changes before closing, because otherwise the Python database interface will assume you didn't mean to make the changes and will perform a rollback - essentially undoing every change since the last commit.

Credits: This guide was created by David Faulkner, Dan Upton, and David Evans for CS150 Fall 2005. It was revised for CS 150 in Spring 2009 by Westley Weimer.

CS1120: Schemer's Guide to Python
cs1120  Spring 2010

cs1120: Computer Science
from Ada and Euclid to Quantum Computing and the World Wide Web


Instructor
Westley Weimer

Teaching Assistants
David Noble
Kinga Dobolyi
Nick Wasilewski
Patrick Mutchler
Rachel Rater
Zak Fry
Email Address
cs1120-staff@cs.virginia.edu

Class Meetings
Mondays and Wednesdays, 3:30-4:45pm in MEC 341
Office & Lab Hours
Mon 12:30-13:30 Small Hall Lab
Mon 13:30-14:00 Olsson 219
Mon 14:00-15:00 Small Hall Lab
Mon 17:00-19:30 Thornton Stacks
Tue 11:00-12:30 Olsson 001
Wed 10:30-13:00 Thornton Stacks
Wed 13:30-14:00 Olsson 219
Thu 10:00-12:30 Thornton Stacks
Sun 13:00-14:30 Olsson 001
Sun 14:30-17:00 Olsson 001


cs1120: Computer Science
University of Virginia
weimer@virginia.edu
Using these Materials