Class outline

Class 1:

1. Historically started with usually several heavy programming courses before anything else, giving little inital idea what you were getting into!
2. Then there was a reaction to breadth-first, essentially no programming.  This is partly because in the past popular languages had a steep learning curve.  Instead of much programming in a real computer language, breadth-first courses have brought algorithms written in English to a central place.
3. That brings us to the present with this course.  Programming is important, and now there is an excellent recent language Python:  extremely simple to learn and understand (close to English) and very powerful  -- why do much in English outlines when with about as much work you can demonstrate things on the computer using Python?  Plus, even beginners can write programs to simplify their own personal tasks.  Hence we spend a fair amount of our time on algorithms actually working with Python.  We still keep the idea that Computer Science is much more than programming, and look at history and social and ethical implications.  We dig down into the guts of a computer below what we see from the high-level language Python, to machine language and assembler code, and to the hardware underneath.  We look beyond Python to application areas like graphics and web servers.

For the programming in Python, we use Zelle.  For most of the other topics, we use Decker/Hirshfield.  The two come close together when DH discusses web pages.  We will simplify the web page creation, relying on recent free software that makes writing web pages be basically using a special word processor.  Like DH, we want interaction with our web pages.  There are two possible approaches, both using web pages with forms on them:  DH chooses interaction restricted to the users machine, with  no memory between sessions, no interaction with other users, using a specialized language called Javascript,  just for use in browsers.  Another approach is to place intelligence on the web server, where we have a choice of programming languages, and we choose Python, of course!  

We are not alone in choosing Python:  Much of the control of Google is by Python, as is much of the administration of Unix.  (Microsoft has not adopted Python, since it does not own this free language, but Python is freely available for Windows, modern Macs, Linux ....)  

Make pairs, conveying information visually:  Indicate if you
live on campus, are a night person, have time after class, have time right before class, are flexible on weekends....?

Starting Python in the lab.  See Lab 1.  

Class 2

little of Zelle
Sign under your picture:  Nick name or first name, follwed by last name.

Mock quizzes (each is one question).  

1.  Briefly compare and contrast:  algorithm and program

2.  What does the following first program line mean to the Python interpreter?
        # File: chaos.py

Quiz procedures.

Questions on Zelle reading.

• what stood out for you as important, meaningful or hard?
• type in program and computer directly execute what you typed?
• syntax templates make sense?

Pair Programming partners: Ask to help people choose:  Free before class; free after class; free and on campus weekday evenings; flexible on campus weekends; + ?

More of Lab 1.  Starting Idle for Python. 

Z ch 2

Zelle questions

note appendix A, p 469!

Intro to Program 1

Intro to idle files, work in class easy input/process/output pattern.  Input a number, output with the square.  Note the input glitch in idle!

commenting out a block of lines  with alt-3 or the edit menu 

Lab 2

Class 3

ch 3 Zelle - range examples

loops in shell - - in idle indent automatically, hit <enter> twice to end

range in for loop as replacement for explicit sequence

vary future value:  print  year, by year, with label 1, 2, 3, ....

Lab 3 Task 1

Class 4

example file loopIdea.py

Do rest of Lab 3

Class 5 History

• Methods and pace of improvements
• Layers added vs. improvements in implementation
• Interplay between hardware, software, theory, and applications imagined
• Abstract ideas that make sense with very different hardware and implementation
• Interfaces and industrial standards
• Machines doing what humans used to do

ch 4 string stuff on slices

s = "computer"

To refer to a single element with a substript, it is easier to think of the data and indices as lined up:

For slices it is easier to think of indices between data elements:

index from left   0   1   2   3   4   5   6   7   8
           data   | c | o | m | p | u | t | e | r |
index from right -8  -7  -6  -5  -4  -3  -2  -1   

s[2:4] # 'mp'

If you use the same diagram to refer to a single subscript:  the data comes to the right of the subscript

Contrast:
when using a single subscript, the index must give an actual location in the string; 
but in slices, references to nonexistent elements are just ignored.
s[10] #  error
s[2:10] # 'mputer'
s[4:2] # '' (empty string)

Programming patterns so far:

• input/process/output
• accumulator for iterative changes:  initialize accumulator, update accumulator for a sequence of data in a loop

