Class: Amb

• Inheritance
• Description
• Class protocol
  • amb evaluations
• Private classes
• Examples

Inheritance:

   Object
   |
   +--Amb

Package:

stx:libbasic2

Category:

Programming-Support

Version:

rev: 1.2 date: 2020/12/28 15:12:19

user: cg

file: Amb.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

Description:

nondeterministic programming.

try values from a range or collection until a solution is found.
Backtracking is done when the action returns nil;
a solution is returned, if non-nil.

example: find the first solution to a problem (pythagoran triangles)

 Amb try:(1 to:11)                 in:[:x |
   Amb try:(1 to:x)                  in:[:y |
     Amb try:(1 to:11)                 in:[:z |
       (x squared + y squared = z squared) ifTrue:[
          {x . y . z}
       ]]]].      

example: find all solutions to a problem (pythagoran triangles)

 Amb allSolutions:[
   Amb try:(1 to:11)                 in:[:x |
     Amb try:(1 to:x)                  in:[:y |
       Amb try:(1 to:11)                 in:[:z |
         (x squared + y squared = z squared) ifTrue:[
            {x . y . z}
         ]]]]].      

copyright
COPYRIGHT (c) 2020 by Claus Gittinger
             All Rights Reserved

This software is furnished under a license and may be used
only in accordance with the terms of that license and with the
inclusion of the above copyright notice.   This software may not
be provided or otherwise made available to, or used by, any
other person.  No title to or ownership of the software is
hereby transferred.

Class protocol:

 allSolutions: aBlock

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}
]]]]]

Usage example(s):

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} ]. ]]]]].

 try: values in: aBlock

Amb try:#('the' 'that' 'a') in:[:w1 |
Amb try:#('frog' 'elephant' 'thing') in:[:w2 |
Amb try:#('walked' 'traded' 'grows') in:[:w3 |
Amb try:#('slowly' 'quickly') in:[:w4 |
Transcript showCR: e'trying {{w1 . w2 . w3 . w4}}'.
(w2 first = w1 last
and:[ w3 first = w2 last
and:[ w4 first = w3 last
]]) ifTrue:[
{w1 . w2 . w3 . w4}
]
]
]
]
].

Usage example(s):

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}}'. w4 first = w3 last ifTrue:[ {w1 . w2 . w3 . w4} ] ] ] ] ] ]].

Usage example(s):

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:[ (Dialog confirm: e'Found solution: {{x . y . z}}.\n\nSee more?') ifTrue:[ nil ] ifFalse:[ {x . y . z} ]. ]. ]]].

Usage example(s):

Amb allSolutions:[ 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} ]. ]]]].

Usage example(s):

Amb allSolutions:[ Amb try:(1 to:11) in:[:x | Amb try:(1 to:x) in:[:y | Amb try:(1 to:11) in:[:z | (x squared + y squared = z squared) ifTrue:[ {x . y . z} ]. ]]]].

 tryAll: valuesCollection in: aBlock

try each set of values in aBlock;
aBlock's number of args must be the number of elements in valuesCollection

Usage example(s):

Amb tryAll:#( (a b c) (d e f) (g h i) ) in:[:a :b :c | Transcript showCR: e'trying {{a . b . c}}'. nil. ]

Usage example(s):

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} ] ]

 until: questionBlock in: aBlock

compute solutions, asking if more solutions are to be searched
via questionBlock (gets the found solution as arg)

Usage example(s):

Amb until:[:solution | (Dialog confirm: e'Found solution: {solution}\nSee more?') not ] in:[ 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} ]. ]]]]].

Private classes:

    FoundSolution

Examples:

    "/ find { s. e. n. d. m. o. r. y.}
    "/ such that:
    "/       send
    "/    +  more
    "/    -------
    "/    = money

      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 }
            ].
       ]]]]]]]]]]]]]]].

      Amb try:#(1 2 3)   in:[:x |
      Amb try:#(7 6 4 5) in:[:y |
            x*y = 8 ifTrue:[ 
                {x . y} transcribeCR
            ]]]

      Amb try:#(1 2 3)   in:[:x |
      Amb try:#(7 6 4 5) in:[:y |
            x*y = 8 ifTrue:[ 
                {x . y} transcribeCR
            ]]]