Chapter 3:ProgrammingCS105: Great Insights in Computer ScienceThe Vector• We can build (or at least imagine!) lots of circuits.• We can even think about state machines that use circuits to do various things over time.• We’re headed towards using these ideas to create a programmable computer.• Hillis has us take a detour to talk about programming first.Logo in Python• Logo is a language invented to help people (kids?) learn to program. • Python is the language we’ve been using for examples in this class.• Hillis uses Logo for his examples in this chapter.• I’ll translate them into Python so it fits better with our other examples.Drawing Commandsforward(10)right(90)forward(10)New Commanddef square():forward(10)right(90)forward(10)right(90)forward(10)right(90)forward(10)Do It!square()Command Using The New Onereset()def window():square()square()square()square()window()reset()square is a subroutine of windowCommand With Parametersdef square(size):forward(size)right(90)forward(size)right(90)forward(size)right(90)forward(size)square(5)def design():square(5)right(10)design()reset()design()...never returnsRecursiondef design(number):square(5)right(10)if number == 1: returnelse: design(number-1)design(4)Proper Recursiondef tree(size):if size < 1: returnelse:forward(size)twoTrees(size/2.0)back(size)def twoTrees(size):left(45)tree(size)right(90)tree(size)left(45)left(90)tree(6)I Think That I Shall Never See...Recap• Using logic gates, we know how to do a bunch of things with bits:- test equality- if-then-else gate- select one bit from a set (universal gate)What Can We Do?• Lots: Any function of bits, we can specify with logic gates.• But, creating dedicated circuitry for every new problem is daunting and inefficient.• Would like a way of using a fixed set of circuits to act like any circuitry we might want.• We can use the state-machine idea to trade gates for time...• present von Neumann architectureConsider Reprogramming• Reprogramming the Christmas lights required that we create a bunch of circuits including the one above.• It’s got 2 “not” gates, 4 “and” gates, and 1 “or” gate wired in a particular pattern.• It would be nice if we didn’t have to play with gates and wires to change behavior.A= (A and not (B and C)) or (not A and (B and C))Concrete Example: Adding• We want to compute the sum of x and y (2-bit numbers). z (3 bits) is the answer and c (2 bits) is the carry.• z0 = (x0 and not y0) or (not x0 and y0)• c0 = (x0 and y0)10011+ 10101c1c0c0x1x0+y1y0z2z1z0Concrete Example: Adding• z1 = (x1 and not y1 and not c0) or (not x1 and y1 and not c0) or (not x1 and not y1 and c0) or (x1 and y1 and c0)• c1 = z2 = (x1 and y1 and not c0) or (x1 and not y1 and c0) or (not x1 and y1 and c0) or (x1 and y1 and c0)10011+ 10101c1c0c0x1x0+y1y0z2z1z0 Adding Bytes• Computing zi and ci from xi, yi, and ci-1 can be carried out with 6 ands, 3 ors, 4 nots.• The previous slide uses 16 ands, 6 ors, and 9 nots (not as good).• This operation is called a “full adder”.• By chaining together one full adder per bit, we can make a circuit that adds any number of bits (4, 8, 16, 32, 64, etc.).Hardware• So, any function we want to implement from bits to bits can be carried out by constructing the right circuit of and/or/nots.• Creating a circuit solves the problem “in hardware”.• The advantage of hardware solutions are that they are fast.• The disadvantage is that they are inflexible.Software• The lovely thing about a computer is that the hardware does not have to change for the computer to change its behavior.• A fixed set of circuits can actually change its behavior to represent any desired function!• Build one, reprogram into anything.• Disadvantage of the software approach: Can be much slower.Programming an AdderCircuit level:Instruction level:• H = A xor B = (A and not B) or (not A and B)• C1 = (A and B) or (C and H)• S = H xor C = (H and not C) or (not H and C)xorxor• ug, need to simplify further... no accumulatorSimple Statements• Still too many different statements.• Break complex statements down into a set of simple statements.• Instead of E = (H and not C) or (not H and C):• acc = not C• acc = acc and H• P = acc• acc = not H• acc = acc and C• acc = acc or P• E = accInstruction Set: 7 Bits• V in 0000...1111 (variables A- P)• 000V: acc = acc or V• 001V: acc = acc and V• 010V: acc = V• 011V: acc = not V• acc: special temporary variable• 100V: V = acc or V• 101V: V = acc and V• 110V: V = acc• 111V: V = not acc0000 A0001 B0010 C0011 D0100 E0101 F0110 G0111 H1000 I1001 J1010 K1011 L1100 M1101 N1110 O1111 PMemory• Need a place to store the various quantities we’re working with.• Main memory is like a giant filing cabinet, where each drawer is numbered consecutively and can store one value.• Need to be able to store and retrieve values.Memory Circuitaddressmem[0] ... mem[21] ... mem[31]Content of mem[21] if address = 21 (010101)Otherwise, FFFFFFFF[T, F, T, F, T]EQUAL5IFTHENELSE7[F, F, F, F, F, F, F]Similar circuits for the other 63 locations.64-loc-inputbitwise ORContent of mem[address] • We’ll have 32 memory locations, for instructions.• Each one has an 5-bit name (0-31) called its “address”.• Memory circuit takes the contents of memory (32 x 7 bits) and an address, 229 bits in all, & outputs the data stored at the corresponding address.Memory Lookupdef memlookup(add, mem): mem00 = mem[0] mem01 = ifthenelse7(equal5(intToByte( 1),add), mem[ 1], mem00) mem02 = ifthenelse7(equal5(intToByte( 2),add), mem[ 2], mem01) mem03 = ifthenelse7(equal5(intToByte( 3),add), mem[ 3], mem02) mem04 = ifthenelse7(equal5(intToByte( 4),add), mem[ 4], mem03) mem05 = ifthenelse7(equal5(intToByte( 5),add), mem[ 5], mem04) mem06 = ifthenelse7(equal5(intToByte( 6),add), mem[ 6], mem05) mem07 = ifthenelse7(equal5(intToByte( 7),add), mem[ 7], mem06) mem08 = ifthenelse7(equal5(intToByte( 8),add), mem[ 8], mem07) mem09 = ifthenelse7(equal5(intToByte( 9),add), mem[ 9], mem08) mem10 = ifthenelse7(equal5(intToByte(10),add), mem[10], mem09) mem11 = ifthenelse7(equal5(intToByte(11),add), mem[11], mem10) mem12 = ifthenelse7(equal5(intToByte(12),add), mem[12], mem11) mem13 = ifthenelse7(equal5(intToByte(13),add), mem[13], mem12) mem14