Version 1.1 of acs/ac-00274.txt

Unformatted version of acs/ac-00274.txt version 1.1
Other versions for file acs/ac-00274.txt

!standard 3.10(0)          16-01-07 AC95-00274/00
!class Amendment 16-01-07
!status received no action 16-01-07
!status received 15-11-20
!subject First-class functions
!summary
!appendix

!topic First-class functions
!reference Ada 2012 RM3.10 and RM8.2
!from Hadrien Grasland 15-11-20
!keywords function first-class callback GUI events
!discussion

This comment stems from a short exchange with Randy Brukart on comp.lang.ada,
which I thought was interesting enough to be brought to the attention of the
ARG. For reference :

https://groups.google.com/forum/#!topic/comp.lang.ada/ebIwPljP0-o

My proposal is that it should be possible to manipulate subprograms, including
all the surrounding state that comes with them, as values that can be stored and
returned. This has traditionally been a distinguishing feature of functional
programming languages, but is now also possible in recent releases of many
popular imperative languages such as C++11, Java 8 or C# 3.0.

The concept is distinct from that of an access-to-subprogram because one cannot
simply take a pointer to a nested subprogram and store it in a container in Ada
for an excellent reason : it would end up dangling. This dangling function
pointer problem is precisely what first-class functions as a programming
language feature address.

======

There are countless applications to first-class functions, but when programming
in an imperative style, I believe they prove most useful when implementing
callbacks. Often, the most elegant place to write a callback is indeed at the
point where said callback is bound to its target, because this is where all the
information needed to write the callback is available.

When callbacks are written as closures, it allows them to have much simpler
signatures (e.g. no need to repeat which object the callback refers to), which
in turn dramatically cleans up the library's interface and makes it easier to
transparently implement higher-level abstractions at a later point.

For example, the OpenCL API has callbacks that takes raw object identifiers as
parameters, in a true C tradition. But in a C++11 wrapper which I'm currently
writing for this API, it is instead possible to directly manipulate
captured-by-value higher-level OpenCL object wrappers inside of callbacks. As a
result, code becomes easier to understand, without a need to change the
underlying OpenCL API. Without the addition of std::function in C++11, this
would have been much harder for me to implement in an elegant way.

Ad-hoc replacements to closure-based callbacks tend to be very ugly, typically
involving such horrors as defining an unwieldly functor class or combining a
global function with a global state container, then using library-provided
callback parameters in order to fetch back the container contents associated to
a specific callback target. The later solution can quickly become a
maintainability nightmare in the presence of concurrency and parallelism...
which is precisely the typical reason why callbacks are introduced in a library
to begin with.

Would you agree that callbacks alone, a very common abstraction of concurrent
and GUI programming, would make the addition of first-class functions to a
future release of Ada worthwhile ? Or would you like me to provide additional
motivation for such a new data type ?

***************************************************************

From: Randy Brukardt
Sent: Friday, November 20, 2015  6:14 PM

...
>Would you agree that callbacks alone, a very common abstraction of concurrent
>and GUI >programming, would make the addition of first-class functions to a
>future release of Ada worthwhile ? Or would you like me to provide additional
>motivation for such a new data type ?

For me personally, the answer is no. Callbacks are a form of spaggeti-code
programming, best avoided. And my experience is that OOP features are a very
viable way of handling GUI programming, where overridding is used to define the
needed state and actions for the GUI. (Claw is based completely on this model,
and it works well in my experience. The glitches that exist have more to do with
our nonlimited programming model than the OOP design.)

Anyway, the ARG typically wants problems that are too hard or painful to solve
with existing Ada, not half-baked solutions without an obvious problem. We're
perfectly capable of coming up with half-baked solutions. :-)

I don't doubt that you can find such problems, but simply saying that you can't
copy the style of some other programming language doesn't cut it. In many cases,
the Ada solution to a problem is better on one or more dimensions, so we're not
necessarily looking to copy the capabilities of other languages.

Technically, I don't understand what you're proposing. You talk about dangling
pointers as if there is some way to get rid of them! Ada already provides
anonymous access-to-subprogram types that can pass nested subprograms. It's easy
to imagine extending that feature to named types, but in such a case dangling
pointers are going to be possible and it would have to be the programmer's
responsibility to prevent trouble.

