Hacker News new | past | comments | ask | show | jobs | submit login

The article refers to one quora answer where the author says - "The machine-based models offer no notion of composition of programs from parts". The instructions are the parts of the so called machine model, isn't sequencing of those instructions and control flow instructions are nothing but composition?



It's a very impoverished form of composition if the only things you can really compose are the absolute primitives, rather than allowing you to compose things that are themselves composed. When you "program" with Turing machines, you don't have a way to take a section of "code" and paste it into another, larger program. You'll have to deal with two pieces numbering their states the same, overwriting each other's tape data, etc. If you have two Turing machines that solve separate pieces of the problem, you know there exists a single machine that does both things, but nobody actually goes and constructs that machine. Instead, they just mention its existence as justification for writing "do this; do that;" in a higher-level machine description.


I think the problem can be defined as "Composition without isolation", each composed sequence of instruction has this same global context (all of memory) to work with which can lead to problems.


What he means is that complicated programs can be built from simple parts. In programming languages you can just take simple parts and compose them into a single program.

If the simple parts are given by machines, then in general there is no canonical way of composing them into a machine for the composed program. You have to construct a new machine from the machines for the parts. An example is the sequential composition of two functions with logarithmic space usage. You cannot just use run one machine after the other, but you have to modify both machines and then build a new machine that contains them in the right way.

Of course, one may use systematic constructions to combine simple machines into more complicated ones. But this amounts to the implementation of a programming model.


I think you are confusing the word machine in this context. It is not the usual general purpose word machine that people use in every day life to denote a physical system. The word machine in context of model of computation means a specific type of "formal system" to describe computation. The problem of composition is about how this formal system does or doesn't support it.


No, I do mean formal machines like Turing Machines. Sequential composition of logarithmic space Turing Machines is a standard example for lack of compositionality.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: