December Adventure

Today was mostly table-setting, but important table-setting nonetheless. Most of the actual 'coding' was writing an example factorial for the documentation, and altering the web repl to display output in a way I find more sensible.

The rest of the efforts today were writing up a bunch of documentation (to try and nail down what the language actually is) and to get everything up on the web, as the initial release.

To continue, I'll be checking out other folks' adventure logs. 'Til tomorrow!

Today saw me writing a bunch of tests, mainly to try and figure out what the current behavoiur is and what I want it to be. I had not set out to do this today, but the circumstances called for it.

I started the day watching the episode of Tacit Talk with Zach Smith, and then read Smith's accompanying article about combinatory programming. Very relevant to what I'm attempting to accomplish here, as the topics included practical usage of combinators. One of the more prudent points made was the significance of naming, I currently have the combinators named after their letters. In my little file of demos, I decided to define the names Smith gives for some of the combinators in terms of my letters. I also implemented the 'conditional combinator', which is both simple and incredibly powerful, I imagine I'll be using it plenty as the moth goes on.

Another thing mentioned in the post is variadic functions, and I immediately realised how wonderful it would be to have some sort of variadic compose in my language. Turns out, implementing it in the language is very simple, with the horrible downside of exposing some behaviour that I didn't like and wasn't consistent and knew I needed to fix at some point. But here it is staring me in the face, so maybe I'll give the issue some effort sooner than later. That said, some sort of variadic compose still works as I want it. The variadic compose I wanted would look like variadic-compose W X Y Z... and work out to (W (X (Y (Z... )))). Turns out, a simple fold applied to the B combinator. So, as it stands, I just need pass a list of functions rather than something more 'variadic' and it works great. A simple example is (fold B (list (+ 4) (* 3) (+ 7))), which takes an argument, adds seven, multipies by three, then add four. So (fold B (list (+ 4) (* 3) (+ 7))) 1 would give you the equivalent of (+ 4 (* 3 (+ 7 1))), which works out to 28. Pretty slick! That's about all for today, 'til tomorrow!

MY PROBLEM IS my design, essentially. I want to be able to do things like ((((((x)))))), which would absolutely break down in most lisps without x being something very particular. I am NOT interested in giving this up. The problem comes in when considering quoting things. How would one pass a list as an argument not to be evaluated otherwise? To get around this, I ended up with a whole type called 'quote', which I'm pretty sure is not in most other lisps that make sense. I don't think this is wrong per se, but it's certainly unusual and I'm not sure if it's actually good.

Perhaps I need to make it more transparent. I already do this to some extent, one can do (+ (quote 4) 5) and get nine and so forth. Perhaps I ought to expand this to an extent, but maybe part of the problem is figuring out where to set the line. Maybe I'll just try to go case-by-case and see what happens. I could also do well to think about when I might want to unquote but not evaluate. One of these instances involves symbols. As it stands, there' pretty much no real way of getting a symbol back from anything. Not being able to get at symbols easily has fairly massive implications for metaprogramming which I'm not interested in accepting at this point. Other problems came when trying to implement a variadic combine combinator. Making the type that accepts a list of functions was straightforward and pleasant, but the expectedly simple means of making it more properly variadic blew up in my face.

So, while this hasn't exactly led to much code today, this has led to lots of thinking about the semantics of what I'm doing.

My past self has been temporarily defeated by my present self. My earlier design (mis)decisions stand to live another day. And by that, I mean I got a variadic composition combinator working.

The points I made yesterday still stand, by and large.I just figured out how to do something I didn't know prior.

But yes, there is now a variadic compose (B) combinator. I have a compose-all that lets me call compose-all f g h j k... and get a function that accomplishes (f (g (h (j (k...)))))

