Add support for first-class functions in expressions

[anandthakker]

We've now seen two cases where first-class functions would make sense:

• Referencing capture groups in a regular expression replace operation (see Implement "regex" expression that returns an array of match groups or… #6228 (comment))
• Providing a reduce function for aggregating feature properties on clustered data ([WIP] add cluster mapreduce feature to style spec #7004)

Let's explore adding function types to the expression language and a syntax for defining (and applying?) function values. Initial proposal to get things started:

---

A function value is defined with ["fn", "a", "b", "c", (etc.), function_body_expression], where a, b, c, ... are parameter names, and function_expression is an expression that may include ["var", paramter_name] expressions to reference parameter values. There is no way to explicitly specify a function's parameter or return types: they must be inferable from the context in which it is being used.

Examples:

["fn", "a", "b", ["+", ["var", "a"], ["var", "b"]]]

["replace", ["get", "name"], "(\w+),\s*(\w+)",
    ["fn", "g1", "g2", [ "concat", ["var", "g1"], " ", ["upcase", ["var", "g2"]] ] ]
]

A function is applied with ["apply", fn_expression, a_expr, b_expr, (etc.)], where a_expr, b_expr, etc. are the arguments to the fn_expression.

Example:

["let", "sum", ["fn", "a", "b", ["+", ["var", "a"], ["var", "b"]]],
  ["apply", ["var", "sum"], 1, 2]
]

function_body_expression is lexically scoped: it can reference any let vars that are in scope at the site of the "fn" definition. Recursion is not allowed: if the "fn" definition itself is being bound to a variable, that variable is not in scope within function_body_expression.

Subtyping: if a function of type (T) -> U is expected, then a function (X) -> Y is valid as long as T is a subtype of X and Y is a subtype of U. E.g.: if (string, value) -> value is expected, then (string, string) -> number is valid.

[anandthakker]

cc @mapbox/studio @mapbox/maps-design @mapbox/maps-ios @mapbox/maps-android

[ansis]

Recursion is not allowed: if the "fn" definition itself is being bound to a variable, that variable is not in scope within function_body_expression.

Yep! but I think the restrictions need to be a bit broader than that to prevent recursion. Some cases that come time mind are:

• the function gets passed to itself as an argument
• a second function which calls the first function gets passed to the first function as an argument

Would we need to construct a graph of all possible function calls and check for cycles?

[anandthakker]

Oof, yeah good call, @ansis... I'd originally omitted apply from the design, thinking that function values would only be used as arguments to built-in operators, but if we're going to have apply, I think we'd need to either check for cycles or disallow named functions.

[dmiluski]

Hi Folks, as a developer recently using the Exp syntax I was seeing if I could add some developer perspective as a swift iOS developer.

🧑‍⚖️ Full disclosure

This is very green observation into the modeling structure/available info, so I don't have the context as to why/how it was approached previously.

🗒️ Context

Given the Expression is providing a wrapper for JSON, it doesn't easily convey what options are available, or how to leverage them. This could lead to user mistakes when entering, as well as a harder hurdle to step through to figure out how to customize a display on a platform (eg. iOS)

👀 Personal Observation

While I see stuff like this on web often (find/replace), now that I use a strongly typed system, requests like this have left me uneasy making these white-box knowledge mutations. In this example, learning the string/const and expression structure was not obvious. Without that example, I don't know if I would have been able to figure it out.

Current Example of Layer opacity configuration

var circleLayer = CircleLayer(id: IdentifierString.waypointCircleLayer)
circleLayer.source = IdentifierString.waypointSource
let opacity = Exp(.switchCase) {
            Exp(.any) {
                Exp(.get) {
                    "waypointCompleted"
                }
            }
            0.5
            1
        }
circleLayer.paint?.circleOpacity = .expression(opacity)

vs

If possible, a strongly typed closure syntax that could wrap these model requirements could make development much quicker (allowing for auto-complete), and less abstract (strongly typed) to configure.

// Closure called to dictate action which includes strongly typed Waypoint model, which includes context into available properties accessible for use.
let opacityClosure = { waypoint in 
  return waypoint.isCompleted ? 0.5 : 1.0
}

Additionally, When reading the concern about recursion, as a developer I don't see this is as big of an issue as the worry around it. Given verbose @escaping closure annotations has made it more clear when self is being captured, some notes on performed on background thread as well as don't call x may be more than enough documentation to see a friendlier developer use case.

    class Bar {
        static let foo: String = {
            // Infinite Loop accessing resource currently under construction
            // as a developer I learn very quickly not to do this
            Bar.foo
        }()
    }
 
 // Given a strongly available passed in, there is a much less likely chance that a developer will reach out to additional models.
 [1, 2, 3, 4].map(String.init)

eg.

1. URLSession task result caught many folks off guard that its result came on a background thread, yet people quickly learned.
2. Infinite recursion can also occur with lazily loaded or static variables, yet developers learn very quickly not to do it. Whereby crashes gives immediate feedback. Given the parameter of a type in question, the requirements to reach out to the system vastly go down and reduce the likelihood this would take place. eg. reduce/map/filter/etc..

Tools to assist: Instruments -> Leaks, CPU, Crash Reports, Thread sanitizer

Modeling

When reviewing the code base, I see that this expression modeling closely aligns with the underlying JSON to support Encode/Decode support. While not yet obvious how to model, I can assure you, if we want to make the map customization experiencing easier for developers, closure syntax + strong modeling would create a friendly novice playground.