#computertech Bot Logged User list

Network: Rizon
Modes: +Nntzl
Last Seen: 3 minutes ago
Topic: #Welcome to #computertech! | End3r is DJing live at https://is.gd/yDJnuF | HIDE YOUR KIDS HIDE YOUR WIFE |
#5
Rank
315
Users

Channel Log Archive for #computertech

Prev
Next
* All times are UTC
Filtering by user: ski
Tuesday, November 15, 2022
[22:13:53] ski sorry to hear, Peorth
[22:15:01] + ski heya Saphir,ComputerTech
[22:19:05] + ski was looking into some C64 things before (including a Prolog), now idly checking some different takes on iteration forms (Common Lisp, but there's also related work in Scheme, Prolog, Haskell)
[22:22:25] + ski some relevant desiderata are : (a) expressivity and extensibility; (b) reasonability and composability; (c) efficiency
[22:30:16] + ski one important part of (b) is that related items are grouped together. e.g. with `for' in C, initialization & termination test % step update are (or rather, can be) grouped together. (as opposed to if you use a `while' or a `do'-`while' to effect the same sort of iteration). however, if you have multiple iteration variables, then this is not quite as true, anymore. while these three parts are all
[22:30:22] + ski together, in the loop header, they're mixed with each other, for the different iteration variables, rather than grouped separately. the `do' form in Lisp improves upon this (separating out a single termination test into its own place)
[22:35:48] + ski however, for common types of iteration variables (iterate an integer between bounds, iterate through elements of a collection (of various sorts), ..), one'd like to abstract away the particular way to step. of course for common iteration methods, one'd prepackage these. but one'd like to enable the programmer to extend the looping clause language by adding their own way of introducing an iteration
[22:35:54] + ski variable. also one may want to incorporate a termination check (for each iteration variable) so that the loop terminates whenever an iteration variable terminates (this also allows one to have open-ended iteration variables, like a running count, running sum, collecting elements, &c.)
[22:38:45] + ski but then one'd also like to have some valid refactoring laws, and ways to reason about it all. orthogonality stuff. and have the different clauses compose well into larger units (which is one thing that higher-order "internal iteration" functions are not that good at .. also efficiency). ideally, it'd all compile down into code that's comparable to something handwritten
[22:41:53] + ski don't mind me too much. i just woke up shortly before, now having these things spinning around in head
[22:48:42] + ski well, the most basic way of looping is using `goto' / `jmp' (or branching instruction) backwards, usually with a conditional (`if') somewhere in there (either to optionally go back, or to optionally break out of the loop)
[22:50:17] + ski of course, this is, in general, pretty inscrutable. you update registers/variables, and memory, sprinkled over the loop (possibly hidden behind macros or function/procedure/subroutine calls), and it can be hard to see what controls the looping
[22:53:04] + ski SSA (Single-Static-Assignment) form is somewhat better. you only set (virtual) registers once, and you cut the code into separate "basic blocks", each of which run from start to end (where they may branch into multiple different basic blocks). and you use "phi nodes" to merge inputs coming from possibly different edges to the current basic block, in the graph of them
[22:57:47] + ski using (possibly mutual) tail recursion is quite similar to this, except that instead of "phi nodes" each basic block has "parameters" (that serve the same function). each jump at the end of one "block" (end of a tail recursive function) will explicitly pass the registers it wants to pass on, as parameters (rather than these appearing in the "phi" node of the receiving basic block). so each "block" is
[22:57:53] + ski more self-contained (better separation of concerns, modularity). also, since everything is expressed in terms of function calls, expressions, you *possibly* (if you use side-effects, this is harder) can use equational reasoning to reason about and refactor the code (another win for reasonability)
[23:00:12] + ski however, (mutual) tail recursion (including the extension "(mutual) tail recursion modulo cons(tructor)", and some similar things that transforms "modulo associative operation" into an accumulator iteration variable) still have the disadvantage that related parts of the loop (the initialization, step update, and possible related termination check, for each iteration variable), are sprinkled all over the
[23:00:18] + ski place .. so it's rather non-composable, in general
[23:00:40] + ski ("tail call" is sometimes known as "`goto` with arguments")
[23:02:38] + ski (in short, tail calls is a desirable thing, for expressivity .. but is a rather sharp tool, usually best hidden inside the implementation of more pleasant abstractions)
[23:08:11] + ski next is higher-order iteration operations. these can be quite powerful, and definitely fits the extensibility bill. but they can sometimes be hard to compose and refactor (although learning laws for the most common ones isn't too hard). another concern is the cost of itermediate structures, that you pay when you combine them. this can be ameliorated by using streams that only generate elements
[23:08:17] + ski on-demand, or (better, if available) some kind of loop fusion (which can be hard to get guarantees of when it triggers). macros / staged programming can get around that last problem. but when a macro is used to introduce a mini-language (of loop clauses, here), often that language is closed (not extensible), or if not, cumbersome to extend
[23:14:15] + ski the two most basic ways to combine two loop clauses is "parallel / lockstep" in which they iterate alongside each other, and "nested", where the latter goes through a whole loop, for each iteration step of the former. (eager or streaming) list/sequence comprehensions (and the related SQL `SELECT ... FROM ...') come in here. in ECLiPSe Prolog, there's a (do)/2 goal construct, which acts like a macro that
[23:14:21] + ski compiles iteration clauses into an efficient form. i've experimented a little bit with "goal implications" in a Prolog setting (made a prototype), which i think may also be relatable to this. Olin Shivers' has written a paper about "the anatomy of a loop", and Riastradh (and foof) made a `loop' package partially based on ideas in that
[23:16:52] + ski in Haskell, there's (a few different) streaming libraries, that allow one to specify parts of iterations, to be pipelined together. there's also the "lens" library which is a very powerful library for accessing (run-time configurable) "fields", updating them, aggregating over them, &c. (this description doesn't do it justice)
[23:18:00] + ski finally, i have some half-baked ideas on how to syntactically separate a collection (like a list, an array, a tree, a finite map, &c.) from its elements. so you can write code which manipulates the containing collection(s) in one place, and code which manipulates the contained elements in another place
[23:18:38] + ski ComputerTech : heh, any questions ? :p
[23:19:31] + ski (in my mind, all these things are sortof related, at least partially .. trying to figure out how all the pieces fit together)
[23:29:25] + ski Prolog predicates (or SQL `SELECT' forms, and views) can make quite nice sources of elements (like a collection stream / iterator) .. if you don't care about generation order (and possibly duplicates) .. if you do, then it can be brittle (seemingly trivial refactorings, either manual or done by implementation, or even changes in part of data, can change order of generation)
[23:31:01] + ski also, if you're doing "lockstep" combination of two sources of elements, perhaps you decide you want to filter out some of the elements of one (or both) streams. now, do you want to align the remaining elements ("shifting back" one stream (or both) to cover up the holes) ? or do you also want to cancel the corresponding element of the other stream ?
[23:32:43] + ski possibly (?) one'd like the ability to do either of these, depending on circumstances .. but then that means that we no longer (conceptually) have a plain stream of elements, but also "holes"
[23:34:08] + ski (hm, now this reminds me that some approaches to data parallelism can work over arrays, with a separate sequence of bits specifying which of the elements are to be used, and which are to be ignored)
[23:38:00] + ski with chocolate chips ?
[23:38:41] + ski in that case, i'll have to, politely, decline
[23:41:11] + ski that sounds fine, don't mind if i do, tyvm :)
[23:41:21] + ski :[#]
Prev
Next