Version 1.9 of ai12s/ai12-0190-1.txt

Unformatted version of ai12s/ai12-0190-1.txt version 1.9
Other versions for file ai12s/ai12-0190-1.txt

!standard 4.4(7/3)          18-12-11 AI12-0190-1/05
!standard 4.5.9(0)
!class Amendment 16-06-02
!status Amendment 1-2012 18-12-10
!status work item 18-12-13
!status ARG Approved 9-0-2 18-12-10
!status work item 16-06-02
!status received 16-05-06
!priority Low
!difficulty Medium
!subject Anonymous functions
!summary
Provide an ability to construct a local anonymous function at the point of a call on a subprogram that has an access-to-function parameter, or in an instantiation with a formal subprogram parameter, or other contexts where the expected type is an access-to-function type, or there is an expected profile for a function.
!problem
We added anonymous access-to-subprogram parameters to allow locally-declared subprograms to be passed to other programs which might iterate over some data structure, applying the passed subprogram multiple times, perhaps as part of a search, or an update, or a transformation of some sort. Being able to pass local subprograms to other subprograms is a fundamental part of "functional" programming, but also appears in other programming paradigms, including old fashioned numeric integration packages, etc.
To enhance the utility of this feature, it is convenient if the subprogram being passed can be constructed at the point of call, rather than requiring a separate declaration. AI12-0189 addresses the case where a procedure (as opposed to a function) is to be passed as the actual parameter. We would like to provide something similar for passing a locally-constructed function as a parameter.
!proposal
A function_expression can be used in a context where the expected type is a single access-to-function type (or as the actual parameter for a formal function). It is roughly equivalent to using the name'Access (or simply name) of an expression function which is declared at the point of use, with parameter types, modes, etc. taken from that of the expected access-to-function type (or the formal function). Only the formal parameter names come from the function_expression.
primary ::= function_expression
function_expression ::= ( function [ function_formal_parameter_list ] return expression )
function_formal_parameter_list ::= ( identifier { , identifier } ) | formal_part
We allow only a single expression as the body of the function_expression. Given that we now have "if" expressions and "case" expressions, this is not a serious limitation. (The possible addition of "declare expressions" would be a welcome enhancement.)
!wording
Replace 4.4(7/3) with:
primary ::= numeric_literal | null | string_literal | aggregate | name | allocator | (expression) | (conditional_expression) | (quantified_expression) | function_expression
Add section after 4.5.8:
4.5.9 Function Expressions
Function expressions provide a way to define a function at a point where an access-to-function type is the expected type, or in a generic instantiation as an actual parameter corresponding to a formal subprogram parameter.
Syntax
function_expression ::= (function [function_formal_parameter_list] return expression)
function_formal_parameter_list ::= formal_part | (identifier {, identifier})
Name Resolution Rules
In a context where there is an expected type rather than an expected profile for a function_expression, the expected type shall be a single access-to-function type, and the profile of this type is considered the expected profile for the function_expression. The result type of the expected profile of the function_expression is the expected type for the expression of the function_expression. If there is no function_formal_parameter_list, the expected profile shall have no parameters. If the function_formal_parameter_list is a formal_part, then it shall be subtype conformant to the expected profile if there is an expected type, or merely mode conformant otherwise. If the function_formal_parameter_list is a sequence of identifiers, the number of identifiers in the sequence shall be the same as the number of formal parameters in the expected profile.
Static Semantics
A function_expression used in a context where there is an expected type is equivalent to a local expression_function_declaration (see 6.8), with the function_expression replaced by an Access attribute_reference of this locally defined function; otherwise, the function_expression is equivalent to such a local declaration with the function_expression replaced by a name denoting this locally defined function. The profile of this locally defined function has a result type determined by the expected profile, and a formal part determined by the formal_part, if provided in the function_expression, or by the formal part of the expected profile otherwise, but with the name of each formal parameter of the expected profile replaced by the corresponding identifier in the sequence of identifiers. The expression of this locally defined expression function is that of the function_expression.
!discussion
We are using the reserved words FUNCTION and RETURN rather than defining a new reserved word such as LAMBDA. We put them surrounding the (optional) parameter list, as that is their normal place in the syntax for declaring a named function.
We considered other names such as "lambda functions," "function literals," and "anonymous functions." We ultimately went with "function expression" as it seemed analogous to "if expression" and "case expression," though there is admittedly some discomfort in having both "expression functions" and "function expressions."
We allow, but do not require, a full formal part as part of the function_expression. Requiring a full formal part seems unnecessary and verbose, since the parameter (and result) types are always provided by the profile of the formal access-to-function parameter.
We are only supporting defining anonymous functions using this proposed "function_expression" construct. Anonymous procedures are nicely handled with the loop-body proposal (AI12-0189). In any case, mixing statements inside expressions seems like a bad idea. Also, we don't have "expression procedures" so it doesn't seem so bad that we don't have "procedure expressions" ;-).
One place where it might be nice to allow a "procedure expression" would be when you want to pass in a do-nothing procedure, which is not uncommon when instantiating a generic with a formal procedure. We allow using "null" as the default for a formal procedure, as well as when defining a null procedure. It would seem pretty reasonable to allow "null" as the actual parameter for a formal procedure, meaning a "do-nothing" procedure.
!example
-- Replace control chars with '?' Ada.Strings.Fixed.Translate
(Str, (function (C) return (if C < ' ' then '?' else C)));
-- Procedure for plotting a function procedure Plot_Graph
(Fun : access function (X : Float) return Float;
Start, Stop : Float);
...
-- Plot a graph of X-squared from 1 to 20 Plot_Graph (Fun => (function (Z) return Z**2),
Start => 1.0, Stop => 20.0);
!corrigendum 4.4(7/3)
Replace the paragraph:
primary ::= numeric_literal | null | string_literal | aggregate | name | allocator | (expression) | (conditional_expression) | (quantified_expression)
by:
primary ::= numeric_literal | null | string_literal | aggregate | name | allocator | (expression) | (conditional_expression) | (quantified_expression) | function_expression
!corrigendum 4.5.9(0)
Insert new clause:
Function expressions provide a way to define a function at a point where an access-to-function type is the expected type, or in a generic instantiation as an actual parameter corresponding to a formal subprogram parameter. Syntax
function_expression ::= (function [function_formal_parameter_list] return expression)
function_formal_parameter_list ::= formal_part | (identifier {, identifier})
Name Resolution Rules
In a context where there is an expected type rather than an expected profile for a function_expression, the expected type shall be a single access-to-function type, and the profile of this type is considered the expected profile for the function_expression. The result type of the expected profile of the function_expression is the expected type for the expression of the function_expression. If there is no function_formal_parameter_list, the expected profile shall have no parameters. If the function_formal_parameter_list is a formal_part, then it shall be subtype conformant to the expected profile if there is an expected type, or merely mode conformant otherwise. If the function_formal_parameter_list is a sequence of identifiers, the number of identifiers in the sequence shall be the same as the number of formal parameters in the expected profile. Static Semantics
A function_expression used in a context where there is an expected type is equivalent to a local expression_function_declaration (see 6.8), with the function_expression replaced by an Access attribute_reference of this locally defined function; otherwise, the function_expression is equivalent to such a local declaration with the function_expression replaced by a name denoting this locally defined function. The profile of this locally defined function has a result type determined by the expected profile, and a formal part determined by the formal_part, if provided in the function_expression, or by the formal part of the expected profile otherwise, but with the name of each formal parameter of the expected profile replaced by the corresponding identifier in the sequence of identifiers. The expression of this locally defined expression function is that of the function_expression.
!ASIS
** TBD.
!ACATS test
An ACATS C-Test is needed to check that the new capabilities are supported.
!appendix

From: Tucker Taft
Sent: Friday, May 6, 2016  2:05 PM

Now that we have a number of language-defined subprograms that take
access-to-subprogram parameters, it seems worth considering supporting some kind
of "anonymous" function/procedures.  Here are two proposals, one for anonymous
(lambda) functions, and one for anonymous (loop-body) procedures:

[Editor's note: See AI12-0189-1 for the other proposal.]

Lambda functions:

A lambda_function can be used in a context where the expected type is a single
access-to-function type (or as the actual parameter for a formal function).  It
is roughly equivalent to using the name'Access (or simply name) of an expression
function which is declared at the point of use, with parameter types, modes,
etc. taken from that of the expected access-to-function type (or the formal
function).  Only the formal parameter names come from the lambda function.

    primary ::= lambda_function

    lambda_function ::= ( LAMBDA [ lambda_parameter_list ] expression )

    lambda_parameter_list ::= ( identifier { , identifier } )

Here is an example:

    --  Replace control chars with '?'
    Ada.Strings.Fixed.Translate
      (Str, (lambda (C) (if C < ' ' then '?' else C)));

    --  Procedure for plotting a function
    procedure Plot_Graph
      (Fun : access function (X : Float) return Float;
       Start, Stop : Float);

    ...

    --  Plot a graph of X-squared from 1 to 20
    Plot_Graph (Fun => (lambda (Z) Z**2), Start => 1.0, Stop => 20.0);

=====================

Again, if there is interest, I can write up these ideas as AIs.  As mentioned,
we discussed the loop-body procedures a bit in Vermont.

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

From: Brad Moore
Sent: Saturday, May 7, 2016  8:40 AM

I'm definitely interested in seeing some improvements in this area, but I'd like
to see a single, more general solution that covers both these cases (expression
functions and iterators) as well as other cases. Essentially, I'd like to be
able to provide an anonymous subprogram for any parameter of an
access-to-subprogram type (not just expression functions), and possibly other
places such as generic formal subprograms.

This capability already exists in C++, C#, and Java in some form.

The idea here is to write the full body of the subprogram inline, including the
parameter profile, but omitting the name for the subprogram.

Tuckers examples might look like;

-- Example using an expression function
Ada.Strings.Fixed.Translate
   (Source => Str,
    Mapping => (C : Character) is (if C < ' ' then '?' else C));

--  Procedure for plotting a function
procedure Plot_Graph
   (Fun : access function (X : Float) return Float;
    Start, Stop : Float);

    ...

--  Another expression function
--  Plot a graph of X-squared from 1 to 20 Plot_Graph (Fun => (Z : Float) is (Z**2)),
             Start => 1.0, Stop => 20.0);


-- Example using a procedure.
-- Iterating via Ada.Environment_Variables Ada.Environment_Variables.Iterate
    (Process => (Name, Value : String) is
     begin
        Put_Line (Name & " => " & Val);
     end);

-- Another example showing not just for iteration and expression
-- functions

-- procedure for executing N Blocks in parallel procedure Parallel_Blocks
   (Number_Of_Blocks : Positive;
    Process : not null access procedure (Worker : Positive));

-- Call to execute two procedures in parallel using inline procedure
-- featuring a declaration
Parallel_Blocks (Number_Of_Blocks => 2,
                  Process => (Worker : Positive) is
    declare
       X : Integer := Foo;
    begin
       if Worker = 1 then
         Do_Lengthy_Processing_A (X);
       else
         Do_Other_Processing (X);
       end if;
    end);

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

From: Tucker Taft
Sent: Saturday, May 7, 2016  2:17 PM

> The idea here is to write the full body of the subprogram inline,
> including the parameter profile, but omitting the name for the subprogram. ...

I believe readability goes down if you start embedding statements inside
expressions. Since you can always declare a local subprogram, trying to bury a
sequence of statements inside an expression is unnecessary, and doesn't really
improve "writability" much either.

Also, it is always redundant to specify the parameter types for a lambda
function, given that they would only be allowed in contexts where the expected
profile is known.

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

From: Jean-Pierre Rosen
Sent: Saturday, May 7, 2016  2:29 PM

But this kind of redundancy appears often in Ada, on the ground that the reader
should not have to wander to far-away places to get important information like
types.

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

From: Tucker Taft
Sent: Saturday, May 7, 2016  2:41 PM

Well, I suppose it would be easy enough to allow a full formal parameter part in
the "lambda" function syntax, as in the proposed syntax for the loop-body
procedure.  But I certainly wouldn't want to require it.

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

From: John Barnes
Sent: Sunday, May 8, 2016  4:15 AM

I am always wary of mixing expressions and statements. I went to a lecture on
lambda expessions by Peter Landin at a Summer School in Oxford in 1963. I must
read the notes.

I am in favour provided it deosn't cause confusion and/or make the next version
of my book much bigger.

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

From: Erhard Ploedereder
Sent: Monday, May 9, 2016  9:18 AM

> Also, it is always redundant to specify the parameter types for a
> lambda function, given that they would only be allowed in contexts
> where the expected profile is known.

But this would mean that lambdas cannot take lambdas as arguments, would it not?
(Which would really turn off the functional crowd).

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

From: Tucker Taft
Sent: Monday, May 9, 2016  10:27 AM

I don't follow this.  If the profile of the lambda is known, then so is the
profile of any arguments of the lambda that are themselves access-to-functions,
so nesting should be no problem.  If you can show an example, I can verify this
claim, but I will admit I am not up to producing a realistic example where a
lambda takes a lambda.

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

From: Edmond Schonberg
Sent: Monday, May 9, 2016  10:42 AM

If nothing else, how do you disambiguate  F (X) within the expression if F is a
lambda parameter?  An array of Xs, a a type with implicit dereference, or a
call?

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

From: Tucker Taft
Sent: Monday, May 9, 2016  10:52 PM

You know the (access-to-function) type of F by context.

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

From: Jeff Cousins
Sent: Tuesday, May 10, 2016  4:04 AM

