modules/lang/brainfzck.zzm

=encoding utf8

=head1 NAME

lang/brainfzck - Parse and run Brainf*ck programs.

=head1 SYNOPSIS

  from lang/brainfzck import brainfzck, compile_brainfzck;

  say( brainfzck("++++++++[>++++++++<-]>+.") );  # A

  let program := compile_brainfzck(",+.");
  say( program.run( { input: "A" } ) );          # B

=head1 DESCRIPTION

This pure-Zuzu module implements Brainf*ck. Non-command characters are
ignored. Bracket pairing is validated before execution, and cells wrap as
unsigned bytes by default.

=head1 EXPORTS

=head2 Functions

=over

=item C<brainfzck(String source, Dict options?)>

Compiles and runs C<source>. Returns captured output unless an
C<output_callback> is supplied.

=item C<compile_brainfzck(String source, String source_name?)>

Returns a C<BrainfzckProgram> object.

=back

=head2 Classes

=over

=item C<BrainfzckProgram>

Compiled Brainf*ck program. Use C<run(options?)> to execute it.

=item C<BrainfzckError>

Base exception type.

=item C<BrainfzckSyntaxError>

Thrown for unmatched brackets.

=item C<BrainfzckRuntimeError>

Thrown for pointer and option errors.

=back

=head1 COPYRIGHT AND LICENCE

B<< lang/brainfzck >> is copyright Toby Inkster.

It is free software; you may redistribute it and/or modify it under the
terms of either the Artistic License 1.0 or the GNU General Public License
version 2.

=cut

from std/string import chr, join, ord, substr;

function _options;
function _run_program;

class BrainfzckError extends Exception {
	let String source_name with get := "<string>";
	let Number source_index with get := -1;

	method to_String () {
		if ( source_index >= 0 ) {
			return self{message} _ " at " _ source_name _ ":" _
				( source_index + 1 );
		}
		return self{message};
	}
}

class BrainfzckSyntaxError extends BrainfzckError;
class BrainfzckRuntimeError extends BrainfzckError;

class BrainfzckProgram {
	let String source with get := "";
	let String source_name with get := "<string>";
	let Array commands with get := [];
	let Array source_indexes with get := [];
	let Dict jumps with get := {};

	method __build__ () {
		commands := [] if commands == null;
		source_indexes := [] if source_indexes == null;
		jumps := {} if jumps == null;
	}

	method run ( options? ) {
		return _run_program( self, _options(options) );
	}
}

function _option ( options, String key, fallback ) {
	if ( typeof options == "Dict" and options.exists(key) ) {
		return options.get(key);
	}
	return fallback;
}

function _positive_int_option ( value, String name ) {
	if ( typeof value ne "Number" or int(value) != value or value < 1 ) {
		throw new BrainfzckRuntimeError(
			message: "lang/brainfzck: " _ name _
				" must be a positive integer",
		);
	}
	return value;
}

function _options ( options ) {
	let eof := "" _ _option( options, "eof", "zero" );
	if ( eof ne "zero" and eof ne "minus-one" and eof ne "unchanged" ) {
		throw new BrainfzckRuntimeError(
			message: "lang/brainfzck: eof must be zero, minus-one, or unchanged",
		);
	}

	let tape_size := _positive_int_option(
		_option( options, "tape_size", 30000 ),
		"tape_size",
	);
	let cell_size := _positive_int_option(
		_option( options, "cell_size", 256 ),
		"cell_size",
	);
	let input := "" _ _option( options, "input", "" );
	let input_callback := _option( options, "input_callback", null );
	let output_callback := _option( options, "output_callback", null );

	if ( input_callback != null and not( input_callback instanceof Function ) ) {
		throw new BrainfzckRuntimeError(
			message: "lang/brainfzck: input_callback must be a Function",
		);
	}
	if ( output_callback != null and not( output_callback instanceof Function ) ) {
		throw new BrainfzckRuntimeError(
			message: "lang/brainfzck: output_callback must be a Function",
		);
	}

	return {
		eof: eof,
		tape_size: tape_size,
		cell_size: cell_size,
		input: input,
		input_callback: input_callback,
		output_callback: output_callback,
	};
}

function _is_command ( String ch ) {
	return ch eq ">" or ch eq "<" or ch eq "+" or ch eq "-" or
		ch eq "." or ch eq "," or ch eq "[" or ch eq "]";
}

function _jump_key ( Number index ) {
	return "" _ index;
}

function _syntax_error ( String message, String source_name,
Number source_index ) {
	throw new BrainfzckSyntaxError(
		message: message,
		source_name: source_name,
		source_index: source_index,
	);
}

function compile_brainfzck ( String source, String source_name := "<string>" ) {
	let commands := [];
	let source_indexes := [];
	let jumps := {};
	let stack := [];
	let i := 0;

	while ( i < length source ) {
		let ch := substr( source, i, 1 );
		if ( _is_command(ch) ) {
			let op_index := commands.length();
			commands.push(ch);
			source_indexes.push(i);

			if ( ch eq "[" ) {
				stack.push(op_index);
			}
			else if ( ch eq "]" ) {
				if ( stack.length() == 0 ) {
					_syntax_error( "Unmatched ]", source_name, i );
				}
				let start := stack.pop();
				jumps.set( _jump_key(start), op_index );
				jumps.set( _jump_key(op_index), start );
			}
		}
		i++;
	}

	if ( stack.length() > 0 ) {
		let start := stack.pop();
		_syntax_error( "Unmatched [", source_name, source_indexes[start] );
	}

	return new BrainfzckProgram(
		source: source,
		source_name: source_name,
		commands: commands,
		source_indexes: source_indexes,
		jumps: jumps,
	);
}

function _runtime_error ( BrainfzckProgram program, Number pc,
String message ) {
	let source_index := -1;
	if ( pc >= 0 and pc < program.get_source_indexes().length() ) {
		source_index := program.get_source_indexes()[pc];
	}
	throw new BrainfzckRuntimeError(
		message: message,
		source_name: program.get_source_name(),
		source_index: source_index,
	);
}

function _get_cell ( Array tape, Number pointer ) {
	while ( pointer >= tape.length() ) {
		tape.push(0);
	}
	return tape[pointer];
}

function _set_cell ( Array tape, Number pointer, Number value ) {
	while ( pointer >= tape.length() ) {
		tape.push(0);
	}
	tape[pointer] := value;
	return value;
}

function _wrap_cell ( Number value, Number cell_size ) {
	let wrapped := value mod cell_size;
	return wrapped + cell_size if wrapped < 0;
	return wrapped;
}

function _input_byte ( Dict opts, Number index ) {
	let raw := null;
	let input_callback := opts{input_callback};

	if ( input_callback != null ) {
		raw := input_callback();
	}
	else if ( index < length opts{input} ) {
		raw := substr( opts{input}, index, 1 );
	}

	return null if raw == null;
	return _wrap_cell( raw, opts{cell_size} ) if typeof raw == "Number";
	return _wrap_cell( ord( "" _ raw, 0 ), opts{cell_size} );
}

function _output_byte ( Dict opts, Array output, Number byte ) {
	let ch := chr(byte);
	if ( opts{output_callback} != null ) {
		opts{output_callback}( ch, byte );
	}
	else {
		output.push(ch);
	}
	return ch;
}

function _run_program ( BrainfzckProgram program, Dict opts ) {
	let tape := [ 0 ];
	let pointer := 0;
	let pc := 0;
	let input_index := 0;
	let output := [];
	let commands := program.get_commands();
	let jumps := program.get_jumps();

	while ( pc < commands.length() ) {
		let op := commands[pc];
		if ( op eq ">" ) {
			pointer++;
			if ( pointer >= opts{tape_size} ) {
				_runtime_error( program, pc, "Tape pointer moved past end" );
			}
		}
		else if ( op eq "<" ) {
			pointer--;
			if ( pointer < 0 ) {
				_runtime_error( program, pc, "Tape pointer moved before start" );
			}
		}
		else if ( op eq "+" ) {
			_set_cell(
				tape,
				pointer,
				_wrap_cell( _get_cell( tape, pointer ) + 1, opts{cell_size} ),
			);
		}
		else if ( op eq "-" ) {
			_set_cell(
				tape,
				pointer,
				_wrap_cell( _get_cell( tape, pointer ) - 1, opts{cell_size} ),
			);
		}
		else if ( op eq "." ) {
			_output_byte( opts, output, _get_cell( tape, pointer ) );
		}
		else if ( op eq "," ) {
			let byte := _input_byte( opts, input_index );
			input_index++ if opts{input_callback} == null;
			if ( byte == null ) {
				if ( opts{eof} eq "zero" ) {
					byte := 0;
				}
				else if ( opts{eof} eq "minus-one" ) {
					byte := opts{cell_size} - 1;
				}
			}
			_set_cell( tape, pointer, byte ) if byte != null;
		}
		else if ( op eq "[" ) {
			if ( _get_cell( tape, pointer ) == 0 ) {
				pc := jumps.get( _jump_key(pc) );
			}
		}
		else if ( op eq "]" ) {
			if ( _get_cell( tape, pointer ) != 0 ) {
				pc := jumps.get( _jump_key(pc) );
			}
		}
		pc++;
	}

	return join( "", output );
}

function brainfzck ( String source, options? ) {
	return compile_brainfzck(source).run(options);
}