Re:Writing a C Compiler (2017)
by golergka on Friday June 09, 2023 @09:59AM
(#36257906)
Weren't a lot of functional languages, like ML and it's descendants, created specifically to write parsers and compilers?
[ Parent
| on HN ]
I'm not sure about specifically. A joyful synergy, maybe. The fact that compilers are, in essence, pure functions, maps from input programs to output programs, was recognized quite early on. I can't put my finger on the origin of the idea, but it may have been understood by Turing himself. Well-understood in the Lisp world by the late 1960s, before ML came along. Parsers and compiler data structures, translate extremely well into recursive functions, operating on algebraic data types. These are applicable to many other problems, but compilers have always had centre place in the functional showroom. Sometimes I do wonder if it's just navel-gazing, though -- look, functional languages are useful for implementing functional languages!
Re:Writing a C Compiler (2017)
by JonChesterfield on Friday June 09, 2023 @10:11AM
(#36258069)
I've seen it claimed that ML was originally written, in lisp, in order to have a better language to write compilers in.
ML was written as the language used by the theorem prover LCF. It was written in Lisp.
Re:Writing a C Compiler (2017)
by JonChesterfield on Friday June 09, 2023 @08:51PM
(#36266400)
I didn't know that link, searches seem to confirm. Thank you.
The LCF style provers rely on the host language type system. A theorem instance can only be created by the trusted kernel. Lisp doesn't obviously lend itself to that - you could represent the proof, but I'm not clear how you'd prevent forging one.
Re:Writing a C Compiler (2017)
by peterfirefly on Friday June 09, 2023 @11:15AM
(#36259087)
No. ML was the meta language for a theorem prover (LCF).
https://en.wikipedia.org/wiki/Logic_for_Computable_Functions