On the Shoulders of Giants

The Text of a Program

Comments that begin with ;

The semicolon opens a comment in most assembly languages since the 1960s, and in Lisp and its descendants. Scaly has it from Scheme: the compiler's own parser is generated by stylesheets written in DSSSL, which is a Scheme dialect.

Block comments ;* … *;

The bracketing pair with an asterisk is PL/I's /* … */ (1964), which B and C made universal. Scaly keeps the shape and exchanges the slash for its own comment sign.

The line as a statement, the colon between two on one line

That a line break ends a statement is as old as Fortran (1957). Putting a second statement on the same line after a colon is the habit of the BASIC dialects of the 1970s.

Blocks in braces

Block structure — a group of statements that counts as one and has names of its own — is ALGOL 60's, written begin … end. CPL bracketed its blocks with the section sign, BCPL with $( and $), and B (Ken Thompson, 1969) with the braces that C handed to everybody. Opening each brace on a line of its own is the style named after Eric Allman, whose BSD sources made it known; it keeps the vertical alignment of begin and end.

Operators are identifiers

That an operator is an ordinary name made of operator characters, and its meaning an ordinary definition, is the way of ML and Haskell, and of Smalltalk's binary messages; Scala showed that it carries a whole language without a single operator built into the grammar. The words and, or and not are ALGOL 60's logical operators in the spelling ALGOL 68 and Pascal gave them.

= compares, <> is unequal

The equals sign for equality is mathematics', and ALGOL 60 kept it that way by giving the assignment a sign of its own. <> is how Pascal, BASIC and SQL write ALGOL's ≠ on a keyboard that has none.

Precedence

The order of the levels — multiplication before addition, then shifts, comparisons, equality, and the bitwise operators below those — is C's table, which C has from B. It is not a table in the compiler: the levels are written in the standard library as types whose values wait for what follows, and the planner reads an operation by them.

Hexadecimal literals with 0x

C.

Expressions embedded in a string

Interpolation comes from the Unix shell, where $name inside double quotes is replaced by its value; Perl, Ruby and Swift extended it from names to expressions. The backtick as the sign of something to be evaluated in place is the shell's too.

Names and Values

The assignment :=

ALGOL 58, the preliminary report that preceded ALGOL 60, and through ALGOL 60 the whole family: Simula, Pascal, Modula, Ada, Smalltalk in its ASCII form. The sign reads becomes and leaves = to mean what it means in mathematics. Before it, Zuse's Plankalkül and Rutishauser's notation wrote an arrow pointing at the target. Go uses the same sign for a declaration; Scaly does not — a name is introduced by let or var, and := only ever changes one that exists.

let and var

let for a name bound to a value is Peter Landin's ISWIM (1966), and from there ML and every functional language; var for something that varies is Pascal's (1970). The pair as two keywords of equal rank, one for the name that stays and one for the name that changes, is Swift's (2014) — Scala and Kotlin write val and var.

The name first, then a colon, then the type: count: int

