Other languages with Lisp macros
Steve Tu
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/' askj...@hotmail.com
Barry Margolin
>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, bar...@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.
Pascal Costanza
> 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
mailto:cost...@web.de Institute of Computer Science III
http://www.pascalcostanza.de Römerstr. 164, D-53117 Bonn (Germany)
Pascal Costanza
> 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?
Barry Margolin
Pascal Costanza <cost...@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?
Pascal Costanza
> In article <b1m452$lh8$1...@f1node01.rhrz.uni-bonn.de>,
> Pascal Costanza <cost...@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.
Joe Marshall
> >>
> >> 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.
Barry Margolin
Pascal Costanza <cost...@web.de> wrote:
>Barry Margolin wrote:
>> In article <b1m452$lh8$1...@f1node01.rhrz.uni-bonn.de>,
>> Pascal Costanza <cost...@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.
Tim Bradshaw
> 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
Thomas F. Burdick
> >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! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Erann Gat
> 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.
Erann Gat
<cost...@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.
Pascal Costanza
g...@jpl.nasa.gov (Erann Gat) 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, 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
Erann Gat
Costanza <cost...@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.
Steve Tu
> 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.
>
> 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
Kaz Kylheku
> In article <b1m452$lh8$1...@f1node01.rhrz.uni-bonn.de>,
> Pascal Costanza <cost...@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.''
:)
Pascal Bourguignon
> 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
Eric Eide
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 <ee...@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
Mike Thomas
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" <a...@b.com> wrote in message news:nWo%9.54416$G83.1090@sccrnsc04...
Thaddeus L Olczyk
wrote:
>In article <costanza-BC3CDE...@news.netcologne.de>, Pascal
>Costanza <cost...@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/
Jeff Caldwell
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
...
Pascal Costanza
> In article <costanza-BC3CDE...@news.netcologne.de>, Pascal
> Costanza <cost...@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.
Tim Bradshaw
> 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
Alexander Schmolck
> 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
Jon Bills
> In article <b1m6pp$4n0$1...@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <cost...@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.
Pascal Costanza
> * 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.)
Kaz Kylheku
> 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.
Joe Marshall
> 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++?
Tim Bradshaw
> (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 Lavoie
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
Pascal Costanza
Good point.
Mario S. Mommer
No. They are its features ;)
Mario.
Mario S. Mommer
> >>>>> "TB" == Tim Bradshaw <t...@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.
Barry Margolin
>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, bar...@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.
Tim Bradshaw
>> 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
Pascal Costanza
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.
Tim Bradshaw
> 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.
"Aurélien Campéas"
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.
sv0f
<tla...@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.
Matthew Danish
> 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 <mda...@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."
Hannah Schroeter
Alexander Schmolck <a.sch...@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.
Paolo Amoroso
wrote:
> In article <ey365s0...@cley.com>, Tim Bradshaw <t...@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
Kaz Kylheku
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? ;)
Tim Lavoie
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 Lavoie
sv0f> In article <87adhct...@theasylum.dyndns.org>, Tim Lavoie
sv0f> <tla...@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.
Kenny Tilton
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
Kent M Pitman
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.
Kent M Pitman
> 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.
Joe Marshall
> 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.
sv0f
k...@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
> 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
Erann Gat
<jon_...@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
olc...@interaccess.com wrote:
> On Mon, 03 Feb 2003 14:36:58 -0800, g...@jpl.nasa.gov (Erann Gat)
> wrote:
>
> >In article <costanza-BC3CDE...@news.netcologne.de>, Pascal
> >Costanza <cost...@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.
Erann Gat
<a.sch...@gmx.net> wrote:
> g...@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.
Erann Gat
<cost...@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.
Barry Watson
> 1/ What other language use the same data structures for programs and
> for data?
PROLOG
Tim Bradshaw
> 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
Pascal Costanza
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 Costanza
> In article <b1og92$ljs$1...@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <cost...@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. ;)
Mario S. Mommer
g...@jpl.nasa.gov (Erann Gat) writes:
> In article <yfsisw0...@black132.ex.ac.uk>, Alexander Schmolck
> <a.sch...@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.
Pascal Costanza
>
>
> 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
Michael Hudson
> Pascal Costanza <cost...@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
Marco Antoniotti
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
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
Erann Gat
<cost...@web.de> wrote:
> Erann Gat wrote:
> > In article <b1og92$ljs$1...@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> > <cost...@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.
Patrick O'Donnell
> Just about everyone considered TECO a horrible language to program
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
Thomas Stegen
> 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.
Kaz Kylheku
> In article <b1qt2a$tjc$1...@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <cost...@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
:)
Erann Gat
<tst...@cis.strath.ac.uk> wrote:
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.
Erann Gat
> g...@jpl.nasa.gov (Erann Gat) wrote in message
news:<gat-050203...@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.
Will Hartung
"Steve Tu" <a...@b.com> wrote in message news:nWo%9.54416$G83.1090@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
(wi...@msoft.com)
Rob Warnock
+---------------
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 <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Pascal Costanza
> 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 Costanza
>
>
> 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...
Daniel Barlow
> In article <cf333042.03020...@posting.google.com>,
> k...@ashi.footprints.net (Kaz Kylheku) wrote:
>
>> g...@jpl.nasa.gov (Erann Gat) wrote in message
> news:<gat-050203...@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
Pascal Costanza
> In article <b1qt2a$tjc$1...@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> <cost...@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
Mario S. Mommer
> > 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
Pascal Costanza
I am sorry, I don't get that. What do you mean?
Thaddeus L Olczyk
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.
Marco Antoniotti
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
Kaz Kylheku
Oh, so stretches are not permitted in discussions about Turing
completeness? News to me. :)
Mario S. Mommer
> 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.
Erann Gat
<d...@telent.net> wrote:
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.
Erann Gat
<cost...@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.
Kaz Kylheku
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?
Pascal Costanza
>>>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 Costanza
> 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.)
Erann Gat
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.
Hannah Schroeter
Erann Gat <g...@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.
Hannah Schroeter
Erann Gat <g...@jpl.nasa.gov> wrote:
>In article <b1oav8$dj...@cvis05.marconicomms.com>, "Jon Bills"
><jon_...@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.
Geoffrey Summerhayes
"Pascal Costanza" <cost...@web.de> wrote in message news:b1tmli$13de$1...@f1node01.rhrz.uni-bonn.de...
> Erann Gat wrote:
> > In article <b1qt2a$tjc$1...@f1node01.rhrz.uni-bonn.de>, Pascal Costanza
> > <cost...@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
Salvador Fandiño García
>>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
Thomas F. Burdick
> 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! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Thomas F. Burdick
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.
Geoffrey Summerhayes
"Salvador Fandiño García" <sfan...@yahoo.com> wrote in message news:3E42CAB3...@yahoo.com...
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
Erann Gat
<cost...@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.
Erann Gat
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.
Pascal Bourguignon
"Geoffrey Summerhayes" <sumNOS...@hotmail.com> writes:
> "Salvador Fandiño García" <sfan...@yahoo.com> wrote in message news:3E42CAB3...@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
Erann Gat
Schroeter) wrote:
> Hello!
Howdy.
> Erann Gat <g...@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.
Erann Gat
Summerhayes" <sumNOS...@hotmail.com> wrote:
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.