11

In Algol 68, is it legal to say this?

proc even = (int x) bool: (x = 0 | true | odd(x – 1));

proc odd = (int x) bool: (x = 0 | false | even(x – 1));

Forward references in structures are used in the Revised Report (10.3.5), but this works because, I think, the syntax “expands” the right-hand side of a mode-declaration when the mode's name is applied, not when it is declared.

However, neither the report nor Lindsey and van der Meulen's Informal Introduction mention or use forward references of procedures (as far as I can tell). The way the syntax works doesn't seem to allow “delaying” the parsing of a routine-text, so I don't see how it could permit referring to something before it's declared.

2
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Chenmunka
    Commented Aug 1, 2022 at 15:26
  • 1
    Beginner question from a padawan. I assumed Algol must be an interpreter because forward references seem to be a problem. In a compiler, the indirect recursive reference would just generate a procedure call, and the reference would be resolved by the link editor. But someone referred to the algol "compiler." Why are forward references a problem? Why do they have to be resolved at compile time? Commented 2 days ago

6 Answers 6

7

I am by no means knowledgeable about Algol 68 - but that won't stop me. I wonder if the issue is a misunderstanding of "elaboration" when an Algol 68 program runs vs. how that is represented by a w-Grammar. In particular, I'm keying off your sentence:

The way the syntax works doesn't seem to allow “delaying” the parsing of a routine-text.

These two paragraphs are from "A Practical Guide To Algol 68" (Frank G. Pagan, 1976), page 101, in a section on "Procedures Without Parameters":

enter image description here

enter image description here

To me these sentences make it clear that a procedure declaration comes into effect when it is elaborated (i.e., it is reached in program flow terms) and then you can use it. The reference to "global identifiers which appear in a routine text" refers to both routines and "ordinary" (other) identifiers here, as this whole discussion is about a declaration of a routine which is just like declarations of other things: in this case a unit is given a proc name.

I don't know how this translates to the two-level grammar, but I think perhaps that considering the grammar as about generating valid Algol 68 programs as opposed to recognizing valid Algol 68 programs may help ...

Update: Check out the great article "A History Of ALGOL 68" (Lindsey, 1996) - easy to read (though long), and nicely chatty (even gossipy!). If you scroll down to page 38 of the PDF (page number 64 in the document) he has a very useful comparison of the W-grammar syntax to PROLOG! And points out the backtracking of PROLOG! And this might be the way to get to understanding how the grammar can define valid programs where all the identifiers are properly declared - even after being mentioned in text. See the discussion of "blind alleys", which is more extensive in the next section 2.5.1.2 Predicates. And that takes you to 2.5.1.3 Context Conditions vs NESTs which is where your question about how this works in the grammar is (i.e., might be?) finally answered. With the caveat that

The tools required to do this are still complex, but once one has understood them they hardly intrude. And their formality ensures that it is always possible to work through any particular case and to see whether and why it is or is not allowed.

Or so he says. A bit later describing the way in which "infinite modes" are removed from the language he says

It is, admittedly, also hard work to read (in spite of copious pragmatics), but the Report is written so that it does not obtrude, and the naive reader need hardly be aware of it.

So it is clear that one approach, suggested by one of the main language designers, is to declare yourself resolutely naive and thus, with respect to all this complexity, you need hardly be aware of it! What a relief!

