00:00:02 -!- danieljabailey has quit (Quit: ZNC 1.6.4+deb1 - http://znc.in).
00:00:17 <shachaf> Some map data structures support iteration
00:00:20 -!- danieljabailey has joined.
00:01:08 <wob_jonas> This is partly for eso reasons, because I'll use a somewhat eso dictionary structure, one that's slower than typical implementations although still much faster than linear scans;
00:01:30 <wob_jonas> and partly because I want to write the reference interpreter in portable C, and there's basically no portable implementation of dictionaries with a C interface.
00:02:41 <wob_jonas> shachaf: no. I mean not in any library I know of, if you want an implementation that's both portable and its interface isn't restricted to unusable.
00:03:09 <wob_jonas> Um, and of decent performance. I don't count using the file system as a dictionary from filenames.
00:03:24 <shachaf> What are the keys and values?
00:03:39 <shachaf> I'm typing on my phone right now, haven't even seen the beginning of the conversation
00:04:08 <ais523> I don't think it was stated yet
00:04:53 <wob_jonas> The keys are strings with characters from a limited character set of around 70 characters or so, of ideally arbitrary length, but definitely at least as long that you shouldn't store them in fixed length arrays;
00:05:24 <wob_jonas> the values don't matter much, let's say they're indexes into an array in the interpreter's memory.
00:05:46 <wob_jonas> You can always just use indexes as values like that for any dictionary, and store the real values indirectly.
00:06:33 <wob_jonas> And it happens to be convenient for this language because there'll be a lot of repeated values, and in many programs some of them will be longer than an index.
00:09:48 <shachaf> Oh, maybe that doesn't help you.
00:12:32 <wob_jonas> Oh, I should look in Knuth's free software (TeX, Metafont, MMIXware, Standford Graph Base). Maybe they have a suitable implementation.
00:12:49 <shachaf> Oh, hsearch, that's the one I was thinking of.
00:13:30 <shachaf> "First a hash table must be created using hcreate(). The argument nel specifies the maximum number of entries in the table. (This maximum cannot be changed later, so choose it wisely.)"
00:14:06 <shachaf> This is a pretty scow library.
00:15:11 <wob_jonas> I looked at the search tree functions in GNU libc, which may overlap with this. I found that they had a really bad interface, one that seriously limits how you can use them. I thought they were specific to GNU libc though, and GNU libc is very non-portable.
00:15:43 <lambdabot> https://gist.github.com/tonious/1377667
00:15:57 <wob_jonas> (As in, it runs on Linux and Hurd, and needs a wizard to compile it, despite that the GNU GPL explicitly forbids distributing a program in a state where ordinary people can't compile it.)
00:16:09 <shachaf> Just use something like that.
00:19:21 <wob_jonas> The POSIX search.h functions, both the hash and the tree ones, are limited to one hash table or tree in the entire program, and don't allow ordered access (lower_bound). That would technically still allow implementing my language, but I dislike that on principle.
00:19:56 <shachaf> They're awful, ignore whatever I said about them.
00:20:07 <wob_jonas> Also it requires a global comparison function with no cookie argument, like qsort.
00:20:58 <wob_jonas> Older versions of gcc might have an implementation I can steal.
00:22:03 <shachaf> I thought you were looking for a simple implementation.
00:22:51 <wob_jonas> But then if it's something in an already well-known software, then I could sort of count it as simple in the same way as just using malloc or some other widely used library function as simple.
00:23:07 <shachaf> What's the interface you need?
00:24:40 <ais523> wob_jonas: Perl has hash tables as a primitive
00:24:42 -!- sleffy has quit (Ping timeout: 252 seconds).
00:26:44 <wob_jonas> I need one dictionary per interpreter (and one interpreter per process in the reference interpreter), initializing it as empty or some other known state, looking up a string key with a fatal error if it's not present, or inserting a pair in such a way that if it's a new key, the key is copied to a permanent storage array and the tree will reference
00:27:22 <wob_jonas> That is, I don't want to keep a new copy of the key in memory forever each time I overwrite the pair for it in the tree.
00:28:40 <wob_jonas> Both lookup an insert/overwrite shall be fast. I don't need ordered lookup or iteration.
00:29:55 <wob_jonas> Ideally I'd like an interface that easily allows to have multiple instances per process, so that someone can modify the reference interpreter to multiple instances per process, in which case I also need deallocation of the whole dictionary.
00:30:27 <wob_jonas> Delete would be a nice extra, but I don't insist on it, because I know it complicates implementations a lot.
00:30:49 <wob_jonas> And if you actually want to use delete, then you also need a malloc to store the keys and be able to free them.
00:31:26 <wob_jonas> Otherwise you'll have two copies of the key in memory when the key gets recreated after deletion.
00:31:39 <wob_jonas> That would be worse than just not deleting anything.
00:33:07 <wob_jonas> A malloc/free system is, in theory, on the same order of magnitude to implement efficiently as a dictionary. The main difference is that malloc is available in C, so everyone has it.
00:33:23 <wob_jonas> ais523: yes, I know perl has one, and so does almost every modern programming language.
00:33:58 <ais523> some languages, e.g. OCaml, do it via the standard library rather than as a primitive
00:34:26 <shachaf> Is Perl's primitive a hash table or a dictionary?
00:34:33 <wob_jonas> shachaf: "<b_jonas> I will write my own implementation for the reference interpreter of the language. / This is partly for eso reasons, because I'll use a somewhat eso dictionary structure, one that's slower than typical implementations although still much faster than linear scans;
00:35:08 <wob_jonas> ... / and partly because I want to write the reference interpreter in portable C, and there's basically no portable implementation of dictionaries with a C interface."
00:35:45 <wob_jonas> and yes, it's in the standard library for most languages where that distinction is important.
00:35:48 <shachaf> Not being ordered doesn't mean it's a hash table.
00:35:49 -!- sleffy has joined.
00:36:13 <wob_jonas> Ruby has has tables as a primitive, python has them and I think they're a primitive,
00:36:21 <wob_jonas> C++ and rust has them in the standard library.
00:36:30 <wob_jonas> C++ and rust have ordered versions.
00:36:45 <HackEgo> [wiki] [[Small]] https://esolangs.org/w/index.php?diff=53124&oldid=52212 * Get52 * (+1) github changed
00:36:46 <wob_jonas> shachaf: yes, but I also know perl implements it as a hash table
00:37:06 <wob_jonas> and they're not even trying to change that, they're just disputing what the Right**TM hash function is to use
00:38:30 <wob_jonas> The perl and rust devs are both worried that a hash table can have security problems because in programs that use untrusted data as keys, the people providing that untrusted data can make a denial of service attack by making the hash table perform badly;
00:38:54 <wob_jonas> but they're both trying to solve it by making a hashing function that's both fast and secure, which I think is theoretically impossible,
00:39:26 <ais523> wob_jonas: what's wrong with siphash?
00:39:49 <wob_jonas> because the cryptography guys have done serious research about how fast you can make a digest that is probably cryptographically secure, and it's still slower than anything the perl and rust guys are trying, and
00:40:16 <wob_jonas> I think a cryptographically secure hash function (with the key never revealed) is the only way to guarantee no suboptimal performance.
00:40:36 <ais523> wob_jonas: there's more than one way to be cryptographically secure
00:40:55 <wob_jonas> ais523: sure, and I have no proof and don't know cryptography, so this is just my conjecture
00:41:41 <ais523> siphash is meant to be cryptosecure when used as a MAC (which is the security guarantee you need for a hash table) but not for other uses of a cryptohash
00:42:08 <wob_jonas> I personally think people should just use balanced trees or something like that with performance guaranteed by deterministic bounds for almost every cases when this consideration is relevant, except perhaps in some cases in operating system kernels.
00:42:26 <ais523> (basically, the security property it's claimed to have is that you can't choose X and Y so that siphash(k, X) == siphash(k, Y) unless you know k)
00:42:57 -!- tromp has joined.
00:43:09 <wob_jonas> ais523: you can't even chose them that way if you get feedback of the order of hashes of any number of keys you construct?
00:43:44 <wob_jonas> ais523: also, this gets ugly because even that is probably only enough if separate secret keys are used for each hash
00:44:03 <ais523> wob_jonas: the property's actually slightly stronger; it says that you can't choose X and Y so that siphash(k, X) == siphash(k, Y) unless you know k, even if you know siphash(k, Z) for arbitrary Z
00:44:11 <wob_jonas> otherwise the attacker can experiment on one hash to make another hash behave badly later
00:44:25 <ais523> so the idea is that you choose k randomly per program
00:44:32 <wob_jonas> by just using the same keys in the order they're in the first hash
00:44:47 <ais523> hash tables only break upon hash /collisions/
00:44:54 <ais523> merely inserting elements in hash order doesn't break must hashing algorithjms
00:46:31 <wob_jonas> ais523: yes, but when you have hashes of multiple sizes, then the smaller hashes use shorter hash keys that are made from the longer hash keys in simple ways that allow the attacker to make collisions in the smaller has by learning about the keys in the longer hash
00:47:01 <wob_jonas> As in, if the key for the shorter hash is the upper bits of the keys of the longer hash, then keys close to each other in the large hash will often collide in the large hash,
00:47:20 <wob_jonas> but other simple methods of creating shorter hash indexes have similar problems.
00:47:35 -!- tromp has quit (Ping timeout: 240 seconds).
00:48:07 <wob_jonas> If I understand correctly, in some cases the devs defend from this by using entirely new random salts for each hash table, and each time they resize a hash table too.
00:48:19 <ais523> wob_jonas: but now you're adding 2**n elements to the large hash so that you can get n**2 performance adding them to the small hash
00:48:40 <ais523> you could just add 2**n elements to the small hash instead…
00:48:58 <wob_jonas> ais523: no, I don't think so. you're adding O(n) elements to one hash to add n elements to a second hash and get O(n) collisions
00:49:51 <wob_jonas> There might be some other way to defend from this attack that I don't know about though
00:50:04 <ais523> wob_jonas: actually, we're both wrong, you're adding O(n) elements to the hash, but only O(sqrt(n)) will have clashing top bits
00:50:16 <ais523> so the second hash has O(sqrt(n)**2) = O(n) performance
00:51:14 <wob_jonas> I'm not convinced, but that sounds more likely than exponential
00:52:35 <wob_jonas> An attacker can already force O(sqrt(n)) performance with just one hash after all, under some reasonable conditions.
00:53:40 <wob_jonas> Dunno. If you say this SIPhash solution could really work, then I should do more reading up on this,
00:54:37 <wob_jonas> because that would be interesting for me to know, even if I just want to avoid the original problem by using either separate passes of sorting and binary search, or a balanced tree or similar dictionary when I can't do that.
00:55:15 <wob_jonas> This because the cryptographical properties you say SIP provides might be useful for other problems,
00:55:28 <wob_jonas> or they might not, I don't know, that's why I'll have to read up about it.
00:56:35 <wob_jonas> There's a particular problem I have in mind that I can so far only solve with similar strong crypto stuff like good message digests, but might have a faster solution under some conditions.
00:56:59 <wob_jonas> I don't think a balanced tree helps there.
01:01:54 -!- clog has joined.
01:01:59 -!- sebbu2 has changed nick to sebbu.
01:03:24 <wob_jonas> Here's the problem. My server communicates with multiple parties that I don't trust and that don't trust each other. When any party asks, I must give them a new unique ID token.
01:04:35 <ais523> that doesn't seem so bad so far
01:05:06 <wob_jonas> Nobody shall be able to guess that ID unless I or that party transitively gives information about the ID to them. But also, nobody should be able to examine the tokens to learn about how many tokens I've generated in any time interval, or when any token they see was generated, except that I've generated at least as many tokens so far as they've see
01:05:06 <wob_jonas> n, and at least as many in an interval as they asked for.
01:05:50 <wob_jonas> The parties may learn about some of this from timing attacks, which seems very expensive to avoid, but they shouldn't learn such information directly from examining any number of tokens.
01:06:15 -!- Phantom_Hoover has quit (Read error: Connection reset by peer).
01:06:23 <wob_jonas> One solution for this is to use 256 bit long cryptographically secure uniform random strings as tokens.
01:07:09 <wob_jonas> There are well-tested libraries for doing that, and it's essentially as hard as computing one or two 256 bit long message digests.
01:07:26 <wob_jonas> I don't think there's a solution for this involving just sequence numbers and no cryptographic operations.
01:08:43 <wob_jonas> There might or might not be crypto solutions that are easier than a HMAC, and this is what I should find out.
01:09:05 <wob_jonas> Or faster than a HMAC, or even faster than a message digest, like as fast as a SIP hash or two.
01:10:48 <ais523> right, you're basically just trying to generate random numbers, but have weaker security requirements
01:10:55 <ais523> so are hoping that you might have something faster than a CSPRNG?
01:11:27 <wob_jonas> I don't know what to think. I thought there isn't anything faster than that, but after what you said about SIP hash, I'll have to reexamine that assumption.
01:12:12 <wob_jonas> I'm also somewhat fuzzy about where there seem to be two essentially different requirements called cryptographically secure PRNG,
01:12:48 <wob_jonas> one of which seems to require as many non-pseudo hardware random entropy as bits output, and one that uses much fewer bits than that.
01:13:05 <ais523> the full CSPRNG requirements are that a) you can't predict any future outputs or any internal state given all past outputs, b) you can't predict any past outputs given the internal state
01:13:20 <ais523> several applications that would typically use a CSPRNG don't actually care about b)
01:13:22 <wob_jonas> I have the impression that the first kind is recommended for generating keys for public key cryptography, but I don't understand why there's a distinction in first place.
01:13:33 <ais523> e.g. NH4's RNG is intended to obey a) but definitely does not obey b)
01:16:12 <wob_jonas> And if you want (a) and (b), then you want as much incoming entropy as outgoing; but when you want only (a), then you don't need that?
01:16:38 <ais523> wob_jonas: this is more to do with security levels
01:17:00 <ais523> say you have a CSPRNG with a 256-bit internal state, you can't then get more than 256 bits of security on keys generated from it
01:17:03 <wob_jonas> I also don't understand why some crypto libraries only seem to provide the first kind of CSPRNG but not the second, despite that the first kind is slow on many hardware in most cases.
01:17:12 <ais523> because you could just brute-force the CSPRNG itself rather than the resulting key
01:19:07 <wob_jonas> Yes, but for currently used public key cryptography, such as RSA, the public key itself is much longer than the entropy you need, because you can factor numbers much faster than with brute force, right? So if you generate a 1024 bit key with 256 bit entropy, then the fastest way to factor your key is faster than brute forcing 256 bits of seeds.
01:19:40 <wob_jonas> Or is the difference important only for generating more random output than just a single public key?
01:20:04 <wob_jonas> Like, generating several Diffie-Hellman keys?
01:20:14 <ais523> well, certainly you don't want to generate so many keys on the same seed that brute-forcing the seed is faster than individually factoring the keys
01:20:29 <wob_jonas> Or even for generating multiple symmetric crypto keys.
01:21:01 <shachaf> Is there any reason to use RSA nowadays?
01:21:05 <wob_jonas> Generating lots of symmetric crypto keys comes up a lot with public key cryptography, do you need the stronger guarantee for that?
01:21:34 <wob_jonas> shachaf: I think this applies not only to RSA, but also for most other public key schemes used nowadays
01:24:44 <wob_jonas> ais523: so is the weaker CSPRNG guarantee enough for the unique ID problem I asked?
01:24:58 <ais523> wob_jonas: I'd think so
01:24:59 <wob_jonas> And does a proper implementation of the weaker CSPRNG need two or just one calls to a digest? I guess I can find that out by reading the source code of tomcrypt
01:25:10 <ais523> at least, I'd be surprised if a security audit told you off for using /dev/urandom there
01:25:15 <ais523> however, I'm not a crypto expert
01:25:18 <ais523> so I may be wrong about all this
01:25:58 <wob_jonas> I'll leave soon because it's late.
01:33:07 -!- oerjan has joined.
01:33:35 <shachaf> I wrote a hash table implementation without delete support. Seems pretty straightforward.
01:34:00 <shachaf> I guess I'd never implemented it before because I don't like hash tables that much.
01:35:45 <oerjan> . o O ( did you make a hash of it )
01:36:51 <wob_jonas> shachaf: yes, but it still makes the implementation longer
01:37:41 -!- tromp has joined.
01:37:54 <oerjan> eep, tunes was away for nearly a day
01:39:13 -!- erkin has quit (Quit: Ouch! Got SIGABRT, dying...).
01:39:28 -!- sleffy has quit (Ping timeout: 248 seconds).
01:41:44 -!- tromp has quit (Ping timeout: 240 seconds).
01:46:50 -!- sleffy has joined.
01:48:02 -!- imode has joined.
01:50:32 <shachaf> What tricks are there for implementing key-value maps efficiently other than ordering and hashing?
01:51:11 <wob_jonas> shachaf: I know one trick that requires ordering but not anything that looks like a tree, and I'll try to use that in my reference implementation.
01:51:24 <shachaf> I guess a prefix tree is another popular one.
01:51:26 <wob_jonas> I don't recommend it for most non-eso purposes though.
01:51:43 <wob_jonas> A prefix tree still counts as ordering.
01:51:58 <shachaf> I would say that an array that you binary search still looks like a tree
01:52:13 <wob_jonas> Oh, in that case this still looks like a tree.
01:52:19 <shachaf> No, prefix structure is more than order structure
01:52:42 <shachaf> A < function isn't sufficient to implement a prefix tree
01:52:59 <shachaf> Also using prefix trees you can sort in linear time?
01:53:20 <wob_jonas> It's more than order structure, sure, but then a balanced tree or a treap or a self-balancing tree is also more than order structure I think.
01:53:32 <imode> is there any cellular automata software that allows arbitrary spaces? as in, CAs on arbitrary graphs or implicit spaces or.. something.
01:53:41 <shachaf> I'm talking about the structure of the keys themselves
01:54:26 <wob_jonas> shachaf: my trick (and I have invented this independetly but I think it's known) is to use a set of sorted arrays of key-value pairs with power of two size, no two of the same size.
01:54:47 <ais523> shachaf: prefix trees are basically an optimized version of radix sort
01:54:52 <wob_jonas> to find an element, find it in each array, which takes O(log**2 n) time
01:55:00 <ais523> so they're O(n) if you have a fixed number of possible keys
01:55:27 <shachaf> wob_jonas: Oh, sure, that's a good trick
01:55:38 <wob_jonas> to insert an element, add a length 1 array, then while there are two arrays of the same size, merge those two arrays to an array twice the size, keeping duplicate keys but keeping track of which one is newest
01:55:46 <ais523> wob_jonas: that's basically a trie, isn't it?
01:55:52 <shachaf> Though you can do it more generally than powers of two, and sometimes there are benefits to other counting systems
01:56:05 <shachaf> For example skew binary works well
01:56:36 <wob_jonas> this takes amortized O(log**2 n) time
01:56:38 <shachaf> It's also the rough idea behind databases like Bigtable?
01:56:49 <wob_jonas> to insert an element, add a length 1 array, then while there are two arrays of the same size, merge those two arrays to an array twice the size, keeping duplicate keys but keeping track of which one is newest.
01:57:03 <wob_jonas> this also helps remove an element.
01:57:47 <shachaf> I'm typing on my phone so I can't type very quickly
01:58:00 <wob_jonas> shachaf: I'm not sure. I know this method also lets you keep snapshots of older versions of the dictionary cheaply, which I think Bigtable or some such db promises, but there are other ways to provide that, and I don't know how they actually implement it.
01:58:13 <wob_jonas> ais523: I don't think it's similar to a trie.
01:58:29 <ais523> ah right, no, I misunderstood how it works
01:58:35 <ais523> it's more like a skiplist, but not the same
01:58:44 <wob_jonas> Yes, skiplists are very similar and more popular.
01:59:08 <wob_jonas> Iirc skiplists differ in that they need randomness.
01:59:25 <ais523> isn't this faster at accessing more recently added data? that might be a useful property in some cases
01:59:28 <wob_jonas> Unlike a trie, this structure only needs key comparisons,.
01:59:36 <shachaf> I can't remember what this data structure is called
01:59:51 <wob_jonas> shachaf: I don't know any name for it either
02:00:26 <wob_jonas> ais523: theoretically yes, but it's so slow in general even for accessing recently added data that if you want that, you'll still use balanced tree or self-balancing tree structures
02:01:01 <wob_jonas> also, this structure can be deamortized, which you need to make persistent snapshots actually, but that makes the implementation more complicated
02:01:27 <wob_jonas> deamortized as in making a version that guarantees non-amortized deterministic upper bound on insertion time
02:02:50 <wob_jonas> and I think it can be deamortized while still being O(log**2 n) time, as opposed to O(log**3 n) which you might think if you just know that an array can be deamortized to a complete binary tree with log speed loss
02:04:49 <shachaf> wob_jonas: How about "cache oblivious lookahead arrays", or "fractal trees"?
02:05:05 <wob_jonas> I haven't even seen a good reference for this data structure, even one that doesn't give it a nice name. In particular, I don't think it's in the current TAOCP, nor in the Chris Okasaki persistent data structures book, nor in anywhere else.\
02:05:16 <wob_jonas> shachaf: I've no idea what those are
02:05:30 <shachaf> I'd look them up but it's very annoying in my
02:05:57 <shachaf> Is that the thing you're describing?
02:06:17 <wob_jonas> shachaf: anyway, deamortizing is easy, just do the merges with the steps delayed compared to one another just fast enough that each merge result is ready by the time you have to merge that one with a new array
02:06:34 <wob_jonas> in each step, do a constant number of merge steps at each level
02:06:53 <wob_jonas> or you can do a constant number of merge steps total
02:07:39 <wob_jonas> The bad part of this structure is that lookup still guarantees only O(log**2 n) but Omega(log n) time,
02:08:16 <wob_jonas> and I don't think you can fix that without turning it into some other structure in disguise with extra unnecessary complications added.
02:08:26 <shachaf> See these slides for example http://ekmett.github.io/presentations/Cache-Oblivious%20Data%20Structures.pdf
02:09:11 <shachaf> I don't like how skip lists are randomized
02:09:22 <wob_jonas> shachaf: it's too late for me to try to read that now, but thanks for the reference, if I don't get back to it, feel free to point it out again
02:09:52 <shachaf> @tell wob_jonas See these slides for example http://ekmett.github.io/presentations/Cache-Oblivious%20Data%20Structures.pdf
02:10:05 <shachaf> Whoops, are you on the list?
02:10:18 <wob_jonas> that won't work, it will ping me when I type the next line, such as this one
02:10:18 <HackEgo> dontaskdonttelllist: quintopia myname int-e
02:10:44 <shachaf> Next time someone else sends you a message
02:11:34 <wob_jonas> I needn't have typed that line though. Good night.
02:11:38 -!- wob_jonas has quit (Quit: http://www.kiwiirc.com/ - A hand crafted IRC client).
02:52:10 <zzo38> I have written hash table codes that are without deletions
02:56:46 -!- tromp has joined.
03:01:22 -!- tromp has quit (Ping timeout: 260 seconds).
03:09:15 -!- ATMunn has quit (Quit: See ya! o/).
03:28:16 -!- tromp has joined.
03:32:44 -!- tromp has quit (Ping timeout: 240 seconds).
03:53:19 -!- sleffy has quit (Ping timeout: 248 seconds).
03:58:33 <HackEgo> [wiki] [[Brainflub]] N https://esolangs.org/w/index.php?oldid=53125 * Snorepion * (+2550) Created page with "'''Brainflub''' is an esoteric programming language created by [[User:Snorepion|Snorepion]]. While its documentation is written jokingly, it isn't as much of a joke as some ot..."
03:58:50 <HackEgo> [wiki] [[User:Snorepion]] N https://esolangs.org/w/index.php?oldid=53126 * Snorepion * (+17) Created page with "I hate red links."
03:59:04 <HackEgo> [wiki] [[User talk:Snorepion]] N https://esolangs.org/w/index.php?oldid=53127 * Snorepion * (+13) Created page with "==Talk here=="
04:28:07 -!- sleffy has joined.
04:53:47 -!- ais523 has quit (Quit: quit).
05:16:10 -!- tromp has joined.
05:21:22 -!- tromp has quit (Ping timeout: 260 seconds).
05:33:01 <shachaf> zzo38: Have you written hash table codes that are with deletions?
06:10:43 -!- tromp has joined.
06:15:13 -!- tromp has quit (Ping timeout: 248 seconds).
06:17:02 <HackEgo> [wiki] [[SELECT.]] https://esolangs.org/w/index.php?diff=53128&oldid=46400 * Quintopia * (-3)
06:22:50 <HackEgo> [wiki] [[SELECT.]] https://esolangs.org/w/index.php?diff=53129&oldid=53128 * Quintopia * (-49) That is a wasteful way to do natural log.
06:24:53 <HackEgo> [wiki] [[SELECT.]] https://esolangs.org/w/index.php?diff=53130&oldid=53129 * Quintopia * (+21) /* Real Part and Imaginary Part */
06:28:31 -!- boily has joined.
06:28:50 <lambdabot> shachaf said 4d 4h 41m 52s ago: I downgraded oerjan to twice punned, because he did notice the pun.
06:29:50 <HackEgo> [wiki] [[SELECT.]] https://esolangs.org/w/index.php?diff=53131&oldid=53130 * Quintopia * (+29) /* Trigonometry */
06:38:32 <\oren\> https://youtu.be/7rmTFxyjSpk
06:52:32 <lambdabot> PAMR 250453Z 19010G16KT 10SM BKN060 10/06 A2963 RMK AO2 SLP035 T01000061 $
07:02:12 -!- FreeFull has quit.
07:05:18 <lambdabot> ETAR 250556Z 11003KT 0600 R27/0500V0900 FG VV002 07/07 A3014 RMK AO2A CIG 001 RWY08 SLP214 T00700070 10070 20032 53000 $
07:05:46 <HackEgo> Ramstein Ab (RMS, ETAR) \ Queretaro Intercontinental (QRO, MMQT) \ Seletar (XSP, WSSL)
07:06:27 <HackEgo> bin/airport \ bin/airport-lookup
07:06:47 -!- Antoxyde has joined.
07:07:04 <oerjan> `` grep share airport-lookup
07:07:05 <HackEgo> grep: airport-lookup: No such file or directory
07:07:13 <oerjan> `` grep share bin/airport-lookup
07:07:14 <HackEgo> with open('share/airports.dat', 'rb') as datafile:
07:07:34 <oerjan> `` grep ETAR share/airports.dat
07:07:35 <HackEgo> 751,"Ramstein Ab","Ramstein","Germany","RMS","ETAR",49.436911,7.600283,776,1,"E","Europe/Berlin"
07:09:02 <oerjan> the most metal metar, obviously
07:10:45 -!- doesthiswork has quit (Quit: Leaving.).
07:18:51 <lambdabot> CYUL 250600Z 22004KT 15SM FEW030 23/21 A3004 RMK CF1 CF TR SLP172 DENSITY ALT 1000FT
07:19:04 <boily> 23/21. the humidity.
07:19:51 <oerjan> itym "oh the humidity" hth
07:21:06 <boily> time to do some circadian realignment.
07:21:19 -!- boily has quit (Quit: TYPED CHICKEN).
07:36:22 -!- oerjan has quit (Quit: Nite).
07:52:14 -!- sleffy has quit (Ping timeout: 240 seconds).
07:52:24 -!- imode has quit (Ping timeout: 252 seconds).
08:06:17 -!- Antoxyde has quit (Remote host closed the connection).
08:07:25 -!- J_Arcane has quit.
08:08:36 -!- zseri has joined.
08:12:16 -!- AnotherTest has joined.
08:15:44 -!- tromp has joined.
08:17:19 -!- LKoen has joined.
08:22:16 -!- hppavilion[0] has quit (Quit: HRII'FHALMA MNAHN'K'YARNAK NGAH NILGH'RI'BTHNKNYTH).
08:25:21 -!- zseri has quit (Quit: Leaving).
08:59:31 -!- prooftechnique has quit (K-Lined).
09:02:21 -!- prooftechnique has joined.
09:25:50 -!- wob_jonas has joined.
09:26:01 <wob_jonas> Some corrections about the dictionary data structure I talked about yesterday.
09:26:59 <wob_jonas> Firstly, about persistence. If you just want to keep snapshots of some or all earlier states of the dictionary, then use the original version. Don't deamortize it the way I suggested, because deamortizing just makes it harder to use persistently, because the deamortized version needs in-place writable arrays, the ordinary version does'nt.
09:28:28 <wob_jonas> This is enough if eg. you want to store all states of a nethack game in such a way that you can play it back (not that I recommend using this structure in practice).
09:29:12 <wob_jonas> If you need a persistent data structure that you can revert (or even fork), then this gets ugly, and I don't know how best to do it. The easiest way is probably to just not use this data structure and use a B-tree instead.
09:29:34 <wob_jonas> Second. Like many other binary data structures, this one has a fibonacci version.
09:30:07 <wob_jonas> Ideally I should use the fibonacci version for eso purposes. In practice, that would screw with my mind too much so I'd be unable to write a correct implementation, so I might not do that.
09:30:54 <wob_jonas> Third, name. If this data structure doesn't yet have a good name, then I call it a plywood, because it's made of layers (of different sized arrays), and is a cheap substitute for real solid trees.
09:34:13 <shachaf> Didn't I give you a name yesterday?
09:34:27 <shachaf> "cache-oblivious lookahead array"
09:34:35 <shachaf> Is this the same thing as COLA or not?
09:34:37 <wob_jonas> shachaf: oh, that turned out to be this structure?
09:34:45 <wob_jonas> I dunno, I haven't read the slides you linked to yet
09:39:59 -!- wob_jonas has quit (Quit: http://www.kiwiirc.com/ - A hand crafted IRC client).
09:47:03 -!- tromp has quit (Read error: Connection reset by peer).
09:47:38 -!- tromp has joined.
10:50:55 <b_jonas> shachaf: oh no. these slides are basically stored as bitmaps. wtf.
10:53:17 -!- LKoen has quit (Quit: “It’s only logical. First you learn to talk, then you learn to think. Too bad it’s not the other way round.”).
11:33:20 -!- impomatic has joined.
11:38:55 -!- tromp has quit (Remote host closed the connection).
11:49:40 -!- tromp has joined.
11:52:35 <b_jonas> That reminds me. If I eventually want to buy an internet domain name for my personal stuff, if I use a distinctive enough name, what top-level domain do you think is the best to put it under? Possibilities can include .org, .net, .com, .xyz
11:52:54 <b_jonas> (Don't hold your breath, this won't happen any time soon, and the answer might change by that time.)
12:22:07 <lambdabot> Plugin `search' failed with: Network.Socket.connect: <socket: 13>: does not exist (No route to host)
12:22:20 <lambdabot> https://wiki.haskell.org/Lambdabot
12:28:10 <int-e> So it still needs that workaround (permanently add an IPv6 neighbour). I wonder whose bug that is.
12:28:48 <b_jonas> int-e: "I wonder whose bug that is" => ah yes, those are the best bugs
12:30:28 <int-e> it's not lambdabot's... it's more low-level than that (I could reproduce it with curl)
12:30:52 <int-e> It's either the Linux kernel or the configuration of the local router.
13:04:53 -!- LKoen has joined.
13:06:33 -!- jaboja has joined.
13:10:25 -!- joast has quit (Quit: Leaving.).
13:16:03 -!- zseri has joined.
13:17:48 <b_jonas> The boost license FAQ "http://www.boost.org/users/license.html" has two interesting tidbits.
13:17:58 <b_jonas> "Why is the "disclaimer" paragraph of the license entirely in uppercase? Capitalization of these particular provisions is a US legal mandate for consumer protection."
13:18:37 <b_jonas> "Do I have to copyright/license trivial files? Even a test file that just contains an empty main() should have a copyright. Files without copyrights make corporate lawyers nervous, and that's a barrier to adoption. The more of Boost is uniformly copyrighted and licensed, the less problem people will have with mounting a Boost release CD on a corporate server."
13:19:03 <b_jonas> Both of these make sense in a twisted legal sort of way in retrospect, but I wouldn't have guessed them.
14:02:20 -!- doesthiswork has joined.
14:03:49 -!- doesthiswork has quit (Client Quit).
14:05:10 -!- ATMunn has joined.
14:19:02 <HackEgo> [wiki] [[InterpretMe]] https://esolangs.org/w/index.php?diff=53132&oldid=49652 * Zseri * (+7) Category
14:22:21 -!- Remavas has joined.
14:24:00 -!- TieSoul has joined.
14:30:02 <HackEgo> [wiki] [[XTW]] https://esolangs.org/w/index.php?diff=53133&oldid=53115 * Zseri * (+11) +Influence:Terse
14:33:08 -!- `^_^v has joined.
14:53:13 -!- joast has joined.
15:03:19 -!- rottytooth has quit (Ping timeout: 260 seconds).
15:23:16 <b_jonas> shachaf: you're right. although I don't like those slides, they do seem to describe the same dictionary data structure as the one I said.
15:44:47 -!- jaboja has quit (Ping timeout: 248 seconds).
15:52:33 <HackEgo> [wiki] [[Brainflub]] M https://esolangs.org/w/index.php?diff=53134&oldid=53125 * Snorepion * (+18) My user page link is still red, updating the page might help
16:03:38 <HackEgo> [wiki] [[Brainflub]] https://esolangs.org/w/index.php?diff=53135&oldid=53134 * Snorepion * (-1) fix broken link
16:06:37 -!- jaboja has joined.
16:28:12 <HackEgo> [wiki] [[Brainflub]] https://esolangs.org/w/index.php?diff=53136&oldid=53135 * Snorepion * (+278) /* Examples */ Better hello world
16:31:43 -!- jaboja has quit (Ping timeout: 248 seconds).
16:37:44 -!- impomatic has quit (Quit: impomatic).
16:55:09 -!- erkin has joined.
16:56:02 -!- jaboja has joined.
17:07:31 -!- FreeFull has joined.
17:07:48 -!- `^_^v has quit (Quit: This computer has gone to sleep).
17:09:39 -!- Antoxyde has joined.
17:22:16 -!- impomatic has joined.
17:23:28 -!- imode has joined.
17:52:16 -!- erkin has quit (Quit: Ouch! Got SIGABRT, dying...).
17:55:03 <imode> hopefully medium well. :P
17:55:24 <rdococ> I like the concept I had of a 'Scope' object, but I have no idea how I'd incorporate that in an interesting manner.
17:59:01 -!- jaboja has quit (Ping timeout: 240 seconds).
18:01:28 -!- jaboja has joined.
18:03:17 -!- `^_^v has joined.
18:07:56 -!- tromp has quit (Remote host closed the connection).
18:09:57 -!- doesthiswork has joined.
18:26:34 <\oren\> Lol world war three is apparently hapening
18:28:04 <\oren\> North korea says they're gonna start shooting down any american aircraft that come near
18:28:17 <imode> do it. I dare them.
18:28:27 <imode> we'll turn the penninsula into a gulf.
18:34:25 -!- Remavas has quit (Read error: Connection reset by peer).
18:34:53 -!- Remavas has joined.
18:35:07 <b_jonas> \oren\: haven't they said that before?
18:35:59 <b_jonas> \oren\: I mean, they bragged before that they have intercontinental ballistic missiles that they can screw their hydrogen bombs onto. if they really had that, would they have to wait for the aircraft to come near?
18:36:35 <b_jonas> or are they acting like the Iraqi people who said in the news that a farmer shot down the super modern American stealth aircraft with his bird rifle?
18:38:04 -!- Phantom_Hoover has joined.
18:38:15 <imode> pretty much the latter. they released a propaganda video that's... just hilarious.
18:39:35 <imode> it shows them "blowing up" U.S aircraft, ships, etc.
18:40:40 <Phantom_Hoover> they said the us had declared war with its actions but that's a surprisingly common state of affairs with north korea, meanwhile the threat to shoot down planes isn't terribly grave because, believe it or not, us planes do not in fact habitually fly over north korea
18:43:41 <Phantom_Hoover> they might plausibly try, though. something could happen but it's not 'ww3 now' territory
18:44:08 <HackEgo> [wiki] [[Chimera]] https://esolangs.org/w/index.php?diff=53137&oldid=17981 * Zseri * (+95) Categories
18:44:25 <imode> we hit "ww3 now" when they actually strike.
18:49:53 <HackEgo> [wiki] [[XTW]] M https://esolangs.org/w/index.php?diff=53138&oldid=53133 * Zseri * (+19) +Category:2017
18:53:53 -!- tromp has joined.
19:20:17 <Phantom_Hoover> imode, b_jonas, fwiw i've found that by far the best way to get clued up on NK is to follow analysts on twitter
19:28:49 -!- Remavas-Hex has joined.
19:31:29 -!- Remavas has quit (Ping timeout: 248 seconds).
19:39:31 -!- tromp has quit (Remote host closed the connection).
19:47:47 <Vorpal> Phantom_Hoover, imode: Somehow I doubt that north korea will trigger WW3. Nobody likes them. Sure, China and Russia don't like US messing in the region, but WW3? Probably not
20:02:10 -!- wob_jonas has joined.
20:02:49 <\oren\> Of course, if this was Civilization, then north korea and america would declare war, and then suddenly for no apparent reason india nukes them both
20:03:01 <wob_jonas> "<zzo38> I tried loading one DOS game on my Linux computer and now the level editor is not work properly. It won't save properly, but the game itself is otherwise working OK." => the problem is that the simulated video card and motherboard doesn't behave exactly like the hardware one.
20:05:47 <wob_jonas> the tunes log is missing for half of the interesting conversation we had yesterday.
20:19:21 -!- tromp has joined.
20:21:27 <rdococ> \oren\: that underflow glitch :P
20:23:48 -!- tromp has quit (Ping timeout: 240 seconds).
20:24:00 -!- sleffy has joined.
20:36:19 -!- TieSoul has quit (Quit: Leaving).
20:48:41 <HackEgo> olist 1100: shachaf oerjan Sgeo FireFly boily nortti b_jonas
20:50:55 -!- Remavas-Hex has quit (Ping timeout: 255 seconds).
20:53:05 -!- Remavas has joined.
21:02:27 <Phantom_Hoover> Vorpal, well, my favourite twitter comment on it of the day is:
21:02:45 <Phantom_Hoover> "So far we have not figured out what they can shoot down, sink or shell and precipitate a full hot war."
21:03:04 <Phantom_Hoover> they have learned from experience that the us will put up with a lot of shit
21:03:35 -!- Remavas has quit (Quit: Leaving).
21:12:33 -!- tromp has joined.
21:31:23 <wob_jonas> fungot, when have you last cleaned your fridge?
21:31:23 <fungot> wob_jonas: look, you're trying to lead well, but has not been dispelled! hah, i should have specified: i'm from like 2 hours in this comic... spider-man! will!! die!
21:37:45 <HackEgo> Ants are great architects. They are famous for their highways.
21:46:08 -!- Antoxyde has quit (Remote host closed the connection).
22:02:39 -!- wob_jonas has quit (Quit: http://www.kiwiirc.com/ - A hand crafted IRC client).
22:09:14 <\oren\> this aint world war three?! lame
22:16:47 -!- AnotherTest has quit (Ping timeout: 246 seconds).
22:17:15 -!- ais523 has joined.
22:21:14 -!- zseri has quit (Quit: Leaving).
22:29:35 <rdococ> fungot, are you actually a human, or well, it depends on whether the chicken or the egg that I just laid - and haha!
22:29:35 <fungot> rdococ: to the last, i will grapple with thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee! from hell's heart, i stab at thee!
22:34:18 -!- ais523 has quit (Remote host closed the connection).
22:35:28 -!- ais523 has joined.
22:36:58 -!- imode has quit (Ping timeout: 264 seconds).
22:36:58 -!- Phantom_Hoover has quit (Read error: Connection reset by peer).
22:40:45 <fizzie> Heh, I haven't seen a loopy fungot in quite a bit.
22:40:45 <fungot> fizzie: you and the dromiceiomimus had a customer is either rude, but as a terminator 2. that was a pretty good... or bad?" each moment we delay, so when i send not to know for sure who i just met!
22:42:40 -!- Phantom_Hoover has joined.
22:42:43 -!- impomatic has quit (Ping timeout: 240 seconds).
22:44:28 -!- tromp has quit (Remote host closed the connection).
22:49:39 -!- `^_^v has quit (Quit: This computer has gone to sleep).
22:53:34 -!- wob_jonas has joined.
22:54:17 <wob_jonas> ais523: the boost license FAQ also tells two interesting things that are sort of obvious in retrospect only
22:55:13 <wob_jonas> ais523: "http://www.boost.org/users/license.html" "Why is the "disclaimer" paragraph of the license entirely in uppercase? Capitalization of these particular provisions is a US legal mandate for consumer protection."
22:55:38 <wob_jonas> and "Do I have to copyright/license trivial files? Even a test file that just contains an empty main() should have a copyright. Files without copyrights make corporate lawyers nervous, and that's a barrier to adoption."
22:55:51 <ais523> wob_jonas: the thing about uppercase license disclaimers, is that the law just says they have to be prominent
22:56:09 <ais523> but there's a court case that found that uppercasing the disclaimer when everything else is lowercase (and in the same/similar font) is sufficient
22:56:23 <ais523> and so everyone uppercases them nowadays because they know that that works
22:57:31 <wob_jonas> ais523: yes, but at the same time at least we in Hungary also have laws that none of the rules are allowed to be printed in small font, so they can't really just use different font sizes. it's either all caps or bolding, and bolding doesn't easily work in text source code
22:58:04 <wob_jonas> (about a third of the text of the travel insurance I buy is in bold, sometimes indicating such disclaimers, and sometimes that it's changed since the previous version, and you can't tell which clause is bold for which of those reasons)
22:59:07 <shachaf> Insurance is so complicated.
22:59:58 <wob_jonas> shachaf: yeah, but I read it through, and it basically comes down to being a travel insurance with some extra services that I don't need but I also can practically never use in practice because the disclaimers cover everything
23:00:43 <shachaf> I quit my job last week. So now I need to figure out US health insurance.
23:02:31 <wob_jonas> shachaf: what job are you looking for now, and are you planning to relocate?
23:02:45 <shachaf> Not immediately looking for any job.
23:03:05 <shachaf> Should I get another job or should I be a lazy unemployed bum for a while?
23:03:29 <shachaf> I have no plans to move but I might.
23:03:30 <wob_jonas> you should *look* for a job. it will take some time to find a good job anyway. you don't have to intentionally delay for that.
23:03:45 <shachaf> But looking for a job is even more stressful than having a job.
23:03:49 <wob_jonas> yeah, obviously the way I should ask is how far you're willing to move for a job.
23:04:10 <shachaf> I'm willing to move anywhere, I suppose. But this area isn't so bad.
23:05:13 <shachaf> Why, where do you recommend?
23:05:57 <shachaf> One time a company wanted me to move to Istanbul for a job. I guess that was a bit drastic for me.
23:06:45 <shachaf> But I think one reason they were in Istanbul was that it was cheaper. Why would I move far away to a place I don't particularly want to live in to work at a job that paid less?
23:06:50 <wob_jonas> I've no idea, I'm in Hungary, but it's not a good place to move to.
23:07:17 <wob_jonas> Exactly. You don't get payed much here, which is why companies get people to work here.
23:08:16 <shachaf> If income scales roughly linearly with cost of living, it's better to live in the most expensive place.
23:08:16 <shachaf> (It doesn't, of course. But it might still be better.)
23:08:21 <wob_jonas> All the qualified workers are moving away from Hungary, but at the same time the companies in western europe figure out they can get half-qualified workers here for much less money than in western europe who work better than the people hired in india for free, so they fire the western europeans and hire teams here.
23:09:39 -!- LKoen has quit (Quit: “It’s only logical. First you learn to talk, then you learn to think. Too bad it’s not the other way round.”).
23:09:55 <shachaf> It looks like keeping my employer's health insurance will cost me a bit over $500/month. That's a lot but it's less than I was expecting.
23:10:38 <wob_jonas> can't you choose some other health insurance?
23:10:46 <wob_jonas> I mean, I understand it's beneficial while you're working there
23:10:54 <shachaf> The cheapest I can get would probably cost ~$250/month.
23:12:31 <shachaf> I got the fanciest most expensive option because my employer was subsidizing most of it. Maybe that was a mistake.
23:12:37 <wob_jonas> that sounds more reasonable, unless you're over 65 years old or something
23:13:02 <shachaf> I suppose it depends on how you treat insurance.
23:13:25 <shachaf> The most important reason to have health insurance is to handle the very expensive cases that cost hundreds of thousands or millions of dollars.
23:14:15 <wob_jonas> like needing to swap your dialysis filter every two days
23:15:21 <shachaf> Dialysis is covered for everyone in the US, I believe.
23:16:07 <wob_jonas> ok. then expensive patented heart medicine.
23:16:27 <wob_jonas> or just the general cost of making hospitals work, which is getting more and more expensive.
23:16:45 <shachaf> I went to the hospital for the first time in a decade last month or so.
23:17:01 <shachaf> Had a good time getting X-rays and CT scans and things.
23:17:16 <shachaf> Looks like I'm OK, though. Hopefully.
23:17:28 <wob_jonas> some of those turn out to be less scary than you thought as a child
23:18:38 <wob_jonas> It turns out getting water through IV is not such a bad or painful thing as I remembered from when I was nine years old, it's just that every time I had to get that, I was so sick that everything felt like a bad experience.
23:19:04 <shachaf> Have you gotten a CT scan?
23:19:05 <wob_jonas> Having a needle stuck in your arm all day isn't as uncomfortable as I remembered.
23:19:14 <wob_jonas> Yes, and those aren't as bad as they imply either.
23:19:18 <shachaf> There's no needle, is there?
23:19:38 <wob_jonas> The doctors warn that it's very loud, and while it's loud, it's not a distracting sort of sound, but a comforting hum.
23:19:49 <shachaf> Getting the dye injected was a very odd experience.
23:20:15 <wob_jonas> CT scan is just an ordinary X-ray, only with a hundred times
23:20:24 <shachaf> It feels very warm. I guess you can feel your own circulation.
23:20:44 <wob_jonas> they scare you about that too, saying they leave a needle in your arm after the dye because there's a small chance of an allergic reaction to it
23:23:03 <wob_jonas> I think I got dye twice, once for CT, and once for just plain X-ray. Plus radioactive measurement chemical once.
23:23:17 <shachaf> "Hungary spent the equivalent of USD 1719 per person on health in 2013, compared with an OECD average of USD 3453."
23:23:33 <wob_jonas> Sort of like radioactive dye, but because they measure the radiation rather than the absorbtion there, it needs only a much smaller dose.
23:24:01 <wob_jonas> shachaf: that's the costs the state pays. it doesn't include what people pay for themselves I think.
23:24:43 <shachaf> I think that's the the total spending.
23:24:48 <shachaf> "Public sources accounted for 65% of overall health spending, below the OECD average"
23:24:55 <shachaf> https://www.oecd.org/els/health-systems/Country-Note-HUNGARY-OECD-Health-Statistics-2015.pdf
23:25:10 <wob_jonas> How about private health insurance companies?
23:25:42 <wob_jonas> at least if you only measure the costs accounted for, not the black market stuff and tips
23:30:05 -!- ais523 has quit (Quit: It seems most convenient to apologise for my connection in the quit message, given how often it comes up… If I immediately reconnect, it's probably because I could send but not receive.).
23:30:27 <shachaf> The same source says the US spent $8713/person: https://www.oecd.org/unitedstates/Country-Note-UNITED%20STATES-OECD-Health-Statistics-2015.pdf
23:33:15 <shachaf> US politicians are saying a lot of nonsense about health insurance.
23:35:13 -!- Phantom_Hoover has quit (Read error: Connection reset by peer).
23:36:02 <shachaf> Anyway, $500/month is below the US number but way above the Hungarian number.
23:36:50 <wob_jonas> politicians always say a lot of nonsense. that's their work
23:37:06 -!- tromp has joined.
23:37:17 <shachaf> I think maybe health insurance is just fundamentally problematic without a lot of regulation (maybe of a form similar to the ACA in the US).
23:42:07 -!- tromp has quit (Ping timeout: 260 seconds).
23:46:59 <shachaf> Do you like the winner's curse?
23:49:03 -!- boily has joined.