A Hugo incarnation of the blog.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

type.cpp 5.3KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187
  1. #include "type.hpp"
  2. #include <ostream>
  3. #include <sstream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include "error.hpp"
  7. void type_scheme::print(const type_mgr& mgr, std::ostream& to) const {
  8. if(forall.size() != 0) {
  9. to << "forall ";
  10. for(auto& var : forall) {
  11. to << var << " ";
  12. }
  13. to << ". ";
  14. }
  15. monotype->print(mgr, to);
  16. }
  17. type_ptr type_scheme::instantiate(type_mgr& mgr) const {
  18. if(forall.size() == 0) return monotype;
  19. std::map<std::string, type_ptr> subst;
  20. for(auto& var : forall) {
  21. subst[var] = mgr.new_type();
  22. }
  23. return mgr.substitute(subst, monotype);
  24. }
  25. void type_var::print(const type_mgr& mgr, std::ostream& to) const {
  26. auto it = mgr.types.find(name);
  27. if(it != mgr.types.end()) {
  28. it->second->print(mgr, to);
  29. } else {
  30. to << name;
  31. }
  32. }
  33. void type_base::print(const type_mgr& mgr, std::ostream& to) const {
  34. to << name;
  35. }
  36. void type_arr::print(const type_mgr& mgr, std::ostream& to) const {
  37. left->print(mgr, to);
  38. to << " -> (";
  39. right->print(mgr, to);
  40. to << ")";
  41. }
  42. void type_app::print(const type_mgr& mgr, std::ostream& to) const {
  43. constructor->print(mgr, to);
  44. to << "* ";
  45. for(auto& arg : arguments) {
  46. to << " ";
  47. arg->print(mgr, to);
  48. }
  49. }
  50. std::string type_mgr::new_type_name() {
  51. int temp = last_id++;
  52. std::string str = "";
  53. while(temp != -1) {
  54. str += (char) ('a' + (temp % 26));
  55. temp = temp / 26 - 1;
  56. }
  57. std::reverse(str.begin(), str.end());
  58. return str;
  59. }
  60. type_ptr type_mgr::new_type() {
  61. return type_ptr(new type_var(new_type_name()));
  62. }
  63. type_ptr type_mgr::new_arrow_type() {
  64. return type_ptr(new type_arr(new_type(), new_type()));
  65. }
  66. type_ptr type_mgr::resolve(type_ptr t, type_var*& var) const {
  67. type_var* cast;
  68. var = nullptr;
  69. while((cast = dynamic_cast<type_var*>(t.get()))) {
  70. auto it = types.find(cast->name);
  71. if(it == types.end()) {
  72. var = cast;
  73. break;
  74. }
  75. t = it->second;
  76. }
  77. return t;
  78. }
  79. void type_mgr::unify(type_ptr l, type_ptr r) {
  80. type_var *lvar, *rvar;
  81. type_arr *larr, *rarr;
  82. type_base *lid, *rid;
  83. type_app *lapp, *rapp;
  84. l = resolve(l, lvar);
  85. r = resolve(r, rvar);
  86. if(lvar) {
  87. bind(lvar->name, r);
  88. return;
  89. } else if(rvar) {
  90. bind(rvar->name, l);
  91. return;
  92. } else if((larr = dynamic_cast<type_arr*>(l.get())) &&
  93. (rarr = dynamic_cast<type_arr*>(r.get()))) {
  94. unify(larr->left, rarr->left);
  95. unify(larr->right, rarr->right);
  96. return;
  97. } else if((lid = dynamic_cast<type_base*>(l.get())) &&
  98. (rid = dynamic_cast<type_base*>(r.get()))) {
  99. if(lid->name == rid->name && lid->arity == rid->arity) return;
  100. } else if((lapp = dynamic_cast<type_app*>(l.get())) &&
  101. (rapp = dynamic_cast<type_app*>(r.get()))) {
  102. unify(lapp->constructor, rapp->constructor);
  103. auto left_it = lapp->arguments.begin();
  104. auto right_it = rapp->arguments.begin();
  105. while(left_it != lapp->arguments.end() &&
  106. right_it != rapp->arguments.end()) {
  107. unify(*left_it, *right_it);
  108. left_it++, right_it++;
  109. }
  110. return;
  111. }
  112. throw unification_error(l, r);
  113. }
  114. type_ptr type_mgr::substitute(const std::map<std::string, type_ptr>& subst, const type_ptr& t) const {
  115. type_ptr temp = t;
  116. while(type_var* var = dynamic_cast<type_var*>(temp.get())) {
  117. auto subst_it = subst.find(var->name);
  118. if(subst_it != subst.end()) return subst_it->second;
  119. auto var_it = types.find(var->name);
  120. if(var_it == types.end()) return t;
  121. temp = var_it->second;
  122. }
  123. if(type_arr* arr = dynamic_cast<type_arr*>(temp.get())) {
  124. auto left_result = substitute(subst, arr->left);
  125. auto right_result = substitute(subst, arr->right);
  126. if(left_result == arr->left && right_result == arr->right) return t;
  127. return type_ptr(new type_arr(left_result, right_result));
  128. } else if(type_app* app = dynamic_cast<type_app*>(temp.get())) {
  129. auto constructor_result = substitute(subst, app->constructor);
  130. bool arg_changed = false;
  131. std::vector<type_ptr> new_args;
  132. for(auto& arg : app->arguments) {
  133. auto arg_result = substitute(subst, arg);
  134. arg_changed |= arg_result != arg;
  135. new_args.push_back(std::move(arg_result));
  136. }
  137. if(constructor_result == app->constructor && !arg_changed) return t;
  138. type_app* new_app = new type_app(std::move(constructor_result));
  139. std::swap(new_app->arguments, new_args);
  140. return type_ptr(new_app);
  141. }
  142. return t;
  143. }
  144. void type_mgr::bind(const std::string& s, type_ptr t) {
  145. type_var* other = dynamic_cast<type_var*>(t.get());
  146. if(other && other->name == s) return;
  147. types[s] = t;
  148. }
  149. void type_mgr::find_free(const type_ptr& t, std::set<std::string>& into) const {
  150. type_var* var;
  151. type_ptr resolved = resolve(t, var);
  152. if(var) {
  153. into.insert(var->name);
  154. } else if(type_arr* arr = dynamic_cast<type_arr*>(resolved.get())) {
  155. find_free(arr->left, into);
  156. find_free(arr->right, into);
  157. } else if(type_app* app = dynamic_cast<type_app*>(resolved.get())) {
  158. find_free(app->constructor, into);
  159. for(auto& arg : app->arguments) find_free(arg, into);
  160. }
  161. }