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

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454
  1. #include "ast.hpp"
  2. #include <ostream>
  3. #include <type_traits>
  4. #include "binop.hpp"
  5. #include "error.hpp"
  6. #include "instruction.hpp"
  7. #include "type.hpp"
  8. #include "type_env.hpp"
  9. #include "env.hpp"
  10. static void print_indent(int n, std::ostream& to) {
  11. while(n--) to << " ";
  12. }
  13. void ast_int::print(int indent, std::ostream& to) const {
  14. print_indent(indent, to);
  15. to << "INT: " << value << std::endl;
  16. }
  17. void ast_int::find_free(std::set<std::string>& into) {
  18. }
  19. type_ptr ast_int::typecheck(type_mgr& mgr, type_env_ptr& env) {
  20. this->env = env;
  21. return type_ptr(new type_app(env->lookup_type("Int")));
  22. }
  23. void ast_int::translate(global_scope& scope) {
  24. }
  25. void ast_int::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  26. into.push_back(instruction_ptr(new instruction_pushint(value)));
  27. }
  28. void ast_lid::print(int indent, std::ostream& to) const {
  29. print_indent(indent, to);
  30. to << "LID: " << id << std::endl;
  31. }
  32. void ast_lid::find_free(std::set<std::string>& into) {
  33. into.insert(id);
  34. }
  35. type_ptr ast_lid::typecheck(type_mgr& mgr, type_env_ptr& env) {
  36. this->env = env;
  37. type_scheme_ptr lid_type = env->lookup(id);
  38. if(!lid_type)
  39. throw type_error("unknown identifier " + id, loc);
  40. return lid_type->instantiate(mgr);
  41. }
  42. void ast_lid::translate(global_scope& scope) {
  43. }
  44. void ast_lid::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  45. into.push_back(instruction_ptr(
  46. (this->env->is_global(id)) ?
  47. (instruction*) new instruction_pushglobal(this->env->get_mangled_name(id)) :
  48. (instruction*) new instruction_push(env->get_offset(id))));
  49. }
  50. void ast_uid::print(int indent, std::ostream& to) const {
  51. print_indent(indent, to);
  52. to << "UID: " << id << std::endl;
  53. }
  54. void ast_uid::find_free(std::set<std::string>& into) {
  55. }
  56. type_ptr ast_uid::typecheck(type_mgr& mgr, type_env_ptr& env) {
  57. this->env = env;
  58. type_scheme_ptr uid_type = env->lookup(id);
  59. if(!uid_type)
  60. throw type_error("unknown constructor " + id, loc);
  61. return uid_type->instantiate(mgr);
  62. }
  63. void ast_uid::translate(global_scope& scope) {
  64. }
  65. void ast_uid::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  66. into.push_back(instruction_ptr(
  67. new instruction_pushglobal(this->env->get_mangled_name(id))));
  68. }
  69. void ast_binop::print(int indent, std::ostream& to) const {
  70. print_indent(indent, to);
  71. to << "BINOP: " << op_name(op) << std::endl;
  72. left->print(indent + 1, to);
  73. right->print(indent + 1, to);
  74. }
  75. void ast_binop::find_free(std::set<std::string>& into) {
  76. left->find_free(into);
  77. right->find_free(into);
  78. }
  79. type_ptr ast_binop::typecheck(type_mgr& mgr, type_env_ptr& env) {
  80. this->env = env;
  81. type_ptr ltype = left->typecheck(mgr, env);
  82. type_ptr rtype = right->typecheck(mgr, env);
  83. type_ptr ftype = env->lookup(op_name(op))->instantiate(mgr);
  84. if(!ftype) throw type_error("unknown binary operator " + op_name(op), loc);
  85. // For better type errors, we first require binary function,
  86. // and only then unify each argument. This way, we can
  87. // precisely point out which argument is "wrong".
  88. type_ptr return_type = mgr.new_type();
  89. type_ptr second_type = mgr.new_type();
  90. type_ptr first_type = mgr.new_type();
  91. type_ptr arrow_one = type_ptr(new type_arr(second_type, return_type));
  92. type_ptr arrow_two = type_ptr(new type_arr(first_type, arrow_one));
  93. mgr.unify(ftype, arrow_two, loc);
  94. mgr.unify(first_type, ltype, left->loc);
  95. mgr.unify(second_type, rtype, right->loc);
  96. return return_type;
  97. }
  98. void ast_binop::translate(global_scope& scope) {
  99. left->translate(scope);
  100. right->translate(scope);
  101. }
  102. void ast_binop::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  103. right->compile(env, into);
  104. left->compile(env_ptr(new env_offset(1, env)), into);
  105. auto mangled_name = this->env->get_mangled_name(op_name(op));
  106. into.push_back(instruction_ptr(new instruction_pushglobal(mangled_name)));
  107. into.push_back(instruction_ptr(new instruction_mkapp()));
  108. into.push_back(instruction_ptr(new instruction_mkapp()));
  109. }
  110. void ast_app::print(int indent, std::ostream& to) const {
  111. print_indent(indent, to);
  112. to << "APP:" << std::endl;
  113. left->print(indent + 1, to);
  114. right->print(indent + 1, to);
  115. }
  116. void ast_app::find_free(std::set<std::string>& into) {
  117. left->find_free(into);
  118. right->find_free(into);
  119. }
  120. type_ptr ast_app::typecheck(type_mgr& mgr, type_env_ptr& env) {
  121. this->env = env;
  122. type_ptr ltype = left->typecheck(mgr, env);
  123. type_ptr rtype = right->typecheck(mgr, env);
  124. type_ptr return_type = mgr.new_type();
  125. type_ptr arrow = type_ptr(new type_arr(rtype, return_type));
  126. mgr.unify(arrow, ltype, left->loc);
  127. return return_type;
  128. }
  129. void ast_app::translate(global_scope& scope) {
  130. left->translate(scope);
  131. right->translate(scope);
  132. }
  133. void ast_app::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  134. right->compile(env, into);
  135. left->compile(env_ptr(new env_offset(1, env)), into);
  136. into.push_back(instruction_ptr(new instruction_mkapp()));
  137. }
  138. void ast_case::print(int indent, std::ostream& to) const {
  139. print_indent(indent, to);
  140. to << "CASE: " << std::endl;
  141. for(auto& branch : branches) {
  142. print_indent(indent + 1, to);
  143. branch->pat->print(to);
  144. to << std::endl;
  145. branch->expr->print(indent + 2, to);
  146. }
  147. }
  148. void ast_case::find_free(std::set<std::string>& into) {
  149. of->find_free(into);
  150. for(auto& branch : branches) {
  151. std::set<std::string> free_in_branch;
  152. std::set<std::string> pattern_variables;
  153. branch->pat->find_variables(pattern_variables);
  154. branch->expr->find_free(free_in_branch);
  155. for(auto& free : free_in_branch) {
  156. if(pattern_variables.find(free) == pattern_variables.end())
  157. into.insert(free);
  158. }
  159. }
  160. }
  161. type_ptr ast_case::typecheck(type_mgr& mgr, type_env_ptr& env) {
  162. this->env = env;
  163. type_var* var;
  164. type_ptr case_type = mgr.resolve(of->typecheck(mgr, env), var);
  165. type_ptr branch_type = mgr.new_type();
  166. for(auto& branch : branches) {
  167. type_env_ptr new_env = type_scope(env);
  168. branch->pat->typecheck(case_type, mgr, new_env);
  169. type_ptr curr_branch_type = branch->expr->typecheck(mgr, new_env);
  170. mgr.unify(curr_branch_type, branch_type, branch->expr->loc);
  171. }
  172. input_type = mgr.resolve(case_type, var);
  173. type_app* app_type;
  174. if(!(app_type = dynamic_cast<type_app*>(input_type.get())) ||
  175. !dynamic_cast<type_data*>(app_type->constructor.get())) {
  176. throw type_error("attempting case analysis of non-data type");
  177. }
  178. return branch_type;
  179. }
  180. void ast_case::translate(global_scope& scope) {
  181. of->translate(scope);
  182. for(auto& branch : branches) {
  183. branch->expr->translate(scope);
  184. }
  185. }
  186. void ast_case::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  187. type_app* app_type = dynamic_cast<type_app*>(input_type.get());
  188. type_data* type = dynamic_cast<type_data*>(app_type->constructor.get());
  189. of->compile(env, into);
  190. into.push_back(instruction_ptr(new instruction_eval()));
  191. instruction_jump* jump_instruction = new instruction_jump();
  192. into.push_back(instruction_ptr(jump_instruction));
  193. for(auto& branch : branches) {
  194. std::vector<instruction_ptr> branch_instructions;
  195. pattern_var* vpat;
  196. pattern_constr* cpat;
  197. if((vpat = dynamic_cast<pattern_var*>(branch->pat.get()))) {
  198. branch->expr->compile(env_ptr(new env_offset(1, env)), branch_instructions);
  199. for(auto& constr_pair : type->constructors) {
  200. if(jump_instruction->tag_mappings.find(constr_pair.second.tag) !=
  201. jump_instruction->tag_mappings.end())
  202. break;
  203. jump_instruction->tag_mappings[constr_pair.second.tag] =
  204. jump_instruction->branches.size();
  205. }
  206. jump_instruction->branches.push_back(std::move(branch_instructions));
  207. } else if((cpat = dynamic_cast<pattern_constr*>(branch->pat.get()))) {
  208. env_ptr new_env = env;
  209. for(auto it = cpat->params.rbegin(); it != cpat->params.rend(); it++) {
  210. new_env = env_ptr(new env_var(*it, new_env));
  211. }
  212. branch_instructions.push_back(instruction_ptr(new instruction_split(
  213. cpat->params.size())));
  214. branch->expr->compile(new_env, branch_instructions);
  215. branch_instructions.push_back(instruction_ptr(new instruction_slide(
  216. cpat->params.size())));
  217. int new_tag = type->constructors[cpat->constr].tag;
  218. if(jump_instruction->tag_mappings.find(new_tag) !=
  219. jump_instruction->tag_mappings.end())
  220. throw type_error("technically not a type error: duplicate pattern");
  221. jump_instruction->tag_mappings[new_tag] =
  222. jump_instruction->branches.size();
  223. jump_instruction->branches.push_back(std::move(branch_instructions));
  224. }
  225. }
  226. for(auto& constr_pair : type->constructors) {
  227. if(jump_instruction->tag_mappings.find(constr_pair.second.tag) ==
  228. jump_instruction->tag_mappings.end())
  229. throw type_error("non-total pattern");
  230. }
  231. }
  232. void ast_let::print(int indent, std::ostream& to) const {
  233. print_indent(indent, to);
  234. to << "LET: " << std::endl;
  235. in->print(indent + 1, to);
  236. }
  237. void ast_let::find_free(std::set<std::string>& into) {
  238. definitions.find_free(into);
  239. std::set<std::string> all_free;
  240. in->find_free(all_free);
  241. for(auto& free_var : all_free) {
  242. if(definitions.defs_defn.find(free_var) == definitions.defs_defn.end())
  243. into.insert(free_var);
  244. }
  245. }
  246. type_ptr ast_let::typecheck(type_mgr& mgr, type_env_ptr& env) {
  247. this->env = env;
  248. definitions.typecheck(mgr, env);
  249. return in->typecheck(mgr, definitions.env);
  250. }
  251. void ast_let::translate(global_scope& scope) {
  252. for(auto& def : definitions.defs_data) {
  253. def.second->into_globals(scope);
  254. }
  255. for(auto& def : definitions.defs_defn) {
  256. size_t original_params = def.second->params.size();
  257. std::string original_name = def.second->name;
  258. auto& global_definition = def.second->into_global(scope);
  259. size_t captured = global_definition.params.size() - original_params;
  260. type_env_ptr mangled_env = type_scope(env);
  261. mangled_env->bind(def.first, env->lookup(def.first), visibility::global);
  262. mangled_env->set_mangled_name(def.first, global_definition.name);
  263. ast_ptr global_app(new ast_lid(original_name));
  264. global_app->env = mangled_env;
  265. for(auto& param : global_definition.params) {
  266. if(!(captured--)) break;
  267. ast_ptr new_arg(new ast_lid(param));
  268. new_arg->env = env;
  269. global_app = ast_ptr(new ast_app(std::move(global_app), std::move(new_arg)));
  270. global_app->env = env;
  271. }
  272. translated_definitions.push_back({ def.first, std::move(global_app) });
  273. }
  274. in->translate(scope);
  275. }
  276. void ast_let::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  277. into.push_back(instruction_ptr(new instruction_alloc(translated_definitions.size())));
  278. env_ptr new_env = env;
  279. for(auto& def : translated_definitions) {
  280. new_env = env_ptr(new env_var(def.first, std::move(new_env)));
  281. }
  282. int offset = translated_definitions.size() - 1;
  283. for(auto& def : translated_definitions) {
  284. def.second->compile(new_env, into);
  285. into.push_back(instruction_ptr(new instruction_update(offset--)));
  286. }
  287. in->compile(new_env, into);
  288. into.push_back(instruction_ptr(new instruction_slide(translated_definitions.size())));
  289. }
  290. void ast_lambda::print(int indent, std::ostream& to) const {
  291. print_indent(indent, to);
  292. to << "LAMBDA";
  293. for(auto& param : params) {
  294. to << " " << param;
  295. }
  296. to << std::endl;
  297. body->print(indent+1, to);
  298. }
  299. void ast_lambda::find_free(std::set<std::string>& into) {
  300. body->find_free(free_variables);
  301. for(auto& param : params) {
  302. free_variables.erase(param);
  303. }
  304. into.insert(free_variables.begin(), free_variables.end());
  305. }
  306. type_ptr ast_lambda::typecheck(type_mgr& mgr, type_env_ptr& env) {
  307. this->env = env;
  308. var_env = type_scope(env);
  309. type_ptr return_type = mgr.new_type();
  310. type_ptr full_type = return_type;
  311. for(auto it = params.rbegin(); it != params.rend(); it++) {
  312. type_ptr param_type = mgr.new_type();
  313. var_env->bind(*it, param_type);
  314. full_type = type_ptr(new type_arr(std::move(param_type), full_type));
  315. }
  316. mgr.unify(return_type, body->typecheck(mgr, var_env), body->loc);
  317. return full_type;
  318. }
  319. void ast_lambda::translate(global_scope& scope) {
  320. std::vector<std::string> function_params;
  321. for(auto& free_variable : free_variables) {
  322. if(env->is_global(free_variable)) continue;
  323. function_params.push_back(free_variable);
  324. }
  325. size_t captured_count = function_params.size();
  326. function_params.insert(function_params.end(), params.begin(), params.end());
  327. auto& new_function = scope.add_function("lambda", std::move(function_params), std::move(body));
  328. type_env_ptr mangled_env = type_scope(env);
  329. mangled_env->bind("lambda", type_scheme_ptr(nullptr), visibility::global);
  330. mangled_env->set_mangled_name("lambda", new_function.name);
  331. ast_ptr new_application = ast_ptr(new ast_lid("lambda"));
  332. new_application->env = mangled_env;
  333. for(auto& param : new_function.params) {
  334. if(!(captured_count--)) break;
  335. ast_ptr new_arg = ast_ptr(new ast_lid(param));
  336. new_arg->env = env;
  337. new_application = ast_ptr(new ast_app(std::move(new_application), std::move(new_arg)));
  338. new_application->env = env;
  339. }
  340. translated = std::move(new_application);
  341. }
  342. void ast_lambda::compile(const env_ptr& env, std::vector<instruction_ptr>& into) const {
  343. translated->compile(env, into);
  344. }
  345. void pattern_var::print(std::ostream& to) const {
  346. to << var;
  347. }
  348. void pattern_var::find_variables(std::set<std::string>& into) const {
  349. into.insert(var);
  350. }
  351. void pattern_var::typecheck(type_ptr t, type_mgr& mgr, type_env_ptr& env) const {
  352. env->bind(var, t);
  353. }
  354. void pattern_constr::print(std::ostream& to) const {
  355. to << constr;
  356. for(auto& param : params) {
  357. to << " " << param;
  358. }
  359. }
  360. void pattern_constr::find_variables(std::set<std::string>& into) const {
  361. into.insert(params.begin(), params.end());
  362. }
  363. void pattern_constr::typecheck(type_ptr t, type_mgr& mgr, type_env_ptr& env) const {
  364. type_scheme_ptr constructor_type_scheme = env->lookup(constr);
  365. if(!constructor_type_scheme) {
  366. throw type_error("pattern using unknown constructor " + constr, loc);
  367. }
  368. type_ptr constructor_type = constructor_type_scheme->instantiate(mgr);
  369. for(auto& param : params) {
  370. type_arr* arr = dynamic_cast<type_arr*>(constructor_type.get());
  371. if(!arr) throw type_error("too many parameters in constructor pattern", loc);
  372. env->bind(param, arr->left);
  373. constructor_type = arr->right;
  374. }
  375. mgr.unify(t, constructor_type, loc);
  376. }