Week 4

The problems we studied in lecture while talking about recursion reminded me of something I tried to do last year around this time. I wanted to make a little program that evaluates the validity of modern symbolic logic arguments for the user. A version of the program that I translated to Javascript is here. (It mostly works, but it doesn’t do predicate logic and its order of operations sometimes needs brackets to be correct.)

One of the problems in establishing validity in Modern Symbolic Logic is the idea of the hypothetical. “Valid” means that if all the premises are true, then the conclusion must be true, and “invalid” means that all the premises can be true and yet the conclusion be false. In this wording, it’s hard to tell how we check that. So in MSL these situations are translated into “worlds” or “models”, each of which is an arrangement of truth values across the irreducible names involved in the argument. Then, “valid” means that in every world in which the premises are true, the conclusion is also true, and “invalid” means that there is at least one world in which the premises are true and the conclusion is false.

Well, that’s good news for my program, because that starts to sound less like a thought experiment and more like something a computer can do. So how do we check the criteria? First, we need to generate all the possible worlds. When humans want to do this, they can make a truth table. A glance at that image should remind you of our first recursion problem. We want to generate every possible assignment of binary values to certain names that form the basis of any proposition in MSL. That’s the problem we’ll look at here.

Typically, names are one-character strings, starting at ‘P’. So what we want is:

>>> get_worlds(['P'])
[{'P': True}, {'P': False}]

>>> get_worlds(['P', 'Q'])
[{'Q': True, 'P': True}, {'Q': False, 'P': True}, {'Q': True, 'P': False}, {'Q': False, 'P': False}]

If we have only one name, ‘P’, there are only two possible models: one where it’s True and one where it’s False. If we have two names we have 2**2 models. Etc.

So here was my attempt last January. I’ll let you look at it and figure out how through the commenting. (P.S. Because we’re using dictionaries, it’s important to note that the program guarantees that each element in names is unique.)

def get_worlds(names):
    '''
    names is a list of immutable objects. Return a list of dictionaries of all
    possible different worlds. A world is an assignment of True or False to
    each name.
    '''
    
    # Set up the worlds list. Prepare it by filling it with empty dictionaries.
    
    worlds = []
    rows = 2 ** len(names)
    for i in range(rows):
        worlds.append({})
    
    # Iterate through the names. Each name is put in all the worlds before
    # moving on to the next one. The value it is assigned alternates every x,
    # where x is determined by how many names there are and this one's position.
    
    for pos in range(len(names)):
        name = names[pos]
        alternate = rows / (2 ** (pos + 1))
        
        row_outer = 0
        value = True
        
        # Start a deployment round (a range through all the worlds).
        
        while row_outer < rows:
            
            # Start an alternation round (an inner segment of the whole round).
                
            row_inner = row_outer
            
            # Iterate through it, deploying value until it's time to alternate.
            
            while row_inner &lt; row_outer + alternate:
                worlds[row_inner][name] = value
                row_inner += 1
            
            # Update our position in the outer round, and reverse the value.
            
            row_outer = row_inner
            value = not value
            
    return worlds

Okay, looks complicated but plausible. And indeed, if you run it, it works.

It’s not at all elegant, though. Its method is charmingly similar to how a human would fill out a truth table: write in all the rows and then write in the values row by row for each column. In code, it just looks silly. Surely we can improve on it.

So! Here’s the point of this blog post. Based on what we’re learning this week, why don’t we try rewriting it so that it’s cleaner and benefits from recursion?

Step one, as always, is to establish our base case: a list with no names. This should turn up a list with an empty dictionary.

def get_worlds_2(names):
    if len(names) == 0:
        return [{}]

Next, let’s figure out how to get from n-1 to n. Here they are again:

>>> get_worlds(['P'])
[{'P': True}, {'P': False}]

>>> get_worlds(['P', 'Q'])
[{'Q': True, 'P': True}, {'Q': False, 'P': True}, {'Q': True, 'P': False}, {'Q': False, 'P': False}]

