Coding: Fleeting Thoughts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Wed Sep 23, 2015 12:27 pm UTC

Crypto professionals, who have learned far more than you most likely ever will, who have generated world-wide headlines finding flaws in important crypto algorithms, still know that they shouldn't roll their own crypto for production.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

commodorejohn
Posts: 1179
Joined: Thu Dec 10, 2009 6:21 pm UTC
Location: Placerville, CA
Contact:

Re: Coding: Fleeting Thoughts

Postby commodorejohn » Wed Sep 23, 2015 2:48 pm UTC

Oh, naturally. There's always Nonspecific People Who Know Much Better Than You out there to tell you not to deviate from the Sacred Libraries.
"'Legacy code' often differs from its suggested alternative by actually working and scaling."
- Bjarne Stroustrup
www.commodorejohn.com - in case you were wondering, which you probably weren't.

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Wed Sep 23, 2015 3:55 pm UTC

But... they're completely right, in this case. My sarcasm detector indicates that you're trying to suggest they're overreacting, but they're not. Don't deploy home-rolled crypto in production. Don't. Do. It.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6568
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Coding: Fleeting Thoughts

Postby Thesh » Wed Sep 23, 2015 4:28 pm UTC

Yeah, use something that has, time and time again, proven to be bug free and secure. Like OpenSSL.

I've actually written several of ciphers that no one has ever broken or found any weakness in. Granted, no one has ever done the cryptanalysis, but still, unbroken. I'm also undefeated in boxing, judo, slalom, and golf.
Summum ius, summa iniuria.

User avatar
Flumble
Yes Man
Posts: 2236
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Wed Sep 23, 2015 5:54 pm UTC

It's completely fine to write your own cryptographic library and use it at large. Just make sure that it
  • implements a known and unbroken cipher exactly (this is the easy part),
  • doesn't have any bugs,
  • is resistent to timing attacks (unlike most of the home-grown crypto software) and
  • doesn't compromise security for speed (accidentally or intentionally).
Although, if you rely on hardware acceleration for the encryption and decryption (e.g. AES-NI), you probably don't need to worry about timing attacks.

Also I've broken Thesh's ROT26 encrypted message above.

commodorejohn
Posts: 1179
Joined: Thu Dec 10, 2009 6:21 pm UTC
Location: Placerville, CA
Contact:

Re: Coding: Fleeting Thoughts

Postby commodorejohn » Wed Sep 23, 2015 6:01 pm UTC

Xanthir wrote:But... they're completely right, in this case. My sarcasm detector indicates that you're trying to suggest they're overreacting, but they're not. Don't deploy home-rolled crypto in production. Don't. Do. It.

Well, first off, I wasn't advocating doing this in production. And I'm not going to make the argument that you or I are necessarily going to write a good crypto algorithm. It's just very funny to me how, no matter how many times stuff like Heartbleed happens, people still have this unshakeable faith in the unattainable-by-mere-mortals Rightness of the Sacred Libraries and look upon any attempt to deviate for any reason as heresy of the highest order.

Flumble wrote:implements a known and unbroken cipher exactly (this is the easy part),

Why is it so important that the cipher be known? Provided you know that it hasn't been broken, wouldn't it be better to use something nobody else knows about?
"'Legacy code' often differs from its suggested alternative by actually working and scaling."
- Bjarne Stroustrup
www.commodorejohn.com - in case you were wondering, which you probably weren't.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Wed Sep 23, 2015 6:10 pm UTC

You forgot:
* And there isn't something you didn't think of that makes your entire system not secure

With Crypto, getting everything you thought of perfectly correct is evidence your library is not secure. Because the only evidence of security is high-cost adversarial attacks on it. Everything else is evidence of insecurity.

Oh, the library has a name? Evidence of insecurity. It is a dynamically linked library? Evidence of insecurity. It is a statically linked library? Evidence of insecurity. It exists? More evidence!

"This is the most tested, and attacked, library ever, and the last flaw was found 2 minutes ago" -- actual evidence of security!

(Yes, this is humour, but it is true humour.)

commodorejohn wrote:Provided you know that it hasn't been broken, wouldn't it be better to use something nobody else knows about?

Spoiler:
That question is so bad that even responding to it with an answer would make this thread worse.

Imagine if we where talking about what new phone to buy. And someone showed up and asked "why don't we just steal phones from other people, break them down to components, then weld the components together, and end up with a better phone? For free too!"

Now, they could be talking seriously. Or they could be trolling. Regardless of which, engaging them in a thread about "what phone to buy" is a bad idea.

That is what the above question adds to a discussion about crypto.


---

Another topic.

So, I've read high-level descriptions of
https://github.com/isocpp/CppCoreGuidel ... delines.md
and much of it has seemed less broken than other guidelines I've read. Any opinions?

One issue: exceptions are still half way to a "come from" instruction for my tastes. I prefer std::experimental::expected style flow control, maybe with some syntactic sugar to make `bind` easier to use.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Flumble
Yes Man
Posts: 2236
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Wed Sep 23, 2015 6:42 pm UTC

Yakk wrote:You forgot:
* And there isn't something you didn't think of that makes your entire system not secure

Do you have an example of this?

To my knowledge even openssl requires that the system isn't compromised to (somewhat) guarantee its integrity.

commodorejohn wrote:Why is it so important that the cipher be known? Provided you know that it hasn't been broken, wouldn't it be better to use something nobody else knows about?
What do you mean by that last question? If nobody knows about a cipher, it can't be broken.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6568
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Coding: Fleeting Thoughts

Postby Thesh » Wed Sep 23, 2015 6:51 pm UTC

I think what they are talking about is let's say you design your own crypto protocol. You use strong ciphers, no flaws, you write your own library, implementing everything correctly. If your implementation of RSA doesn't add noise to avoid side-channel attacks, the whole cryptosystem breaks down by that one weak point.
Summum ius, summa iniuria.

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Wed Sep 23, 2015 8:22 pm UTC

