Stork, 3부: 표현식 및 변수 구현

게시 됨: 2022-03-11

시리즈의 3부에서는 경량 프로그래밍 언어가 마침내 실행됩니다. Turing-complete는 아니며 강력하지도 않지만 표현식을 평가하고 C++로 작성된 외부 함수를 호출할 수도 있습니다.

이 과정을 최대한 자세히 설명하려고 노력할 것입니다. 주로 이것이 이 블로그 시리즈의 목적이기 때문입니다. 또한 이 부분에서는 상황이 조금 복잡해지기 때문에 제 문서에서도 마찬가지입니다.

두 번째 기사를 게시하기 전에 이 부분에 대한 코딩을 시작했지만 표현식 파서는 자체 블로그 게시물을 올릴 가치가 있는 독립 실행형 구성 요소여야 한다는 것이 밝혀졌습니다.

일부 악명 높은 프로그래밍 기술과 함께 이 부분이 엄청나게 크지는 않았지만 일부 독자는 해당 프로그래밍 기술을 지적하고 내가 왜 그 기술을 사용해야 했는지 의아해할 것입니다.

매크로를 사용하는 이유

다른 프로젝트와 다른 사람들과 함께 작업하는 프로그래밍 경험을 얻으면서 개발자가 매우 독단적인 경향이 있다는 것을 알게 되었습니다. 아마도 그렇게 하는 것이 더 쉽기 때문일 것입니다.

프로그래밍의 첫 번째 교리는 goto 문은 나쁘고, 사악하고, 끔찍하다는 것입니다. 나는 그 감정이 어디에서 시작되는지 이해할 수 있으며 누군가 goto 문을 사용하는 대부분의 경우에 그 개념에 동의합니다. 일반적으로 피할 수 있으며 더 읽기 쉬운 코드를 대신 작성할 수 있습니다.

그러나 C++에서 내부 루프를 깨는 것은 goto 문을 사용하여 쉽게 수행할 수 있음을 부인할 수 없습니다. bool 변수 또는 전용 함수가 필요한 대안은 금지된 프로그래밍 기술의 버킷에 독단적으로 떨어지는 코드보다 가독성이 떨어질 수 있습니다.

C 및 C++ 개발자에게만 해당되는 두 번째 도그마는 매크로가 나쁘고, 사악하고, 끔찍하며, 기본적으로 재앙이 일어나기를 기다리고 있다는 것입니다. 이것은 거의 항상 다음 예와 함께 제공됩니다.

 #define max(a, b) ((a) > (b) ? (a) : (b)) ... int x = 3; int z = 2; int y = max(x++, z);

그리고 다음 질문이 있습니다. 이 코드 조각 뒤에 오는 x 의 값은 무엇이며 x 는 ? 의 양쪽에 하나씩 두 번 증가하기 때문에 답은 5 입니다. -운영자.

유일한 문제는 이 시나리오에서 아무도 매크로를 사용하지 않는다는 것입니다. 매크로는 일반적인 기능이 잘 작동하는 시나리오에서 사용되는 경우, 특히 기능인 척하는 경우에 악의적이어서 사용자가 부작용을 인식하지 못합니다. 그러나 우리는 그것들을 함수로 사용하지 않을 것이며 함수가 아님을 분명히 하기 위해 이름에 블록 문자를 사용할 것입니다. 우리는 그것들을 적절하게 디버깅할 수 없을 것이고 그것은 나쁜 것입니다. 그러나 대안은 동일한 코드를 수십 번 복사하여 붙여넣는 것이므로 매크로보다 훨씬 더 오류가 발생하기 쉽습니다. 그 문제에 대한 한 가지 해결책은 코드 생성기를 작성하는 것입니다. 하지만 이미 C++에 포함된 코드 생성기가 있는데 왜 코드 생성기를 작성해야 합니까?

프로그래밍의 도그마는 거의 항상 나쁩니다. 나는 내가 방금 설정한 도그마 덫에 재귀적으로 빠지는 것을 피하기 위해 여기서 "거의"를 조심스럽게 사용합니다.

여기에서 이 부분에 대한 코드와 모든 매크로를 찾을 수 있습니다.

변수

이전 파트에서 Stork는 바이너리 또는 어셈블리 언어와 유사한 것으로 컴파일되지 않을 것이라고 언급했지만 정적으로 유형이 지정된 언어가 될 것이라고도 말했습니다. 따라서 컴파일되지만 실행할 수 있는 C++ 개체에서 실행됩니다. 나중에 더 명확해 지지만 지금은 모든 변수가 그 자체로 객체가 될 것이라고 명시하겠습니다.

