OCaml Programming: Correct and Efficient and Beautiful
cs3110.github.io
cs3110.github.io
This was largely due to automatic currying in OCaml — if I have a function call "some_function arg1 arg2" and "some_function" adds a third argument, that call becomes a function that requires a single argument, arg3, but the typechecker message that tells you all of this is well-nigh unintelligible.
Switching to Rust was a blessed relief, not least because Rust has much better developer tooling and documentation (but also no automatic currying).
It made me think that OCaml is efficient and beautiful if you're the only person touching your specific codebase (which I think is true in the vast majority of cases) or if many of your colleagues are deep OCaml officionados with PhDs, but it's not a good collaborative language for the rest of us.
The example that you are describing should emit an error message of the form
This expression has type type_of_arg_3 -> return_type
but an expression of type return_type was expected
IME, it’s definitely true that OCaml doesn’t have the didactic error messages that many have come to like in Rust et al. They said, imo they generally give the information needed solve problems and I like their concision. It takes a bit of time to learn to read them however.
Yeah, and I think you could say the same of Rust when it comes to the borrow checker's messages.
But in Rust's case the problem it's trying to describe is itself pretty complex. The complexity of OCaml's error messages are really not justified by the problem they're warning you about, which is itself very straight-forward.
Where do you think rust got (more than) half of its type inspiration from?
Either way no one has to use any language. Personally OCaml is not my cup of tea--Haskell is. But it is a great tool and it's solving hard problems.
Given that history, it’s instructive to note the sorts of things (like auto-currying) that Rust did not inherit.
If a functional language is presented today that does not automatically curry calls, I have no interest.
Just because the tool does not work for you does not mean there's a defect in the design.
The sense I have got from my experience is that OCaml is a great language for people who are slightly less error-prone than I am.
My style of coding is to write a lot of slightly dodgy code in one breath, then use the typechecker to tell me all the things I got wrong. Even in a language I’m very familiar in there’s still a lot of trial and error.
OCaml currently seems great for people who are better at getting it mostly-right first time — I’ve seen a lot of OCaml code written by people with PhDs and backgrounds in type theory. Most other languages don’t have that sort of academic pedigree.
That's exactly the style OCaml excels at.
> OCaml currently seems great for people who are better at getting it mostly-right first time
That's because they got it wrong a lot at first, then learned how to get it right. You've heard of people talking about how they internalized the Rust borrow checker's rules after some time, right? Well, internalizing a typechecker's inference rules works very similarly (faster if you read OP).
> I’ve seen a lot of OCaml code written by people with PhDs and backgrounds in type theory.
That's unfortunate, it's a nearly perfect language for industrial work. Tiny example of how easy it is to hack together useful tools with it: https://dev.to/yawaramin/practical-ocaml-314j#proof-of-conce...
But automatic I don't see the point, it's like automatic conversion in C: not the good default IMHO.
I think, unfortunately, I've observed a pattern in much functional programming (F# being a blessed exception) that relatively excellent computer language designers suffer from the utter ineptitude of the human language competency of the tool authors. These days, I am far more interested in an elegant tool chain and support infrastructure than an elegant language.
Error: operator and operand do not agree [tycon mismatch] This expression was expected to have type
'int'
but here has type
'string -> int'But I got the error message
Error: This expression has type
((locl_ty * Tast.pos * ('ex, 'fb, 'en) Aast.expr_) list ->
Result_set.t)
list
but an expression was expected of type Result_set.t list
Type
(locl_ty * Tast.pos * ('ex, 'fb, 'en) Aast.expr_) list ->
Result_set.t
is not compatible with type Result_set.t
I built a reasonably popular typechecker for PHP, so I have some experience with the DX for these sorts of programs. I don't think it's good for a couple of ASCII characters and line breaks to be the difference between an acceptable and an unacceptable type annotation. It requires, as you say, for the OCaml type system to be burned into people's minds for them to immediately spot the issue.
In a similar context Rust will just say "function expected 5 arguments, you gave it 4" which has a very obvious remediation.
1. Error: This expression has type ('x -> Result_set.t) list but an expression was expected of type Result_set.t list
2. where 'x = (locl_ty * Tast.pos * ('ex, 'fb, 'en) Aast.expr_) list
The solution suggested by the parent of your post sounds desirable also, but perhaps the currying semantics of Ocaml makes that difficult or poorly-defined?
myfun :: Int -> Char -> Bool
myfun a b = undefined
myfun 1 'c' 3
• Couldn't match expected type ‘t0 -> t’ with actual type ‘Bool’
• The function ‘myfun’ is applied to three value arguments,
but its type ‘p10 -> Char -> Bool’ has only two
putStrLn (myfun 1)
• No instance for (Show (p20 -> Bool))
arising from a use of ‘print’
(maybe you haven't applied a function to enough arguments?)
applied to three value arguments ... but its type ... has only two
maybe you haven't applied a function to enough arguments? > myfun 1 'c' 3
-- TOO MANY ARGS ---------------------------------------------------------- REPL
The `myfun` function expects 2 arguments, but it got 3 instead.
5| myfun 1 'c' 3
^^^^^
Are there any missing commas? Or missing parentheses?
> not (myfun 1)
-- TYPE MISMATCH ---------------------------------------------------------- REPL
The 1st argument to `not` is not what I expect:
5| not (myfun 1)
^^^^^^^
This `myfun` call produces:
a -> Bool
But `not` needs the 1st argument to be:
Bool
(Edit: Formatting. Note that in the console output the arrows actually line up with the source of the errors)
You're right though that OCaml isn't the kind of language you can pick up in an afternoon.
I don't know OCaml really, but I would read that intuitively as a list of (functions that return Result_set.t), which is not compatible with a list of Result_set.t.
Should that be “Result set type was expected”, not “list”?
means a list whose items are of type Result_set.t.
Also I think the notation X.t is idiomatic for a type defined by module X.
I don't know if you see a real readability issue or not, but I do think it's easy to jump to "hard to read" when that's only true in a certain parochial sense: it's not what we're used to.
Dropping an example in TryOcaml[0]:
let f : int -> int = fun _ -> 1 ;;
val f : int -> int = <fun>
let ex : int list = [f] ;;
Line 1, characters 21-22:
Error: This expression has type int -> int but an expression was expected of type
int
I agree the first 6 months of this is mind-numbingly frustrating.
That's one of the top few specialties tasks for humans. After you learn it, you immediately know its meaning, it becomes easy with no thinking at all required.
Anyway, the plain English example from Elm on the sibling comment is much better, because it's already easy to understand before you learn to recognize it.
Is a lie fabricated to deflect criticism of the person who coined the term via abusive ad hominem of the critic.
Surprisingly, that tends to predict the quality of arguments invoking Stockholm syndrome pretty well, too.
I don't think I would want to use Rust unless I really needed a language with near optimal performance. OCaml on the other hand seems suitable for programs where correctness is important but performance isn't the driving concern. At least I'm considering using it for that type of application, though I'm not yet a serious OCaml programmer (still working my way through this course actually).
In addition I greatly prefer having a garbage collector around.
Elm is not really an alternative to OCaml (or Rust) but it shows how nice compiler error messages can be.
The problem is not OCaml here.
> You can use -annot or -bin-annot when compiling and the Tuareg function caml-types-show-type in Emacs will be your best friend.
Just open OCaml program in some editor with LSP(Vim, NeoVim, VS Code, Emacs) and it will instantly show you the error.
Automatic currying is syntactic sugar that can make these two easier and clearer as it gets rid of a bunch of named arguments and lambdas. For example, I can write:
foo a b c = a * b + c
foo2 = foo 10 20
composed = foo2 >> bar >> baz
foo (a, b, c) = a * b + c
foo2 (z) = foo (10, 20, z)
composed (a) = (\b -> foo2 (b)) ((\c -> bar (c)) (baz (a)))It implies that `(add 3)` is being magically converted into `(\x -> (add 3 x))` by some fancy front-end feature.
But no, `add` is just a function that returns a function.
This pattern is core to the entire paradigm of functional programming, all the way down to the lambda calculus.
All functional programming languages are essentially just fancy syntax around lambda calculus. They have different implementation strategies (strict vs lazy), different type systems, and they have been extended with different primitives (floats, operations on floats, etc).
But at their core, they are all just lambda calculus.
In the lambda calculus, there is ONLY functions, and all functions take one argument. There are no tuples. So, multiple arguments are implemented with the pattern in question. For example:
mul = (λx. λy. λz. x(yz))
---
One benefit is that functions are more reusable. Functions with more arguments can be partially applied and used where applicable.
For instance, if you wanted to increment the values in a list you might do something like this in python:
map(lambda x: x + 1, [1,2,3])
map((+ 1), [1,2,3])
Additionally, you can think of currying as a form of dependency injection.
For example, if you wanted to inject a database client and a logger before running a query you might do something like this:
def queryer(db, logger):
def _q(query):
logger.info("before query")
results = db.fetch(query)
logger.info("after query")
return results
return _q
rows = queryer(db, logger)(query)
queryer db logger query =
logger.info("before query")
results = db.fetch(query)
logger.info("after query")
results
rows = queryer db logger query
rows = (queryer db) logger query
rows = ((queryer db) logger) query
---
I hope this makes sense and I wish I could preview my comment to see if it was formatted reasonably!
If you haven't tried haskell, you probably should. Its type system is much cleaner (and more powerful, if you want) than ocaml's, and many details of Rust are derived from Haskell.
I'm very conscious of the existence of pareto tradeoffs; I am asserting that, in this case, there is essentially no tradeoff to be made. Haskell is equal or better (sometimes significantly so) in almost every relevant domain. For domains in which ocaml is a better choice, it is not the globally best choice (i.e. both ocaml and haskell are bad in those domains).
I think this assertion is false, but it would take a lot of careful evaluation to prove it one way or the other. The most salient counterexample that comes to mind is modularity and namespacing.
Of course it's possible I'm wrong, and Haskell is objectively superior in every regard. But the OCaml language and ecosystem has [a decades long track record of stable and evident success stories](https://ocaml.org/industrial-users) and I find it well suited for the kinds of problems I like to tackle. I also like the prevailing vibe in the (still) small community.
This exchange reminds of a difference I've observed in the cultural tendencies in the OCaml and Haskell ecosystems: in my experience, OCamlers tend to not be very invested in arguing for the supremacy of OCaml.
This is what I was doing for a number of years.
> The most salient counterexample that comes to mind is modularity and namespacing.
Polymorphic variants and ocaml namespacing are nice, granted. These are the two ocaml features I've ever missed while using haskell. Minor details overall though. Namespacing is not as useful with typeclasses and PVs have typing problems.
> in my experience, OCamlers tend to not be very invested in arguing for the supremacy of OCaml
Yeah, this is mostly because it's not as much of a marginal improvement, so it doesn't have as many people interested in shilling it.
In chp 7 on understanding IO, there's also another great section that explains how IO evaluation is often confused. I share an example from the book that reads, writes, and prints files.
Memory intensive func because it attempts to read _all_ files at once because the execution of reading and writing actually only happens when the print fn is called (putStrLn files). makeAndReadFile is actually doing both reading and writing - a normal task in all other languages.
slow =
let files = mapM makeAndReadFile [1..500] :: IO [ String ]
in files >>= (putStrLn . show)
Efficent version. Here we force reads and writes to actually occur per file instead of waiting til the print. Seems like a pretty easy step to misunderstand.
safe :: IO () safe =
foldl ( \ io id -> io >> makeAndShow id ) (return ()) [1..500]* it has never been an issue for me
* I don't think the performance implications are nearly as hard to understand as often implied
* in the extreme you can just enable the STRICT language pragma in your project and forget about it :)
Really, lazy IO is a much larger source of problems, and even there, after a week or two writing IO people just learn to write code that doesn't break due to it.
I know few cases where OCaml require less annotations than Haskell, I would expect the reverse to be true.
And maps and sets are not the main use case for polymorphism in OCaml. Even taking in account that it sounds like you are talking about functors, maps and sets are still not the only instance of functors in OCaml.
A) I am fairly confident this is not actually true in a technical sense, although it's been several years since I've thought about it
B) In any case, in the (many) instances where you (by rule or convention) need to put a type signature on your function (e.g. because it's a top-level function, one that you export, etc.), it is a pain in the ass to make it polymorphic in ocaml compared to in haskell.
> Even taking in account that it sounds like you are talking about functors
No, I'm not, although ocaml people tend to think exclusively in "functors" (badly named, in my opinion - conflicts with the more common category-theoretic definition) because the experience of using actually parametric functions is so bad that they almost never do it.
OCaml typing is principal in all situation where type inference is decidable. The syntax for annotation for polymorphic functions is isomorphic between OCaml and Haskell.
If I take a random module in the standard library, let's say Array, 95% of the functions in this module are parametric polymorphic. I am thus genuinely puzzled by your statement that "OCaml programmers almost never write polymorphic functions".
> The syntax for annotation for polymorphic functions is isomorphic between OCaml and Haskell.
Sorry, but total bullshit. I had to use these pieces of shit all the time. https://v2.ocaml.org/manual/locallyabstract.html
> If I take a random module in the standard library, let's say Array
As I specifically called out, all the core data structures are polymorphic. (Let's not talk about the float array hack; is that still around?)
It's so annoying that pretty much every other library is monomorphic or functorized.
> I am thus genuinely puzzled by your statement that "OCaml programmers almost never write polymorphic functions".
Not sure what to tell you man. I spent 4 years reading & writing ocaml and 95% of the code that would have been polymorphic in haskell (because it would be easy/free) was either monomorphic or (multiple layers of) functors. Many/most of the devs I worked with (great devs with years of OCaml experience) didn't even know what LATs were, let alone used them, which means they were almost certainly not writing polymorphic code which "did anything" with the type. The only polymorphic code that you can write in ocaml without such things are functorial (in the categorical sense, not the ocaml sense). Arrays, map values, that's about it.
Ok, locally abstract types are bit weird and historical quirk due to the pre-existing use of type variables as unification type variables. But first, they only matter with GADTs and local modules (a notion that doesn't exist in Haskell). And the good syntax for polymorphic function with GADTs is `type a. a monoid -> a` which requires just one explicit quantification compared to the Haskell variant. So no, Haskell and OCaml type annotations are isomorphic.
> As I specifically called out, all the core data structures are polymorphic.
I took a totally random module from the standard library! Let me another random module after rolling a dice, Atomic. Here only 66% of the functions are polymorphics. Or do you want me to go to another library? Ok, let's go for container, and let's select another random module CCPair: 100% of the functions are polymorphic. Honestly, I struggle to understand how it is possible to conclude that every OCaml library is monomorphic.
What do you mean by LATs? The Haskell wiki doesn't seem to know that term.
> The only polymorphic code that you can write in ocaml without such things are functorial
I am sorry to ask but are you confusing bounded polymorphism with parametric polymorphism?
Local modules (assuming this means e.g. a module passed in as a function argument, constrained to have one of its types match the type of another argument) are how you write non-trivial polymorphic code.
> Atomic ... CCPair
More functors (in haskell terminology) - code that doesn't do anything interesting with the type parameter.
> What do you mean by LAT
Locally abstract type
> I am sorry to ask but are you confusing bounded polymorphism with parametric polymorphism?
Bounded polymorphism is an application of parametric polymorphism. Not sure what you are asking here. Possibly this will clarify my line of thought: I consider parametrically polymorphic code without any bounds to be "uninteresting"/"trivial", because either the code must treat the polymorphic type completely opaquely (leading to trivial functorial [in the haskell sense] operations like implementing fmap), or requiring you to explicitly pass in all supported operations on the instantiated type (basically requiring you to implement bounding by hand).
I think this may be a blub paradox thing, where the set of useful applications of PP is much more restricted in ocaml, to the point where ocamlers do not even consider what they are missing. A haskell or rust programmer would likely run into these semantic blocks quickly upon trying ocaml.
I remember one annoyance I had with ocaml was the effective inability to use point-free style. I can't remember what limitation was behind this; do you know off the top of your head?
Edit: it's the "value restriction", more annoying bullshit I forgot about! Huge limitation for polymorphic ocaml code.
And in fact OCaml does have BP, as was explained earlier, just with a heavier syntax.
> effective inability to use point-free style
OK but point-free style is not an end in itself, it's just a means to an end (clean code), and there's certainly no universal agreement that it's the best means...explicit style is almost always easier to understand for a wide assortment of people and doesn't require mental backflips trying to figure out the weird heiroglyphics of '(.) (.) (.)' etc. etc.
> Huge limitation for polymorphic ocaml code.
Yeah I can see how writing e.g.
let f x = g [] x
let f = g []
Ok, I'm glad we agree on that.
> I can see how writing
Eta reduction is one example, but a great deal of code is cleanly expressed as e.g.
vecLen = sum . map (^2)
let vec_len vec = vec |> map (fun x -> x ** 2.) |> sum
let square x = x ** 2.
let vec_len vec = vec |> map square |> sum
OCaml was always portrayed as the engineer's alternative for real applications.
I spent some time brushing up on OCaml a few years ago using Exercism.io.
While OCaml is a personal "top tier" language, I'd always prefer Haskell, Rust or Scala.
Type classes / traits just seem to beat a higher-order module system for me.
Still, I'd pick either over Scala. Superior compilation times, cleaner syntax, less complex. Haskell also just feels excessively clever.
I had hoped Rust would be "OCaml but for systems programming" and it sort of is, -- but the borrow checker and memory safety features, as neat as they are, add a lot of mental overhead.
Unfortunately to be a real-world SML user these days is a very isolating proposition, because although there are some really nice implementations (MLton, PolyML), to a first approximation there are zero libraries.
- OCaml vs Haskell: eager vs lazy (=> memory consumption is more predictable)
- OCaml vs Rust: OCaml has a GC (=> comfort) OCaml has tco (could not resist this ;) )
- OCaml vs Clojure: vastly superior typing system. (=> less bugs)
- OCaml vs Kotlin: no JVM needed.
- OCaml vs C++: more safety. once it compiles it will not segv.
- OCaml vs Go: vastly superior typing system. (=> less bugs)
- OCaml vs Python: vastly superior type system, way better performance.
Lots of mainstream languages simply fail this test and make it feel like intellectual poverty or that there's extreme, turgid, boilerplate required for a weak imitation of the features (see the idiomatic class-hierarchy encoding of ADTs in large projects - such as LLVM - in C++, for example).
It's absolutely no surprise that more mainstream languages are picking up a match-like construct and lighter encodings of discriminated sums. So, it really comes to what else you wish to be burdened with when compiling an OCaml-like mental model to X in your head: Tagged unions a-la C? Class hierarchies for ADTs in C++? The travesties of std::variant? Monad transformers in Haskell? Lazy evaluation? No static typing at all? Caring about memory management and ownership? Box and Arc-ing recursive components of ADTs? Writing your own arena allocator? Compiling to the JVM? Spotty TCO support?
OCaml is just a nice, fairly simple (at its core, at least), language that captures the essence of the ML family, compiles to native (and bytecode and, transitively, JavaScript), has great tooling (opam, dune, ocamllex, memhir, etc.), great libraries (official LLVM bindings, for example), and a great community. Lots of OCamlers are well aware of other potential languages that somewhat suit their style of programming, they just don't want to be burdened by the other stuff.
I have no horse in this race, but claiming it to be "vastly superior" and implying "less bugs" makes it sound like this is a logical consequence, when you're actually staying on one side of an endless debate that to me doesn't have clear winners. For instance, from the little I've learned about Clojure, they claim the lack of a "vastly superior type system" is a feature, not a bug, and it's a result of a fundamental difference in some beliefs about how to write correct software.
From this I wonder how misrepresentative your other comparisons are as well. But don't get me wrong, OCaml is probably my "favorite language I've never actually used" (I've never "actually used" Clojure in "real projects" either).
- I'm very specific about when I use None
- I'm a big fan of named function arguments
- I like to think my naming of things is pretty good, as are my conventions for parameters
- I try to handle all possible cases (what I mean here is I do and if I don't I made a mistake)
I use tests very sparingly in personal projects, but yet I haven't really felt their absence. If I ever write a piece of particularly hairy code (metaprogramming comes to mind... lord) I'll write a quick script testing some cases and then delete it.
Anyway, all that is to say I think part of dynamic programming is you build an immune system for this stuff.
I usually avoid bugs in python code by rewriting in bash (at 1-10% the size of the original python, since bash's error handling can be set to "always do the right thing" with "set euxo pipefail")
If bash is a bad fit for the rewrite, go usually works. I don't work on linear algebra software much these days. Python seems to be a good option for that.
I think Python gets bailed out a lot because those things turn out to be a lot of programming these days. The people who have a beef w/ Python are those who've worked with it on large, old codebases. This is a tough job for any language though like, raise your hand if you've ever worked on a large, old codebase in C++ or Java that you liked.
Usually when people push microservices I'm quick with Conway's law, saying "this is a tech solution to an organizational problem that won't actually make a difference", and I think I'm right about that. But I think I've been ignoring that a really nice thing about microservices for engineers is you can keep using languages like Python on small codebases, and at least mentally and emotionally avoid the feeling of working on a huge monolith. That counts for something.
You can if they are motivated to learn. Unless you are offering Jane Street levels of compensation; and in return, the candidate is willing to believe, or pretend to believe that company's shtick about OCaml being so categorically superior as a general-purpose development language so as to leave all the others in the dust -- most likely they won't be.
OK, I'll grant that if you have that "magic skill" then you can in fact recruit developers for niche languages.
Most companies don't, as we know, and frankly it's amazing to me how incoherent their communications are throughout their so-called hiring process.
https://www.benjamistan.tech/2022/06/26/wasting-time-in-tech...
You pick one regardless of language. Not sure what's your point here.
I would like to confirm that fact, by comparing productive output..
'Producing code' to measure 'superiority' is about as useful a metric as counting lines of code to measure productivity.
On the other side OCaml, as a pure functional programming language with immutable value by default doesn't scale well to large, complex application. Just the paradigm is no longer tenable and you need to switch at least partially to imperative programming with mutable variable. For example this is what it does the implementation of the OCaml itself.
To develop further the point about "what doesn't scale" there is also the function with unnamed arguments and currying. While extremely elegant for simple programs it gets confusing for real-world applications when function needs quite a lot of arguments and there is no longer any obvious order to give them. If you stick with that and you choose an order it becomes arbitrary, difficult to remember and currying no longer makes a lot of sense.
Functional programming with immutable values is a wrong pattern for programming languages. Many algorithms, almost all actually, are naturally expressed in imperative style with mutable arrays or variables.
What is needed is to bridge the good things from OCaml, the type system, the pattern matching with tagged types into a modern, imperative programming languages.
Rust is a sort of answer but they got it wrong because it is too low level about managing the memory, the ownership pardon, and everything else so programmers cannot just express the algorithm or the logic they want to implement but they have to spend a lot of mental energy thinking about ownership issues and unneeded accidental complexity like lifetime annotations.
For example a manual for loop will almost always be harder to optimize than a map. The latter gives explicit permission for reordering, allowing for vectorization and parallelization automatically.
Also, I would think twice before claiming FP non-ideal for PLs - modern CPUs employ just as much FPism as they are considered imperative. OOE doesn’t sound too imperative to me. And at the end of the way, imperative steps are just sequential state changes from a different perspective.
Do you have some references where I could learn more about that?
Not sure what you mean by unnamed arguments, but criticizing automatic currying is totally valid.
> Functional programming with immutable values is a wrong pattern for programming languages. Many algorithms, almost all actually, are naturally expressed in imperative style with mutable arrays or variables.
This is a huge jump. Any imperative solution can just be expressed as a fold of some sort and many algorithms, esp. those that use stacks, are easily expressed recursively. Which one is more "natural" is 100% subjective, but I'm in the declarative is easier to reason about than imperative camp. Moreover, the idea that "unnatural" algorithm expression implies "doesn't scale" needs much more elaboration.
> What is needed is to bridge the good things from OCaml, the type system, the pattern matching with tagged types into a modern, imperative programming languages.
> Rust is a sort of answer but they got it wrong because it is too low level about managing the memory, the ownership pardon, and everything else so programmers cannot just express the algorithm or the logic they want to implement but they have to spend a lot of mental energy thinking about ownership issues and unneeded accidental complexity like lifetime annotations.
It's not "wrong" just not what you want, and honestly the ownership model isn't that bad. The overhead amortizes somewhat as you get used to it. I of course agree there is room for more languages with ML-like type systems though!
The optimal implementation might be imperative but that doesn't mean we need to define our code that way. SQL is a good example here.
There are times when it isn't.
I'm thinking of Richard Bird's functional pearl, The Smallest Free Number, where the divide-and-conquer algorithm is faster than the imperative one.
From the conclusion:
One of the differences between a pure functional algorithm designer and a procedural one is that the former does not assume the existence of arrays with a constant-time update operation, at least not without a certain amount of plumbing. For a pure functional programmer, an update operation takes logarithmic time in the size of the array.1 That explains why there sometimes seems to be a logarithmic gap between the best functional and procedural solutions to a problem. But sometimes, as here, the gap vanishes on a closer inspection.
The ability to arrive at the divide-and-conquer algorithm is quite fascinating as it uses plain, boring old mathematics and is, for some, quite straight-forward to derive on one's own.
Yet people are more convinced by imperative implementations. I'm curious why this is. Is it because we "teach" people to believe programs are executed sequentially and are therefore somehow "inherently" imperative? Or is it easier to reason about algorithms in terms of their operational semantics?
The problem then lies in the deeper explanation. It is said that the hardware is just taking instructions and executing them one after another, and that is then mapped to the execution of programming language statements. The issue of ‘imperative’ vs ‘non-imperative’ implementations is really a question of granularity. The map between machine instructions and language constructs is so large (for most every modern machine) that while the imperative algorithm seems more reflective of the underlying architecture it is just a layer of cover up to make programmers feel better.
I really think that the appearance of control over fine grained instructional behavior give people the feeling that their imperative code is truer/more-correct in relation to the machine. This feeling leads to the presumption that imperative is more efficient.
As a final caveat, the ability for a non-imperative algorithm to be equivalent to its imperative alternative tends to rely on the language’s compiler (and the restrictions inherent in the non-imperative language). This is the origin of the ‘with-a-smart-enough-compiler’ argument that people sometimes level against non-imperative programming, i.e. there is not a compiler smart enough to take your high level language and produce the same machine code I do in my low level language.
So I’m sum, I think it is both a teaching error (the continual re-enforcing of confusion between what a program says vs what a machine does) and a general human level confusion as to what an algorithm is at the level of silicon in 2022.
Personally I think the Haskell code is a bit nicer. Mutation is inherently unsafe and you need to be more careful when performing such computations. Haskell code makes this painful to read by planting red-flag words like, "unsafe" around.
In C++ mutation is the norm and so it's much easier skip past such code. No indication that these operations are unsafe. The experienced reader will scrutinize this carefully or gloss over it at their own peril. The code is terse on the subject as the syntax maximizes efficiency for this case.
Here's another: https://stackoverflow.com/a/5269180
If you absolutely need in-place mutation, it's available. It's just not the default.
But I don't think there's a "non-imperative" quicksort algorithm. There's definitely value in preferring functional, non-mutating implementations over imperative where they make sense, but I've seen too many people pretty much claim that functional style of programming is all you need, and that's pretty much a lie IMHO.
I like and use functional and immutable but saying that's best is like saying a screwdriver is better. Sometimes imperative is cleaner. In a video, the creator of Scala, M. Odersky, said Scala allows mutability because sometimes it is cleaner.
As an SQL guy, I remember one time a cursor solution was cleanest and best.
Scala's librares have some string stuff which looks immutable but isn't, under the hood.
As ever, it depends.
> Or is it easier to reason about algorithms in terms of their operational semantics?
Good question. I'd say people think in terms of actions not mathematical functions. I certainly do. Imagine teaching an 8-year old. And it does map so well onto the underlying reality of fundamentally mutable hardware.
It maps well to the abstraction provided by the hardware. In reality we know that modern architectures are executing instructions out-of-order for efficiencies' sake and that data-accesses are not necessarily sequential either. And we haven't even considered multiple-core processors that are so common these days!
As Bird points out in his book, when one looks close enough there are cases where the logarithmic gap between the imperative vs. functional approach disappears.
And further, with register targeting and stuff it's not often true that recursive calls are less efficient than their imperative counterparts anymore... although I suppose historically this could be why, at least for small arrays, imperative programmers could assume constant-time indexing and updating.
I'm not nearly as versed in functional programming as I'd like to be. I was raised on C and algorithms were always described in terms of procedures to me where the proofs took quite a bit of work to follow. However as I learn more about algorithm design in functional programming and functional data structures I can't help but notice that the proofs are much easier to follow while sometimes the solution seems quite alien and I wonder if that's because of my heritage of thinking operationally rather than by calculation. I've often been surprised to learn that many of my assumptions about the logarithmic complexity of functional algorithms are not always there!
The impossibility to return early in a function does create really convoluted code though. I’m wondering if there’s a solution to that in FL
Hmm, I think "cryptic syntax" is probably in the eye of the beholder
The Rust with GC proposals I've looked at all break compile time thread safety checking.
Similarly, I am not sure what is the issue with using imperative OCaml for imperative algorithms when they are a better fit for the problem at hand?
So you have to give up to one of pillars of the functional programming paradigm and you get a less elegant but more practical programming language. Otherwise I agree that using labeled arguments is mostly fine and doesn't completely spoil the language.
The more serious compromise to the functional programming paradigm is the fact that you need to use mutable variables and imperative style programming. Once you do this you lose most of the elegance and attractiveness of functional programming.
> Similarly, I am not sure what is the issue with using imperative OCaml for imperative algorithms when they are a better fit for the problem at hand?
What I mean is that for any moderately complex application you need to switch to imperative style so the appeal of OCaml is mostly lost. You better choose a programming language that is designed for imperative programming since the beginning.
The arguments I am giving explains why there are practically no real world applications done in OCaml. Some people insist using OCaml because they love the elegance of the language and I understand them but reality is it doesn't scale to complex applications.
For people in Janestreet I think this is a sort of niche where they get an added value from OCaml thanks to its superior typing system and compile-time detection of many errors. I guess they care really a lot about the business logic of their applications and OCaml shines to ensure it is correct so for them the advantages out-weights the inconveniences.
In the same way, it is perfectly possible to switch to the imperative style only in the specific code path where performance really matters and use abstraction to isolate this performance-sensitive part from the rest of your application. Ideally, you can then keep both the elegance of functional programming and the performance of imperative programming.
I’m kindly invoking Hitchens razor, here
Let me refer you to the most successful programming language of all time, by far–Microsoft Excel formula language. It's:
- Functional (data transforms are purely function applications, there's even a LAMBDA function now)
- Immutable (functions in the system can't change values, only consume incoming values and output outgoing values).
https://www.goodreads.com/en/book/show/594288.Purely_Functio...
Unfortunately, I haven't had a chance to professionally program functionally since the n. :(
It was all Java and C++. Though I like C++, maybe it's a Stockholm syndrome. ;)
But, partly thanks to that course, I'm able to pick up any paradigm, and my opinion on what's better is informed by knowledge of both things. I'm also able to structure imperative code better than my "imperative only" colleagues.
especially common are pattern-matching assignments (technically `=` is the “match operator”) that idiomatically behave much like matches on the left hand side of `<-` in haskell do notation, i.e. inline runtime assertions on structure
these communicate programmer intent really well! you could probably have them in static land in a non-`monadFail` context too, but you'd want dependent types or something lest you go the way of typescript and resign yourself to unsoundness
in fact it's so nice that i feel pain in any dynamic language without full-fat pattern matching, like when i have to write disgusting if-else chains in complex nix expressions
The pattern-matching would still be made better with static checks. It sucks to have a function blow up at runtime because of something as trivial as args being swapped or some code somewhere changing its return types. Someone brought up Gleam earlier, but god why with that syntax?
I'd still rather have dynamic checked pattern matching over the alternative.
I do still use it and typespecs, because it's better than no checking.
real world ocaml 2e is nice, but like a lot of oreilly books about $LANGUAGE lately it's a lot of thinly-veiled $COMPANY opinions on $LANGUAGE best practices, where $COMPANY is, in this case, jane street. this is great if your motivation for learning ocaml is applying for a job at jane street
if you think ocaml seems cool because wow jane street does epic hft in ocaml, then read real world ocaml 2e
if you think ocaml seems cool because wow they wrote coq/fstar/the early rust compiler in ocaml, then read cs3110
I find I can learn a lot of life lessons by reading a condensed account of a person’s entire life in their (auto)biography.
For the same reason, I would hope to learn a lot of great real life patterns from a book called Real World OCaml… a kind of condensed (auto)biography of an institution’s experience with a technology.
learning the language first, then someone's ideas about how it should be written (in this case, as encoded in a replacement standard library with a special module dedicated to making any call to the actual standard library throw a compile error), gives you the requisite context to understand the latter
But as an example when writing Typescript, I feel so frustrated of not having a clean way of doing pattern-matching
The whole point of Typescript and why it is so successful, is because they only add type system on top of JavaScript.
Pattern matching would introduce new language constructs beyond what is required for defining types.
As for your Kotlin example, Dart's failure shown why it isn't a good approach.
Kotlin also shows what happens when the underlying platform decides to go in another direction (value types, loom, default methods on interfaces), and the amount of boilerplate that needs to be generated to pretend to be like the host language.
A language that only matters, thanks to the way Google is pushing it on Android to replace Java for anything besides system libraries.
We already get stuff like type narrowing and generics.
Typescript code without type annotations should be JavaScript compatible, minus features still in flight for standardisation.
There are other languages for that like ReasonML.
The stdlib is very weak so everyone uses this third party library. That really rubs me the wrong way.
All structures share a namespace for their elements which is super wacky.
So don't use the third-party library then? There's a lot of functionality in the default Stdlib, use what you can from there and find third-party libraries for the rest...
> All structures share a namespace for their elements which is super wacky.
Not sure exactly what you mean here, perhaps that all modules in a single compilation unit are globally namespaced. Simple enough to solve nowadays especially with everyone adopting a common dune-led convention of namespacing by the library name.
Also, just to get proper motivation, why should I learn functional programming as a capable Software Engineer?
I don't write in a functional language in my day job, but I'm much more aware of global state and side-effects in my code than before. We mainly write in Python and C#, but I encourage my team members to dabble in SQL (for dataset manipulation) and Haskell (for functional purity). If anything, it makes them understand LINQ better.
Before that course I was already grouping languages by inheritances from C or Lisp families, but really started to recognize and appreciate ML more.
I've been slowly working my way through this course and I ran into an issue recently when I upgraded my OCaml installation to the latest version (4.13.1). With this version I find that the simple instructions for building an executable with dune (especially one that uses OUnit) given here https://cs3110.github.io/textbook/chapters/data/ounit.html no longer work.
It seems dune now requires you to initialize a project. Does anyone know how to translate the instructions in the course to the current version of dune ?
I realize I could install an opam switch for the previous version but I'd rather be working with the latest one.
Just hoping someone might be able to save me an hour or so figuring this out on my own.
But then it has quirks like using ;; to end statements (EDIT: only in the REPL). And comments with that weird syntax
But worse of all are the optional parenthesis in function calls. Yes, I know Ruby has it. But it feel super weird and a needless flexibility (that causes more confusion than it solves).
I can't get over this stuff, sorry.
Saying "it has quirks like using ;; to end statements" is misleading to the point of just being bogus. The double semi-colon is only ever used in the REPL. In fact, I've been programming OCaml for fun and professionally for over 15 years, and I've never used a double semi-colon in my code, nor have I ever encountered one in the "wild".
??
> let r = some_function x y z in ...
Btw, iirc, SML doesn't have this: there you only have 1 parameter but it could be a tuple
Nah, SML does also support automatically curried function definitions, it's just that by convention that feature didn't get used as often. I tried to find out why that was the case a while ago, and stumbled on this explanation: https://www.reddit.com/r/ProgrammingLanguages/comments/jde9x...
from here https://cs3110.github.io/textbook/chapters/basics/toplevel.h...
Also, I love your handle :P
P.S.: are you referring to the paper entitled “the essence of compiling with continuations”, or something else?