Flumble wrote:
commodorejohn wrote:Why is it so important that the cipher be known? Provided you know that it hasn't been broken, wouldn't it be better to use something nobody else knows about?
What do you mean by that last question? If nobody knows about a cipher, it can't be broken.

The only to prevent people from knowing about a cypher is to not use it. As soon as your cyphertext sees public use, anyone interacting with it knows of it, and cracking can begin. This is, obviously, rather tautological, and not worthwhile as guidance. It's also clearly not what commodorejohn meant - he's under the greatly mistaken impression that obscurity is a reasonable substitute for well-studied security in crypto.

Knowing the source code of your crypto library is not relevant to cracking it. (Or at least, not directly relevant; it of course can help.) All that matters is the *results* of the cyphering, and whether or not that accidentally contains patterns that allow people to reverse it.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

commodorejohn
Posts: 1179
Joined: Thu Dec 10, 2009 6:21 pm UTC
Location: Placerville, CA
Contact:

Re: Coding: Fleeting Thoughts

Postby commodorejohn » Wed Sep 23, 2015 8:38 pm UTC

Xanthir wrote:It's also clearly not what commodorejohn meant - he's under the greatly mistaken impression that obscurity is a reasonable substitute for well-studied security in crypto.

Not a substitute, just possibly a supplement, to my way of thinking. But I'll defer on that to people who know more about cryptography than I do.
"'Legacy code' often differs from its suggested alternative by actually working and scaling."
- Bjarne Stroustrup
www.commodorejohn.com - in case you were wondering, which you probably weren't.

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Wed Sep 23, 2015 8:39 pm UTC

Yakk wrote:One issue: exceptions are still half way to a "come from" instruction for my tastes. I prefer std::experimental::expected style flow control, maybe with some syntactic sugar to make `bind` easier to use.

Agreed. Reifying values-that-might-instead-be-exception as a first-class value is definitely the best way to handle things. You just need a lot of sugar to make it reasonable to work with, like what Rust provides.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Wed Sep 23, 2015 8:43 pm UTC

commodorejohn wrote:
Xanthir wrote:It's also clearly not what commodorejohn meant - he's under the greatly mistaken impression that obscurity is a reasonable substitute for well-studied security in crypto.

Not a substitute, just possibly a supplement, to my way of thinking. But I'll defer on that to people who know more about cryptography than I do.

It's not a supplement, it's actively harmful to security. Crypto that nobody knows about is crypto that hasn't been seriously studied and attacked, and is virtually guaranteed to contain tons of weaknesses that you don't know about. "I've fixed all the bugs I could find" is a worthless thing to say about crypto; "I've fixed all the bugs revealed by years of sustained attacks by people whose livelihood depends on breaking my crypto, and years of sustained study by people whose reputation depends on finding theoretical flaws in my crypto and presenting papers on them" is the only reasonably worthwhile statement one can make about crypto security.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

commodorejohn
Posts: 1179
Joined: Thu Dec 10, 2009 6:21 pm UTC
Location: Placerville, CA
Contact:

Re: Coding: Fleeting Thoughts

Postby commodorejohn » Wed Sep 23, 2015 8:48 pm UTC

Hmm.
"'Legacy code' often differs from its suggested alternative by actually working and scaling."
- Bjarne Stroustrup
www.commodorejohn.com - in case you were wondering, which you probably weren't.

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Wed Sep 23, 2015 9:04 pm UTC

The big thing is that crypto must be perfect to be useful, and the set of things that it must be perfect about is far larger than anyone who's not an active crypto researcher knows about (and even then, any single person doesn't know *all* of it). And any weakness is immediately weaponized by someone who profits off of breaking your crypto.

Other software can get by being imperfect, or caring about perfection in only a much smaller set of topics. You don't have to worry about whether adding an if statement will result in your code sometimes executing less assembly instructions than at other times, thus leaking information about the key via timing attacks. If it's slow sometimes, or corrupts data sometimes, or crashes sometimes, it's annoying, but it can still be used for its intended purpose and is considered "working". This is not true of crypto.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Flumble
Yes Man
Posts: 2236
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Wed Sep 23, 2015 9:22 pm UTC

Xanthir wrote:The only [way] to prevent people from knowing about a cypher is to not use it. As soon as your cyphertext sees public use, anyone interacting with it knows of it, and cracking can begin. This is, obviously, rather tautological, and not worthwhile as guidance. It's also clearly not what commodorejohn meant - he's under the greatly mistaken impression that obscurity is a reasonable substitute for well-studied security in crypto.

Yeah, I wanted commodorejohn to think about the question and either find the flaw in his model or post it for us to disprove, but you answering the question and pointing it out for him also works. :mrgreen:


Thesh wrote:side-channel attacks

Right, that's the word I was looking for.
Which parts of a cipher actually suffer from this? I guess that a substitution step (with a static, cached S-box) could give away information through power consumption because of the popcount of the index (assuming a correlation between index occurence and plaintext occurence), and keypair generation of course gives away information through the timing of the validation phase (e.g. primality test) –are there any others?

commodorejohn
Posts: 1179
Joined: Thu Dec 10, 2009 6:21 pm UTC
Location: Placerville, CA
Contact:

Re: Coding: Fleeting Thoughts

Postby commodorejohn » Wed Sep 23, 2015 9:38 pm UTC

It's a good point either way, so thanks for the explanation.

I still maintain that it's silly to be superstitious about the Sacred Libraries, but those are good practical reasons for your position.
"'Legacy code' often differs from its suggested alternative by actually working and scaling."
- Bjarne Stroustrup
www.commodorejohn.com - in case you were wondering, which you probably weren't.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6568
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Coding: Fleeting Thoughts

Postby Thesh » Wed Sep 23, 2015 9:48 pm UTC

