Цитирование в языках программирования
Задача
Задачу я встретил, решая упражнения из книги Структура и Интерпретация Компьютерных Программ). Обычно её называют 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 left
let right = Expr.Cast right
<@ %left + %right @> :> Expr
let make_prod left right =
let left = Expr.Cast left
let right = Expr.Cast 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 left
let right = Expr.Cast 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 square = x => x * x;
sqaure(2) // 4 Выражения, которые приводятся к типу Expression, складываются в древовидную структуру, которую мы сможем потом обработать.
Expression> expSquare = x => x * x;
expSquare.Compile()(2) // 4 Деревья выражений хорошо знакомы многим программистам на C#, поскольку они применяются в библиотеке Entity Framework. Однако, с помощью их можно делать и более сложную обработку.
Вот функция, которая получает на вход лямбда-функцию и применяет её к самой себе.
static Expression> DoubleFunc(Expression> f)
{
var parameter = Expression.Parameter(typeof(double));
var inner = Expression.Invoke(f, parameter);
var outer = Expression.Invoke(f, inner);
return Expression.Lambda>(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)Symbolic.Derivative(x => x * x).Compile();
d(17)
// => 34 