The unreasonable effectiveness of declarative programming
bollu.github.io
bollu.github.io
Most of the framework was declarative. There were Sprite objects that had an associated Image and a position (among other things). The onUpdate(dt) method of the "screen" didn't explicitly draw things on the screen, it only updated positions and other attributes of the Sprites, and the renderer would do the rest (back in the days of software rendering, it updated only dirty sections of the screen, etc).
Still, making programmatic animations was difficult, and for videogames you want things to look very nice (smooth movement, easing in and out, transparency effects, that kind of thing). There was a lot of { srcX, srcY, dstX, dstY, time } sets, for every thing that moved.
At some point I had an idea similar to what this blog proposes. I called them SpriteControllers, and they could be "attached" to a Sprite. The engine would call each SC's onUpdate(dt) method on every frame, and the SC would change the position, rotation, alpha, or tint of the Sprite.
By default all the attached SCs would work in parallel, so the next step was to have a SCSequence to run things in series. Also each SC was allowed to declare when it was "done". Some did (like linear motion from A to B), some never finished (like a pulsating glow).
It was a fun development in the sense that it made something that was very difficult to do by hand surprisingly easy, and took our games to the next level in terms of visual quality, just by adding a bunch of very short classes.
Making games was fun in a way. Alright, back to work. These protos aren't going to copy themselves into other protos by themselves!
Try the two Sherlock games if you can get them somewhere - these have a special place in my heart :)
Edit: read your other comment and saw the licensing stuff... Shame about games (and such) that you just cannot keep them for sale forever... But just let them die.
Never thought of putting our first-party games on archive.org, sounds like a great idea, I'll look into it :)
One bit of feedback: the sliders are almost impossible to click on with a mobile browser. The drag handle should be much larger. There’s also a horizontal scroll bar that appears partially above the bottom of the page, something is overlapping the main content body.
That said, I found the abbreviations initially confusing. For variable names and symbol/strings, maybe hold off until not the first example? For the functions themselves, can you do a non-abbreviated alias?
I also missed the `par` in `seq((...).par(...))` the first time. And, personally, I think `par([...,...])` would be clearer, and allow for some beneficial constructs - is there a way to allow both?
Particularly, I really admire the time travel aspects; that you can, what that means, and what allows that to happen.
It reminds me a lot of what I've tried to do (not as elegantly, so I might come crib from you!) with the pattern renderer in https://github.com/rangerscience/butterfly
I've always heard declarative as a sort of synonym to programs defined in terms of equational reasoning such as Lustre for instance - a rule of thumb to separate declarative languages from imperative languages is that in declarative languages
x := 1
y := x + 1
x := 2
e.g. it's not enough to just construct a graph-like datastructure for things to be declarative, the language has to do it itself.
Also, note that the par / seq model (https://en.wikipedia.org/wiki/Series-parallel_graph) is not as powerful as a general dag as things such as the K4 graph cannot be represented in it - even though it may make sense in some animation scenarios.
Also, why should the second binding override the first? You introduced a temporal dimension where later lines of code somehow override earlier lines of code. That is not a necessity in a declarative language. It may be how we humans read text (from top to bottom), but it does not mean the computer has to process it in the same way.
c'mon, this is an example in a forum post ! of course it doesn't make sense in real life. real life is
distance := computeDistanceToCenterOfScreen(cursorPosition)
text := "the current distance is: " + distance
> Also, why should the second binding override the first? You introduced a temporal dimension where later lines of code somehow override earlier lines of code.
yes, some languages work like that, but it's not the point - either you assume that you can update values in your declarative bindings like that, or you have to define your binding in terms of some external behaviour that will change in magic ways, which again would not be very nice to do as a simple forum post example
This would be an error in a language with immutable data structures. Declarative and immutable are not the same thing and there is nothing that says a declarative language must have immutable data structures.
It's an error from the point of view of equational thinking; (im)mutabilty is not involved.
The name `x` cannot be 1 and 3 simultaneously. It's either 1 or 3. So in the allegedly declarative program, the programmer first claimed name `x` is bound to the value 1, but later claimed it's 3. That's the error.
This has nothing to do with mutating data structures. Like the sibling comment notes, there is not "first-this-then-that" order of evaluation, so you cannot read this as "first `x` means 1, but later it means 3", because there are no notions of "first" and "later".
you say what you want, and the DB figures out how best to get it.
I can see that the names of the functions are declarative in style but the code is a series of function calls that seem to be giving instructions to the javascript interpreter to perform a sequence of operations. For example, you describe the code as follows:
1. anim_const(name, val) to set a constant value val to name name.
2. anim_interpolated(ease, name, val, time) to change to a named value with name
name to value val in duration time.
3. anim1.seq(anim2) to run anim2 once anim1 has completed.
4. anim1.par(anim2) to run anim2 in parallel with anim1.
5. anim_delay(time) to do nothing for time time.
Do you mean something else by "declarative"? Could you say what you mean by "declarative"?
def SayHello():
print("Hello!")
SayHello()
Personally I'd set the line as being somewhere where by definition of the system, there is a barrier set up and you are no longer allowed to "see into" the implementation because it's going to do things so crazy to your declaration that allowing you to see into it would ruin it. e.g. in SQL when you send in your query the query engine is reserving the right to rewrite it in absolutely crazy ways, and in principle, you have no right to ask about what it actually did as long as you get the "right answer". This is because I then like to segue into how that barrier is somewhat illusory because it's always going to take some concrete actions and you may have need to see into those actions. But that isn't the only place to draw the line, it's just where I find it convenient to draw the line so I can ride a pet hobbyhorse. There isn't really a bright line, even though there is clearly some real difference we are trying to talk about.
To give an example of what I mean, here's a typical C function that concatenates two linked lists [1]:
void concatenate(struct node *a,struct node *b)
{
if (a->next == NULL)
a->next = b;
else
concatenate(a->next,b);
}
append([],Ys,Ys).
append([H|T],Ys,[H|Zs]):-
append(T,Ys,Zs).
append/3 and concatenate() share the same procedural interpretation: "to concatenate two lists walk through the first list until you find the last element in its tail ("[]" in Prolog, NULL in C) and make that element be the first element of the second list [2]".
The difference is that Prolog's declarative interpretation describes not only concatenation of two lists, but also their difference. Indeed, append/3 can be called in different instantiation modes to perform both tasks:
% Zs is the concatenation of _Xs and _Ys
?- _Xs = [a,b,c], _Ys = [d,e,f], append(_Xs,_Ys,Zs).
Zs = [a, b, c, d, e, f].
% Zs \ Xs = Ys
?- _Xs = [a,b,c], _Zs = [a,b,c,d,e,f], append(_Xs,Ys,_Zs).
Ys = [d, e, f].
% Zs \ Ys = Xs
?- _Ys = [d,e,f], _Zs = [a,b,c,d,e,f], append(Xs,_Ys,_Zs).
Xs = [a, b, c] .
% Starting a variable with an underscore, like in _Xs, _Ys, _Zs, stops the
% Swi-Prolog runtime from printing the bindings of the variable and
% cluttering the screen with values you already know ;)
________________
[1] Copied from: https://www.codesdope.com/blog/article/concatenating-two-lin...
[2] "Behind the scenes" both Prolog interpreter and C compiler have the same "view" of computer memory and the pointers from an element in a list to the next. However, the point here is not that the Prolog interpreter "hides" this fact. If you squint a bit- it doesn't. [H|T] is the concatenation of H and T and you can very well read it as a pointer from H to the first element of T.
[3] And note of course there are more purely declarative languages than Prolog, like Answer Set Programming. But, I know Prolog and You Can't Teach an Old Dog New Tricks (old dogs know all the tricks :P).
I like the font used for the code, very readable. But underscoring keywords is superfluous and makes the code listing weird - bold font is enough. Also, the line numbers are jarring, they are too pronounced and they are not important to the reader. Maybe make them gray or put them on the right-hand side. This is a common problem with many blogs. I don't care about the line numbers!
The main text is hard to read - this font, a kind of an hybrid of serifs and tall quasi-monospace characters, is weird and hard to read. Try more usual sans-serif font with shorter-height characters, I think it will be much better both for readability and more distinct from the code listings.
The paragraph symbol is obsolete, I would lose that. At least don't make it look like a link, nothing happens when I click it.
On being invoked, it sets out.v = field (…) out.field = vThe library is very nice too. The only thing I would add is, uh, rub some Category Theory on it. It seems like you could "go all the way" and define a formal mathematical semantics for animations, which would be nice. VPRI STEPS project made a quasi-mathematical language called Nile for compositing 2D vector graphics ( http://www.vpri.org/pdf/tr2009016_steps09.pdf ) that might be something to look at.
type Anim a = (Duration -> a, Maybe Duration)
-- Linear interpolation
linear :: Anim Duration
linear = (id, Nothing)
-- Sequencing
seq :: Anim a -> Anim b -> Anim (Either a b)
seq (f, Nothing) g = (\t -> Left $ f t, Nothing)
seq (f, Just df) (g, dg) =
(\t -> if t < df
then Left $ f t
else Right $ g t
, df + dg)
-- Parallelism
par :: Anim a -> Anim b -> Anim (a, b)
par (f, df) (g, dg) = (\t -> (f t, g t), max df dg)
-- Constant
pure :: a -> Anim a
pure a = (const a, Nothing)
-- EDIT: forgot delay
delay :: Duration -> Anim ()
delay d = (const (), d)
EDIT: More fixes
EDIT: I should really test in GHCI before I post these things. But I'm lazy.
You could add a monoid instance which would be useful (for one example) if the animation produces a matrix transform then you could combine two animations that produce transforms. For example a rotation and a move. I’m sure there are other good monoid animations. Strings would be a simple example I guess.
typo here:
seq (f, Maybe df) (g, dg) t
and `par` should be
par :: Anim a -> Anim b -> Anim (a, b)
par (f, df) (g, dg) = (\t -> (f t, g t), max <$> df <*> dg)
i'm not sure about `par` - if my understanding of Anim is right, it'll take the shorter animation over its specified duration. what if it was something like:
par a@(_, da) b@(_, db) = (ab, max <$> da <*> db)
where ab t = (a `at` t, b `at` t)
at :: Anim a -> Duration -> a
at (f, Nothing) t = f t
-- freeze when t exceeds dur, i.e. the animation is done
at (f, Just dur) t = f (min dur t)
or is that not what the duration represents? i.e. is this correct:
stretch :: Float -> Anim a -> Anim a
stretch factor (f, dur) = (\t -> f (t / factor), (factor *) <$> dur)Maybe I'll try and make a small library of it if there isn't already. I've never posted something on Hackage.
As I was writing it my headspace was that the duration was for seq to know when to switch. I wasn't really thinking about stopping the animation too.
(I also notices that my seq is wrong. The subsequent animation should start at the beginning, so it should be `g (t - df)`, not `g t`
I believe you are correct. Your implementation is more at the heart of what I wanted to show. . The main point I wanted to get across was the interface itself.
Animations are frames over time and can be composed using 'seqA' and 'parA' combinators.
foldr1 (\x y -> ((x `par` delay 1) `seq` y)) $ map pure [1..]
It is like you are speaking in Martian or something.
Haskell is effectively impenetrable to me.
Something like this?
@keyframes ball{
0%{ left:50px; top:100px;width:0px; height:0px }
10%{ left:50px; top:90px; width:20px; height:20px }
20%{ left:50px; top:90px; width:20px; height:20px }
30%{ left:300px;top:50px; width:100px;height:100px}
50%{ left:300px;top:50px; width:100px;height:100px}
60%{ left:200px;top:50px; width:100px;height:100px}
90%{ left:250px;top:100px;width:0px; height:0px }
100%{left:50px; top:100px;width:0px; height:0px }
}
If Martians visited Earth, surely you'd want to learn their language. :)
The "list of actions" approach is what makes code complexity grow exponentially, because whenever you look at a series of 10 instructions, you have to think "what state was created by the combination of the first 7 instructions, and does the eighth instruction depend on that state?"
arr
.map(x => x + 2)
.filter(x => x % 3)
.map(x => other(x))
Declarative code describes the _output_ or final desired state of something.
Similarly, in mathematical notation, `f(g(x))` can be a way of expressing the existence of some sort of law, e.g. maybe f and g are commutative. That means that if code were written as such in a 5th-gen language[1], the underlying engine is free to recompile the code into `g(f(x))` assuming the commutative property holds and the performance is better. By contrast, in a imperative language, `f(g(x))` generally would compile to that exact order of operations (unless you have a mythical sufficiently smart compiler)
I can see an argument about JIT compilers being smart in some cases, but the philosophical distinction between imperative and declarative paradigms is that with declarative style, the compiler can transparently swap units of arbitrary complexity. For example, given some CSS rules, a browser engine can decide to paint the screen buffer however it wants, be it top-to-bottom, edge-to-center, layer-over-layer, etc regardless of how the CSS was originally expressed.
[1] https://en.wikipedia.org/wiki/Fifth-generation_programming_l...
BTW, pedantry: -2 * -2 = 4 too
Compiled programming languages are declarative ways of generating machine code. The source code describes what the output or final state (the executable) should consist of, but not how to construct it (that's in the compiler source).
Is the code "read x; print x + 5" declarative or imperative?
It's declarative because it doesn't specify how to read the number, how to print the result, or how to add numbers. It merely symbolically describes the IO and calculations to be performed.
It's imperative because it specifies in a step-wise fashion reading input, performing a calculation, and outputting the result.
Declarative code is imperative from the perspective of the next layer up in the abstraction stack. Declarative code elides implementation details; the we call the implementation details imperative, because they specify the "how" and not the "what", which is the domain of the higher level.
Under this lens, what can we say about this:
arr
.map(x => x + 2)
.filter(x => x % 3)
.map(x => other(x))
1. While each line is a separate step that's done in order, it's done on the results of the previous step. So it's like "get me the sum of the products of the results of foo" rather than "do x, then do y, then do z".
2. Your example has less steps.
Yes, although not necessarily all of them. Some languages will process this eagerly, some lazily.
In C#, the functions being passed could be passed as analyzable syntax trees, and the implementation could actually be in SQL.
Sequencing is a fundamental computing construct. Data flow graphs allow you to specify sequences, just as shell pipelines do. SQL has sequentiality built-in with nested queries. None of these are imperative environments.
So yes—-it is imperative, but it uses functional abstraction to reduce complexity.
It is certainly less imperative than the equivalent C, that's for sure.
Yield an interpretation of a set of boolean variables that satisfies the following conditions:
- A AND B
- (NOT C) or A or B
- A AND (NOT C)
...etcAnimation at its core is a sequence of images. Imperative animation code would describe how those images change every frame. (For example, a for loop in which you multiply properties by i in order to change them over time).
Declarative animation code would let you define keyframes — how the images look at specific points in time — and the library would generate the images in between them. (This is called "tweening" [0]).
The sample code in this case isn't a list of actions to be performed one after another. It's a list of states (keyframes), which the library interpolates between. That sounds declarative to me!
You would still have the same problem by using a notation that looks like function application.
The alternative is to repeat all unmodified values, so that looking at each animation step, you know what the output state is.
Declarative languages don't specify (or minimize the specification of) the execution, imperative languages specify the execution. You can look at the verbs used in describing or verbalizing the language. In declarative languages you don't talk about "assigning" as much as you talk about relationships: "x is y", "x is related to y by f(x,y)", "if x is predicate(x) then y is z else y is z'". In imperative languages you do things: "x is assigned y", "for x in y do ...", "if x is predicate(x) then do y is assigned z else do y is assigned z'".
Additionally, statements/expressions in declarative languages can be reordered more freely (the "purer" the declarative language the more true this is), given that it tends towards the relational version. In a constraint based system, for example, you could do these in either order:
x in 1..10
x % 3 == 2
;; => x \in {2, 5, 8}
Imperative programming is about each statement altering a program's state, not the act of sequencing.
It's not just syntax sugar. Try writing a function that takes an array of integers and an integer x, and sorts the array mod x by calling qsort. In C this is not just cumbersome but impossible.
static int reg;
int cmp(int a, int b) {
return a%reg - b%reg;
}
void qsortModX(int[] a, size_t len, int x) {
int tmp = reg;
reg = x;
qsort(a, len, sizeof(*a), cmp);
reg = tmp;
}
static void* g_ctx;
static int(*g_cmp)(void*, const void*, const void*)
int compare(const void* a, const void* b) {
return g_cmp(g_ctx, a, b) ;
}
void qsort_cls(void*[] a, size_t len, size_t elem, int(*cmp)(void*, const void*, const void*), void* ctx) {
void* tmp = g_ctx;
g_ctx = ctx;
int(*tmp_f)(void*, const void*, const void*) = g_cmp;
g_cmp = cmp;
qsort(a, len, sizeof(*a), compare);
g_ctx = tmp;
g_cmp = tmp_f;
}
Basically, if you want higher-order functions in C, you can do it, but you need to take a context pointer and a function which accepts a context pointer. The writers of qsort didn't think of that, so we had to resort to global variables to do it, but you could also re-write qsort to avoid the need for the global variable.
As I said, we're missing a lot of syntax sugar, but we can still work with functions as first class objects in pure C.
I would note though that with C's type system, you always have to choose between type safety and genericity, this is not exclusive to higher order functions. C doesn't have a notion of threads or thread safety, so talking about thread safety in pure C does not make sense. And the fact that the designers of the stdlib didn't think about supporting closures still doesn't mean that the language itself doesn't support them. Other foundational libs, like pthreads, do have support for this style of closures built in.
True, but functions defined via some kind of "struct closure" scheme are non-typesafe even when monomorphic (e.g. if all the types are int).
> C doesn't have a notion of threads or thread safety, so talking about thread safety in pure C does not make sense.
I'd hold that a function that relies on a global variable is noticeably second-class in a number of ways. Multithreading is one place where this comes up, but you also have to be careful about using it in a recursive context, or use in a library that might be called from more than one place.
> And the fact that the designers of the stdlib didn't think about supporting closures still doesn't mean that the language itself doesn't support them.
Any Turing-complete language "supports" any feature of any other language in a sense, because it's always possible to emulate that other language. If we say functions are first class then we mean not only that it's possible to represent functions as values (because that will always be possible), but that functions represented this way are just as good values as the language's built-in notion of values, and just as good functions as the language's built-in notion of functions.
In Prolog, everything is either a fact or a rule involving facts. If you leave some variables unbound, you get what we think of as a program, where the system tries to infer values.
But remember that the problem with a declarative syntax, is that it needs a runtime, which typically the end user doesn't touch. And if the runtime doesn't take into consideration one use case, the user is stuck. Don't forget to provide an escape hatch.
GHC compiles to native code, but there's still a runtime for instance to handle the garbage collection, to sort out the lazy evaluation, and to translate the blocking IO API at the haskell end into a non-blocking IO api at the kernel end.
I surely wouldn't want to be debugging my haskell code on a time budget by directly looking at the machine code that is running. I know some people do that and it can be quite illuminating, but the fact that I can debug haskell in its own terms is good.
Something like Django or Rails, is no longer just a "declarative library" it's a framework. You're using their patterns, and you're limited to their escape hatches.
Declarative is just a paradigm, you can use any language to design a declarative API.
Nox, pydantic and sqla are examples of it.
As for more sophisticated animations, I can think of reanimate [1], which outputs animations in SVGs, and should work on the web with wasm if integration is needed [2][3].
I completely agree that declarative programming (and functional-style programming) shines for composing animations. Imperative programming does not show the intent as clearly, and makes it hard to reason about or time travel animations.
[1]: https://reanimate.readthedocs.io/en/latest/glue_tut/
Literate programming is just syntactic sugar around functional programming. For example:
qux(bar(foo,baz),garlply)
foo.bar(baz).qux(garply)
What people usually mean when they say "declarative programming" is they want to write a config file in, say, JSON, and have that be their program. But that would mean that the implementer of the language would have to think of every possible way that you could possibly want to configure the program, so they start adding customization points where you can write code in an actual language which is called in certain spots. So now you have to know how to program in a normal language, and know how all the different customization points work. Oh and while you're doing that, you can forget about getting anything helpful like a stack trace, because it was declarative so you don't need to worry about what is calling what, right? So you get things that just fail silently and you don't know why, like:
class Mail(models.Model):
ordering = '-received'
sender = models.EmailField()
receiver = models.EmailField()
received = models.DateTimeField()
body = models.TextField()
circle is at position 10,10 at time 1.5
circle is of size 50 at time 5
circle is at position 20,50 at time 3
And so forth. And because of this statements, an animation is computed that respects the declarations.
If you write a comment saying x is y. Then rename x to be y. The comment adds a layer of abstraction. Now every time you encounter x you refer to the table of abstractions to get to y.
In a similar way the library has shortened function names. This is another layer of abstraction so you need to decompress the shortened function name once again.
1. Don't use parentheses in comments. They make things more visually confusing when javascript imposes enough syntactic clutter as it is.
2. What's with /* */ ? Doesn't js allow keyword arguments?
3. Your method names are probably a little short for my taste. I'd be happier with sequence() and parallel() instead of seq() and par(). Par especially seems a little too obscure when first encountering it.
4. "cx = location | cr = radius" - why not allow both forms? - or just the clearer one rather than the shorter one.
No.
I wonder if passing in a dict is a good alternative in this case. More syntax clutter but at least the params have some semantic meaning.
----
> 2. What's with /* */ ? Doesn't js allow keyword arguments?
It does since version 6. Example:
The function call anim_interpolated(ease, name, val, time) should be rewritten thus:
anim_interpolated({ease, name, val, time})
The corresponding function definition should be rewritten thus:
function anim_interpolated({ease, name, val, time}) { … }
Basically, method-chaining allows you to concisely express programs, by hiding irrelevant complexity behind abstractions.
Everything else is better to be done by some sort of imperative language. The declarative stuff can be a subset and a convention but you can always break out of it.
Hopefully readers considering this sort of thing for UI transitions will bear in mind: this is nice if the goal of your application is entertainment, deeply irritating if the goal of your application is productivity.
I'm assuming that any declarative language powerful enough for general use is expressive enough to represent an NP-complete problem; i.e. : Find a set of booleans X1..XN that satisfy Y logical statements (or prove that there is none possible). Therefore absent opening up the "black-box" of the language, the time and space complexity could be unbounded.
With an imperative language, of course, since the programmer is probably specifying the exact order of operations and data structures being used, reasoning about and bounding the cost is usually straightforward.
http://python.cocos2d.org/doc/programming_guide/actions.html
Example:
bounce = Jump(150, 0, 4, 2)
scale = ScaleBy(2, duration=1.5)
rot = RotateBy(360, 0.80)
scale_and_rot = scale | rot
bounce_in = bounce | scale_and_rot
bounce_out = Reverse(bounce_in)
logo.do(bounce_in + bounce_out)Highly recommended watch:
Could it be a memory leak? Or simply too many animations for my ageing phone to handle?
(honestly I love SVGs for static images or at most one or two animations when used on a web-page, but if you're not using canvas2d or even webgl with a thin shim for anything more complex than that, mobile users will suffer)
Very cool though!
It's the opposite -- they are reusing the old ones.
https://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness...
Where do you feel this is likely to break down? What would a better approach look like? Is it intractable or can one have both simplicity and power? I suspect the answer is "yes" in which case OP deserves a better response.
anim_set("cx", 100); anim_set("cr", 0); anim_interpolate(ease_cubic, "cr", /val=/10, /time=/3));
etc
don't know what are you trying to achieve here
>anim_interpolate(ease_cubic, "cr", /val=/10, /time=/3)
is still declarative.
In any your example is incomplete and proves nothing because the end result should be a function that takes t and returns cy and cr. Not sure what your code is supposed to be really.
Secondly, the author explained at length what the advantages of their approach are (purity, composition, time travel debugging, ...).
I'm not sure what you're trying to achieve with your comment except trying to make yourself look smarter by deriding others.
No I'm not. Also functional programming is declarative programming (but not the other way around). If your code is supposed to be functional, it is also declarative.
I was trying to freely guess what your incomplete example was supposed to do. Maybe I was wrong, but then you didn't provide much to work with.
> The animation, where sequence of events is known exactly, is the poorest example for declarative programming.
This wasn't a competition to come up with textbook examples of declarative programming.