pasv VS awesome-lisp-companies

Then you go to the more elaborate prover. We used the Boyer-Moore prover for that. After proving a implies b, that became a theorem/rule the fast prover could use when it matched. So if the same situation came up again in code, the rule would be re-used automatically.

I notice that the examples for this verified Rust system don't seem to include a termination check for loops. You prove that loops terminate by demonstrating that some nonnegative integer expression decreases on each iteration and never goes negative. If you can't prove that easily, the code has no place in mission-critical code.

Microsoft's F* is probably the biggest success in this area.[3]

[1] https://archive.org/details/manualzilla-id-5928072/page/n3/m...

[2] https://github.com/John-Nagle/pasv

[3] https://www.microsoft.com/en-us/research/video/programming-w...

This is a generic problem with macro systems, of course, which is why C deliberately had a weak macro system.

LISP is a blast from the path. It's fun for retro reasons, but things have moved on.

[1] https://github.com/John-Nagle/nqthm

[2] https://github.com/John-Nagle/pasv/tree/master/src/CPC4

> In the 70's, this wasn't considered a 'real' proof.

I ran into that decades ago. We used the original Boyer-Moore theorem prover [1] as part of a program verification system. The system had two provers, the Nelson-Oppen simplifier (the first SAT solver) to automatically handle the easy proofs, and the Boyer-Moore system for the hard ones. To make sure that both had consistent theories, I used the Boyer-Moore prover to prove the "axioms" of the Nelson-Oppen system, especially what are usually called McCarthy's axioms (the ones that use Select and Store) for arrays.

The Boyer-Moore system uses a strictly constructive approach to mathematics. It starts from something like Peano arithmetic (there is a number zero, and an operation add 1) and builds up number theory. So I added a concept of arrays, represented as (index, value) tuples in sorted order, and was able to prove the usual "axioms" for arrays as theorems.

The machine proofs were long and involved much case analysis.[2] I submitted a paper to JACM in the early 1980s and got back reviews saying that it was just too long and inelegant to be at the fundamentals of computer science. That might not be the case today.

A few years back, I put the Boyer-Moore prover on Github, after getting it to work with Gnu Common LISP. So you can still run all this 1980s stuff. It's much faster today. It took about 45 minutes to grind through these proofs on a VAX 11/780 in the early 1980s. Now it takes about a second.

The proof log [2] is amusing. It's building up number theory from a very low level, starting by proving that X + 0 = X. Each theorem proved can be used as a lemma by later theorems, so you guide the process by giving it problems to solve in the right order. By line 1900, it's proving that multiplication distributes over addition. Array theory, the new stuff, starts around line 2994.

The reason this is so complicated and ugly is that there's no use of axiomatic set theory. Arrays are easy if you have sets. But there are no sets here. Sets don't fit well into this strict constructive theory, because EQUAL means identical. You can't create weaker definitions of equality which say that two sets are equal if they contain the same elements regardless of order, because that introduces a risk of unsoundness. Effort must be put into keeping the tuples of the array representation in ascending order by subscript, which implies much case analysis. Mathematicians hate case analysis. Computers are good at it.

[1] https://github.com/John-Nagle/nqthm

[2] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...

behave as if it does. The other extreme would be a GUI program.

[1] http://www.animats.com/papers/verifier/verifiermanual.pdf

[2] https://github.com/John-Nagle/pasv

which proves that the storing operation always produces a validly ordered array. That's essentially a code proof of correctness for a recursive function The Boyer-Moore prover was able to grind out a proof of that without help. That was a long proof, too.

I submitted this to JACM. It was rejected, mostly for uglyness. The concept that you needed all this heavy machine-driven case analysis to prove a nice simple "axiom" upset mathematicians. Today it would be less of an issue. People are now more used to proofs that take a lot of grinding through cases.

You could build up set theory this way, via ordered lists, if you wanted.

So that's a classic of what happens if you take "equal" seriously.

[1] http://www-formal.stanford.edu/jmc/towards.pdf

[2] https://theory.stanford.edu/~arbrad/papers/arrays.pdf

[3] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...

[4] https://github.com/John-Nagle/nqthm

Thanks to ITA Software (powering Kayak and Orbitz), Google dedicates resources to open-source Common Lisp development. More specifically, to SBCL:

> Doug Katzman talked about his work at Google getting SBCL to work with Unix better. For those of you who don’t know, he’s done a lot of work on SBCL over the past couple of years, not only adding a lot of new features to the GC and making it play better with applications which have alien parts to them, but also has done a tremendous amount of cleanup on the internals and has helped SBCL become even more Sanely Bootstrappable. That’s a topic for another time, and I hope Doug or Christophe will have the time to write up about the recent improvements to the process, since it really is quite interesting.

