A Simple Programming Language – transcript

Before writing any programs, you should have a broad understanding of what a computer is and how it operates. Any computer can be usefully thought of as a cpu, memory, and what’s called i/o, short for input output.

The cpu, the central processing unit, reads and executes the instructions of programs. So when we write code, ultimately what we are doing is creating a series of instructions for the CPU to run. These instructions are expressed in binary code, and each instruction tells the CPU to do some very small amount of work, something like say, copy this data from this part of memory here to that other part of memory, or take these two parts of memory and add them together as numbers. In general, these instructions perform very small basic operations. At first it can be quite baffling to imagine how these very small basic operations combine to do the sorts of interesting behaviors you see in programs, like say, video games, but as you progress through this series, this should become less mysterious.

The memory of a computer is the location where the data and code of running programs are stored. When the cpu runs a program, it reads the instructions from memory, and during the execution of that program, if the program needs to store some data, it can store the data in memory as well.

The i/o of the system, the input output, does not refer to one component but rather basically everything else other than the memory and the cpu. Systems typically have many input output devices: for example, a monitor is an output device; a keyboard and a mouse, those are input devices; a storage drive like a hard drive, that’s both an input device and an output device because data goes both in and out.

So the relationship between these three parts, the cpu, the memory, and the io devices, is that the cpu is in control. The cpu does its job by reading instructions found in memory, and those instructions may tell the cpu to send instructions to input/output devices, effectively telling those input output devices what to do.

While a cpu will not execute instructions directly from an input-output device, like say a hard drive, typically what happens is that programs are loaded from a stored file like say on a harddrive, copied into memory, and then the cpu executes that program in memory. So in a sense, CPU’s do execute instructions off of input-output devices; they just don’t do so directly. The reason for this, as we’ll discuss later, mainly has to do with performance. The cpu typically can read data from memory much much faster than it can read from input-output devices, like say a harddrive.

Now as we mentioned, the instructions which a CPU executes are binary codes, they’re just a series of zeroes and ones–or more accurately, they’re a series of electrical impulses in one of two states, and we represent these states with the symbols zero and one. The obvious problem is that these binary codes are extremely unfriendly for humans: humans just aren’t very good at reading and writing a long series of zeroes and ones; writing a program as a bunch of ones and zeroes would be extremely tedious. The solution to this problem is to create programming languages.

In a programming language, the programmer writes code in a form that’s more human friendly. It’s of course not a human language like English, but rather a formal a language, a language with formal rules specifying exactly how the code must be written to be understood by the machine. The computer however, cannot directly execute such code because the code is written as a bunch of text instead of binary instructions. So the text written by the programmer has to be translated into binary instructions, an actual runnable program. Programs which do this translation are called compilers and interpreters. The distinction between compilers and interpreters we’ll discuss in a later video. For now, we’ll just use the generic term translator.

Now, you might be wondering where translators come from. Well of course, originally people had to write these translators in machine code directly, but once translators existed, people could use them to write subsequent translators.

So now that you hopefully have a concept of what a programming language is, we can introduce an elementary programming language. This language is in fact one I myself made up, and I call it Pigeon. I created Pigeon explicitly for educational purposes by making it as reductively simple as I believe possible. This doesn’t mean, however, that Pigeon is unrepresentative of real programming languages. All of the concepts you’ll learn with Pigeon directly correlate to the most essential features of real programming languages.

 

 

When we write code in a programming language, we write it as text, and this code is called the source code, so-called because it’s the ‘source’ from which the translator produces actual runnable programs.

The first rule to learn about Pigeon code is that the hash sign, sometimes called the octothorpe or the number sign, that denotes the beginning of a comment. A comment in source code is simply text which is ignored by the translator. All languages allow for comments so that programmers can write notes in code that describe anything about the code which isn’t apparent to a human reader. Notice that when I show a comment I’ll highlight it in orange so that you can more easily distinguish it from actual code.

The term value in programming generically refers to some piece of data. So a number value like the number 3, that obviously is a value, a piece of data. Values in programming though, may come in many different types, not just numbers. So in Pigeon for example, we have numbers, we have what are called strings, we have what are called booleans, and later on we’ll introduce a couple of additional types.

A string, quite simply, is a piece of text; it’s a sequence of text characters. So say in code you wish to store someone’s name; that name would be stored as a string value.

The boolean data type actually has just two different possible values; the values true and false. Booleans come in handy for situations like, say, your program has options that can be enabled or disabled; the enabled state would be represented by the boolean value true while the disabled state would be represented by the value false. (If you’re wondering about the odd name, Booleans are named after the 19th century English mathematician George Boole, who invented binary algebra, the algebra of logic. So it makes sense that we name the data type for true and false after him.)

 

In the text of our source code, when we express a specific value, that is a literal: it is a value literally written in text. So for example, when you write a number in Pigeon, it can just be a simple positive number, like here 3, or a negative number like say negative 724, or a number with a fractional component, a decimal point, 8.93, or a negative number with a decimal point like negative 0.888881. When we express boolean values as literals, we write them simply in lowercase true and false.

When we write a string, we enclose the characters of the string between double quote marks. So here in the top example, that’s a string containing the sequence of characters starting with a capital R, then period, then space, then capital N, lowercase i, lowercase x o n. So one thing to note here is that uppercase letters are different characters than lowercase letters: the uppercase N is a different character than the lowercase N. Also note that a space is itself a kind of character, it’s part of the data of the string.

In the second example from the top, that’s a string with just a single character, a capital T; the third string down reads Elementary comma my dear watson. And then the last string at the bottom consists of just a single character, a percentage sign.

So that’s how we write numbers strings and booleans.

There is however, one more literal, for the special value null. The null value, which you can sort of think of as another data type with just one possible value, is used to represent nothing. It’s effectively used as a placeholder meaning, ‘there’s nothing here’. Note that the null value, like true and false, is always written in all lowercase.

When we write a string literal, there are some characters which can only be included by using what’s called an escape sequence. For example, the double quote mark character, you can’t simply put that in the middle of a string because the double quote mark denotes the end of the string. Consequently, to include a double quote mark, we have to escape it, meaning we have to put a backslash in front of it. And that indicates to the language that the following character, the double quote mark in this case, is not meant to denote the end of the string, it’s just meant to denote a double-quote mark character in the text data. So in the string literal at the top here, the first character of the string is simply a single double-quote mark character. The backslash followed by the double quote mark, those two characters together represent an escape sequence, they represent one character in the text data, a double quote mark.

In the second string, where we see backslash n, that is an escape sequence representing the newline character. The newline character, as the name implies, is used to denote where a new line should start. So the text in this example reads hello comma, and then on the next line, world period. Now of course what we see here is all written on one line, but the idea is that a program that renders text should render this text two successive lines. So just be clear, in the string data, we have this newline character to indicate the intention that there be a newline there, but it’s ultimately up to whatever code renders the string on the screen or a printer somewhere, it’s up to that code to represent the newlines, to draw the character after the newline on the next line down. In our code however, we must write string literals always on just one line; we can’t continue them onto the subsequent lines, so the opening and closing double-quote mark of a string literal will always be on the same line.

