Some abstractions around programming

From Helpful
(Redirected from Memoize)
Jump to navigation Jump to search
Some fragmented programming-related notes, not meant as introduction or tutorial

Data: Numbers in computers ·· Computer dates and times ·· Data structures

Wider abstractions: Programming language typology and glossary · Generics and templating ·· Some abstractions around programming · · Computational complexity theory notes · Synchronous, asynchronous · First-class citizen

Syntaxy abstractions: Constness · Memory aliasing · Binding, assignment, and such · Closures · Context manager · Garbage collection

Sharing stuff: Communicated state and calls · Locking, data versioning, concurrency, and larger-scale computing notes

Language specific: Python notes ·· C and C++ notes · Compiling and linking ·· Lua notes

Teams and products: Programming in teams, working on larger systems, keeping code healthy · Benchmarking, performance testing, load testing, stress testing, etc. · Maintainability

More applied notes: Optimized number crunching · File polling, event notification · Webdev · GUI toolkit notes

Mechanics of duct taping software together: Automation, remote management, configuration management · Build tool notes · Installers



Mathy concepts, state

Invariants

In math

This article/section is a stub — probably a pile of half-sorted notes and is probably a first version, is not well-checked, so may have incorrect bits. (Feel free to ignore, or tell me)

In math, invariants are usually used to point out the concept of 'something that remains unchanged under certain transformations'

(and in the cases you care to use it, it often likes to be as broad as possible, saying that entire classes of transformations don't affect it)


This is potentially useful to

  • classify mathematical objects into groups, and name those groups
  • characterize certain objects.
say, the Pythagorean theorem is an an invariant property of right triangles
(and is still invariant under any operation that maintains the property of being a right triangle)
going a little further, Fundamental invariants of triangles


  • mention what to watch out for in more pragmatic use
Say, programmers (around graphics, geography, and more) may care to know things like
the area of a triangle is invariant under translation, rotation and reflection, but not under magnification
angles are invariant under all of those
  • It is sometimes useful to explain the contraints of a given problem or puzzle.
  • It's useful around various topology.


https://mathworld.wolfram.com/Invariant.html


In more practical engineering

In programming

This article/section is a stub — probably a pile of half-sorted notes and is probably a first version, is not well-checked, so may have incorrect bits. (Feel free to ignore, or tell me)

Invariants are expressions that do not change in value.

Often a boolean expression that should stay true, and often an equality expression. (sometimes counts, relatively rarely more complex things)


If the invariant changes, then the code is probably wrong.

In some cases, that's "things that should test as true no matter when or where I test them".

In other cases, it only matters that they are true at the start and end of a function.


Invariants are useful to describe behaviour in broad terms, describe the correctness of individual operations, to test these, and to check that during debugging.


Class invariant

This article/section is a stub — probably a pile of half-sorted notes and is probably a first version, is not well-checked, so may have incorrect bits. (Feel free to ignore, or tell me)

A class invariant, also known as type invariant (and apparently object invariant(verify)) is something that should stay true throughout an object's lifetime, regardless of its state.


This isn't any different from the above concept, just points out you can often think of an object as a sort of state machine that you may change on any call.

Memoization

In programming, a memo function is a function that remembers the output for a specific set of input parameters it has previously processed, and can answer from that memory rather than from calculation.

Using this as a speed/memory optimization tradeoff is called memoization.


It becomes effective when the duplicated calculation is nontrivial to calculate and/or when the a function is often called with the same input.


A memo function should not have any intentional side effects, or (in general) depend on any external state.


In some cases, memoization is something from the language/syntax itself, particularly in more functional languages (e.g. haskell), but in procedural language it's often done with a more explicit cache, which requires some management, e.g. to keep the cache of answers in check, and possibly even be smart about retaining entries that are requested more than others.

Side effects

This article/section is a stub — probably a pile of half-sorted notes and is probably a first version, is not well-checked, so may have incorrect bits. (Feel free to ignore, or tell me)

In computing, a side effect tends to mean altering some state outside the environment in consideration.


You may see this most often in programming, where e.g.

  • a function that can only refer to its own local variables can never have side effects (...on other code) - (see also pure function)
  • a function that alters global state may easily have effect on other runs of that same function -- or on anything else that happens to rely on it.
  • a function that shares state with others by design
alters shared state tends to be more intentional, done with



More practically, you usually talk about side effects to talk about when you share state, particularly when you unintentionally share state, and particularly when this can lead to issues like race conditions.


...and also when intropducting the abstractions we introduce to avoid such issues.


Such abstractions include

clearer/singular owners of state,
exclusive access to state,
or e.g. concurrent data structures, which exist to tame such issues.


Side effects are not necessarily negative, in that if there is an implicit/explicit contract pointing out how to deal with them. For example, one approach to concurrent data structures exist to have things work predictably even in the presence of side effects.



https://en.wikipedia.org/wiki/Side_effect_(computer_science)

Idempotency

This article/section is a stub — probably a pile of half-sorted notes and is probably a first version, is not well-checked, so may have incorrect bits. (Feel free to ignore, or tell me)

In most contexts, the point of an idempotent operation is that it has no additional effect if it is done more than once.


In general, in machines

For a tactile example, consider an industrial machine has an separate 'on' and a separate 'off' button.

Regardless of the state before, if you press the 'on' button, it is going to be on afterwards
Regardless of the state before, if you press the 'off' button, it is going to be off afterwards
...also regardless of how often you press that same button afterwards.


In comparison, the power button on most computers toggles (and is only a request to change - unless held for 4 seconds as per ATX specs)

...so you won't know entirely for sure about its state afterwards
so it's not idempotent.
(the fact that that's because action depends on the current state just happens to be the main reason, not a defining part of this non-idempotency)


Stoplight crosswalk buttons are idempotent (with few exceptions)

in that you can press them more than once, but it'll just stay in 'requested' mode until the system acts on it.
(and sometimes nullipotent, meaning the light will schedule you regardless of whether you pressed, and it's there just to make you feel in control)
  • elevator call and floor buttons are idempotent (with few exceptions)
...even if people like to hold on to their magical thinking about special modes that make it go faster


In math, in computing


In math and computing, you're saying the output doesn't change if called more than once (with the same input parameters).

For example

  • anything that makes no changes
e.g. HTTP GET, HEAD, OPTIONS, TRACE
though people do abuse GET (e.g. allowing sets from GET requests, not just POST, is moderately common)
  • adding or removing an item to a set
e.g. HTTP DELETE
  • various string operations, e.g. uppercasing a string

...and may more than we usually don't name specifically.


Such a property happens to be useful, in design, and in talking about design, in particular APIs, because you're typically modeling what should happen on the other end, and are usually not inspecting or policing every step.

Say, it's really useful to know that if an identical operation is sent to a server several times, it leaves the server in the same intended state.

Around updating state, this can e.g. simplify complex state management to 'just retry until is says OK'.


For the HTTP examples,

It's just defined that way so that HTTP clients can assume certain things.
it's not that you can't break that, by mistake or even by choice. In particular GET is sometimes not idempotent in practice.



Around parallelism, this relates to things like reentrancy


Scope and namespaces

Encapsulation

Exceptions