Tag: Computer science

The last installment of my coding autobiography was an introduction to LISP.  I’d like to continue that discussion today as a segue to talking about Mathematica, because the way I program in Mathematica is heavily influenced by my experience with LISP.

This week I’ll focus on what are typically referred to as aspects of functional programming.  Rather than try to explain by using a definition (you can always google it), I’d like to show how I’d perform a simple calculation, like adding the sum of the squares of the first n integers.

Here’s a simple snippet of code which performs this task in Python:

Of course you could embed the square function in the loop, but for more complicated functions, this is not usually done.  In any case, I’m using this approach to illustrate a point.

Now in Mathematica, I would write:

You might think that there’s no way the code could be shrunk that much, but it really is possible.  Let’s see why.

We’ll look at the “# * # &” piece first.  This is usually called a pure function, and is essentially a function with no name.  It’s like defining f(#) to be # * #, and then invoking f.  But with the “#” as the argument to the function, this syntax allows you to avoid naming the function altogether.

Why might you want to do this?  One reason is it makes your code less cluttered if you need to define a relatively simple function and use it just once.  I actually use pure functions a lot.  Once you start thinking about programming with them in mind, it really does help streamline your code.  You find you can’t live without them, and when you use a language which doesn’t allow them, you really miss ’em….

What about the “/@”?  This is a map, and is the alternative to iteration in LISP.  What it says is this:  “Here is a function, and here is a list of arguments.  Apply the function to each of the elements of the list in order, and collect the results in a new list.”  So

# * # & /@ {1,2,3}

would return the list {1,4,9}.

In languages like LISP and Mathematica, the use of maps is built in to the heart of the compilers, so that maps are often much faster than iterating.  In fact, to add the squares of the first 1,000,000 integers, it’s about 40 times faster in Mathematica to use a map than to use a loop. I can remember a time I was using iteration to create fractals in Mathematica, and it was taking around 10 minutes to generate each one.  For fun, I thought I’d try using maps, and the run time decreased to less than 30 seconds!  It can really make a difference.

There are more complicated ways to use maps which involve functions of more than one argument, and assembling arguments from lists in different ways.  But the example above illustrates the basic idea.

Of course the use of Range[n] is familiar to Python users, and returns a list of the first n integers, starting with 1 — unlike Python, though, where the list begins at 0.  Personally, for much of what I do, I much prefer the list to begin at 1.  I tend to use “i+1” a lot when I use range(n) in Python.

Finally, what about the “@@”?  This is like the apply function in LISP I described in my last post.  Essentially, it means take this function, Plus, and apply it to this list of numbers, in this case the squares of the first n integers.  It saves having to write a loop which successively adds each next number to a running total.  As an example, it is easy to write a factorial function in Mathematica:

Times @@ Range[n].

So that’s how to sum the squares of the first n integers in just a half line of code!  Now these ideas can all be implemented in LISP and Python as well, and other languages which include more functional apsects.  But for simplicity of syntax, I prefer Mathematica over the others.

The point of using Mathematica code for this example is to show how my style of programming in Mathematica is really very LISP-like.  In fact, I’ve had the experience of showing code like this to some Mathematica programmers, and needing to explain it just like I did for you here.  This is because if you learned a language like PASCAL, C, or some other procedural language, you can code in Mathematica exactly the same way, without ever knowing anything about the functional aspects.

Back to a little history….  I did all my undergraduate and graduate work at Carnegie Mellon, and beginning with my sophomore year as an undergrad, was working a lot with LISP while teaching with the PGSS.  Mathematica was first released during my second year of graduate school, and CMU being the type of school it was, Mathematica was readily available.  I can recall working with it on a NeXT computer.  (Google it!)

So I was introduced to Mathematica while I was heavily into LISP — and found that I was really excited that I could do so many LISP-like things in Mathematica!  More about Mathematica in my next installment of On Coding….

Frankly, I rarely use LISP now.  I do recall creating an address book in LISP — having a list of addresses and phone numbers in a long list, and using LISP to output LaTeX code which I could then run and print out a nicely formatted array of addresses.  But other than that, little else comes to mind.

But although I don’t use the language itself, learning to program in LISP has definitely influenced my programming style more than any other coding experience.  I always encourage my students to study it as a result — although functional programming ideas are now incorporated into many other languages, it’s easy to learn the concepts elsewhere.

For me, I’ll always  have a special place in my hacker heart for all those idiotic stupid parentheses….

During my sophomore year of college at Carnegie Mellon, I got a job in the psychology department as an assistant programmer for a professor working on neural nets.  The language being used was LISP, and the first order of business was to learn it.  I even got paid while I was learning, which I thought was pretty amazing at the time!

