From: Shayne Wissler
Subject: Lisp theory question
Date: 
Message-ID: <4Ugy8.137179$G72.81804@sccrnsc01>
Hello,

I've been having a discussion about lisp in comp.object, and all the lisp
programmers there tell me I've been misinformed. I'm not unconvinced, but
I'd like confirmation that what they're telling me is correct. I'd
appreciate any feedback on these assumptions:

1 - In Lambda Calculus, the number "1" is defined as a function which
returns the value "1".
2 - Pure lisp is based on LC.
3 - In pure lisp, following LC, the number 1 is thought of as a function
that returns the value 1 (even though it is not actually implemented that
way).

The feedback I'm getting in comp.object:

 1 - True.
 2 - It is only partly based on LC, and in fact there is no such
implementation as "pure lisp"; it's an imaginary language.
 3 - False.


Thanks,
 Shayne Wissler

From: Matthias Blume
Subject: Re: Lisp theory question
Date: 
Message-ID: <fohely6wfd.fsf@blume-pcmh.research.bell-labs.com>
"Shayne Wissler" <·········@yahoo.com> writes:

> Hello,
> 
> I've been having a discussion about lisp in comp.object, and all the lisp
> programmers there tell me I've been misinformed. I'm not unconvinced, but
> I'd like confirmation that what they're telling me is correct. I'd
> appreciate any feedback on these assumptions:
> 
> 1 - In Lambda Calculus, the number "1" is defined as a function which
> returns the value "1".
> 2 - Pure lisp is based on LC.
> 3 - In pure lisp, following LC, the number 1 is thought of as a function
> that returns the value 1 (even though it is not actually implemented that
> way).
> 
> The feedback I'm getting in comp.object:
> 
>  1 - True.

As someone else already pointed out, there are many different lambda
calculi.  In the pure untyped lambda calculus there is no 1.  However,
one can single out a family of terms that can be thought of as
representatives of natural numbers because they have strikingly
similar properties as far as computablitity is concerned.  In fact,
every type that can can sensibly be added to a programming language
can also be coded up (= simulated by lambda terms) in some way in the
LC.

In typed lambda calculi, people tend to add things such as booleans
and numbers as "constants" to the language.  This is the same way it
is done in most PLs.

In certain pure lambda- (and other) calculi, constants are, indeed,
viewed as functions with no arguments because there is no essential
difference between these two concepts.  In impure languages, procedure
invocation (even with no arguments) can cause effects, which means
that constants and nullary functions need to be kept distinct.

>  2 - It is only partly based on LC, and in fact there is no such
> implementation as "pure lisp"; it's an imaginary language.

Aspects of Lisp were inspired by the lambda calculus (but McCarthy
initially got some of the important the details wrong).  Most modern,
block-structured programming languages of today (even C!) are, in
fact, partly based on the lambda calculus.  Major differences exist in
how big the "part" is. This trend goes way back to the 60's, probably
starting with the Algol family of languages.

>  3 - False.

In "pure" Lisp (which, as others have pointed out, does not exist),
one could think of constants that way.

-- 
-Matthias
From: Barry Margolin
Subject: Re: Lisp theory question
Date: 
Message-ID: <3fhy8.17$wa4.2434@paloalto-snr2.gtei.net>
In article <······················@sccrnsc01>,
Shayne Wissler <·········@yahoo.com> wrote:
>Hello,
>
>I've been having a discussion about lisp in comp.object, and all the lisp
>programmers there tell me I've been misinformed. I'm not unconvinced, but
>I'd like confirmation that what they're telling me is correct. I'd
>appreciate any feedback on these assumptions:
>
>1 - In Lambda Calculus, the number "1" is defined as a function which
>returns the value "1".
>2 - Pure lisp is based on LC.
>3 - In pure lisp, following LC, the number 1 is thought of as a function
>that returns the value 1 (even though it is not actually implemented that
>way).
>
>The feedback I'm getting in comp.object:
>
> 1 - True.

I don't know enough about Lambda Calculus to confirm or deny this.  What I
can say is that you can be completely fluent in Lisp without ever studying
Lambda Calculus.  Lisp isn't really based on Lambda Calculus, it just
borrowed a few ideas from it (e.g. the word LAMBDA to indicate function
literals).

> 2 - It is only partly based on LC, and in fact there is no such
>implementation as "pure lisp"; it's an imaginary language.

I've been programming in Lisp for over 20 years, and I don't think I've
ever encountered anything called "pure lisp".

> 3 - False.

Since there's no such thing as pure lisp, this statement isn't really
meaningful.

-- 
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Joe Marshall
Subject: Re: Lisp theory question
Date: 
Message-ID: <5Hhy8.49076$%s3.19689862@typhoon.ne.ipsvc.net>
"Shayne Wissler" <·········@yahoo.com> wrote in message ···························@sccrnsc01...
> Hello,
>
> I've been having a discussion about lisp in comp.object, and all the lisp
> programmers there tell me I've been misinformed. I'm not unconvinced, but
> I'd like confirmation that what they're telling me is correct. I'd
> appreciate any feedback on these assumptions:
>
> 1 - In Lambda Calculus, the number "1" is defined as a function which
> returns the value "1".

