Live data from Hacker News

John Carmack on Functional Programming in C++ (2018)

sevangelatos.com

171–179 of 179 posts

Re: John Carmack on Functional Programming in C++ (2018)

#171

Earlier quoted context omitted.

Start with this representation: struct Node { uint bitmap; KeyValuePair [] entries; Node [] children; // Node = Leaf of bitmap * children | Internal of bitmap * children // We inline that sum into a struct where // Leaf -> entries != null // Internal -> children != null } Now consider the case where leaves are somewhat sparse. That means the children arrays will have few entries, so instead of allocating a bunch of o…

I belatedly realized this might require some explanation too. Sorry, too many years of experiments and microoptimizations. This is an unboxed representation of a sum type. Rather than relying on the CLR's inheritance to model sums I lay it out explicitly at the cost of a little space. It may seem wasteful since it looks like I'm adding 8 unused bytes to each node, but the CLR object header is 16 bytes so you're actua…

> You might even challenge the mutable dictionary for performance!

Don't tell me that, I'm an optimisation nut, I might actually do it! ;)

I woke up this morning with a clear understanding of what your optimisation is, so I guess I just needed to load up my brain with the details! It's definitely a super interesting approach and one that I'm surprised I've not come across before.

I'm definitely a bit wary of changing my current implementation, mostly because it's been battle hardened, but I'm sure I won't be able to resist having a go at some point. Thanks for the tip!

Re: John Carmack on Functional Programming in C++ (2018)

#172
post #162

Earlier quoted context omitted.

>I know when I've constricted my data enough, it's when I know all the components of all types have been constricted enough. > Do you not see that this is a tautology? It might be if you hadn't butchered what I wrote. If I have a type called Month, and it can only accept values 1-12. Then I know I have constrained that type enough. If I then create types called Day and Year and constrain those I know they're constrai…

>into a record type called Appointment, etc. etc This breaks down in the etc. What if an appointment is not valid on them weekend, or a holiday, or when someone's child has soccer practice, or when that appointment conflicts with another one. There are all sorts of restriction that can be added and yes they technically cover some potential bug that someone technically could introduce. It may be hard to predict all of…

> This breaks down in the etc. What if an appointment is not valid on them weekend, or a holiday, or when someone's child has soccer practice, or when that appointment conflicts with another one.

Either the rules are an instrinsic part of an appointment or they're not. If you need something that represents exceptions to the state of a basic appointment then that's the job of the containing type (say a type called WeeklySchedule or something like that). Just like `Day` can be [1..31], but when used in a a `Date` then the constructor of `Date` wouldn't allow a `Day` of 31 and a `Month` of 2.

> At compile time 99% of the time they are closed. Languages also add features to let you make it closed.

You can't close an interface.

> This is impossible in the real world where hardware issues are real.

Exceptions in imperative-land tend to be used for all errors, not just exceptional ones, but expected ones. The problem is that no one knows what these side-effects are from the surface (i.e. a function prototype doesn't expose it).

Truly exceptional events should probably shut down the application (things like out-of-memory), or, as with Erlang, escalate to a supervision node that would restart the service.

Exceptions exist in functional languages too. However, expected errors, like 'file not found' and other application level 'could happen' errors should be caught at the point they are raised and represented in the type-system.

For example, a common pure pattern would be `Either l r = Left l | Right r` where the result is either a success (Right) or an alternative value (Left - usually used to mean 'failed').

When your function has this in its declaration, you are then aware of possible alternative paths your code could go down. This isn't known with exceptions.

For example the `parseInt` from C# and Haskell (below), one declares its side-effect upfront, then other doesn't. It may be semi-obvious that the C# one must throw an exception, but that isn't the only outcome - it could return `0`.

    int parseInt(string x);

    parseInt :: String -> Either Error Int
This confusion of what happens inside large blocks of code is exactly the issue I'm trying to highlight.

> Total functions also don't allow for infinite loops which is common place in real systems that mare expected to potentially run forever instead of only being able to serve 1000 requests before exiting.

In pure maths, sure, in reality yeah they do. Haskell has ⊥ [1] in its type-system for exactly this reason.

Anyway, you seem hellbent on shooting down this approach rather than engaging in inquisative discussion about something you don't know or understand. So, this will be my last reply in this thread. Feel free to have the last word as I'm not wasting more time explaining something that is literally about soundness in code and why it's valuable. If you don't get it now, you never will.

[1] https://wiki.haskell.org/Bottom

Re: John Carmack on Functional Programming in C++ (2018)

#173

Earlier quoted context omitted.

It's not just the ADTs but the exhaustive pattern matching that help make sure you've covered all of the cases in your ADT. You'll see JavaScripters use objects as a poor man's ADT where they'll use the key name as a the constructor or a { tag: key, ... }, but that has caveats (aside from feeling less first-class): 1) JavaScript can't do exhaustive pattern matching so you'll always need to handle null cases, 2) check…

That Typescript ADT example is heavily outdated (or explicitly obtuse) class Bar { tag="bar" as const; constructor(public value:string){} } class Baz { tag="baz" as const; constructor(public value:boolean){} } type Foo = Bar|Baz;

That is better, but it's still nowhere near `type Foo = Bar String | Baz Boolean`. It's also nowhere as clean to pattern match on.

Re: John Carmack on Functional Programming in C++ (2018)

#174
post #171

Earlier quoted context omitted.

I belatedly realized this might require some explanation too. Sorry, too many years of experiments and microoptimizations. This is an unboxed representation of a sum type. Rather than relying on the CLR's inheritance to model sums I lay it out explicitly at the cost of a little space. It may seem wasteful since it looks like I'm adding 8 unused bytes to each node, but the CLR object header is 16 bytes so you're actua…

> You might even challenge the mutable dictionary for performance! Don't tell me that, I'm an optimisation nut, I might actually do it! ;) I woke up this morning with a clear understanding of what your optimisation is, so I guess I just needed to load up my brain with the details! It's definitely a super interesting approach and one that I'm surprised I've not come across before. I'm definitely a bit wary of changing…

