• a PDF version of this text is called pv248.seminar.pdf and the source bundle is in directories 01 through 12, s1 through s3 and sol – use the ‘download as ZIP’ option in the sidebar to get entire directories in one go,
• log into aisa using ssh or putty, run pv248 update, then look under ~/pv248 (this chapter is in subdirectory 00).

• a2_grading – what is graded and how; what you need to pass,
• a3_practice – weekly ‘practice’ (preparatory) exercises,
• a4_sets – general guidelines that govern assignment sets,
• a5_exam – final exam (colloquium),
• a6_reviews – teacher and peer reviews,
• a7_cheating – don't.

1. seminars: work out short exercises, attend the seminar, participate actively,
2. sets: work out more challenging exercises over a longer period of time (up to a month),
3. code review: write elegant code and help others do the same.

• max 60pt seminars (4 weeks, 15 points each week):
  • 6pt practice exercise sanity (1pt/exercise),
  • 3pt practice exercise verity (.5pt/exercise),
  • 3pt seminar attendance,
  • 3pt activity in the seminar,
• max 60pt task sets (4 tasks, 15 points each),
• max 30pt reviews of tasks from previous block:
  • 15pt teacher review (depending on grade and task),
  • 15pt peer reviews.

1. ‘sanity’ which are enclosed (i.e. you can run them at your own leisure as you work on your solution) and
2. ‘verity’ which you cannot see, and will run only twice: Thursday 23:59 and then after the submission period closes on Saturday (again 23:59).

• The first set is called syntax and runs immediately after you submit. Only 2 checks are performed: the code can be loaded (no syntax errors) and it passes mypy (strictness depending on the task at hand).
• The next step is sanity and runs every 6 hours, starting at midnight (i.e. 0:00, 6:00, 12:00 and 18:00). Its main role is to check that your program meets basic semantic requirements, e.g. that it recognizes correct inputs and produces correctly formatted outputs. The ‘sanity’ test suite is for your information only and does not guarantee that your solution will be accepted. The ‘sanity’ test suite is only executed if you passed ‘syntax’.
• Finally the verity test suite covers most of the specified functionality and runs 3 times a week – Monday, Wednesday and Friday at 23:59, right after the submission deadline. If you pass the verity suite, the task is considered complete. The verity suite will not run unless the code passes ‘sanity’.

• set 1: 60 for correctness in block 1, 30 for reviews in block 2,
• set 2: 60 for correctness in block 2, 30 for reviews in block 3,
• set 3: 60 for correctness in block 3, 30 for reviews in block 4 (the exam one).

• 4 out of 6 exam exercises,
• 15+ points from reviews + 3 out of the 6 exam exercises.

1. you won't be able to consult anyone at the exam, for real (though this should have been the case during the semester too!),
2. no internet (and hence no googling and no stackoverflow), only this document (without the solution key) and the standard Python documentation.

• Python interpreter (obviously) along with mypy,
• a selection of text editors, VS Code and Thonny.

• A – very good code, easy to read, no major problems,
• B – not great, not terrible,
• C – you made the reviewer sad.

• for teacher review, you get 15, 7.5 or 0 points,
• for peer review, the reviewer gets 2 points for writing the review in the first place, and a variable part that affects both the reviewer and the author of the code:
  • A: the reviewer was so impressed that they give the entire variable part of the reward to the coder (0 to reviewer, 2 to coder),
  • B: mixed bag, the reward is split (0.5 to reviewer, 1 to coder),
  • C: the reviewer keeps everything as a compensation for the suffering they had to endure (1 to reviewer, 0 to coder).

• lose 1/2 of the points awarded for the affected work,
• lose 10 points in the block (i.e. you will need to have earned 70 on top of the points lost above),
• lose additional 10 points from the overall score (this means that, as a special exception, you can still fail even if you pass each block – you also need 180 or 240 points total depending on ending type to get a passing grade; with both 10-point penalties applied, you need 200 or 260 points to pass despite the cheating incident… on a second incident, this increases to 220 and 280 respectively, and so on).

