Mercurial > repo

comparison interps/c-intercal/pit/tests/permute.doc @ 996:859f9b4339e6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
<Gregor> tar xf egobot.tar.xz
author HackBot
date Sun, 09 Dec 2012 19:30:08 +0000
parents
children
comparison
equal deleted inserted replaced
995:6883f5911eb7 996:859f9b4339e6
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).