OTOH, if you're suggesting that somehow saving a nested subprogram would prevent
its enclosing subprogram from being left (so that the nested data would not be
dangling), I don't see that ever happening. It would mean that the cheap
stack-based memory management of Ada would no longer be possible (in general),
and that would be a non-starter for the limited safety critical systems that
form the backbone of current Ada usage. (Can't abandon your current customers to
chase others, lest you end up with none.) I also don't see how to reconcile that
with the normal semantics of leaving and finalizing the data of a subprogram.
One could prevent the subprogram from returning until the subprogram reference
is destroyed (as we do for tasks), but that would make it difficult to program
in a single-threaded context (and multithreaded programs are still way too hard
to get right to insist on using them).

So I'd like both a better problem statement (since many of us have been writing
callbacks in Ada for years, saying that we need to be able to do so is vacuous)
and a better explanation of how the proposed solution works and is different
than the capabilities we already have.

***************************************************************

From: Jeffrey R. Carter
Sent: Friday, November 20, 2015  6:25 PM

> For me personally, the answer is no. Callbacks are a form of
> spaggeti-code programming, best avoided. And my experience is that OOP
> features are a very viable way of handling GUI programming, where
> overridding is used to define the needed state and actions for the
> GUI. (Claw is based completely on this model, and it works well in my
> experience. The glitches that exist have more to do with our
> nonlimited programming model than the OOP design.)

Both approaches are a form of spaghetti-code programming IMO, because they're
sequential solutions to an inherently concurrent problem. Ada is a concurrent
language and we should be using concurrent solutions to concurrent problems:
tasks in the libraries, tasks in the applications, and communication channels
between them.

So my 2 is no, we don't need a mechanism to make sequential solutions to
concurrent problems easier to write.

***************************************************************

From: Hadrien Grasland
Sent: Saturday, November 21, 2015  8:25 AM

> So my 2 is no, we don't need a mechanism to make sequential solutions to
> concurrent problems easier to write.

So in effect, you would suggest to solve problems which are typically addressed
using callbacks in language without built-in tasking support, by instead
leveraging Ada's protected objects as event listeners, then dynamically binding
application-defined tasks to them as event handlers ?

That's an interesting track of thought. It may not always be applicable when
interfacing with non-tasking libraries and APIs, but in the case of OpenCL
(since it's the example I brought to begin with), it could work because the spec
was designed well enough to allow a caller to transmit an arbitrary pointer to
the callback function, which in turn may be used to do the protected method
calling. And I believe that if you don't have this powerful feature in your
callback design, you couldn't use closures either anyway. Thus, point taken :)

> Anyway, the ARG typically wants problems that are too hard or painful to
> solve with existing Ada, not half-baked solutions without an obvious
> problem. We're perfectly capable of coming up with half-baked solutions. :-)

> I don't doubt that you can find such problems, but simply saying that you
> can't copy the style of some other programming language doesn't cut it. In
> many cases, the Ada solution to a problem is better on one or more
> dimensions, so we're not necessarily looking to copy the capabilities of
> other languages.

Of course. I mostly wanted to raise this question because being able to
manipulate functions as values is becoming a de facto standard programming
language functionality these days, and thus I would expect Ada newcomers to be
unconsciously looking for it in a couple of years. Much like in the past,
recursion became a standard programming language feature at some point, as it
became obvious that it was by far the most elegant way to implement some
algorithms like quicksort and tree traversal.

My viewpoint, after some time learning functional programming, is that
first-class functions are a pretty neat abstraction, which like recursion allows
some problems to be solved more elegantly. However, it seems my callback example
was certainly not convincing, so I will try to think of better use cases :)

In any case, due to the funarg problem, there are many possible first-class
function implementations, each with a different set of tradeoffs, and I would
expect an Ada version to match Ada's general design goals. I am certainly not
suggesting to copy and paste an existing design, without any thought given about
how well it would fit in Ada's general design.

