[FOM] Computer Scientists visa vie Mathematicians - "constructors"

[Dennis E. Hamilton]

Lawrence Paulson wrote:

> It might help if more mathematicians were familiar with some basic
> principles of computer science.

Patrik Eklund wrote:

 > I agree, but I would like to add that it also might help if computer 
scientists were familiar with some basic principles in mathematics.

> [...] Mixing languages and bringing in things from the outside is very 
> typical in computer science, but very dubious in mathematics. A typical 
> example of bringing in things from the outside is the function type 
> constructor. Where does it come from? Did it come from the same factory as 
> the types?

I sense a misunderstanding here, and it has to do with the way levels of 
abstraction are managed in computer science and engineering.  I would like to 
unpack that.

First, an apology.

There have been some appropriations of language in computer science and in the 
practice of computer programming that create confusions with respect to 
mathematical notions.  It began with use of "function," "integer," and "real" 
to designate computational notions.  This has continued with use of "type," 
"object," "class," "structure," and even "set."  The replacements "procedure," 
"int," and "float" are preferable but we seem to be stuck with "function."

This sort of collapse/corruption of ideas did not start with programming 
languages.  Engineering and related technical activities had relied on 
mathematical formalisms as expressions interpreted as computations, along with 
the art of numerical analysis, prior to the digital-computer era.   It was 
appealing to the intended developers of technical and engineering computations 
that languages such as 1953's Fortran delivered algebraic-formula and 
trigonometric calculations into the hands of technical users other than the 
heads-down, assembly-language computer programmers of the time.

Considering the popular notion of "maths," it should be no surprise that 
people who become immersed in software development and computer applications 
associate mathiness with their actually-computational notions, because of some 
commonality of expression and nomenclature.  There is, for example, the idea 
of Objects as *distinguished* instances of members of a Class and the 
prevalent conceit that the computational class objects correspond to entities 
in reality.  A sort of Platonic Computerism.

              - - - - - - -

With regard to the layers of abstraction and the apparent bringing things in 
from the outside, a simple view of computation demonstrates what that is 
grounded in.   Consider a function ap(pr, xr) which we can take of having type 
r * r -> r, where r is a denumerable base type, such as strings over some 
alphabet or maybe some other sort of composed but canonically-named data 
structure that can be recorded on persistent electronic storage, read from 
inputs, printed on paper, etc.

Let expression ap(pr, xr) have computational interpretation consisting of 
taking the operand pr as the script for an algorithmic procedure and xr as the 
operand to which that procedure is applied.  We have the same base type, r, 
for representing both scripts and data.  Now consider

applicative expression        ap(ap(ap(sr, fr), gr), xr) = ap(ap(fr, xr), 
ap(gr, xr)).

Here is demonstration of the stored-program principle where scripts and data 
are of the same kind and one can derive new scripts from scripts as data. 
There is a relationship between that expression and the

mathematical expression  s(f, g, x) =  f( x, (g( x) ) also written f(x) (g(x))

where, with respect to -> as application, the evaluation of the applicative 
expression preserves representation of functional type, with x of some type X, 
g of type X -> Y, f of type (X -> (Y -> Z)), and s of type ( ((X -> (Y -> 
Z)) -> ( (X -> Y)  -> (X -> Z) ).   This is an emergent condition, not 
determined by ap itself but by the careful expression of sr, fr, gr, and xr. 
Programming-language compilers make assurances of that and reflect the 
necessary restrictions in the computer program that is produced.

At the ap(pr, xr) level, the evaluation of the applicative expression could 
all be done by rewriting, making a new intended-to-be-a-script result under 
guidance of script pr.  Function such as ap(pr, xr) could be specified in that 
way, and often are.  It is not essential in practice, so long as the result is 
indistinguishable from having done so (and it is engineering of that pragmatic 
validity which bridges the digital computer and mathematics).

Rewriting is avoided in practice by creating forms that are immutable and not 
rewritten, but which are bound to different environments, the contexts of 
individual evaluations.  The bindings are often called closures.  The closures 
are passed as parameters and correctly-connected at the time of operational 
need.  This operates at the time of application of the associated script to 
further operands.  So ap(sr, fr) can be achieved by returning a closure that 
ties to the specific fr for use when needed in an eventual ap(fr, xr), making 
closure fxr that can be used in ap(fxr, ap(gr, xr)), etc.

Notice that we have at the outset a means of representing higher-order 
functional types and it is inherent in the stored programming model of today's 
general-purpose computers.   It should also be clear that "construction" and 
"constructor" are at a different level than the level of expression I just 
characterized.  Similarly, "factories" are at a lower-level of operation, tied 
into the operation of particular programming platforms.  Such facilities are 
part of the internals in the derivation of scripts (computer codes) and their 
execution by directing the attention of the computer's instruction processor. 
Sometimes there a manifestations of construction exposed at the 
programming-language level.  I will say no more on that.

An example of the kind of situation in a higher-level programming notation 
that is resolved using closures (famously called "thunks") is something like 
this:

|  let A(k, c1, c2, c3)
|      = let B() = A(k-1, B, c1, c2)
|          in if k < 1 then c2() + c3() else B()
|   in let x1() = 1,
|             x2() = -1,
|             x3() = 0
|         in A(10, x1, x2, x3)

The definition of functions with nil operands is a computerism for governing 
point of evaluation, distinct from points of definition/mention.  It can be 
taken as  a place where a closure is constructed in the running program, but 
that need not be dealt with explicitly by the programmer.

The reconciliation of bindings is in the c2 and c3 that are involved when 
c2()+c3() is finally evaluated in an instance of B( ) and the instances of B 
those are bound to, their instances of A, etc.  This contrived example is 
derived from an even trickier one by a computer-scientist contemporary who is 
renowned for his reliance on mathematics and who did derive a direct 
closed-form for his version,
<https://en.wikipedia.org/wiki/Man_or_boy_test>.

 - Dennis