Orchid XP v7 <voi### [at] devnull> wrote:
> [I particularly like that way that if I make an array of 4 million 
> Boolean values, each one takes up exactly 1 *bit* of RAM. And yet, the 
> interface is identical to any other kind of array...]

  But my point was not really that. In Java you can, for example, create
an array if 32-bit integers, and each integer will take only 32 bits of
memory. That's not the problem.

  The problem in Java is that if you are making an array of *objects*,
each object having only one 32-bit integer as a member variable, there's
just no way of making each object take only 32 bits of memory.

  So you have only two options: Create a "low-level" array of integers,
which is extremely rigid and very hard to maintain (as it basically is
an array of "exposed objects"), or you create an array of abstract objects
at the cost of the memory consumption increasing by a considerable factor.

  I understand that you can create an "array of integers" or "array of
booleans" in Haskell, but that's not really what I was asking.

> Haskell has "modules". The module is the unit of abstraction in Haskell. 
> When you write a module, you can define precisely what parts of it are 
> visible from the outside, and which parts aren't.

  So Haskell is really a two-paradigm language: Functional and modular?

  (To understand what the "modular programming paradigm" means, it's
basically the same thing as the "object-oriented programming paradigm"
minus inheritance and dynamic binding.)

  Anyways, my real question was: Given such a module (eg. "a pixel"),
can you, for example, create an array of them so that each one takes
only as much memory as the sum of the sizes of its member variables?

-- 
                                                          - Warp

Post a reply to this message

Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
> C++ STL vector template class has a specialization for 'bool' that uses 
> 1 bit per element too. That is, a vector<bool> takes 1 bit per element.

  The C++ standard library also offers the 'bitset' data container which
is specifically optimized to handle bits. (Its disadvantage is that its
size must be determined at compile time, and this size cannot change,
unline with std::vector<bool>.)

  Many operations doable to bitsets are extremely fast. (For example
counting the number of 1-bits is astonishingly fast.)

-- 
                                                          - Warp

Post a reply to this message

On Tue, 25 Mar 2008 17:34:14 +0100, Nicolas Alvarez  
<nic### [at] gmailisthebestcom> wrote:
> C++ STL vector template class has a specialization for 'bool' that uses  
> 1 bit per element too. That is, a vector<bool> takes 1 bit per element.

Yes, but that specialisation is largely considered a mistake because it  
breaks the interface associated with the generic std::vector. Also, there  
is no actual requirement that the elements occupy a single bit each; this  
is left up to the implementation.
There is std::bitset, but that does not use dynamic allocation.


-- 
FE

Post a reply to this message

> On Tue, 25 Mar 2008 17:34:14 +0100, Nicolas Alvarez 
> <nic### [at] gmailisthebestcom> wrote:
>> C++ STL vector template class has a specialization for 'bool' that 
>> uses 1 bit per element too. That is, a vector<bool> takes 1 bit per 
>> element.
> 
> Yes, but that specialisation is largely considered a mistake because it 
> breaks the interface associated with the generic std::vector.

What exactly is broken in the interface?

Post a reply to this message

On Tue, 25 Mar 2008 19:47:39 +0100, Nicolas Alvarez  
<nic### [at] gmailisthebestcom> wrote:

>> On Tue, 25 Mar 2008 17:34:14 +0100, Nicolas Alvarez  
>> <nic### [at] gmailisthebestcom> wrote:
>>> C++ STL vector template class has a specialization for 'bool' that  
>>> uses 1 bit per element too. That is, a vector<bool> takes 1 bit per  
>>> element.
>>  Yes, but that specialisation is largely considered a mistake because  
>> it breaks the interface associated with the generic std::vector.
>
> What exactly is broken in the interface?

Well, it does not satisfy the requirements of an STL container, making it  
incompatible for use with some algorithms and other containers.

For a concrete example, consider this code:

// Code begins
template < typename T >
void func()
{
	std::vector< T > v( 10 );
	T& ref = v[0];
}
// Code ends

It works with any instantiation of the generic std::vector - the standard  
guarantees it - but fails with std::vector<bool>.

Also, things like 'std::stack< bool, std::vector<bool> >' do not work  
either.

As someone else once put it: std::vector<bool>, while listed under  
"containers" in the standard, is not a container, nor does it contain  
bools.


If you really need a compact set of booleans, use std::bitset or  
boost::dynamic_bitset instead.


-- 
FE

Post a reply to this message

Warp wrote:

