Utah Open Source Planet

Via Lambda the Ultimate a pointer to a paper by Alessandro Warth and Alan Kay (PDF) called "Worlds: Controlling the Scope of Side Effects". I didn't get as much out of reading the abstract as I did from the opening paragraphs of the intro:

Suppose that, while browsing the web, you get to a page that has multiple links and it is not clear which one (if any) will lead to the information you're looking for. Maybe the desired information is just one or two clicks away, in which case it makes sense to click on a link, and if you don't find you're looking for, click the back button and try the next link. If the information is more than a few clicks away, it might be better to open the link in a new tab in which you can explore it to arbitrary depths. That way, if you eventually decide that wasn't the way to go, you can close the tab, and easily try a different path. Another option is to open each link in its own tab, and explore all of them "concurrently".

Something like the tabs of a web browser would be even more useful in a programming language, where undoing actions is a lot trickier than clicking a back button. As an example, consider the task of programming a robot to open a locked safe, as shown in Figure 1. There are two keys, A and B (each in its own room), but only one of them unlocks the safe. Using a conventional programming language, we might tell the robot to grab key A from room A, then go to the safe and try to unlock it. At this point, if we find that key A does not open the safe, we probably want to have the robot clean up after himself before trying the next alternative (nobody likes a messy robot). So we must tell the robot to take key A back to room A, and then return to its initial position.

In a programming language that supports "tabs", these clean-up actions would not be required: we could simply open a new tab, and inside it try to open the safe with key A. If A turns out to be the wrong key, we can simply close this new tab to return to the initial conditions.

This paper explores the idea of "tabs for programming languages", which we call worlds.

I like this idea. I like that they used Javascript to build their prototype even more. Javascript's extensibility and flexibility make it an interesting place to explore new programming constructs.

Tags: programming+languages javascript design

I love how Javascript libraries like JQuery require people to use thunks all over the place:

 $(document).ready(function() {
   $("#orderedlist li:last").hover(function() {
     $(this).addClass("green");
   },function(){
     $(this).removeClass("green");
   });
 });

The functions without parameters are called thunks and their purpose is to delay the evaluation of the code in argument positions, circumventing standard applicative order evaluation. Here's hoping that future languages--even future versions of Javascript--take this need into account and add real linguistic features for delayed evaluation. Oh wait--Lisp already does and it's only 50 years old.

Tags: javascript programming+languages thunk

The system we're building at Kynetx includes a domain specific language that uses rules to create JavaScript programs that get sent down to the browser. I've documented our decision to use a domain specific langauge and our choice of Perl in other posts.

When I started this project, I was reading Mark Dominus' book Higher Order Perl and started using his HOP parser to play around with. One thing led to another an before you know it I had a full blown language parser in HOP without giving much thought as to whether or not I'd made the right choice.

I found the HOP parser to be pretty flexible, but it has it's quirks. More importantly, I didn't like the BNF specification format and so I was constantly trying to keep the spec and the implementation in sync. Better if I could just use the spec as the implementation 'ala Bison. Don't get me wrong, this is a great book with lots of wonderful ideas, but I wanted something else for the parser.

As I added more and more features to the language, it got to where I'd dread making the parser changes. Recently, I decided I had to significantly beef up the predicate expressions and thought it would be a good time to change out the parser as well.

A few months ago I picked up Christopher Frenz's Pro Perl Parsing in anticipation of just this day. Reading through it illuminated my choices and ultimately, I picked Damian Conway's Parse::RecDescent, a recursive descent parser over the other contender, Parse::Yapp. The reasons for my choice were partly esthetic and partly a trust in Damian. The main thing I was after was a parse spec that I could read and compile and RecDescent seemed great in that regard.

The biggest downside of RecDescent is that there's no associated Lexer. For most things that's not a big deal since terminals can be specified as regular expressions. The place where it really bit me was comments. Removing comments is trickier than you'd think because you don't want to process "start of comment markers" inside any quotes. With a lexer, that's easy; without one, it's more problematic. Writing the regexp to remove comments took me a while to get right. I ended up using a modified version of the solution given in this FAQ. The problem with most solutions, including Regexp::Common, which has a language comment module, is that they don't account for comment markers in quotes.