There are many lambda calculi, but in the simple untyped lambda calculus
(where everything is a function) you use `Church numerals'.
A Church numeral is a function that takes a function as an argument.
It returns a function that computes the nth application of the argument.
So suppose you had the church numeral representing the integer 3.
You could apply it to the sine function and you would get a function
that computes the (sin (sin (sin x))) for an x.

> 2 - Pure lisp is based on LC.

Pure lisp?

Lisp was inspired by LC, and a number of concepts from LC are incorporated
into lisp, but lisp does not attempt to slavishly adhere to lambda calculus.

> 3 - In pure lisp, following LC, the number 1 is thought of as a function
> that returns the value 1 (even though it is not actually implemented that
> way).

Nope.  A standard lisp system is more like the `typed' lambda calculus
which is LC with the addition of non-function objects such as numbers.
From: Duane Rettig
Subject: Re: Lisp theory question
Date: 
Message-ID: <4wuuu1cau.fsf@beta.franz.com>
"Shayne Wissler" <·········@yahoo.com> writes:

> Hello,
> 
> I've been having a discussion about lisp in comp.object, and all the lisp
> programmers there tell me I've been misinformed. I'm not unconvinced, but
> I'd like confirmation that what they're telling me is correct. I'd
> appreciate any feedback on these assumptions:

I spent just a few minutes scanning some of comp.object in Google, for
the usages of the term "pure lisp".  There are quite a few, but I would
characterize most of the references to them as also saying "it doesn't
exist", and the one time I saw someone referring to it as if it did
exist, that person noted that he had been a lisp programmer and then had
switched to Smalltalk years ago.

I think that you may be confusing "pure lisp" with "pure OO".  
"Pure OO" might be further described as "objects all the way down".
I do know that Smalltalk has traditionally been "pure OO", though I
do not know how strict that tradition is.  Lisp is traditionally not
"pure OO", although it is and handles OO well in a hybrid manner.
In fact, Common Lisp is not pure anything, which is what makes it such
a dynamite language (it does not tie itself to pet philosophical notions
like pure OO, pure-functional programming, etc), but instead embraces
all such concepts non-fanatically.

> 1 - In Lambda Calculus, the number "1" is defined as a function which
> returns the value "1".
> 2 - Pure lisp is based on LC.
> 3 - In pure lisp, following LC, the number 1 is thought of as a function
> that returns the value 1 (even though it is not actually implemented that
> way).
> 
> The feedback I'm getting in comp.object:
> 
>  1 - True.
>  2 - It is only partly based on LC, and in fact there is no such
> implementation as "pure lisp"; it's an imaginary language.
>  3 - False.

I know of no language called "Pure lisp".  Neither do I know of any
successful "Pure OO" lisp implementation.  All of the lisps that I
can think of are hybrids, in one way or the other.

-- 
Duane Rettig          Franz Inc.            http://www.franz.com/ (www)
1995 University Ave Suite 275  Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253   ·····@Franz.COM (internet)
From: Paul Wallich
Subject: Re: Lisp theory question
Date: 
Message-ID: <pw-2604021716540001@192.168.1.100>
In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:

>"Shayne Wissler" <·········@yahoo.com> writes:
>
>> Hello,
>> 
>> I've been having a discussion about lisp in comp.object, and all the lisp
>> programmers there tell me I've been misinformed. I'm not unconvinced, but
>> I'd like confirmation that what they're telling me is correct. I'd
>> appreciate any feedback on these assumptions:
[snip]
>I spent just a few minutes scanning some of comp.object in Google, for
>the usages of the term "pure lisp".  There are quite a few, but I would
>characterize most of the references to them as also saying "it doesn't
>exist", and the one time I saw someone referring to it as if it did
>exist, that person noted that he had been a lisp programmer and then had
>switched to Smalltalk years ago.
>
>I think that you may be confusing "pure lisp" with "pure OO".  
>"Pure OO" might be further described as "objects all the way down".
>I do know that Smalltalk has traditionally been "pure OO", though I
>do not know how strict that tradition is.  Lisp is traditionally not
>"pure OO", although it is and handles OO well in a hybrid manner.
>In fact, Common Lisp is not pure anything, which is what makes it such
>a dynamite language (it does not tie itself to pet philosophical notions
>like pure OO, pure-functional programming, etc), but instead embraces
>all such concepts non-fanatically.

Alan Kay once said in an interview that the early versions of smalltalk
were so thoroughly object-oriented that (as with the simplest lambda
calculus) the whole notion of adding two numbers was nowhere near
primitive.  (He was there, so it seems he would be a good source.) You
would  pass the object named 4 a message telling it you wanted to
execute an addition, plus a pointer to the object named 3, it would
do its own internal lookup and a query to 3 to get the right method for
an integer add, and then hand you back a pointer to the object named
7. (This was pretty quickly replaced by a message telling the object named
4 to add 3 to itself and then by addition without benefit of lookup, but
the paradigm remained.)

There are some times when you might want to think of numbers as
functions that return their value or objects with the appropriate 
methods, but more important than whether such views are "true"
is what circumstances might make you want to think that way.

paul
From: Rainer Joswig
Subject: Re: Lisp theory question
Date: 
Message-ID: <joswig-95E5FE.22473926042002@news.fu-berlin.de>
In article <·············@beta.franz.com>,
 Duane Rettig <·····@franz.com> wrote:

> I know of no language called "Pure lisp".

  http://burks.brighton.ac.uk/burks/foldoc/85/94.htm

  "A purely functional language derived from Lisp by excluding
   any feature which causes side-effects."

The term "pure Lisp" is well known in computer science education
and simply means "core Lisp without side effects". Often used
as a teaching vehicle. John McCarthy mentions "Pure LISP"
in his paper from 1960.
From: Duane Rettig
Subject: Re: Lisp theory question
Date: 
Message-ID: <4sn5i162i.fsf@beta.franz.com>
Rainer Joswig <······@lispmachine.de> writes:

