TITLE: Al Aho, Teaching Compiler Construction, and Computational Thinking
AUTHOR: Eugene Wallingford
DATE: April 14, 2011 10:20 PM
DESC: 
-----
BODY:
Last year I blogged about
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2010-03.html#e2010-03-24T19_42_18.htm">
   Al Aho's talk at SIGCSE 2010</A>.
Today he gave a major annual address sponsored by
the CS department at Iowa State University, one
of our sister schools.  When
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2009-07.html#e2009-07-14T10_28_16.htm">
   former student</A>
and current ISU lecturer
<A HREF="http://twodee.org/">
   Chris Johnson</A>
encouraged me to attend, I decided to drive over
for the day to hear the lecture and to visit with
Chris.

Aho delivered a lecture substantially the same as
his SIGCSE talk.  One major difference was that
he repackaged it in the context of computational
thinking.  First, he defined computational thinking
as the thought processes involved in formulating
problems so that their solutions can be expressed
as algorithms and computational steps.  Then he
suggested that designing and implementing a
programming language is a good way to learn
computational thinking.

With the talk so similar to the one I heard last
year, I listened most closely for additions and
changes.  Here are some of the points that stood
out for me this time around, including some
repeated points:
<UL>
<LI> One of the key elements for students when
     designing a domain-specific language is to
     <EM>exploit domain regularities</EM> in a
     way that delivers expressiveness and
     performance.  </LI>

<LI> Aho estimates that humans today rely on
     somewhere between 0.5 and 1.0 <B>trillion</B>
     lines of software.  If we assume that the
     total cost associated with producing each
     line is $100, then we are talking about a
     most serious investment.  I'm not sure where
     he found the $100/LOC number, but...  </LI>

<LI> Awk contains a fast, efficient regular
     expression matcher.  He showed a figure from
     the widely read
     <A HREF="http://swtch.com/~rsc/regexp/regexp1.html">
        Regular Expression Matching Can Be Simple And Fast</A>,
     with a curve showing Awk's performance --
     quite close to Thompson NFA curve from the
     paper.  Algorithms and theory <B>do</B>
     matter.  </LI>

<LI> It is so easy to generate compiler front ends
     these days using good tools in nearly every
     implementation language.  This frees up time
     in his course for language design and documentation.
     This is a choice I struggle with every time I
     teach compilers.  Our students don't have as
     strong a theory background as Aho's do when they
     take the course, and I think they benefit from
     rolling their own lexers and parsers by hand.
     But I'm tempted by what we could with the extra
     time, including processing a more compelling
     source language and better coverage of optimization
     and code generation.  </LI>

<LI> An automated build system and a complete
     regression test suite are essential tools for
     compiler teams.  As Aho emphasized in both talks,
     building a compiler is a serious exercise in
     software engineering.  I still think it's one
     of the best SE exercises that undergrads can
     do. </LI>

<LI> The language for quantum looks cool, but I still
     don't understand it.  </LI>
</UL>

After the talk, someone asked Aho why he thought
functional programming languages were becoming so
popular.  Aho's answer revealed that he, like any
other person, has biases that cloud his views.
Rather than answering the question, he talked about
why most people don't use functional languages.
Some brains are wired to understand FP, but most of
us are wired for, and so prefer, imperative languages.
I got the impression that he isn't a fan of FP and
that he's glad to see it lose out in the social
darwinian competition among languages.

If you'd like to see an answer to the question that
was asked, you might start with
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2010-10.html#e2010-10-15T12_34_58.htm">
   Guy Steel's StrangeLoop 2010 talk</A>.
Soon after that talk, I speculated that documenting
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2010-10.html#e2010-10-30T13_01_58.htm">
   functional design patterns</A>
would help ease FPs into the mainstream.

I'm glad I took most of my day for this visit.  The
ISU CS department and chair Dr. Carl Chang graciously
invited me to attend a dinner this evening in honor
of Dr. Aho and the department's external advisory
board.  This gave me a chance to meet many ISU CS
profs and to talk shop with a different group of
colleagues.  A nice treat.
-----