1. list – using lists
2. tuple – lists, sort of, but immutable
3. dict – using dictionaries
4. str – using strings
5. fun – writing functions

1. fibfib – iterated Fibonacci sequence

1. rpn – Reverse Polish Notation with lists
2. image – compute the image of a given function
3. ts3esc – escaping magic character sequences
4. alchemy – transmute and mix inputs to reach a goal
5. chain – solving a word puzzle
6. cycles – a simple graph algorithm with dictionaries

1. permute – compute digit permutations of numbers
2. rfence – the rail fence transposition cipher
3. life – the game of life
4. breadth – statistics about a tree
5. radix – radix sorting of strings
6. bipartite – check whether an input graph is bipartite

1. (this section is empty for now)

• control – given the current situation, where does the program go next? which is the next statement or expression that will be executed?
• data – what are the values of variables, what are the results of expressions? what is the program going to output when it prints the ‘thing’ named x?

1. the behaviour of the program can directly or indirectly depend on the identity of a cell (e.g. by using an ‘are these cells the same’ operator, which is available in Python as foo is bar),
2. a value associated with a cell can change, i.e. the cell is mutable (in Python, this depends on the type of the cell: some are mutable, but some are immutable).

• name itself is an identifier, usually an alphanumeric string (give or take a few chars), that the programmer uses to refer to a particular value or cell (depending on which of the two is the more important concept in the given context),
• binding associates a name with a cell (or, again, a value): you can visualise this as an ‘arrow’ connecting a name to its cell,
• environment is the collection of names and their bindings active at any given point in the execution of the program.

• scope is a property of a given name and gives bounds on the validity of that name: which parts of the program can refer to this name (notably, the same string can be associated with two different names, but only one of them might be in scope at any given time).

for key, value in a_dict.items(): 
    a_list.append( key )

a_int = 3 
bar( a_int )

b_list = [ 3, 3, 3 ] 
baz( b_list )

