journal.txt

--- 2010-Oct-04 Monday 10:17pm ---

First thing I did:

$ cd src
$ mkdir brainfuck
$ cd brainfuck

Then I created main.c:

int main() { }

and compiled it:

$ cc -o brainfuck main.o

and ran it:

$ ./brainfuck
$

and then I made a Makefile that did what I had just done, because I knew
I would do it about a thousand more times before this project was done:

brainfuck: main.c
	cc -o brainfuck main.c
	./brainfuck

and of course I type 'make' and press <enter> instinctually:

$ make
cc -o brainfuck main.c
./brainfuck
make: *** [brainfuck] Error 200

---
I accidentally made my first test.  Even though main() returns an int,
I left out the actual return value, so I guess it was just returning whatever
was left over from some random startup code.  In fact I think it returned 
200 cuz I think that's how make works but I'm not 100% sure, and anyway,
I get to fix my first issue!
---

return 0;

$ make
cc -o brainfuck main.c
./brainfuck
---

So then I get uncomfortable with the combined pace of coding and writing,
and a little bored by 'what i'm trying to do with this', so I let that
chest feeling settle, and I search for a test brainfuck program which
I paste into hello.bf:

--- hello.bf
(the usual '---' won't work to delineate brainfuck programs)
=============================================================================
+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'
=============================================================================

I type 'make' and almost hit enter before I realize that just creating a file
on the disk doesn't do anything.  I have to give it to the program I
just made:

$ ./brainfuck hello.bf
$

but of course that doesn't do anything (yet).  I've typed this line
manually probably thousands of times:

int main(int argc, const char *argv[])

but I can't remember the arguments to fread, so I reach for another window and

$ man fread
No manual entry for fread

$ sudo apt-get install manpages-dev
90% [1 manpages-dev 1391217/1,546kB 90%]

$ man fread

---
FREAD(3)                   Linux Programmer's Manual                  FREAD(3)

NAME
       fread, fwrite - binary stream input/output

SYNOPSIS
       #include <stdio.h>

       size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream);

       size_t fwrite(const void *ptr, size_t size, size_t nmemb,
                     FILE *stream);

DESCRIPTION
       The  function  fread()  reads  nmemb  elements of data, each size bytes
       long, from the stream pointed to by stream, storing them at  the  loca‐
       tion given by ptr.

       The  function  fwrite()  writes nmemb elements of data, each size bytes
       long, to the stream pointed to by stream, obtaining them from the loca‐
       tion given by ptr.

       For non-locking counterparts, see unlocked_stdio(3).

RETURN VALUE
       fread()  and  fwrite()  return the number of items successfully read or
       written (i.e., not the number of characters).  If an error  occurs,  or
       the  end-of-file is reached, the return value is a short item count (or
       zero).

       fread() does not distinguish between end-of-file and error, and callers
       must use feof(3) and ferror(3) to determine which occurred.

CONFORMING TO
       C89, POSIX.1-2001.

SEE ALSO
       read(2), write(2), feof(3), ferror(3), unlocked_stdio(3)

COLOPHON
       This  page  is  part of release 3.21 of the Linux man-pages project.  A
       description of the project, and information about reporting  bugs,  can
       be found at http://www.kernel.org/doc/man-pages/.

GNU                               1996-05-17                          FREAD(3)
---

14 years old and 47 lines.  god bless.

fread(fp, 

oh right, this is probably more complicated then it needs to be.  Isn't there
some other f-something that reads one character at a time?  This is
basic C, I should know this, but it's not in the SEE ALSO.  Hmm..

$ man fopen (nothing rings a bell in SEE ALSO, although I note the date is
much newer: 2009-02-23)
$ man fgetch
No manual entry for fgetch
$ man getch
No manual entry for getch
$ man fgets
---
GETS(3)                    Linux Programmer's Manual                   GETS(3)

NAME
       fgetc,  fgets,  getc,  getchar,  gets, ungetc - input of characters and
       strings

SYNOPSIS
       #include <stdio.h>

       int fgetc(FILE *stream);

       char *fgets(char *s, int size, FILE *stream);

       int getc(FILE *stream);

       int getchar(void);

       char *gets(char *s);

       int ungetc(int c, FILE *stream);

DESCRIPTION
       fgetc() reads the next character from  stream  and  returns  it  as  an
       unsigned char cast to an int, or EOF on end of file or error.

       getc()  is equivalent to fgetc() except that it may be implemented as a
       macro which evaluates stream more than once.

       getchar() is equivalent to getc(stdin).

       gets() reads a line from stdin into the buffer pointed to  by  s  until
       either  a  terminating newline or EOF, which it replaces with '\0'.  No
       check for buffer overrun is performed (see BUGS below).

       fgets() reads in at most one less than size characters from stream  and
       stores  them  into  the buffer pointed to by s.  Reading stops after an
       EOF or a newline.  If a newline is read, it is stored into the  buffer.
       A '\0' is stored after the last character in the buffer.

       ungetc()  pushes  c  back to stream, cast to unsigned char, where it is
       available for subsequent read operations.  Pushed-back characters  will
       be returned in reverse order; only one pushback is guaranteed.

       Calls  to the functions described here can be mixed with each other and
       with calls to other input functions from the stdio library for the same
       input stream.

       For non-locking counterparts, see unlocked_stdio(3).

RETURN VALUE
       fgetc(),  getc() and getchar() return the character read as an unsigned
       char cast to an int or EOF on end of file or error.

       gets() and fgets() return s on success, and NULL on error or  when  end
       of file occurs while no characters have been read.

CONFORMING TO
       C89,  C99,  POSIX.1-2001.  LSB deprecates gets().  POSIX.1-2008 removes
       the specification of gets().

BUGS
       Never use gets().  Because it is impossible to tell without knowing the
       data  in  advance  how  many  characters  gets() will read, and because
       gets() will continue to store characters past the end of the buffer, it
       is  extremely  dangerous  to  use.   It has been used to break computer
       security.  Use fgets() instead.

       It is not advisable to mix calls to  input  functions  from  the  stdio
       library with low-level calls to read(2) for the file descriptor associ‐
       ated with the input stream; the results  will  be  undefined  and  very
       probably not what you want.

SEE ALSO
       read(2), write(2), ferror(3), fgetwc(3), fgetws(3), fopen(3), fread(3),
       fseek(3),  getline(3),  getwchar(3),  puts(3),  scanf(3),   ungetwc(3),
       unlocked_stdio(3)

COLOPHON
       This  page  is  part of release 3.21 of the Linux man-pages project.  A
       description of the project, and information about reporting  bugs,  can
       be found at http://www.kernel.org/doc/man-pages/.

GNU                               2008-08-06                           GETS(3)

fgetc is exactly what I want:

int
main(int argc, const char *argv[])
{
    FILE *fp = fopen(argv[1], "r");

    while (! feof(fp)) 
    {
        char ch = fgetc(fp);

        printf("%c", ch);
    }

    fclose(fp);

    return 0;
}

cc -o brainfuck main.c
main.c: In function ‘main’:
main.c:4: error: ‘FILE’ undeclared (first use in this function)
main.c:4: error: (Each undeclared identifier is reported only once
main.c:4: error: for each function it appears in.)
main.c:4: error: ‘fp’ undeclared (first use in this function)
main.c:10: warning: incompatible implicit declaration of built-in function ‘printf’
make: *** [brainfuck] Error 1
---
I'm a little surprised that I get so many errors for code that I know 
is completely legit.

#include <stdio.h>

$ make
cc -o brainfuck main.c
./brainfuck hello.bf

(I had changed the Makefile earlier, instead of typing ./brainfuck
as I wrote.  I wonder if I should have just been honest in the first
place).

cc -o brainfuck main.c
./brainfuck hello.bf
+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'
�$

Okay, let's get this show on the road.  From what I read in the article, 

    // right, we need a data pointer I think

    char array[30000] = { 0 };
    char *ptr = &array[0];  // or simply 'array'

    while (! feof(fp)) 
    {
        char ch = fgetc(fp);

        // in every moment, what is the right thing to do?

        printf("%c", ch);

        switch (ch)
        {
        case '>':
            ++ptr;
            break;
        case '<':
            --ptr;
            break;
        case '+':
            ++*ptr;
            break;
        case '-':
            --*ptr;
            break;
        case '.':
            printf("%c", *ptr);
            break;
        case ',':
            *ptr = getc();
            break;
        case '[':
            if (*ptr == 0)
                ... oh, right.
            break;
        case ']':
            break;
        };
    }

This is kind of neat actually.  not actually even necessarily obfuscated.

I need to store the program and make an instruction pointer, and how am I
going to "match" the [] like parentheses?  i think first of a stack, but that
would be easiest with C++ and i have a High Concept of keeping this as simple
as possible.  So...


#include <stdio.h>

int
main(int argc, const char *argv[])
{
    FILE *fp = fopen(argv[1], "r");

    // right, we need a data pointer I think

    char array[30000] = { 0 };
    int data_ptr = 0;
    char program[30000] = { 0 };
    int instr_ptr = 0;

    // first read in the entire program
    while (! feof(fp)) 
    {
        program[instr_ptr++] = fgetc(fp);
    }

    instr_ptr = 0;

    while (true)
    {
        // in every moment, what is the right thing to do?

//        printf("%c", ch);

        switch (ch)
        {
        case '>':
            ++data_ptr;
            break;
        case '<':
            --data_ptr;
            break;
        case '+':
            ++*data_ptr;
            break;
        case '-':
            --*data_ptr;
            break;
        case '.':
            printf("%c", *data_ptr);
            break;
        case ',':
            *data_ptr = getc();
            break;
        case '[':
        // all problems are the same problem, at their core
            if (*instr_ptr == 0)
            {
                // if the byte at the data pointer is zero, then instead of
                // moving the instruction pointer forward to the next command,
                // jump it forward to the command after the matching ]
                // command*.
            }
            break;
        case ']':
            if (*instr_ptr != 0)
            {
                // if the byte at the data pointer is nonzero, then instead of
                // moving the instruction pointer forward to the next command,
                // jump it back to the command after the matching [ command*.
            }
            break;
        };
    }

    fclose(fp);

    return 0;
}

$ cc -o brainfuck main.c
main.c: In function ‘main’:
main.c:23: error: ‘true’ undeclared (first use in this function)
main.c:23: error: (Each undeclared identifier is reported only once
main.c:23: error: for each function it appears in.)
main.c:29: error: ‘ch’ undeclared (first use in this function)
main.c:38: error: invalid type argument of ‘unary *’ (have ‘int’)
main.c:41: error: invalid type argument of ‘unary *’ (have ‘int’)
main.c:44: error: invalid type argument of ‘unary *’ (have ‘int’)
main.c:47: error: invalid type argument of ‘unary *’ (have ‘int’)
main.c:47: error: too few arguments to function ‘_IO_getc’
main.c:51: error: invalid type argument of ‘unary *’ (have ‘int’)
main.c:60: error: invalid type argument of ‘unary *’ (have ‘int’)
make: *** [brainfuck] Error 1

okay now that's motivating.

I'm beginning to doubt my choice of variable names.  maybe ptr and ip would
have been better.  maybe instead of int indexes into their respective arrays,
they should be pointers like in the wikipedia article, so i can just cutnpaste
code.  oh well, let's just get it compiling again:

$ make
cc -o brainfuck main.c
main.c: In function ‘main’:
main.c:37: error: ‘data’ undeclared (first use in this function)
main.c:37: error: (Each undeclared identifier is reported only once
main.c:37: error: for each function it appears in.)
main.c:46: error: too few arguments to function ‘_IO_getc’
make: *** [brainfuck] Error 1
$ make
cc -o brainfuck main.c
main.c: In function ‘main’:
main.c:46: error: too few arguments to function ‘_IO_getc’
make: *** [brainfuck] Error 1

$ man getc
    ...
    getchar()
    ...

$ make
cc -o brainfuck main.c
./brainfuck hello.bf

and...it hangs without saying anything.  Typical.

Right, I didn't implement those two instructions.  hm.  how to do...

I break down and

#define IP &program[instr_ptr]
#define PTR &array[data_ptr]

:%s/program[instr_ptr]/IP
:%s/program\[instr_ptr\]/IP

                int n = 0;
                while (n != 0 || IP != ']')
                {
                    if (IP == '[')
                        n++;
                    else if (IP == ']')
                        n--;
                }

I realize that using a stack for the second case is an efficiency improvement
and completely unnecessary and overcomplicated.  just do inverse of the upper
loop.

I break down after writing half the ] and cutnpaste the code from the [.
instr_ptr++ becomes instr_ptr-- in ] though, and ']'.  and n++/n-- reversed.

$ make
cc -o brainfuck main.c
main.c: In function ‘main’:
main.c:31: error: ‘IP’ undeclared (first use in this function)
main.c:31: error: (Each undeclared identifier is reported only once
main.c:31: error: for each function it appears in.)
make: *** [brainfuck] Error 1

:%s/program\[instr_ptr\]/IP

and anyway, I realize that a pointer is easier.

    char data[30000] = { 0 };
    char *ptr = data;
    char program[30000] = { 0 };
    char *ip = program;

:%s/instr_ptr/ip/g
...
            if (*ip == 0)
            {
                // if the byte at the data pointer is zero, then instead of
                // moving the instruction pointer forward to the next command,
                // jump it forward to the command after the matching ]
                // command*.
                int n = 0;
                do {
                    ip++;
                    if (*ip == '[')
                        n++;
                    else if (*ip == ']')
                        n--;
                }
                while (n != 0 || *ip != ']');
                ip++;
            }
            break;
        case ']':
            if (*ip != 0)
            {
                // if the byte at the data pointer is nonzero, then instead of
                // moving the instruction pointer forward to the next command,
                // jump it back to the command after the matching [ command*.
                int n = 0;
                do {
                    ip--;
                    if (*ip == '[')
                        n--;
                    else if (*ip == ']')
                        n++;
                }
                while (n != 0 || *ip != ']');
                ip++;
            }
            break;

--- 2010-Oct-05 Tuesday 12:05am ---

$ make
cc -o brainfuck main.c
main.c: In function ‘main’:
main.c:31: error: ‘IP’ undeclared (first use in this function)
main.c:31: error: (Each undeclared identifier is reported only once
main.c:31: error: for each function it appears in.)
make: *** [brainfuck] Error 1

$ make
cc -o brainfuck main.c
main.c:3:9: error: macro names must be identifiers
main.c:4:9: error: macro names must be identifiers
main.c: In function ‘main’:
main.c:21: error: array subscript is not an integer
make: *** [brainfuck] Error 1

$ make
cc -o brainfuck main.c
main.c: In function ‘main’:
main.c:18: error: array subscript is not an integer
make: *** [brainfuck] Error 1

$ make
cc -o brainfuck main.c
./brainfuck hello.bf
make: *** [brainfuck] Segmentation fault
make: *** Deleting file `brainfuck'
---

Pretty much the standard second outcome when you do anything non-trivial.
(first was hang with no output).

$ gdb brainfuck
GNU gdb (GDB) 7.0-ubuntu
Copyright (C) 2009 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
brainfuck: No such file or directory.
(gdb)

test: brainfuck
	./brainfuck hello.bf

brainfuck: main.c
	cc -o brainfuck main.c

$ make
cc -o brainfuck main.c
./brainfuck hello.bf
make: *** [test] Segmentation fault


rm brainfuck
make a couple more times for good measure.


uncomment the printf

all pluses.

ip++

cc -o brainfuck main.c
main.c: In function ‘main’:
main.c:16: warning: incompatible implicit declaration of built-in function ‘exit’
./brainfuck hello.bf
+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
make: *** [test] Segmentation fault
$ gdb brianfu
$ gdb brianfuck
$ gdb brainfuck
Bad ...
$ ^C


$ ulimit -c unlimited
$ make
make: *** [test] Segmentation fault (core dumped)

whee!
$ gdb brainfuck core
Core was generated by `./brainfuck hello.bf'.
Program terminated with signal 11, Segmentation fault.
#0  0x0000000000400981 in main ()
(gdb) bt
#0  0x0000000000400981 in main ()

Everything that can go wrong, does.  nothing goes smoothly.

test: brainfuck
	./brainfuck hello.bf

brainfuck: main.c
	cc -ggdb -o brainfuck main.c

clean:
	rm brainfuck

$ make clean

and of course the actions in makefiles have to be tabbed with a proper ^I tab instead of a number of spaces.  in 2010.

$ make clean
rm brainfuck
$ make
cc -ggdb -o brainfuck main.c
main.c: In function ‘main’:
main.c:16: warning: incompatible implicit declaration of built-in function ‘exit’
./brainfuck hello.bf
+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
make: *** [test] Segmentation fault (core dumped)

$ gdb brainfuck

after a couple of rounds, I decide I have to sleep on it.  2.5 hours so far.

--- 2010-Oct-05 Tuesday 10:41pm ---

Finally branched out beyond http://en.wikipedia.org/wiki/Brainfuck:

-> http://www.iwriteiam.nl/Ha_bf_inter.html (BF interpreter written in BF)
   -> http://www.hevanet.com/cristofd/dbfi.b
      -> http://www.hevanet.com/cristofd/brainfuck/
         -> http://www.hevanet.com/cristofd/brainfuck/epistle.html
            -> http://www.iwriteiam.nl/Ha_BF.html

The # command (dump state) will be useful for debugging my interpreter;
The ! command (separate code from input) helps with automated tests.

---

Worked through exactly what would happen at the first ] block and changed
n != 1 to n != 0.  added begin/loop printfs.  added CHECK whereever ip was
changed:

#define CHECK assert(ip >= program && ip < &program[ncode])

... and now i'm so in the flow of coding that i decided to use svn to track
my progress at a minute level.

stupid bug.  checking if *ip is 0 rather than *ptr.  haha.  teach me to
code while tired :D

but then it works, nearly instantly printing out Hello world (I wasn't sure
at first if maybe it just took forever to run a program, but it really
didn't seem right).  commit.

now what?  clean up code!  it's fun.  and i have a test so i don't break the
program.  or maybe i should get more test programs?  in a bit. first i'm going
to turn debugging back on and see what things are useful and interesting to
look at to determine program state, and remove the rest.  maybe add an option
or two to the program.  this is now the fun part, a safe playground with
revision control and instant feedback.

--- 2013-May-04 Saturday  1:47am ---

Just rediscovered this project last night; I had gotten it to a good point and
checked it into github with an extension for subroutines: '{a' defines the
opcode 'a' to call the routine starting at the opcode following the 'a'.  When
the subsequent '}' is executed, it 'returns'.  Any unused opcode is valid.

It's about 10 lines of code.  Simple but powerful.  Cleaned the tests
up a bit, thinking about how to make a bf compressor that uses it.