MathJax

Monday, August 19, 2013

Computing for Everyone 6: Conditional Execution

Wasn't that last post fun? I'm guessing for a lot of you the answer is "no." I'm sorry--my bad.

So here's the thing: the goal of this series is to allow people who aren't programmers to take full advantage of their computers and other programmable devices at home, school, and work by giving a light introduction to computing concepts. I think the last post went too deep to really serve that purpose. I'll try to steer clear of posts like that in the future. All right, enough metablogging.


Today's topic is conditional execution.

You've seen this before:
visitor:
for your output:

Or have you? I decided to give myself some special treatment this time. Pretend you're me. Just go and tell that box that your name is John and click again.

Neat, eh? So what's the difference?

All computer programming languages support conditional execution: if something is true, do X; otherwise, do Y. Here's what the new code looks like:

function greet (visitor) {
    var greeting;

    if (visitor === "John") {
        greeting = "Hello, " + visitor + ". Remember, authentication is not authorization!";
    } else {
        greeting = "Hello, " + visitor + "!";
    }

    return greeting;
}

Neat, huh? if and else are special instructions in JavaScript (and in most programming languages). The stuff inside the () following if is evaluated as a boolean expression. If the expression evaluates to true, the block (starts with {, ends with the next }) right after the if statement is executed. Otherwise (else), the block ({ to next }) immediately following the else statement is executed.

The statement this new program evaluates is
  visitor === "John"
. A === comparison is true when the values to the left and right are equal and of the same type (e.g. both are numbers or both are strings), so if visitor is set to "John", the comparison visitor === "John" evaluates to true. "John" === "John" would also be true, just a little silly to write (you could just write "true" without the double-quotes (though writing if(true) is pretty silly to write as well)). "John" === "You" is false, 1 === 1 is true, 1 === 2 is false, 1 === "1" is false because the triple-equals comparison operator we're using treats the number 1 as distinct from a string containing 1.

JavaScript has other comparison operators, mostly for numbers. You'll see these same symbols across a wide variety of modern programming languages (well most of these are the same in, C, C#, F#, Java, Ruby, Python, Perl, PHP, BASIC, at least).

Comparing a and b in JavaScriptTrue when...
  a === b
a equals b
  a !== b
a does not equal b
  a < b
a is less than b
  a > b
a is greater than b
  a <= b
a is less than or equal to b
  a >= b
a is greater than or equal to b

Comparison operations can be combined using logical operators && (and), || (or) and ! (not) from last time:

function coverCharge (sex, itIsLadiesNight) {
    var doorPrice;
    if (sex === "F" && itIsLadiesNight) {
      doorPrice = 0;
    } else {
      doorPrice = 10;
    }
    return doorPrice;
}

So women get in free on ladies' night, otherwise it's $10 for everybody.
coverCharge ("M", true) returns 10.
coverCharge ("F", false) returns 10.
coverCharge ("F", true) returns 0.

In addition to if and else, there is "else if". This is how your describe a multi-tined fork in the road for the progress of your program instead.

function sign(birthMonth, birthDay) {
    var sign = "Oops, I guess I missed one. Sorry about that.";
    if (birthMonth === 3 && birthDay > 20  
            || birthMonth === 4 && birthDay <= 20) {
        sign = "Aries";
    } else if (birthMonth === 4 && birthDay > 20 
            || birthMonth === 5 && birthDay <= 20) {
        sign = "Taurus";
    } else if (birthMonth === 5 && birthDay > 20  
            || birthMonth === 6 && birthDay <= 20) {
        sign = "Gemini";
    // ...more of the same for 8 other signs...
    } else if (birthMonth === 2 && birthDay > 20  
            || birthMonth === 3 && birthDay <= 20) {
        sign = "Pisces";
    }
    return sign;
}

else ifs can be chained off of an if indefinitely, but an if must start the chain, and no else ifs may appear after the final else (the final else may be omitted, as above).

Exercise:
Pretend you're a robot. Imagine you have the data you need to make decisions about what to do as conveniently-named variables, and you have conveniently-named statements that describe what you can do. Can you use a chain of if/else if/else statements to describe what to do when you're bored? Describe a series of if/elses that will make your robot version of yourself behave as close to how you would behave as possible.

Bonus:
Death Note is an awesome anime show and manga. How could you express the rules for the Death Note in JavaScript so that your program can compute an outcome from use of the note? What are your inputs and outputs?

I do not often recommend anime shows, but when I do, it's always Death Note.

Wednesday, August 7, 2013

Computing for Everyone 5: Truth and Logic

Computer programming begets philosophizing. You break down complex tasks into parts simple enough for a calculator to digest. You represent real-world concepts as data in a machine. You build towers with your mind (and since the mind has its limits on how much information it can construct and logically process at once, remember to go easy on yourself).