• [ 3, 3, 3 ] – we can immediately rule this out based on the above,
• [ 2, 3, 3 ] – this would be consistent with all of the above,
• [ 1, 2, 1 ] – if int was actually handled differently from lists (spoiler: it isn't).

assert b_list == [ 2, 3, 3 ] 

assert id( x ) == id( x ) 
assert id( x ) != id( y )

z = x 
assert id( z ) == id( x )
z = y
assert id( z ) == id( y )

check_id( x, id( x ) ) 

• s[0][k] = fib(k) is the -th Fibonacci number,
• s[1][k] = fib(fib(k)) is the s[0][k]-th Fibonacci number,
• s[2][k] = fib³(k) is the s[0][s[1][k]]-th Fibonacci number,
• and so on.

def ts3_unescape( string ): 
    pass

• a list of available substances and their quantities,
• a list of desired substances and their quantities,
• a list of transmutation rules, where each is a 2-tuple:
  • first element is the list of required inputs,
  • the second element is the list of outputs,
  • both input and output is a tuple of an element and quantity.

• 3 chamomile, 4 water, 1 verbena, 2 valerian → relaxing concoction
• 7 ethanol → elixir of life
• 4 water, 2 mandrake, 2 valerian, nightshade → elixir of life
• 5 tea leaves → tea tree oil
• 2 primrose oil, 2 water, 1 tea tree oil → skin cleaning oil
• 1 iron, 1 carbon → steel
• 1 footprint → 1 carbon
• 6 ice → 5 water
• 3 steel → 1 cable
• 10 lead, philosopher stone, 2 unicorn hair → 10 gold

• { goose, dog, ethanol } → 3 (dog – goose – ethanol)
• { why, new, neural, moon } → 3 (moon – new – why)

def word_chain( words ): 
    pass

def permute_digits( n, b ): 
    pass

1. mypy – annotation basics
2. class – creating objects, with class
3. generic – polymorphic types and mypy
4. type – classes at runtime
5. anno – working with type annotations

1. geometry – define basic types for planar geometry

1. dsw – Day, Stout & Warren balance binary trees
2. ts3norm – template system 3, normalization
3. ts3render – template system 3, rendering into strings
4. bool – boolean expression trees
5. intersect – computing intersections in a plane
6. list – linked list with generic type annotations

1. json – recursive data types without gross hacks
2. rotate – traversing a tree using rotations
3. ts3bugs – more fun with template system 3
4. treap – randomized search trees
5. distance – shortest distance between two 2D objects
6. istree – finding cycles in object graphs

1. (this section is empty for now)

• a static type system can decide whether the value of a given expression (any value that it can take in the context of a fixed valid program) belongs to a given type,
• a dynamic type system cannot do this (in general), but can still answer this question for a particular value at runtime.

• a strong type system will always give a correct answer to the membership question,
• a weak type system may fail to give a correct answer.

1. Are types disjoint? If yes (each value belongs to exactly one type), the system is monomorphic. This is uncommon. Almost all systems allow some forms of polymorphism (values can belong to more than one type):
   • Is it true that, given two types and , that either or ? In these cases, we say that a type system has subtyping and means that is a subtype of (conversely, is a supertype of ).
   • Parametric polymorphism is technically more difficult, but intuitively, a function is parametrically polymorphic if a single definition (function body) admits infinitely many types that conform to some ‘type schema’.
   • Ad-hoc polymorphism (including ‘duck typing’): neither of the above is true. Rules vary from language to language.
2. Can users define their own types? (The universal answer here seems to be ‘yes’.) Given this is possible, how are new types constructed? There are two main categories:
   • algebraic data types: new types are created as products and disjoint sums of existing types (recursion is often allowed, where a type appears in its own definition),
   • inheritance: new types are created as subtypes of existing types.
3. Annotations: in which cases does the user need to explicitly mention types? Answers vary wildly depending on many factors:
   • every expression and variable (function parameter) needs annotations: an extreme that is basically never used in practice, but has some theoretical use (typed lambda calculus),
   • all variables/bindings (this extends to function parameters) need type annotations, and so do function return values, but types of expressions are inferred (languages like C or older versions of C++),
   • type information for local variables is not (usually) required, but function parameters and function return values require annotations (TypesSript and many other modern languages, newer revisions of C++, mypy in strict mode) – this is known as local inference,
   • only when values are explicitly constructed (literals usually carry an implicit type): see point 4 below.
4. There are 3 main categories of languages without (or with entirely optional) type annotations:
   • dynamic languages (traditional Python and many other high-level languages),
   • statically-typed languages with global inference (ML, traditional Haskell),
   • gradually-typed languages, where annotations are optional and they are checked statically when provided (to the degree that is possible: missing annotations are taken to mean that the type is dynamic, and all operations are considered valid on dynamic values) – the poster child of this category is mypy in non-strict mode.

1. functions are really just values, so the semantic difference isn't huge (they can naturally appear as sub-values of a value stored in a cell),
2. there are no cells without methods in Python anyway – even traditional ‘simple data’ like integers come with methods.

1. first and foremost, classes are types (mind you, not all types need to be classes, though in Python classes and types are almost the same thing) – that is, we can take a value (object) and decide whether it is an instance of a particular class (i.e. it is a member of the type to which the class corresponds),
2. what more, classes are structured types – they really are products, in the sense that an object has multiple fields or sub-values that all exist at the same time (as opposed to sum types); in this sense, classes are like tuples,
3. classes describe a protocol: the names of methods, their signatures, and so on, that all instances of the class conform to (this is not quite the case in Python, but we can ignore that for now),
4. classes provide an implementation of this protocol: method bodies appear in the definition of the class, and these bodies are shared by all instances:
   • this saves space, because there is no need to store each method in each instance,
   • it goes a long way toward consistency of behaviour: if a class only prescribes a protocol (which is only syntax), its instances are free to disagree on the behaviour – the semantics of a particular method,
5. classes are factories: they provide means to create new instances (i.e. to create new objects),
6. classes may be objects in their own right, with data and methods, like any other objects; they may even be instances of some class (in Python, they are instances of the class type… by default) – that class is then known as a metaclass and, you guessed it, we will get to that some other day.

1. since classes are types, and classes are also objects, that means that types are objects and that means that they exist at runtime – there is no type erasure in Python (well, we already knew this),
2. perhaps more interestingly, this means that we can do type-level reflection at runtime ‘for free’, simply by calling methods on the class,
3. since classes exist as objects, instances can keep a (runtime) reference (this is what happens in Python), and delegate to this object in case they do not have a method ‘of their own’ (this is how implementation sharing happens); this is also part of the reason why methods have an explicit self argument,
4. because function calls are an operator and operators are defined by objects, calling a class is a perfectly legitimate thing to do: this simply runs a specific method of the class – this is how objects are created (but it gets complicated and involves metaclasses; we are shelving this for now),
5. inheritance is also implemented as delegation (unfortunately, because Python supports unrestricted multiple inheritance, the algorithm for lookup is ungodly).

1. it has cast so that the programmer can (accidentally) lie about types,
2. it can get things wrong on its own, because it relies on data flow analysis to restrict union types. If you call g in the following program, it dies with a TypeError, but mypy --strict will accept it as correct:

   x: None | int = 1                     
   

    def f() -> None:
        global x
        x = None
   
    def g() -> None:
        if x is not None:
            f()
            print( x + 1 )

Certainly, this is not the outcome we have hoped for. Without
the backing of Python's strong dynamic type system, we could
have ended up in real hot water.

h( 'foo' )

    for i in range( 1, n + 1 ): 
        if n % i == 0:
            count += 1
    return count

def test_divcount() -> None: # demo 
    assert divisor_count( 5 )  == 2 # 1 and 5
    assert divisor_count( 6 )  == 4 # 1, 2, 3 and 6
    assert divisor_count( 12 ) == 6 # 1, 2, 3, 4, 6 and 12

    for i in range( 1, n + 1 ): 
        if n % i == 0:
            res.append( i )

    return res 

def test_divisors() -> None: # demo 
    assert divisors( 5 )  == [ 1, 5 ]
    assert divisors( 6 )  == [ 1, 2, 3, 6 ]
    assert divisors( 12 ) == [ 1, 2, 3, 4, 6, 12 ]

    if value is not None: 

def test_pushes() -> None: # demo 
    int_stack: list[ int ] = []
    str_stack: list[ str ] = []

    push_if_int( int_stack, 3 ) 
    push_if_int( int_stack, 'xoxo' )
    assert int_stack == [ 3 ]

    push_either( int_stack, str_stack, 'xo' ) 
    assert int_stack == [ 3 ]
    assert str_stack == [ 'xo' ]

    min_val: None | int = None 

    for v in values: 

    return min_val 

def test_classes(): # demo 

    assert base.value == 3 

    assert deriv.other == 4 

• equality (but not ordering),
• conversion to a string (i.e. values of type T can be printed), and somewhat surprisingly,
• hashing (you can make a set of T, even if set[ T ] wasn't the type you started with, or use T as a key in a dict).

    except TypeError: 
        pass

S = TypeVar( 'S', bound = Sized ) 

def double( value: S ) -> int: 
    return 2 * len( value )

def test_double() -> None: # demo 
    assert double( 'foo' ) == 6

class AThing: 
    def __init__( self ) -> None:
        self.an_attribute = 42
    def a_method( self, value: int ) -> bool:
        return True

def use_two_things( a_thing: R, b_thing: R ) -> R: 
    if a_thing.an_attribute > b_thing.an_attribute:
        return a_thing
    else:
        return b_thing

class ABox( Generic[ R ] ): 
    def __init__( self, a_thing: R ) -> None:
        self.a_thing = a_thing
    def open( self ) -> R:
        return self.a_thing

def test_a_thing() -> None: # demo 
    a_thing = AThing()
    b_thing = AThing()
    b_thing.an_attribute = 32

    a_box = ABox( a_thing ) 
    b_box : ABox[ AThing ] = ABox( b_thing )

    use_a_thing( a_thing ) 
    assert use_two_things( a_thing, b_thing ) is a_thing
    assert b_box.open() is b_thing

class Vector: 
    def __init__( self, x: float, y: float ) -> None:
        pass
    def length( self ) -> float:
        pass
    def dot( self, other: Vector ) -> float: # dot product
        pass
    def angle( self, other: Vector ) -> float: # in radians
        pass

def line_eq( l1: Line, l2: Line ) -> bool: 
    return dir_eq( l1.get_direction(), l2.get_direction() ) and \
           ( point_eq( l1.get_point(), l2.get_point() ) or
             dir_eq( l1.get_point() - l2.get_point(),
                 l1.get_direction() ) )

T = TypeVar( 'T', bound = SupportsLessThan ) 

def dsw( tree ): # add a type signature here 
    pass

class Template: 
    def __init__( self, text: str ) -> None:
        self.text = text

• Document → replace the ${…} with the text of the document; the pasted text is excluded from further processing,
• Template → the ${…} is replaced with the text of the template; occurrences of ${…} and #{…} within the pasted text are further processed.

class Leaf( Node ): 
    def __init__( self, value: bool ) -> None:
        self.truth_value = value

• append – add an item at the end
• join – concatenate 2 lists
• shift – remove an item from the front and return it
• empty – is the list empty?

    def rotate_left( self ): pass 
    def rotate_right( self ): pass

T = TypeVar( 'T', bound = SupportsLessThan ) 

• a search tree demands the value in the right child to be greater than the value in the root,
• a max heap demands that the value in both children be smaller than the root (and hence specifically in the right child).

1. insert a new node into the tree, based on the key alone, as with a standard binary search tree,
2. if this violates the heap property, rotate the newly inserted node toward the root, until the heap property is restored.

    def insert( self, val, prio ): pass 

def distance_point_line( a: Point, l: Line ) -> float: 
    pass

1. func – a few more features of function definitions
2. closure – the basic intuition and syntax
3. capture – mechanics of capturing variables

1. merge – combine items in a dictionary
2. dice – dicing and slicing lists
3. newton – finding roots with closures
4. sort – sorting and grouping with callbacks
5. file – make pure functions work with files
6. counter – keeping state

1. fold – folding lists
2. trees – folding trees
3. bisect – finding roots of general functions
4. each – traversing data structures
5. objects – a closure-based object system
6. inherit – the same, extended with simple inheritance

1. (nothing here yet)

1. an equivalent of a return address – where in the program to continue when the current function returns,
2. an environment (in the technical sense from chapter 1) – i.e. bindings of names to their values; this environment is realized as local bindings and a reference to the lexically enclosing scope, where the interpreter looks for names that aren't bound locally.

1. We do not want the captured environment to keep all local variables from the enclosing function alive. If the inner function (the closure) is returned or stored somewhere, that would tie the entire scope's lifetime to that return value. This would be expensive. However, it's not super important right now – we will get back to object lifetime in the week after the next.
2. Remember how = is a (re)binding operator? Now that is a problem.

def test_power_sum() -> None: # demo 
    assert power_sum( [ 1, 2 ] ) == 3
    assert power_sum( [ 1, 2 ], 2 ) == 5

def test_power_list() -> None: # demo 
    assert power_list( [ 1, 2 ], 2 ) == 5
    assert power_list( [ 1 ], 1 ) == 6

def make_foo() -> Callable[ [], list[ int ] ]: 
    def foo( l: list[ int ] = [] ) -> list[ int ]:
        l.append( 1 )
        return l
    return foo

def test_foo() -> None: # demo 

def test_make_dict() -> None: # demo 
    assert make_dict() == {}
    assert make_dict( foo = 3 ) == { 'foo': 3 }

1. with lexical scoping – variables are looked up syntactically, in the surrounding text (i.e. in a surrounding function, or a block, etc.) and not on the execution stack (that would be dynamic scope),
2. where functions are first class entities – that is, we can return them from other functions, bind them to local or global names, or accept them as parameters, etc.,
3. in which functions can be defined in local scopes (i.e. other than global/module and class scopes).

Writer = Callable[ [ int ], None ] 
Reader = Callable[ [], int ]

def test_median_logger() -> None: # demo 

    l_1.append( 1 ) 
    assert l_1 != l_2

K = TypeVar( 'K', bound = SupportsLessThan ) 
V = TypeVar( 'V' )
W = TypeVar( 'W' )

• a dict instance, in which some keys are deemed equivalent: the goal of merge_dict is to create a new dictionary, where all equivalent keys have been merged; keys which are not equivalent to anything else are left alone (though the single value is still passed through combine),
• a list of set instances, where each set describes one set of equivalent keys (the sets are pairwise disjoint), and finally,
• a function combine which takes a list of values (not a set, because we may care about duplicates): merge_dict will pass, for each set of equivalent keys, all the values corresponding to those keys into combine.

• the key is the smallest of the keys from the set which were actually present in the input dict,
• the value is the result of calling combine on the list of values associated with all the equivalent keys in the input dict.

• sort_by (with an order relation)
• group_by (with an equivalence relation)
• nub_by (likewise)

• a list of input files,
• a function get_name which maps input filenames to output filenames.
• a pure function fun which maps strings to strings,

• int → it is formatted as a decimal number and the resulting string replaces the ${…},
• list → the length of the list is formatted as if it was an int, and finally,
• dict → .default is appended to the path and the substitution is retried.

• a dict is rendered as a comma-separated (with a space) list of its values, after the keys are sorted alphabetically, where each value is rendered as a scalar,
• a list is likewise rendered as a comma-separated list of its values as scalars,
• everything else is an error: like before, treat this as a failed precondition, fail an assert, and leave it to someone else (or future you) to fix later.

• fold_len – get the length of a list,
• fold_pairs – create a ‘cons list’ made of pairs, such that [1, 2, 3] becomes (1, (2, (3, ()))),
• fold_rev – reverse the input list.

class Tree( Generic[ T ] ): 
    def __init__( self ) -> None:
        self.root : Optional[ Node[ T ] ] = None

• a ternary callback f: the first argument will be the value of the current node and the other two the folded values of the left and right child, respectively,
• the binary tree tree,
• an ‘initial’ value which is used whenever a child is missing (leaf nodes are folded using f( leaf_val, initial, initial)).

def fold( f, tree, initial ): pass 

• each_len – count the number of elements
• each_sum – count the sum of all the elements
• each_avg – compute the average of all elements
• each_median – likewise, but median instead of average

             (return the ⌊n/2⌋ element if there is no
              definite median, or None on an empty list)
  

def each_len( data ): pass 
def each_sum( data ): pass
def each_avg( data ): pass
def each_median( data ): pass

class Obj( Protocol ): 
    def __call__( self, __msg: str, *args: Any ) -> Any: ...

• traffic_light – a 2-state light, either ‘red’ or ‘green’, toggled by messages set_red, set_green and queried using is_green; the set_green method operates immediately (is_green right after set_green returns True) but set_red has a safety timeout: the light turns red, but is_green will only become False after 5 seconds to clear the crossing,
• button – takes a reference to two traffic lights; when pushed (message push), it requests that the first is turned green, then after a timeout (20s), requests it to go back to red; the second light vice-versa; it must ensure that under no circumstances the lights both return is_green at the same time.

1. (to be done)

1. flat – flattening nested data with generators
2. send – understanding full coroutines
3. getline – coroutine-based data streams
4. lexer – more streams
5. parser – coroutine-based lexer + parser combination
6. mbox – event-based (SAX-like) parsing with coroutines

1. iscan – iterator-based scanning
2. gscan – similar, but with generators
3. itree – iterating a binary tree
4. gtree – generators vs trees
5. dfs – walking graphs with coroutines
6. guided – A* search with coroutines

1. (nothing here yet)

1. iterables, which are objects that can be iterated – you could perhaps call them sequences, but iterable is more general (we will get to it),
2. to iterate [an iterable x], which means to create an iterator for x and then use it (usually until it is exhausted, but not necessarily).

1. check whether there are any items left in the sequence,
2. shift to the next item,
3. get the current item.

1. check whether the sequence is empty, and if so, raise StopIteration (yes, really),
2. grab the current item (the sequence is not empty, so there is one) so that it can be returned later,
3. shift the ‘finger’ to the next element (mutating the iterator),
4. return the value grabbed in step 2.

1. ‘one shot’ iterables, which are consumed by iterating over them, and hence can be iterated at most once (you could call them streams),
2. ‘restartable’ iterables, which can be iterated multiple times (these are what we normally think of as sequences).

1. functions can call any number of other functions; they may run forever or they eventually return to their caller once,
2. generators / semi-coroutines differ by the ability to return more than once, but again only to their caller – in this context, the ‘returning’ is called yielding because they can continue executing if resumed,
3. full coroutines can yield into arbitrary other coroutines – they are not restricted to keep returning into their ‘caller’.

1. call into the generator to obtain a value,
2. process the value,
3. resume the generator to obtain another value,
4. repeat until the generator is exhausted.

• a generator function is what looks like a regular function except that it uses a yield keyword; when called, a generator function returns immediately and the result is
• a generator, which is an object that represents a suspended coroutine – it is this generator object that can be iterated.

1. calling next resumes the coroutine,
2. if a yield is encountered, the coroutine is suspended and next returns the yielded value,
3. if a return is encountered, the coroutine is destroyed, its return value is wrapped in a StopIteration object and raised by next.

1. generators exist, obviously,
2. suspended generators are first-class objects,
3. generators actually return into the caller of next.

def test_gen2() -> None: # demo 
    y = gen2()
    assert y.__next__() == 1
    assert y.send( 24 ) == 2 # resumes execution of ‹y›
    print( "sent 24, got 2 back" )
    try: y.__next__() # generators do not return
    except StopIteration: print( "generator done" )

IDENT = 1 
KW = 2
NUM = 3

def stream_lexer( text_stream ): 
    pass

• the parser will get the lexer in the form of a generator object as an argument,
• the parser will yield individual statements,
• the parser will use next(lexer) to fetch a token when it needs one,
• the language has ‘include’ directives: the parser may need to instruct the lexer to switch to a different input file, which it'll do by send-ing it the name of that file.

def lexer( program ): 
    pass

def parser( lex ): 
    pass

• message start: the string 'message' followed by the content of the separator line with the From removed,
• header: yield the name of the field and the content; yield as soon as you read the first character of the next header field, or the body separator,
• body: yield a single string with the entire body in it, as soon as you encounter the end of the file

def parse_mbox( chars ): 
    pass

def prefixes( list_in ): 
    pass

def prefix_sum( list_in ): 
    pass

def suffixes( list_in ): 
    pass

def suffix_sum( list_in ): 
    pass

class Tree( Generic[ T ] ): 
    def __init__( self, value: T,
                  left:  Optional[ Tree[ T ] ] = None,
                  right: Optional[ Tree[ T ] ] = None ) -> None:
        self.left  = left
        self.right = right
        self.value = value
        self.parent : Optional[ Tree[ T ] ] = None

        if left is not None: 
            left.parent = self
        if right is not None:
            right.parent = self

class cor_iter( Generic[ T, S ] ): pass 

def bfs( graph: Graph[ T ], start : T ) -> Gen2[ T, int ]: 

    q : Queue[ T ] = Queue() 
    q.put( start )
    seen : set[ T ] = set()
    while not q.empty():
        item = q.get()
        for succ in graph[ item ]:
            yield succ
            if succ not in seen:
                q.put( succ )
            seen.add( succ )

def a_star( graph, start ): pass 

1. a_while – an interpreter for simple ‘while programs’,
2. b_splay – a self-balancing binary search tree,
3. c_same – a solver for ‘same game’,
4. d_shelter – a simple information system.

• one line = one statement (no exceptions),
• the program is a sequence of statements,
• blocks are delimited by indentation (1–5 spaces),
• there are following statement types:
  • assignment,
  • if statement,
  • while statement.

• constant assignments of the form name = number (where number is an integer written in decimal, and might be negative),
• 3-address code operations, of the form

  name₀ = operation name₁ name₂
  

• logic: and, or, nand (the result is always 0 or 1),
• relational (result is again 0 or 1):
  • lt, gt (less/greater than),
  • eq (equals),
  • leq and geq (less/greater or equal),
• arithmetic: add, sub, mul, div, mod.