Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

For example, in JavaScript, I can do such things:

var arr = [1, "two", /three/, [4]];

There is no way to do such a thing in C! Except by using a void*, which is not an efficient/safe way.

Is this how implementations do it? Using void* everywhere?

share|improve this question
5  
You don't mean "weakly typed". You mean dynamically typed. –  delnan Oct 23 '13 at 9:59
    
@delnan edited the question :) –  Florian Margaine Oct 23 '13 at 10:02
    
Specifically in JavaScript everything is an object, and object means associative array (of objects). Even arrays are implemented like this; an array with four items is simply an associative array with keys "0", "1", "2", "3" and "length". It would not be the most efficient way to do it in C, but it can be done. –  Viliam Búr Oct 23 '13 at 10:28
1  
@ViliamBúr That's not true at all. That doesn't even make sense, the Javascript language doesn't dictate how implementation should actually represent arrays as long as everything looks the same to the user. –  Esailija Oct 23 '13 at 10:33
    
@Esailija Yes, I described what "everything looks the same to the user" means specifically about arrays. It is not necessary to do a straightforward implementation, but author saying "There is no way to do such a thing in C! Except by using a void*" is incorrect. Doing a naive straightforward implementation would be possible in C, would be sufficiently safe and efficient; just not the most efficient. –  Viliam Búr Oct 23 '13 at 10:41

5 Answers 5

up vote 7 down vote accepted

Everything is like a void*, and yes it's more inefficient than values that are stored directly in the array.

But for example in V8 an array can have three type modes: int, double, anything and only in anything-mode everything is stored in the generic format. In int or double modes, the array directly stores those values.

In V8 your array is in generic mode and is represented like:

(SMi means a pointer that actually embeds a direct integer rather than pointing at valid memory)

[MapPointer, Properties[]Pointer, Elements[]Pointer, LengthSMi]

Then at the Elements[] (the actual storage array) array you have:

[MapPointer, LengthSMi, SMiForOne, PointerAtString, PointerAtRegexpObject, PointerAtArrayObject, PointerAtHole, PointerAtHole...]

The holes special objects that mark a reserved slot.

And you don't have to use any struct at all for them (V8 doesn't) - you can and should manage everything yourself with raw memory.

share|improve this answer
    
Ok, so the method is to basically use void* everywhere, and making sure yourself that you're not screwing up the memory/types anywhere. Did I get that correctly? –  Florian Margaine Oct 23 '13 at 10:21
    
@FlorianMargaine well not literally a void * but the same idea yes –  Esailija Oct 23 '13 at 10:23
    
Then what, literally? Any code example? –  Florian Margaine Oct 23 '13 at 10:24
    
@FlorianMargaine well in V8 you would have "Object*". Then you would read the 2 smallest bit to see if it's even a pointer at an object, an error or a direct SMi (small integer) embedded. If it's a pointer at an object, then you can dereference it and see what kind of object it is because MapPointer is always the first field of any heap object and describes what type it is. –  Esailija Oct 23 '13 at 10:26

Basically, yes. Each element of the array has to take the same amount of space, so some representation that can represent any value must be used for all elements. A simple option is making everything heap allocated and always (variables, array elements, object attributes, etc.) use pointers to boxed objects. Another option is to store values of a few types directly and others as pointers. There are a variety of clever schemes for this, but of course they're all limited in that they only support a few types without indirection.

Finally, some implementations automatically recognize when the values stored in an array are homogenous, despite the lanugage not guaranteeing that, and use an optimized representation for those cases. PyPy calls this list strategies.

share|improve this answer
    
Some languages also can unbox things, for example in Haskell GHC can flatten a tuple so that both elements are stored contiguously and unboxed vs storing two pointers to two boxed elements. –  jozefg Oct 23 '13 at 16:02
    
@jozefg Haskell is not dynamically typed. To unbox a tuple, GHC has to know the representation of the elements. –  delnan Oct 23 '13 at 16:03
    
You can fake dynamic typing with an algebraic datatype which GHC can still unbox. You still store it on the heap and use a tag at the front or in the with the pointer to store the needed information to read it. This only works for cases of nested boxing. –  jozefg Oct 23 '13 at 16:05
    
@jozefg Algebraic data types are no more dynamic typing than the Object type in C# (actually slightly less as the latter is open to extension). You can represent values of several different types, but that's not what dynamic typing means - there's still a statically inferred type for every single location in the program. Edit: Or are you're talking about Data.Dynamic? –  delnan Oct 23 '13 at 16:09
    
