Brainfuck interpreter in POSIX sh

brainfuck.sh

#!/bin/sh
# Brainfuck interpreter implemented in pure POSIX sh builtins only (except I/O)
# Tested in bash and busybox ash (getchar uses a bash-specific read)

# === I/O ===
getchar() {
    # bashism
    IFS= read -rN 1 a
    if [ -z "$a" ]; then
        echo $th
    else
        printf %d "'$a"
    fi
}
putchar() {
    printf "\x$(printf %x $1)"
}

# === Core BF interpreter: pure POSIX shell with builtins only from here on ===
pl=""
pr=""
while read -r line; do
    pl="$pl$line"
done <"$1"

th="0"
tl=""
tr=""

while :; do
    case "$pl" in
        '+'*)
            th=$((th+1));;
        '-'*)
            th=$((th-1));;
        '.'*)
            putchar $th;;
        ','*)
            th=$(getchar);;
        '>'*)
            tl="$th $tl"
            set -- $tr
            th=${1:-0}
            shift
            tr="$*"
            ;;
        '<'*)
            tr="$th $tr"
            set -- $tl
            th=${1:-0}
            shift
            tl="$*"
            ;;
        '['*)
            case "$th" in 0)
                i=1
                while :; do
                    tmp="${pl#?}"
                    pr="${pl%"$tmp"}$pr"
                    pl="$tmp"
                    case "$pl" in
                        '['*) i=$((i+1));;
                        ']'*) i=$((i-1));;
                    esac
                    case $i in 0) break; esac
                done
            esac
            ;;
        ']'*)
            case "$th" in 0);; *)
                i=1
                while :; do
                    tmp="${pr#?}"
                    pl="${pr%"$tmp"}$pl"
                    pr="$tmp"
                    case "$pl" in
                        ']'*) i=$((i+1));;
                        '['*) i=$((i-1));;
                    esac
                    case $i in 0) break; esac
                done
            esac
            ;;
        '')
            break
    esac
    tmp="${pl#?}"
    pr="${pl%"$tmp"}$pr"
    pl="$tmp"
done

For getchar, might I recommend:

read dummy a <<EOF
$(dd bs=1 count=1|od -t u1)
EOF
if [ -z "$a" ]; then
  echo "$th"
else
  printf '%s' "$a"
fi

From http://www.etalabs.net/sh_tricks.html. The only reason to change it to this is that that is actually 100% POSIX, without relying on a bash-ism.

It's a tradeoff - the read version is a bashism, but, under bash, uses only shell built-ins without any subprocess calls. The dd version is POSIX, but requires subprocesses. I went with the 'read' option to keep the builtins-only requirement under bash at least. AFAICT I/O is not possible to implement under both constraints (not even output, mostly because 'echo' is not required to be a built-in, otherwise you could just slap a big ASCII table case statement on there), but I/O is out of scope for Turing-completeness.

Also, the dd version does not turn off terminal line buffering, while the read version does. This could be relevant for Brainfuck programs that try to do some kind of interactive input.

It's a tradeoff - the read version is a bashism, but, under bash, uses only shell built-ins without any subprocess calls. The dd version is POSIX, but requires subprocesses. I went with the 'read' option to keep the builtins-only requirement under bash at least. AFAICT I/O is not possible to implement under both constraints (not even output, mostly because 'echo' is not required to be a built-in, otherwise you could just slap a big ASCII table case statement on there), but I/O is out of scope for Turing-completeness.

Isn't read -r POSIX?

Also, the dd version does not turn off terminal line buffering, while the read version does. This could be relevant for Brainfuck programs that try to do some kind of interactive input.

The convention is actually to line-buffer it, though. I understand not wanting to use external utilities, but you can implement I/O portably and properly handle EOF using built-ins if you line-buffer input; you can make it work with pure bash, dash, yash, ash, and ksh. And if what I mentioned above is true, then the only non-POSIX built-in you need is printf (and you can make it compliant with POSIX printf). What is this licensed under?

Thanks for giving me the good idea.
Now I've just found if read line is \n-terminated or EOF-terminated;

IFS= read -r && TERMINATED_WITH=LF || TERMINATED_WITH=EOF

That is, the read's exit status would be 0 if \n-terminated, 1 otherwise.

Also your code has:

putchar() {
    printf "\x$(printf %x $1)"
}

but the fact is that the format %x and \xHH (where HH is hexadecimal) are not in POSIX; octal is available instead.
Thus, you could do this:

putchar(){
    (
    O="$(printf %o $1)"'
    case O in
        ?) O=00"$O";;
        ??) O=0"$O";;
        ????*)
            printf '%s' "$0: putchar: assertion failed: (length of O)<4" 1>&2
            exit 10
            ;;
    esac
    printf '\'"$O"
    )
}

putchar(){
    (
    O="$(printf %o $1)"'
    case O in
        ?) O=00"$O";;
        ??) O=0"$O";;
        ????*)
            printf '%s' "$0: putchar: assertion failed: (length of O)<4" 1>&2
            exit 10
            ;;
    esac
    printf '\'"$O"
    )
}

This is shorter;

printf '\'"$(printf %03o "$1")"