By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
458,053 Members | 1,251 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 458,053 IT Pros & Developers. It's quick & easy.

Church's lambda calculus

P: n/a
Q1) Has anyone seen a treatment of Dr. Church's lambda calculus that uses C
instead of an obscure language designed for logic?

Q2) How does access the forum archives? MPJ
Nov 14 '05 #1
Share this Question
Share on Google+
21 Replies


P: n/a
"Merrill & Michele" <be********@comcast.net> wrote in message
news:Of********************@comcast.com...
Q1) Has anyone seen a treatment of Dr. Church's lambda calculus that uses C instead of an obscure language designed for logic?
I haven't. But then again, I never looked. :-)
Q2) How does access the forum archives?


Visit www.groups.google.com

-Mike
Nov 14 '05 #2

P: n/a
In article <Of********************@comcast.com>,
Merrill & Michele <be********@comcast.net> wrote:
Q1) Has anyone seen a treatment of Dr. Church's lambda calculus that uses C
instead of an obscure language designed for logic?


Doubtful, since C doesn't lend itself well to working with lambda
calculus (the world-view of the two models is too different).

If you want to find a treatment of the lambda calculus that uses a
programming language rather than mathematical notation, you're better
off looking at a functional language like Scheme.
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca
I would lodge a serious QOI complaint with the compiler vendor if either of
these reformatted my nose or caused Scott Nudds to fly out of my hard drive.
--Jack Klein in comp.lang.c
Nov 14 '05 #3

P: n/a
On Fri, 10 Sep 2004 16:48:42 +0000, Dave Vandervies wrote:

<snip>
If you want to find a treatment of the lambda calculus that uses a
programming language rather than mathematical notation, you're better
off looking at a functional language like Scheme.


Or, if you don't like all those parentheses, Perl:
http://perl.plover.com/lambda/
Nov 14 '05 #4

P: n/a
Merrill & Michele wrote:

Q1) Has anyone seen a treatment of Dr. Church's lambda
calculus that uses C
instead of an obscure language designed for logic?

Q2) How does access the forum archives? MPJ


http://groups.google.com/groups?selm...an.ccrwest.org

That post has the term "lambda calculus" in it,
in reference to a program called loader.c,
but I don't understand a lot of that post.

--
pete
Nov 14 '05 #5

P: n/a
....snip...

Thank you all for your replies. I apologize for sloppy posts, as I do not
read well off the screen and am now attempting my first pasting in of a
message that antecedently exists as a hard copy.

1) Mr. Wahler I thank for his link to the archives. My follow-up
question is: does there exist a server on which there exists the posts of
comp.lang.c for the last n years?

2) To Mr. Bart I ask: Do you know anyone outside of the academy who
uses Scheme? As for Perl, I'm too old a dog..

3) Mr. Vandervies, you don't seriously doubt the inability of C to
make Scott Nudds fly? Can the same be said of Richard Heathfield and MY
hard drive?

4) Pete: A very interesting program. Worth looking at.

Again thanks all. MPJ
Nov 14 '05 #6

P: n/a
Merrill & Michele wrote:
1) Mr. Wahler I thank for his link to the archives. My follow-up
question is: does there exist a server on which there exists the posts of
comp.lang.c for the last n years?
<URL:http://groups.google.com/>, in particular
<URL:http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&group=comp.lang.c>
2) To Mr. Bart I ask: Do you know anyone outside of the academy who
uses Scheme? As for Perl, I'm too old a dog..


Both Scheme and Lisp are alive and kicking in a number of commercial
products. These products are used by people as varied as medical
diagnosticians to political campaign strategists.
Nov 14 '05 #7

P: n/a
snip
1) Mr. Wahler I thank for his link to the archives. My follow-up
question is: does there exist a server on which there exists the posts of comp.lang.c for the last n years?


<URL:http://groups.google.com/>, in particular
<URL:http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&group=comp.lang.c>

As I activate the latter link and enter "foo", the search engine tells me
that I'm looking for "foo fighters". If I needed more fighters, I'd drive
two miles to the Teamsters. I refuse to believe that it hasn't dawned on
someone with minor means to serialize this forum.


2) To Mr. Bart I ask: Do you know anyone outside of the academy who uses Scheme? As for Perl, I'm too old a dog..


Both Scheme and Lisp are alive and kicking in a number of commercial
products. These products are used by people as varied as medical
diagnosticians to political campaign strategists.


