quil-lang / quilc

The optimizing Quil compiler.
Apache License 2.0
457 stars 72 forks source link

Add Extern Support #880

Closed macrologist closed 1 year ago

macrologist commented 1 year ago

The EXTERN Pragma keyword allows for users to indicate that certain operators should be "virtual" from the perspective of the frontend parsing and compilation stages. By virtual, I mean that applications of these operators do not have a definition.

It is expected that users will provide definition for these externs during backend-compile for their own subclasses of cl-quil:backend.

For example:

EXTERN PHONY

X 0
CNOT 1 0
PHONY 1
CNOT 0 1

The above code will parse and compile but result in an opaque instance of extern-application in the resulting code. Extern instructions may be rewired, but will otherwise remain untouched. Similar to the effect of PRESERVE_BLOCK pragmas.

Addtionally, the user can specify that an ordinarily "off the shelf" gate should be an EXTERN, meaning that, again, the user is expected to supply an implementation for that gate on the backend.

E.g.

EXTERN H
EXTERN CNOT

X 0
CNOT 1 0
Y 0
H 1
CZ 1 0

Such a program will allow the compiler to neither optimize nor nativize CNOT and H gate applications.

macrologist commented 1 year ago

@stylewarning I have taken your idea about the keyword approach to heart. As of 1481149 the pragma has been removed and replaced with a new keyword.

macrologist commented 1 year ago

I added a few good and bad quil files to test. Let me know if you have worries or thoughts on additional cases I should add tests for. There may be edge cases that my only now waning naivete vis-a-vis quilc has blinded me to.