Finally, in the bottom string, the escape sequence backslash backslash is used to denote just a single backslash character. So the text data of the string actually reads C colon backslash blah backslash blah backslash blah. The reason we have to use an escape sequence to denote a backslash character is because the backslash character itself is used to denote the start of escape sequences. So if we just wrote single backslashes here, then the backslashes would appear to the language to denote the start of escape sequences, but that’s not what we intend here, so we write a pair of backslashes just to have a single backslash character.

 

 

The basic units of action in our code are called operations, and just like in mathematics, an operation is something which takes input values, and then returns an output value. Like say, an addition operation with the inputs 3 and 5 returns the value 8.

In an operation, the part which specifies which operation to perform is called the operator. Like say, the plus sign in an addition operation, that’s the operator. The input values to the operation, those are called the operands. So here’s an example addition operation as you’re used to seeing it in mathematical notation: the plus sign is the operator, and the operands are 3 and 5.

In Pigeon however, we use a slightly different style of notation for operations called prefix notation. The notation you’re familiar with from mathematics is called infix notation, so called because the operator is infixed between the operands. In prefix notation, the operator is placed in front, and then the operands are listed afterwards. Another change we make in Pigeon is that the operators for common operations are not denoted by symbols, but instead are denoted by words. For example, the addition operator is not the plus sign but rather the word ‘add’. So rather than writing 3 plus sign 5, you would write add 3 5.

One other important change with this notation style is that the parentheses that surround an operation are not optional. Every operation is always surrounded in its own pair of parentheses. In infix notation, the parentheses are often optional. Like say, we can write 3 plus 5 without any surrounding parentheses.

Now one advantage of prefix notation is that operators are not limited to having just two operands as they are in infix notation. So whereas in infix notation, we have to write 3 plus 5 plus negative 7 plus 11 to add all those things together, in prefix notation, we can simply write one addition operator followed by all four operands.

Another advantage of prefix notation is that we never have to worry about precedence. With infix notation, the operators are given an order of precedence, that is, a set of rules that determine which operations are performed before others when parentheses don’t explicitly denote the order. So here for example, when you write 11 minus 2 times three, the multiplication operation is performed first because the multiplication operator has a higher precedence than the subtraction operator. Really, the only point of this order of precedence is that it often spares us from having to explicitly surround our operations in parentheses. We only need to use parentheses in infix notation when we wish to subvert the normal order of precedence, as we do here, where we put the subtraction operation in parentheses such that it is performed first before the multiplication. In prefix notation though, there’s no concept of an order of precedence; we just always explicitly put every operation in a pair of parentheses, and there’s never a question of which operation is done first. Here for example, you see the prefix equivalent, where we have a multiplication operator with two operands, one of which is the number 3, the other of which is another operation, the subtraction of 2 from 11.

Last thing to note here, with some operations like multiplication and addition, the order of the operands doesn’t matter, but with other operations like subtraction, it does. For instance, sub 11 2, that returns 9, but if we wrote sub 2 11, that would return negative 9.

 

 

In programming, what we call variables are really quite different from what we call variables in mathematics. In mathematics variables are used in equations such that the value of a variable possibly depends upon the value of other variables. Like say, in the equation x equals 2y, x represents the whole range of possible values for some given y value. A programming variable, in contrast, always just has one value at any moment in time. A variable is simply a symbolic name which we can give a designated value, but we call them variables because, over the course of time as the program executes, we can change a variable’s value. So in the course of a program,  a variable’s value may change, it may vary–hence the name, ‘variable’. Effectively, what a variable represents in the machine is a location in memory to store a value, a location we’ve given a symbolic name.

 

The jargon term for a name in code, such as the name of a variable, is ‘identifier’. Unlike in mathematics, it’s generally considered bad practice to overly use single-letter variable names in programming. Identifiers though, must conform to a few rules: they can consist of uppercase and lowercase letters, and they can also have numerals in them; however, they cannot have spaces in them, and they cannot begin with a numeral. So these three examples are all valid identifiers, but these other three are not. The top one here, newyork, is not valid because you cannot have spaces in your identifiers; the second one is invalid because you cannot have symbols like the carrot sign, the dollar sign, or the asterisk; and 43asdf, that is not valid, because while identifiers may contain numerals, they cannot begin with numerals, they must begin with a letter. The last rule to keep in mind about identifiers in Pigeon, is that they are case sensitive, meaning that the case of each letter matters, so if you have a an identifier new york where N is capitalized and Y is capitalized, but the other letters are lowercase, that is a different identifier than new york with all the letters lowercase or all letters of YORK in uppercase, or some other mix of uppercase and lowercase letters. So all of these identifiers here are considered by the language to be totally different identifiers. If you have a variable named new york in all lowercase, you can also have a variable named new york in all uppercase, and they would be considered totally separate variables.

It turns out that most popular languages have case sensitive identifiers; there are only one or two notable exceptions. The reason case-sensitivity is the norm is that it encourages programmers to be consistent. What tends to happen when a language is not case-sensitive is that the same identifier written throughout code ends up getting written several different ways, and most people feel that’s bad style. It makes the code ugly and hard to read. On the other hand, even though the language allows you to have, say, new york all lower case and also new york all upper case, it’s generally a bad idea. You generally shouldn’t be creating identifiers that are just like other identifiers in your code except for the letter case because doing so easily leads to confusion and errors.

 

A reserved word is an identifier that is specifically reserved by the language; that is, you’re not allowed to use that word for your own identifiers. Pigeon has only a couple dozen reserved words; you’ve seen a few of them already: the operators add, sub, mul; there’s also div for the division operation, and shortly we’ll introduce a few more.

 

 

 

When we give a variable a value, that’s called an assignment. To perform an assignment in Pigeon, we write the reserved word ‘as’, followed by the name of the variable, and then the value to assign to that variable. So here for example in the top line, we are assigning the value true to a variable named dog; and in the next line we’re assigning the value negative 87.2 to a variable named newt; and then the value null, to a variable named bird; and lastly, a string with the text “rubberbabybuggybumper”, we’re assigning that to a variable named cat.

 

So now, let’s look at our first actual sequence of code. ‘as bar 19′, assigns the number value 19 to a variable named bar, and then in the next line, ‘as foo bar’ assigns the current value of bar to a variable named foo, so foo also now has the value 19. And then in the next line, ‘as bar 3′ assigns the value 3 to the variable bar, and in the final line, the  value returned by the add operation is assigned  to fizz. This add operation returns the sum of 11 and the current value of foo. So what is the current value of foo? Well it’s whatever we last assigned to it, and foo was last assigned 19, so we sum 11 and 19, returning 30, which is then assigned to fizz.

