## On Coding III: LISP to Mathematica

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….

## On Coding II: LISP

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….

## On Coding I

If you’ve been following along for a while, you’re well aware of my passion for coding.  I firmly believe that all students should learn basic programming in at least one language, if not more.  My hope is that by seeing how the computer may be used to create digital art, some readers will embark on a lifelong coding journey.

To help put this in perspective, I thought I’d share my personal coding journey.  I’d never thought about my programming experience in chronological order before, and realized that talking about my journey could help others on theirs.

My particular journey began during my senior year of high school.  Here was state-of-the-art technology at the time:

This was new technology.  Complete with LED display.  I still remember a game I’d play.  It’s maybe not as amusing now as it was then…but take your TI-30, and multiply the numbers 96, 169, 13, and 337.  Then add 1.  Turn your calculator upside-down — and it spells “Shell Oil”!  This is the only one I can remember, but I’m sure I must’ve made up a few more.  (OK, I didn’t remember all the numbers, but I did remember the 96 and 169, and easily figured out the other two.)

You might be wondering — if the hand-held calculator didn’t come out until my senior year, what did we do before that?  Well, we learned trigonometry using tables of numbers.  If we needed a value which wasn’t in the tables, we figured it out using linear interpolation.  Same with logarithms, and any other numerical calculation.  Tables, pencil, paper.  Try to imagine it!

There wasn’t anything in the way of personal computers then, either.  That’s why I think novice programmers today have it so easy!  Download Python, and ask the internet how to do stuff.  No problem.

When I was a senior in high school, some of us took a bus to a local university to learn Fortran.  (Though not the most common computer language today, it is widely used in disciplines such as physics because of its speed in doing numerical calculations.)  There were no computers in high schools.

And get this.  We used punch cards.  Which looked like this:

You needed one card for each line of code you wrote, which you created on a sort of typewriter.  Then you put your cards in a stack, and took them over to the card reader.  Your cards were read, your program was executed, and after a few moments, you got a printout of what you told the computer to do.

Now this line of code took about 10-15 seconds to type in Sage, and printed out the numbers from 1 to 10 on my screen:

for i in range(10):  print i+1

No getting on a bus, punching cards, etc.  It’s truly amazing how far technology has progressed since those years, and also very wonderful that learning basic programming is so easy now.

I remember really enjoying the way you had to think in order to write computer programs. So when I went to college, I took a programming course in PASCAL my very first semester. Carnegie Mellon was on the forefront of what is now called “computer science,” but at the time, it was not a well-established discipline.  In fact, when I was an undergraduate, you couldn’t be a computer science major — you had to be an applied math major in the computer science track!  Of course that’s all changed now.

Naturally I enjoyed this course, too.  Like Fortran, PASCAL is a procedural programming language — in other words, you’re essentially writing procedures and routines that execute statements in a particular order.  It was probably the most popular procedural language before C came along.  There are other types of computer languages as well, and we’ll get to them when they appear in the chronology.

I took two other computer courses which also used PASCAL, and liked them, too.  These courses were more intense and involved using a lot of data structures, such as arrays, linked lists, binary trees, etc.  But again, in the days before PCs.

So to do your assignment, you had to go to a computer lab.  Then sit down in front of one of these.

And no — there was no mouse, no touch-screen, no windows — just a keyboard you used to type lines of text on a TV-like screen.  And no — it’s not even a computer!  It’s a terminal.  What that means is that there was just one large computer, called the main frame, with many terminals linked to it.  When you wanted to run your program, you had to get in the queue — the main frame could only compile one program at a time.  Then the output would be printed to your screen.

I still remember my first (and last!) all-nighter finishing a programming assignment.  I put it off, and waited until the night before.  And so did a lot of other people.

What that meant was the queue was long.  So you had to wait — maybe 15 minutes or so — for your turn.  This was for just executing your program once.

If you made a spelling mistake — say typed “BEING” instead of “BEGIN,” which I do now and then when I’m typing fast — you waited 15 more minutes to try again.  A short program which might only 20 minutes to complete when the main frame wasn’t so busy took several hours….  I will say I never did that again!  I learned my lesson.

So know you see why I think it’s so easy to learn programming today!  And why all students should….

There’s lots more to the story, and I’ll come back to it now and again.  It’s been fun thinking about those days of emerging technology!