Simpson's Integral in Common Lisp

Question

Hello all,

I just wrote a simple Common Lisp program to find out Simpson's Integral:

;Integration by Simpson's rule; CL code
;Found to be working correctly with 'clisp'

(defun simpsons(f a b n)

  (defparameter *summation* 0)
  (defvar *h* (/ (- b a) n))
  (loop for k from 2 below (- n 1) by 2 do
     (setf *summation* (+ *summation* (* 2 (funcall f (+ (* k *h*) a))))

    ))
   (loop for k from 1 below n by 2 do
     (setf *summation* (+ *summation* (* 4 (funcall f (+ (* k *h*) a))))

    ))

  (setf *summation* (+ (funcall f a) (funcall f (+ (* n *h*) a))))

  (format t "~d" (* (/ *h* 3.0) *summation*)) 

  ) 

(defun cube(x)
  (* x x x))

;Passing around the function to be integrated

(simpsons 'cube 2 3 8) ;demonstrating higher-order functions

I would like your advice, on the code quality. Like the style of programing, etc. I am from a C/C++, Python, Java background.

Just a small point, my Common Lisp knowledge is till Chapter 10 of Practical Common Lisp

Thanks!

Answer 1

Important edit: You probably have a bug in your function. I do not know about Simpson’s method and can not correct it. But you are calculating some value into *summation* but at the end you forget everything about your computing and only return the result like you had defined:

(defun simpsons (f a b n)
  (let ((h (/ (- b a) n)))
    (* (/ h 3.0) (+ (funcall f a) (funcall f (+ (* n h) a))))))

defparameter and defvar are meant to define so called “special” variables. Here you need bindings that are local to your function ; let would be better suited.

What’s more defvar only assigns the variable if it is not already assigned. That means that if you call your function multiple times with different values you will get wrong results.

Regarding style lispers would make the function return the value, not print it. Just calling it in the interactive environment will print the result. And you can also use (trace simpsons) to see how your function is called and its output.

Do not put closing parentheses on a line by themselves.

Finally people usually use two semicolons for comments on a line by itself while they use a single semicolon for comments at the end of the line.

Here is your function with these applied:

;; Integration by Simpson's rule; CL code
;; Found to be working correctly with 'sbcl'

(defun simpsons (f a b n)
  (let ((summation 0)
        (h (/ (- b a) n)))
    (loop for k from 2 below (- n 1) by 2
      do (setf summation (+ summation (* 2 (funcall f (+ (* k h) a))))))
    (loop for k from 1 below n by 2
      do (setf summation (+ summation (* 4 (funcall f (+ (* k h) a))))))
    (setf summation (+ (funcall f a) (funcall f (+ (* n h) a))))
    (* (/ h 3.0) summation)))

(defun cube(x)
  (* x x x))

;; Passing around the function to be integrated

(simpsons 'cube 2 3 8)    ; demonstrating higher-order functions

Explaination on let: let defines a new lexical binding. That is

(let ((summation 0)) …)

makes the name summation bound to the value 0 in the body of the let expression. The setf expressions changes a place which can be a bit complex to describe (see CLHS: Section 5.1 Generalized Reference). In the context

(let ((summation 0))
  (setf summation (+ summation 1)))

it changes the binding of summation from the value 0 to the value 1. While using

(let ((summation 0))
  (let ((summation (+ summation 1)))
    ;; Here summation is bound to the value 1
    …)
  ;; Here summation is bound to the value 0
  …)

makes two lexical bindings for summation, the first to the value 0 and the second, shadowing the first for the extent of the second let, to the value 1.

Answer 2

What I would add to kmkaplan's answer is that in Lisp programs a bit more functional style is often preferred (but not required though). Also, you can use numeric accumulation clause sum of the LOOP macro.

(defun simpsons (f a b n)
  (let ((h (/ (- b a) n)))
    (* (/ h 3)
       (+ (* 2 (loop for k from 2 below (- n 1) by 2
                     sum (funcall f (+ a (* h k)))))
          (* 4 (loop for k from 1 below n by 2
                     sum (funcall f (+ a (* h k)))))
          (funcall f a) (funcall f b)))))

(defun cube (x) (expt x 3))

Here's a CL rewrite of Python implementation provided at the Wikipedia page, for the sake of completeness:

(defun simpsons1 (f a b &optional (n 2))
  (assert (plusp n) () "n must be positive")
  (unless (evenp n) (incf n))
  (let ((h (/ (- b a) n)))
    (* (/ h 3)
       (+ (loop repeat (1- n)
                for x from (+ a h) by h
                for m = 4 then (- 6 m)
                sum (* m (funcall f x)))
          (funcall f a)
          (funcall f b)))))

Answer 3

The most important things have already been noted, so here are some minor things:

1. I'd change the name.

   It's not very helpful because it doesn't really say what it does, only how it is implemented.

   I recommend INTEGRATE/SIMPSON as name.

   That way you can build a collection of integration functions by algorithm.

2. ;Found to be working correctly with 'clisp' -- it's okay for a beginner to do this, but as you are progressing you should check parts about which you are not sure against the specification.

3. You forgot the documentation string after the function signature.

Answer 4

The DEFPARAMETER and DEFVAR within the fuinction body are, ahem, not ideal.

Unless you ALWAYS want I/O on calling your integration function, skip the FORMAT.

The repeated use of SETF is, ahem, not very elegant (and in this case only serves to obscure the code).

A slightly better version would be:

(defun simpsons(f a b n)
 (let ((h (/ (- b a) n)))
   (+ (loop for k from 2 below (- n 1) by 2 do
        sum (* 2 (funcall f (+ (* k *h*) a))))
      (loop for k from 1 below n by 2 do
        sum (* 4 (funcall f (+ (* k *h*) a))))

      (funcall f a)
      (funcall f (+ (* n *h*) a)))))

Answer 5

As mentioned before:

Learn the comment conventions. One semicolon for an end-of-line comment, two through four (depending on importance) for full-line comments.

Make sure your editor handles parentheses and indentation for you. Otherwise, it'll be a real pain. I find that function almost unreadable, since it's not formatted like I'm used to and the human brain doesn't parse parentheses well. Emacs format is the standard.

Given a function, return the value returned. As in any language, calculation functions should return their answer, with no user-visible side effects.

Use local variables inside functions. This helps avoid side effects.

If you're going to use the loop macro, study it a bit more. It does have summation built in.

In general, hunt down some sort of Lisp style guide. It isn't that Lisp style is deliberately obscure, but Lisp looks different from most languages, and you're unlikely to hit on good style conventions by chance.

The best book I've read on writing serious Lisp code is Norvig's Paradigms of Artificial Intelligence Programming. If you like, think of it as a Lisp programming book with all the examples from the AI field (it works better that way than thinking of it as an AI book that uses Lisp). There may be better, but I haven't read them yet. If nothing else, Paul Graham's book On Lisp is, last I looked, available free under www.paulgraham.com. It's also an excellent book, but with a different focus than Norvig's.

Answer 6

A straight rewrite for clarity would produce (in the style I tend to write with):

(defun simpsons(f a b n)
  "ADD A DOC STRING!"
  (let ((summation 0)
        (h (/ (- b a) n)))
    (loop for k from 2 below (- n 1) by 2 do
      (incf summation (* 2 (funcall f (+ (* k h) a)))))
    (loop for k from 1 below n by 2 do
      (incf summation (* 4 (funcall f (+ (* k h) a)))))
    ;; I assume the below is a mistake, as it completely overwrites all your prior results. Or, if
    ;; it isn't a mistake, then just remove all the previous stuff.
    (setf summation (+ (funcall f a) (funcall f (+ (* n h) a))))
    (format t "~d" (* (/ h 3.0) *summation*))))

Further, you have that bug at the end (setting summation to something which doesn't rely on its prior value... see my comment in the code above).

As far as making an efficient algorithm, I'm sure you could find some ways to refactor those loops into a single loop? (If you are looking for more efficiency). There are other things you could also do to increase the efficiency (such as refactoring the iterations similar to what is done here with generic iterations: http://fare.tunes.org/files/fun/fibonacci.lisp.

Even more concise:

(defun simpsons(f a b n)
  "ADD A DOC STRING!"
  (let ((h (/ (- b a) n)))
    (loop with first-sum = (loop for k from 2 below (- n 1) by 2 sum (* 2 (funcall f (+ (* k h) a))))
          for k from 1 below n by 2 sum (* 4 (funcall f (+ (* k h) a))) into second-sum
          finally
          ;; do whatever you meant to do with the last setf call which overwrote summation
          (setf third-sum? (stuff))
          ;; then...
          (format t "~d" (* (/ h 3.0) (+ first-sum second-sum third-sum))))))