[Haskell-cafe] sharing

[Tom Schouten]

On 2/5/20 8:17 AM, Carter Schonwald wrote:
>
> Have you looked at how stuff like the ivory/tower edsl libraries do 
> their embedding?
>
That is a nice project! Thanks for pointing it out.

For Ivory, the embedding is monadic so not any different in that 
respect, and this is also much more expressive than what I need.


I guess I don't know what exactly I don't know...

I'm doing something quite straightforward. Basically I know that the 
language I'm embedding only has pure functions mapping pairs of 
sequences to pairs of sequences with the restriction that the mapping is 
causal when you look at individual elements in a stream, but I dont' 
think this fact is even observable after abstracting to streams.

Keeping track of the sharing information necessary to be able to compile 
it to an external target introduces an effect.  But this is the _only_ 
effect, and it is an implementation detail that makes me loose all the 
nice properties of pure functions.  That just feels wrong.  I'm sure I'm 
missing something.

I believe the core issue is that I'm not understanding something quite 
fundamental. Why is it so hard to recover sharing information if the 
thing that is embedded is pure? I suspect the answer is something 
something referential transparency but how exactly?


This is what I sort of understand:

- Compiling to categories fixes the problem completely using a big gun: 
abstracting over function abstraction and application. It's great, but 
can't be done in Haskell as is.  This is probably the cleanest solution. 
I suspect this also has the answer to my question above but I don't 
quite see it.

- There is another Functional HDL that solves this using some unsafe 
reference trick to keep track of the sharing. I believe it is CλaSH but 
I'm not sure. I believe you can get away with this because the semantics 
is pure so in practice doesn't cause any inconsistencies, but it really 
doesn't sound like something I would do without some kind of proof that 
it is actually ok. If it is ok, it would probably make sense to abstract 
this in a library. Maybe someone has done that already?

- You can try to recover sharing later by doing common subexpression 
elimination. This works but has complexity issues and doesn't scale to 
large systems.

- Maybe it is possible to hide the compiler using existential types. I 
tried something along these lines but I couldn't figure it out so I 
don't know if it's just lack of insight or just impossible. Probably the 
latter.







-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20200205/a7570885/attachment.html>