우리는 그것들을 전역 변수 컨테이너나 스택에 유지하기를 원하기 때문에 한 가지 편리한 접근 방식은 기본 클래스를 정의하고 상속하는 것입니다.

 class variable; using variable_ptr = std::shared_ptr<variable>; class variable: public std::enable_shared_from_this<variable> { private: variable(const variable&) = delete; void operator=(const variable&) = delete; protected: variable() = default; public: virtual ~variable() = default; virtual variable_ptr clone() const = 0; template <typename T> T static_pointer_downcast() { return std::static_pointer_cast< variable_impl<typename T::element_type::value_type> >(shared_from_this()); } };

보시다시피 상당히 간단하고 깊은 복사를 수행하는 함수 clone 은 소멸자를 제외한 유일한 가상 멤버 함수입니다.

우리는 항상 shared_ptr 을 통해 이 클래스의 객체를 사용하므로 std::enable_shared_from_this 에서 상속하는 것이 합리적이므로 공유 포인터를 쉽게 얻을 수 있습니다. static_pointer_downcast 함수는 이 클래스에서 구현으로 자주 다운캐스트해야 하기 때문에 편의를 위해 여기에 있습니다.

이 클래스의 실제 구현은 보유하는 유형으로 매개변수화된 variable_impl 입니다. 우리가 사용할 네 가지 유형에 대해 인스턴스화됩니다.

 using number = double; using string = std::shared_ptr<std::string>; using array = std::deque<variable_ptr>; using function = std::function<void(runtime_context&)>;

숫자 유형으로 double 을 사용합니다. 문자열은 값으로 전달할 때 특정 최적화를 가능하게 하기 위해 변경할 수 없으므로 참조 카운트됩니다. Array는 안정적이므로 std::deque 가 됩니다. runtime_context 는 런타임 동안 프로그램 메모리에 대한 모든 관련 정보를 보유하는 클래스입니다. 우리는 나중에 그것을 얻을 것입니다.

다음 정의도 자주 사용됩니다.

 using lvalue = variable_ptr; using lnumber = std::shared_ptr<variable_impl<number>>; using lstring = std::shared_ptr<variable_impl<string>>; using larray = std::shared_ptr<variable_impl<array>>; using lfunction = std::shared_ptr<variable_impl<function>>;

여기에서 사용된 "l"은 "lvalue"의 줄임말입니다. 어떤 유형에 대한 lvalue가 있을 때마다 variable_impl 에 대한 공유 포인터를 사용합니다.

런타임 컨텍스트

런타임 동안 메모리 상태는 runtime_context 클래스에 유지됩니다.

 class runtime_context{ private: std::vector<variable_ptr> _globals; std::deque<variable_ptr> _stack; std::stack<size_t> _retval_idx; public: runtime_context(size_t globals); variable_ptr& global(int idx); variable_ptr& retval(); variable_ptr& local(int idx); void push(variable_ptr v); void end_scope(size_t scope_vars); void call(); variable_ptr end_function(size_t params); };

전역 변수의 개수로 초기화됩니다.

_globals 모든 전역 변수를 유지합니다. 절대 인덱스가 있는 global 멤버 함수를 사용하여 액세스합니다.
_stack 지역 변수와 함수 인수를 유지하고 _retval_idx 맨 위에 있는 정수는 현재 반환 값의 _stack 에서 절대 인덱스를 유지합니다.
반환 값 은 retval 함수를 사용하여 액세스하는 반면, 지역 변수와 함수 인수는 현재 반환 값과 관련된 인덱스를 전달하여 local 함수로 액세스합니다. 이 경우 함수 인수에는 음수 인덱스가 있습니다.
push 함수는 스택에 변수를 추가하고 end_scope 는 스택에서 전달된 변수 수를 제거합니다.
call 함수는 스택 크기를 1씩 조정하고 _stack의 마지막 요소 인덱스를 _stack 로 _retval_idx 합니다.
end_function 은 스택에서 반환 값과 전달된 인수 수를 제거하고 제거된 반환 값도 반환합니다.

보시다시피 우리는 저수준 메모리 관리를 구현하지 않고 당연하게 여길 수 있는 기본(C++) 메모리 관리를 활용할 것입니다. 적어도 당분간은 힙 할당을 구현하지 않을 것입니다.

