I might add another class of languages: those intended to express proofs, via the Curry-Howard correspondence. Lean is a primary example here. This could be considered a subclass of functional languages but it might be different enough to warrant a separate class. In particular, the purpose of these programs is to be checked; execution is only secondary.
armchairhacker 44 minutes ago [-]
Theorem proving and complex types are like extensions on an otherwise ordinary language:
- Agda, Idris, etc. are functional languages extended with complex types
- Isabelle, Lean, etc. are functional languages extended with complex types and unreadable interactive proofs
- Dafny etc. are imperative languages extended with theorems and hints
> Agda, Idris, etc. are functional languages extended with complex types
I think they are not. No amount of type level extensions can turn a regular functional language like Haskell into something suitable for theorem proving. Adding dependent types to Haskell, for example, doesn't suffice. To build a theorem prover you need to take away some capability (namely, the ability to do general recursion - the base language must be total and can't be Turing complete), not add new capabilities. In Haskell everything can be "undefined" which means that you can prove everything (even things that are supposed to be false).
There's some ways you can recover Turing completeness in theorem provers. You can use effects like in F* (non-termination can be an effect). You can separate terms that can be used in proofs (those must be total) from terms that can only be used in computations (those can be Turing complete), like in Lean. But still, you need the base terms to be total, your logic is done in the fragment that isn't Turing complete, everything else depends on it.
LeCompteSftware 21 minutes ago [-]
This is just wrong, you're being too didactic. Idris specifically lets you implement nontotal functions in the same way that Rust lets you write memory-unsafe code. The idea is you isolate it to the part of the program with effects (including the main loop), which the compiler can't verify anyway, and leave the total formally verified stuff to the business logic. Anything that's marked as total is proven safe, so you only need to worry about a few ugly bits; just like unsafe Rust.
Idris absolutely is a general-purpose functional language in the ML family. It is Haskell, but boosted with dependent types.
LeCompteSftware 24 minutes ago [-]
Lean is definitely a dependently typed ML-family language like Agda and Idris, so "ML" has it covered. And the long-term goal of Lean certainly is not "execution is only secondary"; Microsoft is clearly interested in writing real software with it: https://lean-lang.org/functional_programming_in_lean/Program...
OTOH if you really want to emphasize "intended to express proofs" then surely Prolog has that covered, so Lean can be seen as half ML, half Prolog. From this view, the Curry-Howard correspondence is just an implementation detail about choosing a particular computational approach to logic.
My favorite subject when studying CompSci (TU Delft) was called "Concepts of programming languages". We learned C, Scala (for functional) and Javascript (prototypes).
It made learning Elixir years later much easier.
We also had a course that basically summed up to programming agents to play Unreal Tournament in a language called GOAL which was based on Prolog.
For years I've wanted to use Prolog but could not figure out how. I ended up making a spellcheck to allow LLM's to iterate over and fix the dismal Papiamentu they generate.
We agree on Algol, Lisp, Forth, APL, and Prolog. For ground-breaking functional language, I have SASL (St Andrews Static Language), which (just) predates ML, and for object oriented language, I have Smalltalk (which predates Self).
I also include Fortran, COBOL, SNOBOL (string processing), and Prograph (visual dataflow), which were similarly ground-breaking in different ways.
macintux 2 hours ago [-]
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.
gottheUIblues 2 hours ago [-]
Rather COBOL is a living fossil? And today's Fortran is the FORTRAN family with horizontal gene transfer from the Algol lineage of programming languages.
shevy-java 2 hours ago [-]
Can COBOL be called a living fossil?
I mean, programming languages do not live; and they do not "die", per se, either. Just the usage may go down towards 0.
COBOL would then be close to extinction. I think it only has a few niche places in the USA and perhaps a very few more areas, but I don't think it will survive for many more decades to come, whereas I think C or python will be around in, say, three decades still.
> family with horizontal gene transfer
Well, you refer here to biology; viruses are the most famous for horizontal gene transfer, transposons and plasmids too. But I don't think these terms apply to software that well. Code does not magically "transfer" and work, often you have to adjust to a particular architecture - that was one key reason why C became so dynamic. In biology you basically just have DNA, if we ignore RNA viruses (but they all need a cell for their own propagation) 4 states per slot in dsDNA (A, T, C, G; here I exclude RNA, but RNA is in many ways just like DNA, see reverse transcriptase, also found in viruses). So you don't have to translate much at all; some organisms use different codons (mitochondrial DNA has a few different codon tables) but by and large what works in organism A, works in organism B too, if you just look to, say, wish to create a protein. That's why "genetic engineering" is so simple, in principle: it just works if you put genes into different organisms (again, some details may be different but e. g. UUU would could for phenylalanine in most organisms; UUU is the mRNA variant of course, in dsDNA it would be TTT). Also, there is little to no "planning" when horizontal gene transfer happens, whereas porting requires thinking by a human. I don't feel that analogy works well at all.
1 hours ago [-]
steve_gh 32 minutes ago [-]
One correction I'd make to the article's taxonomy: Ruby is an object oriented language not an Algol. Its inspiration is Smalltalk, and much of the standard library naming comes from that route (eg collect rather than map).
Ruby is object oriented from the ground up. Everything (and I do mean everything) is an object, and method call is conceived as passing messages to objects.
While Ruby is most often compared to Python (an Algol), they come from very different evolutionary routes, and have converged towards the same point in the ecosystem. I think of Ruby as a cuddly Alpaca compared to Python's spitting camel.
gobdovan 1 hours ago [-]
there's a few more semantic families: verilog, petri nets and variants, Kahn process networks and dataflow machines, process calculi, reactive, term rewriting, constraint solvers/theorem provers (not the same with Prolog), probabilistic programming,
plus up and coming (actual production-ready) languages that don't fit perfectly in the 7 categories: unison, darklang, temporal dataflow, DBSP
It may feel like a little bit of cheating mentioning the above ones, as most are parallel to the regular von Neumann machine setup, but was meaning for a while to do an article with 'all ways we know how to compute (beyond von Neumann)'.
gobdovan 1 hours ago [-]
also Sussman's propagators are nice to check out [0]
[0] The Art of the Propagator (mit url down for the moment)
tagfowufe 3 hours ago [-]
I would refer to the world _cognate_[0]. 'Fundamental programming cognates' sounds cool as a uni course.
This article is full of gross mistakes. For example it claims that Caml is "Cambridge ML" which is ridiculously false. Fact check every sentence. Really sad.
Svip 54 minutes ago [-]
For those curious: Cambridge ML is a thing, but abbreviated CML[0]; and whilst Caml is part of the ML family, it appears to be unrelated to CML.
- Forth: you can use PFE,Gforth for ANS Forth requeriments.
Or EForth if you reached high skills levels
where the missing stuff can be just reimplemented.
EForth under Muxleq: https://github.com/howerj/muxleq
I can provide a working config where a 90% of it
would be valid across SF.
If you follow the instructions on compiling s9, mlite it's similar
with MinC for Windows. If you are a Unix/Linux/Mac user, you already
know how to do that.
You got the whole docs in the TGZ file, and the web.
Altough Scheme and CL are different paths. CL's loop it's really, really complex and Scheme it's pretty much straightforward to understand. Any advanced CL user will have to implement Scheme's syntax (and an interpreter) as an exercise for PAIP. CL in CL... well, CL is too huge, T3X tried with Kilo Lisp 23 http://t3x.org/klisp/22/index.html and I doubt if anyone can even complete anything but the few starting chapters from Intro to Common Lisp with it.
pasc1878 1 hours ago [-]
Or for Lisp you might as well start with Emacs Lisp - you are going to use it for a decent environment unless you have the Common Lisp IDEs which you have to pay for or Racket.
anthk 53 minutes ago [-]
Eh, no. You have Elisp+cl-lib but SBCL too, and you can use Sly wth SBCL.
Huge tip: if you use MCCLIM, install Ultralisp first and (ql-quickload 'mcclim)
later: it will give you a big speed boost. Big, not as the ones from Phoronix.
Actually big. From 'I can almost see redrawing on a really old ass netbook' to
'snappy as TCL/Tk' under SBCL.
As you can see, you don't need to pay thousands of dollars.
For Scheme, S9 just targets R4RS but as a start it's more than enough, and for SICP
you can install Emacs+Geiser+chicken Scheme and from any Linux/BSD: distro
command prompt, you run:
Done. Get the SICP PDF and start doing SICP. You can use Emacs+Geiser with
M-x install RET geiser-chicken
if you are lazy. You can install the SICP book with
M-xpackage-install RET sicp
and read it from
M-x info RET
and do it everything from withing Emacs by running
M-x geiser
(pick chicken as the interpreter).
Save your Emacs settings. Done.
rramadass 11 minutes ago [-]
Folks might find the following useful for studying PLs;
1) Advanced Programming Language Design by Raphael Finkel - A classic (late 90s) book comparing a whole smorgasbord of languages.
2) Design Concepts in Programming Languages by Franklyn Turbak et al. - A comprehensive (and big) book on PL design.
3) Concepts, Techniques and Models of Computer Programming by Peter Van Roy et al. - Shows how to organically add different programming paradigms to a simple core language.
pfdietz 2 hours ago [-]
Another direction to explore logic languages is Datalog.
mellosouls 2 hours ago [-]
(2022) and unfortunately advice to spend significant amounts of time in learning multiple languages is becoming rapidly redundant in the LLM age.
nxpnsv 9 minutes ago [-]
Hmm, here's a thought... If you want to stand out, it doesn't matter that some things now are easier for everybody, what matters is that that you are able to get better results than others. Learning multiple languages gives you more the ability to use them. It improves your thinking, makes you a better coder, and more able to understand different techniques. LLMs are tools, to use them better than the next person you need to understand what to ask, and what a good answer looks like.
justincormack 2 hours ago [-]
These are tools for thinking with, so not obsolete.
sph 39 minutes ago [-]
GP is just trying to convince you that thinking is "rapidly redundant in the LLM age".
aDyslecticCrow 31 minutes ago [-]
You're right. We should just run everything in java-script because that's what LLMs are good at right?
guzfip 30 minutes ago [-]
Make sure to let it pull in as many npm dependencies as it can.
zoky 2 hours ago [-]
Not at all. That’s like saying learning how different kinds of engines work is redundant in the age of taxis. You don’t have to know any of this stuff in order to get from A to B. But if you want to understand the processes involved in getting there, or you maybe want to be the one that builds a better self-driving vehicle, this is where you should start.
Rendered at 13:57:13 GMT+0000 (Coordinated Universal Time) with Vercel.
- Agda, Idris, etc. are functional languages extended with complex types
- Isabelle, Lean, etc. are functional languages extended with complex types and unreadable interactive proofs
- Dafny etc. are imperative languages extended with theorems and hints
- ACL2 is a LISP with theorems and hints
Related, typeclasses are effectively logic programming on an otherwise functional/imperative language (like traits in Rust, mentioned in https://rustc-dev-guide.rust-lang.org/traits/chalk.html).
I think they are not. No amount of type level extensions can turn a regular functional language like Haskell into something suitable for theorem proving. Adding dependent types to Haskell, for example, doesn't suffice. To build a theorem prover you need to take away some capability (namely, the ability to do general recursion - the base language must be total and can't be Turing complete), not add new capabilities. In Haskell everything can be "undefined" which means that you can prove everything (even things that are supposed to be false).
There's some ways you can recover Turing completeness in theorem provers. You can use effects like in F* (non-termination can be an effect). You can separate terms that can be used in proofs (those must be total) from terms that can only be used in computations (those can be Turing complete), like in Lean. But still, you need the base terms to be total, your logic is done in the fragment that isn't Turing complete, everything else depends on it.
Idris absolutely is a general-purpose functional language in the ML family. It is Haskell, but boosted with dependent types.
OTOH if you really want to emphasize "intended to express proofs" then surely Prolog has that covered, so Lean can be seen as half ML, half Prolog. From this view, the Curry-Howard correspondence is just an implementation detail about choosing a particular computational approach to logic.
It made learning Elixir years later much easier.
We also had a course that basically summed up to programming agents to play Unreal Tournament in a language called GOAL which was based on Prolog.
For years I've wanted to use Prolog but could not figure out how. I ended up making a spellcheck to allow LLM's to iterate over and fix the dismal Papiamentu they generate.
We agree on Algol, Lisp, Forth, APL, and Prolog. For ground-breaking functional language, I have SASL (St Andrews Static Language), which (just) predates ML, and for object oriented language, I have Smalltalk (which predates Self).
I also include Fortran, COBOL, SNOBOL (string processing), and Prograph (visual dataflow), which were similarly ground-breaking in different ways.
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.
I mean, programming languages do not live; and they do not "die", per se, either. Just the usage may go down towards 0.
COBOL would then be close to extinction. I think it only has a few niche places in the USA and perhaps a very few more areas, but I don't think it will survive for many more decades to come, whereas I think C or python will be around in, say, three decades still.
> family with horizontal gene transfer
Well, you refer here to biology; viruses are the most famous for horizontal gene transfer, transposons and plasmids too. But I don't think these terms apply to software that well. Code does not magically "transfer" and work, often you have to adjust to a particular architecture - that was one key reason why C became so dynamic. In biology you basically just have DNA, if we ignore RNA viruses (but they all need a cell for their own propagation) 4 states per slot in dsDNA (A, T, C, G; here I exclude RNA, but RNA is in many ways just like DNA, see reverse transcriptase, also found in viruses). So you don't have to translate much at all; some organisms use different codons (mitochondrial DNA has a few different codon tables) but by and large what works in organism A, works in organism B too, if you just look to, say, wish to create a protein. That's why "genetic engineering" is so simple, in principle: it just works if you put genes into different organisms (again, some details may be different but e. g. UUU would could for phenylalanine in most organisms; UUU is the mRNA variant of course, in dsDNA it would be TTT). Also, there is little to no "planning" when horizontal gene transfer happens, whereas porting requires thinking by a human. I don't feel that analogy works well at all.
Ruby is object oriented from the ground up. Everything (and I do mean everything) is an object, and method call is conceived as passing messages to objects.
While Ruby is most often compared to Python (an Algol), they come from very different evolutionary routes, and have converged towards the same point in the ecosystem. I think of Ruby as a cuddly Alpaca compared to Python's spitting camel.
plus up and coming (actual production-ready) languages that don't fit perfectly in the 7 categories: unison, darklang, temporal dataflow, DBSP
It may feel like a little bit of cheating mentioning the above ones, as most are parallel to the regular von Neumann machine setup, but was meaning for a while to do an article with 'all ways we know how to compute (beyond von Neumann)'.
[0] The Art of the Propagator (mit url down for the moment)
[0] https://en.wiktionary.org/wiki/cognate
[0] https://www.cl.cam.ac.uk/teaching/1011/FoundsCS/usingml.html
- Forth: you can use PFE,Gforth for ANS Forth requeriments. Or EForth if you reached high skills levels where the missing stuff can be just reimplemented.
EForth under Muxleq: https://github.com/howerj/muxleq I can provide a working config where a 90% of it would be valid across SF.
Starting Forth, ANS version: https://www.forth.com/starting-forth/
Thinking Forth, do this after finishing SF: https://thinking-forth.sourceforge.net/
Also, Forth Scientific Library. You can make it working with both GForth and PFE, just read the docs.
Full pack: https://www.taygeta.com/fsl/library/Library.tgz
Helping Forth code for GForth/PFE. If you put it under scilib/fs-util.fs, load it with:
https://www.taygeta.com/fsl/library/fsl-util.fs- Lisp. s9fes, it will compile under any nix/Mac/BSD out there, even with MinC.
S9fes: http://www.t3x.org/s9fes/
Pick the bleeding edge version, it will compile just fine.
For Windows users: MinC, install both EXE under Windows. First, mincexe, then buildtools*exe: https://minc.commandlinerevolution.nl/english/home.html
Then get 7zip to decompress the s9fes TGZ file, cd to that directory, and run 'make'.
Run ./s9 to get the prompt, or ./s9 file.scm where file.scm it's the source code.
In order to learn Scheme, there's are two newbie recommended books before "SICP".
Pick any, CACS, SS, it doesn't matter, both will guide you before SICP, the 'big' book on Scheme:
Simply Scheme https://people.eecs.berkeley.edu/~bh/pdf/
Simply.scm file, select from ';;; simply.scm version 3.13 (8/11/98)' to '(strings-are-numbers #t)' and save it as simply.scm
https://people.eecs.berkeley.edu/~bh/ssch27/appendix-simply....
Concrete Abstractions
Book:
https://www.d.umn.edu/~tcolburn/cs1581/ConcreteAbstractions....
The SCM files needed to be (load "foo.scm") ed in the code in order to do the exercises:
https://github.com/freezoo/scheme-concabs
If you are en Emacs user, just read the Elisp intro, it will work for a different Lisp family but with similar design.
Spot the differences:
Scheme (like s9):
We try: Elisp/Common Lisp (as the web site shows): Same there: - Ok, ML like languages:https://www.t3x.org/mlite/index.html
If you follow the instructions on compiling s9, mlite it's similar with MinC for Windows. If you are a Unix/Linux/Mac user, you already know how to do that.
You got the whole docs in the TGZ file, and the web.
Code: https://github.com/norvig/paip-lisp
The EPUB looks broken in my machine, try the PDF: https://commons.wikimedia.org/wiki/File:Peter_Norvig._Paradi...
Altough Scheme and CL are different paths. CL's loop it's really, really complex and Scheme it's pretty much straightforward to understand. Any advanced CL user will have to implement Scheme's syntax (and an interpreter) as an exercise for PAIP. CL in CL... well, CL is too huge, T3X tried with Kilo Lisp 23 http://t3x.org/klisp/22/index.html and I doubt if anyone can even complete anything but the few starting chapters from Intro to Common Lisp with it.
Of Lem with SBCL+Quicklisp:
https://lem-project.github.io/usage/common_lisp/
Huge tip: if you use MCCLIM, install Ultralisp first and (ql-quickload 'mcclim) later: it will give you a big speed boost. Big, not as the ones from Phoronix. Actually big. From 'I can almost see redrawing on a really old ass netbook' to 'snappy as TCL/Tk' under SBCL.
https://ultralisp.org/
As you can see, you don't need to pay thousands of dollars.
For Scheme, S9 just targets R4RS but as a start it's more than enough, and for SICP you can install Emacs+Geiser+chicken Scheme and from any Linux/BSD: distro command prompt, you run:
And, as a ~/.csirc file: To run SCM stuff for SICP: or Done. Get the SICP PDF and start doing SICP. You can use Emacs+Geiser with and read it from and do it everything from withing Emacs by running (pick chicken as the interpreter). Save your Emacs settings. Done.1) Advanced Programming Language Design by Raphael Finkel - A classic (late 90s) book comparing a whole smorgasbord of languages.
2) Design Concepts in Programming Languages by Franklyn Turbak et al. - A comprehensive (and big) book on PL design.
3) Concepts, Techniques and Models of Computer Programming by Peter Van Roy et al. - Shows how to organically add different programming paradigms to a simple core language.