\documentclass{report} \usepackage{pstricks} \usepackage{pspicture} \usepackage{rotating} \usepackage{booktabs} \usepackage{longtable} \usepackage{amsmath} \usepackage{amssymb} \usepackage{epsf} \usepackage{float} \usepackage{fancyvrb} %\usepackage{mathtime} \usepackage{pst-coil} \usepackage{bbold} \addtolength{\textwidth}{3cm} \addtolength{\textheight}{2cm} \addtolength{\oddsidemargin}{-1.5cm} \addtolength{\evensidemargin}{-1.5cm} \setlength{\LTcapwidth}{\textwidth} \usepackage{times} \author{Dennis Furey\\ %Institute for Computing Research\\ %London South Bank University\\ \texttt{ursala-users@freelists.org}} \title{\Huge \textsf{% \textsl {Notational innovations for}\\%[1ex] \textsl {rapid application development}}\\ \normalsize \vspace{2em} \input{pics/rendemo}\vspace{-2em} } \usepackage[grey,times]{quotchap} \makeindex \begin{document} \large \setlength{\arrowlength}{5pt} \psset{unit=1pt,linewidth=.5pt,arrowinset=0,arrowscale=1.1} \floatstyle{ruled} \newfloat{Listing}{tbp}{los}[chapter] \maketitle \begin{abstract} This manual introduces and comprehensively documents a style of software prototyping and development involving a novel programming language. The language draws heavily on the functional paradigm but lies outside the mainstream of the subject, being essentially untyped and variable free. It is based on a firm semantic foundation derived from a well documented virtual machine model visible to the programmer. Use of a concrete virtual machine promotes segregation of procedural considerations within a primarily declarative formalism. Practical advantages of the language are a simple and unified interface to several high performance third party numerical libraries in C\index{C language} and Fortran,\index{Fortran} a convenient mechanism for unrestricted client/server interaction with local or remote command line interpreters, built in support for high quality random variate generation, and an open source compiler with an orthogonal, table driven organization amenable to user defined enhancements. This material is most likely to benefit mathematically proficient software developers, scientists, and engineers, who are arguably less well served by the verbose and restrictive conventions that have become a fixture of modern programming languages. The implications for generality and expressiveness are demonstrated within. \end{abstract} \tableofcontents \part{Introduction} \begin{savequote}[4in] \large Concurrently while your first question may be the most pertinent, you may or may not realize it is also the most irrelevant. \qauthor{The Architect in \emph{The Matrix Reloaded}} \end{savequote} \makeatletter \chapter{Motivation} \label{motiv} Who needs another programming language? The very idea is likely to evoke a frosty reception in some circles, justifiably so if its proponents are insufficiently appreciative of a simple economic fact. The most expensive thing about software is the cost of customizing or maintaining it, including the costs of training or recruitment of suitably qualified individuals. These costs escalate in the case of esoteric software technologies, of which unconventional languages are the prime example, and they ordinarily will take precedence over other considerations. \section{Intended audience} While there is no compelling argument for general commercial deployment of the tools and techniques described in this manual, there is nevertheless a good reason for them to exist. Many so called mature technologies from which organizations now benefit handsomely began as research projects, without which all progress comes to a standstill. Furthermore, this material may be of use to the following constituencies of early adopters. \subsection{Academic researchers} Perhaps you've promised a lot in your thesis proposal or grant application and are now wondering how you'll find an extra year or two for writing the code to support your claims. Outsourcing it is probably not an option, not just because of the money, but because the ideas are too new for anyone but you and a few colleagues to understand. Textbook software engineering methodologies can promise no improvement in productivity because the exploratory nature of the work precludes detailed planning. Automated code generation tools address only the user interface rather than the substance of the application. The language described in this manual provides you with a path from rough ideas to working prototypes in record time. It does so by keeping the focus on a high level of abstraction that dispenses with the tedium and repetition perceived to a greater degree in other languages. By a conservative estimate, you'll write about one tenth the number of lines of code in this language as in C\index{C language} or Java\index{Java} to get the same job done.\footnote{I'm a big fan of C, as all real programmers are, but I still wouldn't want to use it for anything too complicated.} How could such a technology exist without being more widely known? The deal breaker for a commercial organization would be the cost of retraining, and the risk of something untried. These issues pose no obstacle to you because learning and evaluating new ideas is your bread and butter, and financially you have nothing to lose. \subsection{Hackers and hobbyists} \index{hackers} This group merits pride of place as the source of almost every significant advance in the history of computing. A reader who believes that stretching the imagination and looking for new ways of thinking are ends in themselves will find something of value in these pages. The functional programming\index{functional programming} community has changed considerably since the \texttt{lisp}\index{lisp@\texttt{lisp}} era, not necessarily for the better unless one accepts the premise of the compiler writer as policy maker. We are now hard pressed to find current research activity in the field that is not concerned directly or indirectly with type checking and enforcement.\index{type checking} The subject matter of this document offers a glimpse of how functional programming might have progressed in the absence of this constraint. Not too surprisingly, we find ever more imaginative and ubiquitous use of higher order functions than is conceivable within the confines of a static type discipline. \subsection{Numerical analysts} Perhaps you have no great love for programming paradigms, but you have a real problem to solve that involves some serious number crunching. You will already be well aware of many high quality free numerical libraries, such as \texttt{lapack},\index{lapack@\texttt{lapack}} \texttt{Kinsol},\index{Kinsol@\texttt{Kinsol} library} \texttt{fftw},\index{fftw@\texttt{fftw} library} \texttt{gsl},\index{GNU Scientific Library} \emph{etcetera}, which are a good start, but you don't relish the prospect of writing hundreds of lines of glue code to get them all to work together. Maybe on top of that you'd like to leverage some existing code written in mutually incompatible domain specific languages that has no documented API at all but is invoked by a command line interpreter such as \texttt{Octave}\index{Octave} or \texttt{R}\index{R@\texttt{R}!statistical package} or their proprietary equivalents. This language takes about a dozen of the best free numerical libraries and not only combines them into a consistent environment, but simplifies the calling conventions to the extent of eliminating anything pertaining to memory management or mutable storage. The developer can feed the output from one library function seamlessly to another even if the libraries were written in different languages. Furthermore, any command line interpreter present on the host system can be invoked and controlled by a function call from within the language, with a transcript of the interaction returned as the result. \subsection{Independent consultants} Commercial use of this technology may be feasible under certain circumstances. One could envision a sole proprietorship or a small team of academically minded developers, building software for use in house, subject to the assumption that it will be maintained only by its authors. Alternatively, there would need to be a commitment to recruit for premium skills. Possible advantages in a commercial setting are rapid adaptation to changing requirements or market conditions, for example in an engineering or trading environment, and fast turnaround in a service business where software is the enabling technology. A less readily quantifiable benefit would be the long term effects of more attractive working conditions for developers with a preference for advanced tools. \section{Grand tour} The remainder of this chapter attempts to convey a flavor for the kinds of things that can be done well with this language. Examples from a variety of application areas are presented with explanations of the main points. These examples are not meant to be fully comprehensible on a first reading, or else the rest of the manual would be superfluous. Rather, they are intended to allow readers to make an informed decision as to whether the language would be helpful enough to be worth learning. \subsection{Graph transformation} \begin{figure} \begin{center} \epsfbox{pics/com.ps} \end{center} \caption{a finite state transducer} \label{comt} \end{figure} This example is a type of problem that occurs frequently in CAD applications. Given a model for a system, we seek a simpler model if possible that has the same externally observable behavior. If the model represents a circuit\index{circuits!digital} to be synthesized, the optimized version is likely to be conducive to a smaller, faster circuit. \subsubsection{Theory} A graph such as the one shown in Figure~\ref{comt} represents a system that interacts with its environment by way of input and output signals. For concreteness, we can imagine the inputs as buttons and the outputs as lights, each identified with a unique label. When an acceptable combination of buttons is pressed, the system changes from its present state to another designated state, and in so doing emits signals on the required outputs. This diagram summarizes everything there is to know about the system according to the following conventions. \begin{itemize} \item Each circle in the diagram represents a state. \item Each arrow (or ``transition'') represents a possible change of state, and is drawn connecting a state to its successor with respect to the change. \item Each transition is labeled with a set of input signal names, followed by a slash, followed by a set of output signal names. \begin{itemize} \item The input signal names labeling a transition refer to the inputs that cause it to happen when the system is in the state where it originates. \item The output signal names labeling a transition refer to the outputs that are emitted when it happens. \end{itemize} \item An unlabeled arrow points to the initial state. \end{itemize} \subsubsection{Problem statement} Two systems are considered equivalent if their observable behavior is the same in all circumstances. The state of a system is considered unobservable. Only the input and output protocol is of interest. We can now state the problem as follows: \begin{center} \emph{Using whatever data structure you prefer, implement an algorithm that transforms a given system specification to a simpler equivalent one if possible.} \end{center} For example, the system shown in Figure~\ref{comt} could be transformed to the one in Figure~\ref{optt}, because both have the same observable behavior, but the latter is simpler because it has only four states rather than nine. \begin{figure} \begin{center} \epsfbox{pics/opt.ps} \end{center} \caption{a smaller equivalent version} \label{optt} \end{figure} \subsubsection{Data structure} \begin{Listing}[t] \begin{verbatim} #binary+ sys = { 0: {({'a'},{'p'}): 0,({'c','m'},{'p'}): 7}, 8: {({'a'},{'p'}): 0,({'c','m'},{'p'}): 2}, 4: { ({'a'},{'p','r'}): 9, ({'g'},{'s'}): 3, ({'h','m'},{'s','u','v'}): 0}, 2: { ({'a','m'},{'v'}): 8, ({'g','h','m'},{'u','v'}): 9}, 6: {({'a'},{'p'}): 6,({'c','m'},{'p'}): 1}, 1: { ({'a','m'},{'v'}): 8, ({'g','h','m'},{'u','v'}): 9}, 9: { ({'a'},{'p','r'}): 9, ({'g'},{'s'}): 3, ({'h','m'},{'s','u','v'}): 8}, 3: {({'a'},{'u','v'}): 8}, 7: { ({'a','m'},{'v'}): 6, ({'g','h','m'},{'u','v'}): 4}} \end{verbatim} \caption{concrete representation of the system in Figure~\ref{comt}} \label{crep} \end{Listing} A simple, intuitive data structure is perfectly serviceable for this example. \begin{itemize} \item A character string is used for each signal name, a set of them for each set thereof, and a pair of sets of character strings to label each transition. \item For ease of reference, each state is identified with a unique natural number, with 0 reserved for the initial state. \item A transition is represented by its label and its associated destination state number. \item A state is fully characterized by its number and its set of outgoing transitions. \item The entire system is represented by the set of the representations of its states. \end{itemize} The language uses standard mathematical notation of braces and parentheses enclosing comma separated sequences for sets and tuples, respectively. A colon separated pair is an alternative notation optionally used in the language to indicate an association or assignment, as in \texttt{x:~y}. White space is significant in this notation and it denotes a purely non-mutable, compile-time association. Some test data of the required type are prepared as shown in Listing~\ref{crep} in a file named \texttt{sys.fun}. (This source file suffix is standard.) The compiler will parse and evaluate such an expression with no type declaration required, although one will be used later to cast the binary representation for display purposes. For the moment, the specification is compiled and stored for future use in binary form by the command \begin{verbatim} $ fun sys.fun fun: writing `sys' \end{verbatim} The command to invoke the compiler is \texttt{fun}. The dollar \index{dollar sign!shell prompt} sign at the beginning of a line represents the shell command prompt throughout this manual. Writing the file \texttt{sys} is the effect of the \texttt{\#binary+}\index{binary@\texttt{\#binary} compiler directive} compiler directive shown in the source. The file is named after the identifier with which the structure is declared. \subsubsection{Algorithm} \begin{Listing} \begin{verbatim} #import std #import nat #library+ optimized = |=&mnS; -+ ^Hs\~&hS *+ ^|^(~&,*+ ^|/~&)+ -:+ *= ~&nS; ^DrlXS/nleq$- ~&, ^= ^H\~& *=+ |=+ ==++ ~~bm+ *mS+ -:+ ~&nSiiDPSLrlXS+- \end{verbatim}%$ \caption{optimization algorithm} \label{cad} \end{Listing} In abstract terms, the optimization algorithm is as follows. \begin{itemize} \item Partition the set of states initially by equality of outgoing transition labels (ignoring their destination states). \item Further partition each equivalence class thus obtained by equivalence of transition termini under the relation implied hitherto. \item Iterate the previous step until a fixed point is reached. \item Delete all but one state from each terminal equivalence class, (with preference to the initial state where applicable) rerouting incident transitions on deleted states to the surviving class member as needed. \end{itemize} The entire program to implement this algorithm is shown in Listing~\ref{cad}. Some commentary follows, but first a demonstration is in order. To compile the code, we execute\begin{verbatim} $ fun cad.fun fun: writing `cad.avm'\end{verbatim}%$ assuming that the source code in Listing~\ref{cad} is in a file called \texttt{cad.fun}. The virtual machine code for the optimization function is written to a library file with suffix \texttt{.avm} because of the \texttt{\#library+} compiler directive, rather than as a free standing executable. Using the test data previously prepared, we can test the library function easily from the command line without having to write a separate driver.\begin{verbatim} $ fun cad sys --main="optimized sys" --cast %nsSWnASAS { 0: {({'a'},{'p'}): 0,({'c','m'},{'p'}): 1}, 4: { ({'a'},{'p','r'}): 4, ({'g'},{'s'}): 3, ({'h','m'},{'s','u','v'}): 0}, 1: { ({'a','m'},{'v'}): 0, ({'g','h','m'},{'u','v'}): 4}, 3: {({'a'},{'u','v'}): 0}}\end{verbatim}%$ This invocation of the compiler takes the library file \texttt{cad.avm}, with the suffix inferred, and the data file \texttt{sys} as command line arguments. The compiler evaluates an expression on the fly given in the parameter to the \texttt{--main} option, and displays its value cast to the type given by a type expression in the parameter to the \texttt{--cast} option. The result is an optimized version of the specification in Listing~\ref{crep} as computed by the library function, displayed as an instance of the same type. This result corresponds to Figure~\ref{optt}, as required. \subsubsection{Highlights of this example} This example has been chosen to evoke one of two reactions from the reader. Starting from an abstract idea for a fairly sophisticated, non-obvious algorithm of plausibly practical interest, we've done the closest thing possible to pulling a working implementation out of thin air in three lines of code. However, it would be an understatement to say the code is difficult to read. One might therefore react either with aversion to such a notation because of its unfamiliarity, or with a sense of discovery and wonder at its extraordinary expressive power. Of course, the latter is preferable, but at least no time has been wasted otherwise. The following technical points are relevant for the intrepid reader wishing to continue. \paragraph{Type expressions} such as the\index{type expressions} parameter to the \texttt{--cast} command line option above, are built from a selection of primitive types and constructors each represented by a single letter combined in a postorder notation. The type \texttt{n} is for natural numbers, and \texttt{s} is for character strings. \texttt{S} is the set constructor, and \texttt{W} the constructor for a pair of the same type. Hence, \texttt{sS} refers to sets of strings, and \texttt{sSW} to pairs of sets of strings. The binary constructor \texttt{A} pertains to assignments. Type expressions are first class objects in the language and can be given symbolic names. \paragraph{Pointer expressions} such as\index{pointer constructors} \texttt{\textasciitilde\&nSiiDPSLrlXS} from Listing~\ref{cad}, are a computationally universal language within a language using a postorder notation similar to type expressions as a shorthand for a great variety of frequently occurring patterns. Often they pertain to list or set transformations. They can be understood in terms of a well documented virtual machine code semantics, seen here in a more \texttt{lisp}-like notation, that is always readily available for inspection. \begin{verbatim}$ fun --main="~&nSiiDPSLrlXS" --decompile main = compose( map field((0,&),(&,0)), compose( reduce(cat,0), map compose( distribute, compose(field(&,&),map field(&,0)))))\end{verbatim}%$ \paragraph{Library functions} are reusable code fragments either packaged with the compiler or user defined and compiled into library files with a suffix of \texttt{.avm}. The function in this example is defined mostly in terms of language primitives except for one library function, \texttt{nleq},\index{nleq@\texttt{nleq}} the partial order relational predicate on natural numbers imported from the \texttt{nat} library. Functions declared in libraries are made accessible by the \texttt{\#import}\index{import@\texttt{\#import} compiler directive} compiler directive. \paragraph{Operators} are used extensively in the language to express functional combining forms. The most frequently used operators are \texttt{+}, for functional composition\index{functional composition}, \index{composition} as in an expression of the form \texttt{f+ g}, and \texttt{;}, as in \texttt{g; f}, similar to composition with the order reversed. Another kind of operator is function application, expressed by juxtaposition of two expressions separated by white space. Semantically we have an identity $\texttt{(f+ g) x} = \texttt{(g; f) x} = \texttt{f (g x)}$, or simply $\texttt{f g x}$, as function application\index{function application} in this language is right associative. \paragraph{Higher order functions} find a natural expression in terms of operators. It is convenient to regard most operators as having binary, unary, and parameterless forms, so that an expression such as \texttt{g;} is meaningful by itself without a right operand. If \texttt{g;} is directly applied to a function \texttt{f}, we have the resulting function \texttt{g; f}. Alternatively, it would be meaningful to compose \texttt{g;} with a function \texttt{h}, where \texttt{h} is a function returning a function, as in \texttt{g;+ h}. This expression denotes a function returning a function similar to the one that would be returned by \texttt{h} with the added feature of \texttt{g} included in the result as a preprocessor, so to speak. Several cases of this usage occur in Listing~\ref{cad}. \paragraph{Combining forms} are associated with a rich variety of other operators, some of which are used in this example. Without detailing their exact semantics, we conclude this section with an informal summary of a few of the more interesting ones. \begin{itemize} \item The partition combinator, \texttt{|=}, takes a function computing an equivalence relation to the function that splits a list or a set into equivalence classes. \item The limit combinator, \verb|^=|, iterates a function until a fixed point is reached. \item The fan combinator, \texttt{\textasciitilde\textasciitilde}, takes a function to one that operates on a pair by applying the given function to both sides. \item The reification combinator, \texttt{-:}, takes a finite set of pairs of inputs and outputs to the partial function defined by them. \item The minimization operator \texttt{\$-}, takes a function computing a relational predicate to one that returns the minimum item of a list or set with respect to it. \item Another form of functional composition,\index{functional composition} \index{composition} \verb|-+|$\dots$\verb|+-|, constructs the composition of an enclosed comma separated sequence of functions. \item The binary to unary combinators \verb|/| and \verb|\| fix one side of the argument to a function operating on a pair. \verb|f/k y| $=$ \texttt{f(k,y)} and \verb|f\k x| $=$ \texttt{f(x,k)}, where it should be noted as usual that the expression \verb|f/k| is meaningful by itself and consistent with this interpretation. \end{itemize} \subsection{Data visualization} This example demonstrates using the language to manipulate and depict numerical data that might emerge from experimental or theoretical investigations. \subsubsection{Theory} The starting point is a quantity that is not known with certainty, but for which someone purports to have a vague idea. To be less vague, the person making the claim draws a bell shaped curve over the range of possible values and asserts that the unknown value is likely to be somewhere near the peak. A tall, narrow peak leaves less room for doubt than one that's low and spread out.\footnote{apologies to those who might take issue with this greatly simplified introduction to statistics} Let us now suppose that the quantity is time varying, and that its long term future values are more difficult to predict than its short term values. Undeterred, we wish to construct a family of bell shaped curves, with one for each instant of time in the future. Because the quantity is becoming less certain, the long term future curves will have low, spread out peaks. However, we venture to make one mildly predictive statement, which is that the quantity is non-negative and generally follows an increasing trend. The peaks of the curves will therefore become laterally displaced in addition to being flatter. It is possible to be astonishingly precise about being vague, and a well studied model for exactly the situation described has been derived rigorously from simple assumptions. Its essential features are as follows. A measure $\bar x$ of the expected value of the estimate (if we had to pick one), and its dispersion $v$ are given as functions of time by these equations, \begin{eqnarray*} \bar{x}(t)&=&m e^{\mu t}\\ v(t)&=&m^2 e^{2\mu t}\left(e^{\sigma^2 t}-1\right) \end{eqnarray*} where the parameters $m$, $\mu$ and $\sigma$ are fixed or empirically determined constants. A couple of other time varying quantities that defy simple intuitive explanations are also defined. \begin{eqnarray*} \theta(t)&=&\ln\left(\bar{x}(t)^2\right)-\frac{1}{2}\ln\left(\bar{x}(t)^2+v(t)\right)\\ \lambda(t)&=&\sqrt{\ln\left(1+\frac{v(t)}{\bar{x}(t)^2}\right)} \end{eqnarray*} These combine to form the following specification for the bell shaped curves, also known as probability density functions.\index{probability density} \begin{eqnarray*} (\rho(t))(x)&=&\frac{1}{\sqrt{2\pi}\lambda(t) x}\exp\left(-\frac{1}{2}\left(\frac{\ln x - \theta(t)}{\lambda(t)}\right)^2\right) \end{eqnarray*} Whereas it would be fortunate indeed to find a specification of this form in a statistical reference, functional programmers by force of habit will take care to express it as shown if this is the intent. We regard $\rho$ as a second order function, to which one plugs in a time value $t$, whereupon it returns another (unnamed) function as a result. This latter function takes a value $x$ to its probability density at the given time, yielding the bell shaped curve when sampled over a range of $x$ values.\footnote{Some authors will use a more idiomatic notation like $\rho(x;t)$ to suggest a second order function, but seldom use it consistently.} \subsubsection{Problem statement} This problem is just a matter of muscle flexing compared to the previous one. It consists of the following task. \begin{center} \emph{Get some numbers out of this model and verify that the curves look the way they should.} \end{center} \subsubsection{Surface renderings} \begin{Listing} \begin{verbatim} #import std #import nat #import flo #import plo #import ren ---------------------------- constants -------------------------------- imean = 100. # mean at time 0 sigma = 0.3 # larger numbers make the variance increase faster mu = 0.6 # larger numbers make the mean drift upward faster ------------------------ functions of time ---------------------------- expectation = times/imean+ exp+ times/mu theta = minus^(ln+ ~&l,div\2.+ ln+ plus)^/sqr+expectation marv lambda = sqrt+ ln+ plus/1.+ div^/marv sqr+ expectation marv = # variance of the marginal distribution times/sqr(imean)+ times^( exp+ times/2.+ times/mu, minus\1.+ exp+ //times sqr sigma) rho = # takes a positive time value to a probability density function "t". 0.?=/0.! "x". div( exp negative div\2. sqr div(minus/ln"x" theta "t",lambda "t"), times/sqrt(times/2. pi) times/lambda"t" "x") ------------------------- image specifications ----------------------- #binary+ #output dot'tex' //rendering ('ihn+',1.5,1.) spread = visualization[ margin: 35., headroom: 25., picture_frame: ((350.,350.),(-15.,-25.)), pegaxis: axis[variable: '\textsl{time}'], abscissa: axis[variable: '\textsl{estimate}'], ordinates: < axis[variable: '$\rho$',hatches: ari5/0. .04,alias: (10.,0.)]>, curves: ~&H( * curve$[peg: ~&hr,points: * ^/~&l ^H\~&l rho+ ~&r], |=&r ~&K0 (ari41/75. 175.,ari31/0.1 .6))] \end{verbatim} \caption{code to generate the rendering in Figure~\ref{sprd}} \label{csp} \end{Listing} \begin{figure}[t] \begin{center} \input{pics/spread} \end{center} \caption{Probability density drifts and disperses with time as the estimate grows increasingly uncertain} \label{sprd} \end{figure} A favorite choice for book covers and poster presentations is to render a function of two variables in an eye catching graphic as a three dimensional surface. A library for that purpose is packaged with the compiler. It features realistic shading and perspective from multiple views, and generates readable \LaTeX \index{LaTeX@\LaTeX!graphics} code suitable for inclusion in documents or slides. Postscript\index{Postscript} and PDF\index{PDF} renderings, while not directly supported, can be obtained through \LaTeX\/ for users of other document preparation systems. The code to invoke the rendering library function for this model is shown in Listing~\ref{csp} and the result in Figure~\ref{sprd}. Assuming the code is stored in a file named \texttt{viz.fun}, it is compiled as follows. \begin{verbatim} $ fun flo plo ren viz.fun fun: writing `spread' fun: writing `spread.tex' \end{verbatim} The output files in \LaTeX\/ and binary form are generated immediately at compile time, without the need to build any intermediate libraries or executables, because this application is meant to be used once only. This behavior is specified by the \texttt{\#binary+} and \texttt{\#output} compiler directives. The main points of interest raised by this example relate to the handling of numerical functions and abstract data types. \paragraph{Arithmetic operators} are designated by alphanumeric identifiers such as \texttt{times} and \texttt{plus} rather than conventional operator symbols, for obvious reasons. \paragraph{Dummy variables} enclosed in double quotes allow an \index{dummy variables} alternative to the pure combinatoric variable-free style of function specification. For example, we could write \begin{verbatim} expectation "t" = times(imean,exp times(mu,"t")) \end{verbatim} or \begin{verbatim} expectation = "t". times(imean,exp times(mu,"t")) \end{verbatim} as alternatives to the form shown in Listing~\ref{csp}, where the former follows traditional mathematical convention and the latter is more along the lines of ``lambda abstraction''\index{lambda abstraction} familiar to functional programmers.\label{lamdab} Use of dummy variables generalizes to higher order functions, for which it is well suited, as seen in the case of the \texttt{rho} function. It may also be mixed freely with the combinatoric style. Hence we can write \begin{verbatim} rho "t" = 0.?=/0.! "x". div(...) \end{verbatim} which says in effect ``if the argument to the function returned by \texttt{rho} at \verb|"t"| is zero, let that function return a constant value of zero, but otherwise let it return the value of the following expression with the argument substituted for \verb|"x"|.'' \paragraph{Abstract data types} adhere to a straightforward record-like syntax consisting of a symbolic name for the type followed by square brackets enclosing a comma separated sequence of assignments of values to field identifiers. The values can be of any type, including functions and other records. The \texttt{visualization}, \texttt{axis}, and \texttt{curve} types are used to good effect in this example. A record is used as an argument to the rendering function because it is useful for it to have many adjustable parameters, but also useful for the parameters to have convenient default settings to spare the user specifying them needlessly. For example, the numbering of the horizontal axes in Listing~\ref{csp} was not explicitly specified but determined automatically by the library, whereas that of the vertical $\rho$ axis was chosen by the user (in the \texttt{hatches} field). Values for unspecified fields can be determined by any computable function at run time in a manner inviting comparison with object orientation\index{object orientation}. Enlightened development with record types is all about designing them with intelligent defaults. \subsubsection{Planar plots} \begin{Listing} \begin{verbatim} #import std #import nat #import flo #import fit #import lin #import plo #output dot'tex' plot smooth = ~&H\spread visualization$i[ margin: 15.!, picture_frame: ((400.,250.),-30.,-35.)!, curves: ~curves; * curve$i[ points: ^H(*+ ^/~&+ chord_fit0,ari300+ ~&hzXbl)+ ~points, attributes: {'linewidth': '0.1pt'}!]] \end{verbatim} \caption{reuse of the data generated by Listing~\ref{csp} for an interpolated 2-dimensional plot} \label{sme} \end{Listing} The three dimensional rendering is helpful for intuition but not always a complete picture of the data, and rarely enables quantitative judgements about it. In this example, the dispersion of the peak with increasing time is very clear, but its drift toward higher values of the estimate is less so. A two dimensional plot can be a preferable alternative for some purposes. Having done most of the work already, we can use the same \texttt{visualization} data structure to specify a family of curves in a two dimensional plot. It will not be necessary to recompile the source code for the mathematical model because the data structure storing the samples has been written to a file in binary form. Listing~\ref{sme} shows the required code. Although it would be possible to use the original \texttt{spread} record with no modifications, three small adjustments to it are made. These are the kinds of settings that are usually chosen automatically but are nevertheless available to a user preferring more control. \begin{itemize} \item manual changes to the bounding box (a perennial issue for \LaTeX \index{LaTeX@\LaTeX!graphics} images with no standard way of automatically determining it, the default is only approximate) \item a thinner than default line width for the curves, helpful when many curves are plotted together \item smoothing of the curves by a simple piecewise polynomial interpolation method \end{itemize} Assuming the code in Listing~\ref{sme} is in a file named \texttt{smooth.fun}, it is compiled by the command \begin{verbatim} $ fun flo fit lin plo spread smooth.fun fun: writing `smooth.tex' \end{verbatim} The command line parameter \texttt{spread} is the binary file generated on the previous run. Any binary file included on the command line during compilation is available within the source as a predeclared identifier. \begin{figure} \begin{center} \input{pics/rough}\\ \input{pics/smooth} \end{center} \caption{plots of data as in Figure~\ref{sprd} showing the effects of smoothing} \label{rsm} \end{figure} The smoothing effect is visible in Figure~\ref{rsm}, showing how the resulting plot would appear with smoothing and without. Whereas discernible facets in a three dimensional rendering are a helpful visual cue, line segments in a two dimensional plot are a distraction and should be removed. A library providing a variety of interpolation\index{interpolation} methods is distributed with the compiler, including sinusoidal, higher order polynomial, multidimensional, and arbitrary precision versions. For this example, a simple cubic interpolation (\texttt{chord\_fit 0}) resampled at 300 points suffices. \subsection{Number crunching} \label{ncu} For this example, we consider a classic problem in mathematical \index{contingent claims} \index{derivatives!financial} \index{options!financial} finance, the valuation of contingent claims (a stuffy name for an interesting problem comparable to finite element analysis). The solution demonstrates some distinctive features of the language pertaining to abstract data types, numerical methods, and GNU Scientific Library functions. \subsubsection{Theory} Two traders want to make a bet on a stock. One of them makes a commitment to pay an amount determined by its future price and the other pays a fee up front. The fee is subject to negotation, and the future payoff can be any stipulated function of the price at that time. \paragraph{Avoidance of arbitrage} \index{arbitrage} One could imagine an enterprising trader structuring a portfolio of bets with different payoffs in different circumstances such that he or she can't lose. So much the better for such a trader of course, but not so for the counterparties who have therefore negotiated erroneous fees. To avoid falling into this trap, a method of arriving at mutually consistent prices for an ensemble of contracts is to derive them from a common source. A probability distribution for the future stock price is postulated or inferred from the market, and the value of any contingent claim on it is given by its expected payoff with respect to the distribution. The value is also discounted by the prevailing interest rate to the extent that its settlement is postponed. \paragraph{Early exercise} If the claim is payable only on one specific future date, its present value follows immediately from its discounted expectation, but a complication arises when there is a range of possible exercise dates.\footnote{A further complication that we don't consider in this example is a payoff with unrestricted functional dependence on both present and previous prices of the stock.} In this case, a time varying sequence of related distributions is needed. \begin{figure}[t] \begin{center} \begin{picture}(205,280)(-70,-155) \put(0,0){\makebox(0,0)[r]{100.00}} \multiput(0,0)(40,40){3}{\begin{picture}(0,0) \psline{->}(0,5)(15,30) \psline{->}(0,-5)(15,-30)\end{picture}} \multiput(40,-40)(40,40){2}{\begin{picture}(0,0) \psline{->}(0,5)(15,30) \psline{->}(0,-5)(15,-30)\end{picture}} \put(80,-80){\begin{picture}(0,0) \psline{->}(0,5)(15,30) \psline{->}(0,-5)(15,-30)\end{picture}} \put(40,40){\makebox(0,0)[r]{112.24}} \put(40,-40){\makebox(0,0)[r]{89.09}} \put(80,80){\makebox(0,0)[r]{125.98}} \put(80,0){\makebox(0,0)[r]{100.00}} \put(80,-80){\makebox(0,0)[r]{79.38}} \put(120,120){\makebox(0,0)[r]{141.40}} \put(120,40){\makebox(0,0)[r]{112.24}} \put(120,-40){\makebox(0,0)[r]{89.09}} \put(120,-120){\makebox(0,0)[r]{70.72}} \put(0,-150){\makebox(0,0){\textsl{present}}} \psline{->}(20,-150)(100,-150) \put(120,-150){\makebox(0,0){\textsl{future}}} \put(-60,0){\makebox(0,0)[c]{\textsl{price}}} \psline{->}(-60,10)(-60,120) \psline{->}(-60,-10)(-60,-120) \end{picture} \end{center} \caption{when stock prices take a random walk} \label{binlat} \end{figure} \paragraph{Binomial lattices} \index{binomial lattice} \index{lattices!binomial} A standard construction has a geometric progression of possible stock prices at each of a discrete set of time steps ranging from the contract's inception to its expiration. The sequences acquire more alternatives with the passage of time, and the condition is arbitrarily imposed that the price can change only to one of two neighboring prices in the course of a single time step, as shown in Figure~\ref{binlat}. The successor to any price represents either an increase by a factor $u$ or a decrease by a factor $d$, with $ud=1$. A probability given by a binomial distribution is assigned to each price, a probability $p$ is associated with an upward movement, and $q$ with a downward movement. An astute argument and some high school algebra establish values for these parameters based on a few freely chosen constants, namely $\Delta t$, the time elapsed during each step, $r$, the interest rate, $S$ the initial stock price, and $\sigma$, the so called volatility. The parameter values are \begin{eqnarray*} u&=&e^{\sigma\sqrt{\Delta t}}\\ d&=&e^{-\sigma\sqrt{\Delta t}}\\ p&=&\frac{e^{r\Delta t}-d}{u - d}\\ q&=&1-p \end{eqnarray*} With $n$ time steps numbered from $0$ to $n-1$, and $k+1$ possible stock prices at step number $k$ numbered from $0$ to $k$, the fair price of the contract (in this simplified world view) is $v^0_0$ from the recurrence that associates the following value of $v_i^k$ with the contract at time $k$ in state $i$. \begin{equation} v_i^k=\left\{ \begin{array}{lll} f(S_i^k)&\text{if}&k=n-1\\ \max\left(f(S_i^k),e^{-r\Delta t}\left(p v_{i+1}^{k+1} + q v_i^{k+1}\right)\right)&\makebox[0pt][l]{\text{otherwise}} \end{array} \right. \label{amrec} \end{equation} In this formula, $f$ is the stipulated payoff function, and $S_i^k = S u^i d^{k-i}$ is the stock price at time $k$ in state $i$. The intuition underlying this formula is that the value of the contract at expiration is its payoff, and the value at any time prior to expiration is the greater of its immediate or its expected payoff. \subsubsection{Problem statement} The construction of Figure~\ref{binlat}, known as a binomial lattice \index{binomial lattice} \index{lattices!binomial} in financial jargon, can be used to price different contingent claims on the same stock simply by altering the payoff function $f$ accordingly, so it is natural to consider the following tasks. \begin{center} \emph{Implement a reusable binomial lattice pricing library allowing arbitrary payoff functions, and an application program for a specific family of functions.} \end{center} The payoff functions in question are those of the form \[ f(s) = \max(0,s - K) \] for a constant $K$ and a stock price $s$. The application should allow the user to specify the particular choice of payoff function by giving the value of $K$. \subsubsection{Data structures} A lattice can be seen as a rooted graph with nodes organized by levels, such that edges occur only between consecutive levels. Its connection topology is therefore more general than a tree but less general than an unrestricted graph. An unusual feature of the language is a built in type constructor for lattices with arbitrary branching patterns and base types. Lattices in the language should be understood as containers comparable to lists and sets. For this example, a binomial lattice of floating point numbers is used. The lattice appears as one field in a record whose other fields are the model parameters mentioned above such as the time step durations and transition probabilities. As indicated above, some of the model parameters are freely chosen and the rest are determined by them. It will be appropriate to design the record data structure in the same way, in that it automatically initializes the remaining fields when the independent ones are given. For this purpose, Listing~\ref{crt} uses a record declaration of the form \begin{eqnarray*} \lefteqn{\langle\textit{record mnemonic}\rangle\;\texttt{::}}\\ &&\langle\textit{field identifier}\rangle\quad \langle\textit{type expression}\rangle\quad \langle\textit{initializing function}\rangle\\ &&\vdots\\ &&\langle\textit{field identifier}\rangle\quad \langle\textit{type expression}\rangle\quad \langle\textit{initializing function}\rangle \end{eqnarray*} If no values are specified even for the independent fields, the record will initialize itself to the small pedagogical example depicted in Figure~\ref{binlat}. \begin{Listing} \begin{verbatim} #import std #import nat #import flo #import lat #library+ crr :: s %eZ ~s||100.! v %eZ ~v||0.2! t %eZ ~t||1.! n %n ~n||4! r %eZ ~r||0.05! dt %e ||~dt ~t&& div^/~t float+ predecessor+ ~n up %e ||~up ~v&& exp+ times^/~v sqrt+ ~dt dn %eZ ~v&& exp+ negative+ times^/~v sqrt+ ~dt p %eZ -&~r,~dn,div^(minus^\~dn exp+ times+ ~/r dt,minus+ ~/up dn)&- q %eZ -&~p,fleq\1.+ ~p,minus/1.+ ~p&- l %eG ~n&& ~q&& ~l|| grid^( ~&lihBZPFrSPStx+ num*+ ^lrNCNCH\~s ^H/rep+~n :^\~&+ ~&h;+ :^^( ~&h;+ //times+ ~dn, ^lrNCT/~&+ ~&z;+ //times+ ~up), ^DlS( fleq\;eps++ abs*++ minus*++ div;+ \/-*+ <.~up,~dn>, ~&t+ iota+ ~n)) amer = # price of an american option on lattice c with payoff f ("c","f"). ~&H\~l"c" lfold max^|/"f" ||ninf! ~&i&& -+ \/div exp times/~r"c" ~dt "c", iprod/<~q "c",~p "c">+- euro = # price of a european option on lattice c with payoff f ("c","f"). ~&H\~l"c" lfold ||-+"f",~&l+- ~&r; ~&i&& -+ \/div exp times/~r"c" ~dt "c", iprod/<~q "c",~p "c">+-\end{verbatim} \caption{implementation of a binomial lattice for financial derivatives valuation} \label{crt} \end{Listing} By way of a demonstration, the code is Listing~\ref{crt} is compiled by the command\begin{verbatim} $ fun flo lat crt.fun fun: writing `crt.avm' \end{verbatim} assuming it resides in a file named \texttt{crt.fun}. To see the concrete representation of the default binomial lattice, we display one with no user defined fields as follows.\begin{verbatim} $ fun crt --main="crr&" --cast _crr crr[ s: 1.000000e+02, v: 2.000000e-01, t: 1.000000e+00, n: 4, r: 5.000000e-02, dt: 3.333333e-01, up: 1.122401e+00, dn: 8.909473e-01, p: 5.437766e-01, q: 4.562234e-01, l: < [0:0: 1.000000e+02^: <1:0,1:1>], [ 1:1: 1.122401e+02^: <2:1,2:2>, 1:0: 8.909473e+01^: <2:0,2:1>], [ 2:2: 1.259784e+02^: <2:2,2:3>, 2:1: 1.000000e+02^: <2:1,2:2>, 2:0: 7.937870e+01^: <2:0,2:1>], [ 2:3: 1.413982e+02^: <>, 2:2: 1.122401e+02^: <>, 2:1: 8.909473e+01^: <>, 2:0: 7.072224e+01^: <>]>] \end{verbatim}%$ In this command, \verb|_crr| is the implicitly declared type expression for the record whose mnemonic is \verb|crr|. The lattice is associated with the field \texttt{l}, and is displayed as a list of levels starting from the root with each level enclosed in square brackets. Nodes are uniquely identified within each level by an address of the form $n:m$, and the list of addresses of each node's descendents in the next level is shown at its right. The floating point numbers are the same as those in Figure~\ref{binlat}, shown here in exponential notation. \subsubsection{Algorithms} Two pricing functions are exported by the library, one corresponding to Equation~\ref{amrec}, and the other based on the simpler recurrence \[ v_i^k=\left\{ \begin{array}{lll} f(S_i^k)&\text{if}&k=n-1\\ e^{-r\Delta t}\left(p v_{i+1}^{k+1} + q v_i^{k+1}\right)&\makebox[0pt][l]{\text{otherwise}} \end{array} \right. \] which applies to contracts that are exercisable only at expiration. The latter are known as European as opposed to American options. Both of these functions take a pair of operands $(c,f)$, whose left side $c$ is record describing the lattice model and whose right side $f$ is a payoff function. A quick test of one of the pricing functions is afforded by the following command.\begin{verbatim} $ fun flo crt --main="amer(crr&,max/0.+ minus\100.)" --cast 1.104387e+01 \end{verbatim}%$ The payoff function used in this case would be expressed as $ f(s) = \max(0,s - 100) $ in conventional notation, and the lattice model is the default example already seen. As shown in Listing~\ref{crt}, the programs computing these functions take a particularly elegant form avoiding explicit use of subscripts or indices. Instead, they are expressed in terms of the \texttt{lfold} \label{lfc} combinator, which is part of a collection of functional combining forms for operating on lattices defined in the \texttt{lat} library distributed with the compiler. The \texttt{lfold} combinator is an \index{lfold@\texttt{lfold}} adaptation of the standard \texttt{fold} combinator familiar to functional programmers, and corresponds to what is called ``backward \index{backward induction} induction'' in the mathematical finance literature. \subsubsection{The application program} \begin{Listing} \begin{verbatim} #import std #import nat #import flo #import crt #import cop usage = # displayed on errors and in the executable shell script :/'usage: call [-parameter value]* [--greeks]' ~&t -[ -s -t