July 31, 2016 10:19 AM

"I Live In Air Filled With Images..."

Leonard Baskin waved his arms around his head:

I tell you honestly that I do not live in air. I live in air filled with images, waiting, waiting. And they are mad at me because I don't make them. This is not a fantasy. It is real, I assure you.

I know a few programmers who feel the same way about code. I have periods of such immediacy myself.

This is one of those double-edged phenomena, though. Many people would like to find some goal or activity that so enlivens their world, but they also do not want it to drive them to endless distraction. Fortunately, when we get deep into creating a new something, the swirl goes away for a while.

(This passage comes from Conversations with Artists, which I have now quoted a few times. I promise not to type the entire book into my blog.)

Posted by Eugene Wallingford | Permalink | Categories: General

July 28, 2016 2:37 PM

Functional Programming, Inlined Code, and a Programming Challenge

an example of the cover art for the Commander Keen series of games

I recently came across an old entry on Jonathan Blow's blog called John Carmack on Inlined Code. The bulk of the entry consists an even older email message that Carmack, lead programmer on video games such as Doom and Quake, sent to a mailing list, encouraging developers to consider inlining function calls as a matter of style. This email message is the earliest explanation I've seen of Carmack's drift toward functional programming, seeking to as many of its benefits as possible even in the harshly real-time environment of game programming.

The article is a great read, with much advice borne in the trenches of writing and testing large programs whose run-time performance is key to their success. Some of the ideas involve programming language:

It would be kind of nice if C had a "functional" keyword to enforce no global references.

... while others are more about design style:

The function that is least likely to cause a problem is one that doesn't exist, which is the benefit of inlining it.

... and still others remind us to rely on good tools to help avoid inevitable human error:

I now strongly encourage explicit loops for everything, and hope the compiler unrolls it properly.

(This one may come in handy as I prepare to teach my compiler course again this fall.)

This message-within-a-blog-entry itself quotes another email message, by Henry Spencer, which contains the seeds of a programming challenge. Spencer described a piece of flight software written in a particularly limiting style:

It disallowed both subroutine calls and backward branches, except for the one at the bottom of the main loop. Control flow went forward only. Sometimes one piece of code had to leave a note for a later piece telling it what to do, but this worked out well for testing: all data was allocated statically, and monitoring those variables gave a clear picture of most everything the software was doing.

Wow: one big loop, within which all control flows forward. To me, this sounds like a devilish challenge to take on when writing even a moderately complex program like a scanner or parser, which generally contain many loops within loops. In this regard, it reminds me of the Polymorphism Challenge's prohibition of if-statements and other forms of selection in code. The goal of that challenge was to help programmers really grok how the use of substitutable objects can lead to an entirely different style of program than we tend to create with traditional procedural programming.

Even though Carmack knew that "a great deal of stuff that goes on in the aerospace industry should not be emulated by anyone, and is often self destructive", he thought that this idea might have practical value, so he tried it out. The experience helped him evolve his programming style in a promising direction. This is a great example of the power of the pedagogical pattern known as Three Bears: take an idea to its extreme in order to learn the boundaries of its utility. Sometimes, you will find that those boundaries lie beyond what you originally thought.

Carmack's whole article is worth a read. Thanks to Jonathan Blow for preserving it for us.


The image above is an example of the cover art for the "Commander Keen" series of video games, courtesy of Wikipedia. John Carmack was also the lead programmer for this series. What a remarkable oeuvre he has produced.

Posted by Eugene Wallingford | Permalink | Categories: Computing, Patterns, Software Development, Teaching and Learning

July 27, 2016 10:58 AM

Teaching Programming Versus Teaching Art

Like many people, I am fond of analogies between software development and arts like writing and painting. It's easy to be seduced by similarities even when the daily experiences of programmers and artists are often so different.

For that reason, I was glad that this statement by sculptor Jacques Lipschutz stood out in such great relief from the text around it:

Teaching is death. If he teaches, the sculptor has to open up and reveal things that should be closed and sacred.

For me, teaching computer science has been just the opposite. Teaching forces me to open up my thinking processes. It encourages me to talk with professional developers about how they do what they do and what they think about along the way. Through these discussions, we do reveal things that sometimes feel almost sacred, but I think we all benefit from the examination. It not only helps me to teach novice developers more effectively; it also helps me to be a better programmer myself.


(The Lipschutz passage comes from Conversations with Artists, which I quoted for the first time last week.)

Posted by Eugene Wallingford | Permalink | Categories: Software Development, Teaching and Learning

July 22, 2016 11:02 AM

What Happens When We Read To Kids

A great analogy from Frank Cottrell:

Think of it, he says, the sun pours down its energy onto the surface of the planet for millennia. The leaves soak up the energy. The trees fall and turn to coal. Coal is solid sunlight, the stored memory of millions of uninhabited summers. Then one day, in Coalbrookdale, someone opens a hole in the ground and all that stored energy comes pouring out and is consumed in furnaces, engines, motors.

When we -- teachers, parents, carers, friends -- read to our children, I believe that's what we're doing. Laying down strata of fuel, fuel studded with fossils and treasures. If we ask for anything back, we burn it off too soon.

My wife and I surely did a lot of things wrong as we raised our daughters, but I think we did at least two things right: we read to them all the time, and we talked to them like we talk to everyone else. Their ability to speak and reason and imagine grew out of those simple, respectful acts.

Teaching at a university creates an upside-down dynamic by comparison, especially in a discipline many think of as being about jobs. It is the students and parents who are more likely to focus on the utility of knowledge. Students sometimes ask, "When will we use this in industry?" With the cost of tuition and the uncertainty of the times, I understand their concern. Even so, there are times I would like to say "I don't know" or, in my weaker moments, the seemingly disrespectful "I don't care". Something more important should be happening here. We are creating fuel for a lifetime.

(The Cottrell article takes an unusual route to an interesting idea. It was worth a read.)

Posted by Eugene Wallingford | Permalink | Categories: Personal, Teaching and Learning

July 20, 2016 9:16 AM

A Few Quick Lessons from Five Small Joy Programs

I recently wrote about some experiences programming in Joy, in which I use Joy to solve five problems that make up a typical homework assignment early in my Programming Languages course. These problems introduce my students to writing simple functions in a functional style, using Racket. Here is my code, if you care to check it out. I'm just getting back to stack programming, so this code can surely be improved. Feel free to email me suggestions or tweet me at @wallingf!

What did these problems teach me about Joy?

  • The language's documentation is sparse. Like my students, I had to find out which Joy primitives were available to me. It has a lot of the basic arithmetic operators you'd expect, but finding them meant searching through a plain-text file. I should write Racket-caliber documentation for the language to support my own work.

  • The number and order of the arguments to a function matters a lot. A function that takes several arguments can become more complicated than the corresponding Racket function, especially if you need to use them multiple times. I encountered this on my first day back to the language. In Racket, this problem requires a compound expression, but it is relatively straightforward, because arguments have names. With all its arguments on the stack, a Joy function has to do more work simply to access values, let alone replicate them for multiple uses.

  • A slight difference in task can lead to a large change in the code. For Problem 4, I implemented operators for modular addition, subtraction, and multiplication. +mod and *mod were elegant and straightforward. -mod was a different story. Joy has a rem operator that operates like Racket's remainder, but it has no equivalent to modulo. The fact that rem returns negative values means that I need a boolean expression and quoted programs and a new kind of thinking. This militates for a bigger shift in programming style right away.

  • I miss the freedom of Racket naming style. This isn't a knock on Joy, because most every programming language restricts severely the set of characters you can use in identifiers. But after being able to name functions +mod, in-range?, and int->char in Racket, the restrictions feel even more onerous.

  • As in most programming styles, the right answer in Joy is often to write the correct helpers. The difference in level of detail between +mod and *mod on the one hand and -mod on the other indicates that I am missing solution. A better approach is to implement a modulo operator and use it to write all three mod operators. This will hide lower-level details in a general-purpose operator. modulo would make a nice addition to a library of math operators.

  • Even simple problems can excite me about the next step. Several of these solutions, especially the mod operators, cry out for higher-order operators. In Racket, we can factor out the duplication in these operators and create a function that generates these functions for us. In Joy, we can do it, too, using quoted programs of the sort you see in the code for -mod. I'll be moving on to quoted programs in more detail soon, and I can't wait... I know that they will push me farther along the transition to the unique style of stack programming.

It's neat for me to be reminded that even the simplest little functions raise interesting design questions. In Joy, use of a stack for all data values means that identifying the most natural order for the arguments we make available to an operators can have a big effect on the ability to read and write code. In what order will arguments generally appear "in the wild"?

In the course of experimenting and trying to debug my code (or, even more frustrating, trying to understand why the code I wrote worked), I even wrote my first general utility operator:

    DEFINE clear  == [] unstack.

It clears the stack so that I can see exactly what the code I'm about to run creates and consumes. It's the first entry in my own little user library, named utilities.joy.

Fun, fun, fun. Have I ever said that I like to write programs?

Posted by Eugene Wallingford | Permalink | Categories: Computing, Software Development

July 19, 2016 10:32 AM

What Is The Function Of School Today?

Painter Adolph Gottlieb was dismissive of art school in the 1950s:

I'd have done what I'm doing now twenty years ago if I hadn't had to go through that crap. What is the function of the art school today? To confuse the student. To make a living for the teacher. The painter can learn from museums -- probably it is the only way he can to learn. All artists have to solve their problems in the context of their own civilization, painting what their time permits them to paint, extending the boundaries a little further.

It isn't much of a stretch to apply this to computer programming in today's world. We can learn so much these days from programs freely available on GitHub and elsewhere on the web. A good teacher can help, but in general is there a better way to learn how to make things than to study existing works and to make our own?

Most importantly, today's programmers-to-be have to solve their problems in the context of their own civilization: today's computing, whether that's mobile or web or Minecraft. University courses have a hard time keeping up with constant change in the programming milieu. Instead, they often rely on general principles that apply across most environments but which seem lifeless in their abstraction.

I hope that, as a teacher, I add some value for the living I receive. Students with interests and questions and goals help keep me and my courses alive. At least I can set a lower bound of not confusing my students any more than necessary.


(The passage above is quoted from Conversations with Artists, Selden Rodman's delightful excursion through the art world of the 1950s, chatting with many of the great artists of the era. It's not an academic treatise, but rather more an educated friend chatting with creative friends. I would thank the person who recommended this, but I have forgotten whose tweet or article did.)

Posted by Eugene Wallingford | Permalink | Categories: Computing, Teaching and Learning

July 18, 2016 12:47 PM

Getting a Sense of Joy Style Through the Stack

Last time, I wrote about returning to the programming language Joy, without giving too many details of the language or its style. Today, I'll talk a bit more what it means to say that Joy is a "stack language" and show how I sometimes think about the stack as I am writing a simple program. The evolution of the stack is helping me to think about how data types work in this language and to get a sense of why languages such as Joy are called concatenative.

Racket and other Lisp-like languages use prefix notation, unlike the more common infix notation we use in C, Java, and most mainstream languages. A third alternative is postfix notation, in which operators follow their operands. For example, this postfix expression is a valid Joy program:

    2 3 +

computes 2 + 3.

Postfix expressions are programs in a stack-based language. They correspond to a postfix traversal of a program tree. Where is the stack? It is used to interpret the program:

  • 2 is pushed onto the stack.
  • 3 is pushed onto the stack.
  • + is an operator. An operator pops its arguments from the stack, computes a result, and pushes the result on to the stack. + is a two-argument function, so it pops two arguments from the stack, computes their sum, and pushes the 5 back onto the stack.

Longer programs work the same way. Consider 2 3 + 5 *:

  • 2 is pushed onto the stack.
  • 3 is pushed onto the stack.
  • + pops the 2 and the 3, computes a 5, and pushes it on to the stack.
  • 5 is pushed onto the stack.
  • * pops the two 5s, computes a 25, and pushes it on to the stack.

This program is equivalent to 2 + 3 - 5, er, make that (2 + 3) * 5. As long as we know the arity of each procedure, postfix notation requires no rules for the precedence of operators.

The result of the program can be the entire stack or the top value on the stack. At the end of a program, the stack could finish with more than one value on it:

    2 3 + 5 * 6 3 /

