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