> In article <·············@beta.franz.com>,
>  Duane Rettig <·····@franz.com> wrote:
> 
> > I know of no language called "Pure lisp".
> 
>   http://burks.brighton.ac.uk/burks/foldoc/85/94.htm
> 
>   "A purely functional language derived from Lisp by excluding
>    any feature which causes side-effects."
> 
> The term "pure Lisp" is well known in computer science education
> and simply means "core Lisp without side effects". Often used
> as a teaching vehicle. John McCarthy mentions "Pure LISP"
> in his paper from 1960.

All, right, I concede; I should have said "I know of no implemented
language called Pure Lisp", similar to how I phrased it in the
second sentence in the same paragraph.   It's ironic; your's was one of
the articles I chanced upon in comp.object, where you answered that there
is no such thing as "pure lisp".  I'm not quoting you, because I no
longer have the Google search results before me, and so I apologize if
my reading of your statement was taken out of context.

BTW, I have hard time with the above definition.  It is true enough,
but it also takes newbies down a garden path when they make the
assumption that such a language exists (i.e. I can write and run a
program in it).  After all, why talk about a language that doesn't
really exist?  This kind of garden-path logic is the kind of thing
which gives lisp incorrect characterizations, and eventually a bad
name.  It is like the dictionary entry we discussed not long ago
which labelled lisp as interpreted, big, and slow.

-- 
Duane Rettig          Franz Inc.            http://www.franz.com/ (www)
1995 University Ave Suite 275  Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253   ·····@Franz.COM (internet)
From: Rainer Joswig
Subject: Re: Lisp theory question
Date: 
Message-ID: <joswig-6842B5.01594227042002@news.fu-berlin.de>
In article <·············@beta.franz.com>,
 Duane Rettig <·····@franz.com> wrote:

> Rainer Joswig <······@lispmachine.de> writes:
> 
> > In article <·············@beta.franz.com>,
> >  Duane Rettig <·····@franz.com> wrote:
> > 
> > > I know of no language called "Pure lisp".
> > 
> >   http://burks.brighton.ac.uk/burks/foldoc/85/94.htm
> > 
> >   "A purely functional language derived from Lisp by excluding
> >    any feature which causes side-effects."
> > 
> > The term "pure Lisp" is well known in computer science education
> > and simply means "core Lisp without side effects". Often used
> > as a teaching vehicle. John McCarthy mentions "Pure LISP"
> > in his paper from 1960.
> 
> All, right, I concede; I should have said "I know of no implemented
> language called Pure Lisp", similar to how I phrased it in the
> second sentence in the same paragraph.   It's ironic; your's was one of
> the articles I chanced upon in comp.object, where you answered that there
> is no such thing as "pure lisp".

Yes, as a Lisp dialect or implementation one can use, buy,
whatever. Aside from some exercises in some CS courses... ;-)
From: Biep @ http://www.biep.org/
Subject: Re: Lisp theory question
Date: 
Message-ID: <abeb8t$hbvnr$1@ID-63952.news.dfncis.de>
"Duane Rettig" <·····@franz.com> wrote in message
··················@beta.franz.com...
> I know of no implemented language called Pure Lisp

Normally the expression is used in the context of some Lisp.  In that case,
the term refers to that Lisp, minus its "non-pure parts", i.e. minus
anything that is not functional (in the FP sense of the word).

I have given excercises like "In pure Lisp, write ... .  Now write the same
in full-fledged Lisp.  Discuss the differences."

--
Biep
From: Wolfhard Buß
Subject: Re: Lisp theory question
Date: 
Message-ID: <m3r8l213ll.fsf@buss-14250.user.cis.dfn.de>
Rainer Joswig <······@lispmachine.de> writes:

> John McCarthy mentions "Pure LISP" in his paper from 1960.

McCarthy doesn't use the term "Pure Lisp" in 'Recursive Functions of
Symbolic Expressions and their Computation by Machine'.
In the 'Lisp 1.5 Programmer's Manual' p. 14 you'll find: "In the pure
theory of Lisp, all functions other than the five basic ones ...", and
on page 20 "Section I of this manual presented a purely formal mathematical
system that we shall call pure LISP.".
The world of S-expressions and M-expressions.

In 'LISP-NOTES ON ITS PAST AND FUTURE-1980' McCarthy notes:
"Computer checked proofs of program correctness are now possible for
pure LISP and some extensions, but more theory and some smoothing
of the language itself are required before we can take full advantage
of LISP's mathematical basis.", and
"From the beginning, I have wanted to develop techniques for making
computer checkable proofs of LISP programs, and now this is possible
for a large part of LISP.

ACL2 for example, seems to be a member of the pure Lisp family of
programming languages.

Historically Lisp is neither based nor inspired by Lambda Calculus. 
At a certain point there was maplist, and then came lambda. 
McCarthy tried to introduce lambda into Algol 58, ...

-- 
"Das Auto hat keine Zukunft. Ich setze aufs Pferd."  Wilhelm II. (1859-1941)
From: Rainer Joswig
Subject: Re: Lisp theory question
Date: 
Message-ID: <joswig-D5227E.01553827042002@news.fu-berlin.de>
In article <··············@buss-14250.user.cis.dfn.de>,
 ·····@gmx.net (Wolfhard Buss) wrote:

> Rainer Joswig <······@lispmachine.de> writes:
> 
> > John McCarthy mentions "Pure LISP" in his paper from 1960.
> 
> McCarthy doesn't use the term "Pure Lisp" in 'Recursive Functions of
> Symbolic Expressions and their Computation by Machine'.
> In the 'Lisp 1.5 Programmer's Manual' p. 14 you'll find: "In the pure
> theory of Lisp, all functions other than the five basic ones ...", and
> on page 20 "Section I of this manual presented a purely formal mathematical
> system that we shall call pure LISP.".
> The world of S-expressions and M-expressions.

Stoyan/Gorz [Lisp, Eine Einfuhrung in die Programmierung, page 7]
describe it like that:

"... Andererseits hat McCarthy in der schon erwahnten theoretischen
Arbeit (McCarthy (1960)), in der die Grundlagen von LISP
gelegt wurden (nachdem es schon existierte), eine Teilsprache
ausgezeichnet, das "reine LISP" (engl. Pure LISP),
in der man ganz streng nach dem funktionalen Modell vorgehen
kann. Zur praktischen Programmierung wurde das "reine Lisp"
nie verwendet, weil die Implementationen zu ineffizient
waren. ..."
From: Wolfhard Buß
Subject: Re: Lisp theory question
Date: 
Message-ID: <m3elh1l9f7.fsf@buss-14250.user.cis.dfn.de>
'Stoyan/Gorz: LISP' may call the pure Lisp described in section 3
of 'Recursive Functions of Symbolic Expressions ...' pure Lisp.
McCarthy doesn't use this term in that paper!

Section 4 'The Lisp Programming System' describes the implementation
Lisp1 on the IBM 704 "the first large-scale commercially available
computer to employ fully automatic floating-point arithmetic", the
first IBM vacuum-tube supercomputer that used magnetic core memory.
In paragraph f. 'Status of the LISP Programming System (February 1960)'
McCarthy mentions "a program feature", that "allows programs
containing assignment and go to statements in the style of ALGOL".
In case somone should claim Lisp1 was a pure Lisp.

-- 
"Das Auto hat keine Zukunft. Ich setze aufs Pferd."  Wilhelm II. (1859-1941)
From: P.C.
Subject: Re: Lisp theory question
Date: 
Message-ID: <3ccaba36$0$78765$edfadb0f@dspool01.news.tele.dk>
Hi.

"Duane Rettig" <·····@franz.com> skrev i en meddelelse
··················@beta.franz.com...
> I spent just a few minutes scanning some of comp.object in Google, for
> the usages of the term "pure lisp".  There are quite a few, but I would
> characterize most of the references to them as also saying "it doesn't
> exist",

That's not intirily true ; Pure Lisp refere to constructing everything with only
5 primitive functions ;Car ,Cdr , Cons ,Atom and Eq.
With those ,you shuld be able to program just everything , this is "Pure Lisp".
P.C.

http://d1o111.dk.telia.net/~u139600113/a
From: Joe Marshall
Subject: Re: Lisp theory question
Date: 
Message-ID: <yuBy8.50728$%s3.20473279@typhoon.ne.ipsvc.net>
"P.C." <··········@privat.dk> wrote in message ······························@dspool01.news.tele.dk...
> Hi.
>
> "Duane Rettig" <·····@franz.com> skrev i en meddelelse
> ··················@beta.franz.com...
> > I spent just a few minutes scanning some of comp.object in Google, for
> > the usages of the term "pure lisp".  There are quite a few, but I would
> > characterize most of the references to them as also saying "it doesn't
> > exist",
>
> That's not intirily true ; Pure Lisp refere to constructing everything with only
> 5 primitive functions ;Car ,Cdr , Cons ,Atom and Eq.
> With those ,you shuld be able to program just everything , this is "Pure Lisp".

I don't think those five are sufficient.  How would you program a conditional?
From: Rainer Joswig
Subject: Re: Lisp theory question
Date: 
Message-ID: <joswig-9D3BB6.20311527042002@news.fu-berlin.de>
In article <························@typhoon.ne.ipsvc.net>,
 "Joe Marshall" <·············@attbi.com> wrote:

> "P.C." <··········@privat.dk> wrote in message ······························@dspool01.news.tele.dk...
> > Hi.
> >
> > "Duane Rettig" <·····@franz.com> skrev i en meddelelse
> > ··················@beta.franz.com...
> > > I spent just a few minutes scanning some of comp.object in Google, for
> > > the usages of the term "pure lisp".  There are quite a few, but I would
> > > characterize most of the references to them as also saying "it doesn't
> > > exist",
> >
> > That's not intirily true ; Pure Lisp refere to constructing everything with only
> > 5 primitive functions ;Car ,Cdr , Cons ,Atom and Eq.
> > With those ,you shuld be able to program just everything , this is "Pure Lisp".
> 
> I don't think those five are sufficient.  How would you program a conditional?

With LAMBDA ?!
From: P.C.
Subject: Re: Lisp theory question
Date: 
Message-ID: <3ccb2124$0$78790$edfadb0f@dspool01.news.tele.dk>
Hi.

"Rainer Joswig" <······@lispmachine.de> skrev i en meddelelse
·································@news.fu-berlin.de...
> In article <························@typhoon.ne.ipsvc.net>,
>  "Joe Marshall" <·············@attbi.com> wrote:
>
> > "P.C." <··········@privat.dk> wrote in message
······························@dspool01.news.tele.dk...
> > > Hi.
> > >
> > > "Duane Rettig" <·····@franz.com> skrev i en meddelelse
> > > ··················@beta.franz.com...
> > > > I spent just a few minutes scanning some of comp.object in Google, for
> > > > the usages of the term "pure lisp".  There are quite a few, but I would
> > > > characterize most of the references to them as also saying "it doesn't
> > > > exist",
> > >
> > > That's not intirily true ; Pure Lisp refere to constructing everything
with only
> > > 5 primitive functions ;Car ,Cdr , Cons ,Atom and Eq.
> > > With those ,you shuld be able to program just everything , this is "Pure
Lisp".
> >
> > I don't think those five are sufficient.  How would you program a
conditional?
>
> With LAMBDA ?!

