C 언어의 동적 타이핑 표현하기

Question

나는 동적 타입 언어를 쓰고 있습니다. 현재 내 개체는이 방식으로 표현된다 :

struct Class { struct Class* class; struct Object* (*get)(struct Object*,struct Object*); }; 
struct Integer { struct Class* class; int value; }; 
struct Object { struct Class* class; }; 
struct String { struct Class* class; size_t length; char* characters; }; 

목표는 내가 struct Object*로 주변의 모든 것을 통과 할 수 있어야한다는 것입니다 후 class 속성을 비교하여 객체의 유형을 발견 할 수 있습니다. 예를 들어, 단순히 다음을 수행 할 사용하는 정수를 캐스팅 (integer 유형 struct Class*의라고 가정) :

struct Object* foo = bar(); 

// increment foo 
if(foo->class == integer) 
    ((struct Integer*)foo)->value++; 
else 
    handleTypeError(); 

문제는 내가 아는 한, C 표준에 대한 어떤 약속을하지 않으며,이다 구조가 저장되는 방법. 내 플랫폼에서이 작동합니다. 그러나 다른 플랫폼에서 struct String은 class 전에 value을 저장할 수 있으며 위의 경우 foo->class에 액세스했을 때 실제로는 foo->value에 액세스 할 수 있습니다. 이는 분명히 나쁩니다. 이식성은 여기서 큰 목표입니다.

이 방법의 대안이 있습니다

struct Object 
{ 
    struct Class* class; 
    union Value 
    { 
     struct Class c; 
     int i; 
     struct String s; 
    } value; 
}; 

여기서 문제는 노조가 노조에 저장 될 수있는 가장 큰 물건의 크기만큼의 공간을 사용한다는 것입니다. 내 유형 중 일부가 내 다른 유형보다 몇 배나 크기 때문에 내 소형 유형 (int)이 허용 할 수없는 절충점 인 큰 유형 (map)만큼의 공간을 차지한다는 것을 의미합니다.

struct Object 
{ 
    struct Class* class; 
    void* value; 
}; 

이렇게하면 작업 속도가 느려지는 수준의 리디렉션이 생성됩니다. 속도가 목표입니다.

마지막 대안은 void* 초를 전달하고 구조의 내부를 직접 관리하는 것입니다. 예를 들어, 위에서 언급 한 형식 시험을 구현하는이 나에게 내가 원하는 모든 것을 (휴대 성, 다양한 유형에 대해 서로 다른 크기 등)을 제공하지만, 적어도 두 가지 단점이있다

void* foo = bar(); 

// increment foo 
if(*((struct Class*) foo) == integer) 
    (*((int*)(foo + sizeof(struct Class*))))++; 
else 
    handleTypeError(); 

:

1. 무시 무시한를 위의 코드는 단일 멤버 오프셋 만 계산합니다. 정수보다 복잡한 유형에서는 훨씬 더 나 빠지게됩니다. 매크로를 사용하여 조금 완화 할 수는 있지만, 문제가 발생하더라도 문제가 될 수 있습니다.
2. 개체를 나타내는 struct이 없으므로 스택 할당 옵션을 사용할 수 없습니다 (적어도 힙에 자체 스택을 구현하지 않고는).

기본적으로 내 질문은 내가 원하는 것을 어떻게 지불 할 수 있습니까? 이식성이 있고 다양한 유형의 크기가 다르며 리디렉션을 사용하지 않고 내 코드를 꽤 유지할 수있는 방법이 있습니까?

EDIT : 이것은 내가 SO 질문에 대해받은 최고의 응답입니다. 대답을 선택하는 것은 어려웠습니다. 그래서 내가 하나의 대답을 선택하도록 허락 했으므로 나를 내 해결책으로 인도하는 사람을 선택했으나 모두 상향 투표를 받았다.

Answer 1

