A very basic thing I don't get

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

Re: A very basic thing I don't get

Tony Finch
Stefan Reich <[hidden email]> wrote:
> On Sat, Oct 1, 2011 at 7:32 PM, Peter Cawley <[hidden email]> wrote:
>
> > The message to take away from this is that things are truncated to
> > exactly 1 result iff they are not the last thing in an expression
> > list.
>
> Why is that done? Strikes me as rather confusing. (The OP obviously
> fell for it too.)

It allows Lua to assemble an argument list or insert elements into a table
using register numbers (on the stack) or table indexes that are known at
compile time, except for function calls at the end of the list.

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/
Viking, North Utsire: Southerly veering southwesterly 6 to gale 8,
occasionally severe gale 9 at first in northwest Viking. Moderate or rough
becoming very rough or high. Rain then squally showers. Moderate or good,
occasionally poor.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Leo Razoumov
In reply to this post by David Kastrup
On Mon, Oct 3, 2011 at 06:40, David Kastrup <[hidden email]> wrote:

> Axel Kittenberger <[hidden email]> writes:
>
>> Just because not every slot is filled doesn't yet mean that O() isn't
>> 1.Eg a btree will never go below ~50% load.
>
> Radix trees fan out according to the size of the data, not just its
> amount.  Unbalanced trees can have less that 50% load.
>
> --
> David Kastrup
>

Also, a balanced trie (prefix tree) with N values stored in leaves has
O(N*log(N)) nodes making it  O(log(N)) per value in size.
For a non-balanced trie it could be even worse.

--Leo--

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Mark Hamburg
In reply to this post by Lorenzo Donati-2
On Oct 2, 2011, at 12:55 AM, Lorenzo Donati wrote:

> Very, true.
>
> This is IMO a big newbie gotcha: Lua tables are so "high-level", i.e. they can be easily used to implement lists, trees, maps, stacks, etc., that one can easily think they should provide a much fatter interface (the common problem of getting into Lua's spirit).
>
> It's not easy to grasp initially that one can use OOP techniques to turn a generic table into, say, a "stack object", with usual push/pop methods.

Which leads to the argument that the "problem" is that Lua tables are too powerful. So often they are powerful enough that they just solve the problem. Much of the rest of the time, they seem powerful enough until you realize that they aren't quite. And then you come and complain to the list about tables being broken and about how Lua has to change. Maybe the change is that tables should be less powerful and people should be forced to roll their own data structures.

Not that I buy that argument.

Still, it does point to perhaps a getting started FAQ that would disabuse people of notions that will get them in trouble -- "You can do a lot with tables, but understand their limits and build data structures as you approach those limits."; "Metamethods are fallbacks not overrides and though they may seem like methods in an OOP language, they don't always behave that way."; etc. Then the real trick is to write this all without it turning into something like JavaScript: The Good Parts which contains a lot of warnings about the "bad" parts where JavaScript is just bizarre.

Mark


Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

joao lobato
On 10/5/11, Mark Hamburg <[hidden email]> wrote:

> On Oct 2, 2011, at 12:55 AM, Lorenzo Donati wrote:
>
>> Very, true.
>>
>> This is IMO a big newbie gotcha: Lua tables are so "high-level", i.e. they
>> can be easily used to implement lists, trees, maps, stacks, etc., that one
>> can easily think they should provide a much fatter interface (the common
>> problem of getting into Lua's spirit).
>>
>> It's not easy to grasp initially that one can use OOP techniques to turn a
>> generic table into, say, a "stack object", with usual push/pop methods.
>
> Which leads to the argument that the "problem" is that Lua tables are too
> powerful. So often they are powerful enough that they just solve the
> problem. Much of the rest of the time, they seem powerful enough until you
> realize that they aren't quite. And then you come and complain to the list
> about tables being broken and about how Lua has to change. Maybe the change
> is that tables should be less powerful and people should be forced to roll
> their own data structures.
>
> Not that I buy that argument.
>
> Still, it does point to perhaps a getting started FAQ that would disabuse
> people of notions that will get them in trouble -- "You can do a lot with
> tables, but understand their limits and build data structures as you
> approach those limits."; "Metamethods are fallbacks not overrides and though
> they may seem like methods in an OOP language, they don't always behave that
> way."; etc. Then the real trick is to write this all without it turning into
> something like JavaScript: The Good Parts which contains a lot of warnings
> about the "bad" parts where JavaScript is just bizarre.
>
> Mark
>
>
>

Indeed. Tables are a corner stone of what Lua is and one of the
reasons why I like Lua.

My only problem with the "roll your own data structures" is how can
one do it without more basic blocks?

Imagine you want to build a tree datastructure where you can store an
arbitrary Lua value per node. How does one accomplish such a goal
without instanciating a bunch of tables in the process?

My question is not if it's possible, it's how can one do it efficiently.

Wouldn't a simple, fixed size, integer indexable (1 based, of course
;-) ), array type be better suited for the role of building block? I'm
talking about a new full-blown type here, with a metatable per
instance, just like a fixed size array part of a table without the
hash part.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Luiz Henrique de Figueiredo
> Imagine you want to build a tree datastructure where you can store an
> arbitrary Lua value per node. How does one accomplish such a goal
> without instanciating a bunch of tables in the process?

