CSCI 498C: Elements of Computing Systems

Winter/Spring 2010

Lectures

April 26: Lecture 38, Compliers: Parsing & Code Generation

You should be finished with Project 34 (ecs09) (or close to finishing).

Parsing code review and algorithm comparison.

What are some benefits and drawbacks to particular parsing strategies?

How have we sidestepped theories of formal languages and computational linguistics?

What is the analysis-synthesis paradigm underlying most compilers and why does it exist?

What are the main compilation tasks after tokenizing and parsing?

What is a floating point number and how do computers represent them?

Assignment: Reading 38, Quiz 38 and finish Project 34 (ecs10). Prepare Project 38 (ecs11).

April 23: No Class

You should be working on Project 34 (ecs09).

Assignment: Continue Project 34 (ecs10).

April 21: Lecture 37, Compliers: Parsing

You should be working on Project 34 (ecs09).

Are most programming languages context-dependent or context-independent? What about human languages?

What is the Jack grammar like?

How might you approach a general algorithm for parsing tokens into a parse tree?

What areas of the algorithm involve recursion?

Assignment: Continue Project 34 (ecs10).

April 19: Lecture 36, Game Code Review, Tokenization Tips

You should have finished Project 31 (ecs09) and be working on Project 34 (ecs10).

High-level language program (game) demonstrations & code review.

What are some strategies for tokenizing Jack code?

How might you create a parse tree from tokens?

Assignment: Continue Project 34 (ecs10) (parsing).

April 16: Lecture 35, Building a Compiler

You should have finished Project 31 (ecs09) and be working on Project 34 (ecs10).

Why should we first represent tokenization as XML?

What is parsing?

What are the differences between context-free and context-dependent grammars?

What are terminals and non-terminals?

What is a parse tree?

What is recursive-descent parsing?

What does it mean to be an LL(0) grammar?

What is the Jack grammar like?

Assignment: Continue Project 34 (ecs10) (tokenization).

April 14: Lecture 34, Real-World Software Projects, Compilers

You should be working on Project 31 (ecs09).

What is one of the biggest unsolved problems in managing software projects? (accurate estimates)

How does software become late? (one day at a time)

What are two primary options when faced with a deadline? (push the deadline or cut features)

What are the primary steps in typical compilation?

What is tokenization?

What is XML? What characters must be escaped and why? (<, >, etc.)

For the first phase of our project, what must the tokenizer do?

Assignment: Complete Project 31 (ecs09) and start Project 34 (ecs10).

April 12: Lecture 33, Jack, Operating Systems, Compiler Intro

You should be working on Project 31 (ecs09). Spec doc due today.

How should you go about writing a (non-trivial) program?

What are some idiosyncrasies of the Jack language?

What are BIOS, ROM, bootloaders, command processors and operating systems? What do they do?

What is the relationship between the Jack API and an operating system?

What is a compiler and how does it work?

What are the primary steps in typical compilation?

Assignment: Complete Project 31 (ecs09).

April 7: Lecture 32, Jack, Learning a New Language, Constraints & Creativity

You should have started Project 31 (ecs09).

How does the embracing of constraints lead to creative problem solving?

What common features and terminology do all modern computer languages share?

What are the Jack syntax and the Jack Standard Library like?

What should our git workflow be like for our project team?

Assignment: Continue Project 31 (ecs09) (hello world, screen specification).

April 5: Lecture 31, VM Implementation Review, Intro to Jack

You should have completed Project 28 (ecs08).

What problems are you having with the VM implementation?

What are some common pitfalls when implementing call and return?

VM implementation review.

How do you compile and run a Jack program?

Assignment: Reading 31, Quiz 31. Begin Project 31 (ecs09).

April 2: Lecture 30, VM Function Implementation

Your VM for Project 28 (ecs08) should pass the SimpleFunction test.

How might you implement the stack frame management?

How might you implement the VM's function call/return protocol?

What are some common pitfalls when implementing call and return?

Assignment: Finish Project 28 (ecs08), passing the FibonnaciElement and StaticTest tests.

March 31: Lecture 29, Program Flow & Function Implementation

Your VM for Project 28 (ecs08) should pass BasicLoop and FibonacciSeries tests.

