INTERNATIONAL LISP CONFERENCE 2010 - HIGHLIGHTS and CALL for PAPERS

With the usual apologies to those who receive multiple copies of this...

 INTERNATIONAL LISP CONFERENCE 2010 - HIGHLIGHTS and CALL for PAPERS 

Important Dates:
~~~~~~~~~~~~~~~~

 * Deadline for all submissions (FIRM): September 6, 2010
 * Early registration: September 16, 2010
 * Author notification: September 20, 2010
 * Final paper due (in electronic form): October 5, 2010
 * Conference: October 19-21, 2010


Invited Speakers:
~~~~~~~~~~~~~~~~~

We are proud to announce that, for the 2010 edition, we will have the
following invited talks:

 * Lawrence Hunter
     Building a Mind for Life

 * Jans Aasman
     AllegroGraph and the Linked Open Data Cloud

 * Marc Feeley
     Gambit Scheme: Inside Out

 * Peter Seibel
     Common Lisp Standardization: The Good, the Bad, and the Ugly

 * Don Syme
     F#: Taking Succinct, Efficient, Typed Functional Programming 
     into the Mainstream

 * Lowel Hawkinson
     Lisp for Breakthrough Products

More information about speakers and talks is available at
http://www.international-lisp-conference.org/2010/speakers


Registration:
~~~~~~~~~~~~~

Rates for Early Registration (before or on September 16, 2010)

ALU member
 & ACM member      $355
 & ACM non member  $390
 & Student         $150

ALU Individual Sponsors
 & ACM member      $280
 & ACM non-member  $315
 & Student         n/a

non-member of ALU
 & ACM member      $430
 & ACM non-member  $465
 & Student         $165

Rates for Late Registration (after September 16, 2010 & Onsite)

ALU member
 & ACM member      $440
 & ACM non member  $485
 & Student         $185

ALU Individual Sponsors
 & ACM member      $365
 & ACM non-member  $410
 & Student         n/a

non-member of ALU
 & ACM member      $515
 & ACM non-member  $560
 & Student         $200

Due to colocation, registration must be done using ILC/SPLASH'10
unified registration forms available at http://splashcon.org/

Please note that the registration page (page 3) has the option "SPLASH
(OOPSLA/Onward!)" selected by default.  If you are only planning to
attend ILC, don't forget to deselect that option.


Travel and Accommodation:
~~~~~~~~~~~~~~~~~~~~~~~~~

SouthWest Airlines offers low fares into Reno but requires booking
online at www.southwest.com

John Ascuaga's Nugget offers reduced rates for ILC participants.
Please, visit http://splashcon.org/ to obtain the group code.


Scope:
~~~~~~

Lisp is one of the greatest ideas from computer science and a major
influence for almost all programming languages and for all
sufficiently complex software applications.

The International Lisp Conference is a forum for the discussion of
Lisp and, in particular, the design, implementation and application of
any of the Lisp dialects.  We encourage everyone interested in Lisp to
participate.

We invite high quality submissions in all areas involving Lisp
dialects and any other languages in the Lisp family, including, but
not limited to, ACL2, AutoLisp, Clojure, Common Lisp, ECMAScript,
Dylan, Emacs Lisp, ISLISP, Racket, Scheme, etc.

Topics may include any and all combinations of Lisp and:

 * Language design and implementation
 * Language critique
 * Language integration, inter-operation and deployment
 * Applications (especially commercial)
 * 'Pearls' (of wisdom)
 * Experience reports and case studies
 * Reflection, meta-object protocols, meta-programming
 * Domain-specific languages
 * Programming paradigms and environments
 * Parallel and distributed computing
 * Software evolution
 * Theorem proving
 * Scientific computing
 * Data mining
 * Semantic web

We also encourage submissions about known ideas as long as they are
presented in a new setting and/or in a highly elegant way.

Authors concerned about the appropriateness of a topic may communicate
by electronic mail with the program chair prior to submission.

Accepted papers will be published in the ACM Digital Library (PENDING).

Papers must be written in English and submitted electronically at
http://www.easychair.org/conferences?conf=ilc2010 in PDF or WORD
format.  Final submissions must not exceed 15 pages and need to use
the ACM format, for which templates can be found at:
http://www.acm.org/sigs/pubs/proceed/template.html.

