proj-plbook-plChMiscIntermedLangs2

Table of Contents for Programming Languages: a survey


continued from [1]

Cranelift

A low-level retargetable code generator with an IR (the same sort of thing as LLVM). Designed for the Webassembly project. Written in Rust. Formerly called Cretonne.

https://github.com/CraneStation/cranelift https://cranelift.readthedocs.io/en/latest/ir.html https://cranelift.readthedocs.io/en/latest/compare-llvm.html https://blog.benj.me/2021/02/17/cranelift-codegen-primer/

has intermediate representations CLIF and VCode (VCode is target-dependent)

RiSC-16

https://ece.umd.edu/~blj/RiSC/RiSC-isa.pdf

" ...the 16-bit Ridiculously Simple Computer (RiSC?-16), a teaching ISA that is based on the Little Computer (LC-896) developed by Peter Chen at the Uni- versity of Michigan. The RiSC?-16 is an 8-register, 16-bit computer. All addresses are shortword- addresses (i.e. address 0 corresponds to the first two bytes of main memory, address 1 corresponds to the second two bytes of main memory, etc.). Like the MIPS instruction-set architecture, by hardware convention, register 0 will always contain the value 0. The machine enforces this: reads to register 0 always return 0, irrespective of what has been written there. "

instructions: add addi nand lui sw lw beq jalr

WebKit's Air Assembly language

?? Is this the same as:

See also:

WebKit's Bare Bones Backend / B3 IR

IJVM

https://en.wikipedia.org/wiki/IJVM

" an instruction set architecture created by Andrew Tanenbaum for his MIC-1 architecture. It is used to teach assembly basics in his book Structured Computer Organization.

IJVM is mostly a subset of the JVM assembly language that is used in the Java platform. This instruction set is so simple that it's difficult to write complex programs in it (for example, no shift instructions are provided). " -- [2]

"

There's also a set of special ARRAY instructions. Instruction Stack before* Stack after Description

RCPU

https://speakerdeck.com/ddfreyne/simulating-a-cpu-with-ruby?slide=122

https://github.com/ddfreyne/rcpu

33 instructions (from slide 27):

(the github repo documentation also mentions another instruction, SLEEP)

registers:

HSVM

https://github.com/endeav0r/hsvm

Instructions:

IRE

https://github.com/b3orn/ire/

16 bit register based virtual machine

16 registers

50 instructions:

Cranelift

Embed VM

tiny, embeddable VM

skx simplevm

https://github.com/skx/simple.vm

" The following are examples of all instructions:

:test :label goto 0x44ff # Jump to the given address goto label # Jump to the given label jmpnz label # Jump to label if Zero-Flag is not set jmpz label # Jump to label if Zero-Flag is set

store #1, 33 # store 33 in register 1 store #2, "Steve" # Store the string "Steve" in register 1. store #1, #3 # register1 is set to the contents of register #3.

exit # Stop processing. nop # Do nothing

print_int #3 # Print the (integer) contents of register 3 print_str #3 # Print the (string) contents of register 3

system #3 # Call the (string) command stored in register 3

add #1, #2, #3 # Add register 2 + register 3 contents, store in reg 1 sub #1, #2, #3 # sub register 2 + register 3 contents, store in reg 1 mul #1, #2, #3 # multiply register 2 + register 3 contents, store in reg 1 concat #1, #2,#3 # store concatenated strings from reg2 + reg3 in reg1.

dec #2 # Decrement the integer in register 2 inc #2 # Increment the integer in register 2

string2int #3 # Change register 3 to have a string from an int is_integer #3 # Does the given register have an integer content? int2string #3 # Change register 3 to have an int from a string is_string #3 # Does the given register have a string-content?

cmp #3, #4 # Compare contents of reg 3 & 4, set the Z-flag. cmp #3, 42 # Compare contents of reg 3 with the constant 42. sets z. cmp #3, "Moi" # Compare contents of reg 3 with the constant string "Moi". sets z.

peek #1, #4 # Load register 1 with the contents of the address in #4. poke #1, #4 # Set the address stored in register4 with the contents of reg1. random #2 # Store a random integer in register #2.