What is the problem with a bunch of tables?
 
> Wouldn't a simple, fixed size, integer indexable (1 based, of course
> ;-) ), array type be better suited for the role of building block?

If you want Fortran, you know where to find it... :-)
Plus Lua does very well on these arrays already...

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

joao lobato
On 10/5/11, Luiz Henrique de Figueiredo <[hidden email]> wrote:

>> Imagine you want to build a tree datastructure where you can store an
>> arbitrary Lua value per node. How does one accomplish such a goal
>> without instanciating a bunch of tables in the process?
>
> What is the problem with a bunch of tables?
>
>> Wouldn't a simple, fixed size, integer indexable (1 based, of course
>> ;-) ), array type be better suited for the role of building block?
>
> If you want Fortran, you know where to find it... :-)
> Plus Lua does very well on these arrays already...
>
>

Well, I believe you. Not having performed any benchmarking I wouldn't
argue about the overhead of the rest of the table implementation; it
was just a gut feeling :-)

It's just that sometimes I feel that it gets kind of convoluted to mix
userdata and the other Lua types because you have to jump a few hoops
if you want to, say, store a table in a C struct.

I'm ready to believe that, in those cases, I'm simply not doing it
"the Lua way (tm)" and that's the point of this thread that you summed
up spot on: there's how we do it and how others do it, and it's better
to learn the right way than to complain about it.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Javier Guerra Giraldez
On Wed, Oct 5, 2011 at 4:05 PM, joao lobato <[hidden email]> wrote:

>> What is the problem with a bunch of tables?
>>
>>> Wouldn't a simple, fixed size, integer indexable (1 based, of course
>>> ;-) ), array type be better suited for the role of building block?
>>
>> If you want Fortran, you know where to find it... :-)
>> Plus Lua does very well on these arrays already...
>>
>>
>
> Well, I believe you. Not having performed any benchmarking I wouldn't
> argue about the overhead of the rest of the table implementation; it
> was just a gut feeling :-)

a case in point:

