Ересь о синтаксисе let и lambda

let-lambda.scm

; Задача: посмотреть с разных сторон на связку синтаксис lambda и let в
; контексте вычислительной модели R3. Модель проста: в каждый момент времени
; состоянием вычисления является список отложенных вызовов функций, ожидающих
; готовности своих параметров. Когда все параметры готовы, функция срабатывает,
; порождая продолжение списка отложенных вызовов и операторов записи параметров
; в некоторые из этих отложенных вызовов. Отложенные вызовы задаются
; конструкцией (run ...), места подстановки параметров -- конструкцией
; (pin ...), операторы записи значений в места подстановки -- конструкцией
; (bind ...). Меняющиеся во времени множества отложенных вызовов и операций
; записи создают некоторый динамический граф потока данных.
;
; Хочется найти такой вариант синтаксиса, при котором потребовалось бы
; минимальное количество связывающих (let, bind, define и прочих) конструкций
; для комфортного программирования. Ну и скобок чтобы тоже было поменьше
;
; Сравнивать варианты lambda и let будем на кошечках: функция вычисления корней
; квадратного уравнения (оригинал на Clojure), процедура генерации случайного
; значения из распределения Гаусса (оригинал на Arc), процедура распределённого
; блочного умножения матриц (оригинал на одном из вариантов языка для R3).

; Квадратные уравнения
(defn- solve-square-equation [^double a ^double b ^double c]
  (if (zero? a)
    (if (not= 0.0 b)
      (let [t (/ (- c) b)] (->Roots t t)))
    (let [D (- (* b b) (* 4.0 a c))]
      (if (<= 0.0 D)
        (let [D-sqrt (Math/sqrt D)
              a-rcpr (/ (* 2.0 a))
              tp     (* (+ (- b) D-sqrt) a-rcpr)
              tm     (* (- (- b) D-sqrt) a-rcpr)]
          (->Roots (min tp tm) (max tp tm)))))))

; Случайная Гаусса
(def gauss-random (sigma (o mu 0))
  "gausian distributed random with width sigma around mu"
  (withs (u (rand)
          v (* 1.7156 (- (rand) 0.5))
          x (- u 0.449871)
          y (+ abs.v 0.386595)
          q (+ (* x x) (* y (- (* 0.196 y) (* 0.25472 x)))))
    (while (and (> q 0.27597)
                (or (> q 0.27846) (> (* v v) (* -4 log.u u u))))
      (= u (rand)
         v (* 1.7156 (- (rand) 0.5))
         x (- u 0.449871)
         y (+ abs.v 0.386595)
         q (+ (* x x) (* y (- (* 0.196 y) (* 0.25472 x))))))
    (+ mu (/ (* sigma v) u))))

; Умножение распределённой матрицы
(let distributed-matrix-mul
     (lambda R A B
             (for (lambda i j k (run matrix-block-mul (zip 'i.j) (pin A 'i.k) (pin B 'k.j)))
                  (range l)
                  (range n)
                  (range m))

             (let sum-loop
                  (lambda result r-sum r-blocks n-blocks
                          (if (= 0 n-blocks)
                              (run bind result (pin sum))
                              (begin (run matrix-block-add (! pin :sum) (pin r-sum) (zip r-block))
                                     (run sum-loop result (? pin :sum) (r-blocks) (- n-blocks 1))))))

             (for (lambda i j (run sum-loop (pin R 'i.j) (zero-matrix) (? zip 'i.j) m))
                  (range m)
                  (range l))))

; ПЕРВЫЙ ВАРИАНТ. Синтаксис вида:
;   (lambda i1 ... in E1 ... EN)
;   (let i1 e1 ... in en)
;
; Скобок минимум. Конструкция let - с потоковой семантикой. То есть, она в
; текущий поток вносит позиции i1, ..., in, которые связываются со значениями,
; на которые можно ссылаться дальше. Эту конструкцию в R3 можно сделать
; рекурсивной. В R3 не бывает простых переменных, поэтому цикл gauss-random
; нужно переписать. В таком синтаксисе всё будет выглядеть так:

(let solve-square-equation
     (lambda a b c
       (if (zero? a)
         (if (not (zero? b))
           (begin (let t (/ (- c) b)) (Roots t t)))
         (begin (let D (- (* b b) (* 4.0 a c)))
                (if (<= 0.0 D)
                  (begin (let D-sqrt (sqrt D)
                              a-rcpr (/ (* 2.0 a))
                              tp     (* (+ (- b) D-sqrt) a-rcpr)
                              tm     (* (- (- b) D-sqrt) a-rcpr))
                         (Roots (min tp tm) (max tp tm))))))))

; Здесь, в отличии от оригинала, mu - обязательный параметр
(let gauss-random
     (lambda sigma mu
       (begin
         (let next (lambda (list (rand) (* 1.7156 (- (rand) 0.5))))
              loop (lambda u v
                     (begin
                       (let x (- u 0.449871)
                            y (+ (abs v) 0.386595)
                            q (+ (* x x) (* y (- (* 0.196 y) (* 0.25472 x)))))
                       (if (and (> q 0.27597)
                                (or (> q 0.27846) (> (* v v) (* -4 (log u) u u))))
                         (apply loop (next))
                         (+ mu (/ (* sigma v) u))))))
         (apply loop (next)))))

; В потоковой версии изменений почти нет. Но если let - потоковая конструкция,
; то можно отказаться от bind, внеся в let эту функциональность.
(let distributed-matrix-mul
     (lambda R A B
             (for (lambda i j k (run matrix-block-mul (zip 'i.j) (pin A 'i.k) (pin B 'k.j)))
                  (range l)
                  (range n)
                  (range m))

             (let sum-loop
                  (lambda result r-sum r-blocks n-blocks
                          (if (= 0 n-blocks)
                              (run let result (pin sum))
                              (begin (run matrix-block-add (! pin :sum) (pin r-sum) (zip r-block))
                                     (run sum-loop result (? pin :sum) (r-blocks) (- n-blocks 1))))))

             (for (lambda i j (run sum-loop (pin R 'i.j) (zero-matrix) (? zip 'i.j) m))
                  (range m)
                  (range l))))

; Косяки и недостатки этого варианта:
;
; 1. В процедурах, которые вычисляют значения, а не поток данных необходим
; дополнительный синтаксис, чтобы возвращать именно значения. Например, как
; begin выше, у которого может быть семантика такая: если в конце блока стоит
; вычисление значения, это значение нужно и вернуть. Эту семантику можно описать
; в R3. Но сам код вычисления значений, особенно математический, получается
; неудобным со множеством begin-ов. В целом конструкция усложняется.
;
; 2. В таком стиле не описать процедуры, работающие с неопределённым числом
; параметров. Точнее, наверное, можно что-нибудь придумать, но вряд ли это будет
; красиво. А такие процедуры весьма удобны в математике. Можно посмотреть на
; вычисление q в примерах выше.
;
; 3. Слишком широкий текст получается. Слишком большие отступы до конструкций
; тел функций. Для математики это не особо важно. Но удобство написания кода и
; его чтения существенно падает.
;
; Этот вариант хорошо вписывается в модель R3. Но неудобен для описания
; вычислительных функций.

; ВАРИАНТ ДВА. Синтаксис примерно такой:
; (lambda i1 ... in E)
; (let i1 e1 ... i1 en E)
;
; С небольшим числом скобок, но let теперь формирует значение, описываемое
; последним выражением. Для стилистической согласованности в lambda тоже только
; одно выражение в теле. Но так как let теперь не потоковая конструкция, для
; формирования значений в потоке (и для объявления того, что выглядит, как
; переменная) нужен оператор bind, который, может называться и define, как в
; Scheme. Всё выглядит примерно так

(define solve-square-equation
  (lambda a b c
    (if (zero? a)
      (if (not (zero? b))
        (let t (/ (- c) b) (Roots t t)))
      (let D (- (* b b) (* 4.0 a c))
        (if (<= 0.0 D)
          (let D-sqrt (sqrt D)
               a-rcpr (/ (* 2.0 a))
               tp     (* (+ (- b) D-sqrt) a-rcpr)
               tm     (* (- (- b) D-sqrt) a-rcpr)
            (Roots (min tp tm) (max tp tm))))))))

(define gauss-random
  (lambda sigma mu
    (let next (lambda (list (rand) (* 1.7156 (- (rand) 0.5))))
         loop (lambda u v
                (let x (- u 0.449871)
                     y (+ (abs v) 0.386595)
                     q (+ (* x x) (* y (- (* 0.196 y) (* 0.25472 x))))
                  (if (and (> q 0.27597)
                           (or (> q 0.27846) (> (* v v) (* -4 (log u) u u))))
                    (apply loop (next))
                    (+ mu (/ (* sigma v) u)))))
      (apply loop (next)))))

(define distributed-matrix-mul
  (lambda R A B
    (begin
      (for (lambda i j k (run matrix-block-mul (zip 'i.j) (pin A 'i.k) (pin B 'k.j)))
           (range l)
           (range n)
           (range m)))
      (let sum-loop
           (lambda result r-sum r-blocks n-blocks
             (if (= 0 n-blocks)
               (run define result (pin sum))
               (begin (run matrix-block-add (! pin :sum) (pin r-sum) (zip r-block))
                      (run sum-loop result (? pin :sum) (r-blocks) (- n-blocks 1)))))
        (for (lambda i j (run sum-loop (pin R 'i.j) (zero-matrix) (? zip 'i.j) m))
             (range m)
             (range l)))))

; В принципе, неплохой вариант. И проблемы с неопределённым списком параметров
; функции он решает, потому что тело -- это всего последнее выражение в lambda,
; поэтому остальное содержимое может быть оформлено, как угодно.
;
; Но есть проблемы восприятия, написания и редактирования кода. В потоковых
; функциях, обычно, стоит множество операторов формирования этого потока. Много
; run и define. И для таких функций в большинстве случаев необходимо будет
; писать (lambda x1 ... xn (begin ...)), что несколько напрягает чувство
; прекрасного. Кроме того, в таком варианте превращение тела функции (ну, или
; тела let) из одного оператора в тело из нескольких, будет нетривиальной
; задачей. Появятся висящие begin-ы, как это происходит в Си, когда все начинают
; писать (или требовать прямо в синтаксисе) if (x) { ... }, даже если в фигурных
; скобках один оператор.
;
; Можно, в принципе, засахарить define в стиле Scheme и использовать конструкцию
; (define (name x1 ... xn) ...). Но тогда синтаксис обычной lambda и такого
; define будут существенно несогласованы. И перенос кода из одной конструкции в
; другую будет осложнён. Но можно поменять lambda и let.

; ВАРИАНТ ТРИ. Синтаксис вида:
; (lambda (x1 ... en) E1 ... Ek) 
; (let (x1 e1 ... xn en) E1 ... Ek)
;
; Скобок больше, зато begin не нужен. Синтаксис (define (fn x1 ... xn) E1 ...
; Ek) будет согласован с lambda. Можно использовать. Выглядеть всё будет
; примерно так.

(define (solve-square-equation a b c)
    (if (zero? a)
      (if (not (zero? b))
        (let (t (/ (- c) b)) (Roots t t)))
      (let (D (- (* b b) (* 4.0 a c)))
        (if (<= 0.0 D)
          (let (D-sqrt (sqrt D)
                a-rcpr (/ (* 2.0 a))
                tp     (* (+ (- b) D-sqrt) a-rcpr)
                tm     (* (- (- b) D-sqrt) a-rcpr))
            (Roots (min tp tm) (max tp tm)))))))

(define (gauss-random sigma mu)
  (let (next (lambda () (list (rand) (* 1.7156 (- (rand) 0.5))))
        loop (lambda (u v)
               (let (x (- u 0.449871)
                     y (+ (abs v) 0.386595)
                     q (+ (* x x) (* y (- (* 0.196 y) (* 0.25472 x)))))
                 (if (and (> q 0.27597)
                          (or (> q 0.27846) (> (* v v) (* -4 (log u) u u))))
                   (apply loop (next))
                   (+ mu (/ (* sigma v) u))))))
    (apply loop (next))))

(define (distributed-matrix-mul R A B)
  (for (lambda (i j k) (run matrix-block-mul (zip 'i.j) (pin A 'i.k) (pin B 'k.j)))
       (range l)
       (range n)
       (range m))
  (let (sum-loop
        (lambda (result r-sum r-blocks n-blocks)
          (if (= 0 n-blocks)
            (run define result (pin sum))
            (begin (run matrix-block-add (! pin :sum) (pin r-sum) (zip r-block))
                   (run sum-loop result (? pin :sum) (r-blocks) (- n-blocks 1))))))
    (for (lambda (i j) (run sum-loop (pin R 'i.j) (zero-matrix) (? zip 'i.j) m))
         (range m)
         (range l))))

; Технически, это хороший вариант. И скобок не так много. Но есть проблема с
; восприятием. Возможно, это моя персональная проблема. Плохо воспринимаются
; такие вот висяки:
;
; (let (x ...
;       y ...
;
; (let (next ...
;       loop
;       (lambda (u v) ...)
;
; После некоторого опыта чтения и написания кода на Lisp конструкция вида (x
; очень отчётливо мозгом воспринимается, как начало некой целой формы, которая
; должна редуцироваться в некоторое значение. Поэтому мозг throttle-ится немного
; при чтении таких конструкций. Выходом может быть использование [] в стиле
; Clojure. Но в таком стиле, всё равно, не хватает какой-то сгруппированности,
; что ли, переменной со своим значением. Плюс в таком синтаксисе, выравнивание
; выглядит грубо. В столбик, без явного обозначения, что к чему относится:

(let (next
      (lambda () (list (rand) (* 1.7156 (- (rand) 0.5))))

      loop
      (lambda (u v)
        (let (x (- u 0.449871)
              y (+ (abs v) 0.386595)
              q (+ (* x x) (* y (- (* 0.196 y) (* 0.25472 x)))))
          (if (and (> q 0.27597)
                   (or (> q 0.27846) (> (* v v) (* -4 (log u) u u))))
            (apply loop (next))
            (+ mu (/ (* sigma v) u))))))
  (apply loop (next)))

; Необходимо вносить вертикальные разрывы в код. Или делать так:

(let (next
        (lambda () (list (rand) (* 1.7156 (- (rand) 0.5))))
      loop
        (lambda (u v)
          (let (x (- u 0.449871)
                y (+ (abs v) 0.386595)
                q (+ (* x x) (* y (- (* 0.196 y) (* 0.25472 x)))))
            (if (and (> q 0.27597)
                     (or (> q 0.27846) (> (* v v) (* -4 (log u) u u))))
              (apply loop (next))
              (+ mu (/ (* sigma v) u))))))
  (apply loop (next)))

; Группировка loop со своей lambda воспринимается плохо. Поэтому, скажу «нет»
; стилю Пола Грэма (он его в Arc предложил).

; ВАРИАНТ ЧЕТЫРЕ. Вполне может быть, что это всё было продумано уже 100 раз в
; Lisp сообществе. И вполне себе можно остаться с классическим стилем. Скобок в
; нём больше, но неким странным образом он читается и воспринимается лучше.
; Поэтому, классика:

(define (solve-square-equation a b c)
  (if (zero? a)
    (if (not (zero? b))
      (let ((t (/ (- c) b)))
        (Roots t t)))
    (let D (- (* b b) (* 4.0 a c))
      (if (<= 0.0 D)
        (let ((D-sqrt (sqrt D))
              (a-rcpr (/ (* 2.0 a)))
              (tp (* (+ (- b) D-sqrt) a-rcpr))
              (tm (* (- (- b) D-sqrt) a-rcpr)))
          (Roots (min tp tm) (max tp tm)))))))

(define (gauss-random sigma mu)
  (let ((next (lambda () (list (rand) (* 1.7156 (- (rand) 0.5)))))
        (loop
          (lambda (u v)
            (let ((x (- u 0.449871))
                  (y (+ (abs v) 0.386595))
                  (q (+ (* x x) (* y (- (* 0.196 y) (* 0.25472 x))))))
              (if (and (> q 0.27597)
                       (or (> q 0.27846) (> (* v v) (* -4 (log u) u u))))
                (apply loop (next))
                (+ mu (/ (* sigma v) u)))))))
    (apply loop (next))))

(define (distributed-matrix-mul R A B)
  (for (lambda (i j k) (run matrix-block-mul (zip 'i.j) (pin A 'i.k) (pin B 'k.j)))
       (range l)
       (range n)
       (range m))
  (let ((sum-loop
          (lambda (result r-sum r-blocks n-blocks)
            (if (= 0 n-blocks)
              (run define result (pin sum))
              (begin (run matrix-block-add (! pin :sum) (pin r-sum) (zip r-block))
                     (run sum-loop result (? pin :sum) (r-blocks) (- n-blocks 1)))))))
    (for (lambda (i j) (run sum-loop (pin R 'i.j) (zero-matrix) (? zip 'i.j) m))
         (range m)
         (range l))))

; А ещё, в качестве шутки, может быть какой-нибудь забавная греко-славянская
; типизированная ересь:

(тип (при ((дробное t)) (одно-из (λ (t) t) (λ (t t) t))) случайная-Гаусса)
(это случайная-Гаусса 
     (λ (σ) (случайная-Гаусса σ 0))
     (λ ((тип t σ) μ)
        (при ((проба (λ () (n-ка (тип t (случайная))
                                 (* 1.7156 (- (тип t (случайная)) 0.5)))))
              (тест (λ ((n-ка u v))
                       (при ((x (- u 0.449871))
                             (y (+ (abs v) 0.386595))
                             (q (+ (* x x)
                                   (* y (- (* 0.196 y) (* 0.25472 x)))))))
                            (если (∧ (> q 0.27597)
                                     (∨ (> q 0.27846)
                                        (> (* v v) (* -4 (log u) u u))))
                                  (тест (проба))
                                  (+ μ (/ (* σ v) u))))))
           (тест (проба))))) 

; Но, всё же, всё же, почему-то тянет на размышления и о таком «лёгком»
; синтаксисе.

(тип (при (дробное t)
          (одно-из (λ t t) (λ t t t))) случайная-Гаусса)
(это случайная-Гаусса
  (одно-из
    (λ σ (случайная-Гаусса σ 0))
    (λ (тип t σ) μ
       (при вход (λ (n-ка (тип t (случайная))
                           (* 1.7156 (- (тип t (случайная))) 0.5)))
            тест (λ (n-ка u v)
                    (при x (- u 0.449871)
                         y (+ (abs v) 0.386595)
                         q (+ (* x x)
                              (* y (- (* 0.196 y) (* 0.25472 x))))
                      (если (∧ (> q 0.27597)
                               (∨ (> q 0.27846)
                                  (> (* v v) (* -4 (log u) u u))))
                        (тест (вход))
                        (+ μ (/ (* σ v) u)))))
         (тест (вход))))))

; Фишечка в том, что всё же нам нужны begin-ы или аналоги в распределённом
; окружении. Потому что они должны проходить через какой-то процесс или монадку.
; Ладно. Главное, что удалось хотя бы сократить количество вариантов к 2.

(это solve-square-equation
  (λ a b c
     (если (ноль? a)
       (если (не (ноль? b))
         (при t (/ (- c) b) (Roots t t)))
       (при D (- (* b b) (* 4.0 a c))
         (если (<= 0.0 D)
           (при D-sqrt (sqrt D)
                a-rcpr (/ (* 2.0 a))
                tp (* (+ (- b) D-sqrt) a-rcpr)
                tm (* (- (- b) D-sqrt) a-rcpr)
             (Roots (min tp tm) (max tp tm))))))))

(define solve-square-equation
  (lambda a b c
    (if (zero? a)
      (if (not (zero? b)) (let t (/ (- c) b) (Roots t t)))
      (let D (- (* b b) (* 4.0 a c))
        (if (<= 0.0 D)
          (let D-sqrt (sqrt D)
               a-rcpr (/ (* 2.0 a))
               tp (* (+ (- b) D-sqrt) a-rcpr)
               tm (* (- (- b) D-sqrt) a-rcpr)
            (Roots (min tp tm) (max tp tm))))))))

(define (solve-square-equation a b c)
  (if (zero? a)
    (if (not (zero? b)) (let ((t (/ (- c) b))) (Roots t t)))
    (let ((D (- (* b b) (* 4.0 a c))))
      (if (<= 0.0 D)
        (let ((D-sqrt (sqrt D))
              (a-rcpr (/ (* 2.0 a)))
              (tp (* (+ (- b) D-sqrt) a-rcpr))
              (tm (* (- (- b) D-sqrt) a-rcpr)))
          (Roots (min tp tm) (max tp tm)))))))

; Хорошо. Вот такое сопоставление довольно эмс... Внушительно