Table of Contents for Programming Languages: a survey

Other intermediate target languages designed for implementing a single high-level language

---

CPython bytecode

Two stacks:

• main stack
• block stack: "Per frame, there is a stack of blocks, denoting nested loops, try statements, and such."

Stack ops:

• various rots, dups
• in-place binary arithmetic on top0, top1 (doesn't consume top1)

Arithmetic:

• arithmetical negation (-6 -> 6), boolean negation (-6 -> False), inversion (-6 -> 5), unary positive (does nothing by default but can be overridden by __pos__ in custom classes)

instructions:

quoted and paraphrased from https://docs.python.org/release/3.3.2/library/dis.html

General instructions:

• NOP
• POP_TOP (pop), ROT_TWO, ROT_THREE, DUP_TOP, DUP_TOP_TWO

Unary operations:

Unary operations take the top of the stack, apply the operation, and push the result back on the stack.

• UNARY_POSITIVE (+TOS), UNARY_NEGATIVE, UNARY_NOT (not TOS), UNARY_INVERT (~TOS), GET_ITER (iter(TOS))

Binary operations:

Binary operations remove the top of the stack (TOS) and the second top-most stack item (TOS1) from the stack. They perform the operation, and put the result back on the stack.

• BINARY_POWER (TOS1 TOS), BINARY_MULTIPLY, BINARY_FLOOR_DIVIDE (TOS1 TOS), BINARY_TRUE_DIVIDE (TOS1 / TOS), BINARY_MODULO, BINARY_ADD, BINARY_SUBTRACT, BINARY_SUBSCR(TOS1[TOS]), BINARY_LSHIFT (TOS1 1 TOS), BINARY_AND, BINARY_XOR, BINARY_OR

In-place operations:

In-place operations are like binary operations, in that they remove TOS and TOS1, and push the result back on the stack, but the operation is done in-place when TOS1 supports it, and the resulting TOS may be (but does not have to be) the original TOS1.

INPLACE_POWER, INPLACE_MULTIPLY, INPLACE_FLOOR_DIVIDE, INPLACE_TRUE_DIVIDE, INPLACE_MODULO, INPLACE_ADD, INPLACE_SUBTRACT, INPLACE_LSHIFT, INPLACE_RSHIFT, INPLACE_AND, INPLACE_XOR, INPLACE_OR, STORE_SUBSCR (TOS1[TOS] = TOS2), DELETE_SUBSCR (del TOS1[TOS]),

Miscellaneous opcodes:

PRINT_EXPR

• BREAK_LOOP, CONTINUE_LOOP(target) (target is the address to jump to (which should be a FOR_ITER instruction))
• SET_ADD(i) (Calls set.add(TOS1[-i], TOS)), LIST_APPEND(i) (list.append(TOS[-i], TOS)), MAP_ADD(i) (dict.setitem(TOS1[-i], TOS, TOS1)). For all of the SET_ADD, LIST_APPEND and MAP_ADD instructions, while the added value or key/value pair is popped off, the container object remains on the stack so that it is available for further iterations of the loop.
• RETURN_VALUE (Returns with TOS to the caller of the function), YIELD_VALUE (Pops TOS and yields it from a generator), YIELD_FROM (Pops TOS and delegates to it as a subiterator from a generator)
• IMPORT_STAR (Loads all symbols not starting with '_' directly from the module TOS to the local namespace. The module is popped after loading all names. This opcode implements 'from module import *')
• POP_BLOCK (Removes one block from the block stack. Per frame, there is a stack of blocks, denoting nested loops, try statements, and such)
• POP_EXCEPT (Removes one block from the block stack. The popped block must be an exception handler block, as implicitly created when entering an except handler. In addition to popping extraneous values from the frame stack, the last three popped values are used to restore the exception state.)
• END_FINALLY (Terminates a finally clause. The interpreter recalls whether the exception has to be re-raised, or whether the function returns, and continues with the outer-next block)
• LOAD_BUILD_CLASS (builtins.__build_class__() onto the stack. It is later called by CALL_FUNCTION to construct a class)
• SETUP_WITH(delta) (This opcode performs several operations before a with block starts. First, it loads __exit__() from the context manager and pushes it onto the stack for later use by WITH_CLEANUP. Then, __enter__() is called, and a finally block pointing to delta is pushed. Finally, the result of calling the enter method is pushed onto the stack. The next opcode will either ignore it (POP_TOP), or store it in (a) variable(s) (STORE_FAST, STORE_NAME, or UNPACK_SEQUENCE).)
• WITH_CLEANUP (Cleans up the stack when a with statement block exits. TOS is the context manager’s __exit__() bound method. (see https://docs.python.org/release/3.3.2/library/dis.html#opcode-WITH_CLEANUP for details)
• STORE_LOCALS (Pops TOS from the stack and stores it as the current frame’s f_locals. This is used in class construction)

Miscellaneous opcodes with arguments:

All of the following opcodes expect arguments. An argument is two bytes, with the more significant byte last.

• STORE_NAME(namei) (name = TOS; namei is the index of name in the attribute co_names of the code object. The compiler tries to use STORE_FAST or STORE_GLOBAL if possible)
• DELETE_NAME(namei) (del name)
• UNPACK_SEQUENCE(count) (Unpacks TOS into count individual values, which are put onto the stack right-to-left)
• UNPACK_EX(counts) (Implements assignment with a starred target: Unpacks an iterable in TOS into individual values, where the total number of values can be smaller than the number of items in the iterable: one the new values will be a list of all leftover items)
• STORE_ATTR(namei) (TOS.name = TOS1)
• DELETE_ATTR(namei) (del TOS.name)
• STORE_GLOBAL(namei) (STORE_NAME, but stores the name as a global)
• DELETE_GLOBAL(namei)
• LOAD_CONST(consti) (Pushes co_consts[consti] onto the stack), LOAD_NAME(namei) (Pushes the value associated with co_names[namei] onto the stack)
• BUILD_TUPLE(count) (Creates a tuple consuming count items from the stack), BUILD_LIST(count), BUILD_SET(count), BUILD_MAP(count) (Pushes a new dictionary object onto the stack. The dictionary is pre-sized to hold count entries)
• LOAD_ATTR(namei) (getattr(TOS, co_names[namei]))
• COMPARE_OP(opname) (Performs a Boolean operation. The operation name can be found in cmp_op[opname])
• IMPORT_NAME(namei) (Imports the module co_names[namei]. TOS and TOS1 are popped and provide the fromlist and level arguments of __import__(). The module object is pushed onto the stack. The current namespace is not affected: for a proper import statement, a subsequent STORE_FAST instruction modifies the namespace)
• IMPORT_FROM(namei) (Loads the attribute co_names[namei] from the module found in TOS)
• JUMP_FORWARD(delta) (Increments bytecode counter by delta)
• POP_JUMP_IF_TRUE(target) (If TOS is true, sets the bytecode counter to target. TOS is popped)
• POP_JUMP_IF_FALSE(target)
• JUMP_IF_TRUE_OR_POP(target) (If TOS is true, sets the bytecode counter to target and leaves TOS on the stack. Otherwise (TOS is false), TOS is popped)
• JUMP_IF_FALSE_OR_POP(target) (If TOS is false, sets the bytecode counter to target and leaves TOS on the stack. Otherwise (TOS is true), TOS is popped)
• JUMP_ABSOLUTE(target) (Set bytecode counter to target)
• FOR_ITER(delta) (TOS is an iterator. Call its __next__() method. If this yields a new value, push it on the stack (leaving the iterator below it). If the iterator indicates it is exhausted TOS is popped, and the byte code counter is incremented by delta)
• LOAD_GLOBAL(namei) (Loads the global named co_names[namei] onto the stack)
• SETUP_LOOP(delta): Pushes a block for a loop onto the block stack. The block spans from the current instruction with a size of delta bytes.
• SETUP_EXCEPT(delta): Pushes a try block from a try-except clause onto the block stack. delta points to the first except block.
• SETUP_FINALLY(delta): Pushes a try block from a try-except clause onto the block stack. delta points to the finally block.
• STORE_MAP: Store a key and value pair in a dictionary. Pops the key and value while leaving the dictionary on the stack.
• LOAD_FAST(var_num), STORE_FAST(var_num), DELETE_FAST(var_num): local co_varnames[var_num]
• LOAD_CLOSURE(i): Pushes a reference to the cell contained in slot i of the cell and free variable storage. The name of the variable is co_cellvars[i] if i is less than the length of co_cellvars. Otherwise it is co_freevars[i - len(co_cellvars)].
• LOAD_DEREF(i) (Loads the cell contained in slot i of the cell and free variable storage. Pushes a reference to the object the cell contains on the stack), STORE_DEREF(i)
• DELETE_DEREF(i)
• RAISE_VARARGS(argc): Raises an exception. argc indicates the number of parameters to the raise statement, ranging from 0 to 3. The handler will find the traceback as TOS2, the parameter as TOS1, and the exception as TOS.
• CALL_FUNCTION(argc): Calls a function. The low byte of argc indicates the number of positional parameters, the high byte the number of keyword parameters. Pops all function arguments, and the function itself off the stack, and pushes the return value.
• MAKE_FUNCTION(argc): Pushes a new function object on the stack. TOS is the qualified name of the function; TOS1 is the code associated with the function. The function object is defined to have argc default parameters, which are found below TOS1.
• MAKE_CLOSURE(argc): Creates a new function object, sets its __closure__ slot, and pushes it on the stack. TOS is the qualified name of the function, TOS1 is the code associated with the function, and TOS2 is the tuple containing cells for the closure’s free variables. The function also has argc default parameters, which are found below the cells.
• BUILD_SLICE(argc): Pushes a slice object on the stack. argc must be 2 or 3. If it is 2, slice(TOS1, TOS) is pushed; if it is 3, slice(TOS2, TOS1, TOS) is pushed. See the slice() built-in function for more information.

todo

• EXTENDED_ARG(ext)

    Prefixes any opcode which has an argument too big to fit into the default two bytes. ext holds two additional bytes which, taken together with the subsequent opcode’s argument, comprise a four-byte argument, ext being the two most-significant bytes.

CALL_FUNCTION_VAR(argc)

    Calls a function. argc is interpreted as in CALL_FUNCTION. The top element on the stack contains the variable argument list, followed by keyword and positional arguments.

CALL_FUNCTION_KW(argc)

    Calls a function. argc is interpreted as in CALL_FUNCTION. The top element on the stack contains the keyword arguments dictionary, followed by explicit keyword and positional arguments.

CALL_FUNCTION_VAR_KW(argc)

    Calls a function. argc is interpreted as in CALL_FUNCTION. The top element on the stack contains the keyword arguments dictionary, followed by the variable-arguments tuple, followed by explicit keyword and positional arguments.

• HAVE_ARGUMENT: This is not really an opcode. It identifies the dividing line between opcodes which don’t take arguments < HAVE_ARGUMENT and those which do >= HAVE_ARGUMENT.

Note: as of Python 3.6, "The Python interpreter now uses a 16-bit wordcode instead of bytecode which made a number of opcode optimizations possible. (Contributed by Demur Rumed with input and reviews from Serhiy Storchaka and Victor Stinner in bpo-26647 and bpo-28050.)" [1].

(rationale: "The change is to have all instructions take an argument. This removes the branch on each instruction on whether to load oparg. It then also aligns instructions to always be 2 bytes rather than 1 or 3 by having arguments only take up 1 byte. In the case that an argument to an instruction is greater than 255, it can chain EXTENDED_ARG up to 3 times. In practice this rarely occurs, mostly only for jumps, & abarnert measured stdlib to be ~5% smaller

The rationale is that this offers 3 benefits: Smaller code size, simpler instruction iteration/indexing (One may now scan backwards, as peephole.c does in this patch), which between the two results in a small perf gain (the only way for perf to be negatively impacted is by an increase in EXTENDED_ARGs, when I post benchmarking I'll also post a count of how many more EXTENDED_ARGs are emitted)

This also means that if I want to create something like a tracer that tracks some information for each instruction, I can allocate an array of codesize/2 bytes, then index off of half the instruction index. This isn't currently done in peephole.c, nor does this include halving jump opargs

" ) -- [2]

Links:

• http://docs.python.org/release/3.3.2/library/dis.html#bytecodes
• www.troeger.eu/files/teaching/pythonvm08.pdf
• http://www.aosabook.org/en/500L/a-python-interpreter-written-in-python.html

---

Dalvik VM

todo http://www.netmite.com/android/mydroid/dalvik/docs/dalvik-bytecode.html

(todo is this wrong?) interestingly, Dalvik only has 16 registers.

however:

" The Dalvik instruction set implements an interesting compromise: it is register based, but there are a finite number of them as opposed to the theoretically infinite registers of LLVM or Parrot. Dalvik supports 65,536 registers, a vast number compared to hardware CPUs and presumably sufficient to implement SSA (if desired) in reasonably large functions.

Even more interestingly, not all Dalvik instructions can access all registers. Many Dalvik instructions dedicate 4 bits to the register number, requiring their operands to be stored in the first 16 registers. A few more instructions have an 8 bit instruction number, to access the first 256. There are also instructions to copy the value to or from any of the 65,536 registers to a low register, for a subsequent instruction to access.

It took a while to understand the rationale for this choice, and I'm still not confident I fully get it. Clearly the Dalvik designers believe that keeping data in one of the high registers will be faster than explicitly storing it to memory, even if the vast number of registers end up mostly residing in RAM. Addressing data as register numbers instead of memory addresses should make it easier for the VM to dynamically remap Dalvik registers to the real hardware registers. For example, if it can predict that virtual register 257 will likely be used in the near future it can be kept in a CPU register instead of being immediately stored to memory. " -- http://codingrelic.geekhold.com/2010/07/virtual-instruction-sets-opcode.html

Non-deprecated, non-implementation-specific instructions (many instructions have _2ADDR forms, and many also have _LIT8 and _LIT16 forms, and many have _WIDE forms, and many have _FLOAT, _INT, and _LONG forms, and many have _BOOLEAN, _BYTE, _CHAR, _OBJECT, _SHORT, and _WIDE forms, and many have _16 and _32 forms, and many of these are mixed, e.g. ADD_INT_2ADDR. I'll only list the base instruction in these cases)

ADD AGET AND APUT ARRAY_LENGTH CHECK_CAST CMPG CMPL CMP CONST CONST_CLASS CONST_HIGH16 CONST_STRING CONST_STRING_JUMBO DIV DOUBLE_TO_FLOAT DOUBLE_TO_INT DOUBLE_TO_LONG FILLED_NEW_ARRAY FILLED_NEW_ARRAY_RANGE FILL_ARRAY_DATA FLOAT_TO_DOUBLE FLOAT_TO_INT FLOAT_TO_LONG GOTO IF_EQ IF_EQZ IF_GE IF_GEZ IF_GT IF_GTZ IF_LE IF_LEZ IF_LT IF_LTZ IF_NE IF_NEZ IGET INSTANCE_OF INT_TO_BYTE INT_TO_CHAR INT_TO_DOUBLE INT_TO_FLOAT INT_TO_LONG INT_TO_SHORT INVOKE_DIRECT INVOKE_DIRECT_RANGE INVOKE_INTERFACE INVOKE_INTERFACE_RANGE INVOKE_STATIC INVOKE_STATIC_RANGE INVOKE_SUPER INVOKE_SUPER_RANGE INVOKE_VIRTUAL INVOKE_VIRTUAL_RANGE IPUT LONG_TO_DOUBLE LONG_TO_FLOAT LONG_TO_INT MONITOR_ENTER MONITOR_EXIT MOVE MOVE_16 MOVE_EXCEPTION MOVE_FROM16 MOVE_OBJECT MOVE_OBJECT_16 MOVE_OBJECT_FROM16 MOVE_RESULT MOVE_RESULT_OBJECT MOVE_RESULT_WIDE MOVE_WIDE MOVE_WIDE_16 MOVE_WIDE_FROM16 MUL NEG NEW_ARRAY NEW_INSTANCE NOP NOT OR PACKED_SWITCH REM RETURN RETURN_OBJECT RETURN_VOID RETURN_WIDE RSUB SGET SHL SHL SHR SPARSE_SWITCH SPUT SPUT SUB SUB THROW USHR XOR

Links:

• http://source.android.com/devices/tech/dalvik/index.html
  • http://source.android.com/devices/tech/dalvik/dalvik-bytecode.html
  • http://source.android.com/devices/tech/dalvik/dex-format.html
• http://www.netmite.com/android/mydroid/dalvik/docs/
• http://developer.android.com/reference/dalvik/bytecode/Opcodes.html
• http://www.retrodev.com/android/dexformat.html
• http://www.netmite.com/android/mydroid/dalvik/docs/dalvik-bytecode.html

---

Perl6

NQP

https://github.com/perl6/nqp

opcodes (about 268 of them): https://github.com/perl6/nqp/blob/master/docs/ops.markdown

MoarVM

MoarVM? is a VM built for Perl6's Rakudo implementation (the most canonical Perl6 implementation as of this writing).

• Register-based (16-bit registers identifiers, so on the order of 2^16 possible registers)
• primitive types: int, num, str, object
• uses libuv for async I/O, libtommath for multiple precision arithmetic, libatomic_ops for atomic operations, uthash for hashes

MoarVM introduction and features

• "In NQP and Rakudo, all operations that we can perform in a VM-independent way are captured in the nqp:: op set. Covers arithmetic, string manipulation, array and hash operations, object operations, I/O, and a few specialized things for the grammar engine. The MoarVM? instruction set is largely derived from this " -- [3]
• "MoarVM? includes the Unicode Character Database so far as we need it for Perl 6. No external dependencies (like ICU)" -- [4]
• "Threadsafe...We use mutexes in some places. However, many places –especially anything on a hot path –uses atomic operations in place of locks" [5]

"The heart of the VM": "

• Bytecode interpreter
• Most of 6 model
• Generational, parallel GC
• String and Unicode support
• Basic thread support
• Basic I/O support " -- [6]

"What does a VM typically do?

• Execute instructions (possibly by interpreting, possibly by JIT compilation, often a combination)
• Provide memory management (both allocation and deallocation, typically through garbage collection)
• Offer a range of built-in data structures and instructions to operate on them (strings, arrays, objects, ...)
• Abstract away the details of the underlying OS and expose a common interface to IO, threading, etc." " -- [7]

" Some key features provided by MoarVM? include:

• Meta-object programming, using the 6model design
• Precise, generational, and parallel GC
• Unicode 8.0 support (Unicode Character Database, encodings, normalization)
• First-class code objects, lexical variables and closures
• Exceptions
• Continuations
• Bounded serialization
• Code generation from MAST (MoarVM? AST)
• Runtime loading of code
• Big integers
• A range of IO and process support, including asynchronous sockets, signals, timers, and processes
• Native calling and native pointer manipulation
• Threads, mutexes, condition variables, semaphores, and blocking queues
• Bytecode specialization by type, and numerous optimizations (including resolution of method calls and multiple dispatch, dead code elimination, inlining, and on stack replacement)
• JIT compilation
• Instrumentation-based profiling of call frames and allocations " -- [8]

MoarVM AST (MAST)

12 different node types:

• CompUnit?
• Frame
• Op
• SVal
• IVal
• NVal
• Label
• Local
• Lexical
• Call
• Annotated
• HandlerScope?

-- [9]

MoarVM 6model

6model according to http://jnthn.net/papers/2013-yapceu-moarvm.pdf and https://github.com/jnthn/6model/blob/master/overview.pod :

"An object is a blob of memory. The only constraint is that the first thing in the blob must be a pointer/reference to a Shared Table data structure." -- https://github.com/jnthn/6model/blob/master/overview.pod

Object is composed of:

• STable
• Flags, owner
• GC stuff
• <body>

STable is composed of:

• HOW (meta-object)
• REPResentation
• WHAT (type object)
• WHO (stash) ("The package supporting the object." [10]) ("A Stash is a hash that is used for symbol tables at the package scoping level in Perl 6.") -- [11]
• Method cache
• Type check cache

on meta-objects: 6model "provides one meta-object that implements objects with attributes (state) and methods (behavior) - and that's about it. It doesn't enforce one definition of method dispatch, inheritance, interfaces, introspection and so forth. These are all built up by implementing meta-objects that specify their semantics." -- [12]

on representations: " Rather than committing to one view of how to lay out an object in memory, 6model supports "representations". Representations define how attributes are actually stored and accessed, how primitive types (integers, floating point values and strings) are boxed and unboxed - or perhaps both. Additionally, representations are orthogonal to meta-objects, meaning it is possible to define one type (e.g. a class) and use it with different storage strategies. This is known as representation polymorphism...An object may in the abstract be a blob of memory that starts with a pointer to a Shared Table, but of course something has to know what the rest of it means. That's what representations do. A representation is responsible for object allocation, attribute storage and access (both in terms of memory layout and operation), boxing from and unboxing to native types and (depending on the VM) GC interaction. Representations may be like singletons, or they may act more like instances. How a representation is implemented is VM-specific; in fact, pretty much everything the representation has to do is also VM-specific." -- [13]

on meta-objects and caches:

"In an ideal world, every single method dispatch we perform would be conducted by delegating to the meta-object's method that implements method dispatch semantics. In the real world, that's not practical from a performance point of view. Thus 6model provides various mechanisms that a meta-object can "opt in" to in order to allow for muchly increased performance. However, it considers all of these to really just be a kind of "cache". A v-table is just an array of invokable objects published by the meta-object, which it is responsible for maintaining. Similar things apply to type-checking." -- [14]

" REPR API has a common part (allocation, GC marking) along with several sub - protocols for different ways of using memory: Representations are orthogonal to type (and thus dis - interested in method dispatch, type check, etc.) and also non - virtual (if you know the REPR, can inline stuff) "

there are various calls to functions prefixed with 'MVM_6model' in https://github.com/MoarVM/MoarVM/blob/master/src/core/interp.c

these seem to be declared in https://github.com/MoarVM/MoarVM/blob/master/src/6model/6model.h

the list seems to be (for readabilty, i removed the 'MVM' prefixes from everything in this list, and also the '6model' prefixes):

• PUBLIC Object * get_how(ThreadContext? *tc, STable *st);
• PUBLIC Object * get_how_obj(ThreadContext? *tc, Object *obj);
• void find_method(ThreadContext? *tc, Object *obj, String *name, Register *res);
• PUBLIC Object * find_method_cache_only(ThreadContext? *tc, Object *obj, String *name);
• int32 find_method_spesh(ThreadContext? *tc, Object *obj, String *name, int32 ss_idx, Register *res);
• int64 can_method_cache_only(ThreadContext? *tc, Object *obj, String *name);
• void can_method(ThreadContext? *tc, Object *obj, String *name, Register *res);
• void istype(ThreadContext? *tc, Object *obj, Object *type, Register *res);
• PUBLIC int64 istype_cache_only(ThreadContext? *tc, Object *obj, Object *type);
• int64 try_cache_type_check(ThreadContext? *tc, Object *obj, Object *type, int32 *result);
• void invoke_default(ThreadContext? *tc, Object *invokee, Callsite *callsite, Register *args);
• void stable_gc_free(ThreadContext? *tc, STable *st);
• uint64 next_type_cache_id(ThreadContext? *tc);
• void never_repossess(ThreadContext? *tc, Object *obj);

https://github.com/MoarVM/MoarVM/blob/master/docs/bootstrap.markdown describes various primitive types in MoarVM?: strings, arrays, hashes, (external/foreign) functions. All of these are needed for fields within the 'primitive' meta-object type, KnowHOW?. KnowHOW? meta-objects are then constructed for each of the other primitive types. The meta-object for the KnowHOW? class itself is itself a KnowHOW?.

"Every object in MoarVM? is a 6model object - one object system for the whole VM. By object, we mean what you think of as objects (Arrays, Hashes, Boxed integers, floats, etc., Threads, handles)..." [15]

Presumably much of MoarVM?'s 6model implementation is in https://github.com/MoarVM/MoarVM/blob/master/src/6model/

See also http://doc.perl6.org/language/mop

MoarVM links

• http://jnthn.net/papers/2013-yapceu-moarvm.pdf
• http://perl6.com/MoarVM_talk1.pdf‎
• opcodes (that's pretty unenlightening; here's the implementation, i think: https://github.com/MoarVM/MoarVM/blob/master/src/core/interp.c ; and perhaps many of them are the same as NQP opcodes, which are documented at https://github.com/perl6/nqp/blob/master/docs/ops.markdown)
• http://6guts.wordpress.com/2013/05/31/moarvm-a-virtual-machine-for-nqp-and-rakudo/
• https://perl6advent.wordpress.com/2014/12/11/day-11-so-what-does-moarvm-do-with-your-perl-6-code/
• https://github.com/MoarVM/MoarVM/blob/master/docs/jit/overview.org

---

Haskell GHC languages

Note that Haskell is implemented a bit differently from many languages; this stems from Haskell's properties:

• lazy (ie. at runtime we often pass around suspended expressions or 'thunks' rather than values)
• higher-order functions (ie. functions are first-class values)
• currying (ie. if we apply a function f to two arguments using the expression 'f x y', and the result type is an integer, then (f x) is a function which returns a function which takes one argument and returns an integer; in some implementations, the 'f' in (f x y) could be internally implemented either by (a) a function which takes one argument and returns a function which returns an integer, (b) a function which takes two arguments, and returns an integer (c) a function which takes more than two arguments, in which case the result of 'f x y' is a partially applied function)

It is therefore assumed that Haskell programs will, at runtime, very frequently be dealing with unevaluated thunks, with closures which represent unevaluated or partially evaluated functions, and with the application of functions whose arity was unknown at compile time.

• https://www.stephendiehl.com/posts/ghc_02.html
• https://stackoverflow.com/questions/24639279/why-does-ghc-typecheck-before-desugaring

GHC Core

• http://www.scs.stanford.edu/11au-cs240h/notes/ghc-slides.html
• http://webcache.googleusercontent.com/search?q=cache:zDvHNEwVmusJ:www.scs.stanford.edu/11au-cs240h/notes/ghc-slides.html&client=ubuntu&hl=en&gl=us&strip=1
• http://www.haskell.org/ghc/docs/latest/html/libraries/ghc/CoreSyn.html
• https://github.com/ghc/ghc/blob/master/docs/core-spec/core-spec.pdf
• https://github.com/ghc/ghc/tree/master/docs/core-spec
• Chapter 2 (and Appendix E.3) of http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-835.pdf
• http://stackoverflow.com/questions/6121146/reading-ghc-core
• https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/CoreSynType
• http://www.haskellforall.com/2012/10/hello-core.html
• http://typesandkinds.wordpress.com/2012/12/03/a-formalization-of-ghcs-core-language/
• http://alpmestan.com/2013/06/27/ghc-core-by-example-episode-1/
• http://www.aosabook.org/en/ghc.html section 5.3
• SL Peyton Jones, Compiling Haskell by program transformation: a report from the trenches
• GHC primitive types and operations
• http://www.haskellforall.com/2014/10/how-to-desugar-haskell-code.html
• https://www.youtube.com/watch?v=uR_VzYxvbxg

Possible extensions:

• http://www.cl.cam.ac.uk/~mb566/papers/tacc-talk-hs09-static.pdf
• https://github.com/batterseapower/cps-core

Core in one slide: " data Expr b -- "b" for the type of binders, = Var Id

Lit Literal

App (Expr b) (Arg b)

Lam b (Expr b)

Let (Bind b) (Expr b)

Case (Expr b) b Type [Alt b]

Type Type

Cast (Expr b) Coercion

Coercion Coercion

Tick (Tickish Id) (Expr b)

data Bind b = NonRec? b (Expr b)

Rec [(b, (Expr b))]

type Arg b = Expr b

type Alt b = (AltCon?, [b], Expr b)

data AltCon? = DataAlt? DataCon?

" -- [16]

LitAlt? Literal

DEFAULT

"Core is technically a variant of a System FC (which is itself a variant of System F)" -- [17]

" Values: Both data and functions Unboxed: Primitive (machine level) types, not "boxed up" on the heap Closure: Heap allocated data associated with a method Thunk: A suspended computation Continuations: The cousin of closures. Unlike a closure you aren't simply calling a function, you are continuing a saved execution state. Basically though, if you have closures and tail calls as Haskell does, continuations can be built.

Yes, closures, thunks and continuations are all very similar. One implementation can capture them all, however the terminology is used to capture the different use cases.

...

    redex(es):
    reducible expression. A expression that can be evaluated further
        normal form:
        an expression without an redexes
        head normal form:
        an expression where the top level (head) is neither a redex NOR a lambda abstraction with a reducible body
        weak head normal form:
        an expression where the top level (head) isn't a redex
	
    unfolding:
    unfolding of a function f is just the body of f.
        Unfolding = Inlining.

...

    evaluation strategies:
        call-by-value: arguments evaluated before function entered (copied)
        call-by-name: arguments passed unevaluated
        call-by-need: arguments passed unevaluated but an expression is only evaluated once (sharing)
    no-strict evaluation Vs. lazy evaluation:
        non-strict: Includes both call-by-name and call-by-need, general term for evaluation strategies that don't evaluate arguments before entering a function
        lazy evaluation: Specific type of non-strict evaluation. Uses call-by-need (for sharing).... scrutinee: The expression you are case'ing on in a case statement " -- [18]

"Graph Reduction: The way that lazy functional languages like Haskell are implemented is through a technique called graph reduction. Its best to use the graph reduction model as an intuitive way to think about how Haskell is evaluated, the actual way GHC implements Haskell is pretty close to how an imperative language works. " -- [19]