Yes, thanks, Wolfgang! I now see that what was "pulling" on Cs and Zeros, causing infinite expansion of the lazy list, was the final FullAdder: the one that adds Zeros, Zeros and the final bit of Cs. Unlike the other adders, this one is always able to create new list elements on demand. Using your advice, I could just tie the creation of new elements of Zeros to availability of the corresponding element of Xs, and the problem went away.
So, it wasn't the laziness that's caused the problem, but the laziness isn't necessary. It was the lack of dependency between the auto-generated input (Zeros) and the user input (Xs, Ys) that was causing the problem. Anyway, I think it's more appropriate to do the problem without laziness, because it's a question about a part of the chapter before laziness was introduced. Maybe I'm just not used to the debugger yet, but I had a hard time using it to figure out what was going on. It would be nice, when there's a ByNeed triggered, to be able to determine what triggered it. - Lyle On Fri, Jan 1, 2010 at 2:35 PM, Wolfgang Meyer < [email protected]> wrote: > Dear Lyle, > > the digital logic simulation code in CTM works by concurrently waiting > for new input. In you example, you use infinite lazy sequences. These > sequences will be consumed by the gates because the GateLoop function > is not lazy. > New threads are created because laziness is implemented using threads > (which are cheap in Oz). > > One way to fix this is to make the infinite sequences in your example > concurrently depending on the input instead of lazy. See the changed > definitions for Repeat and LMap: > > --------------- > > declare > fun {GateMaker F} > fun {$ Xs Ys} > fun {GateLoop Xs Ys} > case Xs#Ys of (X|Xr)#(Y|Yr) then > {F X Y}|{GateLoop Xr Yr} > end > end > in > thread {GateLoop Xs Ys} end > end > end > > AndG ={GateMaker fun {$ X Y} X*Y end} > OrG ={GateMaker fun {$ X Y} X+Y-X*Y end} > NandG={GateMaker fun {$ X Y} 1-X*Y end} > NorG ={GateMaker fun {$ X Y} 1-X-Y+X*Y end} > XorG ={GateMaker fun {$ X Y} X+Y-2*X*Y end} > > proc {FullAdder X Y Z ?C ?S} > K L M > in > K={AndG X Y} > L={AndG Y Z} > M={AndG X Z} > C={OrG K {OrG L M}} > S={XorG Z {XorG X Y}} > end > > % Z0s=0|0|0|... > % {FullAdder X1s Y1s Z0s C1s S1s} > % {FullAdder X2s Y2s C1s C2s S2s} > % {FullAdder X3s Y3s C2s C3s S3s} > % {FullAdder Z0s Z0s C3s _ S4s} > > fun {Repeat In F} > thread > {Map In fun {$ _} {F} end} > end > end > > fun {LMap Xs F} > thread > case Xs > of nil then nil > [] X|Xr then {F X}|{LMap Xr F} > end > end > end > > local > Bit > in > fun {Bit N Xs} > {LMap Xs fun {$ X} X.N end} > end > > proc {ChainedAdder Xs Ys ?Ss} > N Cs > Zeros={Repeat Xs fun {$} 0 end} > in > N={Width Xs.1} > > Cs={Repeat Xs fun {$} {MakeTuple '#' N+1} end} > Ss={Repeat Xs fun {$} {MakeTuple '#' N+1} end} > > {Browse cs#Cs} > {Browse ss#Ss} > > {Bit 1 Cs}=Zeros > > for I in 1..N do > {FullAdder {Bit I Xs} {Bit I Ys} {Bit I Cs} {Bit I+1 Cs} {Bit I > Ss}} > end > > {FullAdder Zeros Zeros {Bit N+1 Cs} _ {Bit N+1 Ss}} > end > end > > X=(0#1#1)|_ > Y=(1#0#1)|_ > S > > {ChainedAdder X Y S} > {Browse inp(X Y)#sum(S)} > > --------------- > > Another possibility would be to make the whole circuit simulation > lazy. However, just adding "lazy" to the GateLoop function doesn't > seem to be enough. I didn't explore that alternative any further so > far... > > Cheers, > Wolfgang > > > On 1/1/10, Lyle Kopnicky <[email protected]> wrote: > > Hi folks, > > > > I'm new to the list. I've been reading CTM, and I attempted to solve > > Exercise 9 in Chapter 4. This involves creating a "gate" that adds > together > > two numbers by chaining full adders. I decided to encode the multiple > bits > > of a number as a tuple. Unfortunately, although my code produces the > correct > > result, it runs away with creating new threads. Although I've figured out > > that it keeps extending Cs, I don't know why. The key procedure to look > at > > is ChainedAdder. The top section (up through the declaration of > FullAdder) > > is copied straight from 4.3.5. > > > > I've run this through the debugger, and I can watch some threads being > > created, but the runaway threads seem to be coming from nowhere. Any > ideas? > > > > Thanks, > > Lyle Kopnicky > > > > declare GateMaker > > fun {GateMaker F} > > fun {$ Xs Ys} > > fun {GateLoop Xs Ys} > > case Xs#Ys of (X|Xr)#(Y|Yr) then > > {F X Y}|{GateLoop Xr Yr} > > end > > end > > in > > thread {GateLoop Xs Ys} end > > end > > end > > > > declare AndG OrG NandG NorG XorG > > AndG ={GateMaker fun {$ X Y} X*Y end} > > OrG ={GateMaker fun {$ X Y} X+Y-X*Y end} > > NandG={GateMaker fun {$ X Y} 1-X*Y end} > > NorG ={GateMaker fun {$ X Y} 1-X-Y+X*Y end} > > XorG ={GateMaker fun {$ X Y} X+Y-2*X*Y end} > > > > > > declare FullAdder > > proc {FullAdder X Y Z ?C ?S} > > K L M > > in > > K={AndG X Y} > > L={AndG Y Z} > > M={AndG X Z} > > C={OrG K {OrG L M}} > > S={XorG Z {XorG X Y}} > > end > > > > > > % Z0s=0|0|0|... > > % {FullAdder X1s Y1s Z0s C1s S1s} > > % {FullAdder X2s Y2s C1s C2s S2s} > > % {FullAdder X3s Y3s C2s C3s S3s} > > % {FullAdder Z0s Z0s C3s _ S4s} > > > > declare Repeat > > fun lazy {Repeat F} > > {F}|{Repeat F} > > end > > > > declare Zeros > > Zeros={Repeat fun {$} 0 end} > > > > declare LMap > > fun lazy {LMap Xs F} > > case Xs > > of nil then nil > > [] X|Xr then {F X}|{LMap Xr F} > > end > > end > > > > > > declare ChainedAdder > > local > > Bit > > in > > fun {Bit N Xs} > > {LMap Xs fun {$ X} X.N end} > > end > > > > proc {ChainedAdder Xs Ys ?Ss} > > N Cs > > in > > N={Width Xs.1} > > > > Cs={Repeat fun {$} {MakeTuple '#' N+1} end} > > Ss={Repeat fun {$} {MakeTuple '#' N+1} end} > > > > {Browse cs#Cs} > > {Browse ss#Ss} > > > > {Bit 1 Cs}=Zeros > > > > for I in 1..N do > > {FullAdder {Bit I Xs} {Bit I Ys} {Bit I Cs} {Bit I+1 Cs} {Bit I > > Ss}} > > end > > > > {FullAdder Zeros Zeros {Bit N+1 Cs} _ {Bit N+1 Ss}} > > end > > end > > > > > > declare > > X=(0#1#1)|_ > > Y=(1#0#1)|_ > > S > > > > {ChainedAdder X Y S} > > {Browse inp(X Y)#sum(S)} > > > > % END OF FILE > > > _________________________________________________________________________________ > > mozart-users mailing list > > [email protected] > > http://www.mozart-oz.org/mailman/listinfo/mozart-users > > > > _________________________________________________________________________________ > mozart-users mailing list > [email protected] > http://www.mozart-oz.org/mailman/listinfo/mozart-users >
_________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
