Problem Set 2: Alyssa P. Hacker and the Amazing Quantum Scheme Interpreter

Out: 6 February 2001 Due: Thursday, 22 Feburary (in class)

Purpose

This problem set is intended to make everyone comfortable with metalinguistic abstraction. After completing this problem set, you should be able to extend and alter the behavior of any metacircular evaluator.

Collaboration Policy

You are required to collaborate on this problem set. Each student has been pseudo-randomly (according to alphabetical order) assigned a problem set partner shown below. You will not be required to work with the same partner again.

Team 1:	Yuanfang Cai ("Doris") yc7a@cs.virginia.edu	Christopher Taylor ("Chris") cmt5n@virginia.edu
Team 2:	Brian Clarke brian@virginia.edu	Weilin Zhong ("Weilin") weilin@cs.virginia.edu
Team 3:	Michael Deighan ("Mike") mdeighan@earthlink.net	Haiyong Wang hw6h@cs.virginia.edu
Team 4:	Thomas William Sabanosh ("Tom") tws9f@virginia.edu	Elisabeth Strunk eas9d@cs.virginia.edu
Team 5:	Michael Tashbook ("Mike") mst2f@cs.virginia.edu	Dana Wortman dtw7b@virginia.edu

The goal of your collaboration is not to complete the problem set as quickly as possible (for example by dividing it between the two teammates). It is to make both teammates understand as much as possible. If one partner understands something and the other does not, she should explain it to him until he understands well enough to explain it clearly back to her.

It is up to you whether you decide to work together, or inpendendly at first and then go over your answers together. It is usually a good idea if each partner reads through and thinks about the problems independently before you start working together.

Each problem set pair should turn in exactly one problem set. Both team members will receive the same grade. In cases where one team member does not want to do the problem set, the orphaned team member may decide to work independently (and get her own grade on the problem set), or join another team.

1. Extending Mini-Scheme

The Mini-Scheme metacircular evaluator from 30 January (http://www.cs.virginia.edu/cs655/manifests/meval.scm - updated 14 Feburary with Michael Deighan's fix) was missing some useful Scheme features.

a. Change the Mini-Scheme metacircular evaluator to support procedures with multiple parameters and applications with multiple arguments.

b. Explain why it is impossible to define a function in Mini-Scheme that behaves like the Scheme if special form.

c. Extend your Mini-Scheme implementation to support the special form if, that has semantics identical to regular Scheme's if special form.

d. Extend your Mini-Scheme implementation to support lists. This should only require a small change to eval, and extending the global environment with the Scheme list functions cons, car, cdr, list, list? and null?.

2. Quantum Scheme

The NSA has established a top-secret (well, I guess its not so secret anymore) program to develop a quantum computer. Unlike electrical and mechanical computers in which every bit is in exactly one state at a time, in a quantum computer bits (now referred to as qubits) can be in more than one state at once. The NSA would like to have a simulator to experiment with quantum algorithms while they develop their quantum computer.

Your mission is to turn your Mini-Scheme implementation (as modified in problem 1) into a Quantum Scheme Interpreter. Quantum states will be modeled by a new datatype, the quist (short for quantum list). A quist is a list of values representing the possible states of one or more qubits. For example, (quist 0 1) represents a single qubit; (quist 0 1 2 3) represents two qubits, each of which may be in either state.

Expressions invloving quists evaluate to a quist of the value of the expression for all possible values in the quist. We represent quists as tagged lists beginning with 'quist.

Some examples:

(+ (list 'quist 0 1) (list 'quist 0 1))
(quist 0 1 2) or (quist 0 1 1 2)

((list 'quist + -) (list 'quist 2 3) (list 'quist 1 2))
(quist 3 4 5 1 0 2) or (quist 0 1 2 3 4 5)

The order of the values in a quist list does not matter. For example, (quist 0 1) means exactly the same thing as (quist 1 0). The list of values in a quist may include duplicates. That is, (quist 1 1) means the same thing as (quist 1). Your implementation may print out any equivalent quist. Note: this was revised on 14 Feb. The original handout was unclear and implied you had to remove duplicate values form quists. Its fine if you do this, but not required.

a. Extend your Mini-Scheme implementation to support quists.

The act of observing a quantum particle forces it into one of its possible states. Physicists haven't yet figured out good ways to force qubits into particular states (and it may not be possible), but let's assume our quantum computer can provide a flexible observe operation: observe: T -> bool, quist -> value.

That is, observe takes a function that evaluates to a boolean when it is applied to a value of any type and a quist. The value of an observe is that value of any possible value of the quist such that the predicate function does not evaluate to false for that value.

Some examples:

(observe (lambda (x) #t) (list 'quist 0 1))
0 or 1

(observe (lambda (x) #f) (list 'quist 0 1))
Error: unobservable quist.
On the real quantum computer, unobservable quists lead to a chain-reaction explosion that engulfs the Universe. It is not necessary for your simulator to produce the same effect. The NSA hopes training with quantum scheme will encourage its programmers to be careful before they run their programs on the real quantum computer.

(observe (lambda (x) (> x 10) (list 'quist 3 17 8 23 -4))
17 or 23

(observe list? (list 'quist 3 '(0 1) '() 17 '(2 3)))
(0 1) or () or (2 3)

b. Explain why observe must be a special form, and extend your implementation to support observe.

c. (Optional - don't do this unless you want to and don't have any other required work to do) Use your quantum scheme language to program a factoring algorithm that is polynomial in the number of digits of the number to be factored, assuming all primitive Scheme operations take constant time regardless of how many possible states the quists they are applied to are in. (This is a moderately realistic interpretation of what a quantum computer could do.)

Quantum Links

If you are curious why factoring large numbers is such an important problem, see CS551 Lecture 7: Non-secret Key Cryptography and CS551 Lecture 8: Security of RSA. For an account of factoring without a quantum computer, see Derik Atkins, et. al., The Magic Words Are Squeamish Ossifrage, AsiaCrypt 1994. There are lots of papers on factoring.

Neil Gershenfeld and Isaac Chuang, Quantum Computing with Molecules, Scientific American, 1998.
QCL - A Programming Language for Quantum Computers

University of Virginia Department of Computer Science CS 655: Programming Languages

David Evans evans@virginia.edu