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 < 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().