Key/plaintext-dependent lookups and branching are the big problems. RSA has problems because it requires big number libraries that can vary largely in execution time and power consumption depending on what numbers they are operating on (it's very difficult or impossible to efficiently implement modulus without branching). Even simple arithmetic operations can leak information about the number of 1-bits through power analysis (SHA-256 uses only arithmetic, and there are differential power analysis attacks against it), but usually that is considered too unlikely of an attack to include counter measures. Generally speaking, for an efficient block cipher that requires no input-dependent branching or lookups, you are good as long as you have more than enough rounds to fend off all known attacks, with additional rounds to be safe against some future attacks.
Summum ius, summa iniuria.

User avatar
ucim
Posts: 6827
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Coding: Fleeting Thoughts

Postby ucim » Wed Sep 23, 2015 11:29 pm UTC

I've heard that it weakens security to chain crypto - that is, to do plaintext->cyphertext->"supercyphertext".

1: Why is it weaker?

2: What is wrong with the logic: "chain two different protocols, so that even if one is broken, the second still protects the plaintext" (other than you might never know that the second one, which could be your homerolled one, is broken).

I also ran into something setting up a password for ubuntu 14.04; making it longer made it weaker (even when the result did not complete a word). A bug in their running password evaluator, or a bug in my thinking (that making it longer is better)

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Coding: Fleeting Thoughts

Postby korona » Wed Sep 23, 2015 11:53 pm UTC

FT: Most asynchronous I/O interfaces (written in C/C++) use callbacks to signal completion. Consider a web server that communicates with clients through an imaginary write(void *buffer, size_t length, void (*callback) ()) function that sends data to a socket and invokes the supplied callback when the data has actually been send. There are two problems with this approach: Since the caller of this function will have exited long before the write completes the buffer and other contextual information has to be allocated on the heap. Furthermore chaining callback functions in C/C++ is ugly as it separates control flow from program logic.

It is much nicer to turn this control flow into a coroutine and to turn read() into a function that suspends the current coroutine and continues running the caller. Instead of invoking an explicit callback completion is signaled by re-entering the coroutine. This leads to a natural procedural C program. However using coroutines has other problems: Coroutines do not scale well. Every coroutine needs its own stack and common C library functions expect a quite huge stack. Clearly it is too expensive to allocate something like a 64 kiB stack for each asynchronous read-request/process/write-result cycle.

In order to scale better we need to allocate smaller stacks. GCC's -fsplit-stack allows us to split the stack into multiple segments. Of course this adds some runtime cost to the code.

I wonder how well coroutines based on -fsplit-stack would perform in a real world scenario (scalability / request latency / request throughput) compared to the original fine-tuned callback based approach.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6568
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Coding: Fleeting Thoughts

Postby Thesh » Thu Sep 24, 2015 12:22 am UTC

ucim wrote:I've heard that it weakens security to chain crypto - that is, to do plaintext->cyphertext->"supercyphertext".


It isn't as long as you use independent keys (or a good approximation of independent, e.g. a secure PRNG).

Think about it, if taking something and encrypting with AES in CBC more, and then taking a completely different key and encrypting it with Twofish in CTR mode caused it to be insecure, then anyone could simply take and encrypt AES+CBC output with Twofish+CTR and AES would be broken. Using the same key, you lose that proof, but it doesn't necessarily make it less secure, just unproven and potentially less secure. If you used a different algorithm and different key to break AES, that's the equivalent of breaking AES by randomly going through all 2128! possible functions and seeing if any makes it easier to break - it's highly unlikely you will be able to count the number digits in the number of years it would take using all of the computers on earth before the heat death of the universe.
Summum ius, summa iniuria.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Thu Sep 24, 2015 12:54 am UTC

korona wrote:FT: Most asynchronous I/O interfaces (written in C/C++) use callbacks to signal completion. Consider a web server that communicates with clients through an imaginary write(void *buffer, size_t length, void (*callback) ()) function that sends data to a socket and invokes the supplied callback when the data has actually been send. There are two problems with this approach: Since the caller of this function will have exited long before the write completes the buffer and other contextual information has to be allocated on the heap. Furthermore chaining callback functions in C/C++ is ugly as it separates control flow from program logic.

Not in modern C++, where you can do anything from *then* based chaining to coroutine-lites.

*then* based chaining makes IO into a monad, in particular a future<some_data>.

You call future<some_data>::then( lambda saying what to do after the io completes ). You can chain these as much as you want.

The program logic/control flow is inline with each other. Once you have the dependency chain of operations set up, you can abort it, or add more dependencies on it.

haskell-like bind or map is an alternative to then (they differ only in what they pass, and what they do to the return value).
It is much nicer to turn this control flow into a coroutine and to turn read() into a function that suspends the current coroutine and continues running the caller. Instead of invoking an explicit callback completion is signaled by re-entering the coroutine. This leads to a natural procedural C program. However using coroutines has other problems: Coroutines do not scale well. Every coroutine needs its own stack and common C library functions expect a quite huge stack. Clearly it is too expensive to allocate something like a 64 kiB stack for each asynchronous read-request/process/write-result cycle.

More like 1 MB of memory space.

But light coroutines are coming to C++ shortly.

A light coroutine is an function turned into an object. It stores its local variables in its object state instead of on the stack, and each yield-type instruction has an implicit LABEL: after it. A pointer to said LABEL: is stored on a yield before the function returns, and whenever the function is called (the object is operator()ed) it does a GOTO to the last LABEL:.

The state it uses is limited to being no more than the local variables it has to store, sort of like a lambda capture.

All of this can be manually implemented in C/C++ already. But language-based coroutines make the syntax *pretty*, which is important, and far less error prone.

What you get out of it is a light weight coroutine that cannot yield from outside of its own body. (It can call other coroutines and chain them if it wants to).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Flumble
Yes Man
Posts: 2236
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Thu Sep 24, 2015 1:27 am UTC

Thesh wrote:Generally speaking, for an efficient block cipher that requires no input-dependent branching or lookups, you are good as long as you have more than enough rounds to fend off all known attacks, with additional rounds to be safe against some future attacks.

Is that why ciphers have so many rounds? Not only to slow down attacks but also to defend against side-channel attacks?


ucim wrote:I've heard that it weakens security to chain crypto - that is, to do plaintext->cyphertext->"supercyphertext".

Does this answer your question? (ninja'd a bit)

ucim wrote:I also ran into something setting up a password for ubuntu 14.04; making it longer made it weaker (even when the result did not complete a word). A bug in their running password evaluator, or a bug in my thinking (that making it longer is better)

I'm not familiar with the tool, but if I understand pam_passwdqc (the de-facto unix password strength checker) correctly, it switches to a passphrase way of checking when there are sufficient spaces –and looking at parts of the password in isolation may result in a combined entropy much lower than the password seen as a whole.

In any case: yes, adding certain characters to a password may decrease the entropy. This is mostly by completing words, indeed, but that can also happen in obscure ways, like adding 743 to passwordw3d (where "w3d743" is "secure" transposed one key upwards). Also password12 is probably more secure than password1 and password123. (If you need a number sequence, I think it's best to stop at 6 or 8 –everyone stops at 3, 5, 7 or 9 already)

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6568
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Coding: Fleeting Thoughts

Postby Thesh » Thu Sep 24, 2015 2:01 am UTC

Flumble wrote:
Thesh wrote:Generally speaking, for an efficient block cipher that requires no input-dependent branching or lookups, you are good as long as you have more than enough rounds to fend off all known attacks, with additional rounds to be safe against some future attacks.

Is that why ciphers have so many rounds? Not only to slow down attacks but also to defend against side-channel attacks?


Not really to protect against side-channel attacks; generally what cryptographers do is they design a cipher, and then they do a shitload of analysis to determine how many rounds they can break, twerking it where they can. Now, just because you can't break more than 7 rounds, doesn't mean that there won't be another attack in the future that breaks 8, or 9, or even 10 rounds. So you give yourself a comfortable safety margin: if you need 8 rounds so you can't break it today, you give it sixteen rounds so you are confident it won't be broken in the future*. Theoretically, each round you add should increase the attack complexity exponentially (provided you don't have a stupid round function), so doubling it should make it safe for a while.

That said, even in the AES competition with submissions by actual cryptographers, ciphers were still rejected because of major flaws. It's not as easy as it sounds (and it doesn't sound easy).

*For comparison, Rijndael went with 10, 12, and 14 rounds for 128, 192, and 256 bit keys, respectively, and at the time of the AES competition, the best attacks could break 7, 7, and 9 rounds, respectively - today, there are full round attacks against all three, although they aren't feasible attacks, if they went with 16, 18, and 20 rounds (Minimum Rounds * 2 as recommended by cryptographers like Bruce Schneier) then we would be quite a ways off from full-round attacks today, let alone feasible ones.
Summum ius, summa iniuria.

User avatar
ucim
Posts: 6827
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Coding: Fleeting Thoughts

Postby ucim » Thu Sep 24, 2015 4:49 am UTC

Thanks Thesh and Flumble.

How does an attacker know when they have broken the code? I presume it is when they discover meaningful plaintext - if the cyphertext decodes into gibberish, it's the wrong key, but if it decodes into "attack at dawn", then (at least one level of) the cypher looks cracked.

Is this correct?

If so, then how would a cracker recognize that a two-step decode, the first of which is strong, and the second of which is just ROT-13, has been cracked? ROT13 still "looks like gibberish".

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6568
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Coding: Fleeting Thoughts

Postby Thesh » Thu Sep 24, 2015 5:09 am UTC

Against modern ciphers, you generally have known plaintext attacks or in some cases chosen plaintext attacks. There are a lot of situations where you have some knowledge of the plaintexxt, for example, I can guess with a high probability that your request to forums.xkcd.com looks like this:

GET / HTTP/1.1
Host: forums.xkcd.com
User-Agent: Mozilla/5.0


So now I not only know what the message is, but what it encrypts to. With enough plaintext/ciphertext pairs, and a weak cipher, this can be enough to recover the key. Chosen plaintext attacks are even more powerful, but they are more difficult to perform since you need to actually be able to get the target to encrypt arbitrary messages, however, they are not impossible. Let's say I can get you to go to my web page, and in my web page is an iframe. Using that iframe, I could add a dummy querystring. Now, by knowing that I can use javascript to push chosen plaintexts to the querystring, which shows up right a the beginning of the request at a known position.
Summum ius, summa iniuria.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Coding: Fleeting Thoughts

Postby korona » Thu Sep 24, 2015 7:47 am UTC

Yakk wrote:Not in modern C++, where you can do anything from *then* based chaining to coroutine-lites.

*then* based chaining makes IO into a monad, in particular a future<some_data>.

You call future<some_data>::then( lambda saying what to do after the io completes ). You can chain these as much as you want.

The program logic/control flow is inline with each other. Once you have the dependency chain of operations set up, you can abort it, or add more dependencies on it.

haskell-like bind or map is an alternative to then (they differ only in what they pass, and what they do to the return value).

Unfortunately futures are rather limited. C++14's std::future<T>::then only models "async-sequential" control flow. But for many application you need many more primitivies, for example async-while or async-foreach. They also still have to be manually heap-allocated and don't compose well: std::future<T>::then has to perform type erasure on its functor argument which requires another heap allocation. The coroutine based approach needs a single heap allocation when it is invoking but no additional heap allocations for common control flow models.

Yakk wrote:More like 1 MB of memory space.

But light coroutines are coming to C++ shortly.

A light coroutine is an function turned into an object. It stores its local variables in its object state instead of on the stack, and each yield-type instruction has an implicit LABEL: after it. A pointer to said LABEL: is stored on a yield before the function returns, and whenever the function is called (the object is operator()ed) it does a GOTO to the last LABEL:.

The state it uses is limited to being no more than the local variables it has to store, sort of like a lambda capture.

All of this can be manually implemented in C/C++ already. But language-based coroutines make the syntax *pretty*, which is important, and far less error prone.

What you get out of it is a light weight coroutine that cannot yield from outside of its own body. (It can call other coroutines and chain them if it wants to).

By light coroutine do you mean a combination of preprocessor macros with something like Duff's device? That is not really a good substitute for real stackful coroutines that can be composed.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Thu Sep 24, 2015 8:51 am UTC

n3985 is what I am talking about.
...

Type erasure only requires heap if state is large. And on scale of threading, heap allocation is not that expensive.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Coding: Fleeting Thoughts

Postby korona » Thu Sep 24, 2015 9:11 am UTC

n3985 without -fsplit-stack is quite heavy weight. Each coroutine constructor has to allocate an own stack. What I'm interested in would be the performance of n3985 with -fsplit-stack. n3985 is already implemented in boost::coroutine and this implementation supports -fsplit-stack. I guess I'll have to write a small benchmark program to test its performance and scalability.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Thu Sep 24, 2015 1:18 pm UTC

Bah, that was the wrong paper. One sec.

http://www.open-std.org/jtc1/sc22/wg21/ ... /n4134.pdf

Sorry, my bad. The stackless ones in there.

I'm sure that a stackful coroutine can do things that a stackless one cannot, excluding Turing-equivalence (basically, you can always manage a stack manually), but I'd like to see some practical examples if you have any (where a stackful coroutine, in a practial use case, makes the situation much easier than a stackless one).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Diadem
Posts: 5654
Joined: Wed Jun 11, 2008 11:03 am UTC
Location: The Netherlands

Re: Coding: Fleeting Thoughts

Postby Diadem » Thu Sep 24, 2015 1:38 pm UTC

Gaaah!

Matlab has 2 functions to convert numbers to strings. There is int2str() and num2str(). Both work perfectly fine on both ints and floats, but int2str() rounds before converting to a string. That's already pretty confusingly named, but okay, it makes some sense. But what happens if you accidentally put in something that is already a string (which is extremely easy to do, because matlab functions randomly return numbers or numbers-as-string with seemingly no pattern).

Code: Select all

>> int2str(2)
ans =
2
>> int2str('2')
ans =
50
>> num2str(2)
ans =
2
>> num2str('2')
ans =
2

There's just so much wrong with that.
It's one of those irregular verbs, isn't it? I have an independent mind, you are an eccentric, he is round the twist
- Bernard Woolley in Yes, Prime Minister

User avatar
Dason
Posts: 1311
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Coding: Fleeting Thoughts

Postby Dason » Thu Sep 24, 2015 1:54 pm UTC

'2' is 50 in ascii so it at least sort of makes sense.
double epsilon = -.0000001;

User avatar
Flumble
Yes Man
Posts: 2236
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Thu Sep 24, 2015 3:19 pm UTC

The real WTF is: matlab doesn't have documentation about implicit/automatic conversions of data types. There's only one bullet inside this table claiming that a char "Converts to/from numeric". Really helpful, Mathworks. :?

So yeah, num2str is (most likely) a function that takes any argument, checks if it has a routine to get a meaningful number out of that type and then stringifies it. (It's interesting to put a very obscure type in it and watch whether it'll make sense of it, report and error or crash the whole thing.) Passing a character will set off the string parsing routine and you'll get your number back.
int2str is (most likely) a function that expects and integer type, so matlab tries to cast the argument to an integer if necessary. Passing a character will force matlab to cast it to an integer –meaning it'll reinterpret the '2' (byte value 0x32) as 50, like Dason said– and call int2str with that integer.


Diadem wrote:That's already pretty confusingly named, but okay, it makes some sense.

I think int2str is pretty clear about outputting an integer. num2str could've been named better I suppose –perhaps anythingAsRealNumber2str, depending how generic num2str really is.

User avatar
Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: Coding: Fleeting Thoughts

Postby Robert'); DROP TABLE *; » Sat Sep 26, 2015 1:57 am UTC

FT prompted by both Xanthir's help and the Codeless Code: Given,
1) that a functor lets you turn a function (X -> Y) over the category you're "lifting" into the functor into one with signature (F X -> F Y).
2) that you can slice multi-value function signatures into any precedence you want, i.e. (X->Y)->Z == X->(Y->Z)
3) a function chopDown: Ax -> Tree -> Sound

then when you apply Maybe to this function, what do you get? Applying the rules produces a (Maybe Ax) -> Maybe (Tree -> Sound), but I have no idea about what a Maybe-function means, since it suggests you might wind up asking what happens if you call None. (As opposed to just passing None to a function expecting a Maybe T) The other possible arrangement of Maybe (Ax -> Tree) -> Maybe Sound makes slightly more sense, but still doesn't appear to be the same thing as the answer that appears intuitively obvious, which is (Maybe Ax) -> (Maybe Tree) -> (Maybe Sound). Have I missed something and these all inter-convert into each other?

Xanthir wrote:This is just an intermediate thing, to get us on the way to the comonad. You're right that it's "storing a group of pure functions" - it's just partially applying an Immutable→ChangeInstruction→Immutable function. Remember, in this kind of chaining syntax you can "cut" it wherever you want, defining a function with any number of arguments. The 2-arg form is (Immutable, ChangeInstruction)→Immutable: it takes an Immutable and a ChangeInstruction, and returns a new Immutable. The 1-arg form is Immutable→(ChangeInstruction→Immutable): it takes an Immutable, and returns what I'm calling a "Mutable" - a function that'll take a ChangeInstruction and return a new Immutable. It's a really weak form of "mutability", since it can only be mutated *once*, but that's all we need to get going with this concept.