Each paper should explain its contributions in both general and
technical terms, identifying what has been accomplished, explaining
why it is significant, and comparing it with previous work. Authors
should strive to make their papers understandable to a broad audience.
Each paper will be judged according to its significance, novelty,
correctness, clarity, and elegance.

The official language of the conference is English.  Some further
information is available at the conference web site, with more details
added later.  See: http://www.international-lisp-conference.org/

Technical Program:
~~~~~~~~~~~~~~~~~~

Original submissions in all areas related to the conference themes are
invited for the following categories.

 * Papers: Technical papers of up to 15 pages that describe original
   results or explain known ideas in new and elegant ways.

 * Demonstrations: Abstracts of up to 4 pages for demonstrations of
   tools, libraries, and applications.

 * Tutorials: Abstracts of up to 4 pages for in-depth presentations
   about topics of special interest for at least 90 minutes and up to
   180 minutes.

 * Workshops: Abstracts of up to 4 pages for groups of people who
   intend to work on a focused topic for half a day.

 * Panel discussions: Abstracts of up to 4 pages for discussions about
   current themes. Panel discussion proposals must mention panel
   members who are willing to partake in a discussion.

 * Lightning talks: Abstracts of up to one page for talks to last for
   no more than 5 minutes.

Depending on the technical content, each submitted paper will be
classified by the program committee as either a technical paper or as
an experience paper; and authors will be informed about this
classification.  Note that all interesting submissions are considered
valuable contributions to the success of the ILC series of
conferences.  As in past ILC's since 2007, accepted papers in both
categories will be presented at the conference, included in the
proceedings, and submitted to the ACM digital library.


Organizing Committee:
~~~~~~~~~~~~~~~~~~~~~

 * General Chair:
   JonL White - The Ginger IceCream Factory of Palo Alto, ALU

 * Program Chair:
   Antonio Leitao - Instituto Superior Tecnico/INESC-ID

 * Conference Treasurer:
   Duane Rettig - Franz, Inc., ALU Director

 * Publicity Chair:
   Daniel Herring - ALU Director

 * ALU Treasurer:
   Rusty Johnson - TASC, Inc., ALU Director


Program Committee:
~~~~~~~~~~~~~~~~~~

 * Antonio Leitao - Instituto Superior Tecnico/INESC-ID, Portugal
 * Alex Fukunaga - University of Tokyo, Japan
 * Charlotte Herzeel - Vrije Universiteit Brussel, Belgium
 * Christophe Rhodes - Goldsmiths College, University of London, UK
 * Didier Verna - EPITA Research and Development Laboratory, France
 * Duane Rettig - Franz, Inc., USA
 * Giuseppe Attardi - University of Pisa, Italy
 * Jeff Shrager - Symbolic Systems Program, Stanford University, USA
 * Joe Marshall - Google, Inc., USA
 * Julian Padget - University of Bath, UK
 * Keith Corbett - Clozure Associates, USA
 * Kent Pitman - PTC, USA
 * Manuel Serrano - INRIA Sophia Antipolis, France
 * Marc Feeley - University of Montreal, Canada
 * Marie Beurton-Aimar University of Bordeaux 1, France
 * Mark Stickel - SRI International, USA
 * Matthias Felleisen - Northeastern University, USA
 * Scott McKay - ITA Software, USA


Contacts:
~~~~~~~~~

 * Questions: ilc10-organizing-committee at alu.org

 * Program Chair: ilc2010 at easychair.org

For more information, see http://www.international-lisp-conference.org/

P ≠ NP (part 2 correction)

In the previous post I said that one example of an NP problem is “Check if two computer programs always produce the same output.” jkff commented:

The "check if two computer programs always produce the same output" is not NP. It's simply undecidable and cannot be solved in any amount of time.

I blew it and oversimplified the statement. At Wikipedia, they have a list of commonly known NP-complete problems and on that list is “Inequivalence of simple functions.” I seriously mangled the meaning because I was daydreaming about assembly code. What I should have done is put some restrictions on what sort of computer program I meant.

First, we have to restrict ourselves to programs that we can prove will always return an answer within a given amount of time. A computer program that does not have any loops, backward jumps (gotos), subroutine calls, or exceptions should simply run from from start to finish. Second, we do not allow the program to save any state between runs; the output must be a pure function of the input. Furthermore, we restrict the input to a finite set (for example, integers that expressible in a single 32-bit word). Now suppose we have two such programs. To prove they are not equivalent, we need to find a 32-bit integer input that makes each program give a different answer. By trial and error we will eventually find such an input or exhaustively show that there is none. However, if someone were to claim that a particular input produced different output, then it is easy to check by simply trying it out.