> Technically, I don't understand what you're proposing. You talk about
> dangling pointers as if there is some way to get rid of them! Ada already
> provides anonymous access-to-subprogram types that can pass nested
> subprograms. It's easy to imagine extending that feature to named types, but
> in such a case dangling pointers are going to be possible and it would have
> to be the programmer's responsibility to prevent trouble.
>
> OTOH, if you're suggesting that somehow saving a nested subprogram would
> prevent its enclosing subprogram from being left (so that the nested data
> would not be dangling), I don't see that ever happening. It would mean that
> the cheap stack-based memory management of Ada would no longer be possible
> (in general), and that would be a non-starter for the limited safety
> critical systems that form the backbone of current Ada usage. (Can't abandon
> your current customers to chase others, lest you end up with none.) I also
> don't see how to reconcile that with the normal semantics of leaving and
> finalizing the data of a subprogram. One could prevent the subprogram from
> returning until the subprogram reference is destroyed (as we do for tasks),
> but that would make it difficult to program in a single-threaded context
> (and multithreaded programs are still way too hard to get right to insist on
> using them).

What you are discussing here is the funarg problem which I referred to above.
Nested subprogram declarations exist within a scope (or "environment"), and if
we want to return these nested subprograms as function results, or otherwise
keep them around after the enclosing subprogram has finished execution, it
raises the question of what should be done with that environment, in order to
ensure that our first-class function objects never refer to dangling pointers
and values.

This is a difficult abstraction design problem, and so far each programming
language has come with a subtly different approach to it. Some examples:

 * In scripting languages, variables are allocated on the heap, and garbage
   collection and reference counting may be used. This is the simplest way to
   deal with the funarg problem, but it would obviously not fit within Ada's
   design due to its inefficiency and heavy runtime requirements.

 * In Java and the ML family, relevant parts of the enclosing scope are copied
   into the function object so as to make it self-sufficient. This means that if
   these variables change later on, the serialized function will not reflect
   these changes, which can lead to surprising behavior. In both of these
   languages, this is adressed by either a hard requirement (Java) or strong
   recommendation (ML) that captured variables be immutable.

 * In C++, as usual, no strong design standpoint is favored. You can capture a
   function's scope by reference, in which case it is your responsibility to
   ensure that it doesn't dangle, or you can capture it by value, in which case
   you must accept the extra overhead and remind yourself that serialized
   function objects will not take further changes to their enclosing scope into
   account.

In my view, the Java/ML solution is the one which would match Ada's design goals
best. Following the spirit of Ada's accessibility rules, it ensures that a
serialized function object, when called, cannot refer to a non-local variable
that doesn't exist anymore because the underlying stack frame has since been
destroyed.


Of course, this solution would still need to be adapted in order to fit Ada's
design, for example by complementing it with extra language restrictions on what
kind of values a function object may capture. Otherwise, we could still end up
referring, though access values, to silly things like tasks which do not exist
anymore.

> So I'd like both a better problem statement (since many of us have been
> writing callbacks in Ada for years, saying that we need to be able to do so
> is vacuous) and a better explanation of how the proposed solution works and
> is different than the capabilities we already have.

So let me give it another try ! *sharpens virtual pencil*

Inspired by functional programming practices, a growing number of programming
languages these days allow for functions (more rigorously subprograms in Ada
terms) to be manipulated as first-class values. That blanket statement
translates into a number of key language features, several of which Ada already
has :

 * Functions may be passed as an argument to other functions
 * Functions may be declared inside of functions
 * Functions may be returned as a result of another function
 * Functions may be stored into variables and containers, then passed around

Ada already support the first two of these programming scenarii, which have
well-accepted benefits : anonymous access-to-subprograms are the single most
powerful and elegant way to implement user-defined behavior, such as container
filters, and nested subprogram declarations allow for subprograms to be a lot
more concise and understandable since the subprograms can refer to their
enclosing scope instead of taking gazillions of parameters.


Being able to return functions as results has a number of nice applications,
that can only be reproduced with objects at the cost of writing tons of
boilerplate code. Here are a couple of examples :


 * Partial function application (when a library function has too many parameters
   for your needs and you want to specialize it)
 * Function composition
 * Low-overhead implementations of the Strategy pattern (when a strategy is
   selected once and for all early on, and the rest is function calls)
 * Lazy evaluation (see below)