Today we'll discuss basic logic. We'll talk about how you can combine statements that are true or false via a few different logical operators and evaluate the combination is true or false.

This logical discussion lacks a certain degree of subtlety: we assume we have perfect access to knowledge establishing statements as true or false; we're not taking into account a range of uncertainty about a statement or the risks of being wrong. Often these statements are the results of comparisons: 5 > 10 is false; 50 > 10 is true.

Boolean variables are variables that can have only one of two values: true or false. The adjective "boolean" comes from the last name of a 19th-century mathematician; there isn't any deeper meaning buried in the etymology. There are three basic logical operators: \(\land\) (and), \(\lor\) (or), and \(\lnot\) (not).

\(\land\) ("and") evaluates to true if its left and right sides are both true. \(\lor\) ("or" evaluates to true if either its left side or its right side evaluates to true. \(\lnot\) negates the logical value of what follows: if the value is true, \(\lnot\) makes it evaluate to false and vice-versa. In summary,

Logical expressionReads as...Evaluates to true only when...Written in JavaScript (and many programming languages) as...
\(p \land q\)"p and q"p is true and q is true
  p && q
\(p \lor q\)"p or q"either p is true or q is true (or both are true)
  p || q
\(\lnot p\)"not p"p is false
  !p

Truth tables are helpful charts of what a logical expression evaluates to for every variable involved. Here is what the truth tables for and (\(\land\)) , or (\(\lor\)) , and not (\(\lnot\)) look like (0 = false, 1 = true):

\(p\)\(q\)\(p \land q\)\(p \lor q\)\(\lnot p\)
00001
01011
10010
11110

Okay, this might need a touch more explanation. Let's read the second-to-last row as an example. This row tells us, from left to right, that when \(p\) is true and \(q\) is false, \(p\) and \(q\) (\(p \land q\)) is false, \(p\) or \(q\) (\(p \lor q\)) is true, and not p (\(\lnot p\)) is false. The other rows can be read the same way.

Note that because this chart has two variables (\(p\) and \(q\)), each of which can take on either of two values (true or false), there are \(2^2 = 4\) rows in our truth table.

Exercise:
Every new variable in a boolean expression doubles the number of rows in our truth table, so our table above with two variables has four rows.

For each row in our truth table, the expression we examine can either evaluate to true or false (2 distinct values). This means that for an expression with \(n\) different variables, our truth table has \(2^n\) rows which can be true or false giving \(2^\left(2^n\right)\) boolean expressions which are different from each other in terms of the set of outputs given for all sets of inputs.

The boolean operators \(\land\), \(\lor\), and \(\lnot\) are all that is needed to make any of these other expressions. For example, if we wanted to fill in a truth table whose outputs looked like
\(p\)\(q\)???
001
011
100
111


we could make this happen by replacing ??? with \(\lnot p \lor q\). See if you can fill up the entire two-variable truth table using only \(\land\), \(\lor\), and \(\lnot\) (with parentheses, if it makes life easier). The truth tables we've seen above are filled in below. Hint: there's one more entry given to you from today's Bonus. 


\(p\)\(q\)0\(p \land q\)???\(p\)???\(q\)???\(p \lor q\)????????????\(\lnot p\)\(\lnot p \lor q\)???1
000000000011111111
010000111100001111
100011001100110011
110101010101010101

The 0000 and 1111 columns are known as "contradictions" and "tautologies," respectively. The 1001 column is often read "p if and only if q" (abbreviated as "p iff q" (two f's in iff: "p if q" corresponds to column 1101)).




Bonus:
When we evaluate expressions in basic arithmetic, there is an order of operations. We evaluate exponentiation before multiplication, which we evaluate before addition. We can also change the order of operations by using parentheses, so
\[3 \times 4^2 + 2 = 48 + 2 = 50\], but
\[(3 \times 4)^2 + 2 = 144 + 2 = 146\]

To save us from always showing parentheses, logical operators have an order of precedence as well. Just like our arithmetic operators, from highest to lowest precedence, are exponentiation, multiplication, and addition, the order of operations for the logical operations we have seen, from highest to lowest, is negation (\(\lnot\)), then logical conjunction (the official name for "and," \(\land\)), then logical disjunction (the official name for "or," \(\lor\)).

This means we can actually remove the extra parentheses from the expression \((p \land (\lnot q)) \lor ((\lnot p) \land q)\) and it means the exact same thing. In fact, this function is actually kind of interesting. Let's take a look at its truth table:

\(p\)\(q\)\(p \land \lnot q \lor \lnot p \land q\)
000
011
101
110

This expression evaluates to true when either p or q or true, but not both. This expression is known as an "exclusive or" (\lor meaning "inclusive or") or XOR and comes with its own fancy symbol as well: \(\oplus\). This expression could be written as \(p \oplus q\). It's very convenient for us to have this symbol, since having it allows us to write
\[(p \oplus q) \oplus r\]
rather than
\[\lnot p \land \lnot q \land r \lor \lnot p \land q \land \lnot r \lor p \land \lnot q \land \lnot r \lor p \land q \land r\]
by analogy to the above, or, equivalently,
\[\lnot (p \lor q) \land r \lor \lnot (p \lor r) \land q \lor p \land \lnot (q \lor r) \lor p \land q \land r\]
by writing it the way we think about the concept of an "exclusive or." In fact, it turns out that like addition and multiplication, the exclusive or operation is also associative, so we can even drop the parentheses: \(p \oplus q \oplus r\)

I'm dizzy, too. Thank God for \(\oplus\) in times like these.

Here is the truth table for \(p \oplus q \oplus r\):
\(p\)\(q\)\(r\)\(p \oplus q \oplus r\)
0000
0011
0101
0110
1001
1010
1100
1111

There's no actual bonus exercise; you're just a trooper for getting through the extra material. Honestly, I tend to get a little carried away when I start using math symbols in my blog. Here's a brainteaser as a reward:

Is the following statement true or false?
"This statement is false."

Monday, August 5, 2013

Computing for Everyone 4: Clarity

Last time we looked at some basic JavaScript code to start learning how to read and write source code in general. Before continuing, I'd like to show you something about writing code.

Here's that first bit of JavaScript I wrote for you:
function greet (visitor) {
  var greeting = "Hello, " + visitor + "!";
  return greeting;
}

Armed with your basic knowledge of how JavaScript works, it's pretty easy to tell what this code is trying to do.

What if I wrote it this way?
function g (v) {
  var h = "Hello, " + v + "!";
  return h;
}
Functions g and greet behave identically, but notice how greet names what my function does much more descriptively than does g, and visitor and greeting describes the data I'm storing in my variables much better than v and h. If the two functions behave identically, why did I choose to write the longer version? Because when you write software, you aren't only writing the software in a way the computer can understand it; you're writing it in a way that you can understand it.

Even when writing your code, you will spend most of your time trying to read and understand what's there. Writing software is a process of building with your mind. It's a process of learning, understanding, and describing in detail. Here are two more ways I could have written the function:
function doWhateverThisFunctionDoesWhoKnowsAnyway (santaClaus) {
  var hoHoHo = "Hello, " + santaClaus + "!";
  return hoHoHo;
}
These kitschy names obscure what the code is trying to do.

function xxxxxxxxxx (xxxxxxxxxxx) {
  var xxxxxxxxxxxxx = "Hello, " + xxxxxxxxxxx + "!";
  return xxxxxxxxxxxxx;
}
The different identifiers differ only in the number of x characters in their names. Oh, one more thing about JavaScript: statements are separated by curly braces ({}) and ; characters--we don't actually need any of those line breaks or most of those spaces. This is legal JavaScript:
function xxxxxxxxxx(xxxxxxxxxxx){var xxxxxxxxxxxxx="Hello, "+xxxxxxxxxxx+"!";return xxxxxxxxxxxxx;}

It's not enough to write programs that do what you want the first time: you have to avoid going crazy during the process. Your programs should not only do what you want when the computer reads them, but they should be understandable in intent and mechanism when a human reads them.You will thank yourself when you want to add something new to your program later and when you have to track down a mistake in your code.

Programming languages will let you freely choose names for your functions and variables. Your variable names should describe what they represent; your function names should describe what your functions do. Like so much else in life, clarity is your friend.

Exercise:
Go on a ~20-minute Wikipedia binge rooted at the article on the programming language named brainfuck. Make sure you hit the article on Turing tar-pits along the way. Also, there are contests for writing unintelligible code. To each his or her own.

Bonus:
If your life depended on it, how would you label your goblets to avoid confusion like that encountered by Danny Kaye in this scene from The Court Jester?

Quotes:

"Everything [in Digitopolis] is called exactly what it is. The triangles are called triangles, the circles are called circles, and even the same numbers have the same name. Why, can you imagine what would happen if we named all the twos Henry or George or Robert or John or lots of other things? You'd have to say Robert plus John equals four, and if the four's name were Albert, things would be hopeless." - The Phantom Tollbooth

"Everything should be as simple as possible, and no simpler." - Albert Einstein

"There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies." - 1980 Turing Award laureate Tony Hoare

Thursday, August 1, 2013

Computing for Everyone 3: Expressions and Variables

Last time in Computing for Everyone, we discussed the nature of computing at a high level--quickly following a detailed set of simple instructions (a program) to compute output from input. Today we'll start focusing on specific ways to construct the "sentences" that make up these instructions. We're going to start learning how to program. We begin with expressions in JavaScript.


Aside: Why JavaScript? All you need to get started with JavaScript is a text editor and a web browser. I want you to get hooked.


Here is some of the simplest JavaScript you can write:
function greet (visitor) {
  var greeting = "Hello, " + visitor + "!";
  return greeting;
}
Wait, we're missing a means of input and output! Let's hand-wave them into existence for the moment. Here's your input:
Type some text--this will become "visitor" above:
...and for your output:



What's going on here? The computer is executing the JavaScript function above named greet which takes a single input named visitor. Each line ending with a ; between the { and the } is a JavaScript statement, consisting of one or more JavaScript expressions. Linguistically, you can think of statements like sentences and expressions like phrases.

The concept of an expression in computing is pretty much the same as the concept of an expression in arithmetic. Expressions are either values or ways of combining nearby values to get a single value. 3 + 7 is an expression that evaluates to 10. 3 + 7 is also a valid JavaScript expression and evaluates to 10 in JavaScript as well as first grade. Between two numeric values, + is the "addition operator," which evaluates to the sum of the expressions to the left and to the right. For completeness/pedantry, we could note that 3 is an expression that evaluates to 3 and 7 is an expression that evaluates to 7.

Computers don't just manipulate numbers: they manipulate text. A textual value in a computer program is called a string. In JavaScript, string data is text surrounded by 'single' or "double" quotes. Strings can be combined ("concatenated") using the + operator thusly: "Hello, " + "Studmuffin" becomes "Hello, Studmuffin""3" + "7" evaluates to "37", the same answer you might get from a 6-year-old boy on a sugar high. Between two strings, + is interpreted as a "string concatenation operator," joining the left and right strings into a single string. From this you can see that "Hello, " + visitor + "!" evaluates to a sort of "mini Mad Libs" based on the value of the variable visitor.

Programming languages offer more variety in operators than addition and string concatenation, of course. This post isn't meant to give you an exhaustive list of expressions in JavaScript but to introduce the idea of expression evaluation in programming languages. You can (and should) find a more detailed list of JavaScript operators here.

Computer programs keep track of values through variables. You can think of variables like the memory function of your calculator from school. Simpler calculators would let you store a single value; more advanced calculators might let you store many different values.

There are two variables in our little script: visitor and greetingvisitor holds the value of the first text box at the moment the "here" button is clicked (right-click this page and "view source" if you're curious how). greeting is a variable created by our program to store what will become the program's output. The statement return greeting; indicates that the value stored in greeting is the output of our greet function (output which I have hooked up to our second text box). A JavaScript expression consisting only of a variable's name evaluates to the value stored in that variable. You store the result of an expression to a variable by using JavaScript's assignment operator, =. var greeting = "Hello, " + visitor + "!"; stores the result of evaluating the expression right of the = sign to the variable greeting.

Exercise:
Not Photoshopped.
Microsoft has sold software with some complicated names, e.g. Windows Vista Home Premium or Office 2010 Starter. David Finley has written a cheeky bit of JavaScript to generate new Microsoft product names that you can find here.

Visit the link and click "Get Product Name" a few times to see a few different randomly-generated fake (but plausible!) 2006-era Microsoft product names appear in bold next to "Get Product Name."


Right below the link is the script source (between the <script> and </script> tags). Try to read through the code and figure out how it's making the fake product names. Here's that list of JavaScript operators again. That will help with understanding the += operator. Line 23 of Finley's name generator is the HTML that creates a link that causes the instructions in the function getProductName() to be executed when clicked. This page should help clear up some confusion about what the pfx, prd, trm, typ, and sfx variables are and how the function named pick works. How many unique product names can the generator suggest?

Save a copy of the Microsoft Product Name Generator web page as HTML to your computer. By editing the script in a text editor (it starts around line 204--use your text editor's "find" feature to search for "var pfx"), saving changes, and refreshing the view of your local copy in your web browser, add some new product names. They can be whatever you want. Have fun! Remember it's easy to save a backup copy of your file before attempting any particularly ambitious changes.

Bonus:
In Monty Python and the Holy Grail, the ferocity of the French taunting took King Arthur completely by surprise. Based on the movie's two scenes of French taunting, see if you can work out a reusable structure for computing new French insults. Once you have that worked out, try to make a French Taunter by reusing ideas (and possibly code) from the Microsoft Product Name Generator.

Be quick about it, before I make your bottom leak through your underpants, you unfortunate former parent of a salty illegitimate baby seal!