2013-08-31 1 views
17

이것은 C++/D 크로스 오버 질문입니다. D programming languageBoost.Range과 같은 C++ 라이브러리와 달리 반복기 쌍을 기반으로하지 않는 ranges을가집니다. 공무원 C++ Ranges Study Group은 기술 사양을 못 박는 데 어려움을 겪은 것으로 보인다.D 범위를 채택하지 못하게하는 C++ 언어 장애물이 있습니까?

질문 : 현재 C++ 11 다가오는 C++ 14 표준 D를 채택하는 것이 아니라 <algorithm>의 적절 rangefied 버전으로 -as 범위 방지 장애물이 있나요 - 도매?

나는 D 또는 그 범위를 충분히 알지 못하지만 게으르며 구성 가능하고 STL 알고리즘의 수퍼 세트를 제공 할 수있는 것처럼 보입니다. D에 대한 성공에 대한 자신의 주장을 감안할 때 C++ 용 라이브러리로 사용하는 것이 좋다고 보입니다. D의 고유 한 기능 (예 : 문자열 mixins, 유니폼 함수 호출 구문)이 범위를 구현하는 데 얼마나 중요한지 궁금하고 C++이 너무 많은 노력을 기울이지 않고도이를 모방 할 수 있는지 궁금합니다 (예 : C++ 14 constexpr). D 컴파일 타임 함수 평가와 매우 유사합니다)

참고 : D 범위가 C++ 라이브러리로 갖춰야 할 올바른 디자인인지 여부에 대한 기술적 인 대답은 아닙니다.

+0

? 최종 반복자는 다른 반복자와 비교할 때 완료 여부를 알려주는 객체입니다. Lazy C++ iterator 기반 범위는 어렵지 않습니다. 공상 상황에서는, 게으른 범위와 같은 몇 가지 추가 보일러가 필요하다 : 간단한 상황, 도시락 연속 메모리를 통해 다양한처럼, 나는 D 스타일의 범위가 빨리 될 수 있습니다 상상할 수 없습니다. – Yakk

+2

부스트 변환 반복기 등을 봤어? 특히, D에서 저렴하지만 C++에서는 비싸고 불가능한 구체적인 문제를 제시하십시오. – Yakk

+0

당신은 그 이유를 믿습니다. 나는 네가 틀렸다고 생각하거나 내가 익숙하지 않은 방식으로 말을 사용한다. 어쨌든, 구체적인 문제는 제발. '의 – Yakk

답변

9

C++에서 D 스타일 범위와 해당 알고리즘의 시스템을 정의 할 수 없게 만드는 고유 한 기술이 있다고 생각하지 않습니다. 가장 큰 언어 수준의 문제는 C++ 범위 기반 for -loops가 범위에서 begin()end()을 사용할 수 있지만 D 스타일 범위를 사용하여 라이브러리를 정의하는 길이로 가정하고 범위 기반 for을 확장해야한다고 가정합니다. 그 (것)들을 취급하는 반복은 가장자리 변화를 보인다.

C 언어의 D 스타일 범위에서 알고리즘을 실험 할 때 발생했던 주요 기술적 인 문제는 필자의 반복기 (실제로는 커서) 기반 구현만큼 빠르게 알고리즘을 만들 수 없다는 것이 었습니다. 물론, 이것은 단지 내 알고리즘 구현 일 수도 있지만 C에서 ++에 기반한 D- 스타일 범위 알고리즘을 제공하는 사람을 보지 못했습니다. 성능은 중요하며 C++ 표준 라이브러리는 최소한 알고리즘의 구현을 약하게 제공해야합니다 (알고리즘의 일반적인 구현은 이라고 약칭 함). 사용자 정의 구현으로 데이터 구조에 적용 할 경우 적어도 빠른 경우 동일한 알고리즘이 동일한 프로그래밍 언어를 사용하여 동일한 데이터 구조를 사용함).나는 D- 스타일 범위를 기반으로 한 약한 효율적인 알고리즘을 만들 수 없었고 내 목표는 실질적으로 매우 효율적인 알고리즘 (약하게 효율적이지만 모든 프로그래밍 언어를 허용하고 동일한 기본 하드웨어 만 가정 함)입니다.