Are Scheme and Lisp basically the same things? That monkeys (=political
campaign folks) tap keyboards does not impress this Ohio native. Smear
tactics seem to win the day in the battle of the dirigibles. Do I recall
correctly from diagnostics that it ploughed through user-defined cases? MPJ
Nov 14 '05 #8

P: n/a
"Merrill & Michele" <be********@comcast.net> wrote in message news:<DJ********************@comcast.com>...
snip
http://groups.google.com/groups?hl=e...up=comp.lang.c

As I activate the latter link and enter "foo", the search engine tells me that I'm looking for "foo fighters".


Make sure you click on the "search only in comp.lang.c.*" button
before doing your search, otherwise it will search all newsgroups.
Nov 14 '05 #9

P: n/a
On Fri, 10 Sep 2004 19:32:41 -0500, Merrill & Michele wrote:
2) To Mr. Bart I ask: Do you know anyone outside of the academy who
uses Scheme? As for Perl, I'm too old a dog..


First, my name is Barts, not Bart. I don't know why people drop the final
s.

Scheme, in the form of the Guile system, is the official extension
language of the GNU Project. That is, people are encouraged to write
programs that include the Guile Scheme interpreter so people can extend
those applications without recompiling them.

Lisp, in the form of Emacs Lisp, is the most powerful and probably the
most-used programming language included with a text editor. You can do a
web search for Emacs and Emacs extensions to find many examples of people
writing real programs in Emacs Lisp.

Scheme and Lisp are two closely related languages, in that they share a
common lineage and have many elements in common. Someone skilled in a Lisp
dialect can learn Scheme very easily, and vice-versa.

Nov 14 '05 #10

P: n/a
"Merrill & Michele" <be********@comcast.net> wrote:
Q1) Has anyone seen a treatment of Dr. Church's lambda calculus that uses C
instead of an obscure language designed for logic?


You can do it in C++, eg. look at the Boost Lambda library
Nov 14 '05 #11

P: n/a

snip
Thank you again for replies. To Mr. Barts I apologize for the type of
inconsideration that makes me furious. I can, in my defense, only claim
that the theologian Karl Barth is so deeply etched in my mind that my neural
pathways have hardened too much around that spelling. So we have Scheme for
linux, LISP for macs, and squat for windows?

Mr. Hayes, can a person search by date or the name who is posting in the
forum?

Old Wolf, is there something about boost lambda that makes it untopical
here? I think it says a hell of a lot about comp sci that when EBDI don't
know was extended to ascii, they included the ever useful char 190: ? and
not lambda, therewith thumbing their noses at the 20th century's greatest
physicist and logician simultaneously. MPJ
Nov 14 '05 #12

P: n/a
On Sun, 12 Sep 2004 14:15:41 -0500, Merrill & Michele wrote:

snip
Thank you again for replies. To Mr. Barts I apologize for the type of
inconsideration that makes me furious. I can, in my defense, only claim
that the theologian Karl Barth is so deeply etched in my mind that my neural
pathways have hardened too much around that spelling. So we have Scheme for
linux, LISP for macs, and squat for windows?


Your misspelling doesn't annoy me, but I do like to see it spelled
correctly.

Both Emacs and Guile will work just fine on Windows, especially versions
newer than Windows 3.11. You need only to search the Internet to find the
files to download (http://www.google.com gives good results). Those tools
may have been born in a Unix environment, but they have not stayed there.
Nov 14 '05 #13

P: n/a
On Sun, 12 Sep 2004 14:15:41 -0500, in comp.lang.c , "Merrill & Michele"
<be********@comcast.net> wrote:

snip
Thank you again for replies. To Mr. Barts I apologize for the type of
inconsideration that makes me furious. I can, in my defense, only claim
that the theologian Karl Barth is so deeply etched in my mind that my neural
pathways have hardened too much around that spelling. So we have Scheme for
linux, LISP for macs, and squat for windows?
Who knows? This is comp.lang.c
Mr. Hayes, can a person search by date or the name who is posting in the
forum?
Why not try?Old Wolf, is there something about boost lambda that makes it untopical
here?


Its written in C++. This is comp.lang.c
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 14 '05 #14

P: n/a
snip
You can do it in C++, eg. look at the Boost Lambda library


I think the final word is that it's impossible in C because of things like
polymorphism and probably ill-advised in C++. The following link seemed to
has it out pretty well.

http://www.osnews.com/comment.php?ne...set=15&rows=30

Oh well. MPJ
Nov 14 '05 #15

P: n/a
In article <Ld********************@comcast.com>,
Merrill & Michele <be********@comcast.net> wrote:
3) Mr. Vandervies, you don't seriously doubt the inability of C to
make Scott Nudds fly?
I believe the code that the comment in my sig that it appears you
are responding to was made about invoked a relatively tame form of
undefined behavior. There is nothing in the standard defining the
language that directly allows code to make Scott Nudds fly; however,
one of the consequences of the definition of undefined behavior is that
there's nothing in the standard that forbids the compiler from generating
compiled code that does such a thing when presented with source code
that invokes undefined behavior.