Parameters, fields, typed bindings and the arms of a union are all declared this way, and among programming languages it is Pascal's way (Niklaus Wirth, 1970). ALGOL 60 and Wirth's own ALGOL W before it put the type first, integer n, and C followed them. Older languages had the name in front — COBOL (1959) and PL/I (1964) write a name and then its attributes — but without the colon. The colon itself is older than programming: it is how mathematics states what a thing is, f: A → B, and from there it entered type theory (N. G. de Bruijn's Automath, 1967) and ML, independently of Pascal. Nearly every language designed since 2000 has gone back to this order, because a type that may be left out is easier to leave out at the end.

The value of a body is its last expression

Lisp (1958), where everything is an expression; then ALGOL 68 and BLISS among the block-structured languages, and today Ruby, Scala and Rust. The conditional expression itself — an if that has a value — is John McCarthy's invention, taken into ALGOL 60.

A call without parentheses

Application by juxtaposition, print "x", is the notation of the lambda calculus and of ML and Haskell; Logo and Ruby brought it to imperative code. That the argument list in parentheses is a tuple — one value — is ML's view of a function of several arguments.

Integer and float types named by their width

i32, u8, f64 are Rust's names, which follow LLVM's. size_t is C's. The vector types f64x4, u8x16 are named as in Rust's portable SIMD and in WebAssembly.

Control Flow

while, repeat, for … in

while began as a clause of ALGOL 60's for statement and became a statement of its own in ALGOL W, BCPL and Pascal. repeat is Pascal's word; the unconditional loop it stands for in Scaly is BCPL's REPEAT. A for that walks over the elements of a collection instead of counting comes from CLU's iterators (1975); the spelling with in is the Bourne shell's and Python's.

break, continue, named loops

break is BCPL's and B's, continue C's. Leaving an outer loop by its name is Ada's (exit Outer), taken up by Java's labelled break. A loop that yields the value its break carries is Rust's loop.

match and case

The case statement was proposed by Tony Hoare and appeared in ALGOL W (1966); C's switch is its best-known child.

A self tail call is a loop

Scheme (Steele and Sussman, 1975) was the first language to require that a call in tail position take no stack, and so made recursion a legitimate way to write a loop.

Types and Definitions

A structure declared with its fields in parentheses, constructed by a call

Simula 67: a class is declared with parameters, the parameters are its attributes, and creating an object is handing over their values. Most languages after it separated the fields from the constructor that fills them and then spent decades removing the repetition again — Scala's class parameters (2004), Kotlin's primary constructor (2011), the records of C# and Java. Scaly's define Point (x: int, y: int) with Point(1, 2) is that form, and like Scala, Kotlin and Swift it needs no new.

init and this

init as the name of the routine that initializes an object is Objective-C's convention, made a keyword by Swift. this is Simula's, through C++. Writing the receiver as the first parameter of a method follows Python's self and Rust's.

function and procedure

The two words are ALGOL's and Pascal's, where they only say whether there is a result. That a function is checked to have no effect — no write, no global state, no input or output — goes back to Euclid (1977), a language designed for verifiable programs; Ada's functions with in parameters only, Fortran 95's PURE and Nim's func beside proc are the same idea.

mutable on a parameter that is written

Ada's parameter modes (in, out, in out, 1983) are the first to make a routine say in its signature what it changes; Swift's inout and Rust's &mut are the modern forms. A field that cannot change unless it says so is ML's default, and Rust's.

returns and throws

CLU (Barbara Liskov, 1975) wrote a procedure's result as returns (int) and its exceptions as signals (…) after the parameter list. throws is Java's word for the second.

What happens underneath is Rust's. A routine that can fail returns a Result[Payload, Error] — a union of the value and the error — and nothing is unwound: Rust's Result gave that type its name and made it the one way a systems language reports failure, after Haskell's Either had shown that an error can be an ordinary value. And try descends from Rust's try! macro, the predecessor of its ? operator: look at the result, go on with the value, or return the error to the caller at once — which Scaly spells else throw. Swift (2015) put the vocabulary of exceptions, throws and try, on the same mechanism, and Scaly follows it in the words.

Unions and choose

A type that is one of several named alternatives, each with its own payload, taken apart by a construct that names the alternative and binds the payload: ALGOL 68's united modes and conformity clause are the first form, Hope (Edinburgh, 1980) and ML made it the centre of a language as algebraic data types with pattern matching, and Rust and Swift brought it to systems programming. The word when for an arm is Ada's.

Option, the ?, and null

The null reference is Tony Hoare's, introduced into ALGOL W in 1965 and later called by him his billion-dollar mistake. The repair — a separate type for a value or nothing — is ML's option. The question mark after a type is C#'s (2005), and Swift and Kotlin made T? the only type that can hold null, as Scaly does. That an optional reference costs no extra space, the null address serving as the empty case, is known from Rust.

Generics in square brackets

CLU had parameterized types written array[int]; Eiffel and Scala kept the brackets where C++ and Java chose angle brackets and the parsing trouble that comes with them. Compiling one copy of the code per type argument is how Ada's generics and C++'s templates were always implemented. The names of those copies in the object file follow the Itanium C++ ABI, so that every existing debugger and linker tool can read them.

Lambdas and delegates

The anonymous function is Alonzo Church's lambda calculus (1930s) and Lisp's LAMBDA; the backslash as the nearest ASCII character to λ is Haskell's. delegate for the named type of a function value together with what it captured is C#'s.

ref[T] beside pointer[T], & and *

The address-of and dereference operators are B's. The reference — an address that is used as if it were the thing itself and cannot do arithmetic — is C++'s (1985).

is and as

The type test written v IS T is Oberon's (Niklaus Wirth, 1987). The pair — is to ask for a type and as to convert to it, both written after the value — is Object Pascal's as Delphi had it (1995), and went with its designer, Anders Hejlsberg, into C# (2000). Swift, Kotlin and the Clinical Quality Language have the pair from there; Rust has as.

Memory

Scaly frees memory by region: every object belongs to a page that belongs to a call or to a longer-lived owner, and the whole region goes at once. Allocating by lifetime instead of by object is old systems practice — the arenas, zones and pools of compilers and servers, described by David Hanson in 1990. Making it a property of the language, with the compiler working out which region each value belongs to, is the work of Mads Tofte and Jean-Pierre Talpin (1994) and its implementation in the ML Kit. Cyclone (2002) brought regions to a C-like language and had the programmer name them; Rust's lifetimes descend from Cyclone.

Scaly stands closer to Tofte and Talpin than to Rust: the regions are inferred, ordinary code names none, and what the programmer sees is a refusal when a value would outlive its region. That check is escape analysis — the analysis Java and Go compilers use to decide what may live on the stack — turned from an optimization into a rule.

The pattern 0xDD that SCALY_POISON writes over released memory is the one Microsoft's debug heap writes over freed blocks.

Self-Scaling

That a plain loop runs in parallel when the compiler can prove it safe, with no syntax to ask for it, is the promise of the auto-parallelizing Fortran compilers of the 1980s; Fortress (Guy Steele, Sun, 2006) made the parallel loop the default of a language, and ParaSail (Tucker Taft, 2009) built a whole language around implicit parallelism without a global heap. What they needed and what Scaly has in its checked function is a way to know that a body has no effects.

The engine underneath is Cilk's (MIT, 1994): fork-join tasks scheduled by work stealing. When a potential fork becomes a real one is decided by heartbeat scheduling (Acar, Charguéraud, Guatto, Rainey and Sieczkowski, 2018), which bounds the cost of parallelism against the work done.

Fibers are coroutines (Melvin Conway, 1963); the routine that switches between them is modelled on Boost.Context. Channels come from Tony Hoare's Communicating Sequential Processes (1978) by way of occam and Go, and from Go comes the principle that a routine doing input and output looks like any other and needs no async mark.

Modules and Packages

module and use

The module as the unit that hides its insides is Modula's (Niklaus Wirth, 1975), and use to make another unit's names visible is Ada's. The system as Scaly has it is Rust's: a file declares its child modules by name (module parser, Rust's mod parser;) and the compiler finds the file; the modules form a tree of paths; use shortens a path to its last name or, with a star, opens a whole module; and a package has one root file from which everything else is reached.

The interface beside the implementation

Modula-2's definition modules and Ada's package specifications separated what a unit promises from how it keeps the promise, and were written by hand. Scaly's are generated from the sources, as Swift's module interfaces are.

The prelude

A standard library that is visible without being asked for, under that name, is Haskell's.

A package is its sources

Go: packages are distributed as source and compiled into a cache on the machine that uses them.

An Unexpected Ancestor

The Clinical Quality Language is a language of the health-care standards body HL7 for stating clinical rules and quality measures — a pure expression language over patient data, and no relative of any systems language. Scaly's author worked with it, and it left marks:

• define as the one word that introduces a named thing. A CQL library is a list of define statements, each a name and what it stands for.

• The logical operators as words, including xor; CQL writes and, or, not, xor and has no symbols for them.

• is and as after a value, to test its type and to convert it — which CQL in turn has from C#.

• A function's result type after the word returns.

• An identifier in quotes, which may then contain spaces or any other character.

• The version of a library named where the library is asked for, in the source text itself and not in a file beside it.

• = for equality in a language whose definitions have no need of it for anything else.

And What Is Scaly's Own?

Less than one would like to claim. The honest account of four candidates:

One define for everything

A structure, a union, a namespace, a constant, a type alias and a delegate type are all a define followed by what the name stands for; a structure without fields is a namespace. The ambition is not new: BETA (Kristensen, Madsen, Møller-Pedersen and Nygaard, from 1976) folded class, procedure, function and type into a single construct, the pattern, and Zig binds structures, unions and namespaces alike with an ordinary constant declaration. Scaly's form — one keyword, and the shape of what follows decides — was arrived at on its own, and no other language is known to draw the line in the same place.

Precedence is not part of the grammar

Not Scaly's invention. Prolog let a program declare its operators and their priorities in the 1970s, ML and Haskell have fixity declarations, Swift has precedence groups; all of them parse an expression as a flat sequence first and give it structure afterwards, as Scaly does.

The operation, read strictly from left to right

Smalltalk reads its binary messages from left to right with no precedence at all, APL from right to left, and Pony refuses to choose and demands parentheses. What Scaly is building goes one step further: the type of the value so far says what the next thing means — an argument, a member, an operator that leaves a value waiting for its right side, as a section does in Haskell. That combination has no model that the author knows of. It is also not finished: the binding strength of the operators is such a protocol of waiting types already, but a step is still chosen by the shape of what follows as well as by the type.

No semicolons

The line end as a separator is Fortran's and BASIC's, and Python, Go, Swift, Kotlin and Scala all found ways to spare the programmer the semicolon. Scaly's part is small: the line end and the colon are the same token, so that the grammar needs no rule about where a statement may continue, and the semicolon, no longer wanted, became the comment sign.

One thing is a discipline more than an invention, and the author held to it throughout: every sign means one thing. Parentheses are always a tuple — a parameter list is a tuple, the fields of a structure are a tuple, the arguments of a call are a tuple, and because a tuple of one is that one, a single argument needs no parentheses at all. Braces are always a block. Brackets are always a list, of values or of types. And no arithmetic sign is borrowed for something that is not arithmetic: < and > compare and never enclose type arguments, = compares and never assigns, and the signs that are not arithmetic — #, ^, !, ?, the colon, the backslash — are kept out of operators altogether. Most languages descended from C give up each of these somewhere: parentheses that group, call and cast, braces that are blocks here and values there, angle brackets that are generics until they are a shift. The exceptions Scaly allows itself are inherited ones — the = inside ALGOL's :=, and B's prefix * and & for following and taking an address.

What does seem to be Scaly's own lies elsewhere. The lifetime suffixes on a construction — # for the caller's region, ^name for a named one, ! for a thrown value — are a notation found nowhere else, small as it is. So is the pairing that gives the language its name: regions the compiler infers, functions the compiler checks to be pure, and a plain for that runs in parallel because of both. Each part has a history told above; that one language rests all three on each other is new. And no other compiler is known whose grammar is an SGML document.

The Implementation

A compiler written in its own language

The Lisp compiler of Timothy Hart and Michael Levin (1962) is the first that compiled itself. Shipping the compiler in a portable intermediate form, so that a new machine can build it without already having it, is the Pascal-P kit from Zurich (1970s); Scaly's seed is the same idea with LLVM's textual IR in place of P-code.

LLVM

Everything behind the emitter — optimization, code generation for every target, the in-process JIT — is LLVM, begun by Chris Lattner and Vikram Adve at the University of Illinois in 2000. Debug information is DWARF.

The grammar as a document

Scaly's grammar is an SGML document (Charles Goldfarb; ISO 8879, 1986), and parser, syntax tree and editor grammar are generated from it by DSSSL stylesheets (ISO/IEC 10179, 1996). The tools were James Clark's SP and Jade, and are now ports of them written in Scaly. This book is DocBook, produced by the same route.

Tests inside the prose

The chapters on expressions, definitions and control flow are generated from documents whose examples are executed as tests. That a program and its explanation are one text is Donald Knuth's literate programming (1984).

The REPL and the language server

The read-eval-print loop is Lisp's, in name and in substance. The language server speaks the protocol Microsoft published in 2016 for Visual Studio Code.