So that’s the key concept here: when we use a variable, it has the value of whatever was last assigned to it. This can be a confusing point if you learn programming starting with some other languages, because in most popular languages, assignment is denoted with an equals sign. So instead of writing ‘as foo bar’, you would write ‘foo equals sign bar’, and this gives many students the false impression that what assignment does is somehow create an equation, that assignment creates a persisting relationship between the two variables rather than just give the target of the assignment the current value of the other variable. And so here in this case, that misconception would lead you to believe that when we assign 3 to bar, that we are also affecting foo and giving it the value 3 as well. But that’s not how assignment works. When we assign to bar, it’s just assigning to that variable, not any others. Foo still retains the value 19 because that’s the last value which we assigned to it. In fact, that’s how assignment works in all languages, even in languages that misleadingly use an equal sign to denote assignment.

 

Like in mathematics, we use the term expression to refer to anything which evaluates into a value. So an expression in code may be a literal, like null, or the string here, “hello”, or it may be a variable, because a variable evaluates into whatever value was last assigned to it. Or an expression may be an operation, because operations return values; like say, the add operation here will return the sum of 4 and foo. Note that an operation is a kind of expression which itself contains other expressions. So in the add operation here, the variable foo, that itself is an expression, and the number literal 4, that itself is an expression. These expressions made up of other expressions we sometimes call ‘complex’ expressions, in contrast to ‘simple’ expressions.

 

Another important jargon term, is ‘statement’. Statement is just a generic term for the units of syntax that make up our code, somewhat analogous to sentences in English. Our code is a series of statements. So far we’ve seen two kinds of statements: assignment statements and expression statements. An assignment statement, as we’ve seen, begins with the ‘as’ reserved word, and an expression statement consists of just an expression, usually an operation to perform some action. So here for example, ‘as foo 53′, that’s an assignment statement. And then the next line, the addition operation is an expression statement. Now be clear this is an unrealistic example because an addition operation by itself doesn’t do anything useful: it just produces a new number value which doesn’t get used, so the statement is effectively pointless.

 

Let’s introduce two operators for which it actually makes sense to invoke them as stand-alone expression statements. The first of these operators is ‘print’. A print operation takes one operand, and displays the text in a console window.  Consoles, also called terminals, are the simplest possible way for programs in modern operating systems to display text output and get keyboard input from the user. We’ll discuss them in detail in a later unit.

In any case, here in this code, the first line ‘print’ and the string ‘wakka wakka’ will display ‘wakka wakka’ on the console.  The second line assigns the value 19 to a variable bar, and then in the last line, we print the value of bar, which at this moment is 19, so the value 19 is displayed on the console.

 

The prompt operator gets keyboard input which the user types at the console. When prompt is invoked, the program waits while the user types at the console, and then when the user hits enter, everything they’ve typed is returned as a string by the prompt operation. So here in the first line, we invoke prompt, the user types at the console, hits enter, the prompt operation returns that text as a string, and that string is assigned to the variable foo. Then in the next line, if we print foo, that same string is displayed on the console. Effectively, whatever the user types is repeated back to them.

 

For the sake of simplicity, print and prompt are going to be the only means we have in Pigeon to perform input and output.  We’ll have no other way to put something on screen or get input from the user. This is not because of anything fundamentally limited about Pigeon; were Pigeon developed into an actual language it would be perfectly capable of doing any input and output, but for educational purposes, we’re keeping things simple. Ultimately, doing anything interesting in code of course relies upon things like storing data in files, drawing on the screen, getting mouse input, and so forth, but you should accept now that in this course we’ll be going through hours of material before we do any of those things. Just trust me that this approach is easier and more efficient and will give you a better understanding of how programming actually works than a flashier approach would. Starting with graphics programming, for example, just makes things more confusing because that approach inevitably requires glossing over fundamental concepts; you’ll get the thrill of seeing your code do something flashy, but you won’t really understand how you did it.

 

In any case, now that we have the print operator, we can write our first program, which is the traditional first program students always write, called ‘hello world’, a program which simply prints on the screen the text “hello world”. In Pigeon, this program is exceedingly simple; it consists of just one statement, a print operation with the string “Hello, world!”.  In some other languages, though, hello world can actually be surprisingly complicated.

 

To begin to do more interesting things in code, we need yet more operators. First off, the eq operator performs an equality test on two or more operands. When all the operands have the same value, eq returns the boolean value true, but otherwise returns false. So here the first two examples return true, but the last example returns false because 6 is not equal to 2.

The ‘not’ operator takes a single boolean value and returns the reverse truth value, so ‘not true’ returns false and ‘not false’ returns true.

These two operators eq and not, come in useful for what we can call ‘conditional execution’. When we write code, we often want a section of code that is executed only conditionally–that is, depending upon some condition, the block is either executed or skipped over. For this purposes, we have in Pigeon the ‘if’ statement. An ‘if’ statement is written beginning with the reserved word if, followed by a condition, and then on the following lines, we write what is called the ‘body’. The body consists of one or more other statements, but these statements are written indented under the if. The way the if works is that the condition, which is some expression returning a boolean value, is evaluated, and if it returns true, then the body is executed; otherwise if the condition returns false, the body is skipped over. So that’s why it’s called ‘if': it has the sense of ‘if this condition is true, then do this stuff, otherwise skip over this stuff’. Here in this example, we have an if where the condition is the expression ‘eq x 3′, and the body consists of two statements, the first printing cat, and the second printing dog. So when this code executes, if the equality operator returns true because x does equal 3, then first the code will print cat, then it will print dog, and then execution continues in the line after the if, in this case a line that prints bird. If on the other hand, x at this point does not equal 3, the equality operation will return false, and so the statements of the if body will get skipped over, so this code will just print bird.

 

Other times in code, we want not just to skip over something, we want to make a choice of either doing one thing or another thing, and this is called mutual exclusion. We do one thing or the other, but not both. For this purposes, we can simply use two separate if statements by giving them logically inverse conditions. So when this example executes, when x equals 3, the condition of the first if will be true, but the condition of the second if will be false, so the code will print ‘hi’ but not ‘bye’. On the other hand, when x does not equal 3, then the condition of the first if will test false, but the condition of the second if will test true, so this code will print ‘bye’, but not ‘hi’.

Because mutual exclusion is used so commonly, rather than having to write to separate if statements, we have a special convenience, the ‘else’ clause. An if statement can be followed by an optional else clause, which begins with the reserved word else and has its own body. When the if statement is executed and the condition is true, the first body is executed, but the body of the else is not. Conversely, when the condition tests false, the body of the else is executed, but the first body is not. So for example here, when the condition is tested and x does equal 3, then this code prints hi; otherwise when x does not equal 3, it prints ‘bye’.

Now in some cases, you might wish to have mutual exclusion between more than just two cases; you might have 3 cases, as we have here. In this example, again when the condition tests true, we execute just the body of the if, otherwise we execute the body of the else. But this else body itself contains another if statement, so when the else executes, the condition of that if statement is tested, and if true, then it prints bye, otherwise not. Effectively, we have 3 mutually exclusive cases here:  when x equals 3, the code prints hi, when x equals 5, it prints bye, but when x doesn’t equal 3 or 5, then nothing happens.

