Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma once
- #include <insituc/transform/derivator/intrinsics.hpp>
- #include <insituc/base_types.hpp>
- #include <insituc/ast/ast.hpp>
- #include <insituc/ast/compare.hpp>
- #include <insituc/utility/reversed_container.hpp>
- #include <deque>
- #include <stack>
- #include <algorithm>
- #include <iterator>
- #include <functional>
- #include <exception>
- #include <stdexcept>
- #include <map>
- #include <limits>
- #include <experimental/optional>
- namespace insituc
- {
- namespace transform
- {
- struct derivator
- {
- derivator()
- : derive_statement_(*this)
- , derive_expression_(*this)
- , derive_intrinsic_()
- { ; }
- private :
- struct context
- {
- struct trailing_wrt
- {
- size_type block_;
- size_type offset_;
- };
- using tail_type = std::deque< trailing_wrt >;
- using head_type = std::deque< tail_type >;
- ast::symbols wrts_;
- head_type wrts_blocks_;
- std::deque< size_type > wrts_offsets_;
- context() = default;
- context(ast::symbols const & _wrts)
- {
- push(_wrts);
- }
- size_type
- offset(trailing_wrt const & _trailing_wrt) const
- {
- if (_trailing_wrt.block_ == std::numeric_limits< size_type >::max()) {
- assert(_trailing_wrt.offset_ == 0);
- return 0;
- } else {
- return wrts_offsets_[_trailing_wrt.block_] + _trailing_wrt.offset_;
- }
- }
- size_type
- prev_arity() const
- {
- if (wrts_offsets_.empty()) {
- return 1;
- } else {
- return wrts_offsets_.back();
- }
- }
- size_type
- arity() const
- {
- if (wrts_offsets_.empty()) {
- return 1;
- } else {
- return wrts_offsets_.back() + wrts_blocks_.back().size();
- }
- }
- ast::symbol const &
- wrt() const
- {
- assert(!wrts_.empty());
- return wrts_.back();
- }
- void
- push(ast::symbol const & _wrt)
- {
- assert(wrts_.size() == wrts_blocks_.size());
- assert(wrts_offsets_.size() == wrts_blocks_.size());
- wrts_offsets_.push_back(arity());
- wrts_blocks_.push_back(tail(wrts_blocks_, _wrt));
- wrts_.push_back(_wrt);
- }
- void
- push(ast::symbol && _wrt)
- {
- assert(wrts_.size() == wrts_blocks_.size());
- assert(wrts_offsets_.size() == wrts_blocks_.size());
- wrts_offsets_.push_back(arity());
- wrts_blocks_.push_back(tail(wrts_blocks_, _wrt));
- wrts_.push_back(std::move(_wrt));
- }
- void
- push(ast::symbols const & _wrts)
- {
- for (ast::symbol const & wrt_ : _wrts) {
- push(wrt_);
- }
- }
- void
- pop()
- {
- assert(!wrts_.empty());
- assert(wrts_.size() == wrts_blocks_.size());
- assert(wrts_offsets_.size() == wrts_blocks_.size());
- wrts_.pop_back();
- wrts_offsets_.pop_back();
- wrts_blocks_.pop_back();
- }
- void
- clear()
- {
- wrts_.clear();
- wrts_offsets_.clear();
- wrts_blocks_.clear();
- }
- private :
- tail_type
- tail(head_type const & _head, ast::symbol const & _wrt) const
- {
- tail_type tail_;
- size_type block_ = _head.size();
- while (0 < block_) {
- --block_;
- size_type offset_ = _head[block_].size();
- while (0 < offset_) {
- --offset_;
- tail_.push_front({block_, offset_});
- }
- if (_wrt == wrts_[block_]) {
- return tail_;
- }
- }
- tail_.push_front({std::numeric_limits< size_type >::max(), 0});
- return tail_;
- }
- };
- context external_context_;
- std::deque< std::reference_wrapper< ast::symbol const > > local_variables_;
- std::deque< ast::identifier > callies_; // should die-in-use or be cleared after each derive_function call by user code
- ast::entry_definition
- derive_function(ast::entry_definition const & _entry_definition)
- try {
- assert(local_variables_.empty());
- ast::entry_definition entry_definition_;
- entry_definition_.entry_name_ = _entry_definition.entry_name_;
- entry_definition_.entry_name_.derive(external_context_.wrt());
- if (!_entry_definition.argument_list_.lvalues_.empty()) { // if not nullary
- entry_definition_.argument_list_.lvalues_ = derive_lvalues(_entry_definition.argument_list_.lvalues_);
- }
- entry_definition_.body_.statements_ = derive_statements(_entry_definition.body_.statements_);
- local_variables_.clear();
- return entry_definition_;
- } catch (std::exception const &) {
- local_variables_.clear();
- throw;
- }
- ast::lvalues
- derive_lvalues(ast::lvalues const & _lvalues)
- {
- assert(!_lvalues.empty());
- ast::lvalues lvalues_ = _lvalues;
- assert((lvalues_.size() % external_context_.prev_arity()) == 0);
- size_type const arity_ = lvalues_.size() / external_context_.prev_arity();
- for (size_type i = 0; i < arity_; ++i) {
- ast::identifier const & lvalue_ = _lvalues[i];
- assert(lvalue_.is_original());
- local_variables_.emplace_back(lvalue_.symbol_);
- }
- for (typename context::trailing_wrt const & position_ : external_context_.wrts_blocks_.back()) {
- size_type const offset_ = arity_ * external_context_.offset(position_);
- for (size_type i = 0; i < arity_; ++i) {
- ast::identifier const & lvalue_ = _lvalues[offset_ + i];
- lvalues_.push_back(lvalue_);
- lvalues_.back().derive(external_context_.wrt());
- }
- }
- assert(!lvalues_[arity_].is_original());
- return lvalues_;
- }
- ast::rvalues
- derive_rvalues(ast::rvalues const & _rvalues, context const & _context)
- {
- assert(!_rvalues.empty());
- ast::rvalues rvalues_ = _rvalues;
- assert((rvalues_.size() % _context.prev_arity()) == 0);
- size_type const arity_ = rvalues_.size() / _context.prev_arity();
- for (typename context::trailing_wrt const & position_ : _context.wrts_blocks_.back()) {
- size_type const offset_ = arity_ * _context.offset(position_);
- for (size_type i = 0; i < arity_; ++i) {
- ast::rvalue const & rvalue_ = _rvalues[offset_ + i];
- rvalues_.push_back(derive_operand(rvalue_));
- }
- }
- return rvalues_;
- }
- ast::rvalues
- derive_rvalues(ast::rvalues const & _rvalues)
- {
- return derive_rvalues(_rvalues, external_context_);
- }
- struct derivator_of_statement
- {
- using result_type = ast::statement;
- derivator_of_statement(derivator & _derivator)
- : derivator_(_derivator)
- { ; }
- template< typename type >
- result_type
- operator () (type const & _value) const
- {
- return derivator_.derive_statement(_value);
- }
- private :
- derivator & derivator_;
- } const derive_statement_;
- typename derivator_of_statement::result_type
- derive_statement(ast::empty const &)
- {
- throw std::runtime_error("empty statement not allowed");
- }
- typename derivator_of_statement::result_type
- derive_statement(ast::statement const & _statement)
- {
- return _statement.apply_visitor(derive_statement_);
- }
- typename derivator_of_statement::result_type
- derive_statement(ast::variable_declaration const & _variable_declaration)
- {
- ast::variable_declaration variable_declaration_;
- variable_declaration_.lhs_.lvalues_ = derive_lvalues(_variable_declaration.lhs_.lvalues_);
- variable_declaration_.rhs_.rvalues_ = derive_rvalues(_variable_declaration.rhs_.rvalues_);
- return std::move(variable_declaration_);
- }
- typename derivator_of_statement::result_type
- derive_statement(ast::return_statement const & _return_statement)
- {
- ast::return_statement return_statement_;
- for (ast::rvalue const & rvalue_ : _return_statement.return_value_.rvalues_) { // piecewise
- return_statement_.return_value_.rvalues_.push_back(derive_operand(rvalue_));
- }
- return std::move(return_statement_);
- }
- typename derivator_of_statement::result_type
- derive_statement(ast::assignment const &)
- {
- throw std::runtime_error("can't infer a simple analitycal representation for the derivative of an assignment statement");
- }
- typename derivator_of_statement::result_type
- derive_statement(ast::statement_block const & _statement_block)
- {
- return ast::statement_block{derive_statements(_statement_block.statements_)};
- }
- ast::statements
- derive_statements(ast::statements const & _statements)
- {
- size_type const frame_used_ = local_variables_.size();
- ast::statements statements_;
- for (ast::statement const & statement_ : _statements) {
- statements_.push_back(derive_statement(statement_));
- }
- assert(!(local_variables_.size() < frame_used_));
- while (frame_used_ < local_variables_.size()) {
- local_variables_.pop_back();
- }
- return statements_;
- }
- struct derivator_of_expression
- {
- using result_type = ast::operand;
- derivator_of_expression(derivator & _derivator)
- : derivator_(_derivator)
- { ; }
- template< typename type >
- result_type
- operator () (type const & _value) const
- {
- return derivator_.derive_expression(_value);
- }
- private :
- derivator & derivator_;
- } const derive_expression_;
- typename derivator_of_expression::result_type
- derive_operand(ast::operand const & _operand)
- {
- return _operand.apply_visitor(derive_expression_);
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::empty const &)
- {
- throw std::runtime_error("empty expression cannot be derived");
- }
- typename derivator_of_expression::result_type
- derive_expression(G const &)
- {
- return ast::constant::zero;
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::constant const &)
- {
- return ast::constant::zero;
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::intrinsic_invocation const & _intrinsic_invocation)
- {
- ast::rvalues darguments_;
- for (ast::rvalue const & rvalue_ : _intrinsic_invocation.argument_list_.rvalues_) { // piecewise
- darguments_.push_back(derive_operand(rvalue_));
- }
- return ast::rvalue_list{derive_intrinsic_(_intrinsic_invocation.intrinsic_, _intrinsic_invocation.argument_list_.rvalues_, std::move(darguments_))};
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::entry_substitution const & _entry_substitution)
- {
- ast::entry_substitution entry_substitution_;
- entry_substitution_.entry_name_ = _entry_substitution.entry_name_;
- entry_substitution_.entry_name_.derive(external_context_.wrt());
- callies_.push_back(entry_substitution_.entry_name_);
- if (!_entry_substitution.argument_list_.rvalues_.empty()) {
- context context_(entry_substitution_.entry_name_.wrts_);
- entry_substitution_.argument_list_.rvalues_ = derive_rvalues(_entry_substitution.argument_list_.rvalues_, context_);
- }
- return entry_substitution_;
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::identifier const & _identifier)
- {
- ast::symbol const & wrt_ = external_context_.wrt();
- auto const lrend = std::crend(local_variables_);
- if (std::find(std::crbegin(local_variables_), lrend, _identifier.symbol_) != lrend) {
- ast::identifier identifier_ = _identifier;
- identifier_.derive(wrt_);
- return std::move(identifier_);
- } else {
- assert(_identifier.is_original());
- if (_identifier.symbol_ == wrt_) {
- return ast::constant::one;
- } else {
- return ast::constant::zero;
- }
- }
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::unary_expression const & _unary_expression)
- {
- switch (_unary_expression.operator_) {
- case ast::unary::plus : {
- return derive_operand(_unary_expression.operand_);
- }
- case ast::unary::minus : {
- return ast::unary_expression{ast::unary::minus, derive_operand(_unary_expression.operand_)};
- }
- }
- }
- typename derivator_of_expression::result_type
- derive_binary(ast::operand_cref const & _lhs,
- ast::operand && _dlhs,
- ast::binary const _operator,
- ast::operand_cref const & _rhs,
- ast::operand && _drhs) const
- {
- using B = ast::binary_expression;
- using I = ast::intrinsic_invocation;
- switch (_operator) {
- case ast::binary::add : {
- return B{std::move(_dlhs), ast::binary::add, std::move(_drhs)};
- }
- case ast::binary::sub : {
- return B{std::move(_dlhs), ast::binary::sub, std::move(_drhs)};
- }
- case ast::binary::mul : {
- return B{B{std::move(_dlhs), ast::binary::mul, _rhs}, ast::binary::add, B{_lhs, ast::binary::mul, std::move(_drhs)}};
- }
- case ast::binary::div : {
- return B{B{std::move(_dlhs), ast::binary::div, _rhs}, ast::binary::sub, B{B{_lhs, ast::binary::mul, std::move(_drhs)}, ast::binary::div, I{ast::intrinsic::sqr, ast::make_rvalue_list(_rhs)}}};
- }
- case ast::binary::mod : { // http://math.stackexchange.com/questions/672610/
- return B{std::move(_dlhs), ast::binary::sub, B{std::move(_drhs), ast::binary::mul, I{ast::intrinsic::trunc, ast::make_rvalue_list(B{_lhs, ast::binary::div, _rhs})}}};
- }
- case ast::binary::pow : { // functional power rule
- return B{B{_lhs, ast::binary::pow, _rhs}, ast::binary::mul, B{B{std::move(_dlhs), ast::binary::mul, B{_rhs, ast::binary::div, _lhs}}, ast::binary::add, B{std::move(_drhs), ast::binary::mul, I{ast::intrinsic::ln, ast::make_rvalue_list(_lhs)}}}};
- }
- }
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::expression const & _expression)
- {
- if (_expression.rest_.empty()) {
- return derive_operand(_expression.first_);
- } else if (_expression.rest_.size() == 1) {
- ast::operation const & rhs_ = _expression.rest_.back();
- return derive_binary(std::cref(_expression.first_),
- derive_operand(_expression.first_),
- rhs_.operator_,
- std::cref(rhs_.operand_),
- derive_operand(rhs_.operand_));
- } else {
- throw std::logic_error("transform to binary tree first");
- }
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::binary_expression const & _binary_expression)
- {
- return derive_binary(std::cref(_binary_expression.lhs_),
- derive_operand(_binary_expression.lhs_),
- _binary_expression.operator_,
- std::cref(_binary_expression.rhs_),
- derive_operand(_binary_expression.rhs_));
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::rvalue_list const & _rvalue_list)
- {
- ast::rvalue_list rvalue_list_;
- for (ast::rvalue const & rvalue_ : _rvalue_list.rvalues_) {
- rvalue_list_.rvalues_.push_back(derive_operand(rvalue_));
- }
- return std::move(rvalue_list_);
- }
- typename derivator_of_expression::result_type
- derive_expression(ast::operand_cref const & _operand_cref)
- {
- return derive_operand(_operand_cref.get());
- }
- derivator_of_intrinsic const derive_intrinsic_;
- public :
- struct incremental
- {
- incremental(derivator & _derivator)
- : derivator_(_derivator)
- { ; }
- void
- enter()
- {
- assert(derivatives_.empty());
- }
- boolean_type
- push(ast::program const & _primitive, ast::symbol const & _wrt)
- {
- if (derivator_.external_context_.wrts_.empty()) {
- ancestors_.emplace(_primitive);
- } else {
- ancestors_.emplace(derivatives_.back());
- }
- derivator_.external_context_.push(_wrt);
- derivatives_.emplace_back();
- return true;
- }
- boolean_type
- append(ast::symbol const & _wrt)
- {
- derivator_.external_context_.pop();
- derivator_.external_context_.push(_wrt);
- derivatives_.emplace_back();
- return true;
- }
- void
- pop()
- {
- derivator_.external_context_.pop();
- assert(!ancestors_.empty());
- ancestors_.pop();
- }
- template< typename filter >
- boolean_type
- derive(filter && _filter)
- {
- ast::entries & entries_ = derivatives_.back().entries_;
- for (ast::entry_definition const & entry_definition_ : ancestors_.top().get().entries_) {
- try {
- entries_.push_back(std::forward< filter >(_filter)(derivator_.derive_function(entry_definition_)));
- } catch (std::exception const &) {
- derivator_.callies_.clear();
- throw;
- }
- derivator_.callies_.clear();
- }
- return true;
- }
- ast::program
- leave()
- {
- ast::program result_;
- for (ast::program & derivative_ : derivatives_) {
- result_.entries_.splice(std::cend(result_.entries_), std::move(derivative_.entries_));
- }
- derivatives_.clear();
- assert(ancestors_.empty());
- return result_;
- }
- private :
- derivator & derivator_;
- using program_cref = std::reference_wrapper< ast::program const >;
- std::deque< ast::program > derivatives_;
- std::stack< program_cref const > ancestors_;
- };
- struct dependent_recursive
- {
- dependent_recursive(derivator & _derivator)
- : derivator_(_derivator)
- { ; }
- ast::program derivatives_;
- private :
- derivator & derivator_;
- struct is_function_name
- {
- boolean_type
- operator () (ast::entry_definition const & _entry_definition) const
- {
- return (symbol_ == _entry_definition.entry_name_.symbol_) && (wrts_ == _entry_definition.entry_name_.wrts_);
- }
- ast::symbol const & symbol_;
- ast::symbols const & wrts_;
- };
- struct empty {};
- using entry_definition_cref = std::reference_wrapper< ast::entry_definition const >;
- using entry_definition_opt_cref = std::experimental::optional< entry_definition_cref >;
- template< typename filter >
- entry_definition_opt_cref
- derive(ast::program const & _primitives, ast::symbol const & _symbol, ast::symbols && _wrts, filter && _filter)
- {
- is_function_name const is_function_name_{_symbol, _wrts};
- if (_wrts.empty()) {
- assert(derivator_.external_context_.wrts_.empty());
- for (ast::entry_definition const & primitive_ : _primitives.entries_) {
- if (is_function_name_(primitive_)) {
- return std::cref(primitive_);
- }
- }
- return {};
- }
- for (ast::entry_definition const & primitive_ : reverse(derivatives_.entries_)) {
- if (is_function_name_(primitive_)) {
- derivator_.external_context_.push(primitive_.entry_name_.wrts_);
- return std::cref(primitive_);
- }
- }
- ast::symbol wrt_ = std::move(_wrts.back());
- _wrts.pop_back();
- context context_ = std::move(derivator_.external_context_);
- entry_definition_opt_cref const primitive_ = derive(_primitives, _symbol, std::move(_wrts), std::forward< filter >(_filter));
- derivator_.external_context_ = std::move(context_);
- if (!primitive_) {
- return {};
- }
- derivator_.external_context_.push(std::move(wrt_));
- ast::entry_definition derivative_ = std::forward< filter >(_filter)(derivator_.derive_function(*primitive_));
- { // callies first
- context_ = std::move(derivator_.external_context_);
- auto callies_ = std::move(derivator_.callies_);
- for (ast::identifier & callee_ : callies_) {
- entry_definition_opt_cref const derivative_ = derive(_primitives, callee_.symbol_, ast::symbols(callee_.wrts_), std::forward< filter >(_filter));
- derivator_.external_context_.clear();
- if (!derivative_) {
- return {};
- }
- }
- derivator_.external_context_ = std::move(context_);
- }
- derivatives_.entries_.push_back(std::move(derivative_));
- return std::cref(derivatives_.entries_.back());
- }
- public :
- template< typename filter >
- boolean_type
- operator () (ast::program const & _primitives, ast::symbols const & _symbols, ast::symbols const & _wrts, filter && _filter)
- {
- assert(derivatives_.entries_.empty());
- for (ast::symbol const & symbol_ : _symbols) {
- entry_definition_opt_cref const derivative_ = derive(_primitives, symbol_, ast::symbols(_wrts), std::forward< filter >(_filter));
- derivator_.external_context_.clear();
- if (!derivative_) {
- return false;
- }
- }
- return true;
- }
- };
- void
- clear()
- {
- external_context_.clear();
- local_variables_.clear();
- callies_.clear();
- }
- };
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment