Live data from Hacker News

The seven programming ur-languages (2022)

madhadron.com

131–140 of 161 posts

Re: The seven programming ur-languages (2022)

#131

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…

Behold, future children, this is the ur-comment that started the cognitive revolution in how we teach programming languages in the 32nd century. The text and its important idea were almost lost in the tides of history, but it reached us thanks to a few eccentric ur-linguists digging through the ruins of post-WWIV civilizational collapse.

Re: The seven programming ur-languages (2022)

#132
post #108
post #99

Earlier 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.

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)

#133
post #108
post #99

Earlier 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.

Turing completeness is the upper bound of computability, not the lower bound. It's useful mostly for showing that some thing can express the full range of computable problems, or for snarking that some thing is far more complex than it has any right to be.

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)

#134
post #100
post #63

Earlier 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.

Regular expressions are definitely enough for turning characters into tokens, after which a simple recursive descent parser is vastly more straightforward to write. Lexing is optional, but generally advised.

Re: The seven programming ur-languages (2022)

#135
post #43

Earlier 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…

> if you're a developer who wants to exploit the multiplicative factor of a truly flexible and extensible programming language with state of the art features from the cutting-edge of PL research, then maybe give Lean a whirl!

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)

#136
post #132
post #108

Earlier 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.

Is Ladder Logic a programming language? It's used to program industrial controllers, and I don't believe it's Turing complete.

https://en.wikipedia.org/wiki/Ladder_logic

Re: The seven programming ur-languages (2022)

#137
post #61

Earlier quoted context omitted.

Aren't camels a Perl thing?

> Aren't camels a Perl thing? That's a deep cut. :-) For anyone reading this, O'Reilly was once legendary for their cover-art mascots.

Kids those days. There's always one explaining the joke to others.

Re: The seven programming ur-languages (2022)

#138
post #3

Reminds 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.

Perhaps better IMHO is "Strange code" by Ronald Kneusel (NoStarch, 2022) [0], which I found more didactic and developed. Please note than I'm quite a fan of this author's other books [1].

[0] https://nostarch.com/strange-code

[1] https://nostarch.com/search/Kneusel

Re: The seven programming ur-languages (2022)

#140
For any other array language novices, I've experimented with K and J but had the best experience so far with BQN. It is a bit on the Lispy side like K but much better documented, and I thought the APL-esque symbolic alphabet was mnemonically helpful enough while reading code to justify learning an editor keyboard integration. (Plus it's fun.)
Post reply on HN