Lambda terms

[cscherrer]

Hi,

There are currently a couple of ways to represent functions:

1. For Julia functions, all we can do is evaluate them. In particular, we don't know much about types, and there's no clean way to build new ones as we're doing rewrites.
2. FnTypes have nice type information, but their behavior is opaque.

What do you think about having a Lambda term to try to get the best qualities of both options? Something like

struct Lambda{X,Y} <: Symbolic{FnType{Tuple{X}, Y}}
    x :: Sym{X}
    y :: Symbolic{Y}
end

function Lambda(p::Pair{Sym{X}, SY}) where {X, Y, SY <: Symbolic{Y}}
    return Lambda{X,Y}(p.first, p.second)
end

Then, for example,

julia> @syms i::Int x::Float64
(i, x)

julia> Lambda(i => x*i)
Lambda{Int64, Float64}(i, i*x)

It seems like this could also make sums nicer, since (I think) we'd be able to write

s = sum(Lambda(i => x*i), 1:10)

[ChrisRackauckas]

Func is for this.

[cscherrer]

Where is that?

[YingboMa]

Haha, that's from our internal discussions. The feature is planned, and we are working on that.

[cscherrer]

Helpful to have context for the comment, thanks @YingboMa

[cscherrer]

@YingboMa Is there open discussion of where things are going? This library is already a critical dependency for my work.

[cscherrer]

@shashi Any thoughts on this?

[shashi]

Hi check out #183

On Jan 28, 2021, at 8:32 PM, Chad Scherrer notifications@github.com wrote:

 @shashi Any thoughts on this?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[shashi]

This is a nice idea, Func is the same as this, but without the type parameters like you have here. It's geared more towards writing nice Julia functions from symbolic expressions.

Why not just use the type in your OP?

but their behavior is opaque.

It's pretty straightforward to see what FnType means. There's just no function body.

Why do you call it "lambda term"? What would be the interface definition?

[cscherrer]

Func is the same as this, but without the type parameters like you have here. It's geared more towards writing nice Julia functions from symbolic expressions.

That's the idea here too, but having the type information makes it much more reliable.

Why not just use the type in your OP?

Maybe I could, I'm just not sure if there are implementation subtleties I need to watch out for. Does the code snippet I have in the OP seem idiomatic to you, in terms of this library?

It's pretty straightforward to see what FnType means. There's just no function body.

Right, that's what I mean by opaque. There's no way to crack it open and look inside :)

Why do you call it "lambda term"? What would be the interface definition?

It's a lambda in the sense of an anonymous function, like in the lambda calculus. Python also has something like this they call lambda.

I had originally thought we could use ->, but that's treated specially. For example,

help?> ->
search:

  No documentation found.

  Binding -> does not exist.

So maybe ↦ (\mapsto)? That's standard in math, though I haven't seen it in programming languages.

[cscherrer]

@shashi I think this could work:

using SymbolicUtils

using SymbolicUtils: FnType, Symbolic, Sym, symtype
import Base

struct Lambda{X,Y,SX,SY} <: Symbolic{FnType{Tuple{X}, Y}}
    x :: SX
    y :: SY
end

↦(x::SX, y::SY) where {SX, SY} = Lambda{symtype(x), symtype(y), SX, SY}(x,y)

function Base.show(io::IO, λ::Lambda)
    print(io, "(", λ.x, " ↦ ", λ.y, ")")
end

Base.sum(λ::Lambda, x::AbstractArray) = term(sum, λ, x; type=symtype(λ.y))

Then for example,

julia> @syms i::Int x::Real
(i, x)

julia> λ = i ↦ i*x
(i ↦ i*x)

julia> symtype(λ)
FnType{Tuple{Int64}, Real}

julia> sum(λ, 1:10)
sum((i ↦ i*x), 1:10)

What would you think of a PR for this? I think it's much cleaner than how I had been writing sums.

[cscherrer]

cc @dpsanders (since we had talked about sums)

[cscherrer]

Need to implement some more methods, more to come...

[shashi]

It's not clear to me that we should be defining Base.sum etc (where do we stop?) and it would be piracy if Lambda was here and you defined the methods outside this package. And for now I'm not yet sure we should have 2 ways of representing a function in this package... (vs Code.Func). It would be perfectly good to use this in your own code though.

Note that going forward we may not have the Symbolic type. So I would discourage you from relying on it to give you symtype etc, just define the method on your type.

I would imagine the first method to define would be (::Lambda)(..)?

[cscherrer]

It's not clear to me that we should be defining Base.sum etc (where do we stop?)

Good point. I think it's important to be able to have symbolic expressions containing arbitrary function calls. This might require something like an IRTools dynamo, since there's no way to dispatch on functions.

And for now I'm not yet sure we should have 2 ways of representing a function in this package... (vs Code.Func).

I don't have a good understanding yet of what Func can do. I guess the docs are just a preview, right? SymbolicUtils.Code doesn't exist yet.

Note that going forward we may not have the Symbolic type. So I would discourage you from relying on it to give you symtype etc, just define the method on your type.

This is very concerning. It will be very difficult to dispatch if there's no type to use for this. For example, it's a big help for functions to be able to behave differently for an AbstractArray vs a Symbolic{<: AbstractArray}. Losing this would cost me a lot of time.

I would imagine the first method to define would be (::Lambda)(..)?

Yes, but we need to be careful. I think this will need to just create a term, rather than actually do the substitution. Otherwise sums or maps will fully expand.

[shashi]

Good point. I think it's important to be able to have symbolic expressions containing arbitrary function calls. This might require something like an IRTools dynamo, since there's no way to dispatch on functions.

78

behave differently for an AbstractArray vs a Symbolic{<: AbstractArray}. Losing this would cost me a lot of time.

What I mean is the reason for Symbolic abstract type is a little confusing now that we solely rely on the interface. But we will still leave Symbolic{T} as a type alias for Union{Sym{T}, Term{T}, Add{T}, ...}, which means packages other than SymbolicUtils would not be able to extend it. This is so that we actually make sure the interface does not rely on this super type and make it less confusing to onlookers.