How is set! defined in scheme?

Question

How would you implement your own set! function in Scheme? A set! function is a destructive procedure that changes a value that is defined taking into account the previous value.

Answer 1

As noted in the comments, set! is a primitive in Scheme that must be provided by the implementation. Similarly, you can't implement the assignment operator, =, in most programming languages. In Common Lisp, setf can be extended (using setf-expanders) to allow (setf form value) to work on new kinds of forms.

Because Scheme's set! only modifies variable bindings (like Common Lisp's setq), it is still worth asking how can we implement functions like set-car! and other structural modifiers. This could be seen, in one sense, as a generalization of assignment to variables, but because lexical variables (along with closures) are sufficient to represent arbitrarily complex structures, it can also be seen as a more specialized case. In Scheme (aside from built in primitives like arrays), mutation of object fields is a specialization, because objects can be implemented by lexical closures, and implemented in terms of set!. This is a typical exercise given when showing how structures, e.g., cons cells, can be implemented using lexical closures alone. Here's an example that shows the implementation of single-value mutable cells::

(define (make-cell value)
  (lambda (op)
    (case op
      ((update)
       (lambda (new-value)
         (set! value new-value)))
      ((retrieve)
       (lambda ()
         value)))))

(define (set-value! cell new-value)
  ((cell 'update) new-value))

(define (get-value cell)
  ((cell 'retrieve)))

Given these definitions, we can create a cell, that starts with the value 4, update the value to 8 using our set-value!, and retrieve the new value:

(let ((c (make-cell 4)))
  (set-value! c 8)
  (get-value c))
=> 8

Answer 2

As has been mentioned, set! is a primitive and can't be implemented as a procedure. To really understand how it works under the hood, I suggest you take a look at the inner workings of a Lisp interpreter. Here's a great one to start: the metacircular evaluator in SICP, in particular the section titled "Assignments and definitions". Here's an excerpt of the parts relevant for the question:

(define (eval exp env)
  (cond ...
        ((assignment? exp) (eval-assignment exp env))
        ...
        (else (error "Unknown expression type -- EVAL" exp))))

(define (assignment? exp)
  (tagged-list? exp 'set!))

(define (eval-assignment exp env)
  (set-variable-value! (assignment-variable exp)
                       (eval (assignment-value exp) env)
                       env)
  'ok)

(define (set-variable-value! var val env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable -- SET!" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

In the end, a set! operation is just a mutation of a binding's value in the environment. Because a modification at this level is off-limits for a "normal" procedure, it has to be implemented as a special form.