Do Lab 4 tasks 1-3

Class 6, Discussion of String operations

Numerical programming use all the most common operations and symbols.  In string programming, there are again fairly common operations, but the syntax is new, and you need to get used to what basic operations are available:  see table page 96!  Play with these in the shell - - the worst that happens is that you get an error message back!

Rest of Lab 4

Class 7

See the Review for Exam 1 -- link on the course home page 

Selected text solutions on web under Solutions link - - need id/password - - get it in class or from Blackboard Class Content page.

CAUTION:  The answers serve almost no purpose if you look first and then work on them or never work on them.  Reading is WAY different than writing!!!  If you are having trouble, resist the urge to look at the answers.  The significance of the answers is not their actual text but the mental process coming up with them!!!

Learning in English:  read and understand, write, practice writing!  
Learning in programming:  read and understand, write, practice writing!
Difference:  Priog languages picky about syntax.  hastle getting it right, but good to get direct feedback (On more complicated problems it is still an enormous issue to be sure you are right in all cases.)

Play with formatting:

    See example code stringFormat.py.

    Notes on the syntax summary:

• Width is the minimum width -- extra space is taken if needed.
• Precision (if present) must be preceded by the decimal point.
• When more than one data element is to be formatted and embedded in the format string, the values are separated by commas and enclosed in parentheses.  This is a another kind of sequence, a variant on a list called a tuple.
• The precedence of operators is always the same, whatever the type of the operands.  Note that in the showWidth function, there are parentheses around "x"*n.  They are not making a tuple -- there is only one string expression intended as the data.  See what happens when you remove the parentheses.  Explain this in terms of the precedence of the operators % and *.  (The % operator is related to division and has the same precedence as division.)  

    Do Lab 5 task 1 

for ch in "abcABC123!":
    print ch, ord(ch)

for n in range(32, 60):
    print n, chr(n)

For Each:  Above are examples of "for each" loops:  do something for each element of a sequence.  In the simplest situations, like above, the results from processing each element are basically independent -- what happened on the previous one odes not affect the next one.    

It is very important to understand the power of  these ideas with loops and be able to apply them:  If you know how to write instructions for how to do something with one piece of data, you can always process a sequence of such data in a loop.  When solving a problem for independent handling of a sequence of data values, you can always split the problem into two parts:

• How to handle one single case
• How to repeat in a loop   

In more complicated situations the results accumulate somehow, with each time through the loop making incremental changes to a result (or possibly several results).  This accumulator pattern is also very important.

Counting through a sequence

Often you want to process each element of a sequence and keep a count.  For instance to help you associate the right index number with each character in a string, we could write a loop to put the index of each character and the character itself on a line.  We will want a loop.  Since we want to print two pieces of data, index and character, we have several choices:  
    A.  for each index of a character in the sequence
or
    B.  for each character in the sequence

A.  Given a string s, how do you loop through each index in the string?
Inside the loop, given the index, how do you get the corresponing character?

B.  How do you loop through each character in a string directly?

See the example stringIndex.py for the details.  

(Coding each of these is instructive.  Also there is a more direct way, that is specific to Python:  if you want to get deeper into Python see the enumerate function in the Python documentation.)

Class 8

Files

With files we will often have "for each" loops:  either for each character or each line or each word.

Rest of Lab 5 

Introduce Program 2.

Strings and files as Objects

Class 9 

Class 10

From examples - graphics.py to program directory -- new version, updated for today!

updated zelle_code under password

Display graphics?  Mention logic that we are using a restricted version

Point out Graphics web pages under notes

objects, common features, clone, aliases, triangle.py

Lab 6

polygon#.py 0-1

polygon#.py 2-3

Lab 7

Class 11

Entry, Fahrenheit example

Lab 8

Class 12

Start Decisions  ifExamples.py  Lab 9

Class 13

Class 14

Class 15

 list of ints to printed pairs

coord = [10, 20, 5, 3, 30, 35, 40, 42]
print a list of coordinates in pairs (10, 20), (5, 3), (30, 35), (40,42)

look in slightly greater generality:

(s[0], s[1]), (s[2]], s[3]), (s[4], s[5]), (s[6], s[7])

string of ints to printed pairs

moreLoops.py

