00:00:11.570
Let's do this thing! Welcome to "Four Programming Paradigms in 45 Minutes."
00:00:16.680
When I proposed this talk, I did not think they would accept it. When I got the acceptance, I thought, 'What the heck am I going to do?' There are 190 slides in this talk; it's going to be fast! Get ready to hang on.
00:00:27.689
I'm Aja Hammerly, I'm on GitHub as @aHammerly, and I will be posting the code from this talk later today. I need to finalize some licensing issues before I can get it out.
00:00:39.930
I tweet as @aHammerly, and assuming the Internet and automation work properly, I have tweeted the slides. That will provide you with a link to my website, www.ajahammerly.com, where I blog and have the slides for most of the talks I've given.
00:00:45.329
Oh, and I like dinosaurs! I work on Google Cloud Platform as a Developer Advocate.
00:00:56.040
If you have any questions about Google Cloud, Kubernetes, App Engine, BigQuery, or all that stuff, you can come and ask me. I have three colleagues with me here today. Two are up here right now, and one is attending a different talk so he can learn from different people. There's probably going to be a birds-of-a-feather or lunchtime session, so watch my Twitter for announcements.
00:01:07.079
And since I work for a very large company, the lawyer has told me to mention that "Any opinions expressed are my own and do not reflect the views of Google." Just covering the formalities!
00:01:30.869
This talk is based on a class I took in my freshman year of college, which we called CS 60, although the actual title was 'Introduction to Principles of Computer Science.' Unlike a lot of CS majors, this course was very early in the major, and it surveyed all of computing.
00:01:54.919
We studied finite state automata, grammars, provability, and complexity theory, and formal logic. About 10 to 12 weeks of the course was dedicated to learning four different programming languages, each representing a different paradigm. We solved the same problem in each of them, and we tackled problems designed specifically for each language.
00:02:08.009
I learned a lot from this course, more than any other class I took in my major. This course made me the computer scientist that I am today. The biggest takeaway was about abstraction.
00:02:20.250
When I started this class, I knew Java, some Visual Basic, and some Basic. However, my understanding of concepts like arrays and conditionals was tied to the syntax of those languages. I thought about these concepts in terms of syntax. But by being forced to learn four completely new languages in a very short period of time, I was able to move those concepts from being linked to syntax to being actual abstractions in my mind.
00:02:39.010
If you're familiar with philosophy, you might recognize Plato's allegory of the cave; that gives you a good idea of what I'm getting at here.
00:02:53.019
Another insight I gained was that I too could be a polyglot. I was always impressed with people who knew a lot of programming languages, but when you learn three new languages in nine weeks and can be productive with them, you realize that once you grasp the underlying concepts and abstractions, the syntax isn't that hard to master.
00:03:09.250
As a polyglot, you can identify similarities between language concepts like conditions, collections, and arithmetic—these ideas repeat across various languages in different ways. Understanding them conceptually, rather than fixating on the specific syntax, proves incredibly helpful when programming in multiple languages.
00:03:32.109
Moreover, I learned that there are significant differences between programming languages. Different languages excel at different tasks. I'm hoping that you attendees will take some of this knowledge away from this crash course.
00:03:40.659
While I attempt to cover what I learned in 18 weeks in just 45 minutes, don't worry if you can't keep up. This talk is primarily an exploration of ideas, despite the rapid pace.
00:03:48.159
When I took this class, our primary example was solving the Towers of Hanoi puzzle with the little rings and pegs. However, explaining that algorithm in four different languages would take more time than I have today, so we're going to use something much simpler. We'll talk about making change. I will show you how to calculate the amount of change you would provide if you were a cashier working a cash register.
00:04:18.909
So, everyone following? Let's dive straight in! We're going to start with Ruby. I will highlight the code in my slides to make it clear.
00:04:31.210
We're going to begin with something easy. The code gets progressively harder as we move along, but let's talk a little bit about Object-Oriented Programming (OOP). Everything in Ruby is an object. Everything is an object, even false. False is a singleton instance of an object, while the boolean 'true' is also an object.
00:04:53.350
Your classes themselves are instances of the object class. Not all languages are this pure, but the general idea in OOP is that most things, if not all things, are indeed objects.
00:05:06.090
So, what's an object? An object encapsulates state and behavior. State refers to fields, attributes, or instance variables—what you call them can vary depending on the language and your background. Behavior is what you do with that state; it involves methods.
00:05:30.510
In most programming languages, the object is responsible for modifying its own internal state. In Ruby, we refer to this as 'self.' If I were an object, I could say, 'self.pets = ['Nick', 'Shy']' because those are the names of my cats.
00:05:53.350
Objects must interact with each other because, let's face it, an object just sitting there by itself is rather boring. The way they communicate in Ruby is through message passing.
00:06:06.390
For example, if I want to find out the length of an array, I send the message 'length' to an instance of an array object. That object calculates the length of its internal state and then returns that length to me.
00:06:18.430
When teaching, I normally try to use my own examples, but since we're going super fast today, I'll stick to canonical or commonplace examples found in the literature.
00:06:30.890
One of the most common examples is the concept of a bank account. Let's build a bank account object. Objects are instances of classes, so we define a class called 'BankAccount.' Bank accounts need to have a balance, and for several reasons, it's a bad idea to allow external access to modify that balance, which is my internal state.
00:06:53.780
So, I'm going to store the balance as an instance variable and set it to zero when I initialize the class or object. Note that I will represent money as an integer number of cents throughout this talk. If you're representing money as a float in your programs, come talk to me later, and I will explain why that is a horrible idea.
00:07:15.830
Now, I'm going to take a break for IRB. I can create a new bank account and retrieve an account object back. Since I wrote the code, I know the balance is zero, but I can't see it, so let's write an accessor. I'm going to create a reader method because I don't want anyone outside of the class to be able to set the balance. This method will return the balance.
00:07:32.920
Now, I can see that my balance is zero. However, a bank account with a balance of zero is pretty much useless. So, I'm going to add methods for withdrawing and depositing money. The deposit method will increase the balance. Deposit is a message that takes an amount and adds it to the balance.
00:07:49.990
Withdrawal is the opposite; it takes an amount and subtracts that from the balance. You can see from my IRB output that it works.
00:08:07.920
So, in this case, the data of the object is the balance, while the methods—deposit, withdraw, and initialize—are the behavior. All of these methods modify the internal state of the object, and my IRB process communicates with them by passing a message, like 'deposit' with an amount, trusting that the object will manage the data correctly.
00:08:24.130
Some strengths of OOP include its capability to model real-life concepts. For instance, we can create a chair object with attributes like color and methods that represent its behavior, such as 'supporting weight.' We think about the world in terms of concepts that align closely with objects.
00:08:46.480
Furthermore, objects are reusable. Think about the standard library: arrays are objects, hashes are objects, and strings are objects. We use these in many ways because the same types of concepts and objects repeat throughout the problems we're trying to solve.
00:09:00.780
And thanks to OOP, I don't have to implement methods like 'length' for arrays over and over again. Additionally, I believe objects are easier to test. I can test an object in isolation to ensure that it modifies its own behavior correctly, and then I can test the interactions between objects when assessing the system as a whole.
00:09:12.850
Now, let's move on to an example. We'll write the making change algorithm using OOP.
00:09:21.920
Here's the code. I am showing it in a larger font, but I don't expect everyone to be able to read it all at once, so we will build it up piece by piece.
00:09:36.860
I will create a class called 'CashRegister' because that's what I use to generate change. The cash register has a cash drawer, which slides out and contains various denominations of bills and coins—$20s, $10s, $5s, and $1s, as well as quarters, dimes, nickels, and pennies.
00:09:50.570
If I were doing a more thorough implementation, I would include the amounts of each denomination in addition to just having their values.
00:10:04.410
Here is the method that makes change. I will show you the method signature as well. The 'makeChange' method takes two arguments: the amount owed to the customer and the amount the customer has tendered, which you will frequently hear referred to as 'tendered' instead of 'tender love'.
00:10:18.370
The first thing I need to do is determine how much change I need to give the customer, which will be the difference between the amount tendered and the amount owed. To represent the denominations of bills and coins I need to provide to the customer, I'll use an array called 'change.' This array will inform the cashier how many fives, how many ones, and so on.
00:10:43.690
Next, I need to figure out which part of the drawer I am working with. I have seen many people start from one end, either the smallest or largest denomination, then move down the drawer and grab the correct amount before moving to the next slot.
00:11:03.580
I will implement that same logic with my drawer array, using an index 'i' to track my position.
00:11:11.210
Here is the start of the loop. While I still have change to give the customer—and while the difference is greater than zero—I will iterate through this code.
00:11:22.920
Let's expand the loop a little. Here’s the first part: if the difference—the amount I still need to give the customer—is less than the current denomination I'm looking at, I'll want to advance my index and look at the next smallest denomination.
00:11:43.630
In cases where I'm giving $4.50 in change but I'm looking at the $20 denomination, I can’t give the customer a $20 bill, so I'll skip to the next index.
00:12:04.150
I'm making an assumption throughout the entire talk today that my change drawer is always sorted from largest to smallest denomination. If it isn't, none of these algorithms will work. Once done, I'll return to the start of the loop and try again.
00:12:31.390
The next part is where, for instance, I am giving $4.50 in change, but I'm looking at a $1 bill. That's not bigger than what I need to give, so I can use that bill.
00:12:45.300
I will add it to the list of changes I'm giving and then subtract that amount from what I still owe the customer. Then I go back to the top of the loop and keep going. Eventually, I will arrive at the proper change.
00:13:01.510
So, for those of you who believe that this is not OOP, you're absolutely correct; this example is not great for demonstrating OOP. However, this is a suitable problem for demonstrating the other three paradigms I'll focus on today.
00:13:15.300
Next, let’s discuss functional programming using Racket, a general-purpose programming language in the Lisp family.
00:13:29.600
If you’ve never heard of it, Lisp is the second-oldest multipurpose high-level programming language, after Fortran. Lisp stands for 'LISt Processor.' While Racket and Lisp are well suited for demonstrating functional programming, you can also use Ruby for a functional approach.
00:13:46.430
Today, I will focus entirely on pure functional programming, which means my functions never store state and never mutate incoming data. If you provide me with an array, I will return a new array. In other words, I won’t modify the one you provided.
00:14:04.790
So, no bang methods here. The beauty of the pure functional style is that the output only depends on the input; it does not depend on what has occurred prior. If I perform the same input multiple times, I will always receive the same output. History doesn’t matter at all.
00:14:16.630
One of the fundamental principles of functional languages is that data and procedures—state and behavior—are separate, unlike OOP in which they are encapsulated together.
00:14:31.080
I will use Racket's syntax since it is different from Ruby's infix notation. Racket uses prefix notation instead. For example, to add three and five, I will use '+ 3 5.' This may seem odd, but it's useful because I can do something like '* 1 2 3' to multiply three numbers together—something that you can’t do in Ruby with infix notation.
00:14:53.760
You might wonder how one can handle multiple levels of nesting. The answer lies in utilizing parentheses. For instance, to multiply three and five and subtract six from ten, I would write '(- (+ 3 5) 6). The order of operations becomes extremely explicit.
00:15:12.500
Math isn't particularly interesting on its own; I need to be able to write my functions. To declare a function in Racket, I use the word 'define,' followed by the function name and its argument list inside parentheses. For example, I can define a 'square' function that takes one argument 'n', and the body of the function simply multiplies 'n' by itself.
00:15:32.970
To call that function, I write 'square 5,' which returns 25.
00:15:48.090
I also need to implement conditionals, and I'll use Racket's 'cond,' which acts like Ruby's case statement.
00:16:04.950
The first line is a test, followed by the actions to take if that test is true. There can be multiple tests and actions, as well as an 'else' statement for additional conditions.
00:16:16.530
Here’s a concrete example: this function calculates the absolute value of X. If X is greater than zero, the function simply returns X. If X is zero, it returns zero. For all other cases, it returns the negation of X.
00:16:36.560
Now, as I mentioned, lists are essential in Lisp. I can represent them as sets of items separated by spaces, enclosed in parentheses.
00:16:50.060
The prefix notation means I have to call the first element of a list using the 'car' function and can retrieve the rest of the items in the list with 'cdr.' To create a list, I use 'cons' to prepend an item to an existing list.
00:17:06.470
Now, let’s look at a simple function defined in functional style to calculate a factorial. If the number is less than or equal to one, I return one; otherwise, I multiply n by the factorial of n minus one.
00:17:27.640
Next is the Fibonacci function: it calculates the nth Fibonacci number. If n is less than or equal to zero, it returns zero. If it is equal to one, it returns one. Otherwise, it returns the sum of the two preceding Fibonacci numbers.
00:17:43.220
Functional programming has its strengths. Mainly, if I’m using pure functional programming, I don't have to worry about the complexities of concurrency or threading, since we are not sharing any memory or locking tables.
00:18:04.020
Furthermore, functional programs are often easier to test because the input-output relationship is far simpler. I can set the data for testing without needing to state the object first.
00:18:19.300
Another advantage is that I can reuse pure functional code. If it runs in one program, I can easily throw it into another without worrying about requiring context.
00:18:32.450
Short functional programs tend to be especially concise, particularly in Lisp, but while many people dislike it, it brings me joy.
00:18:46.010
Now, let's illustrate the change-making algorithm in Racket. I'll slow down a bit here to ensure understanding. This function takes two arguments: 'x' (the amount of money) requiring change, and 'denoms' (the denominations of bills and coins available in the cash drawer).
00:19:02.830
The first condition checks if the amount is zero, in which case, I can return an empty list because no change needs to be made.
00:19:23.750
The next check verifies whether there is any cash in the drawer. If there are no denominations available, I can't make change, so I'll return 'false.'
00:19:44.140
The tricky cases arise when I'm attempting to make change with a denomination that exceeds the amount I'm seeking. I will utilize 'car' to extract the largest bill currently being considered.
00:20:07.640
If the amount I want to change is less than the first denomination, I will call myself recursively without using that denomination. If my amount surpasses it, I can add that bill to the output list and return the remaining amount, executing the same recursive call.
00:20:25.870
It’s much shorter than the Ruby version. I find it to be logical; it might feel familiar if you have a background in number theory or understanding induction—recursion often appears comforting.
00:20:38.830
While this is not the shortest solution we will encounter today, that honor goes to Prolog. Moving onto logic and constraint programming, brace yourselves—this part will likely be the most brain-bending!
00:20:59.050
In Prolog, we work based on formal logic. For instance, Socrates is a man, all men are mortal; therefore, Socrates is mortal. I would represent various facts about the world within Prolog.
00:21:20.820
Prolog programs consist of facts and clauses—not typical program instructions. The unique part is that instead of explaining how to achieve the outcome, Prolog requires us to clarify what the situation entails.
00:21:39.060
I can state claims like, ‘The man in the yellow house doesn't own the fish’ or that ‘the man who enjoys rum lives next to the cat owner’. Prolog uses its gathered knowledge to construct a world where all stated facts are accurate.
00:21:59.090
The variables in Prolog begin with capital letters, while constants start with lowercase letters. Each fact ends with a period, such as 'Washington is a state' or 'Washington borders Oregon.' I can define rules that specify relationships based on these facts.
00:22:17.080
For instance, I can define an adjacency rule which states that 'X and Y are adjacent if X borders Y.' Prolog's execution involves pattern matching: it attempts to substitute variables for constants, find matches, and fulfill conditions detailed in the rules.
00:22:41.300
Now, here is the adjacency rule demonstrate by providing facts about borders. You can enter queries into an interactive Prolog terminal, asking questions like, 'Is Washington adjacent to Oregon?' Prolog will respond affirmatively, while reversing it may yield a negative response.
00:23:01.550
I have to explicitly state that adjacency is symmetrical; thus, if I say 'X is adjacent to Y,' Y should also be considered adjacent to X.
00:23:19.540
Let me share one of my favorite Prolog jokes: How many Prolog programmers does it take to change a light bulb? The answer is: 'No.' I aim to go over some basic examples, using a well-known canonical scenario—building out a family tree.
00:23:39.900
Let's illustrate with the Simpsons: the first fact states that Homer is Bart's father. Note that the word order differs slightly from standard English.
00:23:56.240
Similarly, I can establish that Marge is Bart's mother and that Homer is Lisa's father. When I ask Prolog, ‘Who is Bart's mother?' the terminal reveals, ‘Marge.’ I can use a semicolon for more results.
00:24:12.720
This flexibility allows me to explore the rules either way; Prolog can run both forwards and backwards, which feels strange but is incredibly powerful.
00:24:29.290
Now, let’s tackle a slightly more complex situation. I can define a sibling rule: X and Y are siblings if there exists a Z such that Z is the mother of both X and Y. Additionally, Z could also be their father.
00:24:45.770
The rule ensures there are conditions for sibling relationships, ensuring X and Y are not identical. This allows Prolog to examine various relationships dynamically.
00:25:00.540
Next, Prolog also handles lists, just like Racket and Ruby do. Lists can vary—these could include numbers mixed with constants or nested lists.
00:25:17.670
To pattern match on lists, however, Prolog employs a specific notation. This notation is a bit tricky: 'F | R' indicates that F is the first element while R represents the rest.
00:25:31.850
If I take a list like [1, 2, 3], I can say that F matches 1, while R matches the list [2, 3]. This is a different take on the 'car' and 'cdr' functions in Racket.
00:25:46.960
Interestingly, the underscore in Prolog signifies an unused variable, or a value that can be disregarded.
00:26:04.490
Next, I have a rule to determine membership: X is a member of the list if it appears as the first item or if it is contained in the rest of the list. Phrased logically, X must also belong to the rest of the list.
00:26:26.390
Similar strengths arise with logic programming, such as running queries backward and forward.
00:26:40.080
I can apply Prolog to real-world scenarios like scheduling and resource management in labs. For example, if multiple users require a resource at the same time, Prolog can help formulate solutions.
00:27:02.950
Time to make some change in Prolog! The intriguing aspect of Prolog is that I don’t employ a return statement—everything we need goes into the method signature.
00:27:21.770
The change rule involves three arguments: the amount required as change, the list of bills and coins we have, and how we will make change with those coins.
00:27:41.390
The first case tackles how to make change for zero. The amount zero gets the empty list, and I don’t need to know the cash drawer contents; that’s why I utilize the underscore.
00:27:58.400
The other case defines that I can make change for amount A by using the first value from the cash drawer. I can only use that if A is greater than the denomination I’m looking at.
00:28:11.840
We’re exploring point cases where I will not use the first element of the list in satisfying the change and will instead use the remaining elements.
00:28:38.290
This last example looks peculiar to newcomers, but once you've used it, Prolog proves to be enjoyable and potent. This was the most complex example we’ll tackle today.
00:28:50.700
Let's transition to a simpler paradigm: procedural programming, which we will demonstrate using assembly.
00:29:03.760
Assembly is a more traditional programming language employing a limited standard library, along with a modest collection of functions—less than 30.
00:29:23.460
I am utilizing assembly from a resource commonly referred to as 'Nand2Tetris.' I’ll provide a bibliographic entry later for those interested.
00:29:46.000
Assembly syntax includes utilizing registers A and D—these will only allow operations on a limited basis as shown in this format.
00:30:01.750
I’ll detail the computations I can execute, such as D = D + 1, A = A - 1; these are fundamental operations We can assign values into the registers or memory.
00:30:14.650
To load constants in, we use an '@' followed by a constant. We can set labels in our programs to access other areas directly.
00:30:30.680
The structure for jumps has a specific format and requires a condition; these jumps only refer to whether D is greater than zero.
00:30:44.130
Next, I will detail how to sum digits from 1 to 5. The first step is to store zero into memory cell 0, establishing a baseline for the sum.
00:31:03.440
I will store five in memory cell 1 to act as my termination point. I will manage my loop through these cells; this requires me to adjust the values and save them accordingly.
00:31:21.620
As I noted earlier about procedural programming: we likely started with straightforward models—our first programs were procedural, like 'Hello, World!.' It's instinctive for many of us to function in this manner.
00:31:37.650
Now, going back to the change-making process, I have an algorithm set up in assembly that works upon the principles laid out before.
00:31:56.660
Again, without lists, I will use separate memory locations to manage the different coin denominations. In this scenario, it operates using straightforward logic.
00:32:12.020
I aim to manage the amounts within the registers while adjusting memory locations to track how many coins I've used versus how many I have left.
00:32:32.870
I have very little time remaining, so I’d like to conclude this quick look into functional programming.
00:32:48.460
To further your understanding of functional programming, check out Jim Weirich's keynote on that subject from RubyConf 2012.
00:33:03.890
For additional resources, explore 'The Little Schemer' series or 'Structure and Interpretation of Computer Programs' for fundamentals from a functional perspective.
00:33:25.610
I presented a simplified version of Prolog at Cascadia Ruby 2012. You can find several other Prolog programming resources to expand your understanding.
00:33:39.290
If you're keen to learn how your computer works, I highly recommend the book 'Elements of Computing Systems: Building a Modern Computer from First Principles.'
