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

## Digital Art II: End of Week 4

It’s hard to believe it’s been four weeks already!  Recall that we ended Week 2 with work on an Evaporation piece.  We’ll see examples of student work after a brief recap of Weeks 3 and 4 (Days 6–10).

In the past two weeks, we focused on affine transformations and their use in creating fractals with iterated function systems.  This was not intended to be a deep discussion of linear algebra, but a practical one — how affine transformations reflect the geomtetry of fractal images.

Days 6 and 7 were an introduction to the geometry of affine transformations.  I like to emphasize the geometry first, so I worked to find a way to simply and unambiguously describe an affine transformation geometrically.

The blue square represents the unit square, and the red parallelogram the transformed square.  The filled-in/open black circles on the parallelogram represent how (0,0) and (1,0) are transformed, respectively.  Additionally, the pink fill in the parallelogram represents that fact that there is a flip (that is, the determinant of the linear part of the transformation is negative).  Strictly speaking, this coloring isn’t necessary, but I think it helps.

We then worked on writing the affine transformation in the form

$T\left(\begin{matrix}x\\y\end{matrix}\right)=\left[\begin{matrix}a&b\\c&d\end{matrix}\right]\left(\begin{matrix}x\\y\end{matrix}\right)+\left(\begin{matrix}e\\f\end{matrix}\right)$

We did this in the usual way, where the columns of the matrix represent where the unit basis vectors are transformed, and the vector added at the end is the translation from the origin.  These can all be read from the diagram, so that the picture above describes the affine transformation

$T\left(\begin{matrix}x\\y\end{matrix}\right)=\left[\begin{matrix}-2&-3\\2&0\end{matrix}\right]\left(\begin{matrix}x\\y\end{matrix}\right)+\left(\begin{matrix}-2\\1\end{matrix}\right).$

To help in visualizing this in general, I also wrote a Sage worksheet which produces diagrams like the above picture given the parameters af.  In addition, I showed how the vertices of the parallelogram may be found algebraically by using the transformation itself, so this meant we could look at affine transformations geometrically and algebraically, as well as with the Sage worksheet.   (Recall that all worksheets/assignments may be found on the corresponding day on the course website.  In addition, I have included the $LaTeX$ code for the assignments for those interested.)

I explained several different types of affine transformations — translations, reflections, scalings, and shears.  On Day 8, we saw how to write the affine transformations which describe the Sierpinski triangle, and students got to play with creating their own fractals using the accompanying Sage worksheet.

On Day 9, I took about half the class to go through three of my blog posts on iterated function systems.  I emphasized the first spiral fractal discussed on Day035, paying particular attention to the rotation involved and matrix multiplication.

Most students weren’t familiar with trigonometry (recall the course has no prerequisites), so I just told them the formula for rotation matrices.  We briefly discussed matrix multiplication as function composition.  I gave them homework which involved some practice with the algebra of matrix multiplication.

On Day 10, we began with going over some previous homework, and then looked at what transformations were needed to producing the fractal below (as practice for their upcoming homework).

We then engaged in the following laboratory exercise:  Create a fractal using two affine transformations.  For the first, rotate by 45 degrees, then scale the x by 0.6 and the y by 0.4, and finally move to the right 1.  For the second transformation, rotate 90 degrees clockwise, and then move up 1.

This was practice in going from a geometrical description to a fractal — they needed to perform the appropriate calculations, and then enter the data in the Sage worksheet and see if their fractal was correct (I gave them a link to the final image).

This turned out to be very challenging, as they were just getting familiar with rotations and matrix multiplication.  So we’ll need to finish during the next class.  I’ll also give them another similar lab exercise during the next class to make sure they’ve got it.

Last week’s digital art assignment was another success!  Again, I was very pleased with how creative my students were.  If you look back at the Sage worksheets, you’ll see that the class was working with color, texture, and color gradients (like my Evaporation piece).

