You are viewing archived messages.
Go here to search the history.

Adriaan Leijnse 2023-04-04 15:39:18

I've been thinking about how the state of a running program could be modeled as the definition of a program changing over time. This seems closely related to "image" based programming systems, right? Does anyone have thoughts or reading related to this?

(I got there thinking about the branchable/forkable database trend which tries to tie program version to state version.)

Chris Knott 2023-04-04 18:21:02

I'm not sure I follow. Does the definition of a program change at runtime?

Do you mean to include user inputs as part of the definition?

greg kavanagh 2023-04-04 18:24:47

Would you consider something like Redux or Recoil and a React SPA as an image?

Andrew F 2023-04-04 21:00:20

I do think about this a lot, particularly in the context of partial evaluation, where (in short) you can supply part of the arguments to a program and get a result program that has all the consequences of that argument baked in (as opposed to partial application, where you supplying an argument probably just builds a closure).

I mean, a program changing over time is kind of how beta reduction is technically defined, right? Transformation from one lambda term to the next. The problem is, implementations using that strategy aren't (IMO) really feasible. They're not efficient, and there tends to be ambiguity as to the next step, where IIRC different choices determine whether the thing even converges.

One of my goals is a computational formalism that efficiently supports partial evaluation and this sort of program -> program mindset in general. (Key point: you want to be able to output "data", therefore data is a program)

I'm not precisely sure what you mean by the forkable database trend. Can you give an example? I feel like I've heard of a couple different things that answer that description in very different ways.

Nick Smith 2023-04-05 00:23:11

@Adriaan Leijnse I tweeted about this a while ago. At some point in the future, I'd like to develop a programming environment based on this principle.

🐦 Nick Smith: Something I’ve recently realized: a running program is just a static program with some extra data (an event history). There’s no reason we shouldn’t be able to fork, edit, undo & redo running programs (and archive them) just as we do with static ones.

Adriaan Leijnse 2023-04-05 13:17:20

@greg kavanagh An image in this sense would contain both code and the state. It's like your editor is a whole OS that you can modify at runtime:

Adriaan Leijnse 2023-04-05 13:19:26

I think the difficulty I have with this is that there's no real model of change; it happens in this uncontrolled imperative kind of way that makes it hard to do version control and the things Nick Smith is talking about

Andrew F 2023-04-05 13:27:10

Maybe you want event sourcing baked in to the environment?

You could explicitly treat the input as an event stream, and treat the program as a reducer over that stream. It does get interesting when that input depends on program output that depends on previous input.

Adriaan Leijnse 2023-04-05 13:28:29

Nick Smith love that thread!

Adriaan Leijnse 2023-04-05 13:30:26

Andrew F yep! FRP models this dependency just fine, but to make history editing work nicely you need to know about causality. I.e. "what past event is responsible for allowing some future event to happen?"

Jarno Montonen 2023-04-06 07:09:13

In my structure editor tech it is possible to store both logic and data in the same interpretable data structure fairly efficiently (I've written a custom sequential tree). Because of this, creating clones/forks and storing snapshots/images of both state and logic is trivial. Diffing and merging should be possible too, but obviously come with their caveats.

Currently one use case I'm thinking for this would be stateful cloud functions. It should be easy and fast to write the snapshot to a persistent storage and then load it when the function needs to run, and then write the possibly changed version back to wait for the next run. Keeping the snapshots in storage would work as a free history of the program state (and logic) that you'd be able to open up in the structure editor. Of course, it won't just scale to infinity size persistent data and handling concurrent requests would be an extra hurdle. However, it should work fairly well for what is usually required of cloud functions. It is also able to keep much of the interpreted intermediate results and only recompute what's necessary.

Emitting some kind of "rewind" messages to external systems still wouldn't be easy, but could be possible by diffing the snapshots and then constructing the rewind message from the diff..