Guess Eq is the root for that, while I also think, that programming in PureLisp
work without defun's and setq's ; you proberly "defun" a mapcar instantly while
using it, and if Eq is a cond primitive, you proberly would program recursive.
Still I don't much more, than those 5 shuld be the primitives ,but I guess the
whole trouble deal with difference in style to. Where most in this groupe
proberly are used to standard lib's and functions, I allway's tried to develob
Lisp as simple as possible ; guess most here, would never program like this ;
(defun mix (x)
(cond
((null x)nil)
((null(cdr x))(append x (mix (cdr x))))
(t(append(list (car x) (cadr x))(mix (cdr x))))
))
And if most don't most proberly also seldom use recursive functions.
Cond is just yielding T or nil, Guess (Eq (car list)) could yield T, then Lambda
Calcus are maby the secret after all ;))
P.C.
From: Rainer Joswig
Subject: Re: Lisp theory question
Date: 
Message-ID: <joswig-C475A6.01021628042002@news.fu-berlin.de>
In article <····························@news.fu-berlin.de>,
 Rainer Joswig <······@lispmachine.de> wrote:

> In article <························@typhoon.ne.ipsvc.net>,
>  "Joe Marshall" <·············@attbi.com> wrote:
> 
> > "P.C." <··········@privat.dk> wrote in message 
> > ······························@dspool01.news.tele.dk...
> > > Hi.
> > >
> > > "Duane Rettig" <·····@franz.com> skrev i en meddelelse
> > > ··················@beta.franz.com...
> > > > I spent just a few minutes scanning some of comp.object in Google, for
> > > > the usages of the term "pure lisp".  There are quite a few, but I would
> > > > characterize most of the references to them as also saying "it doesn't
> > > > exist",
> > >
> > > That's not intirily true ; Pure Lisp refere to constructing everything 
> > > with only
> > > 5 primitive functions ;Car ,Cdr , Cons ,Atom and Eq.
> > > With those ,you shuld be able to program just everything , this is "Pure 
> > > Lisp".
> > 
> > I don't think those five are sufficient.  How would you program a 
> > conditional?
> 
> With LAMBDA ?!

Hmm, IIRC: True and False are represented as functions. "If"
is a function, too.

similar to this:

(defun lc-true (foo bar) (funcall foo))
(defun lc-false (foo bar) (funcall bar))
(defun lc-if (foo bar baz)
  (funcall foo bar baz))

(lc-if #'lc-true (lambda () 'true) (lambda () 'false))
(lc-if #'lc-false (lambda () 'true) (lambda () 'false))
From: Wolfhard Buß
Subject: Re: Lisp theory question
Date: 
Message-ID: <m3bsc2kafn.fsf@buss-14250.user.cis.dfn.de>
Rainer Joswig <······@lispmachine.de> writes:

> Hmm, IIRC: True and False are represented as functions. "If"
> is a function, too.

True and False are represented as symbols.
Since Lisp functions are strict, conditional expressions can't be
Lisp functions. They must be something ... special.

-- 
Lisp: Recursive functions of symbolic expressions.
Symbol: Something with a property list.
From: Matthias Blume
Subject: Re: Lisp theory question
Date: 
Message-ID: <fo3cxe79go.fsf@blume-pcmh.research.bell-labs.com>
·····@gmx.net (Wolfhard Bu�) writes:

> Since Lisp functions are strict, conditional expressions can't be
> Lisp functions. They must be something ... special.

Nonsense.  All you need to do is put then- and else-branch into a
thunk each.  Notice that the question was not to define (real) Lisp's
"if" construct but merely to get "conditionals".  The encoding of
things that behave like "true", "false", and "if" as lambda terms is
well-known.  To put it differently: The answer to the question whether
pure Lisp is Turing-complete is "yes".  The answer to the question
whether you can make pure Lisp look like real Lisp is "no".

By the way, the answer to the Turing-completeness question remains
"yes" even if you remove CONS and friends.  Having just LAMBDA is
plenty.  In a lexically scoped Lisp, CONS can be defined using LAMBDA:

   (defun MCONS (x y) #'(lambda (s) (funcall s x y)))
   (defun MCAR  (p) (funcall p #'(lambda (x y) x)))
   (defun MCDR  (p) (funcall p #'(lambda (x y) y)))

This does not give us a test for NIL (NULL), so let's try again.  To
avoid the funcall/#' clutter, I'll just give lambda-calculus-style
equations.  Inserting the correct amount of FUNCALL, #', DEFUN and/or
DEFVAR and doing the right name-mangling to make this compile under a
real Lisp is left as an exercise to the reader...

 booleans:

   true  = (lambda (x y) x)
   false = (lambda (x y) y)
   if    = (lambda (b th el) ((b th el)))

 lists:
  (shows how sum types can be encoded;
   to avoid having to deal with runtime errors, car and cdr return nil when
   called with nil)

   cons  = (lambda (x y) (lambda (cons-case nil-case) (cons-case x y)))
   nil   = (lambda (cons-case nil-case) (nil-case))
   car   = (lambda (l) (l (lambda (x y) x) (lambda () nil)))
   cdr   = (lambda (l) (l (lambda (x y) y) (lambda () nil)))
   null  = (lambda (l) (l (lambda (x y) false) (lambda () true)))

 recursion:
  (the well-known applicative-order Y)

   y     = (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y))))
                        (lambda (x) (f (lambda (y) ((x x) y))))))

With this we can, e.g.,  append two lists:

  append = (lambda (a b)
             ((y (lambda (app)
                  (lambda (ab)
                     (if (null (car ab))
                         (lambda () (cdr ab))
                          (lambda ()
                            (cons (car (car ab))
                                  (app (cons (cdr (car ab))
                                             (cdr ab)))))))))
              (cons a b)))
 
(Notice the contortions that are necessary because the above y works only
for one-argument functions, so app needs to be a one-arg function.
I hack around this using cons.  Alternatively, we could use product types
(aka pairs), i.e., a kind of cons without nil:

   pair  = (lambda (x y) (lambda (s) (s x y)))
   fst   = (lambda (p) (p (lambda (x y) x)))
   snd   = (lambda (p) (p (lambda (x y) y)))

This matches the first version of cons/car/cdr (and not surprisingly so).)

--
-Matthias
From: P.C.
Subject: Re: Lisp theory question
Date: 
Message-ID: <3ccda521$0$97326$edfadb0f@dspool01.news.tele.dk>
Hi.

"Matthias Blume" <········@shimizu-blume.com> skrev i en meddelelse
···················@blume-pcmh.research.bell-labs.com...
> ·····@gmx.net (Wolfhard Bu�) writes:
>
> > Since Lisp functions are strict, conditional expressions can't be
> > Lisp functions. They must be something ... special.
>
> Nonsense.  All you need to do is put then- and else-branch into a
> thunk each.  Notice that the question was not to define (real) Lisp's
> "if" construct but merely to get "conditionals".  The encoding of
> things that behave like "true", "false", and "if" as lambda terms is
> well-known.  To put it differently: The answer to the question whether
> pure Lisp is Turing-complete is "yes".  The answer to the question
> whether you can make pure Lisp look like real Lisp is "no".

Eh, ---- if I have five primitives, that I can use for building any symbol bound
function, I soon will make a mapcar and an apply, instead of writing a lambda or
set to make a list with the function name as the first Atom.
-------- Sorry I suddenly wonder if anyone forgot what Lisp is about.
So the ansver must be "yes" ,while starting with 5 atoms, also provide an "if"
even all Lisp Guru's proberly say, that "if" is a non Lisp construct, that just
as well could read "cond"  , ------ the most important condision for recursive
Lisp btw ;))
The yield of Lambda calcus is T, then how can it be difficult to se, that "pure
Lisp" cover everything, but restricting to C+ way of programing is just one way
to treat Lisp, Mapcar are defined recursive for Lisp, and run recursive within
Lisp, then implermenting is maby the right word, but making a bobble search
recursive are made more efficient recursivly ,then why is it, everything need
drive that slow ;))
Now I hate bad programing, but think Lisp have just "that" within it, that could
maby help, program a chip , that kind of abilities can't allway's carry around
with If's or Progn or Goto that btw, was dammed by programmers as bad programing
etics.   ,If you program in assembler Lisp could maby provide just the tool
needed , if you use Lisp to make compilers you proberly have a good tool , still
my aproach to Lisp are different.
.  Now my background are construction methods, not according a quote about  if a
var shuld take up space, within an infinity amount of space ; make my oppinion
off-topic. I just want a building method as I thought a computer shuld provide,
so I develobed it myself.  If you ever tried to develob an application, that can
bring pieces back into place,  you wouldn't chose C or Kobold , some you could
do in Pascal or Basic but there are a dialect specialy made for this.  Still
think, that the fact that PureLisp only carry 5 primitives, is very interesting
and offer some interisting options, but I do buildings not the kind of
programming mostly refered in the groupe. So when yiu read my comments in a Lisp
groupe, it's becaurse I simply love to discuss cirtain aspects of Lisp, but
rather bring some of the idear behind, into reality ;))
P.C.
http://d1o111.dk.telia.net/~u139600113/a


and soon I can publish what I made the past halve year ; hold on to glasses and
hat's when I do publish, and don't cheat yourself for the discussion.


>
> By the way, the answer to the Turing-completeness question remains
> "yes" even if you remove CONS and friends.  Having just LAMBDA is
> plenty.  In a lexically scoped Lisp, CONS can be defined using LAMBDA:
>
>    (defun MCONS (x y) #'(lambda (s) (funcall s x y)))
>    (defun MCAR  (p) (funcall p #'(lambda (x y) x)))
>    (defun MCDR  (p) (funcall p #'(lambda (x y) y)))
>
> This does not give us a test for NIL (NULL), so let's try again.  To
> avoid the funcall/#' clutter, I'll just give lambda-calculus-style
> equations.  Inserting the correct amount of FUNCALL, #', DEFUN and/or
> DEFVAR and doing the right name-mangling to make this compile under a
> real Lisp is left as an exercise to the reader...
>
>  booleans:
>
>    true  = (lambda (x y) x)
>    false = (lambda (x y) y)
>    if    = (lambda (b th el) ((b th el)))
>
>  lists:
>   (shows how sum types can be encoded;
>    to avoid having to deal with runtime errors, car and cdr return nil when
>    called with nil)
>
>    cons  = (lambda (x y) (lambda (cons-case nil-case) (cons-case x y)))
>    nil   = (lambda (cons-case nil-case) (nil-case))
>    car   = (lambda (l) (l (lambda (x y) x) (lambda () nil)))
>    cdr   = (lambda (l) (l (lambda (x y) y) (lambda () nil)))
>    null  = (lambda (l) (l (lambda (x y) false) (lambda () true)))
>
>  recursion:
>   (the well-known applicative-order Y)
>
>    y     = (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y))))
>                         (lambda (x) (f (lambda (y) ((x x) y))))))
>
> With this we can, e.g.,  append two lists:
>
>   append = (lambda (a b)
>              ((y (lambda (app)
>                   (lambda (ab)
>                      (if (null (car ab))
>                          (lambda () (cdr ab))
>                           (lambda ()
>                             (cons (car (car ab))
>                                   (app (cons (cdr (car ab))
>                                              (cdr ab)))))))))
>               (cons a b)))
>
> (Notice the contortions that are necessary because the above y works only
> for one-argument functions, so app needs to be a one-arg function.
> I hack around this using cons.  Alternatively, we could use product types
> (aka pairs), i.e., a kind of cons without nil:
>
>    pair  = (lambda (x y) (lambda (s) (s x y)))
>    fst   = (lambda (p) (p (lambda (x y) x)))
>    snd   = (lambda (p) (p (lambda (x y) y)))
>
> This matches the first version of cons/car/cdr (and not surprisingly so).)
>
> --
> -Matthias
From: Joe Marshall
Subject: Re: Lisp theory question
Date: 
Message-ID: <O2qz8.56636$%s3.22621082@typhoon.ne.ipsvc.net>
"P.C." <··········@privat.dk> wrote in message ······························@dspool01.news.tele.dk...
>
> Eh, ---- if I have five primitives, that I can use for building any symbol bound
> function, I soon will make a mapcar and an apply, instead of writing a lambda or
> set to make a list with the function name as the first Atom.

