% File:    P-Quest-Manual.tex
% Author:  Florian Matthes
% Date:    18.10.1991
% Subject: P-Quest Installation and User Manual
%
\documentstyle[tycoon]{article}

\newcommand{\PQ}{{\it P-Quest}}

\title{P-Quest:\\ Installation and User Manual}
\titleid{DBIS Tycoon Report 101-91}
\titlestatus{Initial Version}
\date{October 1991}
\author{Florian Matthes}

\titledescription{ This document 
explains the installation and use of the \PQ\ system (version 14) 
on Sun-4 hardware platforms}

\titlerelated{Tycoon Library Manual (\PQ\ Version) \cite{Matt91b} \\
The \PQ\ C-Call Facility \cite{MaMa91} \\
The Quest Language and System (Tracking Draft) \cite{Card90}
}

\begin{document}

\maketitle

\tableofcontents

\newpage

\section{What is \PQ?}

\PQ\ was developed at the University of Hamburg, Germany, and adds
orthogonal persistence to the programming language Quest developed by
Luca Cardelli at DEC SRC, Palo Alto, USA \cite{Card89}. The implementation
of \PQ\ was carried out in the ESPRIT-II basic research project FIDE and
utilizes the Napier persistent object store provided by the University
of St.~Andrews, Scotland \cite{BrRo90}.

\PQ\ is an intermediate step in the Tycoon project, a long-term research
programme to develop an open database programming environment exploiting
state-of-the-art programming language technology for the construction of
complete data-intensive application systems. Specifically, the current
\PQ\ version is shipped with an initial set of Tycoon libraries that
provide uniform iteration abstractions over a wide range of generic bulk
data structures in addition to a standard library supporting  
base types and (formatted) file input and output. These libraries and a
prototypical \PQ\ Open-Look user interface library are described in a separate
document \cite{Matt91b}.

\PQ\ is strongly and statically typed and has three levels of entities
(i) values, (ii) types and operators, (iii) kinds. Types classify
values, and kinds classify types and type operators. Kinds are needed
because the type level of \PQ\ is unusually rich.

Evaluation is deterministic, left-to-right and applicative-order (call
by value). \PQ\ has a strong functional flair but it also incorporates
imperative features (e.g. assignments). It provides higher-order
functions, loops, conditionals, exceptions and a limited form of dynamic
binding through modules.

The type level provides existential and universal type quantification,
inductively defined subtyping over all type constructors, user-defined
type operators and recursive types. Type annotations are only required
in signatures since types and kinds within bindings are automatically
inferred by the compiler.

Kinds are used to control the instantiation of type variables. They are
means to denote sets of types, e.g., subtypes of a given type or sets of
(higher-order) type operators with the same signature.

The syntax of \PQ\ makes heavy use of initial and final keywords
(resembling Modula-2 and Modula-3) but has virtually no commas and
semicolons. New infix and listfix operators can be declared freely,
hovever, there is no overloading of identifiers and all infix operators
have the same precedence and are right-associative. 

The \PQ\ system runs on Sun-4 hardware platforms under SunOS 4.03 or
higher. \PQ\ expressions and programs are statically parsed, scoped,
type-checked and compiled into portable byte-code. \PQ\ programs can be
either entered and evaluated interactively or stored in pre-compiled
form as interfaces and modules that are linked dynamically. The present
release of the system is equipped with a C-call facility to dynamically
bind and call operating system or user-defined C library code
\cite{MaMa91}.

The \PQ\ compiler, linker, user data, compiled programs, compiled
interfaces and their associated type and dependency information are all
kept in a uniform persistent stable store. However, \PQ\ source code is
maintained outside the stable store in operating system text files.  In
\PQ\ there is no distinction between volatile and persistent data. All
entities (interfaces, modules, values, functions, types, kinds \ldots)
that are reachable from named objects in the user environment outlive a
single program execution. Storage allocated for temporary objects or
persistent objects that are no longer reachable is automatically
reclaimed by the system. There is no explicit object deletion operation
in \PQ.

\section{Installing \PQ}

\begin{center}
\begin{tabular}{rl}
Sofware Version:      	& 14 (based on Quest version 12a of DEC SRC) \\
Required Hardware: 	& Sun 4 \\
Required OS Version:    & SunOS 4.03 or higher \\
Space Requirements:	& 7 MB in /usr/local/lib \\
  			& 8.2 MB for each stable store 
\end{tabular}
\end{center}

