Stack Builders

> For example I can prove my my string reverse works in Idris (https://www.stackbuilders.com/news/reverse-reverse-theorem-p...). This article basically demonstrates GP point, though. It proves that `reverse` is self-inverse, but there are lots and lots of functions that are self-inverse (for example, `x -> x` is self-inverse. As would be the function that swaps any odd-index element with the one following it). The claim was a difficulty of how to encode the actual correctness into your type-system. That this article doesn't actually encode correctness of reverse, seems like pretty good for that difficulty.

Stack Builders is hiring Ruby and Clojure developers in NYC and Colombia, South America. http://stackbuilders.com

There are a lot of people claiming they did it with Haskell (e.g. https://www.stackbuilders.com/blog/wasm-and-cloudflare-workers/). But the compilers don't claim to support it. I am still to make sense of it.

I wrote some things a few years ago on ATS. Its introductory but real world: https://www.stackbuilders.com/news/specific-endpoints. Generally ATS is good for verifying pure algorithms. It has code generators which can compile ATS to C and JS and the like. So if you have a very crucial piece of code and you want to do some formal verification of the process then you can try to use ATS. Other than that its completely a research language. I used ATS to write some stuff for my arduino 5 or so years ago.

Luckily for haskellers, GHC does a thing called fusion, which is an optimization that pipes together different operations on data, and avoids allocating intermediate results. (https://www.stackbuilders.com/tutorials/haskell/ghc-optimization-and-f…

It depends on your type system. In new languages like Idris or F* you can encode in the type the correctness of an algorithm and it will not compile if the compiler can not prove that correctness. For example I can prove my my string reverse works in Idris (https://www.stackbuilders.com/news/reverse-reverse-theorem-proving-wit… Or I could prove that my function squares all elements in a list. Etc. Now a big part of the problem is expressing with sufficient accuracy what the properties of the algorithm you want to prove are. For example for string reverse I may want to show more than that `reverse (reverse s) = s`. Since after all if reverse does nothing that would still be true. I would probably want to express that the first and last chars swap when I just call reverse xs.

Just an idea: this or something similar could be utilized to generate test vectors, for property based testing [0]. Also for model-based testing, if you consider the model to be a vector of actions [1] Currently, AFAIK, property based testing relies on mostly random generation of input vectors. It's possible to "shape" those vectors into other data structures such as trees [2] and it's the way it's usually done, but it's difficult and error-prone for more complex inputs. There's also the option to filter each vector before running, or, after running, by performing the shrinking algorithm to produce the minimal input vector that reproduces the problem. When I tried using property based testing for my use-case, as a model-based testing, I had to write code to filter most of the random test vectors since they weren't relevant, they didn't make sense. So it might be possible to guide the generation of the input vectors so they'll be less random, and save time during run. [0] https://typeable.io/blog/2021-08-09-pbt [1] https://fscheck.github.io/FsCheck/StatefulTesting.html [2] https://www.stackbuilders.com/blog/a-quickcheck-tutorial-generators/