Interpret whatfuck

Question

Smallfuck is a brainfuck-like language with 1-bit cells. It has the following instructions:

> Increment the pointer
< Decrement the pointer
* Flip the current bit
[ If the current bit is not set, jump to the instruction after the matching ]
] If the current bit is set, jump to the instruction after the matching [ 
    ( or just jump unconditionally to matching [ )

Whatfuck adds one more instruction:

? Nondeterministically set the current bit to 0 or 1.

A whatfuck program does not take any input. It can result in one of 3 possibilities: 1 (accept), 0 (reject) or it may never halt.

The program will result in 1 if there exists a sequence of bits chosen for ?s which results in the program terminating with 1 as the current bit.

The program terminates with 0 if all possible choices terminate with current bit 0,

If some choices don't terminate, and all choices which terminate do so with 0, then the program will never terminate.

Your interpreter should run all possibilities simultaneously. You can't try 0 first and then try 1, because some programs will not terminate when they should. For example, *[?*]* will accept with the choice 1, but never terminate if you always choose 0.

As an example, here is a python 2 interpreter I wrote, not golfed

Rules

• Your interpreter must accept a whatfuck program from stdin and print its result.

• You may assume the whatfuck program only contains characters []<>*?

• The array of bits is unbounded on both ends.

• Shortest code wins.

Some Test Cases

This will fail if your code always tries 0 first

*[?*]*
1

Is there a subset of {-7,-3, 5, 8} whose sum is 3?

*<<<<<?[<<<<<<<<<<<<<<]?[<<<<<<]?[>>>>>>>>>>]?[>>>>>>>>>>>>>>>>]<
1

Is there a subset of {-7,-3, 5, 8} whose sum is 4?

*<<<<<<<?[<<<<<<<<<<<<<<]?[<<<<<<]?[>>>>>>>>>>]?[>>>>>>>>>>>>>>>>]<
0

Is there a way to assign boolean values to a,b and c such that

(a XOR b) AND (a XOR c) AND (b XOR c) is true?

?[*>*>*<<]?[*>*>>*<<<]?[*>>*>*<<<]>[*>[*>[*>*<]<]<]>>>
0

Answer 1

Python, 305 chars

P=raw_input()+'$'
S=[(0,0,[])]
F={}
R={}
i=r=0
for c in P:
 if'['==c:S+=i,
 if']'==c:j=S.pop();F[j]=R[i]=i-j
 i+=1
while S*(1-r):p,t,B=S.pop(0);c=P[p];b=B.count(t)%2;p+=1+F.get(p,0)*(1-b)-R.get(p,0)*b;t+=(c=='>')-(c=='<');B=B+[t]*(c=='*');r|=(c=='$')&b;S+=[(p,t,B)]*(c!='$')+[(p,t,B+[t])]*(c=='?')
print r

Keeps track of the nondeterministic set of states in S, each with a code position p, a tape position t, and a list of tape indexes B. A tape index can appear multiple times in the list B, the tape at that index is 1 if the index appears an odd number of times in B.

Answer 2

Infinite tape ahoy!

Haskell, 516

i((p:l,r),(π,'<':φ))=[((l,p:r),('<':π,φ))]
i((l,p:r),(π,'>':φ))=[((p:l,r),('>':π,φ))]
i((l,p:r),(π,'*':φ))=[((l,1-p:r),('*':π,φ))]
i((l,_:r),(π,'?':φ))=[((l,b:r),('?':π,φ))|b<-[0,1]]
i(s@(l,0:r),(π,'[':φ))=[(s,m(']':π,φ)0)]
i(s,(π,'[':φ))=[(s,(']':π,φ))]
i(s,(π,']':φ))=[(s,ξ$m(']':φ,π)0)]
i _=[]
m(l,']':r)0=('[':l,r)
m(l,']':r)n=m('[':l,r)$n-1
m(l,'[':r)n=m(']':l,r)$n+1
m(l,c:r)n=m(c:l,r)n
ν=null;ο=0:ο
μ[]="0"
μ ω|ν[ψ|ψ@((_,b:_),_)<-ω,b>0,ν$i ψ]=μ$ω>>=i
μ _="1"
ξ(a,b)=(b,a)
main=interact$ \ζ->μ[((ο,ο),("",ζ))]

Answer 3

Python (405 399 379)

It takes the input on one line, but I "may assume the whatfuck program only contains characters []<>*?" and newline isn't on that list :P

w,i,p,a={},0,raw_input(),[(0,0,[],[])]
for c in p:
 if c=='[':a+=i,
 if c==']':g=a.pop();w[i],w[g]=g,i
 i+=1
i,z=0,lambda l:l and l.pop()or 0
while a:
 n,c,l,r=a.pop(0)
 try:o=p[n]
 except:
        if c:i=1;break
        continue
 if o=='*':c=not c
 if o=='>':l+=c,;c=z(r)
 if o=='<':r+=c,;c=z(l)
 if o in'[]'and(']'==o)==c:n=w[n]
 if o=='?':a+=(n+1,not c,l[:],r[:]),
 a+=(n+1,c,l,r),
print i