How to resolve the algorithm Amb step by step in the Smalltalk programming language
How to resolve the algorithm Amb step by step in the Smalltalk 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 Smalltalk programming language
Source code in the smalltalk programming language
Object subclass:#Amb
instanceVariableNames:''
classVariableNames:''
poolDictionaries:''
category:'Rosetta'
!
Smalltalk::Notification subclass:#FoundSolution
instanceVariableNames:''
classVariableNames:''
poolDictionaries:''
privateIn:Amb
!
!Amb::FoundSolution methods!
defaultAction
^ parameter
! !
!Amb class methods!
try:values in:aBlock
values do:[:each |
|rslt|
(rslt := aBlock value:each) notNil ifTrue:[
"hint: Notifications simply return nil, if there is no handler"
(FoundSolution raiseRequestWith:rslt) notNil ifTrue:[ ^ rslt ].
].
].
^ nil
! !
result :=
Amb try:#('the' 'that' 'a') in:[:w1 |
Amb try:#('frog' 'elephant' 'thing') in:[:w2 |
w2 first = w1 last ifTrue:[
Amb try:#('walked' 'traded' 'grows') in:[:w3 |
w3 first = w2 last ifTrue:[
Amb try:#('slowly' 'quickly') in:[:w4 |
Transcript showCR: e'trying {{w1 . w2 . w3 . w4}}'. "debug trace only"
w4 first = w3 last ifTrue:[
{w1 . w2 . w3 . w4} ]]]]]]].
Transcript showCR: e'found solution: {result}'
result :=
Amb try:(1 to:11) in:[:x |
Amb try:(1 to:11) in:[:y |
Amb try:(1 to:11) in:[:z |
(x squared + y squared = z squared) ifTrue:[
{x . y . z}
].
]]].
Transcript showCR: e'found rectangle {result}'.
!Amb class methods!
until:questionBlock in:aBlock
"compute solutions, asking if more solutions are to be searched
via questionBlock (gets the found solution as arg)"
|allResults|
allResults := OrderedCollection new.
aBlock on:FoundSolution do:[:ex |
allResults add:ex parameter.
(questionBlock value:ex parameter) ifTrue:[^ allResults].
ex proceedWith:nil.
].
^ allResults
!
allSolutions:aBlock
^ self until:[:solution | false] in:aBlock
!
result :=
Amb allSolutions:[
Amb try:(1 to:11) in:[:x |
Amb try:(1 to:11) in:[:y |
y <= x ifTrue:[
Amb try:(1 to:11) in:[:z |
(x squared + y squared = z squared) ifTrue:[
{x . y . z} ]]]]]].
Transcript showCR: e'all rectangles: {result}'.
result :=
Amb
until:[:solution |
(Dialog confirm: e'Found solution: {solution}\nSee more?') not
] in:[
Amb try:(1 to:100) in:[:x |
Amb try:(1 to:100) in:[:y |
y <= x ifTrue:[
Amb try:(1 to:100) in:[:z |
(x squared + y squared = z squared) ifTrue:[
{x . y . z} ]]]]]].
Transcript showCR: result.
tryAll:valuesCollection in:aBlock
"try each set of values in aBlock;
aBlock's number of args must be the number of elements in valuesCollection"
|tryAll|
tryAll :=
[:valuesCollection :argsIn |
valuesCollection isEmpty ifTrue:[
aBlock valueWithArguments:argsIn
] ifFalse:[
self try:(valuesCollection first) in:[:arg |
tryAll value:(valuesCollection from:2) value:argsIn,{arg} ]]].
^ tryAll value:valuesCollection value:#()
Amb
tryAll:#(
('the' 'that' 'a')
('frog' 'elephant' 'thing')
('walked' 'traded' 'grows')
('slowly' 'quickly')
) in:[:w1 :w2 :w3 :w4 |
(w2 first = w1 last
and:[ w3 first = w2 last
and:[ w4 first = w3 last
]]) ifTrue:[
{w1 . w2 . w3 . w4} ]]
"/ find { s. e. n. d. m. o. r. y.}
"/ such that:
"/ send
"/ + more
"/ -------
"/ = money
result :=
Amb try:(0 to:9) in:[:s |
Amb try:(0 to:9) in:[:e | e~=s ifTrue:[
Amb try:(0 to:9) in:[:n | (n~=e)&(n~=s) ifTrue:[
Amb try:(0 to:9) in:[:d | (d~=n)&(d~=e)&(d~=s) ifTrue:[
Amb try:(1 to:1) in:[:m | (m~=d)&(m~=n)&(m~=e)&(m~=s) ifTrue:[
Amb try:(0 to:9) in:[:o | (o~=m)&(o~=d)&(o~=n)&(o~=e)&(o~=s) ifTrue:[
Amb try:(0 to:9) in:[:r | (r~=o)&(r~=m)&(r~=d)&(r~=n)&(r~=e)&(r~=s) ifTrue:[
Amb try:(0 to:9) in:[:y | (y~=r)&(y~=o)&(y~=m)&(y~=d)&(y~=n)&(y~=e)&(y~=s) ifTrue:[
(
( (1000 * s) + (100 * e) + (10 * n) + d)
+ ( (1000 * m) + (100 * o) + (10 * r) + e)
= ((10000 * m) + (1000 * o) + (100 * n) + (10 * e) + y)
) ifTrue:[
Transcript showCR: e' {s}{e}{n}{d}'.
Transcript showCR: e' + {m}{o}{r}{e}'.
Transcript showCR: e' -----------'.
Transcript showCR: e' = {m}{o}{n}{e}{y}'.
{'s'->s . 'e'->e . 'n'->n . 'd'->d . 'm'->m . 'o'->o . 'r'->r . 'y'->y }
].
]]]]]]]]]]]]]]].
Transcript cr; showCR: result.
You may also check:How to resolve the algorithm Split a character string based on change of character step by step in the Rust programming language
You may also check:How to resolve the algorithm Chat server step by step in the Ada programming language
You may also check:How to resolve the algorithm Sorting algorithms/Bogosort step by step in the TI-83 BASIC programming language
You may also check:How to resolve the algorithm Identity matrix step by step in the Seed7 programming language
You may also check:How to resolve the algorithm Sieve of Eratosthenes step by step in the HicEst programming language