I learned C/C++ in college before learning about Algorithms. And thinking about time complexity in C/C++ came naturally to me because I had a clear mental model of what the computer was doing.
I have been using Elixir and other functional languages these days. I am excited by their promises. Functional languages can be thought as a subset of the declarative class of languages. Unlike procedural languages like C/C++, we don’t tell the computer what steps to follow. We just tell it what is expected to happen.
Since my first introduction to SQL, I have not been able to be build an intuition about how long a particular query will take. You just write the query and the computer somehow gives you the result. Even when I try to think about the time complexity of a query, I end up thinking procedurally. I ask questions like, “What steps will the computer take to return me the result of this query?” This way, I am not able to think in SQL to talk about time complexity. I am still thinking in C/C++.
I face the same problem with Elixir. While asking a question about the time complexity of a function, I am thinking procedurally instead of thinking functionally.
How do you deal with this problem? Is there no way to think about time complexity natively in Elixir, SQL, etc. or am I missing something?
With SQL, it is mostly about having the right indexes. You can see what the database does by running it with explain, analyse, etc selected. You can paste the results into sites like this to get a "better” view. Edit: a resource on SQL indexes
In Elixir, I tend to think in terms of data structures and the most efficient way to transform/run an algorithm over them. There is an efficiency guide for Erlang.
I think it’s fine to think procedurally in Elixir. “Functional” programming is more about the declarative style and the focus on data structures to me, but otherwise any language is procedural in the end. There is only one instruction executed at a time, that inherits the environment and variables of the instructions executed before.
That is, in a single process. Mutiple process problems are rather about correct concurrency patterns and less about time complexity.
I agree we can always think procedurally. But won’t it be great to have a language to talk about time complexity Functionally. A system of that is derived purely from Lambda Calculus where we don’t have to worry about steps of execution.
I’m not sure, it seems to me that lambda calculus has infinite CPU speed and infinite memory, but I’m not really sure what you are looking for besides the traditional big O.
But I hope someone else, more versed into those kind of things, will chime in
The irony is that those languages are declarative, too, if we’re being pedantic. You’re not telling the computer what steps to follow, you’re telling the compiler what effects you want to have on the C/C++ abstract machine which is very much different from what the CPU will execute (mainly by the “as-if” rule).
C++ defines a program’s observable behavior as its interactions with volatile and library I/O functions, allowing any optimization that does not change those interactions (including their order). The compiler is thus free to rewrite your Bubble sort as a Merge sort if it were to somehow recognize that pattern, and for simple patterns (e.g. something that looks like a memcpy or memset) it often does. In fact there have been many security issues arising from the fact that the compiler has optimized away a memset that lacked an observable effect as defined by the standard, necessitating functions like explicit_bzero to get around that.
In any language, including C and C++, you need to have a model of execution to reason about time complexity. I grant that the model is generally simpler for procedural languages, especially given how the transformations usually don’t affect more than constant-factor operations, but you can apply largely the same to functional languages by reasoning about unavoidable work.
e.g. to sum all the elements in a list, every element must be visited and therefore the operation is O(N). To retrieve an item from a :gb_sets, you have to traverse a binary-tree structure and therefore the operation is O(log N). And so on.
Elixir is also simpler than other functional programming languages in that it’s based on Erlang, which defines every function everywhere as side-effecting because of tracing, which precludes all optimizations that would be visible when tracing is enabled (e.g. you cannot remove a function call that provably does “nothing,” because it would disappear from the trace), so @lud is quite right in that you can “reason procedurally” about time complexity in Elixir.
The Erlang run-time system exposes several trace points that allow users to be notified when they are triggered. Trace points are things such as function calls, message sending and receiving, garbage collection, and process scheduling.
The compiler respects all trace points that it has control over, and as such cannot perform even the simplest of optimizations that would affect tracing, like removing a redundant function call, unused parameters, ignored return values, and so on[1].
Technically we could try to maintain the illusion when tracing is enabled for the specific function that was opitimized away, but the maintainability trade-off is the epitome of “not worth it.” It’s far more involved than it first appears. ↩︎
Not having to think of how will the work be done, I want to say what I want done. A classic example is Enum.map; the stdlib / compiler decide how it’s going to be done, you only are saying “I want each element of this list be transformed”.
That was my reason to start using the language. If not for those I could have just easily stayed with Java and Go and then learned Rust as it gained momentum (which I still did).
Reading your comment, I cannot intuit your intent. Do you want to write a competing compiler? Are you suffering from optimisation paralysis and are convinced all Elixir code is slow? Do you want to have better tracing / flame graphs?
Perhaps you’re thinking about (lazy evaluation)[ Lazy evaluation - Wikipedia ], where time complexity can sometimes be difficult to ascertain. This is true in any programming language that has “lazy” features (for example streams in Elixir), but is a particularly well known problem in Haskell (which is entirely lazy-evaluated by default).
SQL implementations are not lazy-evaluated per se, but their declarative nature can hide the procedural steps that will happen when you fire off the query, and for sophisticated query optimizers in RDMSs like Postgres, it’s sometimes hard to reason about what steps will be taken. You can use the EXPLAIN to see how the query planner will run the query.
In my experience, unless you’re using streams, everything is explicit in Elixir. You know exactly which lines are going to run when, sequentially, even when using recursion. However it’s true that it is a much more declarative style than python or C for example, and this can lead to some confusion because it doesn’t “feel” like you’re giving explicit steps, even though you really are. Procedural feels much more recipe-like, like you’ve got your hands in the mixture, whereas functional programming can feel more like you’re doing something abstract without steps, even though this is not the case.
There are some further nuances, obviously, linked to concurrency (which can rapidly boggle the mind when multiple things are going on, and especially in shared_memory languages like Python or C), but Elixir helps a lot with this thanks to the message passing architecture which makes concurrency a lot more easy to reason about. But I digress..
I think it’s quite easy to confuse the more declarative style of Elixir (and SQL), with the idea of laziness. Yet these are separate concepts.
This is an intriguing discussion, I have always found it easier to make a decent assumption when it comes to SQL, since you’re working on sets, big table without indexes slow, many joins with suboptimal filters slow and so on since you’re literally just creating exponential queries in some cases.
But obviously there a non intuitive cases where you gotta reach for explain to understand why the query planner didn’t do what you expected it to do regardless of indexes.
But the same is true for any type of performance optimization, in the end you gotta read the assembly, which is annoying but arguably less today with AI.
Back to your question, is there no way to think about it natively. Big O tells you about access patterns into your data. So the language is completely irrelevant, I don’t even think (correct me if I’m wrong) that any language is used when teaching this academically, since pseudo code is preferable in these cases. That said immutable language have to used different data structures to guarantee the language constraints, although we still have safe mutability with constant time access in Erlang. The best way I found to learn about a language specific behaviour and complexity is to Google and the use of LLM. LLM are great for these kinda open ended question if you don’t have concrete question with a specific data structure and algorithm in mind where you can just look up the documentation.
