Symmetry between language and C API (Was: (not) handling new programming idioms with grace

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Dirk Laurie-2
2018-07-20 20:57 GMT+02:00 William Ahern <[hidden email]>:

> I wish people (myself included) would keep in mind the symmetry that Lua
> tries to maintain between the language and the C API. Aside from making the
> C API incomparably superior to other language implementations, the
> constraint keeps Lua honest and careful. If a feature can be elegantly
> expressed and implemented for *both* the language and the C API, that's
> strong evidence it's a quality choice. If it can't be, it suggests to keep
> searching.

One place where the symmetry currently is broken is concatenation.

The C API function lua_concat respects metamethods, the table.concat
function does not.

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Luiz Henrique de Figueiredo
> One place where the symmetry currently is broken is concatenation.
>
> The C API function lua_concat respects metamethods, the table.concat
> function does not.

The fair comparison is lua_concat vs the concatenation operator: both
respect metamethods.

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Dirk Laurie-2
2018-07-23 11:55 GMT+02:00 Luiz Henrique de Figueiredo <[hidden email]>:
>> One place where the symmetry currently is broken is concatenation.
>>
>> The C API function lua_concat respects metamethods, the table.concat
>> function does not.
>
> The fair comparison is lua_concat vs the concatenation operator: both
> respect metamethods.

The problem with the concatenation operator is that it concatenates
just two values. If I concatenate everything in a table, respecting
metamethods, by the algorithm [1]

   local s = ''
   for k,v in ipairs(tbl) do s = s..v end

it takes O(n²) time, where n=#tbl, not to mention the memory problems.

To write an efficient pure Lua routine is possible, but quite challenging.

[1] The present implementation of 'lub.join' in the LuaRock 'lub' does
just that. I became aware of the problem when using the LuaRock
'xml' which depends on 'lub.join'.  For that application, the workaround
lub.join = table.concat is possible, but there may be lub applications
that rely on metamethods being used.

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Axel Kittenberger
> To write an efficient pure Lua routine is possible, but quite challenging.

an O( n * log( n ) ) one:
"""
function _concat( t, p, n )
    if n > 1 then
        local n2 = n // 2
        return _concat( t, p, n2 ) .. _concat( t, p + n2, n - n2 )
    end
    return t[ p ]
end

function concat( tbl )
    return _concat( tbl, 1, #tbl )
end
"""
For lua < 5.3 use math.floor( n / 2) or math.ceil, or round or whatever, it doesn't matter.
Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Scott Morgan
On 23/07/18 14:26, Axel Kittenberger wrote:

>> To write an efficient pure Lua routine is possible, but quite challenging.
>
> an O( n * log( n ) ) one:
> """
> function _concat( t, p, n )
>     if n > 1 then
>         local n2 = n // 2
>         return _concat( t, p, n2 ) .. _concat( t, p + n2, n - n2 )
>     end
>     return t[ p ]
> end
>
> function concat( tbl )
>     return _concat( tbl, 1, #tbl )
> end
> """
> For lua < 5.3 use math.floor( n / 2) or math.ceil, or round or whatever, it
> doesn't matter.

How about:

function concat(list, sep, i, j)
  i = i or 1
  j = j or #list

  local tmp = {}
  for i=1,#list do
    tmp[i] = tostring(list[i])
  end
  return table.concat(tmp, sep, i, j)
end

Which would just be O(n)?

Might be able to improve with table.pack/unpack, maybe.

Scott

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Scott Morgan
On 23/07/18 15:07, Scott Morgan wrote:

> How about:
>
> function concat(list, sep, i, j)
>   i = i or 1
>   j = j or #list
>
>   local tmp = {}
>   for i=1,#list do
>     tmp[i] = tostring(list[i])
>   end
>   return table.concat(tmp, sep, i, j)
> end
>
> Which would just be O(n)?
>
> Might be able to improve with table.pack/unpack, maybe.

And I notice the mistake in the loop, doh!

Should be `for k=i,j do` etc. etc.

Scott

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Javier Guerra Giraldez
On 23 July 2018 at 15:10, Scott Morgan <[hidden email]> wrote:

> On 23/07/18 15:07, Scott Morgan wrote:
>> function concat(list, sep, i, j)
>>   i = i or 1
>>   j = j or #list
>>
>>   local tmp = {}
>>   for i=1,#list do
>
> And I notice the mistake in the loop, doh!
>
> Should be `for k=i,j do` etc. etc.

it should actually work as is, just the second use of `i` shadowing
the first one on the loop's scope, without affecting the final use.

of course, lint-like tools would bark at you for this

--
Javier

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Scott Morgan
On 23/07/18 15:21, Javier Guerra Giraldez wrote:
> it should actually work as is, just the second use of `i` shadowing
> the first one on the loop's scope, without affecting the final use.
>
> of course, lint-like tools would bark at you for this


Yeah, the scoping would have been fine, just the `i,j` instead of the
inefficient `1,#list` bit was the problem.

Scott

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Axel Kittenberger
In reply to this post by Scott Morgan
> How about:

function concat(list, sep, i, j)
...

which is basically Dirks suggestion. But it doesn't call the __concat metamethod at all. Theoretically __concat could return something else than a string.

PS: I just realised, my version just uses as many __concat operations or intermediatary objects than Dirks simple version. It's just that more intermediate result would consist of shorter whatevers(strings).

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Luiz Henrique de Figueiredo
In reply to this post by Dirk Laurie-2
> The problem with the concatenation operator is that it concatenates
> just two values.

Yes, but it is associative and "a..b..c..d" generates a *one*
instruction, not *three*.

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Dirk Laurie-2
2018-07-23 16:47 GMT+02:00 Luiz Henrique de Figueiredo <[hidden email]>:
>> The problem with the concatenation operator is that it concatenates
>> just two values.
>
> Yes, but it is associative and "a..b..c..d" generates a *one*
> instruction, not *three*.

It's perfect in an actual expression like that.

But a function join(...) that just concatenates all its arguments,
respecting metamethods, is so easy to provide in the API and
so hard to do in pure Lua.

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Dirk Laurie-2
In reply to this post by Scott Morgan
2018-07-23 16:07 GMT+02:00 Scott Morgan <[hidden email]>:

> On 23/07/18 14:26, Axel Kittenberger wrote:
>>> To write an efficient pure Lua routine is possible, but quite challenging.
>>
>> an O( n * log( n ) ) one:
>> """
>> function _concat( t, p, n )
>>     if n > 1 then
>>         local n2 = n // 2
>>         return _concat( t, p, n2 ) .. _concat( t, p + n2, n - n2 )
>>     end
>>     return t[ p ]
>> end
>>
>> function concat( tbl )
>>     return _concat( tbl, 1, #tbl )
>> end
>> """
>> For lua < 5.3 use math.floor( n / 2) or math.ceil, or round or whatever, it
>> doesn't matter.
>
> How about:
>
> function concat(list, sep, i, j)
>   i = i or 1
>   j = j or #list
>
>   local tmp = {}
>   for i=1,#list do
>     tmp[i] = tostring(list[i])
>   end
>   return table.concat(tmp, sep, i, j)
> end

You are not entitled to assume that obj1..obj2 is defined as
tostring(obj1)..tostring(obj2). You are not even entitled to
assume that the result of concatenation is string-valued.

For example, concat may mean list concatenation.

obj{1,2,3}..obj{4,5} --> obj{1,2,3,4,5}

Reply | Threaded
Open this post in threaded view
|

Re: Symmetry between language and C API (Was: (not) handling new programming idioms with grace

Sam Putman


On Mon, Jul 23, 2018 at 5:43 PM, Dirk Laurie <[hidden email]> wrote:
2018-07-23 16:07 GMT+02:00 Scott Morgan <[hidden email]>:

You are not entitled to assume that obj1..obj2 is defined as
tostring(obj1)..tostring(obj2). You are not even entitled to
assume that the result of concatenation is string-valued.

For example, concat may mean list concatenation.

obj{1,2,3}..obj{4,5} --> obj{1,2,3,4,5}


I have profitably used this property to delay string concatenation in a string-builder pattern.

Quite nice, actually, since I had started with simple strings and was able to drop this in.