All in all, rewriting the parser was a good exercise and I'm happy with the choice of RecDescent. Here's a sample production from my file:

decl: VAR '=' VAR ':' VAR '(' expr(s? /,/) ')'
      {$return =
       {'lhs' => $item[1],
        'type' => 'data_source',
        'source' => $item[3],
        'function' => $item[5],
        'args' => $item[7]
       }
      }
    | VAR '=' 'counter' '.' VAR
      {$return =
       {'lhs' => $item[1],
        'type' => $item[3],
        'name' => $item[5]
       }
      }
    | VAR '=' HTML
      {$return =
       {'lhs' => $item[1],
        'type' => 'here_doc',
        'value' => $item[3]
       }
      }
    | 

This production for decl has three alternates. Each has a separate return value (a hash) that represents the portion of the abstract syntax tree created for that part of the input.

If you decide to give Parse::RecDescent a try, here are some resources:

• The Parse::RecDescent documentation
• The Parse::RecDescent tutorial
• The Parse::RecDescent FAQ
• An O'Reilly getting started-style tutorial
• An example showing SQL CREATE TABLE statements

Reading the documentation and the FAQ thoroughly is highly recommended. There's lots of little tricks that can make your job easier.

My job, replacing an existing parser, was made easier by the fact that I'd previously built a pretty thorough test suite in Perl for the parser and some related modules. So once I got the language spec pretty much complete, I started running the tests and correcting errors as they cropped up. In a few hours, I'd solved all the problems and was confident my parser was ready to go. Definitely the way to go.

At any rate, now I've for a shiny new parser that I can go modify. Fun!

Tags: kynetx perl programming+languages parsing

Dave Cross has a piece on why corporations hate Perl. He's being a little hyperbolic (as he admits)--not everyone hates Perl, but he's right in noting that there is a backlash against it. He says:

I was talking to people from one such company last night. The Powers That Be at this company have announced that Perl is no longer their language of choice for web systems and that over time (probably a lot of time) systems will be rewritten in a combination of Java and PHP. Management have started to refer to Perl-based systems as "legacy" and to generally disparage it. This attitude has seeped through to non-technical business users who have started to worry if developers mention a system that is written in Perl. Business users, of course, don't want nasty old, broken Perl code. They want the shiny new technologies.

And so, in a matter of months, the technical managers at this company have create a business environment where Perl is seen as the cause of most of the problems with the current systems. It's an impressive piece of social engineering

From Why Corporates Hate Perl - O'Reilly ONLamp Blog
Referenced Wed Aug 20 2008 10:43:00 GMT-0600 (MDT)

He labels this kind of things "anti-Perl social engineering." I've run into similar feelings.

At Kynetx, our systems are built in Perl and Ruby. We use Rails to create the user facing pieces, but the engine, that part that needs to run fast, is written as an Apache module in Perl.

I've noticed that when I explain the language choice to people I almost always have to answer the spoken or unspoken question: "Perl?? Really? Why Perl?" After I explain the architecture and the reasons behind the decision, they're almost always satisfied, but there's a definite stigma.

I'm doing a talk next week at the Utah Open Source Conference (Friday morning at 10am) on using Apache as an application server. There are some significant advantages and Apache offers some real great application support that is largely untapped. But to talk advantage of it, you're pretty much stuck with C...or Perl. Given that choice the decision is a no-brainer. I'll be putting my thoughts together for the talk later this week or next week and promise to blog the ideas.

Still, the idea that Perl is an old crusty language couldn't be more wrong. I've been programming in Perl for nigh on 15 years now and I don't think it's ever been more interesting. Perl sports the best collection of libraries of any dynamic language and supports modern engineering practices like modules, objects, and testing. I've seen ugly Perl code--heck I've written it--but that's not Perl's fault.

I spoke with a local company last week that has been a Perl shop but is moving to Java. I smiled because I know that means there will be a lot of unhappy Perl programmers there who I can hire later! :-)