Can the same be said of Richard Heathfield and MY
hard drive?


Well, if your implementation was made by a sufficiently talented and
creative implementor, there's nothing in the C standard preventing this
code from making Richard Heathfield fly out of your hard drive:
--------
void main(double **x)
{
int i;
printf("%u%g\n",*x,i);
}
--------
Finding an implementation from a sufficiently talented and creative
implementor (and running on hardware capable of doing such a thing)
is Left As An Exercise.
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca
It's the sort of programming paradigm I'd be perfectly happy for my son to be
seen with in the street, provided of course that the memory does eventually
get freed correctly in the end. --Richard Heathfield in comp.lang.c
Nov 14 '05 #16

P: n/a
Merrill & Michele wrote:
Q1) Has anyone seen a treatment of Dr. Church's lambda calculus that

uses C instead of an obscure language designed for logic?

Embedding the lambda calculus in C directly is difficult due to its lack
of closures, but it's relatively trivial to write a lambda calculus
*simulator* in C. You simply create a tagged union of structures, one
for a lambda, one for an application, and one for variables (you may
want one for atoms too), each containing a tag field indicating which
one it is (union semantics allow this), and referencing one another. You
then create some functions to dynamically allocate and initialize the
various types of objects, and a simple recursive evaluation function,
and then you're ready to plug in lambda expressions and watch it go.
--
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.
Nov 14 '05 #17

P: n/a
"Merrill & Michele" <be********@comcast.net> wrote in message news:<Up********************@comcast.com>...
So we have Scheme for linux, LISP for macs, and squat for windows? His example of LISP was on emacs (which is not related to the Apple
Macintosh computer).
Scheme is used by many apps, including the Guile dialect (used in many
GNU programs, including the GIMP Photoshop-style image editing
software) and other dialects.
To the best of my knowledge, all of the above applications will work
on many OSes (including Windows 95/XP/NT, Macintosh OS X, and Linux) Mr. Hayes, can a person search by date or the name who is posting in the
forum? Investigate the "Advanced Search" link that is right next to the area
where you enter your search terms.
Try to play around with the options--you won't break anything and you
might learn rather a lot. If you have questions, try the help page at
http://groups.google.com/help/index.html or posting questions at a
google or internet help site rather than here (which is, after all, a
C programming group). Old Wolf, is there something about boost lambda that is offtopic here

Boost is a C++ library; this newsgroup doesn't deal with C++.
comp.lang.c++ deals with C++, but I don't know if Boost is pure C++
(in which case comp.lang.c++ is the right place to discuss it) or uses
the features of particular platforms (in which case the
platform-specific newsgroup should be used).
Nov 14 '05 #18

P: n/a

In article <41***********@mindspring.com>, pete <pf*****@mindspring.com> writes:
Merrill & Michele wrote:

Q1) Has anyone seen a treatment of Dr. Church's lambda
calculus that uses C instead of an obscure language designed for logic?


http://groups.google.com/groups?selm...an.ccrwest.org

That post has the term "lambda calculus" in it,
in reference to a program called loader.c,
but I don't understand a lot of that post.