leaves a stack consisting of 25 2.

Adding an operator to the end of that program can return us to a single-value stack:

    2 3 + 5 * 6 3 / -

leaves a stack of one value, 23.

This points out an interesting feature of this style of programming: we can compose programs simply by concatenating their source code. 2 * is a program: "double my argument", where all arguments are read from the stack. If we place it at the end of 2 3 + 5 * 6 3 / -, we get a new program, one that computes the value 46.

This gives us our first hint as to why this style is called concatenative programming.

As I am re-learning Joy's style, I think a lot about the stack, which holds the partial results of the computation I am trying to program. I often find myself simulating the state of stack to help me keep track of what to do next, whether on paper or in a comment on my code.

As an example, think back to the wind chill problem I discussed last time: given the the air temperature T and the wind speed V, compute the wind chill index T'.

    T' = 35.74 + 0.6215·T - 35.75·V0.16 + 0.4275·T·V0.16

This program expects to find T and V on top of the stack:

    T V

The program 0.16 pow computes x0.16 for the 'x' on top of the stack, so it leaves the stack in this state:

    T V'

In Joy documentation, the type of a program is often described with a before/after picture of the stack. The dup2 operator we saw last time is described as:

    dup2 :: a b -> a b a b

because it assumes two arbitrary values on top of the stack and leaves the stack with those values duplicated. In this fashion, we could describe the program 0.16 pow using

    0.16 pow :: N -> N

It expects a number N to be on top of the stack and leaves the stack with another number on top.

When I'm using these expressions to help me follow the state of my program, I sometimes use problem-specific names or simple modifiers to indicate changes in value or type. For the wind-chill program, I thought of the type of 0.16 pow as

    T V -> T V'
, because the values on the stack were a temperature and a velocity-based number.

Applied to this stack, dup2 converts the stack as

    T V' -> T V' T V'
, because the values on the stack were a temperature and a velocity-based number.

If we concatenate these two programs and evaluate them against the original stack, we get:

    [ initial stack]         T V
    0.16 pow              -> T V'
    dup2                  -> T V' T V'

