6

質問について詳しく説明したいと思います。強力な型システム(Felix、Ocaml、Haskellなど)を備えた多くの言語では、型コンストラクターを作成することでポリモーフィックリストを定義できます。Felixの定義は次のとおりです。

typedef list[T] = 1 + T * list[T];
typedef list[T] = (1 + T * self) as self;

Ocamlの場合:

type 'a list = Empty | Cons ('a, 'a list)

Cでは、これは再帰的ですが、多形でも構成でもありません。

struct int_list { int elt; struct int_list *next; };

C ++では、C ++が型再帰をサポートしている場合、次のように実行されます。

struct unit {};
template<typename T>
    using list<T> = variant< unit, tuple<T, list<T>> >;

タプル(別名ペア)とバリアント(ただし、Boostで使用される壊れたものではない)の適切な定義が与えられます。または:

    using list<T> = variant< unit, tuple<T, &list<T>> >;

バリアントの定義がわずかに異なる場合は、許容できる可能性があります。テンプレートtypedefがないと、ポリモーフィズムを取得する方法がなく、typedefの適切な構文がないと、スコープ内のターゲットタイプを取得する方法がないため、これをC ++ <C++11で記述することもできませんでした。上記の構文を使用すると、これらの問題の両方が解決されますが、これは再帰が許可されていることを意味するものではありません。

特に、再帰を許可すると、ABI、つまり名前マングリングに大きな影響があることに注意してください(名前マングリングスキームでフィックスポイントの表現が許可されていない限り、これを行うことはできません)。

私の質問:C ++ 11で動作するために必要ですか?[拡張によって構造体が無限に大きくなることはないと仮定します]


編集:明確にするために、要件は一般的な構造型付けです。テンプレートは、たとえば、それを正確に提供します

pair<int, double>
pair<int, pair <long, double> >

匿名で(構造的に)型付けされ、ペアは明らかに多形です。ただし、C ++ <C ++ 11での再帰は、ポインターを使用しても指定できません。C ++ 11では、テンプレートtypedefを使用していても、再帰を指定できます(新しいusing構文では、=記号のLHSの式がRHSのスコープ内にあります)。

ポリモーフィズムと再帰を伴う構造的(匿名)型付けは、型システムの最小要件です。

最新の型システムは、多項式型ファンクターをサポートする必要があります。そうしないと、型システムが扱いにくく、高水準プログラミングを実行できません。これに必要なコンビネータは通常、次のような型理論家によって述べられています。

1 | * | + | fix

ここで、1はユニットタイプ、*はタプルフォーメーション、+はバリアントフォーメーション、fixは再帰です。アイデアは単純です:

tがタイプで、uがタイプの場合、t+uとt*uもタイプです。

C ++では、struct unit {}は1、タプルは*、バリアントは+であり、フィックスポイントはusing=構文で取得できます。フィックスポイントにはテンプレートtypedefが必要になるため、完全に匿名の入力ではありません。


編集:Cのポリモーフィック型コンストラクターの単なる例:

T*          // pointer formation
T (*)(U)    // one argument function type
T[2]        // array

残念ながら、Cでは、関数値は合成ではなく、ポインターの形成は左辺値の制約を受け、型合成の構文規則自体は合成ではありませんが、ここでは次のように言うことができます。

if T is a type T* is a type
if T and U are types, T (*)(U) is a type
if T is a type T[2] is a type

したがって、これらの型コンストラクター(コンビネーター)を再帰的に適用して、新しい中間型を作成することなく、新しい型を取得できます。C ++では、構文上の問題を簡単に修正できます。

template<typename T> using ptr<T> = T*;
template<typename T, typename U> using fun<T,U> = T (*)(U);
template<typename T> using arr2<T> = T[2];

だから今あなたは書くことができます:

arr2<fun<double, ptr<int>>>

構文は構成的であり、タイピングも同様です。

4

5 に答える 5

10

これが必要な場合は、Felix、Ocaml、またはHaskellに固執してください。成功する言語の中には、これら3つほど豊富な型システムを備えているものはほとんどない(どれもありませんか?)ことは容易に理解できます。そして私の意見では、すべての言語が同じであれば、新しい言語を学ぶことは価値がありません。