What work must be done by your VM to handle label, goto and if-goto?

What does each stack frame need to store?

What do each of the VM function commands (function, call, return) and their parameters mean?

Assignment: Project 28 (ecs08), passing the SimpleFunction test.

March 29: Lecture 28, Program Flow & Functions

You should have finished Project 23 (ecs07).

How does flow control work?

How does function declaration, calling and returning work?

What tasks does a compiler need to handle in order to provide functions to you, the programmer?

Why/how does stack processing complement the function call/return protocol?

What is a stack frame? What do we store in one?

How do we manage the local state of callers and functions in the chain?

Where does the notion of main programs come from?

Assignment: Project 28 (ecs08), passing BasicLoop and FibonacciSeries tests.

March 26: Lecture 27, VM Lab

You should be working on Project 23 (ecs07).

Collaborative help w/ your VM implementation.

Assignment: You should be finishing Project 23 (ecs07), passing all tests.

March 24: Lecture 26, Virtual Machine, Virtual Memory Addresses [screencast]

You should be working on Project 23 (ecs07).

What do the built-in memory labels (SP, LCL, THIS, THAT, TEMP, etc) have to do with your VM translator?

What are the virtual memory segments, really?

What does it mean to pop temp 0, pop pointer 0, pop static 3, etc?

Assignment: You should be working on Project 23 (ecs07), passing BasicTest.tst.

March 22: Lecture 25, Virtual Machine

You should be working on Project 23 (ecs07).

What are some examples of VMs in the wild?

What are some ways of parsing the VM commands?

How might you "templatize" the assembly instructions for a particular VM command?

Review: push constant x, add, and other arithmetic commands.

Assignment: You should be working on Project 23 (ecs07), passing SimpleAdd.tst and StackTest.tst.

March 12: Lecture 24, Virtual Machine

You should have finished Project 23 (ecs07) milestone 1 & 2.

How does the Hack VM work?

What are the Hack VM commands like? What do they do?

How might the Hack VM commands translate to Hack Assembly instructions?

What are virtual memory address segments?

How might you control the stack pointer, in assembly?

How might you implement a push constant x command in assembly?

How might you implement the add command in assembly?

March 10: Lecture 23, Assembler Review, Virtual Machines

You should have read TECS chapter 7. Hand in Quiz 22.

What were some challenges with the assembler?

How do our assembly language and assembler compare to commercial implementations?

A word on top-down methodologies and the art of programming.

What is a virtual machine? Why include one in our computer stack?

What is a stack?

Introduction to the Hack virtual machine.

Assignment: Project 23 (ecs07).

March 8: No Class

You should have finished Reading 22 and Project 20 (ecs06).

Assignment: Finish Project 20 (ecs06), read TECS chapter 7.

March 5: Lecture 22, Assembler Lab

You should have made progress on Project 20 (ecs06).

Collaborative help w/ Assembler code (Java, Python, Ruby, Delphi).

Assignment: Reading 22, Quiz 22. Finish Project 20 (ecs06).

March 3: Lecture 21, Assembler Implementation

You should have finished Reading 20 and be working on Project 20 (ecs06). Hand in Quiz 20.

How might we implement the assembler?

Peer code review! Ugly babies!

Assignment: Continue Project 20 (ecs06).

March 1: Lecture 20, Character Symbols & ASCII; Creating an Assembler

You should have finished Project 17.

CPU implementation review

How are letters represented in binary?

What are ASCII, EBCDIC, and UTF8?

What is an assembler?

What are an assembler's two main tasks?

What is the Hack machine language specification?

What is a two-pass assembler?

Project overview

Assignment: Reading 20, Quiz 20. Begin Project 20 (ecs06).

Feb 26: Lecture 19, The Hack Computer Implementation Review

You should be working on Project 17.

How might you implement the CPU control logic?

How might you handle the JUMP logic in the CPU?

How might you implement Computer.hdl?

Assignment: Finish Project 17 (ecs05) and choose a scripting language for the next project.

Feb 24: Lecture 18, The Hack Computer

You should have finished Reading 17 and begun Project 17. Hand in Quiz 17.

How might you create an artistic assembly language 'demo' with Hack?

A comparison of the Intel 8080, Motorola 6800, modern processors, and the Hack instruction sets.