make card deck + random.shuffle(seq)

nested loops, play computer

testBool.py

other types converted to Boolean

Lab 11

Class 16

review materials for exam 2

functions
print string triangle for 'Bye!'
B
By
Bye
Bye!
print word triangle for any s
return String for triangle
isBetween(x, end1, end2)
distance(point1, point2)
makeCircle(center, ptOnCircle)

Lab 12

Lab 13

Class 17

Class 18

Class 19

Class 20

Finsih writing your own dynamics web pages and CGI scripts

Class 21

mutable objects:  mutable.py

New Assignment submission in Blackboard

Class 22

Pip Assember

As we will see more in Chapter 7, the state inside a computer is usually electrical, and the most dependable system uses voltages, either high or 0 (grounded) .  This means two possibilities.  This is a bit of information, the smallest possible amount.  We will arbitrarily refer to the two states as 0 and 1.  

Computers have a Central Processing Unit (CPU) connected by wires to a memory unit.  Operations take place inside the CPU, with some data maybe transfered in from memory or sent back to memory (and also external devices, though we will skip that part in our simple model).

Like in a Python list, memory is referenced by integer locations, 0, 1, 2, ....  There are several design decisions:  one is how much data to put in a single memory cell that can be individually referenced.  A common unit is a byte = 8 bits.  Pip uses a byte.  While a bit has two possible states, a byte has 2⁸ = 256 states.  Another choice is how big to allow memory to be.  So that one byte can used to refer to any cell in memory, we will assume memory consists of no more than 256 cells.

Von Neumann's concept was the encode the instructions as a form of data in the computer.  That means they must be a sequence of 0's and 1's, like

00010100 00000100  

I introduce the space in the middle only to delineate individual bytes.    

Pip Assembler Simulator

While you ar at it, download sample program files (also in the zip archive):  simple.bin, simple.asm, arith.asm, sum2n.asm, ifElse.asm

Run pipGUI.py.  You will see a graphical Window.  Click on the button that says BINARY, to see its 'native' state.  

The state of the simulated computer is shown in the CPU (lower left) with its accumulator (Acc) and Instruction Pointer (IP).  The middle blue and right yellow blocks display memory.  

First focus on the big middle blue rectangle labeled CODE.  In Pip instruction code is placed at the beginning of memory.  Each instruction takes up two bytes, so for convenience bytes are shown in pairs down the right portion of the main blue rectangle.   We will need to keep track of the locations of these instructions, so the left column in the  blue rectangle shows the address (in decimal) of the beginning of each instruction.  Beside the decimal address label is the same address in binary.  Because each instruction is two bytes, the address labels advance by 2's.

The remaining parts of the display are for controlling the simulator.  They do not correspond to parts of Pip.  The left column of buttons and text boxes is labeled COMMANDS.  You should have already clicked on the command button labeled BINARY. 

 Let us load a machine language program into Pip. Make sure you have downloaded simple.bin.  You can open it in the Idle editor, if you like.  It contains five binary instructions.  

Type simple.bin into the Filename text box.  Then click LOAD.  The contents of the file appear as the first five instructions in Pip.

An Introduction to Pip Machine Language

All Pip instructions use the Accumulator.  It is always a source of data and/or the destination of a result.  There are two other ways Pip refers to data.  One is to have the actual data encoded as the second byte of the instruction.  The more common way is to refer to a location in memory.  In this case the second byte is interpreted as the address in memory where the data resides.   That explains the second byte, so now the first byte.  It can be logically split into two four bit fields, for example

0001 0100 00000100  

In Pip we will have fewer than 16 basic operations, which are encoded in the second four bits.  

0001 0100 00000100  

The 0100 of this example means load a value into the accumulator.  We must distinguish where to get the value from, either the second byte of the instruction or a specified address in memory.  The first 4 bits (actually only 1 is needed) determine this.  The code is that 0000 means a memory address and 0001 means the actual data is in the second byte of the instruction.  That latter is the case above, where the second byte is 00000100 or 4 in decimal, so the full meaning of the instruction is load the value in the second byte (4) into the accumulator.

