Tipo di inferenza con digitazione anatra - funziona? Perché non viene utilizzato?

5

Supponiamo di avere un linguaggio funzionale in cui gli oggetti non hanno tipi definiti in modo esplicito, ma è comunque possibile accedere alle proprietà denominate sugli oggetti. È quindi possibile che il compilatore rintracci nel programma a quali proprietà si possa accedere su quali variabili e faccia l'inferenza di tipo completo sul programma in modo che se il programma viene compilato, è garantito che tutte le proprietà accessibili devono esistere? Ad esempio, ogni nome di proprietà potrebbe corrispondere a un typeclass Haskell e il compilatore potrebbe verificare la solidità utilizzando Hindley-Milner.

Si noti che, come con la maggior parte dei compilatori, il compilatore eseguirà il controllo dei tipi su variabili , non su oggetti . Pertanto rifiuterebbe alcuni programmi tutti i cui accessi di proprietà sono validi. Accettare un programma se e solo se tutti i suoi accessi sono validi è ovviamente inconfutabile, e questo non è ciò che sto suggerendo al compilatore.

Questo metodo di controllo dei tipi funziona? Sarebbe pratico? In tal caso, perché non viene utilizzato come compromesso tra le lingue tipizzate dinamicamente e staticamente?

    
posta Solomonoff's Secret 08.05.2017 - 23:31
fonte

5 risposte

4

Scala fornisce sia l'inferenza di tipo che la tipizzazione strutturale (che è a tutti gli effetti uguale alla digitazione anatra).

A differenza di Haskell, in Scala, il tipo deve essere annotato nell'argomento della funzione (sebbene sia un'opzione per il tipo restituito), quindi è sempre chiaro che cosa richiede la tua funzione.

Questo ha lo svantaggio, che se lo usi molto, specialmente su grandi strutture, il tuo codice avrà molte annotazioni ridondanti.

EDIT:

I tipi strutturali possono essere nominati, per rimuovere la ridondanza, anche se raramente sono:

type Duck = {def quack():String}

Personalmente non penso che i tipi strutturali siano utili in alcun modo in Scala. Non nominare la tua struttura dati non fa nulla di buono.

Puoi semplicemente dichiarare un tratto, in modo da avere una struttura con un nome ed estenderne il comportamento tramite classi di tipi. Se vuoi omettere il nome in nome dell'essere concisi, puoi usare tuple o liste.

forma il glossario Scala:

structural type

A refinement type where the refinements are for members not in the base type. For example, { def close(): Unit } is a structural type, because the base type is AnyRef, and AnyRef does not have a member named close.

    
risposta data 10.05.2017 - 09:53
fonte
2

Suppose we have a functional language where objects don't have explicitly defined types, but where named properties can nonetheless be accessed on objects. Is it then possible for the compiler to trace throughout the program which properties could be accessed on which variables and do full type inference on the program so that if the program compiles, it's guaranteed that all accessed properties must exist? For example, each property name could correspond to a Haskell typeclass and the compiler could check the soundness using Hindley-Milner.

Sì, possiamo fare qualcosa di simile! Ma dubito che sarebbe pratico.

Diamo un'occhiata a come potrebbe essere. Considera la seguente funzione ordinaria di Python (tratta dal link ):

def test_sequential_pop():
    model = Sequential()
    model.add(Dense(num_hidden, input_dim=input_dim))
    model.add(Dense(num_class))
    model.compile(loss='mse', optimizer='sgd')
    x = np.random.random((batch_size, input_dim))
    y = np.random.random((batch_size, num_class))
    model.fit(x, y, epochs=1)
    model.pop()
    assert len(model.layers) == 1
    assert model.output_shape == (None, num_hidden)
    model.compile(loss='mse', optimizer='sgd')
    y = np.random.random((batch_size, num_hidden))
    model.fit(x, y, epochs=1)

Supponiamo di voler eseguire la digitazione anatra e vogliamo anche l'inferenza di tipo. Python non ha inferenza di tipo, ovviamente, ma Haskell lo fa, e possiamo convincere Haskell a fare qualcosa di simile alla digitazione anatra.

Digitare anatra significa che non ci interessa davvero i tipi reali di tutte le cose che stiamo usando; tutto ciò che ci interessa è che le cose possano essere usate insieme, nel modo in cui le usiamo. Per rendere felice Haskell, utilizzeremo parametri impliciti per creare oggetti e accedere alle loro proprietà. Proprio come vogliamo, il compilatore traccerà a quali proprietà si accede su quali variabili e così via.

Il nostro codice Haskell potrebbe essere simile a questo:

testSequentialPop = do
    model <- ?newSequential
    ?newDense numHidden (Just inputDim) >>= ?addLayer model
    ?newDense numClass Nothing >>= ?addLayer model
    ?compileModel model "mse" "sgd"
    x <- ?getRandom [batchSize, inputDim]
    y <- ?getRandom [batchSize, numClass]
    ?fitModel model x y 1
    ?popModel model
    ?assert (?length (?layers model) == 1)
    ?assert (?outputShape model == [Nothing, Just numHidden])
    ?compileModel model "mse" "sgd"
    y2 <- ?getRandom [batchSize, numHidden]
    ?fitModel model x y 1

Finora, tutto bene. Questo codice verrà compilato bene. Se scriviamo il resto del programma, funzionerà anche bene.

Quindi qual è il problema? Chiediamo a GHC quale sia il tipo di testSequentialPop . GHC dice:

testSequentialPop
  :: (Eq a5, Eq a7, Monad m, Num a2, Num a3, Num a5, Num a7, Num t2,
      Num a9, ?addLayer::t -> a1 -> m a, ?assert::Bool -> m a6,
      ?compileModel::t -> [Char] -> [Char] -> m a8,
      ?fitModel::t -> t1 -> t1 -> a9 -> m b, ?getRandom::[t2] -> m t1,
      ?layers::t -> t3, ?length::t3 -> a5,
      ?newDense::a2 -> Maybe a3 -> m a1, ?newSequential::m t,
      ?outputShape::t -> [Maybe a7], ?popModel::t -> m a4) =>
     m b

Ooh, è piuttosto complicato.

Il problema qui è che la funzione deve menzionare ogni operazione che esegue sugli oggetti di input. Se disponi di un programma di grandi dimensioni che fa cose complicate con gli oggetti di input, potresti ritrovarti con un tipo che contiene centinaia, forse migliaia di vincoli.

L'inferenza di tipo aiuterà cose un piccolo , ma non così tanto. L'inferenza di tipo a volte salva i programmatori dal dover calcolare i tipi stessi o dal doverli scrivere per intero. I programmatori dovranno ancora capire i tipi per capire come possono essere utilizzate le funzioni e per diagnosticare cosa causa errori di tipo.

Detto questo, ci sono strumenti che fanno qualcosa di simile a questo. Ad esempio, Checkmarx crea uno strumento di analisi del codice statico in grado di rilevare alcune vulnerabilità della sicurezza, come gli attacchi di SQL injection, tracciando il modo in cui gli oggetti vengono creati e utilizzati. Un attacco di SQL injection è essenzialmente un errore di digitazione anatra: si sta creando un oggetto (una stringa contenente l'input dell'utente) e quindi si esegue un'operazione (utilizzandola come query SQL) su di esso, anche se quell'oggetto non supporta quell'operazione . Checkmarx traccia l'intero percorso di questo oggetto, dalla creazione all'utilizzo, e, se trova qualche problema, mostra l'intero percorso.

Non so se sarebbe possibile estendere questa idea in modo che funzioni su tutte , piuttosto che su operazioni che rappresentano un pericolo per la sicurezza.

    
risposta data 11.05.2017 - 23:18
fonte
1

Penso che sia possibile fino a quando i tipi non possono essere modificati in fase di esecuzione, il che significa che puoi farlo

void PrintDuck(d) {
    print("The "+d.feet+" footed duck says "+d.Quack());
}

var duck = {
    int feet = 2;
    string Quack(){
        return "Quack!";
    }
}

PrintDuck(duck);

ma non questo

void PrintDuck(d) {
    print("The "+d.feet+" footed duck says "+d.Quack());
}

var duck = {
    string Quack(){
        return "Quack!";
    }
}

duck.feet = 2; // illegal, modifies type

PrintDuck(duck);

È solo tipizzazione strutturale e generici. Non conosco personalmente nessuna lingua che abbia entrambe le cose, ma non c'è sicuramente alcun motivo per cui un linguaggio non possa, e non c'è motivo per cui non possa accadere tutto in fase di compilazione.

Se stai suggerendo il secondo esempio, allora no, non è possibile controllare in fase di compilazione. Il compilatore semplicemente non può ragionare su campi o metodi aggiunti in fase di esecuzione.

    
risposta data 11.05.2017 - 20:50
fonte
0

Is it then possible for the compiler to trace throughout the program which properties could be accessed on which variables and do full type inference on the program so that if the program compiles, it's guaranteed that all accessed properties must exist?

No, non la penso così

Gli oggetti prendono vita in fase di esecuzione, non in fase di compilazione. Il compilatore non ha modo di sapere quale oggetto avrà le proprietà in fase di esecuzione.

Da l'articolo di Wikipedia sulla tipizzazione di anatra :

It requires that type checking be deferred to runtime, and is implemented by means of dynamic typing or reflection.

    
risposta data 08.05.2017 - 23:35
fonte
-1

La tua domanda è infondata - affermi che non esiste un tale linguaggio, ma lo fanno chiaramente; prendere qualsiasi lingua con inferenza di tipo completa.

    
risposta data 10.05.2017 - 04:05
fonte

Leggi altre domande sui tag