One student created a texture with a lot of movement by keeping the circles separate and using a wide range of gray tones.

Maddie took advantage of the fact that the algorithm draws the circles in a particular order to create a scalloped texture.  This happens when the circles are particularly large, since the circles are drawn in a linear fashion, creating successive overlap.

Another student also used this overlapping feature with a color gradient.  He describes his piece as follows:

This piece is what I like to call “The Hedge” as it reminds me a lot of those tall square hedges that are in mansions. It’s as if the light is hitting the top of the hedge and dispersing down into the shadows and thickness of the leaves. I especially like the leafy effect the overlapping circles give.

Finally, Madison experimented with altering the dimensions of the grid to create a different feel.

She thought that making the image wider made the evaporation effect more pronounced.

These are just some examples of how students in my Mathematics and Digital Art course take ideas I give them and make them their own.  They are always asking how they can incorporate one effect or another into their work, and Nick and I are glad to oblige by helping out with a little code.

As I strive to keep my posts a consistent length, I won’t be able to share all the images I’d like to this week.  So I’ll be posting additional images on my Twitter feed, @cre8math.  Follow along if you’d like to see more!

## 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!

## Digital Art I: End of Week 2

Mathematics and Digital Art is well underway!  As promised, I’ll be giving weekly or biweekly summaries of how things are going.  You’re also welcome to follow along on the course website.

Day 1 was the usual introductory class, with a discussion about the syllabus and what the course would be like.  (Remember I blogged a four-part series on the course beginning at Day045.)  I wanted to make it clear that there would be both mathematics and coding in the course.  Some students ended up dropping the course the first week as a result, leaving the class with nine students.

On Day 2, I discussed representing color on the computer — using RGB values (both integer and real), as well as using hexadecimal notation.  Since the course has no prerequisites, we really did need to start at the beginning.  Students did some exploring with various RGB values using a Sage worksheet.  (Links to all the worksheets and other websites referenced in class can be found on the course website.)

Josef Albers was the topic of Day 3.  I’ve talked a lot about his work before, so I won’t go into great detail here.  I let students try out a Sage worksheet — they had an assignment to create their own version which was due in about week, so we spent half the class starting the project.

Essentially, they needed to choose a color scheme and size for their piece.  But then they needed to use five different random number seeds, and decide which of the five resulting images looked best to them, and why.  So the assignment included a brief narrative as well.  The complete prompt is on my website.  (And I think I’ll just stop saying this — just know that anything I mention in these posts will be discussed in more detail on the course website.)

The next two classes focused on creating a piece based on Evaporation.

Again, I discussed this in some detail before (Day011 and Day012).  The basic idea is to use randomness to create texture, both with color and geometry.  Add to this the idea of a color gradient, and that’s enough to get started.

I took a bit of time on Day 5 to explain in some detail about how to create color gradients using a function like $y=x^p,$ where $p>0$ — it isn’t exactly obvious if you’ve never done it before.  Having Nick as my TA in the class really helped out — I was at the board, and he was at the computer drawing graphs of functions and varying the parameters in the routine to produce color gradients. We worked well together.

It turns out that having two of us in the computer lab is really great — debugging takes time.  Students are gradually getting accustomed to the Sage environment, and  learning to go back and redefine functions if they get an error message indicating that something is undefined….

I have really been enjoying the laboratory experience!  My students are wonderfully creative, taking the basic motifs in directions I hadn’t considered.  I’ll illustrate with a few examples from the first assignment.  In this post and future posts, all work is presented with the permisson of the student, including the use of his/her name if applicable.

I should also remark that my intent is not merely to post pieces I subjectively like.  True to the title of my blog, Creativity in Mathematics, I intend to illustrate creative, original ideas.  I may feel that some students have been more successful with their ideas than others — but I’ll share that with the students individually rather than discuss it here.

In order to talk about the students’ creativity, however, let me show you the image they started with.

Andrew experimented with minimalism, creating a series of 2 x 2 images.  This is the one he said he liked the best because of the symmetry and contrast.

