lazy evaulation and combining user streams

I was looking at the SICP lectures the other day, and in the part on streams he talks about implementing a system with lazy evaluation, then gives as a example of the "dificulty" in combining streams a system that has 2 users entering data, each with their own stream, and something which has to choose which stream to take the next event from, while combining them into one stream. aparently the "problem" is that they try alternating between user streams, but one of the users may not enter anything for a while, causing the system to wait for him to enter something before continuing.

It would seem to me that the problem here is not in the streams, but in the interface to the keyboard. The keyboard sends events. that means a charactor at a specific moment in time. of course normaly the time gets thrown out, but the event itself should be timestamped as the imput stream. This was even mentioned as a question, which he didn't adress very well.

The next part is what should the keyboard stream return while "waiting" for a keystroke? It should return a "constraint object", which contains not a specifc value, but the constraint that the next data objects timestamp is greater then {current moment}. Then when the system goes to compile the streams, it can compile in timestamp order, and whenever it gets one item from one stream, it can just check the other stream to see if its next objects timestamp is greater then the curent object. Then add the first if it is, or add it if it is not.

To start the process there would have to be a "current time" stream which the current time could be pulled from, and then the referened streams would be checked against it.

Starting a stream access without checking if it's timestamp was less then the current time would be a error that would lock the system up till a event was entered. Just like taking the (cdr `()) is a error.

So i don't see the problem. Is there something wrong with what i put forward, or did this problem just get solved after the videos were made (1980's)?

Combining streams

So i don't see the problem.

As far as I can tell, the problem is how to combine nondeterministically growing streams in a functional programming paradigm. If you have a purely functional language, it can't be done. Your solution, checking object timestamps, is not purely functional! Checking a timestamp is not deterministic: it might say "less than" the first ten times you call it, and then "greater than". This is not functional. So you have solved the problem in the only way how, namely by extending the paradigm with a non-functional operation.

By Peter Van Roy at Mon, 2004-12-13 17:44 | login or register to post comments

clarification

yay. responces! I guess i should have kept checking to see if people responded, even after a few days of nothing. Anyway, sorry for the delay.

I'm thining that I may not have made my idea clear the first time around, so i'm gonna take another stab at it. My idea was that we would have a stream called "current time". whenever you ask for the next number, it gives you whatever the current time is in the real world.

Then we have a compare operator. we say, "do we know if the next object in terminal-io-stream has a timestamp that's greater then the next object in current-time-stream".

Now if the next object in the terminal-io-stream has already been entered by the user, it will be less then the next object in current-time-stream, and referencing the next object in terminal-io-stream would be aproperate. If the next object in the terminal-io-stream has not already been entered, then the timestamp of the next object in terminal-io-stream is greater then the next object in current-time-stream. This will always check the same. The only deterministically vague area would be if you took the current-time, added a year to it, and asked if the next keystroke in the terminal-io-stream's timestamp would be greater or less then that. This would be "don't know". If you wanted to prevent this you could make a type "current-time-object", which could only be made by the current-time-stream, and could not be moddified.

The point here is that I think I've made something deterministic. "current-time" is a object, and whenever you compare 2 objects to each other, you'll get the same result. if you get a new object (i.e. a new time) and compare it to the last terminal-io-stream's timestamp, then of course it could be differnt, just as comparing the next terminal-io-stream's value with "ascii 7" will be differnt.

To see if i've explained this right, I should start with the question: do you agree that this system, the way i have now described it, is now purely functional, while still having io and user interaction?

(this question is to everyone, not just peter :)

By SphereOfDestiny at Mon, 2004-12-20 17:36 | login or register to post comments

...therefore we created AI :-)

If you have a purely functional language, it can't be done.

So it cannot be done by (automatic) Turing machine as well, right?

I cannot help but provide another installment of neverending Turing machine curiosities:

Sir Roger Penrose of Oxford University has argued that the brain can compute things that a Turing Machine cannot, which would mean that it would be impossible to create artificial intelligence. Dr. Siegelmann's work suggests that this is true only for conventional computers and may not cover neural networks.

(quoted from Computer Dictionary Online )

