PL/0

To all interested in this little treasure, I transcribed the source code of the PL/0 compiler from the book "Algorithms + Data Structures = Programs", published by Nicklaus Wirth in 1976, and adapted it to run in Free Pascal.

You can find the sources here: https://github.com/dtoffe/adsp-pl0

Some interesting notes:

- The original compiler does not define nor implements "read" or "write" statements, as was the norm in later PL/0 implementations. - The source code in the book corresponds to the implementation in the CDC 6000 that Wirth had at hand back then. That machine used the CDC Display Code:

https://en.wikipedia.org/wiki/CDC_display_code

a 6 bit character code from before the ASCII times. Among its 64 characters, it includes single symbols for "<>", "<=" and ">=". In an attempt to change the code the least to make it run as original as possible, I changed those three character to #, { and }, as the symbols in the lexer are implemented using an array of char (only the assignment is treated as a special case).

- The interpreter printing out the values of every variable assignment, noted by another reader of this post, was a way of getting some information of the running program, since the compiler does not implement read or write statements.

- Following the compiler code, full of single letter variable names, was not the most exciting part.

I have always disliked the := as assignment operator convention. In these declarative languages, assignment is done frequently. There is little cognitive load to using '=' as assignment, although perhaps a bit jarring for math folk.

<- is somewhat better, but, again, for such a common operation, a single character is just more convenient. Sure, we could have editors that turn "=" into := or <- but now we're getting too fancy especially for something pedagogical.

I also don't mind the -> for C pointers; and certainly don't mind the <= >= or even == conventions (although at least today's compilers warn when they see "if (a=b) ...".

Ultimately, humans won't be writing code anymore anyway ( ;-) ?) so maybe the issue is entirely moot.

"The publisher of Wirth's books (Addison-Wesley) has decided to phase out all his books, but Wirth has published revised editions of his book beginning in 2004."

That is sad, but the revised editions seem to be published online.

Interesting. The article states "The compiler prints the value as a given variable changes." -- surely it means the program does, and not the compiler?

The older I get the more I prefer Wirth syntax languages with keyworded blocks and := assignment operators, and regret how C block syntax and =/== took over.

I learned first on Pascal & Modula-2 and only picked up C later and while I appreciated its terse minimalism at the time and through the 90s, I actually don't at all now. I find it less readable.

Any relation to PL/I?

Why were forward slashes so popular in computing product names in the 70s and 80s?

PL/0, PS/2, CP/M, etc.

"The publisher of Wirth's books (Addison-Wesley) has decided to phase out all his books, but Wirth has published revised editions of his book beginning in 2004."

That is sad, but the revised editions seem to be published online.

Any relation to PL/I?

The older I get the more I prefer Wirth syntax languages with keyworded blocks and := assignment operators, and regret how C block syntax and =/== took over.

I learned first on Pascal & Modula-2 and only picked up C later and while I appreciated its terse minimalism at the time and through the 90s, I actually don't at all now. I find it less readable.

You can find the sources here: https://github.com/dtoffe/adsp-pl0

Some interesting notes:

https://en.wikipedia.org/wiki/CDC_display_code

- Following the compiler code, full of single letter variable names, was not the most exciting part.

Interesting. The article states "The compiler prints the value as a given variable changes." -- surely it means the program does, and not the compiler?

I take it to mean that the compiler inserts variable print code on variable modifications.

It might be more precisely stated something like "The language's semantics require that when a variable changes value, that change includes the side-effect of printing the new value."

The compiler produces p-code to be interpreted by an interpreter, so it is the interpreter that prints the value.

Why were forward slashes so popular in computing product names in the 70s and 80s?

PL/0, PS/2, CP/M, etc.

I also don't mind the -> for C pointers; and certainly don't mind the <= >= or even == conventions (although at least today's compilers warn when they see "if (a=b) ...".

Ultimately, humans won't be writing code anymore anyway ( ;-) ?) so maybe the issue is entirely moot.

I think it started with IBM: System/360 and /370, PS/2, OS/2, PL/I

And then Gary Kildall also seemed to like it with CP/M and PL/M, but those were after IBM had used it and I'd guess Gary was just copying IBM.

Between just those two influences you cover a huge portion of the mainframe and micro computer worlds during the 60s-80s

It was a convention to denote a variation or version. Not sure how the trend started though.

Maybe referencing the reputation of IBM System/360?

Using '=' for both assignment and comparison is awkward when parsing incomplete code. Consider e.g.:

  j = 5;

The user starts writing (<|> is the cursor position):

  i = <|>
  j = 5;

This is a valid expression (i is a boolean). But the user probably intends to finish writing something like:

  i = 0;
  j = 5;

So in the intermediate state we would like to emit a single warning about an incomplete statement. But since it is valid as written, we instead end up warning about e.g. j being unbound.

> I have always disliked the := as assignment operator convention. In these declarative languages, assignment is done frequently.

> I also don't mind the -> for C pointers

Mmm. These two opinions should be contradictory if held on principle as opposed being held out of impression.

    it = next(it);
    if ((*it)->node->op == EQ) ...

vs.

    it := next(it);
    if it.node.op = EQ ...

Eh. I don't really mind either of those except for the stupid parens after the "if" in the first case.

Technically, if you don't make assignment an expression, you can even get away with using "=" for both. And "->" exists only because structs originally weren't really typechecked; you could take any pointer and just do "->struct_field" at it, and the compiler would auto-cast.

I take it to mean that the compiler inserts variable print code on variable modifications.

I think it started with IBM: System/360 and /370, PS/2, OS/2, PL/I

And then Gary Kildall also seemed to like it with CP/M and PL/M, but those were after IBM had used it and I'd guess Gary was just copying IBM.

Between just those two influences you cover a huge portion of the mainframe and micro computer worlds during the 60s-80s

The compiler produces p-code to be interpreted by an interpreter, so it is the interpreter that prints the value.

Maybe referencing the reputation of IBM System/360?

> I have always disliked the := as assignment operator convention. In these declarative languages, assignment is done frequently.

> I also don't mind the -> for C pointers

Mmm. These two opinions should be contradictory if held on principle as opposed being held out of impression.

    it = next(it);
    if ((*it)->node->op == EQ) ...

vs.

    it := next(it);
    if it.node.op = EQ ...

Eh. I don't really mind either of those except for the stupid parens after the "if" in the first case.

It might be more precisely stated something like "The language's semantics require that when a variable changes value, that change includes the side-effect of printing the new value."

It was a convention to denote a variation or version. Not sure how the trend started though.

Using '=' for both assignment and comparison is awkward when parsing incomplete code. Consider e.g.:

  j = 5;

The user starts writing (<|> is the cursor position):

  i = <|>
  j = 5;

This is a valid expression (i is a boolean). But the user probably intends to finish writing something like:

  i = 0;
  j = 5;

So in the intermediate state we would like to emit a single warning about an incomplete statement. But since it is valid as written, we instead end up warning about e.g. j being unbound.

From Wikipedia, the free encyclopedia

This article is about the programming language introduced by Niklaus Wirth. For the subset of a programming language from IBM, see PL/I.

PL/0 is a programming language, intended as an educational programming language, that is similar to but much simpler than Pascal, a general-purpose programming language. It serves as an example of how to construct a compiler. It was originally introduced in the book, Algorithms + Data Structures = Programs, by Niklaus Wirth in 1976. It features quite limited language constructs: there are no real numbers, very few basic arithmetic operations and no control-flow constructs other than "if" and "while" blocks. While these limitations make writing real applications in this language impractical, it helps the compiler remain compact and simple.

All constants and variables used must be declared explicitly.

The only data types are integers. The only operators are arithmetic and comparison operators. There is an odd function that tests whether the argument is odd.

In the original implementation presented by Wirth, there are no input and output routines. The compiler prints the value as a given variable changes. So the program:

var i, s; begin i := 0; s := 0; while i < 5 do begin i := i + 1; s := s + i * i end end.

gives the output:

However, most implementations have single input and single output routines.

Flow control structures are [if-then](https://en.wikipedia.org/wiki/Conditional_\(computer_programming\) "Conditional (computer programming)") and [while-do](https://en.wikipedia.org/wiki/While_loop "While loop") constructs and user-defined procedures. Procedures cannot accept parameters.

The following is the syntax rules of the model language defined in EBNF:

program = block "." ;

block = [ "const" ident "=" number {"," ident "=" number} ";"] [ "var" ident {"," ident} ";"] { "procedure" ident ";" block ";" } statement ;

statement = [ ident ":=" expression | "call" ident | "?" ident | "!" expression | "begin" statement {";" statement } "end" | "if" condition "then" statement | "while" condition "do" statement ];

condition = "odd" expression | expression ("="|"#"|"<"|"<="|">"|">=") expression ;

expression = [ "+"|"-"] term { ("+"|"-") term};

term = factor {("*"|"/") factor};

factor = ident | number | "(" expression ")";

It is rather easy for students to write a recursive descent parser for such a simple syntax. Therefore, the PL/0 compiler is still widely used in courses on compiler construction throughout the world. Due to the lack of features in the original specification, students usually spend most of their time with extending the language and their compiler. They usually start with introducing REPEAT .. UNTIL and continue with more advanced features like parameter passing to procedures or data structures like arrays, strings or floating point numbers.

The main article on compilers honours PL/0[citation needed] for introducing several influential concepts (stepwise refinement, recursive descent parsing, EBNF, P-code, T-diagrams) to the field by educating students to use these concepts. Over the last 3 decades, most university courses on compiler construction that used PL/0 have followed Wirth strictly in employing these techniques (see references below). Some years ago university courses deviated from the course set by Wirth with the replacement of the classical recursive descent parsing technique by a (nonetheless classical) Unix-like approach of employing lex and yacc. Only recently an implementation (PL/0 Language Tools) along this way has also combined modern concepts like object-orientation and design patterns with a modern scripting language (Python), allowing students to consume the source text of the implementation in a contemporary programming style.

Compiler construction

[edit]

In December 1976, Wirth wrote a small booklet about compiler construction, containing the full source code of the PL/0 compiler. The syntax rules above were taken from this first edition of Wirth's book Compilerbau.[1] In later editions of this book (under the influence of his ongoing research) Wirth changed the syntax of PL/0. He changed the spelling of keywords like const and procedure to uppercase. This change made PL/0 resemble Modula-2 more closely. At the same time, Wirth's friend and collaborator C. A. R. Hoare was working on his influential communicating sequential processes concept, which used the exclamation mark ! and the question mark ? to denote communication primitives. Wirth added both symbols to the PL/0 language, but he did not mention their semantics in the book.

This program[2] outputs the squares of numbers from 1 to 10. Most courses in compiler construction today have replaced the exclamation mark with the WriteLn procedure.

VAR x, squ;

PROCEDURE square; BEGIN squ:= x * x END;

BEGIN x := 1; WHILE x <= 10 DO BEGIN CALL square; ! squ; x := x + 1 END END.

This following program prints the prime numbers from 1 to 100. The write statement corresponds to '!' statement in the EBNF syntax above.

const max = 100; var arg, ret;

procedure isprime; var i; begin ret := 1; i := 2; while i < arg do begin if arg / i * i = arg then begin ret := 0; i := arg end; i := i + 1 end end;

procedure primes; begin arg := 2; while arg < max do begin call isprime; if ret = 1 then write arg; arg := arg + 1 end end;

call primes .

The following example was taken from the second edition of Wirth's book Compilerbau,[1] which appeared in 1986 in Germany.

VAR x, y, z, q, r, n, f;

PROCEDURE multiply; VAR a, b; BEGIN a := x; b := y; z := 0; WHILE b > 0 DO BEGIN IF ODD b THEN z := z + a; a := 2 * a; b := b / 2 END END;

PROCEDURE divide; VAR w; BEGIN r := x; q := 0; w := y; WHILE w <= r DO w := 2 * w; WHILE w > y DO BEGIN q := 2 * q; w := w / 2; IF w <= r THEN BEGIN r := r - w; q := q + 1 END END END;

PROCEDURE gcd; VAR f, g; BEGIN f := x; g := y; WHILE f # g DO BEGIN IF f < g THEN g := g - f; IF g < f THEN f := f - g END; z := f END;

PROCEDURE fact; BEGIN IF n > 1 THEN BEGIN f := n * f; n := n - 1; CALL fact END END;

BEGIN ?x; ?y; CALL multiply; !z; ?x; ?y; CALL divide; !q; !r; ?x; ?y; CALL gcd; !z; ?n; f := 1; CALL fact; !f END.

In the third and last edition of his book on compiler construction, Wirth replaced PL/0 with Oberon-0. The language Oberon-0 is much more complex than PL/0. For example, Oberon-0 offers arrays, records, type declarations and procedure parameters. The publisher of Wirth's books (Addison-Wesley) has decided to phase out all his books, but Wirth has published revised editions of his book beginning in 2004.[3] As of August 2017, the most recent revision available is from May 2017.[4][5]

^ a b Wirth, 1986
^ PL/0 Archived 2012-02-21 at the Wayback Machine
^ The revised third edition Archived 2017-02-17 at the Wayback Machine (2005) of Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6 has never seen the printing press, but it is available online.
^ Wirth, Niklaus (2017-05-28). "Compiler Construction". Retrieved 2017-08-25.
^ Wirth, Niklaus (2017-08-18). "news.txt". Archived from the original on 2017-08-25. Retrieved 2017-08-25.

Liffick, Blaise W., Ed (1979), The Byte Book of Pascal, ISBN 0-07-037823-1
Wirth, Niklaus (1975), Algorithms + Data Structures = Programs, ISBN 0-13-022418-9
Wirth, Niklaus (1986), Compilerbau, B.G. Teubner, Stuttgart ISBN 3-519-32338-9
The compiler (.pas file) from the first edition of the Compilerbau book, written in Pascal
Another copy of the compiler at Pascal for small machines site
The interpreter from "Algorithms + Data Structures = Programs" book, written in Pascal
Development of a PL/0 style compiler Archived 2017-02-18 at the Wayback Machine based on 'Compiler construction' written in Mocka (Modula-2 for Linux)
A paper explaining the use of PL/0 at the University of Rochester
The homepage of the PL/0 reference book, "Algorithms + Data Structures = Programs" [1]
https://sourceforge.net/projects/pl0-compiler (written in C/C++, uses QT framework)
https://modernc.org/pl0 (written in Go, runs in terminal, cross platform)
https://github.com/dodobyte/plzero (a very small compiler produces windows executable)
https://github.com/hindermath/TinyPl0 (modern port of PL/0 with Agentic-AI to .Net10/C# 14)
https://github.com/MarcRochkind/pl0compiler (compiler for IBM 701 written in C; generates 701 assembler)
Category:PL/0 Tasks implemented in PL/0 on rosettacode.org

Hacker Times

Hacker Times

Discussion

Discussion

Compiler construction