\documentstyle[a4,12pt]{article}
\begin{document}
\author{APM Manual pages}
\title{Dictionary Operations}
\maketitle
\parskip .1 in
\setcounter{secnumdepth}{10}
\parindent 0in
\section{Preamble}
Dictionary Operations \hspace{ 2.2 in} \{documented 25/05/83\}

Command symbols, external objects, and certain "system" objects are currently
managed using a grammar-based dictionary scheme with the properties that:

Times for insertion and search operations are (roughly) linear in the length
of the name, irrespective of the number of items in the dictionary.

Search operations can succeed on leading substring matches.

Dictionary size requirement is 8 bytes per entry plus 4f bytes per character,
where the compression factor f is (substantially?) less than one, depending
on the extent to which leading substrings can be commoned up.

\section{Dictionary descriptors}

Dictionaries are contiguous areas of (aligned) memory, accessed through
4-longword descriptors. These descriptors are records with the layout:

\small\tt \begin{verbatim}%recordformat f (%integer beg,pos,lim,alt), where

BEG is the address of the start of the contiguous area.
POS is the address of the first unused word within the contiguous area,
    BEG<=POS<=LIM.  The dictionary is full when POS=LIM.
LIM is the address of the end (=start+size) of the contguous area.
ALT is the address of a descriptor of an alternative dictionary to be searched
    when an item is not found in the original dictionary. (Or Zero)

\end{verbatim}\rm  \normalsize \subsection{Internal layout of dictionary}

This section is still to be written



\section{Dictionary operations}

There are three primitive operations:
\small\tt \begin{verbatim}DEFNAME   inserts a name into a dictionary

REFNAME   searches a dictionary for an occurrence of a name

TRANSNAME translates a name-reference (as supplied by DEFNAME or REFNAME) back
          into a name-string.
\end{verbatim}\rm  \normalsize 
\subsection{Defname}

\%integerfnspec(16\_117c)defname(\%string(255)s,\%record(f)\%name d,\%integer size)

The name S is inserted into the dictionary described by D, additionally
reserving SIZE bytes for information to be associated with S. The result
is the address of a SIZE-byte area within the dictionary area.

Special cases:

RESULT=0
\\ \hspace*{ 0.4 in} The dictionary is too full for S to fit.

RESULT$<$0
\\ \hspace*{ 0.4 in} The name S is already in the dictionary. In this case, the
\\ \hspace*{ 0.4 in} result is the sign-bit plus the address of the SIZE-byte area
\\ \hspace*{ 0.4 in} originally associated with S.


\subsection{Refname}

\%integerfnspec(16\_1180)refname(\%string(255)s,\%record(f)\%name d)

Dictioanry D is searched for an occurrence of name S. The result is the
address of the area associated with S when it was defined.

Special cases:

RESULT=0
\\ \hspace*{ 0.3 in} S is not in D.

RESULT$<$0
\\ \hspace*{ 0.3 in} S is not in D, but T is, and S is a leading substring of T. In
\\ \hspace*{ 0.3 in} this case, the result is the sign bit plus the address of the
\\ \hspace*{ 0.3 in} area associated with T when it was defined. T may be identified
\\ \hspace*{ 0.3 in} by performing a TRANSNAME operation (qv).


\subsection{Transname}

\%routinespec(16\_1184)transname(\%integer x,\%string(255)\%name s)

X should be the address of some area associated with a dictionary entry.
The name is extracted from the dictionary and put into string S, which
should be big enough to accomodate it.



\section{Fixed-site descriptors}

The system knows (or will know) about four built-in dictionaries. At present
their descriptors live at fixed sites in the Boot Processor's local memory,
though at least some of them will require to be moved into main memory at
some stage.

\subsection{Command dictionary}

\%record(f)\%spec(16\_3fb0)comdict

The entries in this dictionary are the "command symbols" used by the
command interpreter. The areas associated with each entry are 8 bytes
long and contain two longwords. The first is a reference into the
file dictionary (qv), the second contains information relevant to the
command interpreter (flag symbols).


\subsection{File dictionary}

\%record(f)\%spec(16\_3fc0)fildict

The entries in this dictionary are filenames, which the command interpreter
has associated with command symbols. The associated areas are 8 bytes long.
When the file has not yet been loaded, the two longwords are both zero,
otherwise the first longword is the address of the start of the file, the
second longword is the address of the end (start+size) of the file.


\subsection{External dictionary}

\%record(f)\%spec(16\_3fd0)extdict \hspace{ 1.1 in} $<$Not actually used yet$>$

This dictionary is (will be?) used by compiled programs to establish
linkage of external objects (procedures, variables, ...?). The associated
area is 8 (? cross-ref with DEFEXT) bytes long. The first longword is the
address of the object, the second is the address of type information relevant
to that object.


\subsection{System dictionary}

\%record(f)\%spec(16\_3fe0)sysdict \hspace{ 1.1 in} $<$Not actually used yet$>$

This dictionary will contain entries relevant to the multi-process system,
such as process names, semaphore names, server queue names and the like,
if and when it is desirable for these to be described other than through the
external linkage mechanism.



\section{Dictionary Display Commands}
\subsection{DICTS : Dump contents of one or more Dictionaries}

Parameters:

\small\tt \begin{verbatim}        -System  : Display system dictionary
        -Command : Display command symbol dictionary
        -External: Display External dictionary
        -File    : Display File dictionary
        -Memory  : Display memory bounds
\end{verbatim}\rm  \normalsize 
Options are inclusive.

\small\tt \begin{verbatim}        -Output  : File to which output is to be sent (Default console)
\end{verbatim}\rm  \normalsize 
Parameters are handled by PAM

\subsection{SHOWSYM: Show symbol translation}

Parameter: Symbol to be translated

Additional parameters:

\small\tt \begin{verbatim}           -s:  Look symbol up in system dictionary
           -c:  Look symbol up in command symbol dictionary (default)
           -e:  Look symbol up in external dictionary
           -f:  Look symbol up in file dictionary
\end{verbatim}\rm  \normalsize 
Options are exclusive.


\section{Access to dictionary manipulations}

IMP include files containing specifications of the routines described here
may be found in..

I:DICT.INC \hspace{ 0.3 in} (Current operating system)
INC:DICT.IMP (New operating system)


\vspace{.75in} view:dict printed on 16/02/89 at 15.31

\newpage
\tableofcontents
\end{document}
