From cac651cd88f8da1e5957b0cc13fa25d79e1887fc Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Tue, 23 Aug 2016 20:58:50 +0200 Subject: Many things - two-letter AST union members - AST_QUOTED - AST_LAMBDA - an interpreter that works - function registering in the interpreter - some builtins --- ast.c | 113 +++++++++++++++++++++++++++++++------------------ ast.h | 41 ++++++++++++++---- code.lysp | 18 ++++---- inter_builtins.c | 60 ++++++++++++++++++++++++++ inter_builtins.h | 13 ++++++ interpreter.c | 125 ++++++++++++++++++++++++++++++++++++++++++++++++++++--- interpreter.h | 16 ++++++- main.c | 16 +++++++ parser.c | 23 +++++----- util.c | 9 ++++ util.h | 2 + 11 files changed, 363 insertions(+), 73 deletions(-) create mode 100644 inter_builtins.c create mode 100644 inter_builtins.h diff --git a/ast.c b/ast.c index a6f308d..c2ea654 100644 --- a/ast.c +++ b/ast.c @@ -12,27 +12,37 @@ void ast_free(AST *ast){ assert(ast); switch(ast->type){ case AST_LIST: - assert(ast->l.len>=0); - for(int i=0;il.len;i++){ - assert(ast->l.nodes[i]); - ast_free(ast->l.nodes[i]); + assert(ast->li.len>=0); + for(int i=0;ili.len;i++){ + assert(ast->li.nodes[i]); + ast_free(ast->li.nodes[i]); } break; + case AST_LAMBDA: + assert(ast->la.cfunc||ast->la.body); + if(ast->la.body)ast_free(ast->la.body); + break; + case AST_WORD: - assert(ast->w.word); - free(ast->w.word); + assert(ast->wo.word); + free(ast->wo.word); break; case AST_STRING: - assert(ast->S.str); - free(ast->S.str); + assert(ast->st.str); + free(ast->st.str); break; case AST_NUMBER: case AST_SYMBOL: break; + case AST_QUOTED: + assert(ast->qu.ast); + ast_free(ast->qu.ast); + break; + default: assert(false); } @@ -44,32 +54,36 @@ AST* ast_copy(const AST *ast){ assert(ast); switch(ast->type){ case AST_LIST:{ - assert(ast->l.len>=0); - assert(ast->l.nodes); - AST **nodes=malloc(ast->l.len,AST*); - for(int i=0;il.len;i++)nodes[i]=ast_copy(ast->l.nodes[i]); - AST *l=ast_list(ast->l.len,nodes); - l->l.quoted=ast->l.quoted; - return l; + assert(ast->li.len>=0); + assert(ast->li.nodes); + AST **nodes=malloc(ast->li.len,AST*); + for(int i=0;ili.len;i++)nodes[i]=ast_copy(ast->li.nodes[i]); + return ast_list(ast->li.len,nodes); } + case AST_LAMBDA: + return ast_lambda(ast->la.cfunc,ast->la.body?ast_copy(ast->la.body):NULL); + case AST_WORD: - assert(ast->w.word); - return ast_word(copystring(ast->w.word)); + assert(ast->wo.word); + return ast_word(copystring(ast->wo.word)); case AST_NUMBER: - return ast_number(ast->n.num); + return ast_number(ast->nu.num); case AST_STRING: - return ast_string(copybufasstring(ast->S.str,ast->S.len),ast->S.len); + return ast_string(copybufasstring(ast->st.str,ast->st.len),ast->st.len); case AST_SYMBOL:{ - assert(ast->s.name); - AST *sym=ast_symbol(ast->s.name); - sym->s.symid=ast->s.symid; + assert(ast->sy.name); + AST *sym=ast_symbol(ast->sy.name); + sym->sy.symid=ast->sy.symid; return sym; } + case AST_QUOTED: + return ast_quoted(ast_copy(ast->qu.ast)); + default: assert(false); } @@ -114,22 +128,21 @@ static void ast_stringify_(const AST *ast,Buffer *buf){ assert(buf); switch(ast->type){ case AST_LIST: - if(ast->l.quoted)buf_append(buf,"'",1); buf_append(buf,"(",1); - for(int i=0;il.len;i++){ + for(int i=0;ili.len;i++){ if(i!=0)buf_append(buf," ",1); - ast_stringify_(ast->l.nodes[i],buf); + ast_stringify_(ast->li.nodes[i],buf); } buf_append(buf,")",1); break; case AST_WORD: - buf_append(buf,ast->w.word,strlen(ast->w.word)); + buf_append(buf,ast->wo.word,strlen(ast->wo.word)); break; case AST_NUMBER:{ char *s; - int len=asprintf(&s,"%g",ast->n.num); + int len=asprintf(&s,"%g",ast->nu.num); if(!s)outofmem(); buf_append(buf,s,len); free(s); @@ -138,8 +151,8 @@ static void ast_stringify_(const AST *ast,Buffer *buf){ case AST_STRING:{ buf_append(buf,"\"",1); - const char *str=ast->S.str; - for(int i=0;iS.len;i++){ + const char *str=ast->st.str; + for(int i=0;ist.len;i++){ if(str[i]>=32&&str[i]<=126)buf_append(buf,str+i,1); else switch(str[i]){ case '\n': buf_append(buf,"\\n",2); break; @@ -164,7 +177,12 @@ static void ast_stringify_(const AST *ast,Buffer *buf){ case AST_SYMBOL: buf_append(buf,"'",1); - buf_append(buf,ast->s.name,strlen(ast->s.name)); + buf_append(buf,ast->sy.name,strlen(ast->sy.name)); + break; + + case AST_QUOTED: + buf_append(buf,"'",1); + ast_stringify_(ast->qu.ast,buf); break; default: @@ -185,10 +203,17 @@ AST* ast_list(int len,AST **nodes){ assert(nodes); AST *ast=malloc(1,AST); ast->type=AST_LIST; - ast->l.len=len; - ast->l.nodes=malloc(len,AST*); - memcpy(ast->l.nodes,nodes,len*sizeof(AST*)); - ast->l.quoted=false; + ast->li.len=len; + ast->li.nodes=nodes; + return ast; +} + +AST* ast_lambda(lambdafunc_t cfunc,AST *body){ + assert(cfunc||body); + AST *ast=malloc(1,AST); + ast->type=AST_LAMBDA; + ast->la.cfunc=cfunc; + ast->la.body=body; return ast; } @@ -196,22 +221,22 @@ AST* ast_word(char *word){ assert(word); AST *ast=malloc(1,AST); ast->type=AST_WORD; - ast->w.word=word; + ast->wo.word=word; return ast; } AST* ast_number(double num){ AST *ast=malloc(1,AST); ast->type=AST_NUMBER; - ast->n.num=num; + ast->nu.num=num; return ast; } AST* ast_string(char *str,int len){ AST *ast=malloc(1,AST); ast->type=AST_STRING; - ast->S.str=str; - ast->S.len=len; + ast->st.str=str; + ast->st.len=len; return ast; } @@ -219,7 +244,15 @@ AST* ast_symbol(char *name){ assert(name); AST *ast=malloc(1,AST); ast->type=AST_SYMBOL; - ast->s.name=name; - ast->s.symid=-1; + ast->sy.name=name; + ast->sy.symid=-1; + return ast; +} + +AST* ast_quoted(AST *contents){ + assert(contents); + AST *ast=malloc(1,AST); + ast->type=AST_QUOTED; + ast->qu.ast=contents; return ast; } diff --git a/ast.h b/ast.h index 8d23ef9..6ec6ce8 100644 --- a/ast.h +++ b/ast.h @@ -2,24 +2,40 @@ #include +typedef struct InterState InterState; +typedef struct InterRet InterRet; +typedef struct AST AST; + +typedef InterRet (*lambdafunc_t)(InterState *is,int nargs,AST **args); + typedef enum ASTtype{ AST_LIST, + AST_LAMBDA, + AST_LAMBDAARG, AST_WORD, AST_NUMBER, AST_STRING, AST_SYMBOL, + AST_QUOTED, } ASTtype; -typedef struct AST AST; - typedef struct ASTlist{ int len; AST **nodes; - bool quoted; } ASTlist; +typedef struct ASTlambda{ + //exactly one is non-NULL + lambdafunc_t cfunc; + AST *body; +} ASTlambda; + +typedef struct ASTlambdaArg{ + int idx; +} ASTlambdaArg; + typedef struct ASTword{ char *word; } ASTword; @@ -42,14 +58,21 @@ typedef struct ASTsymbol{ //You should probably use ast_symbol(), in which case you don't have to do anything. } ASTsymbol; +typedef struct ASTquoted{ + AST *ast; +} ASTquoted; + struct AST{ ASTtype type; union { - ASTlist l; - ASTword w; - ASTnumber n; - ASTstring S; - ASTsymbol s; + ASTlist li; + ASTlambda la; + ASTlambdaArg ar; + ASTword wo; + ASTnumber nu; + ASTstring st; + ASTsymbol sy; + ASTquoted qu; }; }; @@ -61,7 +84,9 @@ AST* ast_copy(const AST *ast); char* ast_stringify(const AST *ast); AST* ast_list(int len,AST **nodes); //these convenience functions DO NOT copy their arguments +AST* ast_lambda(lambdafunc_t cfunc,AST *body); AST* ast_word(char *word); AST* ast_number(double num); AST* ast_string(char *str,int len); AST* ast_symbol(char *name); +AST* ast_quoted(AST *ast); diff --git a/code.lysp b/code.lysp index 47a0268..f509404 100644 --- a/code.lysp +++ b/code.lysp @@ -1,7 +1,11 @@ -(print - (+ 1 (% 10 3)) - () - '( #| dit is commentaar|# ()) - (('())) - 'kaas ;meer commentaar - "kazen enzo") +(do + (print 42) + (print + (+ 1 (% 10 3)) + () + '( #| dit is commentaar|# ()) + '(('())) + '''"hoi" + '''''(dit is quoted) + 'kaas ;meer commentaar + "kazen enzo")) \ No newline at end of file diff --git a/inter_builtins.c b/inter_builtins.c new file mode 100644 index 0000000..cc96afd --- /dev/null +++ b/inter_builtins.c @@ -0,0 +1,60 @@ +#include +#include +#include + +#include "inter_builtins.h" +#include "interpreter.h" +#include "util.h" + +InterRet builtin_do(InterState *is,int nargs,AST **args){ + assert(args); + InterRet ir; + for(int i=0;i0)putchar(' '); + printf("%s",s); + free(s); + } + putchar('\n'); + return ir_ast(ast_list(0,malloc(1,AST*))); +} + +#define BUILTIN_ARITH_OP(op,name,defval,expr) \ + InterRet builtin_##name(InterState *is,int nargs,AST **args){ \ + (void)is; \ + assert(args); \ + if(nargs==0)return ir_ast(ast_number(defval)); \ + for(int i=0;itype!=AST_NUMBER){ \ + return ir_err_c("Non-number argument passed to builtin '" #op "'"); \ + } \ + } \ + double res=args[0]->nu.num; \ + for(int i=1;inu.num; \ + res=expr; \ + } \ + return ir_ast(ast_number(res)); \ + } + +BUILTIN_ARITH_OP(+,sum,0,res+n) +BUILTIN_ARITH_OP(-,difference,0,res-n) +BUILTIN_ARITH_OP(*,product,1,res*n) +BUILTIN_ARITH_OP(/,quotient,1,res/n) +BUILTIN_ARITH_OP(%,remainder,1,floatmod(res,n)) + +#undef BUILTIN_ARITH_OP diff --git a/inter_builtins.h b/inter_builtins.h new file mode 100644 index 0000000..6dc935d --- /dev/null +++ b/inter_builtins.h @@ -0,0 +1,13 @@ +#pragma once + +#include "ast.h" + +typedef struct InterRet InterRet; + +InterRet builtin_do(InterState *is,int nargs,AST **args); +InterRet builtin_print(InterState *is,int nargs,AST **args); +InterRet builtin_sum(InterState *is,int nargs,AST **args); +InterRet builtin_difference(InterState *is,int nargs,AST **args); +InterRet builtin_product(InterState *is,int nargs,AST **args); +InterRet builtin_quotient(InterState *is,int nargs,AST **args); +InterRet builtin_remainder(InterState *is,int nargs,AST **args); diff --git a/interpreter.c b/interpreter.c index 333b8c9..05e5d2c 100644 --- a/interpreter.c +++ b/interpreter.c @@ -4,6 +4,7 @@ #include #include "interpreter.h" +#include "inter_builtins.h" #include "util.h" @@ -85,36 +86,148 @@ void inter_destroy(InterState *is){ static void intern_symbols(InterState *is,AST *ast){ switch(ast->type){ case AST_LIST: - for(int i=0;il.len;i++)intern_symbols(is,ast->l.nodes[i]); + for(int i=0;ili.len;i++)intern_symbols(is,ast->li.nodes[i]); break; case AST_SYMBOL:{ - if(ast->s.symid>=0&&ast->s.symidss.len&&strcmp(ast->s.name,is->ss.syms[ast->s.symid])==0){ + if(ast->sy.symid>=0&&ast->sy.symidss.len&&strcmp(ast->sy.name,is->ss.syms[ast->sy.symid])==0){ break; } int i; for(i=0;iss.len;i++){ - if(strcmp(is->ss.syms[i],ast->s.name)==0)break; + if(strcmp(is->ss.syms[i],ast->sy.name)==0)break; } if(iss.len){ - ast->s.symid=i; + ast->sy.symid=i; break; } if(is->ss.len==is->ss.sz){ is->ss.sz*=2; is->ss.syms=realloc(is->ss.syms,is->ss.sz,char*); } - is->ss.syms[is->ss.len++]=copystring(ast->s.name); + is->ss.syms[is->ss.len++]=copystring(ast->sy.name); break; } + case AST_QUOTED: + intern_symbols(is,ast->qu.ast); + break; + case AST_WORD: case AST_NUMBER: case AST_STRING: break; + + default: + assert(false); + } +} + +static const AST* find_var(const InterState *is,const char *name){ + int h=namehash(name,VMAP_HASHSZ); + for(const Scope *scope=is->scope;scope;scope=scope->next){ + for(const Vllist *ll=scope->vmap[h];ll;ll=ll->next){ + if(strcmp(name,ll->name)==0)return ll->value; + } + } + return NULL; +} + +InterRet ir_ast(AST *ast){ + InterRet ir={ast,NULL}; + return ir; +} + +InterRet ir_err(char *errstr){ + InterRet ir={NULL,errstr}; + return ir; +} + +InterRet ir_err_c(const char *errstr){ + return ir_err(copystring(errstr)); +} + +static InterRet interpret(InterState *is,const AST *ast){ + switch(ast->type){ + case AST_LIST:{ + if(ast->li.len==0){ + return ir_ast(ast_copy(ast)); + } + assert(ast->li.len>0); + AST *nodes[ast->li.len]; + for(int i=0;ili.len;i++){ + InterRet ir=interpret(is,ast->li.nodes[i]);; + if(ir.errstr){ + while(i-->0)ast_free(nodes[i]); + return ir; + } + nodes[i]=ir.ast; + } + + if(nodes[0]->type!=AST_LAMBDA){ + fprintf(stderr,"type = %d\n",nodes[0]->type); + return ir_err_c("First node in evaluated list not a function"); + } + +#define NOT_IMPLEMENTED false + if(nodes[0]->la.body)assert(NOT_IMPLEMENTED); + + return nodes[0]->la.cfunc(is,ast->li.len-1,nodes+1); + } + + case AST_SYMBOL: + return ir_ast(ast_copy(ast)); + + case AST_WORD:{ + const AST *cv=find_var(is,ast->wo.word); + if(cv)return ir_ast(ast_copy(cv)); + char *errstr; + asprintf(&errstr,"Unknown variable '%s'",ast->wo.word); + if(!errstr)outofmem(); + return ir_err(errstr); + } + + case AST_NUMBER: + return ir_ast(ast_copy(ast)); + + case AST_STRING: + return ir_ast(ast_copy(ast)); + + case AST_QUOTED: + return ir_ast(ast_copy(ast->qu.ast)); + + default: + assert(false); } } -void inter_runcode(InterState *is,AST *ast){ +void inter_register(InterState *is,const char *name,lambdafunc_t cfunc){ + assert(is->scope); + int h=namehash(name,VMAP_HASHSZ); + Vllist *ll=malloc(1,Vllist); + ll->name=copystring(name); + ll->value=ast_lambda(cfunc,NULL); + ll->next=is->scope->vmap[h]; + is->scope->vmap[h]=ll; +} + +void inter_register_prelude(InterState *is){ + inter_register(is,"do",builtin_do); + inter_register(is,"print",builtin_print); + inter_register(is,"+",builtin_sum); + inter_register(is,"-",builtin_difference); + inter_register(is,"*",builtin_product); + inter_register(is,"/",builtin_quotient); + inter_register(is,"%",builtin_remainder); + inter_register(is,"sum",builtin_sum); + inter_register(is,"difference",builtin_difference); + inter_register(is,"product",builtin_product); + inter_register(is,"quotient",builtin_quotient); + inter_register(is,"remainder",builtin_remainder); +} + +InterRet inter_runcode(InterState *is,AST *ast){ intern_symbols(is,ast); + + return interpret(is,ast); } diff --git a/interpreter.h b/interpreter.h index e643494..4434de2 100644 --- a/interpreter.h +++ b/interpreter.h @@ -3,8 +3,22 @@ #include "ast.h" +typedef struct InterRet{ + // Exactly one of ast and errstr is non-NULL. The non-NULL member + // needs to be free'd. + AST *ast; + char *errstr; +} InterRet; + +InterRet ir_ast(AST *ast); +InterRet ir_err(char *errstr); +InterRet ir_err_c(const char *errstr); + + typedef struct InterState InterState; InterState* inter_make(void); void inter_destroy(InterState *is); -void inter_runcode(InterState *is,AST *ast); //updates symbol id's +void inter_register(InterState *is,const char *name,lambdafunc_t cfunc); +void inter_register_prelude(InterState *is); +InterRet inter_runcode(InterState *is,AST *ast); //updates symbol id's diff --git a/main.c b/main.c index 239e938..fefeafc 100644 --- a/main.c +++ b/main.c @@ -3,6 +3,7 @@ #include #include +#include "interpreter.h" #include "parser.h" #include "util.h" @@ -82,5 +83,20 @@ int main(int argc,char **argv){ char *s=ast_stringify(pr.ast); printf("%s\n",s); free(s); + + InterState *is=inter_make(); + inter_register_prelude(is); + InterRet ir=inter_runcode(is,pr.ast); + if(ir.errstr){ + fprintf(stderr,"\x1B[1;31m%s\x1B[0m\n",ir.errstr); + free(ir.errstr); + return 1; + } + s=ast_stringify(ir.ast); + printf("%s\n",s); + free(s); + ast_free(ir.ast); + inter_destroy(is); + ast_free(pr.ast); } diff --git a/parser.c b/parser.c index 910f3da..d9f4543 100644 --- a/parser.c +++ b/parser.c @@ -28,7 +28,7 @@ typedef struct Token{ int len; } Token; -#define SYMBOLCHARS "()[]" +#define SYMBOLCHARS "'()[]" static Token tt_make(Tokentype type,const char *str,int len){ @@ -92,8 +92,7 @@ static Token nexttoken(Cursor *cursor){ while(cursor->l>=1&&isspace(*cursor->s))advance(cursor,1); if(cursor->l==0)return tt_eof(); - if(strchr(SYMBOLCHARS,*cursor->s)!=NULL|| - (cursor->l>=2&&cursor->s[0]=='\''&&strchr(SYMBOLCHARS,cursor->s[1]))){ + if(strchr(SYMBOLCHARS,*cursor->s)!=NULL){ advance(cursor,1); return tt_make(TT_SYMBOL,cursor->s-1,1); } @@ -174,13 +173,17 @@ static ParseRet parse_(Cursor *cursor){ case TT_SYMBOL:{ char closing; if(tok.len!=1)assert(false); - bool quoted=false; if(tok.str[0]=='\''){ - quoted=true; - tok=nexttoken(cursor); - if(tok.type!=TT_SYMBOL||tok.len!=1||(tok.str[0]!='('&&tok.str[0]!='[')){ - return pr_err_c("Single quote symbol not before paren"); + ParseRet pr=parse_(cursor); + if(pr.errstr)return pr; + if(pr.ast->type==AST_WORD){ + char *word=pr.ast->wo.word; + pr.ast->type=AST_SYMBOL; + pr.ast->sy.name=word; + pr.ast->sy.symid=-1; + return pr; } + return pr_ast(ast_quoted(pr.ast)); } if(tok.str[0]=='(')closing=')'; @@ -216,9 +219,7 @@ static ParseRet parse_(Cursor *cursor){ } nodes[len++]=pr.ast; } - AST *l=ast_list(len,nodes); - l->l.quoted=quoted; - return pr_ast(l); + return pr_ast(ast_list(len,nodes)); } case TT_WORD: diff --git a/util.c b/util.c index d6890d6..d598f17 100644 --- a/util.c +++ b/util.c @@ -1,6 +1,7 @@ #include #include #include +#include #include "util.h" @@ -26,6 +27,14 @@ __attribute__((noreturn)) void outofmem(void){ } +double floatmod(double a,double b){ + if(b==0)return nan(""); + int sa=a<0?-1:1; + a=fabs(a); b=fabs(b); + return sa*(a-b*floor(a/b)); +} + + void* malloccheck(size_t n){ void *p=mallocreal(n); if(!p)outofmem(); diff --git a/util.h b/util.h index d2f18c3..1835aa2 100644 --- a/util.h +++ b/util.h @@ -17,6 +17,8 @@ char* copybufasstring(const char *b,int length); void outofmem(void) __attribute__((noreturn)); +double floatmod(double a,double b); + void* malloccheck(size_t n); void* calloccheck(size_t n,size_t s); void* realloccheck(void *p,size_t n); -- cgit v1.2.3