diff options
Diffstat (limited to 'example/turing/src')
| -rw-r--r-- | example/turing/src/machine.h | 98 | ||||
| -rw-r--r-- | example/turing/src/state.h | 64 | ||||
| -rw-r--r-- | example/turing/src/tape.h | 46 |
3 files changed, 208 insertions, 0 deletions
diff --git a/example/turing/src/machine.h b/example/turing/src/machine.h new file mode 100644 index 0000000..2404d9a --- /dev/null +++ b/example/turing/src/machine.h @@ -0,0 +1,98 @@ +#ifndef TYPEASVALUE_EXAMPLE_TURING_MACHINE_H_ +#define TYPEASVALUE_EXAMPLE_TURING_MACHINE_H_ + +#include "conditional/cond.h" + +#include "state.h" +#include "tape.h" + +namespace machine { + +// (define (simulate transition tape state position) +// (if (= state FINAL) +// tape +// (let* ((current_symbol (readSymbol position tape)) +// (current_state (transition state current_symbol)) +// (direction (nth MOVE current_state)) +// (next_symbol (nth WRITE current_state)) +// (next_state (nth NEXT current_state)) +// (next_position (cond ((= direction RIGHT) (+ position 1)) +// ((= direction LEFT) (- Position 1)) +// (else position)))) +// (simulate transition +// (writeSymbol position next_symbol tape) +// next_state, +// next_position))) +template < + template<typename, typename> class Transition, + typename State, + typename Tape, + typename Position +> +class simulate { + private: + using current_symbol = tape::readSymbol<Position, Tape>; + using current_state = Transition<State, current_symbol>; + + using direction = tav::Nth<state::field::MOVE, current_state>; + + using next_symbol = tav::Nth<state::field::WRITE, current_state>; + using next_state = tav::Nth<state::field::NEXT, current_state>; + using next_position = tav::Cond< + tav::Branch< + tav::IsEqualValue<direction, tav::Char<'R'>>, + tav::Add<Position, tav::Size<1>> + >, + tav::Branch< + tav::IsEqualValue<direction, tav::Char<'L'>>, + tav::Substract<Position, tav::Size<1>> + >, + tav::Else< + Position + > + >; + + static_assert( + tav::Not<tav::LowerThan<next_position, tav::Size<0>>>::value, + "next position out of bounds" + ); + + public: + using type = tav::Eval<simulate< + Transition, + next_state, + tape::writeSymbol<Position, next_symbol, Tape>, + next_position + >>; +}; + +template < + template<typename, typename> class Transition, + typename Tape, + typename Position +> +struct simulate<Transition, void, Tape, Position> { + typedef Tape type; +}; + +// (define (run program state tape position) +// (simulate (transition program) +// tape +// state +// position)) +template < + typename Program, + typename State, + typename Tape, + typename Position +> +using run = tav::Eval<simulate< + state::transition<Program>::template state, + State, + Tape, + Position +>>; + +} + +#endif // TYPEASVALUE_EXAMPLE_TURING_MACHINE_H_ diff --git a/example/turing/src/state.h b/example/turing/src/state.h new file mode 100644 index 0000000..f5bd7f2 --- /dev/null +++ b/example/turing/src/state.h @@ -0,0 +1,64 @@ +#ifndef TYPEASVALUE_EXAMPLE_TURING_SRC_STATE_H_ +#define TYPEASVALUE_EXAMPLE_TURING_SRC_STATE_H_ + +#include "type.h" +#include "list/list.h" +#include "list/operation/higher/find.h" + +namespace machine { + +namespace state { + +struct field { + using ID = tav::Size<0>; + using READ = tav::Size<1>; + using WRITE = tav::Size<2>; + using NEXT = tav::Size<3>; + using MOVE = tav::Size<4>; +}; + +// (define (state_predicate id read) +// (lambda (state) +// (and (= id (nth ID state)) +// (= read (nth READ state))))) +template < + typename Id, + typename Read +> +struct state_predicate { + template <typename State> + using function = tav::And< + tav::IsEqualValue<Id, tav::Nth<field::ID, State>>, + tav::IsEqualValue<Read, tav::Nth<field::READ, State>> + >; +}; + +// (define (findState id read states) +// (find (state_predicate id read) states)) +template < + typename Id, + typename Read, + typename States +> +using findState = tav::Find< + state_predicate<Id, Read>::template function, + States +>; + +// (define (transition states) +// (lambda (state symbol) +// (findState state symbol states))) +template <typename States> +struct transition { + template < + typename State, + typename Symbol + > + using state = findState<State, Symbol, States>; +}; + +} + +} + +#endif // TYPEASVALUE_EXAMPLE_TURING_SRC_STATE_H_ diff --git a/example/turing/src/tape.h b/example/turing/src/tape.h new file mode 100644 index 0000000..39814d8 --- /dev/null +++ b/example/turing/src/tape.h @@ -0,0 +1,46 @@ +#ifndef TYPEASVALUE_EXAMPLE_TURING_SRC_TAPE_H_ +#define TYPEASVALUE_EXAMPLE_TURING_SRC_TAPE_H_ + +#include "type.h" +#include "list/list.h" +#include "list/operation/replace_nth.h" +#include "conditional/if.h" + +namespace machine { + +namespace tape { + +// (define (readSymbol position tape) +// (if (= (length tape) position) +// '() +// (nth position tape))) +template < + typename Position, + typename Tape +> +using readSymbol = tav::If< + tav::IsEqualValue<tav::Length<Tape>, Position>, + void, + tav::Nth<Position, Tape> +>; + +// (define (writeSymbol position symbol tape) +// (if (= (length tape) position) +// (append tape (list symbol)) +// (replace-nth position symbol tape))) +template < + typename Position, + typename Symbol, + typename Tape +> +using writeSymbol = tav::If< + tav::IsEqualValue<tav::Length<Tape>, Position>, + tav::Append<Tape, tav::List<Symbol>>, + tav::ReplaceNth<Position, Symbol, Tape> +>; + +} + +} + +#endif // TYPEASVALUE_EXAMPLE_TURING_SRC_TAPE_H_ |