Discussion:
Lambdas
Dirk Laurie
2018-11-18 18:37:03 UTC
Permalink
Please refresh my memory!

There have been numerous discussions on this list for lambda
notations. Were any of those accompanied by a patch so that one could
try them out?
Philippe Verdy
2018-11-18 19:03:13 UTC
Permalink
Lambda functions in Lua are just standard functions which are not bound to
a name, i.e. expressions of the form "function() ... end" or
"function(parameters...) ... end"

You can declare a function with a bound name by inserting it between
"function" and the next "(", in which case it will be also bound to a new
local variable (or will replace its value if you have a local variable); it
does not replace a function or variable with identical name in the current
outer scope.

You can also bind a local function to give it as the value of an existing
local or outer variable (if there's none, i.e. this variable name has a nil
value) then a new local varaible will be created, otherwise the lambda
function will overwrite the value of the existing variable.

So "function f(x)... end" is not completely equivalent to "f= function(x)
... end": the first one declares a new local variable named "f", the second
overwrites an existing variable "f" in scope, or creates a new local
variable.

Lua not really know if your function is named or not: it may have several
names (given as different keys of the same table, or different or identical
names in distinct tables). It always runs lambda functions.

When debugging Lua programs, Lua will attempt to locate the name of the
function by performing lookups in the stack of closures, to see if there
environment defines a table of variable names bound to the function defined
for the closure: if it locate a table, it will then scan all keys on this
table to see if one of the keys is mapped to the function.

You may initially create a local function bound to a local name, then
assign it to another variable in scope with another name, then when the
local variable is no longer in scope or reassigned another value, that
function will no longer be bound to its initial name. So a function may
have its "most local" name changed over time. function names are not
significant for their execution, they are interesting only for debuggers.
What only matters are the anonymous lambda functions that every function
has.

