Ah, thanks for posting about my Fexl language. Although I'm the author of it, and somewhat fond of it, I must emphasize this caveat: http://news.ycombinator.com/item?id=2717560 .
Although lazy evaluation is quite amazing, in certain circumstances I find that it's kicking my ass. For example, consider a function that simply sums the numbers from 1 to N:
\sum == (\N
long_le N 0
0
(long_add N (sum (long_sub N 1)))
)
Or, more tersely, using the semicolon as a syntactic "pivot" to avoid right-nesting:
\sum == (\N long_le N 0 0; long_add N; sum; long_sub N 1)
The problem is that when you call (sum 100000) it builds up a giant chain of (long_add 100000; long_add 99999; long_add 99998; ...) and then evaluates that monstrosity recursively.
So I need to do some more work on forcing early evaluation. You can start by using the standard accumulator trick:
\sum == (\total\N
long_le N 0
total
(sum (long_add total N) (long_sub N 1))
)
\sum = (sum 0)
But even then you still have the massive recursion problem because you're not forcing the addition operation early.
I'm thinking I just need to allow basic types like "long" to be called as functions with no effect (i.e. equivalent to the identity function, so you can do things like this:
\sum == (\total\N
long_le N 0
total
(
\total = (long_add total N)
total; # force evaluation; result is I (identity function)
sum total (long_sub N 1)
)
)
However, even that doesn't always do the trick, particularly when you're dealing with higher-level values that aren't basic data types. The problem occurs generally when you build up a big "chain" of calculations with arbitrary values, and you have no simple way of forcing evaluation along the way.
This is, of course, the classic struggle between eager and lazy evaluation. But if I don't do the evaluation lazily, I can't define recursion in terms of the closed-form Y combinator, namely (Y F) = (F (Y F)). Instead I'd have to define it in terms of some kind of run-time "environment" using either key-value pairs or the de Bruijn positional technique -- something I've managed to avoid thanks to lazy evaluation in terms of pure combinators.
So I must say that although Fexl is an interesting pure-combinator lazy evaluation language, the jury is still out on its practical utility, in my humble opinion. I've used it in some projects as an embedded interpreter, but the application was quite constricted so you didn't encounter some of these larger issues.
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.
the discussion of side effects on that page is confusing. all you seem to be saying is that any function can be redefined. you do not need to mention side-effects to say that. it is confusing because anyone reading who knows about functional programming is going to see mention of "side effects" and "print" and expect some kind of discussion related to the problems that monads in haskell address (that you can change and examine state in the file system).
also, you should explicitly say somewhere that it is eager (not lazy) (if it is).
also, i couldn't find any discussion of whether it is possible to mutate state (i assume not, but you don't say). related, a table of contents would be a big help - and obvious initial question is "how are data structures handled?" and you don't know where to find the answer when you at the top of the page.
(this is not meant to say that your language is bad - i am just trying to help you "sell" you language to people that read your page!)
Yes, I do need to update things there. I mentioned redefinition in the context of side-effects because I wanted to emphasize that you could isolate a Fexl function in a safe "sandbox" so you could prevent users from calling "print" or "unlink" directly, or even substitute a simulated file system so they can call "unlink" safely. But you're right, they are two separate issues.
On your second point, Fexl is definitely not eager. It is the laziest thing you'll ever see.
And no, you cannot mutate state in any way.
On the subject of "how are data structures handled", I do address that at the top in "RULE 1: Everything is a function." There I say that all data are represented as functions, and I do show a little link to some exposition below.
Thanks for the help on "selling" the language -- until now, I haven't been concerned about that because it's all for my own purposes. But I take your point.
Comments
Ah, thanks for posting about my Fexl language. Although I'm the author of it, and somewhat fond of it, I must emphasize this caveat: http://news.ycombinator.com/item?id=2717560 .
Although lazy evaluation is quite amazing, in certain circumstances I find that it's kicking my ass. For example, consider a function that simply sums the numbers from 1 to N:
Or, more tersely, using the semicolon as a syntactic "pivot" to avoid right-nesting: The problem is that when you call (sum 100000) it builds up a giant chain of (long_add 100000; long_add 99999; long_add 99998; ...) and then evaluates that monstrosity recursively.So I need to do some more work on forcing early evaluation. You can start by using the standard accumulator trick:
But even then you still have the massive recursion problem because you're not forcing the addition operation early.I'm thinking I just need to allow basic types like "long" to be called as functions with no effect (i.e. equivalent to the identity function, so you can do things like this:
However, even that doesn't always do the trick, particularly when you're dealing with higher-level values that aren't basic data types. The problem occurs generally when you build up a big "chain" of calculations with arbitrary values, and you have no simple way of forcing evaluation along the way.This is, of course, the classic struggle between eager and lazy evaluation. But if I don't do the evaluation lazily, I can't define recursion in terms of the closed-form Y combinator, namely (Y F) = (F (Y F)). Instead I'd have to define it in terms of some kind of run-time "environment" using either key-value pairs or the de Bruijn positional technique -- something I've managed to avoid thanks to lazy evaluation in terms of pure combinators.
So I must say that although Fexl is an interesting pure-combinator lazy evaluation language, the jury is still out on its practical utility, in my humble opinion. I've used it in some projects as an embedded interpreter, but the application was quite constricted so you didn't encounter some of these larger issues.
That is why I emphasized this caveat earlier today: http://news.ycombinator.com/item?id=2717560 .
Have you looked at how people deal with too much lazyness in Haskell? If yes, is it applicable to your language? Why, why not?
In your example I'd use foldl' (the prime is important) in Haskell for a strict sum.
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...
the discussion of side effects on that page is confusing. all you seem to be saying is that any function can be redefined. you do not need to mention side-effects to say that. it is confusing because anyone reading who knows about functional programming is going to see mention of "side effects" and "print" and expect some kind of discussion related to the problems that monads in haskell address (that you can change and examine state in the file system).
also, you should explicitly say somewhere that it is eager (not lazy) (if it is).
also, i couldn't find any discussion of whether it is possible to mutate state (i assume not, but you don't say). related, a table of contents would be a big help - and obvious initial question is "how are data structures handled?" and you don't know where to find the answer when you at the top of the page.
(this is not meant to say that your language is bad - i am just trying to help you "sell" you language to people that read your page!)
Yes, I do need to update things there. I mentioned redefinition in the context of side-effects because I wanted to emphasize that you could isolate a Fexl function in a safe "sandbox" so you could prevent users from calling "print" or "unlink" directly, or even substitute a simulated file system so they can call "unlink" safely. But you're right, they are two separate issues.
On your second point, Fexl is definitely not eager. It is the laziest thing you'll ever see.
And no, you cannot mutate state in any way.
On the subject of "how are data structures handled", I do address that at the top in "RULE 1: Everything is a function." There I say that all data are represented as functions, and I do show a little link to some exposition below.
Thanks for the help on "selling" the language -- until now, I haven't been concerned about that because it's all for my own purposes. But I take your point.
In general, I've found explicit lazy evaluation much easier to deal with, such as Python or Clojure. It is potentially less powerful, however.
Btw, interesting language, this Flex of yours.
Thanks -- small typo though, it's actually "Fexl" (pronounced sort of like "pixel").
Ah, yes. Sorry.