Quais são as diferenças entre conceitos e restrições de modelo?

96

Eu quero saber quais são as diferenças semânticas entre a proposta de conceitos completos de C ++ e as restrições de modelo (por exemplo, restrições como apareceu em Dlang ou a nova proposta concepts-lite para C ++ 1y ).

O que conceitos completos são capazes de fazer do que as restrições de modelo não podem?

Rayniery
fonte
2
A proposta de restrições vai para isso.
Chris
Eu estava me lembrando de 4.8 Conceitos de projeto , mas na verdade não há muito listado na forma de como os conceitos aumentam as restrições. No mínimo, os conceitos do Google agora podem revelar algumas diferenças facilmente detectáveis ​​depois de obter uma melhor compreensão das restrições da proposta.
chris
Os conceitos IMHO melhoram a legibilidade e fornecem habilidades programáticas mais claras, conforme solicitado há muito tempo por gente como Alexander Stepanov em 'Elementos de programação'. A proposta lite é apenas uma mudança em direção a isso para aliviar o fardo das estranhas restrições do tipo enable_if que são necessárias no momento. Quanto mais cedo melhor para a programação genérica.
dirvine

Respostas:

135

A seguinte informação está desatualizada. Ele precisa ser atualizado de acordo com o último rascunho do Concepts Lite.

A seção 3 da proposta de restrições cobre isso em uma profundidade razoável.

A proposta de conceitos foi colocada em banho-maria por um curto período na esperança de que as restrições (ou seja, concepts-lite) possam ser concretizadas e implementadas em uma escala de tempo mais curta, atualmente visando pelo menos algo em C ++ 14. A proposta de restrições é projetada para atuar como uma transição suave para uma definição posterior de conceitos. As restrições fazem parte da proposta de conceitos e são um bloco de construção necessário em sua definição.

Em Design of Concept Libraries for C ++ , Sutton e Stroustrup consideram o seguinte relacionamento:

Conceitos = Restrições + Axiomas

Para resumir rapidamente seus significados:

  1. Restrição - um predicado sobre propriedades avaliadas estaticamente de um tipo. Requisitos puramente sintáticos. Não é uma abstração de domínio.
  2. Axiomas - Requisitos semânticos de tipos que são considerados verdadeiros. Não verificado estaticamente.
  3. Conceitos - Requisitos gerais e abstratos de algoritmos em seus argumentos. Definido em termos de restrições e axiomas.

Portanto, se você adicionar axiomas (propriedades semânticas) às restrições (propriedades sintáticas), obterá conceitos.


Concepts-Lite

A proposta de conceitos leves nos traz apenas a primeira parte, restrições, mas este é um passo importante e necessário em direção a conceitos plenamente desenvolvidos.

Restrições

As restrições são todas sobre sintaxe . Eles nos fornecem uma maneira de discernir estaticamente as propriedades de um tipo em tempo de compilação, para que possamos restringir os tipos usados ​​como argumentos de modelo com base em suas propriedades sintáticas. Na proposta atual de restrições, elas são expressas com um subconjunto de cálculo proposicional usando conectivos lógicos como &&e ||.

Vamos dar uma olhada em uma restrição em ação:

template <typename Cont>
  requires Sortable<Cont>()
void sort(Cont& container);

Aqui estamos definindo um template de função chamado sort. A nova adição é a cláusula requer . A cláusula require fornece algumas restrições sobre os argumentos do template para esta função. Em particular, essa restrição diz que o tipo Contdeve ser um Sortabletipo. O interessante é que pode ser escrito de uma forma mais concisa como:

template <Sortable Cont>
void sort(Cont& container);

Agora, se você tentar passar qualquer coisa que não seja considerada Sortablepara esta função, você obterá um belo erro que imediatamente informa que o tipo deduzido para Tnão é um Sortabletipo. Se você tivesse feito isso em C ++ 11, teria ocorrido um erro horrível lançado de dentro da sortfunção que não faria sentido para ninguém.

Os predicados de restrições são muito semelhantes aos traços de tipo. Eles pegam algum tipo de argumento de modelo e fornecem algumas informações sobre ele. As restrições tentam responder aos seguintes tipos de perguntas sobre o tipo:

  1. Esse tipo tem tal operador sobrecarregado?
  2. Esses tipos podem ser usados ​​como operandos para este operador?
  3. Esse tipo tem tal e tal característica?
  4. Esta expressão constante é igual a isso? (para argumentos de modelo sem tipo)
  5. Esse tipo tem uma função chamada yada-yada que retorna esse tipo?
  6. Esse tipo atende a todos os requisitos sintáticos para ser usado dessa forma?

No entanto, as restrições não têm como objetivo substituir as características de tipo. Em vez disso, eles trabalharão de mãos dadas. Alguns traços de tipo agora podem ser definidos em termos de conceitos e alguns conceitos em termos de traços de tipo.

Exemplos

