McCarthy's Ambiguous Operator (2005) • Hacker News Board

Re: McCarthy's Ambiguous Operator (2005)

#21

Post by camtarn » Tue, Feb 12, 2019, 12:05 PM UTC

DarkWiiPlayer wrote: post #11

Regarding the ruby example, thinking about the performance of such a (non-)feature makes my head spin. Not to mention the possibility of side-effects wrecking the program state and the complexity of debugging code like that without making Rubys error handling aware of such a construct. All in all, this seems like a fun hack, but a catastrophically bad idea in practice.

There's some discussion about removing callcc from the language here:

https://bugs.ruby-lang.org/issues/10548

It looks like it's still included at the moment, though:

http://ruby-doc.org/core-2.6.1/Kernel.html#method-i-callcc

Re: McCarthy's Ambiguous Operator (2005)

#22

Post by tempodox » Tue, Feb 12, 2019, 12:22 PM UTC

I envy the languages with continuations. That makes the implementation of backtracking so much easier.

Re: McCarthy's Ambiguous Operator (2005)

#23

Post by sacado2 » Tue, Feb 12, 2019, 12:32 PM UTC

It sounds a lot like constraint programming.

Re: McCarthy's Ambiguous Operator (2005)

#24

Post by sacado2 » Tue, Feb 12, 2019, 12:35 PM UTC

DarkWiiPlayer wrote: post #11

Regarding the ruby example, thinking about the performance of such a (non-)feature makes my head spin. Not to mention the possibility of side-effects wrecking the program state and the complexity of debugging code like that without making Rubys error handling aware of such a construct. All in all, this seems like a fun hack, but a catastrophically bad idea in practice.

This is an NP-complete problem, so performance will be an issue anyway.

Re: McCarthy's Ambiguous Operator (2005)

#25

Post by nn3 » Tue, Feb 12, 2019, 12:55 PM UTC

ekidd wrote: post #20

Author here. It's fun to see this post 14 years later! If you like this, you might also enjoy: - Prolog: This is an entire language built around choice and backtracking. https://en.wikipedia.org/wiki/Prolog - The Reasoned Schemer , which builds a Prolog-in-Scheme from first principles. This book is excellent, or even mind-blowing if you're never seen this before. https://mitpress.mit.edu/books/reasoned-schemer - Oz/M…

There are also icon and txr. I always liked the icon approach where backtracking is fairly explicit, but still tightly integrated into the language. Txr is more for text analysis.

Re: McCarthy's Ambiguous Operator (2005)

#26

Post by Sharlin » Tue, Feb 12, 2019, 1:14 PM UTC

I had been wondering what the `amb` operator in Rx is named after. It takes any number of reactive streams and evaluates to the one that first emits a value, discarding the others. I presume the analogy here is that because it doesn’t block, it figuratively has to ”look into the future” to figure out which stream to return. But is there a deeper theoretical connection there?

Re: McCarthy's Ambiguous Operator (2005)

#27

Post by neel_k » Tue, Feb 12, 2019, 1:58 PM UTC

_ZeD_ wrote: post #8

So it's a base operator for prolog unification?

No. From an implementation POV, Prolog adds two pieces to ordinary programming languages: backtracking plus unification. This post talks about backtracking, but doesn't touch upon unification at all.

Re: McCarthy's Ambiguous Operator (2005)

#28

Post by billsix » Tue, Feb 12, 2019, 2:36 PM UTC

tempodox wrote: post #22

I envy the languages with continuations. That makes the implementation of backtracking so much easier.

Continuations also allowed me to implement python’s yield/send in 16 lines of Scheme code :-)

http://billsix.github.io/bug.html#_make_generator

Re: McCarthy's Ambiguous Operator (2005)

#29

Post by agumonkey » Tue, Feb 12, 2019, 3:02 PM UTC

ekidd wrote: post #20

Author here. It's fun to see this post 14 years later! If you like this, you might also enjoy: - Prolog: This is an entire language built around choice and backtracking. https://en.wikipedia.org/wiki/Prolog - The Reasoned Schemer , which builds a Prolog-in-Scheme from first principles. This book is excellent, or even mind-blowing if you're never seen this before. https://mitpress.mit.edu/books/reasoned-schemer - Oz/M…

is there any new wild idea in this field ? so far all I could find was FD/CLP over prolog like search.

Re: McCarthy's Ambiguous Operator (2005)

#30

Post by hopler » Tue, Feb 12, 2019, 3:14 PM UTC

Dylan16807 wrote: post #16

rfw wrote: post #12

Earlier quoted context omitted.

We can implement it with a single `amb` function, too (I took some shortcuts that might have hidden some of the nature of the implementation)! -- Lifts a list into Amb. amb :: [a] -> Amb a If we assume Amb is just List, then: amb = id If we write the example in the original article in desugared style, we get: amb [1, 2, 3] >>= \x -> amb [4, 5, 6] >>= \y -> if x * y /= 8 then amb [] else pure () >> pure (x, y) (we are…

That's not an amb function. That's a builtin type that's inherently amb-y. You still get credit for solving the basic problem but let's not be misleading. Also don't forget to call head.

In Haskell monads, you define a monadic type and then "bind" is the function that does something specific for that type. "It's a type" because Haskell uses static types and polymorphism to factor out common logic used by different functions.

Of course Haskell list is a built-in type, but it's not magical except for the special bracket syntax. You can make a sugar-free user-defined type

    data List a = Nil | Cons a (List a)

if you want.