Re: Some questions on Lua's design

[Sean Conner <sean@...>]

It was thus said that the Great Marco Salamone once stated:
> Oh- I am really only talking about the theory behind the design of Lua in
> the context of general language design. Many of my thoughts on the matter
> are definitely very ignorant- so I apologize for making ignorant
> assertions, though they are really just another way of asking a question.
> 
> 
> >As noted above, the GC *IS* the part of Lua that automatically manages
> memory. You seem to be saying, "we don't need a GC because Lua should
> detect when memory can be freed and release it automatically". But that's
> what the GC *is* .. the bit of the Lua that detects when memory can be
> freed and does it.
> 
> Thanks Tim, that clears up a lot of things about how it works. I wasn't
> quite sure how GC's operate, but that makes perfect sense. Most of these
> questions are general questions masked in the context of Lua's
> implementation.
> 
> So does Lua work by delaying allocation until an expression needs it to be
> resolved, or does it allocate during assignment?
> 
> >Essentially the philosophy of Lua is "don't worry about the internal
> details", because that's the job of the language and the VM. Of course,
> this makes Lua do rather more work behind the scenes that (say) C, which is
> one reason why Lua will never be as fast as C
> 
> I very much like the theory behind Lua and how Lua is getting me to think
> about language design. I think something Lua-like could make a lot of sense
> as a systems programming language, hence the questions about memory
> management. I know that Lua does this in a VM, but I'm thinking about how
> the design of Lua could be re-contextualized outside of a VM.
> 
> >No, Lua DOES use tables as the only AGGREGATE type, but things like
> strings and numbers are not tables.
> 
> Why is that? The grammar and expressiveness of tables more or less allows
> you to define all the properties of a type within the table itself. I
> understand that we need to have static representations of value, but it
> seems like the concept of storing that data into a variable is analogous
> across all types, including tables. (And don't the static values just go
> into the vTable?)
> 
> aTable = 4
> bTable = Function() return 4 end
> cTable = {__call = Function() return 4 end, __index = Function() return 4
> end }
> 
> Conceptually, these things are all the same- they only differ in the syntax
> to access the data. But if I want to add a special property to a specific
> integer, I have to encapsulate it in another table. Ie,
> aTable = 4
> aTable.isEven = true
> Wouldn't work unless it was a table, which it isn't, so it doesn't (?).
> aTable = {__call = function() return 4 end, isEven = true}
> I'd have to do something like this, but then it isn't going to work with
> integer operators. I could define an Integer archetype (or prototype? What
> are they called >_<) that has a metatable analogous to integer
> functionality- and that would let me do the trick above, but I'm confused
> why that isn't already the case.

> 

> I get how all of that works- but I'm confused why there exists types other
> than Tables at all. It would make sense to me if type declarations were
> just sugar for table archetypes... Forgive me, I'm not talking about how
> the language is used, but how it is designed and works under the hood.

  I'm going to step aside here and use a simplified LISP as an example.  In
this LISP, there are only two types, NIL and () (a list with no elements). 
Memory consists of CONS CELLS, which is conceptually two memory cells, both
pointers.  NIL is:

	+------+------+
	| NULL | NULL |
	+------+------+

while () is

	+---+------+
	| * | NULL |
	+-|-+------+
	  |	+------+------+
	  +---> | NULL | NULL |
		+------+------+

A list can contain NIL and other lists, so you can have:

	( ( () ) )
	( () () () )
	( NIL () NIL )

The first list would look like:

	+---+------+
	| * | NULL |
	+-|-+------+
	  |
	  |    +---+------+
	  +--> | * | NULL |
               +-|-+------+
	 	 |
		 |     +---+------+
		 +---> | * | NULL |
		       +-|-+------+
			 |
			 |     +------+------+
			 +---> | NULL | NULL |
			       +------+------+

The second one:
	+---+------+
	| * | NULL |
        +-|-+------+
	  |
	  V
	+---+---+	+---+---+       +---+------+
	| * | *-------> | * | *------->	| * | NULL |
	+-|-+---+       +-|-+---+       +-|-+------+
	  |               |               |
	  V               V               V
	+------+------+ +------+------+ +------+------+
	| NULL | NULL | | NULL | NULL | | NULL | NULL |
	+------+------+ +------+------+ +------+------+

  You can use just this to represent everything else in LISP, including
numbers.  For instance, 0 is (), 1 is ( () ), two is ( () () ), etc.  You
can then define operations such as addition, subtraction, multiplication,
what have you.

  But you run into a problem.  A number like 65535, which can be held in 16
bits, using *this* representation, requires 65536 CONS CELLS, which on a
32-bit system, would require half a gig of memory (64 bit system is a full
gig, just to represent a number that could fit in 16 bits).

And yet people have done just this.  They've done this in the same way
people have implemented RFC-1149 [1], not because it's practical, but
because they can.






