A functional Scala library implementation of a computer working with a sheet of paper, a pen, and a set of items e.g. matches (Streichholzcomputer / Papiercomputer), used for computer education in the 1980s.
For background see
- WDR paper computer
- Know-how-Computer (German)
A paper-computer is a state-machine. Each state consists of a set of registers, holding the register value information, and the information which line in the program would be executed next.
The execution of a single program line will either fail (e.g. trying to increment a non-existing register, or jumping to a non-existing next program line) or return a new state with potentially changed register values, and a changed command line to execute next.
The execution of a whole program will start execution at the first command and move the state machine forward until
a Stp command is encountered.
The simulated architecture of the paper-computer builds on top of three architectural value ranges.
- The range of values a single register can hold for
RegisterValue. - The range of register addresses for
RegisterNumber. - The range of program line numbers for
LineNumber.
Each of the ranges could be defined separately, e.g. as Scala's type Long, or e.g. Int to reduce resource usage.
By default, the base type for all three ranges is Long.
type RegisterValue = Long
val minRegisterValue: RegisterValue = Long.MinValue
val maxRegisterValue: RegisterValue = Long.MaxValuetype RegisterNumber = Long Refined NonNegative
val minRegisterNumber: RegisterNumber = refineMV[NonNegative](0L)
val maxRegisterNumber: RegisterNumber = refineMV[NonNegative](Long.MaxValue)type RegisterValues = immutable.Map[RegisterNumber, RegisterValue]
case class RegistersConfig(minRegisterValue: RegisterValue, maxRegisterValue: RegisterValue, registerValues: RegisterValues)
case class Registers(minRegisterValue: RegisterValue, maxRegisterValue: RegisterValue, registerValues: RegisterValues)That is: Registers holds a map from RegisterNumber to RegisterValue.
The minRegisterValue and maxRegisterValue allow simulating in the paper-computer various real-world architectures,
e.g. signed 8-bit registers with a value range from -128 to 127,
or unsigned 16-bit registers with a value range from 0 to 65,535, including wrap-around.
For example, incrementing a signed 8-bit register with value 127 results in a new value of -128, like in real world.
A Registers is actually created from a RegistersConfig, which has the same structure. However, Registers creation
guarantees that no illegal state can be represented, while RegistersConfig is unchecked.
type LineNumber = Long Refined Positive
val minLineNumber: LineNumber = refineMV[Positive](1L)
val maxLineNumber: LineNumber = refineMV[Positive](Long.MaxValue)The original paper-computer knows 5 commands:
| Command | Meaning |
|---|---|
Inc(rn) |
Increment the register with register number rn, then continue with the next line in the program. |
Dec(rn) |
Decrement the register with register number rn, then continue with the next line in the program. |
Isz(rn) |
If the register with register number rn has value zero, continue with the second next line in the program, else continue with the next line in the program. |
Jmp(ln) |
Jump, i.e. continue with line ln in the program. |
Stp |
Stop executing this program. |
A program is simply a map from line number to command:
type Program = immutable.Map[LineNumber, Command]Throughout this library errors are represented by type Message. Potentially failing functions return an
Either[Message, T] with T the successful return type. Examples for failure are trying to access a non existing
register or jumping to a non existing program line. The whole library basically work in the effect of Mor[_]:
sealed trait Message
case object MinRegisterValueMustBeLessOrEqualZero extends Message
...and
type Mor[T] = Either[Message, T]A default program execution takes a program and an initial registers state,
and returns either the resulting registers state at the end of the program,
or an error Message, e.g. IllegalAccessToNonExistingRegisterNumber.
class RegistersConfig(minRegisterValue: RegisterValue, maxRegisterValue: RegisterValue, registerValues: RegisterValues)
type ProgramExecutionF = (Program, RegistersConfig) => Mor[Registers]In detail:
- Registers are build from a registers configuration.
- Building the registers will fail with a message for an illegal registers configuration.
- By convention the execution of a program starts at its lowest line number.
- Empty programs can be created, but cannot be executed.
- Executing the program may fail with a message.
- Program execution may be infinite if the program contains a loop.
- If no failure occurs and the program finishes, the final registers are returned.
Execution is safe from stack overflows but may not end if you have an unconditional loop in your paper-computer program.
Under the hood, execution builds a Stream of ProgramStates.
Execution can also be effectful and yielding any other result which can be derived from ProgramState.
See the example usage below for an example of interleaving an IO effect for printing out each intermediate step.
For more details on hooking into the Stream see the source code of ProgramState and ProgramExecution.
This implementation of the paper-computer adds 2 commands for convenience:
| Command | Meaning |
|---|---|
Prg(program) |
Execute program program, starting with that program's lowest line number, and an initial registers state of this program's current registers state. If that program reaches its end via Stp, continue with the next line in this program using that program's resulting registers state. While technically not needed to write programs, this addition allows for easier implementation of a library of pre-defined programs that can be plugged together, e.g. see the fibonacci calculation in the Program Library. |
Sub(ln) |
Jump to line ln, but when the execution ends via Stp, continue with next line after this Sub in the program. While technically not needed to write programs, this simplifies calling a section of this program from different places and continuing from the different respective next lines. |
The following program adds up the values in register 2 and register 3 and returns the result in register 1, thereby destroying the original values in registers 1, 2 and 3.
object demo {
val programAdditionR2PlusR3ToR1: Program = Map(
(10L, Isz(1L)),
(20L, Jmp(40L)),
(30L, Jmp(60L)),
(40L, Dec(1L)),
(50L, Jmp(10L)),
(60L, Isz(2L)),
(70L, Jmp(90L)),
(80L, Jmp(120L)),
(90L, Dec(2L)),
(100L, Inc(1L)),
(110L, Jmp(60L)),
(120L, Isz(3L)),
(130L, Jmp(150L)),
(140L, Stp),
(150L, Dec(3L)),
(160L, Inc(1L)),
(170L, Jmp(120L))
)
// use arbitrary min/max values just to show we can!
val registersConfig: RegistersConfig = RegistersConfig(
minRegisterValue = -21L,
maxRegisterValue = 42L,
registerValues = Map((1L, 42L), (2L, 4L), (3L, 5L))
)
val result: Mor[RegisterValue] = for {
resultingRegisters <- ProgramExecution.execute(programAdditionR2PlusR3ToR1, registersConfig)
resultingR1 = resultingRegisters.registerValues(1L)
} yield resultingR1
// yields: Right(9)
val liftAndMap: Mor[ProgramState] => IO[Mor[Registers]] = morPs => IO {
println(morPs)
morPs.map(_.registers)
}
val resultWithObservation: IO[Mor[Registers]] =
ProgramExecution.execute(programAdditionR2PlusR3ToR1, registersConfig, liftAndMap)
resultWithObservation.unsafeRunSync()
// yields: Right(Registers(-21,42,Map(1 -> 9, 2 -> 0, 3 -> 0)))
// prints out all intermediate program states as IO side-effect:
// Right(ProgramState(RegistersOpsConfig(papercomputer.RegistersOps$<function>apercomputer.RegistersOps$$$Lambda$7644/154046850@23f67fd9,papercomputer.RegistersOps$$$Lambda$7645/525407211@21d9452c),Map(170 -> Jmp(120), 120 -> Isz(3), 10 -> Isz(1), 110 -> Jmp(60), 20 -> Jmp(40), 60 -> Isz(2), 160 -> Inc(1), 70 -> Jmp(90), 140 -> Stp, 130 -> Jmp(150), 80 -> Jmp(120), 150 -> Dec(3), 50 -> Jmp(10), 40 -> Dec(1), 30 -> Jmp(60), 90 -> Dec(2), 100 -> Inc(1)),List(),Some(10),Registers(-21,42,Map(1 -> 42, 2 -> 4, 3 -> 5))))
// ...
//Right(ProgramState(RegistersOpsConfig(papercomputer.RegistersOps$<function>apercomputer.RegistersOps$$$Lambda$7644/154046850@23f67fd9,papercomputer.RegistersOps$$$Lambda$7645/525407211@21d9452c),Map(170 -> Jmp(120), 120 -> Isz(3), 10 -> Isz(1), 110 -> Jmp(60), 20 -> Jmp(40), 60 -> Isz(2), 160 -> Inc(1), 70 -> Jmp(90), 140 -> Stp, 130 -> Jmp(150), 80 -> Jmp(120), 150 -> Dec(3), 50 -> Jmp(10), 40 -> Dec(1), 30 -> Jmp(60), 90 -> Dec(2), 100 -> Inc(1)),List(),None,Registers(-21,42,Map(1 -> 9, 2 -> 0, 3 -> 0))))
}See ProgramLibrary and ProgramLibraryTestSpec.
If you allow negative values in the registers, it will work. However, the original set of 5 commands does not allow
finding out if a given register value is positive or negative, the only test is Isz, which tests if a value is zero
or not.
The programs presented here and contained in the library are optimized for positive numbers. For example, adding two registers could be implemented such that as long as the second register is not zero, the first register is incremented, and the second register is decremented. This while-repeat-loop will finally have in the first register the sum of both original register values.
However, if the second register value is negative, this while-repeat-loop will decrement a negative value to an even more negative value further away from zero. It may thus take an awful lot of time to decrement the second value through the whole value space to reach its lowest value, so that it can then wrap-around to the highest value and after further decrementing finally reach the zero value. At the same time the first register value will move through the whole value space in positive direction, wrap around from the highest value to the lowest value and continue to increment until the program stops.
The end result will be correct, but the number of loop iterations may be up to the size of your value range minus 1, i.e. for simulating an 8-bit register up to 255 steps, for simulating a 16-bit register already up to 65,536 steps.