\section{Evaluation}
\label{eval}

\subsection{Evaluation model}

The evaluation module encapsulates the concept of computation.  It
provides a model where all software is constructed of conduits
connected together for data to flow through.  A datum is a value in a
type.  Components in a conduit have a type specifier at each point
they can connect to another component, and types are checked when the
connection is made.  There are two parts of every connection: a source
and a sink.  You create sources out of functions or other input
providers, and you create sinks out of continuations or other
consumers of output.  Computation occurs when information is requested
from outside the system- such as from a user or a network request.  An
information request originates from a data sink and causes data to
flow from that sink's connected source, and the source's source
recursively.  

<<eval>>=
<<Set the current package>>
<<sources>>
<<sinks>>
<<switchboard>>
@ 
<<Set the current package>>=
(in-package :max)
@ 

\subsection{Data Sources}

Given a data source, you can get the set of all sinks connected to it.
To find out the definition of the data source, which will reveal where
the data actually comes from, you use introspection on the data
source.  There's no introspection of this sort in this iteration.
Data sources are typed and can only be connected with data sinks of
the same type.

<<sources>>=
<<sources type>>
<<operations on sources>>
<<function sources>>
@ 
Each data source is a value in the type containing all data sources.

<<sources type>>=
(defclass source-type (max-type) nil)
(defparameter *sources* (make-type :class 'source-type :key 'SOURCE))