runtime_context 를 사용하여 마침내 이 부분의 가장 중요하고 핵심적인 구성 요소에 필요한 모든 빌딩 블록을 갖게 되었습니다.

식

여기에서 제시할 복잡한 솔루션을 완전히 설명하기 위해 이 접근 방식에 정착하기 전에 시도한 몇 가지 실패한 시도를 간략하게 소개하겠습니다.

가장 쉬운 방법은 모든 표현식을 variable_ptr 로 평가하고 다음 가상 기본 클래스를 사용하는 것입니다.

 class expression { ... public: variable_ptr evaluate(runtime_context& context) const = 0; lnumber evaluate_lnumber(runtime_context& context) const { return evaluate(context)->static_pointer_downcast<lnumber>(); } lstring evaluate_lstring(runtime_context& context) const { return evaluate(context)->static_pointer_downcast<lstring>(); } number evaluate_number(runtime_context& context) const { return evaluate_lnumber(context)->value; } string evaluate_string(runtime_context& context) const { return evaluate_lstring(context)->value; } ... }; using expression_ptr = std::unique_ptr<expression>;

그런 다음 더하기, 연결, 함수 호출 등과 같은 각 작업에 대해 이 클래스에서 상속합니다. 예를 들어 다음은 더하기 표현식 구현입니다.

 class add_expression: public expression { private: expression_ptr _expr1; expression_ptr _expr2; public: ... variable_ptr evaluate(runtime_context& context) const override{ return std::make_shared<variable_impl<number> >( _expr1->evaluate_number(context) + _expr2->evaluate_number(context) ); } ... };

따라서 우리는 양쪽( _expr1 및 _expr2 )을 평가하고 추가한 다음 variable_impl<number> 를 구성해야 합니다.

컴파일 시간 동안 유형을 확인했기 때문에 변수를 안전하게 다운캐스트할 수 있으므로 여기서는 문제가 되지 않습니다. 그러나 가장 큰 문제는 이론상 필요하지 않은 반환 객체의 힙 할당에 대해 지불하는 성능 저하입니다. 우리는 가상 함수 선언을 만족시키기 위해 그렇게 합니다. Stork의 첫 번째 버전에서는 함수에서 숫자를 반환할 때 패널티가 발생합니다. 나는 그것으로 살 수 있지만 힙 할당을 수행하는 간단한 사전 증가 표현식으로는 살 수 없습니다.

그런 다음 공통 기반에서 상속된 유형별 표현식을 사용해 보았습니다.

 class expression { ... public: virtual void evaluate(runtime_context& context) const = 0; ... }; class lvalue_expression: public virtual expression { ... public: virtual lvalue evaluate_lvalue(runtime_context& context) const = 0; void evaluate(runtime_context& context) const override { evaluate_lvalue(context); } ... }; using lvalue_expression_ptr = std::unique_ptr<lvalue_expression>; class number_expression: public virtual expression { ... public: virtual number evaluate_number(runtime_context& context) const = 0; void evaluate(runtime_context& context) const override { evaluate_number(context); } ... }; using number_expression_ptr = std::unique_ptr<number_expression>; class lnumber_expression: public lvalue_expression, public number_expression { ... public: virtual lnumber evaluate_lnumber(runtime_context& context) const = 0; lvalue evaluate_lvalue(runtime_context& context) const override { return evaluate_lnumber(context); } number evaluate_number(runtime_context& context) const override { return evaluate_lnumber(context)->value; } void evaluate(runtime_context& context) const override { return evaluate_lnumber(context); } ... }; using lnumber_expression_ptr = std::unique_ptr<lnumber_expression>;

이것은 계층 구조의 일부일 뿐이며(숫자에만 해당) 우리는 이미 다이아몬드 모양(같은 기본 클래스를 가진 두 개의 클래스를 상속하는 클래스) 문제에 봉착했습니다.

운 좋게도 C++는 상속된 클래스에 포인터를 유지함으로써 기본 클래스에서 상속할 수 있는 기능을 제공하는 가상 상속을 제공합니다. 따라서 클래스 B와 C가 A에서 가상으로 상속하고 클래스 D가 B와 C에서 상속하는 경우 D에는 A의 복사본이 하나만 있습니다.

