Scheme — Where I First Learned Machine Learning and AI

Image for post
Image for post

Machine Learning has been all the rage lately, but some of us were introduced to it decades ago. I first encountered it in my artificial intelligence class (6.034 back in my day) at MIT. When I took the class, it was taught by Patrick Winston, who wrote the book that was considered the definitive guide on artificial intelligence at the time. That book is still used in a lot of places, but I’m sure it has been replaced by other books that have expanded on the ideas and include more discussion about modern frameworks that have made this subject more tangible.

Scheme/Lisp Basics

The class was taught in a language called Scheme. For those who don’t know about scheme, it is a dialect of LISP (also known as Lots of Irritating and Silly Parentheses). LISP and its dialects use parentheses to enclose expressions. The syntax is sometimes known as Polish Notation, but LISP is more explicit about the grouping of operators so that programmers don’t have to think so hard about the calculation stack. For example, this is an expression written in Polish Notation:

These expressions are generally evaluated from right to left, and the interpreter that interprets this statement uses a stack. So the first thing it does is push 1 onto the stack, followed by pushing another 1. Then it encounters the plus, so it pops both 1’s off the stack and adds them, pushing 2 onto the stack. It translates to this (the numbers in square braces represent the stack after each step):

Developers used to write expressions like this all the time, and it was slow and cumbersome, and so LISP added the parentheses to make it clearer what was happening. The above expression could instead be written like this:

At first glance, this may not seem much better, but you can easily see how things get reduced:

Because of this, it was much easier to write and understand what a LISP program was doing versus the old stack based expression.

The above example demonstrates numerical computations in LISP, but it also has functions as well. Data structures in Scheme are made up of lists. For example, I can define a variable x to be the list of the first five integers:

car and cdr

Accessing the data inside this structure uses two main keywords, car and cdr. These functions return the first element of a list, and the rest of the list, respectively. This means:

You can probably see that accessing certain elements of the list can get kind of tricky. For example, to get the 4th element of the list (4), you need to do this:

The expression works in the reverse order of how it reads from left to right — you have to remove 1, 2, and 3 using cdr and then use car to get the first element of the list (4 5). Suffice to say that this language comes from a time when programming languages were much more primitive.

Lambda Expressions

There was, however, some concepts in the Scheme language that are just now reemerging into programming languages. One such example of this is called a lambda expression. These expressions were introduced to Java in the 1.8 JDK, but they actually have been around as a programming construct for more than 30 years.

A lambda expression is essentially an expression that doesn't evaluate immediately but instead requires values for placeholders to be provided in order to be evaluated. For example, I can define a lambda expression in scheme and set it to a variable:

This essentially defines an expression that adds its inputs together. It is kind of like defining a function except that it actually gets stored in a variable and can be passed around (a pointer to a function is kind of a good analogy, but lambda expressions are more like data that can be stored on the stack as opposed to just pointing to some instruction in the program data space). You can then evaluate the lambda expression like this:

So why would anyone do this? A good example is the factory pattern. Say I want to build a custom expression that multiplies one argument by a multiplier that is a parameter to the factory. For example:

The factory itself is a lambda expression that returns another lambda expression. I could make a triple multiplier and use it like this:

Or imagine an even more complex example where the factory creates an expression that does any operation with a parameter:

This is a simple example, but you can imagine building expressions that efficiently compute expressions based on configuration parameters. In the machine learning world, we are often doing complex computations with parameters that require tuning, so we needed a way to be able to define the computations with placeholders that could be changed as we trained the network to be more accurate.

Python of course allows us to create factory methods, but the principles are essentially the same:

Python also has lambda expressions as well (this is a simple example, but the body of a lambda expression can be as complex as any method):

Conclusion

This article was a walk down memory lane for me. When I first started coding at MIT, it was strange and unusual, but now that I look back, the principles I learned back then are still a foundation for things I am doing these days. I’m really fortunate that I was able to go to a place where they taught me these fundamentals so early on, and now the rest of the world is catching on. Scheme isn’t really as widely used any more, but if you dig around, it’s still out there. Scheme 9.2 was released back in 2014.

Originally published on December 18, 2017.

Written by

I'm a technology enthusiast, always searching for better ways of doing things. Lately that has been all things React. I also write a lot on Medium. :)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store