Early functional Fortran
Fortran is considered one of the first programming languages still in use today. Fortran is short for Formula Translator and the initial version was very simple. It’s almost like an assembler but with syntax for math formulas. Pretty similar to math formulas as we are used to in the C based languages. Squinting, does this mean Fortran initially was a functional language?
This is an example of early Fortran:
PROGRAM SUM_SQUARES_EVEN
I = 5
ISUM = 0
10 IF (I) 70, 70, 20
20 IREM = I - 2 * (I / 2)
IF (IREM) 40, 30, 40
30 ISUM = ISUM + I * I
40 I = I - 1
GO TO 10
70 PRINT 100, ISUM
100 FORMAT (I5)
END
This calculates sum of squared even numbers, like:
0 + 22 + 0 + 42 + 0
The number of values calculated is limited by I = 5.
I guess the only things foreign to most programmers are those numeric labels, which are just labels to jump to, and the weird looking arithmetic if statements: These arithmetic conditionals check whether a value is less, equal or greater than 0 and jump to the corresponding labels.
The if statement on the 4:th line, after label 10, IF (I) 70, 70, 20 jumps out of the loop formed by the GO TO 10 further down. It simply jumps out of the loop, to label 70 if I is less or equal to zero.
It’s kind of assembly code, except for the math expressions, which need some cleverness.
The first: IREM = I - 2 * (I / 2)
simply checks whether I is even by performing an integer division to see if there is a remainder.
The second formula: ISUM = ISUM + I * I
the sum reduction, is only executed if IREM is 0, if I is an even number. It is guarded by the second arithmetic conditional: IF (IREM) 40, 30, 40
This jumps to line 30 if IREM is zero (i.e., if I is even); otherwise, it skips to 40.
Formula as assembly
The formula that checks whether I is even—by seeing if there’s an integer remainder:
IREM = I - 2 * (I / 2)
can be translated into the following sequence of statements
IREM = I / 2
IREM = 2 * IREM
IREM = I - IREM
With machine code like instructions it could be expressed like
IREM = DIV I 2
IREM = MUL 2 IREM
IREM = SUB I IREM
with a more mathematical notation, with parentheses for precedence:
IREM = SUB I (MUL 2 (DIV I 2))
The innermost parens: (DIV I 2)
Multiplied with with 2: (MUL 2 (DIV I 2))
Subtracted from I to see if the result is zero or not: (SUB I (MUL 2 (DIV I 2)))
Fortran’s math is pure, but its flow is all jumpy—just like assembler.
Lisp
Lisp is also a very early programming language, or mathematical notation, probably invented a few years after Fortran. I guess it wasn’t a programming language until the eval functions was written.
The very same program, calculating sum of squared even numbers up to 5, can be expressed in a early lisp like:
(DEFUN ONE-OR-LESS? (N)
(NOT (LESSP 1 N)))
(DEFUN EVEN? (N)
(EQ (REM N 2) 0))
(DEFUN SUMSQ-EVEN (N)
(COND
((ONE-OR-LESS? N) 0)
((EVEN? N) (PLUS (SUMSQ-EVEN (DIFFERENCE N 1))
(TIMES N N)))
(T (SUMSQ-EVEN (DIFFERENCE N 1)))))
(SUMSQ-EVEN 5)
If you follow and evaluate the expression (SUMSQ-EVEN 5) you’ll end up in a expression like:
(TIMES (PLUS 0
(TIMES 2 2))
(TIMES 4 4))
The last case of the cond is the outcome when N is 5. 5 is neither one or less, nor even. The result is a recursive call with N as 4.
The second lap, where N is 4 ends up with (PLUS (SUMSQ-EVEN 3) (TIMES 4 4)).
The third lap, where N is 3, ends up as recursive call (SUMSQ-EVEN 2) since 3 neither is one or less, nor even.
The fourth lap, where N is 2 ends up with (PLUS (SUMSQ-EVEN 1) (TIMES 2 2)).
The fifth lap, where N is 1, ends up with a 0.
Then the stack unwinds ending up with: (PLUS 0 (TIMES 2 2)) followed by (PLUS (PLUS 0 (TIMES 2 2)) (TIMES 4 4))
Remainder in Lisp
As we can see in the EVEN? function, Lisp had the remainder function, REM in the early days, while QUOTIENT did integer division. REM could though be implemented like above:
(DEFUN REM (X Y)
(DIFFERENCE X (TIMES Y (QUOTIENT X Y))))
It’s the same expression as the previous math expression with parenteses for precedence, that we got when translating the formula from Fortran. So are math expressions with instructions lisp expressions?
The lisp code, as a whole, is written in functional style. There are no mutable values and the whole program is formed as a single math expression, that could be evaluated as one. The SUMSQ-EVEN is recursive, as it calls itself withing the COND expression.
So in that sense: Is early Fortran noting more than a machine code assembler with a functional extension? There’s no mutation within the formulas translated.
Scheme
Early lisps did not have local bindings, like let-forms. Scheme is the oldest lisp I know of, from the 70:ies, that use let bindings like today. Sure you could simulate local bindings using lambdas in Lisp 1.5, essentially doing beta-reduction as in lambda calculus. But in Scheme you would probably solve the above problem with higher order functions, where function is data. Something like:
(define (numbers n) (iota n 1 1))
(define (square x) (* x x))
(define (sumsq-even n)
(let* ((xs (numbers n))
(evens (filter even? xs))
(squared (map square evens)))
(apply + squared)))
(sumsq-even 5)
This is much easier to read than the recursive solution.
And note that we left the realm of punch cards, and write code in lower case. Ever wonder why SQL still uses capital letters? Like it’s yelling at a mainframe?
Funny enough scheme is one of the very first languages with well defined tail call optimization. Any call in tail position won’t build stack. So you may have ended up writing it as the following tail call friendly way:
(define (sumsq-even n)
(define (helper acc n)
(cond
((<= n 1) acc)
((even? n) (helper (+ acc
(* n n))
(- n 1)))
(else (helper acc (- n 1)))))
(helper 0 n))
A nested define create a local in Scheme. This is not the case for defn in modern Clojure, which explicitly puts the var in a namespace. Clojure does neither make tail call optimizations automatically, but provide recur to make it explcit.
ML
Lisps are not the only functional languages. ML appeared a few years after Scheme, late 70:ies, with inferred static types. ML did also have tail call optimization. You could write the above either with higher order functions as:
fun square x = x * x;
fun even x = x mod 2 = 0;
fun sumSqEven n =
let
val numbers = List.tabulate (n, fn i => i + 1)
val evens = List.filter even numbers
val squared = List.map square evens
in
List.foldl (op +) 0 squared
end;
print (Int.toString (sumSqEven 5));
or recursivly as:
fun sumSqEven n =
let
fun helper acc 0 = acc
| helper acc k =
if k mod 2 = 0 then
helper (acc + k * k) (k - 1)
else
helper acc (k - 1)
in
helper 0 n
end;
print (Int.toString (sumSqEven 5));
In F#, a modern ML of today, we do lack fun and instead use let rec to make recursive functions. In ML, fun creates named function and optimizes them on tail calls.
Summary
Functional programming languages make it easy to extend the functional math expressions in C-like languages, so you can cover entire programs.
A formula in a C like program is functional, and does not include moving parts like mutated variables. The formula is an expression rather than a statement. Since early Fortran, is named after Formula Translator, and doesn’t provide much more than math expressions in a very low-level, almost assembly-like language. You could call it ‘machine code with a functional extension'.
But with this logic, a program in a functional language is like this formula, but all the way, to conver the whole program.
Epilogue
The first Fortran was a bit more advanced. It had DO CONTINUE loops, statement functions to simplify the formulas, as well as both external user functions and subroutines. Also, you could soon declare basic types so that integer variables didn’t have to start with the letters I, J, K, L, M, or N. Code got much easier to reason about:
FUNCTION SUMSQ_EVEN (N)
INTEGER N, I, REMAINDER, SUMSQ_EVEN
SQR(X) = X * X
SUMSQ_EVEN = 0
DO 20 I = 1, N
REMAINDER = I - 2 * (I / 2)
IF (REMAINDER) 20, 10, 20
10 SUMSQ_EVEN = SUMSQ_EVEN + SQR(I)
20 CONTINUE
RETURN
END
PROGRAM SUM_SQUARES_EVEN
INTEGER SUM, SUMSQ_EVEN
SUM = SUMSQ_EVEN(5)
PRINT *, SUM
END
Note that the returned value is the one with the same name as the function, SUMSQ_EVEN. A behaviour inherited by some other languages, like Pascal.
Pascal
Pascal was a language intended for beginners, with a strong static type system. According to early papers, it influenced ML, along with Algol and Lisp. If you see what I mean.
I did quite some Pascal during my school years.
program SumSquaresEven;
function SumSqEven(N: integer): integer;
var
I, RESULT: integer;
begin
RESULT := 0;
for I := 1 to N do
if I mod 2 = 0 then
RESULT := RESULT + I * I;
SumSqEven := RESULT;
end;
var
SUM: integer;
begin
SUM := SumSqEven(5);
writeln(SUM);
end.
Here SumsqEven := RESULT; essentially is return result in a C like language.
Pascal has also had some impact on C#
Basic
Do you remember Basic, that we were supposed to learn programming on in the 80:ies, through home computers like the popular Commodore 64. Here we had no named functions, only global variables and gotos and line numbers everywhere. It was just cruel:
10 LET N = 5
20 REM – CALCULATE SUM OF SQUARES FOR EVEN IN 1 TO 5
30 GOSUB 200
40 PRINT SUM
50 END
200 REM – SUM OF SQUARES OF EVEN 0 TO N
210 LET SUM = 0
220 FOR I = 1 TO N
230 LET REMAIN = I - 2 * INT(I / 2)
240 IF REMAIN <> 0 THEN GOTO 260
250 LET SUM = SUM + I * I
260 NEXT I
270 RETURN
Basic is an old language, purposly inspired by Fortran, so that the students should be able to switch to and pick up on a more serious programming language easily.
Maybe Fortran really was ‘functional assembly’. By the 80s, we were all just longing for some functions and less GOTO.