Author Topic: Lazy Evaluation in Axe  (Read 1421 times)

0 Members and 1 Guest are viewing this topic.

Ashbad

  • Guest
Lazy Evaluation in Axe
« on: July 18, 2011, 01:47:48 pm »
Well, I decided that after writing the new edition of my functional programming tutorial, I needed to come up with something to occupy myself with at work concerning Axe coding.  So, I decided to try and see if I could implement lazy-evaluated Enumerable types into Axe 1.0.0.  And, so I did.  And I would like to share it, because it involves a cool use of functional programming concepts such as lambdas and non-explicit calling of functions, and passing functions as arguments.  Here is what I came up with.

First off, lazy evaluation is simply when you create an "array" of numbers in a consecutive range that would be normally very large, but is stored in a way that the array is very, very compacted.  For all examples in this informative thread, I'll be using a very, very simple lazy evaluated Enumerable, with 8 bit elements, the starting one being 1, the ending one being 100, and a 8 bit step value of 1.  Here is the layout so far of our enum, in bytes:

0: starting element
1: ending element
2: range step

So, that's three bytes.  Here's what it would be to do the same, non-compacted:

0: element 1
1: element 2
2: element 3
3: element 4
...
99: element 100

So, 3 totally beats 100 bytes.  This is a trivial example, since this is a really simple layout for the range, since it only uses a range step to determine the values of contained elements.  It's also not that big of a space saver since it's only 3 versus 100 bytes; though imagine doing the same with 16 bit values, though with 1 to 10000, which would be 6 to 10000 bytes.  Again, trivial because of a small step, but think about if you made a complex one with a lexical range of strings :-)

How do we access an element from this Enumerable?  Here's a simple solution that pertains to our example enum:

Code: [Select]
Lbl AE
  r2*{r1+2}+{r1}->r3<={r1+2}?,-1
Return

Takes pointer to enum instance in r1, and element to access in r2. To keep it simple it only works with positive ranges.  Here is a call to this:

Code: [Select]
1->{L1}->{L1+2}
100->{L1+1}

AE(L1,30)

Returns 31, the 30th element in the enum, since we start at 1.

Up until now, we've been working with plain old Enumerables.  Now let's get into our part of the equation where the "lazy" takes place.  In lazy evaluation, we can apply a rule to an Enumerable so that every element is mapped to the rule.  With a normal routine we can use a normal map(), but with Enumerables, it is quite different.  This is where we start attaching lambdas to part of the Enumerable so that it can apply the rule given when an element is returned.  Our new enum:

0: first element
1: second element
2: range step
3-4: rule

So, we're up to 5 bytes, but this is totally worth it.  See, here's what we can do.  we can now apply a mathematical equation to every element like in mapping, such as element**2, but we don't even have to call this equation until we actually access the element.  I'll start by allocating the enum struct, but this time with a lambda'd rule:

Code: [Select]
1->{L1}->{L1+2}
100->{L1+1}
λ(r1*r1)->{L1+3}r

This rule is now considered applied to the entire enumeration and its elements.  Here is our new calling method:

Code: [Select]
Lbl AE
  r2*{r1+2}+{r1}->r3<={r1+2}?({r1+3}r)(r3),-1
Return

This will now apply the rule at accessing time.  The rule can also be changed at any time trivially, which is also really cool.  Here is the same call as earlier:

Code: [Select]
AE(L1,5)
Returns 25.  The applied rule now is in effect so that when an element is accessed, it is squared.

Why did I share this?  I thought it was a cool use of lambdas, which many people were wondering about how they could be used.  Here is just one of a million examples.  You can even edit the routines here to work with 16 bit numbers, passed functions, multiple passed or attached functions, Enumerables nested into Enumerables, etc.

God do I love 1.0.0.

Also, keep this in mind for my post tomorrow on how to hackishly attempt OOP in Axe.  Our example Enumerable is the star of the show ;)
« Last Edit: July 18, 2011, 02:26:23 pm by Ashbad »