This repository was archived by the owner on Oct 4, 2020. It is now read-only.
Repository navigation
This repository was archived by the owner on Oct 4, 2020. It is now read-only.
free-ish representation of Eff in JS #29
Description
If representation of Eff in JS runtime, was free monad-ish way, like this:
Eff a
= { tag: "effect", val0 :: Void, val1 :: Unit -> a }
| { tag: "pure", val0 :: Void, val1 :: a }
| { tag: "map", val0 :: Eff b, val1 :: b -> a }
| { tag: "apply", val0 :: Eff a, val1 :: Eff (b -> a) }
| { tag: "bind", val0 :: Eff b, val1 :: b -> Eff a } then:
exports.pureE = function (a) {
return { tag: "pure", val0: null, val1: a }
};
exports.bindE = function (a) {
return function (f) {
return { tag: "bind", val0: a, val1: f }
};
};
exports.applyE = function (f) {
return function (a) {
return { tag: "apply", val0: a, val1: f }
};
};
exports.unsafeRun = function (eff) {
// TODO: fold eff in a stack safe way.
};
exports.runPure = function (eff) {
return unsafeRun(eff)
};This will make bind stack safe by default (no need for MonadRec)
Disadvantages:
- now, one could just grab any Eff value from JS and call it, as it's represented as a function. After proposed change, one would need to require
Control/Monad/Eff.jsfirst to get reference tounsafeRunand then use it to run the Eff. - significantly complex than what we have now (not as complex as Aff's implementation as Eff is sync)
- braking change
- as there will be less functions, might be harder to debug
Advantages:
- instead of allocate new functions on common operations like map, ap, bind, pure, now you just create small objects whith same shape (so JS runtime can optimize property access).
- it could be stack safe by default.
- as Eff is a tree now might be easier to debug (like you can print it).
Activity
paf31 commentedon Dec 8, 2017
I think it would be good if you could demonstrate this approach in a repo, although I don't think it's a good default for
purescript-effnecessarily, which is supposed to be as lightweight and low-level as possible.safareli commentedon Dec 11, 2017
Here it is, it's stacksafe, and should be fast, (haven't done benchmarks, yet)
https://gist.github.com/safareli/ca3c3b066d4fe0ed5917bcdd0dcebf56
I could have made port of ps-catlist to js, but uncons might still have O(n) performance (if i understand it correctly), which would not be useful, tho having cat list with 0(1) uncons would be pretty useful (will take a look at okasaki) and will avoid need to go down to the leaf nodes in unsafeRun.
paf31 commentedon Dec 11, 2017
Looks interesting, but I'll need to study it more. Perhaps you could make a repo and package it up as a PureScript library on top of
eff. It might be very useful for certain tasks.safareli commentedon Dec 12, 2017
Currently this is what results look like:
This is how test structures are generated:
Note that generations must be tail call optimized so stack is not overflowed during generation.
Max numbers for particular test type is restricted because of
Eff, proposed implementation could handle:So now there is heap memory and time constraints only.
Right associated binds perform extremely well, my guess is that operations array is smaller in that case. I used bind based implementations of map and apply but they performed badly than normal implementation.
Need to do a bit more testing & benchmarking. but here is the code safareli/purescript-ef#1
Would love to if you can take a look.
paf31 commentedon Dec 12, 2017
I think it looks great! It would be interesting to compare it to
CoyonedaorCodensityoverEfftoo.natefaubion commentedon Dec 12, 2017
This is really cool, but just an FYI wrt minibench. You have to be sure to initiate a manual GC between each test. GC from previous runs will most definitely affect subsequent runs. I hit this problem when benching
purescript-run.safareli commentedon Dec 12, 2017
have you done similar thing somewhere, can you link that?
natefaubion commentedon Dec 12, 2017
For v8 you just call
global.gc().natefaubion commentedon Dec 12, 2017
And call node with
--expose-gc.paf31 commentedon Dec 12, 2017
GC already gets run once inside
minibench. Maybe this would make a good PR there.natefaubion commentedon Dec 12, 2017
@paf31 Maybe I was using an old version?
safareli commentedon Dec 13, 2017
Thanks! I created an initial PR if you wanna review
safareli/purescript-ef#1
safareli commentedon Dec 13, 2017
This is too fast :D
