megahal.c

megahal is the conversation simulators conversing with a user in natural language. The program will

 *						subtree of the given node.  Return the position of the
 *						child node in the subtree if the symbol was found, or the
 *						position where it should be inserted to keep the subtree
 *						sorted if it wasn't.
 */
int search_node(TREE *node, int symbol, bool *found_symbol)
{
    register unsigned int position;
    int min;
    int max;
    int middle;
    int compar;

    /*
     *		Handle the special case where the subtree is empty.
     */
    if(node->branch==0) {
	position=0;
	goto notfound;
    }

    /*
     *		Perform a binary search on the subtree.
     */
    min=0;
    max=node->branch-1;
    while(TRUE) {
	middle=(min+max)/2;
	compar=symbol-node->tree[middle]->symbol;
	if(compar==0) {
	    position=middle;
	    goto found;
	} else if(compar>0) {
	    if(max==middle) {
		position=middle+1;
		goto notfound;
	    }
	    min=middle+1;
	} else {
	    if(min==middle) {
		position=middle;
		goto notfound;
	    }
	    max=middle-1;
	}
    }

found:
    *found_symbol=TRUE;
    return(position);

notfound:
    *found_symbol=FALSE;
    return(position);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Initialize_Context
 *
 *		Purpose:		Set the context of the model to a default value.
 */
void initialize_context(MODEL *model)
{
    register unsigned int i;

    for(i=0; i<=model->order; ++i) model->context[i]=NULL;
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Learn
 *
 *		Purpose:		Learn from the user's input.
 */
void learn(MODEL *model, DICTIONARY *words)
{
    register unsigned int i;
    register int j;
    BYTE2 symbol;

    /*
     *		We only learn from inputs which are long enough
     */
    if(words->size<=(model->order)) return;

    /*
     *		Train the model in the forwards direction.  Start by initializing
     *		the context of the model.
     */
    initialize_context(model);
    model->context[0]=model->forward;
    for(i=0; i<words->size; ++i) {
	/*
	 *		Add the symbol to the model's dictionary if necessary, and then
	 *		update the forward model accordingly.
	 */
	symbol=add_word(model->dictionary, words->entry[i]);
	update_model(model, symbol);
    }
    /*
     *		Add the sentence-terminating symbol.
     */
    update_model(model, 1);

    /*
     *		Train the model in the backwards direction.  Start by initializing
     *		the context of the model.
     */
    initialize_context(model);
    model->context[0]=model->backward;
    for(j=words->size-1; j>=0; --j) {
	/*
	 *		Find the symbol in the model's dictionary, and then update
	 *		the backward model accordingly.
	 */
	symbol=find_word(model->dictionary, words->entry[j]);
	update_model(model, symbol);
    }
    /*
     *		Add the sentence-terminating symbol.
     */
    update_model(model, 1);

    return;
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Train
 *
 *		Purpose:	 	Infer a MegaHAL brain from the contents of a text file.
 */
void train(MODEL *model, char *filename)
{
    FILE *file;
    char buffer[1024];
    DICTIONARY *words=NULL;
    int length;

    if(filename==NULL) return;

    file=fopen(filename, "r");
    if(file==NULL) {
	printf("Unable to find the personality %s\n", filename);
	return;
    }

    fseek(file, 0, 2);
    length=ftell(file);
    rewind(file);

    words=new_dictionary();

    progress("Training from file", 0, 1);
    while(!feof(file)) {

	if(fgets(buffer, 1024, file)==NULL) break;
	if(buffer[0]=='#') continue;

	buffer[strlen(buffer)-1]='\0';

	upper(buffer);
	make_words(buffer, words);
	learn(model, words);

	progress(NULL, ftell(file), length);

    }
    progress(NULL, 1, 1);

    free_dictionary(words);
    fclose(file);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Show_Dictionary
 *
 *		Purpose:		Display the dictionary for training purposes.
 */
void show_dictionary(DICTIONARY *dictionary)
{
    register unsigned int i;
    register unsigned int j;
    FILE *file;

    file=fopen("megahal.dic", "w");
    if(file==NULL) {
	warn("show_dictionary", "Unable to open file");
	return;
    }

    for(i=0; i<dictionary->size; ++i) {
	for(j=0; j<dictionary->entry[i].length; ++j)
	    fprintf(file, "%c", dictionary->entry[i].word[j]);
	fprintf(file, "\n");
    }

    fclose(file);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Save_Model
 *
 *		Purpose:		Save the current state to a MegaHAL brain file.
 */
void save_model(char *modelname, MODEL *model)
{
    FILE *file;
    static char *filename=NULL;

    if(filename==NULL) filename=(char *)malloc(sizeof(char)*1);

    /*
     *    Allocate memory for the filename
     */
    filename=(char *)realloc(filename,
			     sizeof(char)*(strlen(directory)+strlen(SEP)+12));
    if(filename==NULL) error("save_model","Unable to allocate filename");

    show_dictionary(model->dictionary);
    if(filename==NULL) return;

    sprintf(filename, "%s%smegahal.brn", directory, SEP);
    file=fopen(filename, "wb");
    if(file==NULL) {
	warn("save_model", "Unable to open file `%s'", filename);
	return;
    }

    fwrite(COOKIE, sizeof(char), strlen(COOKIE), file);
    fwrite(&(model->order), sizeof(BYTE1), 1, file);
    save_tree(file, model->forward);
    save_tree(file, model->backward);
    save_dictionary(file, model->dictionary);

    fclose(file);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Save_Tree
 *
 *		Purpose:		Save a tree structure to the specified file.
 */
void save_tree(FILE *file, TREE *node)
{
    static int level=0;
    register unsigned int i;

    fwrite(&(node->symbol), sizeof(BYTE2), 1, file);
    fwrite(&(node->usage), sizeof(BYTE4), 1, file);
    fwrite(&(node->count), sizeof(BYTE2), 1, file);
    fwrite(&(node->branch), sizeof(BYTE2), 1, file);

    if(level==0) progress("Saving tree", 0, 1);
    for(i=0; i<node->branch; ++i) {
	++level;
	save_tree(file, node->tree[i]);
	--level;
	if(level==0) progress(NULL, i, node->branch);
    }
    if(level==0) progress(NULL, 1, 1);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Load_Tree
 *
 *		Purpose:		Load a tree structure from the specified file.
 */
void load_tree(FILE *file, TREE *node)
{
    static int level=0;
    register unsigned int i;

    fread(&(node->symbol), sizeof(BYTE2), 1, file);
    fread(&(node->usage), sizeof(BYTE4), 1, file);
    fread(&(node->count), sizeof(BYTE2), 1, file);
    fread(&(node->branch), sizeof(BYTE2), 1, file);

    if(node->branch==0) return;

    node->tree=(TREE **)malloc(sizeof(TREE *)*(node->branch));
    if(node->tree==NULL) {
	error("load_tree", "Unable to allocate subtree");
	return;
    }

    if(level==0) progress("Loading tree", 0, 1);
    for(i=0; i<node->branch; ++i) {
	node->tree[i]=new_node();
	++level;
	load_tree(file, node->tree[i]);
	--level;
	if(level==0) progress(NULL, i, node->branch);
    }
    if(level==0) progress(NULL, 1, 1);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Load_Model
 *
 *		Purpose:		Load a model into memory.
 */
bool load_model(char *filename, MODEL *model)
{
    FILE *file;
    char cookie[16];


    if(filename==NULL) return(FALSE);

    file=fopen(filename, "rb");

    if(file==NULL) {
	warn("load_model", "Unable to open file `%s'", filename);
	return(FALSE);
    }


    fread(cookie, sizeof(char), strlen(COOKIE), file);
    if(strncmp(cookie, COOKIE, strlen(COOKIE))!=0) {
	warn("load_model", "File `%s' is not a MegaHAL brain", filename);
	goto fail;
    }

    fread(&(model->order), sizeof(BYTE1), 1, file);
    load_tree(file, model->forward);
    load_tree(file, model->backward);
    load_dictionary(file, model->dictionary);

    return(TRUE);
fail:
    fclose(file);

    return(FALSE);
}

/*---------------------------------------------------------------------------*/

/*
 *    Function:   Make_Words
 *
 *    Purpose:    Break a string into an array of words.
 */
void make_words(char *input, DICTIONARY *words)
{
    int offset=0;

    /*
     *		Clear the entries in the dictionary
     */
    free_dictionary(words);

    /*
     *		If the string is empty then do nothing, for it contains no words.
     */
    if(strlen(input)==0) return;

    /*
     *		Loop forever.
     */
    while(1) {

	/*
	 *		If the current character is of the same type as the previous
	 *		character, then include it in the word.  Otherwise, terminate
	 *		the current word.
	 */
	if(boundary(input, offset)) {
	    /*
	     *		Add the word to the dictionary
	     */
	    if(words->entry==NULL)
		words->entry=(STRING *)malloc((words->size+1)*sizeof(STRING));
	    else
		words->entry=(STRING *)realloc(words->entry, (words->size+1)*sizeof(STRING));

	    if(words->entry==NULL) {
		error("make_words", "Unable to reallocate dictionary");
		return;
	    }

	    words->entry[words->size].length=offset;
	    words->entry[words->size].word=input;
	    words->size+=1;

	    if(offset==(int)strlen(input)) break;
	    input+=offset;
	    offset=0;
	} else {
	    ++offset;
	}
    }

    /*
     *		If the last word isn't punctuation, then replace it with a
     *		full-stop character.
     */
    if(isalnum(words->entry[words->size-1].word[0])) {
	if(words->entry==NULL)
	    words->entry=(STRING *)malloc((words->size+1)*sizeof(STRING));
	else
	    words->entry=(STRING *)realloc(words->entry, (words->size+1)*sizeof(STRING));
	if(words->entry==NULL) {
	    error("make_words", "Unable to reallocate dictionary");
	    return;
	}

	words->entry[words->size].length=1;
	words->entry[words->size].word=".";
	++words->size;
    }
    else if(strchr("!.?", words->entry[words->size-1].word[words->entry[words->size-1].length-1])==NULL) {
	words->entry[words->size-1].length=1;
	words->entry[words->size-1].word=".";
    }

    return;
}

/*---------------------------------------------------------------------------*/
/*
 *		Function:	Boundary
 *
 *		Purpose:		Return whether or not a word boundary exists in a string
 *						at the specified location.
 */
bool boundary(char *string, int position)
{
    if(position==0)
	return(FALSE);

    if(position==(int)strlen(string))
	return(TRUE);

    if(
	(string[position]=='\'')&&
	(isalpha(string[position-1])!=0)&&
	(isalpha(string[position+1])!=0)
	)
	return(FALSE);

    if(
	(position>1)&&
	(string[position-1]=='\'')&&
	(isalpha(string[position-2])!=0)&&
	(isalpha(string[position])!=0)
	)
	return(FALSE);

    if(
	(isalpha(string[position])!=0)&&
	(isalpha(string[position-1])==0)
	)
	return(TRUE);

    if(
	(isalpha(string[position])==0)&&
	(isalpha(string[position-1])!=0)
	)
	return(TRUE);

    if(isdigit(string[position])!=isdigit(string[position-1]))
	return(TRUE);

    return(FALSE);
}

/*---------------------------------------------------------------------------*/
/*
 *		Function:	Make_Greeting
 *
 *		Purpose:		Put some special words into the dictionary so that the
 *						program will respond as if to a new judge.
 */
void make_greeting(DICTIONARY *words)
{
    register unsigned int i;

    for(i=0; i<words->size; ++i) free(words->entry[i].word);
    free_dictionary(words);
    if(grt->size>0) (void)add_word(words, grt->entry[rnd(grt->size)]);
}

/*---------------------------------------------------------------------------*/
/*
 *    Function:   Generate_Reply
 *
 *    Purpose:    Take a string of user input and return a string of output
 *                which may vaguely be construed as containing a reply to
 *                whatever is in the input string.
 */
char *generate_reply(MODEL *model, DICTIONARY *words)
{
    static DICTIONARY *dummy=NULL;
    DICTIONARY *replywords;
    DICTIONARY *keywords;
    float surprise;
    float max_surprise;
    char *output;
    static char *output_none=NULL;
    int count;
    int basetime;
    int timeout = TIMEOUT;

    /*
     *		Create an array of keywords from the words in the user's input
     */
    keywords=make_keywords(model, words);

    /*
     *		Make sure some sort of reply exists
     */
    if(output_none==NULL) {
	output_none=malloc(40);
	if(output_none!=NULL)
	    strcpy(output_none, "I don't know enough to answer you yet!");
    }
    output=output_none;
    if(dummy == NULL) dummy = new_dictionary();
    replywords = reply(model, dummy);
    if(dissimilar(words, replywords) == TRUE) output = make_output(replywords);

    /*
     *		Loop for the specified waiting period, generating and evaluating
     *		replies
     */
    max_surprise=(float)-1.0;
    count=0;
    basetime=time(NULL);
/*     progress("Generating reply", 0, 1);  */
    do {
	replywords=reply(model, keywords);
	surprise=evaluate_reply(model, keywords, replywords);
	++count;
	if((surprise>max_surprise)&&(dissimilar(words, replywords)==TRUE)) {
	    max_surprise=surprise;
	    output=make_output(replywords);
	}
/*  	progress(NULL, (time(NULL)-basetime),timeout); */
    } while((time(NULL)-basetime)<timeout);
    progress(NULL, 1, 1);