To clarify: ML started out as a scripting language for Robin Milner's proof assistant, LCF. The formal system, or "logic," is implemented in a minimal, trusted kernel, and the proof data structure is protected as an abstract data type that can only be constructed through the trusted kernel. On top of the kernel, tactic scripts may be defined to manipulate proof objects and facilitate proof search/automation.
Then, ML grew into a general-purpose programming language (both OCaml and Standard ML are dialects).
One language that uses the tuple argument convention described in the article is Standard ML. In Standard ML, like OCaml and Haskell, all functions take exactly one argument. However, while OCaml and Haskell prefer to curry the arguments, Standard ML does not.
There is one situation, however, where Standard ML prefers currying: higher-order functions. To take one example, the type signature of `map` (for mapping over lists) is `val map : ('a -> 'b) -> 'a list -> 'b list`. Because the signature is given in this way, one can "stage" the higher-order function argument and represent the function "increment all elements in the list" as `map (fn n => n + 1)`.
That being said, because of the value restriction [0], currying is less powerful because variables defined using partial application cannot be used polymorphically.
One of the unwritten takeaways of this post is that async/await is a leaky abstraction. It's supposed to allow you to write non-blocking I/O as if it were blocking I/O, and make asynchronous code resemble synchronous code. However, the cost model is different because async/await compiles down to a state machine instead of a simple call and return. The programmer needs to understand this implementation detail instead of pretending that async functions work the same way as sync functions. According to Joel Sposky, all non-trivial abstractions are leaky, and async/await is no different. [0]
The article mixes together two distinct points in a rather muddled way. The first is a standard "premature optimization is the root of all evil" message, reminding us to profile the code before optimizing. The second is a reminder that async functions compile down to a state machine, so the optimization reasoning for sync functions don't apply.
One non-trivial problem with async in Rust is that it leads to code that allocates on one CPU and free memory on another. That kills a lot of optimizations that system allocators try to do with CPU local caching and harms performance badly especially on fat servers with a lot of CPUs. When one hits this problem, there is no easy solution.
Ideally using an allocator per request would solve this issue, but Rust has no real support for it.
A workaround that works is to stop using async and just use a native thread per request. But then most crates and frameworks these days use async. So indeed async abstraction us very leaky regarding the cost.
I agree that from the perspective of the implementation of async code, it is in many ways an application doing its own threading and context switching. However, your Parent comment is written from the perspective of the dev writing and reasoning about the code. In that case, from the devs perspective, async is there to make concurrent code ‘look like’ (since it certainly is not actually) sequential code.
I think this type of confusion (or more likely people talking past one another in most cases) is a fairly common problem in discussing programming languages and specific implementations of concepts in a language. In this case the perceived purpose of an abstraction based on a particular “view point”, leads to awkward discussions about those abstractions, their usefulness, and their semantics. I don’t know if there is way to fix these sorts of things (even when someone is just reading a comment thread), but maybe pointing it out can serve to highlight when it happens.
Yeah the author makes a really poor example with the async case here.
Async in rust is done via cooperative scheduling. If you call await you enter a potential suspension point. You're willingly telling the scheduler you're done running and giving another task a chance to run. Compound that with something like tokio's work stealing and now you'll possibly have your task migrated to run on a different thread.
If this is in hot path making another call to await is probably the worst thing you can do lol.
The author demonstrates later with a dead simple inlining example that the asm is equivalent. Wonder why he didn't try that with await ;)
Note that the division-by-zero example used in this article is not the best example to demonstrate "Parse, Don't Validate," because it relies on encapsulation. The principle of "Parse, Don't Validate" is best embodied by functions that transform untrusted data into some data type which is correct by construction.
Alexis King, the author of the original "Parse, Don't Validate" article, also published a follow-up, "Names are not type safety" [0] clarifying that the "newtype" pattern (such as hiding a nonzero integer in a wrapper type) provide weaker guarantees than correctness by construction. Her original "Parse, Don't Validate" article also includes the following caveat:
> Use abstract datatypes to make validators “look like” parsers. Sometimes, making an illegal state truly unrepresentable is just plain impractical given the tools Haskell provides, such as ensuring an integer is in a particular range. In that case, use an abstract newtype with a smart constructor to “fake” a parser from a validator.
So, an abstract data type that protects its inner data is really a "validator" that tries to resemble a "parser" in cases where the type system itself cannot encode the invariant.
The article's second example, the non-empty vec, is a better example, because it encodes within the type system the invariant that one element must exist. The crux of Alexis King's article is that programs should be structured so that functions return data types designed to be correct by construction, akin to a parser transforming less-structured data into more-structured data.
Even the newtype-based "parse, don't validate" is tremendously useful in practice, though. The big thing is that if you have a bare string, you don't know "where it's been". It doesn't carry with it information whether it's already been validated. Even if a newtype can't provide you full correctness by construction, it's vastly easier to be convinced of the validity of an encapsulated value compared to a naked one.
For full-on parse-don't-validate, you essentially need a dependent type system. As a more light-weight partial solution, Rust has been prototyping pattern types, which are types constrained by patterns. For instance a range-restricted integer type could be simply spelled `i8 is 0..100`, or a nonempty slice as `[T] is [_, ..]`. Such a feature would certainly make correctness-by-construction easier in many cases.
The non-empty list implemented as a (T, Vec<T>) is, btw, a nice example of the clash between practicality and theoretical purity. It can't offer you a slice (consecutive view) of its elements without storing the first element twice (which requires immutability and that T: Clone, unlike normal Vec<T>), which makes it fairly useless as a vector. It's okay if you consider it just an abstract list with a more restricted interface.
It's also useful to wrap/tag IDs in structured types. That makes it easier to avoid errors when there are multiple type parameters such as in the Microsoft graph API.
Idris is slightly more mainstream I would say, but not wildy so. If you like the Haskell interop then I'd recommend staying with Agda.
Scala 3 is much more mainstream and has path dependent types. I've only used Scala 2, and there the boilerplate for dependent types was frustrating imo, but I've heard its better in 3.
Ah yes Idris rings a bell. I’ll try that one again.
Scala 3 indeed is more mainstream but it seems also on the way out. At least here in corporate world it is replaced by Kotlin and Java 21+ for a large part.
You can have range-constrained numeric types and collections in Haskell via Liquid Haskell, which has almost seamless integration with the compiler starting from GHC-9.12+
You can also search for "make invalid states impossible/unrepresentable" [0] to find more info on related practices. See "domain modeling made functional" [0] as a nice example
The phrasing that I hear more often is "make illegal states unrepresentable"; both the submitted article and Alexis King's original article use this phrase. At least according to https://fsharpforfunandprofit.com/posts/designing-with-types..., it originates from Yaron Minsky (a programmer at Jane Street who is prominent in the OCaml community).
EDIT: Parent comment was edited to amend the "impossible/unrepresentable" wording
Yes division is a poor example. It's a poor separation of concerns to try to wrap at this level without usage context. To see the point try to wrap overflows on arithmetic functions.
> To see the point try to wrap overflows on arithmetic functions.
The invariant is less obvious, but you could still do this if you really wanted. The observation is that addition of two fixed-size nonnegative integers cannot overflow unless at least one is greater than half the range. So your `non_overflowing_addition` function would need take two inputs of type `NonNegativeLessThanHalfMaxValue`, where the constructor for the latter type enforces the invariant. Multiplication is similar, but with the square root of the range (and I suppose `NonNegativeLessThanSqrtMaxValue` could be a subtype of `NonNegativeLessThanHalfMaxValue` if you want to be fancy).
Note that addition also won't overflow if one addend is greater than half the range, but the other addend is still small enough (e.g. for the range -128 to 127, adding 65 + 12 will not overflow, even though 65 is greater than half of 127).
Your intention of having the restricted domain "NonNegativeLessThanHalfMaxValue" is probably so that both addends have the same domain. If you go down that route, perhaps you'll also want the closure property, meaning that the range should also belong to the same set. However, then you have to deal with the overflow problem all over again...
The real point is that when adding two N-bit integers, the range must be N+1 bits, because the "carry bit" is also part of the output. I think this is a scenario where "Parse, Don't Validate" can't easily help, because the validity of the addition is intrinsically a function of both inputs together.
I agree, 'correct by construction' is the ultimate goal here. Using types like NonZeroU32 is a great simple example, but the real power comes when you design your entire domain logic so that the compiler acts as your gatekeeper. It shifts the mental load from run-time debugging to design-time thinking.
> With Prop, I think what you need to dig into is ‘non-computational’ not ‘non-computable’.
Here's another way to explain this:
As you state, Prop has to do with proof-irrelevance. When doing constructive mathematics, proofs are programs (meaning they carry computational content), but sometimes it's useful to treat any two proofs of the same proposition as equal. As a consequence, proofs cannot be inspected or run as programs, and you get back the Law of Excluded Middle from classical mathematics.
Decidable has to do with decidability. This means that given some proposition P, there is an algorithm that can either produce a proof of P, or a proof of ~P. This is usually useful when P is a predicate, so that at each x, P(x) either has a proof or a disproof.
In classical mathematics, the Law of Excluded Middle holds for all propositions. In constructive mathematics, the Law of Excluded Middle only holds for decidable propositions. If P is decidable, it is safe to constructively assume P or ~P because an algorithm can produce the answer.
This is my point of view as someone who learned WebGPU as a precursor to learning Vulkan, and who is definitely not a graphics programming expert:
My personal experience with WebGPU wasn't the best. One of my dislikes was pipelines, which is something that other people also discuss in this comment thread. Pipeline state objects are awkward to use without an extension like dynamic rendering. You get a combinatorial explosion of pipelines and usually end up storing them in a hash map.
In my opinion, pipelines state objects are a leaky abstraction that exposes the way that GPUs work: namely that some state changes may require some GPUs to recompile the shader, so all of the state should be bundled together. In my opinion, an API for the web should be concerned with abstractions from the point of view of the programmer designing the application: which state logically acts as a single unit, and which state may change frequently?
It seems that many modern APIs have gone with the pipeline abstraction; for example, SDL_GPU also has pipelines. I'm still not sure what the "best practices" are supposed to be for modern graphics programming regarding how to structure your program around pipelines.
I also wish that WebGPU had push constants, so that I do not have to use a bind group for certain data such as transformation matrices.
Because WebGPU is design-by-committee and must support the lowest common denominator hardware, I'm worried whether it will evolve too slowly to reflect whatever the best practices are in "modern" Vulkan. I hope that WebGPU could be a cross-platform API similar to Vulkan, but less verbose. However, it seems to me that by using WebGPU instead of Vulkan, you currently lose out on a lot of features. Since I'm still a beginner, I could have misconceptions that I hope other people will correct.
Typed functional programming has the perspective that types are like propositions and their values are proofs of that proposition. For example, the product type A * B encodes logical conjunction, and having a pair with its first element of type A and its second element of type B "proves" the type signature A * B. Similarly, the NonEmpty type encodes the property that at least one element exists. This way, the program is "correct by construction."
This types-are-propositions persoective is called the Curry-Howard correspondence, and it relates to constructive mathematics (wherein all proofs must provide an algorithm for finding a "witness" object satisfying the desired property).
A great way to understand monads is as a "design pattern," because they pop up extremely often in practical programming. Consider functions with a type signature that looks like `A -> T<B>`, such as `A -> Promise<B>` or `A -> Optional<B>`.
If you have some function fetchResponse that returns a Promise<Response>, and a function processJSON that takes a Response as an argument, you cannot compose them the usual way, as `processJSON(fetchResponse(x))`. Instead, you need to do `fetchReponse(x).then(processJSON)`, and the entire expression has to return another Promise. Ditto for functions that return an Optional.
All data types that implement this design pattern have the structure of a monad. A monad consists of a generic type that is "covariant" in its type parameter (such as Promise or Optional), a way to embed a singular value into the data type, and a "then" method to compose the data type with a callback. Lists also implement the monad design pattern, and the "then" method for lists is flatmap. A monad basically lets you compose functions with a type signature that looks like `A -> T<B>`.
Furthermore, each of these data types (Promises, Optionals, Lists) can be viewed as the output of some computation. Promises are produced whenever a function performs asynchronous IO, Optionals are produced when computations may return some "null" value, and Lists are returned if an algorithm may produce multiple solutions.
Just like Promises have async/await syntactic sugar, similar syntactic sugar can be devised for other "monadic" types. For Optionals, the equivalent of async/await is null propagation (some languages have a `?` operator for this). For Lists, the equivalent of async/await is list comprehension, which "picks" each element from the list to build up a new list. Async/await, null propagation, and list comprehensions all have the same underlying structure, called a "monad."
A "free monad" is a monad that does not implement any specific computation, but instead builds up an abstract syntax tree that needs to be interpreted. Free monads are useful because other monad instances can be implemented in terms of the free monad.
This explanation doesn't contain any practical examples either. I mean, I do know that Promises are a monad, but that's not obviously helpful. You can write plenty of async code using Promises without knowing that, and it will probably be clearer to the reader. Similarly, options are a monad, but that's unhelpful for writing code that deals with optional values.
Why is most writing about functional programming like this?
The practical example is being able to use the same names and utility functions and such on all of the different monads. That's kind of it.
Other than that it's just nice for communication in the right groups, it's shorthand for a whole bunch of properties that you then don't have to explain.
It also only really works super well in languages where the type system is expressive enough to allow that (or just permissive enough not to stop you I guess), so that mostly comes up in fun "functional" languages where they spent a bunch of time on the type system.
You'll probably understand a bit better if you take some time and learn/use Haskell a bit (if you don't already understand, it kind of sounds like you do tbh). It's a fun and educational language in a bunch of ways IMO. It depends on the kind of person/programmer you are if you'll really care though.
Because FP is useless so there aren't any practical examples. ...but all kidding aside, I kinda feel like an astronomer talking to an astrologer when it comes to this stuff. Like I'm scanning the night sky with my telescope while he's talking about Mars being 'in the house of Jupiter' or whatever. It's the old Abelson quote about computer science all over again.
It's serendipitous that I'm seeing this blog post on the front page today, because I'm currently writing an article discussing the free monad.
In addition to the free monad presented in this post, there is a variant, called the "freer" monad, based on the "bind" operation instead of the "join" operation:
data Freer f a where
Pure :: a -> Freer f a
Bind :: f a -> (a -> Freer f b) -> Freer f b
When thinking of monads as giving the semantics of some computational strategy, it's easier to define them in terms of "bind" instead of "join." This way of defining monads is sometimes called a "Kleisli triple" because it is better suggestive of "Kleisli arrows," or functions of the signature `a -> m b`. The "bind" operation defines how to compose a monadic computation with its continuation, and from this perspective, the "freer" monad resembles an abstract syntax tree.
Originally, Eugenio Moggi proposed monads as a technique for specifying the denotational semantics of programming languages. All Java programs "really" happen in the IO + Either monads, because all Java programs may perform IO and throw exceptions. To my understanding, free monads are the monad that OCaml 5 runs in, because they give the semantics for effect handlers (or resumable exceptions).
> All Java programs "really" happen in the IO + Either monads
People say things like this all the time, and I think it's a vacuous assertion. While there is probably some very narrow view where returning early with an error, throwing an exception, and binding in Either are the same thing, such a view ignores a lot of important context (e.g. all of imperative programming). This is why you have to qualify it as "IO + Either", but that doesn't say anything at all because everything is possible in IO.
Then, ML grew into a general-purpose programming language (both OCaml and Standard ML are dialects).