in the world there should only be one debate and one summary about programming languages, and everybody should read that as a starting point before they enter the fray. for example, I would say what i was taught, that lisp is lists made out of cons cells, which contain references to either other lists/cons cells or to atoms. lisp doesn't "have" parentheses any more than lisp has the rest of the ASCII table, but paren…
The seven programming ur-languages (2022)
131–140 of 161 posts
Re: The seven programming ur-languages (2022)
#132Earlier quoted context omitted.
There has never been a requirement for a "true" programming language to be Turing complete. Also, basically every such language has escape hatches similar to unsafe in Rust to allow expressions that are not provably terminating. They can then just be accepted as an axiom.
I feel like Turing completeness has always been set as the boundary of programming language if there's any boundary at all. That's what people has been using to not include HTML as programming language for example. Or to include MTG as one.
HTML is not a programming language, it's a markup language - it's in the name, and it's the way it is used (it's not used to describe any kind of computation, it's straight up data that is parsed by algorithms).
Neither is PowerPoint, or game of life a programming language even though both are Turing complete.
Re: The seven programming ur-languages (2022)
#133Earlier quoted context omitted.
There has never been a requirement for a "true" programming language to be Turing complete. Also, basically every such language has escape hatches similar to unsafe in Rust to allow expressions that are not provably terminating. They can then just be accepted as an axiom.
I feel like Turing completeness has always been set as the boundary of programming language if there's any boundary at all. That's what people has been using to not include HTML as programming language for example. Or to include MTG as one.
Total languages omit partiality and non-termination from Turing completeness.
Partiality is IMO irrelevant when it comes to computability. Any partial function (that is, one whose range is not defined over its whole domain) can be expressed as a total function by either constricting the domain or expanding the range. For example, a "pop" operation on a stack is not defined for an empty stack. You can just loop forever if pop() is called on an empty stack. Alternatively, you can require that pop() is given a witness that the stack is non-empty, or you can require that pop() returns either the top-most element of the stack or a value that indicates the stack was empty. Both let you compute the same set of things as the former.
Non-termination is required to be Turing complete, because being Turing complete means being able to compute functions that one cannot reasonably expect to complete before the heat death of the universe. In _practice_ every function terminates when the computing process dies due to some external factor: process runs out of memory ("real" Turing machines have infinite memory!), user runs out of patience, machine runs out of power, universe runs out of stars, that sort of thing, so _in practice_ doing 2^64 iterations before giving up will generally* give you the same outcome as doing an unbounded number of iterations: it'll either terminate, or the process will be killed (here, due to reaching its iteration limit).
On the flip side, giving up non-termination and partiality only gives you increased correctness. If there's one thing we've definitely established in computing, it's that we will readily discard correctness to gain a little extra productivity. Why make a developer implement code to handle reaching an iteration limit when you can just make the user get sick of waiting and kill your app?
* 18 quintillion is a very large number. Have a try. The most trivial recursive function, on my M4 Mac, when convincing clang to be smart enough to turn it into a loop but dumb enough not to elide it altogether, would take a bit shy of 600 years to complete if iterating ULONG_MAX times; I didn't wait for that, if I'm honest with you, I ran it with a much smaller iteration count and multiplied it out.
Re: The seven programming ur-languages (2022)
#134Earlier quoted context omitted.
>term rewriting In uni we had to make a spreadsheet software. I volunteered to do the formula parser, thinking it sounded like a fun challenge. I was stumped for a week, until I realized I could rewrite the formulas into a form I knew how to parse. So it would rewrite 1+1 into ADD(1,1) and so on. I also refused to learn regex, so the parsing code was "interesting" ;) I recall a comment from a colleague. "Okay, Andy s…
Regular expressions are probably not enough for parsing formulas (depending of course on the exact task given), they usually are at least a context free language.
Re: The seven programming ur-languages (2022)
#135Earlier quoted context omitted.
Random passerby chiming in: so this means you can write "regular" software with this stuff? While reading TFA I thought the theorem stuff deserved its own category, but I guess it's a specialization within an ur-family (several), rather than its own family? It definitely sounds like it deserves its own category of programming language, though. The same way Lojban has ancestry in many natural languages but is very muc…
Yes Idris was meant to write regular code. F* is also meant to write regular code But I think that the theorem prover that excels most at regular code is actually Lean. The reason I think that is because Lean has a growing community, or at least is growing much faster than other similar languages, and for regular code you really need a healthy ecosystem of libraries and stuff. Anyway here an article about Lean as a g…
Does not sound that appealing to me. Sounds like little consistency and having to learn a new language for every project.
Re: The seven programming ur-languages (2022)
#136Earlier quoted context omitted.
I feel like Turing completeness has always been set as the boundary of programming language if there's any boundary at all. That's what people has been using to not include HTML as programming language for example. Or to include MTG as one.
I think it's a pretty recent thing. Turing completeness is neither a sufficient nor a required property. HTML is not a programming language, it's a markup language - it's in the name, and it's the way it is used (it's not used to describe any kind of computation, it's straight up data that is parsed by algorithms). Neither is PowerPoint, or game of life a programming language even though both are Turing complete.
Re: The seven programming ur-languages (2022)
#137Re: The seven programming ur-languages (2022)
#138Reminds me a bit of Bruce Tate’s approach in 7 languages in 7 weeks, which is where I first encountered Erlang. I think from a historical perspective, describing COBOL and Fortran as part of the ALGOL family is a stretch, but I suppose it’s a good reminder that all history is reductive.
There's also (besides Tate's sequel of 7 more languages), Dimitry Zinoviev's 7 Obscure Languahes in Seven Weeks. I liked it a lot, even if it hurt my feelings a bit to have my beloved Forth be one of the obscure languages (the others were APL, SNOBOL, Occam, Simula, Starset, and M4) -- I'm old and nerdy, but hadn't even heard of Occam and Starset.