Class 7 - Notes

Upcoming Schedule

Due now: Project 1
Before Wednesday, 10 February:
    Complete Udacity cs101 Lesson 3: How to Manage Data (Notes) and Lesson 3: Problem Set
Due on Monday, 15 February:
    Project 2 (will be posted in a few days)
Before Friday, 19 February:
    Udacity cs101 Lesson 4: Responding to Queries (Notes) and Lesson 4: Problem Set

Python Tutor

One great resource for understanding python code is Philip Guo’s Python Tutor. It lets you step through Python code forwards and backwards, and visualize what is going on.

For example, here is some crazy and useless code:


[Download (PPTX)]

Binary Numbers and Rules of Evaluation

Binary numbers are base 2, instead of the base 10 decimal numbers we commonly use. This means we can represent any number using only 0s and 1s, and the value of each Bit scales as a power of two (so instead of having a "ones" place, "tens" place, "hundreds" place, "thousands" place, we have a "ones" place", "twos" place, "fours" place, "eights" place, etc.). In Python, a number literal that starts with 0b is interpreted as a binary number:

>>> 0b10
>>> 0b101
>>> 0b1120
SyntaxError: invalid syntax

What is the value of 0b11111111 (as a decimal number)?

IntegerLiteral ::= BinLiteral
BinLiteral ::= 0bBinDigits
BinDigits ::= BinDigits BinDigit
BinDigits ::= BinDigit
BinDigit ::= 0
BinDigit ::= 1

Show how to derive 0b101 with this grammar starting with IntegerLiteral:

Provide semantic rules for the grammar that give the value (as a decimal number) for every BinaryLiteral:

(3) BinDigit ::= 0
        Value(BinDigit) =

(4) BinDigit ::= 1
        Value(BinDigit) =

(2) BinDigits ::= BinDigit
        Value(BinDigits) =

(1) BinDigits ::= BinDigits BinDigit
        Value(BinDigits) =

Test Grammar

Here is a simplified excerpt of the Test grammar from

Test ::= NotTest
NotTest ::= not NotTest
NotTest ::= Expression
Expression ::= True
Expression ::= False

From the grammar, determine which of the following are valid _Test_ expressions in Python:
0x11 < 0x011
True and False and True
0b11 < 0b100 > 0b101  
not not not not not not False
not not not
not False and True
You can try evaluating them in the Python interpreter to check your answers and see how they evaluate.

Develop rules of evaluation for the grammar above that matches how things are interpreted by the Python interpreter.

An MIT linguistics professor was lecturing his class the other day. "In English," he said, "a double negative forms a positive. However, in some languages, such as Russian, a double negative remains a negative. But there isn't a single language, not one, in which a double positive can express a negative."

A voice from the back of the room piped up, "Yeah, right."