C++ modelos de Turing-completa?
https://stackoverflow.com/questions/189172
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianSolução
Exemplo
#include <iostream>
template <int N> struct Factorial
{
enum { val = Factorial<N-1>::val * N };
};
template<>
struct Factorial<0>
{
enum { val = 1 };
};
int main()
{
// Note this value is generated at compile time.
// Also note that most compilers have a limit on the depth of the recursion available.
std::cout << Factorial<4>::val << "\n";
}
Isso foi um pouco divertido, mas não muito prático.
Para responder à segunda parte da pergunta:
É este fato útil na prática?
Resposta Curta:Uma espécie de.
Resposta Longa:Sim, mas somente se você for um modelo daemon.
Para transformar uma boa programação usando o modelo de meta-programação que é muito útil para uso por outras pessoas (ou seja, uma biblioteca) é realmente muito difícil (embora capaz de fazer).Para Ajudar a alavancar ainda tem MPL aka (Meta Biblioteca de Programação).Mas tente depurar um erro de compilador o código do modelo e você será uma longa e difícil viagem.
Mas um bom exemplo prático de ser utilizado para algo útil:
Scott Meyers tem vindo a trabalhar extensões para a linguagem C++ (eu uso o termo vagamente) usando a modelagem de instalações.Você pode ler sobre o seu trabalho aqui 'Aplicação Do Código'
Outras dicas
Eu fiz uma máquina de Turing em C ++ 11. Recursos que C ++ 11 adiciona não são significativos para a máquina de Turing, de fato. Ele apenas fornece para as listas de regras de comprimento arbitrários usando modelos variádicos, em vez de usar metaprogramming perversa macro :). Os nomes para as condições são usados ??para produzir um diagrama de saída padrão. Eu removi esse código para manter a pequena amostra.
#include <iostream>
template<bool C, typename A, typename B>
struct Conditional {
typedef A type;
};
template<typename A, typename B>
struct Conditional<false, A, B> {
typedef B type;
};
template<typename...>
struct ParameterPack;
template<bool C, typename = void>
struct EnableIf { };
template<typename Type>
struct EnableIf<true, Type> {
typedef Type type;
};
template<typename T>
struct Identity {
typedef T type;
};
// define a type list
template<typename...>
struct TypeList;
template<typename T, typename... TT>
struct TypeList<T, TT...> {
typedef T type;
typedef TypeList<TT...> tail;
};
template<>
struct TypeList<> {
};
template<typename List>
struct GetSize;
template<typename... Items>
struct GetSize<TypeList<Items...>> {
enum { value = sizeof...(Items) };
};
template<typename... T>
struct ConcatList;
template<typename... First, typename... Second, typename... Tail>
struct ConcatList<TypeList<First...>, TypeList<Second...>, Tail...> {
typedef typename ConcatList<TypeList<First..., Second...>,
Tail...>::type type;
};
template<typename T>
struct ConcatList<T> {
typedef T type;
};
template<typename NewItem, typename List>
struct AppendItem;
template<typename NewItem, typename...Items>
struct AppendItem<NewItem, TypeList<Items...>> {
typedef TypeList<Items..., NewItem> type;
};
template<typename NewItem, typename List>
struct PrependItem;
template<typename NewItem, typename...Items>
struct PrependItem<NewItem, TypeList<Items...>> {
typedef TypeList<NewItem, Items...> type;
};
template<typename List, int N, typename = void>
struct GetItem {
static_assert(N > 0, "index cannot be negative");
static_assert(GetSize<List>::value > 0, "index too high");
typedef typename GetItem<typename List::tail, N-1>::type type;
};
template<typename List>
struct GetItem<List, 0> {
static_assert(GetSize<List>::value > 0, "index too high");
typedef typename List::type type;
};
template<typename List, template<typename, typename...> class Matcher, typename... Keys>
struct FindItem {
static_assert(GetSize<List>::value > 0, "Could not match any item.");
typedef typename List::type current_type;
typedef typename Conditional<Matcher<current_type, Keys...>::value,
Identity<current_type>, // found!
FindItem<typename List::tail, Matcher, Keys...>>
::type::type type;
};
template<typename List, int I, typename NewItem>
struct ReplaceItem {
static_assert(I > 0, "index cannot be negative");
static_assert(GetSize<List>::value > 0, "index too high");
typedef typename PrependItem<typename List::type,
typename ReplaceItem<typename List::tail, I-1,
NewItem>::type>
::type type;
};
template<typename NewItem, typename Type, typename... T>
struct ReplaceItem<TypeList<Type, T...>, 0, NewItem> {
typedef TypeList<NewItem, T...> type;
};
enum Direction {
Left = -1,
Right = 1
};
template<typename OldState, typename Input, typename NewState,
typename Output, Direction Move>
struct Rule {
typedef OldState old_state;
typedef Input input;
typedef NewState new_state;
typedef Output output;
static Direction const direction = Move;
};
template<typename A, typename B>
struct IsSame {
enum { value = false };
};
template<typename A>
struct IsSame<A, A> {
enum { value = true };
};
template<typename Input, typename State, int Position>
struct Configuration {
typedef Input input;
typedef State state;
enum { position = Position };
};
template<int A, int B>
struct Max {
enum { value = A > B ? A : B };
};
template<int n>
struct State {
enum { value = n };
static char const * name;
};
template<int n>
char const* State<n>::name = "unnamed";
struct QAccept {
enum { value = -1 };
static char const* name;
};
struct QReject {
enum { value = -2 };
static char const* name;
};
#define DEF_STATE(ID, NAME) \
typedef State<ID> NAME ; \
NAME :: name = #NAME ;
template<int n>
struct Input {
enum { value = n };
static char const * name;
template<int... I>
struct Generate {
typedef TypeList<Input<I>...> type;
};
};
template<int n>
char const* Input<n>::name = "unnamed";
typedef Input<-1> InputBlank;
#define DEF_INPUT(ID, NAME) \
typedef Input<ID> NAME ; \
NAME :: name = #NAME ;
template<typename Config, typename Transitions, typename = void>
struct Controller {
typedef Config config;
enum { position = config::position };
typedef typename Conditional<
static_cast<int>(GetSize<typename config::input>::value)
<= static_cast<int>(position),
AppendItem<InputBlank, typename config::input>,
Identity<typename config::input>>::type::type input;
typedef typename config::state state;
typedef typename GetItem<input, position>::type cell;
template<typename Item, typename State, typename Cell>
struct Matcher {
typedef typename Item::old_state checking_state;
typedef typename Item::input checking_input;
enum { value = IsSame<State, checking_state>::value &&
IsSame<Cell, checking_input>::value
};
};
typedef typename FindItem<Transitions, Matcher, state, cell>::type rule;
typedef typename ReplaceItem<input, position, typename rule::output>::type new_input;
typedef typename rule::new_state new_state;
typedef Configuration<new_input,
new_state,
Max<position + rule::direction, 0>::value> new_config;
typedef Controller<new_config, Transitions> next_step;
typedef typename next_step::end_config end_config;
typedef typename next_step::end_input end_input;
typedef typename next_step::end_state end_state;
enum { end_position = next_step::position };
};
template<typename Input, typename State, int Position, typename Transitions>
struct Controller<Configuration<Input, State, Position>, Transitions,
typename EnableIf<IsSame<State, QAccept>::value ||
IsSame<State, QReject>::value>::type> {
typedef Configuration<Input, State, Position> config;
enum { position = config::position };
typedef typename Conditional<
static_cast<int>(GetSize<typename config::input>::value)
<= static_cast<int>(position),
AppendItem<InputBlank, typename config::input>,
Identity<typename config::input>>::type::type input;
typedef typename config::state state;
typedef config end_config;
typedef input end_input;
typedef state end_state;
enum { end_position = position };
};
template<typename Input, typename Transitions, typename StartState>
struct TuringMachine {
typedef Input input;
typedef Transitions transitions;
typedef StartState start_state;
typedef Controller<Configuration<Input, StartState, 0>, Transitions> controller;
typedef typename controller::end_config end_config;
typedef typename controller::end_input end_input;
typedef typename controller::end_state end_state;
enum { end_position = controller::end_position };
};
#include <ostream>
template<>
char const* Input<-1>::name = "_";
char const* QAccept::name = "qaccept";
char const* QReject::name = "qreject";
int main() {
DEF_INPUT(1, x);
DEF_INPUT(2, x_mark);
DEF_INPUT(3, split);
DEF_STATE(0, start);
DEF_STATE(1, find_blank);
DEF_STATE(2, go_back);
/* syntax: State, Input, NewState, Output, Move */
typedef TypeList<
Rule<start, x, find_blank, x_mark, Right>,
Rule<find_blank, x, find_blank, x, Right>,
Rule<find_blank, split, find_blank, split, Right>,
Rule<find_blank, InputBlank, go_back, x, Left>,
Rule<go_back, x, go_back, x, Left>,
Rule<go_back, split, go_back, split, Left>,
Rule<go_back, x_mark, start, x, Right>,
Rule<start, split, QAccept, split, Left>> rules;
/* syntax: initial input, rules, start state */
typedef TuringMachine<TypeList<x, x, x, x, split>, rules, start> double_it;
static_assert(IsSame<double_it::end_input,
TypeList<x, x, x, x, split, x, x, x, x>>::value,
"Hmm... This is borky!");
}
" C ++ modelos são Turing Complete" dá uma implementação de uma máquina de Turing em modelos ... que é não-trivial e prova o ponto de uma maneira muito direta. Claro, ele também não é muito útil!
O meu C ++ é um pouco enferrujado, por isso a não ser perfeito, mas é perto.
template <int N> struct Factorial
{
enum { val = Factorial<N-1>::val * N };
};
template <> struct Factorial<0>
{
enum { val = 1 };
}
const int num = Factorial<10>::val; // num set to 10! at compile time.
O ponto é demonstrar que o compilador está avaliando completamente a definição recursiva até que ele atinja uma resposta.
Para dar um exemplo não-trivial: http://gitorious.org/metatrace , um C ++ tempo de compilação ray tracer.
Note que o C ++ 0x irá adicionar um não-modelo, em tempo de compilação, Turing completo instalação em forma de constexpr:
constexpr unsigned int fac (unsigned int u) {
return (u<=1) ? (1) : (u*fac(u-1));
}
Você pode usar constexpr-expressão em todos os lugares onde você precisa compilar constantes de tempo, mas você também pode ligar constexpr-funções com parâmetros não-const.
Uma coisa legal é que isto irá finalmente permitir a compilação de matemática de ponto flutuante, embora o padrão afirma explicitamente que a aritmética de ponto de tempo de compilação flutuantes não tem que coincidir com tempo de execução aritmética de ponto flutuante:
bool f(){ char array[1+int(1+0.2-0.1-0.1)]; //Must be evaluated during translation int size=1+int(1+0.2-0.1-0.1); //May be evaluated at runtime return sizeof(array)==size; }É unspeci fi cado se o valor de f () será verdadeira ou falsa.
O Projeto ++ C Modern Book - programação genérica e Design Pattern por Andrei Alexandrescu é o melhor lugar para obter as mãos na experiência com padrões de programação genérica úteis e poderosas.
O exemplo factorial realmente não mostra que os modelos são Turing completo, tanto quanto isso mostra que eles suportam recursão primitiva. A maneira mais fácil de mostrar que os modelos são Turing completo é pela tese de Church-Turing, que é através da implementação quer uma máquina de Turing (confuso e um inútil bit) ou as três regras (app, ABS var) do cálculo lambda não tipado. Este último é muito mais simples e muito mais interessante.
O que está sendo discutido é uma característica extremamente útil quando você entende que modelos C ++ permitem programação funcional pura em tempo de compilação, um formalismo que é expressivo, poderoso e elegante, mas também muito complicado para escrever se você tem pouca experiência. Também notar como muitas pessoas acham que apenas começando código fortemente templatized muitas vezes pode exigir um grande esforço:. Este é exatamente o caso com linguagens funcionais (puras), o que torna mais difícil compilar mas surpreendentemente produzem código que não requer a depuração
Eu acho que é chamado modelo de meta-programação .
Você pode verificar este artigo do Dr. Dobbs em uma implementação FFT com modelos que eu não acho que isso trivial. O ponto principal é permitir que o compilador para executar uma otimização melhor do que para implementações não modelo como o algoritmo FFT usa um monte de constantes (mesas pecado por exemplo)
Bem, aqui está um tempo de compilação implementação Máquina de Turing executando um 4-state 2-símbolo ocupado castor
#include <iostream>
#pragma mark - Tape
constexpr int Blank = -1;
template<int... xs>
class Tape {
public:
using type = Tape<xs...>;
constexpr static int length = sizeof...(xs);
};
#pragma mark - Print
template<class T>
void print(T);
template<>
void print(Tape<>) {
std::cout << std::endl;
}
template<int x, int... xs>
void print(Tape<x, xs...>) {
if (x == Blank) {
std::cout << "_ ";
} else {
std::cout << x << " ";
}
print(Tape<xs...>());
}
#pragma mark - Concatenate
template<class, class>
class Concatenate;
template<int... xs, int... ys>
class Concatenate<Tape<xs...>, Tape<ys...>> {
public:
using type = Tape<xs..., ys...>;
};
#pragma mark - Invert
template<class>
class Invert;
template<>
class Invert<Tape<>> {
public:
using type = Tape<>;
};
template<int x, int... xs>
class Invert<Tape<x, xs...>> {
public:
using type = typename Concatenate<
typename Invert<Tape<xs...>>::type,
Tape<x>
>::type;
};
#pragma mark - Read
template<int, class>
class Read;
template<int n, int x, int... xs>
class Read<n, Tape<x, xs...>> {
public:
using type = typename std::conditional<
(n == 0),
std::integral_constant<int, x>,
Read<n - 1, Tape<xs...>>
>::type::type;
};
#pragma mark - N first and N last
template<int, class>
class NLast;
template<int n, int x, int... xs>
class NLast<n, Tape<x, xs...>> {
public:
using type = typename std::conditional<
(n == sizeof...(xs)),
Tape<xs...>,
NLast<n, Tape<xs...>>
>::type::type;
};
template<int, class>
class NFirst;
template<int n, int... xs>
class NFirst<n, Tape<xs...>> {
public:
using type = typename Invert<
typename NLast<
n, typename Invert<Tape<xs...>>::type
>::type
>::type;
};
#pragma mark - Write
template<int, int, class>
class Write;
template<int pos, int x, int... xs>
class Write<pos, x, Tape<xs...>> {
public:
using type = typename Concatenate<
typename Concatenate<
typename NFirst<pos, Tape<xs...>>::type,
Tape<x>
>::type,
typename NLast<(sizeof...(xs) - pos - 1), Tape<xs...>>::type
>::type;
};
#pragma mark - Move
template<int, class>
class Hold;
template<int pos, int... xs>
class Hold<pos, Tape<xs...>> {
public:
constexpr static int position = pos;
using tape = Tape<xs...>;
};
template<int, class>
class Left;
template<int pos, int... xs>
class Left<pos, Tape<xs...>> {
public:
constexpr static int position = typename std::conditional<
(pos > 0),
std::integral_constant<int, pos - 1>,
std::integral_constant<int, 0>
>::type();
using tape = typename std::conditional<
(pos > 0),
Tape<xs...>,
Tape<Blank, xs...>
>::type;
};
template<int, class>
class Right;
template<int pos, int... xs>
class Right<pos, Tape<xs...>> {
public:
constexpr static int position = pos + 1;
using tape = typename std::conditional<
(pos < sizeof...(xs) - 1),
Tape<xs...>,
Tape<xs..., Blank>
>::type;
};
#pragma mark - States
template <int>
class Stop {
public:
constexpr static int write = -1;
template<int pos, class tape> using move = Hold<pos, tape>;
template<int x> using next = Stop<x>;
};
#define ADD_STATE(_state_) \
template<int> \
class _state_ { };
#define ADD_RULE(_state_, _read_, _write_, _move_, _next_) \
template<> \
class _state_<_read_> { \
public: \
constexpr static int write = _write_; \
template<int pos, class tape> using move = _move_<pos, tape>; \
template<int x> using next = _next_<x>; \
};
#pragma mark - Machine
template<template<int> class, int, class>
class Machine;
template<template<int> class State, int pos, int... xs>
class Machine<State, pos, Tape<xs...>> {
constexpr static int symbol = typename Read<pos, Tape<xs...>>::type();
using state = State<symbol>;
template<int x>
using nextState = typename State<symbol>::template next<x>;
using modifiedTape = typename Write<pos, state::write, Tape<xs...>>::type;
using move = typename state::template move<pos, modifiedTape>;
constexpr static int nextPos = move::position;
using nextTape = typename move::tape;
public:
using step = Machine<nextState, nextPos, nextTape>;
};
#pragma mark - Run
template<class>
class Run;
template<template<int> class State, int pos, int... xs>
class Run<Machine<State, pos, Tape<xs...>>> {
using step = typename Machine<State, pos, Tape<xs...>>::step;
public:
using type = typename std::conditional<
std::is_same<State<0>, Stop<0>>::value,
Tape<xs...>,
Run<step>
>::type::type;
};
ADD_STATE(A);
ADD_STATE(B);
ADD_STATE(C);
ADD_STATE(D);
ADD_RULE(A, Blank, 1, Right, B);
ADD_RULE(A, 1, 1, Left, B);
ADD_RULE(B, Blank, 1, Left, A);
ADD_RULE(B, 1, Blank, Left, C);
ADD_RULE(C, Blank, 1, Right, Stop);
ADD_RULE(C, 1, 1, Left, D);
ADD_RULE(D, Blank, 1, Right, D);
ADD_RULE(D, 1, Blank, Right, A);
using tape = Tape<Blank>;
using machine = Machine<A, 0, tape>;
using result = Run<machine>::type;
int main() {
print(result());
return 0;
}
Ideone prova prazo: https://ideone.com/MvBU3Z
Explicação: http://victorkomarov.blogspot.ru/ 2016/03 /-tempo de compilação turing-machine.html
Github com mais exemplos: https://github.com/fnz/CTTM
Também é divertido de salientar que é uma linguagem puramente funcional embora quase impossível de depuração. Se você olhar para James post você vai ver o que quero dizer com isso de ser funcional. Em geral, não é o recurso mais útil de C ++. Ele não foi projetado para fazer isso. algo que de que foi descoberto.
Pode ser útil se você quiser calcular constantes em tempo de compilação, pelo menos em teoria. Confira template metaprogramming .
A máquina de Turing é Turing completo, mas isso não significa que você deve querer para usar um para o código de produção.
Tentando fazer qualquer coisa não-trivial com modelos é na minha experiência confuso, feio e sem sentido. Você não tem nenhuma maneira de "depuração" seu "código", mensagens de erro de tempo de compilação será enigmática e, geralmente, nos lugares mais improváveis, e você pode obter os mesmos benefícios de desempenho de diferentes maneiras. (Dica: 4 = 24). Pior, seu código é incompreensível para a média C ++ programador, e será provavelmente não-portáteis devido ao amplo níveis de apoio dentro compiladores atuais.
Os modelos são grandes para geração genérico código (classes container, invólucros de classe, mix-ins), mas não - na minha opinião o Turing completude de modelos é não é útil na prática.
Um exemplo que é razoavelmente útil é uma classe ratio. Existem algumas variantes flutuando. Travando a D == 0 caso é bastante simples, com sobrecargas parciais. A verdadeira computação é no cálculo da GCD de N e D e tempo de compilação. Isto é essencial quando você está usando estas relações nos cálculos de tempo de compilação.
Exemplo: Quando você está calculando centímetros (5) * quilómetros (5), em tempo de compilação você estará multiplicando razão <1.100> e relação <1000,1>. Para evitar transbordamento, você quer uma relação <10,1> em vez de uma relação <1000.100>.
Apenas mais um exemplo de como não se programa:
template<int Depth, int A, typename B>
struct K17 {
static const int x =
K17 <Depth+1, 0, K17<Depth,A,B> >::x
+ K17 <Depth+1, 1, K17<Depth,A,B> >::x
+ K17 <Depth+1, 2, K17<Depth,A,B> >::x
+ K17 <Depth+1, 3, K17<Depth,A,B> >::x
+ K17 <Depth+1, 4, K17<Depth,A,B> >::x;
};
template <int A, typename B>
struct K17 <16,A,B> { static const int x = 1; };
static const int z = K17 <0,0,int>::x;
void main(void) { }
Post at C ++ modelos são turing completa