I've been preserving these stack traces in my documentation, for me and any students who might end up reading my code. Here is the definition of wind-chill, taken directly from the source file:

    DEFINE wind-chill == 0.16 pow        (* -> T V'        *)
                         dup2            (* -> T V' T V'   *)
                         * 0.4275 *      (* -> T V' t3     *)
                         rollup          (* -> t3 T V'     *)
                         35.75 *         (* -> t3 T t2     *)
                         swap            (* -> t3 t2 T     *)
                         0.6215 *        (* -> t3 t2 t1    *)
                         35.74           (* -> t3 t2 t1 t0 *)
                         + swap - +.     (* -> T'          *)

After the dup2 step, the code alternates between computing a term of the formula and rearranging the stack for the next computation.

Notice the role concatenation plays. I can solve each substep in almost any order, paste the resulting little programs together, and boom! I have the final solution.

I don't know if this kind of documentation helps anyone but me, or if I will think it is as useful after I feel more comfortable in the style. But for now, I find it quite helpful. I do wonder whether thinking in terms of stack transformation may be helpful as I prepare to look into what type theory means for a language like Joy. We'll see.

I am under no pretense that this is a great Joy program, even in the context of a relative novice figuring things out. I'm simply learning, and having fun doing it.

Posted by Eugene Wallingford | Permalink | Categories: Computing

July 16, 2016 2:52 PM

A First Day Back Programming in Joy

I learned about the programming language Joy in the early 2000s, when I was on sabbatical familiarizing myself with functional programming. It drew me quickly into its web. Joy is a different sort of functional language, one in which function composition replaces function application as the primary focus. At that time, I wrote a bunch of small Joy programs and implemented a simple interpreter in PLT Scheme. After my sabbatical, though, I got pulled in a lot of different directions and lost touch with Joy. I saw it only every two or three semesters when I included it in my Programming Languages course. (The future of programming might not look like you expect it to....)

This spring, I felt Joy's call again and decided to make time to dive back into the language. Looking back over my notes from fifteen years ago, I'm surprised at some of the neat thoughts I had back then and at some of the code I wrote. Unfortunately, I have forgotten most of what I learned, especially about higher-order programming in Joy. I never reached the level of a Joy master anyway, but I feel like I'm starting from scratch. That's okay.

On Thursday, I sat down to write solutions in Joy for a few early homework problems from my Programming Languages course. These problems are intended to help my students learn the basics of functional programming and Racket. I figured they could help me do the same in Joy before I dove deeper, while also reminding me of the ways that programming in Joy diverges stylistically from more traditional functional style. As a bonus, I'd have a few more examples to show my students in class next time around.

It didn't take me long to start having fun. I'll talk more in upcoming posts about Joy, this style of programming, and -- I hope -- some of my research. For now, though, I'd like to tell you about one experience I had on my first day without getting into too many details.

In one homework problem, we approximate the wind chill index using this formula:

    T' = 35.74 + 0.6215·T - 35.75·V0.16 + 0.4275·T·V0.16
where T' is the wind chill index in degrees Fahrenheit, T is the air temperature in degrees Fahrenheit, and V is the wind speed in miles/hour. In Racket, this computation gives student a chance to write a compound expression and, if adventurous, to create a local variable to hold V0.16.

In Joy, we don't pass arguments to functions as in most other languages. Its operators pop their arguments from a common data stack and push their results back on to the stack. Many of Joy's operators manipulate the data stack: creating, rearranging, and deleting various items. For example, the dup operator makes a copy of the item on top of the stack, the swap operator swaps the top two items on the stack, and the rolldown operator moves the top two items on the stack below the third.

A solution to the wind-chill problem will expect to find T and V on top of the stack:

    T V
After computing V' = V0.16, the stack looks like this:
    T V'

The formula uses these values twice, so I really need two copies of each:

    T V' T V'

With a little work, I found that this sequence of operations does the trick:

    swap dup rolldown dup rolldown swap

From there, it didn't take long to find a sequence of operators that consumed these four values and left T' on the stack.

As I looked back over my solution, I noticed the duplication of dup rolldown in the longer expression shown above and thought about factoring it out. Giving that sub-phrase a name is hard, though, because it isn't all that meaningful on its own. However, the whole phrase is meaningful, and probably useful in a lot of other contexts: it duplicates the top two items on the stack. So I factored the whole phrase out and named it dup2:

    DEFINE dup2 == swap dup rolldown dup rolldown swap.
My first refactoring in Joy!

As soon as my fingers typed "dup2", though, my mind recognized it. Surely I had seen it before... So I went looking for "dup2" in Joy's documentation. It is not a primitive operator, but it is defined in the language's initial library, inilib.joy, a prelude that defines syntactic sugar in Joy itself:

    dup2 ==  dupd dup swapd

This definition uses two other stack operators, dupd and swapd, which are themselves defined using the higher-order operator dip. I'll be getting to higher-order operators soon enough, I thought; for now I was happy with my longer but conceptually simpler solution.

I was not surprised to find dup2 already defined in Joy. It defines a lot of cool stack operators, the sorts of operations every programmer needs to build more interesting programs in the language. But I was a little disappointed that my creation wasn't new, in the way that only a beginner can be disappointed when he learns that his discovery isn't new. My disappointment was more than offset by the thought that I had recognized an operator that the language's designer thought would be useful. I was already starting to feel like a Joy programmer again.

It was a fun day, and a much-needed respite from administrative work. I intend for it to be only the first day of many more days programming with Joy.

Posted by Eugene Wallingford | Permalink | Categories: Computing

July 13, 2016 11:19 AM

A Student Asks About Pursuing Research Projects

Faculty in my department are seeking students to work on research projects next. I've sent a couple of messages to our student mailing list this week with project details. One of my advisees, a bright guy with a good mind and several interests, sent me a question about applying. His question got to the heart of a concern many students have, so I responded to the entire student list. I thought I'd share the exchange as an open letter to all students out there who are hesitant about pursuing an opportunity.

The student wrote something close to this:

Both professors' projects seem like great opportunities, but I don't feel even remotely qualified for either of them. I imagine many students feel like this. The projects both seem like they'd entail a really advanced set of skills -- especially needing mathematics -- but they also require students with at least two semesters left of school. Should I bother contacting them? I don't want to jump the gun and rule myself out.

Many students "self-select out" -- choose not to pursue an opportunity -- because they don't feel qualified. That's too bad. You would be surprised how often the profs would be able to find a way to include a student who are interested in their work. Sometimes, they work around a skill the student doesn't have by finding a piece of the project he or she can contribute to. More often, though, they help the student begin to learn the skill they need. We learn many things best by doing them.

Time constraints can be a real issue. One semester is not enough time to contribute much to some projects. A grant may run for a year and thus work best with a student who will be around for two or more semesters. Even so, the prof may be able to find a way to include you. They like what they do and like to work with other people who do, too.

My advice is to take a chance. Contact the professor. Stop in to talk with him or her about your interest, your skills, and your constraints. The worst case scenario is that you get to know the professor a little better while finding out that this project is not a good fit for you. Another possible outcome, though, is that you find a connection that leads to something fruitful. You may be surprised!


Postcript. One student has stopped in already this morning to thank me for the encouragement and to say that he is going to contact one of the profs. Don't let a little uncertainty stand in the way of pursuing something you like.

Posted by Eugene Wallingford | Permalink | Categories: General, Teaching and Learning

July 07, 2016 2:01 PM

Oberon: GoogleMaps as Desktop UI

Oberon is a software stack created by Niklaus Wirth and his lab at ETH Zürich. Lukas Mathis describes some of what makes Oberon unusual, including the fact that its desktop is "an infinitely large two-dimensional space on which windows ... can be arranged":

It's incredibly easy to move around on this plane and zoom in and out of it. Instead of stacking windows, hiding them behind each other (which is possible in modern versions of Oberon), you simply arrange them next to each other and zoom out and in again to switch between them. When people held presentations using Oberon, they would arrange all slides next to each other, zoom in on the first one, and then simply slide the view one screen size to the right to go to the next slide.

This sounds like interacting with Google Maps, or any other modern map app. I wonder if anyone else is using this as a model for user interaction on the desktop?

Check out Mathis's article for more. The section "Everything is a Command Line" reminds me of workspaces in Smalltalk. I used to have several workspaces open, with useful snippets of code just waiting for me to do it. Each workspace window was like a custom text-based menu.

I've always liked the idea of Oberon and even considered using the programming language in my compilers course. (I ended up using a variant.) A version of Compiler Construction is now available free online, so everyone can see how Wirth's clear thinking lead to a sparse, complete, elegant whole. I may have to build the latest installment of Oberon and see what all they have working these days.

Posted by Eugene Wallingford | Permalink | Categories: Computing, Software Development

July 06, 2016 12:43 PM

Computational Research Lets Us Ask New Questions, Political Science Edition

The latest example comes from FiveThirtyEight.com, an organization that is built on the idea of data-driven approaches to old problems:

Almost all data about politics that you encounter comes from polls and surveys of individuals or else from analysis of geographic units such as precincts, counties and states. Individual data and geographic data do not capture the essential networks in which we all live -- households and friendships and communities. But other and newer kinds of data -- such as voter files that connect individuals to their households or network data that capture online connections -- revolutionize how we understand politics. By the end of this election cycle, expect to see many more discoveries about the social groupings that define our lives.

Computational research enables us to ask entirely new questions -- both ones that were askable before but not feasible to answer and ones that would not have been conceived before. Even if the question begins as whimsically as "How often do Democrats and Republicans marry one another?"

Back in December 2007, I commented on this in the context of communications studies and public relations. One of our CS master's students, Sergey Golitsynskiy, had just defended an M.A. thesis in communications studies that investigated the blogosphere's impact on a particular dust-up in the public relations world. Such work has the potential to help refine the idea of "the general public" within public relations, and even its nature of "publics". (Sergey is now a tenure-track professor here in communications studies.)

Data that encodes online connections enables us to explore network effects that we can't even see with simpler data. As the 538 piece says, this will revolutionize how we understand politics, along with so many other disciplines.

Posted by Eugene Wallingford | Permalink | Categories: Computing