Note that all lambda functions are not just a series of instructions: they
also have a closure in which they are defined (that closure may not even
have any external variable in rare extreme cases where access to extertnal
variables was blocked by a function set in the closure's metatable
"__index" set to a function that is always returning nil, and all what your
lambda function will have access to are the upvalues in the call stack,
where the values of function unput parameters are passed and where the
function can return its output results)
Post by Dirk Laurie
Please refresh my memory!
There have been numerous discussions on this list for lambda
notations. Were any of those accompanied by a patch so that one could
try them out?
Philippe Verdy
2018-11-18 19:44:51 UTC
Permalink
You may also want a more restrictive definition of lambda functions: it
would be a functions which makes no access at all to its environment (i.e.
where its closure contains no references to other external variables), for
example: function(x) return x^2 end
Post by Philippe Verdy
Lambda functions in Lua are just standard functions which are not bound to
a name, i.e. expressions of the form "function() ... end" or
"function(parameters...) ... end"
You can declare a function with a bound name by inserting it between
"function" and the next "(", in which case it will be also bound to a new
local variable (or will replace its value if you have a local variable); it
does not replace a function or variable with identical name in the current
outer scope.
You can also bind a local function to give it as the value of an existing
local or outer variable (if there's none, i.e. this variable name has a nil
value) then a new local varaible will be created, otherwise the lambda
function will overwrite the value of the existing variable.
So "function f(x)... end" is not completely equivalent to "f= function(x)
... end": the first one declares a new local variable named "f", the second
overwrites an existing variable "f" in scope, or creates a new local
variable.
Lua not really know if your function is named or not: it may have several
names (given as different keys of the same table, or different or identical
names in distinct tables). It always runs lambda functions.
When debugging Lua programs, Lua will attempt to locate the name of the
function by performing lookups in the stack of closures, to see if there
environment defines a table of variable names bound to the function defined
for the closure: if it locate a table, it will then scan all keys on this
table to see if one of the keys is mapped to the function.
You may initially create a local function bound to a local name, then
assign it to another variable in scope with another name, then when the
local variable is no longer in scope or reassigned another value, that
function will no longer be bound to its initial name. So a function may
have its "most local" name changed over time. function names are not
significant for their execution, they are interesting only for debuggers.
What only matters are the anonymous lambda functions that every function
has.
Note that all lambda functions are not just a series of instructions: they
also have a closure in which they are defined (that closure may not even
have any external variable in rare extreme cases where access to extertnal
variables was blocked by a function set in the closure's metatable
"__index" set to a function that is always returning nil, and all what your
lambda function will have access to are the upvalues in the call stack,
where the values of function unput parameters are passed and where the
function can return its output results)
Post by Dirk Laurie
Please refresh my memory!
There have been numerous discussions on this list for lambda
notations. Were any of those accompanied by a patch so that one could
try them out?
Francisco Olarte
2018-11-19 12:06:30 UTC
Permalink
So "function f(x)... end" is not completely equivalent to "f= function(x) ... end": the first one declares a new local variable named "f", the second overwrites an existing variable "f" in scope, or creates a new local variable.
Are you sure? The manual (
https://www.lua.org/manual/5.3/manual.html#3.4.11 ) says it's
completely equivalent and a simple test:

Lua 5.3.3 Copyright (C) 1994-2016 Lua.org, PUC-Rio
a=1;function tst() local b; function a() end; function b() end; function c() end; print('a',a,'b',b,'c',c,'Z'); end; print('a',a,'b',b,'c',c,'Z'); tst(); print('a',a,'b',b,'c',c,'Z');
a 1 b nil c nil Z
a function: 0x9da150 b function: 0x9da0c8 c function:
0x9bfdb8 Z
a function: 0x9da150 b nil c function: 0x9bfdb8 Z
Seems to contradict your "or creates a local variable" ( c is alive
after tst(), so it should be global )

Francisco Olarte.
Philippe Verdy
2018-11-19 12:56:13 UTC
Permalink
your example is wrong.
You've tested only the "function name()" case that does not hides any
"name" variable in scope.
I'm sure that:
c=1; do function c() end; end print(c)
--> 1
and:
c=1; do c=function() end; end print(c)
--> function: 0xnnnn
are NOT equivalent.
- the first one (function c() end) declares a new local variable "c" in all
cases,
- the second one (c = function() end) does NOT declare a new local variable
but overwites the value of the existing variable "c" in scope.
Post by Philippe Verdy
So "function f(x)... end" is not completely equivalent to "f=
function(x) ... end": the first one declares a new local variable named
"f", the second overwrites an existing variable "f" in scope, or creates a
new local variable.
Are you sure? The manual (
https://www.lua.org/manual/5.3/manual.html#3.4.11 ) says it's
Lua 5.3.3 Copyright (C) 1994-2016 Lua.org, PUC-Rio
Post by Philippe Verdy
a=1;function tst() local b; function a() end; function b() end; function
c() end; print('a',a,'b',b,'c',c,'Z'); end; print('a',a,'b',b,'c',c,'Z');
tst(); print('a',a,'b',b,'c',c,'Z');
a 1 b nil c nil Z
0x9bfdb8 Z
a function: 0x9da150 b nil c function: 0x9bfdb8 Z
Seems to contradict your "or creates a local variable" ( c is alive
after tst(), so it should be global )
Francisco Olarte.
Philippe Verdy
2018-11-19 13:00:22 UTC
Permalink
In fact what is really equivalent is:
function c() end
and
local c = function() end
Note the additional "local" keyword needed for the equivalence!

And in all cases the first one does not declare a "global" function. All
functions are declared locally (in the closure where it is defined).
There's no "global" functions at all in Lua.
Post by Philippe Verdy
your example is wrong.
You've tested only the "function name()" case that does not hides any
"name" variable in scope.
c=1; do function c() end; end print(c)
--> 1
c=1; do c=function() end; end print(c)
--> function: 0xnnnn
are NOT equivalent.
- the first one (function c() end) declares a new local variable "c" in
all cases,
- the second one (c = function() end) does NOT declare a new local
variable but overwites the value of the existing variable "c" in scope.
Post by Philippe Verdy
So "function f(x)... end" is not completely equivalent to "f=
function(x) ... end": the first one declares a new local variable named
"f", the second overwrites an existing variable "f" in scope, or creates a
new local variable.
Are you sure? The manual (
https://www.lua.org/manual/5.3/manual.html#3.4.11 ) says it's
Lua 5.3.3 Copyright (C) 1994-2016 Lua.org, PUC-Rio
Post by Philippe Verdy
a=1;function tst() local b; function a() end; function b() end;
function c() end; print('a',a,'b',b,'c',c,'Z'); end;
print('a',a,'b',b,'c',c,'Z'); tst(); print('a',a,'b',b,'c',c,'Z');
a 1 b nil c nil Z
0x9bfdb8 Z
a function: 0x9da150 b nil c function: 0x9bfdb8 Z
Seems to contradict your "or creates a local variable" ( c is alive
after tst(), so it should be global )
Francisco Olarte.
Luiz Henrique de Figueiredo
2018-11-19 13:07:46 UTC
Permalink
Post by Philippe Verdy
c=1; do function c() end; end print(c)
--> 1
This code never prints 1, it always prints "function: 0xnnnn".
Philippe Verdy
2018-11-19 13:31:01 UTC
Permalink
Wow. This has changed! I should have read the new 5.3 manual.

And I have an old Lua implementation that does not behave like this (it did
not allow "function a.b:c() end", only "function c() end" and there was no
need of the leading "local", this was still only allowed as a statement
like in Lua 5.3).

So OK there's now a difference in the Lua 5.3 manual, but this requires now
the syntax "local function c() ... end" which really creates now a local
variable in all cases (requires a separate "local" statement, which cannot
be used as part of an expression, except in the body of another declared
function)

Sorry for the confusion. Lua is still a young language and many things have
not always been specified precisely and formally... We should always
specify the Lua version when speaking... And frequently the Lua
implementation as well: each version/implementation is a separate dialect,
a distinct language with its specificities (this creates known portability
problems, and maintenance problems if one "upgrades" its Lua
installation to a new version...). When Lua changes these things, it should
create a major version, and use minor versions only for security fixes or
performance improvements.



Le lun. 19 nov. 2018 à 14:08, Luiz Henrique de Figueiredo <
Post by Luiz Henrique de Figueiredo
Post by Philippe Verdy
c=1; do function c() end; end print(c)
--> 1
This code never prints 1, it always prints "function: 0xnnnn".
Luiz Henrique de Figueiredo
2018-11-19 13:41:30 UTC
Permalink
Post by Philippe Verdy
Wow. This has changed! I should have read the new 5.3 manual.
That code behaves the same since Lua 3.1, which introduced the do ...
end syntax.
Try it using the lua-all package, available at http://www.lua.org/ftp/ .
Post by Philippe Verdy
And I have an old Lua implementation that does not behave like this (it did not allow "function a.b:c() end", only "function c() end" and there was no need of the leading "local", this was still only allowed as a statement like in Lua 5.3).
Which implementation? Which version?

Luiz Henrique de Figueiredo
2018-11-18 19:28:44 UTC
Permalink
Post by Dirk Laurie
There have been numerous discussions on this list for lambda
notations. Were any of those accompanied by a patch so that one could
try them out?
See http://lua-users.org/lists/lua-l/2010-11/msg00808.html .
Equivalent code for ltokenf should be straightforward.
Philippe Verdy
2018-11-18 19:54:02 UTC
Permalink
The message referenced proposes an implementation in C for a lexical
extension which is not safe: it defines a C function using two static
variables (state and level) which should be located instead in the
strcuture pointed by LexState *ls. As is, the proposal would not allow the
Lua parser to be used recursively (example via a Lua "load()" call).


Le dim. 18 nov. 2018 à 20:29, Luiz Henrique de Figueiredo <
Post by Luiz Henrique de Figueiredo
Post by Dirk Laurie
There have been numerous discussions on this list for lambda
notations. Were any of those accompanied by a patch so that one could
try them out?
See http://lua-users.org/lists/lua-l/2010-11/msg00808.html .
Equivalent code for ltokenf should be straightforward.
Philippe Verdy
2018-11-18 20:02:00 UTC
Permalink
As well the given examples are not pure lambda:

\x,y,z(x+(x-2)*g(x,y,z-2*(x+y))-y*z)
or its transformation into
function(x,y,z) return x+(x-2)*g(x,y,z-2*(x+y))-y*z end

is bound in a closure referencing "g", which is not an upvalue (an input
parameter) of that function. May be it can be viewed as an output parameter
but then it sould be still written as:

\x,y,z,g(x+(x-2)*g(x,y,z-2*(x+y))-y*z)
or
function(x,y,z,g) return x+(x-2)*g(x,y,z-2*(x+y))-y*z end

Closures are exactly that: they are passing additional parameters not
passed explicitly by the call stack, to create a complete environment
(context) where a lambda can be evaluated because all input and output
variables are bound (independantly of additional local varaibles that may
be defined inside the function.

Le dim. 18 nov. 2018 à 20:29, Luiz Henrique de Figueiredo <
Post by Luiz Henrique de Figueiredo
Post by Dirk Laurie
There have been numerous discussions on this list for lambda
notations. Were any of those accompanied by a patch so that one could
try them out?
See http://lua-users.org/lists/lua-l/2010-11/msg00808.html .
Equivalent code for ltokenf should be straightforward.
Muh Muhten
2018-11-18 23:45:32 UTC
Permalink
Post by Philippe Verdy
\x,y,z(x+(x-2)*g(x,y,z-2*(x+y))-y*z)
or its transformation into
function(x,y,z) return x+(x-2)*g(x,y,z-2*(x+y))-y*z end
is bound in a closure referencing "g", which is not an upvalue (an input
parameter) of that function.
This is the first I've heard of a notion of a "pure" lambda which
forbids closures.

It would seem to be a rather *unusual* idea, since the name "lambda"
itself refers to lambda calculus, which is not nearly as interesting
without closed-over variables.
Tim Hill
2018-11-19 00:17:42 UTC
Permalink
Post by Muh Muhten
Post by Philippe Verdy
\x,y,z(x+(x-2)*g(x,y,z-2*(x+y))-y*z)
or its transformation into
function(x,y,z) return x+(x-2)*g(x,y,z-2*(x+y))-y*z end
is bound in a closure referencing "g", which is not an upvalue (an input
parameter) of that function.
This is the first I've heard of a notion of a "pure" lambda which
forbids closures.
It would seem to be a rather *unusual* idea, since the name "lambda"
itself refers to lambda calculus, which is not nearly as interesting
without closed-over variables.
+1 .. it seems to me that this isn’t lambda at all … its just a discussion of pure functions. To the best of my knowledge (others jump in here!) the only difference between a Lua (anonymous) function and a lambda is syntax. That is, any “lambda” extension to Lua would just be syntactic sugar.

—Tim
Philippe Verdy
2018-11-19 01:11:40 UTC
Permalink
I would say the reverse: Lua functions are syntaxic sugar of more general
lambda functions.
Note: lambda functions are not restricted to be just mathematical functions
(i.e. projections), they can be any relation. Lua functions are defined to
segregate the input and ouput, but this is not true for relations that can
be injective or not, and multivalued; the equations between relations may
be reversed when resolving them in the reverse order : single-valued
functions do not always have an inverse if they are not injective, i.e.
bijective because functions are necessarily surjective. But all relations
have an inverse relation, and relations are not limited to be multivalued
input and single-valued output, all inputs and outputs are equally
powerful: the same equation applies when you take some parameters (any one,
including those that Lua's syntaxic sugar calls an "environment") as input
and then take all the other ones as output.

Lambda calculus is extremely powerful and can be used to prove
mathematically that an algorithm is correct, or will be computable at least
for some inputs, or will not find any solution, or will have multiple
solutions (i.e. the algorithm will have unpredictable results), or that it
will be computable in a finite time. It also allows performing
optimizations in their implementation (extremely interesting when
compiling...).

Lambda calculus is an higher order language, more powerful than Lua or most
other programming languages (that use imperative instructions described in
time order, with assignments that are erasing and loosing what was before,
something that is not necessary, but just a syntaxic sugar of the
programming language).

Lambda calculus is based on mathematical quantifiers and equations over
sets defined as relations, not just functions (i.e. surjections, or
projections, which are information-lossy: the loss of information is
formalized by a "forall" quantifier). lambda calculus also uses the
"exists" quantifier over a relation, which is equivalent to the reverse of
a "forall" quantifier applied over the transformed relation.

Lambda calculus has string mathematical bases from the bases of
mathematics: logic and topology, which come just before arithmetic (on
integers), and then all the rest of mathematical domains (on other kinds of
numeric systems and "meta-"domains such as analysis, infinitesimal
calculus... and finally computing which is just mathematics applied to set
of functions that are computable in finite time with a Turing machine,
which is defined as any device capable of doing some arithmetic on finite
ranges of integers and using "n"-tuples of these ranges, with "n" also
finite and representing space resources, i.e. memory).
Post by Muh Muhten
Post by Philippe Verdy
\x,y,z(x+(x-2)*g(x,y,z-2*(x+y))-y*z)
or its transformation into
function(x,y,z) return x+(x-2)*g(x,y,z-2*(x+y))-y*z end
is bound in a closure referencing "g", which is not an upvalue (an input
parameter) of that function.
This is the first I've heard of a notion of a "pure" lambda which
forbids closures.
It would seem to be a rather *unusual* idea, since the name "lambda"
itself refers to lambda calculus, which is not nearly as interesting
without closed-over variables.
+1 .. it seems to me that this isn’t lambda at all 
 its just a discussion
of pure functions. To the best of my knowledge (others jump in here!) the
only difference between a Lua (anonymous) function and a lambda is syntax.
That is, any “lambda” extension to Lua would just be syntactic sugar.
—Tim
Philippe Verdy
2018-11-19 00:41:19 UTC
Permalink
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 !
Muh Muhten
2018-11-19 07:50:54 UTC
Permalink
Post by Luiz Henrique de Figueiredo
Post by Dirk Laurie
There have been numerous discussions on this list for lambda
notations. Were any of those accompanied by a patch so that one could
try them out?
See http://lua-users.org/lists/lua-l/2010-11/msg00808.html .
Equivalent code for ltokenf should be straightforward.
I took a look at this filter and saw that it's not happy about
*nested* \()-functions.
Allow me to rectify this oversight.

I haven't tested it extensively, but:
% ./lua -e 'print((\f((\a(a(a)))(\x(f(\v(x(x)(v)))))))(\fac(\x(x == 0
and 1 or x*fac(x-1))))(10))'
3628800

Looks good to me.

/* proxy.c
* lexer proxy for Lua parser -- implements nested lambdas:
* '\x,y(\z(exp))' -> 'function (x, y) return function (z) return exp end end'
*
* Michael Zuo <***@gmail.com>, 19 nov 2018:
* This code is hereby placed in the public domain.
*
* Based on lhf's work: http://lua-users.org/lists/lua-l/2010-11/msg00808.html
* Luiz Henrique de Figueiredo <***@tecgraf.puc-rio.br>
* 24 Nov 2010 17:17:44
* This code is hereby placed in the public domain.
*
* Add <<#include "proxy.c">> just before the definition of luaX_next in llex.c
*/

static int nexttoken (LexState *ls, SemInfo *seminfo) {
static char needs_end[LUAI_MAXCCALLS];
/* an early ')' will have us check needs_end[level-1] before bailing */
static unsigned state = 0, level = 1;
int t;

switch (state) {
case 0:
t = llex(ls, seminfo);
if (t == '\\') {
state = 1;
return TK_FUNCTION;
}
else if (t == ')' && needs_end[--level]) {
needs_end[level] = 0;
return TK_END;
}
else if (t == '(')
level++;
return t;
case 1:
state = 2;
return '(';
case 2:
t = llex(ls, seminfo);
if (t == '(') {
needs_end[level++] = 1;
state = 3;
return ')';
}
return t;
case 3:
state = 0;
return TK_RETURN;
default: lua_assert(0); return 0;
}
}
#define llex nexttoken
Muh Muhten
2018-11-19 09:42:45 UTC
Permalink
Post by Muh Muhten
% ./lua -e 'print((\f((\a(a(a)))(\x(f(\v(x(x)(v)))))))(\fac(\x(x == 0
and 1 or x*fac(x-1))))(10))'
Of course, the number of brackets used here is ... inspiring. One
might prefer a more nostalgic notation. With credit where it is due:
http://lua-users.org/lists/lua-l/2010-11/msg00776.html