I'll continue to proudly carry the torch for Perl.

Tags: kynetx perl programming+languages

We all know that Intel and AMD have punted. They can't keep building larger, faster chips for a variety of technical and economic reasons, so they have started placing multiple cores on a single chip. This, in theory, maintains the overall processing power and is easier to build. There's just one catch: it's much harder to program because to make use of that power, you have to program concurrently.

Don't get me wrong. I'm not complaining. Microprocessor engineers have saved programmers from the hassles of concurrency for years. That's as it should be: get it right once at the lower level to free programmers higher up the abstraction hierarchy to think about the domain problem being solved.

But, alas, that world has come to an end. It's only a matter of time before chips with 8, 16, 32, and, eventually, 1024 cores appear. How will we program them?

Traditional tools for managing concurrency fall short. Processes and even threads are too course grained. Fine grained concurrency primitives like monitors and conditional variables are prone to error. Fabulously prone to error.

But a new abstraction based on transactional memory is gaining traction and will probably land in your favorite programming language in the near future. Simon Peyton-Jones or Microsoft Research spoke about transactional memory at OSCON. We've got it on IT Conversations:

Simon Peyton-Jones of Microsoft Research introduces a new tool called Transactional Memory to simplify concurrent programming. Due to the increasing prevalence of multi-core hardware, concurrent programming is becoming more and more important. Unfortunately, the most common tools for handling concurrency, locks and condition variables, are over 30 years old and fundamentally flawed. Problems that are simple undergraduate assignments in sequential programming become publishable results when done with concurrency.

Transactional Memory borrows the concept of an atomic transaction from databases. Rather than locking resources, a code block is marked as atomic, and when it runs, the reads and writes are done against a transaction log instead of global memory. When the code is complete, the runtime re-checks all of the reads to make sure they are unchanged and then commits all of the changes to memory at once. If any of the reads are dirty, the transaction is rolled back and re-executed. This, when combined with additional tools for blocking and choice, allows program to remain simple, correct, and composable while scaling to many threads without the additional overhead that course grained locking incurs.

Listening to this talk will give you a fair understanding of what transactional memory is all about. If you're a developer and have only enough time to listen to one IT Conversations talk this week, this is the one.

Tags: itconversations concurrency haskell programming+languages

Tyler Close answers questions after his talk (click to enlarge)

Tyler Close of Waterken fame presented a way of using promises to produce succinct JavaScript (and Java) code for doing multiple asynchronous requests with a Web server. The idea of promises in asynchronous systems was developed by Barbara Liskov in the late 80's. Tyler has a tutorial online. I also found this description from Brian Lothar of Web calculus which discusses promises in that context. Very interesting stuff. I think this was my favorite presentation of WWW2008.

Tags: www2008 javascript programming+languages

Joel Spolsky has a great, understandable description of what MapReduce is and why you might care. He also speaks to the benefit of learning functional programming, even if your first job interviewer isn't going to ask you "Have you even programmed in {Lisp, Scheme, Haskell}?" We're all going to care a lot more about things like MapReduce as the number of cores on a chip goes up exponentially.

Tags: programming+languages CS330 parallel+programming

John McCarthy (click to enlarge)

He wasn't on the program, but this morning's keynote was given by Professor John McCarthy--the inventor of LISP and coiner of the term "artificial intelligence."

This morning, he's talking about Elephant 2000, a programming language designed for writing programs that interact with people. One of the things he points out that I find interesting is the idea that the compiler should generate required data structures without the user having to specify them. I'm not sure how that works from his explanation, but I'm certain that if we want languages that admit more parallelism, this is a feature that would help.

He describes the idea of ascribing believe to a thermostat. He uses a simple system like a thermostat not because it's necessary to understand the operation of thermostats, but rather because it's useful for understanding the nature of belief.

ELephant programs have input and output specifications since their goal is human interaction. They also need accomplishment specifications.

He gives some examples of Elephant programs. This, for example sets is a program saying that if the flight isn't full the make a commitment to the passenger and then communicate that act.

