HNHacker News
TopNewBestAskShowJobs

hiker

180 karma · joined February 21, 2007

submissionscomments
hiker··on How Rust Gets Polymorphism Right [video]
Of course you can. The good old {-# LANGUAGE OverlappingInstances #-}.
hiker··on Simplicity: A New Language for Blockchains [pdf]
Cubical https://github.com/mortberg/cubicaltt is a proof of concept programming language based on constructive (cubical type theory https://arxiv.org/abs/1611.02108) interpretation of HoTT.

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.

hiker··on F* – An ML-like functional programming language aimed at program verification
Lean is quite nice dependently typed language https://leanprover.github.io/
hiker··on How to compare two functions for equivalence, as in (λx.2*x) == (λx.x+x)?
The way I see it there's a whole spectrum of methods for checking program correctness.

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
hiker··on Why I like Golang's interfaces
Not really, it's equivalent to a product type.
hiker··on Category Theory for Programmers (2014)
> return :: x -> (a -> x)

> 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

hiker··on Faster 3D rendering with WebGL 2.0
Most of the progress in the field came from the pursuit of photorealism and trying to simulate better what actually happens in reality.

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...

hiker··on Proofs are Programs – 19th Century Logic and 21st Century Computing (2000) [pdf]
"Physics, Topology, Logic and Computation: A Rosetta Stone"[1] might be a starting point.

[1] http://math.ucr.edu/home/baez/rosetta.pdf

hiker··on Proofs are Programs – 19th Century Logic and 21st Century Computing (2000) [pdf]
Quoting from Wikipedia: "Because of the possibility of writing non-terminating programs, Turing-complete models of computation (such as languages with arbitrary recursive functions) must be interpreted with care, as naive application of the correspondence leads to an inconsistent logic. The best way of dealing with arbitrary computation from a logical point of view is still an actively debated research question, but one popular approach is based on using monads to segregate provably terminating from potentially non-terminating code (an approach that also generalizes to much richer models of computation,[6] and is itself related to modal logic by a natural extension of the Curry–Howard isomorphism[ext 1]). A more radical approach, advocated by total functional programming, is to eliminate unrestricted recursion (and forgo Turing completeness, although still retaining high computational complexity), using more controlled corecursion wherever non-terminating behavior is actually desired."
hiker··on Proofs are Programs – 19th Century Logic and 21st Century Computing (2000) [pdf]
What is commonly known as Curry-Howard correspondence (the duality between programs/proofs, computing/math) actually goes way deeper.

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.

[1] http://math.ucr.edu/home/baez/rosetta.pdf

hiker··on Real-Time Point-Based Global Illumination
Monte Carlo integration is what's used by most (all?) offline production renderers. The standard book on the subject is "Physically Based Rendering" [http://pbrt.org/] if you want to learn more.
hiker··on Maybe it’s time to talk about a new Linux Display Driver Model
WebGL implementations zero out newly allocated buffers for exactly that reason.

https://www.khronos.org/registry/webgl/specs/latest/1.0/#4

hiker··on The Algebra of Algebraic data types
The "Analytic Combinatorics"[1] book by Flajolet and Sedgewick is also relevant here.

[1] http://algo.inria.fr/flajolet/Publications/book.pdf

hiker··on Idiomatic Generics in Go
What's wrong to think that types are important? From mathematical point of view, types are interpreted as theorem statements and functions(values) that typecheck are considered proofs of those theorems. Types are fundamental.

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/

hiker··on Hilbert's 24th problem
I think Kolmogorov complexity is spot on comparison, considering programs as proofs, theorems as types in the Curry–Howard isomorphism.
hiker··on Lime Text: Open Source Sublime Text clone
As an active Emacs user, I can confirm the answer of all of the above is "yes". Heck, it even has a Tetris and a Psychiatrist built in.

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

hiker··on Conway's Proof Of The Free Will Theorem
> In that sense, determinism might be a small part of indeterminism.

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.

hiker··on First taste of Rust
Functional C version for comparison https://github.com/skaslev/catmull-clark/blob/master/obj.c
hiker··on Anti-Tesla sentiment and the death of optimism
https://www.youtube.com/watch?v=eSWWSq714aQ

http://news.bbc.co.uk/2/hi/europe/4923342.stm

hiker··on Performance comparison of Functional C++ 11, Java 8, JavaScript and Wolfram
See my comment here https://news.ycombinator.com/item?id=7857316
hiker··on Performance comparison of Functional C++ 11, Java 8, JavaScript and Wolfram
Here's a Haskell translation of the C++ version. Runtume is around 10x of the original (probably vector vs list cache trashing and vector sort/unique vs list to set/set to list), code reduction is 3x.

  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)
hiker··on Performance comparison of Functional C++ 11, Java 8, JavaScript and Wolfram
I don't see how the use of std::array<int,3> and std::count makes the C++ version less functional. Also, the next_forests.reserve doesn't help as much as you state, it's barely measurable when commenting out from my experiments (try it out!).
hiker··on Pointers Gone Wild
It shows that, if you need to, you can drop to direct memory access in Haskell. Also note the "unsafe" in the names of the functions. Of course, the majority of Haskell code uses algebraic data types and garbage collection.
hiker··on Web GL Ocean Simulation
His system of equations is not linear so vanilla Ax=b won't work.
hiker··on Machine learning is easier than it looks
Imo this would be hard if not impossible.

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.

hiker··on Coding Interview Tips
Not to mention, strings are immutable in Python.
hiker··on The Evolution of a Haskell Programmer
This is a Haskell insider-joke. As is the The International Obfuscated C Code Contest. You wouldn't judge the value of the C language for writing, let's say, a unix kernel based on the code from IOCCC, would you?

Don't take it so seriously.

hiker··on Haskell for Web Developers
Let me hoogle those for you (sic) http://www.haskell.org/hoogle/?hoogle=liftM =-)
hiker··on Haskell for Web Developers
The syntax in Haskell for dealing with side effects is tedious/verbose by design. The intention is to push one in writing pure programs since pure functions and compositions are easier to test, verify and reason about.

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).

hiker··on Physicists Create Quantum Link Between Photons That Don't Exist at the Same Time
What's the easy no-collapse interpretation explanation?
← PreviousPage 2 of 3Next →