How to change values in Scheme but just using purely functional paradigm

Question

I'm trying to change values of some variables but I can not do it without leaving the functional paradigm, for example using set!. Is there any way it can be done?

Example code:

(lambda ()
      (let ((more a))
        (set! a b)
        (set! b (+ more b))

I want to change a taking the value of b and i want to change b taking the value (+ more b) but using purely functional paradigm, without set!.

Answer 1

You can't do this, but you can do something equivalent. Let's say I have some function f1 in which a and b are bound (let's say they are arguments as this is going to make things easier). And at some point I want to swap a and b. So I start with this:

(define f1
  (λ (a b)
    ... code that uses a and b ...
    (let ([tmp a])
      (set! a b)
      (set! b tmp))
    ... code that uses a and b, now swapped ...))

And this code is clearly not functional as it has assignment in it. But I can do this, inventing a new function, f2:

(define f1
  (λ (a b)
    ... code that uses a and b ...
    (f2 b a)))

(define f2
  (λ (a b)
    ... code that uses a and b, now swapped ...))

And this code is functional, and it does the same thing. And I can then just get rid of f2's name, because functions are first-class:

(define f1
  (λ (a b)
    ... code that uses a and b ...
    ((λ (a b)
       ... code that uses a and b, now swapped ...)
     b a))

(And obviously we'd write this as:

(define f1
  (λ (a b)
    ...
    (let ([b a] [a b])
      ...)))

which is the same thing.)

So this code now does exactly the same thing as the original code does, except it is purely functional (well: so long as the code in ellipsis is, which it probably is not, since the first chunk can really only do something by side-effect).

Now here's the clever bit: Scheme is required to be properly tail-recursive. What this means is that tail calls must be eliminated by implementations. Function call, in Scheme, is essentially GO TO passing arguments, as famously described in Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO, one of the famous 'Lambda the ultimate' papers. The function call to what was initially f2 and became an anonymous function is a tail call, and must therefore be eliminated. Any reasonable Scheme implementation will very likely turn this code into code which is the same as or possibly better than the naive code with assignment.

---

A note on the lambda-the-ultimate papers: the site which used to host copies of them them and to which there are still many links, including from Wikipedia has turned into spam: do not follow those links (the site had a name which included the words 'read' and 'scheme'). The best place to look for them now seems to be the AI Memos repository at MIT. It's pretty annoying that they have become so hard to find as they are absolutely foundational papers.