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 boughtConstraint-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 movestoward 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 |
|
| 3 |
|
| 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. |
(originally published January 16, 2006)
No comments:
Post a Comment