Sunday, November 15, 2015

Day 4 A Forth interpreter in C, more math functions.


For today, we add most of the standard C math library functions to the basic four function calculator oriented interpreter.

#include 
#include 
#include 
#include 
#include 


/*
 day 1 - basic 
 day 2 - tokenizing.
 day 3 - basic function calculator.
 day 4 - more math functions. November 15, 2014.
*/

#define MAXBUFFSIZE 128
#define MAXFSTACKSIZE 32

double FSTACK[MAXFSTACKSIZE];
int    FP = 0;                // index to FSTACK;

char    BUFF[MAXBUFFSIZE];   // input string buffer.

char   delims[] = " \t\n";   // delimiters.
double fval     = 0.0;


enum  Dtypes{ERROR, FNUM, FADD,FSUB, FMUL, FDIV, FPRINT,
             FPI, FE, FABS,FNEG, FEXP, FLN, FLOG10, FSIN, FCOS, FTAN, FSINH, FCOSH, FTANH, 
             FDOWN, FUP,
             ECR,  QUIT};

int  lexer(char* tok)
{
    int  n = strlen(tok);
    char c = *tok;
    if (n == 1){
       if (c == '+') return FADD;
       if (c == '-') return FSUB;
       if (c == '*') return FMUL;
       if (c == '/') return FDIV;
       if (c == '.') return FPRINT;
    }
    // A simplistic individual brute force string comparisons 
    if (strcmp(tok, "pi")==0) return FPI; 
    if (strcmp(tok, "e")==0) return FE;
    if (strcmp(tok, "abs")==0) return FABS;
    if (strcmp(tok, "neg")==0) return FNEG;
    if (strcmp(tok, "exp")==0) return FEXP;
    if (strcmp(tok, "ln")==0)  return FLN;
    if (strcmp(tok, "log10")==0) return  FLOG10;
    if (strcmp(tok, "sin")==0) return FSIN;
    if (strcmp(tok, "cos")==0) return FCOS;
    if (strcmp(tok, "tan")==0) return FTAN;
    if (strcmp(tok, "sinh")==0) return FSINH;
    if (strcmp(tok, "cosh")==0) return FCOSH;
    if (strcmp(tok, "tanh")==0) return FTANH;

    if (strcmp(tok, "fdown")==0) return FDOWN;
    if (strcmp(tok, "fup")==0) return FUP;
    
    if (strcmp(tok, "quit")== 0) {
       return QUIT;
    };
    if (strcmp(tok, "ecr") == 0) {
       return ECR;
    }
    if (getnumber(tok) == 0) {
       return FNUM;
    };
    return ERROR;
}


int checknumber(char *s)
{
  /* Description
     Returns 0 if s is a double real number, otherwise nonzero value.
     It is assumed that leading and trailing white spaces are removed from s.
     1 illegal character after '.'
     2 illegal starting character.
     3 illegal character after 'e'
     4 expected a '\0'
     5 empty string.
   */
  char* t = s;
  /* empty string */
  if (*t == '\0') return 5; 
  /* starts with an optional sign? */
  if ((*t == '-') || (*t == '+'))t++;
  // block of digits starting with a digit 
  if (isdigit(*t)) { /* starts with a digit? */
  while (isdigit(*t)) t++;
  if (*t == '.'){ /* a block starting with a .? */
    t++;
    if (*t == '\0') return 0;  // a number ending with a '.'
    while (isdigit(*t)) t++;
  }
  }else if (*t == '.'){ /* a number starting with a .? */
 t++;
 if (! isdigit(*t)) return 1;
 while (isdigit(*t)) t++;
  } else return 2;  /* illegal starting value! */
    
  /* optional exponent */
  if (tolower(*t) == 'e') {
 t++;
 if ((*t == '-') || (*t == '+')) {
    t++;
 }
 if (!isdigit(*t))return 3;
 while isdigit(*t) t++;
  }
  /* illegal character */
  if (*t != '\0') return 4;
  return 0;
};


int getnumber(char *s){
   int i = checknumber(s);
   if (i==0) {
      fval = atof(s);
   }
   return i;
};

int main() {
  int i =0;
  int exitnow = 0;
  while (1) {
    fputs(">>", stdout);
    fgets(BUFF, MAXBUFFSIZE-1, stdin);
    char *tok = strtok(BUFF, delims);
    while (tok)  {
      // printf("%d %s", ++i, tok);
      if (tok == NULL) break;
     
      // process token.
      int dtype = lexer(tok);
      switch(dtype) {
      // basic floating point operations.
      case  FNUM:
            FSTACK[++FP]= fval; break;
      case  FADD:
            FP--; FSTACK[FP]+= FSTACK[FP+1]; break;  
      case  FSUB:
            FP--; FSTACK[FP]-= FSTACK[FP+1]; break;  
      case  FMUL:
            FP--; FSTACK[FP]*= FSTACK[FP+1]; break;  
      case  FDIV:
            FP--; FSTACK[FP]/= FSTACK[FP+1]; break;  
      case  FPRINT:
            printf("%f", FSTACK[FP]); break;
      case  ECR: // prints new line
            printf("\n"); break;
            
            
      // Constants and One argument math functions.      
      case  FPI:   // constant pi
            FSTACK[++FP] = M_PI; break;
      case  FE:    // constant e
            FSTACK[++FP] = exp(1.0); break;
      case  FABS:  FSTACK[FP] = fabs(FSTACK[FP]); break;
      case  FNEG:  FSTACK[FP] = -FSTACK[FP]; break;
      case  FEXP:  FSTACK[FP] = exp(FSTACK[FP]); break;
      case  FLN:   FSTACK[FP] = log(FSTACK[FP]); break;
      case  FLOG10:FSTACK[FP] = log10(FSTACK[FP]); break;
      case  FSIN:  FSTACK[FP] = sin(FSTACK[FP]); break;
      case  FCOS:  FSTACK[FP] = cos(FSTACK[FP]); break;
      case  FTAN:  FSTACK[FP] = tan(FSTACK[FP]); break;
      case  FSINH: FSTACK[FP] = sinh(FSTACK[FP]); break;
      case  FCOSH: FSTACK[FP] = cosh(FSTACK[FP]); break;
      case  FTANH: FSTACK[FP] = tanh(FSTACK[FP]); break;
      case  FUP:   if (FP < MAXFSTACKSIZE-1) FP++; break; 
      case  FDOWN: if (FP) FP--; break;
      case ERROR:
     printf("ERROR\n");
     break;
      case  QUIT:
            printf("quitting...\n");
     exitnow = 1;
     break;
      };
      tok = strtok(NULL, delims);
    } 
    if (exitnow) {
       puts("Thanks for using easyforth!\n");
       break;
    }
  };
  return 0;
};
Here is a simple compilation and execution run.
toto@toto-VirtualBox:~/Projects/forth$ gcc day4-easyforth.c -lm
toto@toto-VirtualBox:~/Projects/forth$ ./a.out 
>>pi 2 / sin .
1.000000>>1.0 exp .
2.718282>>

Friday, November 13, 2015

Day 3: A Forth interpreter in C, basic four function calculator.


It is day 3 for our Forth interpreter in C. To show that we wrote already has capabilities to compute simple arithmetic we add an evaluator routines inside the main function to the current code.


#include 
#include 
#include 
#include 

/*
 day 2 - tokenizing.
 day 3 - 11.13.2015 basic function calculator.
*/

#define MAXBUFFSIZE 128
#define MAXFSTACKSIZE 32

double FSTACK[MAXFSTACKSIZE];
int    FP = 0;                // index to FSTACK;

char    BUFF[MAXBUFFSIZE];   // input string buffer.

char   delims[] = " \t\n";   // delimiters.
double fval     = 0.0;


enum  Dtypes{ERROR, FNUM, FADD,FSUB, FMUL, FDIV, FPRINT, 
             ECR,  QUIT};