;(add-init-hook #'(lambda () (add-name *sources* "sources")))

@

The value of a data source is a CLOS instance.  The different
kinds of data sources will have different classes of source values.
The classes all define a PULL method:

PULL performs a data request on a data source.  The Max function PULL
takes one source address and returns an object (value in the type
*objects*).  The object value will have a member type equal to the the
data source's type.  The LISP function PULL, implemented here, returns
the address in the appropriate type (not an Objects value).

<<operations on sources>>=
(defclass source ()
    nil
)
; (defgeneric pull ..) would go here if it was needed
@ 
\subsubsection{Function sources}

A function source is a source that was created using a function.  In
order to get a data source we have to specify all the arguments to the
function.  This is done by having a sink associated with the function
source, with the same type as the function's argument, and attaching
it to a data source, to use as the argument to the function.  The
output of the function source will vary depending on what source its
argument sink is connected to.

<<function sources>>=

(defclass function-source (source)
    ((argsink :accessor argsink :initarg :argsink)
     (func :accessor func :initarg :func))
)

(defmethod pull ((fs function-source))
    (function-apply (func fs)
      (if (argsink fs)
         (source-pull (function-apply *switchboard*
                    (make-address-form (source-type fs) (argsink fs))
         ))
         nil
      )
    )
)

(defun source-pull (sourceaddr)
    (pull (addr-value sourceaddr))
)

(defmethod source-type ((fs function-source))
    (function-codomain (func fs))
)

@ 

Given a function and a data source matching the type of the
function's domain, you can create a new data source
providing the function's return value.

<<function sources>>=
(defun make-function-source (funcaddr &optional (sourceaddr nil))
  (let ((sink (if sourceaddr (make-sink (function-domain funcaddr) sourceaddr) nil)))
    (make-address-form (addr-value *sources*) 
        (make-instance 'function-source :func funcaddr :argsink (addr-value sink))
    )
  )
)
 
@
\subsubsection{Thunk sources}

A thunk takes no argument and returns one value.  You can create
a data source given a thunk.  You can make a thunk out of an individual
value in a type, and use it as a constant data source.
Thunks are functions with a domain of *null-type* (see section \ref{null-type}.
Converting a thunk to a source is a special case of converting 
a function to a source: it's the same, except that no argument is
required to specify what data source to attach to the function
argument sink.

We've hacked the implementation of MAKE-FUNCTION-SOURCE to work with 
thunks- just leave off the source address.

\subsubsection{Input sources}

Input devices such as keyboards or mice appear in the system as
data sources.
 
\subsection{Data Sinks}

Each data sink is a value in the type containing all data sinks.
Given a data sink, you can find out if it is connected to a data source,
and if so, which source it is.  You can also change the sink to use
a different source.  Sinks are typed and can only be connected to
sources of the same type.

Sinks and sources are finite types.  There is no type containing all
possible sinks.  Instead, the types sources and sinks contain only
existing sinks and sources.

This could be an enumerated type.  Let's see if it works like this...

<<sinks>>=
(defclass sink-type (max-type) nil)
(defparameter *sinks* (make-type :class 'sink-type :key 'SINK))
;(add-init-hook #'(lambda () (add-name *sinks* "sinks")))

@


\subsubsection{Output sinks}

Output devices such as screens, printers, or sound cards appear in
the system as data sinks.

\subsubsection{Sinks as continuations}

In Scheme, a continuation takes one argument and does not return.  In
Max, a continuation would be obtained by taking a closure of a data
sink: everything after the sink in the system of conduits.  We don't
need first-class continuations in any early iteration..

\subsection{The switchboard}

The \emph{switchboard} is a function from sinks to
sources, indicating for each sink what source it is connected to (a
sink only has one source, while a source may be connected to multiple
sinks).  An evaluator uses the switchboard as the specification for
how to propagate information, and implements all necessary
computations to achieve the data flow to fulfill requests from the
sinks.

The switchboard is implemented as an enumerated function.
This is OK since the type of sinks is finite.
 
<<switchboard>>=
(defparameter *switchboard* 
    (make-function 'enumerated-function
        *sinks*
        *sources*
        (function-values)
    )
)
(add-init-hook #'(lambda ()
    (add-public-function *switchboard*)
    (add-name *switchboard* "switchboard")
))
@ 

\subsection{Creating a sink}

To create a sink, call MAKE-SINK and pass it the type of sink to make, and
a source to connect this sink to.

Throws an exception 'TYPE-MISMATCH if the type specified does not
match the type of the source.

<<sinks>>=
(defclass sink () nil)

(defun make-sink (type sourceaddr)
  ; Typecheck
  (if (not (eq (source-type (addr-value sourceaddr)) type))
      (throw 'type-mismatch nil))

  (let ((sink (make-address-form (addr-value *sinks*) (make-instance 'sink))))

    (function-change-2 (function-implementation *switchboard*) sink sourceaddr)
    sink
  )
)
@ 

\subsection{Conduit types}

Conduit types are types that provide more than one source or sink.
Usually they provide a single source and sink pair, but more 
complicated structures are possible.

\subsubsection{Pointer conduits}

A pointer has one data sink, to store a value in it, and one data
source to read its value.  As such, pointers are used to store
intermediate results of computations.  You can insert a pointer
between any source/sink pair to store the value at that point in the
computation and make it addressable
(See section \ref{ptr}).

\subsubsection{Network conduits}

A network connection forms a data sink, a data source, or both.
Early iterations will not have networking!

\subsection{Evaluation}

Given one source and one sink that carry the same data type, you can
connect them together using the switchboard: this changes the results
of the sink's function saying what source it is connected to, and the
source's function saying what set of sinks it is connected to.

Actually, since a sink must always be connected to one source, the
connection is made at the time the sink is created.  The evaluator
then provides an interface to be used by sinks, while the function
returning a particular type of sink will require an argument
specifying what source it is to be connected to.

The conduit has a current value.  
  The
current value is the data from the source that is made available to
the sink.

\subsection{Mutual Exclusion}

A data sink can be connected to only one data source at a time.  If a
source wishes to use a sink that is already connected to another source,
the connection can be changed (switched) in the switchboard.  A request
for such a change may be delayed if a computation is in progress.

Components can be designed that provide sharing for a sink by
exporting multiple sinks and switching the shared sink between the
component's sources according to some specification that makes sense.

This iteration has no such sink-sharing component.

\subsection{Programming Styles}

Functional style is turning functions and thunks into components
and creating conduits from them, perhaps storing the result in a
pointer or sending it to a data sink attached to a terminal.

Procedural style is connecting a data sink and source temporarily
for the duration of one data request.

Declarative style is specifying the type of the result you wish and
using an automated search for a series of functions that can be
combined to result in that type.  Use the domain and codomain functions
on the public types to perform the search.



\subsection{Current implementation}

The implementation requires a bottom-up construction of expressions
since we have the requirement that a sink be connected to one source
at all times.  A good construction interface (external to this module)
would present pieces of expressions and allow the user to combine them
in any arbitrary order, then when the expression is ready to be
evaluated, perform a bottom-up construction using the API defined
here.

The expressions, once built, can be evaluated by calling (PULL)
from LISP.  While this meets the basic functionality requirement
for the first iteration, it is intended that data sinks be created
that continually update an expression on the screen, for instance.

\subsection{Future direction}

Later versions should work toward the eventual goal of describing the
entire Max implementation using the switchboard, and connecting the
max interfaces defined in other modules to an evaluator representing
the lower-level VM that Max is implemented on.

The evaluator will take a particular switchboard layout and translate
it to some lower-level system so that the data flows as specified.
The implementation is free to use any means available to perform this
task: Dynamic compilation is suggested.  There will be a wealth of
information available to use by the evaluator for optimization.