10
  • 1
    I agree, but that skates over the 'how'. In the example, suppose we have z := f rather than z := 3. We may not know the mode of f when encountering this. Obviously a multi-pass compiler can figure it out...
    – dave
    Commented Jul 31, 2022 at 21:28
  • I'm not sure that a grammar (expressed in any formalism) could generate a valid forward reference without keeping track of the as-yet undeclared identifiers. The unrestricted nature of w-grammars would make this possible, but I don't think the Algol 68 revised report does it.
    – texdr.aft
    Commented Jul 31, 2022 at 21:50
  • 1
    @another-dave - the question is about the Algol-68 grammar specified in the "Revised Report". The motivation for the grammar, described in 1. Language and metalanguage / 1.1 The method of description / 1.1.1 Introduction (and other commentary on the Algol 68 report) makes it clear that the grammar is a generator of a language - in particular, it generates all valid production trees and assigns a meaning to each such tree. The OP is asking for "how" the grammar allows mutual references. That's a different "how" than your "how" which is how a compiler can use (or not use) the ...
    – davidbak
    Commented Jul 31, 2022 at 22:05
  • ... grammar to parse a valid string in the "representation language". (Remember, grammars can be used to generate as well as recognize (i.e., "parse") - any may be more suited for one purpose than the other, depending on your tooling - in particular - nobody at all would attempt to parse a language using a two-level grammar.) And I readily admit my answer doesn't answer either "how" - as my last sentence states.
    – davidbak
    Commented Jul 31, 2022 at 22:06
  • 1
    I came back to this after dave's post and you're right. I was misunderstanding the generative nature of the grammar as employed in the report. I'm going to write an answer going into more detail on how I was wrong, and then I'll accept yours.
    – texdr.aft
    Commented Jun 9 at 22:44
10

RosettaCode provides the following example of mutually-recursive procedures in Algol-68:

PROC (INT)INT m; # ONLY required for ELLA ALGOL 68RS - an official subset OF full ALGOL 68 #
 
PROC f = (INT n)INT:
  IF n = 0 THEN 1
  ELSE n - m(f(n-1)) FI;
 
m := (INT n)INT:
  IF n = 0 THEN 0
  ELSE n - f(m(n-1)) FI;
 
main:
(
  FOR i FROM 0 TO 19 DO
    print(whole(f(i),-3))
  OD;
  new line(stand out);
  FOR i FROM 0 TO 19 DO
    print(whole(m(i),-3))
  OD;
  new line(stand out)
)

That is, the standard did not require a forward-declaration, but some implementation did for convenience of the implementor.

In the Informal introduction, we read

4.2.2.3. Recursion

Suppose, now, that a routine happens to contain a call on itself (either directly, or via a chain of calls on other routines which eventually calls the same one again). Are there any problems? In some programming languages there may be, but not in this one. It all works out normally, just like you would expect.

And later, in Appendix 4.3,

The following restrictions arise because of the requirement for one-pass compilation: All declarations of indicators (i.e. of identifiers, operators and mode indications) must precede the first applied occurrences (3.2.3) which identify them. This is normally good programming practice anyway (moreover, see 3.2.3.E7) and the only case where you might regret the restriction is that of mutually recursive pairs of procedures (you would have to declare one of them as a proc variable in the sublanguage)...

Therefore, the standard did indeed allow referring to routines which are not yet declared, in routine-texts, when using a full compiler, and a restriction that declarations must precede occurrences is specific to one-pass compilers.

8
  • I read that as saying “you need to declare procedures before calling them in standard Algol 68”
    – texdr.aft
    Commented Jul 31, 2022 at 5:37
  • @texdr.aft Please follow the link for the full context of that "ONLY required" comment.
    – Leo B.
    Commented Jul 31, 2022 at 5:39
  • @texdr.aft - all of Appendix 4 is specifically about the (standard) sublanguage Algol 68S.
    – dave
    Commented Jul 31, 2022 at 12:46
  • 2
    The declaration PROC (INT) INT m; is not actually a forward declaration. It is a complete declaration of a variable of mode REF PROC, to which a routine is later assigned. The equivalent in C would be int (*m)(int); and not int m(int);.
    – dave
    Commented Jul 31, 2022 at 13:14
  • 1
    If you omit that declaration, the code is invalid in Algol68 (no declaration of 'm'). It then requires a different declaration -- an identity-declaration for 'm', in place of the assignation -- which is not shown. That is, the example demonstrates only the workaround of using a ref-to-proc; it implies but does not show the case where the workaround is not required.
    – dave
    Commented Jul 31, 2022 at 17:59
6

Not an answer, but note that Algol 60 allowed use before declaration. I take this as a strong hint that Algol 68 would also do so.

I ran this code on the KDF9 Whetstone Algol system.

'begin'

'boolean' 'procedure' odd(n);
  'value' n; 'integer' n;
  'begin'
    odd := 'if' n = 0 'then' 'false' 'else' even(n-1)
  'end';

'boolean' 'procedure' even(n);
  'value' n; 'integer' n;
  'begin'
    even := 'if' n = 0 'then' 'true' 'else' odd(n-1)
  'end';

write boolean(30, odd(3))

'end'

This just validates that the scope of an identifier is the entire block in which it is declared (and any nested blocks, of course).

3
  • What is the significance of 30 in the write boolean call?
    – texdr.aft
    Commented Aug 1, 2022 at 2:03
  • 1
    @texdr.aft - it's a semi-virtual 'device number'. 3n mapped to the line printer, although on the multi-access system Eldon2, and in the modern emulator, it is treated as console output. I call it semi-virtual since as far as I recall, you could have multiple 3n streams that would be separately spooled to the line printer, though maybe not under Eldon.
    – dave
    Commented Aug 1, 2022 at 12:14
  • 1
    The I/O routines are not a feature of Algol 60; every implementor did his own thing.
    – dave
    Commented Aug 1, 2022 at 12:19
3

Algol 68R was the first Algol 68 implementation, released before the Revised Report. The "R" is because it was a restricted subset of the language, largely to allow a single-pass compiler to be written.

Among the restrictions were the requirement for all identifiers to be declared ("specified" in Algol jargon) before use. It would seem, thereby, that full Algol 68 did not impose this requirement. Your example, in slightly improved form,

PROC even = (INT number) BOOL: ( number = 0 | TRUE | odd (ABS (number - 1)));
PROC odd = (INT number) BOOL: ( number = 0 | FALSE | even (ABS (number - 1)));

Needs to be re-written for Algol 68R as:

PROC (INT) BOOL odd;
PROC even = (INT number) BOOL : ( number = 0 | TRUE | odd (ABS (number - 1)));
odd := (INT number) BOOL : ( number = 0 | FALSE | even (ABS (number - 1)));

To allow mutually recursive declarations of types ("modes") in 68R, the MODE keyword must be used to create "stub" declarations:

MODE B;
MODE A = STRUCT (REF B b);
MODE B = [1:10] REF A;

I did a fair amount of programming in 68R at college in 1981-83, and the need for forward declarations was not a significant problem.

6
  • 1
    It's too bad specifications for more languages don't recognize the value of limited-subset implementations, with a proviso that a conforming limited-subset implementation may reject constructs that would be difficult to support, but must correctly support constructs it does not reject. C would have been a much more useful language for 8-bit computers if features like recursion weren't seen as mandatory. On a 6502, incrementing a statically-allocated 8-bit value stored would take 2 or 3 bytes of code, and 5 or 6 cycles. Using an automatic-duration object in a re-entrant function...
    – supercat
    Commented Aug 1, 2022 at 20:34
  • ...would increase the typical cost to 9 bytes of code with an execution time of 17 cycles. While it's possible for a 6502 C implementations to generate code that supports recursion, having it supported without regard for whether programs need it is a gross violation of the "only pay for what you use" principle.
    – supercat
    Commented Aug 1, 2022 at 20:40
  • As you said, the restrictions of Algol-68R were mostly needed to permit a one-pass compiler. Those particular restrictions (but not all others) ended up in the sublanguage of the Revised Report.
    – dave
    Commented Aug 1, 2022 at 22:25
  • 2
    But I think the "R" in Algol-68R is for "RSRE" (Royal Signals and Radar Establishment), not "Restricted". See other contemporary examples, such as -68C, for "Cambridge".
    – dave
    Commented Aug 1, 2022 at 22:26
  • 1
    Incidentally: Kernighan & Ritchie's book on C, at 228 pages (original paperback) has been considered an example of concision in the genre. The ALGOL 68-R User's Guide by Woodward & Bond, which is pitched at the same level of audience, weighs in at 99 pages. And they say ALGOL 68 was "complicated" :-)
    – dave
    Commented Aug 1, 2022 at 22:37
3

It turns out that davidbak's answer was correct; I was misunderstanding the generative nature of the grammar. The answer to the title is yes.

The Revised Report is quite clear (1.1.1b) on the purpose of the syntax:

The syntax is a mechanism whereby all the constructs of the language may be produced. … A "program in the strict language" is a production tree for the notion 'program'.