int  lexer(char* tok)
{
    int  n = strlen(tok);
    char c = *tok;
    if (n == 1){
       if (c == '+') return FADD;
       if (c == '-') return FSUB;
       if (c == '*') return FMUL;
       if (c == '/') return FDIV;
       if (c == '.') return FPRINT;
    }
    if (getnumber(tok) == 0) {
       return FNUM;
    };
    if (strcmp(tok, "quit")== 0) {
       return QUIT;
    }
    if (strcmp(tok, "ecr") == 0) {
       return ECR;
    }
    return ERROR;
}


int checknumber(char *s)
{
  /* Description
     Returns 0 if s is a double real number, otherwise nonzero value.
     It is assumed that leading and trailing white spaces are removed from s.
     1 illegal character after '.'
     2 illegal starting character.
     3 illegal character after 'e'
     4 expected a '\0'
     5 empty string.
   */
  char* t = s;
  /* empty string */
  if (*t == '\0') return 5; 
  /* starts with an optional sign? */
  if ((*t == '-') || (*t == '+'))t++;
  // block of digits starting with a digit 
  if (isdigit(*t)) { /* starts with a digit? */
  while (isdigit(*t)) t++;
  if (*t == '.'){ /* a block starting with a .? */
    t++;
    if (*t == '\0') return 0;  // a number ending with a '.'
    while (isdigit(*t)) t++;
  }
  }else if (*t == '.'){ /* a number starting with a .? */
 t++;
 if (! isdigit(*t)) return 1;
 while (isdigit(*t)) t++;
  } else return 2;  /* illegal starting value! */
    
  /* optional exponent */
  if (tolower(*t) == 'e') {
 t++;
 if ((*t == '-') || (*t == '+')) {
    t++;
 }
 if (!isdigit(*t))return 3;
 while isdigit(*t) t++;
  }
  /* illegal character */
  if (*t != '\0') return 4;
  return 0;
};


int getnumber(char *s){
   int i = checknumber(s);
   if (i==0) {
      fval = atof(s);
   }
   return i;
};

int main() {
  int i =0;
  int exitnow = 0;
  while (1) {
    fputs(">>", stdout);
    fgets(BUFF, MAXBUFFSIZE-1, stdin);
    char *tok = strtok(BUFF, delims);
    while (tok)  {
      // printf("%d %s", ++i, tok);
      if (tok == NULL) break;
     
      // process token.
      int dtype = lexer(tok);
      switch(dtype) {
      case  FNUM:
            FSTACK[++FP]= fval; break;
      case  FADD:
            FP--; FSTACK[FP]+= FSTACK[FP+1]; break;  
      case  FSUB:
            FP--; FSTACK[FP]-= FSTACK[FP+1]; break;  
      case  FMUL:
            FP--; FSTACK[FP]*= FSTACK[FP+1]; break;  
      case  FDIV:
            FP--; FSTACK[FP]/= FSTACK[FP+1]; break;  
      case  FPRINT:
            printf("%f", FSTACK[FP]); break;
      case  ECR: // prints new line
            printf("\n"); break;
      case  QUIT:
            printf("quitting...\n");
     exitnow = 1;
     break;
      case ERROR:
     printf("ERROR\n");
     break;
      };
      tok = strtok(NULL, delims);
    } 
    if (exitnow) {
       puts("Thanks for using easyforth!\n");
       break;
    }
  };
  return 0;
};

As a test, we compute, in infix notation, (12 + 34) * -45 + 120) / 456.

toto@toto-VirtualBox:~/Projects/forth$ ./a.out
>>12 34 + -45 * 120 + 456 / .
-4.276316>>quit
quitting...
Thanks for using easyforth!

Using a scientific calculator, gives the result 4276315789.

Thursday, November 12, 2015

Day 2: A forth interpreter in C, tokenizing


On our second day, we analyze each token, determine if it is a number or an operator.


/

#include 
#include 
#include 
#include 

/*
 day 2 - tokenizing.
*/

#define MAXBUFFSIZE 128
char    BUFF[MAXBUFFSIZE];   // input string buffer.

char delims[] = " \t\n";
double fval   = 0;

enum  Dtypes{ERROR, FNUM, FADD,FSUB, FMUL, FDIV, FPRINT, QUIT};

int  lexer(char* tok)
{
    int  n = strlen(tok);
    char c = *tok;
    if (n == 1){
       if (c == '+') return FADD;
       if (c == '-') return FSUB;
       if (c == '*') return FMUL;
       if (c == '/') return FDIV;
       if (c == '.') return FPRINT;
    }
    if (getnumber(tok) == 0) {
       return FNUM;
    };
    if (strcmp(tok, "quit")== 0) {
       return QUIT;
    }
    return ERROR;
}


int checknumber(char *s)
{
  /* Description
     Returns 0 if s is a double real number, otherwise nonzero value.
     It is assumed that leading and trailing white spaces are removed from s.
     1 illegal character after '.'
     2 illegal starting character.
     3 illegal character after 'e'
     4 expected a '\0'
     5 empty string.
   */
  char* t = s;
  /* empty string */
  if (*t == '\0') return 5; 
  /* starts with an optional sign? */
  if ((*t == '-') || (*t == '+'))t++;
  // block of digits starting with a digit 
  if (isdigit(*t)) { /* starts with a digit? */
  while (isdigit(*t)) t++;
  if (*t == '.'){ /* a block starting with a .? */
    t++;
    if (*t == '\0') return 0;  // a number ending with a '.'
    while (isdigit(*t)) t++;
  }
  }else if (*t == '.'){ /* a number starting with a .? */
 t++;
 if (! isdigit(*t)) return 1;
 while (isdigit(*t)) t++;
  } else return 2;  /* illegal starting value! */
    
  /* optional exponent */
  if (tolower(*t) == 'e') {
 t++;
 if ((*t == '-') || (*t == '+')) {
    t++;
 }
 if (!isdigit(*t))return 3;
 while isdigit(*t) t++;
  }
  /* illegal character */
  if (*t != '\0') return 4;
  return 0;
};


int getnumber(char *s){
   int i = checknumber(s);
   if (i==0) {
      fval = atof(s);
   }
   return i;
};

int main() {
  int i =0;
  int exitnow = 0;
  while (1) {
    fputs(">>", stdout);
    fgets(BUFF, MAXBUFFSIZE-1, stdin);
    char *tok = strtok(BUFF, delims);
    while (tok)  {
      printf("%d %s", ++i, tok);
      if (tok == NULL) break;
     
      // process token.
      int dtype = lexer(tok);
      switch(dtype) {
      case  FNUM:
            printf("FNUM %f\n",fval);
            break;
      case  FADD:
      case  FSUB:
      case  FMUL:
      case  FDIV:
      case  FPRINT:
            printf("[%s]\n", tok);  
     break;
      case  QUIT:
            printf("quitting...\n");
     exitnow = 1;
     break;
      case ERROR:
     printf("ERROR\n");
     break;
      };
      tok = strtok(NULL, delims);
    } 
    if (exitnow) {
       puts("Thanks for using easyforth!\n");
       break;
    }
  };
  return 0;
};



Here is a compilation-run of our recent program version.

toto@toto-VirtualBox:~/Projects/forth$ gcc day2-easyforth.c
toto@toto-VirtualBox:~/Projects/forth$ ./a.out
>>-1.2345 320 7 + * - 
1 -1.2345FNUM -1.234500
2 320FNUM 320.000000
3 7FNUM 7.000000
4 +[+]
5 *[*]
6 -[-]
>>quit
7 quitquitting...
Thanks for using easyforth!

In the next installment we add a simple working calculator.


Wednesday, November 11, 2015

Day 1: A fresh restart, A forth interpreter in C.



I do not know why I stop some projects until they are dead or nearly dead. I have forgotten the components of the last Forth interpreter I wrote, and I'd rather rewrite from scratch. So without further ado, here is my latest attempt for a Forth interpreter. As a start, we simply read from the standard input and prints out the tokens. Forth is simple in that tokens are separated by spaces. Here we allow tabs and new lines.


