Re: Detecting Infinite Looping

Subject: Re: Detecting Infinite Looping
From: hanche+dsssl-l@xxxxxxxxxxxx
Date: Thu, 29 Jan 1998 19:12:46 +0100
- "W. Eliot Kimber" <eliot@xxxxxxxxxx>:

| At 09:40 AM 1/29/98 +0000, Henry Thompson wrote:
| >PS.  You can see the tail recursion more clearly by using a named 'let'
| >
| >(define f1
| > (lambda (arg)
| >  (let loop ((x arg)
| >             (result BASE))
| >    (if P
| >      result
| >     (loop NEXT (append result (list F)))))))
| 
| [...]
| 
| Also, what is the significance of the lamba in the above?

The definition is equivalent to

(define (f1 arg)
  (let loop ...))

so it defines a function, pure and simple.

| I've never been able to grasp the significance of using lamba
| instead of a simple let statement.

There is no difference at all between

((lambda (x) ...) y)

and

(let ((x y)) ...)

if that's what you mean -- though hardly anybody would prefer the
former.  The advantage of the lambda is that you can save it in a
variable and then use it in different places of your code, for various
values of y.

| I'm the sure the problem is with name lambda--it means nothing to me
| (at least with respect to mathematics--[...])

Well, it comes from lambda calculus, which is a branch of mathematical
logic.  Mathematicians often say things like "the function x->2x+3",
which means the function which, to any x, assigns the value 2x+3.
Much more rarely, they would come up with a computation like
(x->2x+3)(y-4)=2(y-4)+3=2y-5.  The lambda in lambda calculus is just
another notation for the same idea.  (In what follows, please
substitute a Greek lowercase letter lambda for the word "lambda".)  If
I write lambda x (2x+3), that would be the same function as x->2x+3.
The little computation alluded to above would now look like this:
(lambda x (2x+3))(y-4))=2(y-4)+3=2y-5.

In lambda calculus you would write up a whole set of rules for
formally manipulating lambda expressions, and you study the
consequences of those rules.  This forms the basis for a lot of
programming language theory.

On a more practical side, where a mathematician might say "define
f(x)=2x+3", a more formally minded person might insist that the
definition should read "let f=(x->2x+3)", or "let f=lambda x (2x+3)".
In Scheme, the corresponding definitions read

(define (f x) (+ (* 2 x) 3))
(define f (lambda (x) (+ (* 2 x) 3)))

and they are, like I said, totally equivalent.  Still, many people
(myself included) prefer the former, as it is closer to the classical
mathematicians way of presenting a function definition.

- Harald


 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist


Current Thread
  • Re: Detecting Infinite Looping, (continued)
    • Henry Thompson - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id EAA04681Thu, 29 Jan 1998 04:40:15 -0500 (EST)
    • Pawson, David - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id DAA29108Thu, 29 Jan 1998 03:02:52 -0500 (EST)
    • Gavin Nicol - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id FAA05174Thu, 29 Jan 1998 05:37:26 -0500 (EST)
    • W. Eliot Kimber - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id KAA06902Thu, 29 Jan 1998 10:35:42 -0500 (EST)
      • hanche+dsssl-l - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id NAA07915Thu, 29 Jan 1998 13:13:21 -0500 (EST) <=