diff -rN -u old-lithium/li3_interp.h new-lithium/li3_interp.h --- old-lithium/li3_interp.h 2006-07-25 21:38:45.000000000 -0700 +++ new-lithium/li3_interp.h 2006-07-25 21:38:45.000000000 -0700 @@ -30,42 +30,50 @@ #define MAX_EXPLAIN 9999 /* largest output string */ //#define LIMIT_DEPTH MAX_EXPLAIN /* arbitrary, but limits computations */ #define LIMIT_DEPTH 999 /* arbitrary, but limits computations */ -#define LIMIT_PAIRS MAX_EXPLAIN*10 /* arbitrary, but limits computations */ +#define LIMIT_NODES MAX_EXPLAIN*10 /* arbitrary, but limits computations */ +#define LIMIT_CHARS 256 //#define LIMIT_EVALS MAX_EXPLAIN*100 /* arbitrary, but limits computations */ #define ENABLE_GLOBALS /* global vars instead of lambda, for (aX) */ typedef struct Machine *machine; typedef struct Buffer *buffer; +typedef unsigned long addr; // can hold a pointer + struct Node { + node hd; + node tl; - typedef node (*func_t)(node,machine,node); + enum TYPE { NUMBER, CHAR, PAIR, PARTIAL, CFUNC }; + typedef node (* func_t )(node,machine,node); // func_t points to C function - unsigned short value; - enum { /*non-intlike:*/ PAIR, FUNC, /*intlike:*/ NUMBER, LETTER, SYMBOL } type : 3; - node hd; - node tl; - char typeLetter() { return type==PAIR?'P':type==FUNC?'F':type==NUMBER?'N':type==LETTER?'L':type==SYMBOL?'S': type==PAIR?'p': '?'; } + inline char typeLetter(); + inline Node::TYPE getType(); - bool isNum() { return type==NUMBER; } - bool isLet() { return type==LETTER; } - bool isSym() { return type==SYMBOL; } - bool isPair() { return type==PAIR; } - bool isAtom() { return type!=PAIR; } - bool isFunc() { return type==FUNC; } - bool isIntLike() { return type >= NUMBER; } - inline int integerize(); - - static void Initialize(); - static node Cons(node h, node t); - static node NewFuncNode(func_t f, node t); + inline bool isNumber(); + inline bool isChar(); + inline bool isPair(); + inline bool isCFunc(); + inline bool isPartial(); - node CallFuncNode(machine m, node arg); + inline bool isGlobalLetter(); + inline bool isLambdaLetter(); - char* explain(); // caller must free + inline bool isIntLike(); + inline int integerize(); + inline int letterNumber(); + inline int asciiValue(); + + static void Initialize(); + static node Cons(node h, node t); + static node NewPartialNode(func_t f, node t); + + node CallPartialNode(machine m, node arg); + + char* explain(); // caller must free }; #define NUM_ATOMS 256 /* for the 256 possible bytes */ @@ -73,15 +81,33 @@ #define NUM_VARS NUM_LETTERS #define FIRST_LETTER ATOM('a') +#define FIRST_GLOBAL_LETTER ATOM('a') /* a-m are globals; n-z are lambda */ +#define LAST_GLOBAL_LETTER ATOM('m') /* a-m are globals; n-z are lambda */ #define FIRST_LAMBDA_LETTER ATOM('n') /* a-m are globals; n-z are lambda */ -#define FIRST_NUMBER ATOM('0') +#define LAST_LAMBDA_LETTER ATOM('z') /* a-m are globals; n-z are lambda */ +//#define FIRST_NUMBER ATOM('0') #define Nil ATOM('0') /* our Nil convention is to use Atom '0' */ -extern Node Atoms[NUM_ATOMS]; -extern Node Pairs[LIMIT_PAIRS]; +extern Node Nodes[LIMIT_NODES]; extern node NextPairPtr; -inline node ATOM(char c) { int x= 255&(int)c; assert( 0<=x && xisCFunc(); } +inline bool Node::isPartial() { return !(isNumber()) && CHARS_END<=this && thisisCFunc(); } + +inline Node::TYPE Node::getType() { return isNumber()? NUMBER: isChar()? CHAR: isPair()? PAIR: isPartial()? PARTIAL: isCFunc()? CFUNC: (assert(!"getType"), CFUNC ); } + +inline char Node::typeLetter() { return getType()==PAIR?'P':getType()==CFUNC?'Z':getType()==CHAR?'C':getType()==PARTIAL?'p': '?'; } + +inline bool Node::isIntLike() { return isNumber() || isChar(); } extern node ICombinator; node PrimativeC(node self, machine m, node arg); @@ -90,10 +116,25 @@ node PrimativeK(node self, machine m, node arg); node PrimativeSkipK(node self, machine m, node arg); -int Node::integerize() { +inline int Node::integerize() { // IntLike Atoms have int value relative to atom '0'. // Other Atoms have value 0. - return this->isIntLike()? ( NUM_ATOMS + (this - (Atoms+'0')) ) % NUM_ATOMS : 0; + return isNumber()? ((int)this)>>1 : isChar()? (int)(this-Nodes) : (assert(!"integerize"),0); +} +inline bool Node::isGlobalLetter() { + return ( FIRST_GLOBAL_LETTER<=this && this<=LAST_GLOBAL_LETTER); +} +inline bool Node::isLambdaLetter() { + return ( FIRST_LAMBDA_LETTER<=this && this<=LAST_LAMBDA_LETTER); +} + +inline int Node::letterNumber() { + assert( isGlobalLetter() || isLambdaLetter() ); + return this - FIRST_LETTER; +} +inline int Node::asciiValue() { + assert( isChar() ); + return this - Nodes; } enum FREEABILITY { NOT_FREEABLE, CAN_FREE }; diff -rN -u old-lithium/lithium3.cc new-lithium/lithium3.cc --- old-lithium/lithium3.cc 2006-07-25 21:38:45.000000000 -0700 +++ new-lithium/lithium3.cc 2006-07-25 21:38:45.000000000 -0700 @@ -52,8 +52,8 @@ Node Atoms[NUM_ATOMS]; // A Pool of Pairs -Node Pairs[LIMIT_PAIRS]; -node NextPairPtr; +Node Nodes[LIMIT_NODES]; +node NextNodePtr; static node Question; // input script static node Answer; // for throw-catch @@ -74,17 +74,24 @@ void AssertNode(node p) { - Assert( Pairs<=NextPairPtr && NextPairPtr<=Pairs+LIMIT_PAIRS ); + Assert( Pairs<=NextNodePtr && NextNodePtr<=Pairs+LIMIT_NODES ); Assert(p); - if (p->isIntLike()) { - Assert( Atoms<=p && p<=Atoms+NUM_ATOMS ); + + if ( (int)p & 1 ) return; + + Assert( Nodes <= p ); + Assert( p < Nodes + LIMIT_NODES ); + + if (p->isChar()) { + Assert( Nodes <= p ); + Assert( p < Nodes + LIMIT_CHARS ); } else if (p->isPair()) { - Assert( Pairs<=p && p<=Pairs+LIMIT_PAIRS ); + Assert( Pairs<=p && p<=Pairs+LIMIT_NODES ); //AssertNode( p->hd ); //AssertNode( p->tl ); - } else if (p->isFunc()) { - Assert( Pairs<=p && p<=Pairs+LIMIT_PAIRS ); + } else if (p->isPartial()) { + Assert( Pairs<=p && p<=Pairs+LIMIT_NODES ); //AssertNode( p->tl ); } else Assert(0); } @@ -111,17 +118,17 @@ Answer= Nil; DepthCount= 0; EvalCount= 0; - NextPairPtr= &Pairs[0]; + NextNodePtr= &Pairs[0]; //memset( Pairs, 0, sizeof Pairs ); - ICombinator= Node::NewFuncNode( & PrimativeI, Nil ); + ICombinator= Node::NewPartialNode( & PrimativeI, Nil ); PushOutState= Nil; PrintOutPtr= -1; memset( PrintOutBuffer, 0, sizeof PrintOutBuffer ); } -bool MorePairs() { return NextPairPtr < &Pairs[LIMIT_PAIRS]; } -node NextPair() { return MorePairs() ? NextPairPtr++ : NULL; } +bool MorePairs() { return NextNodePtr < &Pairs[LIMIT_NODES]; } +node NextPair() { return MorePairs() ? NextNodePtr++ : NULL; } // very simple attempt to free p if it was the previous thing allocated int freeNotCount; int freeTryCount; @@ -130,7 +137,7 @@ if ( freeable == NOT_FREEABLE ) ++freeNotCount; else { - ++freeTryCount; if (NextPairPtr - 1 == p) { --NextPairPtr; ++freeSuccessCount; } + ++freeTryCount; if (NextNodePtr - 1 == p) { --NextNodePtr; ++freeSuccessCount; } } } @@ -217,22 +224,21 @@ fprintf(stderr, "\nOKAY: %d Tests, %d Asserts\n", count, AssertCount ); } -node Node::NewFuncNode(func_t f, node t) +node Node::NewPartialNode(func_t f, node t) { AssertNode(t); node p= NextPair(); if ( !p ) JMP_THROW( NO_MORE_PAIRS ); - p->type= FUNC; p->hd= (node)(void*)f; p->tl= t; AssertNode(p); return p; } -node Node::CallFuncNode(machine m, node arg) +node Node::CallPartialNode(machine m, node arg) { - Assert(this->isFunc()); + Assert(this->isPartial()); func_t f= (func_t)(void*)hd; Assert(f); return f(this, m, arg); @@ -246,7 +252,6 @@ AssertNode(h); AssertNode(t); - p->type= PAIR; p->hd= h; p->tl= t; AssertNode(p); @@ -258,11 +263,11 @@ node p= Node::Cons( Atoms+32, Atoms+64 ); Assert( p->hd == Atoms+32 ); Assert( p->tl == Atoms+64 ); - Assert( p->type == Node::PAIR ); + Assert( p->getType() == Node::PAIR ); } TEST(ConsAll) { - int n= LIMIT_PAIRS - 1; // -1 for ICombinator + int n= LIMIT_NODES - LIMIT_CHARS - 1; // -1 for ICombinator ResetInterpreter(); for (int i=0; iisIntLike() ); - Assert( ! Node::NewFuncNode(NULL,Nil)->isIntLike() ); + Assert( ! Node::NewPartialNode(NULL,Nil)->isIntLike() ); } TEST(Integerize) { Assert( Nil->integerize() == 0 ); @@ -312,7 +317,7 @@ // not intlike Assert( Node::Cons(Nil,Nil)->integerize() == 0 ); - Assert( Node::NewFuncNode(NULL,Nil)->integerize() == 0 ); + Assert( Node::NewPartialNode(NULL,Nil)->integerize() == 0 ); } node atomize(int x) @@ -350,7 +355,7 @@ } node PrimativeCons(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialCons, arg ); + return Node::NewPartialNode( & PartialCons, arg ); } node PartialReverseCons(node self, machine m, node arg) { @@ -358,7 +363,7 @@ } node PrimativeReverseCons(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialReverseCons, arg ); + return Node::NewPartialNode( & PartialReverseCons, arg ); } node OriginalProgram; @@ -438,7 +443,7 @@ } node PrimativeMapCar(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialMapCar, arg ); + return Node::NewPartialNode( & PartialMapCar, arg ); } TEST(mapCar) { @@ -463,11 +468,11 @@ } node PartialS1(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialS2, Node::Cons( self->tl, arg ) ); + return Node::NewPartialNode( & PartialS2, Node::Cons( self->tl, arg ) ); } node PrimativeS(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialS1, arg ); + return Node::NewPartialNode( & PartialS1, arg ); } node PartialPlus(node self, machine m, node arg) @@ -479,7 +484,7 @@ } node PrimativePlus(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialPlus, arg ); + return Node::NewPartialNode( & PartialPlus, arg ); } node PartialMinus(node self, machine m, node arg) @@ -491,7 +496,7 @@ } node PrimativeMinus(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialMinus, arg ); + return Node::NewPartialNode( & PartialMinus, arg ); } node PartialMultiply(node self, machine m, node arg) @@ -503,7 +508,7 @@ } node PrimativeMultiply(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialMultiply, arg ); + return Node::NewPartialNode( & PartialMultiply, arg ); } node PartialBitOr(node self, machine m, node arg) @@ -515,7 +520,7 @@ } node PrimativeBitOr(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialBitOr, arg ); + return Node::NewPartialNode( & PartialBitOr, arg ); } node PartialBitAnd(node self, machine m, node arg) @@ -527,7 +532,7 @@ } node PrimativeBitAnd(node self, machine m, node arg) { - return Node::NewFuncNode( & PartialBitAnd, arg ); + return Node::NewPartialNode( & PartialBitAnd, arg ); } void SetPrimitiveSymbol( int ascii, Node::func_t f ) @@ -594,7 +599,7 @@ // PrimativeJ == "((Jab" returns b (the second argument) (compare to K) node PrimativeJ(node self, machine m, node arg) { - return Node::NewFuncNode( &PrimativeI, Nil ); + return Node::NewPartialNode( &PrimativeI, Nil ); } // PrimativeK == K Combinator. "((Kab" returns a (the first argument) @@ -604,14 +609,14 @@ } node PrimativeK(node self, machine m, node arg) { - return Node::NewFuncNode( &PartialK, arg ); + return Node::NewPartialNode( &PartialK, arg ); } // PrimativeU == "((Uab" returns b without evaluating a ( U is lazy J ) node PrimativeU(node self, machine m, node arg) { - return Node::NewFuncNode( &PrimativeI, Nil ); + return Node::NewPartialNode( &PrimativeI, Nil ); } // PrimativeV == "((Vab" returns a without evaluating b ( V is lazy K ) node PartialV(node self, machine m, node arg) @@ -621,7 +626,7 @@ } node PrimativeV(node self, machine m, node arg) { - return Node::NewFuncNode( &PartialV, arg ); + return Node::NewPartialNode( &PartialV, arg ); } @@ -660,7 +665,7 @@ node v= p->hd; // the Var spec node x= p->tl; // the body expression AssertNode(v); - Assert(v->isLet()); + Assert(v->isLambdaLetter()); AssertNode(x); // save old var & install eval(arg) in place @@ -687,7 +692,7 @@ EvalCounter counter; ++EvalCount; - Assert( p->type == Node::PAIR ); + Assert( p->getType() == Node::PAIR ); AssertNode( p ); node h= p->hd; @@ -697,7 +702,7 @@ node z= Nil; - switch(h->type) { + switch(h->getType()) { case Node::NUMBER: // if atomp && <=n { @@ -707,10 +712,10 @@ AssertNode( x ); if (x->isNum() && x->value <= h->value) { if(trace) fprintf(stderr, " Num Cond True: x %d <= h %d -- return I(nil)\n", x->value, h->value); - z= Node::NewFuncNode( &PrimativeK, Nil ); + z= Node::NewPartialNode( &PrimativeK, Nil ); } else { if(trace) fprintf(stderr, " Num Cond False: return I(x)\n"); - z= Node::NewFuncNode( &PrimativeJ, Nil ); + z= Node::NewPartialNode( &PrimativeJ, Nil ); } #else z= eval( t ); @@ -718,41 +723,35 @@ } break; - case Node::LETTER: // lambda or global + case Node::CHAR: // lambda or global or symbol { - if (h < FIRST_LAMBDA_LETTER) { + if ( h->isGlobalLetter() ) { // (aX) means set global var a to evaluation of expression X node x= eval(t); setGlobalVar( h, x ); z= x; - if(trace) fprintf(stderr, " Set Global #%d\n", h->value ); - } else { + if(trace) fprintf(stderr, " Set Global #%d\n", h-FIRST_LETTER ); + } else if ( h->isLambdaLetter() ) { // (zX) means "lambda z . X" for automatically-quoted expression X - z= Node::NewFuncNode( & LambdaFunc, p ); - if(trace) fprintf(stderr, " Lambda #%d\n", h->value ); - } - - } - break; - - case Node::SYMBOL: // primative - { - if ( h == ATOM('\'') ) { // Lisp QUOTE + z= Node::NewPartialNode( & LambdaFunc, p ); + if(trace) fprintf(stderr, " Lambda #%d\n", h-FIRST_LETTER ); + } else { + if ( h == ATOM('\'') ) { // Lisp QUOTE FreeIfPossible(p,freeable); z= t; // un-evaluated if(trace) fprintf(stderr, " Special Quote\n"); - } else if ( h == ATOM(';') ) { // special INCREMENT + } else if ( h == ATOM(';') ) { // special INCREMENT FreeIfPossible(p,freeable); if ( t->isIntLike() ) { z= getVar(t); if (z->isIntLike()) { ++z; if (z == ATOM(NUM_ATOMS)) z= Atoms; - if(trace) fprintf(stderr, " Special Incr Intlike: Global #%d := %d\n", t->value, z->value ); + if(trace) fprintf(stderr, " Special Incr Intlike: Global #%d := %d\n", t->asciiValue(), z->asciiValue() ); } else { - if(trace) fprintf(stderr, " Special Incr: Global #%d :=\n", t->value ); + if(trace) fprintf(stderr, " Special Incr: Global #%d :=\n", t->asciiValue() ); } setGlobalVar(t, z); } else { @@ -760,12 +759,12 @@ if (z->isIntLike()) { ++z; if (z == ATOM(NUM_ATOMS)) z= Atoms; - if(trace) fprintf(stderr, " Special Incr Intlike: -> %d\n", z->value ); + if(trace) fprintf(stderr, " Special Incr Intlike: -> %d\n", z->asciiValue() ); } else { if(trace) fprintf(stderr, " Special Incr: Nop\n" ); } } - } else if ( h->hd ) { // has primitive func + } else if ( h->hd ) { // has primitive func Node::func_t f= (Node::func_t)(void*)(h->hd); node x= t; if ( f != PrimativeWhile && f != PrimativeU ) { @@ -775,12 +774,13 @@ AssertNode( x ); if(trace) fprintf(stderr, "CALL Primative Func... 0x%x\n", (int)f); z= f(p, this, x ); - } else { // do no harm + } else { // do no harm if(trace) fprintf(stderr, " Default I.\n"); FreeIfPossible(p,freeable); z= ICombinator; - } - } + } + } //fi + } //esac break; case Node::PAIR: // Apply @@ -790,7 +790,7 @@ AssertNode( a ); node b; - if ( a->isFunc() && ( (void*)a->hd == (void*)&PrimativeU + if ( a->isPartial() && ( (void*)a->hd == (void*)&PrimativeU || (void*)a->hd == (void*)&PartialV ) ) { @@ -808,7 +808,7 @@ } break; - case Node::FUNC: // ? + case Node::PARTIAL: // ? { FreeIfPossible(p,freeable); Node::func_t f= (Node::func_t)(void*)(h->hd); @@ -841,11 +841,11 @@ node p= Node::Cons( Atoms+'3', Atoms+'7' ); node f= m.evalPair(p, CAN_FREE); - Assert( f->isFunc() ); + Assert( f->isPartial() ); Assert( f->hd == (node)(void*)PrimativeJ ); Assert( f->tl == Nil ); - node z= f->CallFuncNode( &m, Atoms+'8' )->CallFuncNode( &m, Atoms+'9'); + node z= f->CallPartialNode( &m, Atoms+'8' )->CallPartialNode( &m, Atoms+'9'); Assert( z == Atoms+'9' ); @@ -853,11 +853,11 @@ p= Node::Cons( Atoms+'3', Atoms+'2' ); f= m.evalPair(p); - Assert( f->isFunc() ); + Assert( f->isPartial() ); Assert( f->hd == (node)(void*)PrimativeK ); Assert( f->tl == Nil ); - z= f->CallFuncNode( &m, Atoms+'8' )->CallFuncNode( &m, Atoms+'9'); + z= f->CallPartialNode( &m, Atoms+'8' )->CallPartialNode( &m, Atoms+'9'); Assert( z == Atoms+'8' ); } #endif @@ -871,11 +871,11 @@ node p= Node::Cons( Atoms+'x', Atoms+'x' ); node f= m.evalPair(p); - Assert( f->isFunc() ); + Assert( f->isPartial() ); Assert( f->hd == (node)(void*)LambdaFunc ); Assert( f->tl == p ); - node z= f->CallFuncNode( &m, Atoms+'6' ); + node z= f->CallPartialNode( &m, Atoms+'6' ); Assert( z == Atoms+'6' ); Assert( m.vars[3] == Atoms+'@' ); @@ -893,11 +893,11 @@ ) ); node f= m.evalPair(p); - Assert( f->isFunc() ); + Assert( f->isPartial() ); Assert( f->hd == (node)(void*)LambdaFunc ); Assert( f->tl == p ); - node z= f->CallFuncNode( &m, Atoms+'4' ); + node z= f->CallPartialNode( &m, Atoms+'4' ); Assert( z == Atoms+'8' ); Assert( m.vars[3] == Atoms+'@' ); @@ -924,16 +924,19 @@ EvalCounter counter; AssertNode( p ); - switch(p->type) { + switch(p->getType()) { case Node::NUMBER: - case Node::SYMBOL: - case Node::FUNC: + case Node::PARTIAL: z= p; break; - case Node::LETTER: - z= getVar(p); + case Node::CHAR: + if ( p->isGlobalLetter() || p->isLambdaLetter() ) { + z= getVar(p); + } else { + z= p; + } break; case Node::PAIR: @@ -947,8 +950,10 @@ if(trace) { char* pp= p->explain(); char* zz= z->explain(); - if ( p->type == Node::LETTER ) fprintf(stderr, "Eval<%c>: %s --> %s\n", p->typeLetter(), pp, zz ); - else fprintf(stderr, "Eval<%c>nop: %s\n", p->typeLetter(), zz ); + if ( p->isGlobalLetter() || p->isLambdaLetter() ) + fprintf(stderr, "Eval<%c>: %s --> %s\n", p->typeLetter(), pp, zz ); + else + fprintf(stderr, "Eval<%c>nop: %s\n", p->typeLetter(), zz ); free(zz); free(pp); } @@ -976,23 +981,9 @@ { for (int i=0; itype= Node::SYMBOL; - p->hd= 0; - p->tl= 0; - - if ('0'<=i && i<='9') p->type= NUMBER, p->value= i-'0'; - else if ('a'<=i && i<='z') p->type= LETTER, p->value= i-'a'; - else p->type= SYMBOL, p->value= i; - } - //memset( Pairs, 0, sizeof Pairs ); - if (0) for (int i=0; itype= Node::PAIR; - p->hd= 0; - p->tl= 0; + memset( Nodes, 0, sizeof Nodes ); } + ResetInterpreter(); // install binary arithmethic operators @@ -1030,18 +1021,7 @@ TEST(Initialize) { - for (int i=0; iappend( p->tl ) ) return true; if ( this->append(')') ) return true; return false; - } else if ( p->isFunc() ) { + } else if ( p->isPartial() ) { Node::func_t f= (Node::func_t)(void*)p->hd; if ( f == &LambdaFunc ) { @@ -1382,7 +1362,7 @@ } Li3_EvalCount= EvalCount; - Li3_EvalPairCount= NextPairPtr-Pairs; + Li3_EvalPairCount= NextNodePtr-Nodes; } char* Li3_EvalString(const char* s) {