Arc Forum | Nondeterminism

Arc Forum

Nondeterminism

4 points by rincewind 6069 days ago | 8 comments

  (def getcc ()
    ccc.idfn)

  (= amb-stack* nil)

  (def fail ()
    (aif amb-stack* ((pop amb-stack*) nil) (err "no more choices left")))

  (mac amb vals
    `(point return
      ,@(map
         [idfn `(aif (getcc) (do (push it amb-stack*) (return ,_))) ] vals)
      (fail)))

3 points by absz 6069 days ago | link

I think this doesn't quite work:

  arc> (amb 1 2)
  1
  arc> (amb (fail))
  2
  arc> (amb (fail))
  Error: "no more choices left"

My understanding is that when one leaves an amb, one can't use fail to return to it. Or am I supposed to be able to do this?

-----

2 points by rincewind 6068 days ago | link

I think this is supposed to work.

From "Teach yourself Scheme in Fixnum Days":

In particular, amb is required to return a value if at least one its subexpressions converges, ie, doesn't fail. Thus,

   (amb 1 (amb))

 and
   
   (amb (amb) 1)

 both return 1.

http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-...

-----

1 point by absz 6068 days ago | link

That doesn't actually address my concern, but this (from the same page) does:

  (if (amb #f #t)
    1
    (amb))

This has to force the first amb to return #t, or the whole expression would fail. I still find it somewhat odd, though, that I can (fail) on the next line, but I suppose there's not a better way to handle it; after all, that's probably just because the interpreter is sequential.

-----

2 points by almkglor 6069 days ago | link

In order to allow using amb in multiple threads (Anarki only!):

  (def getcc ()
    ccc.idfn)

  (= amb-stack* (thread-local))
  (= (amb-stack*) nil)

  (def fail ()
    (aif (amb-stack*) ((pop (amb-stack*)) nil) (err "no more choices left")))

  (mac amb vals
    ; use w/uniq !!
    (w/uniq return
      `(point ,return
        ,@(map
           [idfn `(aif (getcc) (do (push it (amb-stack*)) (,return ,_))) ] vals)
        (fail))))

-----

2 points by rincewind 6068 days ago | link

I think we could add a prolog-style cut-operator

   (def cut ()
       (if amb-stack* (pop amb-stack*)))

But I am not sure whether the semantics of this is like in Prolog. It may not be exactly the same.

-----

1 point by tokipin 6067 days ago | link

for those of use who'vn't a clue what this is, what does "amb" mean? ambivalent?

-----

2 points by rincewind 6067 days ago | link

It means ambiguous

-----

1 point by offby1 6069 days ago | link

If that really works, I bet it's a record for brevity.

-----