Previous Entry Share Next Entry
Functional QL, and Recursion
device
jducoeur wrote in querki_project
[Definitely a bit esoteric today -- this stuff is intended only to be used by relatively advanced Apps and libraries, not by normal end users, but the programmers may find it fun.]

QL is, quite intentionally, a Functional programming language -- indeed, a fairly pure one, with side-effects mostly happening after the fact. As such, I've been gradually reminded of the fact that there are a lot of standard techniques that every functional language uses, and this one's not going to be an exception.

Today I went and implemented a bunch of the core ones, having realized that displaying a hierarchy of Things is a fundamentally recursive operation. Here are some of the new toys available to use.


Step one was, of course, to implement the two functions that no recursive language can live without: _first and _rest. The names change -- they were car and cdr in the old Lisp days, they're sometimes called head and tail -- but the basic concept is always the same. _first receives a collection, and produces the first element of that collection. (Technically, it returns an Optional containing that element, or None if the list was empty.) _rest receives a collection, and produces a new collection containing everything *but* the first element. (And cuts off processing if the list is empty: I realized I needed that after a few stack overflows. And yes, I now cap the stack recursion in the language. Eventually, we'll add some efficient trampolining internally, but for now the recursion limit is quite small.)

I'm sure that we'll need more functional primitives as we go along. But these are usually the heart of functional programming, especially the heart of recursive programming.


Then there is the basic notion of recursion. I confess, I started out the day asking myself, "does recursion just *work*, with no changes?", and was slightly disappointed to find that the answer wasn't quite yes. But it didn't take much to add it. The trickiest bit, actually, was the realization of the way that recursion interacts with context.

Remember that Querki is designed as a data-processing language -- each Stage receives an incoming context, alters it, and produces an outgoing context. And each Stage is treated as basically a function call applied to the incoming context.

So my first attempt at a recursive function was on object Recursion Text, on which I declared a QL Property (a method, essentially) named Recursive Function:
""[[_first]]
{{addLeft:
[[_rest -> Recursive Function]]
}}""
(addLeft is a style that simply indents by 20 pixels -- a nice easy way to see recursion visibly.) That gave an error (threw an exception, actually), and I was initially mystified, until I realized that the issue was context -- it was trying to invoke the property "Recursive Function" on the *list*, rather than on the defining object where it actually lived.

That was a little disappointing, but is, at least, consistent. After introducing a more graceful (and useful) error message when this happens, I expanded the concept of "partial application", which had already existed for many methods. Normally, you fetch a Property like this:
[[My Thing -> My Property]]
This fetches the value of My Property on My Thing, and produces that as the new context. Which is great -- unless you want to do something else with that Property, not just return its value. That's exactly the case in a QL Function: I want to fetch the "script" (from Thing A), and apply it to a potentially *completely unrelated* context.

So I enhanced the syntax to allow what seems like the obvious way to call this:
[[... Incoming -> My Thing.My Property -> ... Produced]]
This fetches the value of "My Property", applies it to the Incoming context, to result in the Produced context. This isn't actually *useful* for anything other than QL properties yet, but it won't surprise me at all to find that there are lots of other potential uses.


So my example had now become:
""[[_first]]
{{addLeft:
[[_rest -> RecursionText.Recursive Function]]
}}""
That now worked -- but oddly, didn't indent anything! That was mysterious, and all the moreso when I found that there was an addLeft section *after* each element in the resulting output. Weird.

It took me a fair while to puzzle out why, and once again it was because I'm trying to do something weird here, rather than acting as Querki prefers. As I've mentioned before, Querki is optimized for the most common case, where you want to do something to each *element* in the incoming collection, then stitch them back together -- basically, the "->" operator is roughly what is called "map" in many languages. So that QLText Stage that makes up my function was being applied *individually* to each element in the list, not to the list as a whole. Humph.

I spent a good two hours pondering this one, before deciding that, yes, this is Querki working exactly as designed. Moreover, I still think it's the correct design most of the time -- the problem I'm wrestling with here is the advanced edge case. So there was nothing for it but to add something new to make this edge case work.

Hence, I added the "*" operator. You can apply this before any Stage; it means exactly "treat the incoming context as a Collection, rather than mapping it to individual elements". I already had that concept in the system -- many of the primitive functions needed to be able to do this implicitly -- but I hadn't exposed it to the user. I shouldn't be surprised that I would need to do so soon, if I'm going to make the QL language adequately powerful.


After implementing that, I now had:
* ""[[_first]]
{{addLeft:
[[_rest -> RecursionText.Recursive Function]]
}}""
And lo and behold, it works!

Just to check, though, I decided to see whether a simple recursive *function* would work even better.

I've mentioned before that each Stage is basically a function call -- we take the given name, resolve that to a Thing, and call _apply() on that. _apply() on a Property returns the value of that Property (by default); _apply() on a Thing returns a link to that Thing (by default). But I recently added the ability to explicitly define _apply for any Thing. _apply contains a QL Phrase, so if you define it, you're essentially declaring that this Thing is a function that you can just call by naming it.

So I added a new Thing named "Lefting", whose _apply is simply:
* ""[[_first]]
{{addLeft:
[[_rest -> Lefting]]
}}""
And that works exactly as intended -- you can call it on any List, and it will display it with each element indented a little further. There's no need for the dot syntax of the original version, because the name "Lefting" pulls up that QL phrase automatically.


There's a *long* ways to go here, of course. I've just begun to scratch the surface of the libraries that we'll need for effective functional programming, and I can't say that I adore the "*" operator. But today was one of those very encouraging days: for all that I had to spent several hours tweaking, enhancing and debugging, the truth is that "several hours" is pretty damned fast when it comes to comes to building a new language. And the end result isn't half-bad. It's -- well, quirky, as usual -- but it's very consistent with the way the rest of the system works, so hopefully it won't be too opaque for folks if they advance to this level of programming in the system. Indeed, I'm taking a little pride in it: I'm not sure I know any other template languages that do this sort of thing any better...
Tags:

  • 1
Yeah, that's going to add a lot of data processing muscle in the right cases.

  • 1
?

Log in

No account? Create an account