D 스타일 범위 기반 알고리즘을 실험 할 때 반복기 기반 알고리즘보다 알고리즘 구현이 훨씬 어려워 일부 제한 사항을 해결하기 위해 kludges를 처리해야한다는 것을 알았습니다. 물론 현재의 알고리즘이 C++로 지정된 모든 것이 완벽하지는 않습니다. 알고리즘과 추상화를 변경하는 방법에 대한 대략적인 개요는 STL 2.0 페이지에 있습니다. 그러나이 페이지는 관련이 있지만 다소 다른 주제이기 때문에 범위를 많이 다루지는 않습니다. 나는 D- 스타일 범위보다는 iterator (잘 커서, 정말로 커서) 기반의 범위를 상상하고 싶다. 그러나 그 문제는 그것에 관한 것이 아니다.

한 가지 기술적 인 문제는 C++의 모든 범위 추상화가 임시 객체를 합리적인 방법으로 처리해야한다는 것입니다. ranges::sort() 또는 ranges::unique() 게으른인지 여부, 임시 범위의 표현이 처리 될 필요가 종속에서

auto result = ranges::unique(ranges::sort(std::vector<int>{ read_integers() })); 

예를 들어,이 식을 고려하십시오. 임시 범위가 표현의 끝에서 사라지기 때문에 소스 범위의 뷰를 제공하는 것만으로는 이러한 알고리즘 중 하나의 옵션이 될 수 없습니다. 한 가지 가능성은 범위가 r 값인 경우 ranges::sort()ranges::unique()에 대해 다른 결과가 필요하므로 실제 인수가 임시 개체 또는 독립적으로 살아있는 개체 중 하나 인 경우를 구별 할 수 있습니다. D는 가비지 수집되고 원본 범위가 어떤 경우에도 유지되므로이 특정 문제가 없습니다.

위의 예는 또한 지연 평가 알고리즘과 관련된 문제 중 하나를 보여줍니다. 다른 유형을 사용할 수없는 유형을 포함하여 모든 유형은 auto 변수 또는 템플릿 기능에 의해 추론 될 수 있기 때문에 게으른 표현의 끝에서 평가. 따라서 표현 템플릿의 결과를 얻을 수 있고 알고리즘이 실제로 실행되지 않습니다. 즉, l 값이 알고리즘에 전달되면 실제 효과를 얻기 위해 표현식이 실제로 평가되는지 확인해야합니다. 예를 들어, sort() 알고리즘을 사용하면 전체 시퀀스를 돌연변이시킬 수 있습니다 (버전을 변경하지 않으려면 컨테이너를 복사하고 전체 버전을 적용해야합니다. (예를 들어, 거대한 시퀀스의 경우) 즉각적인 문제 일 수있는 여분의 시퀀스를 피할 수 없습니다. 어떤면에서 게으르다 고 가정하면 원래 시퀀스에 대한 l- 값 액세스는 현재 상태에 피크를 제공하며 이는 거의 확실하게 나쁜 것입니다. 이것은 어쨌든 돌연변이 알고리즘의 게으른 평가가 그리 좋은 생각이 아닐 수 있음을 암시합니다.

어떤 경우에도 동일한 고려 사항이 다른 범위 추상화에도 적용되지만 D-sytle 범위를 즉시 채택 할 수없는 C++의 일부 측면이 있습니다. 나는 이러한 고려 사항들이 질문의 범위에서 다소 벗어난 것이라고 생각한다. 또한 첫 번째 문제 (가비지 수집 추가)에 대한 명백한 "솔루션"이 발생하지 않을 것입니다. D에서 두 번째 문제에 대한 해결책이 있는지 모르겠습니다. 두 번째 문제에 대한 해결책이 나올 수도 있지만 (구체적인 질문 : 연산자 자동차) 구체적인 제안이나 그런 기능이 실제로 보입니다.

사실, 범위 스터디 그룹은 기술적 인 세부 사항으로 인해 크게 어려움을 겪지는 않습니다. 지금까지 우리는 실제로 우리가 해결하려고하는 문제를 찾아 내고 솔루션 영역을 확장하고 범위를 좁히려 고 노력했습니다. 또한 그룹은 일반적으로 어떤 일도하지 않습니다. 실제 작업은 항상 개인에 의해 수행되며 대개 매우 소수의 작업자에 의해 수행됩니다.작품의 주요 부분이 실제로 추상화의 집합을 설계하기 때문에 내가 기대하는 연구 그룹이 일부 필요한 사항의 비전과 어떻게 같이해야이 1 ~ 3 개인에 의해 이루어집니다 범위의 결과의 기초.

부족한 어떤 기능
+0

+1 자신의 경험에 대한 매우 상세한 답변. 두 가지 요점은 다음과 같습니다. 1) D 범위가 입력 범위에 대한 참조를 유지하고 모든 중간 알고리즘의 구성된 함수 객체를 저장하므로 임시 문제가 존재하지 않는다고 생각했습니다. 또는 나는 무엇인가 놓치고 있냐? 2) AFAIK는 result.front() 또는 pop-front()를 호출하여 현재 입력 요소에서 저장된 함수 객체를 평가하고 다음 객체를 찾습니다. – TemplateRex

