Media Net Link

Fun With Programming Languages

Most of the time programmers work laboriously at analyzing specifications and data flows and user requirements, and then designing and coding the best possible solution for the client. At other times, they code for the sheer enjoyment of solving a puzzle, comparing the subtleties of language differences, or the elegance in a solution.

One of the many examples of this found on the internet typical of the type of puzzles programmers create was a contest to see how few characters it would take for a perl programmer to list out the entire verse to Ten Little Indians. As a scripting language for the web, Perl is sometimes referred to as "Practical Eclectic Rubbish Lister." Those that were extremely adept at the language were able to get the program down below 100 characters. An example below by Gran Robinson contains 79 characters:

for(;$i++<10;){print"$i little",$i%3?"":" indians",$i<10?"\n":" indian boys\n"}

and outputs:

1 little

2 little

3 little indians

4 little

5 little

6 little indians

7 little

8 little

9 little indians

10 little indian boys

In the examples below, I look at a few other puzzles, and highlight some of the cool and esoteric ways to implement a solution. After posing the problem, I note a few of the more interesting solutions for each case including some insight into the language itself. The source for the examples below is this site. A laundry list of problems like this is but a Google away.

The Infinite "Hello World" program
When confronted with a new programming language, programmers often are asked, or try to implement as their first program, a simple task of printing out "Hello World". This example goes one step further, printing out "hello" forever. The four shortest versions of this oversimplified problem, unsurprisingly, went to environments not generally thought of as real programming languages: the Bourne shell, a toy language called "false", the "dc" RPN command line calculator, and the "vi" editor. It just goes to show that no single tool is always the best for every job.

The winner, in /bin/sh at 9 characters: yes hello

Primes up to N
Moving on to something approaching a real programming problem, the requirement for this challenge is to create the smallest complete subroutine, function, or method that will return a list of prime numbers less than or equal to the number passed in the method. The definition is a bit vague, due to the fact that, depending on the language, there are many ways to define a "function"

The winner of this test is the little-known-outside-of-CS-circles language "Haskell", which performs the task in a scant 40 characters. The 3 runner-ups are all languages which have inherited much of their list-processing design from Lisp, but manage to come in well ahead, from a code-brevity perspective: perl, ruby, and python respectively.

The winner, in Haskell, at 40 characters: f n=[x|x<-[2..n],all((0<).mod x)(f$x-1)]

Power Set
A truly fascinating back-and-forth occurred when trying to implement a short solution to the "power set problem", defined as: give the smallest possible complete subroutine/function/method definition in a language of your choice which, when called with a list, array, whatever, returns the power set of that list. It may be in any order, but must not contain duplicates.

For those not up on their set mathematics, the "power set" is the set of all possible subsets of a given set. For example, given the set [1, 2, 3], the power set is: [[1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]].

The back-and-forth involved trading off length between the lisp, ocaml, and perl versions of the function. OCaml is a modern, object-oriented version of the ML language, which is strongly typed and designed for highly efficient performance. Perl and Lisp are both dynamically typed, meaning a given data structure or variable can contain, at runtime, any type of variable. In this particular exercise, that difference doesn't come into play, so the Ocaml comes out quite short (for a strongly typed language). In fact, in this example the same techniques and algorithms used in, say, the lisp version worked just as well in the perl version, and as each code author found an improvement in their "pet" version, the same technique applied to their competition made it even shorter as well. In the end, the perl (45 chars) and the lisp (73 chars) are basically identical, just with different syntax. Observe below. The perl is on the top, the lisp on the bottom, and they are lined up for comparison:

sub p { @_?map {$_,[ $_[0] ,@$_] } p(@_[1..$#_]) :[ ] }

(defun p(l)(if l(mapcan #'(lambda(x)`(,x (,(car l).,x )))(p(cdr l) ))`(,l)))

These are both twisty mazes of list operations, but the perl uses concise array syntax and an extremely brief { } lambda syntax. The basic gist of how they work in pseudocode would look something like this:

function p takes a list l as an argument:
if the list is empty/null, return a list containing an empty list/null
foreach element resulting from recursively calling p on everything but
the first element of l:
make a list composed of that element and a list composed of the first
element of l and the elements contained in this foreach element
return the list built out of all the elements in that foreach

The winning perl, all crunched together, at 45 characters: sub p{@_?map{$_,[$_[0],@$_]}p(@_[1..$#_]):[]}

Some people actually do find this sort of thing fun. But more than just silly character-crunching games, this sort of hammering away at all the fluff really starts to expose oft-unseen language features, nuances, and bugs. While much of the syntax and many of the tricks used in these exercises would never be... should never be used in production code, knowing how they work is an essential tool for any programmer that truly wants to have a mastery of a given language.

David Bushong - Media Net Link