naur — ALGOL 60 Compiler in Scheme

[ALGOL 60] is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors.

— C. A. R. Hoare

https://florida.moe/algol60

(Eventually will be) retargetable whole-program ALGOL 60 compiler in R5RS implementing the Modified Report on the Algorithmic Language ALGOL 60. Written using multiple passes like Nanopass, but with a much simpler matcher.

Work in progress.

Compiler Structure

1. The source file is parsed into SX-ALGOL. (parser.scm)

2. Forward-declaration of labels. (forward-declare-labels.scm) Blocks are scanned for the closest enclosing labels and they are forward-declared with the implicit-label declaration. The implicit-label declarations determine the lexical scope of the labels.

3. All identifiers are renamed to be unique. (rename.scm)

4. All own variables are lifted. (lift-own.scm) After this stage, there are no own declarations.

5. The use of the procedure identifier to assign the return value of the procedure is changed to be a special variable. (explicit-return.scm) After this, a special return statement is added to the bottom of every returning procedure and every occurence of the procedure identifier is a procedure call ("activiation of the procedure").

6. Lifting of array bounds declarations (array-bounds-lift.scm). For example, begin array A[x+y:z+w]; statements ...; end is transformed into

   begin integer t1, t2; t1 := x + y; t2 := z + w;
    begin array A[t1:t2]; statements ...; end; end
   

   This allows the types of declared arrays to carry information about bounds information of array variables. This also makes analyzing the bounds of arrays simpler, because they are either unchanging identifiers or constants.

7. Type annotations. (annotate.scm) All expressions are annotated with the type that they would produce. The expressions are wrapped as #(typed expression type), where type is

   • integer, boolean, real, label
   • arithmetic for certain operations
   • #(switch length) (length is #f for unknown length).
   • #(procedure return-type argument-type-list) (argument-type-list is #f for unknown argument lists).
   • #(array element-type bounds-list) bounds-list is either a list of lists of two elements, each of which is either an identifier or an integer, or the whole bounds-list if #f.

   The identifier of a for loop is also given a type annotation.

8. Type checking pass. The special procedures integer->real and real->integer are inserted to coerece expression types (see discussion on "transfer" functions in the Report) into the correct type for that expression. Arithmetic procedures are monomorphized.

Higher Order Procedure Arguments and Thunks

A major difficulty of ALGOL 60 is that higher-order procedures do not carry type information about their arguments. This means

1. It is impossible to know which arguments are passed by name or by value.
2. It is impossible to know if a procedure is passed by name, or invoked with no arguments to make a value.

I could make changes to the ALGOL 60 grammar to fix this change, but I decided against it. The point here is to implement ALGOL 60, not yet another ALGOL-like. To cope with this:

1. All arguments are passed as addresses.
2. Procedure types and strings are just the addresses where the thing is.
3. All other types are thunks that return an address. This address can be dereferenced and assigned to (for arrays, atomic types).
4. Arguments passed by value are copied at procedure entry time.

Passing the incorrect arguments to a higher-order procedure is undefined behavior and will cause Bad Things to occur.

Unit Testing Ideas

• Undeclared identifiers used
• Identifiers that are the same declared at once
• Assignment to typeless procedure
• For loop where the assignment variable is the procedure identifier
• Testing proper scoping of labels, i.e. labels after declarations cannot be jumped into