To imitate algebraic effects with an procedural, interpreted language

[complyue]

I'd like to have your comment about how much I can imitate algebraic effects with an imperative, interpreted language.

Currently in my mind is a perform keyword, prefixing to an expression, so if I resolve function (or procedure, more precise for a procedural language) calls in it, against the call stack, instead of the lexical context of the direct enclosing function/procedure, I kinda feel it implements a sort of algebraic effect call, given the language having pattern matching feature for a calling-site, to dispatch or propagate (to outer frames on the call stack) the effect call.

What's your comment about this idea?

[matijapretnar]

I do not fully understand what you are proposing - just effect calls or also their handling? When handling, how are you delimiting and resuming the continuation? Also, are you considering multi-shot continuations (where you resume them more than once?)

[complyue]

Thanks for your attention and sorry I was vague.

I have had a little further discussion at https://www.reddit.com/r/ProgrammingLanguages/comments/gmhr8a/dynamic_effects_system/ , and come up with a prototyping implementation with my procedural dynamic language Edh, the idea can be technically demonstrated with this repl session log:

Đ: 
Đ: export mattersLot = Symbol('mattersLot')
mattersLot
Đ: 
Đ: {
Đ|  1: 
Đ|  2:   method effectsConsumer (data) {
Đ|  3: 
Đ|  4:     # put 'dataType' into current procedure scope
Đ|  5:     dataType = type(data)
Đ|  6: 
Đ|  7:     # put 'dataType' into effect namespace, 
Đ|  8:     # so a called effect method can pull it by `behave`,
Đ|  9:     # kinda like a callback mechanism but for effects
Đ| 10:     effect dataType = dataType
Đ| 11: 
Đ| 12:     # `perform` pulls out an effect method (could be other values as well),
Đ| 13:     # from effect namespace
Đ| 14:     perform @mattersLot
Đ| 15:       # then we call it from here, just like a vanilla procedure
Đ| 16:       ('the data is of ' ++ dataType)
Đ| 17: 
Đ| 18:   }
Đ| 19: 
Đ| 20: 
Đ| 21:   method effectsStaker () {
Đ| 22: 
Đ| 23:     # define an effect method into effect namespace
Đ| 24:     effect method @mattersLot(msg) {
Đ| 25:       console.print( 'It matters a lot: ' ++ msg )
Đ| 26: 
Đ| 27:       # `behave` can pull effects (either methods or other values) from
Đ| 28:       # the effect caller, while `perform` can only pull effects from 
Đ| 29:       # outer stack relative to where the effect method is defined
Đ| 30:       console.print( 'No doubt the data is of ' ++ behave dataType )
Đ| 31:     }
Đ| 32:     # now we have the effect procedure in context
Đ| 33: 
Đ| 34:     # call some procedures make use of the effects
Đ| 35:     # something like `effectsConsumer` should really be imported from
Đ| 36:     # some library modules in real cases
Đ| 37:     effectsConsumer(3)
Đ| 38:     effectsConsumer(Symbol('awesome'))
Đ| 39: 
Đ| 40:   }
Đ| 41: 
Đ| 42: }
effectsStaker
Đ: 
Đ: effectsStaker()
It matters a lot: the data is of DecimalType
No doubt the data is of DecimalType
It matters a lot: the data is of SymbolType
No doubt the data is of SymbolType
Đ: 

Seems I chose direct call instead of continuation passing in this implementation, and after these work, I some how start feeling this implementation a free-form callback mechanism as in traditional imperative languages like JavaScript/Python etc, i.e. callback functions are not passed as explicit arguments, but reside within the call stack context.

I haven't decided whether to try a continuation passing implementation as well. My ideas so far with this implementation regarding the interesting concerns:

delimiting and resuming the continuation

Currently it carries alway-resume semantic. In this implementation, effectful procedures are still vanilla procedures, so to discontinue the effect caller's execution, an effect handler procedure can throw an exception of specific type, to be caught at the same stack frame where it's defined, or at other frames as appropriate. This construct greatly lacks the elegance where exception handling get implemented as an effect, but pragmatically works at least.

multi-shot continuations

Yet I'm going to leverage some other established constructs instead of implement it as an effect. Edh has a goroutine like construct atop GHC's lightweight threads, and event sink for broadcast channel.

An effect-handler controlled multi-shot may work like this:

effect generator liveNodes() {
  # a producer procedure is always forked to run in a separate thread
  # per-called, but held from starting until its outlet is subscribed,
  # e.g. looped against by a for-loop
  producer checkNodes(outlet) {
    # mark end-of-stream anyway this producer procedure terminates,
    # this also terminate any for-loop against the sink `outlet`
    defer outlet <- nil  

    # contact each known node, this should really be dynamically
    # determined, but hard-coded here for simplicity of demo
    go {
      contactNode(1)
      outlet <- 1
    }
    go {
      contactNode(2)
      outlet <- 2
    }
    go {
      contactNode(3)
      outlet <- 3
    }

    # wait 3 seconds as for a timeout constraint
    for _ from console.everySeconds(3) do { break }
  }

  # iterate node# of each node responded in time
  # here the direct return value of the `checkNodes` producer procedure call,
  # is the event sink as its outlet, and can be looped against by this for loop
  for nodeNum from checkNodes() do yield nodeNum
}

# real jobs done in forked threads, this method will return immediately
method announceLiveMsg(msg) {
  go for nodeNum from perform liveNodes() do
    console.print('Announcing ' ++ msg ++ ' to node #' ++ nodeNum)
  }
}

An effect-caller controlled multi-shot may work like this:

effect generator knownNodes() {
  # this should really be dynamically determined, but hard-coded
  # here for simplicity of demo
  yield 1
  yield 2
  yield 3
}

# real jobs done in forked threads, this method will return immediately
method announceLiveMsg(msg) {
  in'time = true
  method annToNode(nodeNum) {
    contactNode(nodeNum)
    not in'time -> { pass }
    console.print('Announcing ' ++ msg ++ ' to node #' ++ nodeNum)
  }
  for nodeNum from perform knownNodes() do
    go annToNode(nodeNum)
  # use 3 seconds as for a timeout constraint
  go for _ from console.everySeconds(3) do { in'time = false; break }
}

Do you think this implementation can be called an algegraic effects system or should have another name?

[matijapretnar]

I may be missing something, but what you are suggesting does not seem algebraic. The first example looks like very much like dynamic binding, and the second one relies on coroutines. Both of these are features that handlers can simulate, but are not equivalent to it (e.g. it is missing full control over the continuation).

[complyue]

Yes, Edh is an imperative procedural language no way to support continuation (though Edh runtime interpreter itself is written heavy in continuation passing style Haskell), but wrt algebraic effects I still see some sorta similarities there.

I implemented Eff's better_state example:

let better_state initial = handler
  | y -> (fun s -> (y, s))
  | effect Get k -> (fun s -> (continue k s) s)
  | effect (Set s') k -> (fun _ -> (continue k ()) s')
  | finally f -> f initial
;;

with better_state 30 handle
  let x = perform Get in
  perform (Set (2 * x));
  perform Get + 10
;;

in Edh:

Đ: {
Đ|  1:   # convention: retrieve the state which is an int
Đ|  2:   Get = Symbol('Get')
Đ|  3:   # convention: set the state, should be an int
Đ|  4:   Set = Symbol('Set')
Đ|  5: 
Đ|  6:   method better_state (initial) {
Đ|  7:     # this anonymous class procedure constructs an object instance,
Đ|  8:     # serving as the state storage
Đ|  9:     # the magic method __init__ receives construction args
Đ| 10:     class _ method __init__ (act) {
Đ| 11:       this.s = initial
Đ| 12:       effect method @Get () this.s
Đ| 13:       effect method @Set (s') this.s = s'
Đ| 14:       return (act(), this.s)
Đ| 15:     }
Đ| 16:   }
Đ| 17: 
Đ| 18:   better_state (30) (
Đ| 19:     # this nullary procedure simulates a niladic computation
Đ| 20:     {method _ () {
Đ| 21: 
Đ| 22:       let x = perform @Get ()
Đ| 23:       perform @Set (2 * x)
Đ| 24:       perform @Get () + 10
Đ| 25: 
Đ| 26:     }}
Đ| 27:   )
Đ| 28: }
( 70, 60, )
Đ: 

Do you feel some similarity?

[complyue]

I'm not sure how finally would work in Eff, here's Edh's version:

Đ: {
Đ|  1:   # convention: retrieve the state which is an int
Đ|  2:   Get = Symbol('Get')
Đ|  3:   # convention: set the state, should be an int
Đ|  4:   Set = Symbol('Set')
Đ|  5: 
Đ|  6:   generator better_state (initial) {
Đ|  7:     yield {
Đ|  8:       # this anonymous class procedure constructs an object instance,
Đ|  9:       # serving as the state storage
Đ| 10:       # the magic method __init__ receives construction args
Đ| 11:       class _ method __init__ (act) {
Đ| 12:         this.s = initial
Đ| 13:         effect method @Get () this.s
Đ| 14:         effect method @Set (s') this.s = s'
Đ| 15:         return (act(), this.s)
Đ| 16:       }
Đ| 17:     }
Đ| 18:     return initial
Đ| 19:   }
Đ| 20: 
Đ| 21:   final'result = for handler from better_state (30) do 
Đ| 22:     block'result = handler (
Đ| 23:     # this anonymous nullary procedure simulates a niladic computation
Đ| 24:     {method _ () {
Đ| 25: 
Đ| 26:       let x = perform @Get ()
Đ| 27:       perform @Set (2 * x)
Đ| 28:       perform @Get () + 10
Đ| 29: 
Đ| 30:     }}
Đ| 31:   )
Đ| 32: 
Đ| 33:   console.print(final'result=final'result, block'result=block'result)
Đ| 34: }
  block'result=( 70, 60, )
  final'result=30
Đ: 

[matijapretnar]

There is similarity in the fact that they both dynamically bind Get and Set to state-manipulating functions, but they are different in how they do it. Eff uses handlers to replace Get and Set with higher-order functions that pass around the state as a parameter, whereas Edh binds them to object accessors. Both can simulate state, but are fundamentally different. You can consider more examples which interact with the continuation in a more involved way - for example try to simulate non-deterministic or probabilistic choice handlers and see if you can get a similar program there.

[complyue]

You are right, just a tiny bit I would like to clarify:

Edh binds them to object accessors

Not to object accessors actually, perform will search the call stack, check presence of the designated (alphanumeric or symbolic) key in each frame's scope until the first hit. No object semantics involved during resolution of effects.

[matijapretnar]

I phrased that badly. I meant accessing properties of an object. If I understand correctly, in this.s and this.s = s', this is an object and s is its property? The search of the call stack searches for Get and Set symbols whereas the s property is bound to the object?

[complyue]

Um, yes, you are totally correct.

Then I understand you better now, agree on all you said about the differences.

I understand algebraic effects is the classic in delimiting impure operations from pure computations, and works with powerful type systems pretty well.

Then I still think my implementation differentiate itself from traditional imperative procedural languages, like Python/JavaScript/Go, but I can't think of a better name for it, maybe dynamic scoping via effects identifiers ?

[complyue]

In a sense I'd say: effect tracking by composing Monads is lexical scoping, while effect tracking by algebraic effects handlers is dynamic scoping. In the same sense if you compare C function calls with Edh effect calls.

[matijapretnar]

Yes, you could say something along those lines about monads and handlers.