7 ms·
Temporal Programming, a new name for an old paradigm
- mjburgess 4y agoAs far as I can see this is just pure functional programming. The IO type in haskell is defined, newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))
- dustingetz 4y agoi think the cycle needs to be looped, see MonadFix and ArrowLoop, also recursive do extension. which is all connected with FRP
- marcosdumay 4y agoIt's not, because the article is feeding several commands into the same RealWord value, before changing into the next, and feeding a lot of commands again.
- pron 4y agoWhile you could describe just about anything with a monadic type (or, indeed, any "Turing-complete" programming language in any other), this isn't functional programming because the central idea of functional programming is that the meaning (denotation) of every term (expression) is a value which is an object of the program, while this is neither the case nor the point for the synchronous paradigm.
- aappleby 4y agoAuthor here. It's not "pure" functional progamming in that state exists and is mutable-in-place, but only via atomic swap - you can interpret the sequence of states as a sequence of monads, but the evaluation semantics are different.
- togaen 4y agoProperty 2 implies immutable state. I also used to think that was a great idea. Then I tried actually programming that way.
- AlchemistCamp 4y agoI’ve done most my programming in the past several years in Elixir, where mutable variables aren’t an option, and it’s been a great dev experience. An entire class of bugs disappears and it makes concurrency very easy to reason about.
- macintux 4y agoAfter spending a few years in Erlang, it's hard (and depressing) to go back to any other way of programming.
- dkersten 4y agoI’ve written a lot of Clojure and Clojurescript over the past ~12 years and I find it a very natural way to program to the point that it’s the single biggest thing I miss when I work in other languages like javascript and Python.
- aappleby 4y agoAuthor here. State is not immutable, it is mutate-in-place via atomic swap. That makes it somewhat different than both functional programming and imperative programming, but it's not an excessively difficult programming style to use in practice.
- mrkeen 4y ago> Temporal programs, as I am attempting to define them, are of the form x' = f(x) - a recurrence relation. Functions. > x = x + 1 would not be valid, while x' = x + 1 would be. Yep. void tick() { a@ = b + 1; b@ = a + 1; } Void, oh no!
- a1369209993 4y ago> Void, oh no! void is the unit type, not the uninhabited type. (I'm really not sure what Haskell was smoking when it messed that[0] up, but it's probably too late to fix now.) 0: Calling it Data.Void rather than something like Data.Noreturn or whatever.
- louthy 4y agoVoid is the uninhabited type, Unit is the singleton type. Void != Unit
- a1369209993 4y agoNo, as previously mentioned, `void` is the singleton type (the same type haskell calls `()`[0], and some other languages call `Unit`). Eg: void foo(int x) { printf("%i\n",x); return; /* <- inhabited */ } 0: Give or take some pedantry about `TYPE 'LiftedRep`.
- louthy 4y agoThe example you give is a statement, not an expression. There is no value returned, and the return-type is void, which can't be constructed. Only imperative languages, that can ignore the lack of a value from an expression (by simply moving on to the next statement), can deal with void returning functions. In Haskell this causes the end-of-the-program because it works solely with expressions, and an expression must have a value. It's been a good 30 years since I've written any C, and I know its type-system is compromised at best, but I'm fairly sure you can't do something like this? void x = new void(); Or, using your foo example: void x = foo(); If you can then void is inhabited (and incorrectly named). I realise you could create void* and other elaborate means of claiming you have an inhabited void, but really can you legally construct one, not hack any underlying value to pretend to have one - there is a difference. If you can construct one and assign it to a variable, then it's inhabited. Railing against Haskell when its implementation actually works correctly is a very strange position to take. The clue really is in the name empty-set = void, singleton-set = unit.
- pubby 4y agoThis sounds a lot like software transactional memory (STM) combined with static single assignment form (SSA). The idea behind STM is to specify some block of code as being one big fat atomic operation, and then the runtime will magically make it so. The idea behind SSA form is to only assign variables once, as doing so makes imperative optimization as easy as functional. I wonder if the author knows about these things, or if they're coming in at a different angle.
- parentheses 4y agoThe proposal here seems to make the idea of STM more natural by creating a language that keeps to that core concept.
- aappleby 4y agoAuthor here. Thanks, that is a core goal of the whole project - take a bunch of existing concepts and represent them as implementation details of a simpler, more general framework.
- aappleby 4y agoAuthor here. You'd be hard-pressed to find an example in the literature that I _haven't_ already heard of, I've been researching this for a few years now. STM certainly makes temporal programming easier, though it's not universally available and I'm not sure to what extent it will scale up to be performant enough for large-scale use - how many megabytes can I commit in a transaction before I hit some hardware limit. SSA is a very valuable formalism for describing the interrelation of changing local variables inside an imperative function, but it's difficult to apply program-wide when you're dealing with large data structures and complex call stacks.
- joeyguerra 4y agoLooks and sounds like event sourcing.
- blowski 4y agoFacinating how this sounds - to different people - like event sourcing, functional programming and "software transaction memory". Are people interpreting using their own experience, or is there a big overlap?
- greenbit 4y agoTo a hammer, everything looks like a nail?
- mrkeen 4y agoEvent sourcing is one way to approximate functional programming in the large. STM provides (compositional) thread-safety within a single process. It requires FP but other than that I don't see the comparison.
- marcosdumay 4y agoTo me, it sounds a lot like the part of functional reactive programing that nobody bother to explain or specify. But, well, I'm not really sure people mean that when they talk about it, because it's left unespecified. And when people implement FRP they always seem to take obvious "shortucts" with significant downsides and that avoid implementing something like this.
- thwayunion 4y agoThere's a big and historical overlap. Now these are all distinct topics of study, but in the 80s when these ideas originated there were precious few CS departments. Most all of the software scientists knew each other and were kind of swimming in the same primordial soup of ideas.
- quickthrower2 4y agoAnd React/Redux :-)
- aappleby 4y agoAuthor here. There is a _huge_ overlap between a _wide_ variety of programming terminology, which is why one of the motivations of temporal programming is to bring all these various ideas under one relatively simple umbrella.
- 314 4y agoSome other names that I've encountered for these kinds of programming constructs: * simulation variables (presumably because the separation into x/x' is similar to the now/next calculation of state in a lot of simulations). * SSA (although there is a subtle difference as x' becoming x in the next period isn't really SSA without some extra edges in the graph). I wonder how phi nodes would fit into the author's scheme?
- mrkeen 4y agoCan't speak for the author but I believe 'phi nodes' map to 'join points' in function land: https://www.microsoft.com/en-us/research/publication/compiling-without-continuations/ https://www.microsoft.com/en-us/research/publication/compili...
- aappleby 4y agoAuthor here. I've commented on SSA and simulations (in the context of gamedev) elsewhere in this thread. Regarding phi nodes, they represent a "merge" of two possible execution branches. In C++ you evaluate one side of the if() branch and ignore the other based on the predicate and the "phi" (sometimes called "phony") function then copies the result from the selected branch to the new SSA variable. In a language like Verilog, you evaluate _both_ branches and the phi node is effectively a "mux gate" that selects between the two branch results based on the predicate.
- charlieflowers 4y agoOverlaps with functional reactive programming
- aappleby 4y agoAuthor here. Temporal programming overlaps with a lot of things, FRP included. I like to thing of FRP as being stream-at-a-time evaluation, whereas TP is whole-state-at-a-time evaluation. That probably doesn't make a whole lot of sense without a diagram, I should draw one. :D
- meindnoch 4y agoIn game programming this is called “double-buffered state”: https://gameprogrammingpatterns.com/double-buffer.html https://gameprogrammingpatterns.com/double-buffer.html
- aappleby 4y agoYep, I am a grumpy old ex-game-programmer (PS1 and N64 era) and wrote many, many little systems using double-buffered state.
- lalwanivikas 4y agoHmmm I got confused by the name. I thought it's related to https://temporal.io/ https://temporal.io/
- aappleby 4y agoAuthor here. Looks like FRP for the backend. I'll skim over it later.
- muhaaa 4y agoYou want to try temporal programming? Try clojure: immutable values, immutable & persistent data structures, software transactional memory. You need a data base with full history (transaction time), try datomic. Additionally if you need full history AND domain time (bi-temporal) included in your data base, try or xtdb.
- gleenn 4y agoI second this, Clojure gives you this both in memory and in the database via Datomic and reasoning about immutable data and pure functions is such a dream. Stateful programming is the worst, once you live in Clojure for a while everything else seems nuts trying to debug what got passed to what and when and what modified what. Such a disaster relatively speaking.
- deterministic 4y agoOr Haskell/Elm/… if you prefer typed programming languages.
- rockwotj 4y agoGleam.run is my current favorite flavor for "typed functional language". It's simple (a small language) and compiles to erlang
- aappleby 4y agoAuthor here. One goal for MetroC is to have a codebase that can run equally well on a CPU or a FPGA. To do that efficiently, I need pretty detailed information about how exactly my program gets translated into x64 instructions or FPGA gates. I'm not sure I can do that in Clojure, but I haven't done more than a cursory skim of the language.
- mpweiher 4y agoSounds a lot like Lucid? https://en.wikipedia.org/wiki/Lucid_(programming_language) https://en.wikipedia.org/wiki/Lucid_(programming_language) They don't use x', but rather fby x, but otherwise the ideas seem very similar. Of course, they called it dataflow, and Lucid inspired the "synchronous dataflow" languages like Esterel (imperative) and Lustre (functional). Which in turn inspired the non Conal Elliott variants of "FRP". It's all related...
- aappleby 4y agoAuthor here. Yep, it's all related. My hope is that temporal programming can provide both a simple practical framework (in the form of MetroC and whatever else spins off of it) and a simple theoretical framework for future research into time-centric programming languages.
- dl7 4y ago> Programs that adhere to these tenets should in theory be far more optimizable than what would be possible in a procedural language, as the compiler is essentially given the entire evaluation graph for the program up front and can completely reschedule evaluations in whatever order is most efficient. They should also be more amenable to formal TLA-type proofs since their computation model is much closer to what TLA+ expects. This sounds a lot like graph computation but on an extremely granular level.
- aappleby 4y agoAuthor here. Yes, it's another way to express graph computation, but without needing a graph-computation-specific language.
- avodonosov 4y agoI once glanced through some explanation of monads by Simon Peyton Jones. He said that in ALGOL specification, the semicolon operator is formally defined as taking the current state of the world, transforming it by the statements preceding the semicolon, and then arranging for the program to continue execution in this new world. So John Backus not only suggested "Applicative State Transition" in his paper. He participated in ALGOL creation. Which influenced most contemporary languages. We have this style of programming in our Pascal and Java programs. Please no new names. Semicolon is semicolon. Sorry, I can't find this blog or paper by Peyton Jones. Leaving that as an exercise for the reader :) And of course, I can misremember something.
- nerdponx 4y agoNow if we could only statically reason about updates to the world state...
- avodonosov 4y agoI must be missing something. The Backus publication referenced by OP is from 1978, much later than Algol. Maybe the OP means some substantial difference, but I don't see what exactly. And indeed, the Backus publication even has a section "14.2 The Structure of Algol Compared to That of AST Systems".
- hgsgm 4y ago
- aappleby 4y agoAuthor here. From the Algol viewpoint, you can think of a temporal program as one enormous statement followed by a semicolon, embedded in a while(1) loop. Semicolon is semicolon, but in Pascal/Java you have lots of tiny semicolons and in a temporal program you have one giant semicolon. The practical implications of that are more wide-ranging than you think, and quite interesting.
- thwayunion 4y agoThis idea has a history! The reason most language research programs like this had limited success is as follows. There are precious few programs for which a|b ~ a;b is true for all atomic programs a,b where: | is a parallel composition operator ; is the normal sequential composition operator (defined in the completely standard way in terms of updates to a global state or heap/stack-like structure if you want to be fancy) ~ is any sort of equivalence relation on reasonable and realistic semantics. More-over, there are precious few programs that easily decompose into parts A,B,... such that A|B ~ A;B is true for each A and B in the set of parts. You can give theoretic characterizations of this fact, and many have, but the pragmatic point is more convincing. Associativity and even reflexivity often fail as well. The allure of this line of thought is promising, but alas... The "just make a simple algebra and arrange your programs to fit it" research program died early on for a reason. In the context of parallel and concurrent programs, it is hard/impossible to solve the decomposition problem at the language level of abstraction. That pretty much summarizes outcome of a big chunk of program analysis research from the 70s to early 90s in a nutshell, unfortunately. Let me briefly illustrate using OP's example: `a' = b + 1; b' = a + 1` from which I've deleted the errant training semicolon (it's `1+1` not `1+1+`!) Suppose we instead have the program: a' = a + b + 1; b' = a + b + 1 Now, the ordering does matter! No worries, so we order. Additionally, suppose we put these programs into an outer while(true) loop and that's our whole program. Now what have we bought ourselves? Not much. In this case we can solve that problem by... well, by solving some sort of integer recurrence equations that give us a program without loops which we can then think about algebraically. But of course this gets difficult or impossible very fast. (And, btw, the algebra part here did not buy us much. It was solving integer recurrence equations that saved the idea in this example). We haven't even added real data structures or external state yet. Anyways, looks like OP is building something around this idea. Good luck! I'll be curious to see how you handle loops inside of blocks that contain @'d variables with recursively defined quantities :)
- oh_my_goodness 4y agoI don't think the ordering matters. In both a' = a + b + 1 and b' = a + b + 1 the new values are on the left and the old values are on the right.
- deterministic 4y agoThis is how I think about programming and how I design software. You don’t need a functional language to do this. However it does require more discipline when the language doesn’t enforce purity. And once I started thinking about software this way I realised that events are important and should be the core of any software design. Basically the application is a single function that takes an event and the current state, and computes a new state and zero or more events.
- not2b 4y agoNonblocking assignments in hardware description languages (like Verilog or VHDL) work a lot like this. For example always @(posedge clk) begin A <= B; B <= A; end swaps A and B on each positive clock edge.
- aappleby 4y agoAuthor here, you are correct. Implementing non-blocking assignment semantics in C++ is hard and can't really be done cleanly from within the language. Metron (the C++ to Verilog translator) relies on static analysis to prove that C-style assignments to non-local variables in a C++ program have the same semantics as if they were non-blocking assignments. MetroC will extend this with the '@' operator to allow for real non-blocking assignments in code that otherwise looks like regular imperative C.
- scrubs 4y agoI'm liking this post a lot. The write up is good Gonna fork it. Well done aappleby
- aappleby 4y agoThanks, I'm always looking for feedback on how to make this concept more understandable.
- kazinator 4y agoWhy wait for a language; here is a macro: Firstly, we define a place (temporal x y) such that when this place is accessed, it denotes x, and when it is assigned, the assignment goes to y: (defplace (temporal-place var var*) body (getter setter ^(macrolet ((,getter () ,var) (,setter (val) ^(set ,',var* ,val))) ,body)) (setter ^(macrolet ((,setter (val) ^(set ,',var* ,val))) ,body))) (define-place-macro temporal (var var*) ^(temporal-place ,var ,var*)) (defmacro temporal (var var*) var) We can then use that as a building block whereby we define an apparent variable v as a symbol macro which expands to (temporal vold vnew). All accesses to v get the value of vold, but assignments to v do not affect vold; they go to vnew. Here is a let-like macro which sets up the specified variable as temporal. The initial values propagate into both the old and new location. Then before the last form of the body is evalulated, the new values are copied to the old values. (defmacro temporal-let (vars . body) (let ((olds (mapcar (ret (gensym)) vars)) (news (mapcar (ret (gensym)) vars))) ^(let* (,*(zip olds [mapcar cadr vars]) ,*(zip news olds)) (symacrolet ,(zip [mapcar car vars] [mapcar (op list 'temporal) olds news]) ,*(butlast body) (set ,*(weave olds news)) ,*(last body))))) Test. e.g: 1> (temporal-let ((x 1) (y 2)) (set x y) (set y x) (list x y)) (2 1) The expansion is: 2> (expand '(temporal-let ((x 1) (y 2)) (set x y) (set y x) (list x y))) (let* ((#:g0024 1) (#:g0025 2) (#:g0026 #:g0024) (#:g0027 #:g0025)) (sys:setq #:g0026 #:g0025) (sys:setq #:g0027 #:g0024) (progn (sys:setq #:g0024 #:g0026) (sys:setq #:g0025 #:g0027)) (list #:g0024 #:g0025)) Let's see how it compiles: 2> (disassemble (compile-toplevel '(temporal-let ((x 1) (y 2)) (set x y) (set y x) (list x y)))) data: 0: 1 1: 2 syms: 0: list code: 0: 20020002 gcall t2 0 d1 d0 1: 04010000 2: 00000400 3: 10000002 end t2 instruction count: 2 #<sys:vm-desc: 903ec50> Oops, it got compiled to a single call instruction invoking (list 2 1). Let's try opt-level zero: 1> (let ((*opt-level* 0)) (disassemble (compile-toplevel '(temporal-let ((x 1) (y 2)) (set x y) (set y x) (list x y))))) data: 0: 1 1: 2 syms: 0: list code: 0: 04020004 frame 2 4 1: 2C800400 movsr v00000 d0 2: 2C810401 movsr v00001 d1 3: 2C820800 movsr v00002 v00000 4: 2C830801 movsr v00003 v00001 5: 2C820801 movsr v00002 v00001 6: 2C830800 movsr v00003 v00000 7: 2C800802 movsr v00000 v00002 8: 2C810803 movsr v00001 v00003 9: 20020002 gcall t2 0 v00000 v00001 10: 08000000 11: 00000801 12: 10000002 end t2 13: 10000002 end t2 instruction count: 12 #<sys:vm-desc: 9de1b50> TXR Lisp's compiler performs frame elimination optimization whereby the v registers get reassigned to t registers, eliminating the frame setup. The t registers are subject to some decent data flow optimizations and can disappear entirely, like in this case.
- svilen_dobrev 4y agothis is dependency-driven inference. Sequence-of-execution (i.e. "time") follows from dependencies. Think "make". i call this "wave" calculation - as the algo to find the sequence after each input change/stimulus is spreading changes like wave from-the-point-of-change-outwards, in topological sort. There might be (direct or indirect) recursion allowed, up to some predefined level, or minimum-change-diff thresholds or whatever. Writing a calculator for such set of rules is relatively easy, from memory they were like 1000 lines in c++, 100 lines python, 200 lines js.. it more depends on the "syntax" and conveniencies for the programmers, than actual engine. Now, Turning that into full language .. will be really interesting. Kind of turning inside-out the relation wavecalc <--> general-language-of-choice..
- quickthrower2 4y agoDoes Elm count as a language that does this? You can only code by transitioning state one at a time. Even when doing async calls.
- aappleby 4y agoAuthor here. I'll have to go look at Elm again - it's in my list of references, but I have so many at this point that I don't recall what exactly Elm does differently.
- esfandia 4y agoIsn't this how Operational Semantics works for describing formally a given programming language? You define what the state of execution of the program is made of, and how state transitions occur during one execution step. The wikipedia link describing it is overly arcane but here it is anyway: https://en.wikipedia.org/wiki/Operational_semantics https://en.wikipedia.org/wiki/Operational_semantics
- aappleby 4y agoAuthor here. Operational semantics are a way of "talking about" a programming language, whereas temporal programming is a way of expressing operational semantics more directly from within a programming language.
- pron 4y agoThe existing name for this paradigm is "synchronous programming" (because such programs, like synchronous circuits, can be thought of as having a clock that ticks at every state change): https://en.wikipedia.org/wiki/Synchronous_programming_language https://en.wikipedia.org/wiki/Synchronous_programming_langua... The first synchronous programming languages were, AFAIK, Statecharts and Esterel, the former designed by David Harel while he was working alongside Amir Pnueli, who would later win the Turing Award for introducing temporal logic to computer science. https://www.wisdom.weizmann.ac.il/~harel/papers/Statecharts.History.pdf https://www.wisdom.weizmann.ac.il/~harel/papers/Statecharts.... Eve also combined synchronous programming with logic programming: https://witheve.com https://witheve.com
- Nokinside 4y agoThis is also how PLC's in industrial automation work. In general, any large hard real-time system. Factories and assembly line automation has a system of state updating devices. They were initially programmed using Ladder Diagrams, then STX (Structured text) a Pascal like language and IL (Instruction List), Sequential function chart, or Function block diagram. These all use Common Elements (IEC 61131 standard) so, you can mix languages.
- aappleby 4y agoAuthor here. Thanks for the reference, I'll add the IEC 61131 standard to my list.
- aappleby 4y agoAuthor here, I'm aware of Lustre/Esterel/Signal/StateCharts/etc - there are a _lot_ of examples of prior art, each with their own interpretations of how time should work in a programming language. I'm hoping that Temporal Programming can serve as both a reboot of Synchronous Programming, as well as a fresh generalization of the ideas from all the various branches of research that have popped up over the years.
- seanmcdirmid 4y ago
- brap 4y agoI don’t really see the usefulness of this. If you write your program this way, how does it interact with the environment (e.g user input, output, network…)? Something is missing. And if it doesn’t interact with the environment, then your program is just one big pure function, in which case you get all of the benefits in OP’s proposal anyway, without having to worry about transforming old state to new state, you just gotta transform input to output.
- robertlagrant 4y ago> If you write your program this way, how does it interact with the environment (e.g user input, output, network…)? The answer is, of course, monads[0]. Probably. [0] https://dl.acm.org/doi/10.1145/158511.158524 https://dl.acm.org/doi/10.1145/158511.158524
- aappleby 4y agoAuthor here. In Backus's paper, the next-state function accepts a (state, input) tuple and returns a (state, output) tuple.
- aappleby 4y agoAuthor here, I missed this post because my own post of this link got lost in the HN ether. Replying to comments now.