Portanto, o importante sobre as restrições é que elas não se importam nem um pouco com a semântica. Alguns bons exemplos de restrições são:

  • Equality_comparable<T>: Verifica se o tipo tem ==com os dois operandos do mesmo tipo.

  • Equality_comparable<T,U>: Verifica se há um ==com operandos esquerdo e direito dos tipos fornecidos

  • Arithmetic<T>: Verifica se o tipo é aritmético.

  • Floating_point<T>: Verifica se o tipo é um tipo de ponto flutuante.

  • Input_iterator<T>: Verifica se o tipo suporta as operações sintáticas que um iterador de entrada deve suportar.

  • Same<T,U>: Verifica se os tipos fornecidos são iguais.

Você pode experimentar tudo isso com uma compilação leve de conceitos especiais do GCC .


Beyond Concepts-Lite

Agora vamos entrar em tudo além da proposta de conceitos leves. Isso é ainda mais futurista do que o próprio futuro. De agora em diante, tudo provavelmente mudará um pouco.

Axiomas

Os axiomas têm tudo a ver com semântica . Eles especificam relacionamentos, invariantes, garantias de complexidade e outras coisas semelhantes. Vejamos um exemplo.

Embora a Equality_comparable<T,U>restrição diga que existe um operator== que aceita tipos Te U, ela não diz o que essa operação significa . Para isso, teremos o axioma Equivalence_relation. Este axioma diz que quando objetos desses dois tipos são comparados com operator==doação true, esses objetos são equivalentes. Isso pode parecer redundante, mas certamente não é. Você poderia facilmente definir um operator==que se comportasse como um operator<. Você seria mau em fazer isso, mas você poderia.

Outro exemplo é um Greateraxioma. É muito bom dizer que dois objetos do tipo Tpodem ser comparados com os operadores >e <, mas o que eles significam ? O Greateraxioma diz que se f xé maior então y, então yé menor que x. A especificação proposta, tal axioma, se parece com:

template<typename T>
axiom Greater(T x, T y) {
  (x>y) == (y<x);
}

Portanto, os axiomas respondem aos seguintes tipos de perguntas:

  1. Esses dois operadores têm essa relação um com o outro?
  2. Este operador para tal e tal tipo significa isso?
  3. Essa operação nesse tipo tem essa complexidade?
  4. Este resultado desse operador implica que isso é verdade?

Ou seja, eles se preocupam inteiramente com a semântica de tipos e operações nesses tipos. Essas coisas não podem ser verificadas estaticamente. Se isso precisar ser verificado, um tipo deve de alguma forma proclamar que está de acordo com essa semântica.

Exemplos

Aqui estão alguns exemplos comuns de axiomas:

  • Equivalence_relation: Se dois objetos se comparam ==, eles são equivalentes.

  • Greater: Sempre x > y, então y < x.

  • Less_equal: Sempre x <= y, então !(y < x).

  • Copy_equality: Para xe yde tipo T: se x == y, um novo objeto do mesmo tipo criado por construção de cópia T{x} == ye ainda x == y(ou seja, não é destrutivo).

Conceitos

Agora, os conceitos são muito fáceis de definir; eles são simplesmente a combinação de restrições e axiomas . Eles fornecem um requisito abstrato sobre a sintaxe e a semântica de um tipo.

Como exemplo, considere o seguinte Orderedconceito:

concept Ordered<Regular T> {
  requires constraint Less<T>;
  requires axiom Strict_total_order<less<T>, T>;
  requires axiom Greater<T>;
  requires axiom Less_equal<T>;
  requires axiom Greater_equal<T>;
}

Em primeiro lugar, observe que para que o tipo de modelo Tseja Ordered, ele também deve atender aos requisitos do Regularconceito. O Regularconceito é um requisito muito básico de que o tipo seja bem comportado - pode ser construído, destruído, copiado e comparado.

Além desses requisitos, o Orderedrequer que Tcumpra uma restrição e quatro axiomas:

  • Restrição: um Orderedtipo deve ter um operator<. Isso é verificado estaticamente, portanto, deve existir.
  • Axiomas: Para xe ydo tipo T:
    • x < y dá uma ordem total estrita.
    • Quando xé maior que y, yé menor que xe vice-versa.
    • Quando xé menor ou igual a y, ynão é menor que xe vice-versa.
    • Quando xé maior ou igual a y, ynão é maior que xe vice-versa.

Combinar restrições e axiomas como esse fornece conceitos. Eles definem os requisitos sintáticos e semânticos para tipos abstratos para uso com algoritmos. Os algoritmos atualmente têm que assumir que os tipos usados ​​suportarão certas operações e expressarão certas semânticas. Com conceitos, seremos capazes de garantir que os requisitos sejam atendidos.

