PAL(ID:336/pal002)

Pedagogic Algorithmic Language  


Pedagogic Algorithmic Language

Landin and Morris, MIT, after ISWIM. Originally written in LISP, later rewritten in BCPL by Richards.

Designed as a language for experimenting in programming language style, to enable students to:

"study linguistic constructs for the specification of algorithms, and students are expected to learn some of the interesting and important intellectual ideas which are relevant to programming languages. (Examples of such ideas are the application of a function to arguments, the "creation" of new variables and allocation of their storage, the updating of the value associated with a variable, etc.) PAL was designed to reveal clearly these various intellectual ideas, with a minimum of syntactic decoration and a maximum of semantic clarity. "

Multi-modal, with garbage-collection, could take various types of assignments and deifinitions, including extensibility and Lambda Calculus. Typeless, and had pointers. Was written in a Lambda-Delta Calculus, which was a refinement of the Lambda calculus

"The PAL language is a direct descendent of Peter Landin's ISWlM, although there are important differences, particularly in the imperatives. The first implementation of PAL was by Landin and James H. Morris, Jr., in LISP. The language they implemented was much closer to ISWIM than to PAL as it now exists. The present version of PAL was designed by Martin Richards along with Thomas J. Barkalow, Evans, Robert M. Graham, Morris and John M. Wozencraft. The implementation is the work of Richards and Barkalow. The intellectual effort of which PAL is one outgrowth owes much to Christopher Strachey."


People:
Related languages
ISWIM => PAL   by original creator Evolution of
PAL => CONNIVER   Incorporated some features of
PAL => Gedanken   Influence
PAL => GTL   Evolution of
PAL => McG   Influence
PAL => SASL   Partial subset of