그 경우에 우리가 지불해야 하는 많은 패널티가 있지만 몇 가지 예를 들면 성능과 A에서 다운캐스트할 수 없는 무능력 등입니다. 그러나 이것은 여전히 가상 상속을 처음으로 사용할 수 있는 기회처럼 보였습니다. 내 인생.

이제 더하기 표현식의 구현이 더 자연스럽게 보일 것입니다.

 class add_expression: public number_expression { private: number_expression_ptr _expr1; number_expression_ptr _expr2; public: ... number evaluate_number(runtime_context& context) const override{ return _expr1->evaluate_number(context) + _expr2->evaluate_number(context); } ... };

구문 면에서 더 이상 요구할 것이 없으며 이는 당연한 일입니다. 그러나 내부 표현식이 lvalue 숫자 표현식인 경우 이를 평가하기 위해 두 개의 가상 함수 호출이 필요합니다. 완벽하지는 않지만 끔찍하지도 않습니다.

이 믹스에 문자열을 추가하고 그것이 우리를 얻는 위치를 봅시다:

 class string_expression: public virtual expression { ... public: virtual string evaluate_string(runtime_context& context) const = 0; void evaluate(runtime_context& context) const override { evaluate_string(context); } ... }; using string_expression_ptr = std::unique_ptr<string_expression>;

숫자를 문자열로 변환할 수 있기를 원하므로 string_expression 에서 number_expression 을 상속해야 합니다.

 class number_expression: public string_expression { ... public: virtual number evaluate_number(runtime_context& context) const = 0; string evaluate_string(runtime_context& context) const override { return tostring(evaluate_number(context)); } void evaluate(runtime_context& context) const override { evaluate_number(context); } ... }; using number_expression_ptr = std::unique_ptr<number_expression>;

우리는 살아남았지만 evaluate 가상 메서드를 다시 재정의해야 합니다. 그렇지 않으면 숫자에서 문자열로의 불필요한 변환으로 인해 심각한 성능 문제에 직면하게 될 것입니다.

따라서 상황이 점점 더 나빠지고 있고 서로 변환해야 하는 두 가지 유형의 표현식이 없기 때문에 우리의 디자인은 간신히 살아남을 수 있습니다(양방향 모두). 그런 경우이거나 순환 변환을 시도하면 계층 구조에서 처리할 수 없습니다. 결국 계층 구조는 is-convertible-to 관계가 아니라 is-관계를 반영해야 합니다.

이 모든 실패한 시도는 나를 아직 복잡하지만 - 내 생각에 - 적절한 디자인으로 이끌었습니다. 첫째, 단일 기본 클래스를 갖는 것은 우리에게 중요하지 않습니다. void로 평가되는 표현식 클래스가 필요하지만 컴파일 타임에 void 표현식과 다른 종류의 표현식을 구별할 수 있다면 런타임에 변환할 필요가 없습니다. 따라서 표현식의 반환 유형으로 기본 클래스를 매개변수화합니다.

다음은 해당 클래스의 전체 구현입니다.

 template <typename R> class expression { expression(const expression&) = delete; void operator=(const expression&) = delete; protected: expression() = default; public: using ptr = std::unique_ptr<const expression>; virtual R evaluate(runtime_context& context) const = 0; virtual ~expression() = default; };

표현식 평가당 가상 함수 호출은 하나만 있고(물론 재귀적으로 호출해야 함) 이진 코드로 컴파일하지 않기 때문에 꽤 좋은 결과입니다. 할 수 있는 유일한 일은 유형 간의 변환이 허용되는 경우입니다.

이를 수행하기 위해 각 표현식을 반환 유형으로 매개변수화하고 해당 기본 클래스에서 상속합니다. 그런 다음 evaluate 함수에서 평가 결과를 해당 함수의 반환 값으로 변환합니다.

예를 들어, 이것은 우리의 덧셈 표현식입니다:

 template <typename R> class add_expression: public expression<R> { ... R evaluate(runtime_context& context) const override{ return convert<R>( _expr1->evaluate(context) + _expr2->evaluate(context) ); } ... };

"convert" 기능을 작성하려면 몇 가지 인프라가 필요합니다.

 template<class V, typename T> struct is_boxed { static const bool value = false; }; template<typename T> struct is_boxed<std::shared_ptr<variable_impl<T> >, T> { static const bool value = true; }; string convert_to_string(number n) { std::string str if (n == int(n)) { str = std::to_string(int(n)); } else { str = std::to_string(n); } return std::make_shared<std::string>(std::move(str)); } string convert_to_string(const lnumber& v) { return convert_to_string(v->value); }

