Say I want to sort three numbers from a given input. How can I convert this function to a boolean circuit?
For this particular question, there are simple answers.
The traditional way to sort number using circuits (which show up when one wants to sort in parallel) are with sorting networks.
For very small input sizes optimal sorting networks are known.
In general the sorting network with the best asymptotics (AKS) is not particularly practical.
Instead, a good (general) recommendation is Batcher Odd-Even Mergesort, which uses $O(n (\log n)^2)$ comparisons, and is a depth $O((\log n)^2)$ circuit.
How do conditional statements work in the boolean circuit?
The main answer is "they are a pain".
General (conditional) statements can be seen as computing something of the form.
if val:
C1(x1,...,xn)
else:
C2(x1,...,xn)
here, C1 and C2 are smaller circuits/functions/whatever.
Anyway, to compute this branch using a circuit, one can first convert it to be branchless by writing
ytrue = C1(x1,...,xn)
yfalse = C2(x1,...,xn)
yreturn = (val and ytrue) or (not val and yfalse)
Essentially, when val is true one can simplify this to the first part of the branch.
When val is false, one can simplify it to the second part of the branch.
In princple it should be straightforward to compile some broad class of programs to binary circuits.
Searching for "MPC Circuit Compiler" finds some relevant results, i.e. this paper which includes some discussion of prior literature.
