Keykos and Scheme have related underlying principles. I explore here how the factory function might be done in Scheme. The idea of suspicious users sharing a Scheme universe first saw print, as far as I know, in Jonathan Rees’s paper Security Kernel Based on the Lambda Calculus. We adopt from that paper the idea of distinct top level environments for each of these users as well as distinct “terminals” and read-eval-print loops. Some worm hole between these environments allows passage of Scheme values so the sender knows to whom he sends and the receiver knows from whom he receives.

Scheme without the standard procedure eval is much like a Harvard architecture machine. In such a machine data and instructions are loaded by distinct means into distinct memories with distinct addresses and a program cannot create code and then obey it. R5RS includes a suitable version of eval.

The Factory

The factory reference above leads to explanations of the factory that are either more careful, or more expansive. Here I will be brief to introduce terminology. User P has a Scheme program p that he is willing for a few others to use, even though he is not willing to let the others see p. p is in the form of a Scheme value such as '(lambda (x) (+ x x)).

O is another user who would like to use p but is unwilling to let P see the argument that he must pass to p.

P could push p thru the hole but then O could abscond with it. P could push the value of (eval p (scheme-report-environment 5)) thru the worm hole to O but O will fear that P has sent some bugged version such as (lambda (x) (set! booty x) ((eval p (scheme-report-environment 5)) x)) where booty is a variable in P’s top level environment. If O invokes the passed procedure, the argument will become accessible to P as booty. Alternatively if p includes '(write x) and P sends (eval p (interaction-environment)), the yield will appear on P’s terminal.

Fortunately there is Fred, yet another ordinary user who is trusted by both O and P. Fred has an ordinary Scheme program to solve the problem of O and P. f is the procedure which is defined by Fred’s program and Fred sends f to both O and P. P sends r = (f "build" p) to O. What is O to make of r? Is O to trust that r is a value returned by f? I think not.

O also has access to f and asks f to vouch for r thus: (f "vouch" r), which yields #t. O now knows that is such a yield and that P will not see x if O perform (r x).

Notice that Fred’s program is protecting two concerns. If either were absent the problem would be much easier.

Is it indeed feasible to write Fred’s program in Scheme? There are several similar ways to do it. I think this is the simplest: 
; Fred says to his read-eval-print loop:
(define funnames      '(car cdr cons + - * / eq? ...))
(define funvalues (list car cdr cons + - * / eq? ...))
(define f (let ((stash '()))(lambda (order p)(cond
   ((string=? order "build") (let (
       (r ((eval (list 'lambda funnames p) (null-environment 5)) funvalues)))
     (set! stash (cons r stash))
     r))
   ((string=? order "vouch")
     (let x ((s stash)) (if (pair? s) (if (eq? p (car s)) #t (x (cdr s))) #f)))
   (#t "stench")))))
and then sends f off to O and P.

The variable stash is private to f and is f’s memory of the values it has produced. What is in the ellipses? Well, all of the Standard procedures, except:

interaction-environment, scheme-report-environment, call-with-input-file, call-output-input-file, current-input-port, current-output-port, with-input-from-file, with-output-to-file, open-input-file, open-output-file, close-input-port, close-output-port,
0 arg versions of {read, read-char, peek-char, char-ready?, newline}
1 arg versions of {write, display, write-char}
load, transcript-on, transcript-off.

There is obviously a problem with IO. The nature of the task and trust arrangement typically precludes any need for IO. If needed, one solution is to Curry p once more and let O supply a set of IO functions to his own liking. (lambda (name) (open-input-file (cdr (assoc name ok-list)))) might evaluate in O’s environment to a useful value to be bound to the identifier open-input-file in the body of p. Such a scheme is strictly between O and P. Fred need not be concerned.

I don’t now see in the language specification that

(begin (string-set! "abcd" 2 #\z) "abcd") => "abcd"
(begin (vector-set! '#(3 4 5) 1 7) '#(3 4 5)) => #(3 4 5)
but this is a necessary system property for this sort of confinement.

Yet a Problem

There is alas still a problem. Suppose that P creates p thus:
(define f (receiveFred))
(define p '(lambda (order x) (if (string=? order "snatch") equal?
   (begin (set! equal? x)(cond .... )))))
(define r (f "build" p))
(sendO r)
... time passes
(write (r "snatch"))
While time passes O does:
(define p (receiveP))
(define f (receiveFred))
(if (f "vouch" p) (p "do" x) "Alarm!")
P’s write operation will reveal O’s value for x, the secret. The secret was stashed in the “location” created when P performed (f "build" p), to hold the standard procedure value for equal?. We really wanted to bind 'equal? to equal? instead of a location assigned to equal?, but that is another rant.

The fix is yet more Currying. Fred tries again: 

; Fred says to his read-eval-print loop:
(define funnames  '(memory car cdr cons + - * / eq? ...))
(define funvaues (list '() car cdr cons + - * / eq? ...))
(define f (let ((stash '()))(lambda (order p)(cond
   ((string=? order "build") (let (
       (r (lambda ()
         ((eval (list 'lambda funnames p) (null-environment 5)) funvalues))))
     (set! stash (cons r stash))
     r))
   ((string=? order "vouch")
     (let x ((s stash)) (if (pair? s) (if (eq? p (car s)) #t (x (cdr s))) #f)))
   (#t "stench")))))
Now (p) creates locations private to the invoker. O does:
(define p (receiveP))
(define f (receiveFred))
(if (f "vouch" p) ((p) "do" x) "Alarm!")
In P’s environment (write ((r) "snatch")) now yields equal?.

Now O can do: 

(define ob (p))
(ob "add" 3) => (3)
(ob "add" 5) => (5 3)
for ob has a memory private to P. P’s p may include the identifier memory bound to a location created when O performed (p).

P’s chastened p reads (lambda (order x)(set! memory (cons x memory)) x)

The Keykos factory is rather more general allowing P to employ software service from Q with the same mutual suspicion between P and Q. The Keykos factory also allows negotiated and audited holes so that P can receive very limited (muffled) signals from his program sufficient for billing. Space and CPU time are also accounted for. Synergy is used to avoid the cost of the stash.