is_boxed 구조는 첫 번째 매개변수가 두 번째 유형으로 매개변수화된 variable_impl 에 대한 공유 포인터인 경우에만 true로 평가되는 내부 상수 value 이 있는 유형 특성입니다.

convert 함수의 구현은 이전 버전의 C++에서도 가능하지만 컴파일 시간에 조건을 평가하는 if constexpr 이라는 C++17에 매우 유용한 문이 있습니다. false 로 평가되면 컴파일 시간 오류가 발생하더라도 블록을 모두 삭제합니다. 그렇지 않으면 else 블록이 삭제됩니다.

 template<typename To, typename From> auto convert(From&& from) { if constexpr(std::is_convertible<From, To>::value) { return std::forward<From>(from); } else if constexpr(is_boxed<From, To>::value) { return unbox(std::forward<From>(from)); } else if constexpr(std::is_same<To, string>::value) { return convert_to_string(from); } else { static_assert(std::is_void<To>::value); } }

이 기능을 읽어보십시오.

C++에서 변환 가능한 경우 변환합니다( variable_impl 포인터 업캐스트용).
박스인 경우 박스를 풉니다.
대상 유형이 문자열인 경우 문자열로 변환합니다.
아무 것도 하지 않고 대상이 무효인지 확인하십시오.

제 생각에 이것은 SFINAE를 기반으로 하는 이전 구문보다 훨씬 읽기 쉽습니다.

표현식 유형에 대한 간략한 개요를 제공하고 합리적으로 간략하게 유지하기 위해 몇 가지 기술적인 세부 사항을 생략합니다.

표현식 트리에는 세 가지 유형의 리프 표현식이 있습니다.

전역 변수 표현식
지역변수 표현
상수 표현

 template<typename R, typename T> class global_variable_expression: public expression<R> { private: int _idx; public: global_variable_expression(int idx) : _idx(idx) { } R evaluate(runtime_context& context) const override { return convert<R>( context.global(_idx) ->template static_pointer_downcast<T>() ); } };

반환 유형 외에도 변수 유형으로 매개변수화됩니다. 지역 변수는 유사하게 처리되며 다음은 상수에 대한 클래스입니다.

 template<typename R, typename T> class constant_expression: public expression<R> { private: T _c; public: constant_expression(T c) : _c(std::move(c)) { } R evaluate(runtime_context& context) const override { return convert<R>(_c); } };

이 경우 생성자에서 즉시 상수를 변환합니다.

이것은 대부분의 표현식의 기본 클래스로 사용됩니다.

 template<class O, typename R, typename... Ts> class generic_expression: public expression<R> { private: std::tuple<typename expression<Ts>::ptr...> _exprs; template<typename... Exprs> R evaluate_tuple( runtime_context& context, const Exprs&... exprs ) const { return convert<R>(O()( std::move(exprs->evaluate(context))...) ); } public: generic_expression(typename expression<Ts>::ptr... exprs) : _exprs(std::move(exprs)...) { } R evaluate(runtime_context& context) const override { return std::apply( [&](const auto&... exprs){ return this->evaluate_tuple(context, exprs...); }, _exprs ); } };

첫 번째 인수는 인스턴스화되고 평가를 위해 호출되는 펑터 유형입니다. 나머지 유형은 자식 표현식의 반환 유형입니다.

상용구 코드를 줄이기 위해 세 가지 매크로를 정의합니다.

 #define UNARY_EXPRESSION(name, code)\ struct name##_op {\ template <typename T1> \ auto operator()(T1 t1) {\ code;\ }\ };\ template<typename R, typename T1>\ using name##_expression = generic_expression<name##_op, R, T1>; #define BINARY_EXPRESSION(name, code)\ struct name##_op {\ template <typename T1, typename T2>\ auto operator()(T1 t1, T2 t2) {\ code;\ }\ };\ template<typename R, typename T1, typename T2>\ using name##_expression = generic_expression<name##_op, R, T1, T2>; #define TERNARY_EXPRESSION(name, code)\ struct name##_op {\ template <typename T1, typename T2, typename T3>\ auto operator()(T1 t1, T2 t2, T3 t3) {\ code;\ }\ };\ template<typename R, typename T1, typename T2, typename T3>\ using name##_expression = generic_expression<name##_op, R, T1, T2, T3>;

