Programming Algol 68 Made Easy - Nunan.myzen.co.uk
Programming Algol 68Made EasySian LeitchPhœnix Engineering
TEX is a trademark of the American Mathematical Society.Copyright c Sian Leitch, 1995, 1997, 2000, 2001.This document is subject to the provisions of the GNU General Public Licenceverstion 2, or at your option, any later version.Publishing history First edition published by Oxford & Cambridge Compilers Ltd in 1995. Second (revised) edition published by Oxford & Cambridge Compilers Ltdin 1997. Third edition published by Phoenix Engineering in 2000. Revised by Phoenix Engineering in 2001, 2002.Prepared in Scotland.
ToAad van WijngaardenFather of Algol 68
ContentsPreface123Introduction1.1What you will need1.2Terminology . . . .1.3Values and modes .1.4Integers . . . . . . .1.5Identity declarations1.6Characters . . . . .1.7Real numbers . . . .1.8Program structure .1.9Comments . . . . .1.10 External values . . .1.11 Summary . . . . . .x.122234679111313Formulæ2.1Monadic operators . . .2.2Dyadic operators . . . .2.3Multiplication . . . . .2.4Division . . . . . . . . .2.5Exponentiation . . . . .2.6Mixed arithmetic . . . .2.7Order of elaboration . .2.8Changing the mode . .2.9Miscellaneous operators2.10 Operators using CHAR .2.11 print revisited . . . . .2.12 Summary . . . . . . . .15151618192021212223232324Repetition3.1Multiples . . . . . . . . . . . .3.1.1Row-displays . . . . .3.1.2Dimensions . . . . . .3.1.3Subscripts and bounds3.2Slicing . . . . . . . . . . . . . .3.3Trimming . . . . . . . . . . . .3.4Printing multiples . . . . . . .3.5Operators with multiples . . .262728293032333536.iv
4.1Boolean values . . . . . . . .4.2Boolean operators . . . . . .4.3Relational operators . . . . .4.4Compound Boolean formulæ4.5Conditional clauses . . . . .4.5.1Pseudo-operators . .4.6Multiple choice . . . . . . . .4.7Summary . . . . . . . . . . .444545464849525457Names5.1Assignment . . . . . . . . . . .5.1.1Copying values . . . .5.1.2Assigning operators .5.2Assignments in formulæ . . . .5.3Multiple names . . . . . . . . .5.4Assigning to multiple names .5.4.1Individual assignment5.4.2Collective assignment5.5Flexible names . . . . . . . . .5.6The mode STRING . . . . . . .5.7Reference modes in transput .5.8Dynamic names . . . . . . . .5.9Loops revisited . . . . . . . . .5.10 Abbreviated declarations . . .5.11 Summary . . . . . . . . . . . es . . . . . . . . . . . . . . .6.1.1Routine modes . . . . . . .6.1.2Multiples as parameters . .6.1.3Names as parameters . . . .6.1.4The mode VOID . . . . . . .6.1.5Routines yielding names . .6.1.6Parameterless routines . . .6.2Operators . . . . . . . . . . . . . . .6.2.1Identification of operators .6.2.2Operator usage . . . . . . .6.2.3Dyadic operators . . . . . .6.2.4Operator symbols . . . . . .6.3Procedures . . . . . . . . . . . . . .6.3.1Parameterless procedures .6.3.2Procedures with sRanges . . . . . . .Program repetition .Nested loops . . . .Program structure .The FORALL loop . .Summary . . . . . .v.Index
CONTENTS6.47vi6.3.3Procedures as parameters . .6.3.4Recursion . . . . . . . . . . .6.3.5Standard procedures . . . . .6.3.6Other features of procedures .Summary . . . . . . . . . . . . . . . 8.1United mode declarations . .8.2United modes in procedures .8.3Conformity clauses . . . . . .8.4Summary . . . . . . . . . . .122122124126128Transput9.1Books, channels and files .9.2Reading books . . . . . . .9.3Writing to books . . . . . .9.4String terminators . . . . .9.5Events . . . . . . . . . . . .9.5.1Logical file end . .9.5.2Physical file end .9.5.3Value error . . . .9.5.4Char error . . . . .9.6The command line . . . . .9.7Environment strings . . . .9.8Writing reports . . . . . . .9.9Binary books . . . . . . . .9.10 Internal books . . . . . . .9.11 Other transput procedures9.12 Summary . . . . . . . . . 4710 Units10.1 Phrases . . . . . . . . . . . .10.2 Contexts . . . . . . . . . . .10.3 Coercions . . . . . . . . . . .10.3.1 Deproceduring . . .10.3.2 Dereferencing . . . .10.3.3 Weakly-dereferencing10.3.4 Uniting . . . . . . .10.3.5 Widening . . . . . .10.3.6 Rowing . . . . . . cture denotations .7.2Field selection . . . . .7.3Mode declarations . . .7.4Complex numbers . . .7.5Multiples in structures .7.6Rows of structures . . .7.7Transput of structures .7.8Summary . . . . . . . .Contents.Index
CONTENTS.15615715815916116316316516717017017111 Advanced constructs11.1 Bits, bytes and words . .11.1.1 Radix arithmetic11.2 The mode BITS . . . . . .11.3 Overlapping slices . . . .11.4 Completers . . . . . . . .11.5 References to names . . .11.6 Identity relations . . . . .11.7 The value NIL . . . . . .11.8 Queues . . . . . . . . . .11.9 The procedure add fan .11.10 More queue procedures .11.11 Trees . . . . . . . . . . .11.12 Parallel programming . .11.13 Summary . . . . . . . . .17217317317618018218418618819019419619820120212 Program development12.1 Writing programs . . . . . . .12.1.1 Top-down analysis . .12.1.2 Program layout . . . .12.1.3 Declarations . . . . . .12.1.4 Procedures . . . . . .12.1.5 Monetary values . . .12.1.6 Optimisation . . . . .12.1.7 Testing and debugging12.1.8 Compilation errors . .12.1.9 Arithmetic overflow .12.1.10 Documentation . . . .12.2 Non-canonical input . . . . . .12.3 A simple utility . . . . . . . .12.3.1 The source code . . .12.3.2 Routines . . . . . . . .12.3.3 Dry-running example .12.3.4 ALIEN procedures . . .12.4 Summary . . . . . . . . . . . 13Contents10.3.7 Voiding . . . .10.3.8 Legal coercionsEnclosed clauses . . . .Primaries . . . . . . . .Secondaries . . . . . . .Tertiaries . . . . . . . .Quaternaries . . . . . .Balancing . . . . . . . .Well-formed modes . . .Flexible names . . . . .Orthogonality . . . . .Summary . . . . . . . .viiIndex
CONTENTS13 Standard Prelude13.1 Standard modes . . . . . . . . . . . . . .13.2 Environment enquiries . . . . . . . . . . .13.2.1 Arithmetic enquiries . . . . . . .13.2.2 Character set enquiries . . . . . .13.3 Standard operators . . . . . . . . . . . .13.3.1 Method of description . . . . . .13.3.2 Standard priorities . . . . . . . .13.3.3 Operators with row operands . .13.3.4 Operators with BOOL operands .13.3.5 Operators with INT operands . .13.3.6 Operators with REAL operands .13.3.7 Operators with COMPL operands .13.3.8 Operators with mixed operands .13.3.9 Operators with BITS operands .13.3.10 Operators with CHAR operands .13.3.11 Operators with STRING operands13.3.12 Assigning operators . . . . . . .13.3.13 Other operators . . . . . . . . . .13.4 Standard procedures . . . . . . . . . . . .13.4.1 Mathematical procedures . . . .13.4.2 Other procedures . . . . . . . . .13.4.3 ALIEN declarations . . . . . . . .13.4.4 ALIEN routines . . . . . . . . . .13.5 a68toc extensions . . . . . . . . . . . . .13.5.1 Modes peculiar to a68toc . . . .13.5.2 a68toc constructs . . . . . . . . .13.5.3 Operators . . . . . . . . . . . . .13.6 Control routines . . . . . . . . . . . . . .13.6.1 Floating-point unit control . . .13.6.2 Terminating a process . . . . . .13.6.3 Garbage-collector control . . . .13.7 Transput . . . . . . . . . . . . . . . . . .13.7.1 Transput modes . . . . . . . . .13.7.2 Standard channels . . . . . . . .13.7.3 Standard files . . . . . . . . . . .13.7.4 Opening files . . . . . . . . . . .13.7.5 Closing files . . . . . . . . . . . .13.7.6 Transput routines . . . . . . . . .13.7.7 Interrogating files . . . . . . . . .13.7.8 File properties . . . . . . . . . .13.7.9 Event routines . . . . . . . . . .13.7.10 Conversion routines . . . . . . .13.7.11 Layout routines . . . . . . . . . .13.8 Summary . . . . . . . . . . . . . . . . . ndex
CONTENTSAAnswersA.1 ChapterA.2 ChapterA.3 ChapterA.4 ChapterA.5 ChapterA.6 ChapterA.7 ChapterA.8 ChapterA.9 ChapterA.10 ChapterA.11 1.271271273275280282289293295297316318328Index
PrefaceIt is a fallacy to say that progress consists of replacing the workable by the new.The brick was invented by the Babylonians and has been used virtually unchangedfor 2500 years. Even now, despite the advent of curtain-walling, the brick is stillthe primary building material. Likewise, the long-predicted revolution in computerprogramming to be produced by the introduction of fourth- and fifth-generationlanguages has not come to pass, almost certainly because their purported advantages are outweighed by their manifest disadvantages. Third-generation languagesare still used for the bulk of the world’s programming. Algol 68 has been used asa paradigm of third-generation languages for 32 years.Each computer programming language has a primary purpose: C was developedas a suitable tool in which to write the Unix operating system, Pascal was designedspecifically to teach computer programming to university students and Fortran wasdesigned to help engineers perform calculations. Where a programming languageis used for its design purpose, it performs that purpose admirably. Fortran, whenit first appeared, was a massive improvement over assembler languages which hadbeen used hitherto. Likewise, C, when restricted to its original purpose, is anadmirable tool, but it is a menace in the hands of a novice. However, novices donot write operating systems.According to the “Revised Report on the Algorithmic Language Algol 68” (seethe Bibliography), Algol 68 was “designed to communicate algorithms, to executethem efficiently on a variety of different computers, and to aid in teaching themto students”. Although this book has not been geared to any specific universitysyllabus, the logical development of the exposition should permit its use in suchan environment. However, since no programming expertise is assumed, the book isalso suitable for home-study.It is time to take a fresh approach to the teaching of computer programming.This book breaks new ground in that direction. The concept of a variable (a termborrowed from mathematics, applied to analogue computers and then, inappropriately, to digital computers) has been replaced by the principle of value integrity:in Algol 68, every value is a constant. All the usual paraphernalia of pointers,statements and expressions is dispensed with. Instead, a whole new sublanguage isprovided for understanding the nature of programming.This book covers the language as implemented by the DRA a68toc translator.Since the last edition, a new chapter on the Standard Prelude has been added,thereby bringing together all the references to that Prelude in the rest of the book.This edition is an interim edition describing the QAD transput provided with theAlgol68toC package.It has been a conscious aim of the author to reduce the amount of descriptionx
Prefacexito a minimum. It is advisable, therefore, that the text be read slowly, re-readinga point if it is not clear. This is particularly true for chapter 5 where the conceptof the name has been introduced rather carefully. The exercises are intended to beworked. Answers to all the exercises have been given except for those which areself-marking.A program written for use with the book can be found in the same directory asthis book.I should like to thank Wilhelm Klöke for bringing the Algol 68RS compiler to myattention and James Jones and Greg Nunan for their active help in the preparationof the QAD transput.In 35 years of programming, I have had many teachers and mentors, and I haveno doubt that I have benefited from what they have told me, although now it isdifficult to pinpoint precisely which part of my understanding is due to which individual. Any errors in the book are my own. If any reader should feel that the bookcould be improved, I should be grateful if she would communicate her suggestionsto the publisher, so that in the event of another edition, I can incorporate those Ifeel are appropriate (she includes he).Sian LeitchInbhir NisMarch 2003ContentsIndex
Chapter 1IntroductionAlgol 68 is a high-level, general-purpose programming language ideally suited tomodern operating systems. This book will teach you Algol 68 plus the necessary development skills to enable you to write substantial programs which can be executedfrom the command line.In principle, you can solve any computable problem with Algol 68. You canwrite programs which perform word processing, perform complicated calculationswith matrices, design graphs or bridges, process pictures, predict the weather, andso on. Or you can write simple programs which count the number of words in a fileor list a file with line numbers.Algol 68 is a powerful language. There are many constructs which enable youto manipulate complicated data structures with ease, and yet it is all easy to understand because one of the guiding principles of Algol 68 was that it was designedto be orthogonal. This means that the language is based on a few independentideas which are developed and applied with generality. The language was designedin such a way that it is impossible to write ambiguous programs. The design is alsodifficult to describe until it has been fully described, which means that some concepts have to be introduced in a superficial manner, but later reading will deepenyour understanding.You need to have a thorough grasp of the basic ideas if you are going to writepowerful programs in Algol 68: these ideas unfold in the first five chapters. Thechapters should be read in order, but chapter 5 is a watershed—it forms the basis ofmuch of the computer programming performed in the world today. Its ideas shouldbe mastered before continuing.Chapter 10 draws together all the various references to grammatical points andclarifies the limitations of the language—you will need to know these if you want tosqueeze the last ounce of power out of the language. Chapters 11 and 12 deal withadvanced topics which should not be touched until you have mastered preceding material. Chapter 13 describes the standard prelude which, besides providing meansof determining the characteristics of an Algol 68 implementation, also provides thetransput facilities whose power are characteristic of Algol 68.In this chapter, some aspects of Algol 68 grammar are described. Don’t worryif they seem confusing; all will become clear later in the book. It also coversdenotations and the identity declaration, the latter having crucial importance inthe language.1
Chapter 1. Introduction1.12What you will needThe language described in this book is that made available by the a68toc Algol 68compiler developed by the Defence Research Agency (see section 1.9 for more information about what a compiler does). It implements almost all of the languageknown as Algol 68, and extends that language in minor respects. To run the programs described in this book you will need a microcomputer with a Linux system.The source package will occupy 12Mb on the hard disk while the binary packagewill also need 9Mb of space on the hard disk. The source package may be deletedonce the binary package has been installed.The book expects you to be familiar with the usual commands for manipulatingfiles. You will need to know how to use an editor for
as a suitable tool in which to write the Unix operating system, Pascal was designed specifically to teach computer programming to university students and Fortran was designed to help engineers perform calculations. Where a programming language is used for its design purpose, it performs that purpose admirably. Fortran, when
'Revised Report on the Algorithmic Language ALGOL 60'. In general, these defects are of little consequence, but have resulted in unnecessary variations in the various implementations of ALGOL 60 thus impairing the portability of ALGOL 60 algorithms. The body responsible for ALGOL 60,
As with the preliminary ALGOL report, three different levels of language are recognized, namely a Reference Language, a Publication Language and several Hardware Representations. I Preliminary report-International Algebraic Language, Comm. A8soc. Camp. Mach. 1, No. 12 (1958),8. 2 Report on the Algorithmic Language ALGOL by the ACM
2 Report on the Algorithmic Language Algol by the ACM Committee on Programming Languages and the GAMM Committee on Programming, edited by A. J. Perlis and K. Samelson, Numerische Mathematik Bd. 1, S. 41-60 (1959).
4 History developed by Niklaus Wirth in the early 1970s developed for teaching programming with a general-purpose, high-level language named for Blaise Pascal, French mathematician and pioneer in computer development Algol-based Algol-60 is a subset of Pascal block stru
4 History developed by Niklaus Wirth in the early 1970s developed for teaching programming with a general-purpose, high-level language named for Blaise Pascal, French mathematician and pioneer in computer development Algol-based Algol-60 is a subset of Pascal block stru
CSC 309 – OOP in C Prof. Massimo Di Pierro History of C 1960: Many computer languages where invented (including Algol) 1970: Ken Thompson invented the B language (from Algol) Norwegian Air Force invented Simula and the concept of class 1971: Dennis Ritchie (Bell Labs) invented the C as an extension of the B language.
ALGOL 68 Revised Report 7 Since the publication of the Original Report, much discussion has taken place in the Working Group concerning the further development of the language. This has been influenced by the experience of many people who saw disadvantages in the original proposals and suggested revised or extended features.
[3] P. Naur (Editor), Revised Report on the Algorithmic Language ALGOL 60, Regnecentralen, Copenhagen, 1962, and elsewhere. [4] P. Naur, Proposals for a new language, AB.18.3.9, October 1964. [5] P. Naur, Proposals for introduction on aims, WG 2.1 Working Paper, October 1965. [6] G. Seegmueller, A proposal four a basis for a Report on a Successor
