Home freenode/#haskell: Logs Calendar

Logs: freenode/#haskell

←Prev  Next→
Page 1 .. 418 419 420 421 422 423 424 425 426 427 428 .. 5022
— 502,152 events total
2020-10-05 02:47:54 <SirClueless> ski Yeah, tail recursion is another important one. Lots of languages end up *requiring* tail recursion as a result, because in practice it affects correctness even if you are a pure functional language for all formal purposes
2020-10-05 02:48:14 <ski> GHC tends to try to not apply "optimizations" which worsen space or time complexity
2020-10-05 02:48:39 × Samos quits (~Kira@201.192.165.173) (Quit: WeeChat 2.9)
2020-10-05 02:48:43 <dsal> tail recursion is a "how" rather than a "what"
2020-10-05 02:48:49 <ski> yes
2020-10-05 02:49:10 <SirClueless> Sure, but it doesn't make guarantees that it *will* make certain optimizations, you just have to assume when it will or not
2020-10-05 02:49:22 <ski> (e.g. CSE can cause worse space usage, so GHC doesn't do much of it)
2020-10-05 02:49:54 <SirClueless> Whether or not you have tail recursion means that certain computations will either complete successfully in a reasonable amount of memory, or blow the stack of every machine ever produced
2020-10-05 02:50:34 <SirClueless> Sure it's just "how" not "what" but at some point "how" becomes "this is no longer computable" and every software engineer in existence has to start caring
2020-10-05 02:50:40 <ski> i think, as a first approximation, it's quite safe to assume that GHC does by-need / lazy reduction. one can also think of this as graph reduction (with e.g. shared nodes caching results)
2020-10-05 02:51:17 <ski> iirc PFDS' analysis of algorithms take this into account
2020-10-05 02:51:22 <ski> @where PFDS
2020-10-05 02:51:22 <lambdabot> http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504
2020-10-05 02:52:25 <ski> anyway, even with "proper tail recursion" (which is what Scheme calls it), that doesn't exactly mandate how you'll implement it. it doesn't have to be TCO, e.g. ..
2020-10-05 02:52:57 lagothrix is now known as Guest19440
2020-10-05 02:52:57 × Guest19440 quits (~lagothrix@unaffiliated/lagothrix) (Killed (tolkien.freenode.net (Nickname regained by services)))
2020-10-05 02:53:03 → lagothrix joins (~lagothrix@unaffiliated/lagothrix)
2020-10-05 02:53:55 <dolio> Yeah, scheme just says it's bounded, right?
2020-10-05 02:54:37 <ski> yep
2020-10-05 02:54:54 <ski> must support an unbounded number of active tail calls in bounded space
2020-10-05 02:55:18 <dolio> Bounded by what?
2020-10-05 02:55:20 → zacts joins (~zacts@dragora/developer/zacts)
2020-10-05 02:57:17 <dolio> Doesn't seem like it says.
2020-10-05 02:59:13 <ski> iirc, Chicken just uses the C stack, with CPS code, making it ever deeper, never returning in C, instead GCing the "stack" (which acts like a heap), compacting it, when necessary
2020-10-05 02:59:50 <SirClueless> I guess I'm too much of a systems programmer to enjoy Haskell :D "You can assume the graph is reduced in a reasonably efficient way" is missing an axis of correctness that matters to me just as much as actually delivering the correct result of the computation
2020-10-05 02:59:58 ski . o O ( "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." by Henry G. Baker in 1995-09 at <https://web.archive.org/web/20200223051632/http://home.pipeline.com:80/~hbaker1/CheneyMTA.html> )
2020-10-05 03:00:01 × torax quits (~torax@185.163.110.116) ()
2020-10-05 03:00:46 <ski> (and, MIT Scheme remembers the last 100 calls (including tail calls), for debugging purposes)
2020-10-05 03:01:44 <dolio> If you care about performance, then implementation details matter, not just the language specification.
2020-10-05 03:02:14 × zaquest quits (~notzaques@5.128.210.178) (Quit: Leaving)
2020-10-05 03:02:32 <quintasan> holy smokes
2020-10-05 03:02:46 <quintasan> I think I'm starting to get it but at the same time I'm not getting it
2020-10-05 03:03:10 ski . o O ( "PCLSRing: Keeping Process State Modular" by Alan Bawden at <http://fare.tunes.org/tmp/emergent/pclsr.htm> ; <https://en.wikipedia.org/wiki/PCLSRing> ; "PCLSRING in Semantics" by Robert Harper in 2016-07-11 at <https://existentialtype.wordpress.com/tag/pclsring/> )
2020-10-05 03:03:14 <SirClueless> ^^ Well sure, but for example, using a language whose definition is "it must behave the same as this abstract machine defined here" which is how C or C++ work, means that unless the implementation expands primitive machine ops into non-constant evaluations, you can make guarantees about runtime
2020-10-05 03:03:17 → zaquest joins (~notzaques@5.128.210.178)
2020-10-05 03:04:19 <quintasan> If I get IO (Int32, Text) and have a record Tea then I can - `fmap (uncurry Tea) $ functionThatGivesIO`. How do I do this for IO [(Int32, Text)] to get IO [Tea]?
2020-10-05 03:05:17 <koz_> quintasan: You fmap twice.
2020-10-05 03:05:41 <dolio> I don't believe that C and C++ specify enough in the language specification to guarantee good performance.
2020-10-05 03:05:55 × brandly quits (~brandly@c-73-68-15-46.hsd1.ma.comcast.net) (Ping timeout: 240 seconds)
2020-10-05 03:06:08 <koz_> dolio: Since UB is a thing, they _can't_.
2020-10-05 03:06:42 <quintasan> wait, so I just fmap . fmap (uncurry Tea) $ functionThatGivesIOArray ?
2020-10-05 03:06:53 <koz_> quintasan: Not quite.
2020-10-05 03:07:05 <koz_> But you're on the right track.
2020-10-05 03:07:09 <koz_> Consider the type of fmap:
2020-10-05 03:07:11 <koz_> :t fmap
2020-10-05 03:07:13 <lambdabot> Functor f => (a -> b) -> f a -> f b
2020-10-05 03:07:29 ski . o O ( "Exceptional Syntax" by Nick Benton,Andrew Kennedy in 2001-07 at <https://www.microsoft.com/en-us/research/publication/exceptional-syntax/>,<http://lambda-the-ultimate.org/node/1193>,.. )
2020-10-05 03:07:30 <koz_> Now, if f ~ IO, you get (a -> b) -> IO a -> IO b
2020-10-05 03:07:38 ski . o O ( ..,<https://web.archive.org/web/20161027043544/http://mjambon.com/extend-ocaml-syntax.html#lettry>,<https://blog.janestreet.com/pattern-matching-and-exception-handling-unite/> )
2020-10-05 03:08:01 <SirClueless> koz_ they can't guarantee runtime of programs that contain UB, for sure, but other programs they might be able to (with a lot of assumptions about the machine you're executing on)
2020-10-05 03:08:06 <koz_> Now, in your case, a ~ [(In32, Text)], and the b you want is [Tea].
2020-10-05 03:08:11 <koz_> SirClueless: There's also IB.
2020-10-05 03:08:24 <koz_> So no, even if we assume no UB, the standard cannot guarantee very much at all.
2020-10-05 03:08:34 <koz_> s/In32/Int32/
2020-10-05 03:08:46 <koz_> So therefore, your function has to have that type.
2020-10-05 03:08:58 <koz_> Now, you have something that types that way - fmap (uncurry Tea).
2020-10-05 03:08:58 <quintasan> So ideally I'd write a function for [(Int32, Text)] -> [Tea] and fmap this?
2020-10-05 03:09:06 <koz_> You can, but in this case, you don't need to.
2020-10-05 03:09:24 <koz_> You would have fmap (fmap (uncurry Tea)).
2020-10-05 03:10:02 <ski> quintasan : `fmap (map (uncurry Tea)) actionThatGivesIOList',`(fmap . map) (uncurry Tea) actionThatGivesIOList',`(fmap . map . uncurry) Tea actionThatGivesIOList',`map (uncurry Tea) <$> actionThatGivesIOList',`(uncurry Tea <$>) <$> actionThatGivesIOList'
2020-10-05 03:10:21 × bloodstalker quits (~bloodstal@46.166.187.154) (Read error: Connection reset by peer)
2020-10-05 03:10:29 <koz_> That last one is a step too far IMHO.
2020-10-05 03:10:49 <SirClueless> It sounds like they can guarantee more than Haskell can though -- if only because they can't really express lazy evaluation and whether or not its result is immediately available
2020-10-05 03:11:08 <quintasan> I still have no idea what <$> and <*> do but I decided that won't stop me from making this work.
2020-10-05 03:11:20 <koz_> quintasan: <$> is just infix fmap.
2020-10-05 03:11:22 <quintasan> koz_, ski: thanks
2020-10-05 03:12:13 <koz_> SirClueless: I don't know how much you could guarantee about the performance of a C program given the standard.
2020-10-05 03:12:21 <koz_> You first must ensure that neither IB nor UB applies.
2020-10-05 03:12:23 → aarvar joins (~foewfoiew@50.35.43.33)
2020-10-05 03:12:54 <koz_> Then after that point, you gotta deal with the fact that the standard makes few promises about, say, type widths.
2020-10-05 03:13:05 <koz_> Which might _significantly_ alter, for instance, how many times a loop will execute.
2020-10-05 03:13:54 <koz_> There's probably _thousands_ of other small things there too.
2020-10-05 03:14:44 <koz_> Maybe it's _different_ to the Haskell case, but 'more'? I doubt it.
2020-10-05 03:14:54 <ski> SirClueless : those last links were about interaction of tail calls with exception handlers (not having the dynamic extent of the handler include the tail call)
2020-10-05 03:15:13 <ski> this suggests it may be a good idea, having `catchBind :: Exception e => IO a -> (e -> IO b) -> (a -> IO b) -> IO b)' / `handleBind :: Exception e => (e -> IO b) -> (a -> IO b) -> (IO a -> IO b)', and not just `catch :: Exception e => IO a -> (e -> IO a) -> IO a',`handle :: Exception e => (e -> IO a) -> (IO a -> IO a)',`try :: Exception e => IO a -> IO (Either e a)'
2020-10-05 03:15:55 × drbean quits (~drbean@TC210-63-209-23.static.apol.com.tw) (Read error: Connection reset by peer)
2020-10-05 03:18:14 <ski> (and perhaps some custom syntax for this, like the `let'-`try' above, which OCaml now supports as pattern-matching <https://caml.inria.fr/pub/docs/manual-ocaml/coreexamples.html#s%3Aexceptions>)
2020-10-05 03:19:07 × justsomeguy quits (~justsomeg@unaffiliated/--/x-3805311) ()
2020-10-05 03:19:09 <SirClueless> Maybe I just already understand all the tradeoffs in C better? Like, I can't think of any way to sneak exponential runtime into a C program -- it would take some *very* obscure interactions. But you can certainly sneak some UB into a C program and that's perhaps worse.
2020-10-05 03:19:30 × perrier-jouet quits (~perrier-j@modemcable012.251-130-66.mc.videotron.ca) (Quit: WeeChat 2.9)
2020-10-05 03:20:08 → perrier-jouet joins (~perrier-j@modemcable012.251-130-66.mc.videotron.ca)
2020-10-05 03:20:49 → Stanley00 joins (~stanley00@unaffiliated/stanley00)
2020-10-05 03:21:29 → snakemasterflex joins (~snakemast@213.100.206.23)
2020-10-05 03:21:39 → tekojo joins (~tekojo@s91904426.blix.com)
2020-10-05 03:21:47 ski . o O ( "A Guide to Undefined Behavior in C and C++" by John Regehr, "Part 1" in 2010-07-09 at <https://blog.regehr.org/archives/213>,"Part 2" in 2010-07-23 at <https://blog.regehr.org/archives/226>,"Part 3" in 2010-07-30 at <https://blog.regehr.org/archives/232> )
2020-10-05 03:22:29 <koz_> SirClueless: Do you understand C-as-the-standard-calls-it? Or C-as-your-favourite-compiler-implements-it?
2020-10-05 03:22:36 <koz_> Those may, or may not, be the same thing.
2020-10-05 03:23:39 <SirClueless> I try, as far as possible, to understand C (and more often C++) as the standard guarantees it. Obviously the C++ standard is like 10k pages or something stupid so there's no way to claim I understand it all.
2020-10-05 03:25:16 <c_wraith> The standard guarantees so little in C. I don't think it's actually possible to write non-trivial code that's portable across all spec-compliant C compilers.
2020-10-05 03:25:31 <SirClueless> But there are ways to guarantee some things even in standard C++ that you can't really in Haskell afaict. For example the ability to interpret bytes in an IO device DMA buffer as data without any copying.
2020-10-05 03:25:38 <koz_> c_wraith: I remember that one C99 draft made memmove impossible to write.
2020-10-05 03:25:55 × snakemasterflex quits (~snakemast@213.100.206.23) (Ping timeout: 240 seconds)
2020-10-05 03:27:00 <c_wraith> SirClueless: sure you can... but it's going to be awkward to use because Haskell forces you to understand that the backing bytes could change at any time.
2020-10-05 03:29:01 <SirClueless> Yes, but using C++ allows you to rely on memory guarantees provided by the device itself. FWIW C++ forces you to understand too that backing bytes can change at any time (it's just less strict about writing programs that fail to acknowledge that fact). This is basically the purpose of the volatile keyword.
2020-10-05 03:29:19 <c_wraith> right. The point of Haskell is that you can't fail to acknowledge it.
2020-10-05 03:29:46 × zacts quits (~zacts@dragora/developer/zacts) (Ping timeout: 256 seconds)
2020-10-05 03:30:14 <dolio> DMA of an IO device is in the C++ standard?
2020-10-05 03:33:08 <SirClueless> Yes. In that there are standard-compliant ways that a device vendor can provide you with a buffer that you can use in productive ways. When you do that you rely on the standard, the linux kernel, the x64 ISA, a certain pointer addressing mechanism, etc. but that's all stuff that's well defined even if it's not portable.
2020-10-05 03:34:08 → polyrain joins (~polyrain@2001:8003:e501:6901:a41a:145a:3fce:c107)
2020-10-05 03:35:35 <dolio> So that's actually a no.
←Prev  Next→
Page 1 .. 418 419 420 421 422 423 424 425 426 427 428 .. 5022

All times are in UTC.