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

Задача

Задачу я встретил, решая упражнения из книги Структура и Интерпретация Компьютерных Программ). Обычно её называют 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