To make it easier to write such cases, we can have clauses beginning with the reserved word elif, which is a  contraction of ‘else and if’. Elif clauses effectively combine an else with an if. When you see an if with an elif clause, as usual, the condition of the if is tested, and when it’s true, then the first body is executed, but when false, then we test the condition of the elif, and when that is true, we execute the body of the elif; otherwise, we skip over that body as well. So we can rewrite the previous example with an elif like so.

 

We can actually give an if more than one elif clauses, effectively adding on more mutually exclusive cases. So here in this example, as usual, we start at the top and test the condition of the if itself, and when it’s true, we print ‘hi’ and then skip over all the elif clauses; otherwise, we test the condition of the first elif clause, and when that’s true, we execute its body; otherwise, we test the condition of the next elif, and so forth. So in short, the way this works is that the conditions are tested from top to bottom, and the first one that tests true, its body is the one–and only one–to execute. In the case that none of the conditions test true, then all the bodies get skipped over. So we effectively have here 5 mutually exclusive cases: when x equals 3, we print ‘hi'; when x equals 5, we print ‘bye'; when x equals -7, we print ‘moo'; when x equals 14 we print woof; and when x doesn’t equal any of those values, we don’t print anything because we’ve skipped over the bodies of each clause.

 

It’s also the case that when an if has one or more elif clauses, it can also end with an ‘else’ clause; the else clause effectively acts as the default, such that when none of the conditions test true, it’s the else clause which gets executed. So here, when x doesn’t equal 3 or 5 or -7, the code prints meow.

 

To have more interesting condition expressions, we need a few more operators. First there’s the ‘less than’ operator, which returns true when its operands, which all must be numbers, increase in value from left to right. So the first example here returns true because 25 is less than 76 and 76 is less than 8000, but then the second example returns false because 35 is not less than -2, and the third example also returns false because 2 is not less than 2.

A similar operator is ‘less-than-or-equal’, which we write lte. In the last example here, when we write lte 2 2 7, that returns true because 2 is less than or equal to 2.

And then predictably, we have the reverse of less than, we have greater than, which returns true when its operands decrease in value from left to right. So the first example here gt 25 76 8000 returns false because 25 is not greater than 76, nor are they greater than 8000. And the second example returns true because 35 is greater than -2 which in turn is greater than -10. And the last example returns false because, yes, 8 is greater than 4, but 4 is not greater than 4. If we used the greater than equal operator instead, written gte, then this last example returns true because 8 is greater than 4 and 4 is equal to 4.

 

The ‘and’ operator takes two or more boolean operands and returns true only when all of those boolean values are true. So the first example here returns true, but all the remaining examples return false.

The ‘or’ operator also takes two or more boolean operands, but returns true when at least one of the operands is true, not necessarily all. So the first three of these examples return true because at least one of the operands is true or all of them are true, but then the last example returns false because the operands are all false.

 

The modulus operator, written mod, returns the remainder of division. So for example, mod 15 5. 15 divided by 5 is 3 with a remainder 0, so this return 0, but 16 divided by 5 is 3 with a remainder of 1, so 16 mod 3 returns 1. And mod 17 5 returns 2 because 17 divided by 5 is 3 with a remainder of 2.

One useful thing to do with the mod operator is to test whether a number is even or odd. Here when we write mod x 2, when x is an even number, mod x 2 will return 0. So here in this code when x is even, mod x 2 returns 0, and yes 0 is equal to 0, so the condition of the if is true, and the code prints “even”. Otherwise when x is odd, mod x 2 will return 1, and one is not equal to 0, so the condition will test false, and the code prints “odd”.

 

Often in code we want what’s called a loop; that is, we want a section of code that repeats some number of times. For this purpose, we have the while statement. A while statement looks very much like an if, with a condition and a body, but with the reserved word while in place of if. The word ‘while’ was chosen because a while loop has the sense of ‘do this stuff while this condition is true’.

The way while works is that, just like an if, the condition is evaluated, and when it’s true, the body is executed. The difference is that once the body is done executing, the condition is tested again, and when the condition is once again true, the body is executed again. This happens ad infinitum until the condition tests false, at which point the body is skipped over and execution continues on past the while.

So consider what this code does: first we assign 6 to a variable named z, and then we encounter a while loop, where the condition asks, is z greater than 0? Currently z has the value 6, so yes it is greater than zero, so this returns true, and we execute the body, which prints the value of z, which is currently 6, and then assigns to z the value of z minus one; so z is currently 6; subtracting one from 6 gets us 5, so we assign 5 to z. And now that the run through the while body is finished, the condition is tested again, and the value of z is still greater than 0, so the body is executed again, the value 5 gets printed, and z is assigned one less than 5, the value 4, before the condition is tested again. And this process continues like this until, in the last iteration of the loop, z is assigned 0, and so the condition will test false because 0 is not greater than 0, ending execution of the loop. In effect, this code ends up printing the values 6 then 5 then 4 then 3 then 2 then 1. The body of this loop ends up running 6 times.

Now that we’ve introduced loops, we can write another traditional simple program called Fizz Buzz. The fizz buzz program simply prints all of the integers from one to one hundred except, instead of any integer evenly divisible by 3, the program prints fizz, and except for any integer evenly divisible by 5, it prints buzz. And then for  any integer evenly divisible by both 3 and 5, the program prints fizzbuzz.

To start, we know we’re going to be printing a range of numbers from 1 up to 100, so first we’re going to want a loop in which a variable starts with the value 1 and gets incremented each iteration until, in the last iteration, it has the value 100. So here the variable x is given the initial value 1, and then the loop tests whether or not x is less than or equal to 100. And so every time this condition tests true, the body of the while loop will execute for another iteration. At the end of the body, we increment the value of x: we take the current value of x, add one, and then assign the result to x itself. So what we have here is a loop where in the first iteration, x has the value 1, in the second iteration, x has the value 2, in the third iteration, x has the value 3, and so forth until, in the last iteration, x will have the value 100, which gets incremented to 101, and so the condition will then test false because 101 is not less than or equal to 100.

 

Now, in each iteration of the loop, we’re going to need to determine whether the value of x is equally divisible by 3 and whether it is equally divisible by 5. When a number is equally divisible by 3, the modulus of that number by 3 will be 0, so we do mod x 3 and test whether that is equal to 0; that will assign true or false to the variable ‘by3′. And then we do the same for 5, taking the modulus of x by 5, testing whether the result is equal to 0, and assigning the true or false value to by5.

Based upon these two variables, we need to decide which thing to print among four mutually exclusive cases. When both by3 and by5 are true, that means that x is evenly divisible by both 3 and 5, so we print fizz buzz. In the case where x is divisible by 3 but not by 5, we print fizz, and in the case where x is divisible by 5 but not by 3, we print buzz. Lastly, in the case where x is not divisible by either 3 or 5, we print the value of x itself.

