\section{Functions}
\label{function}

The concept of \emph{information} is encapsulated in functions.
Information is the meaning of values in a type; or ways to get from a
value in one type to a value in another.  Functions enable these
transitions.  Max functions are \emph{pure} functions as defined in
mathematics.  A pure function is one which has no \emph{side-effects}.
A side-effect is a change to the system.  Pure functions contain no
variable assignments and no I/O.  We will discuss how to perform
variable assignments and I/O in later sections.

A function is a mapping from one type, called the domain, to another,
called the codomain.  This means for every value in the domain
(argument), the function associates it with one value in the codomain
(return value).  Values in the codomain can be used more than once, and
some values might be unused (however, all values in the domain must be
used).  The actual subset of values in the codomain that the function may
return is called the range.

There are currently two implementations of functions in Max:
enumerated functions and builtin functions.  Other kinds of functions
will be added in the future.

<<function>>=
<<Set the current package>>
<<Define a class for the type of functions>>
<<Create the address of the type of functions>>
<<Create the class of functions>>
<<Get the instance implementing a function given its address>>
<<Enumerated functions>>
<<Apply a function>>
<<Quotient a function by an address>>
<<Create a Max function>>
<<Builtin functions>>
<<Domains and codomains>>
<<Identity functions>>
@ 
<<Set the current package>>=
(in-package :max)
@
The type of functions has some special characteristics so we 
implement it using its own class derived from the class of types.

<<Define a class for the type of functions>>=
(defclass function-type (max-type)
        nil
)
@ 

We create the address of the type of functions here.   
[[(addr-value *functions*)]] will go in the "type" field of
function addresses.

<<Create the address of the type of functions>>=
(defparameter *functions* (make-type :class 'function-type :key 'FUNCTION))
(add-init-hook #'(lambda () (add-name *functions* "functions")))
@ 
Create the CLOS base class of all max function implementations.
An instance of a subclass of this class is stored in the value slot of the function address.
Every function has a mapping, so this class defines a slot called ``mapping.''
This slot will contain something totally different depending on which
subclass is instantiated, since the different classes of functions have
different ways of implementing the mapping.

<<Create the class of functions>>=
(defclass function-class ()
        ((mapping :accessor mapping
                :initarg :mapping
        ))
)
@ 

A function address has a type field referring to the *functions* type,
and a value field containing an instance of a class derived from
function-class.

Given the Max function address of a function, return the CLOS object implementing
the function.  The instance is currently stored in the value field of
the function address.
<<Get the instance implementing a function given its address>>=
(defun function-implementation (funcval)
        (third (addr-value funcval))
)

@ 
\subsection{Domains and Codomains}

Functions are strongly typed, meaning the types
for a function's domain and codomain are required to be specified
when the function is defined.  

There are two standard Max functions, DOMAIN and CODOMAIN,
that return the domain or codomain of any Max function.  They 
are implemented as enumerated functions.  When any
function is created, the mappings of DOMAIN and CODOMAIN 
are automatically updated with definitions for the new function.
This leads to some difficulties both creating the DOMAIN and CODOMAIN
functions, and accessing them from LISP.
<<Domains and codomains>>=
<<Bootstrap the domain and codomain functions>>
<<Publish the domain and codomain functions>>
@

Bootstrap the domain and codomain functions--we can't call
MAKE-FUNCTION since it adds to the domain and codomain functions.

<<Bootstrap the domain and codomain functions>>=
(defun function-domain (func)
    (make-address-form (addr-value *types*) (first (addr-value func)))
)

(defun function-codomain (func)
    (make-address-form (addr-value *types*) (second (addr-value func)))
)
(defparameter *domain* (make-function 'builtin-function 
    *functions*
    *types*
    #'(lambda (func)
       (function-domain func)
    )
))
(defparameter *codomain* (make-function 'builtin-function
    *functions*
    *types*
    #'(lambda (func) (function-codomain func))
))
@
<<Publish the domain and codomain functions>>=
(add-init-hook #'(lambda ()
    (add-public-function *domain*)
    (add-public-function *codomain*)
    (add-name *domain* "domain")
    (add-name *codomain* "codomain")
))
@ 
\subsection{Applying functions}

FUNCTION-APPLY takes the address of a function, and the address of a value
in its domain, and returns the value from the codomain as specified by the
function's definition (mapping).

