Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ulowell!page From: page@swan.ulowell.edu (Bob Page) Newsgroups: comp.sources.amiga Subject: v89i078: siod - small lisp interpreter Message-ID: <12301@swan.ulowell.edu> Date: 16 Mar 89 20:16:56 GMT Organization: University of Lowell, Computer Science Dept. Lines: 1550 Approved: page@swan.ulowell.edu Submitted-by: gjc@bu-it.BU.EDU (George Carrette) Posting-number: Volume 89, Issue 78 Archive-name: languages/siod.1 siod - Scheme In One Defun. Siod is a very small scheme interpreter which can be used for short calculations or included as a command interpreter or extension/macro language in other applications. [executable not supplied. ..Bob] # This is a shell archive. # Remove everything above and including the cut line. # Then run the rest of the file through sh. #----cut here-----cut here-----cut here-----cut here----# #!/bin/sh # shar: Shell Archiver # Run the following text with /bin/sh to create: # makefile # siod.c # siod.doc # siod.n # siod.scm # This archive created: Thu Mar 16 15:09:01 1989 cat << \SHAR_EOF > makefile # Note: add the -f68881 flag if you are on a SUN III. siod: siod.c cc -O -o siod siod.c SHAR_EOF cat << \SHAR_EOF > siod.c /* Scheme In One Defun, but in C this time. (c) Copyright 1988 George Carrette, gjc@bu-it.bu.edu For demonstration purposes only. If your interests run to practical applications of symbolic programming techniques, in LISP, Macsyma, C, or other language: Paradigm Associates Inc Phone: 617-492-6079 29 Putnam Ave, Suite 6 Cambridge, MA 02138 Release 1.0: 24-APR-88 Release 1.1: 25-APR-88, added: macros, predicates, load. With additions by Barak.Pearlmutter@DOGHEN.BOLTZ.CS.CMU.EDU: Full flonum recognizer, cleaned up uses of NULL/0. Now distributed with siod.scm. Release 1.2: 28-APR-88, name changes as requested by JAR@AI.AI.MIT.EDU, plus some bug fixes. Release 1.3: 1-MAY-88, changed env to use frames instead of alist. define now works properly. vms specific function edit. This example is small, has a garbage collector, and can run a good deal of the code in Structure and Interpretation of Computer Programs. (Start it up with the siod.scm file for more features). Replacing the evaluator with an explicit control "flat-coded" one as in chapter 5 would allow garbage collection to take place at any time, not just at toplevel in the read-eval-print loop, as herein implemented. This is left as an exersize for the reader. Techniques used will be familiar to most lisp implementors. Having objects be all the same size, and having only two statically allocated spaces simplifies and speeds up both consing and gc considerably. The MSUBR hack allows for a modular implementation of tail recursion, an extension of the FSUBR that is, as far as I know, original. Error handling is rather crude. A topic taken with machine fault, exception handling, tracing, debugging, and state recovery which we could cover in detail, but clearly beyond the scope of this implementation. Suffice it to say that if you have a good symbolic debugger you can set a break point at "err" and observe in detail all the arguments and local variables of the procedures in question, since there is no ugly "casting" of data types. If X is an offending or interesting object then examining X->type will give you the type, and X->storage_as.cons will show the car and the cdr. */ #include #include #include #include #include #include struct obj {short gc_mark; short type; union {struct {struct obj * car; struct obj * cdr;} cons; struct {double data;} flonum; struct {char *pname; struct obj * vcell;} symbol; struct {char *name; struct obj * (*f)();} subr; struct {struct obj *env; struct obj *code;} closure;} storage_as;}; #define CAR(x) ((*x).storage_as.cons.car) #define CDR(x) ((*x).storage_as.cons.cdr) #define PNAME(x) ((*x).storage_as.symbol.pname) #define VCELL(x) ((*x).storage_as.symbol.vcell) #define SUBRF(x) (*((*x).storage_as.subr.f)) #define FLONM(x) ((*x).storage_as.flonum.data) struct obj *heap_1; struct obj *heap_2; struct obj *heap,*heap_end,*heap_org; long heap_size = 5000; long old_heap_used; int which_heap; int gc_status_flag = 1; char *init_file = (char *) NULL; #define TKBUFFERN 100 char tkbuffer[TKBUFFERN]; jmp_buf errjmp; int errjmp_ok = 0; int nointerrupt = 1; struct obj *cons(), *car(), *cdr(), *setcar(), *setcdr(),*consp(); struct obj *symcons(),*rintern(),*cintern(),*cintern_soft(),*symbolp(); struct obj *flocons(),*plus(),*ltimes(),*difference(),*quotient(); struct obj *greaterp(),*lessp(),*eq(),*eql(),*numberp(); struct obj *assq(); struct obj *lread(),*leval(),*lprint(),*lprin1(); struct obj *lreadr(),*lreadparen(),*lreadtk(),*lreadf(); struct obj *subrcons(),*closure(); struct obj *leval_define(),*leval_lambda(),*leval_if(); struct obj *leval_progn(),*leval_setq(),*leval_let(),*let_macro(); struct obj *leval_args(),*extend_env(),*setvar(); struct obj *leval_quote(),*leval_and(),*leval_or(); struct obj *oblistfn(),*copy_list(); struct obj *gc_relocate(),*get_newspace(),*gc_status(); struct obj *vload(),*load(); struct obj *leval_tenv(),*lerr(),*quit(),*nullp(); struct obj *symbol_boundp(),*symbol_value(); struct obj *envlookup(),*arglchk(),*sys_edit(),*reverse(); int handle_sigfpe(); int handle_sigint(); #define NIL ((struct obj *) 0) #define EQ(x,y) ((x) == (y)) #define NEQ(x,y) ((x) != (y)) #define NULLP(x) EQ(x,NIL) #define NNULLP(x) NEQ(x,NIL) #define TYPE(x) (((x) == NIL) ? 0 : ((*(x)).type)) #define TYPEP(x,y) (TYPE(x) == (y)) #define NTYPEP(x,y) (TYPE(x) != (y)) #define tc_nil 0 #define tc_cons 1 #define tc_flonum 2 #define tc_symbol 3 #define tc_subr_0 4 #define tc_subr_1 5 #define tc_subr_2 6 #define tc_subr_3 7 #define tc_lsubr 8 #define tc_fsubr 9 #define tc_msubr 10 #define tc_closure 11 init_subrs() {init_subr("cons",tc_subr_2,cons); init_subr("car",tc_subr_1,car); init_subr("cdr",tc_subr_1,cdr); init_subr("set-car!",tc_subr_2,setcar); init_subr("set-cdr!",tc_subr_2,setcdr); init_subr("+",tc_subr_2,plus); init_subr("-",tc_subr_2,difference); init_subr("*",tc_subr_2,ltimes); init_subr("/",tc_subr_2,quotient); init_subr(">",tc_subr_2,greaterp); init_subr("<",tc_subr_2,lessp); init_subr("eq?",tc_subr_2,eq); init_subr("eqv?",tc_subr_2,eql); init_subr("assq",tc_subr_2,assq); init_subr("read",tc_subr_0,lread); init_subr("print",tc_subr_1,lprint); init_subr("eval",tc_subr_2,leval); init_subr("define",tc_fsubr,leval_define); init_subr("lambda",tc_fsubr,leval_lambda); init_subr("if",tc_msubr,leval_if); init_subr("begin",tc_msubr,leval_progn); init_subr("set!",tc_fsubr,leval_setq); init_subr("or",tc_msubr,leval_or); init_subr("and",tc_msubr,leval_and); init_subr("quote",tc_fsubr,leval_quote); init_subr("oblist",tc_subr_0,oblistfn); init_subr("copy-list",tc_subr_1,copy_list); init_subr("gc-status",tc_lsubr,gc_status); init_subr("load",tc_subr_1,load); init_subr("pair?",tc_subr_1,consp); init_subr("symbol?",tc_subr_1,symbolp); init_subr("number?",tc_subr_1,numberp); init_subr("let-internal",tc_msubr,leval_let); init_subr("let-internal-macro",tc_subr_1,let_macro); init_subr("symbol-bound?",tc_subr_2,symbol_boundp); init_subr("symbol-value",tc_subr_2,symbol_value); init_subr("set-symbol-value!",tc_subr_3,setvar); init_subr("the-environment",tc_fsubr,leval_tenv); init_subr("error",tc_subr_2,lerr); init_subr("quit",tc_subr_0,quit); init_subr("not",tc_subr_1,nullp); init_subr("null?",tc_subr_1,nullp); init_subr("env-lookup",tc_subr_2,envlookup); #ifdef vms init_subr("edit",tc_subr_1,sys_edit); #endif init_subr("reverse",tc_subr_1,reverse); } struct obj *oblist = NIL; struct obj *truth = NIL; struct obj *eof_val = NIL; struct obj *sym_errobj = NIL; struct obj *sym_progn = NIL; struct obj *sym_lambda = NIL; struct obj *sym_quote = NIL; struct obj *open_files = NIL; struct obj *unbound_marker = NIL; scan_registers() {oblist = gc_relocate(oblist); eof_val = gc_relocate(eof_val); truth = gc_relocate(truth); sym_errobj = gc_relocate(sym_errobj); sym_progn = gc_relocate(sym_progn); sym_lambda = gc_relocate(sym_lambda); sym_quote = gc_relocate(sym_quote); open_files = gc_relocate(open_files); unbound_marker = gc_relocate(unbound_marker);} main(argc,argv) int argc; char **argv; {printf("Welcome to SIOD, Scheme In One Defun, Version 1.3\n"); printf("(C) Copyright 1988, George Carrette\n"); process_cla(argc,argv); printf("heap_size = %d cells, %d bytes\n", heap_size,heap_size*sizeof(struct obj)); init_storage(); printf("heap_1 at 0x%X, heap_2 at 0x%X\n",heap_1,heap_2); repl_driver(); printf("EXIT\n");} process_cla(argc,argv) int argc; char **argv; {int k; for(k=1;k #include struct tms time_buffer; double myruntime(){times(&time_buffer);return(time_buffer.tms_utime/60.0);} #endif #endif #else #ifdef vms #include double myruntime(){return(clock() * 1.0e-2);} #include struct obj * sys_edit(fname) struct obj *fname; {struct dsc$descriptor_s d; if NTYPEP(fname,tc_symbol) err("filename not a symbol",fname); d.dsc$b_dtype = DSC$K_DTYPE_T; d.dsc$b_class = DSC$K_CLASS_S; d.dsc$w_length = strlen(PNAME(fname)); d.dsc$a_pointer = PNAME(fname); nointerrupt = 1; edt$edit(&d); nointerrupt = 0; return(fname);} #else double myruntime(){long x;long time();time(&x);return(x);} #endif #endif handle_sigfpe(sig,code,scp) int sig,code; struct sigcontext *scp; {signal(SIGFPE,handle_sigfpe); err("floating point exception",NIL);} handle_sigint(sig,code,scp) int sig,code; struct sigcontext *scp; {signal(SIGINT,handle_sigint); if (nointerrupt == 0) err("control-c interrupt",NIL); printf("interrupts disabled\n");} repl() {struct obj *x,*cw; double rt; while(1) {if ((gc_status_flag) || heap >= heap_end) {rt = myruntime(); gc(); printf("GC took %g seconds, %d compressed to %d, %d free\n", myruntime()-rt,old_heap_used,heap-heap_org,heap_end-heap);} printf("> "); x = lread(); if EQ(x,eof_val) break; rt = myruntime(); cw = heap; x = leval(x,NIL); printf("Evaluation took %g seconds %d cons work\n", myruntime()-rt,heap-cw); lprint(x);}} err(message,x) char *message; struct obj *x; {nointerrupt = 1; if NNULLP(x) printf("ERROR: %s (see errobj)\n",message); else printf("ERROR: %s\n",message); if (errjmp_ok == 1) {setvar(sym_errobj,x,NIL); longjmp(errjmp,1);} printf("FATAL ERROR DURING STARTUP OR CRITICAL CODE SECTION\n"); exit(1);} struct obj * lerr(message,x) struct obj *message,*x; {if NTYPEP(message,tc_symbol) err("argument to error not a symbol",message); err(PNAME(message),x); return(NIL);} struct obj * cons(x,y) struct obj *x,*y; {register struct obj *z; if ((z = heap) >= heap_end) err("ran out of storage",NIL); heap = z+1; (*z).gc_mark = 0; (*z).type = tc_cons; CAR(z) = x; CDR(z) = y; return(z);} struct obj * consp(x) struct obj *x; {if TYPEP(x,tc_cons) return(truth); else return(NIL);} struct obj * car(x) struct obj *x; {switch TYPE(x) {case tc_nil: return(NIL); case tc_cons: return(CAR(x)); default: err("wta to car",x);}} struct obj * cdr(x) struct obj *x; {switch TYPE(x) {case tc_nil: return(NIL); case tc_cons: return(CDR(x)); default: err("wta to cdr",x);}} struct obj * setcar(cell,value) struct obj *cell,*value; {if NTYPEP(cell,tc_cons) err("wta to setcar",cell); return(CAR(cell) = value);} struct obj * setcdr(cell,value) struct obj *cell,*value; {if NTYPEP(cell,tc_cons) err("wta to setcdr",cell); return(CDR(cell) = value);} struct obj * flocons(x) double x; {register struct obj *z; if ((z = heap) >= heap_end) err("ran out of storage",NIL); heap = z+1; (*z).gc_mark = 0; (*z).type = tc_flonum; (*z).storage_as.flonum.data = x; return(z);} struct obj * numberp(x) struct obj *x; {if TYPEP(x,tc_flonum) return(truth); else return(NIL);} struct obj * plus(x,y) struct obj *x,*y; {if NTYPEP(x,tc_flonum) err("wta(1st) to plus",x); if NTYPEP(y,tc_flonum) err("wta(2nd) to plus",y); return(flocons(FLONM(x)+FLONM(y)));} struct obj * ltimes(x,y) struct obj *x,*y; {if NTYPEP(x,tc_flonum) err("wta(1st) to times",x); if NTYPEP(y,tc_flonum) err("wta(2nd) to times",y); return(flocons(FLONM(x)*FLONM(y)));} struct obj * difference(x,y) struct obj *x,*y; {if NTYPEP(x,tc_flonum) err("wta(1st) to difference",x); if NTYPEP(y,tc_flonum) err("wta(2nd) to difference",y); return(flocons(FLONM(x)-FLONM(y)));} struct obj * quotient(x,y) struct obj *x,*y; {if NTYPEP(x,tc_flonum) err("wta(1st) to quotient",x); if NTYPEP(y,tc_flonum) err("wta(2nd) to quotient",y); return(flocons(FLONM(x)/FLONM(y)));} struct obj * greaterp(x,y) struct obj *x,*y; {if NTYPEP(x,tc_flonum) err("wta(1st) to greaterp",x); if NTYPEP(y,tc_flonum) err("wta(2nd) to greaterp",y); if (FLONM(x)>FLONM(y)) return(truth); return(NIL);} struct obj * lessp(x,y) struct obj *x,*y; {if NTYPEP(x,tc_flonum) err("wta(1st) to lessp",x); if NTYPEP(y,tc_flonum) err("wta(2nd) to lessp",y); if (FLONM(x)= heap_end) err("ran out of storage",NIL); heap = z+1; (*z).gc_mark = 0; (*z).type = tc_symbol; PNAME(z) = pname; VCELL(z) = vcell; return(z);} struct obj * symbolp(x) struct obj *x; {if TYPEP(x,tc_symbol) return(truth); else return(NIL);} struct obj * symbol_boundp(x,env) struct obj *x,*env; {struct obj *tmp; if NTYPEP(x,tc_symbol) err("not a symbol",x); tmp = envlookup(x,env); if NNULLP(tmp) return(truth); if EQ(VCELL(x),unbound_marker) return(NIL); else return(truth);} struct obj * symbol_value(x,env) struct obj *x,*env; {struct obj *tmp; if NTYPEP(x,tc_symbol) err("not a symbol",x); tmp = envlookup(x,env); if NNULLP(tmp) return(CAR(tmp)); tmp = VCELL(x); if EQ(tmp,unbound_marker) err("unbound variable",x); return(tmp);} struct obj * cintern_soft(name) char *name; {struct obj *l; for(l=oblist;NNULLP(l);l=CDR(l)) if (strcmp(name,PNAME(CAR(l))) == 0) return(CAR(l)); return(NIL);} struct obj * cintern(name) char *name; {struct obj *sym; sym = cintern_soft(name); if(sym) return(sym); sym = symcons(name,unbound_marker); oblist = cons(sym,oblist); return(sym);} char * must_malloc(size) unsigned long size; {char *tmp; tmp = (char *) malloc(size); if (tmp == (char *)NULL) err("failed to allocate storage from system",NIL); return(tmp);} struct obj * rintern(name) char *name; {struct obj *sym; char *newname; sym = cintern_soft(name); if(sym) return(sym); newname = must_malloc(strlen(name)+1); strcpy(newname,name); sym = symcons(newname,unbound_marker); oblist = cons(sym,oblist); return(sym);} struct obj * subrcons(type,name,f) int type; char *name; struct obj * (*f)(); {register struct obj *z; if ((z = heap) >= heap_end) err("ran out of storage",NIL); heap = z+1; (*z).gc_mark = 0; (*z).type = type; (*z).storage_as.subr.name = name; (*z).storage_as.subr.f = f; return(z);} struct obj * closure(env,code) struct obj *env,*code; {register struct obj *z; if ((z = heap) >= heap_end) err("ran out of storage",NIL); heap = z+1; (*z).gc_mark = 0; (*z).type = tc_closure; (*z).storage_as.closure.env = env; (*z).storage_as.closure.code = code; return(z);} init_storage() {int j; heap_1 = (struct obj *)must_malloc(sizeof(struct obj)*heap_size); heap_2 = (struct obj *)must_malloc(sizeof(struct obj)*heap_size); heap = heap_1; which_heap = 1; heap_org = heap; heap_end = heap + heap_size; unbound_marker = cons(cintern("**unbound-marker**"),NIL); eof_val = cons(cintern("eof"),NIL); truth = cintern("t"); setvar(truth,truth,NIL); setvar(cintern("nil"),NIL,NIL); setvar(cintern("let"),cintern("let-internal-macro"),NIL); sym_errobj = cintern("errobj"); setvar(sym_errobj,NIL,NIL); sym_progn = cintern("begin"); sym_lambda = cintern("lambda"); sym_quote = cintern("quote"); init_subrs();} init_subr(name,type,fcn) char *name; int type; struct obj *(*fcn)(); {setvar(cintern(name),subrcons(type,name,fcn),NIL);} struct obj * assq(x,alist) struct obj *x,*alist; {register struct obj *l,*tmp; for(l=alist;TYPEP(l,tc_cons);l=CDR(l)) {tmp = CAR(l); if (TYPEP(tmp,tc_cons) && EQ(CAR(tmp),x)) return(tmp);} if EQ(l,NIL) return(NIL); err("improper list to assq",alist);} struct obj * gc_relocate(x) struct obj *x; {struct obj *new; if EQ(x,NIL) return(NIL); if ((*x).gc_mark == 1) return(CAR(x)); switch TYPE(x) {case tc_flonum: new = flocons(FLONM(x)); break; case tc_cons: new = cons(CAR(x),CDR(x)); break; case tc_symbol: new = symcons(PNAME(x),VCELL(x)); break; case tc_closure: new = closure((*x).storage_as.closure.env, (*x).storage_as.closure.code); break; case tc_subr_0: case tc_subr_1: case tc_subr_2: case tc_subr_3: case tc_lsubr: case tc_fsubr: case tc_msubr: new = subrcons(TYPE(x), (*x).storage_as.subr.name, (*x).storage_as.subr.f); break; default: err("BUG IN GARBAGE COLLECTOR gc_relocate",NIL);} (*x).gc_mark = 1; CAR(x) = new; return(new);} struct obj * get_newspace() {struct obj * newspace; if (which_heap == 1) {newspace = heap_2; which_heap = 2;} else {newspace = heap_1; which_heap = 1;} heap = newspace; heap_org = heap; heap_end = heap + heap_size; return(newspace);} scan_newspace(newspace) struct obj *newspace; {register struct obj *ptr; for(ptr=newspace; ptr < heap; ++ptr) {switch TYPE(ptr) {case tc_cons: case tc_closure: CAR(ptr) = gc_relocate(CAR(ptr)); CDR(ptr) = gc_relocate(CDR(ptr)); break; case tc_symbol: VCELL(ptr) = gc_relocate(VCELL(ptr)); break; default: break;}}} gc() {struct obj *newspace; errjmp_ok = 0; nointerrupt = 1; old_heap_used = heap - heap_org; newspace = get_newspace(); scan_registers(); scan_newspace(newspace); errjmp_ok = 1; nointerrupt = 0;} struct obj * gc_status(args) struct obj *args; {if NNULLP(args) if NULLP(car(args)) gc_status_flag = 0; else gc_status_flag = 1; if (gc_status_flag) printf("garbage collection is on\n"); else printf("garbage collection is off\n"); printf("%d allocated %d free\n",heap - heap_org, heap_end - heap); return(NIL);} struct obj * leval_args(l,env) struct obj *l,*env; {struct obj *result,*v1,*v2,*tmp; if NULLP(l) return(NIL); if NTYPEP(l,tc_cons) err("bad syntax argument list",l); result = cons(leval(CAR(l),env),NIL); for(v1=result,v2=CDR(l); TYPEP(v2,tc_cons); v1 = tmp, v2 = CDR(v2)) {tmp = cons(leval(CAR(v2),env),NIL); CDR(v1) = tmp;} if NNULLP(v2) err("bad syntax argument list",l); return(result);} struct obj * extend_env(actuals,formals,env) struct obj *actuals,*formals,*env; {if TYPEP(formals,tc_symbol) return(cons(cons(cons(formals,NIL),cons(actuals,NIL)),env)); return(cons(cons(formals,actuals),env));} struct obj * envlookup(var,env) struct obj *var,*env; {struct obj *frame,*al,*fl,*tmp; for(frame=env;TYPEP(frame,tc_cons);frame=CDR(frame)) {tmp = CAR(frame); if NTYPEP(tmp,tc_cons) err("damaged frame",tmp); for(fl=CAR(tmp),al=CDR(tmp); TYPEP(fl,tc_cons); fl=CDR(fl),al=CDR(al)) {if NTYPEP(al,tc_cons) err("too few arguments",tmp); if EQ(CAR(fl),var) return(al);}} if NNULLP(frame) err("damaged env",env); return(NIL);} struct obj * leval(x,env) struct obj *x,*env; {struct obj *tmp; loop: switch TYPE(x) {case tc_symbol: tmp = envlookup(x,env); if (tmp) return(CAR(tmp)); tmp = VCELL(x); if EQ(tmp,unbound_marker) err("unbound variable",x); return(tmp); case tc_cons: tmp = leval(CAR(x),env); switch TYPE(tmp) {case tc_subr_0: return(SUBRF(tmp)()); case tc_subr_1: return(SUBRF(tmp)(leval(car(CDR(x)),env))); case tc_subr_2: return(SUBRF(tmp)(leval(car(CDR(x)),env), leval(car(cdr(CDR(x))),env))); case tc_subr_3: return(SUBRF(tmp)(leval(car(CDR(x)),env), leval(car(cdr(CDR(x))),env), leval(car(cdr(cdr(CDR(x)))),env))); case tc_lsubr: return(SUBRF(tmp)(leval_args(CDR(x),env))); case tc_fsubr: return(SUBRF(tmp)(CDR(x),env)); case tc_msubr: if NULLP(SUBRF(tmp)(&x,&env)) return(x); goto loop; case tc_closure: env = extend_env(leval_args(CDR(x),env), car((*tmp).storage_as.closure.code), (*tmp).storage_as.closure.env); x = cdr((*tmp).storage_as.closure.code); goto loop; case tc_symbol: x = cons(tmp,cons(cons(sym_quote,cons(x,NIL)),NIL)); x = leval(x,NIL); goto loop; default: err("bad function",tmp);} default: return(x);}} struct obj * setvar(var,val,env) struct obj *var,*val,*env; {struct obj *tmp; if NTYPEP(var,tc_symbol) err("wta(non-symbol) to setvar",var); tmp = envlookup(var,env); if NULLP(tmp) return(VCELL(var) = val); return(CAR(tmp)=val);} struct obj * leval_setq(args,env) struct obj *args,*env; {return(setvar(car(args),leval(car(cdr(args)),env),env));} struct obj * syntax_define(args) struct obj *args; {if TYPEP(car(args),tc_symbol) return(args); return(syntax_define( cons(car(car(args)), cons(cons(sym_lambda, cons(cdr(car(args)), cdr(args))), NIL))));} struct obj * leval_define(args,env) struct obj *args,*env; {struct obj *tmp,*var,*val; tmp = syntax_define(args); var = car(tmp); if NTYPEP(var,tc_symbol) err("wta(non-symbol) to define",var); val = leval(car(cdr(tmp)),env); tmp = envlookup(var,env); if NNULLP(tmp) return(CAR(tmp) = val); if NULLP(env) return(VCELL(var) = val); tmp = car(env); setcar(tmp,cons(var,car(tmp))); setcdr(tmp,cons(val,cdr(tmp))); return(val);} struct obj * leval_if(pform,penv) struct obj **pform,**penv; {struct obj *args,*env; args = cdr(*pform); env = *penv; if NNULLP(leval(car(args),env)) *pform = car(cdr(args)); else *pform = car(cdr(cdr(args))); return(truth);} struct obj * leval_lambda(args,env) struct obj *args,*env; {struct obj *body; if NULLP(cdr(cdr(args))) body = car(cdr(args)); else body = cons(sym_progn,cdr(args)); return(closure(env,cons(arglchk(car(args)),body)));} struct obj * leval_progn(pform,penv) struct obj **pform,**penv; {struct obj *env,*l,*next; env = *penv; l = cdr(*pform); next = cdr(l); while(NNULLP(next)) {leval(car(l),env);l=next;next=cdr(next);} *pform = car(l); return(truth);} struct obj * leval_or(pform,penv) struct obj **pform,**penv; {struct obj *env,*l,*next,*val; env = *penv; l = cdr(*pform); next = cdr(l); while(NNULLP(next)) {val = leval(car(l),env); if NNULLP(val) {*pform = val; return(NIL);} l=next;next=cdr(next);} *pform = car(l); return(truth);} struct obj * leval_and(pform,penv) struct obj **pform,**penv; {struct obj *env,*l,*next; env = *penv; l = cdr(*pform); if NULLP(l) {*pform = truth; return(NIL);} next = cdr(l); while(NNULLP(next)) {if NULLP(leval(car(l),env)) {*pform = NIL; return(NIL);} l=next;next=cdr(next);} *pform = car(l); return(truth);} struct obj * leval_let(pform,penv) struct obj **pform,**penv; {struct obj *env,*l; l = cdr(*pform); env = *penv; *penv = extend_env(leval_args(car(cdr(l)),env),car(l),env); *pform = car(cdr(cdr(l))); return(truth);} struct obj * reverse(l) struct obj *l; {struct obj *n,*p; n = NIL; for(p=l;NNULLP(p);p=cdr(p)) n = cons(car(p),n); return(n);} struct obj * let_macro(form) struct obj *form; {struct obj *p,*fl,*al,*tmp; fl = NIL; al = NIL; for(p=car(cdr(form));NNULLP(p);p=cdr(p)) {tmp = car(p); if TYPEP(tmp,tc_symbol) {fl = cons(tmp,fl); al = cons(NIL,al);} else {fl = cons(car(tmp),fl); al = cons(car(cdr(tmp)),al);}} p = cdr(cdr(form)); if NULLP(cdr(p)) p = car(p); else p = cons(sym_progn,p); setcdr(form,cons(reverse(fl),cons(reverse(al),cons(p,NIL)))); setcar(form,cintern("let-internal")); return(form);} struct obj * leval_quote(args,env) struct obj *args,*env; {return(car(args));} struct obj * leval_tenv(args,env) struct obj *args,*env; {return(env);} struct obj * lprint(exp) struct obj *exp; {lprin1(exp); printf("\n"); return(NIL);} struct obj * lprin1(exp) struct obj *exp; {struct obj *tmp; switch TYPE(exp) {case tc_nil: printf("()"); break; case tc_cons: printf("("); lprin1(car(exp)); for(tmp=cdr(exp);TYPEP(tmp,tc_cons);tmp=cdr(tmp)) {printf(" ");lprin1(car(tmp));} if NNULLP(tmp) {printf(" . ");lprin1(tmp);} printf(")"); break; case tc_flonum: printf("%g",FLONM(exp)); break; case tc_symbol: printf("%s",PNAME(exp)); break; case tc_subr_0: case tc_subr_1: case tc_subr_2: case tc_subr_3: case tc_lsubr: case tc_fsubr: case tc_msubr: printf("#",TYPE(exp),(*exp).storage_as.subr.name); break; case tc_closure: printf("#"); break;} return(NIL);} struct obj * lread() {return(lreadf(stdin));} int flush_ws(f,eoferr) FILE *f; char *eoferr; {int c; while(1) {c = getc(f); if (c == EOF) if (eoferr) err(eoferr,NIL); else return(c); if (isspace(c)) continue; return(c);}} struct obj * lreadf(f) FILE *f; {int c; c = flush_ws(f,(char *)NULL); if (c == EOF) return(eof_val); ungetc(c,f); return(lreadr(f));} struct obj * lreadr(f) FILE *f; {int c,j; char *p; c = flush_ws(f,"end of file inside read"); switch (c) {case '(': return(lreadparen(f)); case ')': err("unexpected close paren",NIL); case '\'': return(cons(sym_quote,cons(lreadr(f),NIL)));} p = tkbuffer; *p++ = c; for(j = 1; j siod.doc SIOD: Scheme In One Defun (c) Copyright 1988 George Carrette, gjc@bu-it.bu.edu For demonstration purposes only. If your interests run to practical applications of symbolic programming techniques, in LISP, Macsyma, C, or other language: Paradigm Associates Inc Phone: 617-492-6079 29 Putnam Ave, Suite 6 Cambridge, MA 02138 Documentation for Release 1.3 1-MAY-88 Updated with more detail for experimenters on 17-MAY-88. [SUBJECT INDEX:] [SUBJECT INDEX] [FILES] [COMPILATION] [INVOCATION] [SYSTEM] [SYNTAX] [SPECIAL FORMS] [MACRO SPECIAL FORMS] [BUILT-IN PROCEDURES] [UTILITIES IN SIOD.SCM] [A STREAMS IMPLEMENTATION] [BENCHMARKS] [PORTING] [ADDING NEW SUBRS] [Files:] siod.c The source in C, approximately 28 thousand bytes. siod.doc This file, approximately 8 thousand bytes. siod.scm Some utility function written in Scheme. [Compilation:] The code has been compiled and run by the author on Sun III and IV, Encore Multimax, 4.3BSD VAX, VAX/VMS, and AMIGA 500 using the Lattice C compiler. On all unix machines use %cc -o siod siod.c on VAX/VMS: $ cc siod $ link siod,sys$input:/opt sys$library:vaxcrtl/share $ siod == "$" + F$ENV("DEFAULT") + "SIOD" on AMIGA 500, ignore warning messages about return value mismatches, %lc siod.c %blink lib:c.o,siod.o to siod lib lib:lcm.lib,lib:lc.lib,lib:amiga.lib [Invocation:] siod [-hXXXXX] [-iXXXXX] -h where XXXXX is an integer, to specify the heap size, in obj cells, -i where XXXXX is a filename to load before going into the repl loop. Example: siod -isiod.scm -h100000 [System:] The interrupts called SIGINT and SIGFPE by the C runtime system are handled by invoking the lisp error procedure. SIGINT is usually caused by the CONTROL-C character and SIGFPE by floating point overflow or underflow. [Syntax:] The only special characters are the parenthesis and single quote. Everything else, besides whitespace of course, will make up a regular token. These tokens are either symbols or numbers depending on what they look like. Dotted-list notation is not supported on input, only on output. [Special forms:] The CAR of a list is evaluated first, if the value is a SUBR of type 9 or 10 then it is a special form. (define symbol value) is presently like (set! symbol value). (define (f . arglist) . body) ==> (define f (lambda arglist . body)) (lambda arglist . body) Returns a closure. (if pred val1 val2) If pred evaluates to () then val2 is evaluated else val1. (begin . body) Each form in body is evaluated with the result of the last returned. (set! symbol value) Evaluates value and sets the local or global value of the symbol. (or x1 x2 x3 ...) Returns the first Xn such that Xn evaluated non-(). (and x1 x2 x3 ...) Keeps evaluating Xj until one returns (), or Xn. (quote form). Input syntax 'form, returns form without evaluation. (let pairlist . body) Each element in pairlist is (variable value). Evaluates each value then sets of new bindings for each of the variables, then evaluates the body like the body of a progn. This is actually implemented as a macro turning into a let-internal form. (the-environment) Returns the current lexical environment. [Macro Special forms:] If the CAR of a list evaluates to a symbol then the value of that symbol is called on a single argument, the original form. The result of this application is a new form which is recursively evaluated. [Built-In functions:] These are all SUBR's of type 4,5,6,7, taking from 0 to 3 arguments with extra arguments ignored, (not even evaluated!) and arguments not given defaulting to (). SUBR's of type 8 are lexprs, receiving a list of arguments. Order of evaluation of arguments will depend on the implementation choice of your system C compiler. consp cons car cdr setcar setcdr number? + - * / < > eqv? The arithmetic functions all take two arguments. eq?, pointer objective identity, eqv? also works on numbers. symbol? symbol-bound? takes an optional environment structure. symbol-value also takes optional env. set-symbol-value also takes optional env. env-lookup takes a symbol and an environment structure. If it returns non-nil the CAR will be the value of the symbol. assq read,print eval, takes a second argument, an environment. copy-list. Copies the top level conses in a list. oblist, returns a copy of the list of the symbols that have been interned. gc-status, prints out the status of garbage collection services, the number of cells allocated and the number of cells free. If given a () argument turns gc services off, if non-() then turns gc services on. load, given a filename (which must be a symbol, there are no strings) will read/eval all the forms in that file. quit, will exit back to the operating system. error, takes a symbol as its first argument, prints the pname of this as an error message. The second argument (optional) is an offensive object. The global variable errobj gets set to this object for later observation. null?, not. are the same thing. edit is a VMS specific function that takes a single filename argument and calls the sharable EDT editor to edit the file. [Utility procedures in siod.scm:] Shows how to define macros. cadr,caddr,cdddr,replace,list. (defvar variable default-value) And for us old maclisp hackers, setq and defun, and progn, etc. [A streams implementation:] The first thing we must do is decide how to represent a stream. There is only one reasonable data structure available to us, the list. So we might use ( ) the-empty-stream is just (). empty-stream? head tail cons-stream is a special form. Wraps a lambda around the second argument. *cons-stream is the low-level constructor used by cons-stream. [Benchmarks:] A standard-fib procedure is included in siod.scm so that everyone will use the same definition in any reports of speed. Make sure the return result is correct. use command line argument of %siod -h100000 -isiod.scm (standard-fib 10) => 55 ; 795 cons work. (standard-fib 15) => 610 ; 8877 cons work. (standard-fib 20) => 6765 ; 98508 cons work. [Porting:] The only code under #ifdef is the definition of myruntime, which should be defined to return a double float, the number of cpu seconds used by the process so far. This is currently specific for encore and sun unix, with a default unix which would work on any 4.2BSD derived system. The other specific case is vms, and the last default has myruntime calling the time function, which usually means an integer number of realtime seconds. Nested ifdef's are very difficult to read of course. Sorry. There is a bit of type casting in close_open_files and vload. The pname of an un-interned symbol is used as a pointer to FILE. This saves the code (a conser, a print case, and two gc cases) of defining a new data type for keeping track of binary data. Are there any machines where a pointer to char and a pointer to FILE are different? There should be no problem with integers vs longs on short integer machines. [Adding new SUBRS:] (1) choose a name for it and add a forward declaration to the group of various forward declarations near the beginning of the file. The arguments must all be of type struct obj *, as is the return value. (2) choose a lisp name and add a call to init_subr for it near all the other calls in the procedure init_subrs. The first argument to init_subr is the lisp name as a string, the second is a subr type code, and the third is the name of the C coded procedure. Dont bother with special forms without detailed understanding of how msubrs in particular work. Use tc_subr_0 to get zero arguments through tc_subr_3 for three arguments. Otherwise use tc_lsubr to receive a single list of evaluated arguments. (3) If you need to use stack lisp variables (you can always use calls to cintern to get a handle on a symbol however) these must be declared before the procedure scan_registers, always init to NIL, and explicitely relocated in the scan_register procedure. (4) inside your subr you need not worry about gc relocating since the gc wont go off except at toplevel. You must of course be conservative about your using of cons and flocons if your procedure will have to run long. Since symbol pnames ARE NOT RELOCATED you do not have to worry about passing the pname string of a symbol to a system procedure that will keep an unprotected pointer to it, even across toplevel calls to GC. However, do not pass pointers to things such as &(FLONM(x)) if the called procedure is going to keep that pointer in its internal storage after it returns. Never pass pointers to lisp data to system routines which may asynchronously go off (such as VMS AST's) at a later time and use that pointer data. Instead you may want to cons an uninterned symbol, malloc some data, and set the symbol PNAME to that data if you want to keep track of it. Example kludge: m = "Binary_DATA_" x = (char *) malloc(3+strlen(m)+1+data_needed); y = symcons(x,NIL); sprintf(x,"%s%3d",m,data_needed); The print name of the symbol Y will be harmless looking enough, because of the zero terminating byte put in by sprintf, but the C programmer will know that its pname points to more interesting goodies inside. The VCELL part of the symbol should come in handy for storing other things, like an alist of object properties perhaps. This just goes to show you that you dont need to go through a lot of trouble, like definining new primitive lisp object types and modifying the printer, to get something useful. SHAR_EOF cat << \SHAR_EOF > siod.n .TH SIOD 1C LOCAL .SH NAME siod \- small scheme interpreter (Scheme In One Defun). .SH SYNOPSIS .B siod [-hXXXXX] [-iXXXXX] .SH DESCRIPTION .I Siod is a very small scheme interpreter which can be used for short calculations or included as a command interpreter or extension/macro language in other applications. .RE .SS COMMAND LINE OPTIONS .TP 8 .BI \-h "XXXXX" The .I XXXXX should be an integer, specifying the number of cons cells to allocate in the heap. The default is 5000. .TP .BI \-i "XXXXX" The .I XXXXX should be the name of an init file to load before going into the read/eval/print loop. .SH FILES siod.doc siod.scm .PD .SH SEE ALSO .I Structure and Interpretation of Computer Programs , by Ableson and Sussman, MIT PRESS. .SH DIAGNOSTICS Error messages may also set the variable errobj to the offending object. .SH BUGS Does not GC during EVAL, only before each READ/EVAL/PRINT cycle. SHAR_EOF cat << \SHAR_EOF > siod.scm '(SIOD: Scheme In One Defun (c) Copyright 1988 George Carrette, gjc@bu-it.bu.edu For demonstration purposes only. Optional Runtime Library for Release 1.3) (define list (lambda n n)) (define (sublis l exp) (if (cons? exp) (cons (sublis l (car exp)) (sublis l (cdr exp))) (let ((cell (assq exp l))) (if cell (cdr cell) exp)))) (define (cadr x) (car (cdr x))) (define (caddr x) (car (cdr (cdr x)))) (define (cdddr x) (cdr (cdr (cdr x)))) (define (replace before after) (set-car! before (car after)) (set-cdr! before (cdr after)) after) (define (push-macro form) (replace form (list 'set! (caddr form) (list 'cons (cadr form) (caddr form))))) (define (pop-macro form) (replace form (list 'let (list (list 'tmp (cadr form))) (list 'set! (cadr form) '(cdr tmp)) '(car tmp)))) (define push 'push-macro) (define pop 'pop-macro) (define (defvar-macro form) (list 'or (list 'value-cell (list 'quote (cadr form))) (list 'define (cadr form) (caddr form)))) (define defvar 'defvar-macro) (define (defun-macro form) (cons 'define (cons (cons (cadr form) (caddr form)) (cdddr form)))) (define defun 'defun-macro) (define setq set!) (define progn begin) (define the-empty-stream ()) (define empty-stream? null?) (define (*cons-stream head tail-future) (list head () () tail-future)) (define head car) (define (tail x) (if (car (cdr x)) (car (cdr (cdr x))) (let ((value ((car (cdr (cdr (cdr x))))))) (set-car! (cdr x) t) (set-car! (cdr (cdr x)) value)))) (define (cons-stream-macro form) (replace form (list '*cons-stream (cadr form) (list 'lambda () (caddr form))))) (define cons-stream 'cons-stream-macro) (define (enumerate-interval low high) (if (> low high) the-empty-stream (cons-stream low (enumerate-interval (+ low 1) high)))) (define (print-stream-elements x) (if (empty-stream? x) () (begin (print (head x)) (print-stream-elements (tail x))))) (define (standard-fib x) (if (< x 2) x (+ (standard-fib (- x 1)) (standard-fib (- x 2))))) SHAR_EOF # End of shell archive exit 0 -- Bob Page, U of Lowell CS Dept. page@swan.ulowell.edu ulowell!page Have five nice days.