Отодвиньте вашу тарелку с борщом в сторону, специалисты по макросам!

Не важно, что там в Racket

Действительно, не важно. Дело и не в Racket :)

почему бы самой по себе этой задаче не быть разрешимой?

Потому что вот так. Нельзя до полного раскрытия макро-формы узнать, какие переменные в каком контексте связаны (и вообще какие переменные в каком контексте есть).

По правилу нужно уметь видеть какие переменные из N в RHS связаны (сам RHS это некий простой для анализа терм).

С чего вдруг RHS это простой для анализа терм? Тут-то как раз и проблема - не получится у тебя связанные переменные увидеть по терму.

({x}, {x = macro(y)}) и какие переменные в macro(y) связаны?

({x}, {x = macro(y)}) и какие переменные в macro(y) связаны?

Понятно.

Выше сказано было, что правило достаточно просто по виду — арифметика, стандартные _функции_. То есть RHS это простой для анализа терм. Ну и давай ещё скажем, например, что у нас генератор конструкторов для C++ — тогда слово macro я распарсить вообще не могу (cpp уже всё сделал).

Ну если пишем на каком-то ограниченном подмножестве языка то все ок, конечно, но тогда нужна нормальная спецификация подмножества и проверять, не выходит ли RHS за его пределы. Все-таки лучше уж потребовать, чтобы связывания были в точке вызова слева направо упорядочены.

Нет, ты что-то слишком усложнил. Если говорить в терминах графов, то у нашего графа n ребер, и обязательным условием для продолжения работы нужно связать между собой любые k (неупорядоченно внутри k). То есть, например, у нас есть (помимо начальных значений) {Rx,Ry,Rz,Vx,Vy,Xz,t}. Мы не можем знать коодрдинаты и скорость, зная только t, но посчитать любую скорость, зная соответствующую координату, мы можем. Аналогично, зная Vx & t (и R0, конечно, но не об этом), по функции можно восстановить Rx. То есть здесь по любым 4 переменным (вроде) можно восстановить все 7 (если полагать независимыми координаты скорости).

В твоем самом первом примере ты приводить только x=f(y,z), а у нас речь идет просто о том, чтобы перебрать все возможные комбинации и нагенериовать заранее готовых конструкторов вместо поиска в рантайме по таблице правил и потом таблице функций. Или я неправильно понял твой пост?

чтобы перебрать все возможные комбинации и нагенериовать заранее готовых конструкторов

А зачем? Достаточно же только одного.

C(n, k) < A(n, k)

Как я понимаю, нет выстраивания порядка применения правил по их зависимостям друг от друга.

конечно нет. в исходной задаче зависимостей не было. да и это неразрешимо, в общем случае.

Я исходил из того, что «правила» это просто указания что делать если какой-то именованный аргумент не предоставлен, то есть как его составить из данных (данные могут быть не предоставлены, но зависеть от данных и т.д.), без всякого контроля. Например, для структуры с int x, y; можно попытаться написать максимум 2^2 конструкторов без учёта порядка — {}, {x}, {y}, {x, y}, если правила найдутся. Вообще от одного полного конструктора {x1, x2, ..., xn} до 2^n — {}, {x1}, {x2}, ..., {x1, x2}, {x1, x3}, ..., ..., {x1, x2, ..., xn}, можно считать, обратно, что правила позволяют вычёркивать аргументы из полного конструктора.

А вот для системы уравнений нужно, наверно, её сначала руками решить и добавить правил (увеличить k), плюс запретить (?) конструкторы которые могут противоречить системе. То есть n = 3, k = 3, {x = y + z, y = x - z, z = x - y} и {x, y}, {x, z}, {y, z}.

для системы уравнений нужно

Хотя тут это и не вполне система, так как три эквивалентных уравнения, то есть просто правила на основе обращений f как функции.

Еще актуально? Вот корявый вариант на ракете:

#lang racket

(require (for-syntax syntax/parse))
(require racket/format)
(require (for-syntax racket/syntax))

(define-for-syntax (sd stx)
  (syntax->datum stx))

(define-for-syntax (sym->kw sym)
  (string->keyword (symbol->string sym)))

(define-for-syntax (emit-set-stx var set-form)
  (with-syntax ([var-stx var] [st-stx set-form])
    #'(when (eq? var-stx #f) (set! var-stx st-stx))))

(define-syntax (define-initor stx)
  (syntax-case stx ()
    [(define-initor name init-forms body) 
     (let-values 
         ([(args params setvals)
           (for/fold ([al '()] [pl '()] [sl '()]) 
               ([init-form (sd #'init-forms)])
             (syntax-parse
              (datum->syntax stx init-form)
              [(var:id sval:expr) 
               (values (append al (list #'var))
                       (append pl (list (sym->kw (sd #'var)) (list #'var #f)))
                       (append sl (list #'sval)))]))])
       (with-syntax ([sig-stx (append (list #'name) params)]
                     [set-block (append (list 'begin) 
                                        (for/list ([a args] [sv setvals])
                                          (emit-set-stx a sv)))])
         #'(define sig-stx set-block body)))]))

(define-initor init1 
  ((x (+ y z)) (y (- x z)) (z (- x y)))
  (list x y z))

;; racket@lorinit.rkt> (init1 #:x 10 #:y 20)
;; '(10 20 -10)

чорт, увидел бы этот пост раньше, не стал бы позориться :D