S-algol (St Andrews Algol)^[1]: vii is a computerprogramming language derivative ofALGOL 60 developed at theUniversity of St Andrews in 1979 byRon Morrison and Tony Davie. The language is a modification of ALGOL to contain orthogonaldata types that Morrison created for hisPhD thesis. Morrison would go on to becomeprofessor at the university and head of the department ofcomputer science. The S-algol language was used for teaching at the university at anundergraduate level until 1999. It was also the language taught for several years in the 1980s at a local school in St. Andrews,Madras College. The computer science textRecursive Descent Compiling^[2] describes arecursive descentcompiler for S-algol, implemented in S-algol.

PS-algol is apersistent derivative of S-algol. It was developed around 1981 at theUniversity of Edinburgh and of St Andrews. It supportsdatabase ability by providing for longevity of data in the form of a persistentheap that survives termination of PS-algol programs.

Ron Morrison's 1979 PhD thesis,On the Development of Algol, describes the design and implementation of the S-algol language.^[3] The technical report defining the language,The S-algol Reference Manual (1979, 1988), thanks several people for their help, includingDavid Turner for discussions on language design around 1975.^[4]: 5 The 1981 computer science textRecursive Descent Compiling describes the compiler implementation and bootstrapping process,^[2] and the 1982 bookAn Introduction to Programming with S-algol uses the language to teach computer programming.^[1]

The first S-algol implementation was on aPDP-11/40 computer running theUnix operating system.^[1]: vii Due to the small 64kilobyteaddress space available on the PDP-11, an interpretedbytecode implementation was chosen.^{[3]: 37–38} Asingle-pass,recursive descent compiler written in S-algol translated S-algol source into S-code, a bytecode for astack-based abstract machine tailored for S-algol. The S-code was then executed by aninterpreter. The S-algol implementation had many similarities with work on earlierPascal compilers. The technique of using a recursive descent compiler to produce code for an abstract machine was well known, with thePascal P compiler being a famous example from the early 1970s.^[2]: 137 The S-algol compiler was written using thestepwise refinement process^[2]: 71 described by Urs Amman for the development of a Pascal compiler^[5] and championed by the inventor of Pascal,Niklaus Wirth.^[6]

Reflecting the memory organization of the PDP-11 as 32K 16-bitwords, the S-code instruction encoding was designed so that each bytecode consisted of one word.^[3]: 38 The initialbootstrap was performed by writing an S-algol compiler inAlgol W on theIBM/360 that produced S-code, and using it to compile the compiler written in S-algol to S-code. The resulting S-code file was copied to the PDP-11 and executed on an S-code interpreter written for the PDP-11, making itself-hosting. The self-hosted S-algol compiler executed approximately 7.7 million S-code instructions to compile itself, generating an output file of about ten thousand S-code instructions (16-bit words).^[3]: 45

An S-code interpreter was written for theVAX computer runningVMS, making the VAX the first S-algolport. S-algol was also ported to theZilog Z80 microprocessor runningCP/M, includingraster graphics facilities that had been added to the language. In 1983, S-algol was used as the basis for the PS-algol system, used for research inpersistence. The PS-algol S-code interpreter was implemented inC, and the S-code language was extended to include raster graphics. The PS-algol implementation was the basis for S-algol ports to theMacintosh andSun workstations, featuring a compiler rewritten inC and targeting the extended S-code.^[4]: 5

S-algol was the basis for the PS-algol research in 1983, and a few years later PS-algol became the starting point for theNapier88 language and implementation. While all S-algol compilers produced S-code to be interpreted, a later Napier88 implementation experimented with generating code in C and compiling it with thegcc compiler to provide anative code implementation.^[7]

An S-algol program is a sequence of declarations and clauses. Language elements that are declared include constants, variables, procedures and structures. Constant and variable declarations must specify an initial value. The compiler infers the data type of the declared constant or variable from the type of the initial value, so the type is not stated explicitly. Data types include integer, real, boolean, string, pointer (to a structure), and file, and vectors (arrays) of these types. Procedure declarations do specify the data types of their arguments and return value (unless void). Structures also specify the data types of their fields. Clauses include expressions and control structures (if, case, for, while and repeat while). The if and case control structures can have values and can be used freely in expressions as long as the type compatibility rules are met.^[4][1]

