CODEWITHSUNDEEP
pythonalgorithmdebugging
vv1133
vv1133

Reputation: 739

SICP exercise 1.41

Exercise 1.41. Define a procedure double that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if inc is a procedure that adds 1 to its argument, then (double inc) should be a procedure that adds 2. What value is returned by (((double (double double)) inc) 5)

I implemented it in Python.

def double(f):
    print(f)
    return (lambda x: (f(f(x))))

def inc(x):
    return x+1

print(double(inc)(0))
print((double(double))(inc)(0))
print((double(double(double)))(inc)(0)

Output:

<function inc at 0x00000000029BBB70>
2
<function double at 0x0000000002141730>
<function inc at 0x00000000029BBB70>
<function double.<locals>.<lambda> at 0x00000000029BBC80>
4
<function double at 0x0000000002141730>
<function double.<locals>.<lambda> at 0x00000000029BBD08>
<function inc at 0x00000000029BBB70>
<function double.<locals>.<lambda> at 0x00000000029BBBF8>
<function double.<locals>.<lambda> at 0x00000000029BBD90>
<function double.<locals>.<lambda> at 0x00000000029BBE18>
16

My questions are:

  1. Why the output of print((double(double(double)))(inc)(0) is 16 instead of 8?

  2. Why the function of double was called 3 times instead of 2 times when run (double(double))(inc)(0)

  3. Are there any debug tools that can set breakpoints in python like "gdb" in C so that I can debug this program?

Thank you!

Upvotes: 2

Views: 529

Answers (3)

rici
rici

Reputation: 241911

  1. double applies its argument to itself, as you clearly indicate with:

    lambda x: f(f(x))

    So what's double(double(double)) ? It must be

    (double(double))(double(double))

    So, 16 times.

  2. double(double) uses a call to double to produce lambda f: double(double(f)). Applying that to some f (inc in this case) requires two calls to double. So that's a total of three.

  3. I don't know if gdb would have actually helped you here. Pencil and paper β-reduction is not that difficult in this case, and quite possibly more revealing.

Good luck with SICP!

Upvotes: 1

justhalf
justhalf

Reputation: 9117

Let's analyze your code:

print( double(inc)(0) )

So this will call the function double with argument inc. So as expected, it will return a function which will apply the function inc twice on an argument. So you will get 2 as the output. You have done this correctly.

Now, the interesting point is here:

print( (double(double))(inc)(0) )

Note that you have call the function double with the argument double, and then call the resulting function with the argument inc. So this is what happen:

  1. call double(double) # that is, double with argument double (first call to double)
  2. you get a function which will call double two times on the argument
  3. you use that function on inc.
  4. so you get a function which will apply double two times to inc (there are two times of calls to double here)

What you get is a function that will increment by 4. And actually this is not 2*2, but rather 2^2, it just coincidence (or not) that 2^2 = 2*2 = 4, so you still get answer of 4.

The third print:

print((double(double(double)))(inc)(0)

Actually you call double on the result of double(double), which will apply the function double(double) twice on itself. So effectively you're calling double(double)(double(double(inc))). So you apply the function inc 2*2*(2*2) = 16 times.

To get better understanding of this, note that:

print( double(double(double(inc)))(0) )

will print 8.

Upvotes: 3

R. Max
R. Max

Reputation: 6710

As others already answered the main points, here is an improved version of your code that shows the execution flow with descriptive functions names:

def double(f):
    print('double({})'.format(f))
    def _f(x):
        print('{}({})'.format(_f.__name__, x))
        return f(f(x))
    _f.__name__ = 'double_{}'.format(f.__name__)
    return _f

def inc(x):
    return x + 1

print(double(inc)(0))
print((double(double))(inc)(0))
print((double(double(double)))(inc)(0))

The output:

double(<function inc at 0x7fb3a9ffa578>)
double_inc(0)
2
double(<function double at 0x7fb3a9ffa500>)
double_double(<function inc at 0x7fb3a9ffa578>)
double(<function inc at 0x7fb3a9ffa578>)
double(<function double_inc at 0x7fb3a9ffa6e0>)
double_double_inc(0)
double_inc(0)
double_inc(2)
4
double(<function double at 0x7fb3a9ffa500>)
double(<function double_double at 0x7fb3a9ffa7d0>)
double_double_double(<function inc at 0x7fb3a9ffa578>)
double_double(<function inc at 0x7fb3a9ffa578>)
double(<function inc at 0x7fb3a9ffa578>)
double(<function double_inc at 0x7fb3a9ffa8c0>)
double_double(<function double_double_inc at 0x7fb3a9ffa938>)
double(<function double_double_inc at 0x7fb3a9ffa938>)
double(<function double_double_double_inc at 0x7fb3a9ffa9b0>)
double_double_double_double_inc(0)
double_double_double_inc(0)
double_double_inc(0)
double_inc(0)
double_inc(2)
double_double_inc(4)
double_inc(4)
double_inc(6)
double_double_double_inc(8)
double_double_inc(8)
double_inc(8)
double_inc(10)
double_double_inc(12)
double_inc(12)
double_inc(14)
16

Upvotes: 2

Related Questions