In C#, Java, or any other language, Object is just as dynamic as anything in Ruby, since everything subtypes it (modulo primitives) unboxing object is isomorphic to unboxing an arbitrary dynamic value. More so than an algebraic type since inheritance hierarchies are open. –  jozefg Oct 23 '13 at 16:59

There is no way to do such a thing in C! Except by using a void*, which is not an efficient/safe way.

Why do you believe that using a (void*) is not an efficient/safe way?

If you want to hide implementation details in C, it is a common technique to expose it as typedef to (void*) in a header and provide functions to manipulate it.

Here is an exaple header for a dynamic type holding integers and strings:

/* Dynamic types in C */

#define DYNAMIC_INT 0
#define DYNAMIC_STRING  1

struct dynamic_phantom;

typedef struct dynamic_phantom* dynamic;

dynamic dynamic_of_int(int c);
dynamic dynamic_of_string(char *s);
int dynamic_classify(dynamic v);
int dynamic_get_int(dynamic v, int *c);
int dynanic_get_string(dynamic v, char **s);
void dynamic_free(dynamic v);

I hope that the names of the functions and their protoypes are enough to get what they are for. There is a lot of options to implement this. Let me outline two popular choices:

UNIONS

In your implementation file, you implement the dynamic as a unionlike this:

union dynamic_value {
  int value_int;
  char* value_string;
};

struct dynamic_cell {
  int cell_type;
  union dynamic_value cell_value;
};

typedef struct dynamic_cell *dynamic;

and implement the functions I enumerated above is straightforward. (Of course, you can refine this in several ways, defining error control procedures, add control bits if you wish to avoid duplicating string contents, and so on.)

SPECIALISED MEMORY POOLS

For each available dynamic type, you allocate a memory pool, i.e. a large array of such values. A dynamic value is then implemented as a pointer to some value in these memory pools casted to void*. The type of the value is then recovered from the pointer range.

An advantage of this strategy over the previous one is that it natively deals with values of different sizes while the union approach takes the biggest size of the possible value types. It is however slightly more complicated to implement, especially because of memory management—it needs to reimplement efficiently the logic of malloc if you want to deal with a significant number of values.

share|improve this answer
    
Thanks for the explanation! To me, void* is not really type-safe, is what I was saying :) –  Florian Margaine Oct 23 '13 at 14:36
    
I introduced a dynamic_phantom in the example, to introduce some type-safeness. –  Michael Grünewald Oct 23 '13 at 14:57
    
I think your explanation is the best one, checking! –  Florian Margaine Oct 23 '13 at 17:45
    
Well, it is not efficient because it's an additional level of indirection. –  Esailija Oct 23 '13 at 21:35
    
@Esailija It does not need to have an additional of indirection. For instance, the union-based implementation can offer a macro that takes an argument x and expands to ((x)->cell_value.value_int) that can be used if one is sure that x actually contains an integer. This is just as complicated as an integer array. –  Michael Grünewald Oct 23 '13 at 21:46

void* is not enough if you want dynamic typing. You need a type information for each value as well. Something like:

struct {
  void * data;
  int type_id;
};
share|improve this answer

It is overly naive to think that typing an array to void** will make your code less efficient, then say, int*. This is because the compiler today are often smart enough to manipulate the data behind the scenes in ways a programmer may not anticipate. Of course, some compilers are smarter then others, but it's getting incrementally better, and we are nowhere near the climax of art of compiler writing. We are probably somewhere in the very beginning of the road.

There also may be many other factors in play, such as how exactly the runtime allocates its objects (does it fragment them or not, how does it align them etc.). In what part of the memory do these objects land (memory may have all sorts of structures, hierarchies, different devices may have their own memory etc.) and most important of all: how your code handles them.

Now, from the perspective of type theory, "dynamically typed" is a misconception. There are untyped languages (even better named "languages where all data are of the same type") and there are languages where types are checked at various stages of the program creation cycle. The types can be often checked during compilation (if this is at all a step in the program livecycle), upon loading the program, "dynamically" (that is applying some heuristic after loading the program, based no the program's usage).

However, "dynamic language" is a terminology often found in special literature, different researchers assign different meanings to it, relating to different aspects of the program. By some standards, Java may be called a dynamic language (because it needs to take certain amount of decisions required for method dispatch at run time, for example). But some would not call Common Lisp a dynamic language because it verifies types during the compilation.

So, if anything, I'd avoid using "dynamic language" in an academic setting until further notice :)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.