! Comments are introduced by an exclamation point and continue until end of line.! The let keyword introduces declarations of constants and variables! Identifiers start with an alphabetic character followed by alphanumeric characters or the full stop (.)! An initial value must be given, and this determines the data type of declarationletwidth:=10! := sets the value of a variable, this is an intletanimal:="dog"! type stringletx:=-7;lety:=x+x! ; separates clauses, needed only if there are two or more clauses on a lineletn.a=6.022e+23! = is used to set the value of a constant, this is a cfloat (constant float)! if and case can have values and be used in expressionsletno.of.lives:=ifanimal="cat"then9else1! Sieve of Eratostheneswrite"Find primes up to n = ?"letn=readi! constant values can be set during the program runletp=vector2::noftrue! vector of bool with bounds 2 to nfori=2totruncate(sqrt(n))do! for indexes are constants so they use = rather than :=ifp(i)do! vector dereference uses parens like a procedure callforj=2*itonbyidop(j):=falsefori=2tondo    ifp(i)do writei,"'n"! 'n in a literal string is a newline! structure (record) type for a binary tree of cstrings! the pntr data type can point to a structure of any type, type checking is done at runtimestructuretree.node(cstringname;pntrleft,right)! inserts a new string into the binary tree headprocedureinsert.tree(cpntrhead;cstringnew->pntr)! the case clause ends with a mandatory default option, use default : {} if it is not neededcasetrueofhead=nil:tree.node(new,nil,nil)new<head(name):{head(left):=insert.tree(head(left),new);head}new>head(name):{head(right):=insert.tree(head(right),new);head}default:headprocedure print.tree(cpntrhead)ifhead~=nildo! ~= is the not equals operatorbeginprint.tree(head(left))writehead(name),"'n"print.tree(head(right))endletfruit:=nilfruit:=insert.tree(fruit,"banana")fruit:=insert.tree(fruit,"kiwi")fruit:=insert.tree(fruit,"apple")fruit:=insert.tree(fruit,"peach")print.tree(fruit)! print in sorted order! The end of the S-algol program is indicated by ??

As its name suggests, S-algol is a member of theALGOL family of programming languages. Morrison identifies five traits of the ALGOL family:^[3]: 5

1. Scope rules and block structure – Names can be introduced to define local quantities that are undefined outside thelocal environment, but different environments may use the same name unambiguously to represent different objects.^[3]: 5
2. Abstraction facility – Provision of a powerful abstraction facility to shorten and clarify programs. In the ALGOL family this is offered byprocedures withparameters.^[3]: 5
3. Compile-time type checking –Types can be checked by astatic analysis of the program.^[3]: 5
4. Infinite store – The programmer is not responsible for storage allocation and can create as many data objects as needed.^[3]: 5
5. Selective store updating – The program may selectively alter the store. In the ALGOL family this is effected by theassignment statement.^[3]: 6

S-algol was designed to differ from prior members of the ALGOL family by being designed according to semantic principles to provide power through simplicity, and simplicity through greater generality. (SeeOrthogonal.) Morrison describes three semantic principles that guided the design of S-algol:

1. Principle of correspondence – The rules governing names should be uniform and apply everywhere. This mostly applies to correspondence between declarations and procedure parameters, including consideration of all parameter passing modes. This principle was examined by R. D. Tennent in conjunction with Pascal,^[8] and has its roots in work byPeter Landin^[9] andChristopher Strachey.^{[3]: 9–10 [10]}
2. Principle of abstraction – It should be possible toabstract over all meaningful semantic categories in the language. Examples include the function, which is an abstraction overexpressions, and the procedure, an abstraction overstatements. Tennent and Morrison note that this is a difficult principle to apply because it is hard to identify the semantically meaningful constructs that should be abstracted.^[3]: 10
3. Principle of data type completeness – All data types should have the same rights in the language, and should be allowed in general operations such as assignment or being passed as a parameter.^[3]: 10 (Seefirst-class citizen.)

Morrison also identifies one more basic design consideration:

