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.4KB

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