Archive for May, 2007

New Paradigm for Comparing the Expressive Power of Languages

If you're an ICFP referee, you definitely want to read further.

New Paradigm for Comparing the Expressive Power of Languages

Abstract

The community folklore abounds with informal claims concerning the expressive power of certain programming languages. Given that just about all languages under discussion are Turing Complete, Felleisen introduce the concept of »macro expressiveness« to provide a framework for more principled comparisons between languages [1].

While Felleisen's work was groundbreaking, we have built upon Diggin's recent work on the Cat language [2] to develop a comparative framework that not only correctly captures many informal notions of expressiveness, but is durned cute at the same time. Language features that can be encoded using our methodology are said to be »cat macro expressible« [3]. We illustrate the technique by showing that most features of C language [4] are cat macro expressible as »im in ur stackz overflowing ur bufferz« [5]. Finally, we provide evidence that the massive parallelism inherent in the Internet can be harnessed for the generation of programming idioms that are cat macro expressible [6].

[1] http://www.ccs.neu.edu/scheme/pubs/scp91-felleisen.ps.gz
[2] http://www.cat-language.com/
[3] http://en.wikipedia.org/wiki/Cat_macros
[4] Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language.
[5]

im in ur stackz overflowing ur bufferz

[6] http://www.xkcd.com/c262.html

Comments (1)

The Liberation typefaces

Red Hat recently announced the availability of a family of fonts they had commissioned from Ascender Corp. The goal behind the fonts was to be metric compatible with the nearly ubiquitous Microsoft fonts Arial, Courier New, and Times New Roman. I put together a comparison of the new »Liberation« family of typefaces along with their Microsoft metric compatible counterparts. To provide a little more additional information, I've also included the Bitstream Vera family. Bitstream Vera seems to be made available under a fairly liberal license. The Liberation fonts are made available under the GPL with the standard font embedding exception.

Liberation fonts comparison

Overall, I can't say the Liberation fonts feel particularly notable, but given that their main purposes is to provide a »free«,as in Freedom, replacement for deeply entrenched Microsoft fonts, I don't imagine originality was really considered as a goal. The fonts are available for download from here.

Comments (4)

Next stop: Switzerland

The biggest news for today, at least relative to the center of my universe, is that I have a job. This fall I will be joining the Programming Methods Laboratory at Ecoles Polytechniques Fédérales de Lausanne (EPFL) as a postdoc working on the Scala language. It is an exciting opportunity to apply my expertise to language that is gaining popularity outside academia.

There is, of course, the small matter of finishing my dissertation. As if I didn't have enough pressure before, I've put together a pretty strict time-line that should be feasible.

Comments (3)

Greek typography competition

Over on Typblography a week or so ago, I learned about contest in Greek type design being held as part of a conference on typography being held in Greece next month. Just come up with an innovative design for the phrase

ένα αναμφισβήτητα ξεχωριστό γεγονός.

Dimitris tells me that this translates literally

an undoubtedly special event

or more freely as

something that happened that is recognized to be quite important

Just about any medium you would like is acceptable. The deadline for submission is May 31st, and there are cash prizes that could help with travel expenses.

I was sorely tempted to try putting together an entry, but I just have too many other responsibilities at the moment.

Comments

Theme feedback

I recently heard from a few people that they disliked the current I am ∃xistential Type theme. My overall web presence is due for an overhaul in the near future, so I figured I would solicit feedback on what people dislike about the current design.

Comments (7)

Make it stop

This is just one line of debugging output (the text is wrapped) I'm having to scrutinize as part of debugging InforML.


