2011 Oct 26 at 10:30
DC 2310
Sinisa Catic, Independent Consultant, Ottawa, Ontario, Canada
General Overview
This talk is about the first part of a three-part effort (language definition, compiler implementation, and database storage allocator design and implementation) to rigorously define and implement new programming language ALGOL MMXI by following the principle of orthogonality. ALGOL MMXI integrates relational model of data into a general purpose modular algorithmic language. As a basis for the research is used a slightly modified ALGOL 68 as defined in the Revised Report plus a proposal for modules and separate compilation. The objective is to have a programming language of much wider applicability than any other language available today. ALGOL MMXI is a system, application, and database programming language. ALGOL MMXI program source will be able to compile directly to many different machine instruction set architectures, from 8-bit microcontrollers to mainstream 64-bit RISC processors and to 256-bit graphics processors. ALGOL MMXI program will be able to perform actions sequentially or in parallel using single or multiple processors, on values from individual bits and bytes to multiterabyte and petabyte relational databases. ALGOL MMXI is a high-level programming language but it will be able to act as a general adaptive high-level meta-assembler, which allows programmer to write code that uses directly any instruction set architecture, thus the title ``Universal Programming Language''.
The approximate agenda:
Changes in Terminology. ALGOL 68 has pioneered many new concepts and as a result had to invent new terms. Not all of them have been adopted. ALGOL MMXI uses terms that are common today and slightly different from ALGOL 68 own terms.
Unicode UTF-16 Character Set. ALGOL MMXI uses international standard Unicode UTF-16 to encode program text with possibility of using reserved words in either uppercase or lowercase mode inside single compilation phrase. To use Unicode requires making decision how to map and use such large set of characters inside one programming language.
Phrase Structure. ALGOL MMXI phrase structure consist of declarations and units. You will see ALGOL MMXI phrase structure tree that was derived from the ALGOL 68 phrase structure by simplification and expansion with new entries. Presented and compared will be sets of reserved keywords in ALGOL MMXI and ALGOL 68 .
Identifier Declaration. ALGOL 68 have been definitive improvement over ALGOL 60 but had some deficiencies despite being extraordinary well designed language. Our attention will be on correcting and refining language kernel, part that deals with declaration of identifiers, parameter passing and storage allocation. As a result we get more consistent, precise and expressive declaration mechanisms. ALGOL MMXI has additional ways of storage allocation beside loc and heap including possibility to define own stack-based and heap-based storage allocators with or without automatic deallocation techniques. Also will be shown what are semantic restrictions caused by the stack-based implementation model for routines and how these could be lifted through different implementation of blocks known as retention (contour) model of storage (D.M. Berry, L.M. Chirica, J.B. Johnston, D.F. Martin and A. Sorkin) in environments where this is possible.
Universal Assembler. ALGOL MMXI is not only a high-level language but also a general adaptive high-level meta-assembler. Addition of new syntax categories and asm serial clause enables ALGOL MMXI to be used for programming at the level of individual machine instructions. We will have quick overview of today's hardware microprocessors architectures, from mainstream 64-bit server and workstation microprocessors to 8,16,32-bit embedded microprocessors and specialized 256-bit graphic processors and what are particular requirements for language design.
Language Definition, Partial Evaluation and VW-Grammars. We will first make a quick overview of theoretical and practical contribution of Van Wijngaarden two-level grammars, which have been shown that are very simply and at the same time very powerful definitional and generative (derivative) mechanism, although there are some difficulties for human reader in following derivation process (will be shown how this can be overcome). Role of Van Wijngaarden two-level grammars in ALGOL MMXI is two-fold: for the formal definition of syntax and static semantic and for the compile-time code generation (partial program evaluation). Due to very clean and precise declaration mechanism almost no additional syntax categories are required to introduce partial evaluation. Resulting mechanisms are formally defined and at the same type very powerful.
Type System. ALGOL MMXI type system consist of three levels: values, types and kinds (but no classes). In ALGOL MMXI size of the simple numeric types is absolute (in bytes) instead of size being relative to machine word, which is a variable across different hardware architectures. In the absence of classes, parametric and subtype polymorphism are unified. You will see how ALGOL 68 six coercions have been replaced with more general concepts or simply removed. For example ALGOL 68 widening coercion has been replaced by declarative subtyping and dereferencing coercion has been replaced by explicit dereferencing operator val. In addition to equivalence relation we have subtypeof relation between types. Language support units of measures as a kind of type parameters in which now quantities can be expressed using numeric types parametrized on units of measure.
Syntax and Semantic of Relational Model. You will see what are most important component of language design necessary to express relational model and why ALGOL MMXI is well suited for that. More than forty years after Edgar F. Codd original paper and after SQL language and after over thirty years of the first physical implementation of the Relational Model, syntax and semantics of Relational Model is presented. In the context of ALGOL MMXI this is done through introduction of new composite type constructors, new types of units and new storage allocators.
Parallelism and Concurrency. Answer will be given to questions as what are various forms of concurrency and what are language mechanisms required to support it.
Modules and Rings. For the programming in the large ALGOL MMXI includes modules with separate compilation as have been defined by S.A. Schuman, Charles H. Lindsey and H.J. Boom. This has been extended by ring declaration, which provides ability to declare one or more rings (layers) when taken together represent directed acyclic graph in which nodes are represented by modules and edges in a graph represent access relationships between modules. Therefore rings provides possibility to enforce hierarchical structure between modules in a large software systems (David L. Parnas). In such directed graph every edge appears only once and edges from nodes (modules) are only going to lower rings.