This function is to be called APPLY in Max, but is renamed in LISP to
prevent a clash with LISP's APPLY.

For applying thunks (functions with no argument), pass NIL for param.
<<Apply a function>>=
; Apply a function to param and return the address of the result.
; Wrap apply-address, a generic function
(defun function-apply (funcaddr param)
    (apply-address
        (function-implementation funcaddr) 
        param      ; assume domain is prechecked
    )
)

@
APPLY-ADDRESS is an internal method used by FUNCTION-APPLY
to dispatch based on the class of function being applied.

The ``func'' argument is the instance implementing
the function.

The ``param'' argument is the address being applied.

It finds the return value of the function and returns it.

We could put a DEFGENERIC for APPLY-ADDRESS here but it's optional so
we'll leave it implicit.
@ 
\subsection{Quotient}

QUOTIENT will be a Max function that takes the address of a Max
function and the address of a value in its \emph{codomain}, and
returns the Max set of values in the domain that return that value.
The set will be empty if the value specified is in the codomain but
not in the range of the function.  Sets are defined in section
\ref{sets}.

The LISP implementation is called FUNCTION-QUOTIENT for consistency
with the other FUNCTION-* functions in this module, although QUOTIENT
is not a function in LISP so it could be used.

Like all the other functions in this module, we do no type checking whatsoever,
assuming it is done by the caller.  In LISP this will be the tester calling the
LISP implementations, but in Max type checking is done early.  See Evaluation,
section \ref{eval}.

<<Quotient a function by an address>>=
(defun function-quotient (func_addr result_addr)
        (let ((quotient (get-empty-set))
              (divisor (addr-value result_addr)) 
              (dom (function-domain func_addr)))

                (maphash
                        #'(lambda (key val)
                                (if (addr-value-equal dom divisor val)
                                        (setf quotient (set-add quotient
                                                (make-address-form dom key)
                                        ))
                                )
                        )

                        (mapping (function-implementation func_addr))
                )

                quotient
        )
)
@ 

The type of the second argument is equal to the domain of the first
argument.  Since we have no way to express this constraint directly in
the types of the arguments, we'll do a hack that works for now: The
Max version of function-quotient will take the original function and
return a ``quotienter'' function that takes a value in the codomain and
returns the quotient set.  An alternate approach would be to make the
second argument type *objects* and do run-type type checking, but
that's an inelegant solution.  The first hack is elegant enough, and
if necessary, later we should be able to write a constraint system
that can describe restrictive relationships between argument values
(especially ones that are functions).

<<Quotient a function by an address>>=
(add-init-hook #'(lambda ()
    (let ((function-quotient
            (make-function 'builtin-function *functions* *functions*
                #'(lambda (func)
                    (make-function 'builtin-function 
                        (function-codomain func) *set-type*
                        #'(lambda (divisor)
                            (function-quotient func divisor))
                    ))
            )))

        (add-public-function function-quotient)
        (add-name function-quotient "quotient")
    )
))
@ 
\subsection{Creating functions}

MAKE-FUNCTION creates an enumerated or builtin function.

class: The symbolic name of the class of function to make:
  either 'ENUMERATED-FUNCTION or 'BUILTIN-FUNCTION.  

mapping: initializer for the :mapping slot of CLASS FUNCTION-CLASS.
  For enumerated, use a hash table, while for builtin, it is a lambda.

domain and codomain: Max addresses of the types which are this function's 
domain and codomain.

key: symbolic name of this function to use as key in the *functions* hash
Now optional so unnamed functions can be made.
<<Create a Max function>>=
(defun make-function (class domain codomain mapping &optional key)
        (let* ((obj (make-instance class :mapping mapping))
                (addr (make-address-form (addr-value *functions*) (list (addr-value domain) (addr-value codomain) obj))))

                addr
        )
)
@ 
\subsection{Enumerated functions}

Enumerated functions have finite domains and codomains, defined by an
explicit set of tuples.  You cannot use a set [set.lsp] of tuples
(values in a product type) to create a function, yet, but you will be
able to eventually.

You can modify an enumerated function using FUNCTION-CHANGE to specify
a new pair of values.  This should change at some point to be more like
sets (section ?%\ref{sets}
) to create a new function based on an old one and leave the old one
untouched.
@