Lambda functions seem to me a bit like a WIBNI (wouldn't it be nice if) that, if
we have at all, should be tucked away in some optional annex. Would lambda be a
new reserved word?

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

From: Tucker Taft
Sent: Thursday, May 12, 2016  7:48 PM

Yes, I would recommend a new reserved word, as just trying to do lambda
functions with clever syntax would be harder to read, in my view.  In my view
the loop-body procedures are more important than lambda functions, but others at
AdaCore feel that lambdas are critically important.  But Randy reminded me that
Bob Duff has at least something like this on his plate, so I'll let him take a
stab at it first if he so desires.

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

From: Randy Brukardt
Sent: Thursday, May 12, 2016  5:21 PM

> Again, if there is interest, I can write up these ideas as AIs.  As
> mentioned, we discussed the loop-body procedures a bit in Vermont.

Right, and this topic was assigned to Bob Duff (certainly the second idea, and
arguably the first as well). Given your well-known huge pile of homework, I
recommend that you let Bob write the AI(s) on this topic. (If he doesn't do it,
we can revisit, there certainly isn't any rush at this point.)

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

From: Erhard Ploedereder
Sent: Thursday, May 12, 2016  6:30 PM

You are right. If the context of lambda construction always provides a specified
access-to-function type (obviously including its parameters), calling lambdas
with lambdas as arguments is not a problem.

The problem appears when lambdas can be named and lead an independent existence,
as in
   inc = lambda(x) (x + 1);
   conc = lambda(x) (x & "abc");
   twice = lambda(f, x) (f(f(x));
Now, we know nothing about the type of f (short of doing a very general type
inference) but we can say twice(inc, 5), while twice(conc, 5) should be illegal,
but how to tell without said type inference?

But you are not proposing named lambdas, so all is fine.

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

From: Randy Brukardt
Sent: Thursday, May 12, 2016  6:51 PM

> But you are not proposing named lambdas, so all is fine.

Sorry to toss out a bit of ignorance here, but what is the point of a "named
lambda"? Isn't that the same silliness as a "named anonymous access type"
(something we rightfully decided was too silly to pursue)?

It seems to me that a "named lambda" is essentially the same thing as a normal
subprogram. In your above example, the parameters are typeless, but if that's
allowed at all, it should be allowed everywhere (thus there is no difference
between a "named lambda" and any other kind of named subprogram).

If we were to do a more general lambda facility (which I've against for
readability reasons, but that's not relevant to this discussion), then surely
the context would have to identify an access-to-subprogram type (nothing being
typeless in Ada). The above sort of thing would be possible:

    Inc : constant access function (X : Integer) return Integer := (lambda(X) X + 1);
    Conc : constant access function (X : String) return String := (lambda(X) X & "abc");

And this would essentially be a "named lambda". And not appreciably different
than:

    function Inc (X : Integer) return Integer is (X + 1);
    function Conc (X : String) return String is (X & "abc");

(Which I hope most programmers would prefer.)

So the operative thing in your example that causes trouble is typeless-ness, not
whether or not the lambda is named in some sense. But Tucker (nor Brad for that
matter) were proposing any sort of typeless-ness. So I don't think there is any
problem.

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

From: Brad Moore
Sent: Thursday, May 12, 2016  7:56 PM

> Sorry to toss out a bit of ignorance here, but what is the point of a
> "named lambda"? Isn't that the same silliness as a "named anonymous access type"
> (something we rightfully decided was too silly to pursue)?

I haven't the definitive answer to this question, but I think I have a good
guess.

In such languages as C++ and Java, lambdas provide another missing capability.
They provide a means to essentially write a nested subprogram, which is
important because such subprograms can access variables in the enclosing scope.

Ada doesn't need that capability, because it has had it from day one, in Ada 83
with nested subprograms.

I see a named lambda being particularly useful in C++ because it might be needed
more than once, possibly passed as parameters into 2 or more separate function
calls. Rather than write the same lambda function multiple times, the named
lambda allows C++ programmers to write the function once, and then pass that
lambda into the separate call sites.

Ada doesn't seem to need that capability, because one can just write a nested
subprogram and pass that in, instead of using a lambda.

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

From: Randy Brukardt
Sent: Thursday, May 12, 2016  8:12 PM

On top of which, one can "name" a lambda as I showed (using an object with an
anonymous-access-to-subprogram). So if you really need two copies of a lambda,
that's a way to do it. (But just using a subprogram makes more sense anyway.)

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

From: Randy Brukardt
Sent: Thursday, May 12, 2016  9:20 PM

[Editor's note: From another thread, see AI12-0188-1.]

...
> I agree that some more discussion is needed.

Surely. I have to wonder why "others at AdaCore feel that lambdas are
critically important". Why is it so hard to stick an expression function in a
declare block? That's 20 extra characters or so?? It seems I'm missing
something (or perhaps that lambda proponents are, because none of the proposals
are going to weaken typing).

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

From: Erhard Ploedereder
Sent: Saturday, May 14, 2016  2:30 PM

> Sorry to toss out a bit of ignorance here, but what is the point of a
> "named lambda"?

It is the corner stone of functional programming in all the functional
languages. So people coming from a functional background are looking for that.

It is not quite a named subprogram. It is subclass, namely a named expression
function.

I agree with the remainder of what you wrote.

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

From: Brad Moore
Sent: Thursday, May 12, 2016  8:19 PM

>> ... I'm really dubious that a separate feature is warranted for this.
>
> I think you are in the minority on this one.

Just for comparison, two new syntax variants with specific usage for iterating
through map-like containers ...

    for (Key => Elem) of Container loop
       ...
    end loop;

and

   for (Key => <>) of Container loop
      ...
   end loop;

vs a single syntax capability that is much more general purpose including
other usages that have been discussed in the lambda thread...

    Container.Iterate (Key is
       begin
          ...
       end);

    Container.Iterate((Key, Element) is
       begin
          ...
       end);

Both proposals seem relatively similar in terms of ease of expression.

With specific syntax, there is a danger that more people will not know of its
existence, or remember its existence when a possibility for usage arises. With
a more general solution, chances are more people will think of using the
capability.

So far, I am agreeing with Randy here. I think most people are interested in a
solution, but not necessarily settled on the proposed solution.

   But in any case it sounds
> like we should discuss the various alternatives in an ARG meeting
> before I spend time writing it up, given the amount of other homework
> still on my plate...

I agree that some more discussion is needed.

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

From: Randy Brukardt
Sent: Thursday, May 12, 2016  9:20 PM

> Both proposals seem relatively similar in terms of ease of expression.

Well, I was replying to Tucker's "loop procedure" proposal, which looks like a
loop. (I don't think anyone other than yourself is interested in your general
proposal). Tucker's suggestion (based on his original message and an
appropriate Iterate) would look like:

    for (Key, Element) of Container.Iterate(<>) loop
       ...
    end loop;

which is so close to his first case that it would be madness to provide both.
[And the <> is optional above.]

And it is easy to imagine extending his original idea to allow using <> in
place of parameters not wanted (they'd still exist, but be anonymous), thus
getting:

    for (Key, <>) of Container.Iterate loop
       ...
    end loop;

which handles the second case perfectly.

> With specific syntax, there is a danger that more people will not know
> of its existence, or remember its existence when a possibility for
> usage arises. With a more general solution, chances are more people
> will think of using the capability.

Or even more likely never even consider it because they can't grok lambdas.

I'm in favor of Tucker's loop syntax as given above (it's natural and could be
used for all of the containers). Indeed, it's a better idea than the existing
cursor iterators, which we may not have defined at all if we had the above.

I'm pretty much against all of the other proposals, I don't see the value of
the complications (especially as access-to-anything ought to be minimized,
especially in reusable code). And the idea of sticking statements in the
middle of expressions is a bridge too far to me. All of the languages that you
listed as having lambdas seem to me to be also those languages that are
actively against readability!

I'm also getting worried about feature creep. We expanded expressions to
include if and case and quantified and expression functions because of the
needs of contract aspects. I don't know what is supposed to be driving
lambdas.

...
> I agree that some more discussion is needed.

Surely. I have to wonder why "others at AdaCore feel that lambdas are
critically important". Why is it so hard to stick an expression function in a
declare block? That's 20 extra characters or so?? It seems I'm missing
something (or perhaps that lambda proponents are, because none of the proposals
are going to weaken typing).

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

From: Brad Moore
Sent: Thursday, May 12, 2016  10:55 PM

Anonymous functions are fairly common in programming languages, and apparently
can be found in languages including C++, C#, Dart, Erlang, Go, Haskell, Java,
Javascript, List, Lua, Mathematica, Perl, PHP, Python, Ruby, Scala, Smalltalk,
Swift, ...

https://en.wikipedia.org/wiki/Anonymous_function

There must be at least some folks out there who grok lambdas.

Well, I have one more example, that is kind of interesting that I plan to use
for a tutorial at Ada Europe... Interesting here not from the standpoint of
parallelism, but from the standpoint of being called from multiple languages,
and involving multiple anonymous subprogram parameters.

The following non-generic Ada subprogram that can be called from multiple
languages including C, C++, C#, and Java, as it exports the C calling convention
for the C and C++ case, and can be easily ported to C# and Java as well, which I
have done using the GNAT dot net and java compilers....

procedure Parallel_Loop
   (From           : Loop_Index;
    To             : Loop_Index;
    Reset          : not null access procedure;
    Loop_Body      : not null access
      procedure (Start, Finish : Loop_Index);
    Reduce         : not null access procedure);

Basically,
    Reset is used to reinitialize task local variables,
    Loop_Body does the processing of the loop,
    and Reduce combines results produced by the Loop_Body.

Currently to call this routine from Ada to calculate the sum of numbers from 1
to 1_000_000, one might write in Ada....

    package Partial_Sums is new
       Ada.Task_Attributes (Attribute     => Integer,
                            Initial_Value => 0);
    procedure Reset is
    begin
       Partial_Sums.Set_Value (0);
    end Reset;

    procedure Compute_Sum
      (Start, Finish : Parallel.Loop_Index)
    is
       Partial_Sum : Integer renames Partial_Sums.Reference.all;
    begin
       for I in Start .. Finish loop
          Partial_Sum := Partial_Sum + I;
       end loop;
    end Compute_Sum;

    Sum : Integer := 0;

    procedure Reduce () is
    begin
       Sum := Sum + Partial_Sums.Value;
    end Reduce;

    Reducing_Loops.Work_Seeking.Parallel_Loop
      (From           => 1,
       To             => 1_000_000,
       Reset          => Reset'Access,
       Process        => Compute_Sum'Access,
       Reduce         => Reduce'Access);

To call this same Ada library from C#, one can currently write...

    [ThreadStatic]
    private static int partial_sum;
    ...
       int sum = 0;

       paraffin_pkg.parallel_loop
          (from   : 1,
           to     : 1000000,
           reset  : () => { partial_sum = 0; },
           process: (start, finish) =>
             {
               for (int i = start; i <= finish; i++)
                  partial_sum += i;
             },
           Reduce : () => { sum += partial_sum; });

Which of these two versions do you find more readable?

I prefer the C# version mostly because there is less "noise" text, and the
formal parameters of the call are directly associated with the code. In Ada, you
are first presented with a bunch of routines, not knowing their purpose, until
you get down to the call, but then your eyes have to jump up and down to
associate the logic with the call site.

In this example, it appears to be actually easier to call Ada code from C#, than
from Ada, I would say.

If instead, some sort of general lambda feature existed in Ada, I might be able
to write something like...

package Partial_Sums is new
       Ada.Task_Attributes (Attribute     => Integer,
                            Initial_Value => 0);
    Sum : Integer := 0;

    Reducing_Loops.Work_Seeking.Parallel_Loop
      (From     => 1,
       To       => 1_000_000,
       Reset    => is Partial_Sums.Set_Value (0),
       Process  => (Start, Finish) is
          Partial_Sum : constant access Integer :=
             Partial_Sums.Reference;
         begin
            for I in Start .. Finish loop
               Partial_Sum.all := Partial_Sum.all + I;
            end loop;
         end,
       Reduce   => is Sum := Sum + Partial_Sums.Value);

Which I find more readable, but maybe thats just me...

>
> I'm also getting worried about feature creep. We expanded expressions
> to include if and case and quantified and expression functions because
> of the needs of contract aspects. I don't know what is supposed to be
> driving lambdas.

I suppose its mostly just syntactic sugar to hopefully improve readability with
a short hand form of expression, in the same way that loop iterators of Ada 2012
did that for loops.

Also I think it would be beneficial to be able to say that Ada provides a lambda
feature comparable to most other main stream languages.

If I am alone in seeing the benefit of this, then I wont bother promoting the
idea, but then I tend to agree with the worry of feature creep for special
purpose syntax that has limited use. My concern would be to wonder if the same
capability can be provided reasonably with just a library addition.

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

From: Randy Brukardt
Sent: Friday, May 13, 2016  12:04 AM

A couple of thoughts rather than a complete response to your message because its
important to hear more from the rest of the group before beating to death ideas
that may not have much support anyway:

...
>> I'm pretty much against all of the other proposals, I don't see the
>> value of the complications (especially as access-to-anything ought to
>> be minimized, especially in reusable code). And the idea of sticking
>> statements in the middle of expressions is a bridge too far to me.
>> All of the languages that you listed as having lambdas seem to me to
>> be also those languages that are actively against readability!

>Anonymous functions are fairly common in programming languages, and apparently
>can be found in languages including C++, C#, Dart, Erlang, Go, Haskell, Java,
>Javascript, List, Lua, Mathematica, Perl, PHP, Python, Ruby, Scala, Smalltalk,
>Swift, ...
>
>https://en.wikipedia.org/wiki/Anonymous_function

We've come to regret almost everything anonymous that has ever been in or added
to Ada. They tend to cause all kinds of definitional and usage problems. I'm
quite opposed to repeating that mistake; every time we've been told how it will
all work out fine, and it never does.

What does help is to have short-hand syntax (like generalized references and
generalized indexing) where named stuff can be used with a shorthand.

Besides, what is really going on in most of those languages is some sort of
poor-man's subprogram type and values. The benefit isn't in anonymity but rather
in having subprogram values. We'd be better off looking in that direction if we
really needed it (but still, all of the subprogram types and values should have
names).

...
> The following non-generic Ada subprogram that can be called from
> multiple languages including C, C++, C#, and Java, as it exports the C
> calling convention for the C and C++ case, and can be easily ported to
> C# and Java as well, which I have done using the GNAT dot net and java
> compilers....
>
> procedure Parallel_Loop
>    (From           : Loop_Index;
>     To             : Loop_Index;
>     Reset          : not null access procedure;
>     Loop_Body      : not null access
>       procedure (Start, Finish : Loop_Index);
>     Reduce         : not null access procedure);
>
> Basically,
>     Reset is used to reinitialize task local variables,
>     Loop_Body does the processing of the loop,
>     and Reduce combines results produced by the Loop_Body.
>
> Currently to call this routine from Ada to calculate the sum of
> numbers from 1 to 1_000_000, one might write in Ada....
>
>     package Partial_Sums is new
>        Ada.Task_Attributes (Attribute     => Integer,
>                             Initial_Value => 0);
>     procedure Reset is
>     begin
>        Partial_Sums.Set_Value (0);
>     end Reset;
>
>     procedure Compute_Sum
>       (Start, Finish : Parallel.Loop_Index)
>     is
>        Partial_Sum : Integer renames Partial_Sums.Reference.all;
>     begin
>        for I in Start .. Finish loop
>           Partial_Sum := Partial_Sum + I;
>        end loop;
>     end Compute_Sum;
>
>     Sum : Integer := 0;
>
>     procedure Reduce () is
>     begin
>        Sum := Sum + Partial_Sums.Value;
>     end Reduce;
>
>     Reducing_Loops.Work_Seeking.Parallel_Loop
>       (From           => 1,
>        To             => 1_000_000,
>        Reset          => Reset'Access,
>        Process        => Compute_Sum'Access,
>        Reduce         => Reduce'Access);
>
> To call this same Ada library from C#, one can currently write...
>
>     [ThreadStatic]
>     private static int partial_sum;
>     ...
>        int sum = 0;
>
>        paraffin_pkg.parallel_loop
>           (from   : 1,
>            to     : 1000000,
>            reset  : () => { partial_sum = 0; },
>            process: (start, finish) =>
>              {
>                for (int i = start; i <= finish; i++)
>                   partial_sum += i;
>              },
>            Reduce : () => { sum += partial_sum; });
>
> Which of these two versions do you find more readable?

Neither. A loop should look like a loop; otherwise causal reading/tools will not
discover where the majority of the work is happening.

Tucker's "loop procedure" proposal does look like a loop; it would make this
look something like:

   for (First, Last) of Reducing_Loops.Work_Seeking.Parallel_Loop
       (From           => 1,
        To             => 1_000_000,
        Reset          => Reset'Access,
        Process        => <>,
        Reduce         => Reduce'Access) loop
      declare
        Partial_Sum : Integer renames Partial_Sums.Reference.all;
      begin
        for I in Start .. Finish loop
           Partial_Sum := Partial_Sum + I;
        end loop;
      end;
   end loop;

...and the rename inside the loop body makes it messier. (You still have the
instance and other subprograms, which to me demonstrate that the original
routine is too complex to be used; I'd never bother trying to understand a
routine that takes THREE subprograms. At least the intent is that parallel loops
are directly supported by Ada syntax and the compiler - no subprograms -
anonymous or otherwise - anywhere.)

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

From: Brad Moore
Sent: Friday, May 13, 2016  12:32 AM

...
> Tucker's "loop procedure" proposal does look like a loop; it would
> make this look something like:
>
>     for (First, Last) of Reducing_Loops.Work_Seeking.Parallel_Loop
>         (From           => 1,
>          To             => 1_000_000,
>          Reset          => Reset'Access,
>          Process        => <>,
>          Reduce         => Reduce'Access) loop
>        declare
>          Partial_Sum : Integer renames Partial_Sums.Reference.all;
>        begin
>          for I in Start .. Finish loop
>             Partial_Sum := Partial_Sum + I;
>          end loop;
>        end;
>     end loop;

Ok, I didn't realize Tucker's solution could be applied to this case...
I still worry that people coming from C++, Java, C# etc, might criticize that we
didn't go far enough to allow Reset and Reduce to also be "inlined", or that
other sorts of non-loop cases can't be lambdaized, but I would like to hear
others comments on this as well. John said he had some notes about statements
within expressions from some time ago that would be good to hear.

> ...and the rename inside the loop body makes it messier. (You still
> have the instance and other subprograms, which to me demonstrate that
> the original routine is too complex to be used; I'd never bother
> trying to understand a routine that takes THREE subprograms.

Just thought it would be worth pointing out that C#'s current official
parallelism approach actually looks very similar to the library I have. Their
library also takes three subprograms....

Here is how one would do the same loop using the C# "standard" libraries.

int sum = 0;

Parallel.ForEach
    (source      : Partitioner.Create(1, 1000001),
     LocalInit   : () => 0,        // Reset
     body        : (range, loopState, local) =>
        {
          for (int i = range.Item1; i < range.Item2; i++)
            { local += i; }
          return local;
        },
     localFinally: local =>        // Reduce
        {Interlocked.Add(ref sum, local);});

Its a similar looking library routine, except that it is genericized so that the
thread local variables are passed into the body lambda, instead of having to be
declared separately, and that the programmer has to supply locking around the
code in the Reduce routine.

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

From: Jean-Pierre Rosen
Sent: Friday, May 13, 2016  2:23 AM

> I still worry that people coming from C++, Java, C# etc, might
> criticize that we didn't go far enough to allow Reset and Reduce to
> also be "inlined", or that other sorts of non-loop cases can't be
> lambdaized
<rant>
We've been trying for 30 years to find the killer feature that would attract
those people. The truth is that they don't intend to switch to Ada, and that
their criticizing is just for finding excuses for not switching languages. Ada
has its own strengthes, most of which reside in /not/ doing things the same way
as other languages.

So I suggest we just close our ears to these criticisms </rant>

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

From: Jeff Cousins
Sent: Friday, May 12, 2016  2:55 AM

...
> We've come to regret almost everything anonymous that has ever been in
> or added to Ada. They tend to cause all kinds of definitional and
> usage problems. I'm quite opposed to repeating that mistake; every
> time we've been told how it will all work out fine, and it never does.

John B certainly regrets most of the anonymous stuff, and purged a lot of it
when he revised his book.

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

[Editor's note: This thread continues in AI12-0189-1, since it is turning back
to loops.]

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

From: Tucker Taft
Sent: Tuesday, October 4, 2016  11:02 PM

Here is an update. [This is version /02 of the AI - Editor.] I have shifted
the syntax so it doesn't rely on a new reserved word "lambda" any more. Might
want to change the name of the construct as well if we go this direction.
I have provided !problem and !discussion sections.


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

From: Gary Dismukes
Sent: Wednesday, October 5, 2016  12:09 PM

I definitely prefer including "function" in the syntax.  I think it makes it
much easier to read, and avoids the unpleasant double-paren at the beginning.

(And thanks for eliminating "lambda"!)

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

From: Randy Brukardt
Sent: Wednesday, October 5, 2016  7:58 PM

The alternative with both "function" and "return" looks the best to me. The
others look like something is missing.

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

From: Tucker Taft
Sent: Wednesday, October 12, 2016  4:30 PM

Essentially everyone who saw this likes having "function" as part of the syntax.
So here is an update to the update. [This is version /03 of the AI - Editor.]  I
also changed the syntax category to be "function_expression" in analogy with
"if_expression" and "case_expression".

Here is a simple example of the syntax, showing a function_expression that
returns the square of its operand.

    (function (X) return (X**2))

Types of parameter(s) and result come from the expected profile.

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

From: Raphael Amiard
Sent: Wednesday, October 12, 2016  4:46 PM

I'm confused about something though. I will have to look at the minutes, but
from what I remember from the last meeting, the general agreement was that:

- In most languages lambdas/anonymous functions imply closures
- Making them equivalent to nested functions only gave a negligible boost in
  expressivity and readability.
- But on the other hand would be confusing to people expecting them to work like
  *real* anonymous functions in other languages

So in the end my understanding was that we should investigate the closure
behavior, and that if not it was not deemed a worthy addition to the language.

I don't see any mention of that in the AI, on the contrary it does exactly what
we agreed was not worth it.

Did I miss something ?

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

From: Raphael Amiard
Sent: Wednesday, October 12, 2016  4:49 PM

I did not miss something. Here is the relevant extract:


Erhard says that a simple version isn't interesting. People he knows are only
interested in being able to return constructed lambdas. Steve wonders if
supporting a syntax sugar only version would do more harm than good. People
would think that we are just faking. Erhard thinks we could try to make this
safe by the right restrictions, that would be a boon. (C++ just crashes if one
does.)
Keep alive (original version): 2-4-6.
Keep alive (complex version): 6-1-5. (A complex version would support some sort
of constructed lambda.) Tucker will take another shot at this. Florian would
like to help.

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

From: Tucker Taft
Sent: Wednesday, October 12, 2016  5:50 PM

> I did not miss something. Here is the relevant extract:

Good point.  I missed/forgot that.  On the other hand, if we can at least agree
on the syntax, we could then look into the semantics. ;-)

It seems what is being requested is the ability to write something like this:

    function Filter(Pattern : String) return access function (X : String) return Boolean;

This will return a filter which returns True only if X matches the pattern.

Trying to write this:

     function Filter(Pattern : String)
       return access function (X : String) return Boolean is
     begin
         return (function (X) return Match(X, Pattern));
     end Filter;

This is do-able by treating such a result as living on the secondary stack, I
suppose, which we would *not* cut back until the returned function is no longer
being used.

So it seems that the proposed syntax could work, provided we defined the
semantics of returning an access-function as having this possibility of
preserving the context on the secondary stack.

Personally, I am not convinced that this added functionality is that important,
but others seem to think that without it the feature is useless.  If there is
interest, for the next ARG meeting I could add more details about the
implementation requirements associated with this added functionality, presuming
I have captured it correctly.

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

From: Steve Baird
Sent: Wednesday, October 12, 2016  6:01 PM

It gets more interesting ("interesting" sounds better than "preposterously
inappropriate for Ada") if the anonymous function can refer to things declared
inside of Filter, so that they have to persist after Filter returns.

Even if these guys are pretty much just syntactic sugar, we need to be a little
bit careful in defining them via an equivalence rule because they can refer to
the implicitly declared object of a quantified_expression or of an
iterated_component_association.

Since that cannot be done with an explicitly declared function, a simple
equivalence rule breaks down in this case.

Consider the following (admittedly contrived) example

    function Foo (Func : access function return Character) return Boolean
      is ... ;

    Flag : Boolean := (for some C in Character =>
                         Foo (Func => (function return (C))));

This is not a fundamental problem - just a case that we would need to confirm is
defined correctly.

[Randy - yes, I mentioned this one to you a while back.]

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

From: Tucker Taft
Sent: Wednesday, October 12, 2016  8:07 PM

> ...
> It gets more interesting ("interesting" sounds better than
> "preposterously inappropriate for Ada") if the anonymous function can
> refer to things declared inside of Filter, so that they have to
> persist after Filter returns.

Yes, I was presuming the entire stack frame of Filter would be preserved on the
secondary stack, so you could refer to anything visible at the point of the
function return.  This seems implementable.  You just have to put all things
that are referenced (directly or indirectly) by the return statement on the
secondary stack rather than the primary stack. For simplicity, you could just
allocate everything local to Filter on the secondary stack.

>
> Even if these guys are pretty much just syntactic sugar, we need to be
> a little bit careful in defining them via an equivalence rule because
> they can refer to the implicitly declared object of a
> quantified_expression or of an iterated_component_association.
>
> Since that cannot be done with an explicitly declared function, a
> simple equivalence rule breaks down in this case.
>
> Consider the following (admittedly contrived) example
>
>    function Foo (Func : access function return Character) return Boolean
>      is ... ;
>
>    Flag : Boolean := (for some C in Character =>
>                         Foo (Func => (function return (C))));
>
> This is not a fundamental problem - just a case that we would need to
> confirm is defined correctly.

Agreed.  I don't see any strong reason to define these by an equivalence rule.
I was using the equivalence more to help understand the limitation to a single
expression, which is similar to an expression function.

One twist that I considered for ParaSail was, when the formal was of a
parameterless function type, the caller would be allowed to pass a simple
expression of the return type as the actual parameter (rather than a lambda).
You could then (in ParaSail syntax) define a short-circuit operation like "and
then" as:

    op "and then"(Left : Boolean; Right : func() -> Boolean) -> Boolean is
       if Left then
          return Right();
            //  evaluate the right-hand operand only if necessary
       else
          return #false;
       end if;
    end op "and then";

This doesn't work quite as well when the parameter type is necessarily an
access-to-function type as in Ada, since the actual parameter for Right might be
overloaded so that it could legally be interpreted as either of the correct
access-function type, or of the access-function's result type.  It would be
upward incompatible to consider that ambiguous, though being able to gain the
feature of unevaluated parameters might be worth it!

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

From: Steve Baird
Sent: Wednesday, October 12, 2016  10:44 PM

> This seems implementable.

True, but at some cost in complexity.

en.wikipedia.org/wiki/Parent_pointer_tree says:

   The term spaghetti stack is closely associated with implementations
   of programming languages that support continuations. Spaghetti stacks
   are used to implement the actual run-time stack containing variable
   bindings and other environmental features. When continuations must be
   supported, a function's local variables cannot be destroyed when that
   function returns: a saved continuation may later re-enter into that
   function, and will expect not only the variables there to be intact,
   but it will also expect the entire stack to be present so the
   function is able to return again. To resolve this problem, stack
   frames can be dynamically allocated in a spaghetti stack structure,
   and simply left behind to be garbage collected when no continuations
   refer to them any longer. This type of structure also solves both the
   upward and downward funarg problems, so first-class lexical closures
   are readily implemented in that substrate also.

   Examples of languages that use spaghetti stacks are:

     Languages having first-class continuations such as Scheme
        and Standard ML of New Jersey
     Languages where the execution stack can be inspected and
        modified at runtime such as Smalltalk
     Felix
     Cilk

The interactions with tasking, masters, and finalization would also need to be
worked out.

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

From: Tucker Taft
Sent: Thursday, October 13, 2016  7:42 AM

>   The term spaghetti stack is closely associated with implementations
>   of programming languages that support continuations. ...

I am not sure we need support for full continuations to support returning
function expressions.  If we allocate everything of interest on the secondary
stack and then return the access-to-function without cutting it back (and
without performing any finalization), what more do we need to do?  I have
presumed the accessibility checks would treat this roughly the same way we treat
access-to-subprogram parameters, as though the accessibility level is deeper
than any master, so you can't convert it to any named access-to-subprogram type.
All you can do is pass the result of a call to an access-to-subprogram
parameter, or return the result of the call.  With these restrictions, you
cannot create arrays of these function expressions, nor store them in any object
of a named access type.

In any case, I agree that none of this is trivial.  Also, looking at other
languages that support lambda expressions, many of them support only passing
them as parameters, so I don't think Ada would be in such a bad situation if we
started out only supporting them as parameters, and consider support for
returning them as a later extension.

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

From: Raphael Amiard
Sent: Thursday, October 13, 2016  10:23 AM

> Good point.  I missed/forgot that.  On the other hand, if we can at least
> agree on the syntax, we could then look into the semantics. ;-)

Fine by me ! I guessed that this was an omission :)

> It seems what is being requested is the ability to write something like this:
>
>   function Filter(Pattern : String) return access function (X : String) return Boolean;
>
>This will return a filter which returns True only if X matches the pattern.

This is one of the things that you could do indeed.

>Trying to write this:
>
>    function Filter(Pattern : String)
>      return access function (X : String) return Boolean is
>    begin
>        return (function (X) return Match(X, Pattern));
>    end Filter;

Yeah that's a good example, because we can see that the lambda-function captures
the Pattern parameter.

> This is do-able by treating such a result as living on the secondary stack,
> I suppose, which we would *not* cut back until the returned function is no
> longer being used.
>
> So it seems that the proposed syntax could work,

I like the syntax very much indeed ! This is akin to what Javascript/Lua/ML do.

> provided we defined the semantics of returning an access-function as having
> this possibility of preserving the context on the secondary stack.

This is not sufficient. Suppose you want to then store the resulting filter
lambda function, for example to use in your *lazy* iterator (that could be
implemented using a generator ^^, or not), that will call it everytime the users
calls "Next" on it.

> Personally, I am not convinced that this added functionality is that
> important, but others seem to think that without it the feature is useless.
> If there is interest, for the next ARG meeting I could add more details
> about the implementation requirements associated with this added
> functionality, presuming I have captured it correctly.

Well, I disagree. I think it's important if you want to program in a certain
style. It makes certain patterns much more expressive. One example is the
previous example of providing filters to iterators:

for Node of Tree.Search(function (N): N.Kind = Function_Call) loop
    Do_Stuff;
end loop;

If search is done in such a way that it returns an iterator object (which it
should, because you might want to abort the search before the end), then it will
need to take ownership of the lambda, or store a reference to it (depending on
the semantics of the lambda objects).

Another very common example is giving event handlers in event oriented
programming:

procedure Build_GUI is
    My_Button  : Button;
    My_Form    : Form;
begin
    Initialize_Payment_Form (My_Form);
    Button.Set_On_Click (function (B): My_Form.Show);
end Build_GUI;

Of course, here, to be correct, the Form type needs to be some kind of
ref-counted type. That's fine.

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

From: Tucker Taft
Sent: Thursday, October 13, 2016  11:21 AM

> ...
>> So it seems that the proposed syntax could work,
>
> I like the syntax very much indeed ! This is akin to what Javascript/Lua/ML
> do.
>
>> provided we defined the semantics of returning an access-function as
>> having this possibility of preserving the context on the secondary stack.
>
> This is not sufficient. Suppose you want to then store the resulting
> filter lambda function, for example to use in your *lazy* iterator
> (that could be implemented using a generator ^^, or not), that will call it
> everytime the users calls "Next" on it.

I am not convinced we need to store these, so I would have to see the problem we
are trying to solve.  I am sure you could construct an example that could take
advantage of storing them, but I would suspect (hope?) that there are other ways
of accomplishing the same thing without doing so.  I am not a big fan of burying
everything in lambdas (as explained a bit more below).

>> Personally, I am not convinced that this added functionality is that
>> important, but others seem to think that without it the feature is
>> useless.  If there is interest, for the next ARG meeting I could add
>> more details about the implementation requirements associated with this added
>> functionality, presuming I have captured it correctly.
>
> Well, I disagree. I think it's important if you want to program in a
> certain style. It makes certain patterns much more expressive. One
> example is the previous example of providing filters to iterators:
>
>     for Node of Tree.Search(function (N): N.Kind = Function_Call) loop
>         Do_Stuff;
>     end loop;
>
>
> If search is done in such a way that it returns an iterator object
> (which it should, because you might want to abort the search before
> the end), then it will need to take ownership of the lambda, or store
> a reference to it (depending on the semantics of the lambda objects).
>
> Another very common example is giving event handlers in event oriented
> programming:

I think perhaps you are trying to make lambdas solve all problems, when in fact
event handlers are quite naturally represented as objects with their dispatching
operations being the call backs.  There are some languages where all you have
are lambda expressions, and you end up using them for everything.  But for
languages that have support for dynamic dispatch already, the need for function
objects is much reduced in my view, and generalizing them too much is just
adding complexity and redundancy to the language definition.

In Java, I believe these might end up just being syntactic sugar around
declaring a new class with a single operation.  We could go in that direction
for Ada if we think it is important to be able to store these things, but I
think that is yet another step that seems even less important than being able to
return them.

I think you also have to think about the debugging problem.  You are effectively
creating large numbers of partial stack contexts, each of which is a potentially
very complex piece of state.  Trying to debug such a situation is much harder
than debugging a more data-object-based world, where the contents of the fields
of a record, or equivalent, represents the current state of things.  Yes it is
kind of cool that you can do all kinds of amazing things with lambdas, but I am
not convinced that is the clearest, most efficient, and most verifiable way to
solve the problem.  We should be really sure we need to add all of this
complexity on top of all the features already available for solving such
problems.

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

From: Raphael Amiard
Sent: Thursday, October 13, 2016  1:21 PM

> I am not convinced we need to store these, so I would have to see the
> problem we are trying to solve.  I am sure you could construct an
> example that could take advantage of storing them, but I would suspect
> (hope?) that there are other ways of accomplishing the same thing
> without doing so.  I am not a big fan of burying everything in lambdas (as
> explained a bit more below).

Well, the problem is that you are then inventing a feature called lambda
functions that behaves slightly differently from the way it behaves in *every*
other languages that has lambda functions, because of implementation
considerations. I think the full version is implementable.

By the way, the event handler thing is a perfect example of why you would want
to store a closure object. It's a feature that has been asked many times by
users of GtkAda, both inside and outside of AdaCore.

> I think perhaps you are trying to make lambdas solve all problems,
> when in fact event handlers are quite naturally represented as objects
> with their dispatching operations being the call backs.  There are
> some languages where all you have are lambda expressions, and you end up
> using them for everything.

There are no such languages in wide use today, when even Scheme has a
standardized object system. However, there are a ton of languages (Python,
Javascript, OCaml, Scala, C++) where you could use one or the other, but where
people *consistently choose* to use lambda functions to do that kind of thing in
a certain subset of cases, because they are a much more expressive way of doing
the same thing, where all you can see as the reader of the code is the part of
the code that expresses the intent of the programmer.

>   But for languages that have support for dynamic dispatch already,
> the need for function objects is much reduced in my view, and
> generalizing them too much is just adding complexity and redundancy to the
> language definition.

Well, the fact that they added lambda functions to Java, and that they are
closures, is a good counter-argument to this. They could already do everything
with objects, but still decided to add lambdas. It does not mean we should add
them. However, in my view, it sure means that if we add them they should behave
consistently with user expectations however.

> In Java, I believe these might end up just being syntactic sugar
> around declaring a new class with a single operation.  We could go in
> that direction for Ada if we think it is important to be able to store
> these things, but I think that is yet another step that seems even
> less important than being able to return them.

Yes, in Java they implemented them as anonymous classes, which are closures, and
hence respect the expectations of the users regarding lambdas.

> I think you also have to think about the debugging problem.  You are
> effectively creating large numbers of partial stack contexts, each of
> which is a potentially very complex piece of state. Trying to debug
> such a situation is much harder than debugging a more
> data-object-based world, where the contents of the fields of a record,
> or equivalent, represents the current state of things. Yes it is kind
> of cool that you can do all kinds of amazing things with lambdas, but
> I am not convinced that is the clearest, most efficient, and most
> verifiable way to solve the problem.  We should be really sure we need
> to add all of this complexity on top of all the features already available for
> solving such problems.

That's a good point, but there are solutions to that that already exist. The
call to the lambda expression will appear in the context it is declared, where
you can naturally refer to the variables it closes over.

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

From: Tucker Taft
Sent: Thursday, October 13, 2016  2:03 PM

>> I am not convinced we need to store these, so I would have to see the
>> problem we are trying to solve.  I am sure you could construct an
>> example that could take advantage of storing them, but I would
>> suspect (hope?) that there are other ways of accomplishing the same
>> thing without doing so.  I am not a big fan of burying everything in
>> lambdas (as explained a bit more below).
>
> Well, the problem is that you are then inventing a feature called
> lambda functions that behaves slightly differently from the way it
> behaves in *every* other languages that has lambda functions, because
> of implementation considerations. I think the full version is implementable.

I think you need to distinguish between garbage-collected languages where
everything of interest lives on the heap and has an indefinite lifetime, from
languages that attempt to keep most objects on a stack.  In C++11 they say you
are on your own from a safety point of view if you capture a "reference" to a
local variable.  So clearly there are more limitations when objects might be
stack based, or can't be copied.  Also, as you start expecting the compiler to
"do the right thing" and either complain or somehow automatically copy data that
is referenced, implementation expense goes up and the complexity of the
limitations from the user's perspective also grows.

I think a basic limitation such as treating these like objects of a limited type
that you can temporarily give a name either via rename or a build-in-place
declaration, but that you can't store in some global variable, might be
reasonable and would cover 90% of the cases of interest, without opening
ourselves up to the complexity of a C++-like solution.

> By the way, the event handler thing is a perfect example of why you
> would want to store a closure object. It's a feature that has been
> asked many times by users of GtkAda, both inside and outside of AdaCore. ...

I wonder whether some good syntactic sugar could make this work using tagged
types and single-operation interfaces.  This is not a case where you need to
construct the event handler dynamically and/or return it from a function.  You
just want an easy way to describe what happens when the event occurs, without
the heavy syntax burden of defining a new type with a new operation, and then
adding an appropriately initialized object of that type onto a list.

Another option I suppose might be to support something like an event channel.
You put your event channel on one or more lists, and then read from the channel
and write a simple "case" statement to handle the events as they arrive.

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

From: Raphael Amiard
Sent: Thursday, October 13, 2016  2:28 PM

>> Well, the problem is that you are then inventing a feature called
>> lambda functions that behaves slightly differently from the way it
>> behaves in *every* other languages that has lambda functions, because
>> of implementation considerations. I think the full version is
>> implementable.
>
> I think you need to distinguish between garbage-collected languages
> where everything of interest lives on the heap and has an indefinite
> lifetime, from languages that attempt to keep most objects on a stack.
> In C++11 they say you are on your own from a safety point of view if
> you capture a "reference" to a local variable.

Yes, but you can still capture a value, so it makes all the relevant cases that
I talked about possible in C++11. For capturing references you use
smart-pointers, which are captured by value, but the value of a smart-pointer is
really a reference so all is well.

>   So clearly there are more limitations when objects might be stack
> based, or can't be copied.  Also, as you start expecting the compiler
> to "do the right thing" and either complain or somehow automatically
> copy data that is referenced, implementation expense goes up and the
> complexity of the limitations from the user's perspective also grows.

No, this is the way that it is supposed to work (capture by value). You have an
option for capture by reference in C++ but byval is always used in practice. If
you want reference semantics you use a smart-pointer.

> I think a basic limitation such as treating these like objects of a limited
> type that you can temporarily give a name either via rename or a
> build-in-place declaration, but that you can't store in some global variable,
> might be reasonable and would cover 90% of the cases of interest, without
> opening ourselves up to the complexity of a C++-like solution.

You can put an object of limited type in a global access variable, by allocating
the object dynamically. If we have such an option for lambdas, and make them
limited, then I'm 100% fine with that solution.

I think referencing outer variable needs to be treated like if those were
implicit

>>
>> By the way, the event handler thing is a perfect example of why you would
>> want to store a closure object. It's a feature that has been asked many times
>> by users of GtkAda, both inside and outside of AdaCore. ...
>
> I wonder whether some good syntactic sugar could make this work using tagged
> types and single-operation interfaces.

It could but raises several problems:

1. In C++ the equivalence works because you can overload the call operator. We
could provide something similar I guess, via an aspect for example.
2. The type of your closure, instead of being a special built-in access to
function type, then becomes a variadic generic function type. We don't have
variadic generics, and we'd still have to instantiate and name specific generic
for every closure instance, which is a pain.

Meta-point: This is IMHO the third time that it turns out that we have
weaknesses in the generic model that would force us to have built-in solutions
instead of hybrid library ones, or completely library ones:

1. The first is the type of generators.
2. The second is the type of lambda functions.
3. The third is the 'Reduce function/built-in.

>   This is not a case where you need to construct the event handler dynamically
> and/or return it from a function.  You just want an easy way to describe what
> happens when the event occurs, without the heavy syntax burden of defining a
> new type with a new operation, and then adding an appropriately initialized
> object of that type onto a list.

Well yeah indeed, but what you're doing is essentially a custom version of the
general lambda mechanism: Capturing the necessary variables, wrapping that in an
object with a call, and returning it as a function.

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

From: Erhard Ploedereder
Sent: Thursday, October 13, 2016  11:20 AM

> It seems what is being requested is the ability to write something
> like
> this:
>    function Filter(Pattern : String) return access function (X :
> String) return Boolean; This will return a filter which returns True
> only if X matches the pattern.

Indeed. Coincidentally, when Java came up with lambdas, this capability of
composing and returning functions, or using currying strategies to obtain
partially instantiated functions was THE major feature that at least one of our
industrial customer was heavily interested in. (I had a student doing a thesis
on Java lambdas for this customer - unfortunately not a good one.) And I see
what my functionally inclined grad students produce: heavy use of this
capability.

> Trying to write this:
>
>     function Filter(Pattern : String)
>       return access function (X : String) return Boolean is
>     begin
>         return (function (X) return Match(X, Pattern));
>     end Filter;
>
> This is do-able by treating such a result as living on the secondary
> stack, I suppose, which we would *not* cut back until the returned
> function is no longer being used.

Well, or have lambdas carry closures, i. e., a record of all values of free
variables at the time of lambda creation. Admittedly, this differs from Ada,
where up-level variables are referenced, not locally copied, but this is how
assignment-less functional languages operate. And, having references to anything
not global in a closure should be an accessibility violation - no exceptions.

Secondary stacks for all lambda creators in their textual region? Surely an
unbearable cost, especially when folks really get into recursive functional
programming.

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

From: Tucker Taft
Sent: Thursday, October 13, 2016  11:48 AM

>> This is do-able by treating such a result as living on the secondary
>> stack, I suppose, which we would *not* cut back until the returned
>> function is no longer being used.
>
> Well, or have lambdas carry closures, i. e., a record of all values of
> free variables at the time of lambda creation. Admittedly, this
> differs from Ada, where up-level variables are referenced, not locally
> copied, but this is how assignment-less functional languages operate.

Particularly challenging when dealing with objects of a limited type.

> ... And,
> having references to anything not global in a closure should be an
> accessibility violation - no exceptions.

OK, so you are saying you cannot refer to local variables, only parameters and
globals, in a returned function expression?  Seems pretty limiting.  Basically
you have to put all of the computation inside the function expression itself,
which seems kind of unpleasant, especially if you have some computations you
could do once in advance, since they are independent of the parameters passed to
the function expression.

If we go that route, we should probably impose the same limitations as used by
access discriminants, requiring the use of "aliased" parameters if referring to
[in] out parameters, presuming that we are capturing the 'Access of all free
variables that we are not copying.  That is, we would have a block of 'Access
values for such free variables that was part of the representation of such a
function expression.

> Secondary stacks for all lambda creators in their textual region?
> Surely an unbearable cost, especially when folks really get into
> recursive functional programming.

It seems you could optimize by storing on the secondary stack only those things
that are actually referenced (directly or indirectly) in the returned function
expression.  I suggested, for simplicity, that you could put everything on the
secondary stack, but clearly you can do better than that.

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

From: Erhard Ploedereder
Sent: Thursday, October 13, 2016  2:48 PM

>> ... And,
>> having references to anything not global in a closure should be an
>> accessibility violation - no exceptions.
>
> OK, so you are saying you cannot refer to local variables, only
> parameters and globals, in a returned function expression?

No, you can of course refer to uplevel variables, but what you get is the value
that this entity held when the lambda was created. You do not get an opportunity
to assign to the original, because all you hold is a copy. If you assign (if
permitted at all??), then you change the copy.

Absent assignments, this semantics is indistinguishable from the Ada semantics
of uplevel addressing. With assignments to the up-level address inside or
outside, the semantics obviously differ.

Put differently, up-level variables are effectively cached locally, and that is
the semantics of the new feature called lambdas.

The accessibility issue arises when said value is in turn a reference, e.g. the
code refers to an up-level variable of access type, which in turn references
something. The reference value copied from the local variable better be to a
global entity, nothing else. (One could refine this, but the rules will be as
inscrutable as today's accessibility rules.)

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

From: Erhard Ploedereder
Sent: Thursday, October 13, 2016  4:23 PM

>>     function Filter(Pattern : String)
>>       return access function (X : String) return Boolean is
>>     begin
>>         return (function (X) return Match(X, Pattern));
>>     end Filter;

more on Syntax (and Semantics): I am not so sure that I like the lambda to be
returned typed as an access function ...., implying that it can be assigned to
some variables, hooked into dispatch vectors, etc.

I would much prefer an ability to name, but not necessarily to assign these
values. E.g.,

     function Filter(Pattern : String)
       return function (X : String) return Boolean is
     begin
         return (function (X) return Match(X, Pattern));
     end Filter;

and if anybody wants a name for the lambda:

function ParisMatch(X : String) return Boolean is Filter("Paris");

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

From: Tucker Taft
Sent: Tuesday, February 27, 2018  6:32 PM

I have added wording to this AI on "function expressions". [This is version
/04 of the AI - ED.]

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

From: Brad Moore
Sent: Friday, March 2, 2018  11:32 PM

I like the idea of function expressions overall. I have just a couple of
comments.

>> We are only supporting defining anonymous functions using this 
>> proposed "function_expression" construct.  Anonymous procedures are 
>> nicely handled with the loop-body proposal (AI12-0189).

Not really. The loop-body proposal only applies to a limited subset of cases
where anonymous procedures could be used. Those where the anonymous procedure
is the body of the loop. Not all anonymous procedures fit this use case.

For example, for 'Reduce we were talking about allowing a reducer in the form
of a procedure of the form;
    procedure Reduce (L : in out Item, R : Item);

which might be appropriate when Item is a large matrix type.

It might be nice to write a combiner function as a function expression in some
cases, for instance, which I presume would be allowed by the AI, (for
combiners that are functions). Similarly, I presume one could use function 
expressions for generic actuals when instantiating a generic. 

eg. See below

>> In any case, mixing
>> statements inside expressions seems like a bad idea.  Also, we don't 
>> have "expression procedures" so it doesn't seem so bad that we don't 
>> have "procedure expressions" ;-).

This seems like the better argument.

>> !example
>> 
>>    --  Replace control chars with '?'
>>    Ada.Strings.Fixed.Translate
>>      (Str, (function (C) return (if C < ' ' then '?' else C)));
>> 
>>    --  Procedure for plotting a function
>>    procedure Plot_Graph
>>      (Fun : access function (X : Float) return Float;
>>       Start, Stop : Float);
>> 
>>    ...
>> 
>>    --  Plot a graph of X-squared from 1 to 20
>>    Plot_Graph (Fun => (function (Z) return Z**2),
>>                Start => 1.0, Stop => 20.0);
>> 

I have another example for consideration.

   subtype Degrees is Integer;

   -- Instantiate a list of degree values of a circle, eg. -1 = 359 = 720
   package Degree_Lists is new
     Ada.Containers.Doubly_Linked_Lists (Element_Type => Degrees,
                                         "="          => (function (L, R) return (L mod 360 = R mod 360)));

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

Questions? Ask the ACAA Technical Agent