operator() 는 템플릿으로 정의되지만 일반적으로 그럴 필요는 없습니다. 매크로 인수로 인수 유형을 제공하는 대신 모든 표현식을 동일한 방식으로 정의하는 것이 더 쉽습니다.

이제 대부분의 표현식을 정의할 수 있습니다. 예를 들어, 다음은 /= 에 대한 정의입니다.

 BINARY_EXPRESSION(div_assign, t1->value /= t2; return t1; );

이러한 매크로를 사용하여 거의 모든 표현식을 정의할 수 있습니다. 예외는 인수 평가 순서를 정의한 연산자(논리적 && 및 || , 삼항( ? ) 및 쉼표( , ) 연산자), 배열 인덱스, 함수 호출, 매개변수를 복제하여 함수에 전달하는 param_expression 입니다. 가치로.

이것들을 구현하는 데 복잡한 것은 없습니다. 함수 호출 구현은 가장 복잡하므로 여기에서 설명하겠습니다.

 template<typename R, typename T> class call_expression: public expression<R>{ private: expression<function>::ptr _fexpr; std::vector<expression<lvalue>::ptr> _exprs; public: call_expression( expression<function>::ptr fexpr, std::vector<expression<lvalue>::ptr> exprs ): _fexpr(std::move(fexpr)), _exprs(std::move(exprs)) { } R evaluate(runtime_context& context) const override { std::vector<variable_ptr> params; params.reserve(_exprs.size()); for (size_t i = 0; i < _exprs.size(); ++i) { params.push_back(_exprs[i]->evaluate(context)); } function f = _fexpr->evaluate(context); for (size_t i = params.size(); i > 0; --i) { context.push(std::move(params[i-1])); } context.call(); f(context); if constexpr (std::is_same<R, void>::value) { context.end_function(_exprs.size()); } else { return convert<R>( context.end_function( _exprs.size() )->template static_pointer_downcast<T>() ); } } };

평가된 모든 인수를 스택에 푸시하고 call 함수를 호출하여 runtime_context 를 준비합니다. 그런 다음 평가된 첫 번째 인수(함수 자체)를 호출하고 end_function 메서드의 반환 값을 반환합니다. 여기에서도 if constexpr 구문의 사용법을 볼 수 있습니다. void 를 반환하는 함수에 대한 전체 클래스에 대한 전문화를 작성하지 않아도 됩니다.

이제 런타임 중에 사용할 수 있는 표현식과 관련된 모든 것이 있습니다. 남은 것은 구문 분석된 표현식 트리(이전 블로그 게시물에서 설명)에서 표현식 트리로의 변환뿐입니다.

표현식 빌더

혼동을 피하기 위해 언어 개발 주기의 여러 단계를 명명해 보겠습니다.

메타 컴파일 시간: C++ 컴파일러가 실행되는 단계
컴파일 시간: Stork 컴파일러가 실행되는 단계
런타임: Stork 스크립트가 실행되는 단계

