The above is the original. Timestamps below are from the CodingTech republication. Code reproduced below is copyright Google and licensed Apache 2.0.
Intro
[0:04] “CS60: Introduction to Principles of Computer Science”: a survey of all of computing: finite state automata, grammars, provability and complexity theory. Formal logic.
[0:27] About 10-12 weeks of the course was dedicated to learning 4 different languages, each representing a different paradigm, solving the same problem in all of them, and problems designed for each language.
[0:45] My concepts of things like arrays were attached to the syntax of each language. By learning 4 different languages in a short period of time, I was able to move those concepts from attachment to syntax to abstractions in my mind.
[1:17] Different languages are good for different things.
[2:42] The example we’ll use is change: how much change you should give if you were a cashier working the cash register.
The Object-Oriented Paradigm
[3:09] In Ruby, everything is an object. False is a singleton object. Null is an object. Classes are instances of Class. Not all OO languages are this pure, but generally in an OO language, most, if not all, things are objects.
[3:26] What is an object? An object is a way of encapsulating state and behavior. State are things like fields, attributes, instance variables. Behavior is what you do that state, e.g. methods.
[3:43] Most OO languages, the object is responsible for modifying its own internal state. In Ruby, this is self.
[4:00] Objects have to interact with each other. In Ruby, this is done with message passing.
[6:25] All of these methods modify the internal state of the object, and my IRB process is communicating with these methods by passing a message and trusting that the object is going to do the right thing with that data in that message.
[6:39] One of the strengths of OO is that it’s very good at modeling how we think of the world. Take a chair. It has an attribute color. It has a method “hold me up.”
[6:57] Objects are also reusable. A good way to think of this is the standard library. Arrays, hashes, and strings are objects. This means I don’t have to implement array over and over.
[7:17] Objects are easier to test. I can isolate objects, and relationships between objects.
[10:40] This is a very bad example to demonstrate OO. Rather, this demonstrates why different languages are good for different things!
The Functional Paradigm
[10:55] Racket is a functional programming language in the Lisp family. Lisp, or List Processor, is the second oldest multipurpose, high-level programming language (FORTRAN is older).
[11:14] Racket and Lisp are both excellent for demonstrating functional programming, but they’re not limited to that paradigm.
[11:25] Functional languages are built on functions! Functions take in data, and output data.
[11:37] Pure functions never store state and never mutate incoming data.
[11:54] The nice thing about pure functions is that output only depends on input. So you can do a bunch of stuff, and the output remains the same. History doesn’t matter.
[12:09] Fundamentally, state (data) and behavior (procedures) are separate. (This isn’t entirely true.)
[12:32] Lisp and Racket use prefix notation (vs. infix or postfix notation). Operators are not limited to just two arguments. The order of operations is very explicit.
[16:07] Strengths of functional programming. If I’m not modifying state at all, then I don’t have to worry about concurrency and threading. We’re not sharing memory. We’re not locking tables.
[16:30] Data in, data out. Easy to test, especially in pure functional programs. Setup is “this is the data,” no state setup.
[16:44] Reusable. Can take a function from one program and throw it into another. No worries about required context.
[16:50] Functional programs are brief.
[19:31] If you’ve got background in number or mathematical theory, and you’re used to proofs by induction, this will feel comfortable.
The Logic/Constraint Paradigm
[20:05] Prolog is based on formal logic, like Socrates is a man, all men are mortal, therefore Socrates is mortal.
[20:24] Prolog programs aren’t made up of instructions. Rather, they’re made from facts and clauses.
[20:30] Instead of describing the HOW, it describes the WHAT.
[20:50] “The guy in the yellow house does not own the fish.” “The man who drinks rum lives next to the guy with the fish.” Prolog will take all these facts and tries to come up with a world where all these facts are true.
[21:24] Variables start with a capital letter. Constants start with a lower-case letter. Facts end with a period. Rules specify relationships between facts.
[21:52] The :- sign defines a logical implication.
[22:54] Prolog is incredibly literal. Since I’ve only specified that Washington and Oregon share a border, but not Oregon and Washington share a border, Prolog doesn’t know that the reflexive case is true. This can be done with adjacent(X, Y) :- border(Y, X).
[23:30] How many Prolog programmers does it take to change a lightbulb? No. No is the answer.
[23:40] The canonical example in Prolog is to build a family tree.
[26:10] To pattern match on lists, use bar notation.
[27:00] Underscore _ is called “meh” in Racket. In Prolog, it’s called “don’t care,” this variable isn’t actually used into any logic.
[28:04] Strengths. Flexibility: You can run the code forwards and backwards, in a logic language.
[28:27] You can enter in all your constraints (as facts). Then Prolog can solve for the solution.
[29:02] The biggest context switch: no concept of a return. Everything’s encoded in the method signature (this is required to allow running the code backwards).
[32:05] Prolog is hard! Needed a debugger to write this, and didn’t need it for assembly.
The Procedural Paradigm
[32:16] Assembly is old-school programming. Limited vocabulary, limited standard library, limited number of functions we can call. There are tons of assemblies that exist. We’re using an assembly called nand2tetris — it’s less ugly and very simple.
[32:55] We have two registers, A and D. They’re the only two things I can do operations on. D = data register. A can be a data register, or an address register. If A is an address register, then I pull whatever value is in A and I go pull that cell out of memory. In cases where I’m using A to access memory, I’m going to call that M.
[33:24] I’ll be using A, D, and M. In the cases where I’m using A to access memory, I’m just going to call that M. If I call something A, I’m using the value of A.
[33:29] In Racket, car stands for “contents of the a register”. cdr stands for “contents of the d register”.
[33:40] I have A + D, D - A, A - D, [A or D] - 1. I have bitwise not, and and or: ! & |. I can negate A or D: - [A or D]. Any places I use A, I can use M, like M + 1, and D + M. This is everything I can do! No multiplication, division. Nothing that remotely looks like lists.
[33:25] But I can assign values to registers and to memory: D = M + 1, D = D - A. I can also do multiple assignments: MD = A + 1. M and D both get the value of A + 1 (though this here is a bad idea).
[34:50] I need to be able to get constants into my program. I can do this at-syntax with @Integer. Constants can only go into the A register (that’s why it’s called “at”), e.g. @100, @Label. I can use @Label to access the line of the program on which the label is on. I use this for jumps.
[35:15] Jumps are this format: val;jump type. For example, with D;JGT (Jump Greater Than), I will jump to whatever line of the program in the A register if D is greater than zero (the only reference is zero).
[35:39] JEQ (Jump Equal To). So, 0:JEQ will always jump, since 0 is always equal to 0. JGT, JLT, JGE, JLE. JMP = non-conditional jump. These are the only forms of branching in Assembly.
[36:30] Summing digits from 1 through 5:
[38:04] There are no strengths (to Assembly). But procedural style itself can be useful. You can write procedural style in any language. It’s simple. Scripting is generally procedural. Easy to write (though not in Assembly).
[38:38] I don’t have lists so I’m going to use
M0: Amount to makeM1–M4: Coin denominationsM5–M8: Number of each coin to use
[39:39] Learn more about Functional
- Talks
- (Parenthetically Speaking) by Jim Weirich (GoGaRuCo 2010)
- Functional Principles for OO Development by Jessica Kerr (Ruby Midwest 2013)
- Y Not — Adventures in Functional Programming by Jim Weirich (RubyConf 2012 Keynote)
- Books
- The Little Schemer. Friedman, Daniel & Felleisen, Matthias. Written in Socratic dialogue.
- Structure and Interpretation of Computer Programs. Abelson, Harold et al. Long textbook on fundamentals of computer science from a functional perspective.
[40:08] Learn more about Logic
- Talks
- A Taste of Prolog by Aja Hammerly (Cascadia Ruby 2012)
- Books
- The Art of Prolog, Sterling, Leon & Shapiro, Ehud.
- Clause and Effect: Prolog Programming for the Working Programmer. Clocksin, William F.
- Prolog Programming for Artificial Intelligence. Bratko, Ivan
[40:15] Learn more about Procedural
- Books
- The Elements of Computing Systems: Building a Modern Computer from First Principles. Nisan, Noam & Schocken, Shimon. You start with logic gates, then a very small version of Java, including the assembly, machine code, VM.
[40:40] General
- Books
- Seven Languages in Seven Weeks: A Pragmatic Guide to Learning Programming Languages. Tate, Bruce A. A classic.
- Exercises in Programming Style. Lopes, Cristina Videira. This talk in book form, but better! Explains how to write many different programs in different languages.
[41:00] Closing Thoughts: You can learn different languages. Programming languages are not that different. Everything has conditions, accessing memory, integers, mathematics. Go learn other languages.
Personal Thoughts
- Using Prolog for machine learning is seductive. But growing fact and rule databases can become unmanageable. Pattern matching can be more difficult to generalize than artificial neural networks, and (currently) produce worse practical results. Additionally, some rules can be hard to express (e.g. “this photo contains a crosswalk”). On the other hand, the symbolic logic of Prolog (and logic programming in general) is more easily interpretable, and generally need less data, than deep learning, connectionist systems. Reminds me of Logical vs Analogical, or Symbolic vs Connectionist, Neat vs. Scruffy, by Marvin Minsky, 1991.
- That said, “deep learning is a statistical methodology for clearly ordered tasks, whereas Prolog is designed to understand and create inferences of the data it analyzes. Thus, Prolog systems are well suited for less defined jobs that may require modest judgment calls or outputs that aren’t necessarily categorical.” This article advocates for pairing deep learning, which can “identify [relevant data], as well as what features of that data make them so.” Then “Prolog mechanisms could then make intelligent inferences about how that data applies to a specific [item of interest], or others sharing similar attributes.”
Other Links
- https://hackr.io/blog/programming-paradigms
- https://towardsdatascience.com/deep-learning-and-machine-learning-c1101debe0c (2015)
- http://web.engr.oregonstate.edu/~walkiner/teaching/cs381-wi20/slides/6.LogicProgramming.pdf
- https://www.matchilling.com/introduction-to-logic-programming-with-prolog/