So that’s the entirety of the fizz buzz program; it prints all the numbers from 1 to 100, except when the number is evenly by 3 and 5, it prints fizz buzz instead, and when the number is evenly divisible by just 3, it prints fizz, and when the number is evenly divisibly by just 5, it prints buzz.

 

A very important thing to note here is that the ordering of the mutually exclusive cases matters in this example. Given how we wrote our conditions, our second and third cases test true when the first case tests true, because of course when both by3 and by5 are true at the same time, by3 and by5 are true individually. So if we reordered these cases, we can get the wrong behavior. For example, if we put the case of just by3 is true first, then we’d print fizz when we’re supposed to print fizz buzz (because the just by3 case would test true when both by3 and by5 are true). Likewise, if we put the case of just by5 is true before the case of by3 and by5, then we’d print buzz when we’re supposed to print fizzbuzz.

One way to think about this is that our case conditions have been partly left implicit by their order. In an if statement with elif clauses, the conditions of the elif clauses implicitly require that all previous conditions test false. So in our original ordering, when we put the condition of by3 and by5 first, the second condition by3 implicitly requires that the condition by3 and by5 tested false. If we wanted to keep the same logic but write these clauses in reverse order, we’d have to change the condition from just ‘by3′ to ‘by3 and not by5′.

So the lesson is, when writing your mutually exclusive cases, be sure to either fully state the conditions, or simply be cognizant what’s being left implied in their order.

 

Rather than use just use the operations predefined in the language, programmers also define their own operations, called functions. Functions are also sometimes called routines, subroutines, procedures, or in some contexts methods. ‘Function’ though is the most common term. Once the programmer has defined a function and given it a name, they can invoke–or ‘call’, as we say–that function just like they invoke one of the built-in operations. In parentheses you write the name of the function followed by however many operands are expected by the function.

To create a function in Pigeon, we use a function statement, beginning with the reserved word function. That’s followed by the name you choose for the function, an identifier, and after that, ‘parameters’, which we’ll explain in a moment, and then indented on the following lines, you write the body, a series of statements that execute when the function is invoked.

So here for example, we create a very simple function called Eric. This function eric has no parameters, and it just has one statement in its body, ‘print “hello”‘. So having created this function, we can then invoke it by simply putting it in parentheses. And because it takes no operands, we just write the function name in parentheses and that’s it.  When we invoke this function eric, all it does is print “hello”.

Now functions, like operations, can take input values, but rather than calling those input values operands, we usually call them arguments, and when we invoke a function, the arguments are passed to parameters, which are variables in the function that receive the input values. So here for example, we create a function we call ryan and we give it two parameters, the first called bat and the second called goat. Then in the body of the function, what we do is subtract the value of bat from goat and print the resulting value. So, if we then invoke the function with the arguments 4 and -9, the value 4 gets passed to the parameter bat, and the value -9 gets passed to the parameter goat, and so in the first invocation of this function, when we subtract bat from goat, 4 from -9, we get negative 13, and the function will print -13. In the second invocation of ryan here, the argument 3 is passed to bat, and the argument 5 is passed to goat, so when we subtract bat from goat, we get 2, and so the function prints the value 2.

Operations can not only take input values, they can return an output value. To return an output value, we use a return statement. Here for example is a function jerry which simply returns the value 3. When we invoke Jerry here, it returns the value 3, and so this code prints 3.

 

Now let’s write a function that might actually be useful, a function that computes and returns a factorial. In case you don’t recall, a factorial of a number takes that number and multiplies it by all integers down to 1. So the factorial of 3, for example, is 3 times 2 times 1. The factorial of 0 however is a special case which always returns 1.

Here’s how we could write a factorial function in Pigeon. Let’s call the function factorial and give it a single parameter named n. In the body, we use a loop to compute the factorial and store the result in the variable ‘val’, which is then returned in the last statement of the body. So if we call the factorial function with the argument 4, it’ll  return 24 because 4 times 3 times 2 times 1 is 24, and then if we call the function with the argument 5, it’ll return 120, because 5 times 4 times 3 times 2 times 1 is 120.

Let’s step through exactly what goes on when the argument is 4. The parameter n starts with the value 4, and then we assign to the variable val the number one. Then we enter the loop if n is greater than 1, and n is currently 4, so the condition tests true. In the loop we multiply n times val, that’s 1 times 4 yielding 4, which we assign to val. Then we decrement n by subtracting one from n, yielding 3, and assigning the result to n. So when we test the condition again, is n greater than 1? Well yes because 3 is greater than 1, so we enter the loop again. And we multiply n times val: n is 3, val is 4, so that’s 12 which we assign to val, and then we decrement n again. When we now test the condition, n is 2, still greater than 1, so we enter the loop once more and multiply 2 times 12, yielding 24, which we assign to val. We again decrement n down to 1, but now the condition tests false because 1 is not greater than 1, so we exit the loop and return val, which now has the value 24. So our factorial function invoked with the argument 4 returns 24.

Quickly, though, consider the special case of 0. If we call the function with an argument of 0, val is assigned 1 as usual, but then the condition of the loop tests false the first time, so we never enter the loop, instead just returning the value 1, which is the correct answer for the factorial of 0.

 

 

Programmers have many mantras and aphorisms about how to write good code, but perhaps the most important one is D R Y, Don’t Repeat Yourself. The basic point of D R Y, is that, whenever you feel yourself doing the same thing over and over in your code, there’s probably a better way to write the code that avoids that duplication. Repetition is the number one sign that you’re doing something wrong, that you’re doing more work than you need to do or that you’re creating more work for yourself down the line, because the problem with repetition in code is that, later on, when you want to change something–and you will want to change things–you’re going to have to modify the code in many places at once to make any small change.

So repetition is very toxic. The fundamental tool we have for avoiding repetition is the function. As a beginning programmer, you’re going to be quite uncertain how to organize your code into functions. In fact, you won’t even know when you should write a function at all. The problem is that when we talk about repetition, we don’t necessarily mean verbatim repetition. Very often you will get the vague sense that you have repeated yourself, but that repetition will be intermingled among other things, and it may not be obvious how you can disentangle and extract that repetition into its own functions, how you can take several particular cases and generalize them into one case.

There’s also the related question of how much work individual functions should perform. The mantra here has always been that a function should do one single thing, and only that thing. If we follow this prescription well, we should generally end up with code in which most of the functions end up quite short. How short exactly? Well if there is a consensus among programmers, I would say it’s this: the majority of your functions should stay in the range of 15 to 30 lines. At the very least, anything above about 30 lines strongly warrants careful consideration as to whether it might perhaps be better split into smaller functions.

 

In programming languages, the term scope is used to refer to both the place in code and the time during execution where and when a thing exists. The variables of a function are said to have local scope, to be ‘local’ to the function in which they are found. So here, cat dog and bird are all local variables of the function kate. (And yes, parameters really are just local variables; they’re only special in the way they get their initial values from the arguments to the function calls.)