/
#include 
#include 
#define MAXBUFFSIZE 128

char    BUFF[MAXBUFFSIZE];   // input string buffer.

char delims[] = " \t\n";

int main() {
  int i =0;
  int exitnow = 0;
  while (1) {
    fputs(">>", stdout);
    fgets(BUFF, MAXBUFFSIZE-1, stdin);
    char *tok = strtok(BUFF, delims);
    while (tok)  {
      printf("%d %s\n", ++i, tok);
      if (tok == NULL) break;
      if (strcmp(tok, "quit")==0) {
 printf("quitting...\n");
 exitnow = 1;
 break;
      }
      tok = strtok(NULL, delims);
    } 
    if (exitnow) {
       puts("Thanks for using easyforth!\n");
       break;
    }
  };
  return 0;
}

Here is a run of our preliminary interpreter (without token execution).

toto@toto-VirtualBox:~/Projects/forth$ gcc easyforth.c
toto@toto-VirtualBox:~/Projects/forth$ ./a.out
>>123 456 789 10 + + + .
1 123
2 456
3 789
4 10
5 +
6 +
7 +
8 .
>>

next we shall revise the code above to execute simple arithmetic.


Friday, March 14, 2014

A new Forth interpreter written in C


/
/*
File      forth-and-c.c
Author    Ernesto P. Adorio
          ernesto.adorio@gmail.com
Desc
This simple forth interpreter reads from the command line based on the following
prescription.

loop:
  read
  eval
  print

This version uses double floating point numbers for ease in applications.
Version   0.0.1 march 12, 2014
Compile   gcc -std=gnu99 forth-and-c.c  
*/

#include 
#include 
#include 
#include 



/* Constants */
char* ByeMessage = "Thanks for trying out forth-and-c.\n";
char* WelcomeMessage="Welcome to Forth-and-C Version 0.0.1, March 12, 2014.\n";
    
/* Global interpreter variables. */



#define BUFFMAXLEN 1024 
#define EOI '\0'
 char BUFF[BUFFMAXLEN];
 char * tokenstart, *tokenend = BUFF;
 
 #define MAXSTACKDEPTH 10
 union {
   double f;
   long int i;
 }OPSTACK[MAXSTACKDEPTH];
 int opindex = -1;


char PROMPT[32]= ">> ";

/* token system */
double fnum;  /* number read */
enum tokentype  { FPLUS, FMINUS, FDIV, FMUL, DOT,   BYE,  EMIT,   CR, EOL, FNUM, UNDEFINED};
char* symbols[] ={  "+",  "-",    "/",  "*",  ".",  "bye","emit", "cr" };
int NSYMBOLS=8;

char* errmssgs[] = {"NOERROR", "OVERFLOW", "UNDERFLOW"};
enum errorcodes {NOERROR, OVERFLOW, UNDERFLOW};
int error = NOERROR;


int lex(void)
{  
   /* process token pointed to by token start */
   if (*tokenstart==EOI) {
     return EOL;
   }
   for (int i = 0; i < NSYMBOLS; i++){
      if (strcmp(tokenstart, symbols[i]) == 0){
         return i;
      }   
   }
   
   /* Pure Forth assumes a number only after trying other token types */
   fnum = strtod(tokenstart,NULL);
   return FNUM;
   
   /* Error at this stage! */
   return UNDEFINED;
}p
  
  
int parse(void)
/* Parsing system, splits input line into tokens */
{
   tokenstart = tokenend;
   /* Find location of next space character. */ 
   while (! isspace(*tokenend) &&  *tokenend !=EOI)tokenend++;
   if (*tokenend != EOI){
      *tokenend++='\0';
      return 1;
   } else {
     /* reset tokenend */
     return EOL;
   } 
}


int execute(int toktype)
{
  switch(toktype) {
    case FNUM:if (opindex < MAXSTACKDEPTH) {
                 OPSTACK[++opindex].f = fnum;
              } 
       break;
    case DOT: if (opindex >= 0){
                 printf("%f ", OPSTACK[opindex--].f);
       } else {
  error= UNDERFLOW;
       }; 
       break;
    case FPLUS:  
              OPSTACK[--opindex].f += OPSTACK[opindex + 1].f;
              break;
    case FMINUS:
              OPSTACK[--opindex].f -= OPSTACK[opindex + 1].f;
              break;
    case FMUL:
              OPSTACK[--opindex].f *= OPSTACK[opindex + 1].f;
              break;
    case FDIV:
              OPSTACK[--opindex].f /= OPSTACK[opindex + 1].f;                    
              break;
    case EMIT:putchar( (int) (OPSTACK[opindex--].f));
       break;
    case CR:  /* carriage return */
              putchar(10); putchar(13);
              break;
    default:  break;                  
  };    
};


int main()
{
   int ntokens = 0;
   /* print welcome.*/
   printf("%s", WelcomeMessage);
   
   while (1) {
      /* read input */
      printf("%s", PROMPT);
      fgets(BUFF, BUFFMAXLEN, stdin);
      
      /*reset tokenizer */
      tokenend=BUFF;              
      while (parse()!= EOL) {
 ntokens ++;
 int tokentype = lex();
 // printf("%d: %s %d\n",ntokens, tokenstart, tokentype);
 execute(tokentype);
 
 if (tokentype == BYE) {
   printf("%s", ByeMessage);
  
   return (0);
 }  
 if (error) {
   printf("%s", errmssgs[error]);
   switch(error){
     case UNDERFLOW:opindex= -1; break ;
     case OVERFLOW: opindex= MAXSTACKDEPTH - 1; break;
     default: break;
   }  
   error = 0;
 }
      }
   }
}


We have decided to rewrite our Forth interpreter written in C. Default data type are double floating point numbers and this allows you to use it for processing simple arithmetic problems.

Compile the above using the command line invocation

gcc -std=gnu99 forth-and-c.c
Then run the program by typing ./a.out Type the expression 4 3 * 1 - . You should get the answer 11.


Tuesday, August 20, 2013

Extracting and displaying the Astronomy Photo of the Day in a server.


I am having problems presenting this article. Please be patient.

The most astounding photos in astronomy are posted daily in the NASA site
http://apod.nasa.gov The url of the photo
however do not have the same value everyday, say "apod.jpg", instead the
filename is like "http://apod.nasa.gov/apod/image/1308/sunvenusuv3_dove_960.jpg".
This filename is embedded in the redirected url
"http://apod.nasa.gov/apod/astropix.html".


The image filename is enclosed in an IMG tag.Our hope is that all other html
containing the image file has similar html template.
So we read in this file, extract the filename and build up the image url.
We then use the Linux utility wget to download the image file, then move it
to a fixed destination in our server with a fixed filename apod.jpg.
This way we only "disturb" the NASA site once each day instead of linking
each time a browser visits our weather page which hosts the image.

This is our first version. Python has changed much with new recommended
libraries and we will update the following code to make it more readable and
"Pythonic". We are open to experiment with the regular expression library,
and use the Requests module.


#!/usr/bin/env python

import urllib
import os

 
src = "http://apod.nasa.gov/apod/astropix.html"
strstart="<img SRC=\""
l = len(strstart)

contents = urllib.urlopen(src).read()
startpos = contents.find(strstart)
print "parsing and determining graphics file name"
if startpos:
   endpos = startpos + contents[startpos:].find(".jpg\"")+len(".jpg\"")
   imgurl = "http://apod.nasa.gov/apod/"+contents[startpos+l:endpos-1]
   

   print "copying to destination directory"
   os.system("sudo wget -ct 0 %s" % imgurl)  
   srcfile   = imgurl[imgurl.rfind("/")+1:]

   destfile = "/var/www/xxxxx/xxxx/xxx/apod.jpg"

   #print "storing image file to apod.jpg"
   os.system("sudo cp  %s %s" % (srcfile, destfile))
