Recently, I created a language called Sim to make designing digital circuits simple and fun. Sim looks and feels like a small subset of Elm but has some features unique to circuits. For example, the only types that Sim supports are bit buses, records, and functions. A more advanced feature is the variable bus size:
not a[n] -> [n] =
nand a a
Unlike Elm, Sim allows self and mutual recursions:
Self recursion:
cascading_not_gates input[1] -> [1] =
let
output = or output (not (not input))
in
output
Mutual recursion:
s_r_latch s[n] r[n] -> [n] =
let
q =
nand s not_q
not_q =
nand r q
in
q
Sim’s parser and type checker are written in Elm and JavaScript is emitted for circuit simulation.
I would really love your feedback and suggestions for Sim.
I also created a WIP accompanying guide for Sim called Crafting Computer. Any feedback for that is also welcome.
Lastly, since I’m a newbie in Hindley Milner type inference, I had trouble inferring the variable bus types mentioned above. All works fine until I call the same function twice in another function. I have yet to figure out a way to uniquely represent the variable bus sizes. For now, I use a combination of:
the location of the function they are declared in
the name of the variable size
to identify. However, as you might expect it breaks down when I call the same function twice. Here’s the code for the type checker. An example when type checking breaks down:
test i[i] j[j] k[k] -> [j] =
let
a = nand i i
b = nand j j
c = nand k k
in
b
Also I am making a world editor for survivalcraft and it could be interesting to implement an extension for it that compiles sim to a circuit in survivalcraft
BTW, I don’t know if you ever heard of it, but there is a digital design language called CHISEL - which stands for constructing hardware in a scala embedded language. You might find that interesting to take a look. It certainly can be a powerful idea to combine functional programming with hardware design.
I used it on a non-trivial project, and found it had a lot of advantages over the traditional VHDL/Verilog languages, although it was still very much at an experimental stage back then. The best part was writing unit tests for hardware designs in scala-check (which is similar to elm-test). I never really took to Scala though, the language is way too big, too non-pure. An Elm re-implementation of Chisel could be really sweet.
Thanks for the recommendation. I know a similar functional HDL called Clash that compiles Haskell to other HDLs like vhdl and verilog. Both Chisel and Clash are for real-world circuit design which is much more complicated than Sim. Because of my limited experience in computer architecture, I went with the naive approach of building everything out of only nand gates and Sim was born.
Never heard of Clash until now - I wonder if someone had the idea of remaking Chisel but on a nicer functional language. It certainly looks like a newer thing than Chisel.
The Sim compiler currently runs in the browser. See the Sim Editor. To run the compiler independent of the editor, run the src/Main.elm where you supply the source program as string:
The most difficult job is to emit the survivalcraft circuit because the current JS target have native support for such things as closures and bitwise operations. Some things, however, become easier I believe because all mutual recursions naturally become loops in circuit connections so we don’t need to to resort to closures.
Yes. I will be happy to continue working with you on the adopting Sim to Survivalcraft. Can you explain how your world editor works, how to load the world to Survivalcraft, and the text format for survivalcraft circuits?
I am eventually going to create an extension interface for creating extensions for EditSC, and a Sim to Survivalcraft circuit compiler should be implemented as an extension. This extension interface has not been implemented yet, so it’s not yet possible to make a Sim extension for EditSC.
For now the only thing that can be done is forking the Sim compiler and somehow implementing all of Survivalcraft’s electricity items (not gates, memory banks, LEDs, etc.) as primitive values in Sim just like the nand gate. It’s also important to know that all electric wires in Survivalcraft are analog (they carry 4 bits) but are often treated as 1-bit digital wires by representing on as 0xF and off as 0x0. A name for this fork of Sim should also be made.
I see. Talking about implementing electricity items from survivalcraft, Sim has a very small core (2 functions: nand and fill) and it’s easy to add and remove core functions. Just need a type declaration and specify emitted code. One issue though is Sim is functional and requires all core functions to have inputs and outputs so side-effect items like LEDs are a little hard. Items like switches and LEDs may need to be generated by Sim. As for the name, maybe sim-survivalcraft? I would also appreciate if you can create the fork in the Crafting Computer Github Organization and become a member. Once the extension interface is ready, we can start thinking more about the details.
There also needs to be a way to specify the physical locations of LEDs, switches, etc. The hardest part will be compiling the circuit to correctly arranged blocks in the world and making the resulting circuit compact by efficiently utilizing things like wire through blocks and colored wires (wires only connect to wires of the same color unless uncolored).
For specifying the location of things like switches, I think it should be done by representing these as a value in the Sim code and prompting the user to specify a location for these things before it converts the circuit to blocks.
And I think this fork of Sim should be called something else; maybe “Geranium” because it is used to craft many of the electric items in Survivalcraft
Germanium is more creative than sim-survivalcraft so let’s go with that. For the location though, I feel it can make the logic very cluttered. One of the advantages of using a language rather than placing the blocks by hand is the compiler can arrange components automatically and easily reuse them. It’s gonna be challenging but my thought is that it’s an important abstraction of Sim.
@AlienKevin, exciting work! I have only used VHDL, and I remember being not that great at it. We had a group project to make a CPU that ran MIPS, and I remember writing a little compiler to produce the MIPS code for the final project a bit more easily
Anyway, I have some resources on type inference! I recommend reading The Essence of ML Type Inference which comes with a prototype implementation. I know for Elm, using the Union Find algorithm is really important for performance of global inference on files of 500+ lines. I don’t think I implemented this for about two years, until programs started getting longer in practice, but I bring this up because Union Find requires mutation for the fastest implementation. I don’t know enough about your language to know exactly if you need that, but you may need to use a language like OCaml or Haskell to do that specific optimization. Languages like Scala cannot use Union Find too much because it does not work so well with OO-style sub-typing, so they have to do other things to try to improve performance. Point is, you can get by without, but I’m not personally an expert on what is needed outside of HM(=). I hope that is helpful information!
I also ran into a really impressive language called Lucid Synchrone many years ago, and I recommend reading through that paper! I recall being really impressed that they had used a highly constrained “reactive system” to get really solid and practical proofs about cycle counts and maximum hardware necessary for a given program, but it’s been 6 or 7 years since I’ve read it myself!
Thinking more about it, I’m not 100% clear on how the bus size fits into traditional HM(=) type inference. I think that’s where I’d be doing the most reading. More so than thinking about performance.
Can that be expressed as type constraints like in Haskell? Type level naturals? etc. I do not know enough to know, but I know that having (n + m) in types might get tricky.
Once I have narrowed down what PL people might call something, I would start looking for papers that say “we proved can do X by extending HM(=) in a nice way” which is not always the case! For example, if you start looking into records, they call it Row Polymorphism and if you want union of record types ({a,b} + {c,d} = {a,b,c,d}) I have not seen a proof that this always work with global type inference, even though there are languages like Ur/Web that implement it anyway. I.e. how does it work with type variables? (r + s = ???)
Thank you so much for the detailed replies. I will look through the valuable resources. Lucid Synchrone looks super cool as well. I watched several of your amazing talks and read many easy-to-understand Elm documentation written by you but it’s even more exciting for me to chat with you. Elm is really a life-saver and the most addictive programming language I ever encountered .
All my experiences using the elm compiler, packages.elm-lang.org, elm make, elm reactor, and other elm tools are way beyond the ones offered by any other languages like JavaScript, Python, and Rust. I feel like being in a clean and warm home rather than a messy and noisy market. The amount of thought you put into Elm packages really made them great addons to the language. I used elm/parser in several of my language projects and it just makes writing a good parser feel so natural and smooth. Again, thank you so much for making Elm such a delightful language, and please carry on with your great work.
.