By Andris Birkmanis at Tue, 2004-12-14 08:43 | login or register to post comments

Two cents

I don't think the brain "computes" things. A brain doesn't execute instructions: even if you somehow force someone to, say, solve an arithmetic problem given some procedure, if they fail you cannot conclude that their brain is malfunctioning. In contrast, if a computer is given such a procedure and it fails, then it is malfunctioning by definition.

I think there is a tension and possibly a fundamental conflict between our wanting computers to be our slaves, and at the same time wanting them to be creative, insightful, proactive, even emotional. You cannot have one without the other.

This is, in my mind, related to the tension between wanting to add lots of interacting features to a program and making user interfaces "smart", sometimes even second-guessing the user, and wanting to ensure that a program has a well-defined semantics, one understood by the programmer and/or user, so that you know what will happen when you press this button, click here, follow this procedure, etc.

I guess it's clear where I stand: I want my computer to be my slave; I don't want it second-guessing me; I want to know what my program or application will do without experimentation or guesswork or sending an email to the developers. This is a pretty central part of my philosophy.

If I want creativity or insight or initiative, I will ask a human.

By Frank Atanassow at Tue, 2004-12-14 15:47 | login or register to post comments

AI

This isn't really an either-or proposition. You could quite reasonably do both: make intelligent, creative computers, and keep around some "dumb" computers to do the grunt work.

For me, the main aim of building intelligent machines is to better understand the nature of intelligence. This view of AI is really much closer to philosophy and psychology than computer science, and should probably be correctly referred to as cognitive science. I agree with you that formal techniques are to be preferred to heuristic AI techniques, in areas where formal techniques are known. I also think that as time advances our knowledge of formal techniques increases, and so should be accompanied with a general shift away from AI techniques in mainstream programming. However, this would still leave a legitimate field investigating "intelligence" - whether you call it AI or cognitive science or whatever. This field happens to use computers.

I agree that we should cut down on the second-guessing in applications; it's mostly just annoying. I suspect a trully intelligent machine would also be annoyed by such things. :-)

By Neil Madden at Tue, 2004-12-14 20:33 | login or register to post comments

It can't be done

So it cannot be done by (automatic) Turing machine as well, right?

Yes, it's a question of levels of abstraction. If you implement a Turing machine on top of your functional language, then it may seem that all of a sudden it can be done. But this is not true, and there's no contradiction. The Turing machine lives in its own carefully encoded world. Whatever seems like nondeterminism in this world is actually implemented by determinism. Real nondeterminism still cannot be handled there.

Penrose has a valid point!

By Peter Van Roy at Tue, 2004-12-14 11:49 | login or register to post comments

Brains are not really needed for that

Penrose has a valid point!

But my point was that even a "conventional" computer can do that (though Turing machine or a pure FPL cannot).

By Andris Birkmanis at Tue, 2004-12-14 12:02 | login or register to post comments

Threaded state

Peter's arguments about the need for state are interesting, because pure functional languages do have a variety of mechanisms for dealing with state (usually some form of threaded state, as with monads or CPS) and in order to argue the necessity of freely-mutable state you need to demonstrate that these mechanisms are inadequate or too cumbersome.

Even then, I'm not sure that there's any program written in a language that permits free mutation of state that could not be converted into a program in a language that uses threaded state. FRP (functional reactive programming) could probably be used to handle the stream-combining problem, for instance.

By Dominic Fox at Tue, 2004-12-14 12:46 | login or register to post comments

It's an interactive problem

I suspect that Peter was meaning PL's interface to the world (such as lazy streams or IO monad), not internal implementation (which can use free mutation of state or threaded state or whatever).

In this respect, "really" pure FPLs must behave just like Turing machine - take input, run, terminate with output. No interaction allowed.

The original problem (which was visualized as a chess server independently playing with two opponents in Computability Logic¹) is inherently interactive, and awkward to deal with in many logics.

¹See page 10. Another amusing use case considers both wife and boss of a person as his simultaneous adversaries.

By Andris Birkmanis at Tue, 2004-12-14 13:12 | login or register to post comments

Lambda the Ultimate

User login

Navigation