+0

@TemplateRex : 첫 번째 내용 : D 범위는 원본에 대한 참조를 유지하고 _D_의 임시 입력 범위에는 아무런 문제가 없다고 가정합니다. 그러나 C++에서는 참조가 입력 범위로 유지 되더라도 표현식의 끝에서 객체가 삭제되므로 동일한 작업을 수행 할 수 없습니다. D와 달리 C++에는 가비지 수집이 없습니다. 그러나 기술적 문제가 _C++ _에 무엇이 있는지 질문하십시오. 나는 같은 문제가 D에 존재한다고 주장하지 않는다. –

+0

만약 그들이 끝나면 사전에 모르는 생성자 반복자를 쓸 때, 나의 최종 반복자는 '나는 오메가 다.'라는 플래그를 가진 빈 반복자이다. 끝 반복자를 갖기 위해 끝을 찾을 필요가 없습니다. 그래서'end()'for for 루프가 왜 문제인지 모르겠습니다. – Yakk

8

내 C++ 11 지식은 내가 원하는 것보다 훨씬 제한되어 있으므로 아직 알지 못하는 것을 개선하는 새로운 기능이있을 수 있지만 생각할 수있는 세 가지 영역이 있습니다 템플릿 제약 조건, static if 및 타입 인트로 스펙 (inrospection)과 같은 문제가 있습니다.

D에서 범위 기반 함수는 일반적으로 허용하는 범위 유형 (예 : 전달 범위 대 임의 액세스 범위)을 나타내는 템플릿 제약 조건을 갖습니다. 그것은 유형에 전달되는 것을 확인

auto sort(alias less = "a < b", Range)(Range r) 
    if(isRandomAccessRange!Range && 
     hasSlicing!Range && 
     hasLength!Range) 
{...} 

그것이 슬라이스 할 수있는, 랜덤 액세스 범위이며,이 length 속성이 그 : 예를 들어, 여기 std.algorithm.sort에 대한 단순화 된 서명입니다. 이러한 요구 사항을 만족시키지 못하는 형식은 sort으로 컴파일되지 않으며 템플릿 제약 조건이 실패하면 프로그래머가 왜 sort과 함께 작동하지 않는지 명확히 알 수 있습니다 (중간에서 불쾌한 컴파일러 오류가 발생하는 것보다 주어진 타입으로 컴파일하는데 실패 할 때 템플리트 된 함수의).

