Lisp and the foundations of computing

Posted Feb 11, 2019 1:17 UTC (Mon) by marcH (subscriber, #57642)
In reply to: Lisp and the foundations of computing by nix
Parent article: Lisp and the foundations of computing

> Well generate X and do Y then. These are all things you can do in C, or in any non-cripppled language. [...] C is not magic nor is it impossible to implement 'eval' in. It "just" depends on how precisely you define it.

Science is about all the wild things that are possible given infinite time, knowledge and resources. From a very theoretical perspective C and Lisp are probably the same.

Engineering is about the practical things that people actually do and use given real-world time, knowledge and resources. From a practical perspective C couldn't be more different from Lisp for many reasons (not just C's unsafe boundaries between code and data) hence no one ever tried to actually implement in C anything equivalent to Lisp's "eval" because even if theoretically possible that would one of the most futile and pointless things ever. As useful as trying to make a screwdriver out of a shovel.

Of course science makes better engineers and knowing concepts and ideas from other (higher-level and more abstract...) languages like "eval" most definitely helps making better and safer programs in any (typically: lower-level) language. This helps precisely because some languages do _not_ have any practical "eval" feature for real-world usage.

Thanks for the conference report and fun WE discussion about computer science and eval. Now on Monday, back to $DAYJOB engineering and yet another attempt to explain in <random code review> why copy/paste is bad and "updated stuff" not a good commit message :-)

PS:
- if you're interested in seeing how some science can be applied to practical engineering and shaping a better C then check out Rust.
- off-topic but another reason why C is more and more obsolete: performance disconnect on modern hardware https://queue.acm.org/detail.cfm?id=3212479 (great paper)

Lisp and the foundations of computing

Posted Feb 11, 2019 7:22 UTC (Mon) by amacater (subscriber, #790) [Link]

I really need to steal your last paragraph: it's so true.

$DAYJOB is what keeps most of us running to pay for housing, family, social life, food - but the disconnect between that and LWN is annoying. LWN, the Beowulf list and my Free Software friends and colleagues are, however, what keeps me optimistic and engaged. Jon and the others here - your services to adult mental health and well-being cannot be underestimated.

Lisp and the foundations of computing

Posted Feb 11, 2019 14:41 UTC (Mon) by dgm (subscriber, #49227) [Link] (1 responses)

> Science is about all the wild things that are possible given infinite time, knowledge and resources.
> ...
> Engineering is about the practical things that people actually do and use given real-world time, knowledge and resources.

Maybe this is an engineer's view of science, but it's certainly not a very scientific view of either. In my humble oppinion, Science is about which things are possible and which are not, and *why*. Engineering is about *how* to make those things (or something close enough) at a reasonable cost.

Lisp and the foundations of computing

Posted Feb 11, 2019 21:26 UTC (Mon) by nix (subscriber, #2304) [Link]

Quite. Science can also sometimes tell you that the answer is "never, or at least not unless you fundamentally rethink it". That knowledge of limitations *alone* justifies all this maundering, even if nothing else useful came out of it. :)

Lisp and the foundations of computing

Posted Feb 11, 2019 21:24 UTC (Mon) by nix (subscriber, #2304) [Link]

hence no one ever tried to actually implement in C anything equivalent to Lisp's "eval"

That's not actually true. I know of at least three attempts, or things that could be called something like attempts (heck, one was even in glibc!).

(Yes, it was a mad idea in every case.)

Lisp and the foundations of computing

Posted Feb 16, 2019 18:53 UTC (Sat) by Wol (subscriber, #4433) [Link] (1 responses)

> > Well generate X and do Y then. These are all things you can do in C, or in any non-cripppled language. [...] C is not magic nor is it impossible to implement 'eval' in. It "just" depends on how precisely you define it.

> Science is about all the wild things that are possible given infinite time, knowledge and resources. From a very theoretical perspective C and Lisp are probably the same.

What a profound, spot on statement!

As soon as you start studying turing complete languages, the maths says they are equivalent, which means that they are in fact the same thing.

Let's go back to basic theory - about "what is a computer". A computer is an ALU, where you feed a (big?) number into the input slot, and a (big?) number comes out the output slot. What's to stop you feeding the output back in to the input slot? In other words - "there is no difference between program and data". That's basic computer theory - maths.

(Think about GCC, which is written in C, or any other "self-hosted" language. The code is - must be - both program and data otherwise it couldn't self-host.)

As soon as you start arguing about particular languages, like C++ or Lisp or Erlang or whatever, you are now into Technology or Engineering, where you can enforce arbitrary, random restrictions. Or maybe not, if you have a general-purpose turing-complete environment like a general-purpose computer. In other words, any turing-complete language is capable of having a execution environment written in it, capable of executing any random language. Turtles all the way down ...

Cheers,
Wol

Lisp and the foundations of computing

Posted Feb 18, 2019 23:12 UTC (Mon) by nix (subscriber, #2304) [Link]

As soon as you start studying turing complete languages, the maths says they are equivalent, which means that they are in fact the same thing.

Up to a point, Lord Copper. They are equivalent given an infinite tape and infinite time, and ignoring everything other than pure computation. I/O, random number generators, the time of day, anything at all to do with space or time complexity -- suddenly you are out of the Turing tarpit and languages and Turing-complete systems are distinguishable once more. i.e. just because you can emulate any Turing-complete system in any other doesn't mean you can emulate it at the same speed or in the same space.

So our systems are strictly more powerful than Turing machines -- but since infinite storage and time are not remotely feasible, we have also got no access to anything with the computational power of a "real" Turing machine, nor ever will. (And, of course, there is an unboundedly infinite hierarchy of Turing oracles, each of which can solve the halting problem in lower orders of oracle and in Turing machines themselves. We have even less idea how any of these might work: probably the answer is "they are defined by assertion and are not just unphysical but logically impossible entities".)