다음은 표현식 작성기의 의사 코드입니다.

 function build_expression(nodeptr n, compiler_context context) { if (n is constant) { return constant_expression(n.value); } else if (n is identifier) { id_info info = context.find(n.value); if (context.is_global(info)) { return global_variable_expression(info.index); } else { return local_variable_expression(info.index); } } else { //operation switch (n->value) { case preinc: return preinc_expression( build_expression(n->child[0]) ); ... case add: return add_expression( build_expression(n->child[0]), build_expression(n->child[1]) ); ... case call: return call_expression( n->child[0], //function n->child[1], //arg0 ... n->child[k+1], //argk ); } } }

모든 작업을 처리해야 한다는 점 외에는 간단한 알고리즘처럼 보입니다.

그것이 효과가 있다면 훌륭할 것이지만 그렇지 않습니다. 우선, 우리는 함수의 반환 유형을 지정해야 하며 반환 유형이 방문하는 노드의 유형에 따라 다르기 때문에 여기에서 분명히 고정되지 않습니다. 노드 유형은 컴파일 타임에 알려져 있지만 반환 유형은 메타 컴파일 타임에 알려야 합니다.

이전 게시물에서 동적 유형 검사를 수행하는 언어의 장점을 보지 못한다고 언급했습니다. 이러한 언어에서 위에 표시된 의사 코드는 거의 문자 그대로 구현될 수 있습니다. 이제 동적 유형 언어의 장점을 잘 알고 있습니다. 최고의 인스턴트 카르마.

운 좋게도 우리는 최상위 표현식의 유형을 알고 있습니다. 이는 컴파일 컨텍스트에 따라 다르지만 표현식 트리를 구문 분석하지 않고 유형을 알고 있습니다. 예를 들어 for 루프가 있는 경우:

 for (expression1; expression2; expression3) ...

첫 번째 및 세 번째 표현식은 평가 결과에 대해 아무 작업도 수행하지 않기 때문에 void 반환 유형을 갖습니다. 그러나 두 번째 표현식에는 루프를 중지할지 여부를 결정하기 위해 0과 비교하기 때문에 유형 number 가 있습니다.

노드 작업과 관련된 식의 유형을 알고 있으면 일반적으로 자식 식의 유형을 결정합니다.

예를 들어 식 (expression1) += (expression2) 의 유형이 lnumber 이면 expression1 에도 해당 유형이 있고 expression2 에도 number 유형이 있음을 의미합니다.

그러나 식 (expression1) < (expression2) 는 항상 number 유형을 갖지만 해당 자식 표현식은 number 또는 string 유형을 가질 수 있습니다. 이 표현식의 경우 두 노드가 모두 숫자인지 확인합니다. 그렇다면 expression1 및 expression2 를 expression<number> 로 빌드합니다. 그렇지 않으면 expression<string> 유형이 됩니다.

우리가 고려하고 처리해야 하는 또 다른 문제가 있습니다.

number 유형의 표현식을 작성해야 한다고 상상해 보십시오. 그런 다음 연결 연산자를 만나면 유효한 것을 반환할 수 없습니다. 표현식 트리를 만들 때 이미 유형을 확인했기 때문에(이전 부분에서) 그런 일이 일어날 수 없다는 것을 알고 있지만, 이는 리턴 유형으로 매개변수화된 템플릿 함수를 작성할 수 없다는 것을 의미합니다. 그 반환 유형에.

한 가지 접근 방식은 if constexpr 을 사용하여 반환 유형별로 함수를 분할하지만 동일한 작업이 여러 분기에 존재하는 경우 해당 코드를 반복해야 하기 때문에 비효율적입니다. 이 경우 별도의 함수를 작성할 수 있습니다.

구현된 솔루션은 노드 유형에 따라 기능을 분할합니다. 각 분기에서 해당 분기 유형이 함수 반환 유형으로 변환 가능한지 확인합니다. 그렇지 않은 경우 컴파일러 오류를 던질 것입니다. 왜냐하면 절대 발생해서는 안 되기 때문입니다. 그러나 코드는 그러한 강력한 주장을 하기에는 너무 복잡합니다. 제가 실수를 했을 수도 있습니다.

변환 가능성을 확인하기 위해 다음과 같은 자명한 유형 특성 구조를 사용하고 있습니다.

 template<typename From, typename To> struct is_convertible { static const bool value = std::is_convertible<From, To>::value || is_boxed<From, To>::value || ( std::is_same<To, string>::value && ( std::is_same<From, number>::value || std::is_same<From, lnumber>::value ) ); };

분할 후 코드는 거의 간단합니다. 원래 표현식 유형에서 우리가 만들고자 하는 유형으로 의미론적으로 캐스팅할 수 있으며 메타 컴파일 시간에 오류가 없습니다.

하지만 상용구 코드가 많기 때문에 이를 줄이기 위해 매크로에 크게 의존했습니다.

 template<typename R> class expression_builder{ private: using expression_ptr = typename expression<R>::ptr; static expression_ptr build_void_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_number_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_lnumber_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_string_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_lstring_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_array_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_larray_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_function_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_lfunction_expression( const node_ptr& np, compiler_context& context ); public: static expression_ptr build_expression( const node_ptr& np, compiler_context& context ) { return std::visit(overloaded{ [&](simple_type st){ switch (st) { case simple_type::number: if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(lnumber); } else { RETURN_EXPRESSION_OF_TYPE(number); } case simple_type::string: if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(lstring); } else { RETURN_EXPRESSION_OF_TYPE(string); } case simple_type::nothing: RETURN_EXPRESSION_OF_TYPE(void); } }, [&](const function_type& ft) { if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(lfunction); } else { RETURN_EXPRESSION_OF_TYPE(function); } }, [&](const array_type& at) { if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(larray); } else { RETURN_EXPRESSION_OF_TYPE(array); } } }, *np->get_type_id()); } };

