Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #2408 > unrolled thread

Re: Associativity paradox in functional expressions

Back to article view | Back to comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Associativity paradox in functional expressions Totaram Sanadhya <swami.totaram.sanadhya@gmail.com> - 2012-10-31 00:24 -0700
    Re: Associativity paradox in functional expressions Barb Knox <see@sig.below> - 2012-10-31 21:14 +1300
      Re: Associativity paradox in functional expressions Totaram Sanadhya <swami.totaram.sanadhya@gmail.com> - 2012-10-31 10:34 -0700
        Re: Associativity paradox in functional expressions Dirk Thierbach <dthierbach@usenet.arcornews.de> - 2012-10-31 23:36 +0100
    Re: Associativity paradox in functional expressions Nils M Holm <news2009@t3x.org> - 2012-10-31 09:21 +0000
    Re: Associativity paradox in functional expressions "Pascal J. Bourguignon" <pjb@informatimago.com> - 2012-11-02 14:45 +0100
      Re: Associativity paradox in functional expressions Rivka Miller <rivkaumiller@gmail.com> - 2012-11-02 18:59 -0700
        Re: Associativity paradox in functional expressions "Pascal J. Bourguignon" <pjb@informatimago.com> - 2012-11-03 04:14 +0100
          Re: Associativity paradox in functional expressions Rivka Miller <rivkaumiller@gmail.com> - 2012-11-05 16:53 -0800
            Re: Associativity paradox in functional expressions "Pascal J. Bourguignon" <pjb@informatimago.com> - 2012-11-06 07:28 +0100
              Re: Associativity paradox in functional expressions Barb Knox <see@sig.below> - 2012-11-08 17:35 +1300
                Re: Associativity paradox in functional expressions Aatu Koskensilta <aatu.koskensilta@uta.fi> - 2012-11-08 07:42 +0200
                  Re: Associativity paradox in functional expressions "Pascal J. Bourguignon" <pjb@informatimago.com> - 2012-11-08 21:47 +0100
                  Re: Associativity paradox in functional expressions Barb Knox <see@sig.below> - 2012-11-10 15:13 +1300

#2408 — Re: Associativity paradox in functional expressions

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

[toc] | [next] | [standalone]

#2409

In article 
<9972e570-2504-4401-8de8-49eb1929fdfd@c17g2000yqe.googlegroups.com>,
 Totaram Sanadhya <swami.totaram.sanadhya@gmail.com> wrote:

> 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.


> Swami
-- 
---------------------------
|  BBB                b    \     Barbara at LivingHistory stop co stop uk
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |    Quidquid latine dictum sit,
|  B  B  a  a   r     b  b  |    altum videtur.
|  BBB    aa a  r     bbb   |   
-----------------------------

[toc] | [prev] | [next] | [standalone]

#2417

On Oct 31, 1:14 am, Barb Knox <s...@sig.below> wrote:
> In article
> <9972e570-2504-4401-8de8-49eb1929f...@c17g2000yqe.googlegroups.com>,
>  Totaram Sanadhya <swami.totaram.sanad...@gmail.com> wrote:
>
> > 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.

[toc] | [prev] | [next] | [standalone]

#2426

Totaram Sanadhya <swami.totaram.sanadhya@gmail.com> wrote:
> On Oct 31, 1:14 am, Barb Knox <s...@sig.below> wrote:
>> 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

[toc] | [prev] | [next] | [standalone]

#2413

In comp.lang.scheme Totaram Sanadhya <swami.totaram.sanadhya@gmail.com> wrote:
> 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

-- 
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

[toc] | [prev] | [next] | [standalone]

#2439

Totaram Sanadhya <swami.totaram.sanadhya@gmail.com> writes:

> 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 Bourguignon__

[toc] | [prev] | [next] | [standalone]

#2442

On Nov 2, 6:45 am, "Pascal J. Bourguignon" <p...@informatimago.com>
wrote:
> Totaram Sanadhya <swami.totaram.sanad...@gmail.com> writes:
> > 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

[toc] | [prev] | [next] | [standalone]

#2443

Rivka Miller <rivkaumiller@gmail.com> writes:

> On Nov 2, 6:45 am, "Pascal J. Bourguignon" <p...@informatimago.com>
> wrote:
>> Totaram Sanadhya <swami.totaram.sanad...@gmail.com> writes:
>> > 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…


-- 
__Pascal Bourguignon__
http://www.informatimago.com

[toc] | [prev] | [next] | [standalone]

#2472

On Nov 2, 7:14 pm, "Pascal J. Bourguignon" <p...@informatimago.com>
wrote:
> Rivka Miller <rivkaumil...@gmail.com> writes:
> > On Nov 2, 6:45 am, "Pascal J. Bourguignon" <p...@informatimago.com>
> > wrote:
> >> Totaram Sanadhya <swami.totaram.sanad...@gmail.com> writes:
> >> > 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

[toc] | [prev] | [next] | [standalone]

#2473

Rivka Miller <rivkaumiller@gmail.com> writes:

> 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.


> 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…

-- 
__Pascal Bourguignon__
http://www.informatimago.com

[toc] | [prev] | [next] | [standalone]

#2477

In article <87ip9j8ctc.fsf@informatimago.com>,
 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote:

> Rivka Miller <rivkaumiller@gmail.com> writes:
> 
> > 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.
> 
> 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]

-- 
---------------------------
|  BBB                b    \     Barbara at LivingHistory stop co stop uk
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |    Quidquid latine dictum sit,
|  B  B  a  a   r     b  b  |    altum videtur.
|  BBB    aa a  r     bbb   |   
-----------------------------

[toc] | [prev] | [next] | [standalone]

#2478

Barb Knox <see@sig.below> writes:

> In article <87ip9j8ctc.fsf@informatimago.com>,
>  "Pascal J. Bourguignon" <pjb@informatimago.com> wrote:
>
>> 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

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

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

-- 
Aatu Koskensilta (aatu.koskensilta@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"
  - Ludwig Wittgenstein, Tractatus Logico-Philosophicus

[toc] | [prev] | [next] | [standalone]

#2479

Aatu Koskensilta <aatu.koskensilta@uta.fi> writes:

> Barb Knox <see@sig.below> writes:
>> 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.


-- 
__Pascal Bourguignon__
http://www.informatimago.com

[toc] | [prev] | [next] | [standalone]

#2480

In article <87zk2sabw6.fsf@uta.fi>,
 Aatu Koskensilta <aatu.koskensilta@uta.fi> wrote:

> Barb Knox <see@sig.below> writes:
> 
> > In article <87ip9j8ctc.fsf@informatimago.com>,
> >  "Pascal J. Bourguignon" <pjb@informatimago.com> wrote:
> >
> >> 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
> 
> > 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.

-- 
---------------------------
|  BBB                b    \     Barbara at LivingHistory stop co stop uk
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |    Quidquid latine dictum sit,
|  B  B  a  a   r     b  b  |    altum videtur.
|  BBB    aa a  r     bbb   |   
-----------------------------

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web