I'm not sure whether someone else has commented on this. I am yet to read the comments. Maybe I will read them soon enough.
Anyways and however, speaking in strict mathetical sense, the model of a tree actually breaks the classical mathematical model of operator precedence.
1 + 1 + 1 evaluates to:
(+)
/ \
(+) (1)
/ \
(1) (1)
The above will be correct, mathematically, but will break once you involve multiple mathematical operators in the statement. Because, mathematically, operators have precedence.
The operators are essentially ordered based on their depth into the right of the question / statement but unless I am terribly wrong, this is not the case in mathematics and some operators have higher precedence regardless of their position in the statement.
Any comments on this?
CodesInChaos 2 hours ago [-]
Greenspun's tenth rule of programming:
> Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
tromp 3 hours ago [-]
> Overall, I built a Graph Reduction engine
I did the same for my performant implementation of pure functional programming language BLC/BLC2,
which in 400+ lines contains a graph reduction engine for combinatory logic, to which the lambda calculus programs are converted by Kiselyov's bracket abstraction algorithm.
The function named clapp was likely a beast to debug.
dalton74 24 minutes ago [-]
My weekend project started as "parse a log file" and now it's a microservice mesh. Relatable.
gnarlouse 10 hours ago [-]
This reminds me of decades ago when ...wait, I was still writing code like three years ago.
Joker_vD 3 hours ago [-]
> The thing is, all of our nodes are pointing to each other inside this memory block. When we realloc it with an increased size, it might get moved to a new memory address. Completely breaking all of our pointers and causing a segfault! How do we tackle this problem?
Store indices into the arena array? You could probably even use 4-byte indices and cut down the memory usage...
> Fib(40) literally took 12+ GIGABYTES before hitting an OOM and crashing. Why? Because it spawns approximately 1.3 Billion nodes.
Okay, maybe you can keep 8-byte indices.
> The mark-and-sweep garbage collector we just completed is a stop-the-world garbage collector. And the algorithm we’re running is inherently exponential.
How about a copying collector then? The recursive Fibonacci generates a lot of garbage but IIRC its live set is actually pretty small at any single point of time. If you need a benchmark for GC when your function actually has a huge live set, then something like
def garbage(n):
if n == 0:
return None
return (garbage(n-1), garbage(n-1))
should do the trick; if you don't have proper data structure you can simulate it with closures pretty trivially.
> And we can do something about how we’re evaluating fib itself
You mean "switch from recursively walking AST" or "write a non-exponential Fibonacci"?
herodotus 3 hours ago [-]
I once invented a programming language where EVERYTHING was an object. No message keywords. 1 is an object. + is an object. You can send an object to another object - you get back an object. Example 1+ is an object. Its is the result of sending + to 1. If you send 1+ the object 1, you get 2. If you send 1+ the object + you get a run-time type error. You can also go left to right. +1 is an object. If you send +1 to 2, you get 3. It gets nice when you add list objects. (1,2,3,4,5)+1 => (1+,2+,3+,4+,5+) 1 => (2,3,4,5,6). And so on.
skrebbel 2 hours ago [-]
Does that imply no support for operator precedence?
herodotus 20 minutes ago [-]
It does. Parenthesis are allowed - they are syntax for lists so that a * (b + c) will compute the contents of the list before sending the resulting object to a*. The inspiration is the idea of Currying in Lambda Calculus, although it requires postfix notation. Now you have me thinking about whether I could alaso make parenthesis and commas into objects. So (1+2) for example for do this: ( is sent the object 1. That yields the object (1 That is, an object that is not ready to be sent on. The "(" bounded object would only be released when it received a ")". Thanks for the thought!
heronbank 1 hours ago [-]
Relatable. Spent a week optimizing a query that runs twice a year for a report nobody reads. The rabbit hole is real.
ancientstraits 10 hours ago [-]
The "how to implement a hash table" article 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.
pjmlp 2 hours ago [-]
Why? The only thing missing is the proper data structures and algorithms background.
Which during my degree, the lab deliverables were 100% C code.
Here, one possible book:
Data Structures, Algorithms, and Software Principles in C (1994 edition)
When I was in university, hash tables were definitely among the things we had to learn about and then implement in C, probably in first year. Per Wikipedia, the concept dates to 1953 (with an implementation in assembly); of course people made them in C once that was an option.
kleiba2 3 hours ago [-]
I always liked that idea of just doing a linear wrap-around sweep through an array that holds (key, value) pairs, until you find the pair with the key you're looking for (for 'get' or 'contains?') or an empty spot (for 'put'). The trick to make this fast is that the hash function (key -> int) tells you at which index to start the sweep.
No secondary data structures, super simple to implement, and it works great for small use cases.
dprkh 10 hours ago [-]
Arrays are hash tables. You can implement a very simple hash table from a tutorial, but can you implement a sophisticated one? What about a concurrent hash table?
fodkodrasz 4 hours ago [-]
> Arrays are hash tables.
Maybe in JavaScript... but there is a topic called datastructures, where arrays are arrays, and hashtables are hastables. If people say this without a flip of an eye I'm not surprised why people write stuff like
> I thought that hash tables were something that were basically impossible to make in C
pjmlp 2 hours ago [-]
Besides the sibling comment, you can used closed hash tables algorithm (open addressing), which is fully based on a single array.
In a trivial sense, arrays are hash tables with a hash function of the identity f(x)=x.
It’s just not particularly common (or helpful) to view them that way.
saghm 10 hours ago [-]
Yeah, I'm pretty sure we made hash tables in the first C class I took in college in my second semester freshman year. If you can make a linked list, and then make an array of them, and a function to map keys to array indexes, you have a hash table. Whether it's actually performant is entirely a separate question, but a naive hash table is still a hash table.
raddan 9 hours ago [-]
Hash tables are awesome. They are both an incredibly simple data structure and a seriously deep rabbit hole. Most of the complexity comes from collision resolution [1], and how you handle resolution largely determines what kind of hash table you have. There are at least dozens of collision resolution approaches. The simplest, and probably the one you implemented in your undergrad C class was open addressing. That’s also what I implemented as an undergrad. But there are many more approaches, some quite a bit more complicated, and many of them let you continue to shave off asymptotic costs when you run collision resolution, or they improve locality for typical lookups, allowing better cache utilization, etc. Hash tables are super fun to play with, and for full effect, you really do need to implement them in something like C.
I only skimmed the linked article, but I do wonder whether the author ever realized that they needed to think about scope rules. I searched for the word “scope” but never found it. Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain).
Yeah, I learned about a bunch of the other algorithms later (forgetting the names, but stuff like "move to the next slot rather than putting collisions into buckets" and "hash a second time if you hit a collision"; I'm sure I'm forgetting some of the nuances).
> Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain)
Well if you like both lexical scope and pain, there's always lisp!
jimbokun 6 hours ago [-]
Be careful with Lisp!
You might end up founding one of the first e-commerce sites, sell it for a handsome payday, and then create the first startup accelerator and make insane amounts of money while transforming the industry.
Safer to stick to Blub.
applfanboysbgon 7 hours ago [-]
> I thought that hash tables were something that were basically impossible to make in C,
Why would you believe this in the first place?
satvikpendem 7 hours ago [-]
Yeah it's a strange assumption, as this was taught in basic data structures class years ago and any language can implement any data structure, technically speaking. C especially is a weird assumption because lots of foundational software is written in C including hash tables.
winwang 9 hours ago [-]
Nice, I like this style of exposition. "Let's do this one thing -> well, shit -> (loop)". Term rewriting (graph reduction as you've said) is evaluation.
shingoshoji 3 hours ago [-]
Fascinating read.
When I was in my early teens, I experimented with created programming languages, I distinctly remember one I made on https://esolangs.org
Anyways and however, speaking in strict mathetical sense, the model of a tree actually breaks the classical mathematical model of operator precedence.
1 + 1 + 1 evaluates to:
The above will be correct, mathematically, but will break once you involve multiple mathematical operators in the statement. Because, mathematically, operators have precedence.The operators are essentially ordered based on their depth into the right of the question / statement but unless I am terribly wrong, this is not the case in mathematics and some operators have higher precedence regardless of their position in the statement.
Any comments on this?
> Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
I did the same for my performant implementation of pure functional programming language BLC/BLC2, which in 400+ lines contains a graph reduction engine for combinatory logic, to which the lambda calculus programs are converted by Kiselyov's bracket abstraction algorithm.
[1] https://github.com/tromp/AIT/blob/master/uni.c
Store indices into the arena array? You could probably even use 4-byte indices and cut down the memory usage...
> Fib(40) literally took 12+ GIGABYTES before hitting an OOM and crashing. Why? Because it spawns approximately 1.3 Billion nodes.
Okay, maybe you can keep 8-byte indices.
> The mark-and-sweep garbage collector we just completed is a stop-the-world garbage collector. And the algorithm we’re running is inherently exponential.
How about a copying collector then? The recursive Fibonacci generates a lot of garbage but IIRC its live set is actually pretty small at any single point of time. If you need a benchmark for GC when your function actually has a huge live set, then something like
should do the trick; if you don't have proper data structure you can simulate it with closures pretty trivially.> And we can do something about how we’re evaluating fib itself
You mean "switch from recursively walking AST" or "write a non-exponential Fibonacci"?
Which during my degree, the lab deliverables were 100% C code.
Here, one possible book:
Data Structures, Algorithms, and Software Principles in C (1994 edition)
https://www.amazon.com/dp/0201591189
I also like https://github.com/tidwall/hashmap.c for general use.
No secondary data structures, super simple to implement, and it works great for small use cases.
Maybe in JavaScript... but there is a topic called datastructures, where arrays are arrays, and hashtables are hastables. If people say this without a flip of an eye I'm not surprised why people write stuff like
> I thought that hash tables were something that were basically impossible to make in C
https://en.wikipedia.org/wiki/Open_addressing
It’s just not particularly common (or helpful) to view them that way.
I only skimmed the linked article, but I do wonder whether the author ever realized that they needed to think about scope rules. I searched for the word “scope” but never found it. Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain).
[1] https://en.wikipedia.org/wiki/Hash_table#Collision_resolutio...
> Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain)
Well if you like both lexical scope and pain, there's always lisp!
You might end up founding one of the first e-commerce sites, sell it for a handsome payday, and then create the first startup accelerator and make insane amounts of money while transforming the industry.
Safer to stick to Blub.
Why would you believe this in the first place?
When I was in my early teens, I experimented with created programming languages, I distinctly remember one I made on https://esolangs.org
Fun stuff. I should get back into it.
> Perl Contains the Lambda Calculus
> (How to write a 163 line program to compute 1+1)
> Length: 90 minutes
Prerequisites: None.
This is also a fun introduction to building up lambda calculus. And it gets up to fizzbuzz!
- https://hereticpleb.vercel.app/blog