Цитирование в языках программирования

Задача

Задачу я встретил, решая упражнения из книги Структура и Интерпретация Компьютерных Программ). Обычно её называют SICP (читается сик-пи) — это аббревиатура названия на английском языке.

Раздел 2.3 посвящён цитированию в LISP и символическим вычислениям.

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

Подгоняя , мы можем вычислить производную с хорошей точностью.

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

При значение производной будет абсолютно точно равно .

Реализация на Scheme

SICP предлагает вычислять производную с помощью цитирования. По-английски этот механизм называется quotation.

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

(+ (/ 1 1) (/ 1 1) (/ 1 2) (/ 1 6) (/ 1 24) (/ 1 120) (/ 1 720) (/ 1 5040)) ; => 2.7182539682539684

Но если мы предваряем его кавычкой (quote), Scheme сохраняет выражение в виде списка, не вычисляя.

'(+ (/ 1 1) (/ 1 1) (/ 1 2) (/ 1 6) (/ 1 24) (/ 1 120) (/ 1 720) (/ 1 5040)) ; => (+ (/ 1 1) (/ 1 1) (/ 1 2) (/ 1 6) (/ 1 24) (/ 1 120) (/ 1 720) (/ 1 5040))

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

Вот простая функция, которая строит производную сумм и произведений.

(define (variable? x) (symbol? x)) (define (same-variable? v1 v2)   (and (variable? v1) (variable? v2) (eq? v1 v2))) (define (make-sum a1 a2) (list '+ a1 a2)) (define (make-product m1 m2) (list '* m1 m2)) (define (sum? x)   (and (pair? x) (eq? (car x) '+))) (define (addend s) (cadr s)) (define (augend s) (caddr s)) (define (product? x)   (and (pair? x) (eq? (car x) '*))) (define (multiplier p) (cadr p)) (define (multiplicand p) (caddr p))  (define (deriv exp var)   (cond ((number? exp) 0)         ((variable? exp)          (if (same-variable? exp var) 1 0))         ((sum? exp)          (make-sum (deriv (addend exp) var)                    (deriv (augend exp) var)))         ((product? exp)          (make-sum           (make-product (multiplier exp)                         (deriv (multiplicand exp) var))           (make-product (deriv (multiplier exp) var)                         (multiplicand exp))))         (else          (error "Unknown expression type"))))

Очевидным недостатком функции является сложность получаемых выражений.

(deriv '(+ x 3) 'x) ; => (+ 1 0), это означает 1 + 0  (deriv '(* x y) 'x) ; => (+ (* x 0) (* 1 y)), это озачает 0 * x + 1 * y  (deriv '(* (* x y) (+ x 3)) 'x) ; => (+ (* (* x y) (+ 1 0)) (* (+ (* x 0) (* 1 y)) (+ x 3))), а это вообще сложно

Их надо упрощать, для чего может быть написана отдельная функция. Упрощение выражений также рассматривается в SICP.

Реализация на F#

Цитирование на F# всё ещё похоже на цитирование.

let expSquare = <@ fun x -> x * x @> // => val expSquare : Quotations.Expr<(int -> int)> = Lambda (x, Call (None, op_Multiply, [x, x]))

Чтобы получить вместо кода его представление в виде сложного объекта, заключим код в своеобразные кавычки — <@ и @>.

Результатом будет значение типа Expr, с которым можно работать также, как с деревьями выражений в C#.

Вот простая функция, которая строит производную сумм и произведений.

open Microsoft.FSharp.Quotations open Microsoft.FSharp.Quotations.Patterns open Microsoft.FSharp.Quotations.DerivedPatterns  let  make_sum left right =     let left = Expr.Cast<float> left     let right = Expr.Cast<float> right      <@ %left + %right @> :> Expr      let make_prod left right =     let left = Expr.Cast<float> left     let right = Expr.Cast<float> right      <@ %left * %right @> :> Expr  let deriv (exp: Expr) =     match exp with     | Lambda(arg, body) ->         let rec d exp =             match exp with             | Int32(_) ->                 Expr.Value 0.0             | Var(var) ->                 if var.Name = arg.Name                 then Expr.Value 1.0                 else Expr.Value 0.0             | Double(_) ->                 Expr.Value 0.0             | SpecificCall <@ (+) @> (None, _, [left; right]) ->                 make_sum (d left) (d right)             | SpecificCall <@ (*) @> (_, _, [left; right]) ->                 let left = Expr.Cast<float> left                 let right = Expr.Cast<float> left                 make_sum (make_prod left (d right)) (make_prod (d left) right)             | _ -> failwith "Unknown expression type"          d body     | _ -> failwith "Expr.Lambda expected"  <@ fun (x: double) -> x * x @> // => Lambda (x, Call (None, op_Multiply, [x, x]))  deriv <@ fun (x: double) -> x * x @> // => Call (None op_Addition, //          [Call (None, op_Multiply, [x, Value (1.0)]), //           Call (None, op_Multiply, [Value (1.0), x])])

Реализация на C#

В C# существует аналог цитирования — деревья выражений. В отличие от F#, здесь нет специальных кавычек для выделения кода. Вместо этого мы указываем тип выражения Expression, а всё остальное делает механизм вывода типов.

Обычные выражения вычисляются сразу.

Func<double, double> square = x => x * x; sqaure(2) // 4

Выражения, которые приводятся к типу Expression, складываются в древовидную структуру, которую мы сможем потом обработать.

Expression<Func<double, double>> expSquare = x => x * x; expSquare.Compile()(2) // 4

Деревья выражений хорошо знакомы многим программистам на C#, поскольку они применяются в библиотеке Entity Framework. Однако, с помощью их можно делать и более сложную обработку.

Вот функция, которая получает на вход лямбда-функцию и применяет её к самой себе.

static Expression<Func<double, double>> DoubleFunc(Expression<Func<double, double>> f) {     var parameter = Expression.Parameter(typeof(double));     var inner = Expression.Invoke(f, parameter);     var outer = Expression.Invoke(f, inner);     return Expression.Lambda<Func<double, double>>(outer, parameter); }  var expFourth = DoubleFunc(expSquare);

Если два раза применить функцию возведения в квадрат к какому-то числу, мы получим возведение в четвёртую степень.

expFourth.Compile()(2) // 16

Я разработал пакет SySharp, который умеет генерировать производные функции по деревьям выражений. Исходный код пакета открыт.

Symbolic.Derivative(x => x * x).ToString() // => x => ((x * 1) + (1 * x))

Там же реализован код для упрощения выражений.

Symbolic.Derivative(x => x * x).Simplify().ToString() // => x => (2 * x)

В отличие от F#, в C# очень просто из дерева выражения получить работающий код.

var d = (Func<double, double>)Symbolic.Derivative(x => x * x).Compile(); d(17) // => 34