Quali sono i tipi di matrici di lingue digitate dinamicamente?

3

Ad esempio, in JavaScript, posso fare cose del genere:

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

Non c'è modo di fare una cosa del genere in C! Tranne utilizzando un void* , che non è un modo efficiente / sicuro.

È così che le implementazioni fanno? Usando void* ovunque?

    
posta Florian Margaine 23.10.2013 - 11:53
fonte

5 risposte

7

Tutto è come un vuoto *, e sì è più inefficiente dei valori che sono memorizzati direttamente nell'array.

Ma per esempio in V8 un array può avere tre modalità di tipo: int, double, qualsiasi cosa e solo in qualsiasi cosa-mode tutto è memorizzato nel formato generico. Nelle modalità int o double, la matrice memorizza direttamente quei valori.

In V8 l'array è in modalità generica ed è rappresentato come:

(SMi significa un puntatore che incorpora in realtà un intero diretto anziché indicare una memoria valida)

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

Quindi nell'array Elements[] (l'array di archiviazione effettivo) hai:

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

Gli oggetti speciali dei buchi che segnano uno slot riservato.

E non devi usare alcuna struttura per loro (V8 no) - puoi e dovresti gestire tutto da solo con la memoria grezza.

    
risposta data 23.10.2013 - 12:09
fonte
6

In sostanza, sì. Ogni elemento dell'array deve occupare la stessa quantità di spazio, quindi è necessario utilizzare una rappresentazione che possa rappresentare un valore qualsiasi per tutti . Un'opzione semplice è rendere tutto il heap allocato e sempre (variabili, elementi di array, attributi dell'oggetto, ecc.) Utilizzare i puntatori agli oggetti box. Un'altra opzione è quella di memorizzare i valori di alcuni tipi direttamente e altri come puntatori. Esistono una serie di schemi intelligenti per questo, ma ovviamente sono tutti limitati dal fatto che supportano solo alcuni tipi senza riferimenti indiretti.

Infine, alcune implementazioni riconoscono automaticamente quando i valori memorizzati in un array sono omogenei, nonostante la lanugage non lo garantisce, e usano una rappresentazione ottimizzata per quei casi. PyPy chiama questa lista di strategie .

    
risposta data 23.10.2013 - 12:08
fonte
5

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

Perché credi che l'uso di un (void *) non sia un modo efficiente / sicuro?

Se vuoi nascondere i dettagli di implementazione in C, è una tecnica comune esporlo come typedef a (void*) in un'intestazione e fornire funzioni per manipolarlo.

Ecco un'intestazione di exaple per un tipo dinamico contenente interi e stringhe:

/* 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);

Spero che i nomi delle funzioni e dei loro prototipi siano sufficienti per ottenere ciò per cui sono. Ci sono molte opzioni per implementarlo. Lasciatemi delineare due scelte popolari:

SINDACATI

Nel tuo file di implementazione, implementa il dynamic come union come questo:

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;

e implementare le funzioni che ho enumerato sopra è semplice. (Naturalmente, è possibile perfezionarlo in diversi modi, definendo procedure di controllo degli errori, aggiungendo bit di controllo se si desidera evitare la duplicazione dei contenuti delle stringhe e così via.)

PISCINE DI MEMORIA SPECIALIZZATE

Per ogni tipo dinamico disponibile, si assegna un pool di memoria, cioè una vasta gamma di tali valori. Un valore dinamico viene quindi implementato come puntatore a un valore in questi pool di memoria convertiti in void* . Il tipo del valore viene quindi recuperato dall'intervallo del puntatore.

Un vantaggio di questa strategia rispetto al precedente è che tratta nativamente con valori di dimensioni diverse mentre l'approccio sindacale prende la dimensione più grande dei possibili tipi di valore. È tuttavia leggermente più complicato da implementare, soprattutto a causa della gestione della memoria: è necessario reimplementare in modo efficiente la logica di malloc se si desidera gestire un numero significativo di valori.

    
risposta data 23.10.2013 - 16:08
fonte
2

void* non è sufficiente se vuoi una digitazione dinamica. Hai bisogno di informazioni sul tipo anche per ogni valore. Qualcosa come:

struct {
  void * data;
  int type_id;
};
    
risposta data 23.10.2013 - 12:54
fonte
0

È eccessivamente ingenuo pensare che digitare un array su void** renderà il tuo codice meno efficiente, quindi dì, int* . Questo perché il compilatore oggi è abbastanza intelligente da manipolare i dati dietro le quinte in modi che un programmatore potrebbe non anticipare. Certo, alcuni compilatori sono più intelligenti di altri, ma stanno migliorando in modo incrementale, e non siamo affatto vicini al climax dell'arte della scrittura di compilatori. Siamo probabilmente da qualche parte proprio all'inizio della strada.

Ci possono anche essere molti altri fattori in gioco, come ad esempio il modo in cui il runtime alloca i suoi oggetti (li frammenta o no, come li allinea, ecc.). In quale parte della memoria atterrano questi oggetti (la memoria può avere tutti i tipi di strutture, gerarchie, diversi dispositivi possono avere la propria memoria, ecc.) E soprattutto: come il codice li gestisce.

Ora, dal punto di vista della teoria dei tipi, "digitato dinamicamente" è un equivoco. Esistono linguaggi non tipizzati (ancora meglio denominati "lingue in cui tutti i dati sono dello stesso tipo") e ci sono lingue in cui i tipi vengono controllati in varie fasi del ciclo di creazione del programma. I tipi possono essere controllati spesso durante la compilazione (se si tratta di un passaggio del ciclo di vita del programma), dopo aver caricato il programma, "dinamicamente" (ovvero applicando un certo valore euristico dopo aver caricato il programma, in base all'utilizzo del programma).

Tuttavia, "linguaggio dinamico" è una terminologia che si trova spesso nella letteratura speciale, diversi ricercatori assegnano significati diversi ad esso, relativi a diversi aspetti del programma. Per alcuni standard, Java può essere chiamato un linguaggio dinamico (perché ha bisogno di prendere determinate quantità di decisioni necessarie per l'invio del metodo in fase di esecuzione, ad esempio). Ma alcuni non chiamerebbero Common Lisp un linguaggio dinamico perché verifica i tipi durante la compilazione.

Quindi, semmai, eviterei di usare "linguaggio dinamico" in un ambiente accademico fino a nuovo avviso:)

    
risposta data 02.11.2013 - 11:01
fonte

Leggi altre domande sui tag