1. Conceptual store – The key design decisions concerning the store (memory management) include how the store is used, its relationship to data types, implementation ofpointers, and protection (constant locations that can't be updated).^{[3]: 10–11}

Morrison's thesis explains how the design principles were applied in S-algol.

The basic orprimitive data types in S-algol are integer, real, boolean, file, and string. (Laterpixel and picture types were added to supportraster graphics.)Integer,real, andboolean are types common to most programming languages. The file type is aninput/output (I/O)stream that allows writing or reading data objects. Thestring type in many languages at that time was considered acompound type, but including it as a native type makes the basic operations of concatenation, substring selection, length, and the comparisons (equals, less than, etc.) easier to use. It is much more pleasant than the arrays of characters used in Pascal.^[3]: 12

Vectors are provided with components of any type. For any data typeT,*T is the type of a vector with components of type T. The bounds of the vector are not part of its type but are determined dynamically, and multi-dimension arrays are implemented asvectors of vectors.^[3]: 12

Thestructure data type comprises any fixed number of fields each of a fixed type. The class of a structure is not part of the type but can be determined dynamically.^[3]: 12

Theclosure of basic types over vectors and structures provides an infinite number of data types. The language definition allows any type to be used anywhere a type is acceptable. This does not apply toinfix operators, as they are syntactic sugar for common functions and are not part of the semantic model.^{[3]: 12–13}

Vectors and structures have full rights and can be assigned as passed as parameters, but copy on assignment and when passed can be inefficient for large objects. Vectors and structures are treated as pointers to the objects, and the pointers are assigned and passed as parameters.Pointers as general objects themselves as inALGOL 68 andC are rejected for S-algol because of the concerns ofC.A.R. Hoare about thenull pointer^[11] and the problems withdangling pointers.^[3]: 13

S-algol provides trueconstant values, objects which value cannot be updated. This idea is due to Strachey, but constants in many languages such as Pascal are manifest constants, processed at compile time and not implemented as protected locations. Also it must be possible to declare a constant of any data type, not just the scalar types.^[3]: 13

S-algol is an expression-oriented language, andstatements areexpressions of typevoid. As a consequence, somecontrol structures are expressions that yieldvalues.

There are severalconditional constructs. The two-alternative version of the conditional isif <condition> then <clause> else <clause>, where the clauses can be statements or expressions. If they are expressions, they must have the same type. The one-armed conditionalif <condition> do <statement> has type void.^[3]: 13 Use ofdo instead ofelse in the conditional statement avoids thedangling else syntactic ambiguity.^[2]: 20

Thecase clause has a selector of any type which is matched using an equality test against expressions of the same type to find the selected clause. The case clause can be a statement or an expression, so the result clauses must all be statements (type void) or expressions of the same type. Matches are tested in order, so this resembles theguarded commands ofEdsger Dijkstra without thenon-determinism.^[3]: 14

Theloop statements are mostly conventional. Thefor loop is similar to that of Hoare.^[12] The control identifier is constant and cannot be modified inside the loop. Also conventional are thewhile <condition> do <statement> andrepeat <statement> while <condition> loops. Therepeat <statement> while <condition> do <statement> construct provides the early exit or "n-and-a-half"^[13] loop.^[3]: 14

S-algol abstracts expressions as functions and statements (void expressions) as procedures.Modules would provide the abstraction of declarations, but S-algol does not include modules because of the difficulties they pose with block-structured scope. The final syntactic category is sequencer, or control structure. Tennent used the termsequel for the abstraction over sequencers, these would be generalizations ofgoto andbreak. The best known abstraction in this category iscall-with-current-continuation, but it would not be well understood until some years later. S-algol does not include goto or break, and does not include abstraction over sequencers.^[3]: 14

Every data object in S-algol must be given a value when it is declared. This corresponds tocall by value parameter passing and removes the possibility of using an uninitialised value. In fact call by value is the only parameter passing method in S-algol. Reference and result parameters are rejected, which is consistent with the S-algol ban on passingl-values. Structures and vectors are passed as pointers to the objects, but this is still call by value as the behavior is the same as the value used on the right side of assignments.^[3]: 15

Every declaration has a parametric equivalent. All procedure parameter types must be specified. Any procedure passed as a parameter has its full type specified (in contrast to Pascal) and the same is true for a structure class.^[3]: 15

S-algol provides thefile data type for I/O streams, and several variations ofread andwrite are defined to operate on the basic types. It is expected that individual implementations will extend these simple facilities as needed.^[3]: 15

ALGOL languages have been criticized as being verbose. S-algol attempts to improve this by providing less restrictive syntax.^[1]: 159 This is demonstrated mostly in the declaration syntax. Since variable declarations must always include an initial value, the type does not need to be specified explicitly.^[3]: 17

Although it would be possible to infer procedure parameter and return types by examining where the procedure is called, S-algol does require parameter and return types to be specified. This is a practical decision, since it should be possible to understand a procedure without examining its calls.^[3]: 17

Most ALGOLs require that all declarations come before the statements in a block. In S-algol, declarations may be mixed with statements because everything must be declared before it is used and there is no goto that would permit jumping past a declaration.^[3]: 17

• Napier88

• Algol 60 implementations and dialects,Computer History Museum Software Preservation Group
• Persistent S-algol

• ALGOL 60 dialect

• Articles with short description
• Short description matches Wikidata