I'll try to explain it, mostly for my sake. The statement I ended up with is (def compose-all (rest (B (fold (B (C B unquote) B)) (cons I)))). We start with rest, which takes a function (the remaining matierial) and gives back a variadic function. So, (rest f a b c d...) gets turned into something that feels like (f (a b c d...)). So the function we call on the rest starts with a B combinator, which means it applies the second argument (here (cons I) to the rest before calling the remainder of the function on that. The problem as it existed yesterday was that the passed rest was quoted where it wasn't opportune to have it quoted. Attaching an identity to the front lets us call a fold where the first argument is a proper unquoted function, and the second is quoted, and returns a proper function (representing the composition). That's pretty much all there is to it, I leave the rest as an excersize to the reader (the rest feels more like bookkeeping than insight to me). So now we can compose a bunch of things much more easily.

← ((compose-all (+ 4) (* 7) (+ 3)) 5)
 = ((+ 4) ((* 7) ((+ 3) 5)))
 → 60

Not a day where much happened, but I did manage to drop in the all-too-crucial min and max operations.

Today I worked on and though about something that one might call 'generators' in this language. I'm tentatively using that word because they loosely resemble the ones in Python, though they don't (and won't) behave the same and have the same uses.

To start, let's think of an example of sorts (that has not yet been implemented). Let's say I want a generator for the Fibonacci sequence. I'm imagining an interface where you can use something like fibgen t to get you the next element of the sequence (and something more), and fibgen nil to 'close' the generator (which here wouldn't really accomplish much, but could be used to say close a socket at some point in the future). The 'something more' alluded to above is where the magic really comes in though. What will be returned is a cons cell containing the expected output as the car, and in the cdr sits the new generator that'll give you the next item in the sequence. So, the unfortunate-looking code S (C (C (B print car) I) nil) (B (B print (C car t)) cdr) fibonacci-generatorcould produce output that looks like:

← S (C (C (B print car) I) nil) (B (B print (C car t)) cdr) fibonacci-generator
8
13
 → t

That's very rough, and far from what I want it to be ideally, but it's a starting point I'll probably try to implement to some extent over the next while

Not much to report today, still tooling around with the idea of generators mostly. Also trying to think more abstractly, to maybe find more general forms of tail-recursive functions or generators rather than just implementing a few and looking for patterns. Feels good and proper to flex my mathematical muscles here

Slow day, decided to implement a greater than and less than, which were oddly absent prior.

Okay! We've got our first-ever generator! This is a nice little thing that'll give us fibonacci numbers. It won't entirely be clear how this is supposed to be used just from today's notes, but maybe you can figure out something about it. I'll just drop the code, use it a couple times, and then talk about it some more.

← (def fibonacci-generator (Z (B (B (C (C C nil))) (B (Phi cons (Phi + car cdr)) (C B (Phi cons (Phi + car cdr) car))))))
 → _264
← (fibonacci-generator (cons 1 0) t)
 → (1 . _260)
← (cdr (fibonacci-generator (cons 1 0) t)) t
 → (2 . _260)
← cdr ((cdr (fibonacci-generator (cons 1 0) t)) t) t
 → (3 . _260)
← cdr ((cdr ((cdr (fibonacci-generator (cons 1 0) t)) t)) t) t
 → (5 . _260)

So to call it, we pass it our initial state (here, it's (cons 1 0) for the first two whole number elements of the sequence), then the second argument is just a t to confirm we are after the next element. It returns the next element, and a function representing the next step in the generator. Pretty cool! Also nice to note, that we can indeed change the initial values to get different results, so if one were to pass 1 and 2 instead of 1 and 0, they'd get a generator for the Lucas numbers instead (which means this function is poorly named!), and any other two starting points may provide a different sequence which operates on the same premise.

I've been trying to think about generalizing this, and have been slowly working toward it. To come!

Okay! Some pretty neat developments for today. I did end up banging out a more abstract way of coming up with generators. It ended up much more comprehensible than I expected it to be.

abstract-generator f m s b

The above is a general way to make generators (as previously described). f is a function that takes the state, and returns the 'next' value of the generator. m is a function that modifies the state for the next call of the generator (which I imagine might just be I for an interesting host of generators). s is the state, or rather, the initial state the generator is to take. And finally b is our boolean which if true gives the next step in our generator. So, as an example, let's make a nicer version of the fibonacci generator.

← (def fibgen (abstract-generator (Phi + car cdr) (Phi cons (Phi + car cdr) car) (cons 1 0)))
 → _260
← fibgen t
 → (1 . _260)
← cdr (cdr (cdr (fibgen t) t) t) t
 → (5 . _260)

So, our f adds the previous two numbers to get the next number in the sequence, m swaps the previous two with the previous one and the current, and sis our initial state. Plug all this in, and there's the generator!

I haven't finished some sort of equivalent for some class of tail-recursive functions, but it's in progress. I also haven't really taken an opportunity to really play with this new way of doing generators. But, the process of doing this has made me think about how something like this might be used to better teach recursion in some way. Definitely just speculation at this point, but I'm excited by the promise of this stuff. 'Til next time!

Working on the recursive function abstraction discussed prior, lots of trial, even more error

Progress moves slowly, but I feel like I'm getting a better feel for making mistakes. The Z combinator is a mysterious device whose ins and outs are fun to dance around.

More importantly, I made sure the online repl was up-to-date, and it now includes such wonders as compose-all and abstract-generator

Still learning things about how I might work with this abstraction. Oddly enough feeling a little surprised that I got the abstract generator so quickly.

Nothing to report! Almost no coding today. Still thinking about abstractions upon recursion.

Even less coding today! I'll be back at it tomorrow for certainly.

I have not hit a breakthrough on this singular function I'm trying to implement, but I think I'm close! Hoping to have something more interesting to say tomorrow, but at the very least I'm getting a much better grip on the Z combinator I've decided to base the entire language around.

The bad news is that I haven't made any interesting progress on what I've been working on, but the good news is that I found a frankly massive bug in a couple of the combinators with implications in everything I've been having trouble with lately. I very genuinely expect the outlook to be rosier going forward.

Tail-recursive functions, the easier way?

I've managed to get a more abstract way of doing recursive functions working. Really excited to play with this and to see how terribly I might be able to abuse it. But for today, I'll introduce the interface I've managed to throw together, and do an example or two.

The function I've provided is abstract-rec, and its general interface is abstract-rec cond mod-acc next-val acc val. This might seem a bit odd at first, but if you have experience with writing tail-recursive functions some of this might look familiar. Let's walk through the arguments.

• cond is the condition at which the function terminates. It is a function that takes val and returns t if the terminating condition is met, nil otherwise
• mod-acc is probably the trickiest argument, and definitely the worst-named. It takes the accumulator acc and the current value val, and returns what the next accumulator should be. I promise this might make more sense when we get to an example
• next-val takes the current value and gives the next value to be called upon. It's this language's version of procedural languages' i++ or i-- and so forth
• acc is the accumulator, which essentially keeps track of things for you
• val is the value, it's essentially the argument you pass to your desired recursive function

So with that described, let's see a nice tail-recursive factorial implementation done this way. We'll break down what each of the arguments is and how it works in this context.

• cond here is just (eq 0), which tests if something's zero or not
• mod-acc here is * which takes the current accumulator and multiplies it by the current call value val
• next-val takes the current val and subtracts one from it, getting us closer to our (eq 0) condition. Here it looks like (C - 1)
• The accumulator acc for factorial starts out as our beloved multiplicative identity, 1
• We'll leave off talking about val, as we want to use it as the argument to our factorial function. This is generally how val operates as I currently understand things

So, throwing this all together, we can define factorial as

(def myfac (abstract-rec (eq 0) * (C - 1) 1))

← myfac 6
 → 720

Let's see another example, which just counts down from whatever number you give it, but somewhat abuses the notation to do so

(def countdown (abstract-rec (eq 0) (K print) (C - 1) nil))

← countdown 10
10
9
8
7
6
5
4
3
2
1
 → t

abstract-rec is up on the git repo and up on the web repl, play around with it!

Despite the tour de force of yesterday's improvements, I don't really have much to say today. I did figure out a pretty slick and simple append with my prior work, but that wasn't really the focus of today.

Today's work is not done, but what it's been so far has been work on the online repl. Unfortunately no major user interface improvements yet (though I have some in mind), but what I am working towards is finally figuring out how to make it into a nice progressive web app that'll actually work offline. It's not done yet, but it doesn't seem to be terribly difficult, I just have to wire everything up properly and make sure it works. That said, I couldn't find a glaringly obvious minimal guide on getting a proper setup for a progressive web app with an emscripten core, so I might type one up at some point once I've got something working.

The web repl now functions as a progressive web app with a functional offline! Not the hugest thing for the language as a whole but it'll be pretty convenient for me personally at least, plus it's nice to have as an 'app' on my phone now. I definitely have to look at other web repls to find features to crib from them.

In addition to that, I figured out a couple standards, in append and filter. The filter function doesn't preserve the order of the lists as it currently stands, but otherwise works fine.

One observation I've made in coding up a bunch of things in this language is that a lot of the actual mechanical work of figuring things out in this language is just moving arguments around. In that way it does feel rather Forth-like, though as I keep developing higher-order functions it's starting to feel like more of its own thing. I continue to question the efficacy of not having plain old lambda expressions or something like that, but I'm enjoying seeing how this thing works. Also I'm beginning to realise that I've mostly relied on the B, C, S, and W combinators (beyond the ever-crucial Z), I've really gotta think about expanding my vocabulary.

Also, sort of as an fyi, you can see most of the things I've implemented and am using in the language itself in the demos file in the git repo

Not much to say today, not much was done. I'm currently playing around with implementing some more standard functions

Goodness editing code is no fun on a phone! Going through the experience made me realise most of the actual 'editing' felt more structural than text, so that's something exciting and curious to think about for the future!

Another day of phone-editing, which makes me think there's some promise for the future. I've been imagining various ways in which editing code (in this language) might otherwise be done, and I think that there might be some interesting possibilities once things are further developed. Something to keep in mind.

It's pretty fun the silly little bugs one makes and then later uncovers when working on something of this level. Today, I realised that four is not greater than four, and then made the first change in the actual backend in about a week. I also threw in a way to get a random uint as a convenience.

For xmas, I give you quicksort, eked out amidst the general festivities. I'll put it here, and more properly load it in at a less festive point in time.

← def qsort ((B Z (B (B (S (W atom))) (Phi (Phi (Phi append)) (B (C B) (C (B (Phi filter) (B (B (B not)) (C B car))) cdr)) (B (B (Phi cons car)) (B (C B) (C (B (Phi filter) (C B car)) cdr)))))))
 → _259
← qsort < (list 3 5 9 1 6 3 5 4)
 → (1 3 3 4 5 5 6 9)

In lieu of an update about code (I have none to share), I'll write about how I've been finding things lately. As far as doing everything tacitly, I'm getting better at it, and only most of the time I feel like I'm converting non-tacit code into tacit. To an extent I'm wondering why bother, but haven't been discouraged from this approach yet. Once I iron out the details I feel like I'll probably be able to work out some sort of temporary naming system one might compare with local variables. But I won't have to put it in the core of the language, I feel confident I'll be able to build it on top. I definitely feel like I've started 'editing tacitly' to some extent, which is its own feeling I'm still figuring out. I'm gonna keep at it and see if anything sticks. Still need to implement a bunch more common algorithms, and need to think about how I might do data structures too (curious how far s-expressions can get me).

I've also been thinking about taking things from other languages, been reading a lot of documentation to see what's out there. I anticipate the biggest changes to the core of the language to come might involve when and how things are evaluated. It's feeling like something that'll have to be worked out at some point. Fun stuff ahead.