S-algol

Ron Morrison's 1979 PhD thesis, On the Development of Algol, describes the design and implementation of the S-algol language. The technical report defining the language, The S-algol Reference Manual (1979, 1988), thanks several people for their help, including David Turner for discussions on language design around 1975. The 1981 computer science text Recursive Descent Compiling describes the compiler implementation and bootstrapping process, and the 1982 book An Introduction to Programming with S-algol uses the language to teach computer programming. The first S-algol implementation was on a PDP-11/40 computer running the Unix operating system. and championed by the inventor of Pascal, Niklaus Wirth. Reflecting the memory organization of the PDP-11 as 32K 16-bit words, the S-code instruction encoding was designed so that each bytecode consisted of one word. ==Language overview==

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. let width := 10 ! := sets the value of a variable, this is an int let animal := "dog" ! type string let x := -7 ; let y := x + x ! ; separates clauses, needed only if there are two or more clauses on a line let n.a = 6.022e+23 ! = is used to set the value of a constant, this is a cfloat (constant float) let no.of.lives := if animal = "cat" then 9 else 1 write "Find primes up to n = ?" let n = readi ! constant values can be set during the program run let p = vector 2::n of true ! vector of bool with bounds 2 to n for i = 2 to truncate(sqrt(n)) do ! for indexes are constants so they use = rather than := if p(i) do ! vector dereference uses parens like a procedure call for j = 2 * i to n by i do p(j) := false for i = 2 to n do if p(i) do write i, "'n" ! 'n in a literal string is a newline structure tree.node(cstring name ; pntr left, right) procedure insert.tree(cpntr head ; cstring new -> pntr) case true of head = nil : tree.node(new, nil, nil) new head(name) : { head(right) := insert.tree(head(right), new) ; head } default : head procedure print.tree(cpntr head) if head ~= nil do ! ~= is the not equals operator begin print.tree(head(left)) write head(name), "'n" print.tree(head(right)) end let fruit := nil fruit := 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 ? ==Semantic principles==

As its name suggests, S-algol is a member of the ALGOL family of programming languages. Morrison identifies five traits of the ALGOL family: and has its roots in work by Peter Landin and Christopher Strachey. • Principle of abstraction – It should be possible to abstract over all meaningful semantic categories in the language. Examples include the function, which is an abstraction over expressions, and the procedure, an abstraction over statements. 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. • 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. (See first-class citizen.) Morrison also identifies one more basic design consideration: • Conceptual store – The key design decisions concerning the store (memory management) include how the store is used, its relationship to data types, implementation of pointers, and protection (constant locations that can't be updated). ==Design==

Morrison's thesis explains how the design principles were applied in S-algol. Data types The basic or primitive data types in S-algol are integer, real, boolean, file, and string. (Later pixel and picture types were added to support raster graphics.) Integer, real, and boolean are types common to most programming languages. The file type is an input/output (I/O) stream that allows writing or reading data objects. The string type in many languages at that time was considered a compound 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. and the problems with dangling pointers. The control identifier is constant and cannot be modified inside the loop. Also conventional are the while do and repeat while loops. The repeat while do construct provides the early exit or "n-and-a-half" loop. Abstractions 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 term sequel for the abstraction over sequencers, these would be generalizations of goto and break. The best known abstraction in this category is call-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. Declarations and parameters Every data object in S-algol must be given a value when it is declared. This corresponds to call 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 passing l-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. 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. Input output model S-algol provides the file data type for I/O streams, and several variations of read and write are defined to operate on the basic types. It is expected that individual implementations will extend these simple facilities as needed. Concrete syntax ALGOL languages have been criticized as being verbose. S-algol attempts to improve this by providing less restrictive syntax. 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. 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. 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. ==See also==