How to resolve the algorithm Amb step by step in the Python programming language
How to resolve the algorithm Amb step by step in the Python programming language
Table of Contents
Problem Statement
Define and give an example of the Amb operator. The Amb operator (short for "ambiguous") expresses nondeterminism. This doesn't refer to randomness (as in "nondeterministic universe") but is closely related to the term as it is used in automata theory ("non-deterministic finite automaton"). The Amb operator takes a variable number of expressions (or values if that's simpler in the language) and yields a correct one which will satisfy a constraint in some future computation, thereby avoiding failure. Problems whose solution the Amb operator naturally expresses can be approached with other tools, such as explicit nested iterations over data sets, or with pattern matching. By contrast, the Amb operator appears integrated into the language. Invocations of Amb are not wrapped in any visible loops or other search patterns; they appear to be independent. Essentially Amb(x, y, z) splits the computation into three possible futures: a future in which the value x is yielded, a future in which the value y is yielded and a future in which the value z is yielded. The future which leads to a successful subsequent computation is chosen. The other "parallel universes" somehow go away. Amb called with no arguments fails. For simplicity, one of the domain values usable with Amb may denote failure, if that is convenient. For instance, it is convenient if a Boolean false denotes failure, so that Amb(false) fails, and thus constraints can be expressed using Boolean expressions like Amb(x * y == 8) which unless x and y add to four. A pseudo-code program which satisfies this constraint might look like: The output is 2 4 because Amb(1, 2, 3) correctly chooses the future in which x has value 2, Amb(7, 6, 4, 5) chooses 4 and consequently Amb(x * y = 8) produces a success. Alternatively, failure could be represented using strictly Amb(): Or else Amb could take the form of two operators or functions: one for producing values and one for enforcing constraints: where Ambassert behaves like Amb() if the Boolean expression is false, otherwise it allows the future computation to take place, without yielding any value. The task is to somehow implement Amb, and demonstrate it with a program which chooses one word from each of the following four sets of character strings to generate a four-word sentence: The constraint to be satisfied is that the last character of each word (other than the last) is the same as the first character of its successor. The only successful sentence is "that thing grows slowly"; other combinations do not satisfy the constraint and thus fail. The goal of this task isn't to simply process the four lists of words with explicit, deterministic program flow such as nested iteration, to trivially demonstrate the correct output. The goal is to implement the Amb operator, or a facsimile thereof that is possible within the language limitations.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Amb step by step in the Python programming language
The provided source code is a Python program that demonstrates the use of the amb function, which implements a constraint satisfaction problem (CSP) solver.
The Amb class represents a CSP solver. It has three main attributes:
1._names2values: A dictionary that maps global names to sets of possible values.
2._func: A Boolean constraint function that takes a tuple of values as input and returns True if the values satisfy the constraint and False otherwise.
3._valueiterator: An iterator that generates all possible combinations of values for the global names.
When called with an iterable, the Amb object returns an iterator that yields the next solution to the CSP.
An overview of what the code does:
- It defines a class
Ambwhich encapsulates the logic for solving constraint satisfaction problems (CSPs). __init__method initializes theAmbobject with an empty set of values for each global name, aNoneconstraint function, and aNonevalue iterator.__call__method can be called in several ways:- If called with a constraint function, it validates the function's arguments and sets up the
_func,_valueiterator, and_funcargnamesattributes for further use in solving the CSP. - If called with an iterable, it returns a frozen set of the provided values.
- If called without arguments, it attempts to find the next solution to the CSP using the previously defined constraint and value iterator.
- If called with a constraint function, it validates the function's arguments and sets up the
_nextinsearchmethod is a helper method that finds the next solution to the CSP. It iterates through all possible combinations of values for the global names until it finds one that satisfies the constraint function.__iter__and__next__methods allow theAmbobject to be used as an iterator.- The main function demonstrates the
Ambclass by solving three different CSPs.
In addition to the Amb class, the code also includes several helper functions and main functions that demonstrate its usage. Overall, the code provides a flexible and powerful way to solve CSPs in Python.
Source code in the python programming language
import itertools as _itertools
class Amb(object):
def __init__(self):
self._names2values = {} # set of values for each global name
self._func = None # Boolean constraint function
self._valueiterator = None # itertools.product of names values
self._funcargnames = None # Constraint parameter names
def __call__(self, arg=None):
if hasattr(arg, '__code__'):
##
## Called with a constraint function.
##
globls = arg.__globals__ if hasattr(arg, '__globals__') else arg.func_globals
# Names used in constraint
argv = arg.__code__.co_varnames[:arg.__code__.co_argcount]
for name in argv:
if name not in self._names2values:
assert name in globls, \
"Global name %s not found in function globals" % name
self._names2values[name] = globls[name]
# Gather the range of values of all names used in the constraint
valuesets = [self._names2values[name] for name in argv]
self._valueiterator = _itertools.product(*valuesets)
self._func = arg
self._funcargnames = argv
return self
elif arg is not None:
##
## Assume called with an iterable set of values
##
arg = frozenset(arg)
return arg
else:
##
## blank call tries to return next solution
##
return self._nextinsearch()
def _nextinsearch(self):
arg = self._func
globls = arg.__globals__
argv = self._funcargnames
found = False
for values in self._valueiterator:
if arg(*values):
# Set globals.
found = True
for n, v in zip(argv, values):
globls[n] = v
break
if not found: raise StopIteration
return values
def __iter__(self):
return self
def __next__(self):
return self()
next = __next__ # Python 2
if __name__ == '__main__':
if True:
amb = Amb()
print("\nSmall Pythagorean triples problem:")
x = amb(range(1,11))
y = amb(range(1,11))
z = amb(range(1,11))
for _dummy in amb( lambda x, y, z: x*x + y*y == z*z ):
print ('%s %s %s' % (x, y, z))
if True:
amb = Amb()
print("\nRosetta Code Amb problem:")
w1 = amb(["the", "that", "a"])
w2 = amb(["frog", "elephant", "thing"])
w3 = amb(["walked", "treaded", "grows"])
w4 = amb(["slowly", "quickly"])
for _dummy in amb( lambda w1, w2, w3, w4: \
w1[-1] == w2[0] and \
w2[-1] == w3[0] and \
w3[-1] == w4[0] ):
print ('%s %s %s %s' % (w1, w2, w3, w4))
if True:
amb = Amb()
print("\nAmb problem from "
"http://www.randomhacks.net/articles/2005/10/11/amb-operator:")
x = amb([1, 2, 3])
y = amb([4, 5, 6])
for _dummy in amb( lambda x, y: x * y != 8 ):
print ('%s %s' % (x, y))
# joins :: String -> String -> Bool
def joins(a, b):
return a[-1] == b[0]
print (
[
' '.join([w1, w2, w3, w4])
for w1 in ['the', 'that', 'a']
for w2 in ['frog', 'elephant', 'thing']
for w3 in ['walked', 'treaded', 'grows']
for w4 in ['slowly', 'quickly']
if joins(w1, w2) and joins(w2, w3) and joins(w3, w4)
]
)
def main():
print (
unlines([
unwords([w1, w2, w3, w4])
for w1 in ['the', 'that', 'a']
if True
for w2 in ['frog', 'elephant', 'thing']
if joins(w1, w2)
for w3 in ['walked', 'treaded', 'grows']
if joins(w2, w3)
for w4 in ['slowly', 'quickly']
if joins(w3, w4)
])
)
# joins :: String -> String -> Bool
def joins(a, b):
return a[-1] == b[0]
# unlines :: [String] -> String
def unlines(xs):
return '\n'.join(xs)
# unwords :: [String] -> String
def unwords(xs):
return ' '.join(xs)
if __name__ == '__main__':
main()
from itertools import chain
# amb :: [a] -> (a -> [b]) -> [b]
def amb(xs):
return lambda f: list(
chain.from_iterable(
map(f, xs)
)
)
# main :: IO ()
def main():
xs = enumFromTo(1)(10)
print ('Pythagorean triples from integers 1-10:')
print (
amb(xs)(
lambda x: amb(xs)
(lambda y: amb(xs)
(lambda z: when(
x * x + y * y == z * z
)(
(x, y, z)
)
))
)
)
# joins :: String -> String -> Bool
def joins(a, b):
return a[-1] == b[0]
print ('\nRC problem given above:')
print (
amb(['the', 'that', 'a'])(
lambda w1: amb(
['frog', 'elephant', 'thing']
)(lambda w2: amb(
['walked', 'treaded', 'grows']
)(lambda w3: amb(
['slowly', 'quickly']
)(lambda w4: when(
joins(w1, w2) and joins(w2, w3) and joins(w3, w4)
)(
(w1, w2, w3, w4)
))))
)
)
print('\nAdditional problem reference in procedural version above:')
print(
amb([1, 2, 3])
(
lambda x: amb([4, 5, 6])
(
lambda y: when(x * y != 8)
(
(x, y)
)
)
)
)
# GENERIC -------------------------------------------------
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
return lambda n: list(range(m, 1 + n))
# when :: Bool -> [a] -> [a]
def when(p):
return lambda x: [x] if p else []
# MAIN ---
if __name__ == '__main__':
main()
from itertools import chain
# amb :: [a] -> (a -> [b]) -> [b]
def amb(xs):
return lambda f: list(
chain.from_iterable(
map(f, xs)
)
)
# when :: Bool -> [a] -> [a]
def when(p):
return lambda xs: xs if p else []
# TEST ----------------------------------------------------
# joins :: String -> String -> Bool
def joins(a, b):
return a[-1] == b[0]
print (
amb(['the', 'that', 'a'])(
lambda w1: when(True)
(amb(['frog', 'elephant', 'thing'])
(lambda w2: when(joins(w1, w2))
(amb(['walked', 'treaded', 'grows'])
(lambda w3: when(joins(w2, w3))
(amb(['slowly', 'quickly'])
(lambda w4: when(joins(w3, w4))(
[w1, w2, w3, w4]
))))))
)
)
)
You may also check:How to resolve the algorithm Egyptian division step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Host introspection step by step in the Rust programming language
You may also check:How to resolve the algorithm Power set step by step in the RPL programming language
You may also check:How to resolve the algorithm Greatest common divisor step by step in the RPL programming language
You may also check:How to resolve the algorithm Iterated digits squaring step by step in the Swift programming language