The five you mentioned, CAR, CDR, CONS, ATOM, and EQ, simply aren't sufficient.
You need LAMBDA  (and you can dispense with CAR, CDR, CONS, ATOM and EQ).

>
> and soon I can publish what I made the past halve year ; hold on to glasses and
> hat's when I do publish, and don't cheat yourself for the discussion.
>

I can't wait.
From: P.C.
Subject: Re: Lisp theory question
Date: 
Message-ID: <3cce3845$0$97289$edfadb0f@dspool01.news.tele.dk>
Hi.

"Joe Marshall" <·············@attbi.com> skrev i en meddelelse
·····························@typhoon.ne.ipsvc.net...
>
> "P.C." <··········@privat.dk> wrote in message
······························@dspool01.news.tele.dk...
> >
> > Eh, ---- if I have five primitives, that I can use for building any symbol
bound
> > function, I soon will make a mapcar and an apply, instead of writing a
lambda or
> > set to make a list with the function name as the first Atom.
>
> The five you mentioned, CAR, CDR, CONS, ATOM, and EQ, simply aren't
sufficient.
> You need LAMBDA  (and you can dispense with CAR, CDR, CONS, ATOM and EQ).
>

Now there are a chance that what I now claim is pure nonsense, and I must agrea
that I never realy tried to write a program in PureLisp, but Lambda calcus I
never realy understood.  I allway's seen it as the mekanism that yield the
result , and in that sense it's allway's present.  So what I never tried and
don't know work ,is an idear that the yield T in Lambda is replaced with the
result. ------ this mean that you don't _need Lambda as the result of calling
lambda is there anyway .  Guess Lisp work that way and there is no difference
realy if you se Lambda as the evaluator , --------- then I wonder, while defing
functions work simular to Lambda, but giving the option to run an unnamed
function, for the program there are no difference as the program run on the
results evaluatet.
Anyway defining Lambda in this case ,would not be that difficult, as you just
need to trigger the evaluator with a preset atom Lambda.
Do you think this is that far out ;))
P.C.
From: P.C.
Subject: Re: Lisp theory question
Date: 
Message-ID: <3cce4439$0$97281$edfadb0f@dspool01.news.tele.dk>
Hi.

"P.C." <··········@privat.dk> skrev i en meddelelse
······························@dspool01.news.tele.dk...
> Hi.
>
> "Joe Marshall" <·············@attbi.com> skrev i en meddelelse
> ·····························@typhoon.ne.ipsvc.net...

Forgot to add ,that with Lisp it work like that, that as soon the evaluator se a
list, it check if the first Atom is a predefined function ,and if that it
evaluate the function bound to this Atom with the rest of the list as arguments.
Also Defun is not realy needed, as a function or a Lambda expression can easyli
be replaced with List ;))
You can just use setq or set to construct a list instead of using defun ,then
Lambda is usealy used, to evaluate an "unnamed" function ; ------ that's the
same as evaluating a list, and Im'e not sure you even need to use Lambda, but it
make the code more readable.
P.C.
From: Wolfhard Buß
Subject: Re: Lisp theory question
Date: 
Message-ID: <m3elgxctxd.fsf@buss-14250.user.cis.dfn.de>
·····@gmx.net (Wolfhard Bu�) writes:
> Since Lisp functions are strict, conditional expressions can't be
> Lisp functions. They must be something ... special.

Matthias Blume <········@shimizu-blume.com> writes:
> Nonsense.

No.

> Notice that the question was ...

The original posters cons, car, cdr, eq, atom obviously refer to the
five elementary functions of the prototype of pure Lisp of [1] and [2].
We already know that [2] defines the term 'pure Lisp'.
Among the constituent elements of pure Lisp are symbolic expressions,
elementary functions, and the syntactic constructs cond (aka conditional
expression) lambda and label.
The op's five elementary functions don't ask for Lambda Calculus, they
ask for pure Lisp.
It's an appealing project to build the whole world on lambda expressions
and their reduction. You'll find a family for your lambda calculus based
pure Lisp in the cosmos of the Lisp families of programming languages.
Thanks for the demonstration.