It appears from the post (haven't looked at the program myself) that
loader.c implements a particular lambda calculus, but not lambda
calculus in general, and the calculus it does implement is
implemented using a rather compact notation, which is to say it's not
particularly user-friendly. While it looks like an interesting
program, it's probably not what MPJ had in mind, which I imagine was
something more suitable for conveniently evaluating general lambda
calculus expressions.

Other posters have recommended LISP and Scheme, which do fit that
description, and can be implemented in C; but apparently MPJ isn't
looking for another whole programming language implemented in C, but
something that makes it convenient to perform lambda calculus in a C
program (or maybe just an interactive lambda calculus application
written in C?). Which is a perfectly reasonable thing to be looking
for, I suppose.

Sourceforge lists a project called LCI, which is supposed to be a
lambda calculus interpreter written in C; but it says that no files
have been released yet. The project home page[1], on the other hand,
has a link to download a CVS snapshot. Might be worth a look.
1. http://lci.sourceforge.net/

--
Michael Wojcik mi************@microfocus.com

A coding theorist is someone who doesn't think Alice is crazy. -- John Gordon
Nov 14 '05 #19

P: n/a

In article <Up********************@comcast.com>, "Merrill & Michele" <be********@comcast.net> writes:

I think it says a hell of a lot about comp sci that when EBDI don't
know was extended to ascii, they included the ever useful char 190: ? and
not lambda, therewith thumbing their noses at the 20th century's greatest
physicist and logician simultaneously.


What it says is that the development of ASCII was driven by commercial
computing concerns, and not computer science. ASCII (which is not
an "extension" of EBCDIC, if that's what you were referring to) is
a 7-bit code. It had to include upper- and lowercase English letters,
decimal digits, basic punctuation marks, and control codes; with only
128 code points, that doesn't leave a lot of room. You're welcome to
look at some of the documents on the history of ASCII (there are many
available on the net) and second-guess the committees that developed
it, but I don't think you'll get much agreement among computer
programmers, or computer scientists, or even physicists and logicians
that the omission of lambda was either regretable or an insult to
Alonzo Church.

That said, this is off-topic for comp.lang.c. It would be on-topic
for, say, alt.folklore.computers, where such speculations are
welcome.

--
Michael Wojcik mi************@microfocus.com

Unfortunately, as a software professional, tradition requires me to spend New
Years Eve drinking alone, playing video games and sobbing uncontrollably.
-- Peter Johnson
Nov 14 '05 #20

P: n/a
On Mon, 13 Sep 2004 13:55:28 -0500, Merrill & Michele wrote:
snip
You can do it in C++, eg. look at the Boost Lambda library


I think the final word is that it's impossible in C because of things like
polymorphism and probably ill-advised in C++. The following link seemed to
has it out pretty well.

http://www.osnews.com/comment.php?ne...set=15&rows=30

Oh well. MPJ


It is /not/ impossible in C, and anyone who thinks so has a very limited
worldview. As a trivial argument, I would say that most Scheme
interpreters are written in C, and that the lambda calculus is trivially
implementable in Scheme.

A better argument would get into notions of effective computability and
the ability of a languages to express primitive recursion. Suffice it to
say, C can express primitive recursion just fine, and therefore any
algorithm expressable in the lambda calculus can be written in C. That,
and not piddling issues of syntax, is what matters.

As for run-time polymorphism, it is merely somewhat difficult, and is a
problem often solved. A struct containing a union and a pointer to void
would suffice to create a fully dynamic type, albeit by giving up a bit of
type hygiene in the process. In any case, the ability to define
arbitrarily complex compound types (structs and unions) gives a subtle
power to C's type system that can usually be used to get around the
limitations in the base language.

Nov 14 '05 #21

P: n/a
> > I think the final word is that it's impossible in C because of things
like
polymorphism and probably ill-advised in C++.
It is /not/ impossible in C, and anyone who thinks so has a very limited worldview.

....snip...
That's a little snippy. Sie wollen meine Weltanschauung nicht in Frage
stellen.

A better argument would get into notions of effective computability and
the ability of a languages to express primitive recursion. Suffice it to
say, C can express primitive recursion just fine, and therefore any
algorithm expressable in the lambda calculus can be written in C. That,
and not piddling issues of syntax, is what matters.

As for run-time polymorphism, it is merely somewhat difficult, and is a
problem often solved. A struct containing a union and a pointer to void
would suffice to create a fully dynamic type, albeit by giving up a bit of
type hygiene in the process. In any case, the ability to define
arbitrarily complex compound types (structs and unions) gives a subtle
power to C's type system that can usually be used to get around the
limitations in the base language.


Well said. I guess when I threw in the towel with lambda calc and c I meant
that I don't think that much is ever going to get done with it. As for c++,
the lambda calc will only be discernable if you're cross-eyed. The word the
germans like is "Verzerrung." The reason to develop along these lines will,
IMO, go unrealized. MPJ
Nov 14 '05 #22

This discussion thread is closed

Replies have been disabled for this discussion.