sort이 올바른 연산을 수행 할 수 없기 때문에 sort이 컴파일에 실패 할 때 컴파일 오류를 제공하는 것보다 유용성이 향상 된 것처럼 보일 수 있지만 사실은 함수 오버로딩과 유형에 큰 영향을줍니다 내성. 예를 들어, 여기 std.algorithm.find의 과부하 두 같습니다 번째 순방향 범위 바늘을 수용하는 반면

R find(alias pred = "a == b", R, E)(R haystack, E needle) 
    if(isInputRange!R && 
     is(typeof(binaryFun!pred(haystack.front, needle)) : bool)) 
{...} 


R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 
    if(isForwardRange!R1 && isForwardRange!R2 && 
     is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) && 
     !isRandomAccessRange!R1) 
{...} 

첫번째는, 단일 소자 인 바늘을 수용한다. 이 둘은 완전히 템플릿 제약 조건에 따라 다른 매개 변수 유형을 가질 수 있으며 내부적으로 매우 다른 코드를 가질 수 있습니다. 템플리트 제약 조건과 같은 것이 없으면 인수의 속성에 오버로드 된 템플릿 함수를 사용할 수 없습니다 (특정 유형 자체에 오버로드되는 것과 반대 됨). 따라서 불가능한 경우가 아니라면 서로 다른 구현을 갖는 것이 훨씬 더 어려워집니다. 사용되는 범위 장르 (예 : 입력 범위 대 전진 범위) 또는 사용되는 유형의 기타 속성. 일부 작업은 개념과 유사한 아이디어로 C++에서이 영역에서 수행되었지만 AFAIK, C++은 인수 유형의 속성을 기반으로 템플릿을 오버로드하는 데 필요한 기능이 여전히 부족합니다 (템플릿 함수 또는 템플릿 유형 임). 특정 인수 유형을 전문으로하는 것 (템플릿 전문화에서 발생)

관련 기능은 static if입니다. if과 동일하지만, 조건이 컴파일 타임에 계산된다는 점과 true 또는 false이 실제로 어떤 분기가 실행되는 것과는 대조적으로 어떤 분기가 컴파일되는지를 결정합니다. 컴파일시 알려진 조건에 따라 코드를 분기 할 수 있습니다. 예 : 당신은 본질적으로 하나의 함수 내에서 템플릿 함수의 오버로드를 넣을 수있는 어느 정도

static if(isDynamicArray!T) 
{} 
else 
{} 

또는

static if(isRandomAccessRange!Range) 
{} 
else static if(isBidirectionalRange!Range) 
{} 
else static if(isForwardRange!Range) 
{} 
else static if(isInputRange!Range) 
{} 
else 
    static assert(0, Range.stringof ~ " is not a valid range!"); 

static if 캔, 템플릿 제약의 필요성을 미연에 방지. 예 :

R find(alias pred = "a == b", R, E)(R haystack, E needle) 
{ 
    static if(isInputRange!R && 
     is(typeof(binaryFun!pred(haystack.front, needle)) : bool)) 
    {...} 
    else static if(isForwardRange!R1 && isForwardRange!R2 && 
     is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) && 
     !isRandomAccessRange!R1) 
    {...} 
} 

하지만 컴파일이 실패 할 때 여전히 지저분 오류가 발생하고 (적어도 D의 구현) 템플릿을 오버로드 할 수 있도록 템플릿을 인스턴스화되기 전에 과부하가 결정되기 때문에 실제로 그것을한다. 따라서 static if을 사용하여 템플릿 구현을 전문화 할 수는 있지만 템플릿 제약 조건이 필요없는 템플릿 제약 조건을 충분히 얻을 수는 없습니다.

