comb4.scm

(import (rnrs)
        (ijputils boxes)
        (ice-9 match))

;; Big picture: Two boxes
;; - first = pointer
;; - second = thunk

(define (create-graph l)
  (let lp ((l l))
   (match l
     [() (error 'create-graph "not supposed to happen")]
     [(l) (lp l)]
     [(h t ...)
      (fold-left (lambda (x y)
                   (box (box (cons x (lp y)))))
                 (lp h)
                 t)]
     [x (box (box x))])))

(define (p2 l)
  (let p ((l l) (args '()))
    (define l* (unbox (unbox l)))
    (cond ((pair? l*)
           (p (car l*) (cons (p (cdr l*) '()) args)))
          ((null? args)
           l*)
          (else
           (cons l* args)))))

(define (unbox2 x)
  (unbox (unbox x)))

(define (box2 x)
  (box (box x)))

(define trace? #f)

(define (step g stack)
  ;; stack contains the parents application nodes

  (when trace?
    (pk 'step (p2 g) (map (compose p2 cdr unbox unbox) stack)))
  (match (cons g stack)

    [((= unbox2 (l . r)) . stack)
     (step l (cons g stack))]
      
    [((= unbox2 'S)
      (and fp (= unbox2 (_ . f)))
      (and gp (= unbox2 (_ . g)))
      (and xp (= unbox2 (_ . x)))
      . rest)
     (let* ((fx (box2 (cons f x)))
            (gx (box2 (cons g x)))
            (top (box (cons fx gx))))
       (set-box! xp top)
       (step f (cons fx (cons xp rest))))]
      
    [((= unbox2 'K)
      (and xp (= unbox2 (_ . x)))
      yp
      . rest)
     (set-box! yp (unbox x))
     ;; (step yp rest)
     (step x rest)
     ]
      
    [((= unbox2 'I)
      (and xp (= unbox2 (_ . x)))
      . rest)
     (set-box! xp (unbox x))
     ;;(step xp rest)
     (step x rest)
     ]
      
    [(x . stack)
     #t]))

(define (ev x)
  (define g (create-graph x))
  (step g '())
  (p2 g))

(ev '(S (K K) (K I) I))
(ev '((S (K S) K) f g x)) ; B f g x = f (g x)
(ev '(S ((S (K S) K) ((S (K S) K) S K) S) (K K) f x y)) ; C f x y = f

(ev '(S I g (K x y))) ;; lazy test

;; Ev does not to full normalisation, only the leftmost spine

The reason I kept failing can be seen commented out above, namely,
I was transitioning to step on the old parent, rather than the
same node. This means that the updates did not get seen everywhere

So you used a double boxing, I see. I was thinking of trying a similar approach, but I think I still have other issues. Your code is immensely different than what I have so far, but I imagine that's because we have different use-cases and desired APIs.