Ask HN: How might the most compact programming language in the world look like? | Hacker News Reader

Ask HN: How might the most compact programming language in the world look like?

6 pointsnadam5 comments

I am searching for the limits of programming language compactness. (just for fun, although this can be also interesting in genetic programming)

The definition is a bit subjective, but not very much: A programming language is compact, if the program size is small for the typical programs we want to write. (The subjective part is what we call a typical program.)

Currently I think that the programming language Joy is the best candidate to be the base for creating the most compact programming language in the world.

http://en.wikipedia.org/wiki/Joy_(programming_language)

I have quickly defined a variant of Joy, and I have defined an efficient coding scheme for it. (This is still on paper, I did not write it down precisely enough to publish). It turned out that the really necessary tokens of joy can be typically encoded in 3-4 or in the worst case in 5 bits. This means that the quicksort algorithm mentioned in the wikipedia articel is approximatley 9 bytes long.

Do you have an idea for an even more compact programming language? Do you think that a cleverly encoded Joy-variant is near some theoretical limit of compactness?

Guy Steele knows a bit about language design (having co-invented Scheme and Fortress, worked on early implementations of TeX and TECO/Emacs, and helped write the specifications for Java, Common Lisp, ECMAScript, Fortran, and C). In Coders at Work he says,

"There's this Huffman encoding problem. If you make something concise, something is going to have to be more verbose as a consequence. So in designing a language, one of the things you think about is, 'What are the things I want to make very easy to say and very easy to get right?' But with the understanding that, having used up characters or symbols for that purpose, you're going to have to make something else a little bit harder to say."

So it definitely depends on your domain. If you do some of the harder Project Euler problems and then look in the forums, you can see the same problem solved by a hundred different programmers with different approaches. The shortest solutions there are always in APL-family languages like J and K. But it's partly because those languages are so well-suited to the typical problems in Project Euler.

If you want to implement a concurrent server for binary network protocol like memcache, then you'll probably find Erlang a more concise language instead, because its syntax, its libraries, and the primitives of the Erlang VM are all better adapted to that domain.

Yes you are right, it probably depends on the domain. But still, I have a feeling that there are some languages which are more concise than others generally because of reasons which are very generic: For example imperative languages with local variables contain a lot of unnecessary information, because we always have to reference the local variables we use, while in stack based languages the arguments don't have to be referenced, because they are implicit. In fact, in an extremely concise language there should be only a very few ways to express a program at a certain size. In not so concise languages you can write the same program in lot of ways ('permutations') (having the same size).

Kinda related: there are various genomes that encode overlapping genes. This makes them very compact in that they take less physical space to achieve the same end result,

In this analogy, the language is the genome (DNA or RNA) and the program is the set of proteins that make up the virus or whatnot.

As far as I know, there aren't any computer programming languages that do this. Not that I want them to...

A reference: http://www.bookrags.com/research/overlapping-genes-gen-03/

The language called MUMPS only uses single letter key words as I recall - but that way lies insanity.

APL

Reply on news.ycombinator.com