To read the \PQ\ tape, \kw{cd} to a directory where \PQ\ is to be installed.
It should be on a file system and in a directory that is accessible by
all future users of \PQ. Then type:
\begin{xple}
   tar xf /dev/rst1 
\end{xple}
This creates a directory \kw{quest.p-sparc} in the current directory that
contains all \PQ\ binaries and library files. To install \PQ, first
become super user
\begin{xple}
   su 
\end{xple}
Then create a symbolic link from the directory \kw{/usr/local/lib} to the
newly created directory:
\begin{xple}
   ln -s `pwd`/quest.p-sparc /usr/local/lib 
   cd quest.p-sparc
\end{xple}
Now you have to decide how to make the \PQ\ binaries accessible
to future \PQ\ users. On most systems, new binaries are installed in the
directory \kw{/usr/local/bin}. In this case, use the command
\begin{xple}
   Install.p-sparc /usr/local/bin
\end{xple}
Alternatively, you can choose any other directory that is on the shell
search path, e.g.,
\begin{xple}
   Install.p-sparc /usr/bin
\end{xple}
The script \kw{Install.p-sparc} just creates symbolic links and changes
file access modes and therefore requires virtually no extra disk space.
The files of the distribution directory are listed in
Appendix~\ref{app:files}.


\section{Formatting and Initializing a New Persistent Store}

\PQ\ programs run against a persistent store that contains the complete
\PQ\ environment (programs and data). The first step to develop a \PQ\
application system is therefore usually to create a private persistent
store (implemented as a file in the Unix file system) and initialize it
with the interactive compiler environment.

To create a persistent store in the current directory (called ``\kw{.}''
according to the Unix naming conventions), the following command has to
be used:
\begin{xple}
   PQFormat . 1200 300
\end{xple}
The second parameter specifies the initial (and maximum) size of
the persistent store file measured in 8K pages, while the third
parameters specifies the number of 8K pages that are to be reserved as
shadow storage to implement database recovery. In the example above, a
file \kw{stablestore} of 9830400 bytes will be created in the current
directory. (1200-300) * 8192 bytes = 7.372800 bytes are available for
user-data and  2457600 bytes will be used as shadow storage.
Additionally, a file named \kw{lockfile} will be created in the current
directory. It is used to enforce exclusive access to the persistent
store.

The next step is to initialize the the store with predefined \PQ\
objects (built-in exceptions etc.):
\begin{xple}
   PQInit .
\end{xple}

The following command loads the interactive \PQ\ system (compiler, top
level, linker) into the persistent store:
\begin{xple}
   PQuest . NewQuest.qm
\end{xple}
This operation may take a while since the file \kw{NewQuest.qm}
contains data in a portable format that needs to be converted into the
persistent store format. After the compiler is successfully loaded into
the persistent store, all modules and interfaces listed in the file
\kw{Library.qst} are automatically imported. 

Finally, the \PQ\ prompt (``--'') appears. Enter the following \PQ\
commands to preserve the current status of the store:
\begin{xple}
   \k{import} store :Store;
   store.stabilise();
\end{xple}

To leave the \PQ\ system, type CTRL-D (``\verb$^$D'').

The steps described in this section have to be executed only once for
each persistent store.


\section{Interactive Commands}

Once the persistent store is initialized, it suffices to issue the
command
\begin{xple}
   PQuest
\end{xple}
to restart the compiler environment. All modules and interfaces listed
in the file \kw{Library.qst} which are not already cached in the
persistent store are imported.

When the \PQ\ prompt (``--'') appears, you can evaluate expressions that
have to be terminated by a semicolon,
\begin{xple}
  3 + 4;
\end{xple}
bind values, types and kinds to names,
\begin{xple}
  \k{let} x = 3;
  \k{Let} T = Int;
  \k{DEF} SUBT = POWER(Int);
\end{xple}
import compiled interfaces and modules,
\begin{xple}
  \k{import} print :Print;
\end{xple}
call routines from imported modules,
\begin{xple}
  print.string("Hello World!\verb$\$n");
\end{xple}
read \PQ\ source programs from files,
\begin{xple}
  \k{load}"Library.qst";
\end{xple}
compile \PQ\ interfaces,
\begin{xple}
  \k{interface} A
  \k{export}
    x :Int
  \k{end};
\end{xple}
compile \PQ\ modules,
\begin{xple}
  \k{module} a :A
  \k{export}
    \k{let} x = 3;
  \k{end};
