After Action Report: PADL 2006
Practical Aspects of Declarative Languages
Introduction
This is an highly-opinionated report on the presentations at the
PADL 2006. The sessions are presented chronologically, but are
tabled in the contents by topic, and cross-referenced by their
practicality (i.e. in what I found useful in the presentation).
Presentations
Retrospective
As you can see below, my critisms are very harsh. This begs two
questions: harsh against whom? and would I go again to a PADL?
The answer to the latter is resoundingly in the affirmative (as
William Byrd would pipe up: 't'): the density of
useful concepts I took away from this conference was much greater
than most other conferences I've attended, including, not
surprisingly, the POPL.
So, why so harsh in my reviews? Was I critizing the speakers?
In some cases, I was indeed critizing the speakers, particularly
when they sacrifice rigor for herd thinking (particularly when
they do not acknowledge such lapses), but in the main, my
criticisms, such as 'this topic does not interest me', was not a
criticism of the speaker, nor even the choice of topic (with the
caveat that of the 17 of the 33 papers accepted, the papers
accepted should be more practical and less
esoteric, if the reviewers chose academic curiosities
over less polished papers on the topic of applications
then I do fault the selection process), but a severe
criticism of me. What I mean here is that the PADL's
mission is to gather reports from the front-lines, as it were.
That's where companies, like mine, operate. So, companies, like
mine, including mine, should be submitting these
papers. We do not, and the PADL has suffered for
it.
In short, the PADL was what it set out to be -- a free exchange
of ideas of the application of research and an open channel
between researchers and industry. AND the PADL,
as good as it was, could be even better with more
practical, real, applications developed in the declarative style
showcased for all to see. It motivates the researchers ('my work
has revelance! an audience! a fan club!'), and it improves the
tools industry uses to deliver these applications ('you can
do that?'). Win/win. QED.
The Challenge
So you companies that use declarative programming ... you know
who you are (*cough* galois
*cough* ... um, Doug, what about you? Yeah, me, too), belly up to
the bar, 'cause drinks are on the house! (trans: submit
papers; you are not divulging company secrets, and you're gonna
get lots of neato ideas that will help you on your current
projects).
Day 1: Monday, January 9, 2006
| 9:00 am | Links: Linking Theory to Practice
for the Web |
| | Phil Walder |
| |
Phil presented a proposal for a functional language
to cover the three tiers of building web apps. *YAWN*
What came out of this talk was nothing immediately useful for us, but
he did ask a series of questions to which he didn't have answers. He had
the guts to go to lunch with a bunch of us logic programmers and was
willing to listen to the logic programming side of designing a language
and the trade-offs using that methodology. What I learnt ("Life Lessons") - first, tell everybody what you do not know how to do currently,
and ask how they do it
- second, mingle among the group that has a different
perspective than you or that knows stuff you don't What to learn ("Talk pointers") - Timbre is a functional concurrent programming
language (typed?)
- Hope first functional language to implement the
Hindey-Milner type system
- "Antinomies": n. things that are directly opposed.
|
| 10:30 am | Using CHRs to generate
functional test cases for the Java Card Virtual Machine
|
| | Sandrine-Dominique Gourand (presenter),
Arnaud Gotlieb |
| | Sandrine (or is it 'Dominique') presented a test generating
system that examines disjoint clauses of predicates and, by using
pattern-, or type-, matching generates appropriate unit test cases.
She pointed out the language JSL ('Jakarta Specification Language'
which has nothing to do with the much more popular Jakarta Struts)
which was used to generate the system to generate the test cases --
it's very Lisp-like. JSL is now an unsupported branch of COQ, a
theorem-prover. I talked with both Sandrine and Arnaud after the presentation, re:
automating unit testing; Sandrine gave me two papers to review along
those lines. The first was on
QuickCheck
for Haskell; the second was on using
Isabelle
to generate test cases from a specification. Life Lessons - CHRs (constraint handling rules) have real-world
applicability (beyond Sudoku): generating test cases.
- Theorem provers (COQ and Isabelle) have real-world
applicability -- generating comprehensive test cases.
Talk Pointers
|
| 11:00 am | Probabilistic-logical Modeling
of Music |
| | Jon Sneyers, et al. |
| |
Jon presented a learning system for music. The learning system was
implemented on "probabilist Prolog" (PRISM). It took 75 selections from
Bach pieces and ~25 selections from Mozart pieces. He used a
description language to model the significant parts of the musical
selections (rhythm, tone (polyphony), etc, but not many other facets
of music) as an ordered list of triples (triples of pairs for two
voices, triples of triples for three voices). He then fed these
triples under the appropriate selections as training sets. The
learning system was a Markov chain ("It took two lines of code to
implement in PRISM"). It properly classified all test cases (~30);
when he removed rhythm, it properly classified most of the the test
cases (~26/~30).
This program not only classifies, but also generates fresh example
selections from the learnt selections. Jon was pleased to report
snipplets sounded like things from the composers, but didn't sound
very good -- his pleasure was based on the implication that good
music is not machine generated (with a consequence that composers
still have a role).
Jon is currently pursuing a new approach, using CHRs for the learning
process. The work he presented is now two years old. Life Lessons
In the after-session Q&A, I asked Jon about the memory footprint.
Jon admitted that learning with the Markov Chains grows
exponentially with the size of the selection, so that's
why he used selections from music pieces, and not the entire
piece. Markov Chains or connectionist systems are nice and all, but there
is a large price to be paid for using them.
Talk Pointers - PRISM; a probablistic Prolog.
|
| 11:30 am | Modeling Genome Evolution with a
DSEL for Probabilistic Programming |
| | Martin Erwig and Steve Kollmansberger
(presenter) |
| |
Steve wrote a system in Haskell using monads to describe genome
interaction. As these interactions are stocastic (not deterministic),
the standard way to go about this is algorithmically: writing a
random number generator and assigning values. Steve chose a novel
approach: he created a data type called "Distribution" that
encompassed all possible (finite) values as well as their
probabilities. Then using monadic transform, he described several
basic operations (addition being the one that sticks in my mind) that
could be used directly under the transformation. Using this approach,
modeling the genetic interaction (which is more like an inhibitor)
become facile, reducing nearly to the point of simple arithmetic. Life Lessons
- Of course, data modeling eliminates the alternative algorithmic
implementation, so ...
- Consider novel data structuring approaches
before grabbing that same old algorithmic hammer.
Talk Pointers
|
| 2:00 pm | Using Dominators for
Solving Constrained Path Problems |
| | Luis Quesada, et al. |
| | Luis demonstrated that by using information of the
graph of the search for the shortest path (e.g. nodes 5 and 12
must be on the path, these nodes are said to dominate the path,
and if a particular mandatory node precedes another waypoint,
that mandatory node is said to dominate the waypoint), it allows one to
eliminate paths that do not lead to an eventual solution.
Talking with Luis after his presentation, I asked about ACO (Ant
Colony Optimization). He was familiar with the approach, having talked
with a research group studying it, but opted for this approach. ACO is
not guaranteed to terminate, dominator-search does. He and I also talked
about the problem our company is facing, and I drew out the problem on
a napkin. He said he had studied resource-constrained search paths for
the problem (vehicles that have limitted fuel supply), and asked me to
provide a more detailed problems summary, so we could look at ACO vs.
dominator approaches.
Life Lessons
- Luis' talk, while given in an abstract, theoretical, graph-theory
approach reaked of experience from solving real-world
problems. More presentations at PADL should have this same
smell.
- I was sure that ACO was the only way to go with our problem-space,
and after talking with Luis, I'm still pretty sure of this, but I've
also become aware of another possibility: that the problem, once
specified, may turn out to be so trivial as to need none of
this -- the "shortest path" may actually turn out to be the
smallest great circle, or some such. If one knows exactly what the
problem is (intuitively), then a specification description
might itself contain the solution.
- Know what else is out there. I'm glad that Luis
knew about ACO, considered its merits and decided on the dominator
approach. I don't necessarily agree with his conclusions, but I admire
his thoroughness.
Talk Pointers
|
| 2:30 pm | Adding constraint solving to
Mercury |
| | Ralph Becket, et al. presented by Zoltan
Somogyi (co-author) |
| |
Zoltan covered what the Mercury team is doing
to add constraint solvers as native constructs into the Mercury
language. One interesting thing that came out of this topic is that
the predicates that add constraints to the solver are
declarative, but those that read the state are
not. This, of course, raised eyebrows in the room (particularly
Phil Walder, who asked a question
about it). Zoltan explained this choice by stating that the solver
should be logically consistent, no matter the order in which
constraints are added (making added constraints declarative,
or order-independent), but reading out the solver's state (finding the
current solution set), actually results in a "write" elsewhere (into
users of the constraint solvers), in a way, destructively changing
the state of the program at large, and therefor a read is not
declarative. Zoltan owned that this is completely opposite to
prevalent declarative wisdom, but when examined in this light, is
consistent with the prevalent view.
As is always with these presentations, a holy war exploded. This
case: Prolog vs. Mercury, and on the subject of typing. How is this
even remotely related to the topic of this presentation? Isn't it
sweet that one
can go these genteel sessions to peer into the vaulted chambers of
academe? I always love a good brawl. *sigh* I would offer some
advice about how such fist-to-cuffs over such trivialities cements
views of the world at large about the researchers being out of touch
with reality and how that consequently makes adoption of research
ideas all the more difficult, but I know I would only be 1) wasting
my breath and 2) starting another pointless flame war.
Life Lessons
- Constraints ... who needs 'em? Dunno; but that's a good thing
that came out of this symposium: it points out things I don't know that
I don't know, so I bought Constraint-based Local Search by
Pascal Van Hentenryck and Laurent Michel, so I can learn a bit more
about the topic.
Talk Pointers
|
| 3:00 pm | A Hybrid BDD and SAT Finite
Domain Constraint Solver |
| | Peter Hawkins (presenter) and Peter Stuckey |
| |
Peter's presentation piggybacked on
Zoltan's in that he used the
Mercury constraint solver for this work. Peter noticed that SAT solvers
are very fast (with the cost of expressivity: their expressions are
booleans in propositional logic, ugh!), because SAT solvers 'learn' from
rejected branches, whereas regular constraint
solvers perform not so well (but allow inequalities, etc). So, what he
did was use a binary transformation (the BDD) to accumulate learned
knowledge from rejected branches on the regular constraint solver
in the form of proposition from a SAT solver. He also did some
redundancy elimination. The profiled results were very good for his
hybrid execution-time-wise. Not only that, because of this 'learning'
his constraint solver was able to tackle problems that other constraint
solvers choked on (SAT solvers also suffered because their limitted
syntax prevented formulating some constraint problems). Very cool.
BUT after the presentation I approached Peter. After
complimenting his presentation, I stated that it made no sense to me,
as I did not see a real-world application for constraint-based
programming. Peter was unable to provide
examples to me [that was exceedingly disappointing], but did refer me
to Pascal as an authoritative source, as his area of research is
constraints.
Life Lessons
- Use information learnt from rejected branches to
improve the search on new branches.
|
| 4:00 pm | Efficient top-down set-sharing
analysis using cliques |
| | Jorge Navas, Francisco Bueno and Manuel Hermenegildo
(presenter) |
| |
This presentation was about proving properties of Prolog programs,
such as parameter types and determinism, by using cliques (sets of
relations). Manuel demonstrated the system in action; it was slick!
It gave runtime feedback on a series of asserts he made about the
program (the assertions were ':-'/1 declarations in Ciao Prolog).
The key point of this presentation was that cliques could be represented
as power sets, so that 6 relations (xyz, xy, xz, x, y, z) could be
reduced to one powerset (over xyz). Then, by widening some assumptions,
the system was able to make more general inferences, but at the cost of
complete correctness.
Life Lessons
- Data representation! Using the power set,
instead of explicitly enumerating all the relations explicitly saves both
space and time, simplifying the programming task and the subsequent
debugging/maintenance.
|
| 4:30 pm | Automatic Verification of a
Model Checker by Reflection |
| | Bow-Yaw Wang |
| |
Bow needed to verify the correctness of his model checker (that he
built for what practical purpose? I was unable to determine this), and
had an epiphany: the model checker could itself be checked by
reflection; that is, by building a model of the model checker and
verifying the correctness of that model. Of course, this begs the
question (which, of course, was asked after the presentation, but,
surprisingly, not by me (someone else beat me to it)): how does one
stop this line of induction. Bow really didn't have a satisfying
answer for this (but, practically speaking, one can make a pretty good
determination that "enough" rigor has been applied...).
Model checking is all well and good, I suppose, but, from what I've
seen of it, it seems like a silly exercise: pre-production model
checking is based on requirements that will change during the
development process, and post-production model checking is a forgone
conclusion ("Hey! this working system really works! Fancy that!"). I'm
filing model checking under 'works of
"theoretical" interest'.
|
Day 2: Tuesday, January 10, 2006
9:10 am8
| Generic Cut Actions for External
Prolog Predicates |
| | Tiago Soares, Ricardo Rocha and Michel Ferreira
(presenter) |
| | The presentation noted that some Prologs, including XSB (*cough* Big
Surprise *cough* tabling
*cough*), had problems interacting with, e.g., C, particularly with
database cursors or other persistent structures that required eventual
deallocation. The problem is especially noticeable when a cut ('!'/0)
in the Prolog code prunes away the goal that calls the C deallocation
routine (go figure). Michel's solution was to modify the (in this case, Yap) Prolog
compiler so that the foreign interface required a C function to call
when Prolog encountered a cut. This C function is an extra argument
for each predicate defined by a foreign (C) function. This solves the problem for memory leaks, but I asked a different
question to the group. Dynamic languages pay a penalty whenever they
make a foreign call, something on the order of 40 for marshalling and
unmarshalling data between the languages. I asked was there a way
to represent the foreign interface natively, e.g. a database wrapper in
Prolog, not C; or, generally, is there a way to eliminate this
penalty.
The group shot me down. Zoltan said you either pay the penalty, or
write your own database, which (the latter) is a losing proposition.
Others concurred, saying that was in the nature of dynamic languages.
Zoltan later expressed surprise at the size of the penalty, saying he
observed only a factor of 2 for foreign calls in Mercury [*cough*
strongly typed means less marshalling *cough* Mercury's not
dynamic *cough*].
In a separate conversation over lunch, Michel explained to me the
raison d'être for this system was they built a classic
inductive system and stored the deductive database in MySQL (?), as the
deductions were numerous. I asked if his group had solved the problem
of inductive systems: a very slight perturbation in the data causes
such systems to fall into an undefined state or causes wildly incorrect
resulting rules. He said they hadn't, but were looking at that
problem.
Life Lessons
- Use statictical methods for induction (bayesian
or neural); classical inductive systems are just too delicate to be
useful with real-world problems.
|
| 9:40 am | Tabling in Mercury: Design
and Implementation |
| | Zoltan Somogyi (presenter) and Konstantinos
Sagonas |
| |
Zoltan presented tabling in Mercury given the constraints of the
type system. Given the system we are developing, tabling is not
a propos; I didn't get much out of this talk.
|
| 10:10 am | Incremental Evaluation of
Tabled Prolog: Beyond Pure Logic Programs |
| | Diptikalyan Saha and C. R. Ramakrishnan |
| |
Okay, here's the thing; you all
now know that tabling is not
one of my favorite topics, the the point of having two
talks on a compiler implementation detail
is what again? To prove that XSB Prolog doesn't do tabling correctly
presently? Isn't that clear enough already?
Anyway, what's the point of going in the beyond pure logic? Isn't
that going in a very bad direction? Perhaps one should explore
what happens when one moves toward pure logic, not away
from it? (hint, hint, Mercury, *cough*)
Life Lessons
- Never! Ever! use XSB Prolog: it tables incorrectly
and requires the user to turn off tabling
explicitly!
- Accomodating errors as a goal of design is
erroneous! Instead of accomodating flaws, eliminate them
(perhaps by going to a better system).
|
| 10:40 am | Controlling search space
materialization in a practical declarative
debugger |
| | Ian MacLarty and Zoltan Somogyi (presenter) |
| |
Holy Smart Debugger Design, Batman! This debugger,
instead of having you step through the code in the traditional manner,
does an inductive debugging search: it presents you with a predicate
with instantiated arguments and the result and ask if the result was
expective, if it wasn't it drills into the predicate, seeking the
cause of the disconnect, if it was, it moves on. Groovy!
Life Lessons - Prolog's traditional debugging system is wonderful; much better than
most every other thing out there, so it's unthinkable that something
could be better -- imagine the impossible; then create
it
- Having the computer handle drudge work, repetitive tasks, and
assisting the user in decision making ... What a
concept!
|
| 2:00 pm | LINQ: Reconciling objects,
relations and XML in the .NET framework: a Personal Perspective
|
| | Erik Meijer |
| |
Erik talked about the socialogical aspects of linking a
semi-equivalent of Haskell's typeclasses into Visual Basic, making
sure it was backwards compatible, even down to the IL. He also showed
how XML syntax could be weaved into VC procedures, allowing the
'copy-and-paste' coding style (the usual XML element instantiation
remains for those who wish to do it the longer, or more programatic,
way). He followed a whole side monologue about how the DOM-XML is
bad (oh, my goodness, how can that possibly be!) but not for
the usual reasons (ummmm, that would be, all of them?) but because
an element is entirely dependent on a document instance to exist, so,
things like moving a set of elements from one document to embed into
another are ridiculously hard. He solves this problem by reifying
element independently of the document. He solved this problem, and
probably thousands of others have, too, using the same approach. That's
called, 'reuse', right? One of the thrusts of his presentation
was that results from research were working their way into the
mainstream software engineering community.
Okay, a question: anything that permits and encourages bad
programming ('copy-and-paste' coding) ... that's good?
|
| 3:30 pm | A Generic Code Browser with a
Declarative Configuration Language |
| | Kris De Volder |
| |
Finally! a practical application! Kris demonstrated
a plugin for eclipse (the Java IDE) that used a mercury-like scripting
language to create on-demand code browsers. Slick! Kris was
also well-informed and reasonable: fully recognizing that he had
a small acceptance window ('5 seconds'), and a tiered expertise
base. So, he designed the tool so that most features were automatic
(GUI-selectable), some features obtainable via a regex-like query
system, and finally advanced features only required the full language.
He also saw his niche: smack inbetween the rigid prebuild gui
browsers and the nothingness of rolling your own browser from
scratch, and he documented this niche thoroughly. Bravo! an
unqualified success!
|
| 4:00 pm | Translating
Description Logic Queries to Prolog |
| | Zsolt Nagy, Gergely Lukácsy (presenter)
and Péter Szeredi |
| |
Gergely presented a system that he and his colleagues had
developed that converts description logic assertions and
queries (in the ALC description language, which is
developed from, and is, a frame logic) down to Prolog terms.
He spent some time showing the differences between ALC
and Prolog, particularly highlighting Prolog's closed-world
model (where if a fact is not known, it is false) and
ALC's open-world assumpution (OWA) model (where
something must be stated as false to be false; if something is
unknown, then it is simply unknown. This, of course, impacts
the semantics of negation: Prolog's negation as failure is not
congruent with the OWA model. But it also affects transitive
closures: he demonstrated Prolog's weakness (and the strengths
of frame logic) with the canonical Oedipus/Iocaste patricide
example (which brought forth chuckles from the audience when he
blushed on the moral implications of his example).
Given all this, Gergerly demonstrated the system at
efficiently reduced ALC terms and queries down to
Prolog. He also compared the results against other systems.
This system was very much faster than others. Gergerly pointed
out, in fairness, that other systems also handled other
description logic languages, so they were perhaps not fully
optimized for ALC. No matter: this system is a full
frame logic implementation, and it performs well; even finding
solutions to queries that other systems do not terminate, and
this system is very effective in ignoring "noise" in the
knowledge base (noise being in the form of many other terms
that have no relation to the queries being posed -- other
systems lag exponentially in the face of larger, noisier,
knowledge bases).
Life Lessons
- If you are a father, do not allow any of your sons
to be named 'Oedipus'!
- Too much generality in a tool can kill what you
need to do. The best tool for the job may not be the
most featureful.
Talk Pointers
|
| 4:30 pm | Querying Complex
Graphs |
| | Yanhong A. Liu (presenter) and Scott D. Stoller |
| |
Annie presented a system based on sets and regular
expressions that allowed intuitive querying of
(semi-?)structured data. This system converted the queries to
datalog-equivalents and eventually resulted in the query in C
code. The interesting thing about this system was that the
query itself was only half the answer, the other half of the
answer was a measure of the complexity of the query. In this
way the query could be reformulated so that the result would
entail less complexity. Very sweet!
Life Lessons
- You don't miss what you don't know.
Anyone, on seeing how complex their system is, sees the solid
benefit of this measurement. Why is this not everywhere?
Because nobody knows it is possible.
|
Endnotes
| 1 | As all of the talks in the "Practical" "Applications"
were neither practical (they were all used to further research
or as dissertations) nor applications (several speakers
thoughout the conference, when I
queried them about aspects of their presentation stated that the works
they discussed where under development still), I query the accuracy of
the topic heading for these talks. A saving grace is that all
of the talks on this topic did have results that were practical
and immediately usable for real-world applications, unlike what
some of the other presentations had to offer. |
| 2 | "Theoretical" as in
"yeah, I'll look into this
stuff after I incorporate all the practical stuff from the symposium into
the project, complete the project, build the world's fifth largest (if not
larger) supercomputer, build a demonstratively useful quantum computer
and finish the laundry." |
| 3 |
Also, I do not consider compiler implementations
or optimizations at all a practical application. The compiler is a tool
to provide the ability to build a practical application: it, per
se, is not. |
| 4 | Yes, there were two presentations on
tabling. Both of them I found to be very "useful" in a
"theoretical" sense of the word. |
| 5 | Okay, okay, so I am looking into constraints. This
does point out an issue with the symposium: it may point out things that
I don't know I don't know, but it wasn't very helpful in educating me
about the practical applications in these areas. |
| 6 | I think a more approapriate term for 'description
logics' or 'ontologies' is 'hooey'. Bluntly, descriptions
logics are as innovative and as useful as Java is ('the most distressing
thing to hit computing since MS-DOS' Alan Kay). With the set of claims
proponents are making grandiosely about knowledge representation, which I
must remind everyone is a similar set of claims the AI community was
making for symbolic representation of knowledge (what, again, is
description logic? Oh, the 'symbolic representation of knowledge'? Ah,
yes, we have a winner here!), in the same self-satisfied tone, just before
AI went dark for twenty years, AND with the bedfellows it has
(whispered: 'eggs'-'em'-'ill'), I am shocked that more gullible
consumers of this hogwash haven't made the obvious connections and
avoided this dead end... |
| 7 | The 'random' in "'random' testing" means 'comprehensive
with random generation of parameters', not 'a random selection
[e.g. not comprehensive] of possible tests'. |
| 8 | This is a departure from the published schedule;
the invited speaker for the morning was a no-show. |
| author: | Douglas M. Auclair
dauclair at hotmail dot com |
| date: | January 16, 2006 |
Copyright © 2006, Logical Types, LLC. All rights
reserved. |
