Digite inferência com tipagem de pato - isso funciona? Por que não é usado?

5

Suponha que tenhamos uma linguagem funcional onde os objetos não tenham tipos explicitamente definidos, mas onde propriedades nomeadas possam ser acessadas em objetos. É então possível para o compilador rastrear através do programa quais propriedades poderiam ser acessadas em quais variáveis e fazer inferência de tipo completo no programa, de forma que, se o programa compilar, é garantido que todas as propriedades acessadas devem existir? Por exemplo, cada nome de propriedade poderia corresponder a uma typeclass Haskell e o compilador poderia verificar a solidez usando Hindley-Milner.

Note que, como na maioria dos compiladores, o compilador estaria checando tipos em variáveis , não em objetos . Portanto, ele rejeitaria alguns programas cujos acessos de propriedade são válidos. Aceitar um programa se e somente se todos os seus acessos forem válidos é obviamente incomputável, e não é isso que estou sugerindo ao compilador fazer.

Esse método de verificação de tipos funciona? Isso seria prático? Em caso afirmativo, por que não é usado como um compromisso entre os idiomas tipados dinamicamente e estaticamente?

    
por Solomonoff's Secret 08.05.2017 / 23:31
fonte

5 respostas

4

A Scala fornece inferência de tipos e tipagem estrutural (que, para todos os efeitos, é igual à tipagem de pato).

Em contraste com Haskell, no Scala, o tipo deve ser anotado no argumento da função (embora seja opção para o tipo de retorno), portanto, está sempre claro o que sua função requer.

Isso tem a desvantagem de que, se você usá-lo muito, especialmente em grandes estruturas, seu código terá muitas anotações redundantes.

EDITAR:

Tipos estruturais podem ser nomeados para remover a redundância, embora raramente sejam:

type Duck = {def quack():String}

Pessoalmente, não acho que os tipos estruturais sejam úteis de alguma forma no Scala. Não nomear sua estrutura de dados não faz nada de bom.

Você pode apenas declarar uma característica, então você tem uma estrutura nomeada e estende seu comportamento através de classes de tipos. Se você quiser omitir a nomeação no nome de ser concisa, você pode usar tuplas ou HLists.

formam o glossário do 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.

    
por 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.

Sim, podemos fazer algo assim! Mas duvido que isso seja prático.

Vamos dar uma olhada em como isso pode parecer. Considere a seguinte função comum do Python (retirada do 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)

Suponha que queremos fazer a tipagem de pato e também queremos a inferência de tipos. O Python não tem inferência de tipos, é claro, mas o Haskell sim, e podemos convencer o Haskell a fazer algo muito parecido com a tipagem do pato.

Digitação de pato significa que não nos importamos com os tipos reais de todas as coisas que estamos usando; tudo com o que nos importamos é que as coisas possam ser usadas juntas, da maneira como as usamos. Para deixar Haskell feliz com isso, usaremos parâmetros implícitos para criar objetos e acessar suas propriedades. Assim como nós queremos, o compilador irá rastrear quais propriedades estão sendo acessadas em quais variáveis, e assim por diante.

Nosso código Haskell pode ser assim:

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

Até agora, tudo bem. Este código irá compilar muito bem. Se escrevermos o resto do programa, ele também funcionará bem.

Então, qual é o problema? Vamos perguntar ao GHC qual é o tipo de testSequentialPop . GHC diz:

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, isso é bem complicado.

O problema aqui é que a função deve mencionar todas as operações que ele realiza nos objetos de entrada. Se você tivesse um programa grande que faz coisas complicadas com objetos de entrada, você poderia acabar com um tipo que contém centenas, talvez milhares de restrições.

A inferência de tipos ajudará as coisas um pouco , mas não muito. A inferência de tipo, às vezes, evita que os programadores precisem calcular os tipos por conta própria ou que precisam digitá-los por completo. Os programadores ainda terão que entender os tipos para descobrir como as funções podem ser usadas e para diagnosticar o que está causando erros de tipo.

Dito isto, existem ferramentas que fazem algo semelhante a isto. Por exemplo, a Checkmarx faz uma ferramenta de análise de código estático que pode detectar certas vulnerabilidades de segurança, como ataques de injeção de SQL, rastreando como os objetos são criados e usados. Um ataque de injeção SQL é essencialmente um erro de tipagem de pato: você está criando um objeto (uma cadeia contendo entrada do usuário) e executando uma operação (usando-a como uma consulta SQL), mesmo que esse objeto não suporte essa operação. . Checkmarx traça o caminho inteiro deste objeto, da criação ao uso, e, se encontrar algum problema, ele mostra todo o caminho.

Não sei se seria viável estender essa ideia para que funcione em todas operações, em vez de apenas operações que são um risco à segurança.

    
por 11.05.2017 / 23:18
fonte
1

Acho que isso é possível desde que os tipos não possam ser modificados em tempo de execução, o que significa que você pode fazer isso

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

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

PrintDuck(duck);

mas não isso

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

É apenas digitação estrutural e genéricos. Eu pessoalmente não conheço nenhum idioma que tenha os dois, mas certamente não há nenhuma razão para que uma linguagem não possa, e não há razão para que isso não aconteça em tempo de compilação.

Se você está sugerindo o segundo exemplo, não, não é possível verificar em tempo de compilação. O compilador simplesmente não pode raciocinar sobre campos ou métodos adicionados em tempo de execução.

    
por 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?

Não, acho que não.

Objetos ganham vida em tempo de execução, não em tempo de compilação. O compilador não tem como saber qual objeto terá quais propriedades em tempo de execução.

De o artigo da Wikipédia sobre digitação de :

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

    
por 08.05.2017 / 23:35
fonte
-1

A sua pergunta é infundada - você afirma que não existe tal linguagem, mas eles claramente fazem; tome qualquer idioma com inferência de tipo completa.

    
por 10.05.2017 / 04:05
fonte