search

masak / bel

An interpreter for Bel, Paul Graham's Lisp language
GNU General Public License v3.0
25 stars 1 forks source link

Add an examples/ directory #429

Open masak opened 1 year ago

masak commented 1 year ago

Really short term (and enough to close this issue): two examples, since the directory name has an "s" at the end.

Long term: all of them (or, if something better comes up, as many but better).

(Later edit: Some more suggestions below.)

(Even later edit: Some more.)

(Even even later edit: Yet some more.)

(Edit: Much later, yet others.)

Going to describe them now, in individual messages. With some luck, two will pop out on top of the list.

masak commented 1 year ago

List builder

Inspired by PicoLisp's make function. Main idea can be described as a DSL to dynamically build a list (covering some more exotic list-building situations than just map and keep). (Edit: Actually, the main point is that some things are just plain faster with the list builder, which helpfully keeps pointers internally to both the first element of the list, and the last. The fact that list building is also more straightforward to express with this DSL is... nice, but secondary to the efficiency benefit.)

I have a private repository with this example working already. I should (a) make the repository public, and (b) add it to examples/.

Ok, so this one is clearly a prime candidate. I can see I'd like to split out the testing into its own (proto-) module. Probably put the testing into a function, something like run-tests.

Looking at it, I also see a few more tests I'd like to write, but that's not on a critical path.

Possibly the test suite should also pull in bel-masak-prelude, because it uses prlf. Oh! Both the test module and bel-masak-prelude should go in a different directory, not examples/. No obvious name comes to mind.

masak commented 1 year ago

Left-leaning red-black tree

The selling point of a balanced N-ary tree is that lookup time is logarithmic. That's a big deal. Making it a persistent data structure, returning a new immutable version on every change, makes total sense to in a language leaning functional.

I have a private repository here too with a working-enough implementation, but it's mutative, not persistent. There are a few tests; need to have more of them.

As a nice bonus, there's a nice way to get a faster sort based on this tree data structure.

masak commented 1 year ago

Union-find

Another very impressive data structure. There are two operations: create a new element with a fresh index, and unify two equivalence classes (as represented by two indices). The wonder of it all is that the second operation can be as fast as to be effectively constant-time, as is checking whether two indices belong to the same equivalence class.

No persistent data structure this time; it's ephemeral.

I haven't implemented this one (except in other languages), but it should be fairly straightforward. Some tests would be good too.

masak commented 1 year ago

Maze builder

With the above union-find algorithm, it's pretty straightforward to build a maze: just start with all the walls solid and each enclosed room its own equivalence class, and (in a randomly determined order) knock each wall out if doing so would make two equivalence merge.

It's a small/fun bit of code, and can be drawn in a satisfactory way with ASCII.

Maybe some tests can check a few invariants of the maze: that the graph of rooms is equal to its own spanning tree, which means that there is a unique shortest path between any two rooms.

masak commented 1 year ago

Floats

A numeric data type that implements IEEE 754 double precision floating-point numbers. The built-in numbers in Bel (complex rationals of infinite precision) are nice until they aren't — sometimes you really do want to chop off some precision instead of slowly grinding to a halt because of thousands of decimals of accuracy. See Guido's story about why he didn't retain ABC's infinite-precision rationals in Python:

Numbers are one of the places where I strayed most from ABC. ABC had two types of numbers at run time; exact numbers which were represented as arbitrary precision rational numbers and approximate numbers which were represented as binary floating point with extended exponent range. The rational numbers didn’t pan out in my view. (Anecdote: I tried to compute my taxes once using ABC. The program, which seemed fairly straightforward, was taking way too long to compute a few simple numbers. Upon investigation it turned out that it was doing arithmetic on numers with thousands of digits of precision, which were to be rounded to guilders and cents for printing.) For Python I therefore chose a more traditional model with machine integers and machine binary floating point. In Python's implementation, these numbers are simply represented by the C datatypes of long and double respectively.

This example would basically implement IEEE 754 doubles. Internally, they can be a 64-element bit vector; no doubt the visualizer would provide a good inspiration along the way. (But this is also an excellent occasion to have really clear comments.) (Edit: by an amazing coincidence, I re-stumbled upon such a clear comment in the Wren repository just now.)

There would need to be dozens of tests. Scores. Maybe hundreds.

Other things worth thinking about:

Ah; phew! So this is a big project. Cool, definitely doable, but big. It ends up somewhat further down the list than the first four.

(I also think this will end up being genuinely useful later when doing more advanced CGA graphics stuff. Rationals really do not work well as soon as circle arcs are involved.)

masak commented 1 year ago

The scores so far:

masak commented 1 year ago

Piano

Not quite sure where I was going with this one, maybe some ASCII art of (parts of) a 77-key keyboard, and then some famous melody (such as "Für Elise") being printed under it in real time.

Should be simple enough. When I search, I find several sites with the notes for the song (although not of them especially pleasant). I would put this one under "a little work".