From effddfdd69cf9e5ec700aeda2980c0210575e320 Mon Sep 17 00:00:00 2001 From: Adrian Kummerlaender Date: Sat, 21 Feb 2015 14:56:39 +0100 Subject: Implemented basic Turing machine as an example * executes and prints the _Busy Beaver_ and _Mirror_ state transitions * this example demonstrates how one may use _TypeAsValue_ to simplify and augment normal statically recursive template metaprograms where it makes sense --- example/turing/CMakeLists.txt | 16 +++ example/turing/turing.cc | 257 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 273 insertions(+) create mode 100644 example/turing/CMakeLists.txt create mode 100644 example/turing/turing.cc diff --git a/example/turing/CMakeLists.txt b/example/turing/CMakeLists.txt new file mode 100644 index 0000000..dc08ac9 --- /dev/null +++ b/example/turing/CMakeLists.txt @@ -0,0 +1,16 @@ +cmake_minimum_required(VERSION 2.8) +project(turing) + +set( + CMAKE_CXX_FLAGS + "-std=c++14 -W -Wall -Wextra -Winline -pedantic -ftemplate-depth-1024" +) + +include_directories( + ../../src/ +) + +add_executable( + turing + turing.cc +) diff --git a/example/turing/turing.cc b/example/turing/turing.cc new file mode 100644 index 0000000..e1384d8 --- /dev/null +++ b/example/turing/turing.cc @@ -0,0 +1,257 @@ +#include + +#include "type.h" +#include "operation/math.h" +#include "function/apply.h" + +#include "conditional/if.h" +#include "conditional/cond.h" + +#include "list/operation/replace_nth.h" +#include "list/operation/higher/find.h" +#include "list/generator/make_list.h" + +#include "runtime/list/for_each.h" + +struct symbol { + struct BLANK { }; +}; + +struct movement { + struct RIGHT { }; + struct LEFT { }; + struct NONE { }; +}; + +// helper for easier state access +struct state_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 + using function = tav::And< + tav::IsEqualValue>, + tav::IsEqualValue> + >; +}; + +// (define (findState id read states) +// (find (state_predicate id read) states)) +template < + typename Id, + typename Read, + typename States +> +using findState = tav::Find< + state_predicate::template function, + States +>; + +// (define (readSymbolFromTape position tape) +// (if (= (length tape) position) +// BLANK +// (nth position tape))) +template < + typename Position, + typename Tape +> +using readSymbolFromTape = tav::If< + tav::IsEqualValue, Position>, + symbol::BLANK, + tav::Nth +>; + +// (define (writeSymbolToTape position symbol tape) +// (if (= (length tape) position) +// (append tape (list symbol)) +// (replace-nth position symbol tape))) +template < + typename Position, + typename Symbol, + typename Tape +> +using writeSymbolToTape = tav::If< + tav::IsEqualValue, Position>, + tav::Append>, + tav::ReplaceNth +>; + +// (define (transition states) +// (lambda (state symbol) +// (findState state symbol states))) +template +struct transition { + template < + typename State, + typename Symbol + > + using state = findState; +}; + +// (define (simulateTuringMachine transition tape state position) +// (if (= state FINAL) +// tape +// (let* ((current_symbol (readSymbolFromTape 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)))) +// (simulateTuringMachine transition +// (writeSymbolToTape position next_symbol tape) +// next_state, +// next_position))) +template < + template class Transition, + typename Tape, + typename State, + typename Position +> +class simulateTuringMachine { + private: + using current_symbol = readSymbolFromTape; + using current_state = Transition; + + using direction = tav::Nth; + + using next_symbol = tav::Nth; + using next_state = tav::Nth; + using next_position = tav::Cond< + tav::Branch< + std::is_same, + tav::Add> + >, + tav::Branch< + std::is_same, + tav::Substract> + >, + tav::Else< + Position + > + >; + + static_assert( + tav::Not>>::value, + "next position out of bounds" + ); + + public: + using type = tav::Eval, + next_state, + next_position + >>; +}; + +template < + template class Transition, + typename Tape, + typename Position +> +struct simulateTuringMachine { + typedef Tape type; +}; + +// (define mirror (list (list 1 1 0 2 RIGHT) [...])) +using mirror = tav::List< +// [state] [read] [write] [next state] [head movement] + tav::List, tav::Int<1>, tav::Int<0>, tav::Size<2>, movement::RIGHT>, + tav::List, tav::Int<0>, tav::Int<0>, void, movement::NONE >, + tav::List, tav::Int<1>, tav::Int<1>, tav::Size<2>, movement::RIGHT>, + tav::List, tav::Int<0>, tav::Int<0>, tav::Size<3>, movement::RIGHT>, + tav::List, tav::Int<1>, tav::Int<1>, tav::Size<3>, movement::RIGHT>, + tav::List, tav::Int<0>, tav::Int<1>, tav::Size<4>, movement::LEFT >, + tav::List, tav::Int<1>, tav::Int<1>, tav::Size<4>, movement::LEFT >, + tav::List, tav::Int<0>, tav::Int<0>, tav::Size<5>, movement::LEFT >, + tav::List, tav::Int<1>, tav::Int<1>, tav::Size<5>, movement::LEFT >, + tav::List, tav::Int<0>, tav::Int<1>, tav::Size<1>, movement::RIGHT> +>; + +// (define mirror_initial_tape (list 1 1 1 0 0 0 0)) +using mirror_initial_tape = tav::ListOfType; + +// (define mirror_final_tape +// (simulateTuringMachine (transition mirror) +// mirror_initial_tape +// 1 +// 0)) +using mirror_final_tape = tav::Eval::template state, + mirror_initial_tape, + tav::Size<1>, + tav::Size<0> +>>; + +// (define busy_beaver (list (list 'A' 0 1 'B' RIGHT) [...])) +using busy_beaver = tav::List< +// [state] [read] [write] [next state] [head movement] + tav::List, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, movement::RIGHT>, + tav::List, tav::Int<1>, tav::Int<1>, tav::Char<'C'>, movement::LEFT >, + tav::List, tav::Int<0>, tav::Int<1>, tav::Char<'A'>, movement::LEFT >, + tav::List, tav::Int<1>, tav::Int<1>, tav::Char<'B'>, movement::RIGHT>, + tav::List, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, movement::LEFT >, + tav::List, tav::Int<1>, tav::Int<1>, void, movement::NONE > +>; + +// (define busy_beaver_initial_tape (make-list 13 0)) +using busy_beaver_initial_tape = tav::MakeList, tav::Int<0>>; + +// (define busy_beaver_final_tape +// (simulateTuringMachine (transition busy_beaver) +// busy_beaver_initial_tape +// 'A' +// 6)) +using busy_beaver_final_tape = tav::Eval::template state, + busy_beaver_initial_tape, + tav::Char<'A'>, + tav::Size<6> +>>; + +int main(int, char **) { + const auto printField = [](const int x) { + std::cout << x << " "; + }; + + std::cout << "1. Mirror" + << std::endl + << " Initial: "; + + tav::runtime::for_each(printField); + + std::cout << std::endl + << " Final: "; + + tav::runtime::for_each(printField); + + std::cout << std::endl + << std::endl + << "2. Busy Beaver" + << std::endl + << " Initial: "; + + tav::runtime::for_each(printField); + + std::cout << std::endl + << " Final: "; + + tav::runtime::for_each(printField); + + std::cout << std::endl; +} -- cgit v1.2.3