ConPat lookup (norm): 〈l4 : Lab l5 : Lab l6 : Lab l7 : Lab | α : ⋆ @ (0) [[↑3]] ([] [Sort ()]) β : ⋆ @ (0) [[↑3]] ([] [Sort ()])〉 Spine(0) ([Pi l1 : Lab-(+)→ ⋆ @ (0) -(+)→ Lab -(+)→ ⋆ @ ({zB})[↑17] ([] [Sort ()]) ([] [Sort ()])]) [[↑14]] ([Pi l1 : Lab-(+)→ ⋆ @ (0) -(+)→ Lab -(+)→ ⋆ @ ({zB})[↑15 o ↑4 o ((0) [[↑6]]).((0) [[↑7]]).((0) [[↑8]]).↑15] ([] [Sort ()]) ([] [Sort ()])]) @ (0) [[↑3]] (0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑1]] -(({0B})[↑28]|({1B})[↑28]|({4B})[↑29])→ (0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑1]] ([] [Lab -(+)→ ⋆ @ ({3B})[↑29] ([Sort ()])]) @ Need syntax for pos/neg sets [[((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]):⋆ @ (0) [[↑3]] ([] [Sort ()])).((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑1]] ([⋆ @ (0) [[↑4]] ([] [Sort ()])]):⋆ @ (0) [[↑4]] ([] [Sort ()])).((0) [[↑2]]).((0) [[↑3]]).((0) [[↑4]]).((0) [[↑5]]).↑13]] ([Lab -(+)→ ⋆ @ ({zB})[↑29] ([] [Sort ()])]) @ (0) [[↑2]] -(({yB})[↑28]|Need syntax for pos/neg sets [[((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]):⋆ @ (0) [[↑3]] ([] [Sort ()])).((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑1]] ([⋆ @ (0) [[↑4]] ([] [Sort ()])]):⋆ @ (0) [[↑4]] ([] [Sort ()])).((0) [[↑2]]).((0) [[↑3]]).((0) [[↑4]]).((0) [[↑5]]).↑13]]|({7B})[↑29])→ (0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑2]] -(({8B})[↑29]|({9B})[↑29]|({AC})[↑30])→ Spine(0) ([Pi l1 : Lab-(+)→ ⋆ @ (0) -(+)→ Lab -(+)→ ⋆ @ ({BC})[↑17] ([] [Sort ()]) ([] [Sort ()])]) [[↑16]] ([Pi l1 : Lab-(+)→ ⋆ @ (0) -(+)→ Lab -(+)→ ⋆ @ ({BC})[↑15 o ↑10 o ((0) [[↑2]]).((0) [[↑1]] [[↑1]] [[↑1]]:(0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑5]] ([⋆ @ (0) [[↑8]] ([] [Sort ()])])).((0) [[↑1]] [[↑1]] [[↑1]] [[↑1]]:Spine(0) ([Pi l1 : Lab-(+)→ ⋆ @ (0) -(+)→ Lab -(+)→ ⋆ @ ({zB})[↑17] ([] [Sort ()]) ([] [Sort ()])]) [[↑12]] ([Pi l1 : Lab-(+)→ ⋆ @ (0) -(+)→ Lab -(+)→ ⋆ @ ({zB})[↑15 o ↑7 o ↑1 o ↑4 o ((0)).((0) ([⋆ @ (0) ([] [Sort ()])]) [[↑1]] ([⋆ @ (0) [[↑1]] ([] [Sort ()])]):⋆ @ (0) [[↑1]] ([] [Sort ()])).((0) [[↑2]]).↑4 o ((0)).((0) ([⋆ @ (0) ([] [Sort ()])]) [[↑1]] ([⋆ @ (0) [[↑1]] ([] [Sort ()])]):⋆ @ (0) [[↑1]] ([] [Sort ()])).((0) [[↑2]]).↑4] ([] [Sort ()]) ([] [Sort ()])]) @ (0) [[↑7]] (0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑5]] -(({0B})[↑26]|({1B})[↑26]|({4B})[↑27])→ (0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑5]] ([] [Lab -(+)→ ⋆ @ ({3B})[↑27] ([Sort ()])]) @ Need syntax for pos/neg sets [[((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑4]] ([⋆ @ (0) [[↑7]] ([] [Sort ()])]):⋆ @ (0) [[↑7]] ([] [Sort ()])).((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑5]] ([⋆ @ (0) [[↑8]] ([] [Sort ()])]):⋆ @ (0) [[↑8]] ([] [Sort ()])).((0) [[↑6]]).((0) [[↑7]]).((0) [[↑8]]).((0) [[↑8 o ↑1]]).↑11]] ([Lab -(+)→ ⋆ @ ({zB})[↑27] ([] [Sort ()])]) @ (0) [[↑6]] ([] [⋆ @ ({zB})[↑26] ([] [Sort ()])])).((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑5]] ([⋆ @ (0) [[↑8]] ([] [Sort ()])]):⋆ @ (0) [[↑8]] ([] [Sort ()])).((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑6]] ([⋆ @ (0) [[↑9]] ([] [Sort ()])]):⋆ @ (0) [[↑9]] ([] [Sort ()])).((0) [[↑7]]).((0) [[↑8]]).((0) [[↑9]]).((0) [[↑10]]).↑17] ([] [Sort ()]) ([] [Sort ()])]) @ (0) [[↑6]] (0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑2]] ([Lab -(+)→ ⋆ @ ({BC})[↑15 o ↑2 o ((0) [[↑8]]).↑15] ([] [Sort ()])]) @ (0) [[↑4]] ([Lab -(+)→ ⋆ @ ({/B})[↑30] ([Sort ()])]) @ ({DC})[↑29] ([] [] [Lab -(+)→ ⋆ @ ({6B})[↑29] ([Sort ()])]) @ Need syntax for pos/neg sets [[((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]):⋆ @ (0) [[↑3]] ([] [Sort ()])).((0) ([⋆ @ (0) [[↑3]] ([] [Sort ()])]) [[↑1]] ([⋆ @ (0) [[↑4]] ([] [Sort ()])]):⋆ @ (0) [[↑4]] ([] [Sort ()])).((0) [[↑2]]).((0) [[↑3]]).((0) [[↑4]]).((0) [[↑5]]).↑13]] ([] [⋆ @ Need syntax for pos/neg sets [[↑7]] ([Sort ()])])

Comments