donkirkby

Wednesday, June 27, 2012

Live Coding in Python

I saw Bret Victor's Inventing on Principle video and thought, "Wow, I want those tools!" I couldn't find them, so I built my own version for Python. To try it yourself, visit donkirkby.github.com. To see how my version works, watch my demo video, or read on. I'll start with a trivial chunk of code where I assign a variable, and then modify it.

s = 'Hello'
s += ', World!'

That's easy to step through in your head and see that s is now 'Hello, World!' But why do I have to do it in my head when the computer could do it for me?

I add a special comment to show the live coding display on the left, and add another one to set it to a fixed width.

                                        

s = 'Hello'
s = 'Hello, World!'
# echo on                               
# echo width 40
s = 'Hello'
s += ', World!'

Let's do something more interesting and write a library function that does binary search for a value in a sorted array. The live coding will show us what's happening in our code so we don't have to hold it all in our heads.

                                        
# echo on                               
# echo width 40
def search(n, a):
    return -1

It's a bad search function that never finds anything, but let's see how it works when we call it.

                                        

n = 2 a = [1, 2, 4]
return -1

i = -1 
# echo on                               
# echo width 40
def search(n, a):
    return -1

i = search(2, [1, 2, 4])

You can see the input parameters at the start of the function, and the return value at the end.

We'll start looking for the value in the array, and the first place to look is the middle item.

                                        

n = 2 a = [1, 2, 4]
low = 0
high = 2
mid = 1

return 1


i = 1
# echo on                               
# echo width 40
def search(n, a):
    low = 0
    high = len(a) - 1
    mid = low + high / 2
    if n == a[mid]:
        return mid
    return -1

i = search(2, [1, 2, 4])

That was lucky! It was in the first place we looked, and you can see the calculations as it goes. You see an abstract formula in the code, like high = len(a) - 1, and you see the concrete result in the live coding display, like high = 2. However, a search function usually won't find the item we're searching for on the first try. Let's ask for an item earlier in the list and use a while loop to find it.

                                        

n = 1 a = [1, 2, 4]
low = 0
high = 2
         |
mid = 1  | mid = 0
v = 2    | v = 1
         |
         | return 0
         |
high = 0 |


i = 0
# echo on                               
# echo width 40
def search(n, a):
    low = 0
    high = len(a) - 1
    while True:
        mid = low + high / 2
        v = a[mid]:
        if n == v:
            return mid
        if n < v:
            high = mid - 1
    return -1

i = search(1, [1, 2, 4])

The loop runs twice, and each run adds a column to the display showing the calculations.

Now let's look for an item later in the list.

                                        

n = 4 a = [1, 2, 4]
low = 0
high = 2
        |
mid = 1 | mid = 3
v = 2   | IndexError: list index out of
        |
        | 
        |
        |
        |
low = 2 |


IndexError: list index out of range
# echo on                               
# echo width 40
def search(n, a):
    low = 0
    high = len(a) - 1
    while True:
        mid = low + high / 2
        v = a[mid]
        if n == v:
            return mid
        if n < v:
            high = mid - 1
        else:
            low = mid + 1
    return -1

i = search(4, [1, 2, 4])

Oops, I get an IndexError. Without the live coding display, I would just get a traceback that shows where the error happened, but not how it happened. Now, I can walk back from the error to see where things went wrong. mid is the index value, and it's calculated at the top of the loop. The two values that go into it are both 2, so they should average to 2. Oh, I need parentheses to calculate the average.

                                        

n = 4 a = [1, 2, 4]
low = 0
high = 2
        |
mid = 1 | mid = 2
v = 2   | v = 4
        |
        | return 2
        |
        |
        |
low = 2 |


i = 2
# echo on                               
# echo width 40
def search(n, a):
    low = 0
    high = len(a) - 1
    while True:
        mid = (low + high) / 2
        v = a[mid]
        if n == v:
            return mid
        if n < v:
            high = mid - 1
        else:
            low = mid + 1
    return -1

i = search(4, [1, 2, 4])

What happens if we try to find a value that's not in the list?

                                        

n = 3 a = [1, 2, 4]
low = 0
high = 2
        |          |         |         |
mid = 1 | mid = 2  | mid = 1 | mid = 1 |
v = 2   | v = 4    | v = 4   | v = 4   |
        |          |         |         |
        |          |         |         |
        |          |         |         |
        | high = 1 |         |         |
        |          |         |         |
low = 2 |          | low = 2 | low = 2 |


RuntimeError: live coding message limit
# echo on                               
# echo width 40
def search(n, a):
    low = 0
    high = len(a) - 1
    while True:
        mid = (low + high) / 2
        v = a[mid]
        if n == v:
            return mid
        if n < v:
            high = mid - 1
        else:
            low = mid + 1
    return -1

i = search(3, [1, 2, 4])

I guess that while True wasn't such a good idea, we're stuck in an infinite loop. If you want to see some of the later loop runs, you can add another special comment.

# echo scroll 30

From the third run on, the values in the loop don't change, so we probably want to exit from the second or third run. If you look at the end of the second run, you can see that high is lower than low. That means that we've searched all the way from both ends to meet in the middle, and it's time to give up.

                                        

n = 3 a = [1, 2, 4]
low = 0
high = 2
        |
mid = 1 | mid = 2
v = 2   | v = 4
        |
        |
        |
        | high = 1
        |
low = 2 |
return -1

i = -1
# echo on                               
# echo width 40
def search(n, a):
    low = 0
    high = len(a) - 1
    while low <= high:
        mid = (low + high) / 2
        v = a[mid]
        if n == v:
            return mid
        if n < v:
            high = mid - 1
        else:
            low = mid + 1
    return -1

i = search(3, [1, 2, 4])

At this point, I think I'm done. I can add a few entries and search for them to make sure everything is working. Also, if this were a real library module, I wouldn't want to execute a call at the end of the file, so I use a slight tweak of the standard library module pattern to only make the call when I've got the live coding display on.

if __name__ == '__live_coding__':
    i = search(3, [1, 2, 4])

Remember, you can try this tool yourself by visiting donkirkby.github.com. Help me test it and report your bugs. I'd also love to hear about any other projects working on the same kind of tools.

Labels:

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

Links to this post:

Create a Link

<< Home