5 ms·

What does he mean when he says that it's not possible to write a C program that can write other C programs? Seems like there are counterexamples here: http://w

by ISL 13y ago

What does he mean when he says that it's not possible to write a C program that can write other C programs? Seems like there are counterexamples here: http://www.nyx.net/~gthompso/quine.htm http://www.nyx.net/~gthompso/quine.htm Furthermore, it's possible to encode another programs' code into a single print statement, thereby writing one piece of code with another. As that's trivial, I suspect he meant something else. What was it? :).

wes-exp 13y ago
I suspect "possible" here is not used in the absolute sense, but more just "it would be a total pain in the ass in C, whereas Lisp excels at it". After all, anything is "possible" with hand-written assembly code, too, but realistically speaking, it's not practical.
- gavinpc 13y ago
  I couldn't post this last night, but yeah: My ears perked up at the dual statement that although you can write a Lisp program that writes Lisp programs, nobody does it (um, macros?); and that you can't write a C program that writes a C programs (okay, maybe nobody does this, but you certainly can). I guess he means that C is not "aware" of its own constructs the way that Lisp is. Also, he said that the algebraic languages were "dying out", but that because of this self-generating ability (which nobody uses), that the future of Lisp was "open". Huh?
  - h_r 13y ago
    I understood the "open" comment to mean "open to modification and extension", independent of whether it is dying out.
Guthur 13y ago
I think you might have missed the point of the statement "programs that write programs", it goes far beyond a toy quine. You can't do it in C unless you also implement a compiler or evaluator. And even then generating any sort of reasonably complex C code with C would be highly painful to say the least. You can possibly nearly get there with C macros but I would argue it's not C writing C there, rather a text preprocessor.
- derefr 13y ago
  > You can't do it in C unless you also implement a compiler or evaluator. Someone else already did that work. Your C compiler is very likely, in fact, already written in C. We don't expect a C-importable library interface for the C compiler, because none of the traditional old C compilers had one (gcc, MSVC, etc.) But libclang exists, and it's pretty easy to write a C REPL using it. From there, only a few steps to automation.
lastland 13y ago
He's talking about macro in Lisp and C. see: http://en.wikipedia.org/wiki/Macro_(computer_science) http://en.wikipedia.org/wiki/Macro_(computer_science) The macro in Lisp provides you with much more convenience (and power?) than print statement.
- Skinney 13y ago
  Lisp macroes have access to code that has already been compiled (which means, everything above the macro, and everything defined in imported files). This gives you access to the entire standard library in your macro. Also, because Lisp code is data rather than strings (code is represented as linked lists) it's much simpler to manipulate code in Lisp macros.
svantana 13y ago
He's most likely referring to the homoiconicity of lisp (http://en.wikipedia.org/wiki/Homoiconicity http://en.wikipedia.org/wiki/Homoiconicity) - when processor operations are a data type, writing a subprogram and executing it is as simple as filling in an array. In C, you would need to have a C compiler and a virtual machine in your program to run it!
weland 13y ago
Quines are not quite the same thing. Reasonably simple illustration: in Common Lisp, it is possible to write a function that takes a mathematical expression as an argument and returns another expression, as its derivative. So basically I can write (pseudo-lisp-ish): (defun diff (f) ... ) then call it like this: (diff '(+ (pow x 2) x) and I'd get the expression (+ (* 2 x) 1) as a result. The point is, however, that this expression is Lisp-callable code. If I already have a function p, I can write: (setq dp (diff p)) and dp is now the function computed by (diff p). This is not necessarily the most practically-useful example, but I think it's closest to being a strong illustration of the principle. In a nutshell, you can do symbolic manipulation with code from within your code. Edit: I just read your other post from this thread. It's important to note that this happens at runtime, not at compile time. This isn't impossible to do in C if you really want, but it wouldn't be portable (the reason for this is left at the user's discretion). Think about how you would do the same in C: write a function that takes a pointer to a function f, and returns a pointer to another function g, so that g is the derivative of f. It's obviously ok to restrict f to common mathematical operators. I can think about ways of doing it, but it ain't pretty.
- p4bl0 13y ago
  Actually if you had to do this kind of thing in C or any other non-homoiconic language, the right way to go would be to define data structures that represent your mathematical functions, and manipulate these structures to compute the derivatives (by pattern matching of the represented mathematical expression, exactly as you would do in Lisp using Lisp code which kind of is its own AST). And you would have to embed an interpreter for the mathematical expressions encoded in the data structures of your program, so you can not only manipulate the expressions, but also use them (which also comes for free in Lisp). See Greenspun's tenth rule of programming.
  - weland 13y ago
    > Actually if you had to do this kind of thing in C or any other non-homoiconic language, the right way to go would be to define data structures that represent your mathematical functions, and manipulate these structures to compute the derivatives (by pattern matching of the represented mathematical expression, exactly as you would do in Lisp using Lisp code which kind of is its own AST). Yes, of course. The language, being non-homoiconic, would require you to translate between a data representation that you can process and the data representation that the runtime can process. However, if you were to do the equivalent thing -- that is, obtain the derivative based on the data representation that your runtime can process -- you'd have to examine the contents of the program memory itself. Needless to say, that would make things even unportable, or outright impossible due to compiler optimizations. But it would be the same thing :). Edit: perversity bonus, you're working on a computer that does bank switching and the code that is computing the derivative is in a different memory bank than the function whose derivative it must compute.
agumonkey 13y ago
First by 'cannot' he means 'cannot easily', as other stated it's more than printing source code, and goes into metaprogramming quickly, and high cost resistance will render attempts at doing so in C-like languages painfull. Also, historical context matters, in the late 50s I believe this was very foreign to how machines were seen and used.

by ISL 13y ago

wes-exp 13y ago

I suspect "possible" here is not used in the absolute sense, but more just "it would be a total pain in the ass in C, whereas Lisp excels at it". After all, anything is "possible" with hand-written assembly code, too, but realistically speaking, it's not practical.

gavinpc 13y ago
I couldn't post this last night, but yeah: My ears perked up at the dual statement that although you can write a Lisp program that writes Lisp programs, nobody does it (um, macros?); and that you can't write a C program that writes a C programs (okay, maybe nobody does this, but you certainly can). I guess he means that C is not "aware" of its own constructs the way that Lisp is. Also, he said that the algebraic languages were "dying out", but that because of this self-generating ability (which nobody uses), that the future of Lisp was "open". Huh?
- h_r 13y ago
  I understood the "open" comment to mean "open to modification and extension", independent of whether it is dying out.

Guthur 13y ago

I think you might have missed the point of the statement "programs that write programs", it goes far beyond a toy quine. You can't do it in C unless you also implement a compiler or evaluator. And even then generating any sort of reasonably complex C code with C would be highly painful to say the least. You can possibly nearly get there with C macros but I would argue it's not C writing C there, rather a text preprocessor.

derefr 13y ago
> You can't do it in C unless you also implement a compiler or evaluator. Someone else already did that work. Your C compiler is very likely, in fact, already written in C. We don't expect a C-importable library interface for the C compiler, because none of the traditional old C compilers had one (gcc, MSVC, etc.) But libclang exists, and it's pretty easy to write a C REPL using it. From there, only a few steps to automation.

lastland 13y ago

He's talking about macro in Lisp and C. see: http://en.wikipedia.org/wiki/Macro_(computer_science) http://en.wikipedia.org/wiki/Macro_(computer_science) The macro in Lisp provides you with much more convenience (and power?) than print statement.

Skinney 13y ago
Lisp macroes have access to code that has already been compiled (which means, everything above the macro, and everything defined in imported files). This gives you access to the entire standard library in your macro. Also, because Lisp code is data rather than strings (code is represented as linked lists) it's much simpler to manipulate code in Lisp macros.

svantana 13y ago

He's most likely referring to the homoiconicity of lisp (http://en.wikipedia.org/wiki/Homoiconicity http://en.wikipedia.org/wiki/Homoiconicity) - when processor operations are a data type, writing a subprogram and executing it is as simple as filling in an array. In C, you would need to have a C compiler and a virtual machine in your program to run it!

weland 13y ago

Quines are not quite the same thing. Reasonably simple illustration: in Common Lisp, it is possible to write a function that takes a mathematical expression as an argument and returns another expression, as its derivative. So basically I can write (pseudo-lisp-ish): (defun diff (f) ... ) then call it like this: (diff '(+ (pow x 2) x) and I'd get the expression (+ (* 2 x) 1) as a result. The point is, however, that this expression is Lisp-callable code. If I already have a function p, I can write: (setq dp (diff p)) and dp is now the function computed by (diff p). This is not necessarily the most practically-useful example, but I think it's closest to being a strong illustration of the principle. In a nutshell, you can do symbolic manipulation with code from within your code. Edit: I just read your other post from this thread. It's important to note that this happens at runtime, not at compile time. This isn't impossible to do in C if you really want, but it wouldn't be portable (the reason for this is left at the user's discretion). Think about how you would do the same in C: write a function that takes a pointer to a function f, and returns a pointer to another function g, so that g is the derivative of f. It's obviously ok to restrict f to common mathematical operators. I can think about ways of doing it, but it ain't pretty.

p4bl0 13y ago
Actually if you had to do this kind of thing in C or any other non-homoiconic language, the right way to go would be to define data structures that represent your mathematical functions, and manipulate these structures to compute the derivatives (by pattern matching of the represented mathematical expression, exactly as you would do in Lisp using Lisp code which kind of is its own AST). And you would have to embed an interpreter for the mathematical expressions encoded in the data structures of your program, so you can not only manipulate the expressions, but also use them (which also comes for free in Lisp). See Greenspun's tenth rule of programming.
- weland 13y ago
  > Actually if you had to do this kind of thing in C or any other non-homoiconic language, the right way to go would be to define data structures that represent your mathematical functions, and manipulate these structures to compute the derivatives (by pattern matching of the represented mathematical expression, exactly as you would do in Lisp using Lisp code which kind of is its own AST). Yes, of course. The language, being non-homoiconic, would require you to translate between a data representation that you can process and the data representation that the runtime can process. However, if you were to do the equivalent thing -- that is, obtain the derivative based on the data representation that your runtime can process -- you'd have to examine the contents of the program memory itself. Needless to say, that would make things even unportable, or outright impossible due to compiler optimizations. But it would be the same thing :). Edit: perversity bonus, you're working on a computer that does bank switching and the code that is computing the derivative is in a different memory bank than the function whose derivative it must compute.

agumonkey 13y ago

First by 'cannot' he means 'cannot easily', as other stated it's more than printing source code, and goes into metaprogramming quickly, and high cost resistance will render attempts at doing so in C-like languages painfull. Also, historical context matters, in the late 50s I believe this was very foreign to how machines were seen and used.