HN

Need help?
<- Back
Needed 1+1, built a functional programming language

Needed 1+1, built a functional programming language

birdculture

Comments (24)

  • herodotus
    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.
  • tromp
    > Overall, I built a Graph Reduction engineI 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
  • Joker_vD
    > 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 itselfYou mean "switch from recursively walking AST" or "write a non-exponential Fibonacci"?
  • gnarlouse
    This reminds me of decades ago when ...wait, I was still writing code like three years ago.
  • ancientstraits
    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.
  • winwang
    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
    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 minutesPrerequisites: None.
  • vivzkestrel