summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authortomsmeding <tom.smeding@gmail.com>2016-08-23 20:58:50 +0200
committertomsmeding <tom.smeding@gmail.com>2016-08-23 20:58:50 +0200
commitcac651cd88f8da1e5957b0cc13fa25d79e1887fc (patch)
tree38b2645803df92661b797a64f18772e691d3d8fd
parent44602cb35735575c15cfcb92779337778649df8a (diff)
Many things
- two-letter AST union members - AST_QUOTED - AST_LAMBDA - an interpreter that works - function registering in the interpreter - some builtins
-rw-r--r--ast.c113
-rw-r--r--ast.h41
-rw-r--r--code.lysp18
-rw-r--r--inter_builtins.c60
-rw-r--r--inter_builtins.h13
-rw-r--r--interpreter.c125
-rw-r--r--interpreter.h16
-rw-r--r--main.c16
-rw-r--r--parser.c23
-rw-r--r--util.c9
-rw-r--r--util.h2
11 files changed, 363 insertions, 73 deletions
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;i<ast->l.len;i++){
- assert(ast->l.nodes[i]);
- ast_free(ast->l.nodes[i]);
+ assert(ast->li.len>=0);
+ for(int i=0;i<ast->li.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;i<ast->l.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;i<ast->li.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;i<ast->l.len;i++){
+ for(int i=0;i<ast->li.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;i<ast->S.len;i++){
+ const char *str=ast->st.str;
+ for(int i=0;i<ast->st.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 <stdbool.h>
+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 <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#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;i<nargs;i++){
+ assert(args[i]);
+ ir=inter_runcode(is,args[i]);
+ if(ir.errstr)return ir;
+ if(i<nargs-1)ast_free(ir.ast);
+ }
+ return ir;
+}
+
+InterRet builtin_print(InterState *is,int nargs,AST **args){
+ (void)is;
+ assert(args);
+ for(int i=0;i<nargs;i++){
+ assert(args[i]);
+ char *s=ast_stringify(args[i]);
+ if(i>0)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;i<nargs;i++){ \
+ assert(args[i]); \
+ if(args[i]->type!=AST_NUMBER){ \
+ return ir_err_c("Non-number argument passed to builtin '" #op "'"); \
+ } \
+ } \
+ double res=args[0]->nu.num; \
+ for(int i=1;i<nargs;i++){ \
+ double n=args[i]->nu.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 <assert.h>
#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;i<ast->l.len;i++)intern_symbols(is,ast->l.nodes[i]);
+ for(int i=0;i<ast->li.len;i++)intern_symbols(is,ast->li.nodes[i]);
break;
case AST_SYMBOL:{
- if(ast->s.symid>=0&&ast->s.symid<is->ss.len&&strcmp(ast->s.name,is->ss.syms[ast->s.symid])==0){
+ if(ast->sy.symid>=0&&ast->sy.symid<is->ss.len&&strcmp(ast->sy.name,is->ss.syms[ast->sy.symid])==0){
break;
}
int i;
for(i=0;i<is->ss.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(i<is->ss.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;i<ast->li.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 <string.h>
#include <assert.h>
+#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 <stdio.h>
#include <stdlib.h>
#include <string.h>
+#include <math.h>
#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);