build_expression 함수는 여기에서 유일한 공개 함수입니다. 노드 유형에서 std::visit 함수를 호출합니다. 이 함수는 전달된 펑터를 variant 에 적용하고 프로세스에서 분리합니다. 여기에서 overloaded 에 대한 자세한 내용과 functor에 대해 읽을 수 있습니다.

매크로 RETURN_EXPRESSION_OF_TYPE 은 표현식 작성을 위해 전용 함수를 호출하고 변환이 불가능하면 예외를 던집니다.

 #define RETURN_EXPRESSION_OF_TYPE(T)\ if constexpr(is_convertible<T, R>::value) {\ return build_##T##_expression(np, context);\ } else {\ throw expression_builder_error();\ return expression_ptr();\ }

변환이 불가능한 경우 컴파일러가 함수 반환 유형을 알 수 없으므로 else 분기에서 빈 포인터를 반환해야 합니다. 그렇지 않으면 std::visit 는 모든 오버로드된 함수가 동일한 반환 유형을 갖도록 요구합니다.

예를 들어 반환 유형으로 string 을 사용하여 표현식을 작성하는 함수가 있습니다.

 static expression_ptr build_string_expression( const node_ptr& np, compiler_context& context ) { if (std::holds_alternative<std::string>(np->get_value())) { return std::make_unique<constant_expression<R, string>>( std::make_shared<std::string>( std::get<std::string>(np->get_value()) ) ); } CHECK_IDENTIFIER(lstring); switch (std::get<node_operation>(np->get_value())) { CHECK_BINARY_OPERATION(concat, string, string); CHECK_BINARY_OPERATION(comma, void, string); CHECK_TERNARY_OPERATION(ternary, number, string, string); CHECK_INDEX_OPERATION(lstring); CHECK_CALL_OPERATION(lstring); default: throw expression_builder_error(); } }

노드가 문자열 상수를 유지하는지 확인하고 그럴 경우 constant_expression 을 빌드합니다.

그런 다음 노드가 식별자를 보유하는지 확인하고 이 경우 lstring 유형의 전역 또는 지역 변수 표현식을 반환합니다. 상수 변수를 구현하면 식별자를 보유할 수 있습니다. 그렇지 않으면 노드가 노드 작업을 보유하고 있다고 가정하고 string 을 반환할 수 있는 모든 작업을 시도합니다.

다음은 CHECK_IDENTIFIER 및 CHECK_BINARY_OPERATION 매크로의 구현입니다.

 #define CHECK_IDENTIFIER(T1)\ if (std::holds_alternative<identifier>(np->get_value())) {\ const identifier& id = std::get<identifier>(np->get_value());\ const identifier_info* info = context.find(id.name);\ if (info->is_global()) {\ return std::make_unique<\ global_variable_expression<R, T1>\ >(info->index());\ } else {\ return std::make_unique<\ local_variable_expression<R, T1>\ >(info->index());\ }\ }

 #define CHECK_BINARY_OPERATION(name, T1, T2)\ case node_operation::name:\ return expression_ptr(\ std::make_unique<name##_expression<R, T1, T2> > (\ expression_builder<T1>::build_expression(\ np->get_children()[0], context\ ),\ expression_builder<T2>::build_expression(\ np->get_children()[1], context\ )\ )\ );

CHECK_IDENTIFIER 매크로는 적절한 인덱스를 사용하여 전역 또는 지역 변수 표현식을 작성하기 위해 compiler_context _컨텍스트를 참조해야 합니다. 이것이 이 구조에서 compiler_context 의 유일한 사용법입니다.

build_expression 이 자식 노드에 대해 CHECK_BINARY_OPERATION 을 재귀적으로 호출하는 것을 볼 수 있습니다.

마무리

내 GitHub 페이지에서 전체 소스 코드를 가져와 컴파일한 다음 표현식을 입력하고 평가된 변수의 결과를 볼 수 있습니다.

나는 인간 창의성의 모든 분야에서 저자가 자신의 제품이 어떤 의미에서 살아 있음을 깨닫는 순간이 있다고 상상합니다. 프로그래밍 언어의 구성에서 언어가 "숨쉬는" 것을 확인하는 순간입니다.

이 시리즈의 다음이자 마지막 부분에서는 나머지 언어 기능을 구현하여 라이브로 실행하는 것을 볼 것입니다.