4 ms·
not x not o ---------> o o -------> path-space | | | and | | or | V V
by YeGoblynQueenne 7y ago
not x not
o ---------> o o -------> path-space
| | |
and | | or |
V V |
o ---------> o V
not computation
Huh? I don't get it. This is supposed to be DeMorgan's in this weird notation. I know DeMorgan's but I don't get that diagram. I'm reading about path semantics via the links in the github but it seems to me you need to already have a bit of a background in a certain, shall we say, remote, area of either mathematics of computer science, or the mathematics of computer science in order to follow quickly without spending time going down wikipedia rabbit holes.
Anyway, sounds like an interesting thing to spend some free time on. Thanks.
Oh, please do ELI5 if anyone can.
- lmm 7y ago'not' and 'not x not' are paths, 'and' and 'or' are computations. ('not x not' is just the path on a pair that applies 'not' to each of the two elements - products are pairs, sums are either-or). Diagrams like this generally express a theorem as the diagram commuting. So the theorem is that if you compute 'and' and then lift the result along the path 'not', that's the same as lifting the input along the path 'not x not' and computing 'or'. More mind-bendingly, but ultimately more powerfully, it's also the statement that if you lift the whole computation 'and' along this kind of higher-level path that applies 'not' to everything, the result is 'or'.
- carapace 7y agoOh! 'not ⨯ not' I thought 'x' was maybe a variable or something.
- tom_mellior 7y ago> 'not' and 'not x not' are paths What's a "path", though? Why is it not a computation to map 0 to 1 and 1 to 0?
- andrewflnr 7y agoThey seem to be maps between computations. Seems to me that should be a computation on other computations, but I'm sure it's simpler to have nice distinct levels. Honestly I'm confused why you're asking, since I understood that example based on your diagram below...
- tom_mellior 7y agoIn my diagram everything is a computation (as I understand it): From (a, b) you compute and(a, b), from which you compute not(and(a, b)). Alternatively, from (a, b) you compute (not(a), not(b)), from which you compute or(not(a), not(b)). The "and" and "or" steps are applications of functions, i.e., computations. The "not" steps are also applications of a function, why aren't those computations? I guess you might say that applying the function (not x not) is somehow a higher-order "computation on other computations", so that step might be a "path" (if that's the meaning, the term is ridiculously badly chosen). But the bottom edge is simply applying the "not" function to some binary data.
- YeGoblynQueenne 7y agoSo a path is a higher order function? But then why is not also a path?
- YeGoblynQueenne 7y agoAlso confused about this, btw. Why are some functions "paths" whereas other functions are "computations"? Additionally, I honestly share no intuition that the term "path" is meant to convey. At a very big guess it sounds to me like the "path" that a bit takes through a theoretical computing machine of some kind. But I really don't understand the term.
- lmm 7y agoIt's (at least usually; it sounds like this guy is doing something non-standard) meant to give you the intuition of a path through a space - a line from point a to point b that possibly wiggles about a bit in between. Formally it's a continuous function from [0, 1] to the space that sends 0 to a and 1 to b - so if p is a path then p(0.5) is "halfway along" the path, p(0.25) is a quarter of the way along the path, and so on. The concept of a path in the space {true, false} is kind of trivial - any function into that space is (topologically) continuous - but the intuition should be something like a path between two points on a 2D plane.
- Thiez 7y agoNobody except the author seems to understand "path semantics". https://old.reddit.com/r/rust/comments/bn5eoz/since_some_people_here_are_so_supercritical_to/ https://old.reddit.com/r/rust/comments/bn5eoz/since_some_peo...
- adamnemecek 7y agoI talk to the author a bunch and I believe some of this work is based on our convos. I don't fully understand path semantics however, I can tell that it's similar to my pet theories. Path semantics is still very much a work in progress so it's hard for outsiders to really get into it.
- pwdisswordfish2 7y agoI would expect a theory that has been a ‘work in progress’ for some five years now to have a readily available, comprehensible introduction to its basic concepts and motivation at the very least. I am yet to see such.
- adamnemecek 7y agoThe theory is still changing. Five years is not that long of time period.
- bo1024 7y agoSome research papers at least?
- pwdisswordfish2 7y agoSurely it can’t be changing so much that it’s impossible to produce an accessible explanation of the fundamentals. For comparison, it took about four years from Voevodsky formulating the univalence axiom to the publication of the HoTT book.
- adamnemecek 7y ago
- tom_mellior 7y agoPoint-free notation is used here mainly as a device for obscuring notation. A function "f x g" pairs up f and g and applies them separately to a tuple of arguments: (f x g)(a, b) = (f(a), g(b)). The commutative diagram becomes clearer when we label the points: not x not (a, b) ---------> (not(a), not(b)) | | and | | or V V and(a,b) ---------> not(and(a, b)) = or(not(a), not(b)) not (This is the same as what user lmm wrote in prose in https://news.ycombinator.com/item?id=23203478. https://news.ycombinator.com/item?id=23203478.) As for what "path-space" notation means, even the author appears confused, since they claim that "and[not] <=> or" corresponds to "If you flip the input and output bits of an `and` function, ..." corresponds to "not(and(a, b)) = or(not(a), not(b))", but this clearly isn't the case: flipping both the inputs and outputs of `and` to get `or` would be "not(and(not(a), not(b))) = or(a, b)".
- YeGoblynQueenne 7y agoThanks, annotating the points does make it easier to follow. For some reason I misunderstood the purpose of this to be getting rid of arguments to functions so it didn't occur to me to do what you did (well, in my head).