Julia was interested in exploring different geometries and created a few drafts which deviated from the rectangle-within-rectangle motif.  Here is one of them.

Safina took a slightly different approach.  She wanted to create some variation by using trapezoids in the centers of the larger rectangles.

Ella really worked with the geometry, creating a lot of visual contrast — especially with the asymmetrical polygons.

So we’re off to a great beginning!  Right now, Nick and I are having to help a lot with editing code since it’s a new experience for most students.  But they are eager to learn, and as you can see, willing to explore new ideas, going well beyond where they started.  We can look forward to a lot more interesting work as the semester progresses!

P.S.  If you are ever interested in any of the students’ work and would like to discuss it further, send an email to vjmatsko@usfca.edu and I’ll forward it on to them!

## Celebrating One Year!

It’s hard to believe, but I published my first blog post one year ago today on September 1, 2015.  It’s been a challenge at times to keep up the weekly posts — but I’m very glad I did.  So here I write, fifty-five posts later….

I do wish to thank my followers and email subscribers, but I’ll stop there at sentimentality.  Given the occasion, I thought I’d talk about one important aspect of the art of mathematics that I’ve hinted at now and then.  Mathematics is a team effort.

Sure, sometimes I have to sit at my desk and just do mathematics.  But there’s a lot more to mathematical endeavor than that.  So I’d like to discuss some conversations I’ve had over the past year — conversations which helped me formulate new ideas and forge new directions to pursue.  Places I wouldn’t have gone if all I did was sit at my desk….

Some of my earlier posts were a direct result of doing some independent study work with one of my students, Thomas.

We were talking about the usual recursive algorithm to create the Koch snowflake, and he asked what would happen if we changed the angles used in the algorithm.  This prompted a year-long investigation into properties of images created using the algorithm — especially images with rotational symmetry.

I gave talks about this phenomenon in Vienna and Finland.  I also mentioned discussing this with one of the conference attendees in Vienna — Paul — who said the images in my talk reminded him of some work he had done earlier.  This image is generated using Paul’s algorithm.

When I looked at his paper, I found that he had used a different recursive algorithm — but surprisingly, the images had a similar feel to those I created.  I haven’t had time to explore this alternate algorithm yet, but if I hadn’t been talking to another artist and mathematician, I might never have come across it.

My last two posts were the direct result of attending a talk at the Bridges conference in Finland.  I had posted about Josef Albers before, but James gave a talk which looked at Albers’ Homage to the Square series in an entirely different way.

The ideas in this talk got me thinking about color on a computer screen and the use of opacity — how there are many different ways to color objects using various combinations of color values and opacity such that visually, they appear the same on a computer screen.

By looking at how opacity is implemented in a typical graphics program, this phenomenon may be analyzed mathematically.  I’ve just scratched the surface in the last two posts; there’s definitely more to be done here.

Working with Nick to get prepared for the Bridges conference was also valuable.  He created fractal images using a particular recursive algorithm he developed.

Most recently, Nick generated a series of fractal images based on a certain parameter.  When this parameter is below some threshold value, the image looks like fractal dust.  Above this threshold value, and the image overlaps itself.  But there seems to be a particular value where parts of the fractal just touch.

Sometimes finding such threshold values can be very difficult.  But I have a hunch we might be able to calculate it for some of the simpler fractals, and I look forward to the challenge.

There were many, many other conversations about mathematics and art over the past year — but these jump out to me as significant.

Any mathematician reading will naturally say, “Of course!”  This is the way that most mathematicians I know work on a daily basis.  It is often useful to share work with others and bounce your ideas off them, just like in most other disciplines.

I think it less likely that a non-mathetician would see the social aspect of doing mathematics.  So I thought I’d talk about that today.

A final “Thank you!” to my loyal followers.  I’ll keep talking, traveling, creating art, and introducing you to others who have inspired me along the way.  Time to begin Year Two!