When we say that cat dog and bird are local to the scope of kate, what do we mean? Well this means that they exist only in that function and so cannot be used outside the function or in another function. In fact, when a function is called, the local variables are created for that individual call, and then when the function call returns, when it ends, those local variables disappear: they’re destroyed, they’re no where in memory, they don’t exist. Effectively, each different call to the same function has its own independent set of the local variables, so in two different calls to kate, the cat variable in one is a separate variable from the cat variable in the other. So be clear that when we call a function, the local variable values are not retained from any previous call to that function. (This uniqueness of local variables in different invocations will be very important to understand when we discuss function recursion.)

 

A namespace is simply a space–in the abstract sense–in which a set of names exist. What we want to avoid in programming languages are ‘namespace collisions’. A namespace collision is the situation in which you have a single name that’s ambiguous because it refers to more than one thing. In daily life we cope with these ambiguities, such as in cases where you have two friends with the same name. Programming languages, however, can’t have any ambiguity of what a function or variable name refers to.

The simplest rule a programming language could adopt to avoid namespace collisions is to simply decree that one name always refers to the same thing throughout the entire code of a program. In practice, though, this would be quite inconvenient. For one thing, it would just be bothersome if we had to come up with unique names for simple variables like loop counters. For another, when writing any new code, we’d constantly have to check the entire rest of our code to see if a name we want to use is already in use.

Consequently, languages almost universally adopt the rule that each function is its own namespace. For example, here we have a local variable coconut in the function miguel, but then we also have a local variable coconut in the function colin, but this is fine because each function is its own namespace. Coconut in the one function has nothing to do with coconut in the other; the two variables just happen to have the same name. This works out fine because as we just explained, each function is its own scope anyway; the variables of a function only exist for the duration of each invocation, so it’s simply not possible for one function to use the variables of another. For example, we can’t use the local apple of the miguel function inside the function colin, and so the language will give us an error if we attempt to do so. If we assign to a variable named apple in the colin function, then what we are actually doing is creating a new, separate local variable in colin that has nothing to with the variable apple in miguel.

 

There are other ways in which you might get name collisions. For instance, it’s possible you might create a variable with the name of a function. Here we have two functions, one called harry, the other called lisa, and lisa has a variable called harry. So the question is, if in the body of lisa I use the name harry, which does it refer to? The local variable or the function? Pigeon’s solution to this problem is crude yet simple: Pigeon disallows variables and functions with the same name to coexist, so this code would just be rejected outright. As we’ll see in later units, most languages have rules that allow for such name reuses without ambiguity.

 

A thing which is global in code is the opposite of local: a thing which is global exists everywhere throughout the program and so can be used anywhere. In Pigeon, functions are global, and any variables you create outside of a function are also global.

Here we have three global things: a function alison, a function jason, and a variable cat. The function alison uses the global variable cat such that when it is called, it prints the value of cat, which at this time is the string rubber. The function jason also uses the global variable cat, but it assigns to it. Now normally an assignment in a function creates a local variable of that name, but because here we have a global variable named cat, any assignment to that name is going to assign to the global, not to any local. So effectively, if we have a global variable named cat, then we can’t have any local variables named cat in the same program. Again, this is a crude solution to the problem of name collisions. As we’ll see later, most languages have rules that accommodate the existence of globals and locals of the same name.

In any case, when we call jason with the string “glue” as argument, that string gets assigned to the parameter x and so gets assigned to the global variable cat. So when we subsequently invoke alison again, it prints the current value of cat again, but the current value now the string “glue”.

 

In Pigeon, and in many languages, functions are actually a type of value. This means we can assign them to variables and can pass them as arguments. So say I have this function here gina. I can assign gina to a variable dog, and when I invoke dog as a function, it’s the same as invoking gina, because at the time of this call, the variable dog references the function gina. Or say I might have another function harry with one parameter turtle, which it invokes as a function. So if I call harry with the argument gina, gina gets passed to turtle, and so when turtle is invoked, gina gets invoked, printing “hi”.

It’s also possible to return a function from another function. Here we have a function alec with one parameter cow, and depending upon whether cow is true or not, the function returns either the function harry or the function gina.

 

Something which is recursive is defined in terms of itself. This may sound like a logical impossibility, but in fact it’s not. We can have recursive functions. A recursive function is a function which, somewhere in its body, invokes itself.

So for example, here’s a function jessica which prints hi and then invokes itself. What’s going to happen when we invoke jessica is that it prints hi and then invokes itself, and this second invocation also prints hi and then invokes jessica, meaning a third invocation will also print hi and then invoke jessica again. And this will happen ad infinitum.

Jessica is an example of direct recursion, but it’s also possible to have indirect recursion. Here we have a function kelly which prints “a” and then invokes mike, and a function mike which prints “b” and then invokes kelly. So what happens when we invoke kelly is that it prints “a” and invokes mike, and the invocation of mike prints “b” and then invokes kelly, thus perpetuating an endless cycle: we’ll see “a” and “b” printed in an endless loop as kelly calls mike and mike calls kelly. Both kelly and mike here are indirectly recursive because an invocation of kelly will indirectly result in more invocations of kelly and an invocation of mike will indirectly result in more invocations of mike.

Now in both of these examples, the recursion is infinite, resulting in unending loops. This infinite recursion, you might imagine, is not generally desirable: we don’t want our programs to get stuck doing the same thing forever. Usually when writing recursive functions, we want them to stop invoking themselves at some point.

The classic introductory example of such a function is a recursive version of a factorial function. We of course already made a factorial function using a while loop instead of recursion, and this actually demonstrates a good point: anything you can do iteratively with loops, you can do recursively. So the question is, when is one approach more appropriate than the other? Most programmers find iteration easier to reason about than recursion. On the other hand, recursion offers much more elegant solutions to certain classes of problems. Computing a factorial, however, is not in one of those classes. The iterative solutions and the recursion solutions are about equal in simplicity, as both approaches take only a few lines of code for this problem, so simplicity and elegance are not really an issue here. On the other hand, depending upon how the language you’re using is implemented–in particular, how it does function calls–it’s possible that a recursive solution may use a lot more memory than an iterative solution, as we’ll discuss shortly.

So here’s a recursive version of a factorial function. Note that this way of computing a factorial is actually an elegant expression of how the factorial operation is defined: first we have the special case for the factorial of 0 which always returns 1, but then the factorial of any positive integer is the same as multiplying that number times the factorial of one less than that number. Looking at an example, this checks out: for instance, the factorial of 5 is 5 times 4 times 3 times 2 times 1, and the factorial of 6 is 6 times 5 times 4 times 3 times 2 times 1, so the factorial of 6 can be expressed as 6 times the factorial of 5.

Walking through the code, first what happens with an argument of 0? Well, when n starts as zero, then the test of the if condition will be true, and so we’re going to return 1, the correct answer for the factorial of 0.