Look at the Simulator screen.  See that the accumulator (ACC) has a value of 0.  The instruction pointer (IP) shows the next instruction to execute.  It is also 0.  If you look at address 0 n the simulator you see the instruction we have been discussing.  ALso note that the binary version of the address 0 in the code it highlighted in orange.  To more easily follow what is going on, it wil always match IP.  Click STEP.   IP and the corresponding highlight should advance to 2, and the value in the accumulator should become 00000100 (or 4 in decimal).

One more machine language instruction, the one at address 2:

00000101 10000000    

or to look at the parts:

0000 0101 10000000    

The second four bits 0101 determine the type of instruction.  In this case it is "store the contents of the accumulator to an address in memory".  The second byte gives the address 10000000 (or 128 decimal).  In this case the second byte only makes sense as an address in memory, and the first four bits of the instruction, 0000, reflect this.   Hence the full instruction says to store the accumultor value at memory location 128.

Click STEP again.  Look at memory location 128 (or 10000000 in binary).  Also note IP in the CPU.

We could continue, but this gets tedious.  Reading this binary is a pain.  One of the first programs people wrote was an assembler, which translates something a bit more human readable into this binary code.  In the assember written for this machine, the first two instructions discussed could be written

LOD #4
STO 128

Still not English or as close as Python but closer!  In place of the second four bit pattern we have a three letter mnemonic.  LOD is close to LOAD.  STO is the beginning of STORE.  The pound sign is sometimes used to mean 'number'.  The first instruction says to load the number 4.  The second instruction does not have the '#'.  This means the other interpretation of the second byte is used:  it refers to a memory location.  

Click the button NONE under commands.  Now you see the instructions stated in assembler and all the address labels in decimal.

We will come back to machine language briefly at the end, but for the most part we will code things in assembler.

The next instruction is LOD #3.  From the earlier examples you should be able to figure out what that does.  Click STEP to check.  The next instruction is ADD 128.  It should be no surprize that this involves addition, and from the format you should see that it involves memory location 128.  We need two things to add.  Memory location 128 is one obvious operand.  The accumulator is also available. So the instruction adds the accumulator and memory location 128.  The final issue is where to put the result.  Fancier CPU's than Pip have more options, but in Pip all results go to the accumulator (except in the STOre instruction where a value is copied FROM the accumulator).  Hence the sum of the accumulator and memory location 128 are stored back into the accumulator.

Click STEP to check.

You can put the result of an addition or any other operation into memory:  It just takes an extra step.  Guess what the next instruction STO 129 does.  Click STEP and check.

Next is the HLT instruction, short for HALT.  Click STEP and the program stops (indicated on the screen by'--' in IP).  As a test click STEP again. You should see an error message in the bottom red region.

Click INIT.  This resets IP and ACC to 0.  You could step through the program again, or to see the result, just click RUN, and it goes (up to 100 steps) to the end.

In Python and other higher level languages we also store data in memory.  We refer to the data by name, not number.  That is easier still.  The assembler can also handle that.  Click the button DATA under labels. Every place we had address 128 before, we now have W, and every place we had address 129, we now have W.  In this case the machine code was disassembled (from machine code to assembler code).  The machine code did not include names, so the simulator fakes it, and always uses the names you see in the DATA section labels, W, X, Y, Z, T1-4.  (These are also the names that the Analytical Engine always uses.)  If you load a file with variable names, including ones different than W, X, ..., then pipGUI remembers them and uses them instead.  (The only restriction for the display is that they cannot be more than 8 characters long.)

More on the Simulator and Pip

Click HELP.  See the message at the bottom.  This gives context sensitive help.  First click on HELP again for a summary.  This shows all the help for the simulator operation.  Return to here if you have questions.  It covers the command buttons and a few other things.  

• Toward the bottom note Bottom Right Rectangle.  Old messages persist there.  If you get tired of one, click there.  
• If you are done with the help window you can minimize it, or bring the main window to the front (with Alt-Tab in Windows) or you can close the help window with normal window close button.
• The top line indicates if, after clicking HELP once, you click outside the other places mentioned and outside a text entry, you see the Pip Assembler Help.  Try that now.

The Analytical Engine has a more verbose listing of assembler instructionson page 251.

Class 23

Format of  my Pip assembler:

See arith.asm:

