3 ms·

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

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.
  - jiggawatts 5y ago
    That function example is not allowed in Haskell. It's pure functional throughout, not just at "function boundaries". I agree that conceptually a language can be made where only function boundaries are required to be side-effect free, and internally "anything goes" as long as it doesn't pollute the outside world. This might be a good model for circuit design, especially if using something like an IO monad to store persistent state across clocks, such as flip-flops or registers. However, this is not what Haskell does, at all. There are no mutation functions like "fill(x)". You have to create the buffer filled with x right from the beginning. More importantly, in Haskell that buffer is defined with a recursion, so it looks something like: (x,(x,(x))) Effectively it is an immutable linked list. Any modification involves either rebuilding the whole thing from scratch (recursively!) or making some highly restricted changes such as dropping the prefix and attaching a new one, such as (y,(x,(x))). Haskell is not LISP, F#, or Clojure. It's pure and lazy, which is very rare in functional programming. It's an entirely different beast, and I don't see how any variant of it is a good fit for circuit design, which is inherently highly stateful and in-place-mutable.
    - rowanG077 5y ago
      Such a function is perfectly allowed and even encouraged, see here where I allocate a mutable array with undefined values and write and read from it in a pure function. Basically replicating the pseudo imperative code I have written before: https://replit.com/@RowanGoemans/QuarrelsomeUtilizedMicrokernel#Main.hs:11:10 https://replit.com/@RowanGoemans/QuarrelsomeUtilizedMicroker... Using mutable vectors like this is a must if you need to write high performance Haskell code. I have also written concrete code for magicalhippo in another branch of this thread.
      - jiggawatts 5y ago
        That's a clever hack that was added decades after I learned Haskell. I mean... it works, but it's not in the spirit of Haskell, which is my point. It's not impossible to write pure functional software in C. It just goes against its grain.
        5y ago

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.
- jiggawatts 5y ago
  That function example is not allowed in Haskell. It's pure functional throughout, not just at "function boundaries". I agree that conceptually a language can be made where only function boundaries are required to be side-effect free, and internally "anything goes" as long as it doesn't pollute the outside world. This might be a good model for circuit design, especially if using something like an IO monad to store persistent state across clocks, such as flip-flops or registers. However, this is not what Haskell does, at all. There are no mutation functions like "fill(x)". You have to create the buffer filled with x right from the beginning. More importantly, in Haskell that buffer is defined with a recursion, so it looks something like: (x,(x,(x))) Effectively it is an immutable linked list. Any modification involves either rebuilding the whole thing from scratch (recursively!) or making some highly restricted changes such as dropping the prefix and attaching a new one, such as (y,(x,(x))). Haskell is not LISP, F#, or Clojure. It's pure and lazy, which is very rare in functional programming. It's an entirely different beast, and I don't see how any variant of it is a good fit for circuit design, which is inherently highly stateful and in-place-mutable.
  - rowanG077 5y ago
    Such a function is perfectly allowed and even encouraged, see here where I allocate a mutable array with undefined values and write and read from it in a pure function. Basically replicating the pseudo imperative code I have written before: https://replit.com/@RowanGoemans/QuarrelsomeUtilizedMicrokernel#Main.hs:11:10 https://replit.com/@RowanGoemans/QuarrelsomeUtilizedMicroker... Using mutable vectors like this is a must if you need to write high performance Haskell code. I have also written concrete code for magicalhippo in another branch of this thread.
    - jiggawatts 5y ago
      That's a clever hack that was added decades after I learned Haskell. I mean... it works, but it's not in the spirit of Haskell, which is my point. It's not impossible to write pure functional software in C. It just goes against its grain.
      - 5y ago