undefined | Better HN

0 pointsfexl14y ago0 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:

  \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.

0 comments

3 comments · 1 top-level

chalst14y ago· 2 in thread

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.

fexlOP14y ago

(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:

  \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.

chalst14y ago

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...

j / k navigate · click thread line to collapse