996
|
1 permute.i prints the permutations of the set {1,2,3,4,5,6}, using
|
|
2 backtracking (and therefore must be compiled with the -m compiler
|
|
3 option). The following is the program translated into a mix of Prolog
|
|
4 and C, with some INTERCAL operations (gets, stash, retrieve, giveup)
|
|
5 scattered throughout the program.
|
|
6
|
|
7 goal :- gets(.1, #0),
|
|
8 gennumber,
|
|
9 checklist,
|
|
10 gennumber,
|
|
11 checklist,
|
|
12 gennumber,
|
|
13 checklist,
|
|
14 gennumber,
|
|
15 checklist,
|
|
16 gennumber,
|
|
17 checklist,
|
|
18 gennumber,
|
|
19 checklist,
|
|
20 readout(.1),
|
|
21 retrieve(.1),
|
|
22 readout(.1),
|
|
23 retrieve(.1),
|
|
24 readout(.1),
|
|
25 retrieve(.1),
|
|
26 readout(.1),
|
|
27 retrieve(.1),
|
|
28 readout(.1),
|
|
29 retrieve(.1),
|
|
30 readout(.1),
|
|
31 readout(#30),
|
|
32 fail.
|
|
33 goal :- giveup.
|
|
34
|
|
35 gennumber :- stash(.1), gets(.1, #1).
|
|
36 gennumber :- stash(.1), gets(.1, #2).
|
|
37 gennumber :- stash(.1), gets(.1, #3).
|
|
38 gennumber :- stash(.1), gets(.1, #4).
|
|
39 gennumber :- stash(.1), gets(.1, #5).
|
|
40 gennumber :- stash(.1), gets(.1, #6).
|
|
41
|
|
42 checklist :- gets(.2, .1),
|
|
43 while(.1 != #0)
|
|
44 {
|
|
45 retrieve(.1),
|
|
46 if(.1 == .2) {!, fail.}
|
|
47 },
|
|
48 fail.
|
|
49 checklist.
|
|
50
|
|
51 The backtracking reverses all the stashing and retrieving that is
|
|
52 done, so that at the end of the program .1 is #0 again and there is no
|
|
53 stash on .1. The INTERCAL has a somewhat Prolog-like attitude: it
|
|
54 never uses GO BACK to remove a choicepoint except when GOING BACK to
|
|
55 an earlier choicepoint (just like Prolog). The checklist. at the end
|
|
56 of the pseudo-Prolog source is actually an attempt to replicate the
|
|
57 semantics of MAYBE COME FROM; MAYBE COME FROM...GO BACK continues as
|
|
58 if nothing had happened, except for leaving a stale choicepoint on the
|
|
59 stack (but the program runs GO BACK in a loop whenever there is a risk
|
|
60 of encountering a stale choicepoint on top of the stack), but MAYBE
|
|
61 COME FROM...GO AHEAD, GO BACK causes the line that was come from to
|
|
62 fail. (The GO AHEAD, GO BACK was translated as !, fail in the
|
|
63 pseudo-Prolog above, as it has a similar effect). The program clearly
|
|
64 shows that INTERCAL's variables are more general than Prolog's (you
|
|
65 can rebind a variable in INTERCAL, and the rebinding is undone on
|
|
66 backtracking), especially when stashes are taken into account. On the
|
|
67 other hand, the program couldn't work as written in C, because
|
|
68 checklist destroys all the information about the permutations so far!
|
|
69 (In both the Prolog source above and in the INTERCAL, this destruction
|
|
70 is always cancelled out by backtracking past it). This program
|
|
71 probably could be translated into Prolog, but there would be a lot
|
|
72 more passing-around of variables, and probably more predicates
|
|
73 involved (I think gets, stash, and retrieve might be possible in terms
|
|
74 of assert/retract). However, I think that the INTERCAL source is the
|
|
75 clearest available implementation of the exact program flow above.
|
|
76 Note also the way that I translated the if() and while() into
|
|
77 INTERCAL.
|
|
78
|
|
79 if(<1 or 2>==1) something
|
|
80 becomes
|
|
81 DO ABSTAIN <1 or 2> FROM (label)
|
|
82 DO REINSTATE (label)
|
|
83 (label) DO something AGAIN
|
|
84 which is the shortest way to do an if() statement in INTERCAL that I
|
|
85 have discovered (yes! ABSTAIN and REINSTATE have a purpose again!).
|
|
86
|
|
87 do {block} while(<0 or 1>) becomes
|
|
88
|
|
89 DO COME FROM <0 or 1>$label
|
|
90 most of block
|
|
91 (1$label) last statement of block
|
|
92
|
|
93 which is pretty clear when written like this, but amazingly confusing
|
|
94 to track in the INTERCAL, and also prevents the user using 0$label as
|
|
95 a line number, without any obvious clue to this effect in the source
|
|
96 code. while() can often be transformed into do..while(), and even in
|
|
97 situations where it can't, an extra COME FROM does the trick.
|
|
98
|
|
99 This program uses a large crosssection of INTERCAL control structures;
|
|
100 computed COME FROM, ordinary COME FROM, ABSTAIN/REINSTATE, AGAIN,
|
|
101 NEXT, and MAYBE/GO AHEAD/GO BACK are all used. Only ONCE (which is
|
|
102 implied in the program due to the abstention/reinstatement of an AGAIN
|
|
103 line) and IGNORE are left unused (at least until someone invents a new
|
|
104 even nastier control structure). Unusually, it only contains three
|
|
105 nontrivial expressions (those other than a single constant or a single
|
|
106 variable). |