The "how to implement a hash table" article <a href="https://benhoyt.com/writings/hash-table-in-c/" rel="nofollow">https://benhoyt.com/writings/hash-table-in-c/ was really helpful for me. I thought that hash tables were something that were basically impossible to make in C, but this showed that it was simpler.
If hash tables were impossible to make in C, then it would be impossible to make them in Python, because it is a higher level language than C.
(Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
Google for some videos by Raymond Hettinger about Python dictionaries.
Or look at the source code of the Python interpreter.
> But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
In CPython they are written in C (at the moment). Other Python implementations are written in other languages.
> (Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Btw, higher level languages being implemented in lower level languages is mostly something for interpreters. Writing a C interpreter in Python is pretty much futile, if you care about speed. But writing a C compiler in Python is perfectly fine. And writing a Python compiler in Python is also fine. Many languages self-host (at least some of) their compilers.
>It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Interesting. What are some of those optimisations that Haskell and Lean can do, that a C compiler would not be able to safely do?
A very simple one: in Haskell the compiler has knowledge about which functions cause side-effects and which don't. The compiler can skip calling pure functions whose return value ain't used; similarly, the compiler can call a pure function multiple times, instead of saving the return value in memory.
The Haskell compiler can also fairly freely re-arrange in what order things are computed.
A fairly common idiom in Haskell is to just return a tuple of two values, if they are 'thematically' linked; even if computing one is much more expensive than the other. The compiler is smart enough, to only compute one of the values, if you only use one of them. (When I say 'tuple', it could be literally (a, b), or it could be in a struct or whatever.)
Lean knows even more about your code, so you could do more optimisations. But you need to ask Claude for details, I haven't used it as much nor thought as much about it.
ancientstraits · · focus · HN ↗
fuzztester · · focus · HN ↗
(Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
Google for some videos by Raymond Hettinger about Python dictionaries.
Or look at the source code of the Python interpreter.
eru · · focus · HN ↗
In CPython they are written in C (at the moment). Other Python implementations are written in other languages.
> (Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Btw, higher level languages being implemented in lower level languages is mostly something for interpreters. Writing a C interpreter in Python is pretty much futile, if you care about speed. But writing a C compiler in Python is perfectly fine. And writing a Python compiler in Python is also fine. Many languages self-host (at least some of) their compilers.
fuzztester · · focus · HN ↗
Interesting. What are some of those optimisations that Haskell and Lean can do, that a C compiler would not be able to safely do?
eru · · focus · HN ↗
The Haskell compiler can also fairly freely re-arrange in what order things are computed.
A fairly common idiom in Haskell is to just return a tuple of two values, if they are 'thematically' linked; even if computing one is much more expensive than the other. The compiler is smart enough, to only compute one of the values, if you only use one of them. (When I say 'tuple', it could be literally (a, b), or it could be in a struct or whatever.)
Lean knows even more about your code, so you could do more optimisations. But you need to ask Claude for details, I haven't used it as much nor thought as much about it.
fuzztester · · focus · HN ↗