Multiple Fixed-Point Combinators

General
1

Hi, Racket Discourse.

I have been looking at the bruijn language lately because it has such a nice syntax. I'd encourage any curious readers to take a look, the author is doing some interesting things.

In any case, in a blog post, Marvin speaks about variadic fixed-point combinators, and mentions the paper, A Variadic Extension of Curry's Fixed-Point Combinator, which presents a Scheme implementation of the concept.

It's an easy read, and the code itself is largely self explanatory.

I found it immensely satisfying to write a syntax-parse-rule to explicitly create mutually recursive procedures, but the paper presents a neat functional approach, as well.

#lang racket/base

(require
  (for-syntax
   racket/base)
  syntax/parse/define)

;; explicitly construct mutually recursive procedures
(define-syntax-parse-rule (expl-fps fs ...)
  #:with (xs ...) (generate-temporaries #'(fs ...))
  #:with (fi ...) #'(fs ...) ; used for clarity, not necessary
  #:with (xi ...) #'(xs ...) ;
  (values
   ((lambda (xs ...) (fi (lambda args (apply (xi xs ...) args)) ...))
    (lambda (xs ...) (fs (lambda args (apply (xi xs ...) args)) ...))
    ...)
   ...))

(define (((curry-args xs) xi) . args)
  (apply (apply xi xs) args))

(define ((curry-xs fi) . xs)
  (apply fi (map (curry-args xs) xs)))

(define ((curry-xi xs) xi)
  (apply xi xs))

;; implicitly construct mutually recursive procedures
(define (impl-fps . fs)
  (let ([xs (map curry-xs fs)])
    (apply values (map (curry-xi xs) xs))))

(define _even? ;; partially recursive even?
  (lambda (even? odd?)
    (lambda (n)
      (if (zero? n) #t
          (odd? (- n 1))))))

(define _odd? ;; partially recursive odd?
  (lambda (even? odd?)
    (lambda (n)
      (if (zero? n) #f
          (even? (- n 1))))))

(define-values (even?₁ odd?₁) (expl-fps _even? _odd?))
(define-values (even?₂ odd?₂) (impl-fps _even? _odd?))

(even?₁ 8) ;=> #t
(odd?₁  9) ;=> #t
(even?₂ 4) ;=> #t
(odd?₂  5) ;=> #t

Happy hacking!