파이썬이 표준 C를 사용하여이 문제를 해결하는 방법에 대해 파이썬 PEP 3123 (http://www.python.org/dev/peps/pep-3123/)을 참조하십시오. 파이썬 솔루션을 문제에 직접 적용 할 수 있습니다.기본적으로이 작업을 수행 할 : Integer*에

struct Object { struct Class* class; }; 
struct Integer { struct Object object; int value; }; 
struct String { struct Object object; size_t length; char* characters; }; 

안전하게 Object*에 Integer* 전송할 수 있습니다

및 Object*을 당신이 당신의 객체가 정수인 것을 알고있는 경우.

Answer 2

C는 첫 번째 접근 방식을 사용할 수 있음을 충분히 보증합니다.당신은하지 않습니다 (

union allow_aliasing { 
    struct Class class; 
    struct Object object; 
    struct Integer integer; 
    struct String string; 
}; 

: 당신이해야 할 유일한 수정은 포인터 앨리어싱 확인을하기 위해, 당신이해야합니다 당신이 사이에 캐스팅 된 struct의 모두 포함 범위에 union이다 - 아무것도 이제까지 사용 조합 할 필요가 그냥

내가 표준의 관련 부분이 믿는) 범위에 있어야한다 :

[# 5] 한 가지 예외 경우 값조합 개체의 멤버 인이 사용되었습니다. 개체에 대한 가장 최근의 저장소가 다른 구성원 인 경우 동작은 구현에 따라 정의됩니다. 하는 노조가 공통의 초기 시퀀스 (아래 참조) 공유 여러 구조를 포함하는 경우, 노조 객체 현재이 구조 중 하나가 포함되어있는 경우 : 한 특별 보증은 노동 조합의 사용을 단순화하기 위해 에서 이루어집니다 중 하나의 공통 초기 부분을 의 완료 유형 인 이 완료된 곳에서 검사 할 수 있습니다. . 하나의 초기 멤버의 시퀀스에 대해 해당 멤버가 호환 가능한 유형 (비트 필드의 경우 동일한 비트 필드의 경우 ) 인 경우 두 구조가 공통 초기 시퀀스를 공유합니다.

(이 직접이 확인을 말할하지 않습니다,하지만 난이 개 struct의 공통 intial 순서를 함께 노동 조합에 투입하는 경우, 그들은에 배치됩니다 보장 않는다고 생각 기억은 똑같은 방식입니다. 어쨌든, 이것을 가정 할 때 오랫동안 관용적이었습니다.

Answer 3

내가 아는 한 C 표준은 구조가 저장되는 방법에 대해 약속하지 않습니다. 내 플랫폼에서이 작동합니다. 그러나 다른 플랫폼에서 struct String은 class 전에 value을 저장할 수 있으며 위의 경우 foo->class에 액세스했을 때 실제로는 foo->value에 액세스 할 수 있습니다. 이는 분명히 나쁩니다. 이식성은 여기서 큰 목표입니다.

나는 당신이 틀렸다고 믿습니다. 첫째, 귀하의 struct String에는 value 회원이 없기 때문입니다. 둘째, 나는 C 이 구조체 멤버의 메모리에 레이아웃을 보장한다고 믿기 때문에. C는 보장을하지 않으면

struct { 
    short a; 
    char b; 
    char c; 
} 

struct { 
    char a; 
    short b; 
    char c; 
} 

, 다음 컴파일러는 아마 같은 크기로 그 모두를 최적화하는 것입니다 : 다음은 크기가 다른 이유입니다. 하지만 구조체의 내부 레이아웃을 보장하므로 자연 정렬 규칙이 적용되어 두 번째 것을 첫 번째보다 크게 만듭니다.

Answer 4

이 질문과 대답에서 제기 된 중요한 문제를 고맙게 생각하지만 CPython은 "더 많거나 적은 영원히"비슷한 트릭을 사용했으며 거대한 다양한 C 컴파일러에서 수십 년 동안 일 해왔다.특히 object.h과 같은 매크로, 과 같은 매크로, PyObject과 같은 구조체 : 모든 종류의 파이썬 객체 (C API 수준에서 아래로)가 아무런 해를 끼치 지 않고 PyObject*으로 /에서 영원히왔다 갔다하는 포인터를 얻고 있습니다. 내가 마지막으로 ISO C 표준을 사용하여 해 변호사를 한 지 오래되었지만 사본이 없기 때문에 (!) 그러나 거기에 몇 가지 제약이 있다고 믿습니다. 은으로 유지해야합니다. 그것은 거의 20 년 동안 갖는 한 ...

Answer 5

섹션은 ISO 9899의 6.2.5 :

구조 타입 부재 객체의 순차적 할당 비어 있지 않은 세트를 설명 (및 1999합니다 (C99 표준)라고 , 경우에 따라 불완전한 배열). 각 배열은 선택적으로 지정된 이름과 가능한 고유 한 유형이 있습니다.

절 6.7.2.1는 또한 말한다

6.2.5에서 설명 된 바와 같이

, 구조체가 그 저장 순서가 순차적으로 분배 부재의 순서로 구성된 형태이며, 유니온 저장소가 겹치는 구성원 시퀀스로 구성된 형식입니다.

[...] 구조체 객체 내에

이 아닌 비트 필드 부재 및 유닛되는 비트 필드 상주가 선언되는 순서대로 증가 어드레스를 갖는다. 적절하게 변환 된 구조체 개체에 대한 포인터는 초기 멤버 (또는 해당 멤버가 비트 필드 인 경우 해당 개체가있는 단위)를 가리키고 그 반대의 경우도 마찬가지입니다. 구조체 객체 내에는 이름이없는 패딩이있을 수 있지만 처음에는 패딩되지 않을 수 있습니다.

이 당신이 필요로하는 것을 보장합니다. 질문에

는 말 :

문제는 내가 아는 한, C 표준이 구조를 저장하는 방법에 대한 어떤 약속도하지 않습니다 것입니다. 내 플랫폼에서이 작동합니다.

이 모든 플랫폼에서 작동합니다. 즉, 현재 사용하고있는 첫 번째 대안이 충분히 안전하다는 의미입니다. 내가 foo- 액세스 할 때

그러나 공과를 시작하기 전에 값을 저장할 수 있습니다 다른 플랫폼 구조체 문자열 정수에

과> 위의 클래스는 사실은 분명 나쁜> 값을 foo- 액세스하는 것입니다. 이식성은 여기서 큰 목표입니다.

없음 준수 컴파일러는 그렇게 할 수 없습니다. [첫 번째 선언 집합을 언급했다는 가정하에 정수로 String을 대체했습니다. 더 자세히 살펴보면 조합이 포함 된 구조를 참조했을 수도 있습니다. 컴파일러는 여전히 class 및 value의 순서를 변경할 수 없습니다.]

Answer 6

동적 유형을 구현하는 데 3 가지 주요 방법이 있으며 상황에 따라 가장 적합한 방법이 있습니다.

1) C 스타일 상속 : 첫 번째 것은 Josh Haberman의 답변에 표시됩니다. 우리는 고전적인 C 스타일의 상속을 사용하여 유형 계층 구조를 만들 : 동적으로 입력 된 인수

struct Object { struct Class* class; }; 
struct Integer { struct Object object; int value; }; 
struct String { struct Object object; size_t length; char* characters; }; 

기능이 class 멤버를 검사하고 적절한 캐스팅, Object*로 나타납니다. 형식을 확인하는 데 드는 비용은 두 개의 포인터 홉입니다. 기본 값을 얻는 데 드는 비용은 하나의 포인터 홉입니다. 이와 같은 접근 방식에서는 객체의 크기가 컴파일 타임에 알려지지 않았기 때문에 일반적으로 객체가 힙에 할당됩니다. 대부분의 malloc 구현은 한 번에 최소 32 바이트를 할당하기 때문에 작은 객체는이 접근 방식으로 상당한 양의 메모리를 낭비 할 수 있습니다.

2) 태그 조합 : 우리는 "짧은 문자열의 최적화"를 사용하여 작은 물체를 액세스하기위한 간접적 인 수준을 제거 할 수 있습니다/"작은 물체 최적화"동적으로

struct Object { 
    struct Class* class; 
    union { 
     // fundamental C types or other small types of interest 
     bool as_bool; 
     int as_int; 
     // [...] 
     // object pointer for large types (or actual pointer values) 
     void* as_ptr; 
    }; 
}; 

기능은 입력 인자들을받지 Object으로 class 회원을 검사하고 적절하게 노동 조합을 읽으십시오. 유형을 확인하는 데 드는 비용은 하나의 포인터 홉입니다. 유형이 특수 소형 유형 중 하나 인 경우, 공용체에 직접 저장되며 값을 검색하기위한 간접 참조가 없습니다. 그렇지 않으면 값을 검색하기 위해 하나의 포인터 홉이 필요합니다. 이 방법은 때때로 힙에 오브젝트를 할당하는 것을 피할 수 있습니다. 객체의 정확한 크기는 컴파일 타임에 아직 알려지지 않았지만 작은 객체를 수용하는 데 필요한 크기와 정렬 (union)을 알 수 있습니다.

첫 번째 두 가지 솔루션에서 컴파일 타임에 가능한 모든 유형을 알고 있다면 포인터 대신 정수 유형을 사용하여 유형을 인코딩하고 포인터 홉 하나로 유형 검사 간접 참조를 줄일 수 있습니다.

3) Nan-boxing : 마지막으로 모든 개체 핸들이 64 비트 인 나노 복싱이 있습니다.

double object; 

는 NaN이 아닌 double에 대응하는 상관 값은 단순히 double 것으로 이해된다. 다른 모든 객체 핸들은 NaN입니다. 사실 일반적으로 사용되는 IEEE-754 부동 소수점 표준에서 NaN에 해당하는 배정 밀도 수레의 비트 값은 실제로 광범위하게 존재합니다. NaN 공간에서는 데이터에 대해 태그 유형과 나머지 비트를 사용합니다. 대부분의 64 비트 컴퓨터가 실제로는 48 비트 주소 공간만을 사용한다는 사실을 이용하여 NaN에서 포인터를 숨길 수 있습니다. 이 방법은 간접적 인 사용이나 추가 메모리 사용을 필요로하지 않지만 우리의 작은 객체 유형을 제약하고 어색하며 이론적으로는 휴대용이 아닙니다.