>> Haskell has "modules". The module is the unit of abstraction in Haskell. 
>> When you write a module, you can define precisely what parts of it are 
>> visible from the outside, and which parts aren't.
> 
>   So Haskell is really a two-paradigm language: Functional and modular?
> 
>   (To understand what the "modular programming paradigm" means, it's
> basically the same thing as the "object-oriented programming paradigm"
> minus inheritance and dynamic binding.)

If you consider "modular" to be a programming paradigm then... yes, I 
guess. (Does Pascal count as "module" too?)

Did I mention that Haskell also has "classes"? (Though they don't work 
quite the same as in OOP.)

>   Anyways, my real question was: Given such a module (eg. "a pixel"),
> can you, for example, create an array of them so that each one takes
> only as much memory as the sum of the sizes of its member variables?

You can do this. However, it's sufficiently hard work given the present 
library structure that you would only bother doing this if it was really 
necessary for your particular application.

(In future they're supposed to be adding support for transparently 
storing arbitrary types without pointer indirection. For the moment, 
you'll have to implement it yourself by hand for any type you want an 
array of.)

So it's not a language limitation, it's a library limitation. And I'm 
not sure why nobody is out fixing it, actually...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
>   So Haskell is really a two-paradigm language: Functional and modular?

The functions are defined inside of modules.  Modularity is a good thing
anywhere.

Post a reply to this message

Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
> On Tue, 25 Mar 2008 17:34:14 +0100, Nicolas Alvarez  
> <nic### [at] gmailisthebestcom> wrote:
> > C++ STL vector template class has a specialization for 'bool' that uses  
> > 1 bit per element too. That is, a vector<bool> takes 1 bit per element.

> Yes, but that specialisation is largely considered a mistake

  The alternative would be that there's no specialization, in which
case each element could take even 4 bytes (from which only 1 bit is
actually used).

  I don't see any problem in having an efficient boolean vector.
If it doesn't work with some STL algorithms, then it doesn't. In
the vast majority of cases there isn't any logical use for STL
algorithms for a bool vector anyways (why would you, for example,
try to sort a bool vector? It doesn't make any sense).

  Of course std::bitset should be used whenever possible. However,
it's not always possible. In that case std::vector<bool> is the
next best thing.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> If you consider "modular" to be a programming paradigm then... yes, I 
> guess.

  Yes, modular programming is usually considered a programming paradigm
of its own (a type of precursor of object-oriented programming).

  I think that the quintessential example of a modular programming
language is Modula-2: Its modules are more or less full-fledged classes
(public and private parts, member variables and functions, instanciation,
references to such instances...), except for what would make it an
object-oriented programming language: Inheritance.

  (Modula-3 added inheritance, making it an OOP language.)

> (Does Pascal count as "module" too?)

  Pascal is a programming language, not a module. :P

> Did I mention that Haskell also has "classes"? (Though they don't work 
> quite the same as in OOP.)

  If you can inherit and have dynamic binding (or a messaging system,
ie. delegation) then it would more or less make it an OOP language,
else it's just a modular programming language.

-- 
                                                          - Warp

Post a reply to this message

>> If you consider "modular" to be a programming paradigm then... yes, I 
>> guess.
> 
>   Yes, modular programming is usually considered a programming paradigm
> of its own (a type of precursor of object-oriented programming).

I thought that was structured programming?

>   I think that the quintessential example of a modular programming
> language is Modula-2: Its modules are more or less full-fledged classes
> (public and private parts, member variables and functions, instanciation,
> references to such instances...), except for what would make it an
> object-oriented programming language: Inheritance.

I've heard legend of Modula-2. Never actually seen it though.

(Actually, I've heard legend of another functional language where 
apparently modules *do* have inheritance... There are often debates 
about whether Haskell should do this - with most people agreeing the 
vast increase in complexity isn't worth it.)

>> (Does Pascal count as "module" too?)
> 
>   Pascal is a programming language, not a module. :P

Gah! The difference a few characters makes... :-S

[Obviously I meant "does Pascal count as modular?"]

>> Did I mention that Haskell also has "classes"? (Though they don't work 
>> quite the same as in OOP.)
> 
>   If you can inherit and have dynamic binding (or a messaging system,
> ie. delegation) then it would more or less make it an OOP language,
> else it's just a modular programming language.

Dynamic binding? Sure. That's the entire purpose.

Inheritance? Mmm, not really, no.



[In Java, a class *is* a type. In Haskell, a class is something a type 
may or may not be a member of. For example, the "Show" class provides a 
"show" method. Any type that is a member of the Show class can be 
converted into a string by calling the show function. It is possible to 
make it so that no type can be a member of class X without first being a 
member of class Y - but that's not exactly inheritance.]

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message