7 ms·
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.c
by fexl 15y ago
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 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.
That is why I emphasized this caveat earlier today: http://news.ycombinator.com/item?id=2717560 http://news.ycombinator.com/item?id=2717560 .
- eru 15y agoHave 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.
- fexl 15y agoThanks 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: \chain = (\state \state = (event1 state) \state = (event2 state) \state = (event3 state) state) That of course is simply equivalent to: \chain = (\state event3; event2; event1; state) 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.) Then I did this bit of nastiness: \chain = (\state \state = (event1 state) eval state; \state = (event2 state) eval state; \state = (event3 state) eval state; state) 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.
- chalst 15y agoYou 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-liberated-from-the-von-neumann-paradigm/ 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.