My OS Design

[Candy]

I've coded a Lisp interpreter that does this, but I've never found a way to make the idea work for a compiled language. Due to that, the interpreted version takes a long time to run even simple programs.

However, it is *massively* powerful in terms of available semantics. That seems like a pattern for Lispy and symbolic stuff.

This version works and runs with just this header and anything else you might want to throw at it. Just for fun I've tried to make it work with strings and it required two minor changes in the header to make them work flawlessly, but the concept applied cleanly to both. The improvements are not assigning 0 but T() to a new object (you can't assign 0 to a string, so you have to specify initializers - could be cleaner) and adding an ostream &operator<<(...) for the types so that you can debug easily. Combining strings works just the same as the rest.

I've also cracked up another bit in my quest for learning c++0x, but this bit compiles using the current compiler (since I hit a wall with c++0x). It allows you to wrap an arbitrary operation from type X and type X to type X into a dynamic operation, so you can just use any function you like instead of predefined operators. I'm hoping to get this to any generic function you like (but that requires changing a small design issue in the code that also makes it a bit slower).

m, you have ideas on how to make environment-aware code compile and run with decent speed?

You should be able to run this with decent speed, especially since unused expressions are never evaluated and unused operators aren't even compiled. The bits you can strip out to make this compile without any environment support are iosfwd (strip out the ostream &operator<< and it can go) and vector (replace with whatever you prefer). They are the only thing tying it to a userland environment right now. The easiest thing for the vector is a static array that limits subscription, but that either wastes memory or limits functionality. You can of course change the subscription code to give an error when that happens so you can use it for anything.

[Candy]

Just can't let it rest. Blame me for it, but here goes nothing.

Made a quick change to the previous version (which I forgot to upload - will follow) that removes the operator<< and replaces the vector with an arbitrary-size array, removing *all* dependencies on anything existing. You can attach an ELF header and let Grub load it up if you like. There's an if (without content) indicating the check for the limit, around the 330th line.

Regards & really hoping for response
Candy

[m]

Hi.

Candy wrote:

Regards & really hoping for response

First of all I'm thankful that you've spent so much time on this.
I think I've learnt a lot from both your idea and your code(I read your code with my knowledge of C and Java,along with some necessary references about C++ stantards,because I'm new in C++:?).

Inspired by your implementation,I've been trying out a model of the DV using Java(at first I wanted to put the concepts into assembly code for my OS core directly instead of making a model in advance,but now I think a model written with a high-level language can be of great use,and I've totally changed my attitude towards the OO implementation).

I don't know if C++ has such mechanisms similar to Java's RTTI and the REFLECTION.They can be useful for the DV implementation,as they can support the DV during runtime,especially for the combined version,whose DVs are all applied or registered through a central processing object.I'll try to take advantage of these mechanism(this may take some time).

Candy wrote:

I just now thought up, you can probably use it with strings as well.

In fact,if you make a fixed-size RAM block dynamic,you can make the data of any type dynamic in that area(and other non-dynamic data areas can be used to put in the temp data which you don't intend to let other DVs use).But your words remind me of something else.Despite the strict expectation of the speed,maybe you can pass a string(ASCII) parameter as the name of a DV which you request to get.

[m]

Hi.

I've been busy with my lessons these days and have little time to visit here.

I've finished a DV model using Java.But I didn't make use of the reflection or RTTI.What's more,it's a little DIFFERENT from what I expected.Besides I haven't tested it completely(there seems to be somethig wrong).

-This is only a model for DV.So it just describe how it would be implemented in my OS but may not be effective in a Java application.If the methods announce() takes more time than a direct recalculation,that it is used in a Java application is meaningless.(In fact,in order to get the same purpose,you can call the respective ADT EVERY TIME before you get a value.)
-Again this is a model,so the expression may not look like a common expression in Java.Instead it's contained in calc().(Candy's looks more natural,in the earlier version,I think,but I haven't read the later one.)
-All the DVs make up a peer structure.And if one depends on another ALL THE TIME,it should call apply() in itself for a registration.But it only wants to get the value once,just as a CONSTANT,it doesn't need to.
-Please notice the difference between processing a DV with an expression or a DV with only a constant(they can convert to each other during runtime).
-In fact,it should work much better if multitasking/multithreading is combined.What I think is that it may be efficient to create a Thread object whose Runnable object is designed for updating every DV evry period of time and another to response the I/O.

Here isthe code:

DynVar.java

Code: Select all

/*
 * This version of Dynamic Variables is only available for integers.
 * Other data types can be implemented in similar ways.
 */

public abstract class DynVar {
	
	//Values of a DV:
	private int stableVal;//This one is for its internal use.
	protected int currentVal;//This one can be read by other DVs through get().
	//A sign to indicate if the value should be updated.
	private boolean updated;
	//A sign to indicate if this DV is a constant.
	private boolean isConst;
	//2 Audience reference related to its audiences,used as 2 pointers.
	private Aud firstAud=new Aud(null),lastAud=firstAud;
	
	//The 2 constructors;
	public DynVar(int thisConstant){
		currentVal=thisConstant;
		stableVal=currentVal;
		isConst=true;
		updated=true;
	}
	public DynVar(){
		isConst=false;
		updated=false;
	}
	
	//Other DVs should use this method to read stableVal,which is automatically updated.
	public int get(){
		if(!updated) update();
		return stableVal;
	}
	
	//Use this if you want to update this DV besides it's automatically updated when get() is called.
	public void update(){
		if(!isConst) currentVal=calc();
		if(stableVal!=currentVal){
			stableVal=currentVal;
			announce();
		}
		updated();
	}
	
	//Execute it if any its dependent DV's value is modified.
	public void updatingRequest(){
		updated=false;
	}
	
	private void updated(){
		updated=true;
	}
	
	//When this DV's value is modified,let other DVs whose calculation depend on it know.
	private void announce(){
		Aud audPointer=firstAud;
		while(audPointer.getNext()!=audPointer){
			audPointer.getDV().updatingRequest();
			audPointer=audPointer.getNext();
		}
	}
	
	//To process another DV's request of applying.
	public void register(DynVar DVtoRegister){
		lastAud=new Aud(DVtoRegister);
		lastAud=lastAud.getNext();
	}
	
	//To process another DV's request of disconnecting.
	public void remove(DynVar DVtoRemove){
		Aud audPointer1=firstAud,audPointer2=firstAud;
		while(audPointer1.getNext()!=audPointer1){
			if(audPointer1.getDV().equals(DVtoRemove)){
				audPointer1.setNext(audPointer1.getNext().getNext());
				audPointer1.setNext(audPointer1.getNext().getNext());
				audPointer1.setNext(audPointer1.getNext());
				if(!audPointer2.equals(firstAud)) audPointer2=audPointer2.getNext();
			}else{
				audPointer1.setNext(audPointer1.getNext());
				if(!audPointer2.equals(firstAud)) audPointer2=audPointer2.getNext();
			}
		}
	}
	
	//Call this if this this DV itself depend on another DV's value all the time.
	public void apply(DynVar DVtoRegisterTo){
		DVtoRegisterTo.register(this);
	}
	
	public void disapply(DynVar DVtoDisapplyFrom){
		DVtoDisapplyFrom.remove(this);
	}
	
	public void modify(int newConst){
		currentVal=newConst;
		isConst=true;
		update();
		announce();
	}
	
	protected abstract void applyAll();
	
	protected abstract int calc();
	
}

Aud.java

Code: Select all

/*
 * This class is used for announce() and register() in DynVar.
 * Generally speaking,its objects together make a linked list for the methods mentioned above to go through all the audiences.
 */

public class Aud {
	
	//The DV in this audience.
	private DynVar myDV;
	//Its neighbor Aud.
	private Aud nextAud=new Aud(null);
	
	public Aud(DynVar thisDV){
		myDV=thisDV;
	}
	
	public DynVar getDV(){
		return myDV;
	}
	
	public void setDV(DynVar newDV){
		myDV=newDV;
	}
	
	public void setNext(Aud next){
		nextAud=next;
	}
	
	public Aud getNext(){
		return nextAud;
	}

}

DynVar1.java

Code: Select all

public class DynVar1 extends DynVar{
	
	private DynVar x,y;
	
	public DynVar1(DynVar a,DynVar b){
		super();
		x=a;
		y=b;
		applyAll();
	}
	
	protected void applyAll(){
		apply(x);
		apply(y);
	}
	
	protected int calc(){
		return x.get()+y.get();
	}

}

DynVar2.java

Code: Select all

public class DynVar2 extends DynVar{
	
	private DynVar x,y;
	
	public DynVar2(DynVar a,DynVar b){
		super();
		x=a;
		y=b;
		applyAll();
	}
	
	protected void applyAll(){
		apply(x);
		apply(y);
	}
	
	protected int calc(){
		return x.get()-y.get();
	}

}

DynVar3.java

Code: Select all

public class DynVar3 extends DynVar {
	
	public DynVar3(int thisConst){
		super(thisConst);
	}
	
	protected int calc(){
		return currentVal;
	}
	
	protected void applyAll(){
		
	}
}

Main.java

Code: Select all

public class Main {

	public static void main(String[] args) {
		DynVar DynVarX=new DynVar3(5);
		DynVar DynVarY=new DynVar3(10);
		DynVar DynVarA=new DynVar1(DynVarX,DynVarY);
		DynVar DynVarB=new DynVar2(DynVarX,DynVarY);
		System.out.println(DynVarA.get());
		System.out.println(DynVarB.get());
		DynVarA.remove(DynVarX);
		DynVarX.modify(6);
		System.out.print(DynVarA.get());
		System.out.print(DynVarB.get());
	}
	
}

There're totally 7 files included.The classes DynVar1,DynVar2,DynVar3 and Main are used for testing.
Some of the comments are not complete.I will edit them later(and test them further,too).

[m]

Sorry,I tested my code but it dosen't work.Now I've got to spend more time debugging...

[Candy]

I've finished a DV model using Java.But I didn't make use of the reflection or RTTI.What's more,it's a little DIFFERENT from what I expected.Besides I haven't tested it completely(there seems to be somethig wrong).

I'd only use reflection explicitly when there's no other option or where the other options would severely limit your design. I've used it once, so it's not a complete forbiddance, it's just a strong disrecommendation.

-This is only a model for DV.So it just describe how it would be implemented in my OS but may not be effective in a Java application.If the methods announce() takes more time than a direct recalculation,that it is used in a Java application is meaningless.(In fact,in order to get the same purpose,you can call the respective ADT EVERY TIME before you get a value.)

Direct recalculation is almost always quicker. The few times it isn't is when the other side really doesn't care about the value or only asks it every X seconds or so, where you never calculate the new value.

-Again this is a model,so the expression may not look like a common expression in Java.Instead it's contained in calc().(Candy's looks more natural,in the earlier version,I think,but I haven't read the later one.)

The second version is identical with a few minor bugs removed and a generic function wrapper and functionality. The concept is still the same.

-All the DVs make up a peer structure.And if one depends on another ALL THE TIME,it should call apply() in itself for a registration.But it only wants to get the value once,just as a CONSTANT,it doesn't need to.

My components make a syntax tree for the expression given in objects and keep booleans to indicate when what needs updating. For the rest, they're value objects. When you want to assign as an expression, use the object, otherwise use the value (.value()). This is pretty much the reason why I can't have an operator T() which gives the value, these cases would be ambiguous.

-Please notice the difference between processing a DV with an expression or a DV with only a constant(they can convert to each other during runtime).

I've chosen to keep them identical for ease of code control and simplicity. All constants and such are variables. If they're a number, you just can't change them (since you can't assign to a number).

-In fact,it should work much better if multitasking/multithreading is combined.What I think is that it may be efficient to create a Thread object whose Runnable object is designed for updating every DV evry period of time and another to response the I/O.

How do you make dynamic variables cooperate with threads? I'm missing most of the things they could do using threads.

I was still going to add the "optional" thing where you assign a value, and if a dyn<bool> evaluates to true, the value is substituted with a newer value. That would also make the change info sending more logical, since you can then actually have a function not change because of some other function to which it is listening. You could also make it not listen... hmm....

There's also another architectural error in my current code that prevents a variadic template function call from working properly. The error is that the listening is done with a template interface. You need to implement the template interface exactly once for each type you want to listen to. So if you have a function that uses two arguments of the same type, that's an error. Functions between two identical parameters are pretty common though, so that's a problem. Yet, you can solve this up to a level with a bit of template magic. That magic would completely fall to bits when you make the template variadic. Making the interface either non-template or making the implementation of the interface into a separate object fixes this problem. I'm mostly thinking of the first.

Forwarding the values themselves would work but could give problems with the second item, the variadic template idea. You'd have to make the passed type a void * or such to make that work properly which would completely remove the functionality. From a point of mathematics, you'd want to be able to make the == operator somehow associative, so that the software evaluated the entire expression into some way of making it correct. I'm not sure whether that can be useful though, since it can give a number of problems (unsolvable functions, functions with more than one answer, functions with variables that don't matter at all).

I've just thought up another thing you could do with this dynamic variable idea. You could represent the nodes of an FPGA by a dynamic variable each and make the computer perform all calculations. After the aforementioned changes it'll work properly for all types of object, although true infinite loops need a fix (hack) for not thrashing the stack (thereby causing a stack overflow).

[m]

Hi.

Candy wrote:

How do you make dynamic variables cooperate with threads? I'm missing most of the things they could do using threads.

and

Direct recalculation is almost always quicker. The few times it isn't is when the other side really doesn't care about the value or only asks it every X seconds or so, where you never calculate the new value.

When the value of a DV is accessed at a very high frequency(for example,a DV is being continuiosly displayed on the screen),the whole process will work more effectively than in the situation where the other side "only asks it every X seconds or so".However,if the first situation occurs,in order to keep the whole program running fluently(i.e.,to avoid the condition that the calculation of a complicated DV eats up too much CPU time piece),a multitasking mechanism is necessary.Even if the calculation is out of the time piece limit,other DVs can access its stable value(the current external one,because the updated bit is still set and clearing the updated bit is the last step of the recalculation).We can have 2 kinds of threads.One is the users' which request to apply for a DV or access a DV and the other is part of the system which updates the DVs at a fixed frequency(to avoid the burst request flow).

I've had such a view for long,but I'm not sure it will work in the way I have expected(perhaps it won't and you can figure out what you think of this).

By the way,the second quote here is the exact conclusion which describes in what condition can the DV work for the highest efficiency(that short paragraph solves my problem all about when a DV is essential).

I haven't find all the errors in my code.But after valuing all what you wrote,I'm going to write a better model for that after the first one is ok.

Again thanks a lot for your attention and advice.

[m]

Hi.

Candy wrote:

Direct recalculation is almost always quicker. The few times it isn't is when the other side really doesn't care about the value or only asks it every X seconds or so, where you never calculate the new value.

Err...Now I doubt the words.

When calculation is needed,it is the updating notification that may take as much time as the calculation itself does(testing updating request,which is done before the value is returned,takes little time indeed).However,the notification can be after returning the value and in this way it won't affect the response speed as much as direct recalculation does,because if the notification isn't done,the whole chain-like expressions will be entirely recalculated EVERY TIME when accessed as the expressions that are necessary to be recalculated are not indicated(and if it's not done,the synchronization fails).So if the expression chain is very long,the calculation proberbly takes up more time than the notification(I mean then dynamic variables are preferred).But if the chain is pretty short(for example,only a few expressions are the nodes),direct recalculation is preferred.

In a word,whether to use direct recalculation or to use dynamic variables(the notification,like the listener-related parts in Candy's code or announce() and updatingRequest() in my code) shouldn't mainly be judged by the frequency of accessing,it mainly depends on the complexity of the inter-reference(I think).

Maybe it's necessary to decide which recalculation to use at different occasions.

[Candy]

When calculation is needed,it is the updating notification that may take as much time as the calculation itself does(testing updating request,which is done before the value is returned,takes little time indeed).However,the notification can be after returning the value and in this way it won't affect the response speed as much as direct recalculation does,because if the notification isn't done,the whole chain-like expressions will be entirely recalculated EVERY TIME when accessed as the expressions that are necessary to be recalculated are not indicated(and if it's not done,the synchronization fails).So if the expression chain is very long,the calculation proberbly takes up more time than the notification(I mean then dynamic variables are preferred).But if the chain is pretty short(for example,only a few expressions are the nodes),direct recalculation is preferred.

In a word,whether to use direct recalculation or to use dynamic variables(the notification,like the listener-related parts in Candy's code or announce() and updatingRequest() in my code) shouldn't mainly be judged by the frequency of accessing,it mainly depends on the complexity of the inter-reference(I think).

Maybe it's necessary to decide which recalculation to use at different occasions.

If you have a convoluted variable that is read out every time, you still need to calculate it at every change. The only advantage I can see is with a variable that is one of a number of long calculations, selected by a different function. In that case, all functions are notified once (worst-case) and then only the selected function is notified of change (since the rest had already indicated a change but for which the change wasn't relevant). You'd need a switch-like function for that.

One advantage of direct calculation is that it's a push-mechanism as opposed to pull. You can make recursive functions in a push mechanism (since it recurses to itself after knowing the new value) but you can't do that in a pull mechanism (since it can't calculate its own new value without knowing its own new value, infinite recursion).

[m]

Hi.

Thanks for your reply.I'm still considering the advantages and the disadvantages of dynamic variables.

Here's something else I've just thought up.

The dynamic variable is nothing new indeed.In theory it's exactly a form of event-drive mechanism(like that in Javascript).For example,in Javascript,we have to write event handler in ordr to response the events activated by other components in the page.The modification of a dynamic variavle is just a type of event and the updating in dynamic variables is just a type of event handler.The notification just plays a role of the media.And the whole process is an internal complete event process.Despite the fact above and its specific purpose,it really fits the event-drive model.(Still I'm wondering how Javascript interpreter achieves that...)

Isn't it?