What is the Hack architecture like?

How does the Memory need to work? How might you build it?

How does the CPU need to work? How might you build it? (part 1)

Assignment: Finish Project 17 (ecs05).

Feb 22: Lecture 17, Semiconductors, Transistors, Integrated Circuits, Microprocessors

You should have finished Reading 16 and Project 15 (ecs04). Hand in Quiz 16.

Fill.asm, Mult.asm implementation review

A Brief History of Computing

What were some drawbacks of using vacuum tubes instead of relays?

What is a semiconductor?

What is a transistor and how does it work?

What is an integrated circuit?

Assignment: Reading 17, Quiz 17. Project 17 (ecs05).

Feb 19: Lecture 16, Hack Assembly Language

You should have finished Reading 15 and started Project 15 (ecs04). Hand in Quiz 15.

Where are we in the abstraction stack?

What is the design purpose of any assembly lanugage?

What are some general things every assembly language can do?

What is the von Neumann architecture?

How is the Hack platform designed?

How many registers do we have at our disposal?

What is an A-instruction?

What is a C-instrcution?

How are A and C instructions represented in machine code?

What other symbols are at our disposal in Hack assembly?

How do we interact with I/O devices like the screen and keyboard?

Project tips, assembly exercises.

Assignment: Reading 16, Quiz 16. Complete Project 15 (ecs04).

Feb 17: Lecture 15, Automation and Machine Language

You should be able to explain how to build parts of a computer from symbolic thought to flip-flops & memory.

How might you build an automated sequential adding machine?

How might you expand this machine's capabilities / instruction set?

What is an accumulator, really?

What is an opcode?

What is an instruction fetch? Instruction cycle?

What are the different components of an instruction?

How might you implement a loop with opcodes?

What is a CPU? What does it mean to have a 32-bit CPU?

What is machine language?

What is assembly language?

What is a computer?

Assignment: Reading 15, Quiz 15. Project 15 (ecs04).

Feb 15: No Class, Yay!

Feb 12: Lecture 14, Sequential Chips

You should have finished Reading 13 and Project 12 (ecs03). Hand in Quiz 13.

Implementation review: Bit, Register, RAMn, PC (counter).

The clock, synchronization and "computer speed."

Assignment: Think about everything we've built and be able to explain it. Have a long conversation with a caveman or stranded islander, explaining how everything works, from the bottom up.

Feb 10: Lecture 13, An Assemblage of Memory

You should have finished Reading 12. Hand in Quiz 12.

What is memory?

What is a 1-bit register? How might you create one?

How would you build an 8-bit register?

What does it mean to address memory?

How can you use MUX and DMUX to serve as address selectors?

How might you assemble larger memory units from smaller ones?

Assignment: Reading 13, Quiz 13. Complete Project 12 (ecs03).

Feb 8: Lecture 12, Feedback, Flip-Flops, Frequency Dividers & Counters

You should have finished Reading 11. Hand in Quiz 11.

How might you create a physical buzzer using a relay?

How do you create a simple oscillator?

How do you measure the period, cycle and frequency of an oscillator?

Who invented the flip-flop, and what is 'special' about this kind of circuit?

How might you build an RS latch?

What is the clock? What does it mean for a chip to be clocked?

How does a level-triggered RS flip-flop work?

How does a level-triggered D flip-flop work?

What's does all this out(t)=in(t-1) stuff mean?

How might you build a simple multi-number adding machine?

How does an edge-triggered D flip-flop work?

How might you build a binary counter?

Assignment: Reading 12, Quiz 12 and Project 12 (ecs03).

Feb 5: Lecture 11, Combinatorial Chips

You should have finished Project 9 (ecs02).

Implementation review: HalfAdder, FullAdder, Add16, Inc16, ALU.

Why does the hexadecimal number system conveniently complement bytes?

What is the hex shorthand for an 8, 16, 32, or 64-bit binary number?

Assignment: Reading 11 and Quiz 11.

Feb 3: Lecture 10, Binary Addition & Combinatorial Chips

You should have implemented everything in Project 9 except the ALU.

Using a two's complement system, can the adding machine in Code be used to display negative numbers?

How can we combine simple binary/Boolean operations in a two's complement system to accomplish higher-level operations?