But now, what about an argument of 1. Well, first the condition n equals 0 will test false, so we’ll skip to the second return statement. And in this return statement, just keep in mind that expressions are evaluated inside out: the operations in the inner parentheses get evaluated first, so first evaluated is the subtraction, then the call to the factorial function, then the multiplication, and then what the multiplication operation returns is what this return statement returns.

So first the sub operation returns n subtracted by 1; 1 subtracted by 1 is 0, so factorial is invoked with the argument 0. As we just established, the factorial function invoked with the argument 0 returns 1, so the multiplication operation has the operands n and 1. N still has the value 1, so this is 1 times 1, which is of course 1. So this second return statement ultimately returns the value 1.

OK, now what if we call factorial with the argument 2? Well the if condition again returns false, so we skip to the second return statement, but now n has the value 2, so n minus 1 returns 1, and factorial is invoked with the argument 1. As we just established, the factorial function invoked with the argument 1 returns 1, so the multiplication operation has the operands n and 1. N has the value 2 this time, so this is 2 times 1, which is of course 2. So this second return statement ultimately returns the value 2.

We can see a pattern here: when calling this factorial function with an argument of n, the function will recursively call factorial with the argument which is one less than n. So when we call factorial with an argument of 15, the function will recursively call factorial with the argument 14. And in that call to factorial, the function will recursively call factorial with the argument 13. And so forth. What we get effectively is a chain of recursive calls: a call to factorial with an argument of, say, 5, will trigger a chain of recursive calls with the arguments 4, then 3, then 2, then 1, and then finally 0. What’s special about the argument 0 here is that that call to our factorial function will not trigger another recursive call: the call with argument 0 will simply return 1. The argument 0, here, serves as what is called the base case, the case in which our recursive function will stop making more recursive calls. Once the call with argument 0 returns, then the call with argument 1 can return, then the call with argument 2 can return, and so forth back up the chain. So note that the last recursive call is actually the first to return, while the original call is last to return. This actually is how a chain of function calls always works: the last function called in the chain is always first to return while the first call in the chain returns last.

 

The key thing to understand about a recursive chain of function calls is that, as we discussed when talking about scope, each call to a function has its own set of the local variables. In this case, our function has just one local variable, n, but each recursive call, has its own n. When the call to factorial with an argument of 15 invokes factorial with an argument 14, those two invocations have their own n, the first with the value 15, the second with the value 14.

This actually explains why I said earlier that recursive solutions can often be less efficient than iterative solutions. In our iterative factorial function, we only had two local variables no matter what argument we called the function with. In our recursive function, though, we have a variable taking up memory for each recursive call, so say, invoking this recursive factorial function with the argument 1000 would require enough memory to store 1000 variables. When memory usage is a concern, this extra cost to recursion may be something to watch out for.

 

 

 

 

 

 

Something we want to do very often in code is deal with large sets of data. For instance, we want might a set of all the names of the presidents of the united states in sequential order. Notice though that there’s something very inconvenient and impractical if I have to assign each individual value in this set to its own variable. For starters, it’s silly that I have to contrive a unique variable name for each member of the set, but what’s much worse is what happens when I want to use every member: I have to use each member individually, leading to lots of code repetition. For example, to print each name, I would have to write a print statement for each variable. This is bad enough when I’m dealing with sets of a few dozen things; imagine how bad it would be when dealing with sets of thousands or millions or more.

 

 

 

Another problem with using individual variables for each piece of data is that we often want to deal with sets where the number of items may vary or may even grow and shrink during the course of the program. For instance, if we create a program that keeps track of student attendance, we want the code to work no matter how many or few students any class has. But if we use a variable to hold each student name, our only solution is to create an arbitrary number of variables and hope that no class ever has more than that number of students.

So rather than use individual variables for items in a set, we usually want to use a kind of value called a ‘collection’. A collection is a value which itself is made up of multiple other values. It’s a value which represents some set of things. The most basic kind of collection is a ‘list’. A list is a collection in which the items are ordered in sequence, such that the items are known by their relative order. So if you have say, five things in a list, one of those things is the first thing, another is the second, another is the third, another is the fourth, and one is the fifth, the last thing in the list.

To create a list in Pigeon, we use the list operator, whose operands make up the initial members of the list. So here the top expression returns a new list with three items: first the number 77, second a string “yo”, and third the number -6. The bottom expression returns a new list with no initial items: in other words, an empty list.

To access the items of a list, we use the ‘get’ operator, which takes two operands, first, a list, and second the index of the item to retrieve from that list. Here we create a list of three items and assign the list to a variable ‘will’.  The expression (get will 0) then returns the first item in the list, (get will 1) returns the second, and (get will 2) returns the third. I’m sure it strikes you as odd that the items are indexed starting at 0 instead of 1, but this is the dominant convention in programming, for reasons that will become evident in later units.

 

 

The len operator, short for length, returns the number of items in a list. Here, we have two lists, one with three items and assigned to the variable josh, the other with 1 item and assigned to the variable lisa. So the expression (len josh) returns 3, and the expression (len lisa) returns 1.

Using len, we can write a function printAll which takes a list of any length and prints every item in the list. To start, we assign 0 to a counter variable we’ll call i (as is the convention), and then we’ll create a while loop that executes as long as i is less than the length of the list. In the loop, we’ll retrieve the item of the list at index i and print it. Then we’ll increment i by 1. So if our list has four items, the loop will go through four iterations, with i having the values 0, then 1, then 2, then 3, and in the last iteration, i will be incremented to 4, which is not less than the length of the list, so the loop will end.

 

We can make a distinction between data which is mutable and immutable. Mutable data is data which we allow to change, whereas immutable data is data which we do not allow to change. So far we’ve introduced 6 different data types in pigeon: numbers, strings, booleans, the value null, functions, and now lists. Values of these types are all immutable, except lists, which are mutable. What this means is that we have operations for modifying lists, whereas we don’t have any operations for modifying the other types. You might think that the arithmetic operators like add and sub modify their operands, but actually what they do is produce new number values, leaving their operands unchanged. In the operation (add 3  5), the operands 3 and 5 remain unchanged; instead, the operation returns a new number value, 8. So with the immutable data types, we have operations which produce new values based on existing values, but the operations don’t actually modify those operand values.

 

In contrast, we have two operations in Pigeon which modify an existing list. The first of these operators is ‘set’. Set replaces an item in a list at a specified index with a specified value. Here, the list assigned to kim starts off with 3 values, 77 “yo” and 6, so when we first print the value returned by (get kim 1), the second item in the list, “yo” is printed. But if we then invoke set on the list kim specifying index 1 and a new value -53, then we’re modifying the list, changing its second item to be the value -53 instead of the string “yo”. So when we again print the value returned by (get kim 1), the value -53 is printed.

The other operator that mutates lists is append. Append adds additional items to the end of the list, increasing its length. Starting with an empty list assigned to the variable hugh, invoking (len hugh) will first return 0, but if I then append two items to hugh, invoking (len hugh) will return 2, and if I then append two more items to hugh, invoking (len hugh) will return 4.

 

