|
996
|
1 <HTML>
|
|
|
2 <HEAD>
|
|
|
3 <TITLE>CLC-INTERCAL Reference</TITLE>
|
|
|
4 </HEAD>
|
|
|
5 <BODY>
|
|
|
6 <H1>CLC-INTERCAL Reference</H1>
|
|
|
7 <H2>... Quantum INTERCAL</H2>
|
|
|
8
|
|
|
9 <P>
|
|
|
10 Table of contents:
|
|
|
11 <UL>
|
|
|
12 <LI><A HREF="index.html">Parent directory</A>
|
|
|
13 <LI><A HREF="#introduction">Introduction - quantum computing</A>
|
|
|
14 <LI><A HREF="#intercal">Quantum INTERCAL</A>
|
|
|
15 <LI><A HREF="#emulator">Emulation on classical computers</A>
|
|
|
16 </UL>
|
|
|
17 </P>
|
|
|
18
|
|
|
19 <H2><A NAME="introduction">Introduction - quantum computing</A></H2>
|
|
|
20
|
|
|
21 <P>
|
|
|
22 A quantum computer differs from a classical computer because it allows
|
|
|
23 binary values to be "0" and "1" at the same time. At present, quantum
|
|
|
24 computers are not generally available, but this does not mean that you
|
|
|
25 cannot develop programs for them. It just means that as soon as they
|
|
|
26 will be available, you'll have the software for them. And INTERCAL will
|
|
|
27 be the first language available for them.
|
|
|
28 </P>
|
|
|
29
|
|
|
30 <P>
|
|
|
31 A quantum computer will usually have a limited number of quantum bits
|
|
|
32 (binary values), the rest being classical, one-valued, bits. When a
|
|
|
33 program executes on a quantum computer, some of its data can have multiple
|
|
|
34 values because it includes quantum bits, but most of the data will just
|
|
|
35 have one value.
|
|
|
36 </P>
|
|
|
37
|
|
|
38 <P>
|
|
|
39 Here's a simple example: an equation (depending on a
|
|
|
40 parameter) admits a large number of solutions, say sixtyfour. A program
|
|
|
41 determines whether one of these solution falls between 0 and 1, and prints
|
|
|
42 this solution. If there are several solutions between 0 and 1, it is
|
|
|
43 enough to print one of them. To complicate the matters further, somebody
|
|
|
44 has written algorithms to obtain the 64 solutions. However, they are
|
|
|
45 all different from each other and very time-consuming.
|
|
|
46 </P>
|
|
|
47
|
|
|
48 <P>
|
|
|
49 A classical program would compute the first solution, check if it is between
|
|
|
50 0 and 1, if it is print it and stop, otherwise compute the second one etc.
|
|
|
51 The worst case is to compute all 64 solutions. The average can be as low as
|
|
|
52 computing 32 of them, but could be more than that, depending on how often a
|
|
|
53 value of the parameters causes all solutions to be outside the interval
|
|
|
54 [0,1].
|
|
|
55 </P>
|
|
|
56
|
|
|
57 <P>
|
|
|
58 A quantum program would include a second parameter: the index of the
|
|
|
59 desired solution. For example, it could store pointers to the code to
|
|
|
60 compute each solutions in an array, and look it up using this index. Then
|
|
|
61 execute it and check if the solution is between 0 and 1. If we could know
|
|
|
62 in advance which is the value to assign to this index, the program would
|
|
|
63 be 32 to 64 times faster than the classical one. And here's how to do it:
|
|
|
64 the index can be stored in a 6 bit register. Make that 6 quantum bits, so
|
|
|
65 each one of them can be symultaneously 0 and 1. As a result, the computer
|
|
|
66 would symultaneously compute 64 solutions for the price of 1.
|
|
|
67 </P>
|
|
|
68
|
|
|
69 <H2><A NAME="intercal">Quantum INTERCAL</A></H2>
|
|
|
70
|
|
|
71 <P>
|
|
|
72 Quantum INTERCAL lets the programmer store the IGNORE status of a register.
|
|
|
73 and the ABSTAIN status of a statement in a quantum bit. Examples:
|
|
|
74 <PRE>
|
|
|
75 PLEASE ABSTAIN FROM (1) WHILE REINSTATING IT
|
|
|
76 DO IGNORE .1 WHILE REMEMBERING IT
|
|
|
77 DO REMEMBER .1 + .2 WHILE IGNORING THEM
|
|
|
78 PLEASE REINSTATE COMING FROM + NEXTING WHILE ABSTAINING FROM THEM
|
|
|
79 </PRE>
|
|
|
80 These will assign both values (IGNORE/REMEMBER and ABSTAIN/REINSTATE) to
|
|
|
81 the appropriate bit. As a result of this, the program might continue executing
|
|
|
82 completely different things, for example:
|
|
|
83 <PRE>
|
|
|
84 DO REMEMBER .1
|
|
|
85 DO .1 <- #0
|
|
|
86 DO IGNORE .1 WHILE REMEMBERING IT
|
|
|
87 (15) DO .1 <- #15
|
|
|
88 PLEASE REMEMBER .1
|
|
|
89 DO READ OUT .2
|
|
|
90 DO GIVE UP
|
|
|
91
|
|
|
92 PLEASE COME FROM .1
|
|
|
93 DO READ OUT .3
|
|
|
94 DO GIVE UP
|
|
|
95 </PRE>
|
|
|
96 Will the program READ OUT .2 or .3? Both! after executing the line with label
|
|
|
97 (15), the value of .1 will be both #15 and #0 (because the register is being
|
|
|
98 IGNOREd and REMEMBERed at the same time). Which means that the program will
|
|
|
99 continue with the next instruction (because .1 is #0) but also continue after
|
|
|
100 the COME FROM (because .1 is #15).
|
|
|
101 </P>
|
|
|
102
|
|
|
103 <P>
|
|
|
104 One point to note: the program READs OUT both .2 and .3, but we do
|
|
|
105 not know in which order. The two READ OUT statements cannot be executed at
|
|
|
106 the same time (because they lock the standard output while they are executed),
|
|
|
107 but there is nothing in the program which decides who goes first. If it is
|
|
|
108 important, you can do something like checking the value of a non-quantum
|
|
|
109 variable and have one of the two potential execution path modifying it when
|
|
|
110 the other one waits for the modification. For example:
|
|
|
111 <PRE>
|
|
|
112 DO REMEMBER .1 + .4
|
|
|
113 DO .1 <- #0
|
|
|
114 DO .4 <- #16
|
|
|
115 DO IGNORE .1 WHILE REMEMBERING IT
|
|
|
116 (15) DO .1 <- #15
|
|
|
117 PLEASE REMEMBER .1
|
|
|
118 DO READ OUT .2
|
|
|
119 DO .4 <- #0
|
|
|
120 DO GIVE UP
|
|
|
121
|
|
|
122 PLEASE COME FROM .1
|
|
|
123 (16) DO .1 <- .4
|
|
|
124 DO READ OUT .3
|
|
|
125 DO GIVE UP
|
|
|
126 </PRE>
|
|
|
127 What happens now is that the program always READs OUT .2 and then .3 - this
|
|
|
128 is because initially .4 is #16, so when the line with label (16) is reached,
|
|
|
129 if .4 is still #16 the program will loop. Meanwhile, the program is also
|
|
|
130 executing the READ OUT .2 and eventually will reset .4 to #4 - at which
|
|
|
131 point it will get out of the loop and READ OUT .3
|
|
|
132 </P>
|
|
|
133
|
|
|
134 <P>
|
|
|
135 Beginning with CLC-INTERCAL 0.05, there are two new statements which can
|
|
|
136 generate quantum bits: CONVERT and SWAP. These allow a program to modify
|
|
|
137 its own semantics at runtime, while leaving it unchanged. The syntax is
|
|
|
138 something like:
|
|
|
139 <PRE>
|
|
|
140 DO CONVERT CONVERT STATEMENT TO STATEMENT TO
|
|
|
141 SWAP STATEMENT AND STATEMENT
|
|
|
142 WHILE LEAVING IT UNCHANGED
|
|
|
143 </PRE>
|
|
|
144 This means that next time the program executes a CONVERT, it will
|
|
|
145 (symultaneously) execute a CONVERT (as if this CONVERT had not been
|
|
|
146 executed) and a SWAP (because this CONVERT has also been executed).
|
|
|
147 A similar abomination can be obtained with SWAP:
|
|
|
148 </P>
|
|
|
149
|
|
|
150 <PRE>
|
|
|
151 DO SWAP STASH REGISTER LIST AND IGNORE REGISTER LIST
|
|
|
152 WHILE LEAVING THEM UNCHANGED
|
|
|
153 </PRE>
|
|
|
154
|
|
|
155 <P>
|
|
|
156 What happens next time you STASH something away? Well, it will STASH
|
|
|
157 it as normal, but it will also IGNORE it. Do not confuse the above with:
|
|
|
158 <PRE>
|
|
|
159 DO SWAP STASH REGISTER LIST AND IGNORE REGISTER LIST
|
|
|
160 WHILE REMEMBERING IT
|
|
|
161 </PRE>
|
|
|
162 which is a classical SWAP, which happens to have a quantum IGNORE as
|
|
|
163 one of its arguments.
|
|
|
164 </P>
|
|
|
165
|
|
|
166 <P>
|
|
|
167 CLC-INTERCAL 1.-94.-4 and newer allows any statement to be made quantum
|
|
|
168 statements, with the exception of comments and READ OUT. This is
|
|
|
169 actually implemented by letting the statement run to completion, and
|
|
|
170 then undoing its effects while not undoing them. In most cases this
|
|
|
171 is the same as executing the statements while not executing them,
|
|
|
172 however READ OUT cannot be handled this way - once the output has
|
|
|
173 been observed, we cannot undo that. WRITE IN is fine, as the undoing
|
|
|
174 just restores the registers to the values they had before the input,
|
|
|
175 it does not put the input back.
|
|
|
176 </P>
|
|
|
177
|
|
|
178 <H2><A NAME="emulator">Emulation on classical computers</A></H2>
|
|
|
179
|
|
|
180 <P>
|
|
|
181 As it can be seen from the above examples, a Quantum INTERCAL program
|
|
|
182 effectively behaves like a multithreaded program in which some of the
|
|
|
183 registers are shared between threads, while others are private to each
|
|
|
184 thread. The private registers are the ones which participate in a quantum
|
|
|
185 IGNORE or REMEMBER. More precisely, all registers start as shared. When
|
|
|
186 a quantum IGNORE or REMEMBER is executed, the program acts as if it
|
|
|
187 started another thread, with the variables involved copied to a private
|
|
|
188 area of each thread, but with complementary IGNORE state. If the quantum
|
|
|
189 statement was an ABSTAIN or REINSTATE, a similar thing happens except
|
|
|
190 that no registers are made private to the threads.
|
|
|
191 </P>
|
|
|
192
|
|
|
193 <P>
|
|
|
194 This picture suggests how to emulate this behaviour on a classical
|
|
|
195 computer, using threads. The compiler will notice that this emulation
|
|
|
196 is required if you compile a quantum program on a classical computer,
|
|
|
197 and automatically includes the necessary code.
|
|
|
198 </P>
|
|
|
199
|
|
|
200 </BODY>
|
|
|
201 </HTML>
|
|
|
202
|
