Algol68 - gregorymorrison/euler1 GitHub Wiki

Algol 68, introduced in, um, 1968, is one of the formative languages that helped to define modern Computer Science. Along with Fortran, COBOL, Lisp, etc., the Algol family was instrumental in shaping how we interact with our machines. Algol 68 had lots of modern features - user-defined structures, operator overloading, pointers, threading, garbage collection, It's also missing many features we expect today, such as OOP, exception handling, block comments.

So what does it look like? Here is a simple iterative example of Euler1:

# Euler1 in Algol 68 #

PROC euler1 = (INT n) INT: (
    INT retval := 0;

    FOR i FROM 1 TO n-1 DO
        IF i %* 3 = 0 OR i %* 5 = 0 THEN
            retval +:= i
        FI
    OD;
    retval
);
print (euler1(1000))

Next is a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler is deterministic – it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation – there are instead only functions which return values. The other main point is that this recursion uses tail call optimization – it’s written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.

# Euler1 in Algol 68 #

OP TOSTRING = ( INT n )STRING: whole( n, 0 );

PROC euler = (INT n, acc) INT: (
    IF n = 1 THEN
        acc
    ELIF n %* 3 = 0 OR n %* 5 = 0 THEN
        euler(n-1, acc+n)
    ELSE
        euler(n-1, acc)
    FI
);

PROC euler1 = (INT n) INT: euler(n, 0);

print (("euler1 = ", TOSTRING euler1(999), newline))

Here’s another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler() returns euler() calculated on the half of the list before the pivot element, euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together:

# Euler1 in Algol 68 #

OP TOSTRING = ( INT n )STRING: whole( n, 0 );

PROC range = (INT size) [] INT: (
    [1:size] INT ints;
    FOR i FROM 1 TO size DO
        ints[i] := i
    OD;
    ints
);

PROC size = ([] INT ints) INT: (
    INT retval := 0;
    FOR i FROM LWB ints TO UPB ints DO
        retval +:= 1
    OD;
    retval
);

PROC euler = ([] INT ints) INT: (
    INT retval := 0;

    INT len := size(ints);
    IF len > 0 THEN
        INT pivot := ENTIER( len/2 + 1 );

        INT pivotval := 0;
        IF ints[pivot] %* 3 = 0 OR ints[pivot] %* 5 = 0 THEN
            pivotval := ints[pivot]
        FI;

        retval := euler(ints[1:pivot-1]) + pivotval + euler(ints[pivot+1:len])
    FI;
    retval
);

PROC euler1 = (INT n) INT: euler(range(n));

print (("euler1 = ", TOSTRING euler1(999), newline))

It didn't take me that long to translate this algorithm - maybe a few hours. The runtime errors were not too bad for debugging. The program is disappointingly long, though. You can really see how control structure syntax has improved over the decades. Amusingly, Algol 68 has the only non-English function name I've ever encountered in a programming language. ENTIER (French for whole, highlighted above in blue), is usually called FLOOR in other languages.

Since Algol 68 has pointers, we can relatively easily implement the Functional map, filter, and reduce. Let's define these generic functions, using the keyword PROC to define a function parameter. Then, let's define some functions for map, filter, and reduce to apply. Finally, let's define some functions to apply everything.

# Euler1 in Algol 68 #

OP TOSTRING = ( INT n )STRING: whole( n, 0 );

PROC range = (INT size) [] INT: (
    [1:size] INT ints;
    FOR i FROM 1 TO size DO ints[i] := i OD;
    ints
);

PROC size = ([] INT ints) INT: (
    INT retval := 0;
    FOR i FROM LWB ints TO UPB ints DO
        retval +:= 1
    OD;
    retval
);

PROC map = ([] INT ints, PROC (INT) INT f) [] INT: (
    [1:size(ints)] INT retval;
    FOR i FROM LWB ints TO UPB ints DO
        retval[i] := f(ints[i])
    OD;
    retval
);

PROC filter = ([] INT ints, PROC (INT) BOOL f) [] INT: (
    INT size := 0;
    FOR i FROM LWB ints TO UPB ints DO
        IF f(ints[i]) = TRUE THEN size +:= 1 FI
    OD;

    [1:size] INT retval;
    FOR i FROM LWB ints TO UPB ints DO
        IF f(ints[i]) = TRUE THEN 
            retval[size] := ints[i];
            size -:= 1
        FI
    OD;
    retval
);

PROC reduce = ([] INT ints, PROC (INT, INT) INT f) INT: (
    INT retval := 0;
    FOR i FROM LWB ints TO UPB ints DO
        retval := f(retval, ints[i])
    OD;
    retval
);

PROC f_map    = (INT n) INT: n;
PROC f_filter = (INT n) BOOL: IF n %* 3 = 0 OR n %* 5 = 0 THEN TRUE ELSE FALSE FI;
PROC f_reduce = (INT x, y) INT: x+y;

PROC mymap    = ([] INT ints) [] INT: map(ints, f_map);
PROC myfilter = ([] INT ints) [] INT: filter(ints, f_filter);
PROC myreduce = ([] INT ints) INT: reduce(ints, f_reduce);

PROC euler1 = (INT size) INT: myreduce( myfilter( mymap( range(size))));

print (("euler1 = ", TOSTRING euler1(999), newline))

This took me a few hours to write. I had some frustration with this - my compiler was very fussy about case, e.g. Also, I could not get my compiler to allow me to pass the integer array by reference, even though it should be possible. The documentation is not too bad for such an old language; I didn't have too much trouble finding what I needed with Google.

Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation:

# Euler1 in Algol 68 #

OP TOSTRING = ( INT n )STRING: whole( n, 0 );

PROC mysum = (INT n, size) REAL: (
    (ENTIER(size/n)**2 + ENTIER(size/n)) * n / 2
);

PROC euler1 = (INT size) INT: (
    ROUND(mysum(3,size) + mysum(5,size) - mysum(15,size))
);

print (("euler1 = ", TOSTRING euler1(999), newline))

Algol 68 is available on Ubuntu as algol68g. It's imperative, so there is no compilation. Simply execute as follows:

$ a68g euler1.a68
euler1 = 233168
$