180 karma · joined February 21, 2007
Agda also added recently support for cubical paths https://agda.readthedocs.io/en/latest/language/cubical.html .
I'm also waiting on Lean https://leanprover.github.io to introduce cubical type theory for HoTT. Version 2 of the language had HoTT based on the univalence axiom which was dropped in version 3. With cubical type theory the univalence axiom can be constructively proved and is no longer an axiom.
On the one end are "point tests", manually written tests that check correctness in several predetermined cases. That's what most software engineers mean by "testing".
Then comes randomized tests/fuzz testing/QuickCheck where properties are defined to hold for all values of some variables and then can be checked on randomly generated values. This offers better correctness guarantees than manually created "point tests" but might still miss failing cases since it's sampling and not exhaustively searching through the whole space.
Finally, on the far end are proofs, where one formally proves that the formerly mentioned properties always hold. I cannot imagine a stronger guarantee that something holds than an actual mathematical proof of it.
Dependently typed languages (Agda, Idris, Coq, Lean, etc) push software development into that far end where correctness can actually be proved. Imo that's where the future of software lays for certain classes of programs where correctness is a must.
Here's a proof of the original question in Lean:
def foo : (λ x, 2 * x) = (λ x, x + x) :=
begin
apply funext, intro x,
cases x,
{ refl },
{ simp at *,
dsimp [has_mul.mul, nat.mul],
have zz : Π a : nat, 0 + a = a := by simp at *,
rw zz }
end> return x = \a -> x
>
> (>>=) :: (a -> x) -> (x -> (a -> y)) -> (a -> y)
> m >>= f = \a -> f (m a) a
>(Incidentally, these are two of the Łukasiewicz axioms for propositional calculus.)
Also the K and S in SKI combinator calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus
The path tracing approaches in modern raytracers are actually very similar as computation to Feynman's path integral formulation of quantum electrodynamics (QED). The big difference is that in the "classical" approach one integrates real values (radiance) and in the QED one integrates complex values (amplitudes) whose magnitude describe the probability of a given wavelength hitting the camera sensor.
I was pitching this idea as a research direction in a recent slide deck https://github.com/skaslev/fract/blob/master/mc-production.p...
The reason is that "computation" is very useful concept but it has taken us ages to define what it means precisely. But that didn't stop people of reinventing it in other areas.
Curry-Howard is only one of many other isomorphism between programs and other areas. See "Physics, Topology, Logic and Computation: A Rosetta Stone"[1] and in particular Table 4 on pg. 66. Curry-Howard correspondence is the last two columns of the table; the other three columns are other "correspondences" in topology, physics and category theory.
See Curry-Howard correspondence http://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspond... or, if feeling adventurous, Homotopy type theory dubbed to be a new foundation of mathematics: http://en.wikipedia.org/wiki/Homotopy_type_theory and http://homotopytypetheory.org/
My .emacs is portable and I use it across Linux, OS X and Windows. Of course it's based on my personal preferences (vim emulation anyone?) and I seldom see people sharing the same config except maybe Bozhidar's Emacs prelude https://github.com/bbatsov/prelude
I agree. The astonishing thing about quantum mechanics to me is that it describes how deterministic laws emerge from completely non-deterministic processes.
For example, in quantum electrodynamics, a photon going from A to B, chooses a random path with a well defined probability density assigned to each possible path. When you do the math, it turns out that the shortest path between A and B is the most likely one and that's why the classical "deterministic" law that light goes in straight lines is a good approximation for large distances. Yet the path which the photon chooses to take is completely random, chosen by the photon's free will, if you will.
import qualified Data.Set as S
data Forest = F Int Int Int
deriving (Eq, Ord, Show)
meal forests = (S.toList . S.fromList)
[nextForest |
forest <- forests,
meal <- possibleMeals,
let nextForest = forest <+> meal,
valid nextForest]
where
possibleMeals = [
F (-1) (-1) 1,
F (-1) 1 (-1),
F 1 (-1) (-1)]
F x y z <+> F x' y' z' = F (x+x') (y+y') (z+z')
valid (F x y z) = x >= 0 && y >= 0 && z >= 0
findStable forest = iter [forest]
where
iter forests | not (done forests) = iter (meal forests)
| otherwise = filter stable forests
done forests = null forests || any stable forests
stable (F _ 0 0) = True
stable (F 0 _ 0) = True
stable (F 0 0 _) = True
stable _ = False
main = print $ findStable (F 117 155 106)Mathematical equations don't have any meaning taken by themselves; they just express a certain relationship between quantities without stating anything specific about what those quantities are.
Any translation of an equation to English would be a certain (usually lossy) interpretation of the equation for some particular quantities. But the same equation can have multiple interpretations in wildly different contexts.
Striking example is quantum mechanics. Physicists in the first half of the 20th century figured out a mathematical model (e.g. the Shroedinger equation) that worked perfectly well for predicting the behaviour of fundamental particles. Interpreting what the equation actually means (let's say in English) proved to be hard though and spawned multiple, sometimes conflicting or paradoxical interpretations. In fact, to this very day physicists are split on their favorite interpretation of QM. On the positive side, the mathematics of QM just works no matter how the result or the calculation are being interpreted.
Don't take it so seriously.
Good Haskell programs are pure; side effects are usually isolated in a "shell" wrapping the purely functional core of your program that interacts with the world (IO, networking, graphics, etc).