6 ms·

> Why do you feel there is a mismatch? Can this be because in digital circuits state (memory) plays an important role, while its treatment in a (pure) function

> Why do you feel there is a mismatch? Can this be because in digital circuits state (memory) plays an important role, while its treatment in a (pure) functional language is not straightforward?

rowanG077 5y ago
It's straightforward to implement memory in a pure function. For example if you say a digital circuit is a function from infinite list of inputs to an infinite list of outputs. You can create a "register" by simply adding a value to the start of the list. For example in Haskell: delayCircuit xs = 0:xs take 10 (delayCircuit [1..]) -- [0,1,2,3,4,5,6,7,8,9] Whether a function is pure doesn't mean it can't have internal state. As another example it's perfectly fine to have a completely pure function that has internal state: withInternalState a = let go = get >>= \s -> put (s + 1) in fst (runState go a) What is important for purity is that this internal state doesn't leak outside the function. Which it doesn't for circuits. Outside of things like cosmic rays, heating etc a circuit is completely pure in reality.
- magicalhippo 5y ago
  > Whether a function is pure doesn't mean it can't have internal state. This seems to be in direct contradiction to what is written on Wikipedia[1], specifically that "the function return values are identical for identical arguments". If it has non-trivial internal state, how can it return identical values for identical inputs? Sadly your example eludes me as I don't know any Haskell so it reads like line noise. [1]: https://en.wikipedia.org/wiki/Pure_function https://en.wikipedia.org/wiki/Pure_function
  - rowanG077 5y ago
    It does have identical return values for identical arguments. That doesn't mean the function can't have internal state. Maybe this is more clear in pseudo code: withInternalState(x): buf = Int[100000] buf.fill(x) return buf.sum() The function is pure yet it uses a very large buffer as internal state. That is the same as a circuit that has a internal state(== memories). Could you give a description of a circuit that isn't pure, maybe we are talking past eachother.
    - magicalhippo 5y ago
      What I was thinking of was more like a linear shift feedback register. It has zero inputs and outputs random bits, thanks to its non-trivial internal state. Or as we were saying, a register. Could for example be a function which takes a read/write flag and a value, writes the value to the internal state if write flag is set, and returns the internal value. edit: In my softcore I have a function to read/write registers, it modifies global state rather than internal state so would not be pure either. edit2: I guess my point is, for me "state" is something that is non-trivial, and retained between invocations. Your example is trivial and not retained (it's completely overwritten always).
      - magicalhippo 5y ago
        So your point is you can have temporary variables in pure functions. That's fine. However how do you implement registers? Do you have to pass around the "register file"? And if so, how does that work? Like, how would a parallel-to-serial shift register look like? Ie an asynchronous latch updates the internal shift register and an independent clock shifts out the values.
      - rowanG077 5y ago
        You are seeing a single invocation as running your circuit for a single clock cycle after an arbitrary amount of clock cycles. That's the wrong approach. A single invocation of a circuit takes a stream of values and produces a stream of values. Every invocation start from clock cycle 0. So yes if your circuit depends on external signals driven by registers living in a different circuit you need to pass those in as inputs. Essentially circuits are composeable just like functions. A linear feedback shift registers always produces the same stream of values no matter how many times you run it. It's completely pure.
        magicalhippo 5y ago
        I think I get what you're getting at. Still, I would be very interested to see how one would implement a shift register, lets say something like the 74HC165, so I can see how the pure functions interact with the register state.

> Why do you feel there is a mismatch? Can this be because in digital circuits state (memory) plays an important role, while its treatment in a (pure) functional language is not straightforward?

rowanG077 5y ago

It's straightforward to implement memory in a pure function. For example if you say a digital circuit is a function from infinite list of inputs to an infinite list of outputs. You can create a "register" by simply adding a value to the start of the list. For example in Haskell: delayCircuit xs = 0:xs take 10 (delayCircuit [1..]) -- [0,1,2,3,4,5,6,7,8,9] Whether a function is pure doesn't mean it can't have internal state. As another example it's perfectly fine to have a completely pure function that has internal state: withInternalState a = let go = get >>= \s -> put (s + 1) in fst (runState go a) What is important for purity is that this internal state doesn't leak outside the function. Which it doesn't for circuits. Outside of things like cosmic rays, heating etc a circuit is completely pure in reality.

magicalhippo 5y ago
> Whether a function is pure doesn't mean it can't have internal state. This seems to be in direct contradiction to what is written on Wikipedia[1], specifically that "the function return values are identical for identical arguments". If it has non-trivial internal state, how can it return identical values for identical inputs? Sadly your example eludes me as I don't know any Haskell so it reads like line noise. [1]: https://en.wikipedia.org/wiki/Pure_function https://en.wikipedia.org/wiki/Pure_function
- rowanG077 5y ago
  It does have identical return values for identical arguments. That doesn't mean the function can't have internal state. Maybe this is more clear in pseudo code: withInternalState(x): buf = Int[100000] buf.fill(x) return buf.sum() The function is pure yet it uses a very large buffer as internal state. That is the same as a circuit that has a internal state(== memories). Could you give a description of a circuit that isn't pure, maybe we are talking past eachother.
  - magicalhippo 5y ago
    What I was thinking of was more like a linear shift feedback register. It has zero inputs and outputs random bits, thanks to its non-trivial internal state. Or as we were saying, a register. Could for example be a function which takes a read/write flag and a value, writes the value to the internal state if write flag is set, and returns the internal value. edit: In my softcore I have a function to read/write registers, it modifies global state rather than internal state so would not be pure either. edit2: I guess my point is, for me "state" is something that is non-trivial, and retained between invocations. Your example is trivial and not retained (it's completely overwritten always).
    - magicalhippo 5y ago
      So your point is you can have temporary variables in pure functions. That's fine. However how do you implement registers? Do you have to pass around the "register file"? And if so, how does that work? Like, how would a parallel-to-serial shift register look like? Ie an asynchronous latch updates the internal shift register and an independent clock shifts out the values.
    - rowanG077 5y ago
      You are seeing a single invocation as running your circuit for a single clock cycle after an arbitrary amount of clock cycles. That's the wrong approach. A single invocation of a circuit takes a stream of values and produces a stream of values. Every invocation start from clock cycle 0. So yes if your circuit depends on external signals driven by registers living in a different circuit you need to pass those in as inputs. Essentially circuits are composeable just like functions. A linear feedback shift registers always produces the same stream of values no matter how many times you run it. It's completely pure.
      - magicalhippo 5y ago
        I think I get what you're getting at. Still, I would be very interested to see how one would implement a shift register, lets say something like the 74HC165, so I can see how the pure functions interact with the register state.