Add an examples/ directory

[masak]

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).

• list builder
• left-leaning red black tree
• union-find
• maze builder
• floats
• piano
• BASIC interpreter
• reactive chat bot

(Later edit: Some more suggestions below.)

• polynominoes
• necklaces
• lambda calculus evaluator
• chess

(Even later edit: Some more.)

• rock-paper-scissors
• span
• 12 pentominoes on a chess board with a hole
• zebra puzzle
• fizz buzz

(Even even later edit: Yet some more.)

• non-overlapping intervals
• N-queens
• Sudoku
• cryptarithms (SEND + MORE = MONEY)

(Edit: Much later, yet others.)

• Conway's Doomsday algorithm
• samefringe
• towers of Hanoi (using three solutions: simple recursive, CPS-transformed, and "reconstructing")
• pirate game
• minimal object system with selectors and ports

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

[masak]

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]

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]

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]

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]

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:

• Things like default equality/comparison behavior should work out of the box. (Equality being somewhat the trickier one, as Bel basically forces "structural equality" here. Need to hit the IEEE 754 for details whether that works.)
  • Edit: Haven't checked the spec, but reasonably, the only problem would be that 0 and -0 compare unequal. Maybe that isn't even a real problem, to be honest.
• Arithmetic operations are kind of "taken" already by Bel. Two solutions possible:
  • Instead of using + for addition of floats, use +. — apparently OCaml does this.
  • Overload + to do typechecking (but to fail if you try to mix numbers). Certainly doable, but feels like a slippery slope.
• Printing should also Just Work; probably worth it to overload the Bel printer machinery without asking.
  • But the long term saner thing might be to install a hook for user-defined lit types, and plug lit flo into that.
  • This put me in mind of Printing Floating-Point Numbers Quickly and Accurately (which I haven't read but probably should)
  • There's also this newer paper: Ryū: Fast Float-to-String Conversion; should probably read that too
• Conversion back and forth between floats and Bel rationals:
  • Converting from floats to Bel rationals is mostly no problem, since Bel rationals have sufficient precision to correctly represent floats. Might want to gently nudge the user to think about rounding, to avoid 0.30000000000000004-style situations. Also, NaN and Inf and -Inf are not Bel rationals; might want to fail by default, but allow these to be converted to provided values (not necessarily numbers).
  • Converting from Bel rationals to floats means precision will be lost in many cases. Don't know if there's prior art here? Java's BigDecimal has a conversion method, which mentions both "overflowing" to the infinities and the expected loss of precision.

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]

The scores so far:

• practically no work: list builder
• a little work: left-leaning red-black tree
• straightforward implementation: union-find, maze builder
• ...
• a considerable amount of work: floats

[masak]

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".