What other languages, besides Lisp, have Lisp-level macros? I've
searched faqs and google, but have been unable to derive the magic
incantation.
Specifically, I need compile-time side-effects, not just syntax
translation. As long as the compile-time side-effects can do things
like file io and function calls, it should suffice. GUI stuff would be
nice, too.
Thanks,
Steve
sed 's/j/st/' ·········@hotmail.com
In article <····················@sccrnsc04>, Steve Tu <·@b.com> wrote:
>What other languages, besides Lisp, have Lisp-level macros? I've
>searched faqs and google, but have been unable to derive the magic
>incantation.
The only examples I can think of are some special-purpose languages that
have been implemented in Lisp. For instance, Symbolics had LIL, a
Lisp-like assembly language that they used to program the Lisp Machine's
FEP. And Maclisp had LAP, Lisp Assembly Program; it was an assembler that
used Lisp-like syntax, and supported Lisp macros.
>Specifically, I need compile-time side-effects, not just syntax
>translation. As long as the compile-time side-effects can do things
>like file io and function calls, it should suffice. GUI stuff would be
>nice, too.
A compile-time GUI? Although Lisp macros don't have any inherent limits,
I've never heard of anyone making use of the GUI (or any other user
interaction other than printing warning messages) at compile time.
--
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.
Barry Margolin <······@genuity.net> writes:
> >Specifically, I need compile-time side-effects, not just syntax
> >translation. As long as the compile-time side-effects can do things
> >like file io and function calls, it should suffice. GUI stuff would be
> >nice, too.
>
> A compile-time GUI? Although Lisp macros don't have any inherent limits,
> I've never heard of anyone making use of the GUI (or any other user
> interaction other than printing warning messages) at compile time.
I've never made GUI calls from a macro, but I have used CERROR before.
One example: a fairly large system of macros for describing a specific
RISC-like architecture -- the way this system was written, it's
possible to specify a circularity that needs to be broken. Rather
than just crap out with an ERROR, I had it complain with CERROR,
giving the person writing the definition a chance to fix the
circularity and continue.
I admit, it's probably unusual to do so, but I don't think using
CERROR in a macro is that out-there.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Barry Margolin wrote:
> A compile-time GUI? Although Lisp macros don't have any inherent limits,
> I've never heard of anyone making use of the GUI (or any other user
> interaction other than printing warning messages) at compile time.
Does the interactive mode provided by TeX/LaTeX count?
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Steve Tu wrote:
> What other languages, besides Lisp, have Lisp-level macros? I've
> searched faqs and google, but have been unable to derive the magic
> incantation.
AFAIK, templates in C++ are used for similar purposes like Lisp macros,
and they are Turing-complete at compile-time. You might want to look for
"generative programming" and the book of the same name - see
http://www.awprofessional.com/catalog/product.asp?product_id={6FE1A971-D2D9-4983-A9EF-3F2B341ED0B7}
Furthermore, Jonathan Bachrach is working on macro systems, for example
for Dylan and Java, and provides good sections on related work in his
papers. See http://www.ai.mit.edu/~jrb/
Logic meta-programming might also be of interest, see
http://progwww.vub.ac.be:8080/DMP and http://tyruba.sourceforge.net/
I hope this helps.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
<········@web.de> wrote:
> AFAIK, templates in C++ are used for similar purposes like Lisp macros,
> and they are Turing-complete at compile-time.
That would be news to me. Do you have a reference (other than the
generative programming book?)
E.
In article <····················@k-137-79-50-101.jpl.nasa.gov>,
···@jpl.nasa.gov (Erann Gat) wrote:
> In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <········@web.de> wrote:
>
> > AFAIK, templates in C++ are used for similar purposes like Lisp macros,
> > and they are Turing-complete at compile-time.
>
> That would be news to me. Do you have a reference (other than the
> generative programming book?)
The following URL seems to provide a nice introduction. (I have just
skipped it briefly.)
http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html
It doesn't seem to provide an example of a class that is subclass of
itself, but I have seen something along these lines in a talk. I may be
able to track this down tomorrow if you are interested.
My impression is that this stuff is theoretically interesting but not
suitable for practical use. To me, this view is supported by the fact
that the Turing completeness of templates was not designed into C++ but
was essentially a historical accident. Logic meta-programming seems to
be much more coherent to me. (...or Lisp macros as an alternative
approach)
But I have to stress again that I don't have indepth knowledge about how
this is actually used in real C++ programs. So please take my statements
with a grain of salt.
Pascal
--
"If I could explain it, I wouldn't be able to do it."
A.M.McKenzie
In article <······························@news.netcologne.de>, Pascal
Costanza <········@web.de> wrote:
> http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html
> My impression is that this stuff is theoretically interesting but not
> suitable for practical use.
Well... it's suitable for practical use in some cases, but it's not
Turing-complete. Since built-in types can be template parameters, you can
do compile-time computation as long as the only data you're using in the
computations are built-in types (which pretty much means ints and
floats). This is not Turing-complete because the built-in types are all
fixed-size and all allocation is static. To be Turing-complete you have
to be able to do dynamic allocation, otherwise what you have is a
finite-state machine, not a Turing machine.
But this is really beside the point. What really matters is that
templates don't really allow you to do any kind of syntax abstraction.
For example, you couldn't implement something like the LOOP macro as a
template except by encoding all the keywords as numbers, which would
rather defeat the purpose IMO.
E.
On Mon, 03 Feb 2003 14:36:58 -0800, ···@jpl.nasa.gov (Erann Gat)
wrote:
>In article <······························@news.netcologne.de>, Pascal
>Costanza <········@web.de> wrote:
>
>> http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html
>
>> My impression is that this stuff is theoretically interesting but not
>> suitable for practical use.
>
>Well... it's suitable for practical use in some cases, but it's not
>Turing-complete. Since built-in types can be template parameters, you can
>do compile-time computation as long as the only data you're using in the
>computations are built-in types (which pretty much means ints and
>floats). This is not Turing-complete because the built-in types are all
>fixed-size and all allocation is static. To be Turing-complete you have
>to be able to do dynamic allocation, otherwise what you have is a
>finite-state machine, not a Turing machine.
Well another idiot who spouts off about C++ without knowing much
about C++. I would suggest he read the C++ standard but I know he
won't bother--he's made his mind up he's not going to learn the facts.
( BTW he's strongly suggests that built-in types are the only ones
things that are valid template parameters. Even someone taking C++
101 knows this isn't true. )
There are lots and lots of examples but the two ( aside from C++ )
that I am most familiar with are OCaml's camlp4 preprocessor,
but from the online documentation I see it is no longer supported
( aparently there was a spat among the group ), and a suggestion
to add templates to Haskell by Peyton-Jones:
http://research.microsoft.com/Users/simonpj/
In article <··································@4ax.com>,
······@interaccess.com wrote:
> On Mon, 03 Feb 2003 14:36:58 -0800, ···@jpl.nasa.gov (Erann Gat)
> wrote:
>
> >In article <······························@news.netcologne.de>, Pascal
> >Costanza <········@web.de> wrote:
> >
> >> http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html
> >
> >> My impression is that this stuff is theoretically interesting but not
> >> suitable for practical use.
> >
> >Well... it's suitable for practical use in some cases, but it's not
> >Turing-complete. Since built-in types can be template parameters, you can
> >do compile-time computation as long as the only data you're using in the
> >computations are built-in types (which pretty much means ints and
> >floats). This is not Turing-complete because the built-in types are all
> >fixed-size and all allocation is static. To be Turing-complete you have
> >to be able to do dynamic allocation, otherwise what you have is a
> >finite-state machine, not a Turing machine.
> Well another idiot who spouts off about C++ without knowing much
> about C++. I would suggest he read the C++ standard but I know he
> won't bother--he's made his mind up he's not going to learn the facts.
> ( BTW he's strongly suggests that built-in types are the only ones
> things that are valid template parameters. Even someone taking C++
> 101 knows this isn't true. )
Well, another idiot who spouts off about someone's knowledge of C++
without knowing much about anything. Sure, C++ templates are
Turing-complete, but so are Turing machines, and no sane person considers
that fact to be anything more than an interesting bit of mathematical
trivia (albeit with some historical interest). If you want to dispute
that, show me the code that computes factorial<1000> at compile time.
E.
Hello!
Erann Gat <···@jpl.nasa.gov> wrote:
>[...]
>Well, another idiot who spouts off about someone's knowledge of C++
>without knowing much about anything. Sure, C++ templates are
>Turing-complete, but so are Turing machines, and no sane person considers
>that fact to be anything more than an interesting bit of mathematical
>trivia (albeit with some historical interest). If you want to dispute
>that, show me the code that computes factorial<1000> at compile time.
SUCKY SLOW MEMORY EATING CODE BELOW:
struct Zero {};
template <typename Pred>
struct Successor {
typedef Pred Predecessor;
};
// now we can count
template <unsigned int num>
struct Int2SuckyNumber {
typedef typename Int2SuckyNumber<num - 1>::value predvalue_;
typedef typename Successor<predvalue_> value;
};
template <>
struct Int2SuckyNumber<0> {
typedef Zero value;
};
// Now we can convert ints to sucky numbers
typedef Int2SuckyNumber<1000>::value SuckyThousand;
// now for adding
template <typename A, typename B>
struct Add {};
template <typename B>
struct Add<Zero, B> {
typedef B value;
};
template <typename A, typename B>
struct Add<Successor<A>, B> {
typedef typename Add<A, B>::value value_tmp_;
typedef typename Successor<value_tmp_> value;
};
// that's it. Sucky but should work
template <typename A, typename B>
struct Mul {};
template <typename B>
struct Mul<Zero, B> {
typedef Zero value;
};
template <typename A, typename B>
struct Mul<Successor<A>, B> {
typedef typename Mul<A, B>::value value_tmp_;
typedef typename Add<A, value_tmp_>::value value;
};
// that's the multiplier
template <typename A>
struct Factorial {};
template <>
struct Factorial<Zero> {
typedef Successor<Zero> value;
};
template <typename A>
struct Factorial<Successor<A> > {
typedef typename Factorial<A>::value value_tmp_;
typedef typename Mul<Successor<A>, value_tmp_>::value value;
};
// Now the factorial of thousand
typedef Factorial<SuckyThousand>::value FactOfThousand;
Printing out the result is left as exercise (implement some operation
that does the equivalent of (lambda (x) (floor x 10)), use that to
build a reversed cons list of ASCII characters, convert that to
a static function printing out the digits, call that single static
function from main()).
A more efficient implementation is left as exercise to the reader, too
(using N-adic digits to build compile time bignums).
SCNR,
Hannah.
In article <············@c3po.schlund.de>, ······@schlund.de (Hannah
Schroeter) wrote:
> Hello!
Howdy.
> Erann Gat <···@jpl.nasa.gov> wrote:
> >Sure, C++ templates are
> >Turing-complete, but so are Turing machines, and no sane person considers
> >that fact to be anything more than an interesting bit of mathematical
> >trivia (albeit with some historical interest). If you want to dispute
> >that, show me the code that computes factorial<1000> at compile time.
>
> SUCKY SLOW MEMORY EATING CODE BELOW:
[snip]
Very impressive. This was a little disappointing though:
> Printing out the result is left as exercise
Makes it a little hard to tell if your code actually works, no?
Still, just the fact that you produced a plausible-looking answer gets my
vote for heroic coding effort of the week.
E.
From: Joe Marshall
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <adh8xi9h.fsf@ccs.neu.edu>
······@schlund.de (Hannah Schroeter) writes:
>
> SUCKY SLOW MEMORY EATING CODE BELOW:
[Snip]
I do hope that you are not proud of what you have accomplished.
I promise not to tell anyone about it if you promise not to do it
again.
On 07 Feb 2003 09:44:26 -0500, Joe Marshall <···@ccs.neu.edu> wrote:
>······@schlund.de (Hannah Schroeter) writes:
>
>>
>> SUCKY SLOW MEMORY EATING CODE BELOW:
>[Snip]
>
>I do hope that you are not proud of what you have accomplished.
Why not? It strikes me as an impressive feat to write a 70-line
program whose compile time (if I'm understanding correctly how it
works) would exceed the lifespan of the universe ^.^ (Of course it was
never claimed to be of practical use, but it's an impressive
intellectual exercise.)
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
From: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey3d6lyskmp.fsf@cley.com>
* Russell Wallace wrote:
> Why not? It strikes me as an impressive feat to write a 70-line
> program whose compile time (if I'm understanding correctly how it
> works) would exceed the lifespan of the universe ^.^ (Of course it was
> never claimed to be of practical use, but it's an impressive
> intellectual exercise.)
Surely the point is that you could *far* more easily write a program
in CL whose compile time was enormously long. In particular: take a
computationally complex problem, express it as a macro, compile (or
start compiling) the macro definition and function which calls that
macro.
--tim
Tim Bradshaw <···@cley.com> writes:
> Surely the point is that you could *far* more easily write a program
> in CL whose compile time was enormously long. In particular: take a
(eval-when (:compile-toplevel) (loop))
-dan
--
http://www.cliki.net/ - Link farm for free CL-on-Unix resources
On 11 Feb 2003 19:05:50 +0000, Tim Bradshaw <···@cley.com> wrote:
>Surely the point is that you could *far* more easily write a program
>in CL whose compile time was enormously long.
Of course you could. It's also far easier to drive 26 miles than run
it on foot, but some people have the strange habit of using the latter
mode of transport anyway :) C++ template metaprogramming, Intercal and
crossword puzzles are the intellectual equivalent of this.
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
······@schlund.de (Hannah Schroeter) writes:
> template <typename A, typename B>
> struct Mul<Successor<A>, B> {
> typedef typename Mul<A, B>::value value_tmp_;
> typedef typename Add<A, value_tmp_>::value value;
> };
That needs to be Add<B, value_tmp_>::value.
> Printing out the result is left as exercise (implement some operation
> that does the equivalent of (lambda (x) (floor x 10)), use that to
> build a reversed cons list of ASCII characters, convert that to
> a static function printing out the digits, call that single static
> function from main()).
I don't think it's possible to make just one function;
it's quite easy to inline a chain of functions, though.
template <typename A>
struct Floor10 {};
template <>
struct Floor10<Zero> {
typedef Zero quotient;
enum { remainder = 0 };
};
template <typename A>
struct Floor10<Successor<A> > {
typedef Zero quotient;
enum { remainder = Floor10<A>::remainder + 1 };
};
template <typename A>
struct Floor10<Successor<Successor<Successor<Successor<Successor
<Successor<Successor<Successor<Successor<Successor
<A> > > > > > > > > > > {
typedef Successor<typename Floor10<A>::quotient> quotient;
enum { remainder = Floor10<A>::remainder };
};
#include <iostream>
#include <ostream>
template <typename A>
inline void write_number(std::ostream &os) {
write_number<typename Floor10<A>::quotient>(os);
os << char('0' + Floor10<A>::remainder);
}
template <>
inline void write_number<Zero>(std::ostream &) {}
int main() {
typedef Int2SuckyNumber<5>::value SuckyX;
typedef Factorial<SuckyX>::value FactOfX;
write_number<FactOfX>(std::cout);
}
Erann Gat wrote:
> In article <······························@news.netcologne.de>, Pascal
> Costanza <········@web.de> wrote:
>
>
>>http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html
>
>
>>My impression is that this stuff is theoretically interesting but not
>>suitable for practical use.
>
>
> Well... it's suitable for practical use in some cases, but it's not
> Turing-complete. Since built-in types can be template parameters, you can
> do compile-time computation as long as the only data you're using in the
> computations are built-in types (which pretty much means ints and
> floats). This is not Turing-complete because the built-in types are all
> fixed-size and all allocation is static. To be Turing-complete you have
> to be able to do dynamic allocation, otherwise what you have is a
> finite-state machine, not a Turing machine.
I have just checked out the book on "Generative Programming" again. Here
is a quote: "Surprisingly, templates together with a number of other C++
features constitute a Turing-complete, compile-time sublanguage of C++."
The chapter then proceeds with details on how to implement control and
data structures on top of these features.
The history section mentions the following reference...
E. Unruh. Prime number computation. ANSI X3J16-94-0075/SO WG21-462.
...and other references mainly from http://www.oonumerics.org/blitz/papers/
> But this is really beside the point. What really matters is that
> templates don't really allow you to do any kind of syntax abstraction.
> For example, you couldn't implement something like the LOOP macro as a
> template except by encoding all the keywords as numbers, which would
> rather defeat the purpose IMO.
Right. The "Generative Programming" book mentions a list of other
problems with the template meta-programming approach. They include lack
of debugging support, lack of error reporting, poor readability of the
code, poor compilation times, compiler limits, limitations of expression
templates, poor portability. The authors acknowledge the "template
metaprogramming is not a result of a careful language design but an
accident." Funny though that this topic is covered so deeply in that book.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
From: Joe Marshall
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <k7gg9kb9.fsf@ccs.neu.edu>
Pascal Costanza <········@web.de> writes:
> The "Generative Programming" book mentions a list of other
> problems with the template meta-programming approach. They include
> lack of debugging support, lack of error reporting, poor readability
> of the code, poor compilation times, compiler limits, limitations of
> expression templates, poor portability.
Aren't these the original problems of C++?
Joe Marshall <···@ccs.neu.edu> writes:
> Pascal Costanza <········@web.de> writes:
>
> > The "Generative Programming" book mentions a list of other
> > problems with the template meta-programming approach. They include
> > lack of debugging support, lack of error reporting, poor readability
> > of the code, poor compilation times, compiler limits, limitations of
> > expression templates, poor portability.
>
> Aren't these the original problems of C++?
No. They are its features ;)
Mario.
Joe Marshall <···@ccs.neu.edu> writes:
> Pascal Costanza <········@web.de> writes:
>
> > The "Generative Programming" book mentions a list of other
> > problems with the template meta-programming approach. They include
> > lack of debugging support, lack of error reporting, poor readability
> > of the code, poor compilation times, compiler limits, limitations of
> > expression templates, poor portability.
>
> Aren't these the original problems of C++?
Yeah, so they decided to make them into features instead.
I find template metaprogramming kinda fun, in the same way the
international obfuscated C competion or INTERCAL are fun. That people
take it seriously is scary.
Cheers,
M.
--
SPIDER: 'Scuse me. [scuttles off]
ZAPHOD: One huge spider.
FORD: Polite though.
-- The Hitch-Hikers Guide to the Galaxy, Episode 11
From: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey365s0mh7g.fsf@cley.com>
* Pascal Costanza wrote:
> I have just checked out the book on "Generative Programming"
> again. Here is a quote: "Surprisingly, templates together with a
> number of other C++ features constitute a Turing-complete,
> compile-time sublanguage of C++." The chapter then proceeds with
> details on how to implement control and data structures on top of
> these features.
Isn't this kind of thing rather similar to the sense that vi turns out
to be Turing complete? It's an interesting thing, but it *doesn't*
mean you'd want to write code in it, or that you usefully can, since
there is no useful runtime, which tends to matter for real programs.
(Actually, vi may have a whole lot better support than C++ templates,
since you can, I guess, use editor file IO functionality!)
--tim
>>>>> "TB" == Tim Bradshaw <···@cley.com> writes:
TB> Isn't this kind of thing rather similar to the sense that vi
TB> turns out to be Turing complete? It's an interesting thing,
TB> but it *doesn't* mean you'd want to write code in it, or that
TB> you usefully can, since there is no useful runtime, which
TB> tends to matter for real programs.
IIRC, Conway's Game of Life was Turing complete too. It might be hell
to program in, but it would at least look really, really cool. :)
--
"There's no trick to being a humorist when you have the whole
government working for you."
--Will Rogers
In article <··············@theasylum.dyndns.org>, Tim Lavoie
<·······@acm.org> wrote:
>IIRC, Conway's Game of Life was Turing complete too. It might be hell
>to program in, but it would at least look really, really cool. :)
Its Design Patterns could be compiled into quite the coffee table book.
>>>>> "sv0f" == sv0f <····@vanderbilt.edu> writes:
sv0f> In article <··············@theasylum.dyndns.org>, Tim Lavoie
sv0f> <·······@acm.org> wrote:
>> IIRC, Conway's Game of Life was Turing complete too. It might
>> be hell to program in, but it would at least look really,
>> really cool. :)
sv0f> Its Design Patterns could be compiled into quite the coffee
sv0f> table book.
Yeah, it starts at the *lowest* level. Glider guns for clocks I think,
and other structures for logic gates.
--
Peace, n.:
In international affairs, a period of cheating between two
periods of fighting.
-- Ambrose Bierce, "The Devil's Dictionary"
Tim Lavoie <·······@acm.org> writes:
> >>>>> "TB" == Tim Bradshaw <···@cley.com> writes:
>
> TB> Isn't this kind of thing rather similar to the sense that vi
> TB> turns out to be Turing complete? It's an interesting thing,
> TB> but it *doesn't* mean you'd want to write code in it, or that
> TB> you usefully can, since there is no useful runtime, which
> TB> tends to matter for real programs.
>
> IIRC, Conway's Game of Life was Turing complete too. It might be hell
> to program in, but it would at least look really, really cool. :)
It has been proven constructively that a language can be turing
complete while being totally useless. Try
<http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/>
I like the passage on compilation:
<http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/#impl_comp>
Mario.
>>>>> "Mario" == Mario S Mommer <········@yahoo.com> writes:
Mario> It has been proven constructively that a language can be
Mario> turing complete while being totally useless. Try
Mario> <http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/>
Mario> I like the passage on compilation:
Mario> <http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/#impl_comp>
Heheh. Ditto for Befunge, Intercal, and many others. Though I must say
that I'm tempted to slip some Intercal into change-control docs at
work to see if anyone is awake downstairs.
--
Peace, n.:
In international affairs, a period of cheating between two
periods of fighting.
-- Ambrose Bierce, "The Devil's Dictionary"
Tim Bradshaw wrote:
> * Pascal Costanza wrote:
>
>
>>I have just checked out the book on "Generative Programming"
>>again. Here is a quote: "Surprisingly, templates together with a
>>number of other C++ features constitute a Turing-complete,
>>compile-time sublanguage of C++." The chapter then proceeds with
>>details on how to implement control and data structures on top of
>>these features.
>
>
> Isn't this kind of thing rather similar to the sense that vi turns out
> to be Turing complete? It's an interesting thing, but it *doesn't*
> mean you'd want to write code in it, or that you usefully can, since
> there is no useful runtime, which tends to matter for real programs.
Most probably yes. I am terribly sorry, but I have a tendency to answer
questions from an academic perspective. One of the reasons for the power
of Lisp macros is the fact that you have Turing-completeness at
compile-time. If someone (like the OP) asks whether there are other
languages that offer similar features, I tend to include template
metaprogramming for the sake of completeness. This doesn't mean that I
endorse it, nor that I find it useful in practice.
(However, it's interesting that there is a series of workshops and
conferences devoted to these topics, and I wonder why Lisp is
underrepresented in that community.)
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
From: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey3u1fkkswv.fsf@cley.com>
* Pascal Costanza wrote:
> (However, it's interesting that there is a series of workshops and
> conferences devoted to these topics, and I wonder why Lisp is
> underrepresented in that community.)
My guess is that this is because it's so much a solved problem in the
Lisp world. Why would Lisp people really be interested in `research'
which is reinventing something that Lisp has had for over 40 years?
--tim
Tim Bradshaw <···@cley.com> wrote in message news:<···············@cley.com>...
> * Pascal Costanza wrote:
>
> > (However, it's interesting that there is a series of workshops and
> > conferences devoted to these topics, and I wonder why Lisp is
> > underrepresented in that community.)
>
> My guess is that this is because it's so much a solved problem in the
> Lisp world. Why would Lisp people really be interested in `research'
> which is reinventing something that Lisp has had for over 40 years?
I, for one, would definitely be interested in being the Lisp asshole,
heckling everything that goes on at these conferences, whipping out on
my laptop the ten line Lisp equivalent of the result of every hour of
lecturing. ;)
I would need my own projector and screen that could be set up at the
back of whatever room that already has a projector and screen. This
way people could just conveniently turn around when I pipe up with
something, instead of me having to directly interfere with whatever is
going on at the front.
Sponsorship anyone? ;)
In article <····························@posting.google.com>,
···@ashi.footprints.net (Kaz Kylheku) wrote:
>I, for one, would definitely be interested in being the Lisp asshole,
>heckling everything that goes on at these conferences, whipping out on
>my laptop the ten line Lisp equivalent of the result of every hour of
>lecturing. ;)
>
>I would need my own projector and screen that could be set up at the
>back of whatever room that already has a projector and screen. This
>way people could just conveniently turn around when I pipe up with
>something, instead of me having to directly interfere with whatever is
>going on at the front.
>
>Sponsorship anyone? ;)
Sounds like a reality-based television show...
Tim Bradshaw wrote:
> * Pascal Costanza wrote:
>
>
>>(However, it's interesting that there is a series of workshops and
>>conferences devoted to these topics, and I wonder why Lisp is
>>underrepresented in that community.)
>
>
> My guess is that this is because it's so much a solved problem in the
> Lisp world. Why would Lisp people really be interested in `research'
> which is reinventing something that Lisp has had for over 40 years?
Good point.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
From: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey3lm0wkn64.fsf@cley.com>
* Pascal Costanza wrote:
>> My guess is that this is because it's so much a solved problem in the
>> Lisp world. Why would Lisp people really be interested in `research'
>> which is reinventing something that Lisp has had for over 40 years?
> Good point.
Of course, this is a fine example of why Lisp hasn't taken over the
world. Because we're all technical, rational people, we think `why
should I go to some conference on a solved problem, I have better and
more interesting things to do', while what we *should* all be doing is
turning up at these conferences and vomiting lisp propaganda
at people.
--tim
On Tue, Feb 04, 2003 at 04:47:47PM +0000, Tim Bradshaw wrote:
> Of course, this is a fine example of why Lisp hasn't taken over the
> world. Because we're all technical, rational people, we think `why
> should I go to some conference on a solved problem, I have better and
> more interesting things to do', while what we *should* all be doing is
> turning up at these conferences and vomiting lisp propaganda
> at people.
At which point they will begin to complain that we're all a bunch of
smug Lisp weenies, and close their minds.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
Matthew Danish wrote:
> On Tue, Feb 04, 2003 at 04:47:47PM +0000, Tim Bradshaw wrote:
>
>>Of course, this is a fine example of why Lisp hasn't taken over the
>>world. Because we're all technical, rational people, we think `why
>>should I go to some conference on a solved problem, I have better and
>>more interesting things to do', while what we *should* all be doing is
>>turning up at these conferences and vomiting lisp propaganda
>>at people.
>
>
> At which point they will begin to complain that we're all a bunch of
> smug Lisp weenies, and close their minds.
>
Ah, but there is no such thing as bad publicity.
Also: many are called, few are chosen.
Relevance of the above left as an exercise.
:)
btw, I now seem to have Cello (CL gui built on OpenGL) working under LW.
I'll let you know when it's a definite, in case it's any help to CL-SDL/LW.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Cells let us walk, talk, think, make love and realize
the bath water is cold." -- Lorraine Lee Cudmore
From: Joe Marshall
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <8ywvags7.fsf@ccs.neu.edu>
Tim Bradshaw <···@cley.com> writes:
> what we *should* all be doing is turning up at these conferences and
> vomiting lisp propaganda at people.
Vomiting is right. When I see intelligent people wasting time
attempting to implement macros in a language that requires a program
just to write the *parser* (and even then the grammar is ambiguous),
or when I see people investing a huge amount of energy make a static
type analyzer incrementally smarter so that it behaves more like a
dynamic type system, or when I see people implement lambda expressions
(of a sort) via C++ templates because `lisp is slow and bloated', it
almost makes me nauseous.
But these days you can't be a lisp hacker without a strong sense of
misanthropy. I've gotten to the point where I *recommend* Perl and
XML for complex projects (that I'm not involved it) just to see if
people are really that gullible. I haven't been disappointed either.
Tim Bradshaw wrote:
> * Pascal Costanza wrote:
>
>>>My guess is that this is because it's so much a solved problem in the
>>>Lisp world. Why would Lisp people really be interested in `research'
>>>which is reinventing something that Lisp has had for over 40 years?
>
>
>>Good point.
>
>
> Of course, this is a fine example of why Lisp hasn't taken over the
> world. Because we're all technical, rational people, we think `why
> should I go to some conference on a solved problem, I have better and
> more interesting things to do', while what we *should* all be doing is
> turning up at these conferences and vomiting lisp propaganda
> at people.
At least, the Common Lisp vendors should use these opportunities. ;-)
I also have this idea about a book that places some current topics into
their historical context. For example, Robert Hirschfeld and Kris Gybels
had submitted an "archaeological" paper about Smalltalk's features that
support unanticipated software evolution to a USE workshop. One could
write similar papers about how to do generative programming or
aspect-oriented programming in Lisp. I don't know. This idea does not
have enough substance (yet?), but something along these lines could
raise people's awareness of those "old-fashioned" languages.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Tim Bradshaw wrote:
> * Pascal Costanza wrote:
>
>>>My guess is that this is because it's so much a solved problem in the
>>>Lisp world. Why would Lisp people really be interested in `research'
>>>which is reinventing something that Lisp has had for over 40 years?
>>
>
>>Good point.
>
>
> Of course, this is a fine example of why Lisp hasn't taken over the
> world.
Somewhat relevant: someone from the nascent Lisp NYC Users Group
attended an XP meeting last night. Others mentioned Lisp unprovoked.
Then because lispnyc existed he was able to mention it, and who knows,
maybe lispnyc picks up a few potential lispers.
It occurred to me that the lispnyc's very existence helps Lisp, because
of the psychology thing, the herd issue, the "lisp is dead" issue. Who
uses Lisp? lispnyc. Will I be alone if I use Lisp? lispnyc. Is Lisp
dead? News to lispnyc.
I wonder how many other cities could support a LispUG.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Cells let us walk, talk, think, make love and realize
the bath water is cold." -- Lorraine Lee Cudmore
Kenny Tilton wrote:
>
>
> Tim Bradshaw wrote:
>>>> My guess is that this is because it's so much a solved problem in the
>>>> Lisp world. Why would Lisp people really be interested in `research'
>>>> which is reinventing something that Lisp has had for over 40 years?
>> Of course, this is a fine example of why Lisp hasn't taken over the
>> world.
>
>
> Somewhat relevant: someone from the nascent Lisp NYC Users Group
> attended an XP meeting last night. Others mentioned Lisp unprovoked.
> Then because lispnyc existed he was able to mention it, and who knows,
> maybe lispnyc picks up a few potential lispers.
>
> It occurred to me that the lispnyc's very existence helps Lisp, because
> of the psychology thing, the herd issue, the "lisp is dead" issue. Who
> uses Lisp? lispnyc. Will I be alone if I use Lisp? lispnyc. Is Lisp
> dead? News to lispnyc.
I have made the experience that there are at least some people in the
aspect-oriented community who would like to learn about Common Lisp in
order to learn something about the roots of these current buzzwords. I
guess that it would be a good idea to have some presence at those
workshops and conferences.
So here we go: There is an upcoming conference on generative programming
in Erfurt/Germany this year and they have a call for workshop proposals.
I have already been thinking about a European Lisp meeting/workshop at
that conference, and Sandro Pedrazzini has already agreed to co-organize
such a workshop. If we find another person as a co-organizer, we can
seriously start to work on a proposal. Here is the conference's webpage:
http://gpce.org/GPCE03/
Anyone?
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Pascal Costanza wrote:
>
>
> I have made the experience that there are at least some people in the
> aspect-oriented community who would like to learn about Common Lisp in
> order to learn something about the roots of these current buzzwords. I
> guess that it would be a good idea to have some presence at those
> workshops and conferences.
I am not up to speed to the latest of AOP. The original ideas seemed
very intriguing to me. However, I kind of got the impression that (at
least as the latest incarnations of AspectJ are concerned), AOP is
becoming more or less like a glorified debugging interface these days.
Am I wrong in my perception?
Cheers
--
Marco Antoniotti
Marco Antoniotti <·······@cs.nyu.edu> wrote in message news:<················@typhoon.nyu.edu>...
> Pascal Costanza wrote:
>
> >
> >
> > I have made the experience that there are at least some people in the
> > aspect-oriented community who would like to learn about Common Lisp in
> > order to learn something about the roots of these current buzzwords. I
> > guess that it would be a good idea to have some presence at those
> > workshops and conferences.
>
>
> I am not up to speed to the latest of AOP. The original ideas seemed
> very intriguing to me. However, I kind of got the impression that (at
> least as the latest incarnations of AspectJ are concerned), AOP is
> becoming more or less like a glorified debugging interface these days.
> Am I wrong in my perception?
I think that selecting symbols for a pointcut, by regular expression
matching on their names, is braindamaged. Kiczales and gang really
should rethink this aspect :) of their design.
Symbols should be treated as atoms, not text. If you want to identify
some symbols as a group, then tag them with a common property, or
write some kind of named set. I think that the class writer has to
cooperate with aspects to some point; they can't be entirely
transparent, because changes to the class can affect the correctness
of the aspect. Some of the rsponsibility should be on the side of the
instrumented code---at the very least the arrangement of symbols into
semantic categories which the aspect writer can then treat as units
for adding advice. Rather than matching Get*(), it would be better to
express ``the category of symbols which are methods and accessors''.
An aspect cannot be entirely invisible to the maintainer of the code
which is instrumented by it. This is just a pipe dream. At least a
little bit of cooperation is required.
In CLOS for instance, if we wanted to instrument some class, we would
change the class definition to declare inheritance from a base which
stores the aspect-specific slots, and gives the object a supertype on
which we can hang auxiliary methods. This inheritance is visible to
the programmers who extend and maintain the class. Moreover, because
all the specializations of a generic function use the same symbol,
it's not hard to search the code to find all the auxiliary methods
which provide advice to a given primary method. Moreover the
inheritance controls the order, too. If an object is more of a
LOCKABLE object than a TRACEABLE object, thanks to the order of the
bases, then you know that the locking advice will take place before
the tracing advice, and so the tracing aspect can rely on the lock
being in place, and thus thread-safely inspect the slots.
The AspectJ notion of AOP lacks discipline: it resembles the COMEFROM
construct in the INTERCAL language. Rather than separating concerns,
it ultimately conflates concerns, because at some point, you can't
change any function without worrying about what is instrumenting it.
So you have to be simultaneously concerned about not breaking any one
of these nicely separated concerns. Is there validity in this, or am I
slinging FUD?
Kaz Kylheku wrote:
> I think that selecting symbols for a pointcut, by regular expression
> matching on their names, is braindamaged. Kiczales and gang really
> should rethink this aspect :) of their design.
>
> Symbols should be treated as atoms, not text.
[...]
> The AspectJ notion of AOP lacks discipline: it resembles the COMEFROM
> construct in the INTERCAL language. Rather than separating concerns,
> it ultimately conflates concerns, because at some point, you can't
> change any function without worrying about what is instrumenting it.
> So you have to be simultaneously concerned about not breaking any one
> of these nicely separated concerns. Is there validity in this, or am I
> slinging FUD?
No, I think you are very right in this regard. This problem has already
been acknowledged by some people in the AOP community, but is ignored by
Kiczales and co. AspectJ typically looks nice on finished examples, but
the whole development process that necessarliy includes changes to
source code and refactorings is totally neglected.
I am convinced that LMP that reasons about symbols/categories, not
names/wildcards, is the ultimate AOP approach. Everything else can be
safely ignored. (I don't know whether current LMP approaches reason
about symbols or names.)
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Marco Antoniotti wrote:
> I am not up to speed to the latest of AOP. The original ideas seemed
> very intriguing to me. However, I kind of got the impression that (at
> least as the latest incarnations of AspectJ are concerned), AOP is
> becoming more or less like a glorified debugging interface these days.
> Am I wrong in my perception?
Aspects for tracing method calls are somewhat similar to "Hello, World"
programs or factorial numbers in other programming languages. They serve
as simple examplen to demonstrate language features. (And this of course
has serious drawbacks.)
There are some real-world uses of AOP. Recently there was a discussion
about that in the AspectJ mailing list, but I haven't followed it. There
have also been experience reports at the AOSD conference, for example.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
On Wed, 05 Feb 2003 12:15:18 -0500, Marco Antoniotti
<·······@cs.nyu.edu> wrote:
>
>
>Pascal Costanza wrote:
>
>>
>>
>> I have made the experience that there are at least some people in the
>> aspect-oriented community who would like to learn about Common Lisp in
>> order to learn something about the roots of these current buzzwords. I
>> guess that it would be a good idea to have some presence at those
>> workshops and conferences.
>
>
>I am not up to speed to the latest of AOP. The original ideas seemed
>very intriguing to me. However, I kind of got the impression that (at
>least as the latest incarnations of AspectJ are concerned), AOP is
>becoming more or less like a glorified debugging interface these days.
>Am I wrong in my perception?
>
To make AOP work I beliee you need to be able to write user-defined
aspects. To implement that you will need some sort of aspect language
associated with the main language. This aspect language will need to
have many MOP capabilities.
The thing is that the aspectj people won't admit this. You mention MOP
to them and they start making crosses with their fingers as if warding
off vampires.
Tim Bradshaw <···@cley.com> writes:
> * Pascal Costanza wrote:
> >> My guess is that this is because it's so much a solved problem in the
> >> Lisp world. Why would Lisp people really be interested in `research'
> >> which is reinventing something that Lisp has had for over 40 years?
>
> > Good point.
>
> Of course, this is a fine example of why Lisp hasn't taken over the
> world. Because we're all technical, rational people, we think `why
> should I go to some conference on a solved problem, I have better and
> more interesting things to do', while what we *should* all be doing is
> turning up at these conferences and vomiting lisp propaganda
> at people.
Actually, no need to write a paper. The paper is just to get your sponsor
to pay your airfare anyway, isn't it?
We could just go to the conference paperless and then in the Q&A session
ask the question "Lisp did this 20 years ago. Why is this worth a paper now?"
It's not polite, I suppose, but I've had people ask questions equally pushy
about papers I've written, so I guess it's standard for academia.
From: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey3bs1rlmxd.fsf@cley.com>
* Kent M Pitman wrote:
> Actually, no need to write a paper. The paper is just to get your sponsor
> to pay your airfare anyway, isn't it?
Getting airfares paid for can count...
--tim
In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
<········@web.de> wrote:
> One of the reasons for the power
> of Lisp macros is the fact that you have Turing-completeness at
> compile-time.
No no no no no! Turing-completeness has nothing to do with it. It's a
red herring. What gives Lisp macros their power is that you have Lisp at
compile time. The fact that Lisp is Turing-complete is true but
irrelevant. What matters is that you can do useful things with it.
C++ templates give you Turing-completeness (in a theoretical sense) but
they do *not* give you access to C++. They give you this other language
which I have dubbed STTTL (Stupid Template Typedef Trick Language),
programming in which is not unlike programming an actual Turing machine.
They also give access to a teeny weeny subset of C++ (primitive operations
and data types). This is the subset used to do the canonical factorial
template, but THIS SUBSET IS NOT TURING COMPLETE! It is also largely
disjoint from STTTL.
E.
From: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey31y2nkmul.fsf@cley.com>
* Erann Gat wrote:
> No no no no no! Turing-completeness has nothing to do with it. It's a
> red herring. What gives Lisp macros their power is that you have Lisp at
> compile time. The fact that Lisp is Turing-complete is true but
> irrelevant. What matters is that you can do useful things with it.
This is a really good summary of the issue, I think. There are two
things which make (Lisp) macros so good: one is that you have a whole
proper programming language, complete with run-time (like I/O, and so
on) at compile time, and the other is that this is *the same* language
that you are compiling.
--tim
Tim Bradshaw wrote:
> * Erann Gat wrote:
>
>
>>No no no no no! Turing-completeness has nothing to do with it. It's a
>>red herring. What gives Lisp macros their power is that you have Lisp at
>>compile time. The fact that Lisp is Turing-complete is true but
>>irrelevant. What matters is that you can do useful things with it.
>
>
> This is a really good summary of the issue, I think. There are two
> things which make (Lisp) macros so good: one is that you have a whole
> proper programming language, complete with run-time (like I/O, and so
> on) at compile time, and the other is that this is *the same* language
> that you are compiling.
Yes and no. In the logic meta-programming approach, the base language is
an object-oriented language (currently Smalltalk or Java) and the
meta-language is Prolog. I haven't tried it yet by myself, but what I
have seen so far looks very convincing! However, LMP is conceptually
closer to template meta-programming than to Lisp-style macros.
It's in this sense that I find template meta-programming interesting -
as a precursor to something that might turn out as very useful.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Pascal Costanza wrote:
> Tim Bradshaw wrote:
>
> > * Erann Gat wrote:
> >
> >
> >> No no no no no! Turing-completeness has nothing to do with it. It's a
> >> red herring. What gives Lisp macros their power is that you have
> Lisp at
> >> compile time. The fact that Lisp is Turing-complete is true but
> >> irrelevant. What matters is that you can do useful things with it.
> >
> >
> >
> > This is a really good summary of the issue, I think. There are two
> > things which make (Lisp) macros so good: one is that you have a whole
> > proper programming language, complete with run-time (like I/O, and so
> > on) at compile time, and the other is that this is *the same* language
> > that you are compiling.
>
>
> Yes and no. In the logic meta-programming approach, the base language is
> an object-oriented language (currently Smalltalk or Java) and the
> meta-language is Prolog. I haven't tried it yet by myself, but what I
> have seen so far looks very convincing! However, LMP is conceptually
> closer to template meta-programming than to Lisp-style macros.
>
> It's in this sense that I find template meta-programming interesting -
> as a precursor to something that might turn out as very useful.
This sounds suspiciously similar to a very old piece of work some
friends of mine did in Milan in the 80's. The idea there was to
intertwine a Prolog "virtual machine" with a "3Lisp virtual machine"
(meaning to intertwine the respective reflective towers).
Cheers
Marco Antoniotti wrote:
>
>
> Pascal Costanza wrote:
>
>> In the logic meta-programming approach, the base language is
>> an object-oriented language (currently Smalltalk or Java) and the
>> meta-language is Prolog. I haven't tried it yet by myself, but what I
>> have seen so far looks very convincing!
> This sounds suspiciously similar to a very old piece of work some
> friends of mine did in Milan in the 80's. The idea there was to
> intertwine a Prolog "virtual machine" with a "3Lisp virtual machine"
> (meaning to intertwine the respective reflective towers).
Do you have any references? I would be very interested in learning more
about this...
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Pascal Costanza wrote:
> Marco Antoniotti wrote:
>
> >
> >
> > Pascal Costanza wrote:
> >
>
> >> In the logic meta-programming approach, the base language is
> >> an object-oriented language (currently Smalltalk or Java) and the
> >> meta-language is Prolog. I haven't tried it yet by myself, but what I
> >> have seen so far looks very convincing!
>
>
> > This sounds suspiciously similar to a very old piece of work some
> > friends of mine did in Milan in the 80's. The idea there was to
> > intertwine a Prolog "virtual machine" with a "3Lisp virtual machine"
> > (meaning to intertwine the respective reflective towers).
>
>
> Do you have any references? I would be very interested in learning more
> about this...
It was published in IJCAI 1987 (I believe). The authors should be
Ghislanzoni, Tornielli and Spampinato. I don't have the correct reference.
The did have a funky implementation on Franz Lisp I believe, I can try
to dig it out.
Cheers
--
Marco Antoniotti
Erann Gat wrote:
> In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <········@web.de> wrote:
>
>
>>One of the reasons for the power
>>of Lisp macros is the fact that you have Turing-completeness at
>>compile-time.
>
>
> No no no no no! Turing-completeness has nothing to do with it. It's a
> red herring. What gives Lisp macros their power is that you have Lisp at
> compile time. The fact that Lisp is Turing-complete is true but
> irrelevant. What matters is that you can do useful things with it.
Ahh, I see your point. To me, the Turing completeness is interesting for
the following reason: It's reasonable to see template and logic
meta-programming as a generalisation of aspect-oriented programming. The
difference is that (the popular) AOP approaches don't have
Turing-complete their meta-languages.
What AOP, template and logic meta-programming have in common is that
their meta-languages are declarative, with a tendency towards logic
programming (I am not sure here). Macro programming feels different in
that regard. (I know this is a fuzzy statement, but I don't have a
better idea at the moment.)
> C++ templates give you Turing-completeness (in a theoretical sense) but
> they do *not* give you access to C++. They give you this other language
> which I have dubbed STTTL (Stupid Template Typedef Trick Language),
> programming in which is not unlike programming an actual Turing machine.
I totally agree with you that template meta-programming is most probably
not useful for practical purposes, for the reasons you mention. But I
hope you understand by now why one can think of it as a theoretically
interesting approach.
Pascal
P.S.: As a sidenote, I know one person who uses Turing machines for his
programming. It's actually a compiler that translates Turing programs
into C code. Everything that you can't imagine actually exists. ;)
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
<········@web.de> wrote:
> Erann Gat wrote:
> > In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> > <········@web.de> wrote:
> >
> >
> >>One of the reasons for the power
> >>of Lisp macros is the fact that you have Turing-completeness at
> >>compile-time.
> >
> >
> > No no no no no! Turing-completeness has nothing to do with it. It's a
> > red herring. What gives Lisp macros their power is that you have Lisp at
> > compile time. The fact that Lisp is Turing-complete is true but
> > irrelevant. What matters is that you can do useful things with it.
>
> Ahh, I see your point. To me, the Turing completeness is interesting for
> the following reason: It's reasonable to see template and logic
> meta-programming as a generalisation of aspect-oriented programming. The
> difference is that (the popular) AOP approaches don't have
> Turing-complete their meta-languages.
No no no no no! Arrrggghhh! Turing-completeness is a red herring!
Turing-completeness is pretty much entirely a function of how much memory
you can address. If you can (in principle) address an infinite amount of
memory then you're (almost certainly) Turing complete, otherwise you're
not. C, for example, stripped of its libraries, is not Turing-complete
(because pointers are defined to be of fixed size). By contrast, a
language with nothing more than two variables that contain bignums,
increment, decrement, and test for 0 is Turing-complete.
Interestingly, having one bignum variable is not enough. You need two.
But on a purely theoretical basis, anything more than two is superfluous.
Would you then argue that for a language that only allowed you two
variables? No! Because what matters is not what you can compute, what
matters is HOW WELL THE STRUCTURE OF THE LANGUAGE MATCHES THE STRUCTURE OF
THE IDEAS IN YOUR BRAIN! Most people (but not all) are more comfortable
thinking in terms of words than in terms of bits, which is why most people
prefer to program in a HLL instead of writing Turing machine tables. And
most people run their HLL programs on machines with finite memory,
blissfully unaware that they are really programming finite-state machines
and not Turing machines.
> What AOP, template and logic meta-programming have in common is that
> their meta-languages are declarative, with a tendency towards logic
> programming (I am not sure here). Macro programming feels different in
> that regard.
Normally my response to this would be, "Then you don't understand
macros." But I know enough about you to make me hesitate. Surely you
know that embedding a Prolog interpreter in Lisp -- and therefore
implementing LMP -- is an elementary excercise?
> > C++ templates give you Turing-completeness (in a theoretical sense) but
> > they do *not* give you access to C++. They give you this other language
> > which I have dubbed STTTL (Stupid Template Typedef Trick Language),
> > programming in which is not unlike programming an actual Turing machine.
>
> I totally agree with you that template meta-programming is most probably
> not useful for practical purposes, for the reasons you mention. But I
> hope you understand by now why one can think of it as a theoretically
> interesting approach.
I don't have any children of my own, but I've seen other people's kids
play games where they try to perform physical feats with artificially
imposed constraints. These antics are usually accompanied by loud cries
of, "Hey, watch me, look what I can do!" as they then proceed to try to
stand on their head with one arm tucked behind their backs or some other
such silliness. I suppose in some sense these games can be called
"interesting". (The kids parents certainly seem to think so.) STTTL to
me is interesting in precisely this same sense.
> P.S.: As a sidenote, I know one person who uses Turing machines for his
> programming. It's actually a compiler that translates Turing programs
> into C code. Everything that you can't imagine actually exists. ;)
I can top that: I know a few people who actually like to program in Perl.
Can you imagine?
E.
···@jpl.nasa.gov (Erann Gat) wrote in message news:<····················@192.168.1.51>...
> In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <········@web.de> wrote:
> > Ahh, I see your point. To me, the Turing completeness is interesting for
> > the following reason: It's reasonable to see template and logic
> > meta-programming as a generalisation of aspect-oriented programming. The
> > difference is that (the popular) AOP approaches don't have
> > Turing-complete their meta-languages.
>
> No no no no no! Arrrggghhh! Turing-completeness is a red herring!
But I will take a jar of pickled herring over useless theory any day.
> If you can (in principle) address an infinite amount of
> memory then you're (almost certainly) Turing complete, otherwise you're
> not. C, for example, stripped of its libraries, is not Turing-complete
> (because pointers are defined to be of fixed size).
However you have recursion in C, and local variables that don't have
pointers aimed at them don't need a real address.
> variables? No! Because what matters is not what you can compute, what
> matters is HOW WELL THE STRUCTURE OF THE LANGUAGE MATCHES THE STRUCTURE OF
> THE IDEAS IN YOUR BRAIN!
And of course, the brain is based on manipulating lists consisting of
cons cells. An old paper from the 1980's proves this.
> Most people (but not all) are more comfortable
> thinking in terms of words than in terms of bits, which is why most people
Nope, people think in terms of nested lists full of atoms. This is
psychologically real. Let's dig this up:
http://www.pgc.com/pgc/home-stuff/papers-archive/think-w-diag/psych-rea-lisp.html
:)
In article <····························@posting.google.com>,
···@ashi.footprints.net (Kaz Kylheku) wrote:
> ···@jpl.nasa.gov (Erann Gat) wrote in message
news:<····················@192.168.1.51>...
> > C, for example, stripped of its libraries, is not Turing-complete
> > (because pointers are defined to be of fixed size).
>
> However you have recursion in C, and local variables that don't have
> pointers aimed at them don't need a real address.
Well, this is arguable. C requires that you be able to take the address
of varables, and that the result be a fixed-width pointer. I suppose that
a Sufficiently Smart Compiler might be able to figure out that if you
don't actually avail yourself of this facility then data objects could be
spooled out to disk or something like that. But that seems like a
stretch.
E.
···@jpl.nasa.gov (Erann Gat) wrote in message news:<····················@k-137-79-50-102.jpl.nasa.gov>...
> In article <····························@posting.google.com>,
> ···@ashi.footprints.net (Kaz Kylheku) wrote:
>
> > ···@jpl.nasa.gov (Erann Gat) wrote in message
> news:<····················@192.168.1.51>...
> > > C, for example, stripped of its libraries, is not Turing-complete
> > > (because pointers are defined to be of fixed size).
> >
> > However you have recursion in C, and local variables that don't have
> > pointers aimed at them don't need a real address.
>
> Well, this is arguable. C requires that you be able to take the address
> of varables, and that the result be a fixed-width pointer. I suppose that
> a Sufficiently Smart Compiler might be able to figure out that if you
> don't actually avail yourself of this facility then data objects could be
> spooled out to disk or something like that. But that seems like a
> stretch.
Oh, so stretches are not permitted in discussions about Turing
completeness? News to me. :)
In article <····························@posting.google.com>,
···@ashi.footprints.net (Kaz Kylheku) wrote:
> ···@jpl.nasa.gov (Erann Gat) wrote in message
news:<····················@k-137-79-50-102.jpl.nasa.gov>...
> > In article <····························@posting.google.com>,
> > ···@ashi.footprints.net (Kaz Kylheku) wrote:
> >
> > > ···@jpl.nasa.gov (Erann Gat) wrote in message
> > news:<····················@192.168.1.51>...
> > > > C, for example, stripped of its libraries, is not Turing-complete
> > > > (because pointers are defined to be of fixed size).
> > >
> > > However you have recursion in C, and local variables that don't have
> > > pointers aimed at them don't need a real address.
> >
> > Well, this is arguable. C requires that you be able to take the address
> > of varables, and that the result be a fixed-width pointer. I suppose that
> > a Sufficiently Smart Compiler might be able to figure out that if you
> > don't actually avail yourself of this facility then data objects could be
> > spooled out to disk or something like that. But that seems like a
> > stretch.
>
> Oh, so stretches are not permitted in discussions about Turing
> completeness? News to me. :)
Sure, they're permitted, but you have to think them through if you're
going to actually draw a conclusion. The use of pointers in C is so
pervasive that it's not at all clear what happens if you try to write a
program that doesn't use them. Sure, maybe you can create an infinite
number of data objects without violating the semantics of the language,
but can you *access* them? (You have to be able to in order to be Turing
complete.) I can't think of a way offhand. That doesn't mean it's
impossible. But it seems like a stretch.
E.
···@jpl.nasa.gov (Erann Gat) writes:
> In article <····························@posting.google.com>,
> ···@ashi.footprints.net (Kaz Kylheku) wrote:
>
> > ···@jpl.nasa.gov (Erann Gat) wrote in message
> news:<····················@k-137-79-50-102.jpl.nasa.gov>...
> > > In article <····························@posting.google.com>,
> > > ···@ashi.footprints.net (Kaz Kylheku) wrote:
> > >
> > > > ···@jpl.nasa.gov (Erann Gat) wrote in message
> > > news:<····················@192.168.1.51>...
> > > > > C, for example, stripped of its libraries, is not Turing-complete
> > > > > (because pointers are defined to be of fixed size).
> > > >
> > > > However you have recursion in C, and local variables that don't have
> > > > pointers aimed at them don't need a real address.
> > >
> > > Well, this is arguable. C requires that you be able to take the address
> > > of varables, and that the result be a fixed-width pointer. I suppose that
> > > a Sufficiently Smart Compiler might be able to figure out that if you
> > > don't actually avail yourself of this facility then data objects could be
> > > spooled out to disk or something like that. But that seems like a
> > > stretch.
> >
> > Oh, so stretches are not permitted in discussions about Turing
> > completeness? News to me. :)
>
> Sure, they're permitted, but you have to think them through if you're
> going to actually draw a conclusion. The use of pointers in C is so
> pervasive that it's not at all clear what happens if you try to write a
> program that doesn't use them. Sure, maybe you can create an infinite
> number of data objects without violating the semantics of the language,
> but can you *access* them? (You have to be able to in order to be Turing
> complete.) I can't think of a way offhand. That doesn't mean it's
> impossible. But it seems like a stretch.
Yes, but C has I/O. Classic FORTRAN isn't Turing-complete, except
that you can literally use a tape to model the Turing machine tape.
I'm pretty sure the same works for C.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
In article <···············@apocalypse.OCF.Berkeley.EDU>,
···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In article <····························@posting.google.com>,
> > ···@ashi.footprints.net (Kaz Kylheku) wrote:
> >
> > > ···@jpl.nasa.gov (Erann Gat) wrote in message
> > news:<····················@k-137-79-50-102.jpl.nasa.gov>...
> > > > In article <····························@posting.google.com>,
> > > > ···@ashi.footprints.net (Kaz Kylheku) wrote:
> > > >
> > > > > ···@jpl.nasa.gov (Erann Gat) wrote in message
> > > > news:<····················@192.168.1.51>...
> > > > > > C, for example, stripped of its libraries, is not Turing-complete
> > > > > > (because pointers are defined to be of fixed size).
> > > > >
> > > > > However you have recursion in C, and local variables that don't have
> > > > > pointers aimed at them don't need a real address.
> > > >
> > > > Well, this is arguable. C requires that you be able to take the address
> > > > of varables, and that the result be a fixed-width pointer. I
suppose that
> > > > a Sufficiently Smart Compiler might be able to figure out that if you
> > > > don't actually avail yourself of this facility then data objects
could be
> > > > spooled out to disk or something like that. But that seems like a
> > > > stretch.
> > >
> > > Oh, so stretches are not permitted in discussions about Turing
> > > completeness? News to me. :)
> >
> > Sure, they're permitted, but you have to think them through if you're
> > going to actually draw a conclusion. The use of pointers in C is so
> > pervasive that it's not at all clear what happens if you try to write a
> > program that doesn't use them. Sure, maybe you can create an infinite
> > number of data objects without violating the semantics of the language,
> > but can you *access* them? (You have to be able to in order to be Turing
> > complete.) I can't think of a way offhand. That doesn't mean it's
> > impossible. But it seems like a stretch.
>
> Yes, but C has I/O.
Yes, but C-minus-libraries doesn't. There's a reason I added that
qualification.
E.
···@jpl.nasa.gov (Erann Gat) writes:
> In article <····························@posting.google.com>,
> ···@ashi.footprints.net (Kaz Kylheku) wrote:
>
>> ···@jpl.nasa.gov (Erann Gat) wrote in message
> news:<····················@192.168.1.51>...
>> > C, for example, stripped of its libraries, is not Turing-complete
>> > (because pointers are defined to be of fixed size).
>>
>> However you have recursion in C, and local variables that don't have
>> pointers aimed at them don't need a real address.
>
> Well, this is arguable. C requires that you be able to take the address
> of varables, and that the result be a fixed-width pointer. I suppose that
> a Sufficiently Smart Compiler might be able to figure out that if you
You don't need an SSC: you can mark the variables 'register', and then
even a dumb compiler knows they don't need an address.
So maybe you can get your theoretically infinite storage using
infinite recursion and register variables in each activation record.
-dan
--
http://www.cliki.net/ - Link farm for free CL-on-Unix resources
In article <··············@noetbook.telent.net>, Daniel Barlow
<···@telent.net> wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In article <····························@posting.google.com>,
> > ···@ashi.footprints.net (Kaz Kylheku) wrote:
> >
> >> ···@jpl.nasa.gov (Erann Gat) wrote in message
> > news:<····················@192.168.1.51>...
> >> > C, for example, stripped of its libraries, is not Turing-complete
> >> > (because pointers are defined to be of fixed size).
> >>
> >> However you have recursion in C, and local variables that don't have
> >> pointers aimed at them don't need a real address.
> >
> > Well, this is arguable. C requires that you be able to take the address
> > of varables, and that the result be a fixed-width pointer. I suppose that
> > a Sufficiently Smart Compiler might be able to figure out that if you
>
> You don't need an SSC: you can mark the variables 'register', and then
> even a dumb compiler knows they don't need an address.
>
> So maybe you can get your theoretically infinite storage using
> infinite recursion and register variables in each activation record.
Hm, I hadn't thought of that, but even with that I suspect what you get is
a pushdown automata, not a Turing Machine. I could be wrong though. I
have not worked through the implications of having an SCP (Sufficiently
Clever Programmer).
But the very fact that we're even having this discussion is a perfect
illustration of my point: the answer to the question of whether or not C
is Turing-complete is utterly and completely irrelevant to any practical
concerns of using the language for real work.
(NOTE: there is one circumstance in which knowning whether a language is
theoretically Turing-complete can be important, and that is if you care
about the halting problem. In this case, Turing-completeness is generally
considered a bad thing. Spacecraft sequencing languages, which are
(generally) not Turing-complete are the canonical example.)
E.
Daniel Barlow wrote:
> You don't need an SSC: you can mark the variables 'register', and then
> even a dumb compiler knows they don't need an address.
I don't believe so. The "register" declaration is a suggestion to the
compiler, not a mandate. In fact, taking the address of a register
variable will make many compilers allocate it on the stack regardless of
the register declaration. I'd say that the condition is not an SSC, but a
CSNDE (compiler sufficiently not dumb enough).
faa
"Frank A. Adrian" <·······@ancar.org> writes:
> I don't believe so. The "register" declaration is a suggestion to the
> compiler, not a mandate. In fact, taking the address of a register
> variable will make many compilers allocate it on the stack regardless of
> the register declaration. I'd say that the condition is not an SSC, but a
> CSNDE (compiler sufficiently not dumb enough).
My copy of K&R says "it is not possible to take the address of a
register variable ... regardless of whether the variable is actually
placed in a register" (p83). That said, my copy of K&R is kind of
old, being based on "Draft-proposed ANSI C", so perhaps that's changed
since.
-dan
--
http://www.cliki.net/ - Link farm for free CL-on-Unix resources
Daniel Barlow wrote:
> "Frank A. Adrian" <·······@ancar.org> writes:
>
>
>>I don't believe so. The "register" declaration is a suggestion to the
>>compiler, not a mandate. In fact, taking the address of a register
>>variable will make many compilers allocate it on the stack regardless of
>>the register declaration. I'd say that the condition is not an SSC, but a
>>CSNDE (compiler sufficiently not dumb enough).
>
>
> My copy of K&R says "it is not possible to take the address of a
> register variable ... regardless of whether the variable is actually
> placed in a register" (p83). That said, my copy of K&R is kind of
> old, being based on "Draft-proposed ANSI C", so perhaps that's changed
> since.
>
When a variable is declared using register its address cannot be
computed either explicitly or implicitly (this is a footnote in the
standard). Some compilers might allow you to do this anyway,
but it is in general not a good idea.
The exact wording from the footnote is:
"However,whether or not addressable storage is actually used, the
address of any part of an object declared with storage-class specifier
register cannot be computed, either explicitly [...] or implicitly"
--
Thomas.
Daniel Barlow <···@telent.net> writes:
> You don't need an SSC: you can mark the variables 'register', and then
> even a dumb compiler knows they don't need an address.
You can take addresses of 'register' variables; the qualifier is just
some kind of hint to the compiler.
Florian Weimer <··@deneb.enyo.de> wrote in message news:<··············@deneb.enyo.de>...
> Daniel Barlow <···@telent.net> writes:
>
> > You don't need an SSC: you can mark the variables 'register', and then
> > even a dumb compiler knows they don't need an address.
>
> You can take addresses of 'register' variables; the qualifier is just
> some kind of hint to the compiler.
The qualifier tells the compiler that a diagnostic is required if the
address is taken, after which it's no longer required to continue
processing the program in a standard-conforming way, or at all. It's a
hint in the sense that the intended optimization doesn't have to take
place.
But I think that people misunderstood what was meant by ``sufficiently
smart'' here. It doesn't require brains to recognize that the address
of a local variable in a block has not been taken, just a simple
boolean attribute in the symbol table which is flipped to true when it
happens. :)
By ``sufficiently smart'', it was meant this: that the compiler uses
special storage for those objects whose address is not taken, so that
it can surpass the address space limitation to get closer to Turing
completeness.
···@ashi.footprints.net (Kaz Kylheku) writes:
> The qualifier tells the compiler that a diagnostic is required if the
> address is taken,
Yes, you are correct. I'm sorry for posting garbage.
Erann Gat wrote:
> In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <········@web.de> wrote:
>
>
>>Erann Gat wrote:
>>To me, the Turing completeness is interesting for
>>the following reason: It's reasonable to see template and logic
>>meta-programming as a generalisation of aspect-oriented programming. The
>>difference is that (the popular) AOP approaches don't have
>>Turing-complete meta-languages.
>
>
> No no no no no! Arrrggghhh! Turing-completeness is a red herring!
>
> Turing-completeness is pretty much entirely a function of how much memory
> you can address. If you can (in principle) address an infinite amount of
> memory then you're (almost certainly) Turing complete, otherwise you're
> not. C, for example, stripped of its libraries, is not Turing-complete
> (because pointers are defined to be of fixed size).
I wasn't aware of this "feature" of C. Now it's clear to me. (Your reply
to Thomas Stegen is very clear.)
OK, you're right, C is not Turing complete. (Wow!)
> By contrast, a
> language with nothing more than two variables that contain bignums,
> increment, decrement, and test for 0 is Turing-complete.
>
> Interestingly, having one bignum variable is not enough. You need two.
> But on a purely theoretical basis, anything more than two is superfluous.
> Would you then argue that for a language that only allowed you two
> variables? No!
Right, I wouldn't. But there are (theoretical or conceptual) levels
where these things are interesting.
AOP is a high-level approach that allows programmers to do useful stuff.
However it is limited because the meta-language is not Turing complete,
so you can only express the things the designerns of, say, AspectJ have
anticipated.
Template meta-programming is more powerful, because in principle it
gives you an (almost) Turing-complete meta-language. However, it's very
complicated to use - it's not a high-level approach. (But there exist
some interesting examples.)
The nice thing about logic meta-programming is that it combines the
advantages of these two approaches.
> Because what matters is not what you can compute, what
> matters is HOW WELL THE STRUCTURE OF THE LANGUAGE MATCHES THE STRUCTURE OF
> THE IDEAS IN YOUR BRAIN!
Of course.
>>What AOP, template and logic meta-programming have in common is that
>>their meta-languages are declarative, with a tendency towards logic
>>programming (I am not sure here). Macro programming feels different in
>>that regard.
>
>
> Normally my response to this would be, "Then you don't understand
> macros." But I know enough about you to make me hesitate. Surely you
> know that embedding a Prolog interpreter in Lisp -- and therefore
> implementing LMP -- is an elementary excercise?
Yes, I know. But LMP requires a little bit more than just a Prolog
interpreter. You also need some elementary facts and rules about the
possible structure of your base programs. (Things like "subclass(a, b)"
and "method(a, m, ...signature...)", and so on.)
Of course, this is all possible in Common Lisp, but I haven't seen it so
far (in CL). I have just seen examples of LMP for Smalltalk and Java.
These examples were sufficient for me to find the concept intriguing and
obviously useful. I would love to see that approach implemented in CL!
>>I totally agree with you that template meta-programming is most probably
>>not useful for practical purposes, for the reasons you mention. But I
>>hope you understand by now why one can think of it as a theoretically
>>interesting approach.
>
>
> I don't have any children of my own, but I've seen other people's kids
> play games where they try to perform physical feats with artificially
> imposed constraints. These antics are usually accompanied by loud cries
> of, "Hey, watch me, look what I can do!" as they then proceed to try to
> stand on their head with one arm tucked behind their backs or some other
> such silliness. I suppose in some sense these games can be called
> "interesting". (The kids parents certainly seem to think so.) STTTL to
> me is interesting in precisely this same sense.
OK, then let's just forget about template meta-programming and focus
more on LMP. I am not trying to defend TMP.
>>P.S.: As a sidenote, I know one person who uses Turing machines for his
>>programming. It's actually a compiler that translates Turing programs
>>into C code. Everything that you can't imagine actually exists. ;)
>
>
> I can top that: I know a few people who actually like to program in Perl.
> Can you imagine?
You _must_ be kidding! ;)
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
In article <·············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
<········@web.de> wrote:
> OK, you're right, C is not Turing complete. (Wow!)
See Daniel Barlow's followup for a late-breaking bulletin. C may be
Turing complete after all (or it may not -- the Jury is still out).
However it turns out, I'd say it more like: OK, C is [not]
Turing-complete. (Yawn.)
> > Interestingly, having one bignum variable is not enough. You need two.
> > But on a purely theoretical basis, anything more than two is superfluous.
> > Would you then argue that for a language that only allowed you two
> > variables? No!
>
> Right, I wouldn't. But there are (theoretical or conceptual) levels
> where these things are interesting.
I suppose, if you think like a mathematician. But if you think like a
mathematician then you should probably be hanging out on comp.lang.scheme
(or comp.lang.haskell) rather than here.
> AOP is a high-level approach that allows programmers to do useful stuff.
> However it is limited because the meta-language is not Turing complete,
> so you can only express the things the designerns of, say, AspectJ have
> anticipated.
Right. The word "only" is the key. The C/C++/Java world has divided
itself up into two classes of people (three if you count users): ordinary
programmers, who use the languages to write applications for users, and
"wizards" who invent extensions to the languages. You have to be a wizard
to extend C or C++ or Java because you have to have an intimate
understanding of the inner workings of the parser and the compiler.
Because of this, the work of wizards is held in high regard in that
community.
Extending Lisp is easy, so there is no such wizard/non-wizard divide
between those who are able extend the language and those who are not. In
Lisp, when someone comes up with an extension to the language there is no
hoopla, no great Publication of Papers and Coining of Buzzwords. The very
idea is laughable.
> Template meta-programming is more powerful, because in principle it
> gives you an (almost) Turing-complete meta-language. However, it's very
> complicated to use - it's not a high-level approach. (But there exist
> some interesting examples.)
>
> The nice thing about logic meta-programming is that it combines the
> advantages of these two approaches.
Again, this whole debate is much like the debate over whether C is Turing
complete or not. It is, perhaps, an interesting intellectual excercise,
but of no practical importance whatsoever in the context of Lisp, because
adding any of these features to Lisp is an elementary excercise. So we
don't have to reach a consensus over whether, say, LMP is useful or not.
If you think it's useful, fine, write yourself a little prolog interpreter
(or pull one off the web) and use it.
> Yes, I know. But LMP requires a little bit more than just a Prolog
> interpreter. You also need some elementary facts and rules about the
> possible structure of your base programs. (Things like "subclass(a, b)"
> and "method(a, m, ...signature...)", and so on.)
Yeah, so how hard is it to parse your defclass and defmethod statements?
What am I missing?
> Of course, this is all possible in Common Lisp, but I haven't seen it so
> far (in CL). I have just seen examples of LMP for Smalltalk and Java.
> These examples were sufficient for me to find the concept intriguing and
> obviously useful. I would love to see that approach implemented in CL!
Go for it, dude. If you spend more than an hour or two on it without
making significant progress come back and let us know what problems you're
having.
E.
···@jpl.nasa.gov (Erann Gat) writes:
> Extending Lisp is easy, so there is no such wizard/non-wizard divide
> between those who are able extend the language and those who are not. In
> Lisp, when someone comes up with an extension to the language there is no
> hoopla, no great Publication of Papers and Coining of Buzzwords. The very
> idea is laughable.
So that Emacs Minor Mode that I wrote ... the one that, if it sees
I've defined 20 or more macros in the same CL package, uses
Dissociated Press to generate buzzwords, and sends press releases to
all my friends and family ... it's not useful? Crap. I thouht I'd
automated the whole recognition-and-initial-buzz phase of the process...
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Erann Gat wrote:
>>>Interestingly, having one bignum variable is not enough. You need two.
>>>But on a purely theoretical basis, anything more than two is superfluous.
>>>Would you then argue that for a language that only allowed you two
>>>variables? No!
>>
>>Right, I wouldn't. But there are (theoretical or conceptual) levels
>>where these things are interesting.
>
>
> I suppose, if you think like a mathematician. But if you think like a
> mathematician then you should probably be hanging out on comp.lang.scheme
> (or comp.lang.haskell) rather than here.
Hmmm, do you mind if I am both using a pragmatic language and being
interested in philosophical underpinnings? ;)
Indeed, Scheme and Haskell have some interesting properties but I don't
think they lead to something useful in the long run, for example when
being compared to Common Lisp. TMP is not useful in itself but might
lead to something useful in the long run, IMHO. That's all. (The end
result certainly won't be based on templates in C++.)
> The C/C++/Java world has divided
> itself up into two classes of people (three if you count users): ordinary
> programmers, who use the languages to write applications for users, and
> "wizards" who invent extensions to the languages. You have to be a wizard
> to extend C or C++ or Java because you have to have an intimate
> understanding of the inner workings of the parser and the compiler.
> Because of this, the work of wizards is held in high regard in that
> community.
>
> Extending Lisp is easy, so there is no such wizard/non-wizard divide
> between those who are able extend the language and those who are not. In
> Lisp, when someone comes up with an extension to the language there is no
> hoopla, no great Publication of Papers and Coining of Buzzwords. The very
> idea is laughable.
Hmmm, you are probably very right in this regard. Probably I am still
too close to the former community and therefore still too excited about
things you take for granted.
One of the problems is that the former approach gets far more attention,
probably just because of this difference. Makes me think...
> Again, this whole debate is much like the debate over whether C is Turing
> complete or not. It is, perhaps, an interesting intellectual excercise,
> but of no practical importance whatsoever in the context of Lisp, because
> adding any of these features to Lisp is an elementary excercise. So we
> don't have to reach a consensus over whether, say, LMP is useful or not.
> If you think it's useful, fine, write yourself a little prolog interpreter
> (or pull one off the web) and use it.
OK, agreed.
>>Yes, I know. But LMP requires a little bit more than just a Prolog
>>interpreter. You also need some elementary facts and rules about the
>>possible structure of your base programs. (Things like "subclass(a, b)"
>>and "method(a, m, ...signature...)", and so on.)
>
>
> Yeah, so how hard is it to parse your defclass and defmethod statements?
> What am I missing?
I don't know the details. This is just what the people told me who work
on these things for Smalltalk. My impression is that they are smart
people, therefore I tend to trust them in that regard. Perhaps it's much
simpler to implement in Common Lisp. I can only guess, haven't tried it
myself yet...
>>Of course, this is all possible in Common Lisp, but I haven't seen it so
>>far (in CL). I have just seen examples of LMP for Smalltalk and Java.
>>These examples were sufficient for me to find the concept intriguing and
>>obviously useful. I would love to see that approach implemented in CL!
>
>
> Go for it, dude. If you spend more than an hour or two on it without
> making significant progress come back and let us know what problems you're
> having.
;) I don't have the time for that at the moment. But I get your message.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
<········@web.de> wrote:
> Hmmm, do you mind if I am both using a pragmatic language and being
> interested in philosophical underpinnings? ;)
Not at all. Sorry, I didn't mean to sound like I was trying to get rid of
you. My point was just that "interesting" is not necessarily the same
thing as "useful", and Common Lisp's biases tend to run towards useful.
This is not to say that Common Lisp isn't interesting -- it is. But its
interest derives from its extraordinary utility and not vice versa.
> Indeed, Scheme and Haskell have some interesting properties but I don't
> think they lead to something useful in the long run, for example when
> being compared to Common Lisp.
Yes, and that tends to be the end of the discussion around here.
> Hmmm, you are probably very right in this regard. Probably I am still
> too close to the former community and therefore still too excited about
> things you take for granted.
No, there's nothing wrong with being excited. That's a Good Thing. I'm
just trying to explain why others around here aren't getting as excited as
you might have wished.
> One of the problems is that the former approach gets far more attention,
> probably just because of this difference. Makes me think...
That's also a good thing! ;-)
> > Yeah, so how hard is it to parse your defclass and defmethod statements?
> > What am I missing?
>
> I don't know the details.
So? No one knows the details when they start.
> This is just what the people told me who work
> on these things for Smalltalk. My impression is that they are smart
> people, therefore I tend to trust them in that regard. Perhaps it's much
> simpler to implement in Common Lisp. I can only guess, haven't tried it
> myself yet...
Give it a whirl and see what happens. The outcome can only be good.
Either you'll discover it's easy, in which case a whole new world will be
opened up for you. Or you'll discover that it's hard, you'll discover
*why* it's hard, and then you'll be able to explain it to us. In that
case, either we'll be able to help you, or a whole new world will be
opened up to us. Either way, it's progress.
In any case, the one tactic that will not lead to progress is to come here
and say, "This seems interesting to me. Why doesn't someone else work on
it?" (Unless you have money, of course.)
> ;) I don't have the time for that at the moment. But I get your message.
What? You have time to post on usenet, but you can't spare an hour to
think about parsing defclass forms? Balderdash! Foo! <whack!> More
talk like that and we'll have to bring Erik out of retirement. ;-) ;-)
;-)
E.
In article <····················@k-137-79-50-102.jpl.nasa.gov>,
···@jpl.nasa.gov (Erann Gat) wrote:
> In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <········@web.de> wrote:
[...]
> My point was just that "interesting" is not necessarily the same
> thing as "useful",
Yes, I totally agree. I think this settles it.
> and Common Lisp's biases tend to run towards useful.
> No, there's nothing wrong with being excited. That's a Good Thing. I'm
> just trying to explain why others around here aren't getting as excited as
> you might have wished.
OK, thanks for that.
> > One of the problems is that the former approach gets far more attention,
> > probably just because of this difference. Makes me think...
>
> That's also a good thing! ;-)
;)
> In any case, the one tactic that will not lead to progress is to come here
> and say, "This seems interesting to me. Why doesn't someone else work on
> it?" (Unless you have money, of course.)
That's not what I am trying to do...
> > ;) I don't have the time for that at the moment. But I get your message.
>
> What? You have time to post on usenet, but you can't spare an hour to
> think about parsing defclass forms? Balderdash! Foo! <whack!> More
> talk like that and we'll have to bring Erik out of retirement. ;-) ;-)
> ;-)
Oh my god, please, no!!! ;-)
Pascal
--
"If I could explain it, I wouldn't be able to do it."
A.M.McKenzie
···@jpl.nasa.gov (Erann Gat) writes:
> If you think it's useful, fine, write yourself a little prolog interpreter
> (or pull one off the web) and use it. [To implement LMP]
If you are to do that in Lisp, may I suggest that you should use Screamer
(package providing prolog-style non-determinism integrated into Lisp),
rather than a wholly different language (Prolog) implemented in Lisp?
As an added side-effect, by using Screamer, you can benefit from
Logic Programming not just at the Meta-Level, but at the base-level, too!
[ Fran�ois-Ren� �VB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[ TUNES project for a Free Reflective Computing System | http://tunes.org ]
It is no crime to be ignorant of economics, which is, after all, a specialized
discipline and one that most people consider to be a "dismal science".
But it *is* totally irresponsible to have a loud and vociferous opinion
on economic subjects while remaining in this state of ignorance.
-- Murray Rothbard
In article <·················@Samaris.tunes.org>,
Francois-Rene Rideau <····@tunes.org> wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
> > If you think it's useful, fine, write yourself a little prolog interpreter
> > (or pull one off the web) and use it. [To implement LMP]
> If you are to do that in Lisp, may I suggest that you should use Screamer
> (package providing prolog-style non-determinism integrated into Lisp),
> rather than a wholly different language (Prolog) implemented in Lisp?
> As an added side-effect, by using Screamer, you can benefit from
> Logic Programming not just at the Meta-Level, but at the base-level, too!
Yes, I guess this woud be reasonable.
Pascal
--
"If I could explain it, I wouldn't be able to do it."
A.M.McKenzie
"Pascal Costanza" <········@web.de> wrote in message ··················@f1node01.rhrz.uni-bonn.de...
> Erann Gat wrote:
> > In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> > <········@web.de> wrote:
> >
> > Turing-completeness is pretty much entirely a function of how much memory
> > you can address. If you can (in principle) address an infinite amount of
> > memory then you're (almost certainly) Turing complete, otherwise you're
> > not. C, for example, stripped of its libraries, is not Turing-complete
> > (because pointers are defined to be of fixed size).
>
> I wasn't aware of this "feature" of C. Now it's clear to me. (Your reply
> to Thomas Stegen is very clear.)
>
> OK, you're right, C is not Turing complete. (Wow!)
>
That's a faulty conclusion.
C "stripped of its libraries" is not Turing complete.
But C is defined with the libraries and the addition is
enough to make it Turing complete. What a wierd discussion
this has been, "Look if I take away part of the stuff that
makes this language Turing complete it isn't Turing complete
anymore." Anyone for proving a spider hears through its legs?
--
Geoff
In article <······················@news20.bellglobal.com>, "Geoffrey
Summerhayes" <·············@hotmail.com> wrote:
> "Pascal Costanza" <········@web.de> wrote in message
··················@f1node01.rhrz.uni-bonn.de...
> > Erann Gat wrote:
> > > In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> > > <········@web.de> wrote:
> > >
> > > Turing-completeness is pretty much entirely a function of how much memory
> > > you can address. If you can (in principle) address an infinite amount of
> > > memory then you're (almost certainly) Turing complete, otherwise you're
> > > not. C, for example, stripped of its libraries, is not Turing-complete
> > > (because pointers are defined to be of fixed size).
> >
> > I wasn't aware of this "feature" of C. Now it's clear to me. (Your reply
> > to Thomas Stegen is very clear.)
> >
> > OK, you're right, C is not Turing complete. (Wow!)
> >
>
> That's a faulty conclusion.
>
> C "stripped of its libraries" is not Turing complete.
> But C is defined with the libraries and the addition is
> enough to make it Turing complete. What a wierd discussion
> this has been, "Look if I take away part of the stuff that
> makes this language Turing complete it isn't Turing complete
> anymore." Anyone for proving a spider hears through its legs?
It's actually not quite as uninteresting as all that. Remember, the C
libraries are typically written in C, so taking away the libraries doesn't
really take away all that much, because most (but not all) of the
libraries can simply be re-written in C-minus-libraries. It is an
interesting (though elementary) puzzle to figure out which of the C
standard library routines actually add fundamentally new functionality to
the C language.
Much more interesting than the actual puzzle itself is how few people even
realize that this is an issue.
E.
From: Salvador Fandiño García
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <3E42CAB3.2030905@yahoo.com>
Hi
>>OK, you're right, C is not Turing complete. (Wow!)
>
> That's a faulty conclusion.
>
> C "stripped of its libraries" is not Turing complete.
> But C is defined with the libraries and the addition is
> enough to make it Turing complete. What a wierd discussion
> this has been, "Look if I take away part of the stuff that
> makes this language Turing complete it isn't Turing complete
> anymore." Anyone for proving a spider hears through its legs?
And C libraries are usually implemented in C (maybe with some assembler,
but just to improve performance, it is not really a requirement) so is
that a paradox, where is the trick?
- Salva
In article <················@yahoo.com>,
=?ISO-8859-1?Q?Salvador_Fandi=F1o_Garc=EDa?= <········@yahoo.com> wrote:
> Hi
>
>
> >>OK, you're right, C is not Turing complete. (Wow!)
> >
> > That's a faulty conclusion.
> >
> > C "stripped of its libraries" is not Turing complete.
> > But C is defined with the libraries and the addition is
> > enough to make it Turing complete. What a wierd discussion
> > this has been, "Look if I take away part of the stuff that
> > makes this language Turing complete it isn't Turing complete
> > anymore." Anyone for proving a spider hears through its legs?
>
> And C libraries are usually implemented in C (maybe with some assembler,
> but just to improve performance, it is not really a requirement) so is
> that a paradox, where is the trick?
A most astute observation! It is actually much more important to realize
that this is an issue than to know the answer. You have just taken a step
on the path to enlightenment.
The trick is in the lambda nature, grasshopper!
:-)
E.
"Salvador Fandi�o Garc�a" <········@yahoo.com> wrote in message ·····················@yahoo.com...
> Hi
>
>
> >>OK, you're right, C is not Turing complete. (Wow!)
> >
> > That's a faulty conclusion.
> >
> > C "stripped of its libraries" is not Turing complete.
> > But C is defined with the libraries and the addition is
> > enough to make it Turing complete. What a wierd discussion
> > this has been, "Look if I take away part of the stuff that
> > makes this language Turing complete it isn't Turing complete
> > anymore." Anyone for proving a spider hears through its legs?
>
> And C libraries are usually implemented in C (maybe with some assembler,
> but just to improve performance, it is not really a requirement) so is
> that a paradox, where is the trick?
>
> - Salva
It's in STDIO.H
char ch;
FILE *fh=fopen(infinite_stream,"r+");
fread(&ch,1,1,fh);
fwrite(&ch,1,1,fh);
fseek(fh,1,SEEK_CUR);
fseek(fh,-1,SEEK_CUR);
fclose(fh);
--
Geoff
"Geoffrey Summerhayes" <·············@hotmail.com> writes:
> "Salvador Fandi�o Garc�a" <········@yahoo.com> wrote in message ·····················@yahoo.com...
> > Hi
> >
> >
> > >>OK, you're right, C is not Turing complete. (Wow!)
> > >
> > > That's a faulty conclusion.
> > >
> > > C "stripped of its libraries" is not Turing complete.
> > > But C is defined with the libraries and the addition is
> > > enough to make it Turing complete. What a wierd discussion
> > > this has been, "Look if I take away part of the stuff that
> > > makes this language Turing complete it isn't Turing complete
> > > anymore." Anyone for proving a spider hears through its legs?
> >
> > And C libraries are usually implemented in C (maybe with some assembler,
> > but just to improve performance, it is not really a requirement) so is
> > that a paradox, where is the trick?
> >
> > - Salva
>
> It's in STDIO.H
No. The trick is that the libraries can be implemented in C and using
the underlying OS or hardware. The fact that you can write something
like:
typedef void (*fun_t)();
char machine_code[]={ 0x1b,0xff,0x4e,0x00,0x54 };
fun_t fun=(fun_t)machine_code;
fun();
which allow you to define function using machine code that the
compiler (the language) was not expected to compile, to invoke the OS,
or to access the hardware (non memory mapped devices for example).
In anycase, there are no concrete universal Turing machines, because
that would need infinite memory. Only that some Turing machines can
work with finite tape, and these ones are equivalent to state machines
and to Von-Neuman computers with finite memories.
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
There is a fault in reality. Do not adjust your minds. -- Salman Rushdie
In article <··············@thalassa.informatimago.com>, Pascal Bourguignon
<···@informatimago.com> wrote:
> "Geoffrey Summerhayes" <·············@hotmail.com> writes:
> > "Salvador Fandi�o Garc�a" <········@yahoo.com> wrote in message
·····················@yahoo.com...
> > > Hi
> > >
> > >
> > > >>OK, you're right, C is not Turing complete. (Wow!)
> > > >
> > > > That's a faulty conclusion.
> > > >
> > > > C "stripped of its libraries" is not Turing complete.
> > > > But C is defined with the libraries and the addition is
> > > > enough to make it Turing complete. What a wierd discussion
> > > > this has been, "Look if I take away part of the stuff that
> > > > makes this language Turing complete it isn't Turing complete
> > > > anymore." Anyone for proving a spider hears through its legs?
> > >
> > > And C libraries are usually implemented in C (maybe with some assembler,
> > > but just to improve performance, it is not really a requirement) so is
> > > that a paradox, where is the trick?
> > >
> > > - Salva
> >
> > It's in STDIO.H
>
> No. The trick is that the libraries can be implemented in C and using
> the underlying OS or hardware. The fact that you can write something
> like:
>
> typedef void (*fun_t)();
> char machine_code[]={ 0x1b,0xff,0x4e,0x00,0x54 };
> fun_t fun=(fun_t)machine_code;
> fun();
>
> which allow you to define function using machine code that the
> compiler (the language) was not expected to compile, to invoke the OS,
> or to access the hardware (non memory mapped devices for example).
Actually, you're both wrong -- sort of.
You've both got the right idea, but you're both wrong in the details. The
trick is not really in stdio per se, though stdio is the facility by which
you typically access the trick. It also has nothing to do with being able
to execute machine code, or with the fact that non-memory-mapped I/O is
possible. In fact, just the opposite. It's the fact that dereferencing a
pointer doesn't necessarily access RAM. So the crucial part of the
library is the *device drivers* that know where the magic non-RAM
addresses are, and how to tweak them to read and write from the disk
drives, the network cards, and whatnot.
> In anycase, there are no concrete universal Turing machines, because
> that would need infinite memory. Only that some Turing machines can
> work with finite tape, and these ones are equivalent to state machines
> and to Von-Neuman computers with finite memories.
Right, which is another reason why any discussion of whether or not
something is Turing-complete is almost always pointless.
E.
From: Salvador Fandiño García
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <3E43994C.9020401@yahoo.com>
Hi
> Actually, you're both wrong -- sort of.
>
> You've both got the right idea, but you're both wrong in the details. The
> trick is not really in stdio per se, though stdio is the facility by which
> you typically access the trick. It also has nothing to do with being able
> to execute machine code, or with the fact that non-memory-mapped I/O is
> possible. In fact, just the opposite. It's the fact that dereferencing a
> pointer doesn't necessarily access RAM. So the crucial part of the
> library is the *device drivers* that know where the magic non-RAM
> addresses are, and how to tweak them to read and write from the disk
> drives, the network cards, and whatnot.
All of you have got lost in the low level details...
The trick is that C is not a machine, not even a virtual one. You can
define Lisp as a machine that operates over lists and atoms, Java has
the JVM, etc., and then you can talk about the turing-completeness of
such abstractions, but C does not define a machine abstraction, it just
exposes the underlying real (or also virtual) machine so you can not say
"C is turing complete" or "C is not turing complete" because C has not
enough entity to determine it.
Bye,
- Salva
Pascal Costanza <········@web.de> writes:
> > Because what matters is not what you can compute, what
> > matters is HOW WELL THE STRUCTURE OF THE LANGUAGE MATCHES THE STRUCTURE OF
> > THE IDEAS IN YOUR BRAIN!
>
> Of course.
Great! That now really explains things. This is really the answer to a
great many things that have been driving us mad all along. Now we have
an isomorphic map from C++, Perl, and Java to the brains of its lu
NO CARRIER
Mario S. Mommer wrote:
> Pascal Costanza <········@web.de> writes:
>
>>>Because what matters is not what you can compute, what
>>>matters is HOW WELL THE STRUCTURE OF THE LANGUAGE MATCHES THE STRUCTURE OF
>>>THE IDEAS IN YOUR BRAIN!
>>
>>Of course.
>
>
> Great! That now really explains things. This is really the answer to a
> great many things that have been driving us mad all along. Now we have
> an isomorphic map from C++, Perl, and Java to the brains of its lu
> NO CARRIER
I am sorry, I don't get that. What do you mean?
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Pascal Costanza <········@web.de> writes:
> I am sorry, I don't get that. What do you mean?
That people love C++, Java, or Perl because it mirrors them in a
certain way (which doesn't say much good about them). This is a
tongue-in-cheek corollary from Eran's uppercase theorem:
> >>>WHAT MATTERS IS HOW WELL THE STRUCTURE OF THE LANGUAGE MATCHES
> >>>THE STRUCTURE OF THE IDEAS IN YOUR BRAIN!
That said, I know a few bright people who like to program in Perl, so
I'm not terribly serious about it. That might explain the strange
format of my composition. Sorry.
Mario.
On Wed, 05 Feb 2003 10:02:54 -0800, ···@jpl.nasa.gov (Erann Gat)
wrote:
>No no no no no! Arrrggghhh! Turing-completeness is a red herring!
But fun to shoot the bull about when you're taking a short break from
work :)
>Turing-completeness is pretty much entirely a function of how much memory
>you can address. If you can (in principle) address an infinite amount of
>memory then you're (almost certainly) Turing complete, otherwise you're
>not. C, for example, stripped of its libraries, is not Turing-complete
>(because pointers are defined to be of fixed size).
Are they? sizeof(x) is presumably required to return a finite number
for all x, but does that necessary imply x must be restricted to a
fixed number of bits?
>By contrast, a
>language with nothing more than two variables that contain bignums,
>increment, decrement, and test for 0 is Turing-complete.
>
>Interestingly, having one bignum variable is not enough. You need two.
Yes... is there any easily understood reason why two is the necessary
and sufficient number?
>> P.S.: As a sidenote, I know one person who uses Turing machines for his
>> programming. It's actually a compiler that translates Turing programs
>> into C code. Everything that you can't imagine actually exists. ;)
*boggle*
>I can top that: I know a few people who actually like to program in Perl.
>Can you imagine?
*boggle squared* :)
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
(Russell Wallace) wrote:
> >Turing-completeness is pretty much entirely a function of how much memory
> >you can address. If you can (in principle) address an infinite amount of
> >memory then you're (almost certainly) Turing complete, otherwise you're
> >not. C, for example, stripped of its libraries, is not Turing-complete
> >(because pointers are defined to be of fixed size).
>
> Are they? sizeof(x) is presumably required to return a finite number
> for all x, but does that necessary imply x must be restricted to a
> fixed number of bits?
No it doesn't, but you've left out an important fact: you can apply sizeof
to types, and in particular to pointer types, and that has to return a
finite number too. *That* implies that pointers are restricted to a fixed
number of bits.
> >By contrast, a
> >language with nothing more than two variables that contain bignums,
> >increment, decrement, and test for 0 is Turing-complete.
> >
> >Interestingly, having one bignum variable is not enough. You need two.
>
> Yes... is there any easily understood reason why two is the necessary
> and sufficient number?
That all depends on who is trying to do the understanding, I suppose, and
what level of understanding one is striving for. The facile answer is
that with a single bignum you have the equivalent of a pushdown automaton,
and it's possible to show that there are things that Turing machines can
compute that PDAs cannot.
There are four classes of computational models that are distinguishable in
terms of what they can and cannot compute: finite state machines,
deterministic pushdown automata, non-deterministic pushdown automata, and
Turing machines. But as far as I know, why this is so is a grand cosmic
mystery, rather like trying to understand why pi is irrational.
E.
From: Joe Marshall
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <u1f9pa42.fsf@ccs.neu.edu>
···@jpl.nasa.gov (Erann Gat) writes:
> There are four classes of computational models that are distinguishable in
> terms of what they can and cannot compute: finite state machines,
> deterministic pushdown automata, non-deterministic pushdown automata, and
> Turing machines. But as far as I know, why this is so is a grand cosmic
> mystery, rather like trying to understand why pi is irrational.
Another mystery is why non-deterministic Turing machines are no more
powerful than deterministic ones.
In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu> wrote:
>Another mystery is why non-deterministic Turing machines are no more
>powerful than deterministic ones.
A trivial consequence of the Church-Turing Thesis. ;-)
If only it was the Church-Turing Theorem. ;-(
I've heard it said (but never by a competent person) that quantum
computers can solve problems that evade Turing-equivalent formalisms,
at least in principle. Anyone know if this is true, and if so, the
location of an accessible exposition?
In article <·····················@129.59.212.53>, ····@vanderbilt.edu
(sv0f) wrote:
> In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu> wrote:
>
> >Another mystery is why non-deterministic Turing machines are no more
> >powerful than deterministic ones.
>
> A trivial consequence of the Church-Turing Thesis. ;-)
Not quite. It's actually possible to prove that NDTM=DTM. What the
Church-Turing thesis says is that it is not possible to have a
computational model that is more powerful than a TM. So far no one has
come up with one, but no one has proven (or even conceived of how one
might prove) that it's not possible.
> I've heard it said (but never by a competent person) that quantum
> computers can solve problems that evade Turing-equivalent formalisms,
I'm pretty sure that's not true. Quantum computers provide inherent
exponential speedups for certain classes of problems (that is, you can
prove that a classical TM simulating a QTM must run exponentially slower
[Feynman]), but not any fundamentally new kind of computability.
E.
In article <····················@k-137-79-50-101.jpl.nasa.gov>,
···@jpl.nasa.gov (Erann Gat) wrote:
>> I've heard it said (but never by a competent person) that quantum
>> computers can solve problems that evade Turing-equivalent formalisms,
>
>I'm pretty sure that's not true. Quantum computers provide inherent
>exponential speedups for certain classes of problems (that is, you can
>prove that a classical TM simulating a QTM must run exponentially slower
>[Feynman]), but not any fundamentally new kind of computability.
Ahh, that's right. Thanks.
On Wed, 12 Feb 2003 14:05:52 -0800, ···@jpl.nasa.gov (Erann Gat)
wrote:
>What the
>Church-Turing thesis says is that it is not possible to have a
>computational model that is more powerful than a TM. So far no one has
>come up with one, but no one has proven (or even conceived of how one
>might prove) that it's not possible.
Well, look at it this way: TMs impose no restrictions other than that
the number of bit operations performed must be finite.
I can easily come up with a more powerful computational model:
consider a machine whose registers hold real numbers, and which can
perform arithmetic operations on real numbers in one clock cycle. But
this requires dropping the above mentioned restriction; if you're not
allowed do that, you can't get more powerful than "no other
restrictions".
This argument isn't a proof, of course, but it seems suggestive at
least.
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
(Russell Wallace) wrote:
> There's nothing in the standard that says sizeof(any scalar type)
> can't be 1.
See previous discussion of CHAR_BITS.
> I can easily come up with a more powerful computational model:
But not one that is physically realizable.
E.
On Sun, 16 Feb 2003 14:44:15 -0800, ···@jpl.nasa.gov (Erann Gat)
wrote:
>In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
>(Russell Wallace) wrote:
>> I can easily come up with a more powerful computational model:
>
>But not one that is physically realizable.
Turing machines aren't physically realizable either ^.~
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
(Russell Wallace) wrote:
> On Sun, 16 Feb 2003 14:44:15 -0800, ···@jpl.nasa.gov (Erann Gat)
> wrote:
>
> >In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
> >(Russell Wallace) wrote:
> >> I can easily come up with a more powerful computational model:
> >
> >But not one that is physically realizable.
>
> Turing machines aren't physically realizable either ^.~
Sure they are. Have you looked at the price of disks lately? ;-)
E.
On 8293 day of my life Erann Gat wrote:
> In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
> (Russell Wallace) wrote:
>
> > On Sun, 16 Feb 2003 14:44:15 -0800, ···@jpl.nasa.gov (Erann Gat)
> > wrote:
> >
> > >In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
> > >(Russell Wallace) wrote:
> > >> I can easily come up with a more powerful computational model:
> > >
> > >But not one that is physically realizable.
> >
> > Turing machines aren't physically realizable either ^.~
>
> Sure they are. Have you looked at the price of disks lately? ;-)
Hmm... Are you going to implement imitation of TM with hard disks in C
or Asm? So is C/C++ TM-equivalent or not?
--
Ivan Boldyrev remove .microsoft.com from my address
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
There are 256 symbols in English alphabet.
On Wed, 12 Feb 2003 15:05:04 -0600, ····@vanderbilt.edu (sv0f) wrote:
>I've heard it said (but never by a competent person) that quantum
>computers can solve problems that evade Turing-equivalent formalisms,
>at least in principle. Anyone know if this is true, and if so, the
>location of an accessible exposition?
AFAIK it's the other way around. In principle quantum computers are no
more powerful than Turing machines, but they could (at least
theoretically) solve NP-hard problems in polynomial time, thus
rendering them solvable in practice. (A way to look at it is that a
quantum computer spawns an exponential number of copies of itself, all
running in parallel universes, then collects the desired result from
one copy at the end.)
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
In article <·····················@129.59.212.53>,
····@vanderbilt.edu (sv0f) wrote:
> I've heard it said (but never by a competent person) that quantum
> computers can solve problems that evade Turing-equivalent formalisms,
> at least in principle. Anyone know if this is true, and if so, the
> location of an accessible exposition?
I don't know - but on another track, Peter Wegner claims that
interaction machines are more powerful than Turing machines. I think
this is very interesting (and, for those who followed recent
discussions, might lead to something useful IMHO ;).
See http://www.cs.brown.edu/people/pw/home.html
Pascal
--
"If I could explain it, I wouldn't be able to do it."
A.M.McKenzie
"Pascal Costanza" <········@web.de> wrote in message
···································@news.netcologne.de...
> In article <·····················@129.59.212.53>,
> ····@vanderbilt.edu (sv0f) wrote:
>
> > I've heard it said (but never by a competent person) that quantum
> > computers can solve problems that evade Turing-equivalent formalisms,
> > at least in principle. Anyone know if this is true, and if so, the
> > location of an accessible exposition?
>
> I don't know - but on another track, Peter Wegner claims that
> interaction machines are more powerful than Turing machines. I think
> this is very interesting (and, for those who followed recent
> discussions, might lead to something useful IMHO ;).
>
> See http://www.cs.brown.edu/people/pw/home.html
Interaction may be more efficient at a task than a direct algorithm, but
I doubt it adds theoretical capability. Couldn't an interaction system
be modeled as a blackboard-based system on a regular computer?
Imagine a driver which pseudo-randomly chooses an agent (a program) to run.
That program does a bit of work, checks whether anything has been written
to certain parts of memory, possibly writes something to a shared part
of the memory and returns control to the driver while tracking where it
was so it can resume later on.
In article <······························@news.netcologne.de>, Pascal
Costanza <········@web.de> wrote:
> In article <·····················@129.59.212.53>,
> ····@vanderbilt.edu (sv0f) wrote:
>
> > I've heard it said (but never by a competent person) that quantum
> > computers can solve problems that evade Turing-equivalent formalisms,
> > at least in principle. Anyone know if this is true, and if so, the
> > location of an accessible exposition?
>
> I don't know - but on another track, Peter Wegner claims that
> interaction machines are more powerful than Turing machines. I think
> this is very interesting (and, for those who followed recent
> discussions, might lead to something useful IMHO ;).
>
> See http://www.cs.brown.edu/people/pw/home.html
I finally got around to reading this and it seems to me that Wegner is
wrong. In fact, his argument seems so obviously wrong that I'm a little
surprised that this was published in CACM.
I don't want to say too much more about this because this topic seems to
have died a well-deserved quiet death, but I thought I mention this just
in case someone thinks Wegner is right and wants to try to explain why.
E.
In article <····················@k-137-79-50-102.jpl.nasa.gov>,
···@jpl.nasa.gov (Erann Gat) wrote:
>I finally got around to reading this and it seems to me that Wegner is
>wrong. In fact, his argument seems so obviously wrong that I'm a little
>surprised that this was published in CACM.
>
>I don't want to say too much more about this because this topic seems to
>have died a well-deserved quiet death, but I thought I mention this just
>in case someone thinks Wegner is right and wants to try to explain why.
I downloaded and skimmed a few of the papers. His main (interesting)
claim seemed to go:
(1) The inputs to Turing Machines must be finite in length.
(2) An Interactive Machine is one that constantly
gets input from and broadcasts output to the external
environment.
(3) The (continual stream of) inputs to an Interaction
Machine can be arbitrarily (perhaps infinitely) long because
time is arbitrary (perhaps infinitely) long in duration.
(4) Moreover, the external environment supplying the
stream of inputs can inspect the Interactive Machine's
stream of outputs, and adjust future inputs in an
adverserial manner.
(5) THEREFORE, Interactive Machines are more powerful
than Turing Machines.
This is a bad argument (in part because I have probably misunderstood
it). The infinite version of (3) is questionable to my eyes; I don't
see that (4) much matters; and I'm unsure whey (5) follows from the
rest.
I think Wegner is broadly correct in describing Turing Machines
as functional black boxes: given an input, they compute and output.
This is a one-shot scenario. It differs, at least on the surface,
from the scenario when the black box and environment are co-routines,
so to speak, each iteratively responding to the last output of the
other with a new input for the next time step. But is the difference
more than skin deep? Does it imply extra-Turing computational power?
I wasn't convinced.
[By the way, the papers I found most useful were: "Why Interaction
is More Powerful Than Algorithms" (CACM, 1997) and "Towards Empirical
Computer Science" (The Monist, Spring, 1999). The in press article
was much less useful.]
From: Joe Marshall
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <fzqjkoup.fsf@ccs.neu.edu>
sv0f <····@vanderbilt.edu> writes:
> I think Wegner is broadly correct in describing Turing Machines
> as functional black boxes: given an input, they compute and output.
> This is a one-shot scenario. It differs, at least on the surface,
> from the scenario when the black box and environment are co-routines,
> so to speak, each iteratively responding to the last output of the
> other with a new input for the next time step. But is the difference
> more than skin deep? Does it imply extra-Turing computational power?
> I wasn't convinced.
I'm not convinced either. Certainly if the environment were doing
something computable (in the Turing sense), then it would be possible
to program a Universal Turing Machine to emulate both the black box
and the environment in alternating steps.
In any case, Turing had a notion of an `oracle' that could provide
answers to non-computable questions. A Turing machine with an oracle
would definitely be more powerful than a Turing machine, but it
appears that the `oracle' would have to be some primitive `built-in'
to the universe. You couldn't create one out of `standard' parts.
"sv0f" <····@vanderbilt.edu> wrote in message ·······························@news.vanderbilt.edu...
>
> I downloaded and skimmed a few of the papers. His main (interesting)
> claim seemed to go:
>
> (1) The inputs to Turing Machines must be finite in length.
> (2) An Interactive Machine is one that constantly
> gets input from and broadcasts output to the external
> environment.
> (3) The (continual stream of) inputs to an Interaction
> Machine can be arbitrarily (perhaps infinitely) long because
> time is arbitrary (perhaps infinitely) long in duration.
> (4) Moreover, the external environment supplying the
> stream of inputs can inspect the Interactive Machine's
> stream of outputs, and adjust future inputs in an
> adverserial manner.
> (5) THEREFORE, Interactive Machines are more powerful
> than Turing Machines.
>
> This is a bad argument (in part because I have probably misunderstood
> it). The infinite version of (3) is questionable to my eyes; I don't
> see that (4) much matters; and I'm unsure whey (5) follows from the
> rest.
>
> I think Wegner is broadly correct in describing Turing Machines
> as functional black boxes: given an input, they compute and output.
> This is a one-shot scenario. It differs, at least on the surface,
> from the scenario when the black box and environment are co-routines,
> so to speak, each iteratively responding to the last output of the
> other with a new input for the next time step. But is the difference
> more than skin deep? Does it imply extra-Turing computational power?
> I wasn't convinced.
>
You could achieve the same thing by hooking two TM's together
input to output, one playing the IM and one playing the environment.
Then the whole thing can be collapsed to one TM.
I'll have to take look at his papers. I don't see it either.
--
Geoff
In article <·····················@news20.bellglobal.com>,
"Geoffrey Summerhayes" <·······@NhOoStPmAaMil.com> wrote:
>You could achieve the same thing by hooking two TM's together
>input to output, one playing the IM and one playing the environment.
>Then the whole thing can be collapsed to one TM.
(I think) Wegner hand-waives away this objection with a cryptic
remark that the environment can act in an adveserial manner.
My only experience with adverserial arguments is to establish
lower bounds, not classes of computational power, so this
tactic didn't work for me.
Just a heads up for when you read his paper(s).
"sv0f" <····@vanderbilt.edu> wrote in message ·······························@news.vanderbilt.edu...
> In article <·····················@news20.bellglobal.com>,
> "Geoffrey Summerhayes" <·······@NhOoStPmAaMil.com> wrote:
>
> >You could achieve the same thing by hooking two TM's together
> >input to output, one playing the IM and one playing the environment.
> >Then the whole thing can be collapsed to one TM.
>
> (I think) Wegner hand-waives away this objection with a cryptic
> remark that the environment can act in an adveserial manner.
>
> My only experience with adverserial arguments is to establish
> lower bounds, not classes of computational power, so this
> tactic didn't work for me.
>
> Just a heads up for when you read his paper(s).
Since you've done it already this paper might interest you
http://citeseer.nj.nec.com/vanleeuwen00turing.html
--
Geoff
In article <·····················@news20.bellglobal.com>,
"Geoffrey Summerhayes" <·············@hotmail.com> wrote:
>http://citeseer.nj.nec.com/vanleeuwen00turing.html
Thanks for the reference. I downloaded and read it last night.
The argument is more sober and concrete than Wegner's, although
because it's an exposition, they present theorems that are proved
elsewhere.
The paper also ties the presented results into a literature on
"non-uniform" computation that I didn't know existed.
I will definitely follow up on the paper's arguments and citations
to this literature.
"Geoffrey Summerhayes" <·············@hotmail.com> wrote in message news:<·····················@news20.bellglobal.com>...
> Since you've done it already this paper might interest you
>
> http://citeseer.nj.nec.com/vanleeuwen00turing.html
Well, I read it, and I don't buy it.
If I understood correctly, the paper lays out how "site machines" (i.e.
upgradeable networked computers) are equivalent to "interactive turing machines
with advice" (i.e. TM's with a limited form of oracle).
This part is reasonable.
The paper establishes that interactive TMs are computationally more powerful
than regular TMs, with a short outline of how they can solve the halting problem.
Ok again, although that's one hell of an advice function.
The problem, though, is that site machines (or interactive TMs) have nothing to
say about computers in real life.
E.g. take all the computers on earth and view them as one giant single
computer. This has no more theoretical power than a regular turing machine.
In as far as interactive TMs are useful for describing models of "difficult"
computational problems like social behaviour, I can see their utility.
But if interactive TMs are being touted as some kind of new computation, more
powerful than algorithms, that is mistaken.
With the appropriate advice function or oracle, anything can be done. With
humans serving as the oracles by doing hardware upgrades, the halting problem
ain't gonna be solved anytime soon.
--
Cheers, The Rhythm is around me,
The Rhythm has control.
Ray Blaak The Rhythm is inside me,
·····@telus.net The Rhythm has my soul.
Here's my take on the paper:
Turing machines are sequential processors with a finite control
program, and linear unbounded (infinite) storage. They don't exist
in real life, but are imitated by your every day computer.
Interactive TM's are turing machines with an added ability to
interact with other machines over a network. The idea in this
paper is that if we have an infinite number of such machines
over a network, they can solve the halting problem of a program
on a single machine. And just as TM's don't exist but are
approximated by IBM PC's, Interactive TM's don't exist but
can be approximated by (a segment of) the Internet. What
gives the added power in ITM's is not interaction by itself,
but the unbounded number of processors.
Alan
From: Ray Blaak
Subject: Re: interactive TMs (was Re: Other languages with Lisp macros)
Date:
Message-ID: <uznod6izu.fsf@telus.net>
"Alan Baljeu" <·······@sympatico.deleteme.ca> writes:
> Turing machines are sequential processors with a finite control program, and
> linear unbounded (infinite) storage. They don't exist in real life, but are
> imitated by your every day computer.
>
> Interactive TM's are turing machines with an added ability to interact with
> other machines over a network. The idea in this paper is that if we have an
> infinite number of such machines over a network, they can solve the halting
> problem of a program on a single machine.
Note that unbounded is not the same as infinite. More to the point, in the
real world, there is no measurable, usable notion of infinity.
From the paper itself, section 6:
If the life-span of these machines is taken to infinity, then the
computational equivalence of the respective machines with interactive Turing
machines with advice is a mathematical consequence. If the life-span of the
machines at hand is bounded, any finite portion of the computation will
remain within the scope of standard Turing machines and the standard
Church-Turing thesis.
And there's the rub. In real life we do not work with infinitly big, precise,
numerous, or long living machines. In particular, any result we want from a
machine we want in a useful time frame, otherwise we cannot use it.
I.e. in real life we can only work with "finitely describable algorithms" to
again quote the paper.
Note also that being equivalent to an "interactive Turing machine with advice"
is misleading. It all depends on the "advice" that can be had. If the advice
is "stupid" we don't gain much.
--
Cheers, The Rhythm is around me,
The Rhythm has control.
Ray Blaak The Rhythm is inside me,
·····@telus.net The Rhythm has my soul.
> From the paper itself, section 6:
>
> If the life-span of these machines is taken to infinity, then the
> computational equivalence of the respective machines with interactive
Turing
> machines with advice is a mathematical consequence. If the life-span of
the
> machines at hand is bounded, any finite portion of the computation will
> remain within the scope of standard Turing machines and the standard
> Church-Turing thesis.
>
> And there's the rub. In real life we do not work with infinitly big,
precise,
> numerous, or long living machines. In particular, any result we want from
a
> machine we want in a useful time frame, otherwise we cannot use it.
You are right. Since our machines are finite, a large finite number of
co-operating machines can be imitated by a single turing machine which is
infinite.
However, Turing machines are imitated by von Neumann machines, and IM's are
imitated (or could conceivably be imitated) by a segment of the internet.
It seems to me that if theory says there is more possibility, then practice
should
be able to demonstrate a consequence. For example, a finite state machine
can
recognize palindromes, provided you limit the palindromes to a maximum
length,
and have enough states. In fact, a FSM can simulate a finite turing machine
given enough states. And likewise, a finite turing machine can imitate a
finite
Interaction machine, but are the sizes of each comparable?
The question which arises in my mind is whether it's simply a multiplicity
of computers, or whether it's heavy interaction which is proposed as being
the theoretical gateway to increased power.
Coming closer to reality, are there not kinds of problems would benefit from
having allocate_computer(), release_computer(), transmit_program(),
send_data_packet()? Are the benefits significant enough that it would be
difficult to _describe_ the calculation in a linear programming model
without
such facilities (apart from simulation), or just that it would take a lot
longer?
What if the lisp garbage collector were extended to collect networked
computers
and free them for use on other problems? :-)
Alan
From: Ray Blaak
Subject: Re: interactive TMs (was Re: Other languages with Lisp macros)
Date:
Message-ID: <uel5n7gms.fsf@telus.net>
"Alan Baljeu" <·······@sympatico.deleteme.ca> writes:
> And likewise, a finite turing machine can imitate a finite Interaction
> machine, but are the sizes of each comparable?
It depends on the advice function, or oracle. If the oracle is tractable
enough, then yes, they're comparable.
> The question which arises in my mind is whether it's simply a multiplicity
> of computers, or whether it's heavy interaction which is proposed as being
> the theoretical gateway to increased power.
I would say it's the advice function or oracle with its magic ability to give
uncomputable answers (in the normal TM sense).
Parallelism does not fundamentally increase the theoretical computational
abilities. It only improves things by a polynomial amount (which admittedly is
often significant in real life).
> Coming closer to reality, are there not kinds of problems would benefit from
> having allocate_computer(), release_computer(), transmit_program(),
> send_data_packet()?
There is no question that there are problems that would benefit. E.g. I would
much prefer to get my results in a day versus 100 years.
However, this kind of improvement does not exceed the theoretical abilities of
a regular TM.
> Are the benefits significant enough that it would be difficult to _describe_
> the calculation in a linear programming model without such facilities (apart
> from simulation), or just that it would take a lot longer?
There is a good point here. We think about TMs and RAM machines instead of our
actual, in practice, finite state machines, since they are easier to reason
about for us.
We do calculus with real numbers even though they can't exist on any physical
machine we can make (i.e. floating point numbers are only an approximation),
simply because the math is simpler.
Similarly, more powerful models of computation could very well be more useful
for describing/manipulating certain kinds of problems because they are simpler
to work with.
--
Cheers, The Rhythm is around me,
The Rhythm has control.
Ray Blaak The Rhythm is inside me,
·····@telus.net The Rhythm has my soul.
"Alan Baljeu" <·······@sympatico.deleteme.ca> writes:
> However, Turing machines are imitated by von Neumann machines, and IM's are
> imitated (or could conceivably be imitated) by a segment of the internet.
I doubt it.
The Internet is really much more like a finite system than an infinite
one. It illustrates none of the ACTUAL problems of an infinite number of
machines.
- The need for infinite storage on a single processor just to store
the IP address of one of the infinite machines that you want to
communicate with.
- The notion that a router having to deal with packets of infinite size
just to be able to access the IP address of the target machine.
- The notion of an infinite amount of wire being needed to interconnect
the machines (not including the amount of time needed to set these
machines up and the amount of air conditioning they require, and the
effect of that air conditioning (or lack thereof) on global warming).
- The notion that a router trying to triage addresses of packets going
by would need infinite storage just to hold a single packet, but also
even after triaging even-numbered packets to the router on the left
and odd-numered packets to the router on the right would still have
given an infinite number of packets to each of those two routers and so
arguably would not have reduced the size of the load on either of those
machines (leading one to wonder if any packets would ever, in fact,
be delievered).
- The issue that machines take up physical space, and so can't all exist
physically close, and so, in fact, many (most, and to a close
approximation, "all") will not be anywhere nearby in physical space and
so will require huge amounts of time to reach (even assuming zero time
wasted in router triage, and worse if you assume routing is going to
slow things down).
- The idea that infinite machines cost infinite money.
- The idea that cable and DSL companies take already as close to an
infinite number of days as I ever want to experience to finally come
and install things, and you have to multiply that time the infinite
number of machines. And don't even talk to me about how long you're
going to spend on hold with the company unless they have an infinite
number of customer service reps if anything ever goes offline or if
I forget one of my infinite numbers of passwords.
- The idea that 90% of the bandwidth will be wasted to porn.
(Yes, you had wondered what the universe's secret "dark matter" was...)
From: Erann Gat
Subject: Re: interactive TMs (was Re: Other languages with Lisp macros)
Date:
Message-ID: <gat-0403030818150001@192.168.1.51>
In article <···············@shell01.TheWorld.com>, Kent M Pitman
<······@world.std.com> wrote:
> - The need for infinite storage on a single processor just to store
> the IP address of one of the infinite machines that you want to
> communicate with.
I think this is a straw man. Obviously you'd want to use some kind of
relative addressing scheme on the infi-net just as you do on a Turing
machine.
Actually, I think it's all even much simpler than that at least on a
theoretical level: a multi-head TM is equivalent to a single-head TM as
long as the number of heads is finite. But a multi-head TM with an
infinite number of heads might be able to do things that a TM can't. For
one thing, the program for an infinite-head TM could be infinitely long,
but all the instructions in such a program could nonetheless be executed
in finite time. I think that on a theoretical level this idea is not so
easily dismissed. And even on a practical level it seems to me that once
you put a few thousand machines together you get behavior that is
qualitatively different from what you can get from a single machine.
(Think Google.)
E.
···@jpl.nasa.gov (Erann Gat) writes:
> Actually, I think it's all even much simpler than that at least on a
> theoretical level: a multi-head TM is equivalent to a single-head TM as
> long as the number of heads is finite. But a multi-head TM with an
> infinite number of heads might be able to do things that a TM can't. For
> one thing, the program for an infinite-head TM could be infinitely long,
> but all the instructions in such a program could nonetheless be executed
> in finite time. I think that on a theoretical level this idea is not so
No there are different types of infinity. Lets say you have a infinite
line of TM's and the program is read the tape. And each TM has it's own
infinite tape feed. This turns into the equivalent problem of 1 TM and
an infinitely long tape for each TM and so it never finishes. Some
infinites are more infinite then others.
marc
> easily dismissed. And even on a practical level it seems to me that once
> you put a few thousand machines together you get behavior that is
> qualitatively different from what you can get from a single machine.
> (Think Google.)
>
> E.
From: Ray Blaak
Subject: Re: interactive TMs (was Re: Other languages with Lisp macros)
Date:
Message-ID: <uu1ejhv73.fsf@telus.net>
···@jpl.nasa.gov (Erann Gat) writes:
> In article <···············@shell01.TheWorld.com>, Kent M Pitman
> <······@world.std.com> wrote:
>
> > - The need for infinite storage on a single processor just to store
> > the IP address of one of the infinite machines that you want to
> > communicate with.
>
> I think this is a straw man. Obviously you'd want to use some kind of
> relative addressing scheme on the infi-net just as you do on a Turing
> machine.
With relative addressing you would then tend to have finite regions of local
computations, perhaps nullifying the "power of the infinite".
> Actually, I think it's all even much simpler than that at least on a
> theoretical level: a multi-head TM is equivalent to a single-head TM as
> long as the number of heads is finite. But a multi-head TM with an
> infinite number of heads might be able to do things that a TM can't. For
> one thing, the program for an infinite-head TM could be infinitely long,
> but all the instructions in such a program could nonetheless be executed
> in finite time. I think that on a theoretical level this idea is not so
> easily dismissed. And even on a practical level it seems to me that once
> you put a few thousand machines together you get behavior that is
> qualitatively different from what you can get from a single machine.
> (Think Google.)
A few thousand is nowhere near infinite.
It is certainly true that you can get qualitatively different effects from
massive parallelism.
It is just that you do not get any theoretically more powerful effects.
We certainly do not know how to write infinitely long programs. Indeed the
more massively parallel systems we can make, the dumber and more repetitive
each processor's program seems to be.
Within the realm of finite you can still have "huge", you can still have "big
enough for useful effects".
--
Cheers, The Rhythm is around me,
The Rhythm has control.
Ray Blaak The Rhythm is inside me,
·····@telus.net The Rhythm has my soul.
In article <·············@telus.net>, Ray Blaak <·····@telus.net> wrote:
> A few thousand is nowhere near infinite.
>
> It is certainly true that you can get qualitatively different effects from
> massive parallelism.
>
> It is just that you do not get any theoretically more powerful effects.
Agreed, but qualitatively different may be enough to be interesting.
> We certainly do not know how to write infinitely long programs. Indeed the
> more massively parallel systems we can make, the dumber and more repetitive
> each processor's program seems to be.
Yes, rather reminiscent of the structure of the human brain, which is
pretty interesting despite being (probably, notwithstanding Penrose) a TM
(or perhaps an FSM with a whompin' big number of states).
E.
"Kent M Pitman" <······@world.std.com> wrote in message
····················@shell01.TheWorld.com...
> "Alan Baljeu" <·······@sympatico.deleteme.ca> writes:
>
> > However, Turing machines are imitated by von Neumann machines, and IM's
are
> > imitated (or could conceivably be imitated) by a segment of the
internet.
>
> I doubt it.
>
> The Internet is really much more like a finite system than an infinite
> one. It illustrates none of the ACTUAL problems of an infinite number of
> machines.
>
> - The need for infinite storage on a single processor just to store
> the IP address of one of the infinite machines that you want to
> communicate with.
I think this misses the point. Today's computers with Gigabytes of memory
are no closer to infinity of memory than the ENIAC was 50+ years ago. Yet
Turing machines were a useful model for reasoning about computational power
in 1936 when they were invented, and the concept was applicable to the first
vacuum-tube machines built.
Likewise, a computer network needn't actually have billions of processors to
use the interaction-machine concept. 100 could be a good start. (Consider
that quantum computational power is being investigated using examples
involving only 10s of qubits.)
All our machines are finite. But the theory shows us what they lead to in
the
limit. Analogy: the set of integers is infinite, but the powerset of
integers
(set of all subsets) is uncountably infinite. That's the theoretical limit,
but it is connected to the fact that in the finite world, the powerset of
integers 1..n is exponentially larger than the set of those same integers.
Someone has written a paper arguing that infinite connected TM's have more
theoretical capability (or something like that). The question is whether
this
can be translated into practical algorithms that exploit interaction on
finite
subsets of the infinite network model.
Every Turing machine program, if it halts, uses finite tape, and can hence
be
modeled by a computer of large enough capacity. Likewise, every IM program,
if
it halts, will only get around to using a finite set of computers. (If this
is
not true, then the whole theory is rubbish IMO.) Therefore, we should be
able
to design and build interesting IM programs. In fact, I understood the
paper
saying that we already are doing so, and just lacked the theoretical model
to
describe it.
Alan
"Alan Baljeu" <·······@sympatico.deleteme.ca> writes:
> All our machines are finite. But the theory shows us what they lead
> to in the limit. [...] Someone has written a paper arguing that
> infinite connected TM's have more theoretical capability (or
> something like that). The question is whether this can be
> translated into practical algorithms that exploit interaction on
> finite subsets of the infinite network model.
>
> Every Turing machine program, if it halts, uses finite tape, and can
> hence be modeled by a computer of large enough capacity. Likewise,
> every IM program, if it halts, will only get around to using a
> finite set of computers. (If this is not true, then the whole
> theory is rubbish IMO.) Therefore, we should be able to design and
> build interesting IM programs. In fact, I understood the paper
> saying that we already are doing so, and just lacked the theoretical
> model to describe it.
This leaves me with a vague sense that what you're saying, though, is
that there are no more rationals than reals, because you can map the
rationals onto the reals, and hence you get no more counting "ummph"
but having invented the rationals. If all it takes is "a lot more
TMs" to simulate an "IM", count me as (at least for now, though
obviously not necessarily unchangeably) skeptical that you've added
any interesting computational power.
Disclaimer: This all goes easily well beyond any lingering
mathematical expertise my simplistic little brain has, but my
intuitions are that while it's always fun to imagine something
stronger than a TM, I've not yet seen the proof that such exists.
Ultimately, I'll probably have to trust some better mathemetician who
will simply tell me at some point that I'm wrong.
If it makes any sense, and I might just be babbling here, the "limit"
of my understanding is that in some sense I'm looking for some
Cantor-style diagonalization proof that says that somehow, by
interconnecting the machines in this way, you can get to some result
that evades projection back into the linear space of a TM.
Btw, I would welcome better terminology in the computer field for
talking about the amount of time it takes to get to a certain answer.
The existing terms seem not to capture even the well-known issue that
"programming power" (a la "Turing power") bears little relationship to
"expressive power" (not to date quantified, to my knowledge), such
that you could say much of anything that is at once concise, useful,
and formal that went to the point of "Perl being preferrable to
Fortran or Assembly or, for that matter, a raw Turing Machine for web
processing"; that is, one wants to say not only "this is computable"
but "within a known window of commercially useful time, developers are
more likely to converge on a testably correct solution using language
X than language Y" and "within a known window of end-application
compute time, runtime facility X is more likely than runtime facility
Y to get an answer in finite space and time for typical applications
of a certain kind". We all know these truths to exist, and we
occasionally allude to benchmarks to empirically confirm them in a
sales situation, but there's pathetically little terminology that has
come out which would be suitable for speaking out loud in a casual
conversation or scrawling on a napkin at dinner ... there are only the
unreasonable extremes of the vacuous and the overly formal. Even
absent the issue of IMs being more powerful than TMs in a Turing Power
sense, it might well turn out that IMs were more powerful than TMs
in what I'm calling an "expressive" sense. (And that's mostly for the
good even though in this one conversation we're having now, it could
easily confuse one into believing one has more-than-turing-power
when what one really has is just better-than-turing-programming-tools. :)
Kent M Pitman <······@world.std.com> writes:
> Disclaimer: This all goes easily well beyond any lingering
> mathematical expertise my simplistic little brain has, but my
> intuitions are that while it's always fun to imagine something
> stronger than a TM, I've not yet seen the proof that such exists.
Turing machines do not exist, either, at least not in the sense that
you can find incarnations of them in CS departments. 8-)
Florian Weimer <··@deneb.enyo.de> writes:
> Kent M Pitman <······@world.std.com> writes:
>
> > Disclaimer: This all goes easily well beyond any lingering
> > mathematical expertise my simplistic little brain has, but my
> > intuitions are that while it's always fun to imagine something
> > stronger than a TM, I've not yet seen the proof that such exists.
>
> Turing machines do not exist, either, at least not in the sense that
> you can find incarnations of them in CS departments. 8-)
Funnily enough, what drew me to Lisp originally was that in high
school, isolated geographically from anyone to teach me computer
science, I was trying to program an a "learning" application in BASIC.
I immediately found myself saying "but this has only fixed size
datastructures, I don't know how much space to allocate (DIM)" and I
hypothesized that other languages must have better ways of managing
such things dynamically. But determined not to be held back by BASIC,
I realized that the cassette tape drive on the machine could be used
as extended store (which to me seemed infinite, compared to the 8K I
could store in RAM). In retrospect, it was a lot like a Turing
machine. :) Had I run out of tape, I suppose I'd have though
otherwise. But I never found the end of the tape (a 90 minute TDK
cassette audio tape, trying to pretend to be a data grade tape,
although in 1975, there was little difference), so it was for my
purposes then, infinite. When I later saw Lisp, and CONS, you can
imagine how much easier I found this than manually managing a freelist
and a set of interconnected defstruct-like structures on thetape.
(Thank god my chosen structure was monotonic in nature, not that I
knew the term at that point in high school, so I didn't have
to rewrite the whole tape every time I learned something.)
"Kent M Pitman" <······@world.std.com> wrote in message
····················@shell01.TheWorld.com...
> "Alan Baljeu" <·······@sympatico.deleteme.ca> writes:
>
> > All our machines are finite. But the theory shows us what they lead
> > to in the limit. [...] Someone has written a paper arguing that
> > infinite connected TM's have more theoretical capability (or
> > something like that). The question is whether this can be
> > translated into practical algorithms that exploit interaction on
> > finite subsets of the infinite network model.
> >
> > Every Turing machine program, if it halts, uses finite tape, and can
> > hence be modeled by a computer of large enough capacity. Likewise,
> > every IM program, if it halts, will only get around to using a
> > finite set of computers. (If this is not true, then the whole
> > theory is rubbish IMO.) Therefore, we should be able to design and
> > build interesting IM programs. In fact, I understood the paper
> > saying that we already are doing so, and just lacked the theoretical
> > model to describe it.
>
> This leaves me with a vague sense that what you're saying, though, is
> that there are no more rationals than reals, because you can map the
> rationals onto the reals, and hence you get no more counting "ummph"
> but having invented the rationals. If all it takes is "a lot more
> TMs" to simulate an "IM", count me as (at least for now, though
> obviously not necessarily unchangeably) skeptical that you've added
> any interesting computational power.
It took me a bit to figure this out. Let me see if I follow you.
1. If a Turing Machine corresponds to integers, an IM corresponds to
rationals (position-on-tape/nth-prime(computer-number)).
2. The rationals map onto the integers, but reals do not map onto
integers. So reals are bigger than rationals.
3. Conclusion: IM's probably aren't more complete than TM's.
This makes sense to me, although I'll leave the door open for
any other arguments.
Regarding expressivity versus computational power, something just came
to mind. I don't know if this is true or not:
If you can write an interpreter for A in B then A is at least as
powerful as B, although it may be less expressive.
If A is less powerful than B, you will require an exponential amount
of _code_ to accomplish the same task in A. In the realm of infinite
machines, this means the code size would become infinite.
In the realm of finite machines, the code size would merely become
extremely large.
Alan
"Alan Baljeu" <·······@sympatico.deleteme.ca> writes:
> Regarding expressivity versus computational power, something just came
> to mind. I don't know if this is true or not:
>
> If you can write an interpreter for A in B then A is at least as
> powerful as B, although it may be less expressive.
> If A is less powerful than B, you will require an exponential amount
> of _code_ to accomplish the same task in A. In the realm of infinite
> machines, this means the code size would become infinite.
> In the realm of finite machines, the code size would merely become
> extremely large.
Actually, I was looking for something that was more like the following:
Every language makes some programs short at the expense of others.
To stretch this analogy to the limit, if we think of every language
as being like a set of Goedel numbers, with some programs being short
in the sense of having low-numbered Goedel identifiers and some being long
as in requiring a higher number, then clearly there is a statistical
set of programs that are favored with short numbers and different languages
select different such sets. So, very very loosely, Perl selects programs
whose Goedel numbers are biased to small for string programs while Fortran
selects programs whose Goedel numbers are small for numeric applications.
In a sense, this takes into account the three laws of thermodynamics
(can't win, can't break even, can't get out of the game => you don't get
something for nothing) and says that expressivity is something that always
trades something for something. there are only so many short programs.
there are only so many three letter domain names. the informational land
grab of today is about vying for the 'short named' things, or perhaps
about doing clever tricks with segmentation so that everyone can perceive
short names locally.
One reason I raise this in this context is that it's not obvious to me
when you talk about infinite processors connected whether 'short names'
are rational to think about. While one might not have infinnite associates,
the quesiton is whethre one has "more than the usual number of associaites"
and hence whether one needs bignum IP addressing or if there is a reason
to believe that the number of associates does not grow even as the number
of machines grows for some locality reason. I'm inclined to believe that
if ther eis any benefit to "infinite computers" it's going to be the loss
of this sense of locality, or else everything is going to translate to
turing machines.
But maybe I'm being too cryptic in my remarks just to save typing. Ask me
if something is vague. I AM being vague and handwavy, but maybe not in the
ways you're thinking. ;)
Kent M Pitman <······@world.std.com> writes:
> "Alan Baljeu" <·······@sympatico.deleteme.ca> writes:
>
> > Regarding expressivity versus computational power, something just came
> > to mind. I don't know if this is true or not:
> >
> > If you can write an interpreter for A in B then A is at least as
> > powerful as B, although it may be less expressive.
> > If A is less powerful than B, you will require an exponential amount
> > of _code_ to accomplish the same task in A. In the realm of infinite
> > machines, this means the code size would become infinite.
> > In the realm of finite machines, the code size would merely become
> > extremely large.
>
> Actually, I was looking for something that was more like the following: [...]
To be clear why I was looking for something else, the main thing was
that the really interesting differences between Fortran and C and Lisp
and Perl and Java are not, for the most part, going to reflect themselves
in "exponentially large" differences, yet I think there are material
differences. So I'm looking for explanation tools that are meaningful
in describing qualitatively that there is a difference, yet without being
something that puts things that are not thus exponential into an equivalence
class.
Certainly for the purpose of distinguishing IMs and TMs, your
terminology might still be useful, if that was the nature of the
difference.
> > Actually, I was looking for something that was more like the following:
[...]
>
> To be clear why I was looking for something else, the main thing was
> that the really interesting differences between Fortran and C and Lisp
> and Perl and Java are not, for the most part, going to reflect themselves
> in "exponentially large" differences, yet I think there are material
> differences. So I'm looking for explanation tools that are meaningful
> in describing qualitatively that there is a difference, yet without being
> something that puts things that are not thus exponential into an
equivalence
> class.
>
> Certainly for the purpose of distinguishing IMs and TMs, your
> terminology might still be useful, if that was the nature of the
> difference.
Ah, this is a different subject, in which I am as inexpert as in the TM
subject :-)
To compare Turing-complete languages in terms of expressiveness.
Allow me to suggest an approach. Each of the above languages can
do exactly what each of the others does: simply write an cross-
interpreter. Any particular algorithm can be coded and written as
a function, and each language can use that function. The distinction
is the tools to build the algorithms. What are the basic facilities
provided by the language, and how can they be put together?
Given a facility in one language, can that facility be imitated in
the other language, and how much code does it take? To be precise,
the question is whether a language can express a concept in terms
of the concepts it directly provides.
Alan
In article <·····················@news20.bellglobal.com>,
"Alan Baljeu" <·······@sympatico.deleteme.ca> wrote:
>"Kent M Pitman" <······@world.std.com> wrote in message
>····················@shell01.TheWorld.com...
>> This leaves me with a vague sense that what you're saying, though, is
>> that there are no more rationals than reals, because you can map the
>> rationals onto the reals, and hence you get no more counting "ummph"
>> but having invented the rationals.
[...]
>2. The rationals map onto the integers, but reals do not map onto
>integers. So reals are bigger than rationals.
The number of reals (i.e., the cardinality of the set of real numbers)
is strictly greater than the number of rationals, the number of
integers, and the number of natural numbers. (These last three
numbers are, somewhat surprisingly, the same.)
I think this is what Alan is saying, but "bigger" is an odd
choice of words. That is, his point (2) could be interpreted
as saying the largest real number is larger than the largest
rational number, which is of course not true.
All of this is ICO -- In Cantor's Opinion ;-)
According to sv0f <····@vanderbilt.edu>:
> The number of reals (i.e., the cardinality of the set of real numbers)
> is strictly greater than the number of rationals, the number of
> integers, and the number of natural numbers. (These last three
> numbers are, somewhat surprisingly, the same.)
I recall vaguely (vague-ness's in vogue ;-) these are aleph-1
and aleph-0, respectively. I also recall aleph-2 "exists", but I don't
remember what it "counts". Any idea?
--
Ng Pheng Siong <····@netmemetic.com>
http://firewall.rulemaker.net -+- Improve Your Firewall Operation ROI
http://www.post1.com/home/ngps -+- Open Source Python Crypto & SSL
····@netmemetic.com (Ng Pheng Siong) writes:
> According to sv0f <····@vanderbilt.edu>:
> > The number of reals (i.e., the cardinality of the set of real numbers)
> > is strictly greater than the number of rationals, the number of
> > integers, and the number of natural numbers. (These last three
> > numbers are, somewhat surprisingly, the same.)
>
> I recall vaguely (vague-ness's in vogue ;-) these are aleph-1
> and aleph-0, respectively. I also recall aleph-2 "exists", but I don't
> remember what it "counts". Any idea?
A quick search in Google turns up the following page which looks to have
a fairly readable and comprehensive account of Cantor and the ordinal
infinities designated by Aleph[n], for n >= 0.
http://home.earthlink.net/~mrob/pub/math/largenum-6.html
The page seems to have been written by someone named Robert Munafo.
Btw, a bit of poking around at Munafo's pages reveals the following other
quite amusing page, graphing the degree to which various programming
languages "suck" and/or "rule" (using a curious kind of empirical
pseudo-statistical metric based on AltaVista web queries)...
http://home.earthlink.net/~mrob/pub/lang_srom.html
According to Kent M Pitman <······@world.std.com>:
> A quick search in Google
Thanks. My Google-instinct deserted me there...
--
Ng Pheng Siong <····@netmemetic.com>
http://firewall.rulemaker.net -+- Improve Your Firewall Operation ROI
http://www.post1.com/home/ngps -+- Open Source Python Crypto & SSL
From: Espen Vestre
Subject: Re: interactive TMs (was Re: Other languages with Lisp macros)
Date:
Message-ID: <kwy93r5slm.fsf@merced.netfonds.no>
····@netmemetic.com (Ng Pheng Siong) writes:
> I recall vaguely (vague-ness's in vogue ;-) these are aleph-1
> and aleph-0, respectively. I also recall aleph-2 "exists", but I don't
> remember what it "counts". Any idea?
This is really a topic for an advanced math course, but VERY roughly,
and given some important assumptions (the "generalized continuum
hypothesis") aleph-(n+1) is the size of the "power set" of aleph-n,
i.e. a set consisting of all the subsets of a set of size aleph-n
(Axiomatic set theory starts getting really fun when you start to
define "inaccessible cardinal numbers" which are so large that they
are larger than the power set of any smaller cardinal number).
--
(espen)
Espen Vestre wrote:
> ····@netmemetic.com (Ng Pheng Siong) writes:
>
> > I recall vaguely (vague-ness's in vogue ;-) these are aleph-1
> > and aleph-0, respectively. I also recall aleph-2 "exists", but I don't
> > remember what it "counts". Any idea?
>
> This is really a topic for an advanced math course, but VERY roughly,
> and given some important assumptions (the "generalized continuum
> hypothesis") aleph-(n+1) is the size of the "power set" of aleph-n,
> i.e. a set consisting of all the subsets of a set of size aleph-n
> (Axiomatic set theory starts getting really fun when you start to
> define "inaccessible cardinal numbers" which are so large that they
> are larger than the power set of any smaller cardinal number).
No! :-)
Aleph-0 is the smallest infinite "cardinal number" (cardinal
numbers are things that count the sizes of sets). So far, so
good. But aleph-(n+1) is *not* defined as the size of the
power set of something whose size is aleph-n. Rather, it's
the *next largest cardinal* after aleph-n. The famous
"continuum hypothesis" says that aleph-1 is the size of
the power set of a thing of size aleph-0 (equivalently,
that there are aleph-1 real numbers). It can neither be
proved nor be disproved using the ordinary axioms of set
theory. The "generalized continuum hypothesis" says that
aleph-(n+1) is the size of the power set of a thing of
size aleph-n. It can't be proved or disproved using the
ordinary axioms of set theory either.
--
Gareth McCaughan ················@pobox.com
.sig under construc
From: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey34r788g5r.fsf@cley.com>
* sv0f wrote:
> I've heard it said (but never by a competent person) that quantum
> computers can solve problems that evade Turing-equivalent formalisms,
> at least in principle. Anyone know if this is true, and if so, the
> location of an accessible exposition?
I think this is not so. Quantum Turing machines can solve some
exponential problems in polynomial time[1], but they are not more
powerful than classical TMs. David Deutsch did a lot of the early
work on this, and I am fairly sure he has written some accessible
summary papers on the theory.
--tim
Footnotes:
[1] As far as I can see, a QTM essentially is an NDTM `inside' - it
can happily `look down' both branches of a choice, which you can
see by thinking of the many-worlds model of QM, which, while
conceptually very weird is formally equivalent to more
conventional models - but because of issues with observation you
don't actually get to see it as an NDTM.
Helu
|From: Joe Marshall <···@ccs.neu.edu>
|Date: 12 Feb 2003 14:33:33 -0500
|Message-ID: <············@ccs.neu.edu>
|
|Another mystery is why non-deterministic Turing machines are no more
|powerful than deterministic ones.
[OT] This is true with regard to computability. With regards to
complexity, (assuming all other resources being equal) the difference
between a NDTM and a DTM is like the difference between NP and P.
While still an open question, It would appear that adding Non
Determinism makes the computing model more powerful.
Regards
Madhu
--
Open system or closed system, enlightenment or ideology, those are the
questions. "John C. Mallery" <····@ai.mit>
On Wed, 12 Feb 2003 10:20:05 -0800, ···@jpl.nasa.gov (Erann Gat)
wrote:
>No it doesn't, but you've left out an important fact: you can apply sizeof
>to types, and in particular to pointer types, and that has to return a
>finite number too. *That* implies that pointers are restricted to a fixed
>number of bits.
But does it? sizeof returns a value in units of char; the standard
says nothing about char having to be 8 bits, or having to have any
limit to how large a number it can store, IIRC.
>There are four classes of computational models that are distinguishable in
>terms of what they can and cannot compute: finite state machines,
>deterministic pushdown automata, non-deterministic pushdown automata, and
>Turing machines.
Yep.
>But as far as I know, why this is so is a grand cosmic
>mystery, rather like trying to understand why pi is irrational.
Right, that's what I was wondering.
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
In article <···············@news.eircom.net>, ··@vorpalbunnyeircom.net
(Russell Wallace) wrote:
> On Wed, 12 Feb 2003 10:20:05 -0800, ···@jpl.nasa.gov (Erann Gat)
> wrote:
>
> >No it doesn't, but you've left out an important fact: you can apply sizeof
> >to types, and in particular to pointer types, and that has to return a
> >finite number too. *That* implies that pointers are restricted to a fixed
> >number of bits.
>
> But does it? sizeof returns a value in units of char; the standard
> says nothing about char having to be 8 bits, or having to have any
> limit to how large a number it can store, IIRC.
No. Chars have to be finite. If they weren't then sizeof would be
meaningless, because sizeof(anything) would be 1.
> >But as far as I know, why this is so is a grand cosmic
> >mystery, rather like trying to understand why pi is irrational.
>
> Right, that's what I was wondering.
Sorry, can't help you there.
E.
From: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey3znp071es.fsf@cley.com>
* Erann Gat wrote:
> No. Chars have to be finite. If they weren't then sizeof would be
> meaningless, because sizeof(anything) would be 1.
Hah! Excellent point! Now, can we devise a model for a C-like
language where, say, sizeof measures things in terms of classes of
infinity which would escape this? I think we can't, because
everything needs to be countable (because you can write a program to
enumerate all pointers, I think...).
--tim
Tim Bradshaw wrote:
> * Erann Gat wrote:
>
>
>>No. Chars have to be finite. If they weren't then sizeof would be
>>meaningless, because sizeof(anything) would be 1.
>
>
> Hah! Excellent point! Now, can we devise a model for a C-like
> language where, say, sizeof measures things in terms of classes of
> infinity which would escape this? I think we can't, because
> everything needs to be countable (because you can write a program to
> enumerate all pointers, I think...).
>
Hmm... I am not so sure about this. Take the set of positive integers
for example. This set has infinite cardinality, but all of the integers
have a finite value. This follows from the Peano axioms. So, we could
have a pointer with an infinite number of bits and still be able to
enumerate all the bits. I am not sure if we could enumerate all the
different values though.
Mind-boggling... :)
--
Thomas.
On 8288 day of my life Erann Gat wrote:
> In article <···············@news.eircom.net>, ··@vorpalbunnyeircom.net
> (Russell Wallace) wrote:
>
> > On Wed, 12 Feb 2003 10:20:05 -0800, ···@jpl.nasa.gov (Erann Gat)
> > wrote:
> >
> > >No it doesn't, but you've left out an important fact: you can apply sizeof
> > >to types, and in particular to pointer types, and that has to return a
> > >finite number too. *That* implies that pointers are restricted to a fixed
> > >number of bits.
> >
> > But does it? sizeof returns a value in units of char; the standard
> > says nothing about char having to be 8 bits, or having to have any
> > limit to how large a number it can store, IIRC.
>
> No. Chars have to be finite. If they weren't then sizeof would be
> meaningless, because sizeof(anything) would be 1.
Is it neccessary for sizeof to be meaningfull? Who cares, if every
data object can fit one infinit cell?
Do we compare abstract C-machine with abstract Turing-machine or real
C-machine with real Turing-machine? Real Turing-machine has finit
memory too.
But comparing real Any-machine with abstract Other-machine is mistake.
--
Ivan Boldyrev remove .microsoft.com from my address
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
Today is the first day of the rest of your life.
On Wed, 12 Feb 2003 16:23:23 -0800, ···@jpl.nasa.gov (Erann Gat)
wrote:
>No. Chars have to be finite. If they weren't then sizeof would be
>meaningless, because sizeof(anything) would be 1.
There's nothing in the standard that says sizeof(any scalar type)
can't be 1. Consider a machine whose memory consists of an array of
cells, each capable of holding an arbitrary integer, where char, int,
void* etc are each stored in a single cell.
>> >But as far as I know, why this is so is a grand cosmic
>> >mystery, rather like trying to understand why pi is irrational.
>>
>> Right, that's what I was wondering.
>
>Sorry, can't help you there.
Oh well, it was worth a try ^.~
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
··@vorpalbunnyeircom.net (Russell Wallace) writes:
> But does it? sizeof returns a value in units of char; the standard
> says nothing about char having to be 8 bits, or having to have any
> limit to how large a number it can store, IIRC.
<limits.h> must define UCHAR_MAX as that limit. The standard
requires all implementations to provide this header and macro;
if you don't have a limit then you can't implement the standard.
On 14 Feb 2003 09:56:21 +0200, Kalle Olavi Niemitalo <···@iki.fi>
wrote:
>··@vorpalbunnyeircom.net (Russell Wallace) writes:
>
>> But does it? sizeof returns a value in units of char; the standard
>> says nothing about char having to be 8 bits, or having to have any
>> limit to how large a number it can store, IIRC.
>
><limits.h> must define UCHAR_MAX as that limit. The standard
>requires all implementations to provide this header and macro;
>if you don't have a limit then you can't implement the standard.
The standard says limits.h must define UCHAR_MAX, and that attempting
to store x in an unsigned char, for all x <= UCHAR_MAX, must work
correctly.
However, correct me if I'm wrong, but it doesn't say anything
whatsoever about what happens if you attempt to store x >= UCHAR_MAX
in an unsigned char. In which case, continuing to give the
mathematically correct result for all x wouldn't violate the standard.
(I don't have a copy of the document to hand; if the wording
specifically prohibits this behavior then I'll admit to being wrong.)
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
··@vorpalbunnyeircom.net (Russell Wallace) writes:
> On 14 Feb 2003 09:56:21 +0200, Kalle Olavi Niemitalo <···@iki.fi>
> wrote:
>
> >··@vorpalbunnyeircom.net (Russell Wallace) writes:
> >
> >> But does it? sizeof returns a value in units of char; the standard
> >> says nothing about char having to be 8 bits, or having to have any
> >> limit to how large a number it can store, IIRC.
> >
> ><limits.h> must define UCHAR_MAX as that limit. The standard
> >requires all implementations to provide this header and macro;
> >if you don't have a limit then you can't implement the standard.
>
> The standard says limits.h must define UCHAR_MAX, and that attempting
> to store x in an unsigned char, for all x <= UCHAR_MAX, must work
> correctly.
>
> However, correct me if I'm wrong, but it doesn't say anything
> whatsoever about what happens if you attempt to store x >= UCHAR_MAX
> in an unsigned char.
Yes it does:
# 6.3.1.3 Signed and unsigned integers
#
# 1 When a value with integer type is converted to another integer
# type other than _Bool,if the value can be represented by the new
# type, it is unchanged.
#
# 2 Otherwise, if the new type is unsigned, the value is converted
# by repeatedly adding or subtracting one more than the maximum
# value that can be represented in the new type until the value is
# in the range of the new type.
Regards,
--
Nils G�sche
Ask not for whom the <CONTROL-G> tolls.
PGP key ID #xD26EF2A0
On 15 Feb 2003 19:46:02 +0100, Nils Goesche <···@cartan.de> wrote:
>··@vorpalbunnyeircom.net (Russell Wallace) writes:
>> However, correct me if I'm wrong, but it doesn't say anything
>> whatsoever about what happens if you attempt to store x >= UCHAR_MAX
>> in an unsigned char.
>
>Yes it does:
Oh, okay.
Hmm... *thinks*
Hang on, though. UCHAR_MAX isn't a primitive, it's defined in a
standard header file.
Now the standard header files also define things like file access; if
you allow that, C would seem to be Turing complete. The question at
hand is whether it's Turing complete _minus_ the standard libraries.
But omit those and you also omit UCHAR_MAX :)
--
"Mercy to the guilty is treachery to the innocent."
Remove killer rodent from address to reply.
http://www.esatclear.ie/~rwallace
On 8288 day of my life Erann Gat wrote:
> In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
> (Russell Wallace) wrote:
>
> > >Turing-completeness is pretty much entirely a function of how much memory
> > >you can address. If you can (in principle) address an infinite amount of
> > >memory then you're (almost certainly) Turing complete, otherwise you're
> > >not. C, for example, stripped of its libraries, is not Turing-complete
> > >(because pointers are defined to be of fixed size).
> >
> > Are they? sizeof(x) is presumably required to return a finite number
> > for all x, but does that necessary imply x must be restricted to a
> > fixed number of bits?
>
> No it doesn't, but you've left out an important fact: you can apply sizeof
> to types, and in particular to pointer types, and that has to return a
> finite number too. *That* implies that pointers are restricted to a fixed
> number of bits.
It doesn't. Let sizeof(anything) be always one, but value of every
primitive type (including char) may be any integer. What's is broken?
--
Ivan Boldyrev remove .microsoft.com from my address
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
In article <·············@elaleph.borges.uiggm.nsc.ru>, Ivan Boldyrev
<········@uiggm.nsc.ru.microsoft.com> wrote:
> On 8288 day of my life Erann Gat wrote:
> > In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
> > (Russell Wallace) wrote:
> >
> > > >Turing-completeness is pretty much entirely a function of how much memory
> > > >you can address. If you can (in principle) address an infinite amount of
> > > >memory then you're (almost certainly) Turing complete, otherwise you're
> > > >not. C, for example, stripped of its libraries, is not Turing-complete
> > > >(because pointers are defined to be of fixed size).
> > >
> > > Are they? sizeof(x) is presumably required to return a finite number
> > > for all x, but does that necessary imply x must be restricted to a
> > > fixed number of bits?
> >
> > No it doesn't, but you've left out an important fact: you can apply sizeof
> > to types, and in particular to pointer types, and that has to return a
> > finite number too. *That* implies that pointers are restricted to a fixed
> > number of bits.
>
> It doesn't. Let sizeof(anything) be always one, but value of every
> primitive type (including char) may be any integer. What's is broken?
OK, it's time to put this one to bed.
Turns out that sizeof returns the size of the object IN BYTES. (On top of
that, sizeof(char) has to be 1. Astonishing. They actually built this
brokenness into the standard.)
Now, enough of this silliness.
E.
···@jpl.nasa.gov (Erann Gat) writes:
> OK, it's time to put this one to bed.
>
> Turns out that sizeof returns the size of the object IN BYTES. (On top of
> that, sizeof(char) has to be 1. Astonishing. They actually built this
> brokenness into the standard.)
Not sure what brokenness it is you're singling out. To clarify one
issue, as I understand it, the standard defines one byte as the
sizeof(char). There's a macro CHAR_BIT which lets you know how many
bits are in that byte.
--
If you want divine justice, die.
-- Nick Seldon
Brian Palmer <·······@rescomp.Stanford.EDU> writes:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > OK, it's time to put this one to bed.
> >
> > Turns out that sizeof returns the size of the object IN BYTES. (On top of
> > that, sizeof(char) has to be 1. Astonishing. They actually built this
> > brokenness into the standard.)
>
> Not sure what brokenness it is you're singling out. To clarify one
> issue, as I understand it, the standard defines one byte as the
> sizeof(char).
I've never seen this. I am not a C/C++ expert, so I am not challenging
this claim, bit it would be to my benefit to see the location in
one of the specs that defines a byte in these terms.
> There's a macro CHAR_BIT which lets you know how many
> bits are in that byte.
No, this is incorrect. As its name implies, CHAR_BIT defines the
number of bits in a char only, and says nothing about its relationship
to bytes. It is only if you make the assumption that char == byte
that you will perform the mental substitution in the definiton. After
having known C for over 25 years and making that same mistake, it has
taken me quite a while to retrain myself not to make that mental
substitution and assume that bytes are chars.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig <·····@franz.com> writes:
> Brian Palmer <·······@rescomp.Stanford.EDU> writes:
> > Not sure what brokenness it is you're singling out. To clarify one
> > issue, as I understand it, the standard defines one byte as the
> > sizeof(char).
>
> I've never seen this. I am not a C/C++ expert, so I am not challenging
> this claim, bit it would be to my benefit to see the location in
> one of the specs that defines a byte in these terms.
I don't own the final standard[0], but from a late draft version
of the C99 standard (linked to from
<http://home.tiscalinet.ch/t_wolf/tw/c/c9x_changes.html>)
,----
| 6.5.3.4 The sizeof operator
| [...]
| Semantics
| 2 The sizeof operator yields the size (in bytes) of its operand, which
| may be an expression or the parenthesized name of a type. The size is
| determined from the type of the operand. The result is an integer. If
| the type of the operand is a variable length array type, the operand
| is evaluated; otherwise, the operand is not evaluated and the result
| is an integer constant.
|
| 3 When applied to an operand that has type char, unsigned char, or
| signed char, (or a qualified version thereof) the result is 1. When
| applied to an operand that has array type, the result is the total
| number of bytes in the array.73) When applied to an operand that has
| structure or union type, the result is the total number of bytes in
| such an object, including internal and trailing padding.
`----
There are supposed to be significant differences between this draft
and the final standard, but from reading posters on comp.std.c who
/do/ have (or have written :) the final standard, I don't believe this
aspect of it has changed.
Hopefully others with access to the standard can confirm this.
Note, though, that this is byte as relevant to the C standard; it
doesn't necessarily have any relevance to bytes in the outside world.
[0] The final standard is available for only $18 from ANSI,iirc; but I
don't do enough programming in C anymore to find it justifiable for
me, given my (very) limited budget.
--
If you want divine justice, die.
-- Nick Seldon
Brian Palmer <·······@rescomp.Stanford.EDU> writes:
> Duane Rettig <·····@franz.com> writes:
>
> > Brian Palmer <·······@rescomp.Stanford.EDU> writes:
> > > Not sure what brokenness it is you're singling out. To clarify one
> > > issue, as I understand it, the standard defines one byte as the
> > > sizeof(char).
> >
> > I've never seen this. I am not a C/C++ expert, so I am not challenging
> > this claim, bit it would be to my benefit to see the location in
> > one of the specs that defines a byte in these terms.
>
> I don't own the final standard[0], but from a late draft version
> of the C99 standard (linked to from
> <http://home.tiscalinet.ch/t_wolf/tw/c/c9x_changes.html>)
>
> ,----
> | 6.5.3.4 The sizeof operator
> | [...]
> | Semantics
> | 2 The sizeof operator yields the size (in bytes) of its operand, which
> | may be an expression or the parenthesized name of a type. The size is
> | determined from the type of the operand. The result is an integer. If
> | the type of the operand is a variable length array type, the operand
> | is evaluated; otherwise, the operand is not evaluated and the result
> | is an integer constant.
> |
> | 3 When applied to an operand that has type char, unsigned char, or
> | signed char, (or a qualified version thereof) the result is 1. When
> | applied to an operand that has array type, the result is the total
> | number of bytes in the array.73) When applied to an operand that has
> | structure or union type, the result is the total number of bytes in
> | such an object, including internal and trailing padding.
> `----
Thanks for this reference.
It does indeed look like the C people have switched from the char-oriented
basis to an octet-oriented basis (though it is unfortunate that they
used the less-specific term "byte" instead of the more-specific and
completely defined term "octet". I would have guessed that the reason
to do this was to allow multi-octet character systems to be represented
without changing the sizeof(int) value for a given width. But given
the constraint that sizeof(char) must be 1, I now share Erann's
confusion, regarding the motivation.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
From: Nils Goesche
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <lyd6luit9g.fsf@cartan.de>
Duane Rettig <·····@franz.com> writes:
> Brian Palmer <·······@rescomp.Stanford.EDU> writes:
>
> > | 6.5.3.4 The sizeof operator
> > | [...]
> > | Semantics
> > | 2 The sizeof operator yields the size (in bytes) of its operand,
> > | which may be an expression or the parenthesized name of a
> > | type. The size is determined from the type of the operand. The
> > | result is an integer. If the type of the operand is a variable
> > | length array type, the operand is evaluated; otherwise, the
> > | operand is not evaluated and the result is an integer constant.
> > |
> > | 3 When applied to an operand that has type char, unsigned char,
> > | or signed char, (or a qualified version thereof) the result is
> > | 1. When applied to an operand that has array type, the result is
> > | the total number of bytes in the array.73) When applied to an
> > | operand that has structure or union type, the result is the
> > | total number of bytes in such an object, including internal and
> > | trailing padding. > > `----
>
> It does indeed look like the C people have switched from the
> char-oriented basis to an octet-oriented basis (though it is
> unfortunate that they used the less-specific term "byte" instead of
> the more-specific and completely defined term "octet".
They wanted to allow for systems where one `byte� (the smallest
addressable unit of data storage) is larger than 8 bits. C Compilers
for DSP's, for instance, indeed do this: all of `char�, `unsigned
char�, `signed char�, `short� and `int� might have 16 or even 32
bits. Then there are systems where one byte has 9 bits, but I never
worked with one.
> I would have guessed that the reason to do this was to allow
> multi-octet character systems to be represented without changing the
> sizeof(int) value for a given width. But given the constraint that
> sizeof(char) must be 1, I now share Erann's confusion, regarding the
> motivation.
A `byte� is defined as
# byte
#
# addressable unit of data storage large enough to hold any member
# of the basic character set of the execution environment
Then the C standard also defines:
# character
#
# single-byte character
#
# - bit representation that fits in a byte
and
# multibyte character
#
# sequence of one or more bytes representing a member of the extended
# character set of either the source or the execution environment
#
# NOTE The extended character set is a superset of the basic character
# set.
and
# wide character
#
# bit representation that fits in an object of type wchar_t, capable
# of representing any character in the current locale
So, C does not really have anything like a real character type like
Lisp has, and this is indeed unfortunate.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
Duane Rettig wrote:
> Brian Palmer <·······@rescomp.Stanford.EDU> writes:
>
>
>>···@jpl.nasa.gov (Erann Gat) writes:
>>
>>
>>>OK, it's time to put this one to bed.
>>>
>>>Turns out that sizeof returns the size of the object IN BYTES. (On top of
>>>that, sizeof(char) has to be 1. Astonishing. They actually built this
>>>brokenness into the standard.)
>>
>>Not sure what brokenness it is you're singling out. To clarify one
>>issue, as I understand it, the standard defines one byte as the
>>sizeof(char).
>
>
> I've never seen this. I am not a C/C++ expert, so I am not challenging
> this claim, bit it would be to my benefit to see the location in
> one of the specs that defines a byte in these terms.
See sections 3.6, 3.7.1, 6.2.5 and 6.3.5.4 in ISO/IEC 9899:1999 (C99).
>
>
>>There's a macro CHAR_BIT which lets you know how many
>>bits are in that byte.
>
>
> No, this is incorrect. As its name implies, CHAR_BIT defines the
> number of bits in a char only,
No, this is incorrect. CHAR_BIT is not related to chars at all except
by coincidence. It is explicitly defined as the number of bits in a
byte.
> and says nothing about its relationship
> to bytes.
An unsigned char is defined to be one byte, have no padding bits and
have CHAR_BIT bits. In addition sizeof(char) == sizeof(unsigned char).
See section 6.2.6.2.
Draw your own conclusion.
--
Thomas.
Duane Rettig <·····@franz.com> writes:
> Brian Palmer <·······@rescomp.Stanford.EDU> writes:
>
> > ···@jpl.nasa.gov (Erann Gat) writes:
> >
> > > OK, it's time to put this one to bed.
> > >
> > > Turns out that sizeof returns the size of the object IN BYTES. (On top of
> > > that, sizeof(char) has to be 1. Astonishing. They actually built this
> > > brokenness into the standard.)
> >
> > Not sure what brokenness it is you're singling out. To clarify one
> > issue, as I understand it, the standard defines one byte as the
> > sizeof(char).
>
> I've never seen this. I am not a C/C++ expert, so I am not challenging
> this claim, bit it would be to my benefit to see the location in
> one of the specs that defines a byte in these terms.
>
> > There's a macro CHAR_BIT which lets you know how many
> > bits are in that byte.
>
> No, this is incorrect. As its name implies, CHAR_BIT defines the
> number of bits in a char only, and says nothing about its relationship
> to bytes. It is only if you make the assumption that char == byte
> that you will perform the mental substitution in the definiton. After
> having known C for over 25 years and making that same mistake, it has
> taken me quite a while to retrain myself not to make that mental
> substitution and assume that bytes are chars.
There's no notion of byte in C.
sizeof returns a number in units of sizeof(char) == 1 by definition.
Hence the need for a "compliant" C compiler to provide a source file
for a pre-processor where a macro named CHAR_BIT gives the number of
bits in a char.
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
There is a fault in reality. Do not adjust your minds. -- Salman Rushdie
Thomas Stegen <·······@cis.strath.ac.uk> writes:
> Pascal Bourguignon wrote:
>
> > There's no notion of byte in C.
>
> You are wrong. See one of my other posts.
Though I think it still is standards-compliant to have a byte that is
not an octet and thus has CHAR_BITS != 8. Isn't it?
//Ingvar
--
Sysadmin is brave
Machine is running for now
Backup on Friday
Ingvar Mattsson <······@cathouse.bofh.se> writes:
> Though I think it still is standards-compliant to have a byte that is
> not an octet and thus has CHAR_BITS != 8. Isn't it?
It depends at which standard you look. IIRC, POSIX recently switched
to the "byte is octet" doctrine.
Ingvar Mattsson wrote:
>
> Though I think it still is standards-compliant to have a byte that is
> not an octet and thus has CHAR_BITS != 8. Isn't it?
The only requirement in ISO C is that CHAR_BIT >= 8.
--
Thomas.
From: Friedrich Dominicus
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <874r76atm7.fsf@fbigm.here>
Duane Rettig <·····@franz.com> writes:
> Brian Palmer <·······@rescomp.Stanford.EDU> writes:
>
> > ···@jpl.nasa.gov (Erann Gat) writes:
> >
> > > OK, it's time to put this one to bed.
> > >
> > > Turns out that sizeof returns the size of the object IN BYTES. (On top of
> > > that, sizeof(char) has to be 1. Astonishing. They actually built this
> > > brokenness into the standard.)
> >
> > Not sure what brokenness it is you're singling out. To clarify one
> > issue, as I understand it, the standard defines one byte as the
> > sizeof(char).
>
> I've never seen this. I am not a C/C++ expert, so I am not challenging
> this claim, bit it would be to my benefit to see the location in
> one of the specs that defines a byte in these terms.
Well the original comment is not valid. The thing which is defined is
that sizeof char == 1 (6.5.3.4 sentence 3)
Regards
Friedrich
From: Nils Goesche
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ly3cmr7y6w.fsf@cartan.de>
Brian Palmer <·······@rescomp.Stanford.EDU> writes:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > OK, it's time to put this one to bed.
> >
> > Turns out that sizeof returns the size of the object IN BYTES.
> > (On top of that, sizeof(char) has to be 1. Astonishing. They
> > actually built this brokenness into the standard.)
>
> Not sure what brokenness it is you're singling out. To clarify one
> issue, as I understand it, the standard defines one byte as the
> sizeof(char). There's a macro CHAR_BIT which lets you know how many
> bits are in that byte.
The problem is that characters are regarded as small integers (the
smallest, in fact!) and nothing else. Most of the text processing
code you write in, say, Common Lisp will work without change with,
say, Unicode, too, mainly because you have a truly seperate character
type (that can be larger than one byte). Sure, there is wchar_t in C,
but it isn't exactly well integrated into the language, and most
people (in the West) don't use it anyway. Try to change your Linux
installation to use UTF-8 throughout and you'll see what I mean.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
Nils Goesche <······@cartan.de> writes:
> Brian Palmer <·······@rescomp.Stanford.EDU> writes:
>
> > ···@jpl.nasa.gov (Erann Gat) writes:
> >
> > > OK, it's time to put this one to bed.
> > >
> > > Turns out that sizeof returns the size of the object IN BYTES.
> > > (On top of that, sizeof(char) has to be 1. Astonishing. They
> > > actually built this brokenness into the standard.)
> >
> > Not sure what brokenness it is you're singling out. To clarify one
> > issue, as I understand it, the standard defines one byte as the
> > sizeof(char). There's a macro CHAR_BIT which lets you know how many
> > bits are in that byte.
>
> The problem is that characters are regarded as small integers (the
> smallest, in fact!) and nothing else. Most of the text processing
> code you write in, say, Common Lisp will work without change with,
> say, Unicode, too, mainly because you have a truly seperate character
> type (that can be larger than one byte). Sure, there is wchar_t in C,
> but it isn't exactly well integrated into the language, and most
> people (in the West) don't use it anyway. Try to change your Linux
> installation to use UTF-8 throughout and you'll see what I mean.
Try UTF-16 !
> Regards,
> --
> Nils G�sche
> "Don't ask for whom the <CTRL-G> tolls."
>
> PGP key ID 0x0655CFA0
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
There is a fault in reality. Do not adjust your minds. -- Salman Rushdie
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·············@elaleph.borges.uiggm.nsc.ru>, Ivan Boldyrev
> <········@uiggm.nsc.ru.microsoft.com> wrote:
>
> > On 8288 day of my life Erann Gat wrote:
> > > In article <··················@news.eircom.net>, ··@vorpalbunnyeircom.net
> > > (Russell Wallace) wrote:
> > >
> > > > >Turing-completeness is pretty much entirely a function of how much memory
> > > > >you can address. If you can (in principle) address an infinite amount of
> > > > >memory then you're (almost certainly) Turing complete, otherwise you're
> > > > >not. C, for example, stripped of its libraries, is not Turing-complete
> > > > >(because pointers are defined to be of fixed size).
> > > >
> > > > Are they? sizeof(x) is presumably required to return a finite number
> > > > for all x, but does that necessary imply x must be restricted to a
> > > > fixed number of bits?
> > >
> > > No it doesn't, but you've left out an important fact: you can apply sizeof
> > > to types, and in particular to pointer types, and that has to return a
> > > finite number too. *That* implies that pointers are restricted to a fixed
> > > number of bits.
> >
> > It doesn't. Let sizeof(anything) be always one, but value of every
> > primitive type (including char) may be any integer. What's is broken?
>
> OK, it's time to put this one to bed.
It has insomnia. It just can't go to sleep.
> Turns out that sizeof returns the size of the object IN BYTES. (On top of
> that, sizeof(char) has to be 1. Astonishing. They actually built this
> brokenness into the standard.)
The reason it looks silly to you is that you're being caught in the
trap of assuming that char == byte. sizeof returns sizes in terms
of chars, not bytes. Thus, the definition that sizeof(char) => 1
becomes obvvious, not astonishing.
> Now, enough of this silliness.
The silliness is trying to map 25-year-old concepts (that a byte is
of variable size, and a character is (more likely) a fixed size) into
the modern concept that a byte is a fixed size (octet) and a character
is now more varying in its size.
You'll see this confusion in various C/C++ tutorials that float around,
but I doubt you'll see sizeof ever defined in an other terms than char
in the actual specs. C/C++ hardly even mentions bytes, if at all.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
> sizeof returns sizes in terms of chars, not bytes.
Not according to K&R, second edition. It says (several times) that sizeof
returns the size in bytes. And furthermore, sizeof(char) must be 1.
E.
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
>
> > sizeof returns sizes in terms of chars, not bytes.
>
> Not according to K&R, second edition. It says (several times) that sizeof
> returns the size in bytes. And furthermore, sizeof(char) must be 1.
Interesting. What date is on your second-edition?
I don't have my first-edition K&R handy, but I happened to have
the first edition Stroustrop nearby, and it takes great lengths
to define sizeof in terms of a char, and then to talk about
chars as "(typically an 8-bit byte)". There seems to have been
a change in semantics that has perhaps taken us old-timers (and
at least this old-timer) unawares.
I now share your confusion about the constraints. It's good that
I don't make my living out of C/C++ ... :-)
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
<·····@franz.com> wrote:
>···@jpl.nasa.gov (Erann Gat) writes:
>> Not according to K&R, second edition. It says (several times) that sizeof
>> returns the size in bytes. And furthermore, sizeof(char) must be 1.
>
>Interesting. What date is on your second-edition?
>
>I don't have my first-edition K&R handy, but I happened to have
>the first edition Stroustrop nearby, and it takes great lengths
>to define sizeof in terms of a char, and then to talk about
>chars as "(typically an 8-bit byte)".
K&R1 also defines sizeof in terms of bytes. From Appendix A, section
7.2:
The sizeof operator yields the size, in bytes, of its operand. (A
byte is undefined by the language except in terms of the value of
sizeof. However, in all existing implementations a byte is the space
required to hold a char.)
--
Juho Snellman
From: Friedrich Dominicus
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <87wuk29exa.fsf@fbigm.here>
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
>
> > sizeof returns sizes in terms of chars, not bytes.
>
> Not according to K&R, second edition. It says (several times) that sizeof
> returns the size in bytes. And furthermore, sizeof(char) must be 1.
K&R is not the Standard! The wording was cited here.
Regards
Friedrich
Friedrich Dominicus <·····@q-software-solutions.com> writes:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
> >
> > > sizeof returns sizes in terms of chars, not bytes.
> >
> > Not according to K&R, second edition. It says (several
> > times) that sizeof returns the size in bytes. And
> > furthermore, sizeof(char) must be 1.
> K&R is not the Standard! The wording was cited here.
Once upon a time, K&R /was/ the ``standard��. And I would find
it quite interesting if K&R changed their wording that way.
Regards,
--
Nils G�sche
Ask not for whom the <CONTROL-G> tolls.
PGP key ID #xD26EF2A0
Duane Rettig wrote:
>
> The reason it looks silly to you is that you're being caught in the
> trap of assuming that char == byte. sizeof returns sizes in terms
> of chars, not bytes. Thus, the definition that sizeof(char) => 1
> becomes obvvious, not astonishing.
This sounds like a wild guess to me. It is also a wrong guess.
The wording in the standard is quite clear.
> C/C++ hardly even mentions bytes, if at all.
More guesswork I see.
--
Thomas.
Thomas Stegen <·······@cis.strath.ac.uk> writes:
> Duane Rettig wrote:
> > The reason it looks silly to you is that you're being caught in the
>
> > trap of assuming that char == byte. sizeof returns sizes in terms
> > of chars, not bytes. Thus, the definition that sizeof(char) => 1
> > becomes obvvious, not astonishing.
>
> This sounds like a wild guess to me. It is also a wrong guess.
> The wording in the standard is quite clear.
>
> > C/C++ hardly even mentions bytes, if at all.
>
> More guesswork I see.
No, not guesswork, just old specs. Googling for sizeof and CHAR_BITS
yielded many items of wildly differing opinions, including
these which looked more correct than others (and which might have
been correct at one time):
http://tigcc.ticalc.org/doc/limits.html
and
http://www.iplusplus.com/CppRef/Sizeof.html
Also, The original Stroustrope C++ book and (from my memory) the
original K&R C book took great pains _not_ to define a byte. That's
likely where the _name_ CHAR_BITS came from, anyway.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig wrote:
> sizeof returns sizes in terms of chars, not bytes.
The C++-ISO-Standard says in paragraph 5.3.3 (sizeof)
<quote>
The sizeof operator yields the number of bytes in the object
representation of its operand. [...] sizeof(char), sizeof(signed char)
and sizeof(unsigned char) are 1 [...].
</quote>
Michael
--
Michael Schuerig Failures to use one's frontal lobes
···············@acm.org can result in the loss of them.
http://www.schuerig.de/michael/ --William H. Calvin
On 8289 day of my life Erann Gat wrote:
> In article <·············@elaleph.borges.uiggm.nsc.ru>, Ivan Boldyrev
> <········@uiggm.nsc.ru.microsoft.com> wrote:
> > It doesn't. Let sizeof(anything) be always one, but value of every
> > primitive type (including char) may be any integer. What's is broken?
>
> OK, it's time to put this one to bed.
>
> Turns out that sizeof returns the size of the object IN BYTES.
But standard doesn't define what byte is. :) AFAIR, bytes are not
mentioned in standard, but sizeof returns size in chars.
> (On top of that, sizeof(char) has to be 1. Astonishing.
And sizeof(char) is 1. What's wrong?
> They actually built this brokenness into the standard.)
--
Ivan Boldyrev remove .microsoft.com from my address
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
Outlook has performed an illegal operation and will be shut down.
If the problem persists, contact the program vendor.
Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> writes:
> On 8289 day of my life Erann Gat wrote:
> > In article <·············@elaleph.borges.uiggm.nsc.ru>, Ivan Boldyrev
> > <········@uiggm.nsc.ru.microsoft.com> wrote:
>
> > > It doesn't. Let sizeof(anything) be always one, but value
> > > of every primitive type (including char) may be any
> > > integer. What's is broken?
> >
> > OK, it's time to put this one to bed.
> >
> > Turns out that sizeof returns the size of the object IN BYTES.
>
> But standard doesn't define what byte is. :)
Yes it does (more or less). I pasted its definition directly
from the C standard.
> AFAIR, bytes are not mentioned in standard, but sizeof returns
> size in chars.
Your memory is wrong. It mentions bytes all over the place.
Regards,
--
Nils G�sche
Ask not for whom the <CONTROL-G> tolls.
PGP key ID #xD26EF2A0
In article <···············@cley.com>, Tim Bradshaw <···@cley.com> wrote:
>Isn't this kind of thing rather similar to the sense that vi turns out
>to be Turing complete? It's an interesting thing, but it *doesn't*
>mean you'd want to write code in it, or that you usefully can
25 years ago someone might have said the same thing about TECO. And if
people had listened to them, we wouldn't have EMACS.
Just about everyone considered TECO a horrible language to program in (it
looked even more like line noise than APL and C), but the benefit of
building applications on top of an editor substrate made the struggle worth
it.
--
Barry Margolin, ······@genuity.com
Genuity Managed Services, 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: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey3hebkkm9m.fsf@cley.com>
* Barry Margolin wrote:
> 25 years ago someone might have said the same thing about TECO. And if
> people had listened to them, we wouldn't have EMACS.
I think this depends on the context. If there is a system which is
barely adequate (but adequate) to a task, and it's the *only*
available system, then it's interesting that it is adequate. If there
is a system which is barely adequate, but there are also 10 others
which are much more than barely adequate, then it really is not
interesting in the same way[1].
(In any case, in the C++ case I think the problem is that it *isn't*
really adequate, because it doesn't have the runtime support you might
want?)
--tim
Footnotes:
[1] It may still be interesting for lots of other reasons: I'm
interested in accurate mechanical (or electromechanical) clocks,
but that's not because I think they are a good solution for
getting an accurate measure of time.
Barry Margolin <······@genuity.net> writes:
> Just about everyone considered TECO a horrible language to program
> in (it looked even more like line noise than APL and C), but the
> benefit of building applications on top of an editor substrate made
> the struggle worth it.
I guess I was in the minority. I found it lots of fun to program in.
It was quirky, to be sure, but it had way better facilities available
than some alternatives. It definitely favored programmers with a sense
of humor, though. ;)
The comparison to line noise, which I myself have made, is
superficial, like complaining about Lisp's parens. APL got past that
and I think so did Teco. APL and Teco shared the property that a
single character could invoke great power, so it was very terse and
often idiom-ridden. Learning to program it well was learning idioms,
but ITS Teco overcame this by having long-named q-registers, which led
to a fair deal of abstraction that was absent in conventional DEC
Teco, and helped the writing of large libraries. Oddly, though called
a macro language, Teco did not usually rewrite itself during normal
execution. The normal language it executed was a pretty fixed syntax,
since there was no macro preprocessor (macros were more akin to
cons/eval than to defmacro/macroexpand). But its native syntax really
did grow on you and combined startlingly well into things that gave the
look of multi-character commands, even though everything really was
single character dispatch at the base level.
But I do agree with Barry's remark about the ends justifying the means.
In the spirit of multiple inheritance, I'd class Teco as being in the
family of HyperTalk and PostScript and Visual Basic of having a strong
library bias toward an end user application built-in, such that it didn't
take much notation to get seriously interesting results to come out. The
engine was predisposed to do a specific task, and so only had to be coaxed
slightly in style to do that task. In that sense, it was just front end
customization for an interesting and useful application.
Emacs has carried this tradition forward, offering a powerful text editor
that just has to be nudged slightly into doing its thing by front end
Lisp code. It's surprising we don't see more of that--people taking
applications like existing web servers and just grafting syntax layers
on top. One can argue that CL is too big for that, but that's bogus.
CL was always intended to be subsetted. It's a shame Emacs didn't start
the tradition, but at the time, Stallman was seriously anti-lexical-scope
and was sure that CL had gone against the way of object-oriented programming
by eschewing the more traditional every-variable-is-a-special-variable
mentality of Maclisp and earlier dialects. (I assume he's changed now since
he's advocating or accepting Guile. Too bad he didn't see the light earlier.
I had specifically pled with him to go with a CL-compatible subset and he
refused...)
We do a lot of working back from Lisp to get other applications, of course.
And there's nothing wrong with that. But Lisp really excels at the control
end, and it's pretty boring playing macho "I can do that too" games with
getting Lisp to uninterestingly recreate what has already been done with
other languages and other applications at the low level.
Sorry for rambling... All just my personal opinion. Maybe even a bit off
topic--I've not been following this whole thread.
On Tue, 04 Feb 2003 15:50:04 GMT, Barry Margolin <······@genuity.net>
wrote:
> In article <···············@cley.com>, Tim Bradshaw <···@cley.com> wrote:
> >Isn't this kind of thing rather similar to the sense that vi turns out
> >to be Turing complete? It's an interesting thing, but it *doesn't*
> >mean you'd want to write code in it, or that you usefully can
>
> 25 years ago someone might have said the same thing about TECO. And if
> people had listened to them, we wouldn't have EMACS.
Do you mean that C++ will have some of Lisp's features in 25 years? :)
Paolo
--
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://www.paoloamoroso.it/ency/README
From: Patrick O'Donnell
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <rtk7gel3ko.fsf@ascent.com>
Barry Margolin <······@genuity.net> writes:
> Just about everyone considered TECO a horrible language to program
> in ...
Oh, I don't know. I recall that I rather enjoyed it. (Now that
you've jogged my memory, I wonder if I can find that dart scorekeeper
program I once wrote -- then I wonder if I can remember enough TECO to
read it.)
- Pat
Patrick O'Donnell <···@ascent.com> wrote:
+---------------
| Barry Margolin <······@genuity.net> writes:
| > Just about everyone considered TECO a horrible language to program
| > in ...
|
| Oh, I don't know. I recall that I rather enjoyed it. (Now that
| you've jogged my memory, I wonder if I can find that dart scorekeeper
| program I once wrote -- then I wonder if I can remember enough TECO to
| read it.)
+---------------
I wrote a snail mail list manager with it circa 1971. You know, one of
those awful things that you hand a file of names/addresses and a file
with a template letter to send, where the latter looks like this:
HONORIFIC FIRST LAST ; Honorific=Mr./Mrs./Miss/Ms./The Honorable/&c
ADDR1
ADDR2
CITY, STATE ZIP
Dear SALUTATION, ; Sir/Madam/Senator/Congressman
We here at D.C.A. would like to...
And you get the template filled in and a letter printed for each person.
TECO was quite adequate for such miscellaneous "scripting"...
-Rob
-----
Rob Warnock, PP-ASEL-IA <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Tim Bradshaw <···@cley.com> wrote in message news:<···············@cley.com>...
> * Pascal Costanza wrote:
>
> > I have just checked out the book on "Generative Programming"
> > again. Here is a quote: "Surprisingly, templates together with a
> > number of other C++ features constitute a Turing-complete,
> > compile-time sublanguage of C++." The chapter then proceeds with
> > details on how to implement control and data structures on top of
> > these features.
>
> Isn't this kind of thing rather similar to the sense that vi turns out
> to be Turing complete? It's an interesting thing, but it *doesn't*
I think more telling is that in the long-running elaboration of C++,
the compiler itself became complicated enough that it supported
Turing-complete computation without it being explicitly required by
the language definition.
I suppose the advent of template meta-programming has caused C++
compiler vendors to ensure that the virtual Turing machine is
relatively robust. Perhaps it is only a matter of time before it is
expected that C++ compilers come with GUI-based debuggers for this
virtual machine?
Joseph Oswald wrote:
> I suppose the advent of template meta-programming has caused C++
> compiler vendors to ensure that the virtual Turing machine is
> relatively robust. Perhaps it is only a matter of time before it is
> expected that C++ compilers come with GUI-based debuggers for this
> virtual machine?
A broken design cannot be fixed by adding debugging facilities. But
yeah, probably they will sell this as an improvement...
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
···@jpl.nasa.gov (Erann Gat) writes:
> But this is really beside the point. What really matters is that
> templates don't really allow you to do any kind of syntax abstraction.
> For example, you couldn't implement something like the LOOP macro as a
> template except by encoding all the keywords as numbers, which would
> rather defeat the purpose IMO.
Have you had a look at:
http://www.prakinf.tu-ilmenau.de/~czarn/meta/metalisp.cpp ?
:)
alex
Hello!
Alexander Schmolck <··········@gmx.net> wrote:
>[...]
>Have you had a look at:
>http://www.prakinf.tu-ilmenau.de/~czarn/meta/metalisp.cpp ?
Isn't that a perfect example of Greenspun's tenth? *g*
In fact, you COULD also model destructive modification, using
the usual "tricks" of denotational semantics :-)
The code will just become even more cumbersome than it is anyway.
Kind regards,
Hannah.
In article <···············@black132.ex.ac.uk>, Alexander Schmolck
<··········@gmx.net> wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > But this is really beside the point. What really matters is that
> > templates don't really allow you to do any kind of syntax abstraction.
> > For example, you couldn't implement something like the LOOP macro as a
> > template except by encoding all the keywords as numbers, which would
> > rather defeat the purpose IMO.
>
> Have you had a look at:
>
> http://www.prakinf.tu-ilmenau.de/~czarn/meta/metalisp.cpp ?
>
> :)
>
> alex
Oh my god! The power of Lisp 1.5 with the beauty and elegance of C++!
The horror!
E.
···@jpl.nasa.gov (Erann Gat) writes:
> In article <···············@black132.ex.ac.uk>, Alexander Schmolck
> <··········@gmx.net> wrote:
> > Have you had a look at:
> >
> > http://www.prakinf.tu-ilmenau.de/~czarn/meta/metalisp.cpp ?
> >
> > :)
From the file:
// METALISP.CPP contains a rudimentary LISP implementation as a template
// metaprogram. All the basic primitives and some convenience functions
// are provided. You can use it to write functional programs interpreted by
// the compiler at compile time.
Which is supposed to be good for what? Can that horrid thing, with
which they insult poor old lisp, be used for anything but to fill a
few pages of a bad book?
> Oh my god! The power of Lisp 1.5 with the beauty and elegance of C++!
> The horror!
Nah, not even that. From the file:
// The functions which are not currently not available are documented
// as comments. Many of them cannot be implemented, e.g. destructive
// list functions or input during compile-time.
I think lisp 1.5 had these features. But that's not enough. More
things which aren't implemented:
// EVAL
// APPLY
// QUOTE
// LAMBDA
// MAPCAR
A lisp without these. Yeah, right.
Mario.
From: Jeff Caldwell
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <3E3F230D.9050309@yahoo.com>
Good link on the subject, thanks Pascal. The following link does give an
example of a template class that contains itself as a
differently-specialized subset. Apparently this capability of C++
templates was discovered by Erwin Unruh when he accidently got compile
warnings which listed prime numbers. The link demonstrates a
compile-time pow<x,y> function which calculates a result as x *
myclass<x,y-1> along with a specialized myclass<x,0> to terminate the
recursion.
http://osl.iu.edu/~tveldhui/papers/pepm99/
Mandatory Lisp content: When I can get 'em, I prefer Lisp macros over
C++ templates.
Jeff
Pascal Costanza wrote:
...
> The following URL seems to provide a nice introduction. (I have just
> skipped it briefly.)
>
> http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html
>
> It doesn't seem to provide an example of a class that is subclass of
> itself
...
In article <············@f1node01.rhrz.uni-bonn.de>,
Pascal Costanza <········@web.de> wrote:
>Steve Tu wrote:
>> What other languages, besides Lisp, have Lisp-level macros? I've
>> searched faqs and google, but have been unable to derive the magic
>> incantation.
>
>AFAIK, templates in C++ are used for similar purposes like Lisp macros,
>and they are Turing-complete at compile-time.
Really? So you can call open(), printf(), etc. at compile-time from a
template? Can you show a simple example?
--
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.
Barry Margolin <······@genuity.net> wrote in message news:<················@paloalto-snr1.gtei.net>...
> In article <············@f1node01.rhrz.uni-bonn.de>,
> Pascal Costanza <········@web.de> wrote:
> >Steve Tu wrote:
> >> What other languages, besides Lisp, have Lisp-level macros? I've
> >> searched faqs and google, but have been unable to derive the magic
> >> incantation.
> >
> >AFAIK, templates in C++ are used for similar purposes like Lisp macros,
> >and they are Turing-complete at compile-time.
>
> Really? So you can call open(), printf(), etc. at compile-time from a
> template? Can you show a simple example?
That isn't what Turing completeness means.
Turing completeness means: ``I know it sucks, because it would take
reams of impossible code executing over hundreds of years to make it
do some of the things you are asking for, using representational
contortions that would obfuscate the simplest of data structures
beyond recognition, and I know that some things are squarely out of
reach simply because the suitable connections to the environment don't
exist, but there is a Big Name in Computer Science that I can pull out
of the closet (so to speak), in hopes that nobody will see through the
smoke I'm blowing.''
:)
Barry Margolin wrote:
> In article <············@f1node01.rhrz.uni-bonn.de>,
> Pascal Costanza <········@web.de> wrote:
>
>>Steve Tu wrote:
>>
>>>What other languages, besides Lisp, have Lisp-level macros? I've
>>>searched faqs and google, but have been unable to derive the magic
>>>incantation.
>>
>>AFAIK, templates in C++ are used for similar purposes like Lisp macros,
>>and they are Turing-complete at compile-time.
>
>
> Really? So you can call open(), printf(), etc. at compile-time from a
> template?
I don't know, but probably not. Templates in C++ are Turing complete to
the extent that a class can be a subclass of another variant of itself.
So essentially you have recursion on the class level and this allows you
to generate new classes at compile-time, with features that depend on
the actual template parameters. I don't think this expands to being able
to do library calls. But I am not sure - I am not an expert in template
meta-programming.
> Can you show a simple example?
Hence, no I can't.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
<········@web.de> wrote:
> Templates in C++ are Turing complete to
> the extent that a class can be a subclass of another variant of itself.
Huh? I'm sorry, but that doesn't make any sense at all. What does
"another variant" mean in this context? And how can a class be a subclass
of ... itself?
E.
Erann Gat wrote:
> In article <············@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <········@web.de> wrote:
>
>> Templates in C++ are Turing complete to
>> the extent that a class can be a subclass of another variant of
>> itself.
>
> Huh? I'm sorry, but that doesn't make any sense at all. What does
> "another variant" mean in this context?
I think what Pascal means is that, given a C++ template class, you can
create multiple distinct classes from the template, and each class instance
could be considered a "variant" of the template. For example, given a class
template:
template<typename T>
class C
{};
Then class instantiations can be created by providing a template parameter:
C<int> c1;
C<double> c2;
There is no runtime structural relationship between c1 and c2, as the two
template instantiations using int and double create two distinct classes.
> And how can a class be a
> subclass of ... itself?
It can't. There is, however, an idiom in C++ called the "Curiously Recurring
Template Pattern", where a class is derived from a templated class, passing
itself as the parameter to the base template...
class C : public base<C>
{};
That's about the nearest thing I can think of to what Pascal said.
As for Turing completeness... that's correct, but it's the usual silliness.
You can implement loop and branch constructs, but only with severe
contortions of the language, which kind of provides C++ with a tortured
sub-dialect. For example, here's the canonical introduction to C++
compile-time programming, factorial computation:
//--------------------------------------------------------------------------
template<int n>
struct factorial
{
enum { RET = n * factorial<n-1>::RET };
};
template<>
struct factorial<1>
{
enum { RET = 1 };
};
template<typename T>
class C
{
};
int main()
{
int fact10 = factorial<10>::RET;
}
//--------------------------------------------------------------------------
factorial is a templated class taking an int as a parameter. The enumeration
recursively instantiates the factorial template, and there is a
"specialisation" for the template (for n == 1) which terminates the
recursion. The result of the computation is stored in "RET". Since the
intermediate instantiations of the factorial template are never used to
create objects, they are all thrown away during the compilation process, so
there is no resultant bloat. Incidentally, the recursion depth is
implementation-dependent.
Of course, the Turing completeness argument can be taken further, and a
recent book "Modern C++ Design" shows some of the things that can be
achieved. Templates can be used in conjunction with the C++ "typedef"
feature to build up something called "typelists", which are equivalent to
Lisp's conses, but containing C++ types. Given a templated class like this:
template<typename T, typename U>
struct cons
{
typedef T Head;
typedef U Tail;
};
and a "nil" class:
struct nil {};
A typelist can then be created...
typedef cons<char, cons<int, cons<long, nil> > > signed_integrals;
Further mechanisms can be created, using recursion techniques similar to the
factorial example. In conjunction with multiple inheritance, typelists can
be used to "explode" hierarchies so that a most-derived class ends up
composing all the types within a typelist in a manner analogous to
"component assembly". Modern C++ Design demonstrates how these techniques
can be combined to create compile-time versions of GoF Design Patterns such
as Command, Singleton, Factory and Visitor. Yuck!
My own experiments with these mechanisms have really got me
worried that so many people have become so intoxicated with the
ingeniousness of it all that they don't realise how horrific it really is.
The whole thing really represents a large-scale attempt to shuffle the
static typing out of the way, but the static typing bites sooner or later,
and you'll have written a lot of very nasty code by the time you realise it.
:-)
>
> E.
Jon.
In article <···········@cvis05.marconicomms.com>, "Jon Bills"
<·········@hotmail.com> wrote:
> As for Turing completeness... that's correct, but it's the usual silliness.
> You can implement loop and branch constructs, but only with severe
> contortions of the language, which kind of provides C++ with a tortured
> sub-dialect.
You need more than loop and branch to be Turing-complete. You also need
some form of dynamic memory allocation, i.e. you need CONS, or MALLOC, or
LAMBDA, or something like that. If you don't have that, you have an FSA,
not a Turing machine.
> For example, here's the canonical introduction to C++
> compile-time programming, factorial computation:
Try this on factorial<1000> and see what happens.
> Of course, the Turing completeness argument can be taken further, and a
> recent book "Modern C++ Design" shows some of the things that can be
> achieved. Templates can be used in conjunction with the C++ "typedef"
> feature to build up something called "typelists", which are equivalent to
> Lisp's conses, but containing C++ types. Given a templated class like this:
>
> template<typename T, typename U>
> struct cons
> {
> typedef T Head;
> typedef U Tail;
> };
>
> and a "nil" class:
>
> struct nil {};
>
> A typelist can then be created...
>
> typedef cons<char, cons<int, cons<long, nil> > > signed_integrals;
OK, this is indeed a Turing-complete facility, but it is completely
disjoint from the rest of C++. There is no way to leverage the
computational facilities of C++ to write code for STTTL (Stupid Template
Typedef Trick Language).
> Yuck!
Indeed.
> My own experiments with these mechanisms have really got me
> worried that so many people have become so intoxicated with the
> ingeniousness of it all that they don't realise how horrific it really is.
> The whole thing really represents a large-scale attempt to shuffle the
> static typing out of the way, but the static typing bites sooner or later,
> and you'll have written a lot of very nasty code by the time you realise it.
I think you've really hit the nail on the head here.
E.
Erann Gat wrote:
> You need more than loop and branch to be Turing-complete. You also need
> some form of dynamic memory allocation, i.e. you need CONS, or MALLOC, or
> LAMBDA, or something like that. If you don't have that, you have an FSA,
> not a Turing machine.
To be turing complete you can make do with the following:
A large array (or something similiar) and a pointer into that array.
Now you need operations to increment the pointer, decremenent the
pointer, decrement the byte at the pointer, increment the byte at the
pointer, outputting the byte at the pointer, inputting a byte and
placing it at the pointer and a way of looping.
Of course, to be properly turing complete you would need an
infinetely large array, but there fails all languages anyways.
--
Thomas.
In article <··········@nntphost.cis.strath.ac.uk>, Thomas Stegen
<·······@cis.strath.ac.uk> wrote:
> Erann Gat wrote:
> > You need more than loop and branch to be Turing-complete. You also need
> > some form of dynamic memory allocation, i.e. you need CONS, or MALLOC, or
> > LAMBDA, or something like that. If you don't have that, you have an FSA,
> > not a Turing machine.
>
> To be turing complete you can make do with the following:
>
> A large array (or something similiar) and a pointer into that array.
> Now you need operations to increment the pointer, decremenent the
> pointer, decrement the byte at the pointer, increment the byte at the
> pointer, outputting the byte at the pointer, inputting a byte and
> placing it at the pointer and a way of looping.
>
> Of course, to be properly turing complete you would need an
> infinetely large array, but there fails all languages anyways.
No. C only fails because it is tightly bound to a model of a physical
machine. C requires that you be able to take the address of any object
and have the result be a pointer, which C further requires to have a
finite number of bits. Most languages do not have these kinds of
restrictions. Thus, the language definition limits you to a finite number
of data objects.
E.
Hello!
Erann Gat <···@jpl.nasa.gov> wrote:
>In article <···········@cvis05.marconicomms.com>, "Jon Bills"
><·········@hotmail.com> wrote:
>> As for Turing completeness... that's correct, but it's the usual silliness.
>> You can implement loop and branch constructs, but only with severe
>> contortions of the language, which kind of provides C++ with a tortured
>> sub-dialect.
>You need more than loop and branch to be Turing-complete. You also need
>some form of dynamic memory allocation, i.e. you need CONS, or MALLOC, or
>LAMBDA, or something like that. If you don't have that, you have an FSA,
>not a Turing machine.
Isn't there a theorem (or conjecture) that WHILE languages are
already Turing complete?
Btw, you can model a tape as a triple (list of tape elements left
to the tape head, element under the tape head, list of elements
right to the head). And you could do that with C++'s contorted template
stuff, too, like this:
class Symbol1 {};
class Symbol2 {};
// for all the other tape symbols
class Nil {};
template <typename Head_, typename Tail_>
class Cons {
typedef Head_ Head;
typedef Head_ Car;
typedef Tail_ Tail;
typedef Tail_ Cdr;
};
template <typename Left, typename Current, typename Right>
class Tape {
typedef Left LeftElements;
typedef Current CurrentElements;
typedef Right RightElements;
};
With partial template specialization you can pattern match.
You can also recurse. That's enough for compile time simulation
of specific Turing machines, that is also universal ones.
Memory allocation? Some kind of, see above for Cons *g*
>> For example, here's the canonical introduction to C++
>> compile-time programming, factorial computation:
>Try this on factorial<1000> and see what happens.
You don't expect someone to implement something like gmp in THAT
contorted language called templates/template specializations? :-))
>[...]
>> typedef cons<char, cons<int, cons<long, nil> > > signed_integrals;
>OK, this is indeed a Turing-complete facility, but it is completely
>disjoint from the rest of C++. There is no way to leverage the
>computational facilities of C++ to write code for STTTL (Stupid Template
>Typedef Trick Language).
No, that would be too easy or called Lisp *g*
>> Yuck!
>Indeed.
<AOL/>
>[...]
Kind regards,
Hannah.
In article <············@c3po.schlund.de>, ······@schlund.de (Hannah
Schroeter) wrote:
> Isn't there a theorem (or conjecture) that WHILE languages are
> already Turing complete?
WHILE (or some equivalent) is necessary but not sufficient. In addition,
you need some way of addressing infinite storage.
E.
"Jon Bills" <·········@hotmail.com> writes:
> My own experiments with these mechanisms have really got me worried
> that so many people have become so intoxicated with the
> ingeniousness of it all that they don't realise how horrific it
> really is.
Do you not think that the stuff being done with template
meta-programming by the folks at Boost <http://www.boost.org/> is
genuinely interesting (from the POV of the C++ community, of course)?
From: Joe Marshall
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ptq99rit.fsf@ccs.neu.edu>
Pascal Costanza <········@web.de> writes:
> >>
> >> AFAIK, templates in C++ are used for similar purposes like Lisp
> >> macros, and they are Turing-complete at compile-time.
> > Barry Margolin wrote:
>
> > Really? So you can call open(), printf(), etc. at compile-time from
> > a template?
>
> I don't know, but probably not. Templates in C++ are Turing complete
> to the extent that a class can be a subclass of another variant of
> itself.
And to the extent that you are only allowed to nest the expansion 8
levels. (someone told me 16 once, but whatever)
So it is powerful like a Turing machine with an 8 cell tape. But
Turing machines are significantly easier program.
In article <············@f1node01.rhrz.uni-bonn.de>,
Pascal Costanza <········@web.de> wrote:
>Barry Margolin wrote:
>> In article <············@f1node01.rhrz.uni-bonn.de>,
>> Pascal Costanza <········@web.de> wrote:
>>
>>>Steve Tu wrote:
>>>
>>>>What other languages, besides Lisp, have Lisp-level macros? I've
>>>>searched faqs and google, but have been unable to derive the magic
>>>>incantation.
>>>
>>>AFAIK, templates in C++ are used for similar purposes like Lisp macros,
>>>and they are Turing-complete at compile-time.
>>
>>
>> Really? So you can call open(), printf(), etc. at compile-time from a
>> template?
>
>I don't know, but probably not.
The OP specifically asked about doing I/O from macros. Like I said in my
original reply, I'm not sure *why* you would want that, except perhaps when
debugging.
--
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: Tim Bradshaw
Subject: Re: Other languages with Lisp macros
Date:
Message-ID: <ey3isw1me1p.fsf@cley.com>
* Barry Margolin wrote:
> Really? So you can call open(), printf(), etc. at compile-time from a
> template? Can you show a simple example?
I don't think you can. They are Turing-complete, but they *don't*
have access to a sufficiently rich (or any) runtime (or, I suppose,
macroexpansion-time) system, so I don't think you can do all the nice
stuff you can do with Lisp macros which is at least partly because the
whole of the Lisp runtime is there, not just some `linguistic subset'.
--tim
Barry Margolin <······@genuity.net> wrote in message news:<················@paloalto-snr1.gtei.net>...
> >AFAIK, templates in C++ are used for similar purposes like Lisp macros,
> >and they are Turing-complete at compile-time.
>
> Really? So you can call open(), printf(), etc. at compile-time from a
> template? Can you show a simple example?
Simple? Of course not, it's C++.
Pascal Costanza wrote:
> Steve Tu wrote:
>
>> What other languages, besides Lisp, have Lisp-level macros? I've
>> searched faqs and google, but have been unable to derive the magic
>> incantation.
>
> Furthermore, Jonathan Bachrach is working on macro systems, for example
> for Dylan and Java, and provides good sections on related work in his
> papers. See http://www.ai.mit.edu/~jrb/
Bachrach's Dylan macros ("D-Expressions") and Java Syntactic Extender,
although not standard to either language, do indeed have Lisp-level
macros. His papers also refer to several other Java extensions. Again,
thanks.
Steve
Pascal Costanza <········@web.de> wrote in message news:<············@f1node01.rhrz.uni-bonn.de>...
> Steve Tu wrote:
> > What other languages, besides Lisp, have Lisp-level macros? I've
> > searched faqs and google, but have been unable to derive the magic
> > incantation.
>
> AFAIK, templates in C++ are used for similar purposes like Lisp macros,
> and they are Turing-complete at compile-time. You might want to look for
> "generative programming" and the book of the same name - see
Okay, let's see the C++ template equivalent of IGNORE-ERRORS. That
would be an example of a ``similar purpose'' to me.
"Steve" == Steve Tu <·@b.com> writes:
Steve> What other languages, besides Lisp, have Lisp-level macros?
Steve> I've searched faqs and google, but have been unable to derive
Steve> the magic incantation.
If you're interested in research systems, several people have implemented
Lisp-like macro systems for Java. For instance, see:
Jason Baker and Wilson C. Hsieh. ``Maya: Multiple-Dispatch Syntax
Extension in Java.'' In Proceedings of PLDI 2002.
<http://www.cs.utah.edu/flux/papers/pldi02-maya-base.html>
Eric.
--
-------------------------------------------------------------------------------
Eric Eide <·····@cs.utah.edu> . University of Utah School of Computing
http://www.cs.utah.edu/~eeide/ . +1 (801) 585-5512 voice, +1 (801) 581-5843 FAX
Steve Tu <·@b.com> writes:
> What other languages, besides Lisp, have Lisp-level macros? I've
> searched faqs and google, but have been unable to derive the magic
> incantation.
>
> Specifically, I need compile-time side-effects, not just syntax
> translation. As long as the compile-time side-effects can do things
> like file io and function calls, it should suffice. GUI stuff would
> be nice, too.
1/ What other language use the same data structures for programs and
for data?
2/ You can always use lisp (or any turing-complete language) to
generate any source file.
(defun generate-function (source-stream name arg)
(format source-stream "int ~A (int a)·@
··@
return(a+~A)··@
··@
" name arg))
(with-open-file (source "add2.c" :direction output :if-exists :override
:if-does-not-exist :create)
(generate-function source 'add2 2))
(ext:run-program "gcc" :arguments '( "-c" "-o" "add2.o" "add2.c"))
See for example the package that help generate HTML or PDF or XML or
whatever from Lisp.
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
There is a fault in reality. Do not adjust your minds. -- Salman Rushdie
Hi Steve.
There is an extension of Haskell - "Template Haskell" described at:
http://research.microsoft.com/Users/simonpj/papers/meta-haskell/
That paper discusses other meta-programming systems including Scheme and
C++.
The CVS HEAD Glasgow Haskell Compiler implements the work discussed in the
paper. Below are two modules implementing an incomplete skeleton of
printf:
=============================================
{- Main.hs -}
module Main where
-- Import our template "pr"
import Printf ( pr )
-- The splice operator $ takes the Haskell source code
-- generated at compile time by "pr" and splices it into
-- the argument of "putStrLn".
main = putStrLn ( $(pr "Hello") )
=============================================
{- Printf.hs -}
module Printf where
-- Skeletal printf from the paper.
-- It needs to be in a separate module to the one where
-- you intend to use it.
-- Import some Template Haskell syntax
import Language.Haskell.THSyntax
-- Describe a format string
data Format = D | S | L String
-- Parse a format string. This is left largely to you
-- as we are here interested in building our first ever
-- Template Haskell program and not in building printf.
parse :: String -> [Format]
parse s = [ L s ]
-- Generate Haskell source code from a parsed representation
-- of the format string. The generated code is spliced into
-- the module which calls "pr", at compile time.
gen :: [Format] -> Expr
gen [D] = [| \n -> show n |]
gen [S] = [| \s -> s |]
gen [L s] = string s
-- Here we generate the Haskell code for the splice
-- from an input format string.
pr :: String -> Expr
pr s = gen (parse s)
======================================
Cheers
Mike Thomas.
"Steve Tu" <·@b.com> wrote in message ·························@sccrnsc04...
> What other languages, besides Lisp, have Lisp-level macros? I've
> searched faqs and google, but have been unable to derive the magic
> incantation.
>
> Specifically, I need compile-time side-effects, not just syntax
> translation. As long as the compile-time side-effects can do things
> like file io and function calls, it should suffice. GUI stuff would be
> nice, too.
>
> Thanks,
> Steve
>
> sed 's/j/st/' ·········@hotmail.com
>
On Mon, 03 Feb 2003 07:32:35 +0000, Steve Tu wrote:
You coul try OpenC++. It's a compile-time MOP on top of C++.
I didn't try it very hard, but it can surely help you do some I/O or other
unfancy stuff at compile-time.
I played with it today and found it quite ugly :-)
Aur�lien.
"Steve Tu" <·@b.com> wrote in message ·························@sccrnsc04...
> What other languages, besides Lisp, have Lisp-level macros? I've
> searched faqs and google, but have been unable to derive the magic
> incantation.
>
> Specifically, I need compile-time side-effects, not just syntax
> translation. As long as the compile-time side-effects can do things
> like file io and function calls, it should suffice. GUI stuff would be
> nice, too.
This isn't any help, but I thought I'd bring it up anyway.
Back In The Day (That being mid 1987...), my first experience with anything
close to Lisp-esque macros was actually a version of BASIC.
By Lisp-esque macros, I mean the ability to transform source code during the
compile process. Real Lisp macro are much more powerful.
The BASIC was on an Alpha Micro using the Metropolis Database system. This
system used a system of what were called "GENCODEs". We were able to write
simple macros and place GENCODEs within them to create BASIC source within
the final program.
I suppose it could be called simply a more powerful pre processor, but it
was certainly more capable than any of the modern day generic preprocessors.
We typically used the GENCODEs to create structure based upon the local
database, specifically things like record structure. See, we were working
against an ISAM database, and the record layouts were coded (or GENCODEd I
should say) into the programs. Essentially, they were simple structure
parceling out memory.
One of the details of the system, for example, was that after a record was
added, all of the indexes had to be added as well. The system didn't
automatically create index entries after a record insert or update (this was
hell to work with, FYI, not a recommended practice).
So, a macro like ADDKEY REC1 would create all of the code to populate and
insert the keys to the database.
It is not clear to me today if GENCODEs were written in BASIC or not. I
think they were, but we never worked with them directly. I recall they were
unintuitive as well and not well documented. However, we did use them for
just a vast array of things in the system, and it added a great amount of
power to an otherwise lowly BASIC.
In many ways, though, it directly influenced my long term opinions on how
software should be created.
Regards,
Will Hartung
(·····@msoft.com)
On Mon, 03 Feb 2003, Steve Tu wrote:
>What other languages, besides Lisp, have Lisp-level macros? I've
>searched faqs and google, but have been unable to derive the magic
>incantation.
>
>Specifically, I need compile-time side-effects, not just syntax
>translation. As long as the compile-time side-effects can do things
>like file io and function calls, it should suffice. GUI stuff would be
>nice, too.
Probably not useful for any immediate projects, but it looks like Perl
6 is going to have this sort of macro capabilities:
http://www.perl.com/pub/a/2003/03/07/apocalypse6.html?page=9
--
If you want divine justice, die.
-- Nick Seldon