How might you build an ALU?

Assignment: Review TECS 35-40 and complete ALU Worksheet (optional). Complete Project 9 (build the ALU).

Feb 1: Lecture 9, Binary Addition & Subtraction

You should have finished Reading 8. Hand in Quiz 8.

How might you create a binary adding machine?

What logic gates match the truth tables for sum and carry bits?

How might you construct a half adder? And a full adder?

What is ripple-carry and how does it affect adder performance?

What are three steps (using nine's complement) for subtracting without borrowing?

How can you quickly find the one's complement of a binary number?

How can we represent negative binary numbers?

How can you quickly find the two's complement of a binary number?

What must we beware of when using using a two's complement system?

Assignment: Begin Project 9 (ecs02). Review Reading 8 if necessary.

Jan 29: Lecture 8, Logic Gates

You should have finished Project 6 (ecs01).

What is a multiplexer? What is a demultiplexer?

Implementation review: Mux, DMux, Mux16, Mux4Way16, Mux8Way16, DMux4Way, DMux8Way.

Assignment: Reading 8, Quiz 8.

Jan 27: Lecture 7, Logic Gates

You should have finished Reading 6 and started Project 6 (ecs01). Hand in Quiz 6.

How can you distill the "canonical form" of a boolean function from a truth table?

What is one methodical way of implementing a chip from specification?

Implementation review: Not, And, Or, Xor, Not16, And16, Or16, Or8Way.

Assignment: Complete Project 6 (ecs01).

Jan 25: Lecture 6, Logic Gates

You should have finished Reading 5 and Project 5. Hand in Quiz 5.

What property do boolean expressions and switch "networks" share? (they can be simplified)

What is a logic gate?

What two things can a relay do? (amplify, switch)

What is a double-throw relay?

What is an OR, AND, NOR, NAND, inverter and buffer?

What is DeMorgan's law? How is it related to inverters, OR, AND, NOR and NAND gates?

Assignment: Reading 6, Quiz 6 and Project 6 (ecs01).

Jan 22: Lecture 5, Bits, Logic and Switches

You should have finished Reading 4 and Project 3. Hand in Quiz 4.

What is a bit?

How many bits do you need to represent N codes?

How do UPC bar codes work?

How might you represent Morse code or Braille as bits?

What is logic?

How does Boolean algebra work?

How might you implement a boolean test as an electric circuit?

Assignment: Reading 5, Quiz 5 and Project 5.

Jan 20: Lecture 4, Number Systems, Base-10 to Base-2

You should have finished Reading 3. Hand in Quiz 3. Continue Project 3.

What is a symbolic number system?

How do positional number systems work?

What's so great about ten?

What is meant by a numeric system's base?

How do you convert between binary and decimal?

What is special about binary numbers and switches?

Assignment: Reading 4, Quiz 4.

Jan 18: Lecture 3, Long Circuits & Telegraph Systems

You should have finished Reading 2 and Project 2. Hand in Quiz 2.

What is a common? What is a ground?

What problem did early telegraph installers face?

What was the first message sent via telegraph?

What is a relay and how does it work?

Assignment: Reading 3, Quiz 3 and Project 3.

Jan 15: Lecture 2, Braille, Electric Circuits

You should have finished Reading 1 and Project 1.

What preceded Braille? Who created the Braille code and when? Where did he get the idea?

Is Braille binary? Why?

What is an electric circuit? What does ήλεκτρον (electron) mean in Greek?

Vocab: anode, cathode, series, parallel, conductors, resistors, insulators.

What are voltage, amperes, resistance and watts?

Who is credited with the above terms, and how do you calculate them?

Project 2 demonstration.

Assignment: Reading 2, Quiz 2 and Project 2.

Jan 13: Lecture 1, Hello World (01001000 01100101 01101100 01101100 01101111 00100000 01010111 01101111 01110010 01101100 01100100)

You should be present for the first day of class (of course).

Introductions.

What is a computer? (to be continued)

What is symbolic thought? What is a code?

Who invented Morse code and when?

How might you construct a morse-to-alpha table?

Is Morse code binary? Why?

Assignment: Reading 1 and Project 1.

SYLLABUS | FORUM | CONTACT