Posted on Dec 10, 2008

One topic that always comes up when discussing (or arguing) computer
languages is *expressiveness*. In layman’s terms, a computer language is
generally used to express the logic required to direct a process in a
computer to manipulate some data. Most modern computing languages are
Turing-complete which means that for any problem *X*, any
Turing-complete language can solve for *X* and eventually arrive at the
same answer as any other. What differentiates all of these languages is
their expressiveness; that is their ability to describe the solution to
any problem in a way that is obvious to the reader. Each language has
varying degrees of expressiveness which is a strong point of contention
amongst programmers.

First consider the following from Higher Order Perl:

Any whole number has the form 2*k* +

b, wherekis some smaller whole number andbis either 0 or 1.bis the final bit of the binary expansion. It’s easy to see whether this bit is 0 or 1; just look to see whether the input number is even or odd. The rest of the number is 2*k*, whose binary expansion is the same as that ofk, but shifted left one place. For example, consider the number 37 = 2 * 18 + 1; herekis 18 andbis 1, so the binary expansion of 37 (100101) is the same as that of 18 (10010), but with an extra 1 on the end.

Mark Jason Dominus then goes on to describe the algorithm for finding the binary expansion of a whole number and his solution in Perl. The solution is actually rather simple and is essentially as follows:

```
#!/usr/bin/perl -w
use strict;
sub binary {
# Return the binary expansion of a real number as a string
my ($n) = @_;
return $n if $n == 0 || $n == 1;
# where any real number is 2k + b
my $k = int($n / 2);
my $b = $n % 2;
my $E = binary($k);
return $E . $b;
}
print binary(37) . "n";
```

As the idea behind this post struck me, I decided to write an implementation of Mark’s algorithm in Lisp.

```
(defun binary (n)
"Return the binary expansion of a real number as a string"
(if (or (equal n 1) (equal n 0))
(return-from binary (format t "~d" n)))
; where any real number is 2k + b
(let* ((k (truncate n 2))
(b (mod n 2))
(e (binary k)))
(loop for x in (concatenate 'list (list e b))
if (numberp x)
do (format t "~d" x))))
```

Both of these bits of code produce the same answer (albeit pedantically different ones which will be addressed) and express the same algorithm. Yet syntax aside, they are both strikingly different. This is each language’s respective expressiveness in play. What can we infer about each language from this example?

In the Perl implementation the first thing that strikes me is its
implicitness. The sparse language is almost intuitive to read even if we
don’t quite understand the meaning of the syntax. Here we are breaking
down the problem into naming and returning values. However, implicitness
hides complexity and in Perl’s case, the complexity isn’t obvious. The
*solution* is expressed clearly but the underlying *implementation* is
hidden by the language. This means programmer requires an understanding
of Perl’s internals in order to comprehend the implementation details.

Conversely, the Lisp example is less implicit and more rigorous. The grammar might feel slightly foreign to native English speakers due to Lisps “prefix notation” (which is a fancy way of saying that the verb comes before the nouns they operate on). However, Lisp doesn’t imply any functionality beyond what is written. Therefore, once the programmer learns the grammar and syntax of Lisp they won’t need prior knowledge of Lisp internals in order to comprehend the implementation. In other words, there is no hidden “magic” going on behind the curtain.

Despite arriving at the same answer, there’s also a structural
difference between these two examples. In the Perl example, the result
of the function is *returned* to the caller who prints it to the screen
whereas the Lisp example prints the result from inside the function and
returns nothing to the caller. The Lisp example can be modified to
return values instead of simply printing them, but the point I am trying
to drive home is that Lisp makes this explicit and hides almost nothing
of the implementation between the programmer and what is written.
Whereas the Perl example requires some knowledge of Perl implementation
details in order to fully understand what the binary function is
actually doing.

For example, in the Perl example the caller is the print function and in this context if the binary function was passed the integer value, “1,” it would know to interpolate it to a string and print it to standard output — yet none of those details are exposed to the reader of the code. This is useful for those who know how Perl works and can afford to imply such mundane details if it suits them. Conversely, Lisp is far more explicit and doesn’t hide any of those implementation details.

This isn’t a comparison of which language is superior. I’ve written far
more code in Perl than I have in Lisp and I like it very much. The point
of this post is to clue those new to programming what exactly we mean by
the *expressiveness* of a language and why it matters. Hopefully I have
succeeded, but if there are any questions or corrections I’ll definitely
respond to them and improve this post accordingly.