I have a deep appreciation for formalisms like the Turing Machine and the $\lambda$-Calculus, and enjoy studying them and learning more about how they relate to physical computers. I am now learning about writing GUI programs, and the graphical library (GTK) relies on things like signals and callbacks, which I have not seen modeled by either Turing Machines or the $\lambda$-Calculus; can either the $\lambda$-Calculus or Turing Machines model things like signals, callbacks, sleeping/waiting, or buses? If so, where can I find some good reference material to learn more? If not, why not? and are there any formalisms which are capable of expressing such things?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ Consider the $\pi$-calculus! $\endgroup$– Dave ClarkeJun 20, 2013 at 6:05
-
$\begingroup$ What do you mean by model? Signals, callbacks, sleeping/waiting and buses do not add any power to the computing model (such systems can compute no more than what a TM could), but they might be capable of doing things faster than a TM would (RAM models can decide languages of palindromes in under $O(n^2)$, but good luck coming up with a single-tape Turing machine that can do better. $\endgroup$– Patrick87Jun 20, 2013 at 15:43
-
1$\begingroup$ @BlueBomber yes, TMs and the $\lambda$-calculus can model such features (of course what modelling means is a difficult question, as Patrick87 says), but the quality of the model is low, see e.g. here for a related discussion. A much better model are, as D. Clarke remarks, the various $\pi$-calculi. I suggest to start with the asynchronous $\pi$-calculus, the simplest of the lot, and yet extremely expressive. $\endgroup$– Martin BergerJun 20, 2013 at 17:00
-
$\begingroup$ @Patrick87, Martin Berger, I suppose what I mean by "model" is "encode", in the same way that the Church encoding of natural numbers is how the $\lambda$-calculus "models" (or one of the ways it can "model") the natural numbers. I can see how the $\lambda$-calculus can model basic types, aggregate types, recursion, let-binding, and many other PL features, but I don't yet see how we can model the things mentioned by this question. $\endgroup$– BlueBomberJun 21, 2013 at 15:02
-
$\begingroup$ Would Haskell count? $\endgroup$– Christopher KingJun 15, 2015 at 22:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Yes, there are natural extensions of the $\lambda$-calculus for handling I/O, parallelism, concurrency, exceptions, timeouts, etc. In general such things are viewed as computational effects and there is a rich theory of $\lambda$-calculus for computational effects. This is what Haskell monads are about -- Haskell is $\lambda$-calculus extended with features that you are asking about.
But let me point out that you mix a bunch of features together which are really of two different kinds:
- Interaction with external environment: I/O, communication, timeouts, concurrency, etc.
- Programming models: callbacks, semaphores, shared memory, parallelism, etc.
A classical Turing machine does not interact with an external environment, but it can be modified to do so. For instance, an oracle is essentially an input stream. The so-called "type 2 machines" are Turing machines with infinite input and output tapes which correspond to an input and an output channel, etc. I am sure someone invented "real-time Turing machines", but I think such endaveours miss the point of mathematical models of computation. A mathematical model is designed specifically to fit well a chosen set of features that we want to model. Turing machines were invented to explain what "possible to compute" means, not "how to compute". If you want to model I/O and such then there are better mathematical models to stick to ($\pi$-calculus was suggested by someone).
The second set of features you asked about is really a bunch of programming methods. As is well known, any Turing complete computational model can be used to simulate any other such model. For instance, a Turing machine can compute things in parallel through a technique known as dovetailing. I would not be surprised if dovetailing was invented several decades before the first parallel operating sytem came into existence. (In fact, it must be the case that dovetailing appreaded already in Turing's original 1936 paper, can someone confirm this?)
Callbacks are well known to functional programers, as these are just functions (but if you spend your life programming operating systems in C you will think they are special), while threads and coroutines are known as continuations. So some concepts that look fancy from one perspective are basic and straightforward from another. Another that comes to mind is the object-oriented idea of an "iterator" which gets vastly generalized in functional programming.
answered Sep 18, 2013 at 18:41
$\begingroup$
$\endgroup$
This question mixes two disparate areas of CS and attempts to use analogies that are relevant in one realm in the other realm (or in English vernacular "mixing apples and oranges"). On one end of the spectrum, Turing machines (TM) are an abstraction to understand computation. On the other end of the spectrum are practical "design patterns" and software architecture concepts such as "signals", "callback functions," "GUI" APIs etc.
A TM can implement any programming design pattern hence the term "Turing complete". However, this would require a TM compiler for a high-level language. Apparently almost nobody has written actual high-level language compilers for TMs. The theoretical crowd would regard it as a waste of time and the practical/pragmatic/applied crowd do also. So the theory guarantees it can be done, but not beyond that.
In at least one item you're missing the nearly obvious: in $\lambda$-calculus a lambda function can also function as a "callback".
Buses are more of an EE concept. Signals, sleep, and wait are modelled with threads, processes, or parallelism.
