Associativity paradox in functional expressions

[Totaram Sanadhya]

Hi,

My main functional language is emacs based lisp.

I am not exactly clear about the associativity.

On the one hand the elements of a list such as (a b c d) are right
associative

(cons 'a (cons 'b (cons 'c (cons 'd nil)))) C-x C-e

==> (a b c d)

On the other hand a curried function such as (f x y z) is left
associative by definition

(...(f x) y) z)

How do you resolve this paradox?

Swami

[Totaram Sanadhya]

Hi,

My main functional language is emacs based lisp.

I am not exactly clear about the associativity.

On the one hand the elements of a list such as (a b c d) are right
associative

(cons 'a (cons 'b (cons 'c (cons 'd nil)))) C-x C-e

==> (a b c d)

On the other hand a curried function such as (f x y z) is left
associative by definition

(...(f x) y) z)

How do you resolve this paradox?

Swami

[Barb Knox]

In article

Post by Totaram Sanadhya
Hi,
My main functional language is emacs based lisp.
I am not exactly clear about the associativity.
On the one hand the elements of a list such as (a b c d) are right
associative
(cons 'a (cons 'b (cons 'c (cons 'd nil)))) C-x C-e
==> (a b c d)
On the other hand a curried function such as (f x y z) is left
associative by definition
(...(f x) y) z)
How do you resolve this paradox?

Easily: Lisp does not use curried functions.

Post by Totaram Sanadhya
Swami

[Totaram Sanadhya]

Post by Barb Knox
In article

Post by Totaram Sanadhya
Hi,
My main functional language is emacs based lisp.
I am not exactly clear about the associativity.
On the one hand the elements of a list such as (a b c d) are right
associative
(cons 'a (cons 'b (cons 'c (cons 'd nil)))) C-x C-e
==> (a b c d)
On the other hand a curried function such as (f x y z) is left
associative by definition
(...(f x) y) z)
How do you resolve this paradox?

Easily: Lisp does not use curried functions.

Which programming languages use curried functions?

I have often heard people like Kastrup talk of
curried functions in gnu.emacs.help and they
even give some code like

((lambda(g n) (funcall g g n))
(lambda(f n)
(if (zerop n) 1
(* n (funcall f f (1- n)))))
4 )


Is there some kind of hack by which I could come close to it in emacs
lisp?

I would have gladly put a backtrace or execution trace for you, but I
could not find a single function that gives an output like the
detailed backtrace when there is an execution error. Perhaps, someone
who is more knowledgeable can take this as an _aside_ question.

However, before I end my post, I just want to thank both Barb and
especially Nils for his student-friendly writings, and the wonderful
books he has written.

Swami

P.S. Unfortunately, I have to crosspost as this is relevant in many
groups, so please avoid or ignore any flames or derailing attempts.

[Dirk Thierbach]

Post by Totaram Sanadhya

Post by Barb Knox
Easily: Lisp does not use curried functions.

Which programming languages use curried functions?

The original lambda calculus, Haskell, OCaml, I think the whole ML family ...

On the other hand, these languages don't depend on lists for program
code.

[F'up to c.l.f.]

- Dirk

[WJ]

Post by Dirk Thierbach

Post by Totaram Sanadhya

Post by Barb Knox
Easily: Lisp does not use curried functions.

Which programming languages use curried functions?

The original lambda calculus, Haskell, OCaml, I think the whole ML family ...
On the other hand, these languages don't depend on lists for program
code.
[F'up to c.l.f.]
- Dirk
(map (curry expt 2) '(0 1 2 3 4))

'(1 2 4 8 16)

[Barb Knox]

Post by WJ

Post by Dirk Thierbach

Post by Totaram Sanadhya

Post by Barb Knox
Easily: Lisp does not use curried functions.

Which programming languages use curried functions?

The original lambda calculus, Haskell, OCaml, I think the whole ML family ...
On the other hand, these languages don't depend on lists for program
code.
[F'up to c.l.f.]
- Dirk
(map (curry expt 2) '(0 1 2 3 4))

'(1 2 4 8 16)

Pure, a functional language based on term rewriting
<http://code.google.com/p/pure-lang/>.

[Nils M Holm]

Post by Totaram Sanadhya
On the one hand the elements of a list such as (a b c d) are right
associative
(cons 'a (cons 'b (cons 'c (cons 'd nil)))) C-x C-e
==> (a b c d)
On the other hand a curried function such as (f x y z) is left
associative by definition
(...(f x) y) z)
How do you resolve this paradox?

It depends.

How do you obtain the curried F in the above expression?

What is (curry (curry cons x) y) supposed to give?

What exactly is the paradox?

Maybe, it would be helpful if you posted some code that
demonstrates what you are trying to do.

F'up-To: comp.lang.scheme

[Pascal J. Bourguignon]

Post by Totaram Sanadhya
Hi,
My main functional language is emacs based lisp.
I am not exactly clear about the associativity.
On the one hand the elements of a list such as (a b c d) are right
associative
(cons 'a (cons 'b (cons 'c (cons 'd nil)))) C-x C-e
==> (a b c d)
On the other hand a curried function such as (f x y z) is left
associative by definition
(...(f x) y) z)
How do you resolve this paradox?

By defining a leflt-associative function.

(defun lons (prefix item)
(append prefix (list item)))

(lons (lons (lons (lons nil 'a) 'b) 'c) 'd)
--> (a b c d)

(lons (lons (lons '(f) 'x) 'y) 'z)
--> (f x y z)

[Rivka Miller]

Post by Pascal J. Bourguignon

Post by Totaram Sanadhya
Hi,
My main functional language is emacs based lisp.
I am not exactly clear about the associativity.
On the one hand the elements of a list such as (a b c d) are right
associative
(cons 'a (cons 'b (cons 'c (cons 'd nil))))    C-x C-e
==> (a b c d)
On the other hand a curried function such as (f x y z) is left
associative by definition
(...(f x) y) z)
How do you resolve this paradox?

By defining a leflt-associative function.
    (defun lons (prefix item)
       (append prefix (list item)))
    (lons (lons (lons (lons nil 'a) 'b) 'c) 'd)
    --> (a b c d)
    (lons (lons (lons '(f) 'x) 'y) 'z)
    --> (f x y z)

@Pascal

I did not get what you achieved by defining a left-associative
function. Your sentence did not clarify your thought. I dont see where
is currying achieved.

(defun lons (prefix item)
(append prefix (list item)))

(lons (lons (lons (lons nil 'a) 'b) 'c) 'd)

(lons (lons (lons '(f) 'x) 'y) 'z)

;; clarifies the meaning of lons by Pascal
(append (append (append (append nil (list 'a)) (list 'b)) (list 'c))
(list 'd))

;; clarifies the role of append
(append '(a b) '(c (d) e))

R

[Pascal J. Bourguignon]

Post by Rivka Miller

Post by Totaram Sanadhya
Hi,
My main functional language is emacs based lisp.
I am not exactly clear about the associativity.
On the one hand the elements of a list such as (a b c d) are right
associative
(cons 'a (cons 'b (cons 'c (cons 'd nil))))    C-x C-e
==> (a b c d)
On the other hand a curried function such as (f x y z) is left
associative by definition
(...(f x) y) z)
How do you resolve this paradox?

By defining a left-associative function.
    (defun lons (prefix item)
       (append prefix (list item)))
    (lons (lons (lons (lons nil 'a) 'b) 'c) 'd)
    --> (a b c d)
    (lons (lons (lons '(f) 'x) 'y) 'z)
    --> (f x y z)

@Pascal
I did not get what you achieved by defining a left-associative
function. Your sentence did not clarify your thought. I dont see where
is currying achieved.

Currying is not achieved, there's no currying in lisp, lisp has
multi-adic and variadic functions. Currying is a notion that is only
needed when you have function taking only one argument.



Now, you may write a macro that implements some currying. In such a
macro, you would use lons instead of cons…

[Rivka Miller]

Post by Pascal J. Bourguignon

Post by Rivka Miller

Post by Totaram Sanadhya
Hi,
My main functional language is emacs based lisp.
I am not exactly clear about the associativity.
On the one hand the elements of a list such as (a b c d) are right
associative
(cons 'a (cons 'b (cons 'c (cons 'd nil))))    C-x C-e
==> (a b c d)
On the other hand a curried function such as (f x y z) is left
associative by definition
(...(f x) y) z)
How do you resolve this paradox?

By defining a left-associative function.
    (defun lons (prefix item)
       (append prefix (list item)))
    (lons (lons (lons (lons nil 'a) 'b) 'c) 'd)
    --> (a b c d)
    (lons (lons (lons '(f) 'x) 'y) 'z)
    --> (f x y z)

@Pascal
I did not get what you achieved by defining a left-associative
function. Your sentence did not clarify your thought. I dont see where
is currying achieved.

Currying is not achieved, there's no currying in lisp, lisp has
multi-adic and variadic functions.  Currying is a notion that is only
needed when you have function taking only one argument.
Now,  you may write a macro that implements some currying.  In such a
macro, you would use lons instead of cons…

Are you saying that the Late Dr McCarthy, after thinking of lisp in
terms of lambda calculus (and its associated currying), nevertheless
implemented it in terms of variadic non-curried functions? Thus the
turing machine replacement that lambda calculus is supposed to be,
does not need any currying to be a replacement of turing machine - in
the sense of computability?

How would the "(funcall g g n)" and "(funcall f f (1- n))" in the
function advanced by the OP supposed to be associated if currying were
available?

((lambda(g n) (funcall g g n))
(lambda(f n)
(if (zerop n) 1
(* n (funcall f f (1- n)))))
4 )


R

[Pascal J. Bourguignon]

Post by Rivka Miller
Are you saying that the Late Dr McCarthy, after thinking of lisp in
terms of lambda calculus (and its associated currying), nevertheless
implemented it in terms of variadic non-curried functions? Thus the
turing machine replacement that lambda calculus is supposed to be,
does not need any currying to be a replacement of turing machine - in
the sense of computability?

Yes. John McCarthy didn't understand lambda calculus at the time. He
just used the lambda notation for his functions, but they differed
greately, notably in that he used dynamic binding instead of lexical
binding.

Post by Rivka Miller
How would the "(funcall g g n)" and "(funcall f f (1- n))" in the
function advanced by the OP supposed to be associated if currying were
available?
((lambda(g n) (funcall g g n))
(lambda(f n)
(if (zerop n) 1
(* n (funcall f f (1- n)))))
4 )

Well, in lisp there are parentheses to imply the order of evaluation…

[Barb Knox]

Post by Pascal J. Bourguignon

Post by Rivka Miller
Are you saying that the Late Dr McCarthy, after thinking of lisp in
terms of lambda calculus (and its associated currying), nevertheless
implemented it in terms of variadic non-curried functions? Thus the
turing machine replacement that lambda calculus is supposed to be,
does not need any currying to be a replacement of turing machine - in
the sense of computability?

Lambda calculus supports currying. Lisp is not lambda calculus.

Post by Pascal J. Bourguignon
Yes. John McCarthy didn't understand lambda calculus at the time. He
just used the lambda notation for his functions

Yeah right. McCarthy had a PhD in mathematics and specialised in
mathematical logic; of course he knew lambda calculus. Or do you
believe his use of "lambda" was just a coincidence? In his1960 paper
introducing LISP ("Recursive Functions of Symbolic Expressions and Their
Computation by Machine"
<http://www-formal.stanford.edu/jmc/recursive.html>), one of his
references is Church's 1941 paper on the lambda calculus.

Are you a moron? Is that why you have such a self-aggrandising nickname?

[snip]

[Aatu Koskensilta]

Post by Barb Knox

Post by Pascal J. Bourguignon
Yes. John McCarthy didn't understand lambda calculus at the time. He
just used the lambda notation for his functions

Yeah right. McCarthy had a PhD in mathematics and specialised in
mathematical logic; of course he knew lambda calculus. Or do you
believe his use of "lambda" was just a coincidence?

Naturally McCarthy got the lambda notation from lambda
calculus. McCarthy was not a mathematical logician by any stretch of the
imagination -- his research was mainly in computer science, artificial
intelligence in particular, and his PhD dissertation was on a problem in
partial differantial equations -- and had this to say about the state of
his understanding of the lambda calculus at the time:

To use functions as arguments, one needs a notation for functions,
and it seemed natural to use the lambda-notation of Church (1941). I
didn't understand the rest of the book, so I wasn't tempted to
implement his more general mechanism for defining functions.

This excerpt is from McCarthy's /History of Lisp/, available on-line at:

http://www-formal.stanford.edu/jmc/history/lisp.ps

Post by Barb Knox
Are you a moron? Is that why you have such a self-aggrandising nickname?

You think "Pascal J. Bourguignon" a "self-aggrandising nickname"?

[Pascal J. Bourguignon]

Post by Aatu Koskensilta

Post by Barb Knox
Are you a moron? Is that why you have such a self-aggrandising nickname?

You think "Pascal J. Bourguignon" a "self-aggrandising nickname"?

"informatimago" would be the nickname. It means Software Sorcerer.
Yes, perhaps it's self aggrandising. You have to forgive it, I chosed
it when I was much younger. Software Sorcerer was a name we took with a
friend in 1984, when I was barely 20, with SOS\000 to SOS\377 having
been registered as MacOS application signatures with Apple Computer.
Unfortunately we split out before finishing our developments, and each
went his way. Eventually I moved to Spain and registered the
informatimago.com domain name on 25-may-2001. I was probably influenced
by those early memories and by sicp.

[Barb Knox]

Post by Aatu Koskensilta

Post by Barb Knox

Post by Pascal J. Bourguignon
Yes. John McCarthy didn't understand lambda calculus at the time. He
just used the lambda notation for his functions

Yeah right. McCarthy had a PhD in mathematics and specialised in
mathematical logic; of course he knew lambda calculus. Or do you
believe his use of "lambda" was just a coincidence?

Naturally McCarthy got the lambda notation from lambda
calculus. McCarthy was not a mathematical logician by any stretch of the
imagination -- his research was mainly in computer science, artificial
intelligence in particular, and his PhD dissertation was on a problem in
partial differantial equations -- and had this to say about the state of
To use functions as arguments, one needs a notation for functions,
and it seemed natural to use the lambda-notation of Church (1941). I
didn't understand the rest of the book, so I wasn't tempted to
implement his more general mechanism for defining functions.
http://www-formal.stanford.edu/jmc/history/lisp.ps

Post by Barb Knox
Are you a moron? Is that why you have such a self-aggrandising nickname?

You think "Pascal J. Bourguignon" a "self-aggrandising nickname"?

Oops. I confused it with "Harrison Bergeron". My bad. And I withdraw
the "moron" semi-rhetorical question.