search

carp-lang / Carp

A statically typed lisp, without a GC, for real-time applications.
Apache License 2.0
5.53k stars 178 forks source link

Evaluation using `Traversable` #1083

Open jacereda opened 3 years ago

jacereda commented 3 years ago

I thought I might raise this issue to discuss the possibility of evaluating via Traversable.

One of the stumbling blocks I found is the Sets we have in the AST. Normal Data.Set isn't Traversable because it has Ord restrictions.

I found https://github.com/giorgidze/set-monad but it doesn't have Traversable. I have PR'd https://github.com/giorgidze/set-monad/pull/10

Maybe there're other alternatives. I guess we could implement a simplified Set without Ord restriction. Since our sets will be quite small I guess something like that could be implemented on top of List without being too inefficient.

jacereda commented 3 years ago

Of course we could implement manually traverse on our AST, but I thought an automatic instance based on Generic would be more desirable.

eriksvedang commented 3 years ago

This sounds interesting indeed! What would be a good module to first try out this approach?

jacereda commented 3 years ago

You mean if it should be Eval or Expand? I guess the second is simpler...

jacereda commented 3 years ago

Oh, instead of Generic we could also use https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#extension-DeriveTraversable

eriksvedang commented 3 years ago

Oh, maybe those are the only ones... :)

guess the second is simpler

Yes it must be

jacereda commented 3 years ago

I guess Scoring is a fold. Not sure about Emit, could it also be a fold?

And looking at more modules, looks like most of them could benefit from Foldable and/or Traversable.

scolsen commented 3 years ago

I guess Scoring is a fold. Not sure about Emit, could it also be a fold?

And looking at more modules, looks like most of them could benefit from Foldable and/or Traversable.

Yes, pretty much everything, I think, can be expressed in terms of a fold over the AST

eriksvedang commented 3 years ago

Some of the recursive functions branch in weird ways though - concretize & manageMemory comes to mind. Perhaps it's still possible to just fold, but I'm not sure.