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.

ast.cpp 9.0KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269
  1. #include "ast.hpp"
  2. #include <ostream>
  3. #include "binop.hpp"
  4. #include "error.hpp"
  5. #include "type_env.hpp"
  6. static void print_indent(int n, std::ostream& to) {
  7. while(n--) to << " ";
  8. }
  9. void ast_int::print(int indent, std::ostream& to) const {
  10. print_indent(indent, to);
  11. to << "INT: " << value << std::endl;
  12. }
  13. void ast_int::find_free(type_mgr& mgr, type_env_ptr& env, std::set<std::string>& into) {
  14. this->env = env;
  15. }
  16. type_ptr ast_int::typecheck(type_mgr& mgr) {
  17. return type_ptr(new type_app(env->lookup_type("Int")));
  18. }
  19. void ast_int::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  20. into.push_back(instruction_ptr(new instruction_pushint(value)));
  21. }
  22. void ast_lid::print(int indent, std::ostream& to) const {
  23. print_indent(indent, to);
  24. to << "LID: " << id << std::endl;
  25. }
  26. void ast_lid::find_free(type_mgr& mgr, type_env_ptr& env, std::set<std::string>& into) {
  27. this->env = env;
  28. if(env->lookup(id) == nullptr) into.insert(id);
  29. }
  30. type_ptr ast_lid::typecheck(type_mgr& mgr) {
  31. return env->lookup(id)->instantiate(mgr);
  32. }
  33. void ast_lid::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  34. into.push_back(instruction_ptr(
  35. env->has_variable(id) ?
  36. (instruction*) new instruction_push(env->get_offset(id)) :
  37. (instruction*) new instruction_pushglobal(id)));
  38. }
  39. void ast_uid::print(int indent, std::ostream& to) const {
  40. print_indent(indent, to);
  41. to << "UID: " << id << std::endl;
  42. }
  43. void ast_uid::find_free(type_mgr& mgr, type_env_ptr& env, std::set<std::string>& into) {
  44. this->env = env;
  45. }
  46. type_ptr ast_uid::typecheck(type_mgr& mgr) {
  47. return env->lookup(id)->instantiate(mgr);
  48. }
  49. void ast_uid::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  50. into.push_back(instruction_ptr(new instruction_pushglobal(id)));
  51. }
  52. void ast_binop::print(int indent, std::ostream& to) const {
  53. print_indent(indent, to);
  54. to << "BINOP: " << op_name(op) << std::endl;
  55. left->print(indent + 1, to);
  56. right->print(indent + 1, to);
  57. }
  58. void ast_binop::find_free(type_mgr& mgr, type_env_ptr& env, std::set<std::string>& into) {
  59. this->env = env;
  60. left->find_free(mgr, env, into);
  61. right->find_free(mgr, env, into);
  62. }
  63. type_ptr ast_binop::typecheck(type_mgr& mgr) {
  64. type_ptr ltype = left->typecheck(mgr);
  65. type_ptr rtype = right->typecheck(mgr);
  66. type_ptr ftype = env->lookup(op_name(op))->instantiate(mgr);
  67. if(!ftype) throw type_error(std::string("unknown binary operator ") + op_name(op));
  68. type_ptr return_type = mgr.new_type();
  69. type_ptr arrow_one = type_ptr(new type_arr(rtype, return_type));
  70. type_ptr arrow_two = type_ptr(new type_arr(ltype, arrow_one));
  71. mgr.unify(arrow_two, ftype);
  72. return return_type;
  73. }
  74. void ast_binop::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  75. right->compile(env, into);
  76. left->compile(env_ptr(new env_offset(1, env)), into);
  77. into.push_back(instruction_ptr(new instruction_pushglobal(op_action(op))));
  78. into.push_back(instruction_ptr(new instruction_mkapp()));
  79. into.push_back(instruction_ptr(new instruction_mkapp()));
  80. }
  81. void ast_app::print(int indent, std::ostream& to) const {
  82. print_indent(indent, to);
  83. to << "APP:" << std::endl;
  84. left->print(indent + 1, to);
  85. right->print(indent + 1, to);
  86. }
  87. void ast_app::find_free(type_mgr& mgr, type_env_ptr& env, std::set<std::string>& into) {
  88. this->env = env;
  89. left->find_free(mgr, env, into);
  90. right->find_free(mgr, env, into);
  91. }
  92. type_ptr ast_app::typecheck(type_mgr& mgr) {
  93. type_ptr ltype = left->typecheck(mgr);
  94. type_ptr rtype = right->typecheck(mgr);
  95. type_ptr return_type = mgr.new_type();
  96. type_ptr arrow = type_ptr(new type_arr(rtype, return_type));
  97. mgr.unify(arrow, ltype);
  98. return return_type;
  99. }
  100. void ast_app::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  101. right->compile(env, into);
  102. left->compile(env_ptr(new env_offset(1, env)), into);
  103. into.push_back(instruction_ptr(new instruction_mkapp()));
  104. }
  105. void ast_case::print(int indent, std::ostream& to) const {
  106. print_indent(indent, to);
  107. to << "CASE: " << std::endl;
  108. for(auto& branch : branches) {
  109. print_indent(indent + 1, to);
  110. branch->pat->print(to);
  111. to << std::endl;
  112. branch->expr->print(indent + 2, to);
  113. }
  114. }
  115. void ast_case::find_free(type_mgr& mgr, type_env_ptr& env, std::set<std::string>& into) {
  116. this->env = env;
  117. of->find_free(mgr, env, into);
  118. for(auto& branch : branches) {
  119. type_env_ptr new_env = type_scope(env);
  120. branch->pat->insert_bindings(mgr, new_env);
  121. branch->expr->find_free(mgr, new_env, into);
  122. }
  123. }
  124. type_ptr ast_case::typecheck(type_mgr& mgr) {
  125. type_var* var;
  126. type_ptr case_type = mgr.resolve(of->typecheck(mgr), var);
  127. type_ptr branch_type = mgr.new_type();
  128. for(auto& branch : branches) {
  129. branch->pat->typecheck(case_type, mgr, branch->expr->env);
  130. type_ptr curr_branch_type = branch->expr->typecheck(mgr);
  131. mgr.unify(branch_type, curr_branch_type);
  132. }
  133. input_type = mgr.resolve(case_type, var);
  134. type_app* app_type;
  135. if(!(app_type = dynamic_cast<type_app*>(input_type.get())) ||
  136. !dynamic_cast<type_data*>(app_type->constructor.get())) {
  137. throw type_error("attempting case analysis of non-data type");
  138. }
  139. return branch_type;
  140. }
  141. void ast_case::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  142. type_app* app_type = dynamic_cast<type_app*>(input_type.get());
  143. type_data* type = dynamic_cast<type_data*>(app_type->constructor.get());
  144. of->compile(env, into);
  145. into.push_back(instruction_ptr(new instruction_eval()));
  146. instruction_jump* jump_instruction = new instruction_jump();
  147. into.push_back(instruction_ptr(jump_instruction));
  148. for(auto& branch : branches) {
  149. std::vector<instruction_ptr> branch_instructions;
  150. pattern_var* vpat;
  151. pattern_constr* cpat;
  152. if((vpat = dynamic_cast<pattern_var*>(branch->pat.get()))) {
  153. branch->expr->compile(env_ptr(new env_offset(1, env)), branch_instructions);
  154. for(auto& constr_pair : type->constructors) {
  155. if(jump_instruction->tag_mappings.find(constr_pair.second.tag) !=
  156. jump_instruction->tag_mappings.end())
  157. break;
  158. jump_instruction->tag_mappings[constr_pair.second.tag] =
  159. jump_instruction->branches.size();
  160. }
  161. jump_instruction->branches.push_back(std::move(branch_instructions));
  162. } else if((cpat = dynamic_cast<pattern_constr*>(branch->pat.get()))) {
  163. env_ptr new_env = env;
  164. for(auto it = cpat->params.rbegin(); it != cpat->params.rend(); it++) {
  165. new_env = env_ptr(new env_var(*it, new_env));
  166. }
  167. branch_instructions.push_back(instruction_ptr(new instruction_split(
  168. cpat->params.size())));
  169. branch->expr->compile(new_env, branch_instructions);
  170. branch_instructions.push_back(instruction_ptr(new instruction_slide(
  171. cpat->params.size())));
  172. int new_tag = type->constructors[cpat->constr].tag;
  173. if(jump_instruction->tag_mappings.find(new_tag) !=
  174. jump_instruction->tag_mappings.end())
  175. throw type_error("technically not a type error: duplicate pattern");
  176. jump_instruction->tag_mappings[new_tag] =
  177. jump_instruction->branches.size();
  178. jump_instruction->branches.push_back(std::move(branch_instructions));
  179. }
  180. }
  181. for(auto& constr_pair : type->constructors) {
  182. if(jump_instruction->tag_mappings.find(constr_pair.second.tag) ==
  183. jump_instruction->tag_mappings.end())
  184. throw type_error("non-total pattern");
  185. }
  186. }
  187. void pattern_var::print(std::ostream& to) const {
  188. to << var;
  189. }
  190. void pattern_var::insert_bindings(type_mgr& mgr, type_env_ptr& env) const {
  191. env->bind(var, mgr.new_type());
  192. }
  193. void pattern_var::typecheck(type_ptr t, type_mgr& mgr, type_env_ptr& env) const {
  194. mgr.unify(env->lookup(var)->instantiate(mgr), t);
  195. }
  196. void pattern_constr::print(std::ostream& to) const {
  197. to << constr;
  198. for(auto& param : params) {
  199. to << " " << param;
  200. }
  201. }
  202. void pattern_constr::insert_bindings(type_mgr& mgr, type_env_ptr& env) const {
  203. for(auto& param : params) {
  204. env->bind(param, mgr.new_type());
  205. }
  206. }
  207. void pattern_constr::typecheck(type_ptr t, type_mgr& mgr, type_env_ptr& env) const {
  208. type_ptr constructor_type = env->lookup(constr)->instantiate(mgr);
  209. if(!constructor_type) {
  210. throw type_error(std::string("pattern using unknown constructor ") + constr);
  211. }
  212. for(auto& param : params) {
  213. type_arr* arr = dynamic_cast<type_arr*>(constructor_type.get());
  214. if(!arr) throw type_error("too many parameters in constructor pattern");
  215. mgr.unify(env->lookup(param)->instantiate(mgr), arr->left);
  216. constructor_type = arr->right;
  217. }
  218. mgr.unify(t, constructor_type);
  219. }