1/19/2010

Constructive art on software languages

If you (feel like you) need to explain a piece of art, then something sucks. But I am not saying that Haskell's Tower of Babel is true art. Perhaps it could be called constructive art (or nerdy art). Anyway, I am going to explain you how I constructed this picture. See here for the original twitpic with the tower, but it's included right below for your convenience.


















This is how you can reproduce the tower:
  • Use something like Mac OS's Keynote to actually assemble the picture.
  • Go through a nifty Haskell project and gather all Haskell 98 extensions.
  • Use one line per pragma and format everything with a proportional font as shown.
  • Sort the extensions (the lines) by the visual length. Results depend on the font chosen.
  • Starting at the bottom, adjust font size per line to get a smooth slide from top to bottom.
In my instance, there was some fuzzy effect due to the used proportional font and the tension between the upper case LANGUAGE and the camel-cased name of the extension in each line. Say, while I was generally trying to decrease font size as I was going from bottom to top, I had to actually increase it every now and then--if I wanted that smooth slide from top to bottom.

Background for non-Haskell nerds: In contemporary Haskell, programmers tend to express their dependence on non-standardized features by using detailed pragmas in their modules. For instance, if someone places the pragma for "FunctionalDependencies" in a module, then this means that class declarations are allowed to restrict multi-parameter type classes to model functions on types as opposed to general relations.

At some point, it just occurred to me how organized we Haskell programmers are and how much expressivity we have at avail. From a more historical point of view, we may just run into the kind of problem that is symbolized by the Tower of Babel, but honestly I don't feel like I am suffering from too much expressivity and too sexy types.

As a data point, the project from which I extracted the above language pragmas is a tutorial on type-level programming (joint work with Oleg Kiselyov). The first two lectures of this tutorial have been recorded and posted. I have presented that material for folks with pretty much no Haskell background. Several of the lectures (not those currently available online) require advanced background in typing and programming languages (also measured by the number of language pragmas shown), but the plan is ultimately to get this tutorial to the point that everyone with modest interest in language design and type systems can fully appreciate all that expressivity and sexy typing.

PF

1/03/2010

Palindrom dates

@lizettegagne re-tweeted as follows earlier today (or yesterday +/-): "RT @mashable: Happy Palindrome Day everyone - 01022010! Last one was 10022001, prior to that 08311380!! Wow! They don't come around often." I hacked up the following Prolog code to get some certainty. Simple modification reveals that European ordering or YYYYMMDD ordering would lead to entirely different results. Try it out!

PF


?- main.
08311380
10022001
01022010
true.

% This is what a palindrom is ...
palindrom(S) :- reverse(S,S).

% Generate all palindrom dates; ignoring leap years.
special(MDYS) :-
year(_,YS),
month(M,MS),
day(M,_,DS),
append(MS,DS,MDS),
append(MDS,YS,MDYS),
palindrom(MDYS).

% Here is an over-approximation of dates.
year(X,S) :- ranges(4,1380,2010,X,S).
month(X,S) :- ranges(2,1,12,X,S).
day(1,X,S) :- ranges(2,1,31,X,S).
day(2,X,S) :- ranges(2,1,29,X,S).
day(3,X,S) :- ranges(2,1,31,X,S).
day(4,X,S) :- ranges(2,1,30,X,S).
day(5,X,S) :- ranges(2,1,31,X,S).
day(6,X,S) :- ranges(2,1,30,X,S).
day(7,X,S) :- ranges(2,1,31,X,S).
day(8,X,S) :- ranges(2,1,31,X,S).
day(9,X,S) :- ranges(2,1,30,X,S).
day(10,X,S) :- ranges(2,1,31,X,S).
day(11,X,S) :- ranges(2,1,30,X,S).
day(12,X,S) :- ranges(2,1,31,X,S).

% Generate all strings of values in that range with that length
ranges(L,Min,Max,X,S2) :-
( Min =< Max, X = Min, name(Min,S1), pad(L,S1,S2)
; Min < Max, Min1 is Min + 1, ranges(L,Min1,Max,X,S2)
).

% Extend a string to the length given
pad(L,S1,S2) :-
length(S1,L1),
( L1 > L, abort
; L1 = L, S2 = S1
; L1 < L, pad(L,[0'0|S1],S2)
).

% Print all solutions
print(S) :- atom_codes(A,S), write(A), nl.
main :- findall(S,special(S),Ss), maplist(print,Ss).