CLC-INTERCAL Reference

... Quantum INTERCAL

Table of contents:

• Parent directory
• Introduction - quantum computing
• Quantum INTERCAL
• Emulation on classical computers

Introduction - quantum computing

A quantum computer differs from a classical computer because it allows binary values to be "0" and "1" at the same time. At present, quantum computers are not generally available, but this does not mean that you cannot develop programs for them. It just means that as soon as they will be available, you'll have the software for them. And INTERCAL will be the first language available for them.

A quantum computer will usually have a limited number of quantum bits (binary values), the rest being classical, one-valued, bits. When a program executes on a quantum computer, some of its data can have multiple values because it includes quantum bits, but most of the data will just have one value.

Here's a simple example: an equation (depending on a parameter) admits a large number of solutions, say sixtyfour. A program determines whether one of these solution falls between 0 and 1, and prints this solution. If there are several solutions between 0 and 1, it is enough to print one of them. To complicate the matters further, somebody has written algorithms to obtain the 64 solutions. However, they are all different from each other and very time-consuming.

A classical program would compute the first solution, check if it is between 0 and 1, if it is print it and stop, otherwise compute the second one etc. The worst case is to compute all 64 solutions. The average can be as low as computing 32 of them, but could be more than that, depending on how often a value of the parameters causes all solutions to be outside the interval [0,1].

A quantum program would include a second parameter: the index of the desired solution. For example, it could store pointers to the code to compute each solutions in an array, and look it up using this index. Then execute it and check if the solution is between 0 and 1. If we could know in advance which is the value to assign to this index, the program would be 32 to 64 times faster than the classical one. And here's how to do it: the index can be stored in a 6 bit register. Make that 6 quantum bits, so each one of them can be symultaneously 0 and 1. As a result, the computer would symultaneously compute 64 solutions for the price of 1.

Quantum INTERCAL

Quantum INTERCAL lets the programmer store the IGNORE status of a register. and the ABSTAIN status of a statement in a quantum bit. Examples:

	PLEASE ABSTAIN FROM (1) WHILE REINSTATING IT
	DO IGNORE .1 WHILE REMEMBERING IT
	DO REMEMBER .1 + .2 WHILE IGNORING THEM
	PLEASE REINSTATE COMING FROM + NEXTING WHILE ABSTAINING FROM THEM

	DO REMEMBER .1
	DO .1 <- #0
	DO IGNORE .1 WHILE REMEMBERING IT
(15)	DO .1 <- #15
	PLEASE REMEMBER .1
	DO READ OUT .2
	DO GIVE UP

	PLEASE COME FROM .1
	DO READ OUT .3
	DO GIVE UP

One point to note: the program READs OUT both .2 and .3, but we do not know in which order. The two READ OUT statements cannot be executed at the same time (because they lock the standard output while they are executed), but there is nothing in the program which decides who goes first. If it is important, you can do something like checking the value of a non-quantum variable and have one of the two potential execution path modifying it when the other one waits for the modification. For example:

	DO REMEMBER .1 + .4
	DO .1 <- #0
	DO .4 <- #16
	DO IGNORE .1 WHILE REMEMBERING IT
(15)	DO .1 <- #15
	PLEASE REMEMBER .1
	DO READ OUT .2
	DO .4 <- #0
	DO GIVE UP

	PLEASE COME FROM .1
(16)	DO .1 <- .4
	DO READ OUT .3
	DO GIVE UP

Beginning with CLC-INTERCAL 0.05, there are two new statements which can generate quantum bits: CONVERT and SWAP. These allow a program to modify its own semantics at runtime, while leaving it unchanged. The syntax is something like:

	DO CONVERT CONVERT STATEMENT TO STATEMENT TO
		   SWAP STATEMENT AND STATEMENT
	   WHILE LEAVING IT UNCHANGED

	DO SWAP STASH REGISTER LIST AND IGNORE REGISTER LIST
	   WHILE LEAVING THEM UNCHANGED

What happens next time you STASH something away? Well, it will STASH it as normal, but it will also IGNORE it. Do not confuse the above with:

	DO SWAP STASH REGISTER LIST AND IGNORE REGISTER LIST
	   WHILE REMEMBERING IT

CLC-INTERCAL 1.-94.-4 and newer allows any statement to be made quantum statements, with the exception of comments and READ OUT. This is actually implemented by letting the statement run to completion, and then undoing its effects while not undoing them. In most cases this is the same as executing the statements while not executing them, however READ OUT cannot be handled this way - once the output has been observed, we cannot undo that. WRITE IN is fine, as the undoing just restores the registers to the values they had before the input, it does not put the input back.

Emulation on classical computers

As it can be seen from the above examples, a Quantum INTERCAL program effectively behaves like a multithreaded program in which some of the registers are shared between threads, while others are private to each thread. The private registers are the ones which participate in a quantum IGNORE or REMEMBER. More precisely, all registers start as shared. When a quantum IGNORE or REMEMBER is executed, the program acts as if it started another thread, with the variables involved copied to a private area of each thread, but with complementary IGNORE state. If the quantum statement was an ABSTAIN or REINSTATE, a similar thing happens except that no registers are made private to the threads.

This picture suggests how to emulate this behaviour on a classical computer, using threads. The compiler will notice that this emulation is required if you compile a quantum program on a classical computer, and automatically includes the necessary code.