fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <memory>
  3. #include <utility>
  4.  
  5. enum class Type {
  6.   integer,
  7.   promise,
  8. };
  9.  
  10. struct Object;
  11.  
  12. class ObjectBody {
  13.  public:
  14.   virtual ~ObjectBody() {}
  15.  
  16.   virtual std::shared_ptr<Object> force() {
  17.     return nullptr;
  18.   }
  19.   virtual void dump() {}
  20.   virtual int get_int() {
  21.     return 0;
  22.   }
  23. };
  24.  
  25. struct Object {
  26.   Type type;
  27.   std::unique_ptr<ObjectBody> body;
  28.  
  29.   template <typename T>
  30.   Object(Type type, T&& body) : type(type), body(std::forward<T>(body)) {
  31.     return;
  32.   }
  33.  
  34.   bool evaluated() {
  35.     return type != Type::promise;
  36.   }
  37.  
  38.   auto force() {
  39.     return body->force();
  40.   }
  41.  
  42.   auto get_int() {
  43.     return body->get_int();
  44.   }
  45.  
  46.   bool dump() {
  47.     body->dump();
  48.     return false;
  49.   }
  50. };
  51.  
  52. class Integer : public ObjectBody {
  53.   int value;
  54.  
  55.  public:
  56.   Integer(int v) : value(v) {
  57.     return;
  58.   }
  59.  
  60.   ~Integer() override {
  61.     return;
  62.   }
  63.  
  64.   void dump() override {
  65.     printf("%d", value);
  66.     return;
  67.   }
  68.  
  69.   int get_int() override {
  70.     return value;
  71.   }
  72.  
  73.   static auto make(int v) {
  74.     return std::make_shared<Object>(Type::integer, std::make_unique<Integer>(v));
  75.   }
  76. };
  77.  
  78. class Promise : public ObjectBody {};
  79.  
  80. template <typename T>
  81. constexpr bool is_int = std::is_same<int, std::remove_cv_t<std::remove_reference_t<T>>>::value;
  82.  
  83. class Ackermann : public Promise {
  84.   std::shared_ptr<Object> m, n;
  85.  
  86.   template <typename M, typename N, std::enable_if_t<!is_int<M> && !is_int<N>>* = nullptr>
  87.   static auto make(M&& m, N&& n) {
  88.     return std::make_shared<Object>(Type::promise, std::make_unique<Ackermann>(std::forward<M>(m), std::forward<N>(n)));
  89.   }
  90.  
  91.   template <typename M, typename N, std::enable_if_t<!is_int<M> && is_int<N>>* = nullptr>
  92.   static auto make(M&& m, N&& n) {
  93.     return std::make_shared<Object>(Type::promise, std::make_unique<Ackermann>(std::forward<M>(m), Integer::make(n)));
  94.   }
  95.  
  96.   template <typename M, typename N, std::enable_if_t<is_int<M> && !is_int<N>>* = nullptr>
  97.   static auto make(M&& m, N&& n) {
  98.     return std::make_shared<Object>(Type::promise, std::make_unique<Ackermann>(Integer::make(m), std::forward<N>(n)));
  99.   }
  100.  
  101.   template <typename M, typename N, std::enable_if_t<is_int<M> && is_int<N>>* = nullptr>
  102.   static auto make(M&& m, N&& n) {
  103.     return std::make_shared<Object>(Type::promise, std::make_unique<Ackermann>(Integer::make(m), Integer::make(n)));
  104.   }
  105.  
  106.  public:
  107.   template <typename M, typename N>
  108.   Ackermann(M&& m_, N&& n_) : m(std::forward<M>(m_)), n(std::forward<N>(n_)) {
  109.     return;
  110.   }
  111.  
  112.   ~Ackermann() override {
  113.     return;
  114.   }
  115.  
  116.   std::shared_ptr<Object> force() override {
  117.     if (!m->evaluated()) {
  118.       return Ackermann::make(m->force(), n);
  119.     } else if (!n->evaluated()) {
  120.       return Ackermann::make(m, n->force());
  121.     } else {
  122.       auto &&mi = m->get_int(), &&ni = n->get_int();
  123.       if (mi == 0) {
  124.         return Integer::make(ni + 1);
  125.       } else if (ni == 0) {
  126.         return Ackermann::make(mi - 1, 1);
  127.       } else {
  128.         return Ackermann::make(mi - 1, Ackermann::make(mi, ni - 1));
  129.       }
  130.     }
  131.   }
  132.  
  133.   void dump() override {
  134.     printf("ack(");
  135.     m->dump();
  136.     printf(", ");
  137.     n->dump();
  138.     printf(")");
  139.     return;
  140.   }
  141.  
  142.   static auto make_continuation(int m, int n) {
  143.     return Ackermann::make(m, n);
  144.   }
  145. };
  146.  
  147. int main() {
  148.   for (auto cont = Ackermann::make_continuation(2, 2); !cont->evaluated() || cont->dump(); cont = cont->force()) {
  149.     cont->dump();
  150.     puts("");
  151.   }
  152.   puts("");
  153.   return 0;
  154. }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ack(2, 2)
ack(1, ack(2, 1))
ack(1, ack(1, ack(2, 0)))
ack(1, ack(1, ack(1, 1)))
ack(1, ack(1, ack(0, ack(1, 0))))
ack(1, ack(1, ack(0, ack(0, 1))))
ack(1, ack(1, ack(0, 2)))
ack(1, ack(1, 3))
ack(1, ack(0, ack(1, 2)))
ack(1, ack(0, ack(0, ack(1, 1))))
ack(1, ack(0, ack(0, ack(0, ack(1, 0)))))
ack(1, ack(0, ack(0, ack(0, ack(0, 1)))))
ack(1, ack(0, ack(0, ack(0, 2))))
ack(1, ack(0, ack(0, 3)))
ack(1, ack(0, 4))
ack(1, 5)
ack(0, ack(1, 4))
ack(0, ack(0, ack(1, 3)))
ack(0, ack(0, ack(0, ack(1, 2))))
ack(0, ack(0, ack(0, ack(0, ack(1, 1)))))
ack(0, ack(0, ack(0, ack(0, ack(0, ack(1, 0))))))
ack(0, ack(0, ack(0, ack(0, ack(0, ack(0, 1))))))
ack(0, ack(0, ack(0, ack(0, ack(0, 2)))))
ack(0, ack(0, ack(0, ack(0, 3))))
ack(0, ack(0, ack(0, 4)))
ack(0, ack(0, 5))
ack(0, 6)
7
https://ideone.com/BFP2wh
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!