Beginner: Curried functions in Scheme

Question

I'm using the SICP lectures and text to learn about Scheme on my own. I am looking at an exercise that says "An application of an expression E is an expression of the form (E E1,...En). This includes the case n=0, corresponding to an expression (E). A Curried application of E is either an application of E or an application of a Curried application of E."

(Edit: I corrected the above quote ... I'd originally misquoted the definition.)

The task is to define a Curried application of the procedure which evaluates to 3 for

(define foo1
    (lambda (x)
        (* x x)))

I really don't understand the idea here, and reading the Wikipedia entry on Curriying didn't really help.

Can anyone help with a more lucid explanation of what's being asked for here?

Actually even giving me the answer to this problem would be helpful, since there are five more to solve after this one. ... I just am not getting the basic idea.

Addition: Even after Brian Campbell's lengthy explanation, I'm still somewhat lost.

Is (foo1 (sqrt 3))) considered an application of foo, and therefore a curried application of foo?

Seems too simple, but maybe...

Typing (((foo1 2 )) 2) into DrScheme gives the following error (which I kind of expected)

procedure application: expected procedure, given: 4 (no arguments)

After re-reading What is Currying? I understand I can also re-define foo1 to be:

(define (foo1 a)
    (lambda (b)
        (* a b)))

So then I can type

((foo1 3 ) 4)

12

But this doesn't really get me any closer to producing 3 as an output, and it seems like this isn't really currying the original foo1, it's just re-defining it.

Damn, 20 years of C programming hasn't prepared me for this. :-) :-)

Answer 1

Hm, this problem is fairly confusingly phrased, compared to the usually much more clear style of the books. Actually, it looks like you might be misquoting the problem set, if you're getting the problem set from here; that could be contributing to your confusion.

I'll break the definition down for you, with some examples that might help you figure out what's going on.

An application of an expression E is an expression of the form (E E1 ... En).

Here's an example of an application:

(foo 1 2)      ; This is an application of foo
(bar 1)        ; This is an application of bar

This includes the case n=0, corresponding to an expression (E).

(baz)          ; This is an application of baz

A Curried application of E is either an application of E or an application of a Curried application of E...........

This is the one that you misquoted; above is the definition from the problem set that I found online.

There are two halves to this definition. Starting with the first:

A Curried application of E is either an application of E

(foo 1 2)       ; (1) A Curried application of foo, since it is an application of foo
(bar 1)         ; (2) A Curried application of bar, since it is an application of bar
(baz)           ; (3) A Curried application of baz, since it is an application of baz

or an application of a Curried application of E

((foo 1 2) 3)   ; (4) A Curried application of foo, since it is an application of (1)
((bar 1))       ; (5) A Curried application of bar, since it is an application of (2)
((baz) 1 2)     ; (6) A Curried application of baz, since it is an application of (3)
(((foo 1 2) 3)) ; A Curried application of foo, since it is an application of (4)
(((bar 1)) 2)   ; A Curried application of bar, since it is an application of (5)
                ; etc...

Does that give you the help you need to get started?

edit: Yes, (foo1 (sqrt 3)) is a Curried application of foo1; it is that simple. This is not a very good question, since in many implementations you'll actually get 2.9999999999999996 or something like that; it's not possible to have a value that will return exactly 3, unless your Scheme has some sort of representation of exact algebraic numbers.

Your second example is indeed an error. foo1 returns an integer, which is not valid to apply. It is only some of the later examples for which the recursive case, of an application of an application of the function, are valid. Take a look at foo3, for example.

edit 2: I just checked in SICP, and it looks like the concepts here aren't explained until section 1.3, while this assignment only mentions section 1.1. I would recommend trying to read through section 1.3 if you haven't yet.

Answer 2

See What is 'Currying'?

Currying takes a function and provides a new function accepting a single argument, and returning the specified function with its first argument set to that argument.