% ./lua -e 'print((\f.(\a.a(a))(\x.f(\v.x(x)(v))))(\fac.\x. x == 0 and
1 or x*fac(x-1))(10))'
3628800

/* proxy.c
* lexer proxy for Lua parser -- implements nested lambdas:
* '(\x,y.\z.exp)' -> 'function (x, y) return function (z) return exp end end'
* '\' must immediately follow either '(' or the beginning of another lambda's
* body, and closes at the matching ')'. This may include multiple expressions.
*
* Michael Zuo <***@gmail.com>, 19 nov 2018:
* This code is hereby placed in the public domain.
*
* Based on lhf's work: http://lua-users.org/lists/lua-l/2010-11/msg00808.html
* Luiz Henrique de Figueiredo <***@tecgraf.puc-rio.br>
* 24 Nov 2010 17:17:44
* This code is hereby placed in the public domain.
*
* Add <<#include "proxy.c">> just before the definition of luaX_next in llex.c
*/

static int nexttoken (LexState *ls, SemInfo *seminfo) {
static char needs_end[LUAI_MAXCCALLS];
static unsigned state = 0, level = 1;
int t;

switch (state) {
case 0: case 5:
t = llex(ls, seminfo);
if (t == '\\' && state == 5) {
needs_end[level++] = 1;
state = 1;
return TK_FUNCTION;
}
else if (t == '(') {
level++;
state = 5;
return t;
}
else if (t == ')' && needs_end[--level]) {
state = 4;
return TK_END;
}
state = 0;
return t;
case 1:
state = 2;
return '(';
case 2:
t = llex(ls, seminfo);
if (t == '.') {
state = 3;
return ')';
}
return t;
case 3:
state = 5;
return TK_RETURN;
case 4:
needs_end[level] = 0;
if (needs_end[--level])
return TK_END;
state = 0;
return ')';
default: lua_assert(0); return 0;
}
}
#define llex nexttoken
Sean Conner
2018-11-19 01:30:54 UTC
Permalink
Post by Dirk Laurie
Please refresh my memory!
There have been numerous discussions on this list for lambda
notations. Were any of those accompanied by a patch so that one could
try them out?
http://lua-users.org/lists/lua-l/2009-12/msg00071.html
http://lua-users.org/lists/lua-l/2010-01/msg01277.html
http://lua-users.org/lists/lua-l/2010-03/msg00837.html
http://lua-users.org/lists/lua-l/2010-11/msg00733.html
http://lua-users.org/lists/lua-l/2010-11/msg00823.html (check rest of this thread)
http://lua-users.org/lists/lua-l/2010-12/msg01046.html
http://lua-users.org/lists/lua-l/2013-04/msg00328.html (you wrote this one)
http://lua-users.org/lists/lua-l/2016-06/msg00006.html
http://lua-users.org/lists/lua-l/2017-04/msg00387.html (another one you wrote)

That should be good for now ...

-spc
Philippe Verdy
2018-11-19 01:55:10 UTC
Permalink
So this has been discussed but this is still not ininteresting: may be this
is not needed for the Lua language itself (which has its own syntaxic
representation which is still sufficient), but for formal analysis of the
language, and for implementing it (e.g. in an interpreter, in its VM, or in
a compiler), that Lua language has to be transformed into another more
powerful language (where conformance checks can be made, as well as all
optimizations at compiler time or dynamically at runtime). You can
implement it in various ways. Lua proposes its opcode machine, more or less
stack based (even if there's some data storage described as "registers"),
but you can as well represent a Lua program in a lamda calculus form.

Don't reinvent the wheel: we have a wellknown language for it: Lisp.

And Lisp can also be extremely efficient and fast, if you don't restrict
its internal representation to be **just binary trees** with terminal nodes
and binary nodes containing only two pointers. You can also implement it by
using more types of nodes, for example B-tree pages, which will allow much
better data locality and very fast processing, and which is even much
easier to transform to another native assemble code than any invented
virtual instruction set. With B-tree pages+terminal nodes, you can express
both the program code, and all the data that this code handles, and make
all transforms of the tree mixing these two kinds of nodes, in order to
improve locality, determine constants and precompute them (avoiding also
false branch predictions made in many "optimizers").

And implementing a Lisp-based VM is even much easier than a Lua VM... It
also allows you to use unlimited "opcodes" (implemented as terminal nodes
in Lisp's lists). Lisp lists can also naturally represent any Lua table (if
you've used B-trees this is equally compact and fast, but allows easier
memory management because B-tree pages have fixed sizes and can be
allocated efficiently from a limited set of pools, and you an also easily
compact these pools to reduce the global memory footprint on the system,
just like what you do in relation database stores where B-trees are very
efficient in terms of compacity, speed of accessn data locality,
cachability...).
Post by Sean Conner
Post by Dirk Laurie
Please refresh my memory!
There have been numerous discussions on this list for lambda
notations. Were any of those accompanied by a patch so that one could
try them out?
http://lua-users.org/lists/lua-l/2009-12/msg00071.html
http://lua-users.org/lists/lua-l/2010-01/msg01277.html
http://lua-users.org/lists/lua-l/2010-03/msg00837.html
http://lua-users.org/lists/lua-l/2010-11/msg00733.html
http://lua-users.org/lists/lua-l/2010-11/msg00823.html (check rest of this thread)
http://lua-users.org/lists/lua-l/2010-12/msg01046.html
http://lua-users.org/lists/lua-l/2013-04/msg00328.html (you wrote this one)
http://lua-users.org/lists/lua-l/2016-06/msg00006.html
http://lua-users.org/lists/lua-l/2017-04/msg00387.html (another one you
wrote)
That should be good for now ...
-spc
Dirk Laurie
2018-11-19 04:32:01 UTC
Permalink
Post by Sean Conner
http://lua-users.org/lists/lua-l/2013-04/msg00328.html (you wrote this one)
Ah! That one was a joke, with the "lambda" actually being Lua's own
anonymous function definition, but thanks for reminiding me.
Loading...