Converting a Scheme function to Emacs Lisp

Question

I am taking efforts to rephrase an example from SICP

 #+BEGIN_SRC scheme
(define (average-damp f)
  (lambda (x) (average x (f x))))
(define (average x y)
  (/ (+ x y) 2))
(define (square x)
  (* x x))
((average-damp square) 10)
#+END_SRC

#+RESULTS:
: 55

After spent hours on it and got

(defun average-damp (f)
  (lambda (x) (average x (funcall f x))))

(defun average (x y)
  ;; Keep the float
  (/ (+ x y) 2.0))

(defun square (x)
  (* x x))

(funcall #'(average-damp 'square) 10)

Still report error invalid function, yet I am lost

Could you please provide any hints?

Answer 1

You are almost there. There are only two little details you need to take care of:

1. Remove the quoting #' in (funcall #'(average-damp 'square) 10). You do want to eval average-damp and give you the actual function for the funcall. That is what Aquaactress correctly statet as problem 1.

2. For the form

      (defun average-damp (f)
        (lambda (x) (average x (funcall f x))))
   

   to work you need lexical binding. The argument list of average-damp goes into its lexical environment. You can refer to that variable in the lambda that is within the lexical environment of average-damp. So your source block defining average-damp should have the :lexical t header argument. It should look like follows:

   #+begin_src emacs-lisp :lexical t
      (defun average-damp (f)
        (lambda (x) (average x (funcall f x))))
   #+end_src
   

Answer 2

There are two problems I found with the code you wrote.

problem 1

(funcall #'(average-damp 'square) 10)

funcall requires a function as it's first argument. However, here you're trying to pass in the unevaluated list (average-damp 'square) as if it were a function. But it's not, it's data.

Remember that #' is a shorthand for function and function does not evaluate it's arguments (see anonymous functions). So it does not evaluate (average-damp 'square).

problem 2

The other problem is your definition of average-damp.

(defun average-damp (f x)
  (lambda (x) (average x (funcall f x))))

lambda does not evaluate it's body. Therefore the f that you're passing into average-damp won't end up replacing the f in (funcall f x) which it seems like is what you want.

As an illustration, this is what your version of average-damp returns when passed in with square.

(average-damp 'square) ;=> (lambda (x) (average x (funcall f x)))

Note that the f still hasn't been replaced with square.

Consequently, when the lambda this function is called, it won't know what f is (unless you defined a global variable f) and you're bound to get a Symbol's value as variable is void: f error.

solution

To address problem 2 you can use backquote to ensure that the value of average-damp's parameter, f, is replaced with square.

And to address problem 1, you should remove the #'. You don't need it because you want (average-damp 'square) to be evaluated so that it returns a function, which is what funcall requires as it's first argument.

(defun average-damp (f)
  `(lambda (x) (average x (funcall #',f x))))

(funcall (average-damp 'square) 10) ;=> 55.0

Answer 3

You can not enter x value to (average-damp ) in your code.

You should declare x as a function argument or define (average-damp ) as a macro.

(defun average-damp (f x)
  (average x (funcall f x)))

(defmacro average-damp2 (f)
  `(lambda (x) (average x (funcall ,f x))))

(defun average (x y)
  ;; Keep the float
  (/ (+ x y) 2.0))

(defun square (x)
  (* x x))

;; using function
(funcall #'average-damp #'square 10);; => 55.0
(average-damp #'square 10);; => 55.0

;; using macro
((lambda (x) (average x (square x))) 10);; => 55.0
(funcall (average-damp2 #'square) 10);; => 55.0