대신에 static if은 기능 구현의 일부만 전문화하거나 범위 형식이 래핑 할 범위 형식의 특성을 적절하게 상속 할 수 있도록 만드는 데 적합합니다. 예를 들어 정수 배열에서 std.algorithm.map을 호출하면 결과 범위는 슬라이싱 (소스 범위가 있기 때문에) 될 수 있지만 슬라이스가없는 범위에서 map을 호출하면 (예 : std.algorithm.filter의 범위는 ' 슬라이스가 생겼습니다), 결과 범위는 슬라이싱되지 않습니다. 이를 수행하기 위해 map은 소스 범위가 지원하는 경우에만 opSlice에서 static if을 사용하여 컴파일합니다. 현재의 반환 유형 및 그 코드는 컴파일 여부가 static if의 결과에 달려 map '이

static if (hasSlicing!R) 
{ 
    static if (is(typeof(_input[ulong.max .. ulong.max]))) 
     private alias opSlice_t = ulong; 
    else 
     private alias opSlice_t = uint; 

    static if (hasLength!R) 
    { 
     auto opSlice(opSlice_t low, opSlice_t high) 
     { 
      return typeof(this)(_input[low .. high]); 
     } 
    } 
    else static if (is(typeof(_input[opSlice_t.max .. $]))) 
    { 
     struct DollarToken{} 
     enum opDollar = DollarToken.init; 
     auto opSlice(opSlice_t low, DollarToken) 
     { 
      return typeof(this)(_input[low .. $]); 
     } 

     auto opSlice(opSlice_t low, opSlice_t high) 
     { 
      return this[low .. $].take(high - low); 
     } 
    } 
} 

map의 유형 정의의 코드처럼 보이는 수행의 코드' 그 중 어떤 것도 특정 유형을 기반으로하는 템플릿 특수화로 대체 할 수 없으며 그 중 어떤 유형을 사용하든 모든 새 유형 (분명히 수용 할 수 없음)에 대해 map에 대한 특수화 된 템플릿을 작성할 필요가 없습니다. 특정 유형이 아닌 유형의 속성을 기반으로 코드를 컴파일하려면 static if과 같은 것이 필요합니다 (현재 C++에는 없습니다).

C++에서 부족한 세 번째 주요 항목은 (내가 전반적으로 더 많이 또는 덜 밟았습니다) 유형 인트로 피싱입니다. is(typeof(binaryFun!pred(haystack.front, needle)) : bool) 또는 isForwardRange!Range과 같은 것을 할 수 있다는 사실이 중요합니다. 특정 유형에 특정 속성 집합이 있는지 또는 특정 코드가 컴파일되었는지 여부를 확인하지 않으면 템플리트 제약 조건과 static if이 사용하는 조건을 작성할 수 없습니다. 예를 들어, std.range.isInputRange

template isInputRange(R) 
{ 
    enum bool isInputRange = is(typeof(
    { 
     R r = void;  // can define a range object 
     if (r.empty) {} // can test for empty 
     r.popFront();  // can invoke popFront() 
     auto h = r.front; // can get the front of the range 
    })); 
} 

그것은 코드의 특정 부분이 주어진 형식에 대해 컴파일합니다 확인이 같이 보입니다. 그럴 경우 해당 유형을 입력 범위로 사용할 수 있습니다. 그렇지 않으면 그럴 수 없습니다. AFAIK, C++에서 이와 같은 것을 막연하게 수행하는 것은 불가능합니다. 하지만 범위를 정교하게 구현하려면 isInputRange 같은 것을하거나 특정 유형이 sort - is(typeof(sort(myRange)))으로 컴파일되는지 테스트 할 수 있어야합니다.이를 사용하지 않으면 특정 범위가 지원하는 작업 유형을 기반으로 구현을 전문화 할 수 없으며 범위를 래핑 할 때 범위의 특성을 올바르게 전달할 수 없으며 범위 함수는 모든 인수를 항상 새로운 범위로 래핑합니다. 당신은 제대로 작동하지 않을 타입으로 컴파일되지 않도록 함수를 적절히 보호 할 수 없다. 그리고 물론 static if의 결과와 템플릿 제약 조건도 형식 인트로피멘트에 영향을 미치기 때문에 (이는 컴파일 대상과 컴파일 대상에 영향을 미치기 때문에) 3 가지 기능이 매우 상호 연결됩니다.

실제로 범위가 C++에서 잘 작동하지 않는 주된 이유는 몇 가지 이유 인 metaprogramming in C++ is primitive in comparison to metaprogramming in D입니다. AFAIK, 이러한 기능 (또는 비슷한 것들)을 C++에 추가하고 문제를 해결할 수있는 이유는 없습니다. 그러나 C++에 D와 비슷한 메타 프로그래밍 기능이 있기 전까지는 C++의 범위가 심각하게 약화 될 것입니다.

mixins 및 Uniform Function Call Syntax와 같은 다른 기능도 도움이되지만 근본적인 곳은 없습니다. Mixins은 주로 코드 중복을 줄이는 데 주로 도움이되며 UFCS는 일 반적인 코드가 모든 함수를 멤버 함수처럼 호출하여 유형이 특정 함수 (예 : find)를 정의하는 경우 해당 함수를 호출 할 수 있도록합니다. 좀 더 일반적이고 자유로운 함수 버전 대신에 사용됩니다. 그리고 자유 함수가 사용되기 때문에 코드는 그러한 멤버 함수가 선언되지 않으면 여전히 작동합니다. UFCS는 근본적으로 요구되지 않으며, C++ 11이 beginend으로 수행 한 것과 같이 모든 방향에서 반대 방향으로 자유로운 기능을 선호 할 수도 있습니다. 그렇지만 실제로는 자유 기능이 테스트 할 수 있어야합니다. 멤버 함수가 존재하는지 확인한 다음 자체 구현을 사용하는 대신 내부적으로 멤버 함수를 호출합니다. 따라서 다시 static if 및/또는 템플릿 제약 조건과 함께 인트로 스펙을 입력해야합니다.

범위를 좋아하는만큼이 시점에서 나는 C++에서 그 (것)들로 무엇이든 시도하는 것을 포기했습니다. 왜냐하면 그것들을 정상적으로 만들기위한 기능이 없기 때문입니다. 그러나 다른 사람들이 그것을하는 방법을 알아낼 수 있다면, 그들에게 더 많은 힘이 있습니다. 어쨌든 범위에 관계없이 템플릿 제한, static if 및 유형 내성 검사와 같은 C++ 이득 기능을보고 싶습니다. 메타 프로그래밍이 방법 덜 유쾌하고, 그 동안 D에서 항상 수행합니다. , 나는 C++에서 거의 그것을하지 않는다.

+4

사실, 위의 어느 것도 C++ 범위를 사용하는데 장애가되지 않습니다! C++에서 유사한 기능을 구현하는 데 사용 된 기술이 더 복잡해졌지만 작동하고 사용됩니다. –

+0

+1 어떤 D 기능이 범위/알고리즘에 도움이되는지 보여주는 매우 상세한 대답은 +1입니다. 그러나, 당신의 설명에 따라, 나는 C++이 D의 범위 인터페이스와 일치하지 않을 지 확신하지 못합니다. 확실히, sfinae는'static if'보다 더 장황하지만 실제로 어떤 유효한 D 기능을 모방하는 것이 불가능합니까? 곧 나오는 Concept Lite는 유효한 식의'IsInputRange' 그룹과 밀접하게 일치해야합니다. – TemplateRex

+0

@ DietmarKühl 의견을 C++ 관점에서 답변으로 확장 해 주실 수 있습니까? 나는이 언어 간 질문이 어렵다는 것을 알고 있습니다. – TemplateRex