Integral Calculus in Lambda Calculus (Lisp) | Hacker News Reader

Integral Calculus in Lambda Calculus (Lisp)

jng.imagine27.com

18 pointsjgrant2720 comments

One other thing. The Lisp is rather non-idiomatic. Here is how I'd write it:

    (defparameter small-dx 0.00001)

    (defun integrate (f a b &optional (dx small-dx))
      "integrate a function f from a to b"
      (loop for x from a to b by dx sum (* dx (funcall f x))))

Then you can use it like:

    (flet ((f1 (x) 1)
           (f2 (x) (expt x 2))
           (f3 (x) (* x (exp (expt x 2)))))
      (format t "f1: ~A, f2: ~A, f3: ~A~%"
              (integrate #'f1 0 5)
              (integrate #'f2 0 5)
              (integrate #'f3 0 5)))

In conclusion, CL is not Scheme.

(Edit: Initially I said that the code doesn't compile. It does -- storing functions in the value slot of variables threw me off a bit. Very Scheme-like.)

The code compiles and runs just fine on any CL compiler. Try SBCL or CLozure CL.

Actually the loop macro in CL can be a very contentious topic. I'd hardly refer to the loop macro as idiomatic. Imperative and functional styles in CL can both be idiomatic.

Anyway who said CL was Scheme ?

Anyway who said CL was Scheme ?

Your style strongly hints at a Scheme background. Nothing you do is wrong, but if you read a bunch of Lisp code, you wouldn't see many people doing things the way you did. OTOH, if you read a bunch of Scheme code, it would look exactly like yours.

Also, I don't think the use of loop is a point of contention. LOOP is in the CL spec, tail recursion isn't. (The ITERATE package is a nicer loop, but the idea is the same.)

Interesting opinion regarding my style. Thanks for explaining. There are many things in the CL spec that are very contentious. Arguably too many. Dan Weinreb pointed this out earlier in the week(http://ilc2009.scheming.org/node/7) which inspired a response from me(http://jng.imagine27.com/articles/2009-04-07-135246_cl_hard_...) although not directly related to the "too many concepts, irregular" argument but then again this may effect how per formant/stable code can be written in a language.

Yes tail-recursion is not part of the spec along with many other implementation aspects that probably should be.

Good on you taking criticism so well jgrant27, testament to a mature mind.

Also, absence of tail-call elimination in the spec doesn't have to stop you from using it, if your compiler supports it. We all love Common Lisp, but usually not "warts and all"; we all end up using our personally "attractive" subset. I personally code in Dylan with s-exp notation that happens to compile under SBCL :-)

There's recursion and then there's tail recursion. Recursion is idiomatic of all functional languages. Using the loop macro as in your example is iterative and hence some of the contention about whether that is idiomatic for a functional language such as CL. Some would say that this is a a purist argument but some things are actually easier to write recursively.

I like the tail recursion, but it really would be more idiomatic in CL to write:

  (defun integrate (f a b &aux (dx *small-dx*))
    (labels ((rec (x sum)
               (if (> x b) sum
                   (rec (+ x dx) (+ sum (* (funcall f x) dx))))))
      (rec a 0)))

Absolutely not. Nested functions are LEXICALLY scoped in CL. Why the aversion ?

There is nothing wrong with your code, it's just that nobody else does it that way. Personally, I find code easier to read when it looks something like what I expect... but OTOH, it's very obvious what your code does too.

You know what? Screw the loop debate. The loop version of the integrate function is shorter and easier to understand. So what's wrong with it?

Nothing at all. The loop macro version is iterative and the original is recursive. However some things are easier to represent recursively than iteratively. That is if the programmer clearly understands recursion.

I would really impressed by seeing some kind of wacky function paired with a fixed point combinator so that when a function is integrable, the combinator spits out as a fixed point the answer.

There's a great bit about this in the first chapter of the SICP.

A fancy title for what amounts to addition and function evaluation.

What else does integration primarily entail ?

Symbolic integration would be much more interesting than Riemann sums.

agreed

I'm not going to implement that for you. Sorry.

See Norvig's "Paradigms of Artificial Intelligence Programming - Case Studies in Common Lisp", Chapter 8 - Symbolic Mathematics : A Simplification Program, 8.6 - Integration, page 252.

http://norvig.com/paip.html

Integration usually means symbolic integration. Numerical integration of the definite integral is usually referred to as Quadrature, or Numerical Integration:

http://en.wikipedia.org/wiki/Numerical_integration

That would depend on who's using the word "usually".

See Norvig's "Paradigms of Artificial Intelligence Programming - Case Studies in Common Lisp", Chapter 8 - Symbolic Mathematics : A Simplification Program, 8.6 - Integration, page 252.

http://norvig.com/paip.html

Reply on news.ycombinator.com