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 6.3KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213
  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 type = mgr.lookup(name);
  27. if(type) {
  28. type->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. type_var* var;
  38. bool print_parenths = dynamic_cast<type_arr*>(mgr.resolve(left, var).get()) != nullptr;
  39. if(print_parenths) to << "(";
  40. left->print(mgr, to);
  41. if(print_parenths) to << ")";
  42. to << " -> ";
  43. right->print(mgr, to);
  44. }
  45. void type_app::print(const type_mgr& mgr, std::ostream& to) const {
  46. constructor->print(mgr, to);
  47. to << "*";
  48. for(auto& arg : arguments) {
  49. to << " ";
  50. arg->print(mgr, to);
  51. }
  52. }
  53. std::string type_mgr::new_type_name() {
  54. int temp = last_id++;
  55. std::string str = "";
  56. while(temp != -1) {
  57. str += (char) ('a' + (temp % 26));
  58. temp = temp / 26 - 1;
  59. }
  60. std::reverse(str.begin(), str.end());
  61. return str;
  62. }
  63. type_ptr type_mgr::new_type() {
  64. return type_ptr(new type_var(new_type_name()));
  65. }
  66. type_ptr type_mgr::new_arrow_type() {
  67. return type_ptr(new type_arr(new_type(), new_type()));
  68. }
  69. type_ptr type_mgr::lookup(const std::string& var) const {
  70. auto types_it = types.find(var);
  71. if(types_it != types.end()) return types_it->second;
  72. return nullptr;
  73. }
  74. type_ptr type_mgr::resolve(type_ptr t, type_var*& var) const {
  75. type_var* cast;
  76. var = nullptr;
  77. while((cast = dynamic_cast<type_var*>(t.get()))) {
  78. auto it = types.find(cast->name);
  79. if(it == types.end()) {
  80. var = cast;
  81. break;
  82. }
  83. t = it->second;
  84. }
  85. return t;
  86. }
  87. void type_mgr::unify(type_ptr l, type_ptr r, const std::optional<yy::location>& loc) {
  88. type_var *lvar, *rvar;
  89. type_arr *larr, *rarr;
  90. type_base *lid, *rid;
  91. type_app *lapp, *rapp;
  92. l = resolve(l, lvar);
  93. r = resolve(r, rvar);
  94. if(lvar) {
  95. bind(lvar->name, r);
  96. return;
  97. } else if(rvar) {
  98. bind(rvar->name, l);
  99. return;
  100. } else if((larr = dynamic_cast<type_arr*>(l.get())) &&
  101. (rarr = dynamic_cast<type_arr*>(r.get()))) {
  102. unify(larr->left, rarr->left, loc);
  103. unify(larr->right, rarr->right, loc);
  104. return;
  105. } else if((lid = dynamic_cast<type_base*>(l.get())) &&
  106. (rid = dynamic_cast<type_base*>(r.get()))) {
  107. if(lid->name == rid->name &&
  108. lid->arity == rid->arity)
  109. return;
  110. } else if((lapp = dynamic_cast<type_app*>(l.get())) &&
  111. (rapp = dynamic_cast<type_app*>(r.get()))) {
  112. unify(lapp->constructor, rapp->constructor, loc);
  113. auto left_it = lapp->arguments.begin();
  114. auto right_it = rapp->arguments.begin();
  115. while(left_it != lapp->arguments.end() &&
  116. right_it != rapp->arguments.end()) {
  117. unify(*left_it, *right_it, loc);
  118. left_it++, right_it++;
  119. }
  120. return;
  121. }
  122. throw unification_error(l, r, loc);
  123. }
  124. type_ptr type_mgr::substitute(const std::map<std::string, type_ptr>& subst, const type_ptr& t) const {
  125. type_ptr temp = t;
  126. while(type_var* var = dynamic_cast<type_var*>(temp.get())) {
  127. auto subst_it = subst.find(var->name);
  128. if(subst_it != subst.end()) return subst_it->second;
  129. auto var_it = types.find(var->name);
  130. if(var_it == types.end()) return t;
  131. temp = var_it->second;
  132. }
  133. if(type_arr* arr = dynamic_cast<type_arr*>(temp.get())) {
  134. auto left_result = substitute(subst, arr->left);
  135. auto right_result = substitute(subst, arr->right);
  136. if(left_result == arr->left && right_result == arr->right) return t;
  137. return type_ptr(new type_arr(left_result, right_result));
  138. } else if(type_app* app = dynamic_cast<type_app*>(temp.get())) {
  139. auto constructor_result = substitute(subst, app->constructor);
  140. bool arg_changed = false;
  141. std::vector<type_ptr> new_args;
  142. for(auto& arg : app->arguments) {
  143. auto arg_result = substitute(subst, arg);
  144. arg_changed |= arg_result != arg;
  145. new_args.push_back(std::move(arg_result));
  146. }
  147. if(constructor_result == app->constructor && !arg_changed) return t;
  148. type_app* new_app = new type_app(std::move(constructor_result));
  149. std::swap(new_app->arguments, new_args);
  150. return type_ptr(new_app);
  151. }
  152. return t;
  153. }
  154. void type_mgr::bind(const std::string& s, type_ptr t) {
  155. type_var* other = dynamic_cast<type_var*>(t.get());
  156. if(other && other->name == s) return;
  157. types[s] = t;
  158. }
  159. void type_mgr::find_free(const type_ptr& t, std::set<std::string>& into) const {
  160. type_var* var;
  161. type_ptr resolved = resolve(t, var);
  162. if(var) {
  163. into.insert(var->name);
  164. } else if(type_arr* arr = dynamic_cast<type_arr*>(resolved.get())) {
  165. find_free(arr->left, into);
  166. find_free(arr->right, into);
  167. } else if(type_app* app = dynamic_cast<type_app*>(resolved.get())) {
  168. find_free(app->constructor, into);
  169. for(auto& arg : app->arguments) find_free(arg, into);
  170. }
  171. }
  172. void type_mgr::find_free(const type_scheme_ptr& t, std::set<std::string>& into) const {
  173. std::set<std::string> monotype_free;
  174. type_mgr limited_mgr;
  175. for(auto& binding : types) {
  176. auto existing_position = std::find(t->forall.begin(), t->forall.end(), binding.first);
  177. if(existing_position != t->forall.end()) continue;
  178. limited_mgr.types[binding.first] = binding.second;
  179. }
  180. limited_mgr.find_free(t->monotype, monotype_free);
  181. for(auto& not_free : t->forall) {
  182. monotype_free.erase(not_free);
  183. }
  184. into.insert(monotype_free.begin(), monotype_free.end());
  185. }