Forgot your password?
Document Actions
History of PAL
Paul McJones, editor - paul@mcjones.org - http://www.mcjones.org/dustydecks/
Software Preservation Group
Computer History Museum
Introduction
The goal of this project is to preserve and present primary and secondary source materials (including specifications, source code, manuals, and papers discussing design and implementation) from PAL, the Pedagogic Algorithmic Language. The editor greatly appreciates comments, suggestions, and donations of additional materials.
"Landin’s programming language ISWIM and its immediate derivative PAL were implemented on CTSS, a translator-interpreter system.
ISWIM is modelled after Church’s λ-calculus. The ISWIM expression
f(3) + f(4) where f(x) = 2*x
corresponds to the λ-calculus formula
[λf. f(3) + f(4)] [λx. 2*x]
which, in turn, corresponds to the LISP S-expression
( (LAMBDA (F) (PLUS (F 3) (F 4))) (FUNCTION (LAMBDA (X) (TIMES 2 x ))) )The interpretive mechanism is virtually the SECD machine.* The translator from ISWIM to λ-calculus is based on Floyd’s scanner for precedence grammars extended to provide good error diagnostics. A primitive text-editing system is provided within the system to allow immediate correction of programs, although programs may also be entered via standard CTSS line-marked files.
The system was written in LISP to allow easy modification; a second implementation, written in a compiled language, is being planned. PAL was used as an instructional aid in an undergraduate course in Computer Science.
* P.J. Landin, A λ-Calculus Approach, Advances in Programming and Non-numerical Computation, Pergamon Press, 1966" [Landin and Morris 1967]
"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." [Evans 1968]
Contents
Acknowledgments
Thanks to: Arthur Evans Jr. and Frances J. Wozencraft, Martin Richards, Edward A. Feustel, Robert Mabee, Jim Stephens, and C. D. Tavares.
Source code
PAL system
The PAL/360 system consists of a compiler that translates from PAL to POCODE, an interpreter for POCODE, and a shell interfacing PAL to the underlying operating system.
"POCODE is stored in disk files to support separate compilation, so that the instructors could supply test frameworks that student programs would run against. PAL deliberately models the most interesting aspects of contemporary languages (to fulfil the purpose of course 6.231) but misses all the separate-compilation issues like local vs global names, libraries, include files, linking, etc." [Robert Mabee, personal communication, September 4, 2010]
- Martin Richards et al. PAL/360 source code (BCPL). Last modified by Robert Mabee, June 12, 1970.
- Compiler.
- Interpreter.
- OCR'd source. tar.gz xpalhd.bcpl xpal0.bcpl xpal1.bcpl xpal2.bcpl xpal3.bcpl
- Martin Richards. PAL implementation in BCPL. Approximate date? Version includes addition of a polynomial datatype as a student project. Machine-readable version provided by Ed Feuestel. ASCII
PAL programs
- Arthur Evans, Jr. A PAL Program of the Blackboard Evaluator. May 16, 1968, 2+21 pages. PDF
"Attached is a listing of a PAL program that simulates the left-hand blackboard evaluator of 6.231."
- Arthur Evans, Jr. PAL program for right-hand and jumping evaluators. April-May 1969, 29 pages. PDF
- Arthur Evans, Jr. and Martin Richards. Short example programs, 1967-1969, 18 pages. PDF
Documentation
- Arthur Evans, Jr. PAL Syntax as a Parse Algorithm. Appendix 2.2. November 24, 1967. 1+6 pages. PDF
Computer-printed appendix preceded by handwritten note from Art Evans to 6.231 staff: "Here is still another attempt at PAL syntax. It is Martin's parse algorithm."
- M. Richards. PAL manual draft. December 29, 1967, 13 pages. PDF
"This is part of an experimental PAL manual which was written to demonstrate the usefulness of L and Rvalues when describing PAL."
- A. Evans.
PAL -- A Reference Manual and a Primer.
Department of Electrical Engineering, Massachusetts Institute of Technology, February 1968, 185 pages.
Robert Mabee notes: "I have an identical edition of the reference manual except for:
page 2.6/F - 1 third line typo: = should be .
page 2.7/E - 2 near bottom thinko in arithmetic: 13 should be 12, 43 sb 42
Ap 1.5 is misplaced near the end of Martin's file, followed by a duplicate of the start of sect 2.1
I have one additional appendix, Ap 2.1, 'The Complete Syntax for PAL' [see below].
The reference manual doesn't include later extensions to PAL such as a test/ifso/ifnot sugaring (used in Pal-evans-19apr69)." [private communication to Paul McJones, June 20, 2010] - Anonymous. POCODE. Undated, 10 pages. PDF
Papers and reports
- John W. Wozencraft. Introduction of New Programming Linguistics. In Project MAC Progress Report IV, July 1966-July 1967, Programming Linguistics section, pages 133. Online at apps.dtic.mil
- Peter J. Landin and James H. Morris, Jr. The PAL-ISWIM System. In Project MAC Progress Report IV, July 1966-July 1967, Programming Linguistics section, pages 134. Online at apps.dtic.mil
- Arthur Evans, Jr. PAL -- a language designed for teaching programming linguistics. In Proceedings of the 1968 23rd ACM National Conference (August 27 - 29, 1968). ACM '68. ACM, New York, NY, pages 395-403. ACM Digital Library
- Stephen N. Zilles. An Expansion of the Data Structuring Capabilities of PAL. Report MIT-LCS-TM-015, Laboratory for Computer Science, Massachusetts Institute of Technology, October 1, 1970.
"PAL is a language designed for use as a tool to help teach programming linguistics[8]. As such, it incorporates generalizations of many of the features that are found in most common programming languages. PAL also has a relatively compact formal semantic definition. However, careful reading of this definition clearly shows that it would be much more readable if the control items and abstract syntax could be represented with a more sophisticated data definition facility. One goal of this thesis is to present such a facility."
- J. M. Wozencraft and A. Evans.
Notes on Programming Linguistics.
M.I.T. Department of Electrical Engineering, February 1971. PDF
" The Programming Linguistics Group, formed a year ago, has had two objectives: isolating various linguistic facilities underlying the specification of algorithms, and organizing this material into an introductory course for undergraduates who plan to major in computer science. These objectives are mutually reinforcing: without research, subject development would not be possible; without subject development, discovering the strengths and weaknesses of a proposed formulation would be far more difficult. Accordingly, the work has been supported jointly (and in nearly equal measure) by Project MAC and the Electrical Engineering Department.
The group's principal accomplishments to date consist of first-draft class notes and a programming language, called PAL, which has been implemented on CTSS at both Project MAC and the Computation Center. The notes and PAL were made available to a trial section of 20 sophomores and juniors during the Spring semester of 1967. We expect to refine the notes and increase the efficiency of the PAL implementation during the coming year.
In programming linguistics, the approach followed is intimately related to the branch of mathematical logic known as the λ-calculus. The relevance of λ-calculus to programming was first explored in depth by P. J. Landin, and most of our work thus far has been based on Landin's research. Remaining topics which deserve further investigation concern data structures and the fitting together of algebraic and imperative linguistic features in a more natural union." [Wozencraft 1967]
- Arthur Evans, Jr. The lambda calculus and its relation to programming languages. In Proceedings of the ACM Annual Conference - Volume 2 (Boston, Massachusetts, United States, August 01 - 01, 1972). R. Shields, Ed. ACM '72. ACM, New York, NY, pages 714-716. ACM Digital Library
Other PAL resources
- Martin Richards. Miscellaneous PAL Files, June 14, 2010. Online at cl.cam.ac.uk/~mr10
- Includes the scanned documents under "Source code" and "Documentation" above. Also contains the start of a reimplementation of PAL.
- Diarmuid Pigott. PAL: Pedagogic Algorithmic Language. HOPL: an interactive Roster of Programming Languages. Online at hopl.info