Do it! Do it! Do it! If only for a couple of tests to see how much it changes the results. ;-)

Unboxing sums is a nice optimization but then you can't naively use switch-patern matching to deconstruct them.

I have a bunch of other things in Sasa and other libraries you might find useful. I'm not actively working on most of them anymore except for bug fixes. I learned a lot but didn't end up using a lot of these features as much as I'd hoped.

For instance, being able to create open instance delegates in a way that automatically works around the CLR limits against such delegates to virtual methods. Some of the concurrency primitives are also interesting, as they implement an efficient atomic read/write protocols for arbitrary sized types using only volatile reads/writes (ie. avoid torn reads), and a sort of LLSC using only volatile read/write and a single interlocked inc/dec. Also, I added a kind system to CLR reflection to make working with it much easier [2].

It seems we're thinking along the same lines for numeric types. I reproduced the Haskell numeric hierarchy [1], but I put that on hold because I was thinking a [Deriving] attribute would eliminate a lot of redundancy.

Just FYI, clicking Num on the main GitHub markdown page doesn't jump to the link on the markup.

Lots more to see if you're interested! I've played with parser combinators but never liked how they turned out, and settled on a simpler approach that was pretty interesting.

[1] https://github.com/naasking/HigherLogics.Algebra

[2] https://github.com/naasking/Dynamics.NET#kind-system

Re: John Carmack on Functional Programming in C++ (2018)

#176

Why aren't more universities teaching functional programming first to form good mental models for the students and then show them when to use state and when to not. Why is everyone teaching Python?

I think many CS degrees teach FP, I remember learning a variant of SML (mosml) for my first programming course. Now the same university is teaching the same course in F#.

Of course a lot of the data science/machine learning is being done in Python, but that is likely due much of the frameworks/tooling around is Python in general in that world.

Re: John Carmack on Functional Programming in C++ (2018)

#177

Earlier quoted context omitted.

That Typescript ADT example is heavily outdated (or explicitly obtuse) class Bar { tag="bar" as const; constructor(public value:string){} } class Baz { tag="baz" as const; constructor(public value:boolean){} } type Foo = Bar|Baz;

That is better, but it's still nowhere near `type Foo = Bar String | Baz Boolean`. It's also nowhere as clean to pattern match on.

That's true if pattern matching specifically is what you want, in practice we don't constructs ADT's for the sake of it and rolls with interfaces that also meshes well with data imported from other sources (ie JSON).

Also while pattern matching isn't an explicit thing in TS you get most benefits from compiler checked accesses that can recognize type-tests in your code and derive types and do property access checks.

Re: John Carmack on Functional Programming in C++ (2018)

#178

Earlier quoted context omitted.

>In the same interview he also mentions using python a lot lately and making the point that for the vast majority of code, performance really doesn't matter and productivity is more important. Until it does matter. Then it *really* matters at which point you're normally looking at a bottom up rewrite and likely retooling and rehiring for new skills. Ive been bitten by "oh it's just a prototype" a few too many times n…

One could always create a native python module in Rust/other and call it from Python. It might not work for videogames, for instance, but ML seems to do fine with this approach, and they require a lot of performance from the GPU.

So spend the time doing the hard bit, then introduce some complexity and a software turducken for the sake of calling it from a "simple" language. At which point I'd then ask the question are we really so scared of someone accusing us of overengineering that we're creating more complicated solutions to appear simple and pretending the complexity doesn't exist?

Re: John Carmack on Functional Programming in C++ (2018)

#179

Earlier quoted context omitted.

One could always create a native python module in Rust/other and call it from Python. It might not work for videogames, for instance, but ML seems to do fine with this approach, and they require a lot of performance from the GPU.

So spend the time doing the hard bit, then introduce some complexity and a software turducken for the sake of calling it from a "simple" language. At which point I'd then ask the question are we really so scared of someone accusing us of overengineering that we're creating more complicated solutions to appear simple and pretending the complexity doesn't exist?

This is basically how Python is useful, calling native modules.

It might not be aesthetically pleasant but it works.

If we think about it, most of the time you do not need to do that because some library author has already done it.

If one needs to write the native code it is not overengineering. It is only overengineering if it was not needed in the first place.

Post reply on HN