Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

Friday, October 08, 2021

Converting an algorithm to use Pythons' new Structural Pattern Matching

 Python 3.10 is out and browsing what's new, I decided to convert one of my existing routines to use the new Structural Pattern Matching  statement  to try it out.

I used fgrep -c elif,  as part of a long unix command to find my algorithms with a lot of elif statements, and then chose my routine that evaluates Ackermann's function without explicit recursive function calls and with a lot of optimisations.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import deque

def ack_ix(m, n):
    "Paddy3118's iterative with optimisations on m"

    stack = deque([])
    stack.extend([m, n])

    while  len(stack) > 1:
        n, m = stack.pop(), stack.pop()

        if   m == 0:
            stack.append(n + 1)
        elif m == 1:
            stack.append(n + 2)
        elif m == 2:
            stack.append(2*n + 3)
        elif m == 3:
            stack.append(2**(n + 3) - 3)
        elif n == 0:
            stack.extend([m-1, 1])
        else:
            stack.extend([m-1, m, n-1])

    return stack[0]

Note that first n, then m is popped off the stack in the first line within the while loop.

Checking the match statement examples PEP-634, I create a match subject expression as a list of first the n then the m value and replace the if statement with case statements covering each of the if conditionals and also assigning to n and m as appropriate, to create:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def ack_im(m, n):
    "Paddy3118's iterative with optimisations on m using match of lists"

    stack = deque([])
    stack.extend([m, n])

    while  len(stack) > 1:
        match  [stack.pop(), stack.pop()]:
            case [n, 0]:
                stack.append(n + 1)
            case [n, 1]:
                stack.append(n + 2)
            case [n, 2]:
                stack.append(2*n + 3)
            case [n, 3]:
                stack.append(2**(n + 3) - 3)
            case [0, m]:
                stack.extend([m-1, 1])
            case [n, m]:
                stack.extend([m-1, m, n-1])

    return stack[0]

I had thought that it would be more natural to use tuples rather than lists for the subject expressions and case patterns as there are always only two things being matched, so created a third version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def ack_imt(m, n):
    "Paddy3118's iterative with optimisations on m using match of tuples"

    stack = deque([])
    stack.extend([m, n])

    while  len(stack) > 1:
        match  (stack.pop(), stack.pop()):
            case (n, 0):
                stack.append(n + 1)
            case (n, 1):
                stack.append(n + 2)
            case (n, 2):
                stack.append(2*n + 3)
            case (n, 3):
                stack.append(2**(n + 3) - 3)
            case (0, m):
                stack.extend([m-1, 1])
            case (n, m):
                stack.extend([m-1, m, n-1])

    return stack[0]


Checks/Timings

if __name__ == "__main__":
    import timeit
    assert (ix := ack_ix(4, 2)) == (im := ack_im(4, 2)) == (im := ack_imt(4, 2)), "Whoops!"
    print(f"Answer has {len(str(ix))} decimal digits")
    n = 100_000
    print(f"Timings for {n:_} repetitions of ack(4, 2)")
    for func in 'ack_ix ack_im ack_imt'.split():
        print(f"  {func+':':8}",
              timeit.timeit(f"{func}(4, 2)",
                            number=n,
                            setup=f"from __main__ import {func}"))

Running the code produces the following output:

Answer has 19729 decimal digits
Timings for 100_000 repetitions of ack(4, 2)
  ack_ix:  15.179398099950049
  ack_im:  15.368259999959264
  ack_imt: 15.472230200015474

 

Personal conclusion

There isn't much difference in runtime between if and match statements. This example only touches on the match statements capabilities, and so seems equally expressive as the if statement variant to me.

Wednesday, June 09, 2021

Python hack: Creating local variables in a comprehension

 Lets say you have data and want to create a list of the running sum of the data. For example if the data is [1,2,3] the running sum is [1, 3, 6]

Doing this outside a comprehension:

data = [1, 2, 3]

s = 0  # accumulator
sums = []

for x in data:
    s += x
    sums.append(s)
print(sums)  # [1, 3, 6]

Now this needs the accumulator s, initialised to zero, but comprehensions create their own local variables and the syntax does not allow you to write a simple assignment within it, and each item from the comprehension is stated first in its syntax .


The Hack

I'll just show the hack then work through it afterwards.

In [1]: data = [1, 2, 3]

In [2]: [s for s in [0] for x in data for s in [s + x]]
Out[2]: [1, 3, 6]


When converting a comprehension into  similar for statements then the output expression at the beginning of the comprehension is thought of as moving to inside the rightmost if or for section of the comprehension, so we get:

# Comprehension over many lines
[s                          # output expression
 for s in [0]               # For clauses (nested)
     for x in data
         for s in [s + x]]

# Is similar too...
for s in [0]:                   # For clauses (nested)
    for x in data:
        for s in [s + x]:
            print(s, end=' ')   # output expresion: 1 3 6


Explanation

In the comprehension, the initial

[s for s in [0] ...

says:

  • Individual items of the comprehension will be the expression s.
    (Remember the output expression is stated first , but from the environment at the right of the comprehension).
  • In the comprehensions local scope we use the one-entry outer for loop to set local s to zero.

The middle for loop of the comprehension just iterates over the data

The final for loop of the comprehension is special:

... for s in [s + x]]

s is set to itself plus the next item of data, x, using iteration over a one element list [s + x]:

  • For the first x, s was initialised to zero in the local scope via the outermost for.
  • s becomes 0 + data[0] in the inner loop and becomes the first output expression value, 1.
  • For the second iteration of the middle loop, x = data[1], so s then becomes 0 + data[0] + data[1]. The second evaluation of the the output expression for the comprehension, 3.
  • And so on...

Multiple local variables

 We can generalise this. Here we generate running sums, and running sums of the squares which needs two local variables s and s2:

