Beautiful Programs

the REPL

The REPL is a prompt that interprets results on the fly and returns them to the user. Almost all interpreted languages have one, and they call them a “REPL”, which is short for Read Evaluate Print Loop.

In lisp, it’s four functions:

(loop (print (eval (read))))

1. You read input from the user
2. You evaluate it
3. You print the result
4. You repeat infinitely

In lisp it’s easy to implement like this because it’s easy to evaluate any lisp program you write (lisp programs are interpreted the same way they’re typed, so evaluating is not that hard).

Simply putting together these four functions in this way allows for a new way of experimenting with programming – you can write code and get immediate feedback, instead of having to write code, compile it, and run it. Most people start off with learning interpreted languages, and these four functions are responsible for getting many people into programming, myself included.

The Universal Server

Joe Armstrong wrote about his favorite program, The Universal Server.

It’s simple:

universal_server() ->
    receive
       {become, F} ->
           F()
    end.

5 lines of code define a process that can take any arbitrary work and becomes that function.

He defines a factorial function, which calculates the factorial of an integer it receives:

factorial_server() ->
    receive
       {From, N} ->
           From ! factorial(N),
           factorial_server()
    end.


factorial(0) -> 1;
factorial(N) -> N * factorial(N-1).

And then you can write a function that spawns it and run it.

test() ->
    Pid = spawn(fun universal_server/0),
    Pid ! {become, fun factorial_server/0},
    Pid ! {self(), 50},
    receive
        X -> X
    end.

In 5 lines, this defines a universal protocol for servers – they receive input and return a message. Any server that follows that rule can be spawned by this universal server. Pretty cool. If you have a server running a version right now and you want it to run another version? Go write the code for a new server, and send it over.

A Metacircular evaluator

Another lisp program? A Metacircular evaluator is an evaluator that can evaluate programs written in itself.

This is from Structure and Interpretation of Computer Programs:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp)
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type -- EVAL" exp))))

There’s more to the program, but this is the core of it.

All lisp programs can be defined by two things: their body, the actual program and an environment, which is the bindings required to make the language work. For example, if you have a program:

(print x)

You need some definition for two things, x and print. Normally you’d define x in the course of your program, but you probably wouldn’t define the print function of your language. Thus, you can divide this program into two pieces, its environment (what it needs to run) and the textual definition of the program itself.

{ print: "some implementation here" } ; The "environment"
(print x) ; The program

That’s all you need to evaluate your language, a set of variables, and the program itself. If you want to write a modern programming language, you need to support scopes:

let mut x = 10;
{
    x = 15;
}

All you need to support that is nested hashmaps:

{ x: 10, { x: 15 }}

If you’re in a nested scope, choose that value instead of the higher level value. A language is itself and its environment.

A Simple Regular Expression Engine

This comes from The Practice of Programming by Rob Pike and Brian Kernighan, a simple regular expression matcher.

/* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
{
    if (regexp[0] == '^')
        return matchhere(regexp+1, text);
    do {    /* must look even if string is empty */
        if (matchhere(regexp, text))
            return 1;
    } while (*text++ != '\0');
    return 0;
}

/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text)
{
    if (regexp[0] == '\0')
        return 1;
    if (regexp[1] == '*')
        return matchstar(regexp[0], regexp+2, text);
    if (regexp[0] == '$' && regexp[1] == '\0')
        return *text == '\0';
    if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
        return matchhere(regexp+1, text+1);
    return 0;
}

/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
{
    do {    /* a * matches zero or more instances */
        if (matchhere(regexp, text))
            return 1;
    } while (*text != '\0' && (*text++ == c || c == '.'));
    return 0;
}

The driver function, match, checks if a string matches a given regular expression. If the regex starts with ^, it must only match from the beginning, so it checks that with matchhere. If not, the regex could match from any position in the string, so it checks for the regexes’ match from every position in the string.

The helper function, matchhere, checks if the regex matches starting from the first position in the string. It handles * for repetition, and $ for ending.

matchstar finds zero or more matches of a regex in the string. This is done with a do while loop because there are 0 or more occurrences possible.

All in all, three functions that clearly explain what they’re doing and compose beautifully to tackle the problem at hand. Regexes are extremely useful in programming, and to see most of them boiled down to just these three functions makes this program beautiful, in my eyes.

The Rest?

There are many beautiful programs – I just chose a few from my memory but I’m sure you have plenty that spring to mind – if so, write about them!