No projeto de conceitos mais recentes , o compilador só verifica se os requisitos sintáticos de um conceito são atendidos pelo argumento do modelo. Os axiomas não são verificados. Como os axiomas denotam semânticas que não são estaticamente avaliáveis ​​(ou muitas vezes impossíveis de verificar inteiramente), o autor de um tipo teria que declarar explicitamente que seu tipo atende a todos os requisitos de um conceito. Isso era conhecido como mapeamento de conceito em projetos anteriores, mas foi removido desde então.

Exemplos

Aqui estão alguns exemplos de conceitos:

  • Regular os tipos são construtíveis, destrutíveis, copiáveis ​​e podem ser comparados.

  • Orderedtipos suportam operator<e têm uma ordem total estrita e outras semânticas de ordem.

  • Copyableos tipos podem ser construídos por cópia, destrutíveis e, se xfor igual a ye xfor copiado, a cópia também será comparada igual a y.

  • Iteratortipos tipos devem ter associadas value_type, reference, difference_type, e iterator_categoryque se deve atender a certos conceitos. Eles também devem suportar operator++e ser desreferenciáveis.

The Road to Concepts

As restrições são o primeiro passo em direção a um recurso de conceitos completos do C ++. Eles são uma etapa muito importante, porque fornecem os requisitos de tipos que podem ser executados estaticamente para que possamos escrever funções e classes de modelo muito mais limpas. Agora podemos evitar algumas das dificuldades e feiúras de std::enable_ife seus amigos de metaprogramação.

No entanto, há uma série de coisas que a proposta de restrições não faz:

  1. Não fornece uma linguagem de definição de conceito.

  2. As restrições não são mapas conceituais. O usuário não precisa anotar especificamente seus tipos para atender a certas restrições. Eles são verificados estaticamente usando recursos de linguagem de tempo de compilação simples.

  3. As implementações de modelos não são restringidas pelas restrições de seus argumentos de modelo. Ou seja, se o seu template de função faz algo com um objeto de tipo restrito que não deveria fazer, o compilador não tem como diagnosticar isso. Uma proposta de conceitos com todos os recursos seria capaz de fazer isso.

A proposta de restrições foi projetada especificamente para que uma proposta de conceitos completos possa ser introduzida em cima dela. Com alguma sorte, essa transição deve ser um passeio bastante suave. O grupo de conceitos está procurando introduzir restrições para C ++ 14 (ou em um relatório técnico logo depois), enquanto conceitos completos podem começar a surgir em algum momento em torno do C ++ 17.

sftrabbit
fonte
5
Deve-se observar que o concepts-lite não verifica as restrições contra a implementação do próprio modelo. Portanto, você pode alegar que qualquer DefaultConstructable pode ser usado, mas o compilador não o impedirá de usar um construtor de cópia por acidente. Uma proposta de conceitos mais completa seria.
Nicol Bolas
24
Esse é um primeiro rascunho ?!
Nicol Bolas
2
@sftrabbit, resposta muito boa. Mas eu tenho uma pergunta: como um compilador verificará se um tipo atende aos requisitos semânticos de um conceito?
Rayniery
1
Os 'axiomas' serão verificados (com muita incerteza) durante o tempo de execução ou servirão apenas como uma espécie de etiqueta de promessa?
Red XIII
4
@ScarletAmaranth: Porque tudo se resume a provar automaticamente um teorema em tempo limitado finito. Existem dois obstáculos para isso: 1. Provar qualquer teorema em tempo limitado finito que é extremamente difícil na teoria e impossível com a tecnologia atual. 2. Você não pode provar um axioma, a menos que a prova seja baseada em outros axiomas. (Nesse caso, matematicamente torna-se "não um axioma") Esses axiomas têm como objetivo dizer ao compilador "Claro que você pode reverter a comparação se achar útil ...", ou "Sim, um EmptySet usado em uma interseção sempre dá o mesmo resultado. "
Laurent LA RIZZA
4

Meus 2 centavos:

  1. A proposta concepts-lite não se destina a fazer "verificação de tipo" de implementação de modelo . Ou seja, o Concepts-lite garantirá (teoricamente) a compatibilidade da interface no site de instanciação do modelo. Citando o artigo: "concepts lite é uma extensão de C ++ que permite o uso de predicados para restringir argumentos de template". E é isso. Isso não diz que o corpo do modelo será verificado (isoladamente) em relação aos predicados. Isso provavelmente significa que não há noção de primeira classe de arquétipos quando você está falando sobre conceitos leves . arquétipos, se bem me lembro, em propostas de conceitos pesados ​​são tipos que oferecem nada menos e nada mais para satisfazer a implementação do modelo.

  2. concepts-lite usam funções constexpr glorificadas com um pouco de truque de sintaxe suportado pelo compilador. Nenhuma mudança nas regras de pesquisa.

  3. Os programadores não são obrigados a escrever mapas de conceitos.

  4. Finalmente, citando novamente "A proposta de restrições não aborda diretamente a especificação ou o uso da semântica; ela visa apenas a verificação da sintaxe." Isso significaria que os axiomas não estão dentro do escopo (até agora).

Sumant
fonte