Since lazy evaluation has gotten a lot of bad press recently, due to the way it
is sometimes abused in problems where its overhead is not needed, I believe it
deserves a list of bullet points on its own. So here are a few problems for
which I believe lazy evaluation is a good fit :

 * Partial exploration of infinite or near-infinite data sets (e.g. decision
   trees in AI programs)
 * Integrand evaluation in adaptative numerical algorithms like Gaussian
   quadrature
 * In general, production of "virtual" datasets whoses size is either unknown in
   advance or constantly changing

To implement this function-as-a-result concept, one also needs variables that
can store function objects, for obvious reasons : a functional function result
is no good if you have no place to store it and save it for later. Which leads
us to the funarg problem which Randy mentioned above, and whose popular answers
I tried to summarize in my reply.

***************************************************************

From: Hadrien Grasland
Sent: Sunday, November 22, 2015  4:19 AM

I believe my last e-mail was a bit lacking when it comes to syntax mockups, so
let me propose a prospective Ada syntax for the classical problem of data
interpolation.

In mathematical terms, to interpolate a data set does not really mean to take an
array of values from this data set, and turn it into another array of values. It
means to start from a table of values, and produce a function which goes through
the provided data points and matches certain properties inbetween (for example
being continuous, or having a continuous derivative).

This function may, in turn, be itself tabulated, but that should not be the
concern of an interpolation routine. The goal of mathematical interpolation is
to produce a function, not a discrete data set. If you want a table of the
resulting function, you can build it yourself later on.

Here's a syntax mockup of what such mathematically accurate data interpolation
could look like in Ada if Ada had function objects. For simplicity, I will only
consider regularly spaced data sets, and use the standard data types (Float,
Integer, etc).

======

type Float_Array is array (Integer range <>) of Float;

type Float_Function_Table is
...record
......Values : Float_Array;
......Origin : Float;
......Dx : Float;
...end record;

type Unary_Float_Function is function (X : Float) return Float;


function Linear_Interpolation (Table : Float_Function_Table) return Unary_Float_Function is

...function Interpolant (X : Float) return Float is
......subtype Table_Index is Integer range Table.Values'First .. Table.Values'Last;

......Effective_Index : constant Float := (X - Table.Origin) / Table.Dx + Table.Values'First;

......First_Lookup_Index : constant Table_Index := Table_Index (Float'Floor (Effective_Index)));
......Second_Lookup_Index : constant Table_Index := Table_Index'Succ(First_Lookup_Index);

......First_Weight : constant Float := Effective_Index - Float (First_Lookup_Index);
......Second_Weight : constant Float := 1.0 - First_Weight;
...begin
......return First_Weight * Table.Values (First_Lookup_Index) + Second_Weight * Table.Values (Second_Lookup_Index);
...end Interpolant;

begin

...return Interpolant;

end Linear_Interpolation;

======

As you can see, all the magic happens at line 31, where the Interpolant inner
function is returned. To manage this, an implementation would need to pack
together in a single function object...

 * A pointer to a modified variant of the Interpolant function, which takes its
   Table environment variable not from the enclosing stack but from a data
   block.
 * An instance of said data block type, where a copy of Table is stored.

As far as I can see, this technique could be applied to any environment variable
which is not of a limited type. For limited types, the only reasonable decision,
in my opinion, is for the implementation to reject the code.


Also note that there is a lot of opportunities for performance optimization in
making the right choice of function object representation. Whenever feasible, a
representation which could avoid making the deep copy mentioned above would
certainly have strong performance advantages over a naive one where function
object creation proceeds as I described above. This needs not concern users of
the function object functionality, though, as long as the resulting function
object behaves as if a copy of the underlying environment had been made.


Does this help clarify what I have in mind ?

***************************************************************

From: Hadrien Grasland
Sent: Sunday, November 22, 2015  4:19 AM

There is no such thing as enough code proofreading :)

Lines 23-24 of my code example, the interpolation weighting is off. One should
replace this :

......First_Weight : constant Float := Effective_Index - Float (First_Lookup_Index); ......Second_Weight : constant Float := 1.0 - First_Weight;

with this :

......Second_Weight : constant Float := Effective_Index - Float (First_Lookup_Index); ......First_Weight : constant Float := 1.0 - Second_Weight;

Otherwise, the result would look more like a sawtooth function than like a
continuous linear interpolant.

***************************************************************

Questions? Ask the ACAA Technical Agent