Footnotes: 
[1]  McCarthy J.: Recursive Functions of Symbolic Expressions and Their
     Computation by Machine, Part I, (April 1960)

[2]  McCarthy J. et al.: Lisp 1.5 Programmers's Manual, (August 1962) 

-- 
"Das Auto hat keine Zukunft. Ich setze aufs Pferd."  Wilhelm II. (1859-1941)
From: Matthias Blume
Subject: Re: Lisp theory question
Date: 
Message-ID: <fopu0h5liq.fsf@blume-pcmh.research.bell-labs.com>
·····@gmx.net (Wolfhard Bu�) writes:

> ·····@gmx.net (Wolfhard Bu�) writes:
> > Since Lisp functions are strict, conditional expressions can't be
> > Lisp functions. They must be something ... special.
> 
> Matthias Blume <········@shimizu-blume.com> writes:
> > Nonsense.
> 
> No.

Yes.  You said: "Conditional expressions can't be Lisp functions."
But they can, unless you take the narrow view that by "conditional
expression" you mean precisely McCarthy's COND.  However, with LAMBDA
you don't even need McCarthy's COND....

Matthias
From: Wolfhard Buß
Subject: Re: Lisp theory question
Date: 
Message-ID: <m31ycwq7jm.fsf@buss-14250.user.cis.dfn.de>
Matthias Blume <········@shimizu-blume.com> writes:

> You said: "Conditional expressions can't be Lisp functions."
> But they can, unless you take the narrow view that by "conditional
> expression" you mean precisely McCarthy's COND.  However, with LAMBDA
> you don't even need McCarthy's COND....

With lambda you don't even need Rochester's label, which is not
a defun btw.
Your conditionals are Lisp functions, since they are thunky strict
simulations of conditional expressions, which are nonstrict specials.

Ist der 1. Mai Feiertag in Jersey?

-- 
"Das Auto hat keine Zukunft. Ich setze aufs Pferd."  Wilhelm II. (1859-1941)
From: Matthias Blume
Subject: Re: Lisp theory question
Date: 
Message-ID: <fod6wf6g7w.fsf@blume-pcmh.research.bell-labs.com>
·····@gmx.net (Wolfhard Bu�) writes:

> With lambda you don't even need Rochester's label, which is not
> a defun btw.

Right.  With lambda you need nothing else.

> Your conditionals are Lisp functions, since they are thunky strict
> simulations of conditional expressions, which are nonstrict specials.

Right.  Taking advantage of the fact that strict evaluators evaluate
to a head-normal form, so what would be non-strict things can be
"protected" from (premature) evaluation by wrapping them in a lambda.

> Ist der 1. Mai Feiertag in Jersey?

Nein.

-Matthias
From: P.C.
Subject: Re: Lisp theory question
Date: 
Message-ID: <3ccffd31$0$49153$edfadb0f@dspool01.news.tele.dk>
Hi.

"Wolfhard Bu�" <·····@gmx.net> skrev i en meddelelse
···················@buss-14250.user.cis.dfn.de...
> Matthias Blume <········@shimizu-blume.com> writes:
>
> > You said: "Conditional expressions can't be Lisp functions."
> > But they can, unless you take the narrow view that by "conditional
> > expression" you mean precisely McCarthy's COND.  However, with LAMBDA
> > you don't even need McCarthy's COND....
>
> With lambda you don't even need Rochester's label, which is not
> a defun btw.
> Your conditionals are Lisp functions, since they are thunky strict
> simulations of conditional expressions, which are nonstrict specials.
>
> Ist der 1. Mai Feiertag in Jersey?

But Eq return either T or Nil , so couldn't you construct Cond from Eq.

P.C.
From: Wolfhard Buß
Subject: Re: Lisp theory question
Date: 
Message-ID: <m37kmqk9os.fsf@buss-14250.user.cis.dfn.de>
"P.C." <··········@privat.dk> writes:

> Pure Lisp refere to constructing everything with only
> 5 primitive functions; Car, Cdr, Cons, Atom and Eq.
> With those, you shuld be able to program just everything,
> this is "Pure Lisp".

This is poor Lisp. So today there are at least three well known
families of Lisp.
The pure Lisp family of programming languages, the poor Lisp family
of programming languages and the rich Lisp family of programming
languages. There is possibly some overlap between the families ...

-- 
"Das Auto hat keine Zukunft. Ich setze aufs Pferd."  Wilhelm II. (1859-1941)
From: Matthias Blume
Subject: Re: Lisp theory question
Date: 
Message-ID: <fo7kmq7eao.fsf@blume-pcmh.research.bell-labs.com>
·····@gmx.net (Wolfhard Bu�) writes:

> "P.C." <··········@privat.dk> writes:
> 
> > Pure Lisp refere to constructing everything with only
> > 5 primitive functions; Car, Cdr, Cons, Atom and Eq.
> > With those, you shuld be able to program just everything,
> > this is "Pure Lisp".
> 
> This is poor Lisp. So today there are at least three well known
> families of Lisp.
> The pure Lisp family of programming languages, the poor Lisp family
> of programming languages and the rich Lisp family of programming
> languages. There is possibly some overlap between the families ...

There are at least tree families of puns...
From: Geoff Summerhayes
Subject: Re: Lisp theory question
Date: 
Message-ID: <uOdz8.57668$zj6.1706124@news2.calgary.shaw.ca>
"Matthias Blume" <········@shimizu-blume.com> wrote in message
···················@blume-pcmh.research.bell-labs.com...
> ·····@gmx.net (Wolfhard Bu�) writes:
>
> There are at least tree families of puns...

Not to mention age, I like puns that are fully groan.