  lua-l archive

• Subject: Re: Lambdas
• From: Philippe Verdy <verdy_p@...>
• Date: Mon, 19 Nov 2018 01:41:19 +0100

Closed-over variables CANNOT be ignored in lambda-calculsu; the faact that there's a closure in addition to "standard function variables" does not change the fact that they are real varibles of the function (in a pure mathematical definition).

This is also the base of functional languages, where all side effects must be taken into account, trackable and must also be reversible (as much as possible: you cannot reverse an I/O operation that has already occured, but I/O can still be simulated by reversible virtual I/O with a proxy agent emulating a real I/O agent and only buffering their input/output).

Closed-over variables ARE actual functional parameters of functions, independantly of the syntaxic features of a programming language.

Anyway, for the case of Lua finctions, that have multiple inputs and mutliple outputs, this can be transformed into true lambda functions by adding the environment to the lambda input parameters and to the lambda output parameters. inut and output parameters are like vectors; the lambda transforms then the input vector into an output vector.

If we want a syntax to represent this, using only input parameters is not enough, even for functions that don't use anything from the Lau environment like:
square = function(x) return x^2 end
dist = function(x,y) return (x^2+y^2)^0.5 end
The lambdas should be:
square = \x\y( y=x^2 )
dist = \x,y\d( d= (x^2+y^2)^0.5 )

We can note also that operators in Lua are actually functions taken from the environment, if we consider this, then the complete lambdas are
square = \x,^\y( y=x^2 )
dist = \x,y,+,^\d( d= (x^2+y^2)^0.5 )

Note that in that notation the "\" separates the input and output parameters, none are forgotten, they form two separate comma-separated ordered lists (i.e. n-tuples).

Lambda calculus also fordids assignments that overwrite variables, it needs equations, so that the function is modeled as a projection (a surjection): this is not a problem if there are branch controls (if/else, switch) but it is challenging if the function contains loops, unless there's another lambda-calculus used to represent sets of operands, overwhich the loop is applied, and the loop body is also modeled as a lambda function...

The "\input\output" above uses a notation where each "\" represents a the logical "forall" in mathematics, but we need something to represent loop constraints (notably that a variable is a member of a set delimited by other variables, we can use this notation: "\variable=(set _expression_)" to represent this in equations:
sum = function(...) local s = 0; for x in ... do s = s + x end; return s; end
First, the content of the inner loop becomes a lambda:
(\s, x, + \t ( t = s + x))
then the loop itself constrains x in "..." to produce an additional aggregate result in output when applying the previous lambda repeatedly
f = (\s, x, + \t ( t = s + x))
loop = \input,+\sum = (\x=input,+\ sum  f), i.e.
loop = (\input,+\ sum   = (\x=input,+\ sum  (\s, x, + \t ( t = s + x)) ))
there's then the first assignment s=0 which becomes an equation used to represent the input of the loop, the output is the sum (+) of this input and the output of the previous loop:
local s=0; return t = loop(s), i.e.
(\input,+\output = (\x=input,+\sum (\s, x, + \t ( t = s + x)) ))(s = 0)
We can hide this local variable which is now constant and bind this constant directly to the input:
(\0,+\output = (\x=input,+\sum (\s, x, + \t ( t = s + x)) ))
And then simplify it inside the first lambda (removing it from its first parameter):
(\+\sum = (\x=0,+\sum (\s, x, + \t ( t = s + x)) ))
now this is a completely defined and resolved (reduced) lambda equation which represents the initial Lua function !