Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Update:

GIT repo up: https://github.com/ElessarWebb/turing.git

Curious if anyone will take a look at the progress. Still WIP. Added a parser and two sample turing machine files.

Documentation on the way (we have a tiny wiki with basic usage)

Update:

I've updated the code to incorporate (most of) the advice below. Also I've added a small parser that will parse a turing machine from file.

I'll put my repo with the code on github soon and post the URL for those who are interested or like to review my code a bit more. Thank you all for the help so far.


I'm new to C. Yesterday I got a sudden urge to go from writing Python to something, well, more UNIX core-ish.

I read some examples on http://c.learncodethehardway.org/book/ and decided I might as well put some of that stuff to use to test something else I'm working on: computability theory. Ergo: I wanted to write a basic, one tape, turing machine simulator.

It works. As far as I know. It's not brilliant, the turing machine is hard coded in this early version. But it is functional.

I really like some review on the code though. Basically all good practices and advise is welcome.

One thing I'm particulary curious about is whether I'm doing appropriate error checking and handling. e.g. are there specific cases where assert is more appropriate or where I should do more error checking?

I'm also new to Code Review so I'v read the FAQ and I think I'm asking the right question, but if I'm wrong, correct me.

turing.h

#ifndef __turing_h__
#define __turing_h__

#define MAX_TRANSITIONS 5
#define MAX_STATES 25

// forward declare structs
struct State;
struct Transition;

typedef enum {
    LEFT, RIGHT
} Direction;

typedef enum {
    FALSE, TRUE
} Bool;

struct Transition {
    char input;
    char write;
    Direction move;
    struct State *next;
};

typedef struct Transition Transition;

struct State {
    int id;
    int trans_count;
    struct Transition* transitions[ MAX_TRANSITIONS ];
    Bool accept;
    Bool reject;
};

typedef struct State State;

struct Turing {
    int state_count;
    State* states[ MAX_STATES ];
    State* current;
    int head;
};

typedef struct Turing Turing;

#endif

turing.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "turing.h"

// disable debug mode
#define NDEBUG
#include "debug.h"

// used to hand out ids
int state_id = 0;

void die( char *message )
{
    if( message )
    {
        printf( "Error: %s.\n", message );
    }

    // exit unsuccesfully
    exit(1);
}

Transition* Transition_create( char input, char write, Direction move, State *next )
{
    // allocate memory
    Transition *trans = malloc( sizeof( Transition ));
    if( ! trans ) die( "Memory error" );

    trans->input = input;
    trans->write = write;
    trans->move = move;
    trans->next = next;

    return trans;
}

void Transition_destroy( Transition* trans )
{
    free( trans );
}

State* State_create( Bool accept, Bool reject )
{
    // allocate mem
    State *state = malloc( sizeof( State ));
    if( ! state ) die( "Memory error" );

    state->id = state_id++;
    state->accept = accept;
    state->reject = reject;
    state->trans_count = 0;

    return state;
}

void State_add_transition( State *state, Transition *trans )
{
    // check if we can still add another transition
    if( state->trans_count == MAX_TRANSITIONS ) {
        char buffer[ 50 ];
        sprintf( buffer, "State %d already has the maximum amount of transitions.", state->id );

        die( buffer );
    }

    // add the transition
    state->transitions[ state->trans_count ] = trans;
    state->trans_count++;
}

void State_destroy( State *state )
{
    int i = 0;

    // loop over its transitions
    for( i = 0; i < state->trans_count; i++ ) {
        Transition *trans = state->transitions[ i ];
        if( !trans ) die( "Could not fetch transition." );

        Transition_destroy( trans );
    }

    free( state );
}

Turing* Turing_create()
{
    // allocate mem
    Turing *machine = malloc( sizeof( Turing ));

    machine->state_count = 0;
    machine->current = NULL;
    machine->head = 0;

    return machine;
}

void Turing_destroy( Turing *machine )
{
    int i = 0;

    // loop over it's states
    for( i = 0; i < machine->state_count; i++ ) {
        State *state = machine->states[ i ];
        if( !state ) die( "Could not fetch turing state" );

        State_destroy( state );
    }

    free( machine );
}

void Turing_add_state( Turing *machine, State *state )
{
    if( machine->state_count == MAX_STATES ) {
        die( "The turing machine already has the maximum amount of states" );
    }

    // add the state
    machine->states[ machine->state_count++ ] = state;
}

State* Turing_step( Turing *machine, char* tape, int tape_len )
{
    int i = 0;
    char input = tape[ machine->head ];
    State* state = machine->current;

    // look for a transition on the given input
    for( i = 0; i < state->trans_count; i++ ) {
        Transition* trans = state->transitions[ i ];
        if( !trans ) die( "Transition retrieval error" );

        // check if this is a transition in the given char input
        if( trans->input == input ) {
            debug( "Found transition for input %c", input );

            State *next = trans->next;
            if( !next ) die( "Transitions to NULL state" );

            // write if nescesary
            if( trans->write != '\0' ) {
                debug( "Writing %c", trans->write );
                tape[ machine->head ] = trans->write;
                debug( "Writing done" );
            }

            // move the head
            if( trans->move == LEFT ) {
                if( machine->head > 0 ) {
                    machine->head--;
                    debug( "Moved head left" );
                }
            } else {
                if( machine->head + 1 >= tape_len ) {
                    die( "Machine walked of tape on right side" );
                }

                machine->head++;
                debug( "Moved head right" );
            }

            // move the machine to the next state
            debug( "Setting current state" );
            machine->current = next;

            return next;
        }
    }

    char buffer[ 50 ];
    sprintf( buffer, "Turing machine blocked: state %d for input %c", state->id, input );

    die( buffer );
}

void Turing_run( Turing *machine, char *tape, int tapelen )
{
    // check if the start state is configured properly
    if( !machine->current ) die( "Turing machine has now start state" );

    while( TRUE ) {
        State* state = Turing_step( machine, tape, tapelen );

        if( state->accept ) {
            printf( "Input accepted in state: %d\n", state->id );
            break;
        } else if( state->reject ) {
            printf( "Input rejected in state: %d\n", state->id );
            break;
        } else {
            printf( "Moved to state: %d\n", state->id );    
        }
    }
}

int main( int argc, char* argv[] )
{
    Turing* machine = Turing_create();

    State* q1 = State_create( FALSE, FALSE );
    State* q2 = State_create( FALSE, FALSE );
    State* q3 = State_create( FALSE, FALSE );
    State* q4 = State_create( FALSE, FALSE );
    State* q5 = State_create( FALSE, FALSE );
    State* qaccept = State_create( TRUE, FALSE );
    State* qreject = State_create( FALSE, TRUE );

    Transition* q1_r_space = Transition_create( ' ', '\0', RIGHT, qreject );
    Transition* q1_r_x = Transition_create( 'x', '\0', RIGHT, qreject );
    Transition* q1_q2_zero = Transition_create( '0', ' ', RIGHT, q2 );
    Transition* q2_q2_x = Transition_create( 'x', '\0', RIGHT, q2 );
    Transition* q2_a_space = Transition_create( ' ', '\0', RIGHT, qaccept );
    Transition* q2_q3_zero = Transition_create( '0', 'x', RIGHT, q3 );
    Transition* q3_q3_x = Transition_create( 'x', '\0', RIGHT, q3 );
    Transition* q3_q4_zero = Transition_create( '0', '\0', RIGHT, q4 );
    Transition* q3_q5_space = Transition_create( ' ', '\0', LEFT, q5 );
    Transition* q4_q3_zero = Transition_create( '0', 'x', RIGHT, q3 );
    Transition* q4_q4_x = Transition_create( 'x', '\0', RIGHT, q4 );
    Transition* q4_r_space = Transition_create( ' ', '\0', RIGHT, qreject );
    Transition* q5_q5_zero = Transition_create( '0', '\0', LEFT, q5 ); 
    Transition* q5_q5_x = Transition_create( 'x', '\0', LEFT, q5 ); 
    Transition* q5_q2_space = Transition_create( ' ', '\0', RIGHT, q2 ); 

    State_add_transition( q1, q1_r_space );
    State_add_transition( q1, q1_r_x );
    State_add_transition( q1, q1_q2_zero );
    State_add_transition( q2, q2_q2_x );
    State_add_transition( q2, q2_a_space );
    State_add_transition( q2, q2_q3_zero );
    State_add_transition( q3, q3_q3_x );
    State_add_transition( q3, q3_q4_zero );
    State_add_transition( q3, q3_q5_space );
    State_add_transition( q4, q4_q3_zero );
    State_add_transition( q4, q4_q4_x );
    State_add_transition( q4, q4_r_space );
    State_add_transition( q5, q5_q5_zero );
    State_add_transition( q5, q5_q5_x );
    State_add_transition( q5, q5_q2_space );

    Turing_add_state( machine, q1 );
    Turing_add_state( machine, q2 );
    Turing_add_state( machine, q3 );
    Turing_add_state( machine, q4 );
    Turing_add_state( machine, q5 );
    Turing_add_state( machine, qaccept );
    Turing_add_state( machine, qreject );

    machine->current = q1;

    char* input = "0000000000000000  ";
    int len = strlen( input );
    char* tape = malloc( len * sizeof( char ));
    strcpy( tape, input );
    Turing_run( machine, tape, len );

    // clean up
    Turing_destroy( machine );
    free( tape );
}

debug.h

#ifndef __debug_h__
#define __debug_h__

#ifndef NDEBUG
#define debug(M, ... ) fprintf( stderr, "DEBUG: %s:%d: " M "\n", __FILE__,   __LINE__, ##__VA_ARGS__ )
#else
#define debug(M, ... )
#endif

#endif

For now the simulator is configured to accept on input strings from the language:

L = { 0^2^n | n > 0 }

Or: all strings of 0s whose length is a power of 2.

If you happen to have Sipser "Introduction to the Theory of Computation". It's on page 145 of the 2nd edition.

share|improve this question
    
I'll add some comments ASAP. –  A.J.Rouvoet Dec 20 '12 at 15:42
    
Identifiers with two underscores __turing_h__ are reserved for the implementation don't use them. –  Loki Astari Dec 20 '12 at 17:59
    
@LokiAstari Thank you. Good to know. –  A.J.Rouvoet Dec 20 '12 at 18:16
    
You might find this page interesting: codegolf.stackexchange.com/questions/8787/… –  luser droog Dec 21 '12 at 7:57
    
could you provide example of usage ? –  user20773 Jan 3 '13 at 13:29
show 1 more comment

2 Answers

AJ, I like it. Very nicely coded.

Here are some comments. I've omitted things already mentioned by @LokiAstari

  • forward declaration of struct Transition is unnecessary.

  • die, prefer to print errors to stderr

  • exit(1) prefer exit(EXIT_FAILURE)

  • some noisey comments ("exit unsucessfully", "allocate memory" etc)

  • State_create does not initialise transitions (probably benign)

  • sprintf is often used badly, resulting in buffer overflows. snprintf is preferred. But as you use it only before dying, no risk.

  • Turing_create does not check malloc (other uses do).

  • do you prefer type* var or type *var? I prefer the latter, but whichever you use, consistency is best.

  • don't you get a warning (control may reach end of non-void function, or similar) from Turing_step?

  • in some places you can define loop variables in the loop: for( int i = 0; ...

  • make local functions static. This is good practice but for a small project like this makes no difference.

  • your list of Transition_create calls in main would be more readable if aligned.

  • your main has some issues in the copying of input.

    • strlen returns size_t and malloc takes size_t. So best to use size_t (-Wsign-conversion)
    • sizeof(char) is 1 by definition
    • you malloced one too few bytes for the string copy.
    • you could have used strdup if you have it.
    • but note that mallocing a copy of input is not necessary. You can just declare the string as char input[] = "..." instead of char* input = "..." and it will be writable.
    • if you use char input[] you need not do strlen(input) - just sizeof input -1
  • passing the length of the input string around seems unnecessary (users of the string can check for the terminating '\0')

On error checking and use of assert, I think you have done a good job of checking. I'm not a big user of asserts (so maybe my thoughts on them are not of much use to you). I'm always uneasy using an assert - they are funny things. They say, in effect, that the tested condition is so important that it is worth exiting if it occurs during testing, but that if it occurs during normal use (NDEBUG) it can be ignored. That is illogical unless you can be sure that all possible assert failures can be detected during testing. To me that implies that asserts should be used only to test for errors that are intrinsic to the program and have no dependence upon the data or the runtime. For example checking whether malloc failed would use an if condition whereas checking for something that can only happen if an algorithm is wrongly coded is a fair use of assert. In your case, I might be tempted to use assert where you check array entries are not NULL:

    Transition *trans = state->transitions[ i ];
    assert( trans );

But I've seen asserts sprinkled around like confettii, so opinions clearly differ. Maybe other reviewers will be able to help.

share|improve this answer
    
Thank you. Some of these I already incorporated. Some of them I'll research a bit. I agree with you on the assert/if dilemma. I see alot of code (in other languages) that seem to forget that asserts are usually not for runtime checking. –  A.J.Rouvoet Dec 21 '12 at 10:26
    
About passing around the string length: I'm getting the impressions there are several opinions on the matter. You either have to make SURE all strings are \0 terminated and rely on C string tools and/or build in extra checks to prevent overflows. You clearly vote for the former. Anyone else? –  A.J.Rouvoet Dec 21 '12 at 10:28
    
AJ, strings should always be terminated with \0 but arrays in general are not. But strings are arrays - maybe that is where the confusion arrises... Note that I corrected a piece of badly wrong advice above (using sizeof on a pointer!) –  William Morris Dec 21 '12 at 12:43
    
No, there is no confusion. I'm just deliberating whether I should TRUST the strings in my program to be properly terminated. Should I? –  A.J.Rouvoet Dec 21 '12 at 13:12
    
Yes, if it is created by the compiler (from your quoted string, as in "01234..") it will definitely be terminated. If created by someone using strcpy (as in your original code) then it depends upon the code. But if the \0 is missing, using strlen to find out how long it is will also fail, as strlen won't find the \0 it needs. So in practice you have to assume it is correctly terminated. –  William Morris Dec 21 '12 at 13:26
add comment

Identifiers with two underscores are reserved for the implementation (so don't use them). Also MACROS (things defined by #define) are traditionally all uppercase (because they do not obey scope rules (because they are not part of the C language but part of the pre-processor system) we make them all uppercase to make sure that we don't accidentally clash with other identifiers).

#ifndef __turing_h__
#define __turing_h__

If you are going to forward declare these then also do the appropriate typedefs.

struct State;
struct Transition;    

// Add
typedef struct State State;
typedef struct Transition Transition;

Now you will be able to refer to then without using the prefix struct.

Don't use all caps. A macro (with no scope boundary may play havake with these identifiers).

typedef enum {
    LEFT, RIGHT
} Direction;

The system header files aready define FALSE/TRUE. Also in this situation you define TRUE as 1. This is not correct. The only thing you can say about TRUE is (!FALSE). Which is not necessarily the same as 1.

typedef enum {
    FALSE, TRUE
} Bool;

Nothing wrong with this. But if you lay out your type with the chars first then you may not get the best packing arrangement. Always order them from largest to smallest (if you care about layout (usually it is not a big thing but if you have large space requirements and can become an issue)).

struct Transition {
    char input;
    char write;
    Direction move;
    State *next;
};

So I would have layed it out like this:

typedef struct Transition {
    State     *next;      // At least as big as an int (but can be bigger).
    Direction  move;      // Enum is an int.
    char       input;     // Now chars.
    char       write;
} Transition;
share|improve this answer
    
Thank you, I will upvote when I gain that privilige. –  A.J.Rouvoet Dec 20 '12 at 18:18
    
"Don't use all caps." Actually, all caps is a very common way to declare constants, enums and all manner of global identifiers, not just macros. –  Lundin Dec 21 '12 at 7:25
    
"...you define TRUE as 1. This is not correct." Yes it is perfectly correct. Always make the code compatible with the C standard bool type, which is explicitly guaranteed to be 1 and not some magical "not 0 maybe 1". The best is of course to use the standard bool type from stdbool.h. –  Lundin Dec 21 '12 at 7:27
    
Ah stdbool.h. Another useful note! –  A.J.Rouvoet Dec 21 '12 at 10:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.