Add closures to Stan language

[VMatthijs]

The point of this feature is to add lexical closures to the Stan language.
For a possible use case, see e.g. this thread .

It should be relatively straightforward to add these in to stanc3. The AST already treats function definitions as statements that could theoretically occur anywhere in the program. It is the parser that currently disallows that. The point of this issue will be to modify the parser to allow function definitions anywhere and to deprecate the functions block. A challenge would be to change the logic in the semantic check to now check at the level of the whole program whether there is a function declaration which is missing a definition.

A strong requirement for the PR would be a decent set of good and bad test models to make sure sensible error messages are generated.

[bob-carpenter]

I think it would make sense to get a design for this before opening an issue. Is there a proposed syntax you have in mind? It's hard to have design discussions in issue comments as there's no quoting or LaTeX support.

Is the idea here that a function currently declared in the functions block would just be declared in the data block because it wouldn't need any closure variables? And just to kick off the syntax discussion, I think that'd look like this:

data {
  (real, real):real hypoteneuse = (real x1, real x2).sqrt(x1^2 + x2^2);
  ...

where we'd do type inference to deduce the return type of the function on the right-hand side to make sure it matched the declaration on the left-hand side. I'm not at all wedded to any of this syntax, by the way---it's just similar to what C++11 does for binding and what I've done in the manual for describing function types.

[VMatthijs]

Ah, for the closures (before we add higher-order functions and lambdas etc which you seem to be describing a syntax for), I imagined we could just keep the current syntax, e.g.:

transformed data {
  real x = 42;
  void an_example_of_a_closure() { // here we define it
    print(x);
  }
  x = 17;
  an_example_of_a_closure(); // here we use it, still prints 42
}

Of course, the semantic check to make sure the return type matches the declaration needs to happen, but the semantic check is currently written in such a way that that should still be true if function definitions occur elsewhere in code than in the functions block.

In my mind they should be allowed anywhere in the program where a statement is currently allowed.
For example, we should also be able to have locally defined functions like

transformed data {
  real x = 42;
  {
    void an_example_of_a_closure() { // here we define it
      print(x);
    }
    an_example_of_a_closure(); // here we use it
  }
  an_example_of_a_closure(); // error here as it is no longer in scope.
}

[bob-carpenter]

Ah, for the closures (before we add higher-order functions and lambdas etc), I imagined we could just keep the current syntax, e.g.:

I hadn't thought of that :-) We just get static lexical scope on identifiers then, right?

[VMatthijs]

Yes, that's what I was thinking. This could be quite useful and wouldn't be super hard to implement, I hope, as we could just use C++'s closures for code generation.

The higher-order functions and lambdas seem like a separate issue. (Even though they often appear together with closures in languages.) There, we'd definitely need to think carefully about a spec.

[bob-carpenter]

Yes, that's what I was thinking. This could be quite useful and wouldn't be super hard to implement, I hope, as we could just use C++'s closures for code generation.

Right. That's been on the table since we opened up C++11.

The higher-order functions and lambdas seem like a separate issue. (Even though they often appear together with closures in languages.) There, we'd definitely need to think carefully about a spec.

I think they're very closely related because we can think of a function definition with static lexical scope, such as the following to capture y,

real foo(real x) { return x^3 - y; }

as syntactic sugar for for the more explicit closure form

(real):real foo = (real x).{ return x^3 - y; }

This way, higher-order functions are an orthogonal concern

[VMatthijs]

Ah, right! I see what you mean. You could also theoretically keep the three notions of closures (i.e. functions which store the values of variables from their enclosing scope), lambdas (i.e. anonymous functions) and higher-order functions (functions which take functions as arguments) separate. I can imagine having a language which has any of these features independently of the others. Personally, my feeling is that closures and higher-order functions would be very useful for Stan, while I am not dead set on having lambdas (seeing that I cannot imagine people using functional programming so heavily in Stan that it becomes cumbersome to name functions, especially as we do not have type inference so people will still need to type the types of the arguments on the lambdas).

Personally, I was thinking about the notations
(real) -> real foo = fun (real x) -> { return x^3 - y; }
for function types and lambdas.
That is to be somewhat consistent with common notations.

Notations I've seen for function types (let's do a multi-argument function for generality):
(real, vector) -> int (SML/NJ, OCaml, Coq, Rust)
(real, vector) => int (Haskell, Agda, Scala)
Func<(real, vector), int> (C#)
Function<(real, vector), int> (Java)
function<int(real, vector)> (C++)

Notations that I've seen for lambdas:
fun (x, z) -> x^3 - y (OCaml, Coq)
(x, z) => { return x^3 - y} (Scala)
(x, z) -> { return x^3 - y} (Java)
[]( real x, vector z) { return x^3 - y} (C++)
\(x, z) -> x^3 - y (Haskell, Agda)
fn (x,z) -> { x^3 - y (Rust)
fn [x,z] -> (- (^ x 3) y) (Clojure)

I'm sure there are many more relevant ones, but these are the first that come to mind.

Generally, I have a preference for self-explanatory syntax that is easy to Google, e.g. fun rather than just using some symbol like []. When it comes to the types, I am a bit torn between something like -> and Fun or Func as the latter two can become hard to read when you start nesting them, like for the signature of ODE solvers.
`
I'd like to decide on a syntax for higher order types before we release the new compiler, so the type error messages for functions can already use the function type syntax.

We should probably treat lambdas à la Church rather than Curry (i.e. type annotations on the variable binders) as that would make type checking much easier.

[bob-carpenter]

(real)->real foo = fun (x) -> { return x^3 - y; }

I have a bunch of issues with this. I'm not keen on compound symbols like ->. They look terrible in documentation because the x-level of the '-' never match that of the '>'. I do see the motivation for the types, as it's standard math notation, but not for the lambda abstract/action which would be |-> if we want to add compound symbols. I prefer ':' for the type and a more lambda-oriented notation with '.' for the abstraction. I don't see the point of writing "fun" (I do see the point of having fun, though!). Should there be a semicolon at the end of all this? I think we need it if the whole function abstraction is treated as an expression, which it's going to have to be if we start adding higher-order functions. I'm confused about typing. The right hand side is polymorphic because there's no argument type. x could be a vector or a scalar here (or at least it could be once we vectorize ^). So we'd need a polymorphic type system to evaluate the right-hand side. Even still, I see a problem with declaring foo with a type like (real) -> real, because we immediately lose the polymorphism on assignment to a fully instantiated type like (real) -> real. I was thinking of something more strongly typed along the lines of C++, good idea, so that the declarations matched function sigs more closely, e.g., (real):real foo = (real x).{ return x^3 - y; }; That may turn out to be too limiting. P.S. I'd still rather be having this discussion somewhere else than issue commentary, but this is Sean's repo to manage and I'll continue to reply here unless he suggests otherwise.

…

On Jan 18, 2019, at 9:39 AM, Matthijs Vákár ***@***.***> wrote: Ah, right! I see what you mean. So we might still want to decide on a syntax for lambda-abstractions and for function type constructors. Personally, I was thinking about (real)->real foo = fun (x) -> { return x^3 - y; } for that one, or the short-hand (which only applies to functions with a single argument) real->real foo = fun x -> { return x^3 - y; }. That is to be consistent with common notations. Notations I've seen for function types (let's do a multi-argument function for generality): (real, vector) -> int (SML/NJ, OCaml, Coq, Rust) (real, vector) => int (Haskell, Agda, Scala) Func<(real, vector), int> (C#) Function<(real, vector), int> (Java) function<int(real, vector)> (C++) — You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

[seantalts]

I think you're right that this belongs somewhere else. I'd propose we use the design-docs repo (and maybe rename it to RFCs to follow Rust?) to post proposals for additions to the Stan language and allow users to comment.

[seantalts]

I'm going to close this issue for now; @VMatthijs if you or @bob-carpenter (or whoever) want to make a proposal for closure / lambda syntax additions to Stan, please add an RFC for it in the design-docs repo (instructions and template live in that repo).

[nhuurre]

The closure design-doc was accepted a while ago. Should we reopen this?

[seantalts]

Yeah! Definitely want closures

…

On Tue, Feb 4, 2020 at 13:47 Niko Huurre ***@***.***> wrote: The closure design-doc <stan-dev/design-docs#6> was accepted a while ago. Should we reopen this? — You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub <#29?email_source=notifications&email_token=AAGET3FETOCNBHIUQ47HKNTRBGZ5VA5CNFSM4GPNEWWKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKYX7BQ#issuecomment-582057862>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGET3CVJBUGMXQIGYLVUELRBGZ5VANCNFSM4GPNEWWA> .