1. 1

    The title doesn’t make it clear, but this is only about Common Lisp rather than the Lisp family of languages.

    1. 6

      I’ve recently seen a fair argument on a textboard that when you say “Lisp”, it makes the most sense to infer “Common Lisp”. And I kind of get it, if your language retains a direct linage to implementations from the 60’s, it does seem legitimate to call that “a Lisp”, as compared to Scheme or other syntactic-lookalikes, no?

      1. 6

        It’s a long standing convention that unqualified “Lisp” means Common Lisp. Other than Scheme, Emacs Lisp, Clojure, and AutoLisp, it’s the only general purpose Lisp anybody still uses, and if somebody means one of the others they’re sure to use the more specific name.

        #Lisp on Freenode is dedicated to Common Lisp, for example.

        1. 3

          Small correction, but it’s #lisp that’s dedicated to Common Lisp. ##lisp is for the family of languages.

          1. 2

            Oops, thank you! Corrected!

          2. 4

            It’s a long standing convention that unqualified “Lisp” means Common Lisp.

            It’s a long-standing convention among Common Lispers only.

        1. 1

          Not sure if the author is reading here, but FWIW, PI is defined as a constant in CL.

          1. 1

            Yes, I was remarking that it is defined as a constant in CL, while in Scheme it is not.

          1. 1

            Honestly, I’m more interested in why somebody needs a function like this.

            I suppose it makes sense as a library function, but then why bind to a keyboard shortcut?

            1. 1

              Because people tend to edit their shell configuration. I do this quite often and I appreciate having some small utility to help with that (as opposed to having 4 register bindings).

              1. 1

                That’s fair, I guess. I didn’t realize people edited their shell configuration often enough to warrant an editor shortcut for it.

                1. 1

                  To be honest its a bit weird to me, just keep a buffer open and switch to it like any other is the strategy I use for all text files. I normally view me effing with dotfiles to be a temporary thing, not so often that I’d want to keybind it. The latter seems more like avoiding work and automating/optimizing that problem than anything else. But my goal tends to be one and done try not to mess with your tools more than use the tools so axiomatically I disagree with the idea in general I guess.

            1. 3

              12 years old software is legacy? I have such things running in production but never thought they are legacy. Perhaps because I built them…

              1. 2

                Yeah, I wouldn’t call 12 years old legacy, either. Especially not when it’s written in a language that’s still popular.

                Around 2007-2009 I worked on a system that was about 30 years old, with some of the code dating back longer than that. It was in the process of being replaced, but wasn’t scheduled to be fully decommissioned for another 5 years still.

                I guess anything not using the newest buzzword language, containers, or the newest Javascript framework is legacy now?

                1. 1

                  To be fair it was written in a language version that was being deprecated. That means libraries were bit-rotten, certain things couldn’t be run locally without first downloading the exact runtime dependencies (rather than letting the package manager solve it automagically) etc. etc.

                  As far as I’m concerned it was legacy and the author’s work primarily involved making sure that twelve years later people could still use the damn thing after a good chunk of its requirements either moved on from its version or were obsoleted.

              1. 9

                This is a great idea for a post that I’ve wanted to write myself. Leaving aside trees, hash tables, and stacks, I probably used less than one “interesting” data structure/algorithm PER YEAR of programming. Some notable counterexamples are two kinds of reservoir sampling, regular languages/automata, random number generation, some crypto, and some info retrieval algorithms.

                One thing that sparked it is a obscure but long-running debate over whether dynamic programming interview questions are valid.

                I don’t think they’re valid. It’s mostly a proxy for “I got a CS degree at a certain school” (which I did, I learned dynamic programming in my algorithms class and never used it again in ~20 years.)

                I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                I’ve tried this in the past and nobody has been able to point to a concrete instance. I think the best I’ve heard is someone heard about a professor who heard about some proprietary software once that used it.


                Related: algorithms used in real software (although this is certainly not representative, since compiler engineering is a subfield with its own body of knowledge):

                https://old.reddit.com/r/ProgrammingLanguages/comments/b22tw6/papers_and_algorithms_in_llvms_source_code/

                https://github.com/oilshell/blog-code/blob/master/grep-for-papers/llvm.txt

                Linux kernel algorithms:

                https://github.com/oilshell/blog-code/blob/master/grep-for-papers/linux.txt

                1. 10

                  I challenge anyone to name ANY piece of open source software that uses dynamic programming.

                  Git, or most reasonable implementations of “diff”, will contain an implementation of the Myers Algorithm for longest-common-subsequence, which is very dynamic-programmy.

                  No concrete example for this one, but I know that bioinformatics code is full of dynamic programming algorithms for the task of sequence alignment, which is similar to diff — identifying a way to align two or more base sequences so that they coincide with the minimal number of changes/additions/deletions required to make them identical.

                  1. 1

                    Hm I’m familiar with that algorithm but I never thought of it as dynamic programming.

                    Wikipedia does say it’s an instance of dynamic programming. Although when I click on the paper, it appears to contrast itself with “the basic O(MN) dynamic programming algorithm” (section 4).

                  2. 8

                    Since you mentioned dynamic programming, it’s worth pointing out that the name “dynamic programming” was chosen for political reasons, as pointed out in the history section of the Wikipedia article on dynamic programming. So I think it’s a really bad name.

                    1. 1

                      That’s funny, I remembered xkcd’s “dynamic entropy” comic, and it quotes the same passage:

                      https://xkcd.com/2318/

                      It also has a very interesting property as an adjective, and that is it’s impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible.

                      LOL

                      Agree it’s a terrible name… I would say it was chosen for “marketing” reasons

                    2. 7

                      I have thought about whether dynamic programming questions are fair to ask, and I ended up where you are: they are not.

                      Dynamic programming was the one I struggled most in understanding and implementing correctly. And while there are semi-practical examples (like the backpack problem), I have not found any practical, day-to-day use cases on this.

                      I had an argument with my colleague who asked this kind of problem, saying it’s basic knowledge. Turns out he did competitive programming and there, it is table stakes. But in practice, it just filtered for anyone who has learned and practiced this approach.

                      I stay away from asking this, problems that need dynamic programming to solve.

                      1. 4

                        I’m familiar with dynamic programming mostly from high-school competitive programming as well. Otherwise I can’t say I’ve encountered real-life problems where it occurred to me to use the technique.

                      2. 8

                        I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                        I’m literally about to implement something that could be classified as dynamic programming at work, which can be sumarrized as “computing a few simple statistics such as number of bytes changed for each directory in a large filesystem”. Dynamic programming is such a general term that it applies regularly if you want to use it.

                        1. 4

                          I’d like to see it. I don’t think dynamic programming is a general term.

                          In fact one time I participated in this argument (which was years ago so my memory is fuzzy), a former CS professor I worked with explained the difference between memoization and dynamic programming. A bunch of 10-20+ year programmers like myself went “ah OK”. Unfortunately I don’t even remember the difference, but the point is that most programmers don’t, because dynamic programming is very uncommon.

                          What you’re describing sounds like an obvious algorithm that anyone could implement, which is not the same as dynamic programming interview questions, or dynamic programming in competitive programing.

                          As other posters mentioned, competitive programming is the main place you see it outside of a CS class.

                          1. 2

                            It’s absolutely an obvious algorithm, so is most dynamic programming. That was sort of my point.

                            Can’t share the code unfortunately, but it’s just iterate over sorted list of file changes in reverse order and collect statistics as we go. Dynamic part comes from the fact that we can just look at the subdirectories of a dir (that we already have numbers for) instead of recursing into it.

                            1. 2

                              What you’re talking about could be called memoization, or it probably doesn’t even deserve that name. It’s just what a “normal” programmer would come up with.

                              That’s not the type of thing that’s asked in interview questions or competitive programming. The wikipedia page gives some examples.

                              Dynamic programming usually changes the computational complexity of an algorithm in some non-obvious way. There’s very little you can do recursing over a directory tree that doesn’t have a clear O(n) way to code it (e.g. computing statistics).

                              1. 7

                                I like Erik Demaine’s explanation, that problems where dynamic programming can be applied are ones where their subproblems and their dependencies can be modeled as a directed acyclic graph [1]. Up to you if you’d like to tackle that with a top down approach where you look at a node and calculate its solution based on the solutions of its ancestors, or a bottom up approach starting from the nodes in the DAG with no dependencies and propagate the solutions in topological order.

                                My colleague and I used it for a generalization of matrix chain multiplication (for tensors) [2].

                                [1] https://youtu.be/OQ5jsbhAv_M?t=2736

                                [2] https://github.com/TensorCon/ratcon/blob/release/opt/gencon/pathopt.py#L198

                                edit: by the definition above, even naive memoization can count as DP, if you’re caching solutions to subproblems of that structure. Doesn’t have to be at the difficulty level of competition to count as DP in that case.

                                1. 1

                                  Hm interesting, searching through my personal wiki, I found a related definition which is different. I haven’t really thought about it enough to form an opinion.

                                  Either way, it doesn’t change my overall point: that there are certain kinds of algorithms problems that appear on coding interviews, and in competititve programming, that do not show up in 99% of programming jobs. They are easy to pose and have cute solutions, but aren’t testing very much.

                                  I think the “DP tables” part is key but again I haven’t thought about it enough …

                                  https://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html

                                  Memoization is fundamentally a top-down computation and DP is fundamentally bottom-up. In memoization, we observe that a computational tree can actually be represented as a computational DAG

                                  In DP, we make the same observation, but construct the DAG from the bottom-up. That means we have to rewrite the computation to express the delta from each computational tree/DAG node to its parents. We also need a means for addressing/naming those parents (which we did not need in the top-down case, since this was implicit in the recursive call stack). This leads to inventions like DP tables, but people often fail to understand why they exist: it’s primarily as a naming mechanism (and while we’re at it, why not make it efficient to find a named element, ergo arrays and matrices).

                                  This bottom-up / top-down distinction might have been the same as what the aforementioned professor said 5+ years ago, but I don’t remember exactly.

                                  1. 1

                                    So, is memorization of factorial top-down, or bottom-up?

                                    1. 1

                                      I would probably say neither… Either factorial or Fibonacci is so trivial that it doesn’t help to be thinking about it that way.

                                      Though I think the quote hints at a clear test for whether it’s top-down or bottom-up: if you need extra state outside the call stack. I’m getting curious enough to try this out, but right now all I can do is quote what other people say.

                                      In any case it’s clear to me that there’s some controversy over what dynamic programming really is. I think the issue is that a lot of algorithms could be framed that way but were not discovered that way, and not taught and learned that way.

                                      1. 1

                                        I would probably say neither… Either factorial or Fibonacci is so trivial that it doesn’t help to be thinking about it that way.

                                        I think that the triviality is actually helpful here. If it’s actually true that memoization and dynamic programming are different (and there’s clearly debate on this), can 2 implementations of a trivial function, that everyone can understand highlight the differences?

                                2. 1

                                  On the contrary the stupidly naive way (recurse on every directory) is O(n^2).

                                  Dynamic programming is just solving a series of problems while using the answers of shared subproblems multiple times. Memoization is a common way to implement this.

                                  Yes there are some very clever algorithms that use dynamic programming, this doesn’t make obvious algorithms that use dynamic programming not also fit under the definition.

                                  1. 3

                                    Why would recursing into every directory be O(n^2)? You’re still only visiting every directory/file once? It seems like something missing?

                                    1. 1

                                      Say you have a directory structure with a single file in it, /a/b/c/d/e

                                      To get the number of bytes changed in e you need to visit e, then to get the number of bytes changed in d you need to visit d and then e, then for c you need to visit c, d, and e, and so on.

                                      Like I said, it takes a really naive solution, but if you don’t remember the values you calculate anywhere for some reason it’s sum over inodes (depth of inode)… which is O(n^2) (for bad directory structures).

                                      Note that I need these values for every directory, not just for one particular directory.

                                      1. 2

                                        That’s still linear complexity space. Unless you’re hardlinking directories (which you then have to deal with potential recursion), it’s still O(n). If you add a file at /a/b/c/file you only visit 1 more file and no more dirs, not an exponential. O(n + n + n) or O(n + 3) still simplifies to O(n).

                                        1. 1

                                          If you add /a/b/c/file you add 4 more visits, not 1. Going from n= 3 /a/b/file to n=4 /a/b/c/file adds 4 more visits. In other words this worst case example takes time O(sum from 1 to n of i) = O(n(n-1)) = O(n^2).

                                          N is the number of inodes in a arbitrary tree not a number of files in a fixed tree.

                                          1. 1

                                            That’s still adding a linear number of operations for each file, the depth could technically be considered a different variable, say m. So for each file (n+1) you add, you also add the number of directory traversals (m) resulting in O(m+n), which simplifies again to O(n), but in reality folders are files too, so are part of n in the first place, so again O(n). Ultimately your n space is the total number of inodes, which both files and folders have.

                                            Abstractly, you’re just traversing a tree structure (or a directed graph if using links), which is well understood to be O(n) (maybe O(n^2) worst case if all folders are links, resulting in a fully connected graph), because you only visit each node once. If it were O(n^2), you would visit each node n times.

                                            Remember, Big O notation is about scaling, not the actual concrete number of operations, which is why you drop any constants or variables other than n.

                                            1. 1

                                              It’s O(mn) not O(m+n) (in the insanely naive algorithm that recalculate things every time).

                                              It’s not a single tree traversal but #internal nodes tree traversals.

                                              1. 1

                                                Even if it was O(mn) (it’s not), that still simplifies to O(n). An ‘internal nodes’ tree traversal is still O(n), n is just smaller, but again, your problem is not an internal nodes traversal, it’s a full traversal because you have to look at the blocks attached to the file (leaf) inodes, which means you need to read all inodes of all files and of all folders one time each. n = # of files + # of folders = O(n)

                                                1. 1

                                                  I supposed an extremely naive solution could be to fully traverse each sub tree for every folder visited, which would be… O(log n)? But even that isn’t O(n^2), as the total repeated space shrinks the deeper you get.

                                                  1. 1

                                                    You’re assuming a balanced tree, which is not guaranteed. Depth of tree is O(n) in pathological cases (and average case O(sqrt(n)) is typical for randomly generated trees)

                                                    1. 1

                                                      Ah yeah, I think it would be O(n log n) not O(log n), because you traverse the tree once for each node, and a subset of of the tree for almost every n (except leafs), at least in the worst case. Still not O(n^2), and the solution for a O(n) is almost easier to conceptualize than the completely naive solution :)

                                                      1. 1

                                                        and the solution for a O(n) is almost easier to conceptualize than the completely naive solution :)

                                                        No argument here…

                                                        I think it would be O(n log n)

                                                        We agree it’s O(n) * O(time tree search) now right? And you’re trying to call the tree search time log(n)? Because trees are height log(n)? Then see the post you replied to, that’s true in a balanced tree, it’s not true in a random tree (where it is sqrt(n)) and it’s definitely not tree in a pathological worst case (where a tree is just a n length linked list).

                                                        1. 2

                                                          Yeah, the part I was hung up on before was that you’re naive solution traverses the entire subtree below a node for each node visit, I was stuck in the simple optimal solution. For the pathological case, basically just a bunch of folders in folders with a single file at the bottom, the depth of the tree is n, and the file inode at the bottom would be accessed n times, so O(n^2). For the common case it would be about O(n log n) where you can skip traversing larger and larger parts of the tree the deeper you get on each ‘path.’ Thanks for the discussion, I enjoyed it :)

                                3. 1

                                  I think comparing memoization to dynamic programming is a category mistake: they are different kinds of things.

                                  ‘Dynamic programming’ is a description of a style of algorithm. It’s divide-and-conquer, usually with overlapping subproblems, making it possible to reuse intermediate results.

                                  Memoization is a programming technique to remember intermediate results, by remembering the results of function calls. You can e.g. also store the intermediate results somewhere explicitly, usually in a matrix, in which case you don’t memoize the result ‘transparently inside the function’, but use a lookup table ‘external to the function that computed the result’.

                                  1. 1

                                    I dunno I find that in addition to the Racket language resource I gave elsewhere in the thread, lots of people compare them:

                                    https://medium.com/@afshanf/cracking-the-coding-interview-questions-part-7-a7c8f834d63d

                                    A note on terminology: Some people call top-down dynamic programming “memoization” and only use “dynamic programming” to refer to bottom-up work. We do not make such a distinction here. We call both dynamic programming.

                                    There does seem to be disagreement on what dynamic programming is. And many algorithms that were not derived with dynamic programming techniques could be described as dynamic programming.

                                    But it seems that most people agree it’s related to memoization.

                              2. 4

                                GCC uses dynamic programming to split IA-64 instructions into bundles.

                                1. 2

                                  Thanks, nice example and link! Still I would say it’s a niche skill, especially to come up with from scratch in an interview.

                                2. 4

                                  I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                                  Ever do video encoding or transcoding with anything built on FFmpeg or x264? Encode images with MozJPEG? Encode an AV1 video or AVIF image with libaom? Trellis quantization in advanced lossy compression encoders is a dynamic programming algorithm.

                                  1. 3

                                    Hm very interesting! I was not aware of that algorithm. Paper I found:

                                    https://www.mp3-tech.org/programmer/docs/e00_9.pdf

                                    I would still say it’s a bad interview topic, but it’s cool to see real world usages of it.

                                    1. 2

                                      Oh, no disagreement there! Even after coding it up myself, I’d hate to have someone ask me to whiteboard a working implementation of trellis quantization in 40 minutes or whatever (though I’m pretty sure I could sketch out an explanation now).

                                      In general I’m not a fan of whiteboard coding exercises at all. Whenever I’ve interviewed candidates I’ve always preferred the old-fashioned method of just reading their resume well ahead of time, looking up what ever piques my interest on it, and then having a friendly conversation about that. Usually that provides plenty of esoteric material for me to quiz them on and it also lets them show me their strengths and enthusiasm.

                                      1. 1

                                        My current company doesn’t do a whiteboard exercise, but my previous one did… but the thing is, the usual task was to implement a basic “grep”. That is, read a file and print all of the lines that contain a user-specified string, in a language of your choice, with whatever libraries make you happy (it’s not a trick, you’re not supposed to implement Boyer-Moore on your own). Assuming you succeeded at that, we would ask you to implement a few more features, like a -v flag (only print lines that don’t match), and -A and -B flags (print context lines before and after the matching line), until you got stuck or the time for that segment was up. It wasn’t graded on minutiae like correct semicolon placement, it was just an evaluation of whether a candidate could do a trivial task, how they handled additional requirements, whether they asked sensible questions and got clarification when needed, etc. I found it pretty reasonable.

                                  2. 4

                                    I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                                    I used Warshall’s algorithm (which is dynamic programming) to compute the transitive closure of a graph for a typechecker. This is, in my experience, a very common algorithm.

                                    In high school, I wrote a program for my professor that places students into groups of 4 such that their meyers-briggs personalities are as different as possible. This used dynamic programming.

                                    A professor of mine (who taught the subject to me) used dynamic programming for some kind of RNA sequencing problem in a paper he published. One of our homework assignments had us arrive at a watered down version of his (and his co-authors’) algorithm.

                                    I’m fairly certain that at least some fuzzy string matching algorithms use string distance, which is also solved using dynamic programming.

                                    These are all diverse applications of DP. In my personal, subjective experience, the idea that DP is in any way obscure or dated is absurd.

                                    Edit:

                                    To be more concrete, the “transitive closure of a graph” is for the graph of dependencies, computing the set of all functions that a particular function depends on. This is as described in the Haskell Report.

                                    For fuzzy string matching, I have in mind something like fzf, though I cannot say with certainty that it uses string distance (I’m unfamiliar with its implementation).

                                    Here’s the paper that I think I’m referencing: Statistical Mechanics of Helix Bundles using a Dynamic Programming Approach

                                    1. 2

                                      Thanks for the examples. The claim is definitely not that it’s outdated or obscure; the claim is that it’s not a good interview question because it doesn’t show up much at work. Although there were lots of people here who pointed out interesting uses of dynamic programming, that’s not incompatible with the idea that you could have a 10 or 20 year programming career and never use it.

                                      Side note: I’m familiar with the Floyd Warshall algorithm but I never thought of it as dynamic programming. I think part of the issue is that I may have a more narrow definition of it than others. (I think people even say the linear time fibonacci is an example of dynamic programming, which I find silly. I just call that the obvious algorithm. I guess it can be used to illustrate a principle.)

                                      Even so, I definitely think it’s more popular in universities, and certain domains like bioinformatics. In contrast to what people on this site typically do “for work”.

                                    2. 3

                                      I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                                      I do a lot of work with text processing – computing the edit distance between two strings is something I do very often. That’s a classic dynamic programming algorithm. There are probably hundreds of open source packages that do this or some variation thereof.

                                      1. 3

                                        Just to add to the list of responses clearly demonstrating Cunningham’s Law:

                                        I believe the Knuth-Plass line-breaking algorithm used in LaTeX to lay out text “optimally” uses dynamic programming. This was done for efficiency, as opposed to using some kind of general global optimization routine. It’s also the reason why LaTeX doesn’t support “backtracking”.

                                        1. 2

                                          It’s also the reason why LaTeX doesn’t support “backtracking”.

                                          Sile uses a variant of the same dynamic programming algorithm to lay out paragraphs on a page. The original paper describing the algorithm says that TeX wanted to use it like that, but it would require more than one entire megabyte of state for a large document, which was infeasible.

                                          1. 1

                                            Definitely an instance of Cunningham’s law at work :) I should make another go for my pet problems:

                                            • it’s impossible to make a zsh-like interactive interface on top of GNU readline
                                            • you can’t make a constant-space linear-time model of computation that’s more powerful than regular languages, and that can parse shell/JS/Python/C++
                                            • you can’t make an extended glob to regex translator in less than a week (https://github.com/oilshell/oil/issues/192)

                                            Thanks for the example. If there were more specific links I would make a blog post out of this :)

                                            And although my comment was a tangent, it did motivate me to get out the “Algorithm Design Manual” and flip to the part on dynamic programming. Though I remember the applications in that book being interesting but seemingly far removed from what programmers do day-to-day. It seemed to be by a professor who consulted on algorithms for various companies, which is an interesting job!

                                          2. 1

                                            The Grasshopper routing library uses contraction hierarchies, which are implemented using Dijkstra’s shortest path algorithm and A* search, which are special cases of dynamic programming.

                                            I have to agree it’s not something most people will use every day, but it never hurts to have a general idea how it works.

                                            1. 1

                                              Here is a concrete example of Dynamic Programming that you use every day: Word Wrap. Knuth has an algorithm that is often used for maximizing the number of words per line.

                                              Also the field of Bioinformatics often uses the Levenshtein distance when matching two dna strands.

                                              Also I would like to mention the single most important thing I learned from Dynamic Progrmming: Start at the end case, and figure out what constraints can work from there. For example, think about the last recursion call, and what constraints it needs, and go backwards from there.

                                              1. 3

                                                When using modules (as in this case, see https://github.com/OpenDiablo2/OpenDiablo2/blob/master/go.mod) go wants you to use fully qualified imports all the time. There are some tweaks to avoid that (which help reuse code in both module and non-module environments) using renames in go.mod, but yeah, it’s normal.

                                                1. 2

                                                  Yes, though they’re not really importing them from Github, but relative to the $GOPATH/src. This is a consequence of how Go originally managed code. I was never a fan.

                                                  Contrary what pgeorgi mentioned, Go modules actually remove the strict need for this, though it makes sense for older projects to keep old style fully-qualified imports as OpenDiablo 2 does so as not to disrupt existing code.

                                                  In newer projects, you could have something like this in your go.mod file:

                                                  module OpenDiablo2
                                                  

                                                  Which would allow you to write imports within your module’s internal source like this instead:

                                                  package d2server
                                                  
                                                  import (
                                                  	"OpenDiablo2/d2game/d2player"
                                                  	"OpenDiablo2/d2networking/d2client/d2clientconnectiontype"
                                                  	"OpenDiablo2/d2networking/d2netpacket"
                                                  )
                                                  

                                                  Which is vastly better. For third-party code you’re pulling in as dependencies, you’d still use fully-qualified imports, however.

                                                  Go modules are far from perfect, but they make life so much easier.

                                                  1. 1

                                                    Which language has the most perfect module/package system according to you?

                                                    1. 1

                                                      I don’t think there is such a thing. Practically every half-decent module system these days is essentially riffing on Wirth’s original work on Modula and its successors.

                                                      Now, packaging (i.e., their distribution, as opposed to the modules/packages themselves) is a whole other issue. Talking about that is a bit of a quagmire, and I don’t think anybody’s really cracked it.

                                                1. 2

                                                  About to eat lunch and head out on a long bike ride. Possibly another bike ride tomorrow, or maybe a hike instead.

                                                  And I’d like to finish the book I’m reading.

                                                  I’m also trying to go back through some of my GitHub/Sourcehut repos and clean up the code, add documentation, refactor, and add more tests. It’s something I’ve thought about doing before, and since I’ve had a creative mental block lately, I realized it’s a great opportunity to finally get around to it.

                                                  1. 5

                                                    Honestly, I feel the ACM prices are fair.

                                                    Membership with library access is only $198 a year, and realistically that’s not a burden for most people who would want access.

                                                    Furthermore, as the author points out, “The ACM exists to serve the field of computing and society itself,” and the main way they fund that work is through membership fees and charging for library access. The money has to come from somewhere.

                                                    1. 6

                                                      If journal access is the only value that the ACM can provide for their membership fees, then they don’t have much of a legitimate reason to exist. Real professional societies do much more, both for their members and for society at large. I can appreciate that the ACM doesn’t have anything close to the kind of leverage that they would need to really fulfill their mission, but they’ll never get there with that kind of petty gatekeeping mindset and revenue model. It’s simply off-putting.

                                                      Here’s what Scott Aaronson had to say about the practice of charging for access to academic research. Please do follow the links to statements from John Baez and Donald Knuth, too.

                                                      1. 3

                                                        Journal access isn’t the only value they provide, it’s the only thing they provide that gets them net revenue. They also do things like run conferences, running the library, and “magazines”. You can read the full breakdown here.

                                                        1. 2

                                                          Membership is what brings them revenue. Tying that to journal access is just a marketing strategy.

                                                      2. 4

                                                        I looked into getting ACM membership, but unfortunately I did not agree with all of their principles and other things as stated, and did not wish to compromise my own integrity or insult their stance by agreeing to a membership just so I could download articles.

                                                        1. 7

                                                          Huh, I admit I didn’t read the principles very carefully, but after skimming through them these all seem pretty reasonable to me. Could you say which ones you don’t agree with?

                                                          1. 8

                                                            For what it’s worth, while I don’t like the ACM’s code of ethics I do support something in the form of the ASME code of ethics or the AlChE code of ethics.

                                                            A big difference I see between the ACM and those other forms is that there is a focus not on some lofty idealism but instead on the realpolitick of a guild looking to protect its interest. An extremely cynical reading of those classical engineering ethics suggests an impetus of “Hey, look, people don’t understand what we do and they’re gonna blame us if we fuck up. so, we need to explicitly always be trying to serve the public good so that they trust us, ensure we don’t engage in buddyfucking that would harm our guild, and act in a generally moral way that means our mandate to charge what we do to do the work we do to the standards we want is not revoked.”

                                                            I’ll point at a few to give the flavor, though I think @asthasr has a good explanation of overall what bothers me.

                                                            In section 1.2, “harm” is vague and made worse by the frequent qualifier of “unjustified”. If somebody thinks something is “justified”, poof, there goes the protections.

                                                            The requirement to use “generally accepted best practices” is so at odds with how software is actually developed today that it shakes my belief in the empirical grounding of any of what follows. Ditto the absurd idea that “consequences of data aggregation and emergent properties of systems should be carefully analyzed”–not that those sentiments are wrong, but they’re so clearly not how we do software “engineering” outside of a few niche applications.

                                                            The entire bit about “capricious or misguided reporting of risks” is basically useless–practitioners must report risks, expect when there’s a chance the reporting might introduce “harm”. So, your obligation is to report issues except when reporting it might have further issues. The ASME criteria (criteria section, 1.3.1) is a lot more straightforward:

                                                            Whenever the Engineers’ professional judgments are over ruled under circumstances where the safety, health, and welfare of the public are endangered, the Engineers shall inform their clients and/or employers of the possible consequences.

                                                            You report the risks, always. If they go ahead with it and you believe there is imminent danger to the public, you go to the authorities. You don’t have this “a computing professional should carefully assess relevant aspects of the situation” nonsense–if you see something, you say something, and if it’s bad enough to endanger the public you fucking report it.

                                                            The problem with the ACM stuff here is that, frankly, it’s very rare that any individual software system is going to pose such an obvious threat to life and limb (compared with, say, a bridge) that a practitioner is going to risk souring their relationship with their work over it. Only recently have we seen any approximation of this behavior with the walkouts over ICE contracts or what have you, but that’s been quite limited.

                                                            In section 1.4, the wording of discrimination includes the phrase “inappropriate factor”. This implies that there are in fact appropriate factors for discrimination, and thus some subset of people that should be discriminated against. This goes directly against (in my reading) the immediately preceding claim of that we “should foster fair participation of all people, including those of underrepresented groups.”. Well, which is it?

                                                            It goes on to talk about “computing professionals should take action to avoid creating systems or technologies that disenfranchise or oppress people.” What exactly does this mean? If I work on software for ultrasound used in abortions, am I not aiding in disenfranchising or oppressing future people? If I work on door lock software for prisons where we put violent white nationalists, am I not doing the same? What about banking software that by necessity only serves those with some pre-existing form of wealth?

                                                            Section 1.5 is about supporting patents. In the first paragraph, we are told to “respect copyrights, patents, trade secrets, license agreements, and other methods of protecting authors’ works.” In the very next paragraph, “Computing professionals should not unduly oppose reasonable uses of their intellectual works”. Again, which is it? The entire bloody point of patents is to prevent any unauthorized use of intellectual work (for a good cause or no!) and grant a limited monopoly so as to encourage further innovation. The invocation of “protecting of authors’ works” is supporting a fictional narrative where we don’t live in a world where every salaried or engaged software engineer signs away their rights as parts of Assignments of Invention.

                                                            It goes on and on, and I won’t take up more space here.

                                                            The real failure of the ACM document is that it’s so goddamn long. Any sort of reasonable ethical boundaries need to be succinct, trivially seen to be representative of common practice, and ideally not containing text that directly contradicts itself. The ACM Code fails on all three of those counts for me.

                                                            1. 2

                                                              The problem with these sorts of lists is that they are meaningless without an ethics. What does it mean to “do no harm?” What is the “public good?” What is the justifying authority behind the “compelling belief” that accessing someone else’s system would help the public good?

                                                              Without an ethical basis this is worse than useless: it’s gormless sloganeering.

                                                              1. 2

                                                                i don’t think you have to provide a clear plan before saying you want to do no harm

                                                                1. 2

                                                                  So what if I think it’s very harmful not to send your data to my religious organization for inspection to make sure you’re not sinning? That’s clearly “justified” disclosure of information.

                                                            2. 6

                                                              Woof. I see what you mean.

                                                              They’re really walking themselves out onto an ethical cliff, aren’t they?

                                                              I’ve never gone for membership simply because the price/value equation never made sense to me, but having read the above now I have two reasons to avoid it :)

                                                              I own a hardbound set of volumes 1-3 of their History of Programming Languages series though, and treasure them :)

                                                              1. 6

                                                                Any chance you can point out the problematic principle?

                                                                1. 5

                                                                  It’s less about one single principle, and more about the fact that many of these are an INCREDIBLY slippery slope.

                                                                  Let me give you an example:

                                                                  3.1 Ensure that the public good is the central concern during all professional computing work.

                                                                  Step back and think about that for a moment.

                                                                  Is anything any of us ever does in this industry short of those of us doing charity work REALLY in the public good?

                                                                  Lots of folks think writing open source software is in the public good. Is it? It encourages the use of computers, which have some VERY serious environmental impacts both in terms of their manufacture and their use at scale.

                                                                  It’s a very slippery slope. I appreciate the fact that they are striving to live and work by a set of ideals, but my point is that trying to reduce those ideals down to an actionable set of guidelines for our daily work is an incredibly daunting task, and possibly impossible.

                                                                  1. 2

                                                                    Is anything any of us ever does in this industry short of those of us doing charity work REALLY in the public good?

                                                                    Yes! (After a long career of “not really”).

                                                                    World would be a markedly worse place for humans without the stuff I get to work on (a widely used study aid for medicine), including a few people who are alive today because their doctors were able to look things up (in much of the world the specialist textbooks you would otherwise need are prohibitively expensive).

                                                                    1. 2

                                                                      As usual I phrased that poorly.

                                                                      I wasn’t saying that such jobs don’t exist, because I’ve worked at jobs like that as well.

                                                                      What I was ham fisted-ly trying to communicate is that not everyone is so lucky, and so putting that in their list of tenets is creating a moral quandary where there doesn’t need to be one.

                                                                      Do no harm is enough for me.

                                                              2. 4

                                                                I’m sure you’re not the only one. For as toothless and out-of-touch as they are, they sure do a lot of purity testing and virtue signalling. It just serves to keep them irrelevant outside academia… which in turn sure doesn’t enhance the relevance of academia to industrial practice. The whole thing is a sad mess, IMHO.

                                                                1. 3

                                                                  Seems like a pretty reasonable list, and the baseline of ethical, professional responsibility for somebody working in the field of computing. What in particular do you have an issue with?

                                                                  1. 1

                                                                    Interesting. You may not want to explain on a public forum but that’s some really mild stuff. If you dropped the “computing” phrases it wouldn’t be out of line in a list of Abrahamic religion’s sermon topics (and maybe other faiths, I don’t have first hand experience in those).

                                                                1. 6

                                                                  Following through to the main Pyret description page, I don’t know if this is new to Pyret or half-inched from some amazing promethean functional language I’ve never heard of, but this is one of the best things I’ve come across in a new-to-me language for a very long time:

                                                                  Functions can end in a where: clause that holds unit tests for the function. These assertions are checked dynamically.

                                                                  Maybe not awesome for performance but what a boon for function-level correctness without having to dive deep into complex types. Also

                                                                  you can also write check: blocks at the top level, for general program testing

                                                                  All-round good thinking about consistency and coherence from the ground up. Rad.

                                                                  1. 3

                                                                    Might be taking contracts from Eiffel/OO languages and/or pattern matching guards from Erlang/Elixir/functional languages. Not sure what the lineage of Pyret is though.

                                                                    1. 3

                                                                      Might be taking contracts from Eiffel

                                                                      That’s what I thought at first, too. But a look at their example shows that they aren’t contracts/invariants, they’re literally just standard unit tests. The only difference between these and, say, a D unit test, is that these are syntactically tied to the function. This affords you better test failure messages, at least.

                                                                    2. 1

                                                                      That “where: “ clause is kinda neat, and I’ve never seen it before either. Seems like there shouldn’t be any performance impact if the compiler is smart enough.

                                                                      1. 1

                                                                        I wish they did not use where as the keyword. I like how Haksell uses where to define small local functions, and it fits better there.

                                                                    1. 2

                                                                      @work In theory I’m testing our product running under Windows in WSL. In practice, at least Thursday and most of today, I’m struggling to get the right versions of Windows, WSL, and our code setup in AWS. Hopefully it’ll go smoothly once I get that all worked out…

                                                                      @home I finished reading through “The Book of Shaders,” and now I want to use it for something. I might try a graphing/charting library for Common Lisp with OpenGL graphics. Not sure that’d use much from “The Book of Shaders,” but it’s something I’d like to have.

                                                                      I also started reading the second book of “His Dark Materials” last night, and I’m hoping to finish this week.

                                                                      1. 2

                                                                        @work More release testing.

                                                                        @home Over the weekend I wrote this package for using the RideWithGPS API from the Lisp REPL. This week I’d like to build something on top of it.

                                                                        And I’m finally getting around to reading the boxed set of “His Dark Materials” that I received as a Christmas gift.

                                                                        1. 3

                                                                          The weather looks good, so I’m going for an overnight bike trip. I’ll ride from my apartment and camp between Ward and Nederland off the Peak to Peak highway.

                                                                          1. 6

                                                                            Does anyone know of cases where a big language with a big compiler code base goes through the kind of renewal that Stephen implies here? It seems like the way that usually happens is not incrementally but a step function when someone creates a new language derived from the old one.

                                                                            1. 4

                                                                              Maybe C++ going from C++98 to C++11?

                                                                              It’s not quite the same, though, because C++ has multiple compilers and a larger user base.

                                                                              1. 3

                                                                                a step function when someone creates a new language derived from the old one.

                                                                                Yes, historically that has been the case.

                                                                              1. 3

                                                                                I’m usually not one to defend Microsoft products, but I’ve used COM quite a bit over the years, and I don’t get the negativity in this article.

                                                                                There’s a HUGE amount of Windows internals, other MS applications (like Office), and even third party applications, exposed through COM. There’s a big learning curve, and the docs can be a little overwhelming, but they’re actually quite good once you know where to look and what you’re trying to do.

                                                                                I won’t deny that there’s often not a lot of example code around the web, but it’s hard to take the “poor documentation” claim very seriously when the second paragraph links to a page in the documentation explaining how shell namespace extensions work, and off on the left is a TOC sidebar with an API reference, a developer’s guide, and sample code for using and extending the Shell with COM…

                                                                                1. 2

                                                                                  …Except much of that documentation was brought over from Windows 2000 API docs and doesn’t cover newer APIs very well - some of the ones I was struggling with were additions from late XP and Vista era. That and examples tend to be very, very simplistic and don’t cover possible error and edge cases. Otherwise, I would tend to agree MS documentation is fairly good.

                                                                                  edit: I didn’t really mean to be negative - I think there’s a lot of untapped potential in the COM world. I just think the MS documentation is while normally good, not quite as good w/ COM (explanations and such), and that’s a contributing factor as to why developers never took full advantage of it.

                                                                                1. 1

                                                                                  @work We’ve started release testing for our next release, so we’re all working on manual testing. I lucked out (I think) and the tests I’m responsible for should go pretty fast and I can get back to regular work. Manual release testing feels kind of silly in this day and age (IMO), but we’re working on automating it, and it’s getting better, so hopefully soon we won’t have to do this any more…

                                                                                  @home I’ve been trying to stay off the computer, though I’m still reading “Algorithms, Graphs, and Computers,” and may implement some of the algorithms. I may take the opportunity to learn a new programming language (or get re-acquainted with one I haven’t used recently) because I haven’t done so in a while.

                                                                                  Other than that, I need to finish up some lingering spring cleaning.

                                                                                  1. 2

                                                                                    Based on that, you can set up a fake input keyboard and do weird stuffs or have pre encoded scenarii when the circuit is plugged in the computer. The first basic idea (and I know that you can get pedals and stuff) is to have an Alt-Tab function accessed by foot taping. I don’t know why.

                                                                                    1. 1

                                                                                      That’s more common than you may think…

                                                                                      I have a Kensington laser pointer/USB drive where plugging in the USB drive attaches both a storage device and a wireless keyboard, but the “keyboard” only ever sends two keys, “Previous” and “Next” for moving around the presentation.

                                                                                      1. 2

                                                                                        That could be a funny attack vector (not the Kensington but the DIY one) if you manage to send any keypress and shortcuts (and or mouse click if you get the coordinates properly).

                                                                                    1. 6

                                                                                      I’m not sure I buy it.

                                                                                      First of all, without seeing the code behind the PRs and commits, it’s difficult to know what conclusion to draw. Maybe the stacked PR would have had more discussion in either case?

                                                                                      Perhaps the underlying problem is the PR “… contains multiple logical changes,” implying it should have been multiple PRs in the first place.

                                                                                      One of my co-workers is really good about making small, self-contained commits, and when I review his PRs I go through commit-by-commit and follow along with the changes over time. It seems to give all of the benefits of these “stacked pull requests”, without the overhead, and it makes reviewing larger PRs much easier. I’ve been trying to get better at it and use the same technique when I make large changes.

                                                                                      1. 14

                                                                                        I guess this is a little off topic, but creating a browser engine is so difficult, I wonder if anybody has considered creating Markdown browsers and communities around them?

                                                                                        The key ideas would be:

                                                                                        • Serve markdown (maybe an extended version) over HTTPS
                                                                                        • Reuse existing server infrastructure
                                                                                        • Only text, images, video, and audio - no client scripting
                                                                                        • Leave all rendering decisions to the browser
                                                                                        • Participating sites would (ideally) only link to other markdown sites

                                                                                        The HTML and Javascript web seems to get more and more like TV every day, with less user control and more centralized/corporate control. A new browser engine might help, but it feels like it’s beyond saving at this point.

                                                                                        1. 25

                                                                                          https://gemini.circumlunar.space/

                                                                                          Gemini is a new, collaboratively designed internet protocol, which explores the space inbetween gopher and the web, striving to address (perceived) limitations of one while avoiding the (undeniable) pitfalls of the other.

                                                                                          While not a browser per say, this is similar in spirit to your markdown browser idea.

                                                                                          1. 12

                                                                                            Leave all rendering decisions to the browser

                                                                                            I’m torn on this. I don’t really care for the CSS or layout for random news sites, but at the same time I really like the distinctive and wacky styles I see on people’s personal sites. Removing that element of individuality would, IMO, make the web more corporate.

                                                                                            1. 6

                                                                                              Sounds kind of like the existing Gopherverse, sans HTTPS.

                                                                                              1. 5

                                                                                                Reminds me a bit of this post calling for a “Khyber Pass Browser”. I saw it in another forum, so I’ll paste my comments here as they also apply to your idea, and I’m intrigued by the design space and problem of staying simple:

                                                                                                What are your use cases or goals? I ask because I am ancient, and this sounds like a design doc for Mosaic 1.0, down to opening an external application to deal with those newfangled jpegs.

                                                                                                Depending on those high-level questions, maybe you want to lean way, way more into unix and do the most extreme version of “defer any content-specific rendering to user-specified helper programs” and like make a FUSE filesystem for browsing IPFS/DataShards or similar? Then you don’t even have to define a document format and write a renderer. (But more likely there’s some context/assumptions I’m missing.)

                                                                                                [discussion turned to the “should be implementable by a motivated undergad in a year of free time” heading]

                                                                                                I think an undergrad with a high-level binding like fusepy could bang out an integration pretty quickly. But I’m not married to the idea, I was throwing it out there to try to figure out what’s important to you in this project, same with the use case/goals question. Is it networking? Is it a new document markup? Is it use of mimetypes?

                                                                                                A point I meant to make with the comparison: Mosaic was an undergrad project and thirty years later, here we are with browsers that have 10x more code than the OS it ran on. What about this project keeps it from growing? How would you allow it to change and adapt, but not grow? That’s a really fascinating problem; how do you repeal Zawinski’s Law? Is there something in your design space that you think will help a KBP become a living fossil?

                                                                                                  1. 1

                                                                                                    I could see myself using that, though I assume it’s going to mostly for personal websites, so one will still need an extra conventional browsers.

                                                                                                    Really interesting idea

                                                                                                  1. 3

                                                                                                    The .xyz TLD is fun, small, refreshing, funky, a whole lot cheaper and you don’t support colonialism.

                                                                                                    Perhaps, but it still sounds childish and looks like something you’d choose if all other serious options are not available. At least that’s the feel I get and I’m certain a lot of other more casual user do too. .io was kind of lucky that it managed to get into the .com, .net, .co.uk, … group of common domain names.

                                                                                                    1. 17

                                                                                                      Yeah, good point. It must be my recent interactions with the indieweb, but… The internet is supposed to be fun and perhaps, to some degree, childish. For serious stuff, by all means, avoid .xyz, .wtf, .ooo, use .org, .com, .net, .tech, .news, .computer. There’s so much out there, even more meaningful than “input/output” :)

                                                                                                      1. 17

                                                                                                        The internet is supposed to be fun and perhaps, to some degree, childish.

                                                                                                        I couldn’t agree with this more. People have lost touch with this attitude.

                                                                                                        1. 6

                                                                                                          People have lost touch with this attitude.

                                                                                                          Sorry to be so cynical, but it’s easy to lose touch with the fun internet when even personal blogs are packed with trackers and advertising and trying to monetize everybody.

                                                                                                          Except for some relatively obscure corners, the light hearted and fun internet is dead. At this point, I doubt most people ever even experienced that part of it.

                                                                                                          1. 4

                                                                                                            I strongly disagree. Let’s say in 1995 there were 10 websites and all of them were fun and childish. In 2000 maybe there were 10,000 websites and 50 of them were fun and childish. In 2020 there are 10 million websites and 10,000 of them are fun and childish. And I see people calling that a bad thing?!

                                                                                                            The internet of the 90s didn’t go away, there’s just more built up around it. You can have that old internet back, just block Facebook and Google and hell even the top million sites. All you have to do is just not visit the sites you don’t like. When I hear people say the old internet is gone what I hear is that they want all websites to be like the old internet. There’s more “old internet” today than there ever has been and it’s easier to find those sites than it ever has been. I don’t go into my favorite ice cream shop and complain about all the fancy new flavors, because I can still buy plain old vanilla. Strawberry shortcake didn’t replace my favorite flavor, it’s all still there. The only difference now is that I have other flavors tempting me, flavors no one is forcing me to buy. Vanilla is still there.

                                                                                                            Complaining that the good sites are stuck to the obscure corners ignores the fact that the 90s web was an obscure corner.

                                                                                                            1. 2

                                                                                                              I think you misunderstood what I was trying to say. I was on the internet in 1995, and while there are things I miss, like the higher signal to noise ratio and less advertising, I don’t have anything against the modern web and I don’t have any interest in making the modern internet more like the internet of the past.

                                                                                                              The point I was making is that the whole mindset of the web has changed, and even if you block millions of sites you’re not going to get the same open and “fun” experience as browsing back in the 90s. The mere fact that you have to put so much effort into it changes the experience.

                                                                                                              It’s like trying to relive the 1870s by driving a horse and buggy in traffic on modern streets - maybe you’re getting some idea for what it was like, but it’s a long ways off from what it was really like back then.

                                                                                                            2. 3

                                                                                                              I didn’t intend for my comment to be a pointed one, or to blame anyone. It was perhaps directed more at the people who run those blogs that are packed with trackers and advertising.

                                                                                                          2. 2

                                                                                                            I recall when there was a minor uproar over .xxx … at some point one must do away with childish things, no?

                                                                                                            1. 4

                                                                                                              Why, exactly?

                                                                                                              It’s never to late to have a happy childhood. (That’s a quotation, yes. Fine book.)

                                                                                                              1. 1
                                                                                                                1. 2

                                                                                                                  This is actually a verse from the Bible:

                                                                                                                  https://biblehub.com/kjv/1_corinthians/13-11.htm

                                                                                                                  1. 1

                                                                                                                    Is that a film where the man is a thoughtful person or more of a badass? If thoughtful you can make a thoughful argument. If badass, I suppose there isn’t much of an argument to be be made.

                                                                                                            2. 4

                                                                                                              I agree. I own both snazz.xyz (because it’s fun, short, and fits well with the theme of my username) and a more professional website with my CV and academic information at [firstname][lastname].com. I think that owning both serves me well at a lower annual cost than a single .io.