[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Growable arrays?

From: David Kastrup
Subject: Re: Growable arrays?
Date: Mon, 11 Jun 2012 11:55:48 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1.50 (gnu/linux)

Andy Wingo <address@hidden> writes:

> You raise an interesting issue.  But first, a nitpick :)
> On Sat 09 Jun 2012 14:32, David Kastrup <address@hidden> writes:
>> Scheme hashtable
> To be very pedantic, there are no hashtables in R5RS Scheme.  SRFI-69
> and R6RS specify them (in different ways), but do not mandate that they
> grow.  Guile's do grow, but that's a detail.
> The underlying message important:  _Scheme_ doesn't give you much in the
> way of data structures.

Lua gives you one data structure, period.  And it is pretty good at
making this one work well.  Sometimes, the "one thing that works well"
approach beats the "give the user choice between several options with
different drawbacks" approach, since there may be use cases exercising
at least one deficiency in every option.

> Guile (as an implementation) also provides a few data structures
> built-in.  It could provide more.
> But, I don't think that "table" is the right strategy for what you
> want.

Tables are a superset of what I need here.  I need the "growable vector"
aspect, not the "hash part" aspect.  Guile 1.8 only offers subsets:
"growable" does not come together with "vector".

Guile hashtables _internally_ use a growable vector, but it is not
accessible as such.

> Lua (and JS) implementations typically have many different
> implementation strategies for their table-like objects.  For example,
> V8 has over two dozen.

Uh what?  Lua has one implementation "strategy".  Array part, and hash
part.  Lua is not JavaScript.  That Lua emulators without access to a
reasonably fitting table building block have to make do with substitutes
is not much of a surprise.

There has been some sort of a language shootout on the LilyPond
developer list.  With regard to the question Guile/Lua, my respective
pro/contra list for suitability for extensions was

a) lexically Scheme is _very_ nice to integrate.  Scheme reader rules
are straightforward.  LilyPond basically starts Scheme expressions with
#, and so things like #3, #(+ 2 1) #(cond ...) provide a seamless
transition from just constants to more complex things, including the
ability to plug into scopes.  The combination of a straightforward lexer
and a basically non-existent parser (you enter the parse trees directly)
makes for predictable and extensible behavior and easy manipulation of
expressions and pattern matching.

b) from the data types, Lua is _very_ nice to integrate because it does
not give you choice.  You don't need to pick between symbols and strings
when mapping your system to the extension language, because there are
only interned strings.  You don't need to pick between lists and
fixed-size arrays because there are just variable size tables.  You
don't need to pick between arrays and structs because everything is a
table.  And so on.  Since you get only a minimal set of data types and
data structures, but those implemented in a manner where they actually
cover most use cases nevertheless, you are saved from a lot of decisions
that may have different drawbacks.

c) for general-purpose programming, Lua is more human-friendly.  That
comes at the cost of being less computer-friendly by having a parser
between input and parse trees.  Macro manipulation in Lua is sort of a
text processing exercise and not reliable.  It is off the charts as a
feasible programming technique.

Goops is powerful and flexible, but has a bit of a problem in that it is
too powerful and flexible.  As a result, there is no really established
programming style for it: it is more a tool for developing your own OOP
technology rather than prescribing one itself.

That would already be a mixed blessing.  It becomes worse since, while
the documentation does not take a lot of choices regarding how to do
things or not and leaves the programmer with a lot of freedom, the
implementation is optimized for certain uses, and if you want to find
out if your plan of mapping your OOP requirement to Goops will actually
work reasonably efficiently, you need to read all the internals of the
Goops implementation and figure out just _which_ use patterns are
supported efficiently, and which patterns aren't.

That's somewhat less than fabulous.  While the results are reasonably
easy to understand and maintain, designing the first implementation
requires a grandwizard if performance is not just an academical

If you take a look at Lua, while things do get complex when you dive
into metatable territory, the performance implications are rather
transparent even without having to analyze the implementation of Lua
manually in fine-grained detail.

This is mostly a diversion from the original question, but it might
still be interesting as a sort of observation.

David Kastrup

reply via email to

[Prev in Thread] Current Thread [Next in Thread]