To truly understand how variables work in Pigeon, you have to understand that variables in Pigeon are reference variables, meaning that they actually hold addresses, not actual values. When we create a new value in Pigeon, the language finds a space to store that value, but when we assign the value to a variable, the data assigned to the variable is not the value itself but rather the address of memory where the value is stored.

So consider this piece of code involving only immutable pieces of data, some numbers. The top line stores the number value 3 somewhere in memory, designates another place in memory for the variable zed, and writes at this location the address of that value 3. The second line, then, simply stores another number value, 5, and changes which address is written in the variable zed: instead of referencing the location of the value 3, zed now references the location of the value 5. In the third line, the sub operation stores a new number value 4 somewhere in memory, designates another place in memory for the variable molly, and writes at this location the address of the value 4.

So when we assign to a variable, it is really an address that is changed in memory, not any value.

 

But now, look what happens when we deal with mutable values. Here we create an empty list which we assign to the variable leo, and we assign the value of leo to bruce. What we have in memory then is a list stored somewhere in memory and two variables, leo and bruce, both holding the same address of that list. Both variables ‘reference’ the same list. Consequently, when we modify the list via one variable, the changes are visible when we access the list through the other. Here (len leo) first returns 0, but if we append an item to bruce, (len leo) then returns 1.

 

Because parameters are variables, and because variables are really just references, we say that arguments to functions, in Pigeon, are “passed by reference”. This simply means that it is the addresses of the argument values which are written in the parameter variables, not the values themselves.  Again, when dealing with immutable data, this distinction is not significant because you can’t change immutable things anyway. However, you do have to be cognizant when passing mutable values as arguments, because the function then might modify those values.

Here, for instance, we create a list which we assign to chris, and we pass this list as argument to the function ian. The function ian modifies its parameter with an append operation, so this change is reflected in chris. Before the call to ian, chris had the length 2, but afterwards, it has the length 3.

 

So as just discussed, variables really store addresses, not values directly. Well the same is true of lists. The items of a list are stored in the list as their addresses, not as values directly. The significance of this is that a list can be an item of another list, and in fact, a list can be an item in itself. Here for example, we create two lists. The first is assigned to joe, and then this variable is specified as the first item in the second list, so the first item in the second list is actually our first list.

To make a list an item of itself, we use set, such as here, where the list yves is set as the new third item of itself. Just be clear what’s going on in memory: the data of a list consists of a sequence of addresses, and now the third address in the sequence is the address of the list itself.

 

Another important distinction in programming is between the concepts of equality and identity.  When we say that two values are equal, we mean that they have the same type and the same content. So say, if you have two strings stored separately in memory, if both of those strings represent the same sequence of characters, then they are equal to each other. In contrast, when we say that two values are identical, we mean that they are not just equal, they are actually the very same value stored in memory. In other words, they are not separate values at all, but really just one value. So any value in memory is of course equal to itself, but it is also identical to itself.

Because multiple variables can reference the same value, it can be useful to have a test for whether two operands are identical. In Pigeon, this is called the I D operator. Here we create two lists with the same values, assigning one list to ed and the other to thom. Because they are both lists and with the same content, they are equal, but because they are two separate lists in memory, they are not identical.

 

A key is a value which is used to point at another value. It’s a value which uniquely identifies some other value. A key and the value associated with it are together known as a key-value pair. A key-value pair is an associative relationship: you have a value which is known by its association with another value, a key. Key-value pairs make up our other kind of collection type, what we’ll call dictionaries. Whereas a list is a collection of values organized in sequence and known by a numeric index, in a dictionary, there is no order: instead, there are just a bunch of key-value pairs in no particular order, and no two keys can be equal with each other because the values are indexed by the keys.

To create a dictionary, we use the dict operator. In the top expression, here, we create an empty dictionary, and in the bottom expression, we create a dictionary with two key-value pairs. The key-value pairs are written with the key first followed by the value, so in this example, the key 77 has the value “yo”, and the key “avast” has the value true. Again, be clear that there is no sense of order among the key-value pairs, so it doesn’t matter which order we write them in.

 

The operators len, get, and set can all be used on dictionaries. Here we assign to ted a new dictionary with two key-value pairs, the key 5 with the value 2, and the key “yo” with the value -1. (len ted) first returns 2 because the dictionary has 2 key value pairs. (get ted “yo” 0) returns -1, the value of the key “yo”. (set ted “yo” 8) changes the value of the key “yo” from -1 to 8. (len ted) still returns 2 because the number of key-value pairs has not changed. (get ted “yo”) returns 8, the current value of the key “yo”. (set ted 21 false) creates a new key-value pair, a key 21 with the value false. (len ted) then returns 3 because the dictionary now has 3 key-value pairs.

 

Like lists, dictionaries are mutable, so we have to be cognizant of when they are modified. Here we assign an empty dictionary to a variable cow and also to a variable goose. (set cow “name” “Fred”) adds a key “name” with the value “Fred”, and then (get goose “name”) returns “Fred” because goose and cow reference the same dictionary.

 

So when might you want to use dictionaries? Well imagine you have a program in which you need to create information about a bunch of people. One solution would be to have a bunch of lists, such that one list stores their names, another stores their addresses, another stores their phone numbers, and so on. These lists would be kept in sync such that the info of one person is stored at the same index in each list; for example, the address at index 5 of the address list should be the address of the person whose name is at index 5 of the name list. While workable, this solution is error prone. The better solution is to create a single list of dictionaries, where each dictionary holds the info of one person, e.g. the person’s name is stored as the value of the “name” key, and the person’s address is stored as the value of the “address” key.

Here we have a function we might use to create these dictionaries, a function which takes a name, age, and social security number and returns a new dictionary with those values. We could then call this makePerson function like so, with the string “Mike Smith” for the name, 43 for the age, and 5555555555 for the social security number. The function would then return a new dictionary with a key “name” with the value “Mike Smith”, a key “age” with the value 43, and a key “ss” with the value 5555555555.

 

So that’s everything to know about Pigeon. I imagine you’re wondering what makes real languages different?

Well first off, as we already discussed, Pigeon has no way of doing interesting input and output beyond simple text input and output on the console. If pigeon were a real language, we’d have some means of doing things like reading and writing files, getting mouse input, and drawing graphics on the screen.

Other things which Pigeon deliberately lacks are conveniences, such as an easier way of writing loops that isn’t so verbose.

Lastly, all of the tiny programs we wrote were all written as one file of source code. In any non-trivial program, though, you’ll want to separate your source code into multiple files for organizational purposes because, past a few hundred lines, keeping all of your code in one file becomes more and more impractical. So real languages give us ways to modularize code into separate source files.

All of this said, aside from input/output, conveniences, and modularization of code, most real languages don’t have all that much going-on conceptually which you haven’t just seen in Pigeon.

Comments are closed.