In [3]: data = [1, 2, 3]

In [4]: [(s, s2) for s, s2 in [(0, 0)] for x in data for s, s2 in [(s + x, s2 + x**2)]]
Out[4]: [(1, 1), (3, 5), (6, 14)]

Summary

  1. You can satisfy the need for local variables in comprehensions.
  2. Its a hard to understand hack!
 

UPDATE: Added Walrus:

The walrus operator can now be used to give a more readable equivalent. 
This introduces the external initialised variable into the comprehension as well as  keeping the running sums.

In [5]: # We had:

In [6]: data = [1, 2, 3]

In [7]: [s for s in [0] for x in data for s in [s + x]]
Out[7]: [1, 3, 6]

In [9]: # With :=

In [10]: s = 0

In [11]: [s := (s + x) for x in data]
Out[11]: [1, 3, 6]

In [12]: 

In [13]: # We then had:

In [14]: del s

In [15]: [(s, s2) for s, s2 in [(0, 0)] for x in data for s, s2 in [(s + x, s2 + x**2)]]
Out[15]: [(1, 1), (3, 5), (6, 14)]

In [16]: # Which becomes:

In [17]: s = s2 = 0

In [18]: [(s := s + x, s2 := s2 + x**2) for x in data]
Out[18]: [(1, 1), (3, 5), (6, 14)]
(Those external variables s and s2 are updated to the last running sum).

Source

 This all came about because I re-read the "Whats new in Python 3.9" doc after upgrading Anaconda and came across code I couldn't initially fathom.

End.

Tuesday, April 27, 2021

Read PEP 636 on Structural Pattern Matching: The Tutorial

 Hi, I am just reading through PEP 636 -- Structural Pattern Matching: Tutorial. I'll give my views as I go along...

I really liked the choice of example - a text adventure. I am old enough to relate to it, and I guess a quick google would inform others.

Section "Matching sequences" serves as a gentle introduction to a match statement with one case

Subsequent sections expand on aspects of match: literals seem to match literally; names, (also called variables), when matched are also bind-to for use in the stastements, (plueral), of the case block.

skipping a few sections to something that is stated, that is nevertheless a departure from previous uses, that is the treatment of the underscore.

Underscores

In section "Adding a wildcard" underscore becomes more than just a valid name, as it is outside the match statement. 

Underscore always matches an object - just like any other identifier name; but does not get assigned the object it matches - like any other name.

Their example:

match command.split():
    case ["quit"]: ... # Code omitted for brevity
    case ["go", direction]: ...
    case ["drop", *objects]: ...
    ... # Other cases
    case _:
        print(f"Sorry, I couldn't understand {command!r}")

You cannot write the following

match command.split():
    case ["quit"]: ... # Code omitted for brevity
    case ["go", direction]: ...
    case ["drop", *objects]: ...
    ... # Other cases
    case _:
        print(f"Sorry, I couldn't understand {_!r}")

As _ is not assigned. Is it de-assigned in this block or will an earlier assignment outside the match statement still exist?


I am curious as to the decision for this extra non-assignment behaviour for underscore?

Testing Scope and Assignment

Lets expand on their example assigning names globally and trying different commands to match different case clauses:


_, direction, objects = "_ global", "direction global", "objects global"
print(f"{(_, direction, objects)=}")

command = "Nothing to match"
for command in ["quit", "quit me", "go south", "drop anvil arrows"]:
    print(f"\n## COMMAND IS: {command!r}\n")
    match command.split():
        case ["quit"]:
            print("quit")
            print(f"{(_, direction, objects)=}")
        case ["go", direction]:
            print("go", direction)
            print(f"{(_, direction, objects)=}")
        case ["drop", *objects]:
            print("drop", objects)
            print(f"{(_, direction, objects)=}")
        case _:
            print(f"Sorry, I couldn't understand {command!r}")
            print(f"{(_, direction, objects)=}")

Output:

xx

Python 3.10.0a7 (tags/v3.10.0a7:53e5529, Apr  6 2021, 10:20:47) [MSC v.1928 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>> 
======== RESTART: C:/Users/paddy/Google Drive/Code/python_3_10_match.py ========
(_, direction, objects)=('_ global', 'direction global', 'objects global')

## COMMAND IS: 'quit'

quit
(_, direction, objects)=('_ global', 'direction global', 'objects global')

## COMMAND IS: 'quit me'

Sorry, I couldn't understand 'quit me'
(_, direction, objects)=('_ global', 'direction global', 'objects global')

## COMMAND IS: 'go south'

go south
(_, direction, objects)=('_ global', 'south', 'objects global')

## COMMAND IS: 'drop anvil arrows'

drop ['anvil', 'arrows']
(_, direction, objects)=('_ global', 'south', ['anvil', 'arrows'])
>>> 

 Concentrating on underscore, we see that it always has the initially assigned global value.

Once direction is changed in the case statement, however, it is this global value that is changed and the next iteration of the loop that does not match to it shows its new changed value.


The special treatment of underscore seems odd to me? Why not assign to it like normal and have only the special treatment of checking that if it is the only pattern then that pattern is the last pattern?

As

Reading section "Capturing matched sub-patterns" I kind of thought ahead and was thinking "another use for the walrus operator", until the use of the as keyword revealed itself :-)

"as" reads well, I like it.


Type and attribute matching

Yay! Duck type friendly matching of attribute names.

Outside of a match statement a call of MyObject might require arguments, but it seems that MyObject() is valid in a match statement, regardless - something to remember.


END?

I'll stop here for now although there is more of the doc to read.





Tuesday, April 06, 2021

Wednesday, February 17, 2021

Longest Common Substring: An investigation using Python.

 (Best browsed on a larger than phone screen)

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive