In Haskell and PureScript, Monad is a typeclass just like any other.
They are an abstraction, effectful computation is not inherent to them, they represent computational contexts, e.g. the list monad is used to model non-determinism, the maybe monad represents computations that can fail, both of these are pure.
See this is the kind of thing that made learning Haskell so hard for me. I'm not a math guy, I'm terrible at math. I have no idea what "non-determinism" means, and I'd venture to guess that list monad is used to model "ordered collections of things".
Scala calls the monad bind "flatMap". Java actually implements it for Streams.
If you have a `Stream<Deck> decks;` of card decks, and want to get all the cards from all the decks, you might try to do something like `decks.map(deck -> deck.getCards().stream())`, but that will give you the type `Stream<Stream<Deck>>`. That sucks, we just want a single stream, not a stream of streams, so we call the function that flattens at the same time. `decks.flatMap(deck -> deck.getCards().stream())`.
Nondeterminism is just a standard use for this construction: given one choice, generate more choices, given that choice, generate more choices, do some computation with the choices, and then return the list of possible final results.
I'm not a math guy either and I did indeed find it difficult to penetrate the inner sanctum of Haskell for this very reason. I won't say I've completely succeeded in that effort, but I've come quite a long way.
I'm fairly certain that in this context, non-determinism means that there can be more than one answer/result.
See, to me, the sequence of keypresses I make while banging on my keyboard seem like it could be represented as an ordered list. I may be missing something, though.
If something is unordered it does not mean it may not be ordered. It only says you cannot assume that it is ordered. (A Collection in Java/C# is an unordered contract, but a List is also a Collection.)
But the idea of a list also suggests an ordering to me.
A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1.
An oracle is a black box that can solve a particular decision problem in O(1).
The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT.
It gets really ingesting because there are particular oracle machines for which P^X == NP^X.
Off topic (but related to almost surely), one of my favourite theorems is Pólya's recurrence theorem which says that a simple random walk on Z^d (lattice) is recurrent for d=1,2 and transient otherwise, so if you get lost on a 1 or 2 dimensional grid, just execute a simple random walk and you'll get back to the origin almost surely! IIRC the probability of recurrence is about 34% in 3d.
This result is slightly less interesting that it sounds. "an oracle X chosen uniformly at random from all oracles" is also called a "random oracle", more commonly referred to nowadays as a cryptographically secure pseudo-random number generator. So what this is really saying is that "an oracle X chosen uniformly at random from all oracles" is almost certain to not do anything more interesting than produce numbers that indistinguishable from random, and hence cannot be compressed. So yes, it's a cool result, but not quite as earth-shattering as it may appear to be at first glance.
The Sipser book is excellent. It's one of only a handful of textbooks I decided to keep after I graduated from university. And perhaps the only one I kept because of how good it was rather than because the campus bookstore wanted to give me a pittance for it... and I didn't even buy the book until after the semester when I had to return the copy I'd checked out from the library...
I later on picked up the first two editions of Hopcroft & Ullman for $1 each at a used book store. I don't think either edition can really hold a candle to the Sipser book, which is shorter, more thorough, and (imo) easier to understand.
One caveat: it's super-expensive. I'd recommend finding a used copy or even an "international edition" (which will be soft-cover rather than hard-cover, but the content is the same).
I bought Sipser for this very purpose. I found it very difficult without being able to discuss it with anyone to clarify my understanding of the ideas. I would love to work through it, but would need a CS tutor to help me... any takers? ;)
Edit: to be honest it's the maths notation that is a big barrier for me. Until one can read it relatively fluently it's very hard to translate the ideas into a meaningful mental model .
"Meta Math!: The Quest for Omega" by Gregory Chaitin [0] was my introduction to the theory of computability [1]. I found it enjoyable and approachable.
This 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context. I've shown this to plenty of friends (including those outside of computer science).
Essentially, "does being able to quickly recognize correct answers mean there's also a quick way to find them?"
What does it mean to take a random oracle from all oracles? How do you enumerate oracle-space? Is that something like the space of all problems, where each problem corresponds to an oracle for that problem?
Another way to enumerate oracles is to consider the set of terminating Turing machines (and enumerating them is itself uncomputable but whatever). Each TM corresponds to an oracle that computes its result in O(1).
> A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1.
Wait, this has to be conditional on something. If P = NP, then P^X = NP^X for any oracle X, right? (It's been a while since my theoretical CS class, so maybe it's my naïve assumption that's not true.)
> If P = NP, then P^X = NP^X for any oracle X, right?
No, surprisingly, it's not true!
The problem is that a nondeterministic turing machine can ask "more" or "better" questions of an oracle than a deterministic one. Intuitively, it can ask an exponential number of questions and then accept if any of the answers turn out to be "useful".
So even if we know they solve the same problems when unaided by an oracle, this doesn't imply that an oracle amplifies their abilities in the same way.
It's tricky and the notation confuses things a bit.
P and NP are not the machine, but the set of problems solvable by deterministic/non-deterministic Turing machines limited to a polynomial number of steps. P^X is set of problems solvable by a deterministic Turing machine with access to oracle X, which is fairly straight forward, but need have little to with P. Similarly, NP^X is the set of problems solvable by a non-deterministic Turing machine with access to oracle X. However, this means if there's any input it could ask X to get an answer it can use to solve the problem, it can solve the problem, which may be vastly more efficient than trying to construct the right question to ask.
Essentially it boils down to:
Just because two different models of computation can solve the same problems, does not mean that when augmented by the same oracle can solve the same problems (they can access the oracles in different ways).
> Essentially it boils down to: Just because two different models of computation can solve the same problems, does not mean that when augmented by the same oracle can solve the same problems (they can access the oracles in different ways).
Indeed, it was just the worry that something nasty like this could happen that made me weasel my initial definite assertion into the form of a question. Thank you for this informal explanation; it nicely complements openasocket's formal reference (https://news.ycombinator.com/item?id=12893077).
(Long-delayed post because "You are submitting too fast".)
Thanks for that reference! I am glad that, even if my intuition led me astray, at least I had the foresight to append the weasel "… right?" to the end of my false claim. :-)
> If P = NP, then P^X = NP^X for any oracle X, right?
Edit: No, I think. See child comment by JadeNB.
Probably wrong {
Yes, since we could just not invoke the oracle. But people do this sort of stuff to study it backwards e.g. what do P^X and NP^X (and any class^X) tell us about P and NP (and any other class).
}
I hope this is clearer, let {A, B, C, ...} be the set of all oracles.
For TM + A:
P^A is the class of problems that can be done in P time on this machine.
NP^A is the class of problems that can be done in NP time on this machine.
Similarly for
TM + B
TM + C
...
This theorem says that if we choose one of these oracle machines uniformly at random then P =/= NP in _its_ model of computation a.s.
This is an entirely probabilistic statement about machines that are more "powerful" than standard TMs.
I think that only shows that P^X contains P and NP^X contains NP, not that P = NP implies P^X = NP^X. Indeed, my supposition that this implication holds seems to be false; openasocket (https://news.ycombinator.com/item?id=12893077) points to a paper mentioning a specific example of an oracle B so that P^B \ne NP^B. If my naïve reasoning were correct, then we'd be able to deduce that P \ne NP; but we famously can't.
It's great people are exploring this problem space, but so far nothing comes close to https://www.passwordstore.org/ which is just a wrapper around gpg and git. It has Android/iOS clients, as well as GUI clients.
On Android I use Password Store + OpenKeychain, the UX with a YubiKey is very smooth.
I was using this for ~4 years and really liked it, but recently I've been using 1Password. I tried 1Password as it has a family plan, that didn't really work out though (getting non-technical people to use a password manager is hard - so I'll forever keep being asked "What's the Netflix password?"), but I have stuck with it for myself.
I really like the browser integration, which there isn't anything comparable for pass. I had a bash script [0] which when run would pull the current URL from my browser, and run pass to generate or copy the password to the clipboard - but the 1Password extension is so much nicer. If I'm on a site with weird requirements I'd have to figure out the params to make pass generate a password which matched it; with the extension I just click a few buttons.
I've also got hooked on the iOS app. I didn't know there was one for pass, but it looks rather basic compared to 1Password [1]. 1Password also supports TOTP, so you don't need a seperate app for that - although for security you probably should.
Maybe one day I'll get around to writing my own extension and app for pass, but for now paying $60/year is worth it for me. I don't pay for many apps/services, but this I find really worth it.
>> 1Password also supports TOTP, so you don't need a seperate app for that - although for security you probably should.
It goes way beyond "probably should" regarding security. You're giving a single company not only potential access to your usernames and passwords, but also your last line of defense - TOTP generation. That combination of apps put everything in reach of one company to fuck you over.
Using a password manager that is being coded and maintained by a random everyday software company should be the only concern anyone has over even considering using such an app. That one company has the ability - whether intentionally or via being hacked - to release an update to any of their client apps that sends your entire database, decrypted to plaintext, to any server in the world.
Can you think of any scenario where someone slips in a 2-line commit to one of their client apps that sends your decrypted database to any server of their choice? We're talking about one disgruntled employee who decides they would like access to millions of users' most sensitive credentials. Or perhaps a single firewall opening or social engineering attack away.
It blows my mind that anyone would put this much trust in any for-profit password manager. Every month we hear about yet another major hack against software companies. One day soon, such a hack will happen to 1Password or LastPass, and the majority of their customers are going to have their entire lives (logins to bank accounts, government portals, etc.) exposed.
Such an eventuality cannot be defended against. It will start and end in less than 48 hours thanks to auto-updating applications, and will affect millions.
After lastpass was bought out, I went on a spree to find a different password manager and in that process, I tried almost all of them (free & paid). Nothing came close to Lastpass so I decided to stick with them until they mess up.
If the worst comes to worst, I'll probably move to Dashlane (which is significantly more expensive & a bit more work to use - extensions won't work without a desktop app)
I did try 1Password, and while it was pretty good, it was never "great". By that I mean,
1. It required a desktop app to be installed to use the clients (while this is an issue with Dashlane, the 1Password windows desktop client is just weird - looks outdated, crashes etc.)
2. The 1Password Android app seemed to not have in-app password fill in (which both Dashlane & Lastpass had). While it's not too much of an inconvenience, I feel like 1Password is great if you are in the apple ecosystem.
This is not to say 1Password is "bad" by any means...I loved it's dropbox sync feature for example and it's integration with Alfred on Mac was awesome!
I think you misunderstood my comment. I meant that there isn't anything comparable to 1Password's browser integration for pass (https://www.passwordstore.org/).
As an android user, I've tried 1password and it's pretty much the worst password experience on the platform. The Android client can't generate passwords, and it also can't cache my passphrase for any amount of time if I'm using the 1password keyboard (which is, as far as I can tell, the only way to make 1password fill a field.) After typing my fairly long passphrase 10x a day on the fiddly 1password keyboard with no feedback for the past few weeks, I'm switching to pass.
I understand that 1password on iOS doesn't interact as a third party keyboard, and 1password is an iOS/mac app first and foremost, but that's no excuse for making their Android UX so incredibly frustrating.
I've been using passff[0] with a lot of success for an in-browser pass client with filling support and so on. Works really well.
My understanding is that Chrome makes it difficult to have this kind of thing due to it's sandbox. There was some talk of exposing pass over the network locally so there were no sandbox concerns.
> If I'm on a site with weird requirements I'd have to figure out the params to make pass generate a password which matched it; with the extension I just click a few buttons.
How does this work? I don't suppose there's a micro format for password requirements? Does 1password just have a database of password formats for popular websites?
Pass doesn't have a sane iOS app. The only app available for Pass requires a jailbreak and doesn't function on phones without Cydia, GPG, and an SSH daemon running.
You can use a hash of the site appended with a .pass wide pepper as the name of the directory storing credentials for a particular site, then use a wrapper script that hashes its input before passing it to pass.
This is all a lot of effort, if I went down that road I might as well skip "pass" and handle the passwords myself. What I like about pass is that there isn't much setup.
Full disk encryption also doesn't prevent a running application from seeing the directory structure. But I guess this is not a very realistic attack vector.
Not to shamelessly self promote, but if you like pass but hate GPG, then I already built you a command line password manager that is almost exactly the same as pass
It can securely save files, generate passwords, save passwords and optionally can sync using git.
GPG is well known to have a very clunky interface. It also is based on very old crypto (we know it works against the NSA, but we also know that it has problems that other crypto doesn't).
I don't think it supports any browsers via plugin. You use a separate app to unlock your keychain, it places the relevant password on your clipboard and then it clears the clipboard 30s later. Very simple and therefore avoids a whole bunch of vulnerabilities other password managers (like LastPass) introduce by integrating with browser plugins.
However I think the parent might be concerned that OWS could be compelled to change their server code to log more meta data, currently we must trust them.
For (b)
Not sure what could be done about this, maybe an independent service audits each release, subsequent audits would take less time since the diff of the code base would be small. Don't really know, I'd like to know of there are any solutions to this, it seems less like a technical problem than the others though.
On (d)
Using GCM means Google can get all the meta data too if they want/are compelled to. This is a legitimate concern but OWS is very clear what signal does, they don't claim to tackle e.g. traffic analysis. A world with everyone using end to end encryption would be much closed to the crypto-utopia.
I'm on Windows + iOS (which says a lot about how much tinkering I like to do with tech :D ).
When it comes to ease of setup and general UX polish every open solution leaves a lot to be desired. In the choice between insecure and cumbersome, insecure wins every time. Case in point: gmail is what people want in terms of usability. A more secure solution (such as any pgp solution on standalone mail client) is not really an option.
Really nice to seem doom9 mentioned. Doom9 is one of those places that I used to frequent a lot. That knowledge saved me a lot of learning in university :)
Sadly also one of those places where I forgot both the password to my account and the gmx email doesn't exist anymore. It's a shame, the account is from 2001.
[1]: http://www.purescript.org/