Anonymous user
Talk:Amb: Difference between revisions
→Nondeterministic
(My apologies...I thought I'd made sure math extensions would continue to work.) |
|||
Line 27:
Wouldn't it more sense just to call the task something like "nondeterministic choice" and leave it to the implementations to use whatever language feature works best for that? The SICP implenetation uses call/cc and side-effects, but to require a special operator ''amb'' for Prolog, where nondeterminism is in-built, is a bit silly. Python has generators. And it's equally silly in the Haskell example, where ''amb'' just reduces to the identity in the List-Monad. One could emulate the construction in the Continuation-and-State-Monad, but that would be even more silly :-) After all, the article "Replacing failure with a list of successes" was written long after SICP. The List-Monad construction also probably carries over more easily to other languages than call/cc. --[[User:Dirkt|Dirkt]] 02:22, 25 March 2008 (MDT)
What I think the first sentence is trying to say (and also the conventional meaning) is that Amb is a bottom-avoiding choice combinator.
What I think the first sentence is trying to say (and also the conventional meaning) is that Amb is a bottom-avoiding choice combinator. Suppose you have a function <math>f</math> that works fine for some inputs <math>x</math>, but crashes or fails to terminate for others. Similarly a function <math>g</math> works only for some limited set of inputs, not necessarily the same as <math>f</math>. Then <math>\mathrm{Amb}(f,g)</math> is a function that returns either <math>f(x)</math> or <math>g(x)</math> when given an input <math>x</math>, but is guaranteed (!) to choose the one that terminates correctly if one of them does and the other doesn't. Once you understand this definition, you'll realize that the only right way to implement Amb for arbitrary unknown functions <math>f</math> and <math>g</math> is by multi-threading or interleaving on some level, which is where the emphasis in this task belongs. (You can't get away with using only exception handlers unless you exclude the possibility of non-termination.) Note that this semantics differs from non-deterministic choice. If <math>f</math> and <math>g</math> happen to have disjoint domains, it's completely deterministic.▼
:: This task and a couple others, unfortunately, have descriptions that are pretty meaningless and I'm not sure it makes much sense for people to speculate what any one of us thinks they're supposed to do. If it isn't clear, then we shouldn't guess - we should eliminate the task and make it the burden of whoever posed it to come up with a new one that actually means something testable. [[User:Sgeier|Sgeier]] 00:28, 6 October 2009 (UTC)
Suppose you have a function <math>f</math> that works fine for some inputs <math>x</math>, but crashes or fails to terminate for others. Similarly a function <math>g</math> works only for some limited set of inputs, not necessarily the same as <math>f</math>. Then <math>\mathrm{Amb}(f,g)</math> is a function that returns either <math>f(x)</math> or <math>g(x)</math> when given an input <math>x</math>, but is guaranteed (!) to choose the one that terminates correctly if one of them does and the other doesn't.
:: This is a pretty succinct little paragraph that outlines an understandable, verifiable, testable concept. I know how I would implement such a thing in a variety of languages. I know how I would test a given piece of code and verify that it does what you describe. Unfortunately, this paragraph does no bear the slightest resemblance to the actual task description and there is no way for me to know whether this task actually asks for what you wrote there or whether it is asking for something different entirely. Neither do I see any resemblance between your description and any of the things written in the section up there (where the only group of words that appears to form English sentences is about "sequences of elements in sets").[[User:Sgeier|Sgeier]] 00:28, 6 October 2009 (UTC)
▲
--[[User:Sluggo|Sluggo]] 22:20, 6 September 2009 (UTC)
| |||