\end{xple}
and import (link) new modules:
\begin{xple}
  \k{import} a:A;
  a.x;
  \k{import} a:A;
  a.x;
\end{xple}
Note that the module body is evaluated only once.


\section{Stability and Recovery}

To preserve the top-level value, type, kind, module and interface
declarations as well as the values of all transitively reachable objects
including mutable values, the store has to be ``stabilised''. This is
achieved by calling a routine from the standard module \kw{store}.
\begin{xple}
   \k{import} store :Store;
   store.stabilise();
\end{xple}
This operation can be embedded also into application program to
checkpoint the store (including active stack frames) at arbitrary points
in time. However, it should be noted that the stabilise operation does
not preserve the state of external files or of the screen.

The operation
\begin{xple}
   store.halt();
\end{xple}
stabilises the store and immediately terminates program execution.

If you leave the interactive loop of the \PQ\ system with CTRL-D
(``\verb$^$D''), or if the system crashes, all changes to the persistent store
since the last checkpoint will be undone.

By invoking the \PQ\ system with the Unix command
\begin{xple}
  PQuestRecover
\end{xple}
execution resumes with the next statement after the last
\kw{store.stabilise()} resp. \kw{store.halt()} statement.

The following program fragment makes use of this suspension mechanism:
\begin{xple}
\k{let rec} stopAfter(depth :Int) :Ok =
  \k{if} depth \k{is} 0 \k{then}
    store.halt()
  \k{else}
    print.string("Entering, depth = " $<>$ fmt.int(depth) $<>$ "\verb$\$n")
    stopAfter(depth-1)
    print.string("Leaving, depth = " $<>$ fmt.int(depth) $<>$ "\verb$\$n")
  \k{end};
\end{xple}
\begin{verbatim}
stopAfter(5);
..let stopAfter : All(depth:Int) Ok = <fun stopAfter()>
Entering, depth = 5
Entering, depth = 4
Entering, depth = 3
Entering, depth = 2
Entering, depth = 1
Exception: 
florian@dbis1> PQuestRecover
                                      ___   
     _____    _____ __ __ _____ _____|   |_ 
    |     |__|     |  |  |  _  |   __|    _|
    |  |  |__|  |  |     |   __|__   |   |  
    |   __|  |__   |_____|_____|_____|___|  
    |__|        |__|                        

    Hamburg University
    Tycoon Language Environment Release 1.1
    
    Restart from last checkpoint ...
    
Leaving, depth = 1
Leaving, depth = 2
Leaving, depth = 3
Leaving, depth = 4
Leaving, depth = 5
\end{verbatim}

\section{Garbage Collection}

The persistence model of \PQ\ is based on transitive reachability from
the ``main program''. Typically, this main program is the interactive
compiler environment (see Sec~\ref{stand-alone} how to load a new main
program into a persistent store). By introducing bindings at the
top-level, new, user-defined data structures can be made reachable.
There is no (unsafe) explicit object deletion mechanism. Garbage
collection is either invoked explicitly
\begin{xple}
   store.garbageCollect();
\end{xple}
or implicitly, as soon as the system runs out of (persistent) memory.
For example, the following program fragment triggers a garbage collection:
\begin{xple}
   \k{let} createGarbage(count :Int) :Ok =
     (* create count arrays with 10000 integer elements *)
     \k{for} i= 1 \k{upto} count \k{do}
       \k{let} dummy = arrayOp.new(10000 0)
    \k{end};

createGarbage(100);  (* allocate 4.000.000 bytes *)
createGarbage(100);  (* allocate 4.000.000 bytes *)
\end{xple}

There is also a possibility to garbage collect a \PQ\ store with a Unix
command: 
\begin{xple}
   PQCollect .
\end{xple}
This command performs a full garbage collection on the persistent store
in the current directory.


\section{Exchanging Data and Defining Search Paths}

As you may have noticed by now, compiled interfaces and modules are
created as separate Unix files with the extension ``\kw{.x}''. Only when
a module or interface is imported, this file is linked into the
persistent store. This makes it possible to share libraries between
separate persistent stores.

The search path for ``\kw{.x}'' files and files loaded with the \k{load}
command is initialized to
\begin{xple}
  .:/:/usr/local/lib/quest.p-sparc
\end{xple}
Therefore, \PQ\ first scans the current directory, then the root
directory and finally the \PQ\ installation directory. The inclusion of
the root directory allows the specification of files by their absolute
path names, e.g.,
\begin{xple}
   \k{load} "/users/dbis1/Test.qst";