> Anyway, what Doug talked about was his work on making SBCL more amenable to external debugging tools, such as gdb and external profilers. It seems like they interface with aliens a lot from Lisp at Google, so it’s nice to have backtraces from alien tools understand Lisp. It turns out a lot of prerequisite work was needed to make SBCL play nice like this, including implementing a non-moving GC runtime, so that Lisp objects and especially Lisp code (which are normally dynamic space objects and move around just like everything else) can’t evade the aliens and will always have known locations.

https://mstmetent.blogspot.com/2020/01/sbcl20-in-vienna-last...

https://lisp-journey.gitlab.io/blog/yes-google-develops-comm...

The ASDF system definition facility, at the heart of CL projects, also comes from Google developers.

While we're at it, some more companies using CL today: https://github.com/azzamsa/awesome-lisp-companies/

Everyone, if you don't have a clue on how's Common Lisp going these days, I suggest:

https://lisp-journey.gitlab.io/blog/these-years-in-common-li... (https://www.reddit.com/r/lisp/comments/107oejk/these_years_i...)

A curated list of libraries: https://github.com/CodyReichert/awesome-cl

Some companies, the ones we hear about: https://github.com/azzamsa/awesome-lisp-companies/

and oh, some more editors besides Emacs or Vim: https://lispcookbook.github.io/cl-cookbook/editor-support.ht... (Atom/Pulsar support is good, VSCode support less so, Jetbrains one getting good, Lem is a modern Emacsy built in CL, Jupyter notebooks, cl-repl for a terminal REPL, etc)

Examples (for Common Lisp, so not citing Emacs): reddit v1, Google's ITA Software that powers airfare search engines (Kayak, Orbitz…), Postgres' pgloader (http://pgloader.io/), which was re-written from Python to Common Lisp, Opus Modus for music composition, the Maxima CAS, PTC 3D designer CAD software (used by big brands worldwide), Grammarly, Mirai, the 3D editor that designed Gollum's face, the ScoreCloud app that lets you whistle or play an instrument and get the music score,

but also the ACL2 theorem prover, used in the industry since the 90s, NASA's PVS provers and SPIKE scheduler used for Hubble and JWT, many companies in Quantum Computing, companies like SISCOG, who plans the transportation systems of european metropolis' underground since the 80s, Ravenpack who's into big-data analysis for financial services (they might be hiring), Keepit (https://www.keepit.com/), Pocket Change (Japan, https://www.pocket-change.jp/en/), the new Feetr in trading (https://feetr.io/, you can search HN), Airbus, Alstom, Planisware (https://planisware.com),

or also the open-source screenshotbot (https://screenshotbot.io), the Kandria game (https://kandria.com/),

and the companies in https://github.com/azzamsa/awesome-lisp-companies and on LispWorks and Allegro's Success Stories.

https://github.com/tamurashingo/reddit1.0/

http://opusmodus.com/

https://www.ptc.com/en/products/cad/3d-design

http://www.izware.com/mirai

https://apps.apple.com/us/app/scorecloud-express/id566535238

> but there doesn't seem to be one that really stands out as pragmatic, industrial

disagree ;) This industrial language is Common Lisp.

Some industrial uses:

- http://www.lispworks.com/success-stories/index.html

- https://github.com/azzamsa/awesome-lisp-companies/

- https://lisp-lang.org/success/

Example companies: Intel's programmable chips, the ACL2 theorem prover (https://royalsocietypublishing.org/doi/10.1098/rsta.2015.039...), urban transportation planning systems (SISCOG), Quantum Computing (HRL Labs, Rigetti…), big data financial analysis (Ravenpack, they might be hiring), Google, Boeing, the NASA, etc.

ps: Python competing? strong disagree^^

and of course, a quite recent list of companies, in addition of LW's success stories page: https://github.com/azzamsa/awesome-lisp-companies/

Hey there, newer member of the first group here. Please see https://github.com/azzamsa/awesome-lisp-companies/ to update your meta-comment. So, is CL used in the industry today, yes or no?

Personal note: I much prefer to maintain a long-living software in Common Lisp rather than in Python, thank you very much. May all the new programmers learn easily and all the teams have lots of ~~burden~~ work with Python, good for them.

Common Lisp has many industrial uses though.

(https://github.com/azzamsa/awesome-lisp-companies/

https://lisp-lang.org/success/

http://www.lispworks.com/success-stories/index.html

such as

https://www.cs.utexas.edu/users/moore/acl2/ (theorem prover used by big corp©)

https://allegrograph.com/press_room/barefoot-networks-uses-f... (Intel programmable chip)

quantum compilers https://news.ycombinator.com/item?id=32741928

etc, etc, etc)

A few more that we know of, using CL today: https://github.com/azzamsa/awesome-lisp-companies/

Others: https://lisp-lang.org/success/

yes

https://github.com/azzamsa/awesome-lisp-companies

http://lisp-lang.org/success/

industrial theorem prover, design of Intel chips, quantum compilers...

and little me, being more productive and having more fun than with python to deploy boring tools (read a DB, format the data, send to FTP servers, show a web interface...).