Courses/CS 460/Fall 2005/Notes for Oct 15 & 22
From CSWiki
References | Homework | Questions | Course notes | Oz notes
Contents |
[edit] Concurrent logic programming in Oz
[edit] Search, one solution at a time
declare
proc {Append Xs Ys Zs}
choice
Xs = nil
Ys = Zs
[] X Xr in
Xs = X | Xr
Zs = X | {Append Xr Ys}
end
end
proc {P S} X Y in {Append X Y [1 2 3 4 5 6]} S = sol(X Y) end
E = {New Search.object script(P)}
local X in {E next(X)} {Browse X} end
[edit] The zebra puzzle
Five men with different nationalities live in the first five houses of a street. There are only houses on one side of the street. The men practice distinct professions, and each of them has a favorite drink and a favorite animal, all of them different. The five houses are painted with different colors. The following facts are known:
- The Englishman lives in a red house.
- The Spaniard owns a dog.
- The Japanese is a painter.
- The Italian drinks tea.
- The Norwegian lives in the first house.
- The owner of the green house drinks coffee.
- The green house comes after the white one.
- The sculptor breeds snails.
- The diplomat lives in the yellow house.
- Milk is drunk in the third house.
- The Norwegian's house is next to the blue one.
- The violinist drinks juice.
- The fox is in the house next to that of the doctor.
- The horse is in the house next to that of the diplomat.
- The zebra is in the white house.
- One of the men drinks water.
Who lives where?
The following illustrates the set-up for the zebra puzzle.
The variable Nb is a record whose field names correspond to the various property values. The value of each field is a number 1 .. 5, which identifies which house has that property vaue.
Run this with Ozcar to watch some of the fields get instantiated.
local
proc {Adjacent X Y}
thread {Number.abs X - Y} = 1 end
end
proc {Zebra Nb}
Nationalities = [english spanish japanese italian norwegian]
Colors = [green red yellow blue white]
Professions = [painter diplomat violinist doctor sculptor]
Pets = [dog zebra fox snails horse]
Drinks = [juice water tea coffee milk]
Groups = [Nationalities Colors Professions Drinks Pets]
Properties = {FoldR Groups Append nil}
in
{MakeRecord neighborProperties Properties Nb}
Nb.english = Nb.red
Nb.spanish = Nb.dog
Nb.japanese = Nb.painter
Nb.italian = Nb.tea
Nb.norwegian = 1
Nb.green = Nb.coffee
thread Nb.green > Nb.white = true Nb.snails = yes end
Nb.sculptor = Nb.snails
Nb.diplomat = Nb.yellow
Nb.milk = 3
{Adjacent Nb.norwegian Nb.blue}
Nb.violinist = Nb.juice
{Adjacent Nb.fox Nb.doctor}
{Adjacent Nb.horse Nb.diplomat}
Nb.zebra = Nb.white
end
Nb
in
{Zebra Nb}
{Browse Nb}
end
[edit] Delete/3
local proc {Delete X Xs XRest} Head Tail in Xs = Head | Tail choice Head = X XRest = Tail [] NewTail in XRest = Head | NewTail {Delete X Tail NewTail} end end in {Browse {SearchAll proc {$ Before} After1 After2 in Before = [_ _ _] {Delete 1 Before After1} {Delete 2 After1 After2} {Delete 3 After2 _} /* The three Delete's may be replaced by any of the following. If you do this, the declarations of After1 and After2 are no longer needed. 1. {Delete 1 Before _} {Delete 2 Before _} {Delete 3 Before _} ----------------- 2. {Map [1 2 3] proc {$ X _} {Delete X Before _} end _} {ForAll [1 2 3] proc {$ X} {Delete X Before _} end} ----------------- 3. {FoldL [1 2 3] proc {$ List X NewList} {Delete X List NewList} end Before _} ----------------- 4. {FoldR [1 2 3] proc {$ X List NewList} {Delete X List NewList} end Before _} Note the different order of X and List in FoldL and FoldR */ end}} endProduces [[1 2 3] [1 3 2] [2 1 3] [3 1 2] [2 3 1] [3 2 1]]
[edit] PlaceDigits
Same as example in the preceding. Don't have to specify the digits.
local
proc {Delete X Xs XRest}
Head Tail NewTail in
Xs = Head | Tail
choice
Head = X
XRest = Tail
[] XRest = Head | NewTail
{Delete X Tail NewTail}
end
end
proc {PlaceDigits Xs} {PlaceDigits2 {Length Xs} Xs} end
proc {PlaceDigits2 N Xs}
if N == 0 then skip %We're done
else
Xr in
{Delete N Xs Xr}
{PlaceDigits2 N-1 Xr}
end
end
in
{Browse {SearchAll
proc {$ Ans} Ans = [_ _ _] {PlaceDigits Ans} end}}
end
[edit] PlaceDigitsInFields
proc {PlaceDigitsInFields PropertyGroups Nb}
{Map PropertyGroups proc {$ Group _} {PlaceDigits {GetFields Nb Group}} end _}
end
[edit] Zebra solution
local
proc {Adjacent X Y}
choice
X = 1 Y = 2
[] X = 2 Y = 3
[] X = 3 Y = 4
[] X = 4 Y = 5
[] X = 2 Y = 1
[] X = 3 Y = 2
[] X = 4 Y = 3
[] X = 5 Y = 4
end
end
proc {Delete X Xs XRest}
Head Tail in
Xs = Head | Tail
choice
Head = X
XRest = Tail
[] NewTail in
XRest = Head | NewTail
{Delete X Tail NewTail}
end
end
proc {GetFields Record FieldNames Fields}
{Map
FieldNames
proc {$ Field Value} Value = Record.Field end Fields}
end
proc {PlaceDigits Xs} {PlaceDigits2 {Length Xs} Xs} end
proc {PlaceDigits2 N Xs}
if N == 0 then Xs = nil %We're done
else
Xr in
{Delete N Xs Xr}
{PlaceDigits2 N-1 Xr}
end
end
proc {PlaceDigitsInFields PropertyGroups Nb}
{ForAll
PropertyGroups
proc {$ Group} {PlaceDigits {GetFields Nb Group}} end}
end
fun {Zebra}
Nationalities = [english spanish japanese italian norwegian]
Colors = [green red yellow blue white]
Professions = [painter diplomat violinist doctor sculptor]
Pets = [dog zebra fox snails horse]
Drinks = [juice water tea coffee milk]
PropertyGroups = [Nationalities Colors Professions Pets Drinks]
Properties = {FoldR PropertyGroups Append nil}
Nb = {MakeRecord neighborProperties Properties}
in
{PlaceDigits {GetFields Nb Colors}}
Nb.english = Nb.red
Nb.spanish = Nb.dog
Nb.japanese = Nb.painter
Nb.italian = Nb.tea
Nb.norwegian = 1
Nb.green = Nb.coffee
Nb.green > Nb.white = true
Nb.sculptor = Nb.snails
Nb.diplomat = Nb.yellow
Nb.milk = 3
{Adjacent Nb.norwegian Nb.blue}
Nb.violinist = Nb.juice
{Adjacent Nb.fox Nb.doctor}
{Adjacent Nb.horse Nb.diplomat}
Nb.zebra = Nb.white
{PlaceDigitsInFields PropertyGroups Nb}
Nb
end
in
{Browse {SearchAll Zebra}}
end
[edit] Second Zebra solution
In this solution, the list is a list of records:
Nb = [neighbor(color:white drink:juice ...) neighbor(color:blue drink:tea ...) ...]
local
proc {Adjacent X Y List}
choice
{Append _ (X | Y | _) List}
[] {Append _ (Y | X | _) List}
end
end
proc {Append Xs Ys Zs}
choice
Xs = nil Ys = Zs
[] Xr X in
Xs = X | Xr
Zs = X | {Append Xr Ys}
end
end
proc {IsANeighbor Props Ns} {IsMember {Neighbor Props} Ns} end
proc {IsMember X Xs}
H Tail in
Xs = H | Tail
choice H = X [] {IsMember X Tail} end
end
proc {MakeNeighbor N}
{Record.make neighbor [color drink nationality pet profession] N}
end
% Neighbor N has properties Properties, which is a list
% of the form: [prop1#value1 prop2#value2 ...]
proc {Neighbor Properties N}
{MakeNeighbor N}
{ForAll
Properties
% Apparently anonymous function parameters can be structures.
proc {$ Property#Value} N.Property = Value end}
end
proc {Zebra Nb}
% The norwegian and the milk drinker are in positions 1 and 3 rspectively.
Nb = [{Neighbor [nationality#norwegian]}
{MakeNeighbor}
{Neighbor [drink#milk]}
{MakeNeighbor}
{MakeNeighbor}]
{IsANeighbor [nationality#english color#red] Nb}
{IsANeighbor [nationality#spanish pet#dog] Nb}
{IsANeighbor [nationality#japanese profession#painter] Nb}
{IsANeighbor [nationality#italian drink#tea] Nb}
{IsANeighbor [color#green drink#coffee] Nb}
% The green house comes after the white house.
local Before in
{Append Before ({Neighbor [color#green]}|_) Nb}
{IsANeighbor [color#white] Before}
end
{IsANeighbor [profession#sculptor pet#snails] Nb}
{IsANeighbor [profession#diplomat color#yellow] Nb}
{Adjacent {Neighbor [nationality#norwegian]} {Neighbor [color#blue]} Nb}
{IsANeighbor [profession#violinist drink#juice] Nb}
{Adjacent {Neighbor [pet#fox]} {Neighbor [profession#doctor]} Nb}
{Adjacent {Neighbor [pet#horse]} {Neighbor [profession#diplomat]} Nb}
{IsANeighbor [pet#zebra color#white] Nb}
{IsANeighbor [drink#water] Nb}
end
in
{Browse {SearchAll Zebra}}
end
[edit] Useful predicates
These weren't needed for the Zebra problem, but they may be useful
%% Ensure that all the record fields are instantiated.
proc {AllDetermined Ns} {ForAll Ns proc {$ N} {IsDetermined N} end} end
% Succeed if each of the Neighbors in Ns has property values
% that no other Neighbor has. Should really do this one property
% at a time. In this case all property values are distinct.
proc {AllDistinct Ns}
{FoldR
Ns
% Accumulate the values of all the properties.
% If any appear twice, fail. (The nil's ensure failure.)
fun {$ N OldPVs}
% {Record.toList N} returns a list of the values of the fields in record N.
PVs = {Record.toList N} in
% Partition the PVs into those that have and have not appeared
% before, i.e., in OldPVs.
% The final two arguments (nil and PVs) are what the input PVs are
% partitioned into. In other words, all PVs fail the List.member test.
{List.partition PVs fun {$ PV} {List.member PV OldPVs} end nil PVs}
{Append PVs OldPVs}
end
nil
_}
end
% Ensure that all of N's fields are instantiated
proc {IsDetermined N}
{IsMember N.color [green red yellow blue white]}
{IsMember N.drink [juice water tea coffee milk] }
{IsMember N.nationality [english spanish japanese italian norwegian]}
{IsMember N.pet [dog zebra fox snails horse]}
{IsMember N.profession [painter diplomat violinist doctor sculptor]}
end