if !full(flt) then accept.request(make commitment(admit(psgr,flt)))
  answer.query exists commitment admit(psgr, flt).

There are more examples online. Obviously, the notation itself is clean. The question is whether you can do something with the semantics associated with the notation. Unfortunately, Professor McCarthy ran out of time and we didn't really get to the punch line, I think.

Tags: cs330 lisp etech etech08 programming+languages

Fran Allen delivers Organick Lecture (click to enlarge)

Fran Allen was the Turing Award winner for 2006. This afternoon she's giving the University of Utah's Organick Memorial Lecture. I've reported on some of these in the past few years:

• Jim Gray on Distributed Computing Economics
• Vint Cerf on Internet Challenges
• Alan Kay: Is Computer Science an Oxymoron?
• Alan Kay: The 100 Dollar Laptop and Powerful Ideas
• Jeannette Wing on Computational Thinking

I try to come every year. I find it's something I'm inspired by each time.

The grand goal of high performance computers right now is a 1 petaflop machine. This requires 1,000,000 gigaflop processors. Wow. She shows a semilog plot of peak speed vs year introduced that is a linear line (Moore's law at work).

Much of Allen's work in the 80's and early 90's was around the PTRAN system of analysis for parallelism. The techniques are used, for example in the optimization stage of IBM's XL family of compilers.

Because more and more transistors are being placed on chips, they're using more and more energy--getting hotter. Part of the solution--which we're seeing play out--is multi-core chips. This requires parallelism to achieve the performance users expect. But making use of multi-codes requires that tasks be organized by either users or software to run in parallel.

By 2021, there will be chips with 1024 cores on them. Is parallelism the tool that will make al these ores useful? John Hennessey has called it the biggest challenge Computer Science has every faced. He has credentials that might make you believe him. Allen says that it's also the best opportunity that Computer Science has to improve user productivity, application performance and system integrity.

For parallel (superscalar, etc.) architectures, compilers--software--have been used to automatically manage scheduling tasks so that they can operate in parallel. What about those techniques will be useful in this new world of multi-cores?

Allen says we need to get rid of C--soon. C, as a language, doesn't provide enough information to the compiler for it to figure out interdependencies--making it hard to parallelize. Another way to look at it is that pointers allow programmers to build programs that can't be easily analyzed to find out which parts of the program can be executed at the same time.

Another factor that makes parallelization hard is data movement. Allen offers no silver bullet. The latency of data movement inhibits high performance.

The key is the right high level language that can effectively take advantage of the many good scheduling and pipelining algorithms that exist. If we don't start with the right high level language, those techniques will have limited impact.

She presents some research from Vivek Sarkar on compiling for parallelism. Only a small fraction of application developers are experts in parallelism. Expecting them to become such is unreasonable. The software is too complex and the primary bottleneck in the usage of parallel systems. X10 is an example of a language (object oriented) that tries to maximize the amount of automatic parallel optimization that can be done.

Major themes include cross-procedure parallelization, data dependency analysis, control dependency analysis, and then using those analyses to satisfy the dependencies while maximizing parallelism.

Useful parallelism depends on the run time behavior of the program (i.e. loop frequency, branch prediction, and node run times) and the parameters of the target multiprocessor. Finding the maximal parallelism isn't enough because it probably can't be efficiently mapped on the multiple cores or processors. There is a trade off between the partition cost and the run time. Finding the intersection gives the right level of parallelism--the level that is the most efficient use of available resources. Interprocedural analysis is the key to whole program parallelism.

One of the PTRAN analysis techniques was the transform the program into a functional equivalent that used static single assignment. This, of course, is what functional programming enthusiasts have been saying for years: one of functional programming's biggest advantages is that functional programs--those without mutation--are much more easily parallelized than imperative programs (including imperative-based object oriented languages).

There's a long list of transformations that can be done--everything from array padding to get easily handled dimensions to loop unrolling and interleaving. Doing most of these transformations well requires detailed knowledge of the machine--making it a better job for compilers than humans. Even then, the speedup is less than the number of additional processors applied o the job. That is, applying 4 processors doesn't get you a speedup of 4--more like 2.2. The speed up--at present--is asymptotic.

Tags: events utah parallel+computing programming+languages functional+programming

I caught a little flack in response to my post calling attention to Steve Yegge's recent essay "Portrait of a Noob." In particular Levi thought I was out of line for endorsing something so inflammatory:

"People who approach programming differently than I do are insecure n00bs"

That's a great attitude for a professor to endorse in a public forum. Steve's rant is nothing more than hot air attempting to justify his personal preferences at the expense of others. It makes you feel good because his preferences are the same as yours. The fact remains, however, that there's no real meat; it's just the evisceration of a straw man.

Dynamic languages and agile methodologies (whatever those vague terms mean today) are great, but so are modeling tools and static program analysis. Different tools for different jobs, etc. No one needs to be called insecure or a 'n00b'.

From Phil Windley's Technometria | Types as Comments
Referenced Tue Feb 12 2008 08:37:20 GMT-0700 (MST)

We're not talking about your taste in clothes or furniture. We're talking about a way of working that can be right or wrong. This isn't simply a matter of personal preference. We like to wave it all away with "depends on the situation" kinds of comments, but that's a cop out for the most part.

I believe that there are styles of programing and of organizing large programming projects that are better than others--not simply a matter of style. Businesses, particularly small ones can gain significant advantages by choosing one language or style over another. This is not simple a matter of taste.

That said, circumstances often dictate choices. I'm in the middle of a project right now, for example, where the right architectural choice was to use the Apache Web server as the application server. That requires writing Apache modules and that means C or Perl. No other languages offer complete solutions in that space. (I chose Perl.)

A few specific comments on the Yegge article

1. You need to read Yegge's entire article--or at least skim it--not just read the pull quote I used which is the most inflammatory part of an otherwise long article. Maybe you did...
2. Yegge makes some interesting and useful points about static analysis and it's sometimes dubious value (yes, I'm now stating my opinion).
3. Static type analysis is taken by so many people as "the right way" and dynamic type analysis as "the lazy way." I see part of my role as an educator to challenge that assumption.
4. No matter what kind of type system you use, you need to think about types. That's part of programming. What level of tool support is appropriate depends in large part on what the programmer is comfortable with.
5. That said, for large programming projects (which I am also leery of), static modeling allows the automation of large parts of the refactoring code and other tasks. More power to them.