To see how it works out, please click on our weather http://adorio-research.org/wordpress/?page_id=5833 page.

Wednesday, November 14, 2012

Programming in R, computing determinant of matrix.


Assume that the matrix is square with number of rows greater than or equal to 2.
The determinant of the 2 by 2 matrix


$
A = \begin{array}{ll}
a_{11} & a_{12}\\
a_{21} & a_{22} \\
\end{array}
$

is given by A[1,1]* A[2,2] - A[2,1] * A[1,2]. To be continued.....

$\sum_{\forall j} A[1,j] * (-1) ^ {j+1} *det(A[-1,-j]$

where A[-1, -j] denotes the submatrix obtained by deleting the first row and the jth column! R has a clever method of denoting the row or column to be deleted.


here is a simple recursive implementation with debugging statements. We ask the reader to remove them and simplify the code.

"""
# file    mydet.R
# author  your name here!


mydet <- function (A) {
    rows <-nrow(A)
    print (c("rows=", rows))
    if (rows != ncol(A)) {
       print("A is not a square matrix!!!")
    }
    if (rows == 2) {
       result <- (A[1,1] * A[2,2] - A[2,1] * A[1,2])
       print (c("result=", result))
       return(result)
    }

    # expand by first row.
    tot = 0.0
    sign = 1
    for (j in seq(1, rows)){
       tot  = tot + sign * A[1,j] * mydet(A[-1,-j])
       sign = -sign
    }
    return(tot)
}


Sunday, September 23, 2012

Friday, August 24, 2012

Finding all locations of substring in a string.


There are a lot of methods for fining all locations of a substring substr in a string s, and if we ever find ourselves teaching again Python, I would first emphasize the simplest algorithm to do so.

We repeatedly use the basic string object find function. If s is a string and substr is a string pattern (no wild cards!) then s.find(substr) will -1 if substr is not found in s, otherwise it will return the starting index of substr in s.

Here is our function for findind all occurence of substr in a string:


"""
def findall(s, substr):
   """
   Find all locations of substr in s.
   """
   out = []
   oldpos = 0
   n = len(substr)
   while (1):
     pos = s[oldpos:].find(substr)
     if pos >=0:
        out.append(oldpos + pos)
        oldpos += (pos+n+1) #remove +n if you want to find occurences starting within substr also!
     else:
        break
   return out
 

if __name__ == "__main__":
   s   = 'the quick brown fox jumps over the lazy dog near the bank of the river.'
   sub = 'the'
   x=  findall(s, sub)
   print x
   for v in x:
      print s[v:v+len(sub)]

The string find function can actually perform a search using a sprcified starting and ending indices. Thus s[oldpos:].find(substr) may be rewritten as s.find(substr, oldpos). We ask the reader to experiment by modifying the above code.

Help on built-in function find:

find(...)
    S.find(sub [,start [,end]]) -> int
    
    Return the lowest index in S where substring sub is found,
    such that sub is contained within S[start:end].  Optional
    arguments start and end are interpreted as in slice notation.
    
    Return -1 on failure.


Other methods may be searched in Google. Here are some links to get you started in learning alternative and complicated approaches:

Saturday, July 7, 2012

Two giants of computing who died in the same month!



This image from a facebook posting emphasized the importance of both Steve Jobs and Dennis Ritchie.




Wednesday, February 1, 2012

Python, finding nearest matching color name for RGB values




There are 147 standard color names for use in HTML. here is a simple Python code to find the nearest matching color name given input R,G, B values (from 0-255). The minimization criterion is the sum of absolute vaues of the differences from the color r, g, b values of the colornames.


"""
File    colornames.py
Author  Ernesto P. Adorio, Ph.D
Version 0.0.1 February 1, 2012
"""


# Src: http://www.w3schools.com/html/html_colornames.asp
lines = """AliceBlue  #F0F8FF   Shades Mix
AntiqueWhite  #FAEBD7   Shades Mix
Aqua  #00FFFF   Shades Mix
Aquamarine  #7FFFD4   Shades Mix
Azure  #F0FFFF   Shades Mix
Beige  #F5F5DC   Shades Mix
Bisque  #FFE4C4   Shades Mix
Black  #000000   Shades Mix
BlanchedAlmond  #FFEBCD   Shades Mix
Blue  #0000FF   Shades Mix
BlueViolet  #8A2BE2   Shades Mix
Brown  #A52A2A   Shades Mix
BurlyWood  #DEB887   Shades Mix
CadetBlue  #5F9EA0   Shades Mix
Chartreuse  #7FFF00   Shades Mix
Chocolate  #D2691E   Shades Mix
Coral  #FF7F50   Shades Mix
CornflowerBlue  #6495ED   Shades Mix
Cornsilk  #FFF8DC   Shades Mix
Crimson  #DC143C   Shades Mix
Cyan  #00FFFF   Shades Mix
DarkBlue  #00008B   Shades Mix
DarkCyan  #008B8B   Shades Mix
DarkGoldenRod  #B8860B   Shades Mix
DarkGray  #A9A9A9   Shades Mix
DarkGrey  #A9A9A9   Shades Mix
DarkGreen  #006400   Shades Mix
DarkKhaki  #BDB76B   Shades Mix
DarkMagenta  #8B008B   Shades Mix
DarkOliveGreen  #556B2F   Shades Mix
Darkorange  #FF8C00   Shades Mix
DarkOrchid  #9932CC   Shades Mix
DarkRed  #8B0000   Shades Mix
DarkSalmon  #E9967A   Shades Mix
DarkSeaGreen  #8FBC8F   Shades Mix
DarkSlateBlue  #483D8B   Shades Mix
DarkSlateGray  #2F4F4F   Shades Mix
DarkSlateGrey  #2F4F4F   Shades Mix
DarkTurquoise  #00CED1   Shades Mix
DarkViolet  #9400D3   Shades Mix
DeepPink  #FF1493   Shades Mix
DeepSkyBlue  #00BFFF   Shades Mix
DimGray  #696969   Shades Mix
DimGrey  #696969   Shades Mix
DodgerBlue  #1E90FF   Shades Mix
FireBrick  #B22222   Shades Mix
FloralWhite  #FFFAF0   Shades Mix
ForestGreen  #228B22   Shades Mix
Fuchsia  #FF00FF   Shades Mix
Gainsboro  #DCDCDC   Shades Mix
GhostWhite  #F8F8FF   Shades Mix
Gold  #FFD700   Shades Mix
GoldenRod  #DAA520   Shades Mix
Gray  #808080   Shades Mix
Grey  #808080   Shades Mix
Green  #008000   Shades Mix
GreenYellow  #ADFF2F   Shades Mix
HoneyDew  #F0FFF0   Shades Mix
HotPink  #FF69B4   Shades Mix
IndianRed   #CD5C5C   Shades Mix
Indigo   #4B0082   Shades Mix
Ivory  #FFFFF0   Shades Mix
Khaki  #F0E68C   Shades Mix
Lavender  #E6E6FA   Shades Mix
LavenderBlush  #FFF0F5   Shades Mix
LawnGreen  #7CFC00   Shades Mix
LemonChiffon  #FFFACD   Shades Mix
LightBlue  #ADD8E6   Shades Mix
LightCoral  #F08080   Shades Mix
LightCyan  #E0FFFF   Shades Mix
LightGoldenRodYellow  #FAFAD2   Shades Mix
LightGray  #D3D3D3   Shades Mix
LightGrey  #D3D3D3   Shades Mix
LightGreen  #90EE90   Shades Mix
LightPink  #FFB6C1   Shades Mix
LightSalmon  #FFA07A   Shades Mix
LightSeaGreen  #20B2AA   Shades Mix
LightSkyBlue  #87CEFA   Shades Mix
LightSlateGray  #778899   Shades Mix
LightSlateGrey  #778899   Shades Mix
LightSteelBlue  #B0C4DE   Shades Mix
LightYellow  #FFFFE0   Shades Mix
Lime  #00FF00   Shades Mix
LimeGreen  #32CD32   Shades Mix
Linen  #FAF0E6   Shades Mix
Magenta  #FF00FF   Shades Mix
Maroon  #800000   Shades Mix
MediumAquaMarine  #66CDAA   Shades Mix
MediumBlue  #0000CD   Shades Mix
MediumOrchid  #BA55D3   Shades Mix
MediumPurple  #9370D8   Shades Mix
MediumSeaGreen  #3CB371   Shades Mix
MediumSlateBlue  #7B68EE   Shades Mix
MediumSpringGreen  #00FA9A   Shades Mix
MediumTurquoise  #48D1CC   Shades Mix
MediumVioletRed  #C71585   Shades Mix
MidnightBlue  #191970   Shades Mix
MintCream  #F5FFFA   Shades Mix
MistyRose  #FFE4E1   Shades Mix
Moccasin  #FFE4B5   Shades Mix
NavajoWhite  #FFDEAD   Shades Mix
Navy  #000080   Shades Mix
OldLace  #FDF5E6   Shades Mix
Olive  #808000   Shades Mix
OliveDrab  #6B8E23   Shades Mix
Orange  #FFA500   Shades Mix
OrangeRed  #FF4500   Shades Mix
Orchid  #DA70D6   Shades Mix
PaleGoldenRod  #EEE8AA   Shades Mix
PaleGreen  #98FB98   Shades Mix
PaleTurquoise  #AFEEEE   Shades Mix
PaleVioletRed  #D87093   Shades Mix
PapayaWhip  #FFEFD5   Shades Mix
PeachPuff  #FFDAB9   Shades Mix
Peru  #CD853F   Shades Mix
Pink  #FFC0CB   Shades Mix
Plum  #DDA0DD   Shades Mix
PowderBlue  #B0E0E6   Shades Mix
Purple  #800080   Shades Mix
Red  #FF0000   Shades Mix
RosyBrown  #BC8F8F   Shades Mix
RoyalBlue  #4169E1   Shades Mix
SaddleBrown  #8B4513   Shades Mix
Salmon  #FA8072   Shades Mix
SandyBrown  #F4A460   Shades Mix
SeaGreen  #2E8B57   Shades Mix
SeaShell  #FFF5EE   Shades Mix
Sienna  #A0522D   Shades Mix
Silver  #C0C0C0   Shades Mix
SkyBlue  #87CEEB   Shades Mix
SlateBlue  #6A5ACD   Shades Mix
SlateGray  #708090   Shades Mix
SlateGrey  #708090   Shades Mix
Snow  #FFFAFA   Shades Mix
SpringGreen  #00FF7F   Shades Mix
SteelBlue  #4682B4   Shades Mix
Tan  #D2B48C   Shades Mix
Teal  #008080   Shades Mix
Thistle  #D8BFD8   Shades Mix
Tomato  #FF6347   Shades Mix
Turquoise  #40E0D0   Shades Mix
Violet  #EE82EE   Shades Mix
Wheat  #F5DEB3   Shades Mix
White  #FFFFFF   Shades Mix
WhiteSmoke  #F5F5F5   Shades Mix
Yellow  #FFFF00   Shades Mix
YellowGreen  #9ACD32"""

def rgbfromstr(s):
    # s starts with a #.
    r, g, b = int(s[1:3],16), int(s[3:5], 16),int(s[5:7], 16)
    return r, g, b

def findnearestcolorname(R,G, B, colorD):
    mindiff = None

    for d in colorD:
       r, g, b = rgbfromstr(colorD[d])
       diff = abs(R -r)*256 + abs(G-g)* 256 + abs(B- b)* 256 
       if mindiff is None or diff < mindiff:
          mindiff = diff
          mincolorname = d
    return mincolorname
 

if __name__ == "__main__":
  D={}
  for line in lines.split("\n"):
    tokens = line.split()
    if len(tokens) > 1:
        D[tokens[0]]= tokens[1]
     
  R, G, B = 0, 127, 127
  colorname = findnearestcolorname(0, 127, 127, D)
  print hex(R), hex(G), hex(B)
  print colorname, D[colorname]
 

When the above program runs, it outputs


$ python colornames.py
0x0 0x7f 0x7f
Teal #008080



Questions.

1. Modify the minimizaiton criterion to use least sum of squares of the differences.

2. Provide error checking for input R, G, B values to be within the interval [0, 255].

3. Procide different ways to specify the input RGB values, aside from the (R, G, B) values as done in the program above.

Wednesday, January 25, 2012

Simple floating point arithmetic for simple-forth

Here is our latest incarnation of simple-forth, a forth interpreter written in C.
This time we add floating point arithmetic capabilities. There are two basic ways to incorporate floating point capabilities. One is using the same integer stack and the other is using a separate foating point stack.



We use a separate floating point stack with maximum 32 elements. in our newest version shown below for simplicity. The built-in integer stack is 32 bits wide. Floating point numbers in our interpreter are 64 bit wide. The current stack element index is indicated by FP. The basic floating point operations are f+, f-, f*, f/ these Forth words are the equivalent floating point words corresponding to the built-in basic + - * / operator words



:


/*
file     simple-forth-0.0.3.c
author   Dr. Ernesto P. Adorio
         UPDEPP (University of the Philippines,
         Extension Program in Pampanga
         Clarkfield, Pampanga
email    ernesto.adorio@gmail.com
version  0.0.1 January 14, 2012 basic interpreter.
         0.0.2 January 16, 2012 interactivity added.
         0.0.3 January 25, 2012 basic floating point.
*/

#include 
#include 
#include 
#include 



enum {E_STACKUNDERFLOW, E_FSTACKUNDERFLOW} ERRCODES;


enum {L_EMIT, L_DOT,L_DOTT, L_SPACE, L_ADD, L_SUB, L_MUL, L_DIV, L_DROP, L_INT32, L_CR,
      L_FNUM, L_FPLUS, L_FSUB, L_FMUL, L_FDIV, L_FDOT, L_FDOTT, L_FDROP,
      L_BYE, L_EOS,L_ERROR} OPCODES;

const char *stdwords[] = { "emit", ".",  ".t", "space", "+", "-", "*", "/", "drop", "int32", "cr",
                           "fnum", "f+", "f-", "f*" ,"f/", "f.","f.t","fdrop",
                           "bye",
                           "\n",
                         };
// "int32" and "fnum" are dummies. 


#define MAXSTKLEN 32
#define MAXFSTKLEN 32
#define MAXTOKENLEN 128

int  LENSTDWORDS = sizeof(stdwords)/sizeof(stdwords[0]);
char LINEBUFFER[256];
char *goodbye= "bye";
int  ERRCODE = 0;
int SP = -1;   /* stack pointer index */
int stack[MAXSTKLEN];

int  opcode;
char *tokstart;
char *tokend;

int FP = -1;   /* floating point stack index */
double fstack[MAXFSTKLEN];


int numbertype(char *s) 
{
   /*
   Returns 
     0 - not a number!
     1 - an integer
     2 - a floating point number
   */
   
   char *t = s;
   while (isspace(*t)) t++;
   if (*t == '\0') return 0;
    
   if (*t == '+' || *t == '-') t++;
   if (*t == '\0') return 0;
   while (isdigit(*t)) t++;
   if (*t == '\0') {
     return 1; // an integer!
   }
  
   if (*t == '.') t++;
   while (isdigit(*t)) t++;
   if (*t == '\0') return 2;
   
   if (*t == 'e') t++;
   if (*t == '\0') return 0; // error!
   if (*t == '+' || *t == '-') t++;
   if (*t == '\0') return 0; // error!
   while (isdigit(*t)) t++;
   if (*t == '\0') return 2; // a floating point number!
   return 0; // not an integer or floating point.
}





int eval(int opcode)
{
    /* Evaluate opcode */
    switch (opcode){
    case L_EMIT: 
      //@@printf("opcode L_EMIT %s %d\n", tokstart, SP);
      if (SP < 0) {
     ERRCODE = E_STACKUNDERFLOW;
      } else {
        printf ("%c", stack[SP--]);
      }
      break;

    case L_DOT:
      printf("opcode L_EMIT %s %d\n", tokstart, SP);
      if (SP < 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
      } else {
        printf ("%d", stack[SP--]);
      }
      break;

    case L_DOTT:
      //@@printf("opcode L_EMIT %s %d\n", tokstart, SP);
      if (SP < 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
      } else {
        printf ("%d", stack[SP]);
      }
      break;
      
    case L_SPACE:
      printf ("%c", 32);
      break;
      
    case L_ADD:
      //printf("opcode L_ADD %s\n", tokstart);
      if (SP <= 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
     break;
      } 
      stack[SP-1] += stack[SP];
      SP--;
      break;
      
    case L_SUB:
      //printf("opcode L_SUB %s\n", tokstart);
      if (SP <= 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
     break;
      } 
      stack[SP-1] -= stack[SP];
      SP--;
      break;
      
    case L_MUL:
      //printf("opcode L_MUL %s\n", tokstart);
      if (SP <= 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
     break;
      } 
      stack[SP-1] *= stack[SP];
      SP--;
      break;
      
    case L_DIV:
      //printf("opcode L_DIV %s\n", tokstart);
      if (SP <= 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
     break;
      } 
      stack[SP-1] /= stack[SP];
      SP--;
      break;
  
   case L_INT32:
      //printf("opcode L_INT32 %s\n",tokstart);
      stack[++SP]= atoi(tokstart);
      // printf("@@@ pushing an integer!");
      break;
      
    case L_DROP:
      //printf("opcode L_DROP %s \n", tokstart);
      SP=SP -1;
      break;
      
    case L_CR:
      // printf("opcode L_CR %s \n", tokstart);
      printf("\n");
      break;


/* simple floating point features */
    case L_FNUM:
      //printf("floating point number %s\n",tokstart);
      fstack[++FP]= atof(tokstart);
      break;
    
    case L_FPLUS:
      if (FP <= 0) {
     ERRCODE = E_FSTACKUNDERFLOW;
     printf("%s", "fstack underflow!");
     break;
      } 
      fstack[FP-1] += fstack[FP];
      FP--;
      break;

    case L_FSUB:
      if (FP <= 0) {
     ERRCODE = E_FSTACKUNDERFLOW;
     printf("%s", "fstack underflow!");
     break;
      } 
      fstack[FP-1] -= fstack[FP];
      FP--;
      break;

    case L_FMUL:
      if (FP <= 0) {
     ERRCODE = E_FSTACKUNDERFLOW;
     printf("%s", "fstack underflow!");
     break;
      } 
      fstack[FP-1] *= fstack[FP];
      FP--;
      break;

    case L_FDIV:
      if (FP <= 0) {
     ERRCODE = E_FSTACKUNDERFLOW;
     printf("%s", "fstack underflow!");
     break;
      } 
      fstack[FP-1] /= fstack[FP];
      FP--;
      break;

    case L_FDOT:
      printf("opcode FDOT %s\n", tokstart);
      if (FP < 0) {
     ERRCODE = E_FSTACKUNDERFLOW;
     printf("%s", "underflow!");
      } else {
        printf ("%f", fstack[FP--]);
      }
      break;

    case L_FDOTT:
      //@@printf("opcode L_EMIT %s %d\n", tokstart, SP);
      if (SP < 0) {
     ERRCODE = E_FSTACKUNDERFLOW;
     printf("%s", "underflow!");
      } else {
        printf ("%f", fstack[FP]);
      }
      break;
      
    case L_BYE:
      printf("Terminating... ");
      break;
    default:
      ;
      break;
    }  
   
}

void nexttoken()
{   
    tokstart = tokend;
    //@ printf("inside nexttoken [%s]", tokstart);
    
    /* ignore leading white spaces */
    while (isspace(*tokstart)) tokstart++;

    /* find terminating space of end of string */
    tokend = tokstart;
    while (!isspace(*tokend) && *tokend != '\0') tokend++;
    
    /* string terminator */
    if (*tokend != '\0') {
      *tokend = '\0';
      tokend ++;
    } 

    /* get opcode */
    opcode = -1; 
    if (tokend == tokstart) {
       opcode = L_EOS;
       return;
    }

    //@@@ printf("token [%s]\n", tokstart); 
    for (int i =0; i < LENSTDWORDS; i++) {
      if (strcmp(stdwords[i], tokstart) == 0){
 opcode = i;
        break;
      }
    }
    if (opcode != -1) {
       return;
    }

    int ntype = numbertype(tokstart); 
    if (ntype == 1){
      /* is this a number ?*/
      opcode = L_INT32;
    } else if (ntype == 2) {
      opcode = L_FNUM;
    } else if (opcode == -1){
      opcode = L_ERROR;
    };
}



int main(){
  while (1) {
    printf("> ");
    if (fgets(LINEBUFFER, 250, stdin)!= NULL) {
      tokend=LINEBUFFER;
    } else {
      tokend= goodbye;
    }
    while (1) {
      nexttoken();
      eval(opcode);
      if (opcode == L_BYE) {
 return 0;
      }
      if (opcode ==L_EOS) {
 break;
      }
      if (ERRCODE != 0) {
 printf("ERRORCODE [%d]", ERRCODE);
 break;
      };
    }
  }
  printf("\n");
  return 0;
}



Here is compilation and a simple execution run.

gcc simple-forth-0.0.3.c -g -std=c99 -o simple-forth
toto@toto-Aspire-4520:~/Blogs/my-other-life-as-programmer/forth$ ./simple-forth
> 23.34 -56.12 f* f. 
-1309.840800> bye
Terminating... 

Dont forget: a floating point number has a comma or an exponent in our simple-forth implementation.

Tuesday, January 24, 2012

Terminal interactivity added to simple-forth.

Our previous Forth interpreter processed only fixed strings. To add interactivity from a console or terminal, we have to read an input string to a buffer. There is more than one way, we may use scanf. Another one, much better is fgets which avoids buffer overruns. Here is our version 0.0.2 with terminal interactivity.

/*
file     simple-forth-0.0.2.c
author   Dr. Ernesto P. Adorio
         UPDEPP (University of the Philippines,
         Extension Program in Pampanga
         Clarkfield, Pampanga
email    ernesto.adorio@gmail.com
version  0.0.1 January 14, 2012 basic interpreter.
         0.0.2 January 16, 2012 interactivity added.
*/

#include 
#include 
#include 
#include 



enum {E_STACKUNDERFLOW} ERRCODES;


enum {L_EMIT, L_DOT,L_DOTT, L_SPACE, L_ADD, L_SUB, L_MUL, L_DIV, L_DROP, L_INT32, L_CR,  L_BYE, L_EOS,L_ERROR} OPCODES;
const char *stdwords[] = { 
"emit",
".", 
".t",
"space",
"+",
"-",
"*",
"/",
"drop",
"int32",
"cr",
"bye",
"\n",
};

#define MAXSTKLEN 32
#define MAXFSTKLEN 32
#define MAXTOKENLEN 128

int  LENSTDWORDS = sizeof(stdwords)/sizeof(stdwords[0]);
char LINEBUFFER[256];
char *goodbye= "bye";
int  ERRCODE = 0;
int SP = -1;   /* stack pointer index */

int    stack[MAXSTKLEN];
double fstack[MAXFSTKLEN];

int  opcode;
char *tokstart;
char *tokend;






int eval(int opcode)
{
    /* Evaluate opcode */
    switch (opcode){
    case L_EMIT: 
      //@@printf("opcode L_EMIT %s %d\n", tokstart, SP);
      if (SP < 0) {
     ERRCODE = E_STACKUNDERFLOW;
      } else {
        printf ("%c", stack[SP--]);
      }
      break;

    case L_DOT:
      //@@printf("opcode L_EMIT %s %d\n", tokstart, SP);
      if (SP < 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
      } else {
        printf ("%d", stack[SP--]);
      }
      break;

    case L_DOTT:
      //@@printf("opcode L_EMIT %s %d\n", tokstart, SP);
      if (SP < 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
      } else {
        printf ("%d", stack[SP]);
      }
      break;
      
    case L_SPACE:
      printf ("%c", 32);
      break;
      
    case L_ADD:
      //printf("opcode L_ADD %s\n", tokstart);
      if (SP <= 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
     break;
      } 
      stack[SP-1] += stack[SP];
      SP--;
      break;
      
    case L_SUB:
      //printf("opcode L_SUB %s\n", tokstart);
      if (SP <= 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
     break;
      } 
      stack[SP-1] -= stack[SP];
      SP--;
      break;
      
    case L_MUL:
      //printf("opcode L_MUL %s\n", tokstart);
      if (SP <= 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
     break;
      } 
      stack[SP-1] *= stack[SP];
      SP--;
      break;
      
    case L_DIV:
      //printf("opcode L_DIV %s\n", tokstart);
      if (SP <= 0) {
     ERRCODE = E_STACKUNDERFLOW;
     printf("%s", "underflow!");
     break;
      } 
      stack[SP-1] /= stack[SP];
      SP--;
      break;
    case L_INT32:
      //printf("opcode L_INT32 %s\n",tokstart);
      stack[++SP]= atoi(tokstart);
      break;
      
    case L_DROP:
      //printf("opcode L_DROP %s \n", tokstart);
      SP=SP -1;
      break;
      
    case L_CR:
      // printf("opcode L_CR %s \n", tokstart);
      printf("\n");
      break;
    default:
      ;
      break;
    }  
   
}

void nexttoken()
{   
    tokstart = tokend;
    //@ printf("inside nexttoken [%s]", tokstart);
    
    /* ignore leading white spaces */
    while (isspace(*tokstart)) tokstart++;

    /* find terminating space of end of string */
    tokend = tokstart;
    while (!isspace(*tokend) && *tokend != '\0') tokend++;
    
    /* string terminator */
    if (*tokend != '\0') {
      *tokend = '\0';
      tokend ++;
    } 

    /* get opcode */
    opcode = -1; 
    if (tokend == tokstart) {
       opcode = L_EOS;
       return;
    }

    /*@@@ printf("token [%s]\n", tokstart); */
    for (int i =0; i < LENSTDWORDS; i++) {
      if (strcmp(stdwords[i], tokstart) == 0){
 opcode = i;
 //@ printf("opcde [%d]", opcode);
        break;
      }
    }
    if (opcode == -1){
      opcode = L_INT32;
    }
}



int main(){
  while (1) {
    // read string.
    printf("> ");
    if (fgets(LINEBUFFER, 250, stdin)!= NULL) {
      tokend=LINEBUFFER;
      // @@@ printf("input string [%s]", LINEBUFFER);
    } else {
      tokend= goodbye;
    }
    // eval
    // printf ("Entering evaluation loop.\n");
    while (1) {
      nexttoken();
      //@ printf ("[%d] %s", opcode, tokstart);
      eval(opcode);
      if (opcode== L_BYE) {
 //printf ("%% opcode is L_BYE");
 return 0;
      }
      if (opcode ==L_EOS) {
 break;
      }
      if (ERRCODE != 0) {
 printf("ERRORCODE [%d]", ERRCODE);
 break;
      };
    }
    // loop back unless BYE!
  }
  printf("\n");
  return 0;
}

Save file to simple-forth-0.0.2.c, then compile it using the following command:

: gcc simple-forth.c -std=c99 -o simple-forth-0.0.2

Then run it by issuing ./simple-forth00.0.2 Here is an uninspired terminal run:

> 2 3 - 1 + .
0> 56 emit
8> 97 emit
a> 64 emit
@> 
> 
> bye

Next, we will add add a floating point computation capabilities using a separate stack.



Tuesday, January 17, 2012

Tiobe rankings of programming languages

Click on for the latest popularity rankings of programming languages. It is not based on absolute value but on the relative change of market share.

For January 2012, Objective C showed the fastest growth. Click on the link for the the definition of the Tiobe index.


The next popular is C# followed by C and Javascript. On the other hand, based on absolute market share, the top languages are Java, C, C#, C++, Objective-C, PHP and Visual Basic. Our favorite language Python is at #8. Interesting to note that the statistical software R is at #19.








Saturday, January 14, 2012

Does a number string represents an integer or a floating value in C?

I got the shock of my blogging life when I cannot access an old post about the evils of the C function atof. Here is a code which return 1 for integers and 2 for floating point and 0 if not a valid integer or a valid float.

/*
author  Ernesto P. Adorio
        UPDEPP (University of the 
        Philippines, Extension Program
        in Pampanga, Clarkfield, Pampanga
email   ernesto. adorio@ gmail.com [remove spaces]
version 0.0.1 january 14, 2012
*/

#include 
#include 


int numbertype(char *s) 
{
   char *t = s;
   while (isspace(*t)) t++;
   if (*t == '\0') return 0;
    
   // number sign
   printf("ltrimmed [%s]", t);
   if (*t == '+' || *t == '-') t++;
   if (*t == '\0') return 0;
   printf("after sign [%s]", t);
   while (isdigit(*t)) t++;
   printf("after digits [%s]", t);
   if (*t == '\0') return 1; // an integer!
   
   // floating point??
   printf ("decimal point? [%s] ", t);  
   if (*t == '.') t++;
   printf ("fractional digits?");
   while (isdigit(*t)) t++;
   if (*t == '\0') return 2;
   
   // exponent part.
   printf ("testing exponent part %s", t); 
   if (*t == 'e') t++;
   printf ("after 'e' ");  
   if (*t == '\0') return 0; // error!
   printf ("sign after e?", t);  
   if (*t == '+' || *t == '-') t++;
   printf("%s", t);  
   if (*t == '\0') return 0; // error!
   while (isdigit(*t)) t++;
   if (*t == '\0') return 2; // a floating point number!
   return 0; // not an integer or floating point.
}

int main() 
{
  printf("numtype =[%d]", numbertype("-123.34")); 
};

Remove the deubgging printf statements when you use it for applications.

When the program is run, it returns a code of 2 to denote a floating point number, a 1 for an integer, and a 0 if not a number.


A basic Forth language interpreter (non-interactive)

Last time we showed a simple tokenizer for a Forth interpreter. We find it easier to combine the ideas in that post to create a simple Forth engine which process a simple string.

We will expound further on this until we successfully build a compiler for a non-standard Forth language.

Have fun working on this. The current version works on simple strings but specified on the source code itself. We will introduce interactivity and expand the capabilities of this simple Forth interpreter.



/*
file     simple-forth.c
author   Dr. Ernesto P. Adorio
         UPDEPP (University of the Philippines,
         Extension Program in Pampanga
         Clarkfield, Pampanga
email    ernesto.adorio@gmail.com
version  0.0.1 January 14, 2012
*/

#include 
#include 
#include 
#include 


#define MAXSTKLEN 32
#define MAXTOKENLEN 128

enum {L_EMIT, L_ADD, L_SUB, L_MUL, L_DIV, L_POP, L_INT32, L_CR, L_ERROR} OPCODES;
const char *stdwords[] = { 
".", 
"+",
"-",
"*",
"/",
"pop",
"int32",
"cr",
};


int LENSTDWORDS = 8;

int stack[MAXSTKLEN];
int SP = 0;   /* stack pointer index */

int main(){
  char tokens[] = "   123 34 + . cr 567 -3456 * . cr";
  char *tokstart = tokens;
  char *tokend = tokstart;
  int  opcode;

  /* @@@ printf("tokstart: %s\n", tokstart);*/

  tokend = tokens;

  while (1) {
    tokstart = tokend;
    /* ignore leading white spaces */
    while (isspace(*tokstart)) tokstart++;

    /* find terminating space of end of string */
    tokend = tokstart;
    while (!isspace(*tokend) && *tokend != '\0') tokend++;
    
    /* string terminator */
    if (*tokend != '\0') {
      *tokend = '\0';
      tokend ++;
    } else {
      break;
    } 

    /* get opcode */
    opcode = -1; 
    /*@@@ printf("token [%s]\n", tokstart); */
    for (int i =0; i < LENSTDWORDS; i++) {
      if (strcmp(stdwords[i], tokstart) == 0){
 opcode = i;
        break;
      }
    }
    if (opcode == -1){
      opcode = L_INT32;
    }


    /* Evaluate opcode */
    switch (opcode){
    case L_EMIT: 
      //printf("opcode L_EMIT %s \n", tokstart);
      printf ("%d", stack[SP--] );
      break;
    case L_ADD:
      //printf("opcode L_ADD %s\n", tokstart);
      stack[SP-1] += stack[SP];
      SP--;
      break;
    case L_SUB:
      //printf("opcode L_SUB %s\n", tokstart);
      stack[SP-1] += stack[SP];
      SP--;
      break;
    case L_MUL:
      //printf("opcode L_MUL %s\n", tokstart);
      stack[SP-1] *= stack[SP];
      SP--;
      break;
    case L_DIV:
      //printf("opcode L_DIV %s\n", tokstart);
      stack[SP-1] /= stack[SP];
      SP--;
      break;
    case L_INT32:
      //printf("opcode L_INT32 %s\n",tokstart);
      stack[++SP]= atoi(tokstart);
      break;
    case L_POP:
      //printf("opcode L_POP %s \n", tokstart);
      SP--;
      break;
    case L_CR:
      // printf("opcode L_CR %s \n", tokstart);
      printf("\n");
    }  
  }
  printf("\n");
  return 0;
}
Save the code to a file simple-forth.c, then compile using the following command line on the directory where the source file is stored. gcc simple-forth.c -std=c99 -o forth It should compile cleanly, then execute the executible by issuing ./forth When the program runs, it prints out
toto@toto-Aspire-4520:~/Blogs/my-other-life-as-programmer/forth$ ./forth
157
-1959552


Tuesday, October 18, 2011



Testing latex server by watchmath.com.

The are of a triangle is $\frac{1}{2}b*h$.

I thought this was working already! Oh, I have to redo the installation.

January 15, 2012: This is making me sick! this does not work anymore! I changed to mathjax latex server. For instructions, refer to tex.stackexchange.com

Thursday, October 13, 2011

Dennis Ritchie (September 9, 1941 – October 8, 2011: inventor of C programming language

One of my regrets in life is not having to meet in person Dennis Ritichie, the developer of the C programmng language.



I will never forget the time I have to understand pointers (I suspect my instructor did not understand much too!). C is like more a friendlier assembly language in English! C++, Java may be more "in" these days, but they owe their success to the pioneering path blazed by C.

Wednesday, October 12, 2011

Python: Permutations, Combinations, Cartesian Products with Itertools module

Python itertools module has built-in functions for permutations, combinations, cycles and products.
So the Python programmers can focus on building the next killer-apps :) which will dominate the whole world, instead
of reading obtuse treatises, papers, and other publications on algorithms for generating combinatorial objects.

Here we list the combinatorial capabilities of Python (versions 2.6+) in the itertools module.


  • Permutations


    itertools.permutation create a permutation object from an iterable input or string. You can list
    the successive permutations by using object.next() or by creating a list (a bad idea if the size of the object is large!)
    list(object). Here is an example:

    x = itertools.permutation(range(7))
       try:
          while True:
            print x.next()
       except:
          pass
    

    You can also do:

    x = itertools.permutation(range(7))
       for i, e in enumerate(list(x)):
           print i+1, e
    

    Converting to a list give rise to a dangerous situation where you can run out of memory!. but if you know that it can be safely stored,
    by all means use a list conversion.

    Permutations can also accept an extra parameter r so you can generate all permutations of size n of the object taken r at a time.
    The number of elements in such permutations is given by n!/(n-r)!. If r is not specified, then the number of permutations is n!
    which look innocous.(50! is nothing to sneeze at).

  • combinations

  • itertools.combinations creates a combinatorial object. Here ordering does not matter. As an example, the combinations of 6 elements taken 3 at a time can be listed in two groups, as follows:
    import itertools
    
    seq = range(6)
    x = itertools.combinations(seq, 3)
    
    try:
      for i, e in list(enumerate(x)):
         f = [y for y in seq if y not in e]
         print i+1, list(e), f
    except:
       pass
    
    The output of permutations and combinations are tuples for fast execution of the functions, and have to be typecast to a list. Itertools also provide combinations with replacement. The best way to see the difference with the standard combinations is to see them in action from the command line:
    x = combinations_with_replacement([1,2,3,4], 2)
    y = combinations([1,2,3,4], 2)
    
    list(x)
    [(1, 1),
     (1, 2),
     (1, 3),
     (1, 4),
     (2, 2),
     (2, 3),
     (2, 4),
     (3, 3),
     (3, 4),
     (4, 4)]
    
    list(y)
    [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
    
  • Cartesion products


    Itertools has cartesian products! So instead of writing (this from the documentation)

    ((x,y) for x in A for y in B)

    we simply write product(A,B)

    Wait, how about the cartesian product of A with itself?
    you can write product(A,A) or if you want more, product(A,A,A,A). The latter can be written as
    product(A, repeat=4). Python programmers can be lazy as Perl programmers!

  • cycle





  • Not strictly referrring to a mathematical object. Rather it refers to the way an element in an
    iterable is accessed. Instead of stopping at the last element, the access is cycled back to the first element.
    Try this on the command line (not running in a script file)

    x = cycle((1,2,3,4))
    while True:
       print x.next()
    

    You will notice that this loop never terminates, and after the 4 is printed, the next element to be printed is the first element.
    Type Ctrl-C to abort the printing.


Aside from these basic combinatorial objects, Itertools provide now a repeat function! For example, a list of 100
elements with all values equal to 5: [5] * 100 can now be written as itertools.repeat(5, 100). Easier to understand for beginners.


Dont you just love Python?

Hopefully, Python will offer genuine cycle objects (where you can multiply two cycles) and derangements with basic functions such as nPr and nCr. These combinatorial features are solutions waiting for problems and applications!

TO BE CONTINUED.

Saturday, October 1, 2011

Programming Problems: Replace numbers in a list by an increasing sequence.

Consider X = [1, 5, 7, 1, 34]. We want to replace this by X = [1,3,2,1,4].
Consider X = [1000, 500, 700, 5000, 700]. We want to replace this by [3, 1,2,4,2].

Criteria:
1. Use Python. Sorry no java.
2. Fewest lines of code.
3. Elegant, not to use a temporary copy and not using a convoluted BRUTE force method as in the following example, yes I wrote it but that was a temporary solution. I refuse to give a hint, but Python has a powerful discrete math function :)


tempR = X[:]
        for j in range(1, n+1):
            minrank =  min(tempR)
            for k in range(n):
                if X[k] == minrank and k< n+1:
                    X[k] = j
                    tempR[k] = n+1
        return X   
4. Name your function, normalsequence(X). . Here is what I believe a more elegant solution.
def normalsequence(X):
      #ensure that  the ranks are in sequence!
         for i, x in enumerate(sorted(list(set(R[:])))):
             for j, y in enumerate(R):
                 if y == x:
                    R[j] = i+1  
Far more sophisticated (one-liners) for a similar problem is stack overflow: efficient method to calculate the rank vector of a Python list. This solution is also part of the Python code for transforming raw scores to ranks in my other post Python, statistics: Ranking a single array of raw scores