Needed 1+1, built a functional programming language

gnarlouse•about 5 hours ago

This reminds me of decades ago when ...wait, I was still writing code like three years ago.

ancientstraits•about 4 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.

eru•about 2 hours ago

You can also look at how CPython implements hash tables in C. The implementation is surprisingly approachable for a real world one.

krapp•about 2 hours ago

SDL3's properties API uses an internal hashtable I'm waiting for them to make public.

I also like https://github.com/tidwall/hashmap.c for general use.

dprkh•about 4 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?

saghm•about 4 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•about 3 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).

[1] https://en.wikipedia.org/wiki/Hash_table#Collision_resolutio...

applfanboysbgon•about 2 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•about 2 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•about 3 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.

gbacon•about 3 hours ago

See also https://perl.plover.com/yak/lambda/ from 1999.

> Perl Contains the Lambda Calculus

> (How to write a 163 line program to compute 1+1)

> Length: 90 minutes

Prerequisites: None.

Dylan16807•about 3 hours ago

https://tomstu.art/programming-with-nothing

This is also a fun introduction to building up lambda calculus. And it gets up to fizzbuzz!

vivzkestrel•about 2 hours ago

- 404? on blog page

- https://hereticpleb.vercel.app/blog

BurnerBurner•about 1 hour ago

Ah shit. I'll have it redirect to / ig. I vibecoded the website I didn't really wanna write javascript or deal with frameworks

Needed 1+1, built a functional programming language

⚡ Community Insights

Discussion (16 Comments)Read Original on HackerNews