program
Code written in a specific programming language, intertwined with implementation details and language-specific constructs, as opposed to the abstract algorithm it implements
As defined in Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
Where it comes up · 1
- Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport9 claims
Most important claims · 9 of 9Search all claims for “program” →
- Writing an instruction manual before coding forces the developer to discover design flaws and necessary changes—when writing the LaTeX book, Lamport discovered things that were hard to explain, requiring him to revise the design.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- The origin of the time-sharing problem was that computers were expensive and fast, so they could be used simultaneously by multiple people whose programs would compete for shared resources like printers, requiring synchronization to prevent garbled output.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Understanding a concurrent program requires identifying invariants—boolean-valued properties of the state that, if true at each step, guarantee the output is correct—and reasoning about invariants rather than behavioral sequences reduces complexity from exponential to quadratic in the number of processes.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- A state machine is defined by its state and a next-state relation: each command takes the system from one state to another, with correctness determined by invariants—boolean-valued properties of the state that ensure correct output regardless of what happened in the past.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Computer people and programmers are 'really hung up on languages,' inventing languages and believing they improve thinking, but for understanding and reasoning about systems, mathematics beats any programming language.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Edsger Dijkstra invented the formal theory of concurrent programming in a 1965 paper by introducing the concept of critical sections—pieces of code that at most one process can execute at a time—as a way to structure programs as collections of semi-independent tasks that must synchronize.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- An algorithm is more abstract than a program—it can be implemented in any programming language, whereas a program is concrete code in a specific language; thinking in terms of algorithms rather than code is crucial for concurrent systems.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- When describing algorithms, Lamport talks about variables that can hold any integer, not just finite-precision integers—a deliberate abstraction that simplifies reasoning, not a complication; infinity was introduced into mathematics to simplify arithmetic, not complicate it.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Lamport submitted a simple two-process algorithm to CACM in 1972, received a letter pointing out a bug, and realized that concurrent programs are hard to get right and require proofs of correctness—this rejection motivated him to develop the bakery algorithm.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport