209 lines
8.9 KiB
C++
209 lines
8.9 KiB
C++
#include "ast.hpp"
|
|
#include "type_checker.hpp"
|
|
#include "error.hpp"
|
|
|
|
namespace lily {
|
|
type* ast::typecheck(type_manager& mgr, std::shared_ptr<type_env> env) {
|
|
return (ast_type = check(mgr, env));
|
|
}
|
|
|
|
type* ast_num::check(type_manager& mgr, std::shared_ptr<type_env> env) {
|
|
return mgr.require_type("Int");
|
|
}
|
|
|
|
type* ast_var::check(type_manager& mgr, std::shared_ptr<type_env> env) {
|
|
return env->get_identifier_type(name);
|
|
}
|
|
|
|
type* ast_app::check(type_manager& mgr, std::shared_ptr<type_env> env) {
|
|
type* ltype = left->typecheck(mgr, env);
|
|
type* rtype = right->typecheck(mgr, env);
|
|
|
|
// We LHS has to be a function, so unify LHS with that.
|
|
type_func* f = mgr.create_type<type_func>(nullptr, nullptr);
|
|
// Input type of function is known - it's rtype.
|
|
f->left = rtype;
|
|
// Output is not known - create parameter for it.
|
|
type* new_param = mgr.create_type<type_parameter>();
|
|
f->right = new_param;
|
|
|
|
// Unify ltype with the function (we know it has to be one!)
|
|
if(!ltype->unify_with(f))
|
|
throw error("unable to unify application type");
|
|
|
|
return new_param;
|
|
}
|
|
|
|
type* ast_op::check(type_manager& mgr, std::shared_ptr<type_env> env) {
|
|
type* ltype = left->typecheck(mgr, env);
|
|
type* rtype = right->typecheck(mgr, env);
|
|
|
|
// We know the thing has to be a nunmber, so we unify with number type.
|
|
type* inttype = mgr.require_type("Int");
|
|
if(!ltype->unify_with(inttype))
|
|
throw error("left hand side of operator must be a number.");
|
|
if(!rtype->unify_with(inttype))
|
|
throw error("right hand side of operator must be a number.");
|
|
|
|
// We return an integer.
|
|
return inttype;
|
|
}
|
|
|
|
type* ast_let::check(type_manager& mgr, std::shared_ptr<type_env> env) {
|
|
if(env->identifier_exists(name))
|
|
throw error("invalid redefinition of variable.");
|
|
type* etype = expr->typecheck(mgr, env);
|
|
auto new_env = env->with_type(name, etype);
|
|
return in->typecheck(mgr, new_env);
|
|
}
|
|
|
|
type* ast_letrec::check(type_manager& mgr, std::shared_ptr<type_env> env) {
|
|
if(env->identifier_exists(name))
|
|
throw error("invalid redefinition of variable.");
|
|
type* variable_type = mgr.create_type<type_parameter>();
|
|
auto new_env = env->with_type(name, variable_type);
|
|
type* etype = expr->typecheck(mgr, new_env);
|
|
if(!variable_type->unify_with(etype))
|
|
throw error("incompatible type for variable");
|
|
return in->typecheck(mgr, new_env);
|
|
}
|
|
|
|
type* ast_case::check(type_manager& mgr, std::shared_ptr<type_env> env) {
|
|
type* ctype = of->typecheck(mgr, env);
|
|
type* pattern_type = nullptr;
|
|
type* branch_type = nullptr;
|
|
for(auto& branch : branches) {
|
|
auto new_env = std::make_shared<type_env>();
|
|
new_env->set_parent(env.get());
|
|
type* new_type = branch.pattern->check_modifying(mgr, new_env);
|
|
|
|
if(!pattern_type) {
|
|
pattern_type = new_type;
|
|
} else {
|
|
if(!pattern_type->unify_with(new_type))
|
|
throw error("incompatible pattern types");
|
|
}
|
|
if(!pattern_type->unify_with(ctype))
|
|
throw error("pattern type doesn't match case value type");
|
|
|
|
type* new_branch_type = branch.expr->typecheck(mgr, new_env);
|
|
if(!branch_type) {
|
|
branch_type = new_branch_type;
|
|
} else {
|
|
if(!branch_type->unify_with(new_branch_type))
|
|
throw error("branches have incompatible types");
|
|
}
|
|
}
|
|
|
|
case_type = pattern_type;
|
|
|
|
return branch_type;
|
|
}
|
|
|
|
void ast_num::compile(instruction_manager& mgr, std::vector<instruction*>& into, std::shared_ptr<compile_env> env) {
|
|
into.push_back(mgr.add_instruction<instruction_push_int>(num));
|
|
}
|
|
|
|
void ast_var::compile(instruction_manager& mgr, std::vector<instruction*>& into, std::shared_ptr<compile_env> env) {
|
|
if(env->is_variable(name)) {
|
|
into.push_back(mgr.add_instruction<instruction_push>(env->get_offset(name)));
|
|
} else {
|
|
into.push_back(mgr.add_instruction<instruction_push_global>(name));
|
|
}
|
|
}
|
|
|
|
void ast_app::compile(instruction_manager& mgr, std::vector<instruction*>& into, std::shared_ptr<compile_env> env) {
|
|
auto new_env = std::make_shared<compile_env_offset>(1);
|
|
new_env->set_parent(env);
|
|
right->compile(mgr, into, env);
|
|
left->compile(mgr, into, new_env);
|
|
into.push_back(mgr.add_instruction<instruction_mkapp>());
|
|
}
|
|
|
|
void ast_op::compile(instruction_manager& mgr, std::vector<instruction*>& into, std::shared_ptr<compile_env> env) {
|
|
auto new_env = std::make_shared<compile_env_offset>(1);
|
|
new_env->set_parent(env);
|
|
right->compile(mgr, into, env);
|
|
left->compile(mgr, into, new_env);
|
|
into.push_back(mgr.add_instruction<instruction_push_global>(op_supercombinator(op)));
|
|
into.push_back(mgr.add_instruction<instruction_mkapp>());
|
|
into.push_back(mgr.add_instruction<instruction_mkapp>());
|
|
}
|
|
|
|
void ast_let::compile(instruction_manager& mgr, std::vector<instruction*>& into, std::shared_ptr<compile_env> env) {
|
|
expr->compile(mgr, into, env);
|
|
auto new_env = std::make_shared<compile_env_var>(name);
|
|
new_env->set_parent(env);
|
|
in->compile(mgr, into, new_env);
|
|
into.push_back(mgr.add_instruction<instruction_slide>(1));
|
|
}
|
|
|
|
void ast_letrec::compile(instruction_manager& mgr, std::vector<instruction*>& into, std::shared_ptr<compile_env> env) {
|
|
into.push_back(mgr.add_instruction<instruction_alloc>(1));
|
|
auto new_env = std::make_shared<compile_env_var>(name);
|
|
new_env->set_parent(env);
|
|
expr->compile(mgr, into, new_env);
|
|
into.push_back(mgr.add_instruction<instruction_update>(0));
|
|
in->compile(mgr, into, new_env);
|
|
into.push_back(mgr.add_instruction<instruction_slide>(1));
|
|
}
|
|
|
|
void ast_case::compile(instruction_manager& mgr, std::vector<instruction*>& into, std::shared_ptr<compile_env> env) {
|
|
type_parameter* param;
|
|
type* current_type = case_type;
|
|
while((param = dynamic_cast<type_parameter*>(current_type))) current_type = param->actual_type;
|
|
|
|
type_data* data = dynamic_cast<type_data*>(current_type);
|
|
if(!data) throw error("case expression must be a data type!");
|
|
|
|
of->compile(mgr, into, env);
|
|
into.push_back(mgr.add_instruction<instruction_eval>());
|
|
|
|
instruction_jump* ijump = mgr.add_instruction<instruction_jump>();
|
|
int ccount = data->constructors.size();
|
|
bool branched[ccount];
|
|
for(int i = 0; i < ccount; i++) branched[i] = false;
|
|
for(auto& branch : branches) {
|
|
auto& pattern = branch.pattern;
|
|
pattern_var* var_pattern = dynamic_cast<pattern_var*>(pattern.get());
|
|
if(var_pattern) {
|
|
auto new_env = std::make_shared<compile_env_var>(var_pattern->name);
|
|
new_env->set_parent(env);
|
|
std::vector<instruction*> new_branch;
|
|
branch.expr->compile(mgr, new_branch, new_env);
|
|
new_branch.push_back(mgr.add_instruction<instruction_slide>(1));
|
|
ijump->instructions.push_back(std::move(new_branch));
|
|
|
|
for(int i = 0; i < ccount; i++) {
|
|
if(!branched[i]) ijump->const_instructions[i] = ijump->instructions.size() - 1;
|
|
branched[i] = true;
|
|
}
|
|
} else {
|
|
pattern_cons* cons_pattern = dynamic_cast<pattern_cons*>(pattern.get());
|
|
int constructor;
|
|
for(auto& pair : data->constructors) {
|
|
if(pair.first == cons_pattern->name) constructor = pair.second->id;
|
|
}
|
|
if(branched[constructor]) throw error("cannot branch on the same constructor twice");
|
|
branched[constructor] = true;
|
|
|
|
int vcount = cons_pattern->vnames.size();
|
|
for(int i = 0; i < cons_pattern->vnames.size(); i++) {
|
|
auto new_env = std::make_shared<compile_env_var>(cons_pattern->vnames[vcount - i - 1]);
|
|
new_env->set_parent(env);
|
|
env = new_env;
|
|
}
|
|
|
|
std::vector<instruction*> into;
|
|
into.push_back(mgr.add_instruction<instruction_split>(vcount));
|
|
branch.expr->compile(mgr, into, env);
|
|
into.push_back(mgr.add_instruction<instruction_slide>(vcount));
|
|
ijump->instructions.push_back(std::move(into));
|
|
ijump->const_instructions[constructor] = ijump->instructions.size() - 1;
|
|
}
|
|
}
|
|
for(int i = 0; i < ccount; i++) if(!branched[i]) throw error("non-total case expression");
|
|
into.push_back(ijump);
|
|
}
|
|
}
|