A way to do functions in brainfuck.

brainfuck_function_tutorial.b

[How to do functions in brainfuck.

Okay. We'll translate the following program into brainfuck, with no thought of efficiency:

char fib (char a){
	switch(a):
		case 0: return 0
		case 1: return 1
		default: return fib(a-2)+fib(a-1)
}

void main(void){
	output fib(10);
}

The first thing is to make this more cleanly sequential.

char fib(char a){
	switch (a):
		case 0: return 0
		case 1: return 1
		default:
			call fib(a-2)
			get return value
			char b = return value //b is a local variable
			call fib(a-1)
			get return value
			b = b+return value
			return b
}

void main(void){
	call fib(10)
	get return value
	output return value
}

The next thing is to break functions up, whenever they need to do things AFTER calling another function. The things to do after are put in a different function. So all calls are tail calls, but on the other hand we can (incongruous as it sounds) queue up multiple future functions on the stack.

(At this stage, I'm also incidentally removing "dead" variables from these new functions. For instance, fib3 doesn't need the value of a, because that part of the original fib function doesn't use a. So fib2 can discard a after using it. Conversely, fib3 DOES need the value of b, so fib2 passes fib3 that value as a parameter.)

char fib1(char a){
	switch (a):
		case 0: return 0
		case 1: return 1
		default:
			execute fib1(a-2) followed by fib2(a)
}

char fib2(char a){
	get return value
	char b = return value //local variable
	execute fib1(a-1) followed by fib3(b)
}

char fib3(char b){
	get return value
	b = b+return value
	return b
}

void main1(void){
	execute fib(10) followed by main2()
}

void main2(void){
	get return value
	output return value
}

Now we arbitrarily assign nonzero numeric identifiers to our functions, and we'll note what their respective frames look like on the stack, given what variables they use.

main1: 1 (1)
main2: 2 (ret 2)
fib1: 3 (a 3)
fib2: 4 (a b ret 4)
fib3: 5 (b ret 5)

When calling a function, we put its parameters on the stack, and leave space for any non-parameter local variables, and empty space for any values that will need to be returned to that function, followed by the function's identifier. The list above shows what space gets allocated for each function when it's called (i.e., queued). We're putting the space to receive return values immediately left of the function identifier, in the three functions that accept a return value.

Various aspects of this can be changed; I'll note some of that at the end.

We will use case statements of this form to select functions:
>+<[
	-[
		-[
			-[
				-[
					[-]>-default<
				]>[-4]<
			]>[-3]<
		]>[-2]<
	]>[-1]<
]>[-0]<

Note that this means when the body of a function starts executing, its identifier will already have been consumed by the case statement apparatus, and the pointer will be at a 1 flag one space right of where the identifier was, i.e. two spaces right of the memory allocated for that function. Each function body has the responsibility to zero that flag, and to leave the pointer two cells right of the rightmost identifier on the stack when it terminates, in order to skip all subsequent cases.

Note also that the functions can use the empty space to the right freely for their calculations; everything right of the stack top is zero.

So! Memory layout is 0 stack stack... stack_top 0 0 ...

Now here's the program.]

>+[ call main1 and execute while any functions are left on the stack
	>+< set flag for case statement
	-[
		-[
			-[
				-[
					->fib3
						-<<[<+>-]<[<<+>>-]>
					<
				]>[fib2
					-<<[<+>-]<<-[>>>+<<<-]>[<+>-]>+++++>>+++>>
				]<
			]>[fib1
				-<<>+<[inner case statement
					-[->default
						-<++[>+>>>+<<<<-]>[<+>-]>>++++>-->+++>
					]>[1
						-<<<+>>>
					]<
				]>[0
					-<<<>>>
				]
			]<
		]>[main2
			-<<.[-]++++++++++.[-]>
		]<
	]>[main1
		-<>++>++++++++++>+++>>
	]<
	< go to next function identifier
]

[This should output fib(10), which is 55, i.e. '7'.

If you want to use a debugger to watch this some, the end of the first line is a fine place for a breakpoint.

As I've written this, when a function gets broken into a series of functions, any local variables that need to be saved need to get passed to the next function as parameters. It would also work fine to define fib1, fib2, and fib3 as all using an identical stack frame, with all variables used by any of the three (a b ret identifier), in which case a and b can just be left in place, and only the identifier changed from fib1 to fib2 to fib3. Which is better will depend on things like how much data the functions keep around.
]