I would say working with LISP over the next several years had a huge impact on my life as a programmer — moreso than working with any other language.  So I’d like to devote today’s post to the wonderful world of LISP….

LISP (which stands for LISt Processing) is an example of a functional programming language. I talked a little about procedural programming languages earlier, so today I’ll describe some functional aspects of LISP.  Of course there is no substitute for just diving in and learning it yourself….

Why did I spend so many years programming in LISP?  I worked a few hours a week as a math tutor, so my interest in teaching was already blossoming.  In the Spring of my sophomore year, my roommate heard about a summer program for talented math and science students, and suggested I look into it.  Computer science was one of the courses, and the language being taught was — you guessed it — LISP.  I could hardly believe it!

So I spent ten summers teaching LISP at the Pennsylvania Governor’s School for the Sciences.  I started as a teaching assistant, but eventually became the instructor for the lab course and director of student projects in computer science when I was in graduate school at CMU.

The reason LISP was the language taught, incidentally, was because the students were a particularly bright bunch — only the top two students from each county in the state were accepted.  Many of them already had programming experience — but BASIC and PASCAL were the popular languages at the time for high school students.  It was thought that LISP would level the playing field, as it were.  I can’t recall that any student ever had experience with LISP before.

What makes LISP so different?  Certainly its structure — everything is a list.   Even function calls!  So to add two numbers, you’d write

(plus 3 4).

The first element of this list is the function name, then the arguments follow later.

How do you distinguish lists from function calls?   Consider the function call

(append ‘(1 2 3) ‘(4 5 6))

This does what you’d expect — concatenates two lists together.  The single quote indicates the list represents a pure data structure; you aren’t applying the function “1” with arguments “2” and “3.”  The quote suspends evaluation of the list.

So data structures and function calls look the same.  But here’s what’s neat.  You can write commands like

(eval ‘(plus 3 4)).

The function eval evaluates the list as a function call.  So this is equivalent to (plus 3 4).  Now think about this for a moment.  It’s like taking a string like “3+4” in a language like C and saying “interpret this string as an arithmetic expression.”  Nope, can’t do it.  You’d need to write a parser to do that — and writing a parser isn’t a simple undertaking.

This means you can build function calls as lists and evaluate them, as in

(eval (cons ‘plus ‘(3 4))),

where cons is the constructor function which inserts an element into the front of the list.  (And as you read through the examples, you’ll understand the joke that LISP stands for “Lots of Idiotic Stupid Parentheses.”)

One reason this is even possible is that LISP is not a typed language.  In other words, what the ‘plus means depends on how it’s used — it has no predefined type.  Of course if you use it the wrong way, you’ll get an error — or perhaps not.  LISP will try its best to evaluate what you give it, and may find a way, but it may not be what you intended….

So there are lots of predicates in LISP, like listp, which tells you if something is a list or not.  For example, (listp ‘(1 2 3)) would be true, while (listp 2) would be false.  Some languages are so heavily typed that all variables must be given a type when they’re declared.

I think the ability to construct function calls and evaluate them is one of the major differences between a functional programming language like LISP and other languages.  It might not seem such a big deal at first, but really understanding this idea has definitely impacted the way I think about programming.

Another aspect of the course I TAed which made an impact was the avoidance of loops and variable assignments.  Yes, there are loops and variable assignments in LISP, but the style of the course was to avoid them — in other words, it got students (and me!) to think outside the procedural programming box.

This style of programming is not inherent in functional programming, but it was so significant in my learning, it deserves a few words.

The natural alternative to loops is recursion.  You can write recursive functions in any programming language, but when it’s your only option, you often have to get creative.  So I had to think recursively about everything, not just arithmetic operations, such as in recursively defining the factorial or the Fibonacci numbers.  I got pretty good at recursion.

So much so, that when I submitted a multi-procedure program in one of my CS courses at CMU — where I implemented every loop recursively — I was penalized.  Why?  Because in most languages, recursion has more overhead and is less efficient.  Moreover, there is usually a limit imposed to the depth of recursive calls, so in some languages, you can only use recursion up to a point.  There are pros and cons to using recursion.

Avoiding variable assignments forces you to think about function parameters.  If I wanted to add the sum of the squares of the numbers from 1 to n recursively and avoiding variable assignments, here is what I would do in Python:

So you would have to call sumsquares with an additional argument, as in

sumsquares(10, 0).

This essentially initializes the result to 0 before it’s incremented.

Wow, I didn’t know I had so much to say about LISP!  So stay tuned for the next installment of On Coding, where I continue to describe how working with LISP expanded my programming mind in so many different directions….