schemelisp

How to use symbolic expressions produced by a function to define another function?


I am trying to make a symbolic derivation function in Chez scheme. It works alright-ish (simplification is not yet being done):

(define (derive var expr)
;; var is the direction in which you would like to derive
  (if (list? expr)
      (case (car expr)
        ('+    (sum-rule var expr))
        ('-    (sub-rule var expr))
        ('*    (prod-rule var expr))
        ;; other rules
        (else  (atomic-rule var expr )))
      (atomic-rule var expr)))

(define (atomic-rule var expr)
  (if (list? expr)
      expr
      (if (eqv? var expr)
          1
          0)))

(define (sum-rule var expr)
  (let ((args (cdr expr)))
    `(+ ,@(map (lambda (e) (derive var e)) args))))

(define (sub-rule var expr)
  (let ((args (cdr expr)))
    `(- ,@(map (lambda (e) (derive var e)) args))))

(define (prod-rule var  expr)
  (let* ((args (cdr expr))
         (f (car args))
         (g (cadr args)))
    `(+ (* ,f ,(derive var g))
        (* ,g ,(derive var f)))))

I can do(derive 'x '(+ (* x x) (* x y))) and get (+ (+ (* x 1) (* x 1)) (+ (* x 0) (* y 1))) which is correct. But I'd also like to programmatically create functions that return numerical values from those expressions.

My attempts have failed:

(define (lambda-derive var expr)
  (let ([derivative (derive var expr)])
    (lambda (var) derivative)))

((lambda-derive 'x '(* x x)) 2) => (+ (* x 1) (* x 1)) ;; should be 4

(define-syntax lbd-macro
  (lambda (context)
    (syntax-case context ()
      [(k expr var )
       (with-syntax ([new-var (datum->syntax #'k (syntax->datum #'var))])
         #'(lambda (new-var) expr))])))


((lbd-macro (derive 'x '(* x x)) x) 2) => (+ (* x 1) (* x 1)) ;; should be 4

I feel like I am missing something very obvious. Can someone provide a light? (Yes I know the attempts do not cover multi-variate cases)

==EDIT==

I had a bad night of sleep and decided to keep working, and I've arrived in a similar solution to what @ignis volens described, albeit using hash-tables and being way more hacky:

(define (lambda-aux variables vals expr)
  (let ((ht (make-eqv-hashtable (length variables))))
    (for-each (lambda (k v) (hashtable-set! ht k v)) variables vals)
    (let loop ((expr expr))
      (if (list? expr)
          (let ((op (car expr))
                (args (map loop (cdr expr))))
            (cons op args))
          (let ((variable (hashtable-ref ht expr #f)))
            (if variable
                variable
                (if (number? expr)
                    expr
                    (error "variable not found"))))))))

(define-syntax lambda-derive
  (syntax-rules ()
    [(_ expr var var* ...)
     (lambda (var var* ...) (eval (lambda-aux '(var var* ...) (list var var* ...) (derive 'var 'expr) )))]))

Which can be used like so:

(define my-test-derivative
  ;;f(x,y) = x^2 + x * y
  ;;df/dx (x,y) = 2*x + y
  (lambda-derive (+ (* x y) (* x x)) x y))
(my-test-derivative 2 2) => 6
(my-test-derivative 8 2) => 18
;; ...

Solution

  • This is a case where you either want to clench your teeth and use eval:

    (eval `(lambda (x) ,(derive 'x '(* x x))) (scheme-report-environment 5))
    

    will return a function of one argument which will evaluate the derivative of (* x x) for a given value of x (I am assuming R5RS here, as I don't have Chez Scheme):

    > (let ((d (eval `(lambda (x) ,(derive 'x '(* x x))) (scheme-report-environment 5))))
        (d 1))
    2
    

    Or, arguably better (and certainly more safely) you can write a symbolic expression evaluator. Again this is R5RS:

    (define (evaluate-symbolic-expression expression bindings)
      ;; Evaluate a symbolic expression in the presence of bindings
      (cond
        ((number? expression)
         expression)
        ((symbol? expression)
         (let ((found (assq expression bindings)))
           (if found
               (evaluate-symbolic-expression (cadr found) bindings)
               expression)))
        ((pair? expression)
         (apply-symbolic-operator
          (car expression)
          (map (lambda (e) (evaluate-symbolic-expression e bindings))
               (cdr expression))
          bindings))
        (else
         expression)))
    
    (define (all-numbers? l)
      (cond
        ((null? l)
         #t)
        ((number? (car l))
         (all-numbers? (cdr l)))
        (else
         #f)))
    
    (define (apply-symbolic-operator op args bindings)
      (if (all-numbers? args)
          (let ((f (assq op bindings)))
            (if f
             (apply (cadr f) args)
             `(,op ,@args)))
          `(,op ,@args)))
    
    (define arithmetic-operator-bindings
      `((+ ,+)
        (- ,-)
        (* ,*)
        (/ ,/)))
    

    And now

    > (evaluate-symbolic-expression
       (derive 'x '(* x x))
       (append '((x 4)) arithmetic-operator-bindings))
    8
    

    evaluate-symbolic-expression could be more clearly written: it started off implementing an evaluator for what was essentially a tiny Lisp-2, but I changed it and was too lazy to redo it all.