\end{xple}
The search path can be changed at the \PQ\ top level as follows:
\begin{xple}
   \k{command} "SetPath .:./graphicenv";
\end{xple}

Using the generic import and export mechanisms of \PQ, it is also
possible to write arbitrary complex data structures (including
functions) onto a file and to re-load them into another persistent
store, preserving circularities and sharing within the data structure.
\begin{xple}
 \k{let} w = writer.file("data.x");
 \k{let} a = 3;
 dynamic.extern(w dynamic.new(a) dynamic.portable);
 writer.close(w);
\end{xple}

The file \kw{data.x} contains a single integer (a). It can be re-imported
as follows:
\begin{xple}
 \k{let} r = reader.file("data.x");
 \k{let} a = dynamic.be(:Int dynamic.intern(r dynamic.portable));
 reader.close(r);
 a;
\end{xple}

\section{Linking Stand-Alone Applictions}

\label{stand-alone}
For some applications it is desirable to have a persistent store that
only contains the application program and not the full \PQ\ compilation
environment.

The following \PQ\ declaration defines a main program function
\kw{prog} that is statically linked to the standard modules (e.g.
\kw{print, store}) it transitively imports. It is important that the 
main program function does not return but terminates by raising an exception:
\begin{xple}
\k{let} prog() :Ok =
  \k{begin}
    print("Hello World!\verb$\$n")
    store.stabilise()
    print("Hello World 2!\verb$\$n")
    \k{raise} \k{exception} exit:Ok \k{end} \k{end}
  \k{end};
\end{xple}

To generate a stand-alone \PQ\ boot file in portable format, the generic
export mechanism is used:
\begin{xple}
 \k{let} w = writer.file("Prog.qm");
 dynamic.extern(w dynamic.new(prog) dynamic.portable);
 writer.close(w);
\end{xple}

The program \kw{Prog.qm} is then executed in the persistent store found
in the current directory:
\begin{xple}
   PQuest . prog.qm
\end{xple}

Subsequent \kw{PQuestRecover} and \kw{PQuest} commands will execute
\kw{Prog.qm}. To re-load the compiler environment into the store, use the
command:
\begin{xple}
   PQuest . NewQuest.qm
\end{xple}

\section{Compatibility Issues}

Since \PQ\ uses the same portable data format like Quest Version 12, it
is possible to exchange \e{binary data} freely between both systems.
To ``intern'' the data file \kw{data.x} and the program
\kw{Prog.qm} into the non-persistent Quest environment, simply write:

\begin{xple}
 \k{let} r = reader.file("data.x");
 \k{let} a = dynamic.be(:Int dynamic.internPortable(r));
 reader.close(r);
 a;
 \k{let} r = reader.file("Prog.qm");
 \k{let} f = dynamic.be(:All()Ok dynamic.internPortable(r));
 reader.close(r);
 f();
\end{xple}

The ``intern'' of binary data ``externed'' by Quest into a \PQ\ object
store works analogously.

\noindent{\bf Restrictions:} \PQ\ and Quest Programs that make use of
the \kw{store} module as well as \PQ\ programs that utilize the module
\kw{ccall} cannot be exchanged (they will fail at run time).

\appendix

\section{Files Included in the Distribution Tape}
\label{app:files}

\begin{center}
\begin{tabular}{|l|l|}
\hline
File Name:      & Short Description \\
\hline
\verb$*$.spec   & Source code for Tycoon library modules \\
\verb$*$.spec.x & Compiled interface descriptions \\
\verb$*$.impl.x & Compiled Tycoon library modules \\
\verb$*$.info.x & Debugger information for Tycoon library modules (unused) \\
Install.p-sparc & Installation script (csh) \\
Library.qst     & \PQ\ statements executed whenever the interactive \\
                & environment is entered (imports standard Tycoon modules) \\
NewQuest.qm     & Byte code for the bootstrapped \PQ\ system \\
PQCollect       & Stand-alone garbage collection program \\
PQFormat        & Program to create a new persistent store \\
PQInit          & Program to initialize an existing persistent store \\
PQM             & Interpreter for \PQ\ byte code \\
PQStatistics    & Stand-alone program to generate store statistics \\
\hline
\end{tabular}
\end{center}

\bibliographystyle{florian}
\bibliography{../bib/florian}

\end{document}