push #1 # Store the contents of register #1 in the stack pop #1 # Load register #1 with the contents of the stack. call 0xFFEE # Call the given address. call my_label # Call the defined label ret # Return from a called-routine. "

LightVM

https://bitbucket.org/earlz/lightvm/src/master/doc/

Rusty-jsyc

https://github.com/jwillbold/rusty-jsyc/blob/master/vm/vm.js

"

const OP = { Loaders LOAD_STRING: 1, LOAD_NUM: 2, LOAD_FLOAT: 3, LOAD_LONG_NUM: 4, LOAD_ARRAY: 5,

  // Misc
  PROPACCESS: 10,
  FUNC_CALL: 11,
  EVAL: 12,
  CALL_BCFUNC: 13,
  RETURN_BCFUNC: 14,
  COPY: 15,
  EXIT: 16,
  COND_JUMP: 17,
  JUMP: 18,
  JUMP_COND_NEG: 19,
  BCFUNC_CALLBACK: 20,
  PROPSET: 21,
  // Comparisons
  COMP_EQUAL: 50,
  COMP_NOT_EQUAL: 51,
  COMP_STRICT_EQUAL: 52,
  COMP_STRICT_NOT_EQUAL: 53,
  COMP_LESS_THAN: 54,
  COMP_GREATHER_THAN: 55,
  COMP_LESS_THAN_EQUAL: 56,
  COMP_GREATHER_THAN_EQUAL: 57,
  // Math
  ADD: 100,
  MUL: 101,
  MINUS: 102,
  DIV: 103}; "

LIL

https://www.researchgate.net/publication/220817745_LIL_An_Architecture-Neutral_Language_for_Virtual-Machine_Stubs

" Table 2: LIL General-Purpose Instructions LIL syntax; Description Arithmetic:

Memory:

Calls:

Branches:

Table 3: LIL VM-Specific Instructions LIL syntax Description

M2nFrames:

JNI Handles:

Thread Pointer:

Allocation:

RockSalt RTL

https://web.archive.org/web/20170830050228/http://www.cse.psu.edu/~gxt29//paper/rocksalt.pdf

"RTL is a small RISC-like language for computing with bit-vectors. The language abstracts over an architecture’s definitionof machine state, which in the case of the x86 includes the variouskinds of registers shown in Figure 1 as well as a memory, represented as afinite map from addresses to bytes. Internally, the language supports a countably infinite supply of local variables thatcan be used to hold intermediate bit-vector values. The RTL instruction set is sketched in Figure 3 and includes standard arithmetic, logic, and comparison operations for bit vectors; operations to sign/zero-extend and truncate bit vectors; an operation to load an immediate value into a local variable; operationsto load/store values in local variables from/to registers; operations to load and store bytes into memory; and a special operation fornon-deterministically choosing a bit-vector value of a particular size. We use dependent types to embed the language into Coq and ensure that only bit-vectors of the appropriate size are used in instructions."

Figure 3.The RTL Language

Machine locations: PC

EAX...CF···SS...

Local variables: x, y, z \in identifier

Arithmetic operators:

Comparison operators:

RTL instructions:

UCSD p-code

https://en.wikipedia.org/wiki/P-code_machine#UCSD_p-Machine

Transputer

" The transputer instruction set consisted of 8-bit instructions assembled from opcode and operand nibbles. The upper nibble contained the 16 possible primary instruction codes, making it one of the very few commercialized minimal instruction set computers. The lower nibble contained the one immediate constant operand, commonly used as an offset relative to the Workspace (memory stack) pointer. Two prefix instructions allowed construction of larger constants by prepending their lower nibbles to the operands of following instructions. Further instructions were supported via the instruction code Operate (Opr), which decoded the constant operand as an extended zero-operand opcode, providing for almost endless and easy instruction set expansion as newer implementations of the transputer were introduced.

The 16 'primary' one-operand instructions were: Mnemonic Description J Jump – add immediate operand to instruction pointer LDLP Load Local Pointer – load a Workspace-relative pointer onto the top of the register stack PFIX Prefix – general way to increase lower nibble of following primary instruction LDNL Load non-local – load a value offset from address at top of stack LDC Load constant – load constant operand onto the top of the register stack LDNLP Load Non-local pointer – load address, offset from top of stack NFIX Negative prefix – general way to negate (and possibly increase) lower nibble LDL Load Local – load value offset from Workspace ADC Add Constant – add constant operand to top of register stack CALL Subroutine call – push instruction pointer and jump CJ Conditional jump – depending on value at top of register stack AJW Adjust workspace – add operand to workspace pointer EQC Equals constant – test if top of register stack equals constant operand STL Store local – store at constant offset from workspace STNL Store non-local – store at address offset from top of stack OPR Operate – general way to extend instruction set

All these instructions take a constant, representing an offset or an arithmetic constant. If this constant was less than 16, all these instructions coded to one byte.

The first 16 'secondary' zero-operand instructions (using the OPR primary instruction) were: Mnemonic Description REV Reverse – swap two top items of register stack LB Load byte BSUB Byte subscript ENDP End process DIFF Difference ADD Add GCALL General Call – swap top of stack and instruction pointer IN Input – receive message PROD Product GT Greater Than – the only comparison instruction WSUB Word subscript OUT Output – send message SUB Subtract STARTP Start process OUTBYTE Output byte – send one-byte message OUTWORD Output word – send one-word message

...

Transputers were intended to be programmed using the programming language occam, based on the communicating sequential processes (CSP) process calculus. The transputer was built to run Occam specifically, more than contemporary CISC designs were built to run languages like Pascal or C.

...

The transputer did not include a memory management unit (MMU) or a virtual memory system...The transputer's lack of support for virtual memory inhibited the porting of mainstream variants of the Unix operating system" -- [4]

---

CHIP-8

---

VTIL

https://github.com/vtil-project/VTIL-Core/blob/0e0f34925590ff6946595653c3ab5564ff5e2259/VTIL-Architecture/arch/instruction_set.hpp

---

REIL

https://github.com/Cr4sh/openreil#_3

" Mnemonic Pseudocode Instruction description STR c = a Store to register STM *c = a Store to memory LDM c = *a Load from memory ADD c = a + b Addition SUB c = a − b Subtraction NEG c = −a Negation MUL c = a * b Multiplication DIV c = a / b Division MOD c = a % b Modulus SHL c = a 1 b Shift right AND c = a & b Binary AND OR c = a

XOR c = a ^ b Binary XOR NOT c = ~a Binary NOT EQ c = a == b Equation LT c = a < b Less than SMUL c = a * b Signed multiplication SDIV c = a / b Signed division SMOD c = a % b Signed modulus JCC Jump to c if a is not zero NONE No operation UNK Untranslated instruction
b Binary OR

...

Instruction argument can have following type:

    A_REG − CPU register (example: R_EAX:32, R_ZF:1).
    A_TEMP − temporary register (example: V_01:8, V_02:32).
    A_CONST − constant value (example: 0:1, fffffff4:32).
    A_LOC − jump location that consists from machine instruction address and IR instruction number (example: 8048360.0, 100000.3).
    A_NONE − argument is not used by instruction."

---

Schneider's IL

"a first-order language IL that re- stricts function application to tail position, and does not allow mutually recursive definitions. We give two semantic interpretations to the language: The functional interpretation IL/F given in Section 3.2 yields a standard, first-order func- tional language with a tail call restriction. The imperative interpretation IL/I given in Section 3.3 reveals a low-level imperative register transfer lan- guage.

3.1 Syntax of IL We emphasize the first-order nature of the language by using different al- phabets for the names of variables and functions. x ranges over V , the alphabet for variables, which denote values of base type. f ranges over L, the alphabet for labels, which we use to denote first-order functions. The language is parametrized over a structure of simple expressions which we call operations and denote by Op. By convention, e ranges over Op. We assume a partial function [[·?]] : (V → V ) * V which evaluates an op- eration given the values of the variables. Evaluation of an operation cannot change the value of a variable, hence operations cannot have side effects. As [[·?]] is a partial function, operation evaluation may err: [[e?]] E = ⊥, but evaluation is deterministic.

Figure 3.1: Syntax of IL Exp \oe s, t ::= let x = e in s first-order let

if x then {s} else {t} conditional
x value
fun f x_bar = s in t second-order recursive let
fx_bar application

...

The following syntax is an alternative presentation of the syntax of IL, which generates the same abstract syntax trees, but is more suggestive of IL/I’s imperative interpreta- tion:

Exp \in s, t ::= x := e; s assignment

if x then {s} else {t} conditional
return x value
block f x {s}; {t} block definition
goto f x jump + parallel assignment

" -- https://www.researchgate.net/publication/260321293_Semantics_of_an_Intermediate_Language_for_Program_Transformation

---

Binaryen IR

" Binaryen's internal IR is designed to be

    Flexible and fast for optimization.
    As close as possible to WebAssembly so it is simple and fast to convert it to and from WebAssembly.

There are a few differences between Binaryen IR and the WebAssembly? language:

    Tree structure
        Binaryen IR is a tree, i.e., it has hierarchical structure, for convenience of optimization. This differs from the WebAssembly binary format which is a stack machine.
        Consequently Binaryen's text format allows only s-expressions. WebAssembly's official text format is primarily a linear instruction list (with s-expression extensions). Binaryen can't read the linear style, but it can read a wasm text file if it contains only s-expressions.
        Binaryen uses Stack IR to optimize "stacky" code (that can't be represented in structured form).
        When stacky code must be represented in Binaryen IR, such as with multivalue instructions and blocks, it is represented with tuple types that do not exist in the WebAssembly language. In addition to multivalue instructions, locals and globals can also have tuple types in Binaryen IR but not in WebAssembly.
    Types and unreachable code
        WebAssembly limits block/if/loop types to none and the concrete value types (i32, i64, f32, f64). Binaryen IR has an unreachable type, and it allows block/if/loop to take it, allowing local transforms that don't need to know the global context. As a result, Binaryen's default text output is not necessarily valid wasm text. (To get valid wasm text, you can do --generate-stack-ir --print-stack-ir, which prints Stack IR, this is guaranteed to be valid for wasm parsers.)
        Binaryen ignores unreachable code when reading WebAssembly binaries. That means that if you read a wasm file with unreachable code, that code will be discarded as if it were optimized out (often this is what you want anyhow, and optimized programs have no unreachable code anyway, but if you write an unoptimized file and then read it, it may look different). The reason for this behavior is that unreachable code in WebAssembly has corner cases that are tricky to handle in Binaryen IR (it can be very unstructured, and Binaryen IR is more structured than WebAssembly as noted earlier). Note that Binaryen does support unreachable code in .wat text files, since as we saw Binaryen only supports s-expressions there, which are structured.
    Blocks
        Binaryen IR has only one node that contains a variable-length list of operands: the block. WebAssembly on the other hand allows lists in loops, if arms, and the top level of a function. Binaryen's IR has a single operand for all non-block nodes; this operand may of course be a block. The motivation for this property is that many passes need special code for iterating on lists, so having a single IR node with a list simplifies them.
        As in wasm, blocks and loops may have names. Branch targets in the IR are resolved by name (as opposed to nesting depth). This has 2 consequences:
            Blocks without names may not be branch targets.
            Names are required to be unique. (Reading .wat files with duplicate names is supported; the names are modified when the IR is constructed).
        As an optimization, a block that is the child of a loop (or if arm, or function toplevel) and which has no branches targeting it will not be emitted when generating wasm. Instead its list of operands will be directly used in the containing node. Such a block is sometimes called an "implicit block".
    Multivalue
        Binaryen will not represent multivalue instructions and values directly. Binaryen's main focus is on optimization of wasm, and therefore the question of whether we should have multivalue in the main IR is whether it justifes the extra complexity there. Experiments show that the shrinking of code size thanks to multivalue is useful but small, just 1-3% or so. Given that, we prefer to keep the main IR simple, and focus on multivalue optimizations in Stack IR, which is more suitable for such things.
        Binaryen does still need to implement the "ABI" level of multivalue, that is, we need multivalue calls because those may cross module boundaries, and so they are observable externally. To support that, Binaryen may use push and pop as mentioned earlier; another option is to add LLVM-like extractvalue/composevalue instructions.

" -- https://github.com/WebAssembly/binaryen#binaryen-ir

---

Lisp the ultimate opcode

An assembly language, not an intermediate one.

https://dspace.mit.edu/handle/1721.1/5731 https://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.pdf?sequence=2&isAllowed=y

see section "Instruction set" starting on pdf page 31

---

STRAP

https://github.com/mniip/BOOTSTRA/tree/master/STRAP

---

QBE

https://c9x.me/compile/

Used in https://github.com/michaelforney/cproc

---

Pascal P5 P-Code

Links:

---

BRIL

https://capra.cs.cornell.edu/bril/intro.html

used in https://www.cs.cornell.edu/courses/cs6120/2020fa/

Dalvik

Android has a non-canonical JVM compiler that called 'Dalvik' that compiles JVM to another Dalvik-specific VM.

It doesn't support invokedynamic. (?)

Retrospectives:

Variant implementations of dalvik:

---

Oberon RISC

https://people.inf.ethz.ch/wirth/FPGA-relatedWork/RISC.pdf (the ISA is defined in pages 2 thru 6 (sections 2 thru 3); the rest concerns hardware implementation)

---

Algorand TEAL

https://developer.algorand.org/docs/reference/teal/specification/ https://developer.algorand.org/docs/reference/teal/opcodes/ https://developer.algorand.org/docs/features/asc1/teal/ https://developer.algorand.org/articles/introducing-teal-version-3/

---

Mako VM

https://github.com/JohnEarnest/Mako "Mako is a portable stack-based virtual game console. Mako was designed to be simple to port and implement: even including optional features, the reference implementation is only a few pages of Java.

The Mako platform includes a complete development toolchain centered around Maker, a Forth-like systems programming language. Maker comes with an extensive standard library, including such highlights as a modular garbage collector, a cooperative multitasking system, an entity management system, and audio synthesis utilities. Where applicable, libraries have test harnesses based on the Test Anything Protocol.

Other programming tools targeting the Mako VM include FiveTran?, a historically-inspired FORTRAN compiler, and Stroyent, a C-like systems language. Other programming environments run directly on the Mako VM, like MASICA, a TinyBASIC?, Loko, a powerful Logo environment, and MakoForth?, a proper Forth which powers the game Forth Warrior.

...

Hardware Overview

    All registers are memory-mapped, simplifying save-states and metaprogramming.
    Dual-stack architecture (parameter stack and return stack).
    32-bit word-oriented memory.
    320x240 pixel 24-bit display at 60hz.
    256 variable-sized sprites with flags for mirroring.
    Scrollable 31x41 grid of 8x8 background tiles, with draw-priority flags.
    Keyboard and "virtual gamepad" input.
    8khz sampled audio output.
    Memory-mapped RNG.
    Optional console and filesystem I/O."

---

FiDo

https://github.com/JohnEarnest/Mako/blob/master/demos/FiDo.fs

"A tiny compiler based on the simple programming language described by Edsger Dijkstra in the book "A Discipline of Programming". John Earnest "

Mite

https://www.cs.tufts.edu/~nr/cs257/archive/reuben-thomas/mitethes.pdf (November 2000)

SIC (Symmetric Interaction Calculus)

https://github.com/VictorTaelin/Symmetric-Interaction-Calculus

"The Symmetric Interaction Calculus is a minimal programming language and model of computation obtained by slightly modifying the Lambda Calculus so that it matches perfectly the abstract part of Lamping's optimal reduction algorithm. ... The syntax is obtained by simply extending the Lambda Calculus with pairs and le ... Except variables are restricted to occur only once and are freed to occur globally (why?).

"term ::=

-- [5]
λx. term -- abstraction
(term term) -- application
(term,term) -- pair
let (p,q) = term in term -- definition
x -- variable"

HVM

https://github.com/Kindelia/HVM https://github.com/Kindelia/HVM/blob/master/HOW.md

example: " Creates a tree with `2^n` elements (Gen 0) = (Leaf 1) (Gen n) = (Node (Gen(- n 1)) (Gen(- n 1)))

Adds all elements of a tree (Sum (Leaf x)) = x (Sum (Node a b)) = (+ (Sum a) (Sum b))

Performs 2^n additions in parallel (Main n) = (Sum (Gen n)) " -- https://github.com/Kindelia/HVM

"High-order Virtual Machine (HVM) is a pure functional compile target that is lazy, non-garbage-collected and massively parallel. It is also beta-optimal, meaning that, in several cases, it can be exponentially faster than most functional runtimes, including Haskell's GHC.

That is possible due to a new model of computation, the Interaction Net, which combines the Turing Machine with the Lambda Calculus. Previous implementations of this model have been inefficient in practice, however, a recent breakthrough has drastically improved its efficiency, giving birth to the HVM." " -- https://github.com/Kindelia/HVM

"HVM doesn't need a global, stop-the-world garbage collector because every "object" only exists in one place, exactly like in Rust; i.e., HVM is linear. The catch is that, when an object needs to be referenced in multiple places, instead of a complex borrow system, HVM has an elegant, pervasive lazy clone primitive that works very similarly to Haskell's evaluation model. This makes cloning essentially free, because the copy of any object isn't made in a single, expensive pass, but in a layer-by-layer, on-demand fashion. And the nicest part is that this clone primitive works for not only data, but also for lambdas, which explains why HVM has better asymptotics than GHC: it is capable of sharing computations inside lambdas, which GHC can't. That was only possible due to a key insight that comes from Lamping's Abstract Algorithm for optimal evaluation of λ-calculus terms. Finally, the fact that objects only exist in one place greatly simplifies parallelism. Notice how there is only one use of atomics in the entire runtime.c.

This was all known and possible since years ago (see other implementations of optimal reduction), but all implementations of this algorithm, until now, represented terms as graphs. This demanded a lot of pointer indirection, making it slow in practice. A new memory format, based on SIC, takes advantage of the fact that inputs are known to be λ-terms, allowing for a 50% lower memory usage, and letting us avoid several impossible cases. This made the runtime 50x (!) faster, which finally allowed it to compete with GHC and similar." " -- https://github.com/Kindelia/HVM/blob/master/HOW.md

" HVM's Core is a very simple language that resembles untyped Haskell. It features lambdas (eliminated by applications), constructors (eliminated by user-defined rewrite rules) and machine integers (eliminated by operators).

term ::=

λvar. term # a lambda
(term term) # an application
(ctr term term ...) # a constructor
num # a machine int
(op2 term term) # an operator
let var = term; term # a local definition

rule ::=

term = term

file ::= list<rule> " -- https://github.com/Kindelia/HVM/blob/master/HOW.md

Discussion:

---

nand2tetris VM

https://drive.google.com/file/d/19fe1PeGnggDHymu4LlVY08KmDdhMVRpm/view https://drive.google.com/file/d/1lBsaO5XKLkUgrGY6g6vLMsiZo6rWxlYJ/view https://www.csie.ntu.edu.tw/~cyy/courses/introCS/14fall/lectures/handouts/lec11_VMI_4up.pdf

https://www.nand2tetris.org/project07

https://drive.google.com/file/d/1lBsaO5XKLkUgrGY6g6vLMsiZo6rWxlYJ/view

https://www.nand2tetris.org/project08

" Arithmetic / Boolean commands add sub neg eq gt lt and or not

Memory access commands pop x (pop into x, which is a variable) push y (y being a variable or a constant)

Program flow commands label (declaration) goto (label) if‐goto (label) Function calling commands function (declaration) call (a function) return (from a function) " -- https://www.csie.ntu.edu.tw/~cyy/courses/introCS/14fall/lectures/handouts/lec11_VMI_4up.pdf

https://www.csie.ntu.edu.tw/~cyy/courses/introCS/14fall/lectures/handouts/lec12_VMII_4up.pdf

---

Pawn

Pawn is a tiny, embeddable, C-like language. It is untyped but uses "tags" instead. It is from 1999.

A variant of Pawn is Sourcepawn:

mini-vm

https://github.com/philipaconrad/mini-vm

"Out of the box it supports 0 operations, but it is very easy to extend." -- [6] ---

Popular ILs

Lists of ILs


Footnotes:

1.

 b 	Shift leftSHR 	c = a