template<typename T>
using list<T> = variant< unit, tuple<T, list<T>> >;

C ++では、エイリアステンプレートが新しい型を定義しないため、機能しません。これは純粋にエイリアス、同義語であり、その置換と同等です。これは機能です、ところで

そのエイリアステンプレートは、Haskellの次の部分と同等です。

type List a = Either () (a, List a)

「タイプシノニム宣言の[cycles]」は許可されていないため、GHCiはこれを拒否します。これがC++で完全に禁止されているのか、それとも許可されているのに置換すると無限再帰が発生するのかはわかりません。いずれにせよ、それは機能しません。

C ++で新しい型を定義する方法は、、、、、structおよびclassキーワードunionenum使用することです。次のHaskellのようなものが必要な場合(他の2つの言語がわからないため、Haskellの例を主張します)、これらのキーワードを使用する必要があります。

newtype List a = List (Either () (a, List a))
于 2012-04-25T20:47:03.040 に答える
10

いいえ、それはできません。エイリアス テンプレートによる間接的な再帰も禁止されています。

C++11、4.5.7/3:

エイリアス テンプレート宣言の type-id は、宣言されているエイリアス テンプレートを参照してはなりません。エイリアス テンプレートの特殊化によって生成された型は、その特殊化を直接的または間接的に使用してはなりません。[ 例:

template <class T> struct A;
template <class T> using B = typename A<T>::U;
template <class T> struct A {
typedef B<T> U;
};
B<short> b; // error: instantiation of B<short> uses own type via A<short>::U

— 終了例 ]

于 2012-04-25T18:57:27.800 に答える
2

I think you may need to review your type theory, as several of your assertions are incorrect.

Let's address your main question (and backhanded point) - as others have pointed out type recursion of the type you requested is not allowed. This does not mean that c++ does not support type recursion. It supports it perfectly well. The type recursion you requested is type name recursion, which is a syntactic flair that actually has no consequence on the actual type system.

C++ allows tuple membership recursion by proxy. For instance, c++ allows

class A
{
    A * oneOfMe_;
};

That is type recursion that has real consequences. (And obviously no language can do this without internal proxy representation because size is infinitely recursive otherwise).

Also C++ allows translationtime polymorphism, which allow for the creation of objects that act like any type you may create using name recursion. The name recursion is only used to unload types to members or provide translationtime behavior assignments in the type system. Type tags, type traits, etc. are well known c++ idioms for this.

To prove that type name recursion does not add functionality to a type system, it only needs to be pointed out that c++'s type system allows a fully Turing Complete type calculation, using metaprogramming on compiletime constants (and typelists of them), through simple mapping of names to constants. This means there is a function MakeItC++:YourIdeaOfPrettyName->TypeParametrisedByTypelistOfInts that makes any Turing computible typesystem you want.

As you know, being a student of type theory, variants are dual to tuple products. In the type category, any property of variants has a dual property of tuple products with arrows reversed. If you work consistently with the duality, you do not get properties with "new capabilities" (in terms of type calculations). So on the level of type calculations, you obviously don't need variants. (This should also be obvious from the Turing Completeness.)

However, in terms of runtime behavior in an imperative language, you do get different behavior. And it is bad behavior. Whereas products restrict semantics, variants relax semantics. You should never want this, as it provably destroys code correctness. The history of statically typed programming languages has been moving towards greater and greater expression of the semantics in the type system, with the goal that the compiler should be able to understand when the program does not mean what you want it to. The goal has been to turn the compiler into the program verification system.

For instance, with type units, you can express that a particular value isn't just an int but is actually an acceleration measured in meters per square seconds. Assigning a value that is a velocity expressed in feet per hour divided by a timespan of minutes shouldn't just divide the two values - it should note that a conversion is necessary (and either perform it or fail compilation or... do the right thing). Assinging a force should fail compilation. Doing these kinds of checks on program meaning could have given us potentially more martian exploration, for instance.

Variants are the opposite direction. Sure, "if you code correctly, they work correctly", but that's not the point with code verification. They provably add code loci where a different engineer, unfamiliar with current type usage, can introduce the incorrect semantic assumption without translation failure. And, there is always a code transformation that changes an imperative code section from one that uses Variants unsafely to one that use semantically validated non-variant types, so their use is also "always suboptimal".

The majority of runtime uses for variants are typically those that are better encapsulated in runtime polymorphism. Runtime polymorphism has a statically verified semantics that may have associated runtime invariant checking and unlike variants (where the sum type is universally declared in one code locus) actually supports the Open-Closed principle. By needing to declare a variant in one location, you must change that location everytime you add a new functional type to the sum. This means that code never closes to change, and therefore may have bugs introduced. Runtime polymorphism, though, allows new behaviors to be added in separate code loci from the other behaviors.

(And besides, most real language type systems are not distributive anyway. (a, b | c) =/= (a, b) | (a, c) so what is the point here?)

I would be careful making blanket statements about what makes a type system good without getting some experience in the field, particularly if your point is to be provocative and political and enact change. I do not see anything in your post that actually points to healthy changes for any computer language. I do not see features, safety, or any of the other actual real-world concerns being addressed. I totally get the love of type theory. I think every computer scientist should know Cateogry Theory and the denotational semantics of programming languages (domain theory, cartesian categories, all the good stuff). I think if more people understood the Curry-Howard isomorphism as an ontological manifesto, constructivist logics would get more respect.

But none of that provides reasons to attack the c++ type system. There are legitimate attacks for nearly every language - type name recursion and variant availability are not them.


EDIT: Since my point about Turing completeness does not seem to be understood, nor my comment about the c++ way of using type tags and traits to offload type calculations, maybe an example is in order.

Now the OP claims to want this in a usage case for lists, which my earlier point on the layout easily handles. Better, just use std::list. But from other comments and elsewhere, I think they really want this to work on the Felix->C++ translation.

So, what I think the OP thinks they want is something like

template <typename Type>
class SomeClass
{
    // ...
};

and then be able to build a type

SomeClass< /*insert the SomeClass<...> type created here*/ >

I've mentioned this is just a naming convention wanted. Nobody wants typenames - they are transients of the translation process. What is actually wanted is what you will do with Type later on in the structural composition of the type. It will be used in typename calculations to produce member data and method signatures.

So, what can be done in c++ is

struct SelfTag {};

Then, when you want to refer to self, just put this type tag there.

When it's meaningful to do the type calculation, you have a template specialisation on SelfTag that will substitute SomeClass<SelfTag> instead of substituting SelfTag in the appropriate place of the type calculation.

My point here is that the c++ type system is Turing Complete - and that means a lot more than what I think the OP is reading everytime I've written that. Any type calculation may be done (given constraints of compiler recursion) and that really does mean that if you have a problem in one type system in a completely different language, you can find a translation here. I hope this makes things even clearer about my point. Coming back and saying "well you still can't do XYZ in the type system" would be clearly missing the point.

于 2012-04-26T00:41:00.843 に答える
0

C++ には、「奇妙な繰り返しテンプレート パターン」または CRTP があります。ただし、これは C++11 に固有のものではありません。これは、次のことができることを意味します ( Wikipediaから恥知らずにコピー):

template <typename T>
struct base
{
    // ...
};
struct derived : base<derived>
{
    // ...
};
于 2012-04-25T19:22:19.287 に答える
0

@jpalcek が私の質問に答えました。ただし、私の実際の問題 (例で示唆されているように) は、次のような再帰的なエイリアスなしで解決できます。

// core combinators
struct unit;
struct point;
template<class T,class U> struct fix;
template<class T, class U> struct tup2;
template<class T, class U> struct var2;

template <> struct   
  fix<
    point,
    var2<unit, tup2<int,point> > 
  > 
{ 
  // definition goes here
};

fix 型と point 型を使用して再帰を表します。テンプレートを定義する必要はありません。特殊化を定義するだけで済みます。私が必要としていたのは、外部リンケージの 2 つの異なる翻訳単位で同じになる名前でした。名前は型構造の関数でなければなりませんでした。

@Ex0du5 はこれについて考えるよう促しました。実際の解決策は、何年も前のガブリエル・デ・ロワからの通信にも関連しています。貢献してくれたすべての人に感謝したい。

于 2012-04-28T03:36:35.680 に答える