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

Лол, я борщ сейчас ем

Ждем примеров на скала!

«целиком в монаде Future»(c)

А какое практическое приложение у этой задачи?

поцоны сейчас заняты зарабатыванием на борщ

Специальная олимпиада, бессмысленная и беспощадная.

Ну, например, научить тебя, балбеса, читать ОП до конца.

условия нашего микро-квеста заключаются в следующем: имеем n переменных, k из которых выражается через (n-k)

Например,
n = 3, k = 1, {x = y + z, y = x - z, z = x - y}

Мне кажется, или в приведенном примере каждая переменная выражается через две других?

Ну просто вот обычно в яп-срачах крики о том, что макросы очень все ускоряют и упрощают, сопровождаются макросами по 25 строк, которые генерят функцию длиной 5 строк, которая используется всего пару раз. Итого, профит неочевиден. А здесь очевиден, потому что пишем один макрос, а он генерирует достаточно много однотипных функций.

Да, правильно. Аналогично и для (n; k)-случая. Суть в том, что правила вывода формул имеются для абсолютно каждого значения.

Тогда я не совсем понимаю, как это соотносится с k переменными, выражаемыми через (n - k). В примере, получается, k = 3?

Суть в том, что правила вывода формул имеются для абсолютно каждого значения.

А макрос, получается, должен нагенерить все варианты минимального набора значений, достаточного для полной инициализации?

То есть 3 переменных выражается через 0? Нет, имеется в виду, что «базисных» переменных меньше, чем вообще всех, откуда следует возможность во время компиляции нагенерировать однотипных функций с максимально упрощенными расчетами (избавляемся от поиска по таблице этих соответствий переменных в рантайме, например). Или я что-то намудрил^W натупил?

Нам лень писать процедуры выведения и проверки в отдельном шаге

Правильно, зачем делать один раз, экономично и красиво, когда можно написать говнокод, который генерит дофига быдлокода. А потом спрашивают, почему программы тормозят.

Если у нас есть start, duration & end, то мы можем считать третью переменную из первых двух. Можно написать init(start, end), init(end, duration), init(start, duration) самому, а можно, наверное, написать макрос? Или вообще, имея тот набор соответствий, в рантайме вычислять, чего нам дано из stdin, а чего нужно вычислить. А если я не хочу в рантайме считать, то остается либо самому, либо макрос?

А как бы ты написал?

Ладно, допустим, это уяснили. А какие операции тогда допустимы в ограничениях? Только арифметические, или ещё вызов произвольных функций?

Ну вообще, по правильному, если есть сущность из набора полей, избыточность устраняют, а всё, что можно вычислить из минимума - вычисляют в методах, замкнутых над минимумом.

Те, которые поставляются стандартной библиотекой и не требуют ничего, что может потребоваться не на этапе компиляции (арифметические + может быть, еще всякие аналоги strlen, но для простоты пусть только арифметические).

Или разруливание зависимостей и вычисление необходимых параметров во время выполнения, или нагенерил бы оберток для функции init (но не копий функции init с разными параметрами).

с++-темплейт-шаманы

http://www.boost.org/doc/libs/1_54_0/libs/parameter/doc/html/index.html

Кажется, это оно

Как-то так. Схачено за 15 минут. Может оно и косячное где-то, тогда поправляйте:)

(defpackage #:lor-macro-init
  (:use :cl))

(in-package #:lor-macro-init)

;; (define-initor init (k)
;;   ((var1 initform1)
;;    (var2 initform2)
;;    ...
;;    (varN initform3))
;;   initor-form1
;;   initor-form2
;;   ...
;;   initor-formN)

(defmacro define-initor (name (k) (&rest init-forms*) &body initor-body*)
  (destructuring-bind (arg-list supplied-p dependent-filler)
      (loop for init-form in init-forms*
         for var-name = (first init-form)
         for var-init-form = (second init-form)
         for var-name-p = (gensym)
         collect var-name-p into supplied-p
         collect (list var-name nil var-name-p) into arg-list
         collect `(unless ,var-name-p
                    (setf ,var-name ,var-init-form)) into dependent-filler
         finally (return (list arg-list supplied-p dependent-filler)))
    
    `(defun ,name (&key ,@arg-list)
       (assert (<= (length (remove-if #'identity (list ,@supplied-p)))
                   ,k))
       ,@dependent-filler
       ,@initor-body*)))


(define-initor init (1)
    ((x (+ y z))
     (y (- x z))
     (z (- x y)))
  (list :x x
        :y y
        :z z))

;; LOR-MACRO-INIT> (init :x 100 :y 10)
;; (:X 100 :Y 10 :Z 90)
;; LOR-MACRO-INIT> (init :y 10 :x 100)
;; (:X 100 :Y 10 :Z 90)
;; LOR-MACRO-INIT> (init :z 10 :y 100)
;; (:X 110 :Y 100 :Z 10)

Ну все, тему можно закрывать.

In Lisp, if you want to do aspect-oriented programming, you just do a bunch of macros and you're there. In Java, you have to get Gregor Kiczales to go out and start a new company, taking months and years and try to get that to work.

Peter Norvig

То есть нужно писать (генерировать) не A(n, k), а C(n, k) функций.

«Возьмем X танков. Не, X мало. Возьмем Y танков.» (с) армейская задача.

Не в тему, по-моему, ты сказал.

То есть нужно писать (генерировать) не A(n, k), а C(n, k) функций.

«Возьмем X танков. Не, X мало. Возьмем Y танков.» (с) армейская задача.

А так:

«Возьмем A(n, k) танков. Не, A(n, k) мало. Возьмем C(n, k) танков.» (с) армейская задача.

#include <cstdio>

#define init(...) \
    []() { \
        struct base { \
            base() : __VA_ARGS__ {} \
            int x; \
            int y; \
            int z; \
        }; \
        struct calc : public base { \
            calc() : __VA_ARGS__ {} \
            int x = base::y + base::z; \
            int y = base::x - base::z; \
            int z = base::x - base::y; \
        }; \
        return calc(); \
    } ()

int main() {
    printf( "%d\n", init( x(100), y(90) ).z );
    printf( "%d\n", init( y(10), z(90) ).x );
}

как-то так

проверки, если надо, добавляются в конструктор calc

Что и во что должно раскрыться, ты пример-то напиши.

Тред про named & default arguments?
В скале из коробки есть: http://www.scala-lang.org/old/node/2075

а теперь попробуй решить с их помощью задачу ТС

Это как бы общепринятые обозначения, и при этом С меньше А на целый (n-k)!, но я уже увидел, что ты не понимаешь, о чем речь, поэтому можешь и дальше выступать в жанре неграмотной клоунады.

C(n, k) более-менее стандартно, еще это зовется биномиальным коэффициентом. A(n, k) стандарт в твоих влажных фантазиях.

C(n, k) более-менее стандартно, еще это зовется биномиальным коэффициентом.

Оно зовется числом сочетаний. Который совпадает с биномиальный коэффициентом, чисто случайно. А A(n,k) - число размещений, впонле стандартное, да.

Специалисты по комбинаторике в треде, все по ячейкам без повторений!

так пример экспанда для того что ты хочешь можно?

По описанию задача содержит вывод биндингов в макросе, то есть неразрешима алгоритмически.

Чего-то задание — ну ни хрена не понятно.

Нужен хотя бы один пример: что на входе, что на выходе.

Просто все мелкие примеры тривиальны. Ну вот пусть будет такой: есть неразбитый на дорожки аудиофайл, и к нему список из start-duration-end. Но так вышло, что для любой композиции доступно только две величины из трех. Мы разбиваем, и хотим знать зачем-то все три, причем неизвестно, какие из них будут встечаться. Поэтому я хочу, чтобы можно было давать на вход любое из. (start, duration), (start, end), (end, duration) (порядок внутри пар неважен). У меня есть конфигурация: {variables = {s, d, e}, exprs = { s = e - d, e = s + d, d = e - s} }. На выходе хочу получить минимальный набор функций, покрывающий полностью все возможные комбинации, т.е.

f(s, e) = { write_time_info(s, s + d, e) }
f(s, d) = { write_time_info(s, d, s + d) }
f(d, e) = { write_time_info(e - d, d, e) }

И да, я понимаю, что пример надуманный, нереалистичный и т.д. Я же это еще в ОП написал. Никого не заставляют писать, просто интересно увидеть, как в каком языке это реализуемо.

да никто не говорит о содержательности и реалистичности, просто из ОПпоста ничерта не ясно, чего ты хотел.

Ну да, алгоритмически неразрешимо, как я и говорил.

Я не уверен в этом. Что именно мешает быть разрешимиым?

Вот тут:

{variables = {s, d, e}, exprs = { s = e - d, e = s + d, d = e - s} }

Надо знать, какие переменные свободны в каждом из rule-выражений («e - d», «s + d», «e - s»). Эта задача алгоритмически неразрешима до экспанда выражения, то есть надо это выражение сперва раскрыть. Но для этого надо связать часть свободных переменных в контексте раскрытия - то есть знать, какие переменные не связаны в других rule-выражений, а для этого их надо раскрыть. Замкнутый круг. Мы не можем раскрыть первое выражение, пока не раскрыто второе, и не можем раскрыть второе, пока не раскрыто первое.

Решается, только если руками задать зависимости по переменным (тогда понятно, что за чем будет связываться).

Ага, в общем случае вижу. Но в моем варианте я предполагаю делать это «на условиях компилятора», т.е. просто нагенерировать функций вида f(x, y), которые можно вызывать с упоминанием этих же параметров, т. е. f(x = 5, y = 6), что позволяет выбрать из набора f(v1, v2) (где v1, v2 - любые) именно те, у которых нужная сигнатура. А избыточностью (т.е. z = g(x, y) => (x, y, z) = (x, y, g(x, y))) мы гарантируем, что переменная z _в_вызванной_с_обозначенными_параметрами_ функции не может быть потенциально дальше развернута по какой-то формуле (т. е. применять внутри нее правила - излишне). oh shi! я только что понял, кажется, о чем ты. В общем случае нет гарантий, что в правиле для завсимой переменной не будет новой необходимости раскрывать что-то? Если так, то, может, есть какие-то границы соотношения n:k, при которых любые k можно выразить через n-k без таких опасений?

tl;dr: два последних предложения.

которые можно вызывать с упоминанием этих же параметров, т. е. f(x = 5, y = 6), что позволяет выбрать из набора f(v1, v2) (где v1, v2 - любые) именно те, у которых нужная сигнатура

Суть в следующем. Вот такой пример:

(f [x (* 2 d)] [d 1])

Нам надо знать, что d должно быть вычислено _до_ x. Для этого нам надо знать, какие из переменных (x, d в данном случае) в каких rule-выражениях встречаются, но чтобы это знать, нам надо эти выражения полностью раскрыть (т.к. их может, например, какой-то макрос в выражении внедрять или перекрывать), вообще это несколько сложнее, чем найти свободные вхождения. А чтобы это выражения раскрыть - надо понимать, какие из переменных (x,d) в них надо связать (в частности, чтобы корректно перекрыть переменные из внешнего контекста (если они там есть).

Но если ограничить все это дело так, чтобы зависимые переменные шли после независимых (то есть нельзя (f [x (* 2 d)] [d 1]), но можно (f [d 1] [x (* 2 d)]), то все ок)

C(n, k) функций

Как так? Допустим, я буду рисовать переменные как вершины графа, а правила как множества ребёр (каждое множество своего цвета) к определяемому узлу от того через что он определяется. Рёбер вида x -> x для узла x быть не должно (полагаем, что не может быть правил вида x = f[x]).

Например

n = 3, k = 1

x = f[y, z]

y ----> x <---- z

можно написать конструкторы только из {x, y, z} и {y, z} — два варианта (это можно связать с количеством возможных полных обходов (понятие которого для нашего случая нужно определить) такого графа).

Или так

n = 3, k = 2

x = f[y, z]
y = g[z]

y ---> x
^      ^
 .     |
   .   |
     . |
       z

{x, y, z}, {y, z}, {x, z}, {z} — четыре.

А вообще это какое-то число от 1 до 2^n (мощность множества всех подмножеств множества вершин/переменных), в зависимости от того как устроены правила.

1:

n, k = 0

x1    x2    ...

(только полный конструктор из {x1 .. xn}).

2^n - 1:

n, k = n

x1 = f1[xn], x2 = f2[x1], ...

x1 ---> x2 ****> ... ////> xn
 ^                          +
 ++++++++++++++++++++++++++++

(выбираем Exp({x1 .. xn}) \ {} множеств вершин — каждый раз есть возможность обойти весь граф согласно правилам).

2^n:

n, k = n

x1 = c, x2 = f1[x1], ...

----> x1 ****> x2 ////> ... ++++> xn

(любое из Exp({x1 .. xn})). В частности

x1 = c1, x2 = c2, ...

|     +
|     +
v     v
x1    x2    ...

Может оно и косячное где-то, тогда поправляйте:)

Нашлось такое:

;; тут я не понял почему k = 1, но его изменение не помогает
(define-initor init (3) ((x (1+ y)) (y (1+ z)) (z (1+ x))) (list :x x :y y :z z))
(init :x 1)

Можно без цикла:

(define-initor init (2) ((x y) (y 0)) (list :x x :y y))
(init)

хотя тут поможет перестановка правил.

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

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

И не может быть. Как я объяснил выше - это алгоритмически неразрешимая задача.

вообще фот как-то так

#lang racket
(require syntax/parse/define
         (for-syntax syntax/parse
                     racket/syntax))

(define (undefined)
  (define x x)
  x)

(begin-for-syntax
  (define-syntax-class rule
    (pattern id:id
             #:with value #'(undefined))
    (pattern (id:id e:expr ...+)
             #:with value #'(begin e ...))))

(define-simple-macro (define-with-init (name rule:rule ...) body:expr ...+)
  #:with hidden-name (format-symbol "hidden-~a" (syntax-e #'name))
  #:with (tvar ...) (generate-temporaries #'(rule ...))
  (begin (define (hidden-name rule.id ...) body ...)
         (define-simple-macro (name (~optional [(~datum rule.id) tvar]
                                               #:defaults ([tvar #'rule.value])) 
                                    ...)
           (let* ([rule.id tvar] ...) 
             (hidden-name rule.id ...)))))

> (define-with-init (yoba x [y (+ x 5)] [z (+ y 10)])
    (list x (* 2 y) (* 3 z)))
> (yoba [x 1])
'(1 12 48)
> 

это алгоритмически неразрешимая задача.

Почему? Не важно, что там в Racket — почему бы самой по себе этой задаче не быть разрешимой? Из N переменных проходим все V из Exp(N), для каждой V смотрим является ли N \ V подмножеством LHS правил, если нет — не пишем такой конструктор, если да — пробуем писать, разрешение зависимостей сводится к выявлению циклов и путей в графе (что разрешимо). По правилу нужно уметь видеть какие переменные из N в RHS связаны (сам RHS это некий простой для анализа терм).