Lisp interpreter from PPL
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.
 
 
 

262 lines
8.5 KiB

#include <cstring>
#include "lisp.hh"
#include "builtins.hh"
int main() {
builtin_functions.insert({{"help", help}});
builtin_functions.insert({{"read", read}});
builtin_functions.insert({{"print", print}});
builtin_functions.insert({{"quit", quit}});
builtin_functions.insert({{"eval", eval}});
// Some example expressions defined in the global scope
ParseTree *pi = AST::read("3.141592653589793");
ParseTree *tau = AST::read("6.283185307179586");
ParseTree *exp = AST::read("2.718281828459045");
ParseTree *phi = AST::read("1.618033988749894");
ParseTree *dbl = AST::read("(lambda (x) (+ x x))");
ParseTree *even = AST::read("(lambda (n) (= 0 (% n 2)))");
ParseTree *conj = AST::read("(lambda (a b) (if a (if b t nil) nil))");
ParseTree *disj = AST::read("(lambda (a b) (if a t (if b t nil)))");
AST::SymbolTable *global_scope = new AST::SymbolTable(nullptr, {
{"phi", phi}
, {"pi", pi}
, {"tau", tau}
, {"e", exp}
, {"double", dbl}
, {"even", even}
, {"and", conj}
, {"or", disj}
});
printf("โ–‘โ–€โ–€โ–ˆโ–‘โ–ˆโ–€โ–ˆโ–‘โ–ˆโ–„โ–ˆโ–‘โ–ˆโ–„โ–ˆโ–‘โ–€โ–ˆโ–€โ–‘โ–ˆโ–€โ–ˆโ–‘โ–€โ–‘โ–‘โ–‘โ–ˆโ–‘โ–‘โ–‘โ–€โ–ˆโ–€โ–‘โ–ˆโ–€โ–€โ–‘โ–ˆโ–€โ–ˆ\n");
printf("โ–‘โ–‘โ–‘โ–ˆโ–‘โ–ˆโ–€โ–ˆโ–‘โ–ˆโ–‘โ–ˆโ–‘โ–ˆโ–‘โ–ˆโ–‘โ–‘โ–ˆโ–‘โ–‘โ–ˆโ–‘โ–ˆโ–‘โ–‘โ–‘โ–‘โ–‘โ–ˆโ–‘โ–‘โ–‘โ–‘โ–ˆโ–‘โ–‘โ–€โ–€โ–ˆโ–‘โ–ˆโ–€โ–€\n");
printf("โ–‘โ–€โ–€โ–‘โ–‘โ–€โ–‘โ–€โ–‘โ–€โ–‘โ–€โ–‘โ–€โ–‘โ–€โ–‘โ–€โ–€โ–€โ–‘โ–€โ–‘โ–€โ–‘โ–‘โ–‘โ–‘โ–‘โ–€โ–€โ–€โ–‘โ–€โ–€โ–€โ–‘โ–€โ–€โ–€โ–‘โ–€โ–‘โ–‘ (J-Maes, 2k16)\n");
FILE *outfile = fopen("results.file", "w");
while (true) {
printf(" * ");
std::string expr = readline(stdin);
ParseTree *ast = AST::read(expr, global_scope);
ParseTree *result = eval(ast);
// shoepolish!
printf(" |\n โ•ฐโ”€> %s\n\n", result->str().c_str());
fprintf(outfile, "%s\n", result->str().c_str());
}
fclose(outfile);
return 0;
}
// reads a line of text from an input file, trimming leading and tailing
// whitespace
std::string readline(FILE *input) {
char buffer[256];
std::string expr = "";
if ((fgets(buffer, 256, input) != NULL)) {
int len = strnlen(buffer, 256);
std::string whitespace = " \t\n\r\x0b\x0c";
expr = std::string(buffer, len);
// empty string, just stop
if (expr.find_first_not_of(whitespace) == std::string::npos) {
expr.clear();
}
} else {
quit(nullptr);
}
return expr;
}
// Recursively evaluate a lisp expression
ParseTree *eval(ParseTree *expr) {
// if the expression is an atom that is defined in scope, it evaluates to
// its definition
if (expr->scope != nullptr) {
ParseTree *val = expr->scope->lookup(expr->atom);
if (val != nullptr) {
return val;
}
}
// if the expression is a list, it needs to be called like a function
if (expr->iscons()) {
// quote is a special case - return a copy of the inner tree without
// evaluating it
if (expr->list[0]->atom == "quote" || expr->list[0]->atom == "'") {
return quote(expr->cdr());
}
// if is another special case - evaluate only one of expression's
// subtrees
else if (expr->list[0]->atom == "if") {
if (expr->list.size() == 4) {
if (eval(expr->list[1])->isnil()) {
return eval(expr->list[3]);
} else {
return eval(expr->list[2]);
}
} else {
return new ParseTree(AST::invalid_funccall);
}
}
// a "(define)" statement evaluates its second argument and inserts the
// result into the local scope of its expression
else if (expr->list[0]->atom == "define") {
if (expr->list.size() == 3 && expr->list[1]->atomp()) {
ParseTree *def = eval(expr->list[2]);
expr->scope->define(expr->list[1]->atom, def);
return def;
} else {
return new ParseTree(AST::invalid_funccall);
}
}
// "(set!)" works almost exactly the same, but it uses "redefine" to
// overwrite an already existing variable
else if (expr->list[0]->atom == "set!") {
if (expr->list.size() == 3 && expr->list[1]->atomp()) {
ParseTree *def = eval(expr->list[2]);
expr->scope->redefine(expr->list[1]->atom, def);
return def;
} else {
return new ParseTree(AST::invalid_funccall);
}
}
// "(defun)" is syntactic sugar for defining a lambda function
else if (expr->list[0]->atom == "defun") {
if (expr->list.size() == 4 && expr->list[1]->atomp()) {
ParseTree *def = expr->cdr();
def->list[0]->atom = "lambda";
expr->scope->define(expr->list[1]->atom, def);
return def;
} else {
return new ParseTree(AST::invalid_funccall);
}
}
// a lambda is a valid term, but should not be evaluated
else if (expr->islambda()) {
return expr;
}
// if none of the above special cases apply, then the list is evaluated
// as a function call!
else {
ParseTree *func = eval(expr->list[0]);
ParseTree *args = new ParseTree(AST::no_error, expr->scope);
// evaluate every argument separately before calling
for (size_t i = 1; i < expr->list.size(); i++) {
args->list.push_back(eval(expr->list[i]));
}
// escape ((argument list)) in the case of eval
if (func->atom == "eval" || func->atom == "print") {
args = args->car();
}
return funccall(func, args);
}
} else {
// a constant literal evaluates to itself
return expr;
}
}
// Evaluate a lisp function call with a list of arguments
ParseTree *funccall(ParseTree *func, ParseTree *args) {
// search to see if "func" is a builtin function
FunctionTable::const_iterator lkp = builtin_functions.find(func->atom);
// if so, call it and return the result
if (lkp != builtin_functions.end()) {
return lkp->second(args);
}
// if it's not a builtin, evaluate the function again to make sure its a
// lambda expression
func = eval(func);
if (func->islambda()) {
// a lambda is of the form (lambda (params) (body))
ParseTree *params = func->list[1];
if (params->list.size() == args->list.size()) {
// copy the parse tree of the body and define a new child scope
ParseTree *body = new ParseTree(*func->list[2]);
AST::SymbolTable *env = body->scope->gen_child();
int idx = 0;
for (ParseTree *param : params->list) {
if (param->atomp()) {
// in the new local scope, bind all the variables in the
// list of parameters to the evaluated arguments passed to
// the function
ParseTree *arg = eval(args->list[idx++]);
env->define(param->atom, arg);
} else {
return new ParseTree(AST::invalid_funccall);
}
}
// apply the new scope to the entire body of the function call and
// evaluate the result
body->set_scope(env);
return eval(body);
}
}
return new ParseTree(AST::invalid_funccall);
}
ParseTree *help(ParseTree *expr) {
printf("\nBuiltin functions:\n");
int len = 0;
for (std::pair<std::string, LispFunction> keyval : builtin_functions) {
if (len == 0) {
printf("\n ");
}
len += printf("%s, ", keyval.first.c_str());
if (len > 70) {
len = 0;
}
}
printf("\n\nLocally defined variables:\n\n");
expr->scope->print();
return new ParseTree(std::string("nil"));
}
ParseTree *print(ParseTree *expr) {
printf("%s\n", expr->str().c_str());
return expr;
}
ParseTree *read(ParseTree *expr) {
if (expr->iscons()) {
printf("%s ", expr->list[0]->str().c_str());
}
std::string line = readline(stdin);
return AST::read(line, expr->scope);
}
// Allows the user to exit the interpreter with "(quit)"
ParseTree *quit(ParseTree *expr) {
delete expr;
printf("au revoir!\n");
exit(0);
}