P ≠ NP (part 2)

As I mentioned in my last post, P and NP are commonly encountered complexity classes. Knowing what complexity class a problem is in can give us some idea of how difficult it may be to solve the problem. So what's the difference between P and NP? I don't want to get into the technical definition of P and NP, so I'm going to make broad generalizations that aren't technically rigorous, but will give you a feel for the difference.

Problems in class P are generally considered “tractable” by computer scientists. By this we mean that a computer can probably solve such a problem efficiently and relatively quickly. Recall that the complexity classes relate the ‘number of pieces’ to the difficulty. If you can solve a particular problem in P, then a similiar problem with a ‘larger number of pieces’ is likely within your grasp (and if not, it is usually a question of upgrading to a better computer). Problems in class P are the ‘meat and potatoes’ of computer programs.

Before I discuss NP, let me introduce the complexity class EXPTIME. EXPTIME is where you find some really hard problems, like computer chess or Go. It is true that there are computers that can play chess really well, but if we were to modify the rules of chess to add a couple of new pieces and make the board 9x9 instead of 8x8, it would greatly increase the difficulty of the game. Problems in EXPTIME are generally considered “intractable”. By this we mean that a computer will have a hard time solving such a problem efficiently and quickly. And if you are able to solve a particular problem in EXPTIME, then a similar problem with just ‘a few more pieces’ is likely beyond your grasp, no matter how fancy a computer you might buy. Problems in class EXPTIME take a lot of time and money to solve.

So what about NP? Problems in NP are quite curious. They seem to be very difficult to solve, much like EXPTIME problems, but they have the unusual property that it is very easy to check if a solution is correct. Let me illustrate: if I showed you a chess position and claimed that it was a good position for white, you'd have to do a lot of work to verify whether my claim was true. In fact, it would have to be about the same amount of work it took me to come up with the position in the first place. On the other hand, if I were to show you a jigsaw puzzle and claim that I had finished it, you could tell at a glance whether my claim were true. Problems in NP seem to be much harder to solve than problems in P, but as easy to verify as problems in P. That is a little weird.

Problems in NP are often encountered in computer programs, and many of these kind of problems, although very difficult to solve, have approximations that are relatively easy. In some cases, when a perfect solution is not needed, one that is ‘good enough’ will be a lot easier to compute. Another weird thing is that a lot of problems in NP don't sound at all like they'd be hard to solve. Here are some examples:

• Take a group of people and divide them into two subgroups such that both subgroups have exactly the same amount of change in their pockets. (No, you aren't allowed to move the change around.)
• Find the shortest path that visits all the major landmarks in a city.
• Check if two computer programs always produce the same output.  Whoops!  I blew this one.  Check the next posting.

There is one final bit of weirdness. It is easy to prove that EXPTIME problems are much harder to solve that P problems, but no one has proven that NP problems are harder than P problems. (or that they aren't harder than P problems!) This isn't for lack of trying. Many smart people have worked on a proof for some time. There's a million dollar prize for the first person to prove this one way or the other. Recently, Vinay Deolalikar of HP Labs claimed that he has a proof. Unfortunately, other experts in the field have pointed out flaws in the proof that may invalidate it.

P ≠ NP (part 1)

I'm sure most people who read this blog know a bit about what this means, but I want to try to explain it in a way my mom could understand. I won't go into excruciating detail, and I'll probably gloss over interesting points.

Let's start with an analogy. Suppose you go to the store to buy a present for your nephew. He likes jigsaw puzzles, so you want to get him one. He's going to be twelve years old, so you need to find one that has the appropriate challenge. A simple one with four pieces might be great for a two year-old, but your nephew would find that boring. A big one with ten thousand pieces is probably too much for him. You know he just finished one with five hundred pieces, so you pick one with six hundred pieces because it won't be too easy, but not too frustrating. What you are doing is estimating the complexity of the puzzle.

When you get to the store you find that they are sold out of jigsaw puzzles. They have a variety of other puzzles, though. They have a Rubik's cube, a Sudoku book, some cryptograms, a Tower of Hanoi, etc. They have models you can put together as well. But these things aren't jigsaw puzzles. You can't estimate the complexity the same way. A model with five hundred pieces would be quite a bit more difficult to assemble than a jigsaw puzzle with the same number of pieces.

Perhaps you look at the age ratings for the various puzzles. The eight-piece Tower of Hanoi puzzle is rated for ages ten and up, so maybe a twelve piece? The standard 3x3x3 Rubik's cube is rated for ages eight and up, but would the 4x4x4 be too hard or too easy? What about the 5x5x5?

The kind of rating system you use to describe the difficulty of a puzzle is analogous to the “complexity class” of a problem. The complexity class roughly describes how hard a problem will be to solve, and more importantly, how much harder ‘big’ problems are compared to the ‘small’ ones. Here's what I mean: if I take a jigsaw puzzle, any jigsaw puzzle, and double the number of pieces in it, I'll make it roughly twice as hard (more or less). If I take a cryptogram and double the number of words in it, I'll actually make it a lot easier. If I take the Tower of Hanoi and double the number of discs, I'll make it incredibly harder, maybe even impossible. These puzzles are in different complexity classes.

As it turns out, a lot of puzzles are in the same complexity class as the jigsaw puzzle: the difficulty is reasonably proportional to the number of pieces. Adding a piece or two doesn't change things that much, and it is easy to figure out how long it will take to solve if you've done a few of them. A lot of puzzles are more like the Tower of Hanoi. Adding a single piece will double the amount of time it takes to solve them.

P and NP are complexity classes for problems you might want to solve on a computer. There are all sorts of rating systems, but everyone is familiar with the MPAA movie ratings. There are all sorts of complexity classes, but most computer scientists are familiar with P and NP.

I'll pause here because the analogy is wearing thin. The main point is that “P ≠ NP” is a statement about complexity classes. In particular, it talks about two of the most popular complexity classes and that is part of the reason it is interesting.

Rambling

Writing a blog is hard. I need practice so I'm going to ramble a bit.

First, I'm very pleased that Blogger has improved their comment spam detection. Every time I made a post I'd have to come back a day or two later and remove a bunch of pointless comment spam.

Second, I told my daughter that someone claims to have a proof that P ≠ NP. She replied “Well, now we know that N doesn't equal 1.”

I read through the proof and I confess that I don't get it. On the other hand, I think I want to get it, so I'll have to learn some interesting things.

Here's another thing I don't get.

`` E8 is any of several closely related exceptional simple Lie groups and Lie algebras of dimension 248''

``a simple Lie group is a connected non-abelian Lie group G which does not have nontrivial connected normal subgroups.''

``a Lie group is a group which is also a differentiable manifold, with the property that the group operations are compatible with the smooth structure.''

``a non-abelian group is a group (G, * ) in which there are at least two elements a and b of G such that a * b ≠ b * a.''

``a connected space is a topological space which cannot be represented as the union of two or more disjoint nonempty open subsets''

Happy 80th Birthday to Neil Armstrong

Neil Armstrong turns 80 years old today!

My definition

Here's my definition:

A computer program is a description of a process which is formal enough to be carried out by a machine.

Most of the other definitions describe a program as a ‘set of instructions’. Some of the definitions suggest that these instructions should be organized in some way, perhaps as a (linear) list. These instructions ‘make the computer do things’, ‘bring about a certain result’, ‘cause the computer to behave in a predetermined manner’, or ‘alter the contents of memory’. But these definitions have an explicit or implicit assumption: a sequential, imperative mode of thought.

Look at this Prolog code:

append(c(H,T), B, c(H,TB)) <= append(T, B, TB).
append(nil, B, B).

This code describes relationship of appending lists, but it doesn't specify how to accomplish the appending. Is the first clause an ‘instruction’ to build a list, or to take one apart? Are the clauses to be run in any particular order? Is there a deterministic ‘answer’?

What is a ‘computer program’?

This seems like a simple enough question.

Here's what the web says. A computer program is

1. a set of statements or instructions to be used directly or indirectly in a computer in order to bring about a certain result
2. what makes the computer do things
3. a set of instructions written in a programming language
4. an algorithm written in a language that a computer can understand
5. simply a long list of code written in another language
6. a set of instructions for altering the contents of various words in the computer's memory
7. a carefully thought out, step-by-step, set of instructions prepared by a programmer
8. an organized list of instructions that, when executed, causes the computer to behave in a predetermined manner
9. is a procedure (or algorithm) for performing some computation
10. a bunch of instructions run by a computer, just like a storybook is just a whole bunch of sentences read by the reader

Does anyone have any better definitions?