Thanks for the tip -- I do see something in Haskell about marking things as strict. Perhaps I can do something similar in Fexl. The general problem I'm dealing with is long chains of state transformations like this:
But the former is a way of showing the computation in a forward instead of reverse direction. And I know I could rephrase the former in a monadic style, but that in itself does not alleviate the problem of the lazy evaluation.
This certainly does not matter if you're just chaining three events together, but try linking that chain together 20000 times to give you 60000 events. Oh it works, but it's nasty with memory usage.
So maybe I can introduce something into Fexl, without sacrificing elegance, which forces some level of evaluation of the event applications.
I did try forcing at least a top-level evaluation of each event along the way, using a technique sort of like this:
\eval = (\state state I \_\_ I)
(That's because I know the state is ultimately just a list. I have a really efficient way of doing arbitrarily large key-value maps simply using nested lists in just a few lines of Fexl.)
But I dunno, it still didn't quite do the trick. The jury's still out. So far for most "real work" I'm still just using embedded simple token-based domain-specific concatenative languages, with the enclosing interpreter written in either ANSI C or Perl. Fexl is still mostly a lab toy.
You can control the order of execution of pure functions by using CPS (so strict can be represented by lazy or vice versa). You can't force monadic operations to occur out of order this way: you need to have some concurrency between the pure expansion semantics and the action semantics.
So why can't you interleave the add operations? Are the atomic arithmetic operations side effects? Can you not represent CPS faithfully for some reason? I'd really like to see the expansion phase of Fexl expressed using CPS.
BTW, borrow a notation from Haskell and have a dot operator be the transpose of the semicolon operator.
In short, when you evaluate (long_add 2 3), that value is replaced with the number 5, right inside the machine data structure. So in that sense there is a "side effect", but it's a purely functional referentially transparent side effect only in the C internals -- nothing mutable going on at the Fexl level.
I'm all well-versed with CPS (continuation-passing style), e.g. I've done stuff like this:
\do_stuff = (\state\return
do_this state \state
do_that state \state
return state)
But that doesn't in itself help me, yet.
By swapping the order of the parameters "state" and "return" in do_stuff, do_this, and do_that, I can transform that function into a monadic style:
\do_stuff = (\return
do_this;
do_that;
return)
But as it turns out that accomplishes nothing essential -- it is merely a syntactic difference.
Keep in mind that Fexl is purely combinatorial, and ultimately what's really going on under the hood are the application of these two rules:
C x y = x
S x y z = x z; y z
So maybe that will give you some insight into just how irredeemably lazy this language really is. :)
(Yes there are some other combinators such as I, L, R, and Y, but these are ultimately shorthands for S and C forms.)
If by "interleave the add operations" you are suggesting a change to the core evaluation strategy used in the interpreter, that is probably out of the question -- I've made my bed there and I have to lie in it. There's not much I can do at this point about my reliance on combinators, I mean, check out the S combinator: https://github.com/chkoreff/Fexl/blob/master/src/S.c . That's baked in the cake!
But if you mean there's something I can do different in my Fexl function itself, that might be something to consider.
I tried the full gamut here, using both accumulator and CPS:
\test_big_sum_4 =
(
\sum == (\N \total \return
long_le N 0
(return total)
(sum (long_sub N 1) (long_add total N) return)
)
# TODO still a problem!!
\N = 100000
sum N 0 \total
print "sum 1 .. "; print N; print " is "; print total;nl;
)
test_big_sum_4
But to no avail: it still uses up large amounts of memory.
However, I could force the evaluation of (long_sub N 1) and (long_add total N), and that might do the trick. Then it'll be totally tail recursive with machine integers at every turn, and run in constant memory.
I'm talking about a particular application of CPS, the encoding of CBV lambda-calculus in the CBN calculus. Checkout Danvy & Filinksi (1992) if you need brushing up on this: look at what happens in your calculus when you code up the CBV version of the foldl, which should force the first atomic operation to happen before unwinding the next application of addition.
Comments
Thanks for the tip -- I do see something in Haskell about marking things as strict. Perhaps I can do something similar in Fexl. The general problem I'm dealing with is long chains of state transformations like this:
That of course is simply equivalent to: But the former is a way of showing the computation in a forward instead of reverse direction. And I know I could rephrase the former in a monadic style, but that in itself does not alleviate the problem of the lazy evaluation.This certainly does not matter if you're just chaining three events together, but try linking that chain together 20000 times to give you 60000 events. Oh it works, but it's nasty with memory usage.
So maybe I can introduce something into Fexl, without sacrificing elegance, which forces some level of evaluation of the event applications.
I did try forcing at least a top-level evaluation of each event along the way, using a technique sort of like this:
(That's because I know the state is ultimately just a list. I have a really efficient way of doing arbitrarily large key-value maps simply using nested lists in just a few lines of Fexl.)Then I did this bit of nastiness:
But I dunno, it still didn't quite do the trick. The jury's still out. So far for most "real work" I'm still just using embedded simple token-based domain-specific concatenative languages, with the enclosing interpreter written in either ANSI C or Perl. Fexl is still mostly a lab toy.You can control the order of execution of pure functions by using CPS (so strict can be represented by lazy or vice versa). You can't force monadic operations to occur out of order this way: you need to have some concurrency between the pure expansion semantics and the action semantics.
Conal Elliot has written some nice things in this vein; he makes a relevant point in http://conal.net/blog/posts/can-functional-programming-be-li...
So why can't you interleave the add operations? Are the atomic arithmetic operations side effects? Can you not represent CPS faithfully for some reason? I'd really like to see the expansion phase of Fexl expressed using CPS.
BTW, borrow a notation from Haskell and have a dot operator be the transpose of the semicolon operator.
(Intriguing suggestion about the dot operator by the way.)
On this question: "Are the atomic arithmetic operations side effects?" Not really. Well, sort of. I mean, take a look at the reduction code for adding two long values: https://github.com/chkoreff/Fexl/blob/master/src/long_add.c
In short, when you evaluate (long_add 2 3), that value is replaced with the number 5, right inside the machine data structure. So in that sense there is a "side effect", but it's a purely functional referentially transparent side effect only in the C internals -- nothing mutable going on at the Fexl level.
I'm all well-versed with CPS (continuation-passing style), e.g. I've done stuff like this:
But that doesn't in itself help me, yet.By swapping the order of the parameters "state" and "return" in do_stuff, do_this, and do_that, I can transform that function into a monadic style:
But as it turns out that accomplishes nothing essential -- it is merely a syntactic difference.Keep in mind that Fexl is purely combinatorial, and ultimately what's really going on under the hood are the application of these two rules:
So maybe that will give you some insight into just how irredeemably lazy this language really is. :)(Yes there are some other combinators such as I, L, R, and Y, but these are ultimately shorthands for S and C forms.)
If by "interleave the add operations" you are suggesting a change to the core evaluation strategy used in the interpreter, that is probably out of the question -- I've made my bed there and I have to lie in it. There's not much I can do at this point about my reliance on combinators, I mean, check out the S combinator: https://github.com/chkoreff/Fexl/blob/master/src/S.c . That's baked in the cake!
But if you mean there's something I can do different in my Fexl function itself, that might be something to consider.
I tried the full gamut here, using both accumulator and CPS:
But to no avail: it still uses up large amounts of memory.However, I could force the evaluation of (long_sub N 1) and (long_add total N), and that might do the trick. Then it'll be totally tail recursive with machine integers at every turn, and run in constant memory.
I'm all well-versed with CPS
I'm talking about a particular application of CPS, the encoding of CBV lambda-calculus in the CBN calculus. Checkout Danvy & Filinksi (1992) if you need brushing up on this: look at what happens in your calculus when you code up the CBV version of the foldl, which should force the first atomic operation to happen before unwinding the next application of addition.
Danvy & Filinksi, 1992, Representing control: a study of the CPS transformation http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.8...