The answer seems to be that to find get_worlds([‘P’, ‘Q’], we…

(1) Take the list returned by get_worlds([‘P’])
(2) Make a copy of each dictionary and add a key ‘Q’ and value True
(3) Make another copy of each one and add a key ‘Q’ and value False

So here’s how we might do that basic operation:

for world in smaller:
    plus_True = world.copy()
    plus_False = world.copy()
        
    plus_True.update({names[len(names)-1]: True})
    plus_False.update({names[len(names)-1]: False})

First we copy the world dictionary twice. Then we update* each copy with a new key:value pair, taking the last item in names for our key and linking it to one of each boolean value. Great!

So let’s put it all together with the proper recursion structure:

def get_worlds_2(names):
    
    if names == []:
        return [{}]
    
    smaller = get_worlds_2(names[:len(names)-1])
    bigger = []
    
    for world in smaller:
        plus_True = world.copy()
        plus_False = world.copy()
        
        plus_True.update({names[len(names)-1]: True})
        plus_False.update({names[len(names)-1]: False})
        
        bigger.append(plus_True)
        bigger.append(plus_False)
    
    return bigger

Yay! A much cleaner function! And if we do our tests on it, we’ll find that it works just as well.

Thank you, recursion! Surprisingly straightforward! And thank you, zingarod, for teaching it to us!

*Concatenating dictionaries in Python is not as easy as using +. One reason that could be problematic is if the keys are not unique. This thread should clarify why I chose dict.update().

Side note: queue solution

Thought I might as well mention my solution to the queue efficiency problem. My idea was basically to not actually remove anything from the list (the implementation we’ve seen for this ADT so far). Instead, simply start a counter at 0 and make the dequeue method (a) return the item at the index of the counter, and (b) increment the counter by 1. Now none of the remaining elements need to have their indexes shifted, which is what took so awfully long in this implementation.

The issue is that your queue could get to be massive—particularly if you have hundreds of thousands of elements to enqueue and dequeue, like zingarod showed us in lecture! I just assume that in a real computing environment, you could check CPU load and quietly clear the excess items (the cache?) in the background whenever the computer has the time and processing power.

Week 3 (late-ish)

When we talked about try…except, I thought back to my personal project last semester after taking 108: Coursegrade. (If you’re going to download it, avoid the Mac application. It doesn’t work. And I rarely have access to a Mac, which means I can’t compile it right now. Just grab the source… but hey, it is a good program, I promise!)

I wanted to do two things when allowing people to enter various inputs into the program: it had to be a valid input and it had to be sorted properly. Regarding the sorting, for example, I wanted to let people enter the grade they received on an assignment, and rather than bothering them with having to choose “percent” or “fraction”, I wanted the program to figure it out for them. The program takes several different inputs (the functions I have for checking input are valid_number, valid_letter, valid_fraction, and valid_string),

I looked up how I could easily handle a lot of different requirements. Boy, handling valid input is complicated. At first I had a ton of if…else checks, but it got so complicated that I couldn’t even keep track of all the different things that could go wrong with someone entering a fraction string. Then I found a reference to try…except somewhere on Stack Overflow and decided it could help me.

So, without further ado, here are some excerpts in case other learners can benefit.

First, the very simple valid_number:

def valid_number(s):

    try:
        number = float(s)
        return True
    except:
        return False

The functionality is clear: it’s going to try to float the input. If it’s possible to convert it to a float, this is a valid number. If that attempt raised an error, it’s not.

Here’s the second example. I thought this was a slightly more innovative use of try…except. The background is that the program saves your data in a text file. This data consists of profiles, which primarily contain courses, which primarily contain assignments, which primarily contain weights and grades. These are all classes. Whenever you open up the program, it looks for a save file, reads everything, and instantiates a single object: a class that (for some strange reason) I called “Runtime”. Then it calls the program’s all-encapsulating function, main_menu, passing it this object as a parameter.

Now, when do we save the data? I thought of including a button on every menu called “save”, but decided against it. Instead, I decided to basically save everything you do and make it unavoidable (for simplicity’s sake and to avoid you forgetting to save). I’ll probably change this if I make a new version, but the result was a “Save & Exit” button. So the question was: how do I make this implementation as simple and elegant as possible? After all, my program is structured as a set of nested menu functions running on while loops until you close them. I’d have to use break multiple times to get out quickly.

Well, here was my solution, four of the only five lines in __main__:

try:
    main_menu(runtime)
except(SystemExit):
    file_save(FILENAME, runtime)

I saw that there was an exception class called SystemExit, which seems to be called only when you intentionally call the function exit() from the sys module. Since I could control exactly when this “error” was raised, I was able to use it strategically. The whole program is run in a try block. Each “Save & Exit” button has only one effect: it calls exit(). (If I had learned what we learned this week, I would have known I could just use a raise statement.) The SystemExit exception that’s raised isn’t caught by any of the handlers on the way up, so it gets handled by the except block here, which will take this as a cue to save the file. Note that no other errors will be caught, and therefore no other errors will save the file. Normally, if an unexpected error is encountered, the data is going to be messed up in some way, so I only wanted it to be saved when everything’s going well and the user intentionally saves and quits.

So there you go! Two easy uses of try…except, one where we’re catching an expected error and one where we raise it ourselves as a way of backing our way out of a lot of nested functions in a quick and controlled way. Hope this has been useful!

Week 2a

Well, hello, and welcome to this blogulation. Or slog. Whatever you want to call it. I like to call it “Berkey Colortran”, named for a camera or light or something I saw in the lecture hall. They might hunt me down and litigate my butt for taking the name, but frankly I doubt it. I’m just a kid with a dream, you know? Anyway, here I’ll be reflecting dutifully on my learnings in the course whose code you see at the top of the page.

Yesterday zingarod (IPA: /ˈzɪŋgəˌrɒd/ (yes, that’s how I will refer to him)) informed us of the existence of Exercise 1. I made a note on my phone and thought, “I am so on that tonight.” But when I got home my mind had selectively forgotten the fact and I played DotA 2 instead. When I woke up this morning I realized my grave error and decided to do it this evening. Then a friend cancelled our afternoon piano lesson, so I did it in the afternoon.

The handout says that part a is really only review from 108, but the whole thing was only review from 108. I’d actually say that the chance to use the only new-ish skill we’ve learned so far — that of object-oriented analysis based on a real-world description — was circumvented by the handout’s listing of the actual method names we were to use. What can I say, though? It’s only 2% of the grade.

I had a bit of trouble with the square_root dealie at first. I was like, “The difference between the guesses? Hm hm. So which do I subtract from which?” The progression from this_guess to next_guess not corresponding exactly to greater or lesser value confused me. I did some practical test cases that didn’t clarify things and then I realized I was being dumb and decided to just use the absolute value. Then I forgot to update this_guess for a while, which made the iterations kind of, y’know, pointless. I was so confused that I read the start of the Wikipedia page on Newton’s Method in case I’d misunderstood it. Eventually I caught it. These ridiculous oversights are always what get me…

Anyway, the algorithm itself wasn’t hard. I wondered if I should use a while loop or a for loop and then I realized that since I know exactly how many times I want it to run, I’ll just run a for loop. I was also reminded of the loathsome syntax of loops in Javascript, which I was trying to figure out over the summer. Python is so… clean. And delicious.

The second part was okay too. When zingarod wrote in his handout that we could “probably omit” the __init__ method, I thought, “Trouble’s on the horizon, boys.” So I made an __init__ method just to be safe. But then I had to admit to myself that it didn’t have anything to do, so I just wrote “pass”. Later zingarod confirmed my curiosity that the result is in fact the exact same (except, of course, that you could require parameters if you define it). But my fears were assuaged.

I don’t know, there’s not a lot to say about it. I put in the wrong slash for a long time with my newline. See what I mean about ridiculous oversights? I also decided once and for all that I prefer the string “format” method over concatenation through addition by a ratio of maybe 997:1. After all, allowing math operators on strings is intuitively sick. Consider the following: ‘crumbl’ + ‘e’ == ‘crumble’ but ‘crumble’ – ‘e’ raises an error. This just goes to show that the application is not natural.

In other news, for another ridiculous oversight I had Python choose the minimum between the int parameter and 0 instead of the maximum to avoid negative strings. I fixed it when every call mysteriously turned up the empty string. Also, at first I did this to the parameter itself. Then I realized that the automarker might be tricksy and check if I screwed with my input at any point, so I just did it in the actual calculation.

Well, I guess that’s enough for one post, especially an unmarked one for the first week. Till next time, folks & artichokes.