References:
  • Evans, Arthur Jr "A Language for Teaching Programming Linguistics" view details Abstract: This paper describes PAL—a new computer language. Given the fact that new languages seem to appear in computer literature at the rate of several per month, it seems incumbent on one who creates a new language to justify having done so. In the present case, there are two important considerations: control and specification. Let us consider each of these in turn. By virtue of our having designed PAL, it is ours. There is no PAL Users Group or Committee of Vested Interests concerned with retaining upward compatibility with what was done last year (or last month). This doesn't mean we change the specifications of the language every few weeks (our students are, in a real sense, our Committee of Vested Interests), but it does mean we can make decisions on changes solely on technical grounds. More important, though, we can design the language to meet the criteria we think important. For example, the language almost demands interpretive execution. Since no one writes production programs in PAL we are able to put up with inefficiencies in the implementation that would otherwise be intolerable. Thus we have designed our own language so that we will have control over it. Extract: INTRODUCTION
    INTRODUCTION
    This paper describes PAL--a new computer language. Given the fact that new languages seem to appear in computer literature at the rate of several per month, it seems incumbent on one who creates a new language to justify having done so. In the present case, there are two important considerations: control and specification. Let us consider each of these in turn.

    By virtue of our having designed PAL, it is ours. There is no PAL Users Group or Committee of Vested Interests concerned with retaining upward compatibility with what was done last year (or last month). This doesn't mean we change the specifications of the language every few weeks (our students are, in a real sense, our Committee of Vested Interests), but it does mean we can make decisions on changes solely on technical grounds. More important, though, we can design the language to meet the criteria we think important. For example, the language almost demands interpretive execution. Since no one writes production programs in PAL we are able to put up with inefficiencies in the implementation that would otherwise be intolerable. Thus we have designed our own language so that we will have control over it.

    Control alone is not adequate to justify a language design effort--there must be more, and there is. The designer of a computer language has an obligation to describe it--that is, if he expects anyone other than himself and a few of his friends to use it. We felt that a language for student use must be completely and accurately specified. This leads directly to a problem currently attracting much attention in Computer Science research: formalizing the specification of the syntax and semantics of computer languages. The syntax part of the problem has been under fairly good control since about 1960, when John Backus and Peter Naur created what is now referred to as Backus-Naur Form. The semantics part of the problem, however, is very far from being under control. Indeed, it is currently the subject of research by many groups. While we by no means feel that we have solved the problem in the general case, we do feel that we can present to our students an honest formalization of PAL's semantics. Of course a large part of Our success in doing so is a result of our having chosen a fairly simple language to describe, and this reasoning is the second justification for our having produced a new language. An important design criterion in adding features to PAL has been that their formal specification be clean.

    Before proceeding with a discussion of PAL, it seems worthwhile to discuss briefly the use for which it is intended: as a pedagogical vehicle in an undergraduate subject called "Programming Linguistics". This subject is designed primarily for sophomores who anticipate a major professional interest in computer science, and has two objectives. The first is to study linguistic constructs for the specification of algorithms, and students are expected to learn some of the interesting and important intellectual ideas which are relevant to programming languages. (Examples of such ideas are the application of a function to arg.uments, the "creation" of new variables and allocation of their storage, the updating of the value associated with a variable, etc.) PAL was designed to reveal clearly these various intellectual ideas, with a minimum of syntactic decoration and a maximum of semantic clarity. The second objective of the subject is that the students improve their proficiency in computer programming. PAL is an adequately clean and powerful programming language that can readily be used by the students to perform fairly complex programming exercises as homework. As a final word, it should be remarked that students taking this subject have already had exposure to computer languages, either through experience or from an introductory subject.

    The world view of computation underlying the design of PAL may be summarized as follows: We regard computation as having to do with the manipulation of abstract objects. Thus we are led to consider a universe of discourse made up of such abstract objects. It should be clear that the nature of this universe of discourse is invariant with respect to the representation of these objects: The properties of the integers remain invariant regardless of whether they are represented as Arabic numerals or as Roman numerals. Of course, in communicating with computers or in writing programs, we are deeply concerned with the external representation of an abstract object rather than the abstract object itself. With this fact in mind then, we suggest the following:
    1. An algorithm is the specification of a transformation on abstract objects, expressed in terms of other transformations which are themselves sufficiently simple that they need no further specification.
    2. A programming language is a set of conventions for communicating algorithms.
    3. A program is an algorithm represented in a programming language.
    This point of view on the nature of computation influences the design and nature of the PAL language. It surely influences the way we choose to describe PAL. For example, we distinguish carefully between strings, which are abstract objects, and quotations which are the written representation of strings.
    One of the basic intellectual ideas illustrated in PAL is so important that we refer to it by name: the Principle of Referential Transparency. This means that any subexpression may be replaced by any other expression, providing they both denote the same value. (We choose to ignore for the moment the problem of side effects. Clearly, the principledoes not hold if the evaluation of one of the expressions produces side effects different from those produced by the evaluation of the other.)
    [...]
    As a final preliminary to discussing the details of PAL, it is worth mentioning a few of the more important points in which it differs from other languages. The PAL compiler knows nothing whatsoever about types: the type of a variable is known only at run-time. Stated differently, the type is associated with the value and not with the variable. Since there is complete type checking, it therefore follows that the running system must be interpretive. For example, consider the application of the value of a variable to some argument. The variable must denote a value which is something which can properly be applied. It may be a basic function built into PAL, a function defined by the programmer, or (as we will see later) a tuple. In any case, though, it is necessary that the argument be checked to insure that it is an appropriate one. For example, a function defined by the programmer to have three arguments cannot be applied other than to a three-tuple.

    As suggested by the last sentence of the previous paragraph, it is the case that all functions in PAL are monadic. This means that each function is applied to only a single argument. Since it is obviously necessary to have functions of "several arguments", the convention is that such a function is to be applied to a tuple. An n-tuple is a constructed object with n components. Transformationally, an n-tuple behaves as function on integers, and may be applied to an integer between one and n to select the relevant component. Thus, a "function of three arguments" is one which is properly applied to a three-tuple. For convenience of discourse, though, we will frequently refer to "functions of n arguments" in what follows, tolerating the abuse of language.

    A final important difference between PAL and most other computer languages has to do with sharing. Two variables are said to share if updating one of them (as, with an assignment statement) causes the value of the other to be changed also. (Equivalently, the two variables occupy the same memory location.) For example, suppose that P denotes some 5-tuple and that i denotes a positive integer less than six. Then the declaration
    let w = P (i)
    causes w to share with the i th component of P. Thus the effect achieved in Fortran at compile time with EQUIVALENCE statements is available dynamically in PAL.
    Extract: The PAL Language
    The PAL Language
    There are two important subsets of PAL: the applicative subset and the imperative subset. The applicative subset has to do with the application of functions to arguments. Using this part of PAL only, it is possible to write arbitrafil# complicated expressions whose evaluation gives a result in terms of an initial set of values. Since this part of PAL includes the ability to state definitions and the ability to write conditionals, and since the ability to write definitions includes the ability to define recursive functions, it should be clear that this is all that is needed. (What we have just stated is that Church's lambdacalculus is equivalent in computational power to any of the various other schemes, such as Turing machines.) Indeed, this part of PAL matches very closely the computational power of pure LISP, or LISP-1. Although it would in principle be possible to have nothing else in PAL, it turns out that programming convenience requires imperative abilities. Equivalently, the users of LISP-I found the need for the features which show up in LISP- 1.5.

    The imperative features of PAL include such statements as assignment statements and go-to statements. Thus the evaluation of a program is more than just the value of a complicated expression: it is reflected also in the contents of a memory unit. The availability of assignment statements implies the existence of a memory.
    [...]
    Extract: PAL's Universe of Discourse
    PAL's Universe of Discourse
    An important part of the specification of a programming language is the specification of the objects which the programmer may manipulate. In PAL these objects include numbers, character strings, truth values, tuples, labels and functions. A number in PAL is either an integer or a "real". As suggested earlier, a character string is any collection of characters from PAL's alphabet. (Special provisions are made for quoting quote-marks and format effectors such as new-line or tab.) The truth values are available with names true and false.

    A tuple is an ordered collection of objects, the objects being any of the permissable data objects in PAL. Thus, for example, an element of a tuple may itself be a tuple. There is no requirement that successive elements of a tuple be of the same type: for example, the first may be an integer, the second element another tuple and the third element a label. A tuple transforms as a function on integers: The application of a tuple as an operator to an integer as an operand results in the selection of the relevant element of the tuple. Thus if A is a tuple, then the result of applying A to 2 is the second element of A. Such a construction may appear on .the left side of an assignment statement. Updating A(2) causes any variable that shares with it to be updated also.

    A label in PAL is very much like a label in most programming languages, although there are differences we will see later. Syntactically, a label is indicated by following it with a colon. A label is actually a variable and has the same syntax as a variable.

    A function is just that. Functions are defined in PAL with a syntax explained later.

    Consider now what are, called functors. The usual arithmetic plus, minus, times and divide are provided, as is an exponentiation operator. The first four of these operators will operate on two integers or on two reals, but will not do mixed-mode arithmetic. Operating on truth values are the logical operators and, or and not. Operating on numbers and producing truth values are the relational operators less than and greater than. Equality will operate on any two objects from the classes number, string and truth value. If both objects have the same type and have the same value, the equality relation between them is true, while it is false otherwise. The infixed operator aug takes an n-tuple as its left operand and any object as its right operand and produces as result an n+l-tuple. Other functors will be mentioned later in this discussion.

          in Proceedings of the 23rd ACM national conference January 1968 view details
  • Evans, Arthur Jr "PAL — A reference manual and a primer" MIT Department of Electrical Engineering Feb 1968 view details
          in Proceedings of the 23rd ACM national conference January 1968 view details
  • Evans, A . "PAL - Pedagogic Algorithmic Language", M. I.T. Department of Electrical Engineering, October 1970 view details
          in Proceedings of the 23rd ACM national conference January 1968 view details
  • Zilles, S.N. "An Expansion of the Data Structuring Capabilities of PAL" LCS Document MIT-LCS-TM-015 10-1-1970 view details
          in Proceedings of the 23rd ACM national conference January 1968 view details
  • Stock, Karl F. "A listing of some programming languages and their users" in RZ-Informationen. Graz: Rechenzentrum Graz 1971 181 view details Abstract: 321 Programmiersprachen mit Angabe der Computer-Hersteller, auf deren Anlagen die entsprechenden Sprachen verwendet werden kennen. Register der 74 Computer-Firmen; Reihenfolge der Programmiersprachen nach der Anzahl der Herstellerfirmen, auf deren Anlagen die Sprache implementiert ist; Reihenfolge der Herstellerfirmen nach der Anzahl der verwendeten Programmiersprachen.

    [321 programming languages with indication of the computer manufacturers, on whose machinery the appropriate languages are used to know.  Register of the 74 computer companies;  Sequence of the programming languages after the number of manufacturing firms, on whose plants the language is implemented;  Sequence of the manufacturing firms after the number of used programming languages.]
          in Proceedings of the 23rd ACM national conference January 1968 view details
  • Wozencraft, J.M. and Evans, A., "Notes on Programming Linguistics", MIT Department of Electrical Engineering, February 1971. view details
          in Proceedings of the 23rd ACM national conference January 1968 view details
  • Evans, Arthur Jr "The Lambda Calculus and its relation to programming languages" view details Abstract: An approach to the formal specification of the semantics of the programming language PAL is presented. A subset of the language is exhibited which is equivalent to Church's Lambda-calculus, and the semantics of that subset is specified by transformation rules from it to the Lambda-calculus. The semantics of the basic operators of the language (such as "+") is defined by axiomatization. The remainder of the language is specified by exhibiting an interpretor for it, the interpretor being expressed in the subset. The approach is tutorial in nature, concentrating on explaining the methods rather than on giving the details. No knowledge of the Lambda-calculus is assumed.

    Extract: Introduction
    The traditional way to define a programming language, by a manual written in English prose, results in a document that is on occasion readable but which usually suffers badly from lack of precision. Specifically, the requirement of language-defining documentation is that it answer any reasonable question about any program written in the language. Prose descriptions seldom meet that criterion. Language definition falls conveniently in two parts: syntax and semantics. Since publication of the Algol-60 report, syntax definition has been under control, BNF providing a notation for the precise specification of programming language syntax. However, the semantics part of a language definition is usually expressed in English prose, so that the question, "What does construct X in the language mean?" has been a hard one to answer. This paper considers one approach to the formal definition of semantics, just as BNF is a technique for the formal specification of syntax.
    Semantics has to do with answering the question, "What does a particular construct mean?" Meaning can be expressed only in terms of something else, so what is it in terms of that we can express the meaning of a programming language? Before we can answer this question, we must know what it means to specify meaning. We choose the following definition: Given a programming language, our objective is to be able to specify what happens if any program written in that language is obeyed by a computer.
    One way to answer this question is to write an interpretor for the language. An interpretor is some sort of mechanism, or algorithm, for interpreting programs, and one usually expresses algorithms in a programming language. This reasoning leads directly to the hard question: In what language shall we write the program?
    One possibility is to write the interpretor for L in language L itself. Although mathematically this approach suffers from disasterous circularity, it has pedagogic value and is frequently seen in the literature. Nonetheless, we desire a method that avoids the circularity. Recall our earlier statement that meaning can be expressed only in terms of something else. A prose definition, though sadly lacking in precision, does not suffer from the circularity problem, because the "something else" is English, a language totally independent of language L. We need some other language that is independent of L but is more precise than is English. Also needed of this language is that it be already understood by both the language definer and the studier of_L_L. Furtunately, there is such a language: the language of mathematics. If we can express the interpreter mathematically, then we will have met our original requirement for a formal semantics. There is a branch of mathematics that provides the notation needed to express the interpretor - the X-calculus of Church. In the remainder of this paper, we investigate this notation and show how to use it to provide a formal definition of the semantics R-PAL, a subset of the language PAL.


          in [ACM] Proceedings of the 1972 Annual Conference of the ACM view details
  • Sammet, Jean E., "Roster of Programming Languages 1972" 202 view details
          in Computers & Automation 21(6B), 30 Aug 1972 view details
  • Stock, Marylene and Stock, Karl F. "Bibliography of Programming Languages: Books, User Manuals and Articles from PLANKALKUL to PL/I" Verlag Dokumentation, Pullach/Munchen 1973 443 view details Abstract: PREFACE  AND  INTRODUCTION
    The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one.

    There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages.

    The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM.

    Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) .

    It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers.

    The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA).
    As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found.

    It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel.

    We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work.

    Graz / Austria, May, 1973
          in Computers & Automation 21(6B), 30 Aug 1972 view details
  • Strachey, Christopher "The Varieties of Programming Language" Programming Research Group Technical Monograph PRG-10 March 1973 view details Abstract: This paper suggests an analysis of the domains used in programming languages. It identifies some of the characteristic domains and shows that programming languages vary widely in their definition of these domains. Two languages are considered as extreme examples of programming language design, ALGOL 60 and PAL.


          in Computers & Automation 21(6B), 30 Aug 1972 view details
  • Zilles, S.N. "Procedural encapsulation: A linguistic protection technique" view details
          in SIGPLAN Notices 8(09) June 1973 Proceedings of ACM SIGPLAN - SIGOPS interface meeting on Architectural Support for Programming Languages and Operating Systems, Savannah, Georgia, 1973 view details