HackerWhat can a language express, and what can it guarantee?
Factorial can be written without naming the function. That trick raises a harder question: if every program must terminate, can unrestricted recursion be allowed? Take that distinction into slides, libraries and language extensions.
Questions in this reading · 10
- Can anonymous functions recurse and still guarantee termination?
- Can presentation slides perform general computation?
- Can libraries grow a language?
- Does concise array notation make a language easy to extend?
- What does a recursive call leave behind?
- When does an argument about rules become a physical conjecture?
- Does knowing the rule give you the millionth step?
- Why did the branch we skipped start recursing?
- What changes when “this program” becomes “every program”?
- Two cut branches, one successor to evaluate
Can anonymous functions recurse and still guarantee termination?
Weirich derives a fixed-point combinator so a function can recur without a name. Wadler approaches the same operator from the other direction. Adding unrestricted recursion gives up the termination guarantee of the simply typed calculus.
Compare original passages and timestamps · 2
the function y calculates the fixpoint of an improver function.not using What's called the fixo operator that is unlimited General recursionCan presentation slides perform general computation?
Compare a deliberately minimal interpreter with a surprising construction inside slides. The decisive question is which operations the system can express.
Compare original passages and timestamps · 2
you only need these three lines that's turn complete actuallyessentially imitate any transition function of any other touring machineCan libraries grow a language?
If libraries can express new abstractions in ordinary code, the core language can grow through its users. Compare the facilities needed to make those extensions feel native.
Compare original passages and timestamps · 2
the new words defined by a library should look just like the primitivesthe idea is that distributed programming should just be a libraryDoes concise array notation make a language easy to extend?
Array operations can express a great deal in a few symbols. Integrating a new operation into the language raises a separate question about its rules and conventions.
Compare original passages and timestamps · 2
you'll notice that it contains no explicit loops and no temporary variablesnew words defined by the user do not look like language primitives at all.What does a recursive call leave behind?
Work through 3+2 on paper. One definition leaves an instruction to add one after a call returns; another moves one unit between two running arguments. Both can call themselves, but only the first builds up pending increments. Fibonacci adds a different cost: separate branches can ask for the same F(k). Memoization turns later requests into lookups while preserving the dependencies of the first computation. Try drawing two diagrams, one for pending work and another for distinct subproblems.
Passages and timestamps · 2
There's nothing special about the fact that the definition is recursive that leads to a recursive process.So I count how many different subproblems do I need to do?When does an argument about rules become a physical conjecture?
Penrose distinguishes following rules from understanding why they yield truths. Later he suggests gravity might alter the description of quantum mechanics. Even if the first passage motivates a mathematical question, the second still needs independent physical tests. The two timestamps mark a change in the subject of the argument; taken together they do not prove that a program cannot be conscious.
Passages and timestamps · 2
understanding why the rules give you truths enables you to transcend the rules.gravity affects the structure of quantum mechanics too.Does knowing the rule give you the millionth step?
Rule 30 has a short update rule. Wolfram recalls running it to discover the unexpected pattern that grows from a simple start. In another interview he sharpens the question: specify an output at step one million. Can most intermediate work be skipped? Running the rule supplies an answer. The intricate picture neither constructs a shortcut nor proves that none exists. If you spot a pattern, name the columns and initial states it predicts, then try positions that did not help you guess it.
Passages and timestamps · 4
from very simple initial conditions, it makes really complicated behaviorno intuition, just experimental scienceyou can run it for a million stepsI don't have to go through anything like that computational effortWhy did the branch we skipped start recursing?
Turn an if into an ordinary selection function. On the left put the answer for the base case and on the right put one more recursive call. In David Beazley’s Python demo both arguments are evaluated before selection, so recursion has already started. Wrap each computation in a function and invoke only the chosen one. A print at the start of each branch reveals the different work performed by two expressions that seem to make the same decision.
Passages and timestamps · 2
it goes down both paths. And it turns out that the second path just explodes in infinite recursionyou're basically delaying the calculation to some later point in timeWhat changes when “this program” becomes “every program”?
Bernstein describes a verification task that succeeds: inspect the actual machine code emitted for a sort and establish the specified property for that implementation. This removes one assumption about the compiler. The halting problem ranges over arbitrary programs and inputs. Assume a decider that always answers, build a program that does the opposite of the prediction and feed it its own description. Either answer defeats itself. Name the program, the property and the range of inputs before comparing these two results.
Passages and timestamps · 3
verification isn't going to rely on some compiler being correct.I make it loop forever without ever stoppingEither way we get a contradictionTwo cut branches, one successor to evaluate
Different cuts in Hackenbush can leave equivalent positions. Evaluating successors recursively then permits reuse. The equivalence must preserve whose turn it is and which options each side has. Merging pictures merely because they look alike could remove the move that decides the game.
Passages and timestamps · 2
these two one positions are essentially identicalanother huge perk of our recursive definitionsTry it on your own example
Before adding an expressive feature, name one guarantee it might cost you.