asQuirreL

In fairness, the donation is not monetary. It is probably more aptly described as "Contribution".

As already suggested, function pointers are a particularly memory inefficient way to represent instructions/opcodes.

But on top of that, there is another issue with this representation: Your interpreter will very likely be dog slow, because you have to make a function call on each iteration, and it cannot be inlined, because it is dynamic.

And I suspect there are implications for the I-Cache that should probably be considered as well.

EDIT By "considered", I mean, measured, and then considered.

Hmmm... So the article seems to suggest that for every insertion of a character, a log time lookup is made. Is that really the case? If so, why is the leaf node that the cursor is in not saved? If you were to use a B+-tree implementation then you would already have access to neighbour pointers for rebalancing purposes, making the majority of incremental changes very cheap (constant time). This is just a thought, there may be good reasons why it's not possible.

Personally, when I say "excuse me" on the pavement, I'm being sincere :) the space is no more mine than it is their's. But, I think all of this varies based on the culture of your immediate surroundings (for context, I live in London, UK). After all, "excuse me" could only be used ironically, if its genuine tone was apologetic (at least somewhere). I also have heard "pardon me" used interchangeably with "excuse me" in the ironic sense (usually to feign not having heard an offensive remark).

What visual programming languages do is lower the barrier for entry. Once you're hooked, and you begin gaining experience, you will naturally understand the limitations of the platform. By being inquisitive, you will realise that the software used in the real world isn't all built in Scratch. But, to breed that inquisitiveness in children at a young age requires making it accessible.

You, for example, probably very quickly realised that if you wanted to make games with a GUI, QBASIC was not the tool for you, but by the sounds of it, that didn't dissuade you.

Personally, I'm of the opinion that your very first language doesn't matter very much. As a programmer, you will (should) be learning plenty more, so the first one is more about learning how to learn than anything else.

The question is probably more aptly written as "Take the width, height and depth of a cuboid in centimetres, and return its volume in litres".

Nice writeup! One thing though, I believe Rust's BTreeMap [1] is a B-Tree (not a binary tree, as suggested), i.e. it's a tree whose branch factor is generally greater than 2.

The docs say that if you don't give a branch factor, a sensible choice is made for you, probably to get nodes to fit neatly into cache lines, so seeing as we are storing 35 unsigned 64 bit integers, this would be around 16 or 32 elements in a single node, and a depth of about 2. This means that, because the current implementation of BTreeMap does linear searches at insertion, for this particular use case, the BTreeMap isn't doing much better than a plain old array, that you are insertion sorting.

TL;DR: Storing the results in a vector and then in-placing sorting it could be faster, but not noticeably. I know this isn't the point of the article, but it was just an observation I had :)

[1]: https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...

AFAICT Swift does the sensible thing to maintain backwards compatibility with ObjC: When Swift code calls Swift code, the dispatch is static (a jump, and some stack fiddling, when you're counting the change). But if it's interfacing with ObjC then it must necessarily resort to the ObjC runtime's message based dispatch, which is a bit slower.

So the example I have in mind is that of a Randomised Binary Search Tree (or Treap, if you want). Its interface is pure, however it requires access to an RNG for insertions. Because of this, it cannot be treated as a pure collection: you need to tell the type system, hang on, this RBST carts around some state which changes when you insert to it, despite the fact that the state doesn't change the extensional behaviour of the structure. This is a provable property, but maybe not provable by Haskell's type system.

Now I know that you can hide unsafePerformIO in the interface, and in this case I expect it is fine, but this is not easy, it feels like a hack.

Another example that I have personally watched play itself out in disbelief was in a fairly large Haskell project: There was need of a lookup table, with some 10000 elements. In such cases, I would have stored the lookup in a database, or a separate file at least, but because they wanted to maintain purity so badly, the solution was to write a 10000 line long Haskell file. But wouldn't it be nice if you could load a file and tell Haskell: don't worry, this won't change, so treat reads to this purely.

I never said such things were impossible, merely not easy, and I don't believe this is by accident. I am almost certain that such things are made difficult to prevent abusing such features, but that doesn't stop me from missing them :) .

There doesn't need to be an overhead to this extra type disciplining of side-effectful computing. It is perfectly possible for the compiler to take the pure monadic code and implement it with actual side effects (which I believe GHC does do).

What I do miss though (dearly) is that there is a certain cost as to what can be encapsulated. For instance, in Haskell, it is no longer so easy to hide side effects behind a pure interface.

I guess I should clarify and say "What sort of a cache would use IO and make a pure function impure?". Even if the cache is so large that it doesn't fit in memory, its behaviour would still be referentially transparent.

What sort of a cache would use IO? Not any cache I've heard of. (Genuinely interested)

Kozen's book that has been mentioned is very good. I also recommend Sipser's "Introduction to the Theory of Computation".

It goes from Deterministic Finite Automata (equivalent in power to regular expressions in their purest sense, as opposed to POSIX regexps) to Context-Free Grammars and then finally Turing Machines. So this will give an idea of the hierarchy that TMs sit in.

Also, there are plenty of variations of Turing Machines with lots of cool properties. If you want to have a look, try searching for "Non-Deterministic Turing Machines", "Probabilistic Turing Machines", or "Alternating Turing Machines".

Well, if you want file `X` then you can ensure you find the minimal set of files to produce `X` from your given rules using Horn-SAT by adding `and X` to the Horn Formula representation of the build rules. Pretty neat!

To build on the pedantry, make would be traversing a restricted form of directed acyclic hyper-graph, no? The edges are between sets of vertices to a single vertex.

I found these structures cropping up alongside Horn clauses, and Context-Free Grammars in interesting ways. In this case, viewing make rules as Horn clauses allows us to use a variant of Horn-SAT to find the minimum set of files we have to produce to build a rule, which is interesting to think about, and reason about.

This article felt as though it was food for thought and not really trying to push any particular idea too hard. In any case, I found it interesting as it found parallels to the sorts of structures I found when exploring various algorithms for Context-Free Grammars (such as pruning, or detecting erasable non-terminals, which can both be described in terms of Horn-SAT).

...or those with pacemakers? ;)

Nobody's saying that the best way to implement the fibonacci sequence is using CPS, but in this instance it is a great example of what to do when converting a function with multiple recursive calls into CPS.

Sometimes, if you want an example to be both small and instructive, you'll have to put up with some contrivances.

The issue with arguments of the form "Mutation is..." is that all these things are models of mutation: merely representations. Different models help us elucidate different properties of the same underlying phenomena. This does not mean that either one is "correct" or the one true representation of mutation.

Yes, exactly this. Different tools are good for different abstraction levels. Nobody expects people to write applications entirely in assembly anymore, because we have higher levels of abstraction, but that doesn't mean assembly is good for nothing. Assembly is a great and necessary abstraction level. Similarly, technologies in other abstraction levels are useful too.

Too often I see people conflating "X is good" for "X is good for everything" when that is so rarely, if ever, true.

Perhaps some notion of entropy would be useful here? Normal information theoretic definitions of entropy usually rely on "bits of entropy". I.e. if you are given information in the form, "Should I compare %s to a summer's day" then how many new bits of information are we actually getting? In this case, it is unbounded, because what we are calling `name` can be arbitrarily long.

But what about if we define entropy in terms of something like parts of speech? Then, the computer can only change one part of speech (the noun phrase to which we compare a summer's day) whilst maintaining the context of the sentence, so in terms of that metric, entropy is low.

With this parts of speech entropy metric in hand maybe we could declare the output of a computer to be "written by a computer" if the entropy in its sentences approaches that of a human writing about the same topic.

Disclaimer: I spent about as much time thinking about this as you did just reading it, so I don't expect this is in any way a fully formed or implementable idea, just food for thought.

You're right `h :: a -> c`.

This idea has been knocking around the collective consciousness of computer science for a while now. For example, the SECD machine [1], a virtual machine for functional programming languages to target. Then there are also examples of people compiling functional programming languages to various lambda calculus bases, such as SKI [2], and BCKW [3]. Through the judicious use of some extra combinators, you can also get more compact "object code"[Turner79].

One advantage of compiling to something like an SKI or BCKW basis (or a mix) is that you can represent abstraction (functions/closures) without bound variables, or scoping, which can be a pain to implement (esp. in hardware).

Take, for example, the SKI basis. Suppose you had two functions, with types as follows:

  f :: a -> b
  g :: b -> a -> c

And you wished to combine them in the natural way to get `h`:

  h :: b -> c
  h x = g (f x) x 

Then, to achieve the same with S, K and I combinators we do the following (assuming we have SKI representations of `f, g` as `F, G`.

  H := S(S(KG)F)I

The `x` has disappeared! But, if we apply H to some CL expression `X` we get:

  HX = S(S(KG)F)IX
     = S(KG)FX(IX)    ;; apply S
     = KGX(FX)(IX)    ;; apply S   
     = G(FX)(IX)      ;; apply K
     = G(FX)X         ;; apply I

We can use S to Split (duplicate) parameters, and K to Kill (ignore) parameters, in a very straight forward way. Imagine the AST of the original code:

     App
     /\
    /  \
   App  x
   /\
  / App
  g /\
   /  \
   f  x

Every `App` is replaced with an `S`, every `x` with an `I`, everything else (`y`) is replaced with `Ky`. In my example, I have also gone to the trouble of "optimising" `S(KF)I` away, as it is equivalent to just `F`.

Interesting stuff, and plenty of theoretical grounding to boot. Especially as this sort of thing has started enjoying a renaissance, in the likes of "point-free" notation in languages like Haskell.

[1]: http://en.wikipedia.org/wiki/SECD_machine [2]: http://en.wikipedia.org/wiki/SKI_combinator_calculus [3]: http://en.wikipedia.org/wiki/B,C,K,W_system [Turner79]: http://courses.cecs.anu.edu.au/courses/COMP3610/assignments/... (apologies, I couldn't seem to find a version with an intact abstract).

You're right, this kind of study is really hard to set up properly. However, in this instance, I'm more concerned by the quality of the analysis. It seems to be, ignoring actual data in favour of anecdotal evidence, even when they clearly aren't even correlated at a cursory glance.

After reading the paper [1] regarding the empirical study on TDD, I'm pretty dubious about how well backed the conclusions are. If you look at Table 2, in the 4 case studies, 2 of the projects took longer with TDD (2.00x, and 2.64x ratio in man months to 3sf) but then the other 2 did better: (0.319x and 0.476x ratio in man months, 3sf). But all of this seems to be ignored in proving the original statement that TDD take 15-35% longer, which appears to be backed by what is described as "Management Estimates" [Table 3].

In fact, taking the geometric mean of the man month values (which, I think, but am not sure is the right metric to use when comparing ratios), we find the average ratio to be 0.947x. Make of this what you will, given the size of the sample.

[1]: http://research.microsoft.com/en-us/groups/ese/nagappan_tdd....

There does seem to be a method/interface system (Under the "Methods, Protocols, Implementations" header). And it seems to have some sort of dispatch system for tagged structures that can be later modified by the user.

The length of the program isn't necessarily correlated with the amount of time it takes to write it, or more importantly, understand it ;)