CS1001 Notes: Python Memory Model, Collections, Grammars

Python Memory Model and Core Concepts

• Python Memory Model (Memory, Variables, Objects)

  • Objects are stored at specific memory locations; id(object1) == id(object2) iff object1 is object2. ext{id}( ext{object}1) = ext{id}( ext{object}2) \iff \ ext{object}1 ext{ is } ext{object}2}

  • Warning: For optimization reasons, two objects with non-overlapping lifetimes may have the same id. In two different executions, the same object may be assigned a different id. Platform dependent.

  • Variables are temporary names for memory addresses.

  • Memory address does not imply value, and value does not imply memory address (except for some optimization cases with small integers and some strings).

  • Assignment of one variable to another merely creates another reference to the object; no new object is created.

  • Mutable objects (e.g., lists) allow changing their inner components without changing the memory location of the containing object.

  • Reference: Python Tutor (visualization) — https://www.pythontutor.com/visualize.html#mode=edit

• Function parameter passing in Python

  • In Python, the address of the actual parameter is passed to the corresponding formal parameter in the function.

  • When you assign to a formal parameter inside the function, you create a new object and rebind the formal parameter to it. This change is not visible to the caller.

  • If the function mutates one of its parameters, the address in the function remains the same, so mutation can affect the caller’s environment (a side effect).

  • Summary: Python uses pass-by-object-reference (often described as pass-by-assignment). See also the distinction between binding vs mutation.

• Information Flow and Side Effects of functions

  • There are three ways to return information from a function back to its caller:

  1. Return value(s) (the safest and easiest to understand).

  2. Mutating a mutable formal parameter (more error-prone and harder to debug).

  3. Changing global variables (harder to understand and debug).

• Comic Relief slides

  • Notes that slides include invited submissions for slide images during the semester (e.g., various captions and humor). Example: acknowledgement captions and cartoon-style reminders.

• More Collections in Python

  • Recall: collections (containers) can contain other elements; common types seen so far include: str, list, range.

  • There are additional collections classified by two properties: order and mutability.

  • Ordered (sequence) vs unordered types; Mutable vs Immutable examples:

  • Mutable ordered: list, e.g.,

    • Example: [1, 2, 3]

  • Unordered: set, dict

    • Examples: {1, 2, 3} and {1: "a", 2: "b", 3: "c"}

  • Immutable: str, range, tuple

    • Examples: "123", range(1, 4), (1, 2, 3)

• Tuples

  • Tuple vs list: Tuples are enclosed in regular brackets (), lists in square brackets [].

  • Tuples are immutable; attempting to mutate raises a TypeError.

  • Examples:

    • a = (2,3,4)

    • b = [2,3,4]

    • type(a) , type(b)

    • [a[i] == b[i] for i in range(3)] -> [True, True, True]

    • a == b -> False

    • b[0] = 99 # works, mutates b

    • a[0] = 99 # raises TypeError: 'tuple' object does not support item assignment

• Using tuples for function return values

  • A function can return a single value, but you can return a tuple to convey multiple values.

  • Example:

def mydivmod(a, b):
    """ return quotient and remainder """
    return a // b, a % b

• Demonstration:

  • >>> mydivmod(21, 5)

  • (4, 1)

  • >>> type(mydivmod(21, 5))

  • 
    

  • >>> mydivmod(21, 5)[0]

  • 4

• Simultaneous assignment (shortcut):

q, r = mydivmod(21, 5)
print(q, r)  # 4 1

• Takeaway: The function syntactically returns a single value of type tuple, enabling multiple assignment semantics.

  • Sets (type set)

• Python’s set closely resembles the mathematical notion of a set:

  • No repetitions, no guaranteed order (though in practice insertion order is not relied upon historically).

  • Set members must be immutable (we may discuss mutability of the set container itself later).

• Examples:

  • >>> s = {1, 2, 3, "a"}

  • >>> type(s)

  • >>> s.add(4) # in-place modification, returns None

  • >>> s # {1, 2, 3, 4, 'a'}

  • >>> s.add("4") # adding a string

  • >>> s # {1, 2, 3, 4, '4', 'a'}

  • >>> s.intersection({1, 11, 111}) # {1}

  • >>> s.union({1, 11, 111}) # {1, 2, 3, 4, '4', 11, 111, 'a'}

• Tip: Explore more set operations as the course progresses.

  • Dictionaries (type dict)

• Python’s dicts contain key:value pairs (mappings). Keys cannot repeat and are immutable (thus form a set). The dict itself is mutable.

• Examples:

  • >>> d = {"France":"Europe", "Germany":"Europe", "Japan":"Asia"}

  • >>> type(d)

  • >>> d # order not necessarily as initialized (historically)

  • {'Germany':'Europe', 'France':'Europe', 'Japan':'Asia'}

  • >>> d["Japan"]

  • 'Asia'

  • >>> d["Asia"] # KeyError: 'Asia'

  • >>> d["Israel"] = "Asia"

  • >>> d["Israel"]

  • 'Asia'

  • Dictionaries (type dict) – iteration and order

• Example:

>>> d = {"France":"Europe", "Germany":"Europe", "Japan":"Asia"}
>>> for key in d:
...     print(key, "is in", d[key])
Germany is in Europe
France is in Europe
Japan is in Asia

• Note: order of elements is not necessarily the same as initialization. This changed in Python 3.7: insertion order is guaranteed, but relying on a specific order is not recommended because it is version-dependent. Dicts and sets are iterable.

  • Dictionaries (type dict) – Example: letter count

• Task: compute the number of occurrences of each letter in a given text.

• Input: text (type string)

• Output: pairs letter:count (type dict)

def char_count(text):
    d = {}
    for ch in text:
        if ch in d:
            d[ch] += 1
        else:
            d[ch] = 1
    return d

• Advantages of dict and set over ordered collections

  • Hash-table-based lookups provide faster membership checks that do not depend on the collection size (on average).

  • Example:

s = {1, 2, 3, "a"}
2 in s     # True
"2" in s   # False

• For a larger list, membership checks grow with size:

lst = [1, 2, 3, "a"]
2 in lst     # True (linear search hypothesis)
"2" in lst # False

• In contrast, a larger set tends to require roughly the same time for membership checks as a smaller set.

  • Before we Move Beyond Python

• We are almost done with the introductory Python part of the course.

• The following slides contain material about grammars and related topics that may not be taught this semester, with one exception: a slide about expressions in Python.

• All slides are provided for reference.

  • Grammars, Syntax vs. Semantics

• Syntax: the form of a valid program. Every language has its own syntax. Example: print("abc") is valid; print("abc)" is not.

• Syntax can be defined by a grammar. The interpreter (e.g., IDLE) verifies that the program conforms to the grammar before evaluation.

• Semantics: the meaning of the program and the expected results of execution. Not easy to formalize in this course; touched upon in compilation or software verification courses.

  • Specifying a Syntax

• A grammar is formally defined by:

  • The alphabet of the language.

  • A set of variables representing types of phrases or clauses.

  • The set of rules (productions).

• We say a grammar yields a string if we can derive the string using the rules until there are no variables left.

  • Grammar (formal structure)

• A grammar is defined by:

  • The alphabet of the language.

  • A set of variables representing types of phrases or clauses.

  • The set of rules (productions).

• If we can derive a string using the rules, the grammar yields that string.

  • Example #1

• Grammar:

  • →

  • →

  • → boy | girl | cat

  • → a | the

  • → touches | likes | sees

• Which strings can be formed?

  • "a girl likes" ✓

  • "the boy sees" ✓

  • "the girl likes the cat" ✗

  • Example #2

• Grammar:

  • ⟨S⟩ → a⟨S⟩a | b⟨S⟩b | c

• Which strings can be formed?

  • ⟨S⟩ → a⟨S⟩a → aa⟨S⟩aa → aab⟨S⟩baa → aabcbaa

• Also: ⟨S⟩ → c

• Question: can you generalize which strings can be formed with this grammar?

  • Parse Tree

• Parsing is the process of analyzing the syntactic structure of a string.

• A parse tree (syntax tree) represents this structure; example for the string "a girl likes":

<SENTENCE>
  <NP>
    <ARTICLE>
    <NOUN>
  a   girl   likes

• Python’s Grammar

  • The full Python grammar is defined in the language specification; you are not required to understand all of it.

  • Python code is parsed according to this grammar.

• Statements in Python

  • Can be either simple or compound.

  • Compound statements include: if, while, for, and many more (with blocks).

  • Simple statements include: expressions (e.g., 3+4**2), assignments (e.g., res = 400), return, break, etc.

• Sketch of Statements in Python

  • Simple statements: expressions, assignment, return, break, …

  • Compound statements: if, while, for, …

• Expressions

  • An expression is a statement that has a value (i.e., can be on the right-hand side of an assignment).

  • Examples listed:

  • 1

  • 3 + 2

  • x (assuming x has been defined)

  • x > y

  • "A" in "Amir"

  • sum([1,2,3,4,5])

  • [x**2 for x in [1,2,3] if x-1 != 0]

  • None

  • sum (as a function name, returning a value)

  • "equal" if x == 4 else "not equal" (conditional expression)

  • lambda x,y: x + y (lambda expressions)

  • res = Conditional expression

• Break in loop (comic slide)

  • References to a humorous mock-up about breaking out of loops; part of the course’s light content.

• Comic Relief slides (final)

  • Additional captions and humor; included for engagement.

• Random notes

  • The transcript includes several slides intended for humor and student engagement; the substantive sections cover memory model, collections, grammars, and expressions.

If you want a condensed quick-start version, I can produce a shorter cheat-sheet version as well, focusing on the core concepts and typical code patterns used in CS1001.