LLL Specification ================= Version 20120511 LLL is an esoteric programming language based on logic circuits. What is an esoteric programming language? It's a programming language with no useful purpose, but which can be used as a toy, joke or interesting proof of concept. Other examples of an esoteric programming languages are LOLCODE and Befunge. LLL allows defining an electronic logic circuit in a text file, with input and output to the host computer, and run that as a program. Overview -------- The source code is a series of ASCII characters in a text file, laid out in a two dimensional grid. The dimensions of the 2D grid are: width of the widest line x number of lines in the text file. Newlines can be of the Unix or DOS type and may be mixed. The maximum width and height are not bounded by this specification, only by the memory capabilities of your computer. Other ASCII characters than those listed for cells further down and the characters needed for newlines and comments, are ignored (but are taken into account for the width and height calculation). Lines which are shorter than the longest line, are treated as if they are filled with spaces from their ending until the grid width. On the 2D grid, every character is a cell. Each cell is a partial part or a whole part on its own. Parts can be seen as (partial) elementary elements of a logic circuit, or wires to connect parts together. Most logic gates have to be made out of multiple parts. Some part types are always exactly a single cell in size, others can take mane shapes and sizes, and are formed by touching cells of the same, or related, type. For example, a diode is always a single cell, but a wire can be anything from a single cell to a long wire with multiple branches, crossings and backplane connections. This whole wire is a single part. Parts which touch each other through legal connections (compatible types of neighbor cells), are said to be connected to each other. For example, a diode can form a connection with a wire, but a wire cannot form a direct connection with a XOR-wire. When the program is running, every tick, all parts are simulated for one tick. Each part calculates its next state, based on the current state of other parts connected to it (where, if that other part was already calculated for this tick, current means its previous state). Wires are an exceptional part: they are updated immediately on the fly when asked for their state, which means that they never cause a delay, they are instant, while all other parts cause a delay of 1 tick. XOR-wires and counter-wires are also instant (using them introduces a delay anyway since they have to be connected to invertors and diodes, which are parts that cause a delay). There are two modes in which a program can run: program mode, and interactive mode. Interactive mode is intended as a toy or for debugging. It allows toggling inputs with the mouse, and shows a graphical representation of the circuit running. In program mode, it is still a toy (after all, this is an esoteric programming language), but the program can communicate with the host computer running it, allowing console input and output of the host computer, using ASCII codes formed by 8 numbered input and output bit signals represented by specific parts in the program. The freedom to implement such programs is unbounded: you could implement the program directly with logic gates, or create logic circuit of an actual CPU and store the program in a ROM, or use the cells and parts in unforeseen ways. Cells ----- This lists cells, not parts. In many cases a cell is a part, but in many other cases it is not. The description explains how the cell forms parts, not what it does. space, . or end of shorter-than-width text line endings: isolator leaves nothing through, no interaction *: wire Leaves current through on its 4 sides. Forms a wire part together with +, x and b. Interacts with diodes, invertors, inputs and outputs, but not with XOR wire. +: +-shaped wire crossing Allows two wires to cross. Two independent wires can run through this single cell. Interacts with same cells as * does. x: x-shaped wire crossing Allows two wires to cross, connects to wires only in the 4 corners. Unlike other wire cells, the x cell only touches * cells or other x cells in its corners, it does not interact with any other cell at all. ^: diode SN >: diode WE v: diode NS <: diode EW The diode cells for a single part. It interacts with other cells only on its input and output side, the other two sides are isolating. It interacts with every cell except x. m: invertor SN ]: invertor WE w: invertor NS [: invertor EW The invertor cells for a single part. It interacts with other cells only on its input and output side, the other two sides are isolating. It interacts with every cell except x. i: input Multiple input cells touching each other form one large input part. In interactive mode, such a full part can be toggled on and off with the mouse. A single i cell can interact with a number cell (0-9). If an i touches a number, it is not allowed to touch any other i, and it is allowed to touch a single number only, anything more is a parsing error. An group of i's becomes 'high' like a group of I's as soon as they touch one or more I's. An i interacts with everything that wire interacts with, except 'x'. I: input, actived Same explanation as for i. j: button input Same as input, but only useful in interactive mode, and acts as a button to the mouse button rather than a toggle switch. That is, it deactivates as soon as you stop pressing the mouse. o: output Same explanation as for i. O: output Same explanation as for i. Only used for special signal outputs. 0: mark input or output 1: mark input or output 2: mark input or output 3: mark input or output 4: mark input or output 5: mark input or output 6: mark input or output 7: mark input or output These are used to mark a single input or output cell as a numbered input or output part. Extended Cells -------------- Cells for extended parts, or to extend regular parts. b: backplane connection Allows many separate wires to be all connected together, forming one giant wire. Interacts with same cells as * does. Since there's only one single shared backplane for the whole program, this is best used for an important global signal, e.g. a master clock signal. r: XOR-wire Multiple r cells touching each other form a large XOR-wire part. For the rest, r cells only interact with diode and invertor cells. Any other cell touching it is considered as if there's an isolator in between. c: counter-wire This works like a T-flipflop or counter. Just like the XOR-wire, this type of cell only interacts with input and output sides of diode and invertor cells, and isolates with everything else. d: delay-wire Just like r and c, this only interacts with inputs and outputs of diodes and invertors. It causes a longer delay. See under Parts for more info. Parts ----- This section lists the parts which are made out of the above cells, and explains what they do. *) Isolator This is not a real part. It does nothing. Isolator cells, separate parts from each other. *) Wire Wires leave current through. Wires connect multiple parts together. Wires are not required to connect them together, parts can also touch each other without wires in between. But wires allows routing connections over any distance. A single wire can connect more than two parts together. Wire parts are formed by *, +, x and b cells. It can have any shape, and anything touching it in a legitimate way to form a connection, is part of the group. Wires can be gigantic, because the backplane is considered to be one single wire, and every group of *'s, +'s that touches a b cell, is part of this giant wire. There is only a single such backplane, and it is convenient to use, for example, as clock signal that has to be brought to every section of your system. Unlike other parts, wires cause no delay of one tick. Whether two non-wire parts are connected to each other directly, or with a wire in between, makes no speed difference. The backplane, too, causes no delay. *) Diode Leaves current through in one direction only. The 4 diode cell types are one type for each direction, indicated by the shape of the ASCII symbol. A diode is always one cell in side, so multiple diodes touching each other work independently and cause a longer delay. A single diode, like every part other than wire, causes a delay of one tick. If the input side of the diode is powered, its output will be powered the next tick. If the input side of the diode is not powered, its output will not be powered the next tick. If the output side of the diode is powered, e.g. by something else, nothing particular happens, the diode does not use that side as input. *) Invertor Is direction just like the diode, except its output is (after 1 tick) the inverse of the input signal. It is a NOT gate. Unlike the diode, the invertor has some less obvious ASCII symbols, because no other set of 4 ASCII symbols that look like 90 degree rotated versions of each other exist. For the horizontal directions, square brackets were used, these correspond to the chevron brackets (lesser than and greater than symbols) of the diode symbols. For the vertical directions, a 'w' is used instead of the 'v' for the diode, and an 'm', which should be seen as an upside down 'w' for the other direction. *) Input This is a versatile part. There exist unnumbered and numbered inputs. Numbered inputs are formed when the input cell touches a 0-9 character, see Cells chapter for more info. Unnumbered inputs have a state, on or off. By using a capital 'I' symbol, it is in on state initially, otherwise it's in off state. Unnumbered inputs can have any size (of grouped touching cells of the same type). In program mode, inputs never toggle state after initialization. In interactive mode, they can be toggled by pressing the part with the mouse button on its graphical representation on the screen. Numbered inputs are used for communication with the host computer in program mode. In interactive mode, there are some GUI controls to set the numbered values instead. Depending on whether 'i' or 'I' was used for the input, it is a low or high numbered input. Low numbered inputs represent input bits, high numbered inputs are for control signals. See the chapter "Host Computer Input/Output" for how this works. *) Output This is a versatile part. There exist unnumbered and numbered inputs. Numbered outputs are formed when the input cell touches a 0-9 character, see Cells chapter for more info. Unnumbered outputs have no effect in program mode. In interactive mode, they will have a different color in off and on mode, but still have no further effect. Numbered outputs are used for communication with the host computer in program mode. In interactive mode, there are some GUI controls to read the numbered values instead. If multiple outputs connect to the same number, the final output value for that number is the 'OR' of all these outputs. If there is no output at all for that number, it is considered to be 'off'. Depending on whether 'o' or 'O' was used for the output, it is a low or high numbered output. Low numbered outputs represent output bits, high numbered outputs are for control signals. See the chapter "Host Computer Input/Output" for how this works. Outputs does not act as a wire. If multiple wires are connected to an output, and one wire turns the output on, the other wires do not get current from the activated output. Extended Parts -------------- These parts are not strictly necessary for building any possible circuit, but they make it a lot easier, allowing circuits that take up less space and have less delay. The extended parts are chosen to be useful but still very basic, so do not expect predefined parts like JK flipflops or full adders here. This are still rather basic parts, out of which e.g. JK flipflops and full adders can be built more easily. *) XOR wire This is a wire acting like the core of a XOR gate. It is called XOR-wire, not XOR-gate, because it requires other parts (diodes or invertors) interacting with this to become a true XOR gate. The XOR wire interacts only with diodes and invertors. Each diode/invertor output connected to a XOR wire, is a XOR input. Each diode/invertor input connected to a XOR wire, is a XOR output. All XOR outputs receive the XOR operation of the input bits as value. Connecting a XOR wire directly to a regular wire, does nothing, they do not interact. Note that XOR wire uses 'r' cells, not 'x' cells, 'x' cells are crossings for regular wire. *) Counter-wire This is a wire acting like a counter. It is called counter-wire, not just counter, because it requires other parts (diodes or invertors) interacting with this to become a true working counter. This is a single-input, single output part. It can be seen as a T-flipflop with T always set to true, and the input being the clock. Whenever the input goes from off to on (positive edge), the output state will flip. Initially the output state is false. The input is the OR-combination of all inputs connected to this. *) Delay-wire A delay wire delays as follows: if the input was one, then the output will only become zero after the input is zero for N ticks. N is calculated as (two to the power of d) - 2, where d is the amount of d-cells touching to form this delay-wire. The reason it's not just 2^d but 2^d - 2 is that there is already a delay of two ticks due to the input and output diode or invertor, so the subtraction of 2 is done. This means a delay wire consisting out of a single d has a delay of zero in itself (but two in practice to the required input and output diode or invertor). The d's can have any shape as long as they touch. The maximum amount of d-cells is 30. Any higher amount gives unspecified behaviour: the N for the ticks would overflow a 32-bit integer. For example: including the input and output diode, 1 d gives a delay of 4 ticks, 2 d's gives a delay of 8 ticks, 3 d's gives a delay of 16 ticks, etc... As all extended parts, this is a part purely for convenience and especially winning space, for example the following two are roughly equivalent in functionality (stabilizing the input for a while): i**>*>*>*>*>*>*>*>***o v v v v v v v v * ****************** i*>ddd>*o Update speed ------------ When the program runs, per tick each part is updated once. Each part calculates its next state, based on the previous (current) state of all its neighbor parts. It does NOT use any state of neighbor parts that was already calculated for this tick (if this would be allowed, then signals might transfer instantly in one direction but not in the other depending on the order in which parts are ran, but the order in which they are ran is not defined!). So both the current and new state of each part needs to be remembered. Wires do not cause a delay. They are, unlike other parts, updated with the latest state immediately. Wires can never have other wires as neighbor part, because all touching wire cells form one large wire. All groups of wires connected to the backplane, form one single giant wire. The result is that the following signal transfers are achieved from i to o in the next examples, where the tick of updating i is not taken into account: io: 1 tick (the tick needed to calculate the new state of o) i**o: 1 tick (the wire causes no extra delay) i>o: 2 ticks (one for the diode, one for the o) i****>******o: also 2 ticks, wires cause no extra delay i>>>>>o: 6 ticks Initialization -------------- Before the program starts, all parts are initialized. During initialization, all parts are updated and states of connected parts calculated on the fly as needed, so that everything is stabilized before the first tick. During initialization, every part is calculated exactly once, and when there are no loops the order in which this happens is exactly defined (start points are always calculated before end points). However, if a a circuit has loops, like in the following example, the initial state can be undefined! **]***]** * * ********* Depending on the interpreter, either the first invertor will be on and the second off, or vice versa. This is called an undefined state. But an undefined state is still either on or off, it's not a special kind of signal, it's just a signal of which you can't predict beforehand which it'll be, it depends on the interpreter implementation. However, one thing is defined, and that is that in the following circuit, the output of the invertor is initially (= in the first post-initialization program tick) OFF, and after one tick on, the next tick off again, etc... (fastest possible clock): *]* *** However, the state of the invertor during initialization (before the first actual program tick) is undefined! So parts connected to the above circuit can possibly have undefined state during the first program tick. This means that, for example, RS latches or other memory elements typically have undefined state at startup and must be initialized by the program. During initialization, all inputs are off, even those marked as 'I'. Only after initialization those become active. So, a reliable way to get a single pulse shortly after program start and then never anymore, is the following: I>>r>* **>r During initialization, counter wires never toggle on. They can only toggle if their input goes from off to on at some point after initialization. So the following counter will output false, not true, after initialization: ]c>*o Host Computer Input/Output -------------------------- Host Computer Input/Output in program mode works using the numbered input and output parts. *) Input Numbered inputs are used for communication with the host computer in program mode. Depending on whether 'i' or 'I' was used for the input, it is a low or high numbered inputs. The low numbered inputs from 0 to 7, form 8 bits of a byte. This byte represents an ASCII code gotten from the terminal of the host computer. Input 0 corresponds to the least significant bit, input 7 to the most. In some operating systems, binary byte data can also be redirected to this instead. The high numbered inputs are: 0: input EOF 1: input update 2: This input is unused. It is reserved for analogy with high numbered output 2. High numbered input 0 becomes true once the host computer received "End of file" (EOF). This means the host computer will not send any further input. High numbered input 1 is toggled from off to on (rising edge) whenever the host computer has updated the 8 input bits. This way you can distinguish when a new character is sent to us. High numbered input 2 could mean "host computer is ready to receive output", but to make it easier to implement programs, it is specified that the host computer is *always* ready to receive output. Reading input from the host computer works as follows: -indicate you're ready to receive the next 8 input bits by outputting "input ready" (output O2, see Output part description). -toggle input ready off again as soon as possible, it must be off 1 tick after the next step happened (to indicate you're not ready to receive the next batch of 8 bits yet) -wait for input update signal to be toggled on -read the 8 input bits (inputs 0-7) -etc... The reference implementation of the interpreter for this language will, whenever "input ready" is enabled, wait for the user to enter text in their terminal. It will then send all the characters the user entered (one by one, waiting for the next "input ready" signals, supporting the above "Reading input" steps). While the user enters text in the terminal, everything is paused, so for the program it is as if this happens in one tick. Since the user enters a line of text with the enter key, the reference interpreter does not support sending newlines to the program. However, other interpreters are allowed to handle user input in other ways, such as realtime, supporting the enter key as sending character 10 and/or 13, or use any other method to send bytes to the program according to the protocol specified above. If you can process input fast enough to read it once every two ticks, you can leave "input ready" on all the time without ever toggling it off. Then, always wait for "input update" to be toggled from off to on, read the 8 bits the next tick, wait a tick again, etc... *) Output Numbered outputs are used for communication with the host computer in program mode. In interactive mode, there are some GUI controls to read the numbered values instead. If multiple outputs connect to the same number, the final output value for that number is the 'OR' of all these outputs. If there is no output at all for that number, it is considered to be 'off'. Depending on whether 'o' or 'O' was used for the output, it is a low or high numbered output. The low numbered inputs from 0 to 7, form 8 bits of a byte. This byte represents an ASCII code sent to the terminal of the host computer. Output 0 corresponds to the least significant bit, output 7 to the most. In some operating systems, this can be redirected as binary data instead. The high numbered outputs are: 0: output EOF (end program) 1: output update 2: input ready (see Input section above) Use high numbered output 0 to end the program. You signal EOF to the host computer, which will then stop your program. Toggle high numbered output 1 on (rising edge) to indicate to the host computer that it should read the next 8 bits. Every time you toggle this on, a character is read. High numbered output 2 means "input ready". Only when you turn this on, the host computer will send new input bits. This allows you to do all processing of input before receiving the next one. Sending output to the host computer works as follows: -Put the correct 8 bits in the output -Ensure "output update" is off -Toggle "output update" on Comments -------- Comments can be added in source code diagrams, by putting it between two quotes. Comments continue into newlines. Comments do take up space and can also determine the size of the final program. However, every ascii character that is part of a comment counts as an isolator. Any ascii character is allowed in comments. Example of a gate with a comment above it: "And gate" i*]* *]*o i*]* Example of a wire which is broken because one cell of it is a comment and thus an isolator (input will not activate the output): I * "*" * o The Reference Interpreter ------------------------- Here's some help about the reference interpreter: To compile it (in Linux), type this (requires SDL): g++ src/*.cpp -lSDL -O3 -o lll To compile it in Windows, find and install a C++ compiler, get it to link SDL with this, and compile it. Note that the program mode uses the console, start the program from a terminal window to see its output. If you don't have SDL, you can still compile it, but then interactive mode will not be supported. To compile without SDL, comment out "#define SDLGRAPHICS" in the file main.h, and don't compile quickcg.cpp. Then -lSDL linking is no longer required. To run a program in program mode, run it like so (with -c meaning console): ./lll -c examples/hello.txt To run a program in interactive mode, run it like so: ./lll examples/div.txt In Windows, you can probably also right click on div.txt, then choose "Open With...", and then choose lll.exe, to run it in interactive mode. For program mode, you'll need the console though. In program mode, whenever the program is ready to receive input, everything pauses while you type characters in the terminal. Hit enter to send the characters (excluding the newline) to the program. Hit CTRL+C to stop the program. In Linux, hit CTRL+D to send an "EOF" (end of file) to the program. In other operating sytems, maybe CTRL+Z sends an EOF? In interactive mode, the whole circuit it shown as colored pixels. The grey/ white ones are inputs, the green ones are outputs. Click on inputs with the mouse to toggle them (Note: it may sometimes seem as if the inputs don't really react to your clicks. The mousepointer must be on the input pixel at the moment a tick happens, only then will the input register your click. So if you run in the mode with only 1 tick per 2 seconds, you may need to keep the mousepointer there for 2 seconds. If the program is paused the inputs register no clicks at all because they, too, are paused). You can change the speed at which the circuit runs by clicking the numbers in the bottom right of the window. There are 6 speed settings: 0: pauzed 1: 2 seconds per tick (very slow) 2: 0.5 seconds per tick 3: 0.1 seconds per tick (default) 4: 0.05 seconds per tick 5: 1 tick per graphics frame (speed depends on your computer's rendering speed) 6: many ticks per frame (superfast, speed only limited by your computers CPU) Note that superfast is way faster than the 1 tick per graphics frame mode, there can occur thousands of ticks per graphics frame, and it'll draw a graphics frame 25 times per second. In program mode, it always runs the fastest possible, like the "superfast" mode of interactive mode. In interactive mode, you can also type characters in the keyboard to convert their ASCII codes to input values for numbered inputs and give a single input update pulse to the program. Output values of the program are also displayed in the bottom left corner of the window. Note, however, that the keyboard input is somewhat jerky, not very reliable. Program mode is adviced for this. The mouse currently requires the mouse pointer to remain above the clicked input until a tick is done. This may require holding the mouse still on slow speeds. Interactive mode currently has a fixed window size of 1024*768. Larger circuits will not be fully rendered. Smaller circuits are rendered as large as possible. Possibly a future version will support interactive zooming and panning. What's new ---------- 22 april 2012: initial release 11 may 2012: -Added 'j' button input part. -Added 'd' delay wire extended part. -Created a compiled Windows exe version of the interpretor so that in Windows people don't need to compile it (in Linux it's easy to compile). -Put 'b' in the "extended cells" category since it's not an essential cell type. -Added game of life example. -Made it render each cell type with a different color, though not all are distinguishable by the eye, rather it is to know the source state given a screenshot. -Fixed compiler warnings. Copyright (C) 2012 by Lode Vandevenne. All rights reserved.