once upon a time,
(http://lua-users.org/lists/lua-l/2008-03/msg00498.html), there was a
thread where a few of us enjoyed optimizing a priority queue;
comparing a heap structure with a sorted table.

at first, a binary heap (easy to implement on an array) performed
really well; but then Gé Weijers surprised everybody with the speed of
a skew heap (that uses a tree-like structure internally).

the surprising part is that Gé's code instantiated lots of small
tables (with named fields!) to create the internal tree, but it still
was far faster than the supposedly-optimized binary heap (which used a
single integer-indexed array).

moral of the story: Lua tables are wicked fast!

--
Javier

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Geoff Leyland
On 6/10/2011, at 10:41 AM, Javier Guerra Giraldez wrote:

> once upon a time,
> (http://lua-users.org/lists/lua-l/2008-03/msg00498.html), there was a
> thread where a few of us enjoyed optimizing a priority queue;
> comparing a heap structure with a sorted table.
>
> at first, a binary heap (easy to implement on an array) performed
> really well; but then Gé Weijers surprised everybody with the speed of
> a skew heap (that uses a tree-like structure internally).
>
> the surprising part is that Gé's code instantiated lots of small
> tables (with named fields!) to create the internal tree, but it still
> was far faster than the supposedly-optimized binary heap (which used a
> single integer-indexed array).
>
> moral of the story: Lua tables are wicked fast!

I certainly agree with the moral of the story, but I'm not sure that the conclusion regarding binary vs skew heaps holds [1].  In any case, I've dug out the code I wrote at the time and put it here [2], so you can draw your own conclusions (either about heaps or about the quality of my implementations)

Cheers,
Geoff

[1]
Lua:
binary heap: 12.96 s
skew heap: 13.36 s
sorted queue: 68.30

LuaJIT:
binary heap: 2.37 s
skew heap: 4.56 s
sorted queue: 30.70 s

[2] https://github.com/geoffleyland/lua-heaps


Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Lorenzo Donati-2
In reply to this post by Mark Hamburg
On 05/10/2011 16.36, Mark Hamburg wrote:

> Which leads to the argument that the "problem" is that Lua
> tables are too powerful. So often they are powerful enough
> that they just solve the problem. Much of the rest of the
> time, they seem powerful enough until you realize that they
> aren't quite. And then you come and complain to the list
> about tables being broken and about how Lua has to change.

I couldn't have expressed the idea in a better way!

> Maybe the change is that tables should be less powerful and
> people should be forced to roll their own data structures.
>
> Not that I buy that argument.
>

Neither do I. I think Lua tables are good this way.

FWIW I'd like some more enhancements on the "virtualization" side, that
is some nice idea to make it a bit easier to do OOP, but I realize that
it is hard to add good orthogonal features in that area without imposing
some OOP paradigm on the user or cluttering Lua.

> Still, it does point to perhaps a getting started FAQ that
> would disabuse people of notions that will get them in
> trouble -- "You can do a lot with tables, but understand
> their limits and build data structures as you approach those
> limits."; "Metamethods are fallbacks not overrides and though
> they may seem like methods in an OOP language, they don't
> always behave that way."; etc.

Well said! Probably the hardest part of learning Lua for me was to
"attune" to Lua's spirit. I must confess that at first sight it seems
*really weird* (especially for people having strong imperative,
statically typed, languages background). It takes some time and some
effort to understand that it is not so weird and there's a strong
rationale beneath all that stuff.

Not that some aspects are not debatable, but as Roberto sometimes
pointed out, some design decisions were well-thought tradeoffs.

Probably many recurring topics on this lists could be avoided if there
were a sort of "Rationale FAQ", explaining *why* (*not* how) something
is the way it is, maybe with a nice introductory essay on the general
philosophy of Lua (I mean, more extended than the introductions in the
refman or PiL - more focused on a Lua newbie's perspective). The cherry
on top would be also comments about the current status of the feature,
i.e. if it is a state-of-the-art feature (unlikely to be changed), or it
is the result of a tradeoff (and what were the factors influencing the
decision), or if it is something that Lua team regretted to have done
("module" function comes to my mind). A section on what new features Lua
team would like to add in the future could improve the quality of the
discussions (adding perspective).

I understand that it is a somewhat a daunting task, but if it were ever
done curious and/or enthusiast people would have an easier path for
learning what is worth arguing about. In other words, if more people
concentrated on aspects that also Lua team would like to improve, there
could be better chances that a good idea would pop up from the
discussion, instead of wasting time arguing about the sanity of holes in
tables.

Caveat: no flamebait inteded here. I too fell victim of the "why not do
this and this" disease, and sometimes I could have avoided to jump into
the discussion if I had had a clearer view of the rationale behind the
features.

Often the rationale has indeed been discussed somewhere, but this kind
of information is usually scattered in the WIKI or, more often, in some
remote thread in the list archive. You may say one has to do his
homework better, but it's much harder IMO to search for "whys" instead
of searching for "how-tos".

> Then the real trick is to
> write this all without it turning into something like
> JavaScript: The Good Parts which contains a lot of warnings
> about the "bad" parts where JavaScript is just bizarre.
>
> Mark
>

Cheers.
-- Lorenzo

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

phlnc8
On Thu, Oct 6, 2011 at 1:23 AM, Lorenzo Donati
<[hidden email]> wrote:
>
> (...)
> Probably many recurring topics on this lists could be avoided
> if there were a sort of "Rationale FAQ", explaining *why* (*not* how)
> something is the way it is, maybe with a nice introductory essay on
> the general philosophy of Lua (I mean, more extended than the
> introductions in the refman or PiL - more focused on a Lua
> newbie's perspective).


I found the following paper provides a great perspective about the
"philosophy of Lua" and main language design options:

"The evolution of Lua", R. Ierusalimschy, L. H. de Figueiredo, W.
Celes (ACM HOPL III, 2007)
http://www.lua.org/doc/hopl.pdf

HTH

Phil

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Petite Abeille

On Oct 6, 2011, at 7:07 PM, phlnc8 wrote:

> "The evolution of Lua", R. Ierusalimschy, L. H. de Figueiredo, W.
> Celes (ACM HOPL III, 2007)
> http://www.lua.org/doc/hopl.pdf

Yes, very nice paper. Favorite quote:

"... we did not (and still do not) believe in the standard multithreading model, which is preemptive concurrency with shared memory: we still think that no one can write correct programs in a language where ‘a=a+1’ is not deterministic..."

Regarding Lua itself, I like Roberto one-liner in "Programming in Lua" [1]:

"Lua gives you the power; you build the mechanisms."

Luiz seems to be fond of Saint-Exupery (even though I would personally prefer another quote [2]):

"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away."

Regarding libraries, Lua is very much "une auberge espagnole" (a casa da mãe Joana?) where you mostly get what you bring in.


[1] http://www.lua.org/pil/12.1.2.html
[2] "Grown-ups never understand anything for themselves, and it is tiresome for children to be always and forever explaining things to them."

123