Here are two examples in Python syntax, assuming "yield" is no longer a keyword. def f(): def receiver(yield): yield(2) # yield jumps out of

Here are two examples in Python syntax, assuming "yield" is no longer a keyword. def f(): def receiver(yield): yield(2) # yield jumps out of the 'receiver' function and never returns print("This never prints") x = callcc(receiver) return x+1 print(f()) # f returns 2+1 # backtracks stores (continuation,[values]) pairs. Whenever a computation fails, we pull out another # value from the list and feed it to the continuation. The idea is to perform a depth-first search. backtracks = [] def fail(): """Aborts the current continuation and backtracks to another alternative stored in backtracks.""" if not backtracks: raise Exception('amb ran out of alternatives') yield, alternatives = backtracks.pop() alt = alternatives.pop() if alternatives: # this continuation still has alternatives, so put them back on the list in case of a future 'fail' backtracks.push((yield, alternatives)) yield(alt) def amb(*alternatives): """The "ambivalent operator." The arguments to amb are alternatives, and the return value of amb is an alternative which makes the future computation not fail.""" if not alternatives: fail() def receiver(yield): backtracks.append((yield, alternatives)) fail() return callcc(receiver) def expect(b): if not b: fail() def test_amb(): """Let's find a Pythagorean triple.""" x = amb(*range(1,100)) y = amb(*range(1,100)) z = amb(*range(1,100)) expect(x**2 + y**2 == z**2) return (x,y,z) # We can print out all the Pythagorean triples. trip = test_amb() print("(x,y,z)=(%s,%s,%s)" % trip) fail() # fail every time so it keeps backtracking, but the side effect of printing out remains