Lua
> needs to have strict expectations for what data is in a Number type to
> allow it to communicate with C (or whatever it is embedded in) in a
> predictable manner- but why does that mean that Numbers aren't just a
> special-case of a table? In this manner, it seems like every keyword,
> function, and static value can be expressed as a Table-- or rather, that it
> IS a table within the context of however an expression is defined to work.
> Ie,
> if a < 4 then foo(a) else bar(a) end
> Is similar in concept to calling an archetype of type 'if' dynamically and
> assigning it values relative to how the grammar specifies- ie,
> { true = foo; false = bar; }[a<4](a)
> Though the grammar defined for 'if' implicitly accomplishes this in the
> original conditional. I don't really know if it works like that though.
> Scope, in a way, is an expression that can be expressed as a table and vice
> versa? Or does it not work like this at all?
> 
> I think I'm beginning to understand. I had the impression that Tables are
> Expressions and Expressions are Tables in a way that's similar to
> particle-wave duality, and that really excited me, but it looks like it
> isn't quite that abstract. It seemed like you could define your own
> grammars and keywords within the idea of meta-tables to achieve an almost
> unparalleled degree of expressiveness (supplemented with ::= ofc)- and in
> many ways that is true as it is, but I don't think it works quite in the
> way that my head interprets it. With that in mind, is what I'm talking
> about make any conceptual sense? Could that work as a programming paradigm?
> 
> Thank you so much! Your replies are awesome!
> 
> On Sun, Mar 31, 2013 at 4:08 PM, Tim Hill <drtimhill@gmail.com> wrote:
> 
> >
> > > I've read that a Lua program IS a table. This would suggest that it
> > would be trivially simple to save the state of a lua program or subroutine
> > by writing out said table- which has a lot of intrinsically awesome
> > properties if my assumption is correct. How does this work, conceptually,
> > in relation to the program as a running procedure? Are we just iterating
> > through a table of expressions or is there a special way in which we are
> > stepping through the program? It seems like we're stepping through a table
> > of expressions and throwing things onto a stack until we have an evaluation
> > which may or may not bubble up in scope to modify values of some other
> > tables. Is it as LISP-like as it seems?
> >
> > No, Lua programs are not tables. However, functions (the unit of code in
> > Lua) ARE first-class values, which means you can treat a function in the
> > same way you would treat (say) a number or string.
> >
> > > It seems like all data is or could be perfectly well-managed. Why is
> > there a need for a GC? When we leave scope all local variables get freed
> > and whenever a table is nil'ed we're implicitly freeing that memory. I
> > don't understand GC's very well-- in C, we malloc and free memory whenever
> > we need to.
> >
> > Lua needs a GC to automate memory management. Memory is allocated when
> > necessary, however it turns out to be rather more complex to know when
> > memory can be freed (automatically). Humans get it wrong all the time;
> > hence the ubiquity of pointer problems in C and C++. The GC gets it right,
> > but its not as trivial as you make it seem, mostly because of circular
> > cross-references. Local variables (or, to me more precise, the value they
> > reference), are NOT necessarily freed when they exit scope, as a result of
> > upvalues. Similarly, A table can be referred to via many different
> > variables (global and local, as well as upvalues).  Determining when a
> > value is truly unused (in GC terms, "unreachable"), is non-trivial and is
> > the task of the GC.
> >
> > > This leads me to another point of conjecture in regards to memory
> > management. This is more of a general question about language design. How
> > are static values stored in memory? Suppose I have an expression,
> > > X = 10
> > > In C, we have a zillion different integer types to wrap memory
> > allocation expectations into the definition. That all makes sense, but in
> > the above expression, we don't need more than 4-bits. In C, we can malloc 4
> > bits of space, assign it to a variable, and just treat it like an integer-
> > afaik, the type declarations in plain old C are not much more than
> > syntactic sugar. However, suppose we have-
> > > X, Y = 10, 10
> > > Y = X + Y
> > > X and Y, in my mind, should both initially point to the static value
> > 4-bit value of 10. Then they're put on an evaluation stack, the result is
> > cached, and then Y points to a new static 5-bit value of 20. Now let's do,
> > > X = 4
> >
> > Lua is a high-level language and hence abstracts (mostly) things like
> > numeric representation (this is also true, though less so, of C).
> > Essentially the philosophy of Lua is "don't worry about the internal
> > details", because that's the job of the language and the VM. Of course,
> > this makes Lua do rather more work behind the scenes that (say) C, which is
> > one reason why Lua will never be as fast as C. However, *no* language will
> > do the kind of thing you are proposing, since the language must map to the
> > underlying CPU architecture, and in general these are designed to work
> > optimally on numeric values of certain sizes (for example, 32 or 64 bit
> > integers).
> >
> > > It seems like all data in Lua are tables. That there aren't actually any
> > simple data types- but rather syntactic sugar to make them feel simple. IE
> > a number "Type" is cloned or generated from an expression that outlines the
> > metatable necessary for a number to function in the way we expect. Is this
> > how Lua does it? If it is, very cool- I can see how that would streamline
> > the engineering side of the language. Do all of Lua's primitives function
> > in this manner? Or am I just completely off on this assertion? With the
> > above memory concerns, it seems like Lua could easily manage memory without
> > a GC, implicitly calling malloc/free in appropriate places- or is this what
> > it is essentially doing?
> >
> > No, Lua DOES use tables as the only AGGREGATE type, but things like
> > strings and numbers are not tables. Metatables are just a way to attach
> > user-defined behaviors to certain Lua operations on values on certain
> > types. As noted above, the GC *IS* the part of Lua that automatically
> > manages memory. You seem to be saying, "we don't need a GC because Lua
> > should detect when memory can be freed and release it automatically". But
> > that's what the GC *is* .. the bit of the Lua that detects when memory can
> > be freed and does it.
> >
> >
> > --Tim
> >
> >
> >







[1]	http://www.ietf.org/rfc/rfc1149.txt