Human comments are allowed starting with a ';' (just like Python with '#', but # is already used in Pip assembler.)  In the example comments are a very direct translation to Python.  I use the symbolic data names the book allows.  

Load arith.asm into pipGUI.  You should see the code, minus comments.  

Loops and Symbolic Address Labels

The book sums from 1 to n on page 253, with high level code in Javascript.  The direct Python translaton is

sum = 0
i = 1
while i <= n:
    sum = sum + i
    i = i+1

In assembler it is easier to sum from n down to 1:

sum = 0
while n != 0:
    sum = sum + n
    n = n-1

For a loop you need to change the order of execution.  There are only the low level instructions JMP and JMZ. 

For example
    JMP 12  
means jump to the instruction at address 12.  More briefly, set IP to 12, rather than advancing IP by 2, like usual.

JMZ is a conditional jump
    JMZ 20
means jump to address 20 IF the accumulator is zero.  Otherwise go on to the next instruction normally.  In Pythonesque pseudocode:
    if acc == 0:
        IP = 20
    else:
        IP = IP + 2 # the usual case

Both these instructions are needed to translate the Python while loops above:  This is the first time the exact instruction numbers are important, so I show the addresses on the left.  My assembler allows numeric address labels followed by a colon:

Again we are writing numerical addresses rather than meaningful names.  This is also particularly awkward if you insert a new instruction and change a bunch of addresses.  Again the assembler can be smart enough to count and translate symbolic address labels (hough not allowed in the AE applet, the book mentions that symbolic labels for code addresses are also useful).  My version allows up to 8 character labels for both data and code addresses.  I have a variation of the book's example on page 253 in sum2n.asm:  

      LOD #4    ; n = 4  # high level for comparison       
      STO n                    
      LOD #0    ; sum = 0        
      STO sum                     
LOOP: LOD n     ; while n != 0:  
      JMZ DONE                  
      ADD sum   ;     sum = sum + n     
      STO sum                      
      LOD n     ;     n = n - 1    
      SUB #1                  
      STO n                     
      JMP LOOP                   
                  
      LOD sum   ; # for easy display - result in accumulator                  
DONE: HLT                       

PipGUI allows symbolic names (followed by a colon) to be placed before an instruction that is a jump target, and then the same name can be used in the JMP or JMZ instruction.  The while loop syntax is certainly clearer, but it an easily automated step in a compiler to switch to the low-level version, so you do not have to worry about it in a Python program!

Class 24

if x != 0:
     y = 3
else:
     y = 5
x = 2

Translation

Boolean Algebra, Truth Tables, and Digital Circuits

Transistors, Gates, and Circuits

Class 25

Finding a Boolean Expression for a truth table

Class 25

Class 26

Class 27

HW2:  on paper in class next Tuesday May 2.  Individual assignment!

Be sure to do the reading assignments in the Analytical Engine for the next class:  we will be having a class discussion.

Other circuits needed for a computer.

It has two main direct inputs d, the data value, and g, which is 1 as we shall see when the circuit should get the data.  Note the two lines feeding back: y, z.  Also z goes to the output q.  These are nand gates so x = (dg)'; z = (xy)'; y = (g'z)'  

If g is 1 and g' is 0, this simplifies to x = (d1)' = d' = 1; y = (0z)' = (0)' = 1, so z = (d'1)' = (d')' = d, and this is passed to q:  that means the value of d is transmitted to the output, however it changes.

If g is 0 and g' is 1, it is more complicated and we mut take the old value of y = q', z = q, into account.  x = (0d)' = 1, and d has no further effect.  y = (1q)' = q' which then circles around to make z = (1q')' = q, which is what it was before, so the loop maintains its old value, independent of how d is changed!  



It is not quite that simple if you look at latch.dat in the lab 7.1 applet.  If you try to run it (with lower input g = 1), you can switch the upper input d and have it behave as expected.  However if you change g to 0, you should see the circuit flash continuously:  That transition of g from 1 to 0 is a problem.  This is a timing issue.  Load latchWorks.dat.  See that two extra NOT gates are inserted.  In a static logical state they cancel each other out, but they change the timing when the signal from g alters and splits.  Now try running the applet with any sequence of input data, and it should work.   When the lower input (g) is 1, the output changes with the upper input (d).  When g is changed to 0, the last output is remembered, no matter what you do later to d.