<<Enumerated functions>>=
<<Define the class of enumerated functions>>
<<Define comparison of two enumerated functions>>
<<Apply an enumerated function>>
<<Helper for changing enumerated functions>>
<<Create mappings using LISP symbols>>
<<Change one value pair using literal arguments>>
<<Change one value pair using symbolic arguments>>
@ 
The implementation of enumerated functions uses a hash table to store 
an explicit map of values.  The hash table is stored in the ``mapping'' slot
defined by the base class, FUNCTION-CLASS.
<<Define the class of enumerated functions>>=
(defclass enumerated-function (function-class)
        ; Use accessor and initarg from parent for this slot
        ((mapping :type hash-table))
)
@ 

If ``a'' and ``b'' are enumerated functions, they are equal if and
only if their CLOS instance is the same object (EQ).

<<Define comparison of two enumerated functions>>=
(defmethod addr-value-equal ((f enumerated-function) a b)
        (eq a b)
)
@
Specify how to apply an enumerated function (get the
result given the argument): Look it up in the hash table.

This method is the specialization of APPLY-ADDRESS for
enumerated functions.
<<Apply an enumerated function>>=
(defmethod apply-address ((func enumerated-function) param)
    (make-address-form
        (addr-type param)
        (gethash (addr-value param) (mapping func))
    )
)
@ 
FUNCTION-CHANGE-HELPER modifies one key/value pair
in the hash table of an enumerated function.  

h is a hash table

x is a dotted pair of symbols bound to Max addresses.
(See FUNCTION-VALUES)

The function definition is updated with the new
tuple, either creating or changing the mapping for
the first address, so that the function will
return the second address.
<<Helper for changing enumerated functions>>=
(defun function-change-helper (h x)
        (setf (gethash (addr-value (symbol-value (car x))) h)
                (addr-value (symbol-value (cdr x))))
)
@

FUNCTION-VALUES creates the "mapping" part of a function definition
for an enumerated function.  Arguments are any number of dotted pairs
of symbols bound to Max addresses.  Returns a hash table suitable for
the implementation field of a function.  Then to create the enumerated
function, pass this hash table to MAKE-FUNCTION as the ``mapping''
argument.  See the boolean module for examples of use.

<<Create mappings using LISP symbols>>=
(defun function-values (&rest args)
        (let ((h (make-hash-table)))
                (map
                        nil
                        #'(lambda (x)
                                (function-change-helper h x))
                        args
                )
                h
        )
)
@ 

FUNCTION-CHANGE changes an enumerated function in-place.

Tup is '(arg . value), so use FUNCTION-CHANGE when you have literal arguments.

The supplied function's definition is updated with the new pair.  If the
argument key was already in the function, its associated value is changed;
otherwise the key,value pair is added to the definition.

The return value is undefined.
<<Change one value pair using literal arguments>>=
(defmethod function-change ((func enumerated-function) tup)
        (let ((h (mapping func)))
                (function-change-helper h tup)
        )
)
@
FUNCTION-CHANGE-2 is like function-change, but for symbolic arguments.

<<Change one value pair using symbolic arguments>>=
(defmethod function-change-2 ((func enumerated-function) arg result)
        (let ((h (mapping func)))
                (setf (gethash (addr-value arg) h)
                        (addr-value result))
        )
)
@
\subsection{Builtin Functions}

Builtins are implemented in LISP but take Max addresses as arguments
and return Max addresses, so they can be called from Max.
<<Builtin functions>>=
<<Define the class of builtin functions>>
<<Define function application on builtin functions>>
@ 
For builtins, the :mapping slot inherited from function-class
is a LISP function.
<<Define the class of builtin functions>>=
(defclass builtin-function (function-class)
        ((mapping :type function)) ;store a lambda expression
)
@
Call LISP's apply on the LISP function stored in the mapping slot
to determine the return value of a builtin function.
<<Define function application on builtin functions>>= 
(defmethod apply-address ((bf builtin-function) arg)
        (apply (mapping bf) (list arg))
)

@ 

\subsection{Identity functions}

An identity function for a type takes any value in that type
and returns the same value.

IDENTITY-FUNCTION below can return an identity function for any type.
LISP defines the function [[IDENTITY]] so we use the longer name:

<<Identity functions>>=
(defun identity-function (type)
        (make-function 'builtin-function type type
                #'(lambda (addr) addr))
)