TODO: note the need for functions & stack is incorrect; actually we don’t need a stack per se, and certainly don’t need functions! we just need any growable structure to store values so that register clobbering doesn’t lose output information.
-
programming is divided not into "code & data." that is inappropriate because code is data (as are all things) and code can connote data or instructions (as code means "data encoded by an encoding"). honestly code & data are the same. code & information is more appropriate: data is encoded information (data being used as a mass noun like information.) what people really mean is that some data are instructions; they would say that
[1,2,3]is data and thatconsis code. then iscons 1 [1,2]code? it evaluates to a datum. ah, i suppose that people mean that code is data that can be evaluated. but what is evaluation? typically it’s β-reduction: simply a re-expression.cons 1 [1,2]is equal to[1,1,2]; the only reason that they’re presumed different is because non-algebraity is assumed i.e. thatcons 1 [1,2]is an an expression (relation of abstract symbols), but merely a parameterized unidirectional map for rearranging data, including arithmetic. thus "code" "expressions" are treated as though they aren’t data! they’re treated as the result of their β-reduction! thus "functions" as commonly used in programming discussions are just syntactic sugar! they should be called reductions, not functions. the meaning of procedure, subroutine, and function varies by context, but they’re all the same at least up to scoping rules; namely most commonly some or all of functions inputs are explicitly noted and are called formal arguments, and procedures aka subroutines may be defined of any vars in its scope, which may include any formal args or not. state means any arguments outside the formals. the flaw of distinguishing functions from procedures is the assumption that there’s meaningful difference between formal args and non-formal ones. such distinction exists only because functions are arbitrarily (and senselessly) defined by only one statement in one place, or in multiple places (e.g. haskell) but formals are static. remove the constraint/association between a function and a formals vector, and remove scope, and now you have functions being a set of sequences of mutations of arbitrary subsets of program state. now that functions are found to equal procedures, they’re just state manipulations: changing a physical value (e.g. one in ram or filesystem), or re-expressing an abstract value (e.g. the cons example.) the physical changes cannot be expressed by abstract re-expressions, but only concurrency primitives must be expressed by physical changes/values. because most programs are re-expressions of abstractions, using only abstractions that emulate physical changes is quite stupid, needlessly limiting. if you have symbolic expressions, then use them as such like a computer algebra system would! reduce & rearrange the symbolic expressions, and only after that should you bind free vars to values for re-expression! we see this as programs re-expressing to simplified equivalents; then seeing those programs becoming less abstract when given non-abstract inputs e.g. a datum literal; in this case the program is an abstract re-expression that is applied to a non-abstract value to an outputs that is related by the program to the inputs (the program is seen as a relation of inputs & outputs.) however, if the inputs or outputs are abstract, then the program is just a system of constraints that is further constrained by the inputs (the inputs, being abstract, must be constraints/predicates: qualified/constrained symbols); thus specifying the abstract inputs or outputs is a constraint system endomorphism; the new system can be reduced and and solved for a set of constrained relations of inputs & outputs. we see programs then as constrained systems of variables, where freeness or boundedness of any vars is a matter of representation. the system may contain non-abstract values called constants e.g.2; a constant is formally defined as a constraint that, when joined with any other constraints, has the same value e.g.∀p 2 : p ⇒ 2.-
stack langs, which haven’t λs, degenerate λ-calculus and procedures into a single model: stack programs are just sequences of mutations of implicit state. by not having variables they appropriately describe mutation sequences without misleadingly resembling symbolic expressions.
-
reductions & procedures will be henceforth known by the single concept called mutation sequences
-
-
mutation sequences are often useful but are a poor universal model of computation! they should be thought of as macros [text editors, microsoft excel]: playing back a mutation sequence. symbolic expression endomorphisms is the only sensible way to write programs, as it’s the only sensible way to reason about math or logic. why does programming, which is strongly associated with logic, math, and grammar, not enjoy such an old & obvious technique, instead having only reductions/mutations? i suspect that the popularity of turing’s machine encouraged reasoning about mutation sequences rather than programs as abstract algebraic expressions. functional programming seems to try to take the turing model in the direction of algebra, but of course the two models cannot be simultaneously used, though a turing machine can be used just fine to implement an programmatic algebraic system (pas.) bottom line: decent programs must be constraints/relations of symbols or constraints/relations—
type Rel := Pred({Symbol | Rel}), which sees predicates as n-ary, parameterized by a set of symbols or relations; however, note that, as with any recursive structure, it may be flattened, here into a set of constraints e.g.and(even?(Y),>(X,4))to{even?(Y), X > 4}(or flattening a recursively defined tree into a list of branches.) this is what prolog does; the program execution then, as with reductions, is done simply by specifying inputs (or, unlike reductions, any subset of inputs or outputs may be given.)
-
got it! the solution to making things good in a reductionist paradigm is to have literal data that represent actual reductions; this way the data can be manipulated and thus have morphisms across abstract instructions. this implements a logical model by a reductionist model. think of haskell’s foldl/Fold typeclass or the tuple (a,b) to represent the series from a to b; let’s say that i want to intersect them. though it’d be painful to work with the lists that they represent, but finding the intersection of (a,b) & (c,d) is easy! also stuff like filter not doing a whole sequence, but instead adding the predicate that it check any given single element against a predicate when evaluated, backtracking/continuing if it fails. so this is just virtualization and/or non-strict eval. as another example, the identity matrix can be encoded in factor as = 1 0 ?. combining filters is just ANDing (product of) the predicates.
-
consider how in sql everything is in a relation, and how plurality is.
-
identify cata/morphic programming as a specific version of declarative programming
-
identify technically what a catamorphism is and maybe identify a better name than cata/morphic programming
-
stack, unlike func, relates data implicitly in a sort of if-then pattern; the stack being e.g.
a b ctells us that we expectcto be used in some computations, thenb, orbas an argument tocfor some computations; and afterb&care used, thenamay be used; or thatb&amay be are used together i.e. are related. it also tells the order in which these data will be considered; this expectation makes the program easier to follow when read, as opposed to the func (generally binding) model, where vars are bound, but there’s no expectation for how they relate or when they’ll be used. this is useful if the relations of these arguments are complex, but that’s rare, and suggests that the data should be in a data structure, all of which should always be stored in a relation. also an ast may appear complex, but its stack reduction reveals that the ast could’ve been written more elegantly; however, only the stack model forces a reduction and thus forces elegance by non-redundancy. such reduction can be done by the functional model, but is painful because of: 1. the need to name everything; 2. the need to useletorλ, both of which require crufty & difficult-to-refactor syntax nesting and introduces scope—much worse thandup/over/pick,bi, &c. we thus see that the functional model is cruftier because of its mandatory explicitity whereas the stack is terse and easier to work with because it’s implicit: not just that arguments are implied, but that the boundary of arguments is implied. see, unlike the functional model, the stack model is concatenative; it allows splitting a program at any arbitrary point. this makes program composition much easier than function composition! this implies that multiple inputs & outputs can be used together e.g.a b g h→a c d hwherehusesa c das its args. the functional model cannot express this, because args are not related to each other. furthermore, in the stack model both inputs & outputs are related! they’re strictly separate in the functional model. func suffers from needless installment of ad-hoc rules. the relational model relates inputs & outputs, but does not distinguish one set from the other; thus rel is superior to stack b/c it lacks the needless ad-hoc rule that separates inputs & outputs, despite both being implicitly inputs on the stack.
tl;dr: relational programming is the only sensible way to program.
loops, reductions/folds, catamorphisms, are all the same: an initial state that ultimately ends at a state. it generalizes map (obviously, since we know that foldr generalizes map.) thus the catamorphism is the same as reduction; we can call reductionist programming cata/morphic programming (since generally those programs can be non-cata morphisms.) the morphism is defined without its dual being implicitly known.
one of the the problems with the funcmodel is scope: that each function has only its inputs in scope! this is a variety of the nesting problem: that each thing is unaware (and cannot compute on) things in the set to which the thing is an element, or sets containing that set &c. this is why flat indices are important: no nesting means no scope! this being said, nesting does not necessarily imply scoping! there are variable scopes too, e.g. picolisp’s shadowing model, which is akin to the stack model, where elts closer to the top have higher precedence but all elts are accessible. regardless, we must remember, when designing or reasoning about related/structured data, to never make other data unavailable, though ordering data by preference of use is fine—again, as shadowing does, except that i’m saying that we should be able to access variables being shadowed—not just the shadowing variable. nested map is a common instance of this problem: inner subprograms cannot access the outer superprograms. the common solution is to create new inputs or outputs and use them in complex passing schemes.
the stack model generalizes the applicative model to support:
-
inter-application mutation e.g.
(h (f x) (g y))isx y f [ g ] dip h, but betweenfapplying toxandgapplying toy, any operation can be inserted, and the stack can be manipulated in any way that makesyavailable tog, and the result off xandg yavailable tohat the time thathis evalutated. the ast can be traversed or flattened depth-first or breadth-first. -
multiple function outputs (which i think is called a multifunction?)
the "black box" function problem ([extent of] subprogram interaction by sharing state/information/data)
can factor’s model (dynvars, stack, locals) help the following functional problem: f : a → b, g : b → c, h=g⚬f, but i want access to b without refactoring h? with functions you’d need to split h or modify it to inject b into its codomain. one solution is simply writing very many small inline words, so that arranging those words is easy and terse; thus we get expressivity without sacrificing terseness. i know that this isn’t a problem in prolog because prolog doesn’t define dataflow pipelines. consider pipelines as paths through a graph. prolog defines vertices and valid edges, but says nothing about particular paths through the graph! instead it derives, much like hxt [haskell] semiring arrows, a set of paths from vertices satisfying initial conditions to the query’s terminal result set of vertices. contrast with non-declarative langs, which only define pipelines of only existentially qualified variables, lacking universal quantification. also, all pipelines are just reductions. this is seen by variables being not global. they’re all local in a bunch of nested scopes or kept in various positions on the stack; either way they’re kept at arbitrary & relative ordinal or lexiographic addresses. global vars …. it’s basically (or exactly) the same problem as functions being black boxes, unmodifiable i.e. not truly first class since their definitions (arrangements of "variables") are treated differently from how they’re used (application only). black-boxing loses information unless the function preserves all original data. no such analogue exists in logic programming. i quote "variables" b/c they aren’t true variables; they’re symbols that represent values rather than being themselves computable. this is seen by x == x not being immediately obviously true to the computation engine, but is instead only known at runtime by replacing both `x’s by whatever value they hold, then testing equality against those objects.
solutions:
actually, factor, since it quotes programs instead of using black box functions, allows you, so long as your program is quoted, to consider it as a sequence, testing on words ond manipulating or inserting words. what’s more, this is much easier for a linear structure (stack) than a recursive one (ast.)
cata/morphic programming defines only specific edges; there are too many possible edges to specify them all, as silly as trying to specify all the numbers existentially rather than universally. really, trying to define any program is like that; it’s sensible only to define a space (graph) by which a program can be identified (as a path.) any non-flatness makes structure difficult because it makes looking difficult. the only decent way is to use relations, a generalization of indices. to solve the black box problem, we basically have to split a path at some points. however, because program state changes as paths are traversed, there must be a way to access certain substates at certain points of execution (vertices.) the problem with fns is that the define a closed set of inputs (and outputs), and definitions are in one place only, whereas declarative clauses are ad-hoc implicit relations of variables in multiple places, much like how factor generic methods are defined in multiple places. a ⇒ b says nothing about how a relates to other vars, whereas in a function f(a)=b defines f only for a; if i want to define it for other things too, then i need to add those to its formals, then refactor its body to account for the new variables in relation to the old, where the relation is ordered, meaning rearranging nestings of dataflow! the openness/implicity and decoupling of predicates makes them vastly better than functions! the decoupling is in the form of both multiple sites of declaring relations and of the relations being not nested.
consider many functions that naturally combine together vs one large function with multiple options. the latter is less maintainable because it’s a black box (unmodifiable, non-partitionable). it, like all programs, can be factored [partitioned into an expression of free & bound symbols] by any predicate or symbol. given that, why should many fns be different from one? we see a sort of infinitesimal calculus here where dp is the smallest possible program—a primitive. the tradeoff (given how programs have been structured) is many small programs which is flexible but requires syntax to label subsections of a program vs which is inflexible, central, convenient [how/why?]. yes, that’s the solution: dispense with functions (just like we dispense with programs [defined by entry points]) and instead have only code, but, for convenience, we may label any partition of programs. this requires programs to be not reductionist, but actual logical objects. this can be done textually in a statically scoped language, but it more powerful when programs are considered logically by the language without imposing any static scoping constraint. actually, even reductionist picolisp is somewhat without the black box fault: functions can inherit state from other functions by dynamic binding! i can define a function that runs differently depending on which function is using it! that’s pretty cool, but limited: functions must be nested and inheritance is one-way. you may say that the outer function already knows what the inner function is, and so can choose how it interacts with the inner one e.g. setting certain vars for the inner function’s use, since the inner function is hard-coded in the outer function’s body, but that’s wrong simply because the inner function may be variable (e.g. taken as a parameter or inferred from a type class.) again, this is impractical in the functional model, since therein all inputs & outputs (i.e. all relations among functions [[sub]programs]) must be explicitly specified, again excepting variadic functions (available only in non-statically-typed languages.)
TODO: words (generally scoped evaluation) can leave values, allow "dipping into" inner scopes. maybe scopes or mutation sequences can be dynamic, indexed, rearranged or smth.
| dataflow | prolog |
|---|---|
paths |
graph |
nested |
flat |
directed |
undirected |
bound traversal, unconsidered structure |
bound structure, free traversal |
explicit paths |
implicit edges |
existential |
universal |
ad-hoc |
symmetric |
morphisms |
rules |
imperative (instructive/actional) |
implicative |
whitelist (start with nothing then add things) |
blacklist (start with everything then add constraints) |
symbols are definite pronouns |
symbols are indefinite pronouns |
horn clauses can be nested, but that’s merely syntactic sugar, a lossless compression of the ordinary notation.
having no distinction between data & functions, naturally coupled with words having stack effects instead of arities, and that functions are not first class, but instead that, more generally, quoted programs are data passed around, makes program composition very easy, whereas function composition is an enormous pain in the ass. the word/stack model frees us from concern about which kinds of functions to pass around e.g. a functional paradigm would distinguish between a → b and (c → a) → b` whereas a stack paradigm can define a word with effect ( a — b ) and not care at all how a is arrived at. this is true of unary functions, but basically in a stack paradigm a → b → c is effectively b → c. though application and currying try to achieve such elegance, they generally fail because there is a distinction between a → b → c and b → c, or a → (x → y → z) → b. in a stack lang, just set-up the stack to have the correct args when a word is evaluated, and quote words that shouldn’t immediately evaluate. now certainly we can have the effect ( a x y q: ( x y — z ) — b ), but it’s just as well to say ( a x y q — b ). i’m still not communicating the exact elegance that stack langs permit us. TODO: do it. basically it’s easier to pass around a stack than each arg manually, especially when the stack is implicitly passed, and quoted programs generalize currying, composition, and first-class fns.
TODO: reduce redundant statements.
firsty, any reductionist (cf declarative) model requires the programmer to trace through state changes, whether it’s data mutation through functions, or a variable mutated in place, or a stack mutated throughout word application. they’re all the same. the declarative model does not require this because facts are declared universally instead of per datum. the reductionist model defines things derivative of other things, which is a variety of directional relation between things (directed edge between two data), but the declarative model declares only undirected relations among things (constrained set of data.) the directionality is what significantly makes the reductionist model more limited; it cannot infer/produce, only reduce; this makes sense because produce & reduce are duals while an arrow a→b is dual of arrow b→a. a-b = a<→b; an undirected edge is equal to a bidirectional edge. what is produced is the most general system still satisfying known constraints; this contrasts with reductionist programs which are not endowed with knowledge that enables them to generalize their program i.e. it’s not considered to which sets [math, abstract structure] each datum belongs.
regardless of which model is chosen, we want for code to be terse. in a functional model, this means terse recursive functions; in procedural programming this means a terse loop; in the declarative model this is seen as a set of facts. again notice the lack of ordering in the declarative model. ordering things is perhaps the greatest trouble that the reductionist model imposes. actually, order is the only thing that separates the reductionist & declarative models! generally taking arrows to commutative relations implies relations instead of functions; relations can be interpreted as symbolic functions. symbolic functions reduce not by application but by unification (application (intersection) of constraints (predicates.)) a function can be reduced to another function through partial application, which is a variety of enforcing constraint, but a function does not, in the reductionist model, imply a set; we cannot use set-theoretic operations on functions or define higher-order functions like function inverse once for all functions.
the stack is elegant for β-reductions where data are incrementally added into the stack near related data, where related means that they’re arguments to a common reduction (e.g. in g(a,f(b,c)) a is still near b and is expressed in factor as a b c f g.) another example is f(a,a) i.e. a dup f; expressed pointfree in factor as dup f but cannot be pointfree in λ-calculus, which can express it only as \a → f a a or in terms of a combinator dup f = \a → f a a, by which dup f is still dup f and pointed is dup f a e.g. dup (*) 4 in haskell.
the stack is not inelegant when data are related to many other data; the stack is still fine for this, but with an inline pointed mutation of the stack. the stack is inelegant if one must use only pointfree words. the same is true of applicative languages, too: an applicative language without lambdas would be painful to use. of course, this means no definitions since those are just lambdas. thus a purely pointfree stack lang is equivalent to a pointfree applicative lang. being pointfree does not even have to do with programs being concatenative; being compositional is what makes them concatenative. thus any language all of whose functions are composable with each other is concatenative. the only reason why stacklangs are concatenative but applangs aren’t is that applangs only define function composition as a function of number of inputs or outputs excepting lisp, where inputs & outputs can each be considered as lists. we can generalize from lists to any data structure, abstract data to abstract expressions, thus leaving us with an abstract structure, and generalize stack or ast evaluation to any traversal of the abstract structure. this is the general description of a program. recall that all structure is specified/defined exactly by constraints; thus prolog or any other form that uses only constraints is the most general programming model.
the stack is very apt for concatenative (monoidal, associative, ordered/sequenced) programs, not relations of things (commutative "programs" i.e. fact sets.) the stack is preferable for reductionist programming but not logic programming. it seems…that the stack being pointfree is not in competition with logic programming’s use of symbols, since their meaning is different: in reductionism symbols are value placeholders but in logic programming symbols are predicates required matter. one could, however, use a stack to define a pointfree predicate combinator e.g. unary combinator even [ > 5 ] bi@ and or binary even [ > 5 ] bi and, which relate variable symbols to given relations. so yes, the stack can be useful for pointfree relation encoding. that being said, to make any stack program pointed all one must do is add literal data (namely symbols) e.g. x y even [ > 5 ] bi and for even(x), >(y,5). this is an advantage over prolog, which does not have such a simple relation between its pointed & pointfree relation expressions. to instantiate a symbol one would say e.g. 5 x set instead of x is 5. the stack is, though flat, stateful & ordered, which makes it more complex than a flat fact set, which makes it more difficult to refactor & consider but gives a terser encoding of related facts. whether the stack is worth using for expressing logic programming should be determined by actually trying it in practice. certainly, as one of the most important coding facilities, one should be able to easily factor-out a common form whenever it’s discovered that multiple things match it, for certainly c(a b) is decomplected and terser over (ca cb); most importantly, though, is that it partitions distinct information, which allows us to consider more & simpler concepts, which improves our understanding & reasoning of the encoded situation.
well,…what’s odd is that, despite logic programming using a fact set, its facts are still ordered syntax! given that prolog predicate parenthesis are redundant and commas should be replaced by whitespace—rel(a,b,…) [:- …]. is better as rel a b … [:- …].—but are not redundant when expressing nested relations e.g. rel1 a (rel2 b c) [:- …]., we can use that the stack is a better way of expressing nested relations—b c rel2 a rel1 to express relations. then the optional implication clause is no longer any more or less optional than nesting relations inside other relations; we either put it on the stack or not, before passing the accumulated predicate to the . word which shall, as in prolog, add the predicate to the global set: b c rel2 a rel1 :- … . i specify :- between the head & body as a delimiter, since in head1 … headn body1 … bodyn :- there’s nothing to separate the head from the body, since they’re of the same form and would compose in the same way. putting the :- between them (to effectively create a curried :-) is terser than enclosing each of head … & body … in delimiters. so the stack is the best model for expressing horn clauses. because horn clauses are all that prolog programs are, this implies that the stack is better than prolog’s horn clause syntax. given that the stack already well encodes reductionist programs, and that the only things needed for horn clauses are symbols (which exist in factor as defined by SYMBOL:) and an [implicit] global state for the fact set (again, expressable by set-global in factor, or by leaving it at the bottom of the stack, adding one rule to it at a time), factor can easily do logic programming even more plainly than prolog without even creating special syntax! the only remotely difficult logic paradigm implementation task is the traversal/unification of the fact set, needed to satisfy queries.
anyway, arbitrarily related data sounds like a textbook use case for relations, which are unordered except by predicates.
consider, though, a notation (a …) for a list/set, which may parameterize a symbol i.e. be bound in the context in which the symbol is being considered e.g. do-action(i,value(i,t)). this is similar to lisp function parameterization mixed with prolog symbol unification/instantiation. we can re-express the notation: do-action (i value (i t)) → (i (i t) value) do-action. with a stack model the parenthesis are redundant; in the stack model it’s i i t value do-action, which is expressed as a pointfree word: : thing ( i t — * ) [ dup ] dip value do-action ;. stacks can express relations (not strictly operations/functions [reductions]) just like prolog; however, their one deficiency is that stack words must have definite arity (number of parameters); this is unlike a logical language, wherein parameters may remain unspecified, which retains whatever meaning they had. the stack is appropriate when data’s relation can be encoded by order (being sequenced on the stack.) logic programming is inherently generally unordered, even if encoding particular relations as sequences is common. i currently conclude that stacks are an encoding superior to applicative but somewhat specific, and so should be used as a convenient encoding for relating data, but not as a general model, at least until a variadic word parameterization scheme is identified. i suppose that one solution is { pred … } word where each pred is a constraint [relation] on symbols that is assumed for word. one would then want to remove some constraints for other parts of the program, but this is better expressd by a flat set of horn clauses: word(p1,p2) :- b. word(p1) :- a.. the clauses are tried in order; the more specific clause is tried first; if instead p2 is free or not meeting a specific predicate then the unary predicate is tried. this defines separate contexts somewhat independently of each other. ideally they’d be entirely independent, encoded as clauses whose order does not matter (as in datalog), which would be enabled by the interpreter automatically ordering clauses by specificity i.e. their information content. therefore though the stack is sometimes a terser encoding than horn clauses, it’s probably best to forgo the stack, preferring the simplicity of using only horn clauses, which are simple, stateless (no stack state), and independent/flat/non-complected, or rather than their complexion (relation) is implicit and not strictly considered e.g. a rule that always fails but never must be considered in order to unify another rule’s implication will never affect a unification.
the fact that factor (unlike joy) is impure is very useful; things like stateful cond enable us great power in relating subprograms (through state) while requiring little cruft to make the subprograms independent. this being said, functions are still useful. that being said, we can interpret words as functions and still write recursive functions like we would in any funclang simply by using inline recursive after a word definition. thus factor (impure stack) elegantly generalizes the functional model.
an ast clearly corresponds to the idea of β-reduction to a single outcome, as a tree has one root. a relation connotes no prescribed end value; its data are not related by the structure, but instead many permit many relations as predicates on their values. a stack still reduces to emptiness by applying words to other words, eventually ending when the stack is empty.
this all being said, remember to use the stack how it should be used! direct translation from an applang to a stacklang is generally inappropriate, since the original function was not made for the stacklang; consider the following translation from scheme to factor:
(define (limit/slippage amt slippage) `(amt limit ,(+ (car slippage) (* (sgn amt) (cdr slippage))))) : limit/slippage ( amt slippage -- x ) [ second over sgn * ] [ first ] bi + "limit" swap 3array ;
in the scheme version, slippage is a list because it is expected to be returned from another function, and returning in a cons pair is easier than returning multiple values, since, as a language constraint, multiple values can only be used inside a let-values clause, which is syntactically crufty, especially if not all values will be used. if the whole program were coded in factor, then the following would be appropriate:
: limit/slippage ( amt slippage1 slippage2 -- amt x lim ) swap [ over sgn * ] dip + "limit" ;however, at least for this function, it’s more sensible for the inputs to be given in a better order:
: limit/slippage ( slippage1 slippage2 amt -- x amt lim ) [ sgn * + ] keep "limit" ;it’s unknown but considerable whether this order is so appropriate for other words that may use these inputs. the core of the program, [ * + ] dip is much better than (λ (a b) `(a ,(+ (car b) (* (sgn a) (cdr b))))), and still better than (λ (a b c) `(a ,(+ b (* (sgn a) c)))).
|
Note
|
this shows keep as effectively moving the evaluation point down the stack; complementary words like over move it up the stack.
|
as it turns-out, a tuple rather than an array is ideal for this: SYMBOL: limit ; limit >>type dup >>amt sgn * + >>limit. tuples are a good accumulation pattern that doesn’t concern order, which frees one from stack shuffling. hash tables and other set-like data structures provides the same benefit.
another nice thing about the stack is its flatness; whereas in applicative languages we must either nest or bind, in a stacklang we just sequence operations. consider
(let ([zs (for/list ([x (or xs (in-naturals))] [y ys])
(g x y))])
(h zs) ; indentation creep!or
(define zs (for/list ([x (or xs (in-naturals))] [y ys])
(g x y)))
(h zs) ; no indentation creep, but we had to bind to arbitrary symbol #'zsor
(h (for/list ([x (or xs (in-naturals))] [y ys])
(g x y))) ; still indentation creep! without indentation or newlines, nesting still creeps-in!vs
[ [0,inf] or ] dip [ g ] 2map
h ! neither senseless bind nor nesting, so no indentation! never indentation! even `if` can be expressed flatly!just to make production-sized codebases of applicative code syntax manageable we need to break into multiple functions, binding clauses, or indent into enormous chunks of code! this is where we clearly see that concatenative langs can be split anywhere, whereas complex monoliths of composed functions can be split only in certain places while retaining readability or sensability! they must be carefully rearranged like a ship in a bottle. furthermore, as functions are composed and symbols are needed for their binds just to keep them in scope, we’re forced into producing a glut of symbols, some of which will be used only once (which would be ideally tacit), or some in many places (ideally non-tacit), and many of which will have not descriptive names or will need to be shadowed because they describe the same thing but at different stages of computation. that’s a confusing mess!
apl is applicative but does not really suffer this problem basically because it’s terse, has limited arity, and features combinators, so large programs are 1-liners, which we can do in other langs, but they’re usually unreadable there, and most langs don’t have combinators. even if they were to support combinators, their support of multi-arity (or even more complicated, also supporting kwargs & optional args!) coupled with the inflexibility of functions (fixed args) means that very many combinators would be needed, and many would be similar to each other, which is inelegant. also:
-
apl programs mostly read like stack or monoidal programs: as unilateral continuous modifications of program state
-
programs can be split anywhere without affecting meaning (whitespace is not part of the language)
-
when binds are desired, apl uses non-nesting bind form
←likedefinein the 2nd of the above examples, unlikeletin haskell or scheme, which use indentation or parens respectively to denote scope
(f (if p
a ; but also make this whole expression return #t
b)) ; return this to f but make this whole expression return #frefactor into
(let-values ([(r1 r2) (if p
(values a #t)
(values b #f))])
(f r1)
r2)this is the functional style. concatenative/stack gives the perfect solution: p a b if* g becomes p [ t a ] [ f b ] if g h where h is a binary function whose boolean argument tells which branch was taken. we still put a or b on the stack for f, but after f ( x — ) uses it for side effect, t or f remains atop the stack, and thus effectively becomes the whole segment of code’s return value.
h / \ f g | | x y
can be, in a stack lang, equally interpreted as h(f(x),g(y)) [app] i.e. x f y g h [stack] or, assuming h as if, then f & g would be program branches. actually, this can already be done in any applicative language; it’s just that in a stack lang managing variables across branches is easy b/c they’re all just on the stack rather than needing to manage multiple names & scopes.
stack languages are basically functional mixed with mutative but with implicit, ordinal state rather than needing to name state(s) then explicitly reference it/them by name(s).
here’s a real-world example of some racket code that i had:
(define pts (map (match-lambda [(cons y xcs) (cons y (sort xcs < #:key car))])
(sort (hash->list (let* ([range (let-values ([(min max) (min&max < vs)]) (- max min))]
[h (if (negative? h)
(min (abs h) (exact-ceiling (/ range num-dots)))
h)])
(for/fold ([acc (hash)]) ([v vs] [x (or xs (in-naturals 1))])
(let*-values ([(y rem) (quotient/remainder (- (exact-floor (/ (* v 3 h) range)) 1) 3)] ; y=0 is bottom row
[(char) (hash-ref >dot (exact-floor rem))])
;; accumulate ((x . c))@y
(hash-set acc y `((,x . ,char) . ,(hash-ref acc y '())))))))
>
#:key car)))hideous, i know. it’s about to get worse; it turns-out that i need to get the max x value encountered; to do that, i need to add fold var max-x:
(define pts (map (match-lambda [(cons y xcs) (cons y (sort xcs < #:key car))])
(sort (hash->list (let* ([range (let-values ([(min max) (min&max < vs)]) (- max min))]
[h (if (negative? h)
(min (abs h) (exact-ceiling (/ range num-dots)))
h)])
(for/fold ([acc (hash)] [max-x 0]) ([v vs] [x (or xs (in-naturals 1))])
(let*-values ([(y rem) (quotient/remainder (- (exact-floor (/ (* v 3 h) range)) 1) 3)] ; y=0 is bottom row
[(char) (hash-ref >dot (exact-floor rem))])
;; accumulate ((x . c))@y
(values (hash-set acc y `((,x . ,char) . ,(hash-ref acc y '())))
(max max-x x))))))
>
#:key car)))now the fold returns multiple values: acc & max-x. this means that the above code is invalid: i can’t pass that huge chunk directly to hash→list! per the language, i must bind both values by a let-values clause:
(define pts (map (match-lambda [(cons y xcs) (cons y (sort xcs < #:key car))])
(let-values ([(acc max-x) (let* ([range (let-values ([(min max) (min&max < vs)]) (- max min))]
[h (if (negative? h)
(min (abs h) (exact-ceiling (/ range num-dots)))
h)])
(for/fold ([acc (hash)] [max-x 0]) ([v vs] [x (or xs (in-naturals 1))])
(let*-values ([(y rem) (quotient/remainder (- (exact-floor (/ (* v 3 h) range)) 1) 3)] ; y=0 is bottom row
[(char) (hash-ref >dot (exact-floor rem))])
;; accumulate ((x . c))@y
(values (hash-set acc y `((,x . ,char) . ,(hash-ref acc y '())))
(max max-x x)))))])
(sort (hash->list acc) > #:key car))))ok, now i’ve extracted acc from the fold’s multiple outputs then passed it to hash→list. what about max-x? where does it go? as it turns-out, it’s used later in the program. we must keep it in scope, which means that define pts becomes define-values (pts max-x):
(define-values (pts max-x)
(map (match-lambda [(cons y xcs) (cons y (sort xcs < #:key car))])
(let-values ([(acc max-x) (let* ([range (let-values ([(min max) (min&max < vs)]) (- max min))]
[h (if (negative? h)
(min (abs h) (exact-ceiling (/ range num-dots)))
h)])
(for/fold ([acc (hash)] [max-x 0]) ([v vs] [x (or xs (in-naturals 1))])
(let*-values ([(y rem) (quotient/remainder (- (exact-floor (/ (* v 3 h) range)) 1) 3)] ; y=0 is bottom row
[(char) (hash-ref >dot (exact-floor rem))])
;; accumulate ((x . c))@y
(values (hash-set acc y `((,x . ,char) . ,(hash-ref acc y '())))
(max max-x x)))))])
(values (sort (hash->list acc) > #:key car)
max-x))))now you may have asked why not just leave it all in the one let-values instead of using both it and define-values. the answer is that, as discussed in the prior section, define-values avoids indentation/nesting creep.
oops. i didn’t even realize that this is still wrong! i’m binding to multiple values within the argument to map! that means that i need to bind those values before map then pass them to map:
(define-values (pts max-x)
(let-values ([(acc max-x) (let* ([range (let-values ([(min max) (min&max < vs)]) (- max min))]
[h (if (negative? h)
(min (abs h) (exact-ceiling (/ range num-dots)))
h)])
(for/fold ([acc (hash)] [max-x 0]) ([v vs] [x (or xs (in-naturals 1))])
(let*-values ([(y rem) (quotient/remainder (- (exact-floor (/ (* v 3 h) range)) 1) 3)] ; y=0 is bottom row
[(char) (hash-ref >dot (exact-floor rem))])
;; accumulate ((x . c))@y
(values (hash-set acc y `((,x . ,char) . ,(hash-ref acc y '())))
(max max-x x)))))])
(values (map (match-lambda [(cons y xcs) (cons y (sort xcs < #:key car))])
(sort (hash->list acc) > #:key car))
max-x)))there we go! acc is bound locally so that only map uses it, and pts is bound for use for later code, and max-x is locally bound by let-values to be passed through to define-values to bind it in the greater scope where it’s actually used! wow, is that inelegant? i suppose it’s arguably better to define acc as pts then mutate its value: (define-values (pts max-x) […]) (set! pts (map (match-lambda [(cons y xcs) (cons y (sort xcs < #:key car))]) (sort (hash→list pts) > #:key car))) but…eh, either way it’s ugly.
and this is the problem with the functional paradigm: to keep things in scope, we must return and bind, whereas in a stack paradigm we just push it to the stack and if it’s not what we’re immediately using, then we just push it further down the stack for use later. mutating state is easier than using functions for the same reason that the stack is easier. aside from the immediately prior mutation example, i could mutate max-x for more elegant code, too:
(define max-x #f) ; dummy #f value
(define pts (map (match-lambda [(cons y xcs) (cons y (sort xcs < #:key car))])
(let-values ([(acc max-x) (let* ([range (let-values ([(min max) (min&max < vs)]) (- max min))]
[h (if (negative? h)
(min (abs h) (exact-ceiling (/ range num-dots)))
h)])
(for/fold ([acc (hash)] [max-x 0]) ([v vs] [x (or xs (in-naturals 1))])
(let*-values ([(y rem) (quotient/remainder (- (exact-floor (/ (* v 3 h) range)) 1) 3)] ; y=0 is bottom row
[(char) (hash-ref >dot (exact-floor rem))])
;; accumulate ((x . c))@y
(values (hash-set acc y `((,x . ,char) . ,(hash-ref acc y '())))
(max max-x x)))))])
(set! max-x max-x)
(sort (hash->list acc) > #:key car))))you get the idea. this doesn’t work because, in the set! sexp, both max-x refer to the same object, though i want the first one to refer to the max-x of the outer scope and the latter of the inner. and here’s a problem that the stack lacks: not only we must name variables when it shouldn’t be necessary, but we must insensibly change names just to make the code technically correct. as a stylistic rule, give the inner-scoped variables the stupid identifiers. even if there were scoping rules such that (set! x x) set one x to a different x, that’s just stupid language; never should x=x be anything other than a tautology.
the common refactoring pattern for applicative languages, (f (+ 3 5)) → (let (x (+ 3 5)) (* (f x) (g x))), is done by dup in stack langs: 3 5 + f → 3 5 + dup [ f ] dip g * (though it’d really be written using non-primitive combinator bi: 3 5 + f g bi *.) in summary, in factor the refactor is just appending g bi * to the program. no nesting or binding junk. you can even put a newline for readability:
3 5 + f ! original
g bi * ! account for new thingthink about how nice that looks on diffs [vcs].
like functions, stack words have access only to those explicitly left by other words. this means that every word must account for all words left by the former word(s). that disables us from the context-sensitive subprograms available in picolisp by its use of dynamic binding; in picolisp, any all variables are available (including those never bound, which have NIL value) to every function, so a function may use whatever subset of variables happen to be bound or not at its execution time. though a word implicitly has access to the whole stack, putting to the stack is the only way to pass data among words; words cannot set variables (as a side effect) of which another word may use an arbitrary subset.
this is simply solved by mutating variables (the most flexible of which are global & dynamically bound.) that allows changing program state in a way that words not must, but may, care about those changes. this being said, dynamic variables must still be declared by SYMBOL:, which really makes them like global variables. to be true dynamic variables they’d need to, as in picolisp or lua, be able to reference variables without declaration (e.g. print(z) in a fresh lua repl prints nil.)
TODO: consider how apl recurses on trees, and the relational model for sexps; between the two of those i definitely should identify a loop that’s effectively recursion!
recursion is equivalent to, though often more elegant than, loops. recursion is defined of functions. a function can be thought of as a word, but rather than pushing to a stack, it outputs to whatever function called it. consider foldl, foldr, and foldTree:
-
foldlis strict and easily translates to a loop: the result of one iteration is left atop the stack and is used as input to the next iteration -
foldraccumulates thunks then evaluates them; this too is translated easily to a loop, where the loop is parameterized by a stack of thunks. this method is O(2n) whereas foldr is O(n). -
foldTreedoes not obviously translate to a loop, because each recursive call has different context (parameterization). despite the traversal’s symmetry (as shown by the simplicity offoldTreedefinition), it’s extremely complex (as shown by the program state throughout execution)
the clear question is how to express general folds (i.e. those which accumulate thunks) strictly in terms of a traversal structure (commonly a call stack, but generally a graph/relation[relalg] which may even support parallelism), an accumulator structure, and the remainder of the structure to consume (which may not exist and may instead be expressed purely by the traversal structure)? a simple, strict linear right fold pushes to a stack tuples (relevant loop state). consider haskell foldr / 0 [1,2,3], which expands to 3/(2/(1/0)), an ugly applicative form more clearly expressed in factor [stacklang] as 1 0 / 2 / 3 /, demonstrating that foldr does traverse the input structure in normal order. foldr looks normal in factor! indeed, foldl looks odd in factor: 3 2 1 0 / /. which is just a loop that checks if the structure to consume is empty, and if so then it traverses the traversal structure, applying its elements to the current accumulator value; else push the accumulated function .
the general difference between recursion and looping is that a loop has one context which may change whereas recursion may have variable context i.e. each call to a recursive function is parameterized by fn args whereas a loop is parameterized by in-scope state. though state/progs & fns/args are equivalent concepts, the importantly practical difference here is that fn args do not contend with each other; they’re neatly separate, which allows us to specify each’s parameters without managing their relation to other invocations' parameters. fns also have outputs! thus nested recursive fns are easier to traverse than looping through a structure corresponding to a traversal, because the traversal is implicit in the definition!
context has slightly different meaning in recursion than looping because each recursive call may have its own parameterization and return point whereas a loop has exactly one of each. as i mentioned with foldr, using a traversal parameter incurrs extra runtime complexity. however, physical processors do not support "recursion" or "loops" per se; they support only jumps. naturally recursion is a loop with a call stack whereas a non-recursive loop does not have a call stack.
for something to be easy to express recursively but not as a loop implies that losslessly flattening the recursive structure is difficult. that should never be possible, though; and traversing a flattened structure is exactly as easy as writing a parser. however, perhaps that statement is true only if the parser is itself a recursive function! then the question is: can parsers be easily written in terms only of loops?
both foldr & foldl are, in factor, defined recursively. they work on linked lists. this is sensible because loop is not a primitive; it’s just a recursive combinator that allows inline recursion/looping without needing to define a word, much like fix in haskell or named let in scheme. foldl is strict whereas foldr accumulates thunks then evaluates them, which is the equivalent to pushing thunks to a stack then popping off the stack with eval (call in factor.)
summary: unlike loops, recursive fns' traversal and accumulation structures are implied by the combination of 1. the definition of function, and 2. the recursive function’s definition.
TODO: how this would be done in the relational or deductive model? let relational model guide your reasoning about structure. consider multidimensional geometric interpretations of data. how can recursion be interpreted by or relate to dimensionality (axes)?
{ } { f g h } a
[| ctrl rst a | rst
[ ctrl reduce ]
[ unclip-slice ctrl prefix! ]
if-empty ] loopthere can be a conditional inside the loop that modifies the return point (here the fn to apply next.)
|
Note
|
for lists one can just access the list from right to left, but this does not generalize e.g. to rose trees. |