Napier88

From SystemsResearch

Jump to: navigation, search


Napier88 is a persistent programming language named after John Napier.

The Language

The Napier88 persistent programming system provides the following facilities:

  • Orthogonal persistence - models of data independent of longevity
  • Type completeness - no restrictions on constructing types
  • Higher-order procedures - procedures are data objects
  • Parametric polymorphism - generic forms which may be specialised for use
  • Abstract (existential) data types - for sophisticated protection and viewing
  • Collections of bindings - for name space control, incremental system construction and system evolution
  • A strongly typed stable store - a populated environment of typed data objects that may be updated atomically
  • Graphical data types - for line drawings and raster images
  • Concurrent execution and data access - using threads, semaphores and transactions
  • Support for reflective programming - for system evolution

The Napier88 system consists of the language and its persistent environment. The persistent store is populated and, indeed, the system uses objects within the persistent store to support itself. The implication of orthogonal persistence is that the user need never write code to move or convert data for long or short term storage [ABC+83]. The model of persistence in Napier88 is that of reachability from a root object. The persistent store is also stable, that is, it is transformed from one consistent state to the next. Stabilisation must be performed by the user to preserve data except that programs which terminate normally generate an automatic stabilise operation. Execution against the persistent store is always restarted from the last stabilised state.

Concurrency is provided by threads and semaphores [Mun93] for co-operative concurrency and by the CACS system [SM92] for competitive concurrency and designer transactions. Thus the notions of stability and visibility in commitment are orthogonal [Kra85, AMP86, MBB+89]. The entire computation including the state of the programs, threads and transactions is stable and recoverable after a system crash.

The Napier88 language is in the algol tradition as were its predecessors S-algol [Mor79] and PS-algol [PS88]. Following the work of Strachey [Str67] and Tennant [Ten77] the languages obey the principles of correspondence, abstraction and type completeness. This makes for languages with few defining rules allowing no exceptions. It is the belief of the designers that such an approach to language design yields more powerful and less complex languages.

The Napier88 type system was evolving at the same time as Cardelli and Wegner [CW85] published their work. Many of the ideas are related to theirs and some have been borrowed from them. The philosophy is that types are sets of values from the value space. The type system is mostly statically checkable, a property we wish to retain wherever possible. However, some dynamic projection out of unions for types any and env [Dea89], as well as variant selection, allows the dynamic binding required for orthogonal persistence [ABC+83] and system evolution [MCC+93].

The type system is polymorphic, like ML [Mil78, MTH89], Russell [DD79] and Poly [Mat85] and uses the existentially quantified types of Mitchell & Plotkin [MP88, CMM91] for abstract data types. There is deliberately no type inference, to allow for explicit specialisation of polymorphic forms from the persistent store. A unique design feature of the implementation of the typed objects is that their storage format may be non-uniform [MDC+91]. The type system also includes graphical types for line drawing in an infinite two-dimensional real space and for manipulating raster images.

The type equivalence rule in Napier88 is by structure and both recursive and parameterised types are allowed in the type algebra of the language, which in general leads to undecidable type checking. This is dealt with in Napier88 by a syntactic convention which allows the type checking to be sound, complete and co-complete [Con90].

The Napier88 system is designed as a layered architecture [Bro89] consisting of a compiler [ Dea88, Con90, Cut92, Kir92], the Persistent Abstract Machine (PAM) [BCC+88, CBC+90] and persistent storage architecture [Bro89, BM92, Mun93]. All the Napier88 architectural layers are virtual in that, in any implementation, they may be implemented separately or together as efficiency dictates. Thus, they are definitional rather than concrete. In the current release the stable storage is provided by an after-look shadow paging mechanism [ Bro89, BM92, Mun93]. The architecture is shown below:

Napier88 programs are executed in a strict left to right, top to bottom manner except where the flow of control is altered by one of the language clauses. On encountering an error state, the PAM generates a call to a standard error procedure held in the persistent store. These error procedures may be redefined by the user. The Persistent Abstract Machine also monitors interaction with UNIX environment in which Napier88 resides. When an asynchronous interrupt occurs the PAM records it and causes the appropriate procedure call to a standard event procedure in the persistent store. Again, the user may redefine the procedures used to intercept asynchronous interrupts.