OK, I understand this, and your explanation has been great. :)

A "mutation function" takes the arguments it needs to specify the mutation it's going to do (like the angle to rotate the shape by), and a "Mutable", in our terms, and mutates the Mutable accordingly. The rotate() signature is something like Angle→Mutable→Immutable. Once you pass in the Angle, you're left with a Mutable→Immutable function, and this is the part we care about. Now, the point of rotate() is that it constructs the ChangeInstructions for us. It produces some rotation ChangeInstruction (in this case, a list containing a single rotate transform), and passes it to the Mutable (which is a function, remember).

I can just about understand this as well, although it gets kinda shaky because you're passing a function as a value in the middle there. I'm used to the idea of a first-class function, but it's hard to see that Angle->Mutable->Immutable and Angle->ChangeInstruction->Immutable->Immutable are the same. Or have I misunderstood and they aren't the same? (What does it mean to call the latter function with just an angle, since you said it produces its own ChangeInstruction?)

[...helpful stuff about extend...]

Code: Select all

func extend(Func mutFunc, Mutable mut) {
  Mutable finalMutable = func(ChangeInstruction after) {
    Mutable fakeMutable = func(ChangeInstruction before) {
      Shape immut = mut(before + after);
      return immut;
    };
    Shape immut = mutFunc(fakeMutable);
    return immut;
  };
  return finalMutable;
}

So there's some fun back-and-forth that happens here.

No kidding. :P While I'm reasonably sure I get what's going on here, it's immensely hard to follow because the logic seems to be written backwards and inside-out, i.e. when the function extend() returns is executed, flow of control winds up in the innermost-function first, and then unwinds out. I guess it looks clearer if you're writing in a syntax that's designed around this sort of thing. (Although thank you for posting in C-style, since I'm even worse at parsing Haskell.)

The important bit is the "fake" mutable we build on line 3. By passing the fake to the first mutation function, rather than our real Mutable, we can "intercept" the ChangeInstruction that the mutation function is trying to pass to the Mutable. Once it's intercepted, we can combine it with the other ChangeInstruction that the second, later mutation function is giving us, so we only actually call a single real Mutable, and thus only do all the expensive transform work once.

I think this was the part I didn't get originally. As I said, I'm used to a C#/Java environment, so I didn't realize Haskell could do function composition in a way that meant the result was "truly" one function that didn't involve extra stack frames, allocations for return values and such. (As opposed to the dirty hack in the code snippet I posted, where the "single function" is built of a bunch of nested closures.)

Now we can chain the mutations together:
[...code...]
And each mutation function doesn't have to give a shit about this; all it has to do is construct a ChangeInstruction and pass it to the Mutable it receives!

Right... I think. :) I'm still not entirely comfortable with the idea of a mutation function and a ChangeInstruction being different things on a purely intuitional level, but I can see how this result works once you make them different things.

Nope, you just do like "mut2 = extend(rotate30deg, mut1)" and you get another Mutable back that already has the 30deg rotation "baked in". You can then just go pass that Mutable around freely, and don't have to keep track of anything else. You can extract the Shape whenever you want by just calling "mut([])" (no additional transform). You can even keep around multiple version with different amounts of stuff baked in, and decide at the end which one you want to instantiate; the rest are essentially free, since they're just a couple of extra function objects that haven't done any real work.

Since you pointed out that a StringBuilder works on this pattern, I can see the difference now. (Although a StringBuilder can't do the multiple versions thing, AFAIK)

You seem to be talking about affine transforms; they're definitely associative, don't worry.

Affine transformation as in these things...? I don't see how they can apply to code in this context.
...And that is how we know the Earth to be banana-shaped.

User avatar
chridd
Has a vermicelli title
Posts: 840
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: Coding: Fleeting Thoughts

Postby chridd » Sat Sep 26, 2015 8:28 am UTC

Robert'); DROP TABLE *; wrote:2) that you can slice multi-value function signatures into any precedence you want, i.e. (X->Y)->Z == X->(Y->Z)
This isn't true. However, X->(Y->Z) is equivalent to (X, Y)->Z, where (X, Y) is a tuple type. (E.g., a function add(x, y) = x + y can be written as a function that takes a tuple, say (2, 3) ((number, number) -> number); or as a function that takes a number, say 2, and then returns a function that adds 2 to things (number -> (number -> number)), but it's not a function that can take a single function as an argument and return a number ((number -> number) -> number))

then when you apply Maybe to this function, what do you get? Applying the rules produces a (Maybe Ax) -> Maybe (Tree -> Sound), but I have no idea about what a Maybe-function means, since it suggests you might wind up asking what happens if you call None.
You can't call a maybe function directly; you have to somehow get it out of the Maybe to call it, just like you have to get a number out of the Maybe to do math on it. No different than when you want to pass a maybe value to a function that doesn't expect a Maybe.

The other possible arrangement of Maybe (Ax -> Tree) -> Maybe Sound makes slightly more sense, but still doesn't appear to be the same thing as the answer that appears intuitively obvious, which is (Maybe Ax) -> (Maybe Tree) -> (Maybe Sound). Have I missed something and these all inter-convert into each other?
There's Maybe (Ax, Tree) -> Maybe Sound, and it's possible to convert (Maybe Ax, Maybe Tree) into Maybe (Ax, Tree) (though this can lose information if you only have one or the other).
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she · Forum game scores
mittfh wrote:I wish this post was very quotable...

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Sun Sep 27, 2015 5:52 am UTC

Robert'); DROP TABLE *; wrote:2) that you can slice multi-value function signatures into any precedence you want, i.e. (X->Y)->Z == X->(Y->Z)

This isn't precisely correct as you've written it. Yes, you can slice them however you want, but the things on the LHS all become arguments, not functions. That is, given X→Y→Z, you can chop it at the first → to get X→(Y→Z) (a 1-arg function that takes an X, and returns a Y→Z function), or you can chop it at the second to get (X, Y)→Z, a two-arg function that takes an X and a Y, and return a Z.

(X→Y)→Z is, instead, a 1-arg function that takes an X→Y function and returns a Z.

(Oh wait, chridd already said this.)

then when you apply Maybe to this function, what do you get? Applying the rules produces a (Maybe Ax) -> Maybe (Tree -> Sound), but I have no idea about what a Maybe-function means, since it suggests you might wind up asking what happens if you call None. (As opposed to just passing None to a function expecting a Maybe T) The other possible arrangement of Maybe (Ax -> Tree) -> Maybe Sound makes slightly more sense, but still doesn't appear to be the same thing as the answer that appears intuitively obvious, which is (Maybe Ax) -> (Maybe Tree) -> (Maybe Sound). Have I missed something and these all inter-convert into each other?

That's a different topic - Applicative Functors. They lie between functor and monad in complexity. (Luckily, almost all realistic functors are applicative; you have to get weird to find one that isn't, afaict.)

I can just about understand this as well, although it gets kinda shaky because you're passing a function as a value in the middle there. I'm used to the idea of a first-class function, but it's hard to see that Angle->Mutable->Immutable and Angle->ChangeInstruction->Immutable->Immutable are the same. Or have I misunderstood and they aren't the same?

They're not the same as written - you need some parens. ^_^ Angle→Mutable→Immutable is the same as Angle→(ChangeInstruction→Immutable)→Immutable. That's just variable substitution.

(What does it mean to call the latter function with just an angle, since you said it produces its own ChangeInstruction?)

It takes two arguments, an Angle (from which it produces a ChangeInstruction), and a function that takes a ChangeInstruction and produces an Immutable. It then passes the ChangeInstruction it produced to the function it was passed, and returns the result.

If you pass only the Angle, you're left with a function that's (ChangeInstruction→Immutable)→Immutable - it's waiting for you to pass it a mutable shape so it can apply the change and hand you back the Immutable result.

No kidding. :P While I'm reasonably sure I get what's going on here, it's immensely hard to follow because the logic seems to be written backwards and inside-out, i.e. when the function extend() returns is executed, flow of control winds up in the innermost-function first, and then unwinds out. I guess it looks clearer if you're writing in a syntax that's designed around this sort of thing. (Although thank you for posting in C-style, since I'm even worse at parsing Haskell.)

Yeah, it just requires some study, and some familiarity with this kind of style helps. And I definitely did it C-style on purpose, to make it more familiar.

The important bit is the "fake" mutable we build on line 3. By passing the fake to the first mutation function, rather than our real Mutable, we can "intercept" the ChangeInstruction that the mutation function is trying to pass to the Mutable. Once it's intercepted, we can combine it with the other ChangeInstruction that the second, later mutation function is giving us, so we only actually call a single real Mutable, and thus only do all the expensive transform work once.

I think this was the part I didn't get originally. As I said, I'm used to a C#/Java environment, so I didn't realize Haskell could do function composition in a way that meant the result was "truly" one function that didn't involve extra stack frames, allocations for return values and such. (As opposed to the dirty hack in the code snippet I posted, where the "single function" is built of a bunch of nested closures.)

There's nothing special about Haskell here; this works just as well in Javascript or any other language that has first-class functions to begin with. It does build a lot of nested closures, but the important part is that, rather than each one doing an expensive Immutable→Mutable→Immutable transformation, each one just builds up the eventual ChangeInstruction, larger and larger, until the very last one actually applies it in a single operation. Building up ChangeInstructions is cheap (by assumption).

Right... I think. :) I'm still not entirely comfortable with the idea of a mutation function and a ChangeInstruction being different things on a purely intuitional level, but I can see how this result works once you make them different things.

In this case, a ChangeInstruction can just be a list of things like

Code: Select all

[ ("rotate", 30), ("scale", 2), ...]
. That is, just a record of the changes you eventually want to make. If you know CSS, the value of the 'transform' property is the concept I'm shooting for.

Since you pointed out that a StringBuilder works on this pattern, I can see the difference now. (Although a StringBuilder can't do the multiple versions thing, AFAIK)

Yeah, because it's mutating. A non-mutating version would just collect the string pieces into a cheaply-copyable form (like a linked list), and return new objects each time. That would make things more expensive, tho, and less of a win for small strings.

Affine transformation as in these things...? I don't see how they can apply to code in this context.

Rotate/scale/etc are affine transforms. As usual, Math wikipedia is terrible.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Coding: Fleeting Thoughts

Postby ahammel » Sun Sep 27, 2015 3:16 pm UTC

Xanthir wrote:That's a different topic - Applicative Functors. They lie between functor and monad in complexity. (Luckily, almost all realistic functors are applicative; you have to get weird to find one that isn't, afaict.)
The tagged tuple is one.

Code: Select all

fmap f (tag,value) = (tag,f value)
Is fine and dandy, but

Code: Select all

pure value = (???,value)
Can't be lawfully defined because there's no way to make an base-case value for tags of arbitraty type. Similarly

Code: Select all

apply (tag,f) (otherTag,value) = (???,f value)
Doesn't work because there's no lawful way to combine arbitrary tags.
He/Him/His/Alex
God damn these electric sex pants!

Ubik
Posts: 1016
Joined: Thu Oct 18, 2007 3:43 pm UTC

Re: Coding: Fleeting Thoughts

Postby Ubik » Sun Sep 27, 2015 3:46 pm UTC

I've rewritten my OpenGL wrapper - again. This time I intend to go forward with what I have now and want to build higher level concepts on the current base. Now things are getting hard and it's making me noticeably anxious. Today I have mostly walked in a circle and though what would be my next target and tried to imagine what lies further ahead.

Edit: Oh, no need to move on today. Indexed drawing doesn't work and can't figure why.

Edit 2: Fixed at least two bugs. Vertex arrays and index buffers are not easy to handle, at least not with my approach...

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Sun Sep 27, 2015 8:34 pm UTC

Note that X->Y->Z can be written X->(Y->Z). (X,Y)->Z is another way to write that (uncurried).

(X->Y)->Z doesn't work, because it takes a function from X->Y, and returns an element of Z.

Now, (X->Y)->(X->Z) can be created from (X->Y->Z) easily (You have a function from X,Y to Z. and you provide a function from X to Y. You just take your X, feed it to X->Y, then feed both it and the resulting Y to the original function), as can Y->X->Z (you take your X->Y->Z, and you attach a passed Y to it. Then when you pass the X, you take the stored Y and pass it in, getting a Z).

One issue with the -> notation is that there are many trivial transformations -- X->Y->Z <-> Y->X->Z -- that act *as if they matter*. Much like a multi-linear transformation doesn't care which argument you pass it first, neither does a multi-argument function. All there is to that is syntax, and it is the very "->" syntax (and derived ones) that cause the issue.

Positional arguments in general have this problem. You can see this in some languages with named arguments, in which X->Y->Z and Y->X->Z are "the same thing" -- you literally say "Call with X=blah and Y=blah". A bit of syntax and we can have partial function application we get gravy.

Haskell seems to embrace this from what I can tell (but I'm no expert) -- overly complex type descriptions and transformations that seem meaningful, but are really just juggling of syntax. This is true to such a great extent that often the *type* of a function is used as a short-hand for its implementation when people talk about the function! Because the only thing the function "reasonably" does is juggle the types of the arguments to new arrangement, and nothing else.
Xanthir wrote:
Affine transformation as in these things...? I don't see how they can apply to code in this context.

Rotate/scale/etc are affine transforms. As usual, Math wikipedia is terrible.

Really, that is terrible? The first two paragraphs read clear to me. The only question is "what is an affine space", and if you drop the adjective "affine" as a preliminary, everything else is basically true.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: Coding: Fleeting Thoughts

Postby Robert'); DROP TABLE *; » Tue Sep 29, 2015 12:05 am UTC

(Yay, another question-laden post. Thanks for the help and explanation so far, I've learned a lot more than trying to scrape the various wikis.)
chridd wrote:This isn't true. However, X->(Y->Z) is equivalent to (X, Y)->Z, where (X, Y) is a tuple type. (E.g., a function add(x, y) = x + y can be written as a function that takes a tuple, say (2, 3) ((number, number) -> number); or as a function that takes a number, say 2, and then returns a function that adds 2 to things (number -> (number -> number)), but it's not a function that can take a single function as an argument and return a number ((number -> number) -> number))

Xanthir wrote:This isn't precisely correct as you've written it. Yes, you can slice them however you want, but the things on the LHS all become arguments, not functions. That is, given X→Y→Z, you can chop it at the first → to get X→(Y→Z) (a 1-arg function that takes an X, and returns a Y→Z function), or you can chop it at the second to get (X, Y)→Z, a two-arg function that takes an X and a Y, and return a Z.

(X→Y)→Z is, instead, a 1-arg function that takes an X→Y function and returns a Z.

(Oh wait, chridd already said this.)

Thanks for the help, what you've both said makes a lot more sense now. It's suddenly become much more obvious that (X->Y)->Z doesn't make sense, since there's nowhere for the Y to come from except from the X, and that's not true of (X, Y) -> Z.

You can't call a maybe function directly; you have to somehow get it out of the Maybe to call it, just like you have to get a number out of the Maybe to do math on it. No different than when you want to pass a maybe value to a function that doesn't expect a Maybe.

Thanks for the help. Is it valid to consider "function invocation" a (class of) high-order function in itself that you can apply applicatives/monads to, or does that lead to a paradox somehow? (I'm thinking that "invoke a 1-arg function" would have signature (X->Y)->X->Y.)

There's Maybe (Ax, Tree) -> Maybe Sound, and it's possible to convert (Maybe Ax, Maybe Tree) into Maybe (Ax, Tree) (though this can lose information if you only have one or the other).

Is it possible to do that conversion in reverse? It would seem strange to me that you could have two equivalent forms of the same function ( (Ax,Tree) -> Sound and Ax -> Tree -> Sound) and only be able to use the applicative on one of them, or have a one-way conversion.

Xanthir wrote:That's a different topic - Applicative Functors. They lie between functor and monad in complexity. (Luckily, almost all realistic functors are applicative; you have to get weird to find one that isn't, afaict.)

Ah. I wasn't entirely sure on whether it was a seperate rule or some derivable property of a standard functor. I saw a statement of the difference between functors, applicatives and monads on the Haskell wiki, but didn't understand it beyond that monads are special cases of applicatives are special cases of functors, and that the signatures of the respective "apply function to this value" functions were slightly different. Is there an ELI5 explanation of what the differences mean and what they imply about how the value inside the functor can be transformed? :)

There's nothing special about Haskell here; this works just as well in Javascript or any other language that has first-class functions to begin with. It does build a lot of nested closures, but the important part is that, rather than each one doing an expensive Immutable→Mutable→Immutable transformation, each one just builds up the eventual ChangeInstruction, larger and larger, until the very last one actually applies it in a single operation. Building up ChangeInstructions is cheap (by assumption).

In this case, a ChangeInstruction can just be a list of things like

Code: Select all

[ ("rotate", 30), ("scale", 2), ...]
. That is, just a record of the changes you eventually want to make. If you know CSS, the value of the 'transform' property is the concept I'm shooting for.

I'm very short of time just now, so I think I'll have to give this some more thought and get back to you, because there's something I'm still not understanding in the difference between what you can do in Haskell vs. what my original C# snippet did.

Rotate/scale/etc are affine transforms. As usual, Math wikipedia is terrible.

Oh, I'm confused because, IIRC, the original comment about associativity was about arbitarary (C#) mutations on an Immutable object, and I wasn't clear on how to even test the question, since AFAIK function composition is always associative.
...And that is how we know the Earth to be banana-shaped.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 11 guests