Yacc is of the Living Dead

The scientific process seems to evolve towards something like pop culture and music industry. For starters, we have publishing houses and record companies.

And then, there is a scientific article with the title "Yacc is dead" [1] which, quite possibly, has reached more people than all the accepted papers of the conference to which it was submitted.

Russ Cox criticized this paper quite harshly in an insightful blog post [2].

So, in short, the paper proposes a method that yields all parse trees and claims that the approach is "efficiently on average". The authors run a benchmark, but of course a benchmark is not exactly a proof. Russ's argument (by regexp analogy) goes something like we can make up grammars that simulate NFAs. Since there are regexps whose NFA will have O(exp(n)) possible successful runs on input of length n, (maybe something like a*a*), getting all parse trees means asking for trouble.

Where I am not so sure is, whether the authors are really unaware of this. It is possible to understand "parses efficiently on average" as "works efficiently for the average grammar programmers want to parse". Writing an ambiguous grammar by accident is one thing, writing something like a*a* is something else. Agreed, a statement like "works well for the average grammar" does not really have much scientific worth -- and Russ's criticism still stands -- but indeed it may work out in practice.

The math that derives working parsers from their specification is beautiful... the issue for practical purposes is that there are are other approaches to combinator parsing -- these are the ones that should be compared with derivative-based method, not yacc.

There is at least one paper (journal publication) out there that shows how memoization can make top-down functional parsers linear [3?], unfortunately I cannot access it so cannot comment on how applicable it is here. What's next, DMCA for papers? <b>J'accuse</b>.

Regardless what is up with yacc or memoization, among functional programming literature, there is a plethora of papers that use parser combinators to achieve polynomial parsing (the first reference that came to my mind is Swierstra and Duponcheel's paper [4]), but the wikipedia page on combinator parsing [5] has a link to more recent -- 2007 -- work from Frost and Hafiz that looks interesting.

There are no conclusions here. Combinator parsing is not new, but with the rising popularity of Scala, it is pretty much alive and kicking. After all, it has a packrat combinator parsing library included. For my next parser, I will certainly use that one and not Might and Darais approach. Still, I think the approach described in Might and Darais paper has educational value and I sincerely hope the authors will come up with a longer, more polished version.

[1] Matthew Might, David Darais. Yacc is dead.

[2] Russ Cox. Yacc is not dead.

[3?] Frost, Szydlowski. Memoizing purely functional top-down backtracking language processors. Science of Computer Programming
Volume 27, Issue 3, November 1996, Pages 263-288

[4] Swierstra, Duponcheel. Deterministic, error correcting parser combinators.  

[5] http://en.wikipedia.org/wiki/Parser_combinator

Romantic enthusiasm for verification

Recently, a workshop got me interested in contract programming again. In essence, programming by contract means we annotate our source code with pre- and postconditions.

@Requires(numChars % 2 == 0)
@Ensures(result.length() == numChars)
String foo(int numChars) {
...
}


This is like saying "the only proper way to call this method with a numChars parameter that is even. You will get a nice non-empty string in return." Sounds like a deal.

There is probably a lot to say about contracts and how they can help developers understand their code. There are frameworks that will take these annotations and turn these into run-time checks. My interest is more in verification though. Automated program verification is really hard to do, because several undecidability results apply -- but in the words of Prof Jürgen Giesl this also means that one can always improve the state of the art.

The previous time I got excited by contracts was when I had the pleasure to host Prof Peter Müller at Google where he give a talk and demo of SpecSharp. The article Specification and Verification: The Spec# Experience gives a glimpse of the programming system the authors had built. An amusing quote from there: "When programmers see our demos, they often develop a romantic enthusiasm that does not correspond to verification reality."

Let me state that dream here: a program is made of method calls. If the compiler, or IDE, "understands" the pre-conditions and post-conditions of method calls, it should be able to chain these "facts" together and achieve some form of "understanding" of the program. This can help developers add or change lines and get immediate feedback on whether the source code they write is correct.

Going back to the example above: imagine writing foo(3) in your IDE and having it underlined in squiggly red, with a mouse-over message stating "precondition numChars % 2 == 0 not satisfied".

Spec# translates the pre- and postconditions into Satisfiability Modulo Theories (SMT) problems which are then solved by the underlying engine called Boogie. Another SMT solver is Z3 which has a readable tutorial. Reading up on these, it is quite striking that Spec# is working on a real programming language, and that neat interfaces do exist between the layers of byte code, verification source and the nitty gritty predicate logic formulae.

And then, there still is the following flaw, quoted here:

At the moment you find an error, your brain may disappear because
of the Heisenberg uncertainty principle, and be replaced by a new
brain that thinks the proof is correct.
L.A. Levin

Just kidding. Robert Pollack's article is concerned with the problem that we can come up with a system that will verify our program, but we won't necessarily be able to trust it, because it is a program itself. Here is the bit that is relevant though: "My guess is that tech- 
nologies of automated proof search will be highly developed because of economic 
pressure for reliable hardware and software, and these, applied as tactics to proof 
checking, will make formal mathematics a practical reality in the foreseeable fu- 
ture."

It seems we still have a long way to go before developers see the light in IDEs having some form of automated program verification. I have a hope that if one goes back to natural deduction style proofs, logical frameworks or simple logic programming with SLD resolution, it may be possible to write reasonable (logical) annotations and have proper support. Let (expert) programmers write more. Only experimentation can show whether this is a good idea.

first baby steps with luatex

ok, I compiled the luatex beta and was puzzled on how to run this.

Then I found Luigi Scarso's answer:

what about
$texmfstart texexec --luatex luatest1.tex

What is texmfstart? No idea, but "wer sucht, der findet"

$ locate texmfstart
/usr/local/teTeX/share/texmf.local/scripts/context/ruby/texmfstart.rb
/usr/local/teTeX/share/texmf.tetex/scripts/context/ruby/texmfstart.rb

I do remember having played with context ones, but I do not remember whether I installed context there. Anyway, the .rb extension is for ruby, so

ruby /usr/local/teTeX/share/texmf.local/scripts/context/ruby/texmfstart.rb texexec --luatex sheet06.tex

did what I wanted... mostly. It produces a .pdf but it looks very basic, the page numbers are on the top of the page, and so on. Well a good starting point nevertheless.

lost in multi-lingualization

I figured out that my multi-lingual dictionary needs a multi-lingual website.

In web-design as elsewhere, i18n is quite a pain: one has to actually think what one wants before going off and doing something.

For my web dictionary and its associated websites, there is one obvious requirement: the text on every page should be viewable in various languages.

There are interesting links on the net on how to approach this systematically: I have found the following particularly useful:

• the comments in W3C's q&a blog article Content Negotiation: why it is useful, and how to make it work


• the EURESCOM report Multi-lingual web sites: Best practice guidelines and architectures

When looking for a standard encoding of languages as strings, the three letter languages codes (ISO639-2) are quite enough (ISO-639-1 are the two-letter ones). Of course, despite the thing being a standard, there is some fun to be had with e.g. deu == ger.

Apart from deciding, which languages to support, there is also a user interface question, and for my website, I consider this the most important. In times of Google, content can also be found if your website has a lousy user interface, but since I am looking for something that is fun to use interactively, usability takes priority.

That is why I need to ask myself: how would one select between languages? I think the best is to go with a hybrid approach:

• have URIs of the shape domain/language-code/path and rewrite them to domain/path.language-code.extension (the dispatching described in the comments to the W3C article).


• additionally have a footer with links (view page in language1, ..., languageN)

Pages should not be very long, so that the footer is visible. For added fun, I can later go into having facebook's wall-to-wall (two pages displayed side-by-side) layout to see the same page in two different languages, for translation and language-learning.

asp.net, and computerclubzwei

About to start a web app... coming from a Scala and Java background, but my web hoster offers me php and asp.net -- which poison is tastier? I was set to go for php, although I don't like the language much. So I thought I'd give this asp.net stuff a try.

For my first timid steps, I was happy to have read the German Wikipedia entry, and the
beginning wikibook "Webentwicklung mit ASP.NET". This had a link to visual studio web express, which is free, and it rocks as an IDE (I am a big fan of Microsoft IDEs, although I do everything to avoid owning a Windows OS). I get curious about MonoDevelop, all this Emacs juggling is getting boring sometimes.

About asp.net proper, the difference in complexity seems ridiculous compared to php... but this is more a psychological thing. While I quickly hacked a phpinfo.php to test that scripts were properly executed on the server, asp.net development first started by installing an IDE. There are quite some concepts to learn, and here I lost interest. Compared to the jsp world, the "usine à gaz" factor seems the same (I also lost interest in JSP 2, my last activity was a struts-1 webapp).

Out of curiosity, I will try to connect to the mysql database on asp.net, and continue some experiments... and if that works fine, I might stick with it and get used to IDE land again.

---

Growing up in Germany, I have at least one seen a show called "computer club" - although I was too young to appreciate it back then. Apparently, they have recently started podcasting on their new site cczwei. It's fun to listen to this professionally produced piece of audio-layman-tech-journalism - for one who enjoys people talking about technical things in a simple manner.

Code-follows-Type

Adriaan writes up something on Code-follows-Type programming. It's a neat technique that has a killer application: automatically generating pickling and unpickling code from your class definitions - without code generation, without reflection, without anything... wait, it says it only works for "representable" types.

Again, a web designer might be interested in
Google's Web Authoring Statistics for best practices.


There are far too many articles about the GWT, but here is Dion Hinchcliffe's analysis of GWT's service abstraction.

always good to remember some best practices in web development.


Ralf Laemmel and Erik Meijer take a head-on jump into xml object mismatch. More (or less) data binding.


I still haven't gotten to look microformats and wonder if I need to.


This Scala XML documentation needs some updating.

different takes on data binding

Some time ago, Kathleen Dollard showed how to generate classes from an XML Schema using XSLT. I dislike both schema and XSLT, but I would understand why someone would need to use both technologies and have respect for everybody that plunges in that hell. However all those technologies together might serve to describe the problem rather than the solution

Pull parsing examples, also a while ago, is often demonstrated as a fast way to do data binding. We can find Chris Fry's writeup on XML pull parsing. It seems
Pull parsing will be available in JDK6

This pull parsing stuff ultimately looks better than all other APIs, because all the other ones can be implemented on top of this one.

typed scripting? typescript

Types are good, but a language aiming to resemble JavaScript should leave type annotations optional wherever possible. Palsberg and Schwartzbach have something to say about type inference for object oriented programs.

What would types be good for? There's all those "message-not-understood" (and so on), but there is also fancier stuff like Session types for channels, or regexp-like types for semistructured data.

JavaScript is object based, but not class based. Abadi and Cardelli's "A Theory of Objects" is the standard reference on object calculi. "Type inference for JavaScript" introduces a calculus for modeling JavaScript.

Castagna provides an account on overloading in the publication that came out of his thesis, titled
"Object-Oriented Programming: A Unified Foundation". The thing with overloading is that it might give a more precise type to pattern matching statements, an idea that haunts me since ages.

JavaScript2

Brendan Eich's XTech 2006 keynote JavaScript 2 and the Future of the Web mentions some deltas to the language. This is warmly welcomed on LtU, who add a new JavaScript department.

One of the typing experts sitting int the committee, Cormac Flanagan, has worked on SAGE: Practical Hybrid type checking for Expressive Types and Specifications[pdf]

Not to be confounded with ECMAScript 4, the next version of JavaScript 1, designed by committee ECMA TC39TG1. They get proposals from Mozilla guys, and recently published their Wiki, which also is half-heartedly discussed on LtU.

why those books? discussions with friends

Edward Angel. OpenGL(tm): a Primer. ISBN 0-201-74186-5 A fascination with NeuroScience and displaying 3d graphics, ideally in a web browser. Unfortunately, we are missing a Canvas3D that supports this stuff. For the moment, there are Java bindings, and lwjgl looks like the way to go.

David Flanagan. JavaScript: The Definitive Guide, Fourth Edition. ISBN 0-596-00048-0 Actually I don't remember why that book is here, I get all the info I want from the net.

John C. Mitchell. Foundations for Programming Languages. ISBN 0-262-13321-0The style and notation of this book are of a beauty that makes me want to read it over and over again. Although I don't really have spare cycles to do more foundational stuff, the proofs are spelled out in a very clear, yet concise manner and it is inspiring.

Benjamin Pierce, ed. Advanced Topics in Types and Programming Languages. ISBN 0-262-16228-8 Here, I started with the chapter of typed assembly language, also with an implementation actually. Wouldn't it be useful to have a low-level VM for iron that interprets typed assembly code? and have an x86 backend at some point.

When chatting with my chap about my final project, I was surprised how rational I could tell him the objectives and problems that I am facing, things I have been trying to find out for a long time. And there I am just communicating it as if I had known it all the time. My reluctance to use *the language*, the advantages of using HTML for user interfaces, the insights into GWT and the architectural sketch and constraints of the system.

When receiving another chap's email I'm surprised at his argument for dynamic typing having become more differentiated, preferring LISP over Python. And it somehow makes sense, because uniform containers (like sequences and hashtables) seems to be what most of my obsession with iron is about as well. His CLOS speak is beyond me but I recall from the book that I forgot to mention that setting up some object system in those languages is not very difficult.

Abelson and Sussman. Structure and Interpretation of Computer Programs. ISBN 0-262-51087-1 Never made it to those later chapters, where writing a scheme compiler is given as an exercise. Opening this book again is due to my interest in doing dynamic typing via tags. However it just clashes with the idea of doing static checking for regular expression types. What gives? There should be some program analysis and type inference.

Benjamin Pierce. Types and Programming Languages. ISBN 0-262-16209-1 There's something about recursive types that makes me return to this book. It stems from my obsession of regular expression types for sequences. The iron language is supposed to have sequences as primitives, and do some type-checking for an xsd-extension based object-class system. Also, the type inference idea mentioned above can be nourished from this book.

forging templates Google style

Well, not surprisingly Google have their own way of templatin.

forging hypertext templates

The good old hypertext. What have they done to you, pal? Just look at you. JSPed all over. And all those taglibs hanging down your front.

<%@ taglib uri="/WEB-INF/tld/struts-bean.tld" prefix="bean" %>
<%@ taglib uri="/WEB-INF/tld/struts-html.tld" prefix="html" %>
<%@ taglib uri="/WEB-INF/tld/struts-logic.tld" prefix="logic" %>
<!--Logon_Block_Start-->
<html:form action="/loginlogout/login" focus="username">
  <TABLE WIDTH="<bean:message key="block.size.x"/>" 
   ...

No, no, some other I may have done this to you myself a long time ago, but not again.
Joel is right, so facade elements with attributes and ognl and tapestry style it shall be.

editable, viewable, maybe even validatable and bindable. No use to go over the top with WebObjects.

so you want to get web programming right, eh?

Programming should be done in a decent language. That language should be the same on client and server (and I won't tell you why).

All web scripting somehow started with JavaScript. You could embed it on your server side if you really want to.

One can target JavaScript (and also targets ActionScript) with the haXe language. It also has a server component, going through an Apache plugin.

The Links language promises to compile from a single source database updates and Javascript bits in your page.

OTOH, one can get a nice language, XML capabilities and leverage the whole Java shebang using the Scala language. However, the whole backend-multiplexing thing is missing as of yet.

so you want to start a blog, eh?

No meta-discussion, no navel-gazing, no propaganda. No technical details.

Once again scanning the web for frameworks, I got lost in Apache MyFaces and Tapestry and of course Google Web Toolkit the new kid on the block.

Over lunch, a discussion on JavaScript turns onto the XML lane and I realize that is another something that is missing in that language, just like actors.