There may be many incarnations of the stable persistent store and many activations of the PAM. However, only one PAM incarnation may work on one persistent store at any one time.

The current release of the Napier88 language is release 2.2.1 [MBC+94]. The language has only a few changes to that of release 1.0 [ MBC+89a, MBC+89b] but the persistent environment has been significantly enriched and re-organised. The changes to the language are:

  • a dynamic abstract witness model for abstract types, and
  • type operators

The main changes to the persistent environment are the provision of a browser, a compiler for reflective programming, threads and semaphores, a new organisation of the object store to provide a navigation free store, distributed stores with remote scan and copy and a hyper-programming system. The environment also provides a mechanism, through internet, for other sites to contribute programs and data which may then be accessed by remote scan and copy from other Napier88 stores.

The Napier88 persistent programming system was originally planned as part of the PISA project [AMP86] and was intended as a testbed for our experiments in type systems, programming environments, concurrency, bulk data, object stores and persistence. The form of the Napier88 language was first conceived by Ron Morrison and Malcolm Atkinson but the main design and first implementation was done by Fred Brown, Richard Connor, Alan Dearle and Ron Morrison. Release 2.2.1 constitutes a major re-engineering, re-organisation and enhancement of the system by, in addition to the above, Quintin Cutts, Graham Kirby and Dave Munro.

Many people have contributed to the Napier88 design. Malcolm Atkinson played a major role [MBC+87, AM88, MBB+89], as did his research assistants Richard Cooper, Francis Wai & Paul Philbrow. At STC Technology Ltd., John Scott, John Robinson, Dave Sparks and Michael Guy aided, abetted and often criticised constructively the early designs.

Our Visiting Fellows at St Andrews, John Hurst, Chris Barter, Chris Marlin, John Rosenberg, Dave Stemple and Robin Stanton also contributed and influenced the design and the research undertaken in the context of Napier88.

Further Information

References

  • [ABC+83] An Approach to Persistent Programming Atkinson, M.P., Bailey, P.J., Chisholm, K.J., Cockshott, W.P. & Morrison, R. Computer Journal 26,4 (1983) pp 360-365.
  • [AM88] Types, Bindings and Parameters in a Persistent Environment Atkinson, M.P. & Morrison, R. In Data Types and Persistence, Atkinson, M.P., Buneman, O.P. & Morrison, R. (ed), Springer-Verlag (1988) pp 3-20.
  • [AMP86] Designing a Persistent Information Space Architecture Atkinson, M.P., Morrison, R. & Pratten, G.D. In Proc. 10th IFIP World Congress, Dublin (1986) pp 115-120.
  • [BCC+88] The Persistent Abstract Machine Brown, A.L., Carrick, R., Connor, R.C.H., Dearle, A. & Morrison, R. Universities of Glasgow and St Andrews Technical Report PPRR-59-88 (1988).
  • [BM92] A Generic Persistent Object Store Brown, A.L. & Morrison, R. Software Engineering Journal 7, 2 (1992) pp 161-168.
  • [Bro89] Persistent Object Stores Brown, A.L. Ph.D. Thesis, University of St Andrews (1989).
  • [CBC+90] The Persistent Abstract Machine Connor, R.C.H., Brown, A.L., Carrick, R., Dearle, A. & Morrison, R. In Persistent Object Systems, Rosenberg, J. & Koch, D.M. (ed), Springer-Verlag (1990) pp 353-366.
  • [CMM91] Subtyping and Assignment in Database Programming Languages Connor, R.C.H., McNally, D.J. & Morrison, R. In Proc. 3rd International Workshop on Database Programming Languages, Nafplion, Greece (1991).
  • [Con90] Types and Polymorphism in Persistent Programming Systems Connor, R.C.H. Ph.D. Thesis, University of St Andrews (1990).
  • [Cut92] Delivering the Benefits of Persistence to System Construction and Execution Cutts, Q.I. Ph.D. Thesis, University of St Andrews (1992).
  • [CW85] On Understanding Types, Data Abstraction and Polymorphism Cardelli, L. & Wegner, P. ACM Computing Surveys 17, 4 (1985) pp 471-523.
  • [DD79] Revised Report on Russell Demers, A. & Donahue, J. Cornell University Technical Report TR79-389 (1979).
  • [Dea88] On the Construction of Persistent Programming Environments Dearle, A. Ph.D. Thesis, University of St Andrews (1988).
  • [Dea89] Environments: A flexible binding mechanism to support system evolution Dearle, A. In Proc. 22nd International Conference on Systems Sciences, Hawaii (1989) pp 46-55.
  • [Kir92] Reflection and Hyper-Programming in Persistent Programming Systems Kirby, G.N.C. Ph.D. Thesis, University of St Andrews (1992).
  • [Kra85] Building Flexible Multilevel Transactions in a Distributed Persistent Environment Krablin, G.L. In Proc. 2nd International Workshop on Persistent Object Systems, Appin, Scotland (1985) pp 86-117.
  • [Mat85] Poly Manual Matthews, D.C.J. University of Cambridge Technical Report 65 (1985).
  • [MBB+89] Language Design Issues in Supporting Process-Oriented Computation in Persistent Environments Morrison, R., Barter, C.J., Brown, A.L., Carrick, R., Connor, R.C.H., Dearle, A., Hurst, A.J. & Livesey, M.J. In Proc. 22nd International Conference on System Sciences, Hawaii (1989) pp 736-744.
  • [MBC+87] Polymorphism, Persistence and Software Reuse in a Strongly Typed Object-Oriented Environment Morrison, R., Brown, A.L., Connor, R.C.H. & Dearle, A. Software Engineering Journal, December (1987) pp 199-204.
  • [MBC+89a] The Napier88 Reference Manual Morrison, R., Brown, A.L., Connor, R.C.H. & Dearle, A. Universities of Glasgow and St Andrews Technical Report PPRR-77-89 (1989).
  • [MBC+89b] Napier88 Release 1.0 Morrison, R., Brown, A.L., Connor, R.C.H. & Dearle, A. University of St Andrews (1989).
  • [MBC+94] The Napier88 Reference Manual (Release 2.0) Morrison, R., Brown, A.L., Connor, R.C.H., Cutts, Q.I., Dearle, A., Kirby, G.N.C. & Munro, D.S. University of St Andrews Technical Report CS/94/8 (1994).
  • [MCC+93] Mechanisms for Controlling Evolution in Persistent Object Systems Morrison, R., Connor, R.C.H., Cutts, Q.I., Kirby, G.N.C. & Stemple, D. Journal of Microprocessors and Microprogramming 17, 3 (1993) pp 173-181.
  • [MDC+91] An Ad-Hoc Approach to the Implementation of Polymorphism Morrison, R., Dearle, A., Connor, R.C.H. & Brown, A.L. ACM Transactions on Programming Languages and Systems 13, 3 (1991) pp 342-371.
  • [Mil78] A Theory of Type Polymorphism in Programming Milner, R. Journal of Computer and System Sciences 17, 3 (1978) pp 348-375.
  • [Mor79] On the Development of Algol Morrison, R. Ph.D. Thesis, University of St Andrews (1979).
  • [MP88] Abstract Types have Existential Type Mitchell, J.C. & Plotkin, G.D. ACM Transactions on Programming Languages and Systems 10, 3 (1988) pp 470-502.
  • [MTH89] The Definition of Standard ML Milner, R., Tofte, M. & Harper, R. MIT Press, Cambridge, Massachusetts (1989).
  • [Mun93] On the Integration of Concurrency, Distribution and Persistence Munro, D.S. Ph.D. Thesis, University of St Andrews (1993).
  • [PS88] PS-algol Reference Manual, 4th edition Universities of Glasgow and St Andrews Technical Report PPRR-12-88 (1988).
  • [SM92] Specifying Flexible Concurrency Control Schemes: An Abstract Operational Approach Stemple, D. & Morrison, R. In Proc. 15th Australian Computer Science Conference, Hobart, Tasmania (1992) pp 873-891.
  • [Str67] Fundamental Concepts in Programming Languages Strachey, C. Oxford University Press, Oxford (1967).
  • [Ten77] Language Design Methods Based on Semantic Principles Tennant, R.D. Acta Informatica 8 (1977) pp 97-112.
Personal tools