Visualizing Solutions with Viewers - Complang

Visualizing Solutions with Viewers
Ulrich Neumerkel, Christoph Rettig, Christian Schallhart
Institut für Computersprachen
Technische Universität Wien
A-1040 Wien, Austria
[email protected]
Abstract
Visualization can be a powerful aid for learning a programming language. It may be
used to reinforce central language concepts. In the context of Prolog and CLP-languages,
however, most approaches to visualization aim at procedural aspects. Instead of explaining
what a relation describes, visualization is used to animate procedural machinery. In this
paper we present approaches to visualizing aspects of Prolog programs that try to avoid
unnecessary and irritating procedural details. Answer substitutions are visualized with
the help of so called viewers. Some procedural aspects are explained with animations.
The viewers have been integrated into a side-effect free programming environment and
are used in introductory Prolog and CLP courses. The didactical impact of our approaches
is discussed.
1
Introduction
Common approaches to program visualization focus on visualizing a program’s state and animating its execution mechanism. While program animation is very compelling, this approach
may cover the essential declarative and procedural aspects of a program because of the rather
complex representations of Prolog’s state. In an introductory Prolog programming course at
TU-Wien a different path has been chosen for teaching and visualizing Prolog focusing on
the declarative side of the language. Two new elements facilitate teaching declarative programming with Prolog. First, a new programming methodology has been developed whose
main part consists of several reading techniques that explain specific properties of a Prolog program. In this manner both declarative and procedural aspects are covered without
using the commonly used notions of proof trees and execution traces. Second, a side-effect
free programming environment helps to avoid many frequently encountered errors, facilitates
a specification oriented style of programming and eases communication with the lecturer.
In this paper we discuss the integration of visualization devices into the programming environment. Our approach tries to separate the declarative and procedural concerns during
visualization. We therefore focus on visualizing particular answer substitutions in a side-effect
free manner.
Contents. After presenting the programming environment GUPU in Section 2, the notion
of viewers is discussed in Sect. 3. Some problem specific viewers are shown in Sect. 4. The
1
problem of visualizing Prolog’s chronological backtracking is addressed in Section 5. Finally
animations of labeling strategies for CLP(FD) programs are discussed.
2
The programming environment GUPU
The programming environment GUPU (Gesprächsunterstützende Programmierübungsumgebung, conversation supporting programming course environment) has been developed to
realize Prolog programming courses. GUPU has been used since Spring 1992 for Prolog programming courses at TU-Wien. It has been continually developed since then. The major
objective of GUPU was to provide a side-effect free programming environment.
Figure 1: GUPU’s screen
GUPU’s screen consists of two EMACS-windows (Fig. 1). The left contains examples
to be solved. The right contains help (read-only) texts containing links to further texts.
All interaction is performed through these two windows. State oriented notions like files or
top-level shells are absent. The whole state (i.e. the text) is visible in the left window.
Simple interaction. GUPU’s metaphor is very simple: The left window is like a paper
sheet containing at first only example statements. The student adds more text and saves it
2
from time to time. Comments from the system or lecturer are written back into the text.
When saving an example the following actions are performed. The example is saved,
checked w.r.t. syntactic restrictions, compiled, loaded, and assertions are tested. It is not
possible to save an example without seeing the comments from the system on it. In particular
all assertions (test goals) are tested. “Last minute changes” that are no more tested cannot
happen. Inconsistency between the visible text and the Prolog system is kept to the minimum.
At any time only a single example might be modified.
Error messages are inserted into the program text as lines beginning with an exclamation
mark. These lines are regular text. As long as they starts with an exclamation mark, they
are deleted upon the next saving and are generated anew.
← child of(joseph II Parent).
! child of(joseph II<<*>>Parent).
! Argument list incomplete: A , is missing.
Assertions. Lines beginning with an arrow are called assertions. They serve as test cases
for a program and allow to write down test cases with ease prior to implementing the actual
program. It is therefore possible to specify a relation before its actual implementation. Simple
assertions (like ← true.) should succeed within a limited amount of time. Goals that take
$
longer, but still succeed, are annotated with ←. Those that do not succeed because of an
∞
$
∞
infinite loop are marked with ←. Goals that should fail are annotated with 6←, ←,
6
and ←
6
respectively. Every time an example is saved assertions are tested. In case an assertion does
not behave as specified, an error message is issued.
Interactive queries. The only means to interact with the system beyond the automatic
testing upon saving is to ask queries. All assertions can also be used as queries. By clicking
on the arrow of the assertion, answer substitutions are displayed. Redundant solutions are
labeled separately. The comment ↑↑Redundant below is a link to a help text about redundant
solutions.
← child of(joseph II, Parent).
@@ % Parent = maria theresia.
@@ % Parent = maria theresia. % ↑↑Redundant
@@ % Parent = franz I.
@@ %% 3 solutions found, 1 thereof redundant.
Solutions are displayed in chunks of at most five at a time. Also very large sequences —in particular infinite sequences— can be displayed with ease. The traditional Prolog top-level shell
requires one to type the two keys ; RETURN for each solution which is somewhat tedious and
causes most students to stick with the first solution. But many errors in predicates show up
only “on backtracking”. These errors are much more difficult to find. Seeing several solutions
helps to detect these errors. Similar to error messages the inserted answer substitutions are
regular text lines beginning with the @-sign. Upon the next saving they are deleted.
3
3
Elementary viewers
Answer substitutions are the only way to get some response from pure Prolog. Often this
is taken as a pretext to introduce impure features and side-effects. There are however approaches similar to pure functional languages to provide side-effects in a pure logic language.
Current state of the art in providing I/O in a pure logic language (like Mercury [1]) restricts
nondeterminism in I/O-related predicates. Modes and other procedural notions have to be
taken into account. This approach is not desirable within the focus of our course. Some
less universal primitives have been implemented. There is no direct output, but (the terms
of) answer substitutions can be viewed with some viewers. There is no input except for the
program text. While this is a serious restriction, our limited interaction allows to integrate
complex programs like the partial evaluator Mixtus[4].
To use a viewer for answer substitutions a Goal is annotated
with <<< as follows: ← Viewer <<< Goal. The most elemen← text(Cs) <<< Query.
tary viewers display ASCII-text, Postscript, and html. All
← postscript(Cs) <<< Query. of them expect a string (a ground list of characters codes) as
argument. An additional text window, Postscript viewer, or
← html(Cs) <<< Query.
Web-Browser displays the string accordingly.
With the help of viewers the error prone printing procedures of Prolog are replaced by grammars, reinforcing the notion that grammars can also be used to describe the actual output as
indented text or simple “ASCII-graphics”.
Predicate hpuzzle/1 describes the solutions to a simple puzzle
← hpuzzle(Xs).
$
problem. In front of each predicate several assertions are
6 hpuzzle(Xs), false.
←
hpuzzle(Zs) ←
given which are tested each time the program is saved. With
hpuzzlerel(Zs),
assertions of the form 6← Query, false. it is stated that the
labeling zs([], Zs).
particular Query terminates universally.
In most cases the actual solution of a predicate must be
← hpuzzlerel(Xs).
converted with an additional predicate into the string repre← hpuzzlerel([2,7,3,4,5,1,6]).
sentation. Seeing the string as an answer substitution (and
6← hpuzzlerel([1,3,7,6,2,4,5]).
therefore a list of integers) is not very useful. If the predicate
6← hpuzzlerel(Xs), false.
hpuzzlerel(Zs) ←
responsible for text representation is determinate (describing
Zs = [A,B,C,D,E,F,G],
a single string for a particular solution) it can be wrapped
domain zs(1..7,Zs),
into the viewer as follows.
all different(Zs),
A+B+C #= H,
B+D+F #= H,
E+F+G #= H.
← text(Cs↑solution text(S, Cs)) <<< pred(S).
In this manner only the answer substitutions for S are displayed.
← text(Cs) <<< hpuzzle(Zs), phrase(hpuzzletext(Zs),Cs).
@@ % Cs = [49,32, ... ,10], Zs = [1,3,7,6,4,2,5].
← text(Cs↑phrase(hpuzzletext(Zs),Cs)) <<< hpuzzle(Zs).
@@ % Zs = [1,3,7,6,4,2,5]. % No answer substitution for Cs
hpuzzletext([A,B,C,D,E,F,G]) −→
( digit(A),
”ÃÃÃÃÔ,
digit(E), nl ),
(
”|”,
”ÃÃÃÃÔ,
”|”, nl ),
( digit(B),
”− −”, digit(D), ”− −”,
digit(F), nl ),
(
”|”,
”ÃÃÃÃÔ,
”|”, nl ),
( digit(C),
”ÃÃÃÃÔ,
digit(G), nl ).
4
1
4
|
|
3--6--2
|
|
7
5
4
Problem specific viewers
Schalli’s Spielbrett
Based on the elementary viewers more complex viewers are predefined for specific problems.
The major advantage of problem specific viewers is the immediate visual feedback they provide
about the accurateness of a solution. Each solution displays a corresponding picture.
The viewer ← europa(Path) <<< Query. shows the list of cities in a path through the
European railway network (left picture). By inspecting the actual railway map it is easy to
see whether a path leads directly from one city to another. Queens on a checkerboard are
displayed by marking all threatened fields (middle picture). It is therefore obvious whether or
not the queens threaten each other. As long as the field of a queen remains white, the queen
is not threatened. A sequence of left and right turns of a line is described by a list of ls and
rs. E.g., a simple square is thus ← lrs(LRs) <<< LRs = ”lll”. The folding of a paper strip can
be described with a grammar, resulting in the well known dragon curve.
... in Bearbeitung.
Fertig!
5
... in Bearbeitung.
Fertig!
Visualizing backtracking
Backtracking is one of the more sensible areas of Prolog. Prolog’s actual control mechanism
is divided into two orthogonal controls, AND- and OR- control, which are tightly interlaced
during execution. Visualizing the actual control mechanism as done by procedural debuggers
seems to lead to more confusion than insight. In particular, we have the impression from
earlier courses that debuggers increase the unnecessary and incorrect usage of cuts. Instead
of avoiding the alternate clause form the beginning (either by shallow cuts or better means)
cuts are placed at the point where the failure occurs that leads to the undesirable alternative.
It seems that procedural tracers suggest doing this error because right before displaying the
undesirable alternative the place where failure occurs is displayed. Such deep cuts often lead
to programs lacking steadfastness.
On the other hand understanding the rôle of goal ordering is essential to understanding
efficiency considerations. An appropriate metaphor was therefore required which is able
to express the idea of chronological backtracking without going into the details of Prolog’s
execution. In a first attempt clocks and odometers were considered, because they seem to be
an obvious metaphor for “chrono-logical” backtracking. However, their visualization did not
lead to satisfactory results. On the one hand the examples were difficult to motivate, on the
other hand the uniformity of the data (digits) makes places of digits difficult to distinguish.
5
ft
pttp zs
saf
tp t
sncish
xp t
xr
zrb s
BS
zrtb h
bSlc
ay u zrw
c t
en
t
ft
g
i
h
brch sachl af
gse nr der bSrc
l
brcbk
hsoe er C
Sch
d
d
b
r
b
n
huie
cShcrhm
brdst
ivner
brfst
cSlchn
rft
bt
unster
lo
Schr
cr
crg sam
sal
umt
mi
rgk
ch
Schw
D
o
e
un
miss
rl
chs
rm
cht
Sp
vollch dr
na
rn
ck
Spl
E
nvoebne
drnd
n
nvoierd
drnss usanm
St
F
g
drnt s
nwee er fSk
drpts t
owbe cghst fT tr
r
f
r
ge
pf
n G
eoie frfr
th
frts
gtrk
huenig
grsdc
t
gr h
grts skt
grtz
hs
khe
it
Georg Phillip Harsdörffer realized
a Lullian machine to describe German words [2]. His device consists of five concentric rings with
h
hscl pm
hs sn
hs tr ikneit
word constituents like prefixes, cenhs s
gtzn
ht
r
e
r
euu htht
end r gV
tral letters, and suffixes. By turni
h
kts
ow dene
W
H
i
kttk
b
ow l t
ltbz
IX
inum
th
ing the rings all word combinations
swaom
xh
lc
t
Y
K
r
i
tk
sze
x
lc
hre Z l
z
ld
szownisdce K
can be seen; many of which bezt
ldt
Zw
zu ber Kn
ue
zw
lg
ing only remotely related to GerAb
ver
A
Kr
ia ll
thum
bar
b
bb
lm
Anter L
un
B
bd
lp
man words. The constellation on
uam
nt
bs
ls
bl
M
bstch
ls
uanus
br
N
btt
ls
vaoulf
the right shows the inexistent word
ebtar
C
O
c
l
l
t
vboe
lcthz
chr
P
vboe n
chs
m
“verkrillbar”. Harsdörffer’s device
ry
iaee m
pclf
ch
ck bt
m
pcrf
l
d bd
m
shows in an obvious manner the todsd bs ert
m
d
m
dtmtf
m
s
tality of all possible combinations
of word constituents. In contrast to
the usual visualizations of alternate
solutions via proof trees the complete mechanism is visible. This
representation can now be used to
explain the systematic enumeration
of solutions via Prolog’s chronologCHRISTOPHVS ME RECONSTRVXIT
ical backtracking.
The possible words of the five rings can be described with the predicate wordconstituents/1.
Prolog enumerates solutions to this predicate in chronological order. For every solution the
corresponding constellation of the rings is displayed in the viewer. The viewer itself is completely side-effect free. It simply displays a particular solution. However, by inspecting the
sequence of solutions, we get the intended coincidental impression that the rings are rotating.
h
k eliyc
rmc db
rm t d
rmdbf bs
rm
SKpr l
rmftd
SLp
ueu rmgfgm
iesych
rm k
f
SMt
ainu
rml p
rmmpf
SNtr
bloes
rmns
bmeiyt
O
T
mtd
rn
dmaiss
P
th
ht
n s ic
rn
isch
h
dnarch tr
ncst
rn
pf
nck
rp
en
nebch
dur
pfl ai rpf
tz
nd
nieder
ein
ndt
rr
pfn
nf
rs
nect hst V
en
ichtg
nfch
rs
p
W
l lin
fr
eor
b
ngt
rs
pl
X
fouhe
rntgs
n
r
foobr
pr
Y
rntgzt
snn
gsae etn Zp
s
m
sncsh
t
i
a
q
Z
e
e snpsc leining
uw
sns h
AR
sn t
tn t
tp tz
ptsf h
nleiis
ns
ttpp s
ls
p t
tz
nis
sa
xp
r
xt
zrb s
BS
rb h
zt
n
bSlc
y
au
rc ht
zw
itge
m fft
brc
Sch
gsee nder br
scha
sa
rck
bb
hsoer r C
Schl
rd
bd
uenbe
hi
Scrhm
ch
rdt
bs
r
ve
in
rf
bst
Schn
cl
rft
bt
unter
los
Schr
cr
crg ung
sal
um
mit
rgk
ch
Schw eo chs
D
un
miss
rl
rm
cht
Sp
dr
voll
nach
rn
ck
Spl
vonen E
neb
drnd
sam
voed
ni
rns heit
ds
St
F
r
rns
dt
weg er fk
ne
Str
rp t
dts
owbe chst fr
T
frpf
ge
n G
rr
ff
oe
ei
th
ftrs
gtrk
unitg
ke
rs
gd
grs ch
grt kt
grt s
hs tz
he
in
it
h
lic
k is
m b
rc
m d
rd
t
mb bs
rd
m td
rf
SKpr l
m f
rf
mm
SLp
ueu rg
eyht
ic
mk
rg
f
M
St
ainu
mp
rl
mpf
rm
Nr
St
bloes
ms
rn
mity
be
O
T
mt
rnd
miss
da
P
th
n
rns
isch
ling
nach tr
dar
nch
rnst
pf
nck
rp
neben
durch
pfl a
tz
i rpf
nd
nieder
ein
ndt
rr
pfn
nf
rs
nechst V
ent
icht
nfl lein
rsch
pfr
W
ob
er
ng
rst
pl
X
ngs
rt
pr
Y
ngt
rtz
snn
Zps
ns
sc
linssg
ie sp
ae
qZuw
ns h ni
ns ch
ss
n t
st
tn t
p tz
th
tspf
lein
sc
ha
fft
AR
CHRISTOPHVS ME RECONSTRVXIT
→
h
hscl m
hsp n
it
hss r th
keum
hst
gtzn
t
hs
er
th
gVr
u ht
eu
nd
kts
wohie ener
W
H
tt
kk
owbid t
tz
lb
IX
m
in r
ba
ol
w
sa
x
lch
Y
K
r
zeit
se
xt
lck
e Kl
der
sch
Z
z
ld
zwi
son
zt
ldt
Zw
Kn
zu
ueber
zw
lg
Ab
ver
A
Kr
ia ll
thum
et
b
bb
lm
An
unter
B
L
bd
lp
ant
um
bs
ls
bl
M
bst
lsch
aus
un
br
N
bt
lst
aullf
vo
bar
er
C
O
c
lt
be
vo
ch
ltz
chr
P
vboe n
ch
m
ry
ae m
ie
pclf
chbt s
ck
m
pcrfl
d bd
m
et
d bs em
m
d sd
m
dtsmtf
m
enr
p
f pf
m
ff s
m
ft dt
m
g
m
ngk h es
em
pDfn
gs k
nc
r
pdfr
yau
gt
nc
g
h t
nd
E
dae r en pl
w
hl
nd
F
daeg dehr pr
w
hm
nf
fk
ps
hn haff
nfl
duierc
w
en t
hr
ng
ein er qu
wid
fr
hs
ngs
ent
wol
G
R
ht
ngt
k
er
zer
Sgk oe nn
kk
ns
fuer
zwische
es
lb ig
nsch
gn
Sc
fort
zu
lch
nst
gr
Sch
lck
nt
ge
Ab
ld
ntz
H hl
Sc
genge
A
pldt
I hm
ahner n Sc
lg
pf
hahfft
lic
ahuin t
K hn
Sc
ll
pp
s
lm
ei ps
oe
SKch
l
lp
pt
SKcn r
rls
hw
ls
rb
ls ch
rb
ig
lt ts ey
rc
rltcz h
ht
h
k eliyc
m b
rc
m d
rd
t
mb bs
rd
m td
rf
SKpr l
m f
rf
mm
SLp
ueu rg
ey h
isc
mk
rg
f
M
St
ainu
mp
rl
mpf
rm
Nr
St
bloes
ms
rn
mity
be
O
T
mt
rnd
miss
da
P
th
n
rns
isch
icht
nach tr
dar
nch
rnst
pf
nck
rp
neben
durch
pfl a
tz
i rpf
nd
nieder
ein
ndt
rr
pfn
nf
rs
nechst V
ent
icht
nfl ling
rsch
pfr
W
ob
er
ng
rst
pl
X
ngs
rt
pr
Y
ngt
rtz
snn
Zps
ns
sc
lining
ie sp
ae
qZuw
ns h le
ns ch
ss
n t
st
tn t
p tz
th
tspf
nleisin
s
AR
oher
fu
n
obrt
fo
gsae en
mt
h
k lic
m b
rc
m d
rd
t
mb bs
rd
m td
rf
SKpr
m
rf
l
mf m
SLp
ueu rg
ey
mk
rg
f
M
St
ainu
mp
rl
mpf
rm
Nr
St
bloes
ms
rn
mity
be
O
T
mt
rnd
miss
da
P
th
n
rns
isch
nach
dar
nch
rnst
pf
tr
nck
rp
neben
durch
pfl a
tz
i rpf
nd
nieder
ein
ndt
rr
pfn
nf
rs
nechst V
ent
nfl icht
rsch
pfr
W
ob
er
ng
rst
pl
X
ngs
rt
pr
Y
ngt
rtz
snn
Zps
ns
sc
ie sp
ae
qZuw
ns h ling
ns ch
ss
n t
st
tn t
p tz
th
tspf
lein
AR
oher
fu
n
obrt
fo
gsae en
mt
CHRISTOPHVS ME RECONSTRVXIT
→
h
hscl m
hsp n
hss r in
keit
hst
gtzn
t
hs
er
th
gVr
u ht
eu
nd
kts
wohie ener
W
H
tt
kk
owbid t
tz
lb
IX
m
in m
thu
ol
w
sa
x
lch
Y
K
r
zeit
se
xt
lck
e Kl
der
sch
Z
z
ld
zwi
son
zt
ldt
Zw
Kn
zu
ueber
zw
lg
Ab
ver
A
Kr
ia ll
thum
bar
b
bb
lm
An
unter
B
L
bd
lp
ant
um
bs
ls
bl
M
bst
lsch
aus
un
br
N
bt
lst
aullf
vo
bar
et
C
O
c
lt
be
vo
ch
ltz
chr
P
vboe n
ch
m
ry
ae m
ie
pclf
chbt s
ck
m
pcrfl
d bd
m
et
d bs er
m
d sd
m
dtsmtf
m
r
em
p
f pf
m
ff s
m
ft dt
m
g
m
ngk h en
em
pDfn
gs k
nc
r
pdfr
yau nc
gt
g
h t
nd
E
dae r en pl
w
hl
nd
F
daeg dehr pr
w
hm
nf
fk
ps
hn es
nfl
duierc
w
en
hr
ng
ein er qu
wid
fr
hs
ngs
ent
wol
G
R
ht
ngt
k
er
zer
Sgk oe nn
kk
ns
fuer
zwische
es
lb hafft
nsch
gn
Sc
fort
zu
lch
nst
gr
Sch
lck
nt
ge
Ab
ld
ntz
H hl
Sc
genge
A
pldt
I hm
ahner n Sc
lg
pf
hafft
ig
ahuin t
K hn
Sc
ll
pp
s
lm
ei ps
oe
SKch
l
lp
pt
SKcn r
rls
hw
ls
rb
ls ch
rb
lt ts liigch
rc
rltcz h
ht
er
p
f pf
m
ff s
m
ft dt
m
g
m
ngk h em
pDfn
gs k
nc
r
pdfr
yau nc
gt
g
h t
nd
E
dae r en pl
w
hl
nd
F
daeg dehr pr
w
hm
nf
fk
ps
hn en
nfl
duierc
w
hr
ng
ein er qu
wid
fr
hs
ngs
ent
wol
G
R
ht
ngt
k
nn
er
zer
Sgk oe ns
kk
fuer
zwische
lb es
nsch
gn
Sc
fort
zu
lch
nst
gr
Sch
lck
nt
ge
Ab
ld
ntz
H hl
Sc
genge
A
pldt
I hm
ahner n Sc
lg
pf
hafft
ahuin t
K hn
Sc
ll
pp
s
lm
ei ps
oe
SKch
l
lp
pt
SKcn r
rls
hw
ls
rb
ls ch
rb
lt ts ig
rc
rltcz h
ht
h
hscl m
hsp n
hss r keit
hst
gtzn
t
hs
er
th
gVr
u ht
eu
nd
kts
wohie ener
W
H
tt
kk
owbid t
tz
lb
IX
m
in
ol
w
sa
x
lch
Y
K
r
zeit
se
xt
lck
e Kl
der
sch
Z
z
ld
zwi
son
zt
ldt
Zw
Kn
zu
ueber
zw
lg
Ab
ver
A
Kr
ia ll
thum
b
bb
lm
An
unter
B
L
bd
lp
ant
um
bs
ls
bl
M
bst
lsch
aus
un
br
N
bt
lst
aullf
vo
bar
C
O
c
lt
be
vo
ch
ltz
chr
P
vboe n
ch
m
ry
ae m
ie
pclf
chbt s
ck
m
pcrfl
d bd
m
d bs et
m
d sd
m
dtsmtf
m
oher
fu
n
obrt
fo
gsae en
mt
ttpp s
s
p t
tz
nis
xp
r
xt
zrb s
BS
rb h
zt
n
bSlc
y
au
rc ht
zw
itge
fft
brc
Sch
gsee nder br
scha
rck
bb
hsoer r C
Schl
rd
bd
uenbe
hi
hm
r
Sc
ch
rdt
bs
ver
in
rf
bst
Schn
cl
rft
bt
unter
los
Schr
cr
crg sal
um
mit
rgk
Schw eo ch
D
un
miss
rl
chs
rm
cht
Sp
dr
voll
nach
rn
ck
Spl
vonen E
neb
drnd
voed
ni
rns sam
ds
St
F
r
rns
dt
weg er fk
ne
Str
rp t
dts
owbe chst fr
T
frp
ge
n G
rr f
oe ff
ei
th
ftrs
gtrk
rsch ung
gd
grs
grt kt
grt s
hs tz
he
it
t
ttpp s
saff
p t
tz
nish
sc
xp
r
xt
zrb s
BS
rb h
zt
n
bSlc
y
au
rc ht
zw
itge
l fft
brc
Sch
gsee nder br
scha
sa
rck
bb
hsoer r C
Schl
rd
bd
uenbe
hi
rhm
Sc
ch
rdt
bs
ver
in
rf
bst
Schn
cl
rft
bt
unter
los
Schr
cr
crg sam
sal
um
mit
rgk
ch
Schw eo chs
D
un
miss
rl
rm
cht
Sp
dr
voll
nach
rn
ck
Spl
vonen E
neb
drnd
sam
voed
ni
rns ung
ds
St
F
r
rns
dt
weg er fk
ne
Str
rp t
dts
owbe chst fr
T
frpf
ge
n G
rr
oe ff
ei
th
ftrs
gtrk
unitg
he
rs
gd
grs ch
grt kt
grt s
hs tz
khe
it
r
em
p
f f pf
m
f ts
m
f dt
m
g
m
n
ngk h enm
pDf
ngcs
pdfrr
yau ngct k
l
d
g
h
n
dae rgen pE r
w
nhdl t
dae dcher pF
w
nhfm
n esn
pfks
nhfl
duier
w
nhgr
ider qfru
ein
w
hs s
ng
enolt
w
G
R
ht
ngt
k
nn
er
zer
gk
S
e
o
kk
ns
fueisc
zw
r he Sc
es ft
lb h haf
nsc
gn
zfourt
lcht
ns
g
S
r
c
h
nlctk
geb
A
nldtz
SHchl
gen
A
pldt
g
ahne en SI chm
plgf
ahui rt
SKc
pllp ihgafft
h
n
s
n
e
o
K
S
ie plpplms
cl
t
SKcn hr
rls
hw
rls
rl bch
rl sbts liigch
lrtcz tch
ht
wordconstituents([C1,C2,C3,C4,C5]) ←
ring1(C1),
ring2(C2),
ring3(C3),
ring4(C4),
ring5(C5).
CHRISTOPHVS ME RECONSTRVXIT
← harsdörffer(Xs) <<< Xs = [ver,’Kr’,i,ll| ], wordconstituents(Xs).
@@ % Xs = [ver,’Kr’,i,ll,thum].
@@ % Xs = [ver,’Kr’,i,ll,bar].
@@ % Xs = [ver,’Kr’,i,ll,et].
@@ ? Further solutions with SPACE
The order of the goals in wordconstituents/1 directly affects the way how the rings are “rotating”. The ring of the last goal rotates fastest. Whereas the first ring is the slowest one.
In this manner it is possible to explain the essential properties of chronological backtracking
(and its weaknesses) without going into the details of Prolog’s machinery.
6
6
Visualizing labeling strategies
The viewers presented so far have visualized a particular answer substitution. For understanding some procedural aspects of constraint programs viewers for animating labeling strategies
have been realized.
Most CLP(FD)-programs are divided mainly
into two separate parts. In the first part variables, their ranges, and their specific relations are stated with the help of constraints.
The second part is used to obtain specific solutions in a nondeterminate manner by using labeling predicates. This structure separated the declarative and procedural aspects.
While the first part is responsible for the
correctness of solutions, the second part is
concerned with effectively finding them by
using a particular labeling strategy. The
major concern for labeling is therefore to
understand the effectiveness of a particular
strategy. Details of the actual labeling process are mainly independent from correctness
concerns. The simple generic viewer on the
right displays the number of variables bound
Schritte =
4687, freie Variable =
11 /
25
during labeling.
Generic viewers do not represent the actual labeling process very well. Therefore problem
specific viewers are provided. For magic squares the process of labeling is illustrated as
follows. The darker a field the fewer values are possible for a variable. A black field contains
an actual number. The font size of the number represents the time when that variable was
bound. Newer (more volatile) bindings are thus represented by smaller numbers. A naı̈ve
left-to-right labeling produces the following steps1 :
0
1 2 13 24 25
→
2
3
4
5
6
7
8
9
10
11
12
13
14
1 2 13 24 25
1 2 13 24 25
1 2 13 24 25
1 2 13 24 25
3
3 4
3 4
3 456
→
→
Implementation. Labeling
animations
are realized similar to the approach proposed
in [5]. Blocking implication is realized with
SICStus Prolog’s[3] blocked goals.
The
number of possible values for a variable is
obtained with reı̈fied constraints, that are
connected to a side-effect producing blocked
predicate. For each possible value of a
variable a separate reı̈fied constraint is used.
1
1
→
15
16
17
18
19
20
21
22
23
24
25
1 2 13 24 25
··· →
3 22 19 6 15
23 16 10 11 5
21
7
9
20
8
17
18
14
4
12
... ←
...,
E #\= N0 #⇔ B,
show element i j n(B, E, I,J, N),
... .
http://www.complang.tuwien.ac.at/ulrich/gupu/io-magic.html contains runnable Postscript animations
7
Our implementation of animated constraint solving is independent both of the internal
representations of the constraint system as well as the actual labeling predicates. However, the
disadvantages of our approach are very high memory requirements and imprecise visualization.
The number of auxiliary constraints required is proportional to the sum of all variable ranges.
In the case of magic squares each variable on the n×n square has n2 possible values. Therefore
at least n4 reı̈fied constraints and blocked goals are required. Further, our animations are
only an approximation of the actual constraint solving process, because actual constraints
and our auxiliary constraints for animation are scheduled in an implementation dependent
manner. Some unsuccessful propagations may therefore not be displayed at all.
7
Conclusion
In this paper we have presented approaches to visualize aspects of Prolog and CLP(FD) programs avoiding unnecessary detail of the actual procedural machinery. With the help of a new
methodology and programming environment GUPU many of the distractions and perplexions beginners face when exposed to Prolog are avoided but the deeper task — understanding
declarative programming — still remains a challenge. In fact, most students suffer from expectation failure. The usual approach to programming simply does not work with Prolog.
Understanding all the details of Prolog’s execution mechanism is not helpful at all. Unlearing
these common habits, appreciating a more specification driven approach to programming is
still a difficult task that can be supported with the help of appropriate visual metaphors.
Acknowledgements. The contribution of the tutors Markus Schordan, Wolfgang Faber,
Niko Neufeld, Walter Binder, and others has been very valuable. The picture of Harsdörffer’s
machine is from text machines http://berlin.icf.de/˜inscape/.
References
[1] Z. Somogyi, F. Henderson, Th. Conway, The Execution Algorithm of Mercury, an Efficient Purely Declarative Logic Programming Language. JLP 29(1-3): 17-64 (1996).
[2] G. Ph. Harsdörffer, Philosophische und Mathematische Erquickungsstunden, Nürnberg
(1651), reprinted Frankfurt/Main (1990). See http://berlin.icf.de/˜inscape/.
[3] Intelligent Systems Laboratory, SICStus Prolog User’s Manual, Swedish Institute of Computer Science (1997).
[4] D. Sahlin, The Mixtus Approach to Automatic Partial Evaluation of Full Prolog, NACLP
(1990).
[5] P. Van Hentenryck, V. Saraswat, Y. Deville, Design, Implementation, and Evaluations of
the Constraint Language cc(FD), in A. Podelski, Constraint Programming: Basics and
Trends, LNCS 910, (1994).
8