So, in summary, I do think that Yegge's post (and many of his others) is delightful read that challenges many preconceived notions about types and forces exactly the discussion we're having now. "It worked!", I think Steve would say.

Tags: programming programming+languages kynetx

One of my students, Duane Johnson, asked me this morning if I'd heard of the IO programming language. I hadn't. Looking around, it looks like a fun little language.

IO is a "pure" object oriented programming language with a simple syntax. IO is a prototype-based OO language. Consequently, Javascript programmers will find the sample code pretty easy to follow. IO's reflective capabilities are very impressive.

IO isn't, as far as I can tell, ready for your next programming project--yet. It's still experimental. Still, it's good to see new languages spring up. There are good ideas to be had and the best way to propagate them is by making them work.

Tags: programming+languages cs330

Here's a good, short artcile from Raganwald on the trade-off between intuitiveness and programming languagge expressiveness. Most of the article is a few quotes. The meat is at the bottom.

Is Ruby's for loop an improvement over Java? By how much? Ruby's big win over Java in that regard is the ease with which you can use Enumerable's collect, select, detect, and inject methods. Which, of course, are not familiar to the programmer with a grounding in for loops. They require study to understand. But once understood, they make code easier to read thereafter.

When you're building a new notation, power doesn't come from replicating the familiar. Another way to look at this: if learning a new language isn't uncomfortable or a little painful--if there's no learning curve to speak of--you aren't gaining much.

Tags: programming+languages cs330

Here is proof positive that the utility of a domain specific language depends on the domain.

Tags: programming+languages humor cs330