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, where k is some smaller whole number and b is either 0 or 1. b is 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 of k, but shifted left one place. For example, consider the number 37 = 2 * 18 + 1; here k is 18 and b is 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.