Formalism in programming languages
Kenneth E. Iverson · Communications of the ACM · 1964
Boolean procedure exacno (arg, n); eeJnment exactly n occurrences of arg; exacno : = if -1 arg then (ifn~0 then true else false) else ifn =< 0 then false else exacno (arg, n--l)Boolean procedure minmax (arg, m, n); comment at least m but not more than n occurrences of arg; minmax : = if -~ arg then (ifm~O then true else false) else ifn =< 0 then false else minimax (arg, m--l, n--l)The following identities are evident from the above definitions : arbno (arg) = minno (arg, O) = maxno (arg, oo) = minmax (arg, O, ~) minno (arg, n) = minmax (arg, n, 0) maxno (arg, n) = minmax (arg, 0, n) exacno (arg, n) = minmax (arg, n, n) DISCUSSIONFirst Dijkstra objected to carrying the "side-effect" references g~ explicitly in the Boolean expressions.He pointed out that it was surely equivalent and a good deal cleaner to have the g's buried in the recognizers or called from the recognizers.Leavenworth agreed, but explained that his intent was to clarify the exposition.Cheatham: What comes out of the hind end of this thing?Leavenworth responded that anything could, depending on how one wrote his generators; at the moment, macros come out, not code.Cheatham pressed the point of what help FORTRAN gave in writing these arbitrary generators.Leavenworth indicated that the string-manipulative functions were written in FORTRAN.Abrahams: Could this method enable you to handle FORTRAN, ALGOL, COMIT, and LISP?Gorn: All those except LISP, which is not context-free.Brooker: What are your general views regarding the merits of doing the syntax analysis from the "top down" as against the "bottom up"?The speaker listed the main users of the two methods, but expressed no strong opinion about their relative merit.Irons: My analyzer is bottom-up and Warshall's is top-down, and I don't think there is any appreciable difference between them from the viewpoint of the difficulty of syntax specification.Irons went on to ask Leavenworth whether he could handle "really messy bnf languages" in which, for example, a whole tentative parse of a large string might be negated by its last character.The speaker felt that there was no inherent limitation in his system with respect to backup distance.Warshall agreed with Irons about the essential equivalence of the two analysis methods from the specifiers' viewpoint.He remarked that the bottom-up methods seemed to permit better handling of "ndrror recursion" (a situation in which each of two syntactic types has a formation with the other named as first component, and the obvious extension to n types naming each other cyclically).Abrahams: It seems to me that the transformation of a given syntax into your FORTRAN form is not a trivial job.The speaker agreed that the transformation from syntax into a compiler for the defined language was scarcely a mere automatic or transliterative one in his system.He did feel, however, that the transformation was easier than conventional methods.This provoked a good deal of audience reaction, mostly negative, best exemplified by: Graham: But then you have no "syntax processor"; you are the syntax processor!! Leavenworth: This is true, but you always have to do some preprocessing.Cheatham: Warshall has been putting in the syntax rules for a year and a half, and Irons did it three years ago.Perlis opened up a new area of discussion by asking why bnf should be used in the first place.He made specific reference to Floyd's method, as described in "A Descriptive Language for Symbol Manipulation" [J.ACM 8, 4 (Oct.196l)].Floyd remarked that he had developed his notation purely for descriptive purposes and was not completely certain that it would be entirely free of sequencing problems if used computationally.Evans said that he had built a processor from ALGOL to postfix using Floyd's method and had found it very useful as a basis for a computational method.It also appeared to be ideal for effective error diagnostics.