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

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