Of course, traditional BNF-style grammars can be used to generate sentences of a language, but they have the convenient property of being context free, so that they can easily be used for parsing (recovering the steps needed to generate the sentence). On the other hand, Algol 68's formalism is decidedly not context free* and is basically useless for syntactic analysis.

For example, many of Algol 68's productions are annotated with things like “MOID” and “NEST” that roughly correspond to an interpreter's concepts of “the expected result type of this expression” and “the lexical environment”. These are static semantics of the language: You can determine the expected type and the applicable lexical environment based solely on the program text, without executing anything. Thus they are part of the syntax in the Algol 68 report.

Here is a fragment of the derivation for the even/odd example. I was originally going to do the whole thing, but it became too annoying.

  • {particular program : strong void NEST ENCLOSED clause}
  • strong void new closed clause {NESTnew; ENCLOSEDclosed}
  • {SOID NEST closed clause : SOID NEST serial clause defining LAYER PACK}
  • strong void new serial clause defining LAYER PACK
  • {SOID NEST serial clause defining new PROPSETY: SOID NEST new PROPSETY series with PROPSETY}
  • {strong void new PROPSETY series with PROPSETYNEST has disappeared; susbsequent NESTs are unrelated}
  • {→ strong void new DECSETY1 LABSETY1 series with DECSETY1 LABSETY1}
  • {→ strong void new DECS1 DECSETY1 LABSETY1 series with DECS1 DECSETY1 LABSETY1}
  • {SOID NEST series with PROPSETY : where (PROPSETY) is (DECS DECSETY LABSETY), NEST declaration of DECS, “;”, SOID NEST series with DECSETY LABSETY}
  • where (DECS1 DECSETY1 LABSETY1) is (DECS1 DECSETY1 LABSETY1), NEST declaration of DECS1, “;”, SOID NEST series with DECSETY1 LABSETY1
  • {→ NEST declaration of DECS1,;, SOID NEST series with DECSETY1 LABSETY1}
    • {NEST declaration of DECS : NEST COMMON declaration of DECS}
    • NEST MODINE identity declaration of DECS {COMMONMODINE}
    • NEST routine identity declaration of DECS {COMMONMODINE}
    • {NEST MODINE identity declaration of DECS : formal MODINE NEST declarer, NEST MODINE identity joined definition of DECS}
    • {VICTAL routine NEST declarer :proc”}
    • {“proc, NEST routine identity joined definition of DECS}
    • {NEST COMMON joined definition of PROPS PROP : NEST COMMON joined definition of PROPS,,, NEST COMMON joined definition of PROP}
      • NEST routine identity joined definition of PROPS,,, NEST routine identity joined definition of PROP
      • {→ NEST routine identity definition of [PROP1],,, NEST routine identity definition of [PROP2]}
      • {→ NEST routine identity definition of [DEC1],,, NEST routine identity definition of [DEC2]}
      • {→ NEST routine identity definition of [MODE1 TAG1],,, NEST routine identity definition of [MODE2 TAG2]}
      • {→ NEST routine identity definition of [PROCEDURE1 TAG1],,, NEST routine identity definition of [PROCEDURE2 TAG2]}
      • {→ NEST routine identity definition of [procedure PARAMETY1 yielding MOID1 TAG1],,, NEST routine identity definition of [procedure PARAMETY2 yielding MOID2 TAG2]}
      • {→ NEST routine identity definition of [procedure with PARAMETERS1 yielding MOID1 TAG1],,, NEST routine identity definition of [procedure with PARAMETERS2 yielding MOID2 TAG2]}
      • {→ NEST routine identity definition of [procedure with PARAMETER1 yielding MOID1 TAG1],,, NEST routine identity definition of [procedure with PARAMETER2 yielding MOID2 TAG2]}
      • {→ NEST routine identity definition of [procedure with MODE1 parameter yielding MOID1 TAG1],,, NEST routine identity definition of [procedure with MODE2 parameter yielding MOID2 TAG2]}
      • {→ NEST routine identity definition of [procedure with integral parameter yielding MOID1 TAG1],,, NEST routine identity definition of [procedure with integral parameter yielding MOID2 TAG2]}
      • {→ NEST routine identity definition of [procedure with integral parameter yielding MOID1 TAG1],,, NEST routine identity definition of [procedure with integral parameter yielding MOID2 TAG2]}
      • {→ NEST routine identity definition of [procedure with integral parameter yielding MOID1 TAG1],,, NEST routine identity definition of [procedure with integral parameter yielding MOID2 TAG2]}
      • {→ NEST routine identity definition of [procedure with integral parameter yielding integral TAG1],,, NEST routine identity definition of [procedure with integral parameter yielding integral TAG2]}
      • {→ NEST routine identity definition of [procedure with integral parameter yielding integral [letter e letter v letter e letter n]],,, NEST routine identity definition of [procedure with integral parameter yielding integral [letter o letter d letter d]]}

You can see how this forces all the declarations into the environment simultaneously with the generation of the sentential form. Therefore the declarations can be ultimately “out of order”. This goes beyond procedures; operators can be used before their priority is declared.


* The best description of this kind of grammar that I know of is in Pagan's Formal Specification of Programming Languages, section 2.4. A very rough analogy is that it is like a context-free formalism with a macro preprocessor.

† This is a fairly obvious use of a context-sensitive formalism. Shockingly, however, when two-level grammars were adopted for Algol 68, they were used mainly for abbreviation and for enforcing small-scale context-sensitive constraints. See Lindsey's “A history of ALGOL 68”, section 2.5.1. Apparently, this (van Wijngaarden's “Orthogonal Design and Description of a Formal Language”, MR76) is the document that convinced the working group. Lindsey says it “really was unreadable” (2.5.5) and I'm inclined to agree.

1

I came back to this question after a couple of years, and I am surprised at the hesitancy in my earlier non-answer.

Yes, the standard allows a procedure to be called before its declaration.

(Assumption: Lindsey and van der Meulen's Informal Introduction accurately reflects the intent of the Revised Report. I think I am on safe ground there.)

Consider section 3.2.3, "Identification", in the Informal Introduction. This describes how an applied-identifier is correlated with a defining-identifer, as a search outward through the nested ranges and reaches of the source text.

In the odd/even example, the identifiers 'odd' and 'even' occur in the same reach. It is clear then that the applied-identifier 'odd' in the routine-text defining 'even' unambiguously refers to the defining-identifier 'odd' occurring later in the program.

Later on in the same section (p159 in the scan I am looking at), it is explicitly stated:

However, an applied-identifier need not necessarily come after its defining-identifier

Naturally, a multipass compiler is required in order to deal with this. In Barry Mailloux's PhD thesis establishing the implementability of Algol 68, compilation of the unrestricted language requires 4 passes, with identifiers being handled on the 2nd pass - the 1st being dedicated to finding mode indicants and priority declarations.

No specific mention is made of proc identifiers. This is unnecessary; all identifiers are treated the same way. It is, after all, the orthogonal Algol 68 we are discussing.

ADDENDUM:

It seems this ground was already covered in the comments which were abruptly 'moved to chat'. Those comments, now not immediately visible when reading the question, clarify that the intent was to ask how the grammar permitted that, not simply whether it did. Oh well, I'll leave this here as a minor contribution.

I have never mastered the two-level grammar of the Revised Report, and I get very confused with ortho, meta, and paranotions except on a benzene ring, but it seems to me that NESTs were invented for precisely this purpose. RR 7.2 "Identification in nests" gives the grammar for this. Naively, I take this to mean you can't decide what identifiers "mean" until you have seen the entire range.

3
  • 3
    If you're interested in pure W-grammars consider getting the excellent book Grammars For Programming Languages (Cleaveland, Uzgalis, 1977) (you'll see my review there at amazon). But see also descriptions of affix grammars. And thank you for the link to Mailoux's dissertation!
    – davidbak
    Commented Apr 30 at 4:55
  • @davidbak - As any fule kno, an applied-identifier need not necessarily come after its defining-identifier (C. H. Molesworth).
    – dave
    Commented Apr 30 at 22:32
  • dave - you kno: Molesworth was great!
    – davidbak
    Commented May 8 at 3:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .