Formation Js Back End

DEGREE PROJECT IN TECHNOLOGY,
FIRST CYCLE, 15 CREDITS

STOCKHOLM, SWEDEN 2022
A JavaScript Backend
for the Miking Compiler
KTH Bachelor Thesis Report
William Rågstad
KTH ROYAL INSTITUTE OF TECHNOLOGY

ELECTRICAL ENGINEERING AND COMPUTER SCIENCE
© 2022 William Rågstad
Abstract
This thesis presents the design and implementation of an extension of the self-
hosted Miking compiler to enable the generation of JavaScript code for different
runtime environments and web browsers. Miking is a framework for developing
domain-specific and general-purpose programming languages through sound
language fragment composition, among other things, to create efficient compilers.
Miking Core encapsulates a meta-language called Miking Lang and a fundamental
functional Miking Expression language which Miking Lang itself is also lowered
to. The presented backend translates Miking expressions into semantically
equivalent effective, readable, sound, and correct JavaScript programs.
In this report, development challenges, implementation methods, and techniques

are also discussed and evaluated along with a review of the final compiler
backend. Likewise, details on JavaScript-specific optimizations and pattern-
matching compilation are presented, including how tail recursion is handled
to enable complex Miking programs to be compiled into flexible and efficient
JavaScript.
Keywords
Bachelor’s Thesis, Miking, JavaScript, Compiler, Semantics, Code Generation,
Optimization, Correctness, Soundness, and Readability.
CCS Assignment
Theory of computation → Semantics and reasoning → Program reasoning
Medium Relevance
Software and its engineering → Software notations and tools → Compilers
High Relevance
i
Abstract
Detta examensarbete presenterar design och implementation för utveckling av
Miking-kompilatorn, med syfte att möjliggöra generering av JavaScript-kod för
olika exekveringsmiljöer och webbläsare. Miking är ett ramverk för att utveckla
domänspecifika och generella programmeringsspråk genom sund komposition av
språksfragment som kan används för att skapa effektiva kompilatorer. Miking
Core ramverket innehåller ett metaspråk kallat Miking Lang, vilket ”sänks” till det
mer grundläggande funktionella Miking Expression-språket. ”Sänkning” betyder
i huvudsak att skriva om mer komplexa semantiska konstruktioner i form av
enklare. Den backend som presenteras översätter Miking-uttryck till semantiskt
ekvivalenta JavaScript program som också är effektiva, läsbara, sunda och
korrekta.
I denna rapport diskuteras och utvärderas även utvecklingsutmaningar,

implementeringsmetod och andra tekniker som har använts under arbetet.
På samma sätt presenteras detaljer om JavaScript-specifika optimeringar och
mönstermatchningskompilering, inklusive hur svansrekursion hanteras för att
möjliggöra kompilering av komplexa Miking-program till flexibel och effektiv
JavaScript med hjälp av ”trampoline” teknik.
Nyckelord
Kandidat Examensarbete, Miking, JavaScript,
Kompilatorer, Semantik, Kodgenerering, Optimering, Korrekthet, Sundhet och
Läsbarhet.
ii
Acknowledgements
Although this research project has been an intellectual challenge and a personally
developing experience, working on my bachelor’s thesis may have been one of the
most difficult tasks I have ever overcome and completed. The reason is primarily
due to the requirement of sustained long-term devotion and intense focus on
the completion of the project, with a lot of time investment and self-education
about existing research, methods, and techniques in programming languages.
Programming language theory and compiler construction is a field of research
that I have inadequate formal knowledge of previously and has led to the biggest
resistance in the work.
I would like to express special thanks to my supervisor David Broman for uniquely
investing trust in me and giving me the opportunity to do this thesis work together
with his research team and their project. Your professional support and guidance
on recent and relevant research have been useful and fundamental. Specifically, I
want to thank Lars Hummelgren for his vast expertise and support. I would also
like to thank my examiner Johan Montelius for providing excellent feedback and
guidance when writing my thesis, as well as being flexible, understanding, and
helpful in planning the stages of completion of this thesis.
Last but not least, I would like to thank my family for supporting and encouraging
my work through this thesis. Without you, this thesis would not exist.
Stockholm, November 2022

William Rågstad
iii
Author
William Rågstad
<wragstad@kth.se>
Bachelor’s Programme in Computer Science and Engineering
KTH Royal Institute of Technology
Place for Project

December 16, 2022
Stockholm, Sweden
KISTAGÅNGEN 16, KISTA
Examiner
Assoc. Prof. Johan Montelius
<johanmon@kth.se>
Supervisor
Assoc. Prof. David Broman
<dbro@kth.se>
Contents
List of Abbreviations viii
List of Program Code x
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6 Benefits, Ethics and Sustainability . . . . . . . . . . . . . . . . . . . 4
1.7 Delimitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Theoretical Background 6
2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 SMLtoJs: Hosting a Standard ML Compiler in a Web Browser 6
2.1.2 St Andrews Algol to JavaScript compiler project . . . . . . . 6
2.1.3 From bytecode to JavaScript: the Js_of_ocaml compiler . . 7
2.1.4 Hop Client-Side Compilation . . . . . . . . . . . . . . . . . . 7
2.1.5 A Compiler from CakeML to JavaScript . . . . . . . . . . . . 7
2.1.6 Research Themes . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Functional and Imperative Recursion . . . . . . . . . . . . . . . . . 9
3 Methodology 10
3.1 Research Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Software Engineering Process . . . . . . . . . . . . . . . . . . . . . 10
3.2.1 Project Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Testing and Validation . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3.1 Unit Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3.2 Benchmarking . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3.3 Partial Bootstrapping . . . . . . . . . . . . . . . . . . . . . . 14
4 Design 15
4.1 Pipeline Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.1.1 Frontend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1.2 Backend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 ECMAScript 2015 Support . . . . . . . . . . . . . . . . . . . . . . . 19
v
4.3 ES6 Features and Translations . . . . . . . . . . . . . . . . . . . . . 20
4.3.1 Variable Declaration . . . . . . . . . . . . . . . . . . . . . . . 20
4.3.2 Arrow Functions . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3.3 Ternary Operators . . . . . . . . . . . . . . . . . . . . . . . . 22
4.3.4 Rest & Spread Operators . . . . . . . . . . . . . . . . . . . . 22
4.3.5 Destructuring Assignment . . . . . . . . . . . . . . . . . . . 24
4.4 Target Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Implementation 26
5.1 Construct Transformations . . . . . . . . . . . . . . . . . . . . . . . 27
5.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.1.2 Lambdas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.1.3 Function Application . . . . . . . . . . . . . . . . . . . . . . 29
5.1.4 Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.1.5 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.1.6 Constant Literals . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.1.7 Let Declarations . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.1.8 Recursive Lets . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.1.9 Intrinsic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2.2 Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2.3 Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2.4 Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3 Foreign Function Interfaces . . . . . . . . . . . . . . . . . . . . . . . 42
5.3.1 Type Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3.2 Miking Externals . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.3.3 Runtime Targets . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.3.4 Browser API . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.4 Tail-Call Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.4.2 Trampolining . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.4.3 Fundamental Translation . . . . . . . . . . . . . . . . . . . . 51
5.4.4 Translation of Non-recursive Callers . . . . . . . . . . . . . . 53
5.4.5 Translation of Recursive Function Chains . . . . . . . . . . . 54
5.4.6 Translation Example . . . . . . . . . . . . . . . . . . . . . . 56
5.5 Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
vi
5.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.5.2 Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.5.3 Readability, Soundness and Correctness . . . . . . . . . . . 59
6 Evaluation 61
6.1 Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.2 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.3 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.3.1 Compiler Coverage . . . . . . . . . . . . . . . . . . . . . . . 63
6.3.2 Runtime Disparity . . . . . . . . . . . . . . . . . . . . . . . . 63
6.4 Performance Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . 64
6.4.1 Motivation of Benchmark Suite . . . . . . . . . . . . . . . . 65
6.4.2 Benchmark Results . . . . . . . . . . . . . . . . . . . . . . . 66
6.4.3 Code Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.4.4 Statistical Result . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.4.5 Hardware and Environment . . . . . . . . . . . . . . . . . . 68
7 Conclusion 69
7.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.1.1 Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.1.2 Foreign Function Interface . . . . . . . . . . . . . . . . . . . 70
7.1.3 Bootstrapping in JavaScript . . . . . . . . . . . . . . . . . . 70
7.2 Final Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
References 73
vii
List of Abbreviations
The following table describes the meaning of various abbreviations and acronyms
used through out this report, along with each page it is first defined and used.
Abbreviation Meaning Page

API Application Programming Interface 3
AST Abstract Syntax Tree 15
CFS Control Flow Structure (statement or expression) 10
CLI Command Line Interface 17
DOM Document Object Model 3
DSL Domain-Specific Language 1
ES6 ECMAScript specification released 2015 (version 6) 15
FFI Foreign Function Interface 3
HTML Hyper-Text Markup Language 7
IP Intellectual Property 5
IR Intermediate Representation 6
JS JavaScript, a high-level language that conforms to ECMAScript 2
JSExpr JavaScript Expression AST node 10
JSON JavaScript Object Notation 31
JIT Just-In-Time compilation 2
MCore Miking Core language 1
MExpr Miking Expression language 1
ML Meta Language 1
OSS Open-Source Software 5
TCO Tail Call Optimization 3
VM Viritual Machine 54
WASM WebAssembly 2
WBS Work Breakdown Structure 9
viii
List of Program Code
1 Variable declaration and initialization . . . . . . . . . . . . . . . . . 20
2 Allocating and freeing data . . . . . . . . . . . . . . . . . . . . . . . 20
3 Different types of functions . . . . . . . . . . . . . . . . . . . . . . . 21
4 Currying in Miking using nested lambdas . . . . . . . . . . . . . . . 21
5 Translation of 4 to curried JS arrow functions . . . . . . . . . . . . 21
6 Ternary operator in lambda . . . . . . . . . . . . . . . . . . . . . . . 22
7 Spread operator in objects . . . . . . . . . . . . . . . . . . . . . . . 22
8 Split string into list of characters . . . . . . . . . . . . . . . . . . . . 23
9 Function arguments with rest operator . . . . . . . . . . . . . . . . 23
10 List destructuring assignment . . . . . . . . . . . . . . . . . . . . . 23
11 Examples of destructuring assignments . . . . . . . . . . . . . . . . 24
12 Destructuring assignment separated from declaration . . . . . . . . 24
13 Destructuring assignment as control flow condition . . . . . . . . . 24
14 MExpr to JavaScript Compiler Language Fragment . . . . . . . . . 27
15 Format of the compileMExpr Semantic Function . . . . . . . . . . . 27
16 Compilation of TmVar . . . . . . . . . . . . . . . . . . . . . . . . . . 28
17 Example of lambdas in Miking . . . . . . . . . . . . . . . . . . . . . 28
18 Example of translated lambdas in JS . . . . . . . . . . . . . . . . . . 28
19 Compilation of TmLam . . . . . . . . . . . . . . . . . . . . . . . . . . 29
20 Folding curried function applications . . . . . . . . . . . . . . . . . 29
21 Compilation of TmApp . . . . . . . . . . . . . . . . . . . . . . . . . . 30
22 Example of records in Miking . . . . . . . . . . . . . . . . . . . . . . 30
23 Example of 22 using objects in JavaScript . . . . . . . . . . . . . . . 31
24 Compilation of TmRecord . . . . . . . . . . . . . . . . . . . . . . . . 31
25 Compilation of TmSeq . . . . . . . . . . . . . . . . . . . . . . . . . . 32
26 Compilation of TmConst . . . . . . . . . . . . . . . . . . . . . . . . . 32
27 Compilation of TmLet . . . . . . . . . . . . . . . . . . . . . . . . . . 33
28 Compilation of TmRecLets . . . . . . . . . . . . . . . . . . . . . . . . 34
29 Compilation of operators in compileMConst . . . . . . . . . . . . . . 35
30 Compilation of TmMatch . . . . . . . . . . . . . . . . . . . . . . . . . 37
31 Some Pattern Compilations . . . . . . . . . . . . . . . . . . . . . . . 38
32 Single Pattern Compilations . . . . . . . . . . . . . . . . . . . . . . 39
33 Safe Compilation of Single Patterns . . . . . . . . . . . . . . . . . . 40
34 Some Expression Optimizations . . . . . . . . . . . . . . . . . . . . 41
35 Example of External Function Interfaces . . . . . . . . . . . . . . . 44
ix
36 Node.js intrinsic header . . . . . . . . . . . . . . . . . . . . . . . . . 45
37 Browser FFI API subset . . . . . . . . . . . . . . . . . . . . . . . . . 46
38 Trampoline Functions in JavaScript . . . . . . . . . . . . . . . . . . 49
39 Example of a Trampolined Function in JavaScript . . . . . . . . . . 50
40 Factorial implementation in Miking . . . . . . . . . . . . . . . . . . 52
41 Factorial translated to JavaScript . . . . . . . . . . . . . . . . . . . 52
42 Mutual Recursive Functions in Miking . . . . . . . . . . . . . . . . . 54
43 Mutual Recursive Functions compiled to JavaScript . . . . . . . . . 56
44 Example sum function in Miking . . . . . . . . . . . . . . . . . . . . 57
45 Example sum function compiled to JavaScript . . . . . . . . . . . . . 58
46 Example code in Miking . . . . . . . . . . . . . . . . . . . . . . . . . 59
47 Compiled example code in JavaScript . . . . . . . . . . . . . . . . . 59
48 Sample Factorial Benchmark Run . . . . . . . . . . . . . . . . . . . 64
x
1 Introduction
In this chapter, a background to the area of research is presented together with
the underlying motivation of the work. Likewise, the objective, purpose and goal
is described.
1.1 Background
This degree thesis takes place in collaboration with David Broman’s research team
for the Miking project. Miking is a framework for building and developing new
domain-specific (DSL) and general-purpose programming languages. Languages
are made up of fragments that enable a rapid development process that also
guarantees soundness and safety [10].
The Miking framework and language workbench will be capable of producing

efficient and sound language environments targeting heterogeneous execution
platforms when released. This includes DSL-specific editors, compilers, test
environments, debugging, and various syntactic and semantic services [10]. The
focus of this report is on compiler targets. This is the vision for the framework
currently under development. The current status of the project can be found on
the Miking GitHub repository [55].
The Miking framework is based on a core functional meta language, Miking

Core (MCore) influenced by ML [57]. Meta-languages are used ubiquitously
throughout computer science and programming languages. They are mostly used
to make statements regarding other languages [52, 53], or, in the case of Miking, to
design, compose, and construct new domain-specific languages [10, 57, 70] from
language fragments. To compile such meta-language programs, the core language
gets lowered to the more fundamental functional Miking Expression language
(MExpr). This is the source language this thesis will aim to translate and compile
to JavaScript.
1
1.2 Motivation
Currently, the Miking framework has a compiler with support for generating
OCaml and C source code. In contrast to the two systems programming languages,
JavaScript (JS) is a high-level, dynamic programming language. JavaScript
was first designed and developed in 1997 [31] and has been improved on ever
since. The technology has been driven by modern web engines and runtime
environments, such as Google’s V8 engine [80] that powers browsers and the
Node.js runtime [59]. These developments have led to the introduction of a
just-in-time (JIT) compilation, which had a tremendous impact in terms of
performance. It is said that “sequential JavaScript is within a factor of 2 of native
code” [45]. This makes JavaScript a serious compilation target alternative for
modern programming languages.
Due to the growth of browser-based applications, JavaScript is used everywhere

to run anything from interactive websites to desktop apps. This implies that the
language will continue to be used for a long time. That is why many languages
and hobby developers build tools to transpile different types of modern languages,
called “compile-to-JavaScript” languages. These are using JavaScript as an
”assembly language” similar to how compilers use to target assembly for lowering
[39]. Those languages allow programmers to use other languages than JavaScript
to develop applications for browser-based web clients [2, 25, 32, 50, 51, 82].
A recent trend among modern programming languages is hosting online

playgrounds for promoting the language, quick testing and as an easy introduction
to potential new users [19, 63, 77, 78]. These integrated online development
environments often use a bootstrapped version of the actual compiler running in
JavaScript or WebAssembly (WASM) [6, 83, 85]. Providing an easy way for new
developers to get started can be very helpful to gain popularity, and emphasizes
on the importance of supporting modern (web) technologies, helping it expand
the language domain of usage [77].
Miking wants to meet the same standard as the languages discussed above. With
the same goal, of supporting cross-compilation towards the web. Thus enabling
developers to get more out of the language itself. These advances in the Miking
project would help new potential users quickly get started through an online
playground.
2
1.3 Objective
Thanks to the support for compilation to other languages, there already exist
compiler back-end implementations in Miking that can be used for inspiration
and to expand upon. The compilation, optimization, and code generation passes
will therefore follow similar procedures as for the other backends. However, there
are many differences between JavaScript and the other target languages.
The objective of this thesis is to implement compilation support for targeting

different JavaScript execution environment runtimes in the self-hosted Miking
compiler. This implementation must also satisfy a number of requirements.
Mainly, generating code that is effective, readable, sound and correct.
As part of development, the backend should also be able to support basic foreign
function interfaces (FFI). This means that external interfaces used within Miking
programs should be compiled and linked together, enabling external libraries
to access JavaScript-only functionalities working inline in the Miking source
code. Using FFIs allows Miking programs to take advantage of all JavaScript
features, for example, interacting with the browser document object model
(DOM) application programming interface (API) in client-side JavaScript and
building interactive websites. Or, reading and writing to files in the local file
system through the Node.js runtime. This enables an incredible number of new
applications to be built using the Miking framework.
Likewise, pattern matching expressions should be compiled correctly. The last

challenge and objective of this thesis project are to translate and optimize tail
recursive functions of any degree. This compilation process is called tail call
optimization (TCO) and is a major task when compiling functional languages to
lower-level languages.
3
1.4 Purpose
The purpose of this degree project is to contribute to the Miking framework and
research project, and deepen my knowledge in the field of programming languages
and execution environments. This thesis presents the work of building a compiler
backends for web and native runtime environments, and discusses the importance
of the web as a platform for the development of new programming languages and
applications.
1.5 Goal
The desired deliverable is a functional compiler extended with a backend capable
to generate JavaScript target code. It should cover the whole feature set of the
MExpr language, compiling functional constructs such as pattern matching and
tail recursion to use JavaScript features. The generated code should also fulfill the
requirements presented in section 1.3.
1.6 Benefits, Ethics and Sustainability

Social ethics and sustainability is described as the focus on ”actions, attitudes,
beliefs, cultural traditions, and decisions that an individual makes“ to line up with
a group identity [81]. This thesis project is conducted in the Miking Research
Group, led by professor David Broman. The decisions mentioned above are
relevant to discuss in the context of being a productive member of this new group.
I feel like I have entered the group with a positive and humble attitude, interested
in learning their methods and techniques for project development. I adopted some
cultural traditions such as participation in weekly Miking meetings1 and voted on
things considered beneficial, valuable, reasonable, fair, and just [81].
David Broman and his research project directly benefit from this project work,
contributed code, and thesis report, followed by potential future users of the
Miking framework. Since the research project is open source (OSS), all the source
code produced is contributed to the benefit of project development. It is important
to responsibly write the code and credit any code borrowed for sustainable
development [37]. Program source code is deemed intellectual property (IP) and
is protected by law against copying, theft, or other use that the owner does not
1
View the Miking meeting protocol notes from 2022 here: https://github.com/miking-
lang/miking/wiki/Miking-Meeting-Notes-2022.
4
allow [37]. Permits can be granted through licensing agreements to allow certain
use and distribution of code.
1.7 Delimitations
Both time and theoretical knowledge is a limitation for this project. I have no
formal education in compilers and execution environments or computational
theory, but mostly practical knowledge. Therefore, reading research papers on the
subject has been challenging due to lack of complete understanding of operational
semantics, inference rules, code generation techniques, program optimizations
and advanced terminology in programming language theory. Therefore, self-
education and research in the field was the biggest obstacle during the course of
the project.
The delimitations therefore become a non-formal report with documentation for

how the generation of source code in the target language works explained in basic
terms. Furthermore, code, methods and results are still presented and discussed
in the report in a way that enables later development.
Manual implementation of any optimization passes are also be excluded from the
project, as there is no time to focus on that part because the goal is to generate
JavaScript code in the main. Thereafter, this can be achieved by using tool chains
along the course of work as mentioned previously.
5
2 Theoretical Background
This chapter is about the theoretical research made before and during the thesis
project work. A detailed description about background of the degree project is
presented together with related work.
2.1 Related Work

Before and during the main project work effort, research on previously conducted
projects with related work was made to gain a better understanding of the task an
build up a theoretical background for the thesis.
2.1.1 SMLtoJs: Hosting a Standard ML Compiler in a Web

Browser
This paper presents an optimizing compiler from Standard ML to JavaScript

for support in web browsers. It also shows that the SMLtoJs compiler can be
bootstrapped and compiled by itself to run in the browser. The non-aware
front end aspect is very suitable for this project, as Miking is also a multi-
target compiler. Another fitting detail is how SMLtoJs supports a level of foreign
function interface (FFI) to interact with native web-based JavaScript such as the
DOM API. This is in alignment with one of this thesis goals, of mapping native
Miking built-ins and correctly handling FFI API:s to JavaScript. This was done
through implementing a JsCore semi-type-safe module in the base language.
This is an implementation approach of native APIs is useful for Miking as well,
because OCaml and Standard ML are similar functional languages in many ways
[32].
2.1.2 St Andrews Algol to JavaScript compiler project
The St Andrews Algol to JavaScript compiler project describes the design and
implementation of a compiler that accepts S-algol programs and translates them
into JavaScript [77]. He also describes the lexical analyzer and parser passes in his
thesis, but are irrelevant to this project as Miking already has a compiler frontend.
The interesting parts of the S-Algol to JS project are the static analysis stages, code
generation, and lowering methods.
6
2.1.3 From bytecode to JavaScript: the Js_of_ocaml compiler
The js_of_ocaml project implements an OCaml bytecode to the JavaScript

compiler targeting environments such as browsers and Node.js. General tail call
optimization has not been implemented, and the compiler is limited to optimizing
tail calls to direct recursive function calls. Mutually recursive functions are also
optimized, but using trampolines. This is a technique described further in the
research themes section 2.1.6. The project also suggests a solution for further
optimization improvements of tail calls by performing function specialization and
better inlining [42, 71, 82].
2.1.4 Hop Client-Side Compilation
Hop is a language that “aims to replace HTML, JavaScript, and server-side

scripting languages” by building on top of Scheme programs and using their
custom designed compiler Scm2Js to create a Hop execution platform. One
interesting part of the paper is the function compilation section. There they talk
about how “all important JavaScript interpreters are known not to perform tail
call optimization”, and the compiler must therefore handle tail calls by performing
loop optimization pass transforms to convert recursive tail calls into loops [51]. A
deeper dive into the technical process is described in their other paper “Compiling
Scheme to JavaScript” where they again mentions that a direct mapping from
Scheme to JavaScript is impossible due to lack of support for tail-recursive
functions in JavaScript [50].
2.1.5 A Compiler from CakeML to JavaScript
This master thesis report presents a complete source-to-source compiler from

the functional programming language CakeML to JavaScript. CakeML is based
on the Standard ML language [70] also mentioned in chapter 2.1.1 [60] about
the SMLtoJs compiler project. It also introduces formal semantics for a subset
of the ECMAScript 2015 standard, similar to what is used as a target for the
Miking backend in this thesis. The new CakeML compiler enables programs to
be executed in the web browser on desktop and mobile devices, which is a context
not previously available for CakeML code [60]. The vast differences between the
languages and the lack of officially documented formal semantics for JavaScript
are brought up in the report, underlining important similarities such as both
having support for higher-order or first-class functions.
7
2.1.6 Research Themes
Common research themes and challenges that emerged from previous reviews
are often concerning different types of compiler optimizations, foreign function
interfaces, and wrapping of native JavaScript APIs. These are all important to
take inspiration from when implementing the backend for the Miking compiler.
Mostly, the primary challenge is to correctly transform recursive tail calls. This is
an important aspect to reflect upon for this thesis project, as, similar to Miking,
functional languages continuously utilize tail calls and recursion. This becomes
a problem, as JavaScript does not perform any tail call optimization [27], thus a
direct translation from a functional language would cause stack overflows. The
proposed solutions for the SMLtoJs, js_of_ocaml and Scm2Js projects was to
compile self-recursive functions to while loops using the JavaScript continue
statement, or using a technique called trampolining.
The trampoline technique is a concept where the recursive function gets controlled
by an outer function, that is, calling it repeatedly as well as preventing self-
recursion. Therefore, each time the inner function calls another function, it
instead returns the inner function identity as a closure to the outer trampoline
function, which in turn makes the call. This prevents unlimited stack growth, but
due to the extra amount of function calls, some performance is lost [67, 72].
There are several issues with transforming recursive function calls, as there is
a whole class of tail calls that cannot be optimized by the previously described
techniques. Most of the implementations of previous research focus only on
straight tail calls. “A straight tail call is a recursive call to the nearest enclosing
function such that the call does not appear under another function abstraction”
[32]. This essentially means that a “straight tail call” is a call inside a function
body referring directly to the function itself.
8
2.2 Functional and Imperative Recursion
An important detail when examining the two languages within the early studies
is that functional languages such as Miking often make use of recursive functions
to iterate when imperative languages such as JavaScript use while and for loops.
The main difference is that a recursive function call produces a new stack frame
unless they have optimized this feature. This concept was discussed more in-depth
previously in chapter 2.1.6.
JavaScript, for example, does not optimize recursive tail calls; hence, a naive
translation from Miking to JavaScript would produce code that crashes due to
exceeding the maximum recursion depth and throws a ”maximum call stack size
exceeded” exception. JavaScript associates exactly one execution context with
every function call, containing all bound variables and their values for the call
instance up to that point and stores it on a call stack [29]. When a function calls
itself or another function, the current function is paused, and a new execution
context is created for the next call. After executing the call to the nested function,
the old execution context is fetched from the execution call stack, and the outer
function resumes from where it stopped.
9
3 Methodology
This chapter describes both the research and engineering methodologies and
methods used in this degree project. The research methods specify how the
implementation correctness can be justified using an empirical study. The
engineering part discusses and presents different models and methods on how
this project was conducted, to prove that this thesis follows accepted software
development processes and methods using different modeling tools.
3.1 Research Method

The purpose of this thesis is to extend the existing Miking compiler to support
JavaScript compilation from its intermediate MExpr language using a deductive
approach. Therefore, existing research and theory is used to build a product and
hypotheses that it is correct, and then testing it empirically [88]. This is done by
running unit tests in the compiler and benchmarking the generated JavaScript
source code. Measurement and comparison of execution time against other
Miking supported target languages, and an optimized version of the generated
code using the Google Closure Compiler [15].
Another aspect is to compare the results based on the set requirements:

effectiveness, readability, soundness and correctness. To test how readable and
sound the produced code is, we discuss how different the code is from an ideal
solution in terms of what constructs are used, formatting and clutter. Lastly,
the compiler should handle and compile FFIs, pattern matching, and performing
TCO on all forms of tail recursive functions. This plays an important role in the
efficiency and correctness of the implementation.
3.2 Software Engineering Process

In the last decade, computers and software have massively grown in popularity
and demand, setting high expectations followed by accepted standards. Almost
all modern systems include software in some way; such as transportation, finance,
education, healthcare and so on. Along with this increase comes corresponding
methods, models, tools and metrics useful for software engineering [68]. To
conduct a successful software development project, one must utilise the relevant
methods, tools and processes as much as possible. Such methods suggest a rigid
structure on the software development activities, ultimately making the activity
10
more likely to be successful. However, the difficulty is stay up to date of recent
technical software engineering tools and methods, as specifications and practices
are altered regularly [13].
3.2.1 Project Plan
A project time plan is important for any project, and a Gantt chart was used
for time management and scheduling for this degree project. Gantt charts are
useful when planning projects in relation to time and dates. Activities are
often represented as bar segments with different lengths based on the estimated
duration to complete the work. Each segment is also show the dependencies and
relations between different activities [34]. Because deadlines and important dates
are marked in the chart, it is easy to get an estimate of the current status of the
project.
Construction of
JavaScript Backend
Research Design Implementation Evaluation
Compile MExpr3
Study Miking language Study existing backends Benchmark performance
constructs to JSExpr4
Supported ECMAScript Convert constants to

Related work Compare effectiveness
specification version curried JavaScript intrinsic
Compile pattern matching

Compilation methods Supported target platforms2 Validate correctness
to deconstructions in CFS5
Transformative
Tail call optimization Construct translations Assess readability
optimizations on JSExpr
Printing generated
Pattern matching Run compiler test suite
JavaScript source code
Figure 3.1: Work Breakdown Structure
2
Generic JavaScript (platform independent), Web browser environment and Node.js runtime.
3
The parsed AST from the Miking compiler frontend.
4
The generated AST by the JavaScript backend in the Miking compiler, transformed upon and
lastly pretty printed.
5
Control Flow Statement or Expressions, such as if-else statements or ternary expressions
(cond ? e1 : e2).
11
The project plan is used to describe how the development is intended to be
carried out, stages of work, processes, deadlines, and resources [68]. To further
visualize and organize the main phases and all partial steps of the process, a
Work Breakdown Structure (WBS) diagram (see Figure 3.1) was created. A WBS
diagram intends to summarize both scopes, cost (briefly), and schedule in a
comprehensible format to improve project management and systems engineering
[86, 87].
3.3 Testing and Validation

In this chapter, the methods and techniques for testing and validation of the final
implementation are described. This is an in-depth extension of previous chapters
and research methods for this degree project with respect to the evaluation of the
result.
3.3.1 Unit Testing
Unit tests are performed on small pieces of code individually. This is a very
common test in software development and is used to test the accuracy of each
segment of a program. To improve the quality of software development and
production, automatic testing and code coverage can be used. The benefits of
unit testing are among others; it helps to identify bugs in the code, and it helps
to identify the areas of the code that need to be improved.
In this case, the unit tests make up parts of the code implemented in the compiler
backend. Together, the unit tests verify the implementation of the compiler.
An important distinction is that unit tests do not prove the correctness of the
compiler and its output, but they do prove the correctness of the compiler’s
internal implementation.
The unit testing plan for the backend development is to extract functionality that
is often reused into abstract functions with the goal of moving towards modular
compiler design. Each function should therefore ideally perform some pure
atomic task, which is tested at the bottom of the program file with a set of different
parameters and expected results. This is not different from what is currently done
in the Miking compiler.
The Miking core language provides built-in functionality for integrated unit tests
through the utest keyword. This is going to be used when developing the backend
and test vital parts of the compiler.
12
3.3.2 Benchmarking
A useful tool for comparing the performance of code generated by the compiler
backend with idiomatic JavaScript, is by running a suite of benchmarks. By using
this method, we can measure the performance of our code compared to a manual
implementation of a corresponding program, with hand-tuned optimizations.
This is a quantitative approach which requires programs to use a wide range
of features from the Miking language for the whole suite to be effective and
give accurate results. By comparing hand-tuned JavaScript code against that
generated by the compiler, we can estimate the efficiency and correctness of
the implemented compiler backend. This achieves some verification of the
correctness of the compiler itself in turn and increases the credibility of the overall
backend implementation.
Benchmark runtimes are collected, normalized over multiple runs, visualized

and analyzed. An important to distinguish between execution in a fresh and
cold-started environment, versus code that has been run several times. For
JIT-compiled environments, benchmark results can be drastically affected by
repeated calculations being replaced with native code or caching results, leading
to minimized or close to constant execution time.
It’s also interesting to see how closely the performance of highly optimized
and simplified versions of the JavaScript programs compiled compares with the
manual implementations. Generated programs will therefore be optimized using
the Google Closure Compiler [15], measured and compared against manual code
as well as the original JavaScript program compiled by the backend.
13
3.3.3 Partial Bootstrapping
To prove the correctness of the implemented compiler backend, the largest and
most complex software written in Miking would need to be written and compiled
to JavaScript, and asserting the two programs have equivalent functionality
and behaviour. The optimal way to prove and verify the correctness of the
implementation would therefore be to compile the entire compiler to JavaScript
through the developed backend (as it is currently the largest program written
in Miking). However, this is currently not possible due to dependencies on the
OCaml language through an external parser in the Miking compiler. What is
possible, on the other hand, is to compile the Miking compiler piece by piece for
those files that do not depend on external functions. Therefore, the plan is to
support only partial bootstrapping as reasonable proof to increase the confidence
of the compiler correctness.
14
4 Design
This chapter introduces the design of the existing compiler frontend along with
the backend to be implemented.
In Miking, code is written and structured in a certain way using semantic language
fragment composition, enhancing the implementation soundness from a compiler
construction perspective. Due to a large amount of historic JavaScript engines, the
ECMAScript 262 standardization of the JavaScript language exists. This standard
specifies the formal semantics and official implementation documentation [26,
28, 31, 36]. The design presented in the following chapter will therefore take
these semantic specifications into account. Overall, the design follows the general
structure of regular compiler passes and stages.
4.1 Pipeline Overview

A function model with a logical view of the compiler architecture and expected
component relations is presented in chapter 4.1.2. Given the overview of the
structure, the data flow diagram in Figure 4.1 can be constructed. It place
the model in Figure 4.2 into the context of the whole compiler, and shows the
stages of the compilation process as well as each type of data passed between the
stages.
Input Source code List of tokens MExpr AST

Lexer Parser Type Checker
Miking File
Checked
MExpr AST
Compile MExpr Generate

Pretty Print
JSExpr AST to JSExpr MExpr AST uTest Runner
with uTests
Generated JS source
Output JS source Third-Party

JavaScript File JS Optimizer
Figure 4.1: Code Flow of Compilation Process
The diagram in Figure 4.1 represents external interactions with yellow rounded
rectangles and illustrates transformations of some sort with blue rectangles. The
green dashed rectangles show what parts of the compiler that has been developed
and contributed to in this degree project. They also represent source code data
transformations detailed by the labeled arrows. Finally, the red dashed rectangle
15
represents an optional external component that is not part of the compiler
system.
Figure 4.1 is massively simplified as it only displays the small segment relevant
to this thesis. The Miking compiler has many other features such as a stage for
lowering MLang to MExpr, dead code elimination, symbolizing, etc.
4.1.1 Frontend
In the diagram above visualize the inner pipeline of the Miking compiler, where
the source code is initially passed as input to the Lexer. The lexical analyzer
transforms the input text into a sequence of tokens. A token is the smallest
meaningful part of the source code in a language.
The tokenized sequence is then passed to Parser, which collects tokens that
together have some meaning in an abstract syntax tree (AST). This could be
compared to the way natural language is composed of phonemes that follow
rules and grammar to create sentence structures. Different phrases in a sentence
have different meanings, as in programming languages. Therefore, the AST
is a tree representation of language constructs. MExpr is the type for Miking
expression nodes, and similarly, JSExpr represents the base type for all JavaScript
nodes.
Computers do not have the same intuition for languages as humans; this is
the reason why many programming languages require additional information in
terms of types. This can be explained as an “underlying meaning” that humans can
intuitively associate with, but computers can not. Therefore, the Type Checker
validates that the additional information added by the programmer agrees with
the actual semantics of the input program. The programmer can also let the
compiler figure out the type signatures of variables and lambdas itself; this
is called type inference and is combined with user-defined types during type
checking. This is also one of the more recent features fully supported in the Miking
compiler.
Miking has built-in constructs for performing unit tests, as well as a custom test
runner suite part of the core language. There is an optional flag in the command-
line interface (CLI) to enable unit tests for the compiled file, thus inserting lowered
and transformed unit tests into the AST.
16
4.1.2 Backend
Because the Miking compiler already has an existing frontend, these parts will
not be covered further in this thesis. On the other hand, the design and
implementation for all passes that follow until a final program is generated
will be presented. The stage after a program has been parsed is called the
compiler backend. In Figure 4.1, the backend is represented as green dashed
rectangles.
The compiler from MExpr to JSExpr computes a transformed equivalent internal

representation of the Miking expression AST node for the target language. This
is the main component implemented in this degree project. After the MExpr to
JSExpr is complete, the resulting JSExpr AST is passed to a pretty printer that
emits formatted source code in the correct syntax for the target language. The
target JS platform can be specified through the CLI, and dictates which FFI
intrinsics should be added to the generated JavaScript source code. The focus for
the degree project excludes any subsequent events after the created code is saved
to a file. The red dashed rectangle in Figure 4.1, therefore, represents a suggested
optional interaction with a third-party optimization toolchain such as the Google
Closure Compiler [15, 16, 35].
Nested
Constructs
Parsed Final Generated

Compiler MExpr MExpr to JS JSExpr Pretty Source Code Output
Frontend AST Transformer Printer JS File
JS AST Platform
Optimizations Intrinsic
MExpr Match
Construct
Compiler JS
Pattern Transformer Optimizing Transformer Backend
Figure 4.2: Functional Model of Compilation Process
The model above (Figure 4.2) takes on a functional modeling perspective

concentrating on describing the dynamic process [33] of compilation from Miking
expressions to JavaScript. This is a logical view of the system in development
[46]. The green circles represent an external data collection store for fetching
different kinds of material used in the process. The blue rectangles illustrate
17
transformations of an input MExpr to an output JSExpr, and the last transformer
generates pretty printed JavaScript source code based on the final JSExpr. The
yellow rounded rectangles signify an external interaction.
The backend in Figure 4.1 has been greatly simplified to better fit the overall
pipeline. To visually describe the desired result for the project, a functional model
[68] and general data flow diagram for source code is used to conceptualize the
procedure of compiling a Miking program to JavaScript (see Figure 4.2). This
helps to put the task into a concrete perspective and is helpful in explaining the
concept to team members and stakeholders. It can give further context to the main
phases presented in the WBS chart (see Figure 3.1). In software engineering, a
function model is a structural representation of the set of functions in a system
[33].
18
4.2 ECMAScript 2015 Support
We choose to target the ECMAScript 2015 (also known as ES6) edition of
JavaScript [28]. This version is also labeled as the Harmony specification [29, 30,
41] and is a project to “unify the committee around shared values and a common
roadmap”. It features concepts such as anonymous functions, arrow functions
(lambda expressions), spread operator, lexical block scoping using let, const,
and destructuring assignments. The complete formal semantics for the language
is defined in the official specification [28].
Currently, many modern browsers have full feature support for the latest version
of ECMAScript. Therefore, there are no direct negative consequences of targeting
an older version of ECMAScript (2015). Apart from browser environments,
Node.js is the main priority target of all native JavaScript runtimes. This also
supports ES6 out of the box, as Node.js is built on the modern V86 JavaScript
engine, which fully supports ECMAScript 2021, thus guaranteeing support for ES6
[58].
All ECMAScript specifications are strictly backward compatible, allowing

developers to write code without fearing any breaking changes in the language.
This means that all versions of ECMAScript syntax and semantics are subsets
of the previous ones, making for example the latest version of ECMAScript also
support all features specified in ES6.
Although the most recent version of ECMAScript would be tempting to target, it

is wise to support an older version due to implementation differences between
JavaScript engines for different browsers [1, 29]. Thus, all the latest features
might not be correctly implemented yet. Currently, Safari is the only modern
browser with support for TCO7 for example. This is also the reason why the
“compile-to-JavaScript” languages need to handle TCO transforms beforehand.
There is a section in the ES6 specification mentioning tail position calls8 .
By utilizing the features provided by the ES6 version of JavaScript, it is possible to

generate more expressive, effective, concise, and readable code from the Miking
compiler and better meet project requirements than for previous specifications.
ES6 makes it easier to write functional code in a syntactically similar manner to
Miking programs.
6
V8 is Google’s open-source high-performance JavaScript and WebAssembly engine [80]
7
Browser compatibility table filtered by support of tail call optimization:
https://kangax.github.io/compat-table/es6
8
Tail position calls: https://262.ecma-international.org/6.0
19
4.3 ES6 Features and Translations
This chapter covers the feature subset that is used in the compiler for this degree
project, together with examples of translated Miking code in JS.
4.3.1 Variable Declaration
Variables in ES6 can be declared using either of the following keywords var, let
or const, see code 1. The new declaration methods are let and const, they behave
similarly to variable declarations in other languages, whereas the old var does not.
The main difference is that var is bound to the nearest function scope, otherwise
the global scope. This means that a variable declared using var in a block is
accessible and mutable from outside that block. This is not the case for let, it
is always bound to the current scope and does not leak outside its closure.
For this project, the code is generated using let and const variable declarations
due to their predictable behavior.
1 var a = 1; // Mutable, nearest global or function scope

2 let b = 2; // Mutable, block scope
3 const c = 3; // Immutable, block scope
Program code 1: Variable declaration and initialization
The new const keyword specify an immutable reference, meaning the ”pointer”
cannot be moved. This improves memory performance as the garbage collector
always know that the value cannot change or be manually deleted. This is possible
when using mutable variables by setting its value to null, forcing the previously
allocated structure to get garbage collected, see code 2. const share the same
declaration scope binding rules as let. When using the new let and const
keywords, all variable bindings in a function body gets automatically garbage
collected as soon as the function is done executing and goes out of scope (returns).
This improves memory efficiency in comparison to var, that kept references to
previously allocated data.
1 let lst = [1, 2, 3]; // Allocated list

2 lst = null; // Free the list
Program code 2: Allocating and freeing data
20
4.3.2 Arrow Functions
JavaScript provides lambda expressions called arrow functions. A modern

alternative to the previous technique with anonymous functions, see the code 3.
The main difference is that arrow functions do not have a local this reference as
regular (or anonymous) functions do. This is because functions are considered
objects in JavaScript. This is not the case for arrow functions (or lambda
expressions).
Another difference is that arrow functions support either a single expression

or a block, while an anonymous function always requires a block. This is
better when compiling from a functional language where almost all values are
expressions.
1 function a(x) { return x; } // Named function

2 let b = function(x) { return x; }; // Anonymous function
3 let c = x => x; // Arrow function
Program code 3: Different types of functions
By using lambdas, we can reduce code clutter and generate more expressive
and readable code. All ”functions” in Miking are lambda expressions with only
a single parameter, thus passing multiple values to a function is done through
nested lambdas. This technique is called currying and originates from lambda
calculus and provide a way to study functions with multiple arguments using
simple models [20].
The examples below illustrates how a function with multiple arguments (code 4)
can be compiled to JavaScript using nested arrow functions (code 5).
1 let f = lam x. lam y. x + y in

2 print f 14 38
Program code 4: Currying in Miking using nested lambdas
1 let f = x => y => x + y;

2 console.log(f(14)(38));
Program code 5: Translation of 4 to curried JS arrow functions
21
4.3.3 Ternary Operators
This is an old feature introduced in the first version of ECMAScript 1997, together
with var [31]. Nevertheless, this is a useful feature because it allows for control
flow in an expression format, see code 6. Other CFS constructs such as if-else
doesn’t return a value, and when compiling from a functional language where
everything is an expression, the ternary operator comes in handy.
1 let x = 10;
2 let y = z => z < x ? "less" : "more";
3 console.log(y(5)) // "less"
Program code 6: Ternary operator in lambda
By using ternary expressions in places where a return value is dependent on

some condition, code complexity can be reduce large chunks combined into one
expression. This feature is directly applicable for compilation of pattern matching
constructs in Miking.
4.3.4 Rest & Spread Operators
The rest and spread operator is used when working with iterative data structures,
such as lists, objects and strings [69]. The spread operator lets us insert
elements or key-value pairs into lists, objects and function calls by expanding and
extracting the remaining values from the original collection data structure, see
example 7.
1 let a = {x: 5, y: 10}

2 let b = {y: 8, ...a} // Spread the pairs of a into b
3 let c = [1, 2, 3, 4, 5]
4 let d = [0, ...c, 6] // Insert the elements of c into d
5 console.log(b) // { x: 5, y: 8 }
6 console.log(d) // [0, 1, 2, 3, 4, 5, 6]
7 console.log(...d) // 0 1 2 3 4 5 6
Program code 7: Spread operator in objects
This method could be used for tricks like splitting a string into a list of characters,
see example 8.
22
1 [..."Hello, world!"]
2 // ['H', 'e', 'l', 'l', 'o', ',', ' ', 'w', 'o', 'r', 'l', 'd', '!']
Program code 8: Split string into list of characters
The rest operator looks exactly like the spread operator, but has in some send
a very opposite behaviour. The spread operator expands the contents of some
collection data structure, while the rest operator collects a set of elements into
a single ”condense” value [69]. It is used in pattern expressions, for example
function parameter lists can collect elements outside of named ones, see code
9.
1 function myFunc(first, second, ...rest) {

2 console.log(first, second, rest);
3 }
4 myFunc(2, 4, 8, 16, 32) // 2 4 [8, 16, 32]
Program code 9: Function arguments with rest operator
It can also be used in destructuring assignment to match all elements after a

number of named ones, see code 10.
1 let [a, b, ...rest] = [1, 2, 3, 4, 5, 6]

2 console.log(a, b, rest) // 1 2 [3, 4, 5, 6]
Program code 10: List destructuring assignment
This feature is directly applicable in pattern matching compilation.
23
4.3.5 Destructuring Assignment
Using the rest and spread operators, destructured assignments can be very
powerful and simulate certain pattern matching capabilities [65], see example
11.
1 let a = 1; // Named pattern, always matches

2 let {b} = {b: 2} // Extract property from object
3 let [c, d] = [3, 4, 5] // Extract first two elements from list
4 let {e: {f: x}} = {e: {f: 6}, g: 7} // Extract nested property
5 let [h, ...rest] = [8, 9, 10] // Extract the first element
6 // and save remaining to rest
Program code 11: Examples of destructuring assignments
Destructing assignments are essentially a method to extract data from an Object

by matching a value against a certain pattern. This feature provides a limited
alternative for performing pattern matching in comparison to more powerful
implementations in other languages. It is also possible to assign variable values
with destructuring separate from its declaration [23], see code 12.
1 let a, b;
2 ({a, b} = {a: 1, b: 2});
Program code 12: Destructuring assignment separated from declaration
Notice the surrounding parentheses around the assignment. They are required
when using object literal destructuring assignment without a declaration [23], see
code example 12. This is important when using destructuring for simple pattern
matching, see example 13.
1 let o = {a: 1, b: 2, c: 3}
2 if ({a, b, ...rest} = o) console.log(a, b, rest)
3 else throw "Not an object"
Program code 13: Destructuring assignment as control flow condition
24
The example in program code 13 does not pre-define the destructured variables a,
b and rest on line 2. This syntax is only accepted by some JavaScript runtimes,
such as Node.js [59], but not Deno and Bun [9, 11] by default. To run some
equivalent code in those runtimes, a variable declaration is always required before
an assignment to a variable in a pattern. Hence, we need to first define the
variables in Figure 13 using let a, b, rest.
Investigating deeper into the differences seen between the runtimes previously,
Node.js reports a similar error if the file extension of the Program code 13 would be
.mjs instead. This is because modern Node.js parsers treat .js files as CommonJS
ScriptBody modules, instead of ModuleBody as Deno and Bun do for all JavaScript
files [17, 18]. The ES6 specification describes how files are treated as Program,
which is the previous term before the distinction of scripts and modules was
introduced in later versions of ECMAScript [28, 31].
4.4 Target Platforms

Today, JavaScript runs on multiple platforms through modern browsers and
runtime environments such as Node.js, Deno, and Bun [11, 22, 59]. They enable
systems programming in JavaScript and provide an API to interact with the
underlying operating and file systems. This allows JavaScript to go beyond the
constraints of the web as a language, making it possible to write both the backend
web server and the frontend in JavaScript.
All platforms have full support for ES6, and adding new platforms is simply a
matter of adding custom built intrinsic for that environment. By writing intrinsic
functionality from Miking in JavaScript into separate files, lets up decouple the
compiler and the target platforms much better and helps separation of concerns.
Hence, updating the intrinsic does not necessarily affect the compiler.
The Miking compiler CLI accepts flags to specify any optional platform targets
for the JavaScript backend. This is done by passing the --js-target flag with
either a web, bun, deno or node value, the default target is always generic (platform
independent) JavaScript.
25
5 Implementation
The Miking compiler is self hosted, meaning it has been implemented in the core
Miking language, allowing the compiler to bootstrap itself. This means that all
development for the implementation takes place in the core language as well,
using their testing tools and design patterns. The core language is functional,
meaning regular design patterns doesn’t apply in the same way as for the object
oriented programming paradigm. The main differences between the paradigms
are, higher-order functions, function composition abstractions, immutability and
the fact that types are not classes [38].
Functional languages do not use statements as heavily as imperative and

object oriented languages do, with constructs mostly focusing on working with
expressions and returning values. That is why the MExpr AST only consists
of expression nodes and no statements. In comparison to the C backend in
the Miking compiler, that includes both CStmt and CExpr ASTs [56]. For
this degree project, mostly JavaScript expressions will be supported with
exceptions to variable declarations. The backend will therefore output nodes
from the expression based AST JSExpr, thus simplifying the compilation process
significantly. This can in turn be optimized and refactored further in the future to
convert expression based constructs into JS statements with the same semantic
meaning.
Since the thesis work takes place in a research project with an existing compiler
environment, we don’t need to implement a frontend such as a lexer or parser.
Instead, we only need to connect the backend in the compiler module after
the existing frontend has produced a Miking expression AST data structure. If
the user input a compiler flag indicating the Miking code should be transpiled
into JavaScript, our backend transforms and translates the Miking AST into
the corresponding JavaScript AST form and generates code in the target
language.
26
5.1 Construct Transformations
The fundamental functionality of the compiler backend is the compileMExpr
function. It takes an Miking Expr AST as input and transforms it into an JSExpr
AST. In Miking, these functionalities are part of language fragments (lang) and
represent the semantics (sem) in a language and compiler. The language fragment
for the JavaScript backend uses both the MExprAst and JSProgAST fragments, see
code 14. This is because the AST fragments define different semantics required for
the compiler, one to match (Miking) on and the other to translate to (JS).
1 lang MExprJSCompile = MExprAst + JSProgAst
Program code 14: MExpr to JavaScript Compiler Language Fragment
The semantic compileMExpr function is written on the form seen in the example
15. Semantic functions can take a set of parameters, for this we accept a context
of the type CompileJSContext holding metadata about the current compilation.
The function takes a single expression of a certain type Expr (fundamental Miking
expression AST, also referred to as an MExpr), this is matched against a set
of patterns, or cases (case1 and case2 in example 15). If a case matches a
given expression, the corresponding case branch body will be evaluated and
returned.
1 sem compileMExpr ctx =

2 | case1 -> expr1
3 | case2 -> expr2
4 ...
Program code 15: Format of the compileMExpr Semantic Function
For all of the following chapters, the different construct transformation codes
are formatted in ”case -> body” style. They are also part of the compileMExpr
semantic function branches in the program code example 15. All code examples
will also be simplified to better describe the underlying concepts when compiling
each construct. This simplification is the removal of the context ctx, in
return expressions. Otherwise the type of the compileMExpr would normally
be CompileJSContext -> Expr -> (CompileJSContext, JSExpr), but for the
following compiler implementation examples, the value will just be JSExpr.
27
An example of a construct is a Miking term, prefixed with Tm. The backend also
defines a set of AST node types, often starting with JS followed by for example an
E if it is an expression or O for operators.
5.1.1 Variables
The most fundamental piece of the Miking language is the identifier literal TmVar.
It simply contains a name, which we can simply compile to a JavaScript variable
reference JSEVar by extracting that name, see code 16.
1 TmVar { ident = id } -> JSEVar { id = id }
Program code 16: Compilation of TmVar
The code above matches a MExpr with a TmVar with a field ident (as a case in the
compileMExpr function). The value of ident is then bound to the variable id, and
again passed to a JavaScript AST node JSEVar with the same id.
5.1.2 Lambdas
Lambda functions are the second most fundamental piece of a functional

language. Miking makes heavy use of them in terms of regular let-in, recursive
lets and sem declarations, see code 17. Lambdas start with the lam keyword,
takes one argument and a body expression. The body expression can be a nested
lambda, resulting in a function that takes multiple curried parameters.
1 let add = lam l. lam r. addi l r in

2 add 5 6
Program code 17: Example of lambdas in Miking
The goal is to compile the code example above, 17, into the equivalent curried
JavaScript code using arrow functions below, see code 18. The addi function is an
operation used for integer addition in Miking.
1 let add = l => r => l + r;

2 add(5)(6);
Program code 18: Example of translated lambdas in JS
28
By extracting the parameter and body for a given lambda, we can compile the
MExpr body expression into its corresponding JSExpr value, and construct a new
arrow function expression (JSEFun), see code 19.
1 TmLam { ident = arg, body = body } ->

2 match compileMExpr ctx body with (ctx, body) in
3 JSEFun { params = [arg], body = body }
Program code 19: Compilation of TmLam
5.1.3 Function Application
Because Miking lambdas are curried, the translated JavaScript must also support
currying. This becomes a problem when supporting FFIs, because JavaScript
passes arguments in a single parameter vector. The solution to this is to curry
arguments in function applications by default and specifically disable it for
external interfaces and built-in APIs.
The code example 17, illustrates how lambdas are constructed, but also on line 2,
how function application looks like. The translated code can also be seen in code
example 18 on line 2.
1 sem foldApp : [Expr] -> Expr -> (Expr, [Expr])

2 sem foldApp acc =
3 | TmApp { lhs = lhs, rhs = rhs } ->
4 if _isUnitTy (tyTm rhs) then foldApp acc lhs
5 else foldApp (cons rhs acc) lhs
6 | t -> (t, acc)
Program code 20: Folding curried function applications
The code for compiling function applications (see 21) uses a helper function
foldApp, that extracts all arguments from nested function applications, see 20.
Applications work similar to how lambdas are constructed, one argument is
passed to one lambda at a time (currying). This means that the applications at
line 2 in example 17, can be re-written as (((add) 5) 6). The foldApp simply
peels off each argument until it encounters an expression that is not a function
application (TmApp), and collects them into a list and returns it as a tuple including
the function expression (add, [5, 6]).
29
1 TmApp _ & app ->
2 match foldApp [] app with (fun, args) in
3 match mapCompileMExpr ctx args with (ctx, args) in
4 match fun with TmVar { ident = ident } then
5 JSEApp {
6 fun = JSEVar { id = ident },
7 args = args,
8 curried = true
9 }
10 else match fun with TmConst { val = val, info = info } then
11 compileMConst info ctx args val
12 else ... -- error
Program code 21: Compilation of TmApp
As mentioned previously, function applications are uncurried to their function

reference and argument vector counterparts. Then the arguments are compiled
using the helper function mapCompileMExpr, it simply compiles a list of Miking
expressions one by one while using and updating a compile context for all and
then returning both the final context and compiled arguments. The last step is
to check if the function expression fun, is a variable reference and if so returns
a regular function application in JavaScript. Otherwise check if it is a constant
expression (TmConst) and compile it to JS intrinsic using the compileMConst
semantic function, read more in chapter 5.1.9
5.1.4 Records
Records in Miking are very similar to JavaScript objects. They almost have the
same notation and behaviour, except in Miking all records are immutable. On the
other hand, object fields can be changed, using shadowing.
1 let r = {a = 1, b = 2, c = 3} in
2 let r = {r with c = 4} in -- Update a record field
3 match r with {a = a} then print int2string a
Program code 22: Example of records in Miking
30
In the example code above 22, the variable r holds a reference to a record
data structure. On the second line, r gets shadowed with a new record where
c = 4.
1 let r = {a: 1, b: 2, c: 3};

2 r = {...r, c: 4}; -- Immutable object field update
3 if ({a} = r) console.log(a);
Program code 23: Example of 22 using objects in JavaScript
Program code 23 display how program code 22 could look when compiled to
JSON 9 objects.
1 TmRecord { bindings = bindings } ->

2 let compileField = (lam f. match f with (sid, expr) in
3 (sidToString sid, compileMExpr expr)
4 ) in
5 JSEObject { fields = map compileField (mapToSeq bindings) }
Program code 24: Compilation of TmRecord
Due to the data structures similarities, translating between them is done trivially
by compiling each field values. In Miking record keys are identifiers, which is the
same as in JavaScript. Thus program code 24 maps over all fields and compiles
them to a list of key-value pairs.
5.1.5 Sequences
Sequences in Miking are synonymous to JavaScript lists (arrays). Therefore the

compilation of these is trivial. See the lines 4-5 in program code 25.
In Miking, strings are represented as character lists with the type alias
String = [Char]. These are compiled into JS strings ("example" or 'string')
by first checking if a given sequence is not empty and only consists of characters.
In such a case, a JSEString AST expression node is returned with the given string
value of that character sequence. Otherwise it is returned as a normal array, see
program code 25.
9
JavaScript Object Notation [43, 44].
31
1 TmSeq {tms = tms} ->
2 if _isCharSeq tms then
3 JSEString { s = _charSeq2String tms }
4 else match mapCompileMExpr ctx tms with (ctx, exprs) in
5 JSEArray { exprs = exprs }
Program code 25: Compilation of TmSeq
5.1.6 Constant Literals
Constants in Miking are primitive data types (integers, floating point numbers,
single characters, logical booleans) and built-in functions.
1 TmConst { val = val, info = info } ->

2 match val with CInt { val = val } then JSEInt { i = val }
3 else match val with CFloat { val = val } then JSEFloat { f = val }
4 else match val with CChar { val = val } then JSEChar { c = val }
5 else match val with CBool { val = val } then JSEBool { b = val }
6 else compileMConst info ctx [] val
Program code 26: Compilation of TmConst
The code above 26, compiles each of the Miking constant types. It also handles the
case for build-in functions by defaulting to the compileMConst semantic function.
More about that in chapter 5.1.9.
32
5.1.7 Let Declarations
Let constructs define new or shadow previous variables in a given scope. This
modifies the program environment for the expressions afterwards.
1 TmLet { ident = ident, body = body, inexpr = e } ->

3 match compileMExpr ctx e with (ctx, e) in
4 match compileDeclarations ctx with (ctx, decs) in
5 JSEBlock {
6 exprs = [decs, JSEDef { id = ident, expr = body }],
7 ret = e
8 }
Program code 27: Compilation of TmLet
The code above (Program code 27) shows how Miking-lets are translated into
JavaScript variable definitions (declaration and initialization). Because almost
every data structure in Miking is immutable, we can utilize the const keyword in
JavaScript to signal to the runtime that this variable can be disposed when exiting
the defined variable scope.
We could also use the Object.freeze method to make JavaScript objects

static, though this is not a requirement as all other code assume it already is
immutable.
One exception to the immutable data structures in Miking are references.

These point to local mutable data and are required to implement some
functionality such as interacting with the file and operating system, or optimized
implementations of common data structures and algorithms.
5.1.8 Recursive Lets
This is the most interesting construction to compile in this thesis. The difficulties
of compiling between a functional and an imperative language are explained
extensively in this report, and it is this construct that makes it possible to create
the kind of code that is hard to translate between paradigms. The problem in
question is actually recursive functions.
TmRecLets define new recursive structures, such as functions that has self
references or multiple functions referencing each other. Mutually recursive
33
functions is an example of chains of cyclic recursive function dependencies with
two functions. More about how these types of functions can be compiled and
optimized in chapter 5.4.
1 TmRecLets { bindings = bindings, inexpr = e, ty = ty } ->

2 match compileMExpr ctx e with (ctx, e) in
3 match foldl (lam acc: (CompileJSContext, [JSExpr]). lam bind.
4 match acc with (ctx, es) in
5 match bind with { ident = ident, body = body, info = info } in
6 match body with TmLam _ then
8 let expr = (if ctx.options.tailCallOptimizations
9 then optimizeTailCallFunc ctx ident info body
10 else JSEDef { id = ident, expr = body }) in
11 (ctx, cons expr es)
12 else ... -- error
13 ) (ctx, []) bindings with (ctx, exprs) in
14 match compileDeclarations ctx with (ctx, decs) in
15 JSEBlock {
16 exprs = cons decs exprs,
17 ret = e
18 }
Program code 28: Compilation of TmRecLets
The program code 28 displays the intricate compilation implementation of these

kinds of recursive let binding constructs. It compiles each binding using a
special lambda function (seen in line 3) and folds them into a list of compiled
expressions using an accumulator acc. This implementation only supports
lambda expressions as values in recursive lets for each binding body and throws
an error for other values. The body is compiled as normal but also checks if tail call
optimization is enabled, and calls the optimizeTailCallFunc semantic function
to convert recursive functions that might ”blow“ or ”smash“ the call stack if not
optimized [12, 39, 73]. Finally, a JavaScript definition node is returned with either
an optimized or regular function and is appended to the list of expressions. All of
the resulting expressions get collected into the same block structure.
34
5.1.9 Intrinsic
As mentioned in chapter 5.1.6, there are several built-in constructs and primitive
data types in Miking. The language does not have any operators such as +, -,
*, /, but instead functions called add, sub, mul, div for each data type. These
constants are handled separately for better separation of concerns.
1 sem compileMConst info ctx args =

2 -- Binary operators
3 | CAddi _ & t
4 | CAddf _ & t -> optimizedIntrinsicGenStr t "add" args (_binOp (JSOAdd {}))
5 | CSubi _ & t
6 | CSubf _ & t -> optimizedIntrinsicGenStr t "sub" args (_binOp (JSOSub {}))
7 | CMuli _ & t
8 | CMulf _ & t -> optimizedIntrinsicGenStr t "mul" args (_binOp (JSOMul {}))
9 | CDivi _ & t
10 | CDivf _ & t -> optimizedIntrinsicGenStr t "div" args (_binOp (JSODiv {}))
11 -- Unary operators
12 | CNegf _ & t
13 | CNegi _ & t -> optimizedIntrinsicGenStr t "neg" args (_unOp (JSONeg {}))
14 | CFloorfi _ & t -> intrinsicStrGen "floor" args
15 -- Sequential operators
16 | CLength _ & t -> intrinsicGen t args
17 | CHead _ & t -> intrinsicGen t args
18 | CTail _ & t -> intrinsicGen t args
19 | CCons _ & t -> intrinsicGen t args
20 ...
Program code 29: Compilation of operators in compileMConst
The code 29 is a short extract of all translations of all supported built-in

operations. It is simply a long list of all constant functions (denoted by a prefix ”C”)
and their corresponding intrinsic functions in JavaScript on the right. Many of
them use the helper function optimizedIntrinsicGenStr, which ”optimizes” the
function if it is fully applied, meaning that all arguments that the specific constant
can take (using the constArity function under the hood to extract the number of
parameters the constant t has). If it is fully applied, the JavaScript operator is
used directly instead of referencing a curried intrinsic function.
Other built-in constant functions do not have a corresponding JS operator, hence

the use of the intrinsicStrGen function, that simply calls an intrinsic function
with a given name and arguments. Some const functions even have the same name
35
and can be compiled using the intrinsicGen function. The suffix ”Gen” specifies
which target runtime the intrinsic exists in.
5.2 Pattern Matching

In this chapter, method and implementation details are presented and explained
for the compilation of Miking match expressions to JavaScript destructuring
expressions with full support for nested structures. A number of general
optimization suggestions are also described in chapter 5.2.4.
5.2.1 Introduction
Pattern matching is a concept that originates from functional programming

languages, where the concept of classes, inheritance, and abstractions do not
exist. Instead, there are various immutable data structures, and the way to
distinguish, separate and classify these is by matching them against a certain
pattern and changing the flow of the program based on the result. If you have
ever written functional code and used pattern matching, you know how powerful
they are and learn to miss them among modern imperative languages. This is why
many modern programming languages today adopt this method and accept and
standardize it with wide support. However, JavaScript has not had time to keep up
with this relatively rapid development yet. But lacks support for pattern matching
of the same capacity found in other languages.
On the other hand, there is a proposal made by several leading experts in today’s
industry for future support for full-fledged pattern matching in JavaScript, and
reached Stage 1 on July 14, 2022 [30, 62, 66]!
5.2.2 Method
When compiling match constructs to JavaScript in this thesis, we resort to using

the already existing destructuring assignment feature [65]. This is because pattern
matching is not currently supported and the decided target ECMAScript standard
to support in the compiler backend is ES6. While Node.js doesn’t require variables
to be defined before being assigned, some JS runtimes such as Bun and Deno
do [11, 22]. This forces the compiler to generate code that declares variables
before assignments or references to them. The backend does this through hoisting
variables used in nested sub-expressions up to the nearest block scope level. The
36
place where new variables might get introduced (other than in let and recursive
let constructs) is mainly in binding pattern bodies in match constructs.
1 TmMatch {target = target, pat = pat, thn = thn, els = els } ->
2 match compileMExpr ctx target with (ctx, target) in
3 match compileBindingPattern ctx target pat with (ctx2, pat) in
4 match compileMExpr ctx thn with (ctx, thn) in
5 match compileMExpr ctx els with (ctx, els) in
6 let ctx = combineDeclarations ctx ctx2 in
7 let expr = JSETernary {
8 cond = pat,
9 thn = immediatelyInvokeBlock thn,
10 els = immediatelyInvokeBlock els
11 } in
12 let expr = optimizeExpr3 expr in
13 (ctx, expr)
Program code 30: Compilation of TmMatch
Program code 30 shows how match constructs gets compiled into ternary
expressions (created on line 7 and optimized on line 12). This translation
maintains the expressive property of pattern matching in Miking, as everything
is an expression.
In Miking, the syntax for pattern matching expressions looks like the following:
”match value with pattern then body else otherwise”, this is structurally
similar to JavaScript’s ternary expression with a nested destructuring assignment
as a condition ”(pattern = value) ? body : otherwise”.
The immediatelyInvokeBlock function in program code 30 creates an

immediately invoked function expression (IIFE) with a block as body if given,
else the expression is just returned.
Undefined variables are transferred in the compiler context ctx, and surface in
semantic functions where a compilation might result in a block expression. Some
examples of where undefined variables are declared is when compiling let and
recursive let constructs (27 and 28).
37
5.2.3 Patterns
As mentioned in the previous chapters, translation of pattern matching constructs

to JavaScript utilizes the destructuring assignment feature to create a sequence
of unfolded pattern matches. This means that some structure patterns are not
directly matched in whole, but each element is extracted and compared on their
own. The result of all these individual matchings are then combined using the
logical and operator & in JavaScript to ensure that the full pattern only matches if
all sub-patterns match.
1 sem compileBindingPattern ctx target =

2 | PatNamed { ident = PWildcard () } -> (ctx, JSEBool { b = true })
3 | PatNamed { ident = PName name } & p ->
4 match compileSinglePattern ctx p with (ctx, pat, _) in
5 (ctx, _assign pat target )
6 | (PatInt _ | PatBool _ | PatChar _) & p ->
7 match compileSinglePattern ctx p with (ctx, pat, []) in
8 (ctx, _binOp (JSOEq {}) [target, pat])
9 | ( PatSeqEdge _ | PatRecord _ ) & p ->
10 match compileSinglePattern ctx p with (ctx, pat, extra) in
11 (ctx, _binOpM (JSOAnd {}) (cons (_assign (pat) target) extra) )
12 | PatSeqTot { pats = pats } & p ->
13 let lengthCheck = compilePatsLen pats target in
14 if null pats then (ctx, lengthCheck)
15 else if _isCharPatSeq pats then
16 let str = JSEString { s = _charPatSeq2String pats } in
17 (ctx, _binOp (JSOEq {}) [target, str] )
18 else
19 match compileSinglePattern ctx p with (ctx, pat, extra) in
20 (ctx, _binOpM (JSOAnd {}) (
21 join [ [lengthCheck], [_assign (pat) target], extra]) )
Program code 31: Some Pattern Compilations
In program code 31 is a short extract shown from the compileBindingPattern

semantic function. This is used in compilation of match constructs (code 30).
The function shown above takes a target and a Miking pattern (Pat*), and
disassembles it, compile it as a single pattern or directly returns a logical value
38
depending on the type of pattern. Program code 31 only handles the overall
”logical” part as well as unfolding sequence edge patterns, but that is not
covered here. The remaining task is to compile the actual data structures to
JavaScript.
1 sem compileSinglePattern ctx =

2 | PatInt { val = val } -> (ctx, JSEInt { i = val }, [])
3 | PatBool { val = val } -> (ctx, JSEBool { b = val }, [])
4 | PatChar { val = val } -> (ctx, JSEChar { c = val}, [])
5 | PatNamed { ident = PName name } ->
6 let ctx = { ctx with declarations = setInsert name ctx.declarations } in
7 (ctx, JSEVar { id = name }, [])
8 | PatNamed { ident = PWildcard () } -> (ctx, tmpIgnoreJS, [])
9 | PatSeqTot { pats = patterns } ->
10 match safeMapSinglePattern ctx patterns with (ctx, elems, extra) in
11 (ctx, JSEArray { exprs = elems }, extra)
12 | PatRecord { bindings = bindings } -> match foldr (
13 lam field: (SID, Pat). lam acc.
14 match acc with (ctx, patts, extra) in
15 match field with (sid, pat) in
16 match safeCompileSinglePattern ctx pat with (ctx, patExpr, patExtras) in
17 (ctx, cons (sidToString sid, patExpr) patts, concat patExtras extra)
18 ) (ctx, [], []) (mapToSeq bindings) with (ctx, fields, extra) in
19 (ctx, JSEObject { fields = fields }, extra)
Program code 32: Single Pattern Compilations
The code above (Program 32) display how a single pattern gets translated into
its corresponding JavaScript expression form. Most are trivial and simply
return an AST expression with the same values as in Miking. But looking at
PatSeqTot and PatRecord, we notice the use of safeCompileSinglePattern and
safeMapSinglePattern (map version of the former).
39
1 sem safeCompileSinglePattern ctx =
2 | ( PatInt _ | PatBool _ | PatChar _
3 | PatSeqTot _ | PatSeqEdge _
4 | PatRecord _ | PatCon _ ) & p ->
5 let id = nameSym "_nstd" in
6 let matchVar = JSEVar { id = id } in
7 let ctx = { ctx with declarations = setInsert id ctx.declarations } in
8 match compileBindingPattern ctx matchVar p with (ctx, matchBinding) in
9 (ctx, matchVar, [matchBinding])
10 | p -> compileSinglePattern ctx p
Program code 33: Safe Compilation of Single Patterns
The semantic function safeCompileSinglePattern is only used when compiling

nested patterns, the program code 33 shows how a selected number of patterns
are replaced with a single variable indicating a nested match (_nstd). This is
replaced in the nested structure and the original pattern is compiled individually
as a binding pattern but with the value of _nstd from the nested structure match
earlier.
The compilation context is updated with the new temporary _nstd variable on line
7 in program code 33. This context is also returned together with the expression
that should be inserted as a nested sub-pattern, and with any extra binding
included in the pattern matching check.
This method will soon be deprecated as a pull request is being reviewed to

implement a pre-processing step to also lower patterns into shallow versions10 .
A different implementation will therefore be used later on in the future of the
JavaScript backend.
10
View the PR here: https://github.com/miking-lang/miking/pull/619
40
5.2.4 Optimizations
Many patterns after being compiled into JavaScript, have redundant checks,
nested ternary expressions, and some checks that could be converted into logical
operators.
1 sem optimizeExpr =
2 | JSEBinOp { op = JSOEq {}, lhs = lhs, rhs = rhs } & p ->
3 match lhs with JSEBool { b = true } then optimizeExpr rhs else
4 match rhs with JSEBool { b = true } then optimizeExpr lhs else
5 match lhs with JSEBool { b = false } then
6 JSEUnOp { op = JSONot {}, rhs = optimizeExpr rhs } else
7 match rhs with JSEBool { b = false } then
8 JSEUnOp { op = JSONot {}, rhs = optimizeExpr lhs } else p
9 | JSETernary { cond = cond, thn = thn, els = els } ->
10 let cond = optimizeExpr cond in
11 let thn = optimizeExpr thn in
12 let els = optimizeExpr els in
13 match cond with JSEBool { b = true } then thn else
14 match cond with JSEBool { b = false } then els else
15 match els with JSEBool { b = false } then
16 JSEBinOp { op = JSOAnd {}, lhs = cond, rhs = thn }
17 else match thn with JSEBool { b = true } then
18 JSEBinOp { op = JSOOr {}, lhs = cond, rhs = els }
19 else match (thn, els) with (JSEBool {b = true}, JSEBool {b = false})
20 then cond
21 else match (thn, els) with (JSEBool {b = false}, JSEBool {b = true})
22 then JSEUnOp { op = JSONot {}, rhs = cond }
23 else JSETernary { cond = cond, thn = thn, els = els }
Program code 34: Some Expression Optimizations
The optimizeExpr semantic function matches expressions of different types

against different known patterns that can be simplified into more compact code,
which may improve readability. In program code 34, a short solution is presented
for general pattern optimizations (after compilation). Covering the most frequent
cases that emerged during the development of the backend implementation.
41
5.3 Foreign Function Interfaces
Foreign function interfaces allow us to interact with external functions in the
target programming language. These functions have defined interfaces and type
information that allow them to be interacted with in Miking seamlessly, and
are translated into precisely functional JavaScript that makes use of the desired
API. The following chapters present handling of these at a deep level and discuss
their usefulness for system programming and interactive websites through client
JavaScript accessing browser-specific functionality.
5.3.1 Type Systems
The two languages are vastly different in this aspect, as Miking is statically typed
with type inference while JavaScript is instead weakly and dynamically typed,
which means that it performs runtime type checking. It is often claimed that
dynamic languages like JavaScript do not have a type system. Although this is
not completely true. There are ways to raise type errors in JavaScript engines by
passing invalid values to a native function or operator, modifying an immutable
reference, or accessing a value in an inappropriate way or in an invalid context.
The following expression is an example of code that will throw a TypeError in
JavaScript: null.f() [79].
JavaScript has a model that supports implicit type conversions, allowing some
operators to support different types mixed with each other. One such operator
is the addition (+), which supports both regular integer and floating point
addition, as well as string concatenation with different types ("hello" + 42).
This property can be used to advantage in the development of a compiler from a
statically typed language to a dynamic one. For example, Miking has a number
of operator functions to handle binary expressions (addi, addf, subi, etc.)
and to cast values between different types (int2string, int2float, char2int,
etc.).
Since we are translating types from a ”larger” system to a ”smaller”, we can

reduce the surface of the built-in operator functions as long as we don’t create
any edge cases where types miss-match in JS but do in Miking. Therefore, the
intersection between the two built-in standard libraries must have the same type
of interface.
42
Miking JavaScript
x : t ∈ Γ (var) (var)
Γ⊢x:t Γ ⊢ x : t || Γ
Γ ⊢ e1 : t Γ ⊢ e2 : t Γ ⊢ e 1 : t1 Γ ⊢ e 2 : t2
(add) (add)
Γ ⊢ addt e1 e2 : t Γ ⊢ e1 +e2 : max(t1 , t2 )
Figure 5.1: Typing Rules in Miking and JavaScript
Because type inference differentiates between the two languages, it is important

to know what reductions in the standard library are possible. Therefore a
comparison is necessary to visualize what pitfalls to avoid when designing the
intrinsic in JavaScript. The table in Figure 5.1 shows some examples of how
Miking type inference and JavaScript runtime type checking work. JavaScript
does not require variables to be declared or initialized before being referenced [4,
5, 14, 24, 49] in contrast to Miking, where they must exist in the current context
(or environment) Γ. JavaScript does add types during runtime which is why x : t
is inferred even if it does not exists, if not undefined is returned.
Looking at the bottom row of the table in figure 5.1 there is a comparison for
the addition operation. Miking have special built-in functions for each type of
addition (addt ∈ {addi, addf}) and sets a constraint on the term types t, that
t ∈ {Int, F loat} for both e1 and e2 . JavaScript abstracts this away under the +
operator that practically take any type but might fail during runtime. Therefore,
well-formed programs use the types t1 and t2 that are defined for the + operator.
Those are t1 ∧ t2 ∈ {N umber, Boolean, String, BigInt} [3]. The max function
decides which type t1 and t2 should be cast to before performing the operation.
For example max(N umber, String) = String, which means that the number e1
will be converted into its string representation and concatenated with the string
e2 .
43
5.3.2 Miking Externals
The current implementation of FFIs is soon going to be obsolete, as the method

of handling external functions is under a ground-up rework by the Miking
compiler team. Regardless, the implementation used in the back end is presented
anyway.
To declare new foreign function interfaces in Miking, the external keyword is

used to bind an identifier name, tell if it may cause side effects (!) and its type
signature. The program code 35 shows a number of external example functions of
the standard library in the Miking compiler.
1 external fileExists ! : String -> Bool

2 external deleteFile ! : String -> ()
3 let deleteFile = lam s. if fileExists s then deleteFile s else ()
4 external fileSize ! : String -> Int
5 external externalSin : Float -> Float
6 let sin = lam x : Float. externalSin x
7 utest sin (divf pi 2.) with 1. using eqf
8 utest sin 0. with 0. using eqf
9 external externalCos : Float -> Float
10 external externalExp : Float -> Float
Program code 35: Example of External Function Interfaces
Each compilation target language backend needs to implement regular external

function bindings or definitions in the generated code. For the C backend,
this is done via a hash table containing all corresponding functions from
the math library; for example, the exponential function externalExp has the
entry: { ident = "exp", header = "<math.h>" }. Similarly, OCaml binds the
same exponential function to the member method on the Float data type:
{ expr = "Float.exp" } (extra type information was omitted).
For the JavaScript backend, generic intrinsic functions are added to a single object
containing platform-independent implementations of built-in Miking functions
and external FFIs. External functions are compiled into references to intrinsic
functions by the same method but using semantic functions, so the code entry for
the exponential function looks like "externalExp" -> externalRefGen "exp".
This line creates a new function reference to exp in the generic intrinsic.
44
This method of implementing support for external function interaction in Miking
is highly scalable from within the compiler standard library. The downside is that
user implementations of FFIs are not possible locally. This is why FFI handling in
the compiler is under ground-up rework.
5.3.3 Runtime Targets
Due to the support of multiple target platforms, runtime environments, and

JavaScript engines (see chapter 4.4). The generated code must be highly adaptive
when compiling code to different targets depending on external functions defined
in the target runtimes API. For example, Node.js and Bun differ a lot when
it comes to structuring and integrating runtime-specific functions. Bun, for
example, defines most of its API in the module namespace Bun, while Node.js uses
a standard library from which the user is required to import functions. To write
to a file on the operating system, Bun uses Bun.write("file.txt", data) while
Node.js must first fs = require("fs") then fs.writeFile("file.txt", data)
[11, 59]. Then the problem of missing API overlaps arises; for example, the
browser does not have access to the underlying operating system and file system
by default. Thus, compiling code targeting the web that uses IO functions such as
writing to files must throw a compile-time exception. The same goes the other way
around as well; system programs cannot access browser-specific functions.
1 const MExpr_Node_JS_Intrinsics = Object.freeze({

2 print: msg => process.stdout.write(msg),
3 exit: code => process.exit(code),
4 argv: () => process.argv.slice(1),
5 });
Program code 36: Node.js intrinsic header
With the current extensible design and implementation of external FFI handling,
adding support for new runtimes in the JavaScript compiler backend is easy.
The only thing that must be done is to add a JavaScript file defining a constant
frozen object that is included as a header for all generated code. For example,
the program code 36 describes a subset of runtime-specific external functions
supported by the compiler when targeting node.
45
5.3.4 Browser API
In the thesis project, along with a multi-target compiler backend, a small library
is included to interact with browser client APIs when targeting the web. This
is possible thanks to the shared platform-independent code generated by the
backend, with extra external FFIs defined on top.
1 type Location = {
2 host: String, hostname: String, href: String, origin: String,
3 pathname: String, port: String, protocol: String, search: String,
4 reload: () -> (), replace: () -> (), assign: () -> ()
5 }
6 type Element = {
7 childNodes: [Element], children: [Element], classList: [String],
8 hidden: Boolean, id: String, innerHTML: String, innerText: String,
9 nodeName: String, onchange: () -> (), onclick: () -> (),
10 onfocus: () -> (), onload: () -> ()
11 }
12 type Document = {
13 append: Element -> (), body: Element, childNodes: [Element],
14 children: [Element], cookie: String, location: Location,
15 getElementById: String -> Option Element
16 getElementsByClassName: String -> [Element]
17 }
18 external getDocument : () -> Document
Program code 37: Browser FFI API subset
The above program code 37 is a small subset of the browser FFI library API
enabling client-side JavaScript code to interact with the DOM of a website
(getDocument). Like in the previous section, the bindings between Miking and
the web target intrinsic must be added, and the getDocument function must be
defined. The glue code is similar to the program code 36, except that we define
getDocument: () => window.document. Notice how the Location, Element and
Document types are omitted, this is because they do not translate to JavaScript.
Instead, they model the browser environment as closely as possible so that the
interfaces overlap.
46
To begin writing client-side JavaScript, the dom-api-ext.mc file must first be
included in the Miking program. This brings in the relevant types and functions
ready to be used by the programmer. The only thing left is to compile the Miking
program into JavaScript targeting the web environment. This development
process is seamless, thanks to the dom-api library being compliant with the web
target.
Similarly to what has been presented in this chapter, other libraries can be built
using the same method for different runtimes and environments. The limitation
of compiler only-libraries will soon be solved and implementing custom FFIs and
intrinsic glue bindings will soon be possible for users locally.
47
5.4 Tail-Call Optimization
JavaScript is an imperative language with statements and functions, in contrast to
most functional languages, which are often purely expression-based. This means
that iterating over data structures, such as lists, requires some kind of recursion.
The challenge of translating between these two language paradigms comes mostly
from the task of transforming recursive code into equivalent code constructed with
statements and non-recursive functions in the imperative target language.
5.4.1 Introduction
Using recursive functions in a language without tail-call optimization (i.e.,

JavaScript) would result in multiple stack frames added to the call stack if invoked.
This is the reason why for and while loops exist in these languages. On the one
hand, translating an expression from a functional language to use these types of
looping constructs is possible and a viable option for dealing with direct recursion.
However, this quickly becomes a problem when it comes to mutual recursion and
higher-order cyclic recursive function dependency chains.
To solve the translation problem of these types of functions that traverse a number
of other functions before recursively calling them again, we use a technique called
trampolining [7, 8, 47, 48, 54, 61, 64, 74–76]. This method works for both direct
and mutual recursion and is a higher-level abstraction of directly translating into
loop constructs. This comes at a slight performance cost, as an additional function
call is done for each recursive function.
The following chapter describes a method of translating any recursive function

into an optimized non-recursive function using trampolines. Functions that are
mutually recursive remain so but are also independently optimized and retain
their pairwise dependencies. This works for any length of cyclic recursive function
chains.
48
5.4.2 Trampolining
Tail calls can be optimized by specific methods, depending on the use case, in a
multitude of ways. When compiling to native binaries, tail calls can directly be
replaced with a jump or ”goto” instruction, with the goal to pop the call stack
frame when exiting the function. In other cases, calls to other functions simply
push a new execution frame to the call stack, thus increasing the size of the stack.
To directly jump outside of functions and dispose of their call contexts, holding
scoped variables, also helps the program to be executed faster, as well as taking
up less memory. Therefore, this is an optimization dealing with the execution call
stack and execution time.
In JavaScript, there is no quick and easy way of controlling how execution contexts
are disposed of. That is why an adaptation must be done to only optimize functions
that might ”smash” the call stack and cause it to overflow. Such functions are
explicitly declared with the recursive keyword in Miking; read more about the
compilation of recursive lets in Chapter 5.1.8.
Instead, we use a technique called trampolining, which helps minimize the

potential negative effect recursive functions might have on the call stack. In
JavaScript, this method trades efficiency against more safe execution, preventing
the call stack to be maxed out and causing ”maximum call stack size exceeded”
exceptions.
1 const trampolineCapture = fun => args =>

2 ({ fun: fun, args: args, isTrampolineCapture: true });
3
4 const trampolineValue = val => {
5 while (val.isTrampolineCapture) {
6 val = val.args.reduce((acc, arg) => acc(arg), val.fun);
7 }
8 return val;
9 };
Program code 38: Trampoline Functions in JavaScript
A trampoline is essentially a function taking a capture thunk and repeatedly calling

the specified functions returned in the capture until it arrives at a final result
value.
49
Program code 38 shows the implementations of the two utility functions
trampolineCapture and trampolineValue, which are used for trampolining calls
within some function. The trampolineCapture function is a constructor for
captures represented as objects in JavaScript, it has function and argument fields,
as well as a ”magic” flag indicating it is a trampoline capture. This is done to
separate different types of possible return values from the function and not mix
up other objects or lambdas as captures, which is a risk in other thunk-based
implementations.
The backend intrinsic implementation of trampolineValue works with captures of

curried functions. This is why the argument list is reduced (folded) and applied
one by one on the initial function reference (on line 6 in the program code 38).
This works as long as the number of arguments is the same as the function arity,
and is ensured by the type checker for the backend. Another approach would be
to use the spread operator here: val = val.fun(...val.args). Though this will
not work for curried arguments.
1 const rec_fact = n => acc => {

2 if (n < 2) return acc;
3 return trampolineCapture(rec_fact)([n - 1, n * acc]);
4 }
5 const fact = n => trampolineValue(rec_fact(n)(1));
6 console.log(fact(5)); // 120
Program code 39: Example of a Trampolined Function in JavaScript
The code above (program 39) is an example of how the utility functions in the
program code 38 can be used. The interesting aspect to note is how rec_fact
is a curried arrow function (lambda), which returns a trampolineCapture in the
tail position instead of calling itself recursively. The captured thunk contains
a reference to itself along with the intended arguments for the next invocation.
Together with the ”optimized” rec_fact function, we have defined a function
fact. This function wraps a call to the recursive variation passed to the
trampolineValue utility function. This gives us a cleaner interface to interact with
rec_fact. It also passes a default value to the accumulator (1).
50
5.4.3 Fundamental Translation
To generally explain the TCO concept used in this thesis, an abstraction of each
component in the translation process and the connections has been made.
Figure 5.2 shows a commutative diagram with three different functions: ϕFM Expr ,
ϕF1,′ JSExpr and F2,′ JSExpr . FM Expr is an example of a function interface named F in
the M Expr language. F ′ is a new function derived from the original in some way
and the index Fi′ describes the specific implementation variation.
The ϕ-prefix denotes a recursive function of any kind [21].
Dashed arrows represent directional dependencies between functions, or

”abstract” function invocations within the same language. Solid arrows describes
translation of constructs from one language to another using a given process
(specified by the label). Ψ and ψ are compiler translation processes between
languages (solid). Φ and π are transformed dependencies (dashed) within the
same language (dashed).
ϕF1,′ JSExpr
ψ
ϕFM Expr Φ
Ψ
F2,′ JSExpr
Figure 5.2: Fundamental TCO Translation Procedure
The diagram in Figure 5.2 describes the procedure to translate the recursive
function ϕFM Expr from the Miking expression language (M Expr) to JavaScript
(JSExpr) using Ψ and ψ, and produce two new functions: ϕF1,′ JSExpr and
F2,′ JSExpr . The non-recursive function F2,′ JSExpr invokes the recursive variation
ϕF1,′ JSExpr that implements the recursive behaviour of ϕFM Expr , but translated
into JavaScript and semantically equivalent. The invocation is transformed
during compile time using Φ, which is wrapping the result from the recursive
function variation ϕF1,′ JSExpr with a call to the trampoline function, taking a
capture or a result value that is finally returned.
The code in Program code 40 shows an example of how a recursive function with
a tail call is optimized and translated to the corresponding JavaScript in Program
51
code 41. The function fact is split into two separate functions fact_rec$ and
fact. The first function fact_rec$ is simply a renamed variation of the original
with the exact same semantics translated into JavaScript. The ”_rec$” suffix is
added to avoid any name collision conflicts with any user-defined functions. The
key difference is that instead of calling itself in the else-branch, we return a
trampoline capture (created by the trampolineCapture function in program code
38) with the next function to call and a vector of accompanied arguments. This
breaks the pattern of recursion and prevents creating more than a single stack
frame on the call stack per call. The trampoline capture gets caught in the fact
function after a value is returned from fact_rec$, and trampolined until a non-
capture result value is returned by the trampolineValue function (program code
38).
1 recursive let fact = lam n. lam acc.

2 if lti n 1 then acc else fact (subi n 1) (muli n acc)
Program code 40: Factorial implementation in Miking
1 const fact_rec$ = n => acc => (n < 1) ? acc

2 : trampolineCapture(fact_rec$)([(n - 1), (n * acc)]);
3 const fact = n => acc => trampolineValue(fact_rec$(n)(acc));
Program code 41: Factorial translated to JavaScript
In the example above, the recursive function ϕf actM Expr is translated by ψ and
compiled to ϕf act′1, JSExpr (fact_rec$), and by Ψ to f act′2, JSExpr (fact) vice
versa. Notice how ϕf actM Expr and f act′2, JSExpr have the same function interface
n: Int -> acc: Int -> Int. This means that the functions depending on fact
don’t need to change their calling behavior, this is presented more in-depth in the
next chapter 5.4.4. Compilation of more complex dependency chains is presented
in chapter 5.4.5.
52
5.4.4 Translation of Non-recursive Callers
The goal with this method is to keep direct functions dependent on this translation
to be left intact. This means that all modifications during compilation must be
done only on the recursive function itself, not its references. This is also a good
design pattern in respect to separation of concerns and encapsulation from a
compiler implementation perspective.
ϕF1,′ JSExpr
ψ
′
HM Expr ϕFM Expr Φ HJSExpr
F2,′ JSExpr
Figure 5.3: Translation Procedure for Non-recursive Caller
The diagram in figure 5.3 illustrates this property. Before compilation, the non-
recursive function H calls the recursive function ϕF in it’s body thus having
a direct dependency to it (dashed arrow). After ϕF is compiled from Miking
(M Expr) to JavaScript (JSExpr), the corresponding function H ′ (compiled
separately) has a reference to the non-recursive F2′ with the exact same interface as
ϕF . The compilation of H is therefore independent of the compilation method for
′
ϕF . One could imagine an “implicit arrow” in Figure 5.3 from HM Expr to HJSExpr
representing the translation of the non-recursive function. This is not shown in
Figure 5.3 as it is done in another step elsewhere in the compiler.
53
5.4.5 Translation of Recursive Function Chains
To detect and optimize higher-order chains of recursive functions is a bit more of

a challenge. Some recursive functions depend on other recursive functions that
are defined ”below” in a recursive let construct. This makes it impossible to
know what kind of function a reference is referring to within a recursive let
when compiling top-down, a standard let declaration or a neighbouring recursive
function defined later?
1 let tru = lam. true in

2 let fls = lam. false in
3 recursive
4 let isEven = lam n. if eqi n 0 then tru() else isOdd (subi n 1)
5 let isOdd = lam n. if eqi n 0 then fls() else isEven (subi n 1)
Program code 42: Mutual Recursive Functions in Miking
The program code 42 illustrate how such a dependency chain could look like.
In this example, the function we need to find and remember is isOdd before
compiling isEven. In this example, the recursive dependency follows the same
structure as shown in Figure 5.4. The recursive functions in program 42 reference
the two functions tru and fls. The purpose of these functions is to show how the
translation process only apply to recursive functions.
This solution performs an initial pass through the AST of recursive let bindings
before fully compiling each let binding clause. This process extracts every
recursive lambda into a set of names which is later used as a lookup table to
identify recursive function references at actual compile time. This allows recursive
functions that are, for example, mutually dependent, to be aware of each other
before the others are compiled. Thanks to this, these dependencies can be
optimized and returned as trampoline captures. Other dependencies on non-
recursive functions are left intact.
54
π
ϕF1,′ JSExpr ϕG′1, JSExpr

ψ
π
ϕGM Expr ϕFM Expr Φ Φ
Ψ
F2,′ JSExpr G′2, JSExpr
Figure 5.4: Translation Procedure for Mutual Recursive Functions
Optimized recursive function dependency chains can be compiled separately

thanks to the name set lookup table introduced previously in this chapter. Figure
5.4 depicts how the mutually recursive functions ϕF and ϕG maintain the loop
dependency between their recursive variations ϕF1′ and ϕG′1 in the target language
(JSExpr).
As mentioned in chapter 5.4.3, calls to other recursive functions are transformed

into returned trampoline captures. This dependency transformation is indicated
by the label π on the dashed arrow between two recursive functions.
π
ϕHM Expr ϕF1,′ JSExpr ϕG′1, JSExpr

ψ
ϕFM Expr π ′
ϕH1, π
Φ JSExpr Φ
Φ
Ψ
ϕGM Expr F2,′ JSExpr ′
H2, JSExpr G′2, JSExpr
Figure 5.5: Translation Procedure for a Chain of three Recursive Functions
This compilation tactic for recursive chains is not limited by the number of
functions. Figure 5.5 shows how this is possible for any chain of cyclic recursive
function dependencies.
Notice that there is also no restriction on what the dependency graph looks like,
there only needs to be a cycle somewhere for this optimization to be beneficial. For
example, a labeled recursive function can reference both itself (direct recursion)
and a chain of multiple mutually recursive functions.
55
5.4.6 Translation Example
To support the concepts covered in this chapter, a concrete example of translation,

transformation, and compilation is presented in this section. This will hopefully
contribute to a deeper understanding of the explanations earlier. To keep
things simple, we use the same program code 42 from earlier to compile to
JavaScript.
1 const tru = () => true;

2 const fls = () => false;
3 const isEven_rec$ = n => n === 0 ? tru() :
4 trampolineCapture(isOdd_rec$)([n - 1]);
5 const isEven = n => trampolineValue(isEven_rec$(n));
6 const isOdd_rec$ = n => n === 0 ? fls() :
7 trampolineCapture(isEven_rec$)([n - 1]);
8 const isOdd = n => trampolineValue(isOdd_rec$(n));
Program code 43: Mutual Recursive Functions compiled to JavaScript
The code examples 43 illustrate how the mutual recursive functions isEven and
isOdd are compiled to JavaScript from the implementation in Miking (program
code 42). In the JavaScript code 43, isEven and isOdd has two function variations.
This is a process done during compilation to translate the function semantics to
JavaScript in a better way. The translation of isEven to isEven_rec$ is called ψ,
and isEven (Miking) to isEven (JS) Ψ.
Notice how the calls to tru and fls are not captured in isEven_rec$ and
isOdd_rec$. Instead they are immediately invoked, because there is no ”risk” for
them to exceed the call stack limit. They might call other functions, but this is not
a problem. Looking at line 4 and 7 in code examples 43, the mutual recursive
calls are captured instead of returning the value of a tail call. This is because
the function application has been transformed by π. This is because they are
references to recursive functions (each other).
Also notice how in code example 42, isEven and isOdd reference each other as
usual. But after compilation in code example 43, isEven and isOdd both call their
isEven_rec$ and isOdd_rec$ counterparts and is denoted by Φ. This is exactly
the same as what is shown in figure 5.4 for F and G.
56
5.5 Code Generation
This chapter presents the developed component that generates JavaScript code,
and how it meets the specified requirements with its method and implementation
in the Miking compiler.
5.5.1 Introduction
After the compiler backend is done translating the Miking expression AST to
JavaScript, the constructed AST is passed on to the code generator. The
generation consists of a tree walking emitter that formats and outputs the
JavaScript target code to a string. The output can later be written to a file, sent
over the internet or handled by something else.
A tree walking emitter is simply a recursive function that traverses AST nodes,
pretty printing each node to readable and structural recognizable JavaScript
code. This is important as some of the main requirements were to output
readable, sound and correct. These aspects are further discussed in the following
chapters.
5.5.2 Method
To visualize how code generation happens, we will step through the process and
see how the code in example 44 is translated into JavaScript.
let sum = lam lst. foldl (addi) lst 0
Program code 44: Example sum function in Miking
First the code is parsed and translated into its AST representation before being
passed to the JavaScript backend. After the Miking AST is translated to the
corresponding JavaScript AST seen below in figure 5.6.
57
JSEDef
id = ”sum” expr = JSEF un
params = [”lst”] body = JSEApp
f un = JSEV ar args : [JSExpr]
id = ”f oldl” 0 = JSEV ar 1 = JSEV ar 2 = JSEInt
id = ”addi” id = ”lst” i=0
Figure 5.6: Translated JavaScript AST
The pretty printing algorithm steps through the AST and starts traversing the
first JSEDef node first. Then it recursively walks to any sub-expressions before
generating any source code. This is important because the resulting code is
dependant on any nested nodes. Hence the JSEFun node is immediately printed
which in turn goes all the way down to the last arguments of type JSExpr passed
to the foldl function that is called in the body. The code generator converts the
function application JSEApp to a correctly formatted function call in JavaScript
”foldl(addi)(lst)(0)”, and is used in the generation for the body of the sum
function definition.
const sum = lst => foldl(addi)(lst)(0);
Program code 45: Example sum function compiled to JavaScript
Finally, program code 45 gets returned from the pretty printing tree walking
emitter, and the code generator is done.
58
5.5.3 Readability, Soundness and Correctness
To show that the code is readable and sound is difficult, since it is judged
subjectively. What we can easily do instead is to compare the original code
in Miking with the compiled code in JavaScript and reason about the different
aspects and compare similarities and differences.
1 let abs = lam x. if lti x 0 then negi x else x in

2 let area = lam w. lam h. muli (abs w) (abs h) in
3 dprintLn (area 5 7)
Program code 46: Example code in Miking
1 const abs = x => x < 0 ? -x : x;

2 const area = w => h => abs(w) * abs(h);
3 dprintLn(area(5)(7));
Program code 47: Compiled example code in JavaScript
The above programs are example of possible code written by a user. They consist
of two functions abs and area, used for calculating the area of a 5x7 rectangle. The
dprintLn function is used to output the value of any type to the screen.
Judging from a first overlook of the code, the two programs have the same number
of lines, representing the same operations and functions. The function names are
retained but the syntax is a bit different. JavaScript does have the keyword let,
but this has different logical meaning than in Miking and the use of const is more
fitting, as the values will always remain constant.
Another aspect, is that the JavaScript code also use dprintLn. This function is not
included in the program code 47, but is part of the generated code. The reason
why this line isn’t replaced with a console.log, is because of better readability,
recognizability and reasonability. Our JavaScript code looks very similar to the
Miking source code, thus improving the readability from the perspective of a
Miking programmer inspecting the output JS program.
The compiled program (47) also uses simple constructs to produce code similar to
that of the original program (46). These have the same semantic meaning and are
structurally equvalent. Constant functions such as negi and muli are translated to
their corresponding JS operators - and *. In Miking, all constructs are expressions
59
and return a value, in JavaScript if-else statements does not have this property.
Instead, we compile to ternary expressions keeping the structural similarity and
semantic meaning. Therefore, I claim that the generated code is sound and correct
in this example. But also that this property holds for all compiled programs.
60
6 Evaluation
The purpose of this chapter is to briefly present, measure and evaluate the results
and most important aspects of the work that has been done in this thesis project.
What was done in a practical sense in respect to how the method was applied. A
more in-depth description of the implementation details are specified in chapter
5.
The goal with this chapter is therefore to show that the compiler backend works
as intended and that the chosen solution is adequate and good. This is done by
showing that the developed backend implementation is able to compile and run
a set of test programs, compiling a large set of the compiler source code written
in the language itself, benchmark its performance and comparing it with other
backends, to justify the correctness of the solution.
The test programs should be chosen to show that the compiler is able to compile
and run each part of the feature set in the language. The benchmark is an
important to compare the efficiency of the backend itself as well as comparing
the execution time for the compiled code against the code generated by the other
backends. Most preferably, the backend should be able to bootstrap the whole
compiler itself. This is the best way to show that the compiler is working as
intended because it is the most complex program that can be written in the
language.
6.1 Result
The developed JavaScript backend is currently present in the publicly available
Miking compiler [55]. The code consists of about 5,000 lines of Miking and
JavaScript. Most of the Miking standard library and large parts of the self hosted
compiler can be compiled and used in any JavaScript runtime environment.
Miking still has some features and constructs that are still not supported by all
target runtimes in the JavaScript backend. This is mainly because of differences
in execution environments between browser client JS, and ”native” JS through
Node.js, Deno or Bun.
There is also support for interacting with browser APIs from a set of library
functions utilizing a foreign function interface capabilities in the backend.
Manipulation of a website’s client-side HTML through a virtual Document
Object Model (DOM) type is also possible, with a number of additional library
61
functions with side-effects. This is all provided by the external dom-api-ext.mc
standard library, using an manual middle-ware implementation mapping of JS
web intrinsic functions.
6.2 Testing
As described in the project method chapter 3.3 about the plans and strategies
used for testing and validation, the backend implementation has numerous
unit and system tests to prove semantic equivalence coverage between the
Miking interpreter and compiled JavaScript code executed in different runtime
engines.
The compiler project had existing tests for different backends and features prior to
this thesis. This testing suit has been extended with a set of feature-specific tests
with aim to cover all edge cases and controversial uses of the Miking language.
This is necessary for laying out a ground framework to prove the correctness of
code produced by the compiler backend that is implemented. An example of some
of these tests are: operators.mc, foldl.mc, lam.mc, lists.mc, match_list.mc,
match_record.mc, refs.mc, rec_let.mc.
The test files get compiled by a shell script, the outputs from running the source
file using the Miking interpreter and the compiled JS through Node.js are captured
and compared using the diff11 command. If the outputs are the same, everything
passes and returns a successful status.
To improve the trustworthiness of any future modifications, all tests are

automatically executed using the help script when running make test, including
testing the rest of the compiler. Because the project is hosted on Github [55], these
automatic tests for the JS backend is used to validate correctness with a certain
level of trust in any future modifications. Github Actions performs these testing
steps for all pull requests.
As the Miking language has more features and combinations of features that is
currently not covered by the test suite, a number of additional and more rigorous
tests could be used to further enhance the coverage, density and credibility of the
test suite.
11
Linux manual page: man7.org/linux/man-pages/man1/diff.
62
6.3 Validation
The real proof of implementation correctness comes from compiling as large
and complex software written in Miking as possible and asserting that it has the
same functionality. The ultimate test and validation of the JavaScript backend
is therefore to try to bootstrap the whole Miking compiler (that is written in
Miking) into JavaScript. The term ”bootstrapping“ means to compile a compiler
using itself, and enables the developer to in turn write a new compiler in the
new language. This process is called self-hosting and has the implication that the
language is implemented in itself.
6.3.1 Compiler Coverage
Previously the Miking compiler only produce OCaml code which in turn was
compiled into a native executable binary. From this, many parts was implemented
externally in OCaml for optimization possibilities and included in the Miking
code through it’s FFI towards OCaml. That is why the whole Miking compiler
source code can not be compiled into JavaScript. Because that would require to
re-write those parts in JavaScript, or refactor the Miking compiler source code
and remove those OCaml dependencies. Instead, we go through each part of
the Miking compiler and check if each file can be compiled to JavaScript. This
delimitation gives us an almost complete set of files in the compiler that make
up all use cases of the language and is a sufficiently complex piece of software
that if successfully compiled to JavaScript, increases the confidence that the
backend implementation is correct and is the closest thing we have to proof or
evidence.
6.3.2 Runtime Disparity
The Miking framework has a number of tools, among which interpreters to

evaluate source code directly without producing a binary file. The same exists in
the JavaScript ecosystem, where a number of runtimes and JS engines exists. All
of these interpreters and runtimes have different implementations with various
defects, bugs and specification deviations. This is a common problem among
web browser developed by different companies using different technologies.
For this reason, compatibility tables to show support for the ECMAScript 2015
specification in different browsers and runtimes has been created [1, 29]. Because
of this, ECMAScript 5 introduced a new directive "use strict"; with the purpose
to indicate that the code should be executed in ”strict mode” where for example,
63
you can not use undeclared variables [39].
For this reason, it is impossible to solve all ambiguities in how the same program
is executed in different runtimes, interpreters, browsers or engines. The semantic
of program syntax when reasoning about the code can be equivalent, but due
to the effects of JavaScript engine disparity the program execution, side-effects
and results can never be assured to be exactly the same. This is also trivially
true when comparing the Miking interpreter with execution in let’s say a browser
environment. There will always exist corner cases in compiler and interpreter
implementations that differ.
6.4 Performance Benchmarks

We tested, benchmarked, and compared the compiler using several sample
programs, most taken from the existing standard OCaml compiler backend.
The benchmarking process is composed of a number of steps. Each benchmark

has a main Miking source file with some code that compute some result from
an input number of iterations. Likewise, a manual JavaScript implementation
of the same program with the same behaviour is provided for each benchmark
(manual).
Running benchmark 'factorial' for 80000 iterations...

- Miking interpreter : 1594 ms
- Boot interpreter : 1151 ms
- OCaml ELF (compiled) : 6 ms
- Node (manual) : 127 ms
- Node (compiled) : 107 ms
- Node (compiled+opt) : 94 ms
- Bun (manual) : 124 ms
- Bun (compiled) : 66 ms
- Bun (compiled+opt) : 64 ms
Program code 48: Sample Factorial Benchmark Run
To run and compare all benchmarks, each Miking source file is interpreted
by Boot (built in OCaml) and Miking (Self-hosted) respectively. A compiled
binary executable is also added in the benchmark for each source file, as the
Miking interpreters are slow and the OCaml backend produce high performing
64
executable ELF (native Linux) programs. The source files are also compiled
to JavaScript through the implemented backend targeting Node.js and Bun
(compiled). The compiled files are in turn aggressively optimized (specified by
the --compilation_level=ADVANCED_OPTIMIZATIONS flag) and minimized using
the Google Closure Compiler toolchain [15, 35] (compiled+opt). To properly
compare the efficiency of generated JS programs by the compiler backend, a
manual implementation written by hand is used (manual). An example of these
benchmarks can be seen in figure 48, where some sample output of the factorial
benchmark is given.
6.4.1 Motivation of Benchmark Suite
As described in section 3.3.2, it is important to use programs that include a

variety of features of the Miking language for the benchmarks to yield effective
and accurate results. When selecting the benchmarks to use, much inspiration
was taken from the existing suites developed to test the previous backends. This
fact is brought up in the introduction in chapter 6.4 on performance benchmarks.
Each program in the benchmark test suite are intended to use a wide range of
features. These aspects emphasize on the performance benefit or drawbacks of
each choice of transformation method. The idea is that the compilation of each
feature is fine-tuned and the method is adjusted in future work to achieve better
performance. Some benchmark aspects are described below:
• Factorial – Non-optimized recursion
• Factorial (fast) – Tail call optimized recursion
• Fold List – Intrinsic function usage at high load
• Tree – Non-optimized exponential recursion performance hit
65
6.4.2 Benchmark Results
This section shows the results of the benchmark suit and describes the graphs in
detail. The results of these tests are presented in Figure 6.1. The tests revealed a
significant difference between
Summary of benchmark results

Time (ms)
in logarithmic scale
100000
14820
11176
7013
10000 3737
3144 34333353
1886
1430 1188
1061 985 1036
1000 443
249 237 284 257
170 173 168 159
130 123
104 98 91 102 101
100 60 61
30 28
15
10 5
4
1
factorial factorial fast fold list tree
(80000 iter) (80000 iter) (80000 iter) (80000 iter)
Benchmark
mi eval node (manual) bun (manual)

boot eval node (compiled) bun (compiled)
ocaml (compiled) node (compiled+opt) bun (compiled+opt)
Figure 6.1: Normalized Execution Times of Benchmark Suite
In order to get a more reliable overview of the performance properly, we

implement several benchmark programs that utilize a various range of features
that affect the execution time in different ways.
Each benchmark program was run with a suitable number of iterations, which
most often was around 8,000. The execution times of the Miking source code, the
manual, and the generated JavaScript code is presented in Figure 6.1.
The reason for adding two execution time charts is that some environments
performed significantly better after running the same code a couple of times. In
order to minimize various temporary influences, the result is normalized over
several benchmarking runs (between 5 to 10 times) to avoid cache effects for
example. This is the result presented in figure 6.1.
Generally, the JavaScript runtimes are faster compared to the Miking interpreters
mi eval and boot eval. Most outstanding is the run time of the compiled
OCaml code, this is a native binary file compiled by the OCaml backend. Of
the JavaScript runtimes, running Bun on the manual JS code takes far less
time than the code generated by the compiler (see figure 6.1). This is probably
66
thanks to a combination of JIT-compilation and heavy optimizations. The code
generated by the JavaScript compiler backend is constructed using mostly relying
on expressions instead of on statements, and is supposedly harder for Bun to find
optimizations for. On the other hand, running the program a single time in a fresh
environment with a cold start for Bun, the manual implementation sometimes
performed worse than the compiled code.
6.4.3 Code Efficiency
One important distinction between the manual and compiled JavaScript

programs in the benchmarks is that the manual implementation uses ”optimal”
code to compute a result, essentially meaning that the code is written as compact
and minimal as possible, in contrast to the compiled JS code that my include more
extra code. This is the main reason why compiled JavaScript code perform worse
and the solution would be to detect direct self recursion and translate it to loops
instead. Making a fair comparison with manually written JavaScript is difficult
and the compiler back-end is unlikely to match the performance of heavily tuned
programs [82].
On the upside, we can conclude that even if the compiled code is optimized using
advance state of the art technologies, no immediate performance boost is gained.
Therefore, it seems reasonable to claim that the generated code is efficient by
default.
6.4.4 Statistical Result
Our experiments from the selected benchmark programs show that compiled
JavaScript code compares favorably and is consistently faster than interpreted
Miking code. The performance results in figure 6.1 display the execution time for
all runtime environments, but a closer comparison between manual and compiled
code is more interesting for potential users.
When comparing the results from Node.js, the compiled JavaScript code performs
about the same as for the manual implementation (within ±10% variation). On
the contrary, an optimized version of the compiled code is approximately 1.35
times faster than a manual JS implementation.
A fascinating feature of Bun that stands out in the statistics is its ability to optimize
a direct and clear classical implementation of a program that uses basic JavaScript
constructs. From figure 6.1 it can be seen that the manual implementations in Bun
67
perform significantly better in some cases (up to ∼24 times faster) or at least as
good as the compiled code. This is in contrast to Node.js, where the manual and
generated programs performed equivalently.
6.4.5 Hardware and Environment
This section explains the setup and environment under which the tests and
benchmarks were performed.
The computer hardware used for all tests and benchmarks include an AMD Ryzen
7 5800X processor with 32 GB (2 x 16 GB) 3200 MHz DDR4 RAM. Computer
processor speed of 4.7 GHz running the Windows 11 operating system with a 750
W Power Supply.
More than one JavaScript runtime (VM) is used to evaluate the different execution
times. We used the Node.js (version 16.14.2) and Deno (version 1.17.3) runtime
implementations, both based on the V8 engine from Google [22, 59, 80]. In
addition to this, the more recent and modern JS runtime Bun (version 0.1.10)
was also used. Bun is built on the JavaScriptCore engine developed by Apple [11,
40]. V8 is the JavaScript engine commonly used by Node.js, Deno, Chrome and
Chromium web browsers, while JavaScriptCore is mainly part of Apple’s WebKit
used in Safari and iOS [84].
68
7 Conclusion
This thesis project has given enthralling insights into the nature of compilers and
programming languages. To develop and implement a JavaScript backend for
the Miking compiler have provided great knowledge and practice useful for future
work.
The main contribution of this work has been to demonstrate that compiling
a functional programming language to JavaScript is feasible. This thesis
achieved the goals and satisfied the problem requirements correctly and efficiently
by successfully designing and implementing a compiler backend capable of
producing JavaScript code within the performance range of hand written code,
including language features from the ECMAScript 2015 (ES6) standard supported
by all major browsers and native runtime environments.
The most challenging part of the thesis work was to figure out the compilation
process for recursive functions with cyclical dependencies. Finding existing
literature and previous research on this topic was difficult and not well
documented. Because of this, the chapter on tail call optimization 5.4 goes more
in-depth on the transformations, steps and processes used by the implemented
compiler backend. This is the second contribution to the field of research withing
compiler construction and is useful when translating functional languages relying
heavily on recursion to imperative code without the need to untangle mutual
recursive functions.
In this thesis, translation problems and paradigmatic differences has been dealt
with swiftly using advanced compilation of pattern matching and recursive
functions utilizing a trampolining technique.
I’m proud to have created a high quality, scalable software engineering project.
The final compiler including the JavaScript backend can be found in the official
repository for the Miking project [55].
69
7.1 Future Work
There are a number of drawbacks with the current solution that can be addressed
in future work.
7.1.1 Statements
First of all, the backend mainly produce expression based code which is not as
easily to optimize by external tools and runtimes. Instead, the AST should be
extended to support statements and let the compiler generate nodes of type JSStmt
instead of JSExpr.
7.1.2 Foreign Function Interface
The current backend only have partial support for foreign function interfaces
through the standard library, as it is currently not possible for used defined
FFI:s.
At the moment, there exists a library allowing Miking code to interact with
the browsers client DOM when compiling to JavaScript targeting the web
environment. Future work will put into adding more functions to this module
and extending the range of browser APIs such as asynchronous code, local storage,
fetching data over the internet, etc.
It would also be nice if popular JavaScript libraries and frameworks could be

ported to Miking such as JQuery and React.
7.1.3 Bootstrapping in JavaScript
As large parts of the current Miking compiler is dependant on a lexer and parser
written i OCaml, it has not been possible to fully compile the complete compiler
itself. One task for future work would be to compile the self-hosted Miking
compiler to JavaScript through the new backend. This would enable the Miking
compiler to be hosted online directly in the browser and interacted with through
client-side JavaScript. An online playground or integrated editor could be built
on top of this, thus lowering the bar for new developers to get started with using
the Miking workbench.
70
7.2 Final Words
I am extremely grateful for this chance to delve into this area of research that I
have been trying to get into for a long time. This has been a perfect opportunity
for me to learn more about compilers and programming languages. It has been
an honor to work closely with the Miking research group and take part in the
development process of an impressive and potentially very useful research project.
I wish to continue to contribute to the development and success of Miking in the
future.
Considering the ambition and scope of this thesis project, I am very pleased
with the result. This thesis project has allowed me to demonstrate the ability
to design and implement a backend system for an existing compiler that meets
the requirements of the problem statement. I have also demonstrated the ability
to use the tools and techniques that are available to me to solve problems
accordingly, as well as expand on previous ideas and generalize them in a good
way.
My goal is to continue to develop and learn so that at some point in the future, I
can contribute something more meaningful and impactful to the industry and in
the research field of programming languages.
71
72
References
[1] ”es6” | Can I use... Support tables for HTML5, CSS3, etc. URL: https://
caniuse.com/?search=es6 (visited on 08/28/2022).
[2] [GWT] -. URL: https://www.gwtproject.org/ (visited on 09/01/2022).
[3] Addition (+) - JavaScript | MDN. URL: https://developer.mozilla.org/
en- US/docs/Web/JavaScript/Reference/Operators/Addition (visited
on 08/16/2022).
[4] Anderson, Christopher, Giannini, Paola, and Drossopoulou, Sophia.
“Towards Type Inference for JavaScript”. In: ECOOP 2005 - Object-
Oriented Programming. Ed. by Andrew P. Black. Lecture Notes in
Computer Science. Berlin, Heidelberg: Springer, 2005, pp. 428–452. ISBN:
978-3-540-31725-8. DOI: 10.1007/11531142_19.
[5] Anderson, Christopher Lyon. Type inference for javascript. 2003.
[6] appcypher. Awesome WebAssembly Languages. original-date: 2017-12-
15T11:24:02Z. Feb. 27, 2022. URL: https : / / github . com / appcypher /
awesome-wasm-langs (visited on 02/27/2022).
[7] Baranov, Valeriy. Safe Recursion with Trampoline in JavaScript. Medium.
May 11, 2020. URL: https : / / levelup . gitconnected . com / safe -
recursion- with- trampoline- in- javascript- dbec2b903022 (visited on
05/23/2022).
[8] Benoit. What is a trampoline function? Stack Overflow. July 11, 2013.
URL: https : / / stackoverflow . com / q / 189725 / 5698805 (visited on
05/06/2022).
[9] Breugel, Franck van. “An introduction to metric semantics: operational
and denotational models for programming and specification languages”.
In: Theoretical Computer Science 258.1 (May 6, 2001), pp. 1–98. ISSN:
0304-3975. DOI: 10.1016/S0304-3975(00)00403-5. URL: https://www.
sciencedirect.com/science/article/pii/S0304397500004035 (visited
on 04/20/2022).
[10] Broman, David. “A vision of miking: interactive programmatic modeling,
sound
language composition, and self-learning compilation”. In: Proceedings of
the 12th ACM SIGPLAN International Conference on Software Language
Engineering. SLE 2019. New York, NY, USA: Association for Computing
73
Machinery, Oct. 20, 2019, pp. 55–60. ISBN: 978-1-4503-6981-7. DOI: 10.
1145 / 3357766 . 3359531. URL: https : / / doi . org / 10 . 1145 / 3357766 .
3359531 (visited on 12/03/2021).
[11] Bun is a fast all-in-one JavaScript runtime. URL: https : / / bun . sh/
(visited on 08/26/2022).
[12] Call stack. In: Wikipedia. Page Version ID: 1094890277. June 25, 2022.
URL: https: / /en. wikipedia. org/w /index. php?title =Call _stack&
oldid=1094890277 (visited on 08/20/2022).
[13] Carrington, David. “CHAPTER 10 SOFTWARE ENGINEERING TOOLS
AND METHODS”. In: (2001), p. 10.
[14] Chandra, Satish et al. “Type inference for static compilation of JavaScript”.
In: Proceedings of the 2016 ACM SIGPLAN International Conference on
Object-Oriented Programming, Systems, Languages, and Applications.
SPLASH ’16: Conference on Systems, Programming, Languages, and
Applications: Software for Humanity. Amsterdam Netherlands: ACM,
Oct. 19, 2016, pp. 410–429. ISBN: 978-1-4503-4444-9. DOI: 10 . 1145 /
2983990.2984017. URL: https://dl.acm.org/doi/10.1145/2983990.
2984017 (visited on 08/16/2022).
[15] Closure Compiler. Google Developers. URL: https : / / developers .
google.com/closure/compiler (visited on 02/28/2022).
[16] Closure Compiler Service. URL: https://closure- compiler.appspot.
com/home (visited on 02/28/2022).
[17] CommonJS. In: Wikipedia. Page Version ID: 1111866230. Sept. 23, 2022.
URL: https://en.wikipedia.org/w/index.php?title=CommonJS&oldid=
1111866230 (visited on 10/27/2022).
[18] CommonJS: JavaScript Standard Library. URL: https://www.commonjs.
org/ (visited on 10/27/2022).
[19] Comparison of parser generators. In: Wikipedia. Page Version ID:
1089988360. May 26, 2022. URL: https://en.wikipedia.org/w/index.
php ? title = Comparison _ of _ parser _ generators & oldid = 1089988360
(visited on 06/13/2022).
[20] Currying. In: Wikipedia. Page Version ID: 1075077790. Mar. 3, 2022.
URL: https://en.wikipedia.org/w/index.php?title=Currying&oldid=
1075077790 (visited on 05/25/2022).
74
[21] Dean, Walter. “Recursive Functions”. In: The Stanford Encyclopedia of
Philosophy. Ed. by Edward N. Zalta. Winter 2021. Metaphysics Research
Lab, Stanford University, 2021. URL: https : / / plato . stanford .
edu / archives / win2021 / entries / recursive - functions/ (visited on
08/15/2022).
[22] Deno - A modern runtime for JavaScript and TypeScript. DenoLand. URL:
https://deno.land/ (visited on 04/06/2022).
[23] Destructuring assignment - JavaScript | MDN. URL: https : / /
developer . mozilla . org / en - US / docs / Web / JavaScript / Reference /
Operators/Destructuring_assignment (visited on 05/27/2022).
[24] Documentation - Type Inference. URL: https : / / www . typescriptlang .
org/docs/handbook/type-inference.html (visited on 08/16/2022).
[25] Domoszlai, Laszlo and Plasmeijer, Rinus. “COMPILING HASKELL TO
JAVASCRIPT THROUGH CLEAN’S CORE”. In: (), p. 26.
[26] ECMA-262. Ecma International. URL: https : / / www . ecma -
international . org / publications - and - standards / standards / ecma -
262/ (visited on 11/24/2022).
[27] ECMA, TC39 Meeting Notes 2016-05-24. original-date: 2019-11-
15T08:32:10Z. May 2, 2022. URL: https : / / github . com / tc39 / notes /
blob/791545c497cf595015475a822496959d379fb032/meetings/2016-05/
may-24.md (visited on 05/04/2022).
[28] “ECMAScript 2015 Language Specification”. In: (2015), p. 566. URL:
https://262.ecma-international.org/6.0/.
[29] ECMAScript Harmony. URL: https : / / esdiscuss . org / topic /
ecmascript-harmony (visited on 11/06/2022).
[30] ECMAScript Pattern Matching. original-date: 2017-07-03T21:21:23Z.
Aug. 20, 2022. URL: https : / / github . com / tc39 / proposal - pattern -
matching (visited on 08/20/2022).
[31] ECMAScript-262 1st Edition June 1997. June 1997. URL: https://www.
ecma-international.org/wp-content/uploads/ECMA-262_1st_edition_
june_1997.pdf.
75
[32] Elsman, Martin. “SMLtoJs: hosting a standard ML compiler in a web
browser”. In: Proceedings of the 1st ACM SIGPLAN international
workshop on Programming language and systems technologies for
internet clients. PLASTIC ’11. New York, NY, USA: Association for
Computing Machinery, 2011, pp. 39–48. ISBN: 978-1-4503-1171-7. DOI:
10.1145/2093328.2093336. URL: https://doi.org/10.1145/2093328.
2093336 (visited on 04/13/2022).
[33] Function model. In: Wikipedia. Page Version ID: 1078157690. Mar. 20,
2022. URL: https://en.wikipedia.org/w/index.php?title=Function_
model&oldid=1078157690 (visited on 05/24/2022).
[34] Gantt chart. In: Wikipedia. Page Version ID: 1084255741. Apr. 23, 2022.
URL: https://en.wikipedia.org/w/index.php?title=Gantt_chart&
oldid=1084255741 (visited on 05/24/2022).
[35] Google Closure Compiler. original-date: 2014-04-16T15:30:36Z. Feb. 28,
2022. URL: https://github.com/google/closure-compiler (visited on
02/28/2022).
[36] Harband,
Jordan and Smith, Kevin. ECMAScript 2015 Language Specification. In:
URL: https://262.ecma-international.org/6.0/.
[37] Is Source Code Intellectual Property? Stop Source Code Theft. Section:
Legal Guides. Sept. 28, 2018. URL: https : / / www . stop - source - code -
theft . com / is - source - code - intellectual - property/ (visited on
09/10/2022).
[38] Ivan Plyusnin. Functional programming design patterns by Scott
Wlaschin. Aug. 30, 2015. URL: https : / / www . youtube . com / watch ? v =
E8I19uA-wGY (visited on 05/27/2022).
[39] JavaScript ”use strict”. URL: https : / / www . w3schools . com / js / js _
strict.asp (visited on 08/28/2022).
[40] JavaScriptCore | Apple Developer Documentation. URL: https : / /
developer . apple . com / documentation / javascriptcore (visited on
08/26/2022).
[41] John Resig - ECMAScript Harmony. URL: https://johnresig.com/blog/
ecmascript-harmony/ (visited on 11/06/2022).
[42] Js_of_ocaml. URL: http://ocsigen.org/js_of_ocaml/latest/manual/
overview (visited on 05/06/2022).
76
[43] JSON. In: Wikipedia. Page Version ID: 49913207. Dec. 7, 2021. URL:
https://sv.wikipedia.org/w/index.php?title=JSON&oldid=49913207
(visited on 08/19/2022).
[44] JSON. URL: https : / / www . json . org / json - en . html (visited on
08/19/2022).
[45] Khan, Faiz et al. “Using JavaScript
and WebCL for numerical computations: a comparative study of native and
web technologies”. In: ACM SIGPLAN Notices 50.2 (Oct. 14, 2014), pp. 91–
102. ISSN: 0362-1340. DOI: 10 . 1145 / 2775052 . 2661090. URL: https :
//doi.org/10.1145/2775052.2661090 (visited on 12/03/2021).
[46] Kruchten, Philippe. “Architectural Blueprints—The “4+1” View Model of
Software Architecture”. In: (), p. 15.
[47] Krump, Matt. Mutual Recursion and Trampoline. matthewkrump.com.
May 25, 2017. URL: https : / / matthewkrump . com / 2017 - 05 - 25 -
trampoline/ (visited on 05/25/2022).
[48] Lambda World. Laziness, trampolines, monoids and other functional
amenities - Mario Fusco. Nov. 3, 2015. URL: https://www.youtube.com/
watch?v=dBqTemTyB7o (visited on 06/10/2022).
[49] Little, Christopher, Gray, Kathryn E, and Owens, Scott. “JSTyper: Type
inference for JavaScript”. In: (), p. 12.
[50] Loitsch, Florian and Serrano, Manuel. “Compiling Scheme to JavaScript”.
In: (), p. 10.
[51] Loitsch, Florian and Serrano, Manuel. “Hop Client-side Compilation”. In:
(), pp. 15–18.
[52] Macro (computer science). In: Wikipedia. Page Version ID: 1107079210.
Aug. 28, 2022. URL: https://en.wikipedia.org/w/index.php?title=
Macro_(computer_science)&oldid=1107079210 (visited on 09/01/2022).
[53] Metaprogramming. In: Wikipedia. Page Version ID: 1102889553. Aug. 7,
2022. URL: https : / / en . wikipedia . org / w / index . php ? title =
Metaprogramming&oldid=1102889553 (visited on 09/01/2022).
[54] Michel, Thiery. Understanding Recursion, Tail Call and Trampoline
Optimizations. URL: https : / / marmelab . com / /blog / 2018 / 02 / 12 /
understanding-recursion.html (visited on 05/23/2022).
77
[55] Miking GitHub repository. original-date: 2017-08-07T12:32:00Z. Dec. 3,
2021. URL: https : / / github . com / miking - lang / miking (visited on
12/07/2021).
[56] Miking Stdlib - JS Compile. original-date: 2017-08-07T12:32:00Z. May 11,
2022. URL: https : / / github . com / miking - lang / miking / blob /
4fdbd7890020edcd772e9d6cebe6f03caff7c746 / stdlib / javascript /
compile.mc (visited on 05/27/2022).
[57] ML (programming language). In: Wikipedia. Page Version ID:
1106423335. Aug. 24, 2022. URL: https://en.wikipedia.org/w/index.
php?title=ML_(programming_language)&oldid=1106423335 (visited on
09/01/2022).
[58] Node.js. ECMAScript 2015 (ES6) and beyond. Node.js. URL: https : / /
nodejs.org/en/docs/es6/ (visited on 05/16/2022).
[59] Node.js. Node.js. Node.js. URL: https : / / nodejs . org / en/ (visited on
02/27/2022).
[60] Nyberg, Oskar. “A Compiler from CakeML to JavaScript”. In: (2018), p. 62.
URL: https://odr.chalmers.se/bitstream/20.500.12380/255702/1/
255702.pdf.
[61] On Recursion, Continuations and Trampolines - Eli Bendersky’s website.
URL: https : / / eli . thegreenplace . net / 2017 / on - recursion -
continuations-and-trampolines/ (visited on 05/24/2022).
[62] Pattern Matching. URL: https://tc39.es/proposal-pattern-matching/
(visited on 08/20/2022).
[63] replit. The collaborative browser based IDE. replit. URL: https : / /
replit.com/ (visited on 02/27/2022).
[64] RISK IDENT. Stacksafe functions with trampolines. Aug. 13, 2018. URL:
https : / / www . youtube . com / watch ? v = jLyeSYfNcAY (visited on
06/10/2022).
[65] Riva, Michele. ES6 Destructuring Assignment. openmind. June 23, 2019.
URL: https : / / medium . com / openmindonline / js - monday - 14 -
destructuring-assignment-934018a6e04d (visited on 08/20/2022).
[66] Riva, Michele. Pattern Matching Proposal. openmind. June 23, 2019.
URL: https://medium.com/openmindonline/js- monday- 15- pattern-
matching-proposal-cb978ba0b9d9 (visited on 08/20/2022).
78
[67] Schinz, Michel and Odersky, Martin. “Tail Call Elimination on the Java
Virtual Machine”. In: Electronic Notes in Theoretical Computer Science
59 (Nov. 1, 2001), pp. 158–171. DOI: 10.1016/S1571-0661(05)80459-1.
[68] Software Engineering Features - Models, Methods, Tools, Standards, and
Metrics - SEBoK. URL: https://www.sebokwiki.org/wiki/Software_
Engineering_Features_-_Models,_Methods,_Tools,_Standards,_and_
Metrics (visited on 05/24/2022).
[69] Spread syntax (...) - JavaScript | MDN. URL: https : / / developer .
mozilla . org / en - US / docs / Web / JavaScript / Reference / Operators /
Spread_syntax (visited on 05/26/2022).
[70] Standard ML. In: Wikipedia. Page Version ID: 1104658462. Aug. 16, 2022.
URL: https://en.wikipedia.org/w/index.php?title=Standard_ML&
oldid=1104658462 (visited on 09/01/2022).
[71] Tail recursion, but modulo cons. URL: https://jfmengels.net/modulo-
cons/ (visited on 06/17/2022).
[72] Tarditi, David, Lee, Peter, and Acharya, Anurag. “No assembly required:
compiling standard ML to C”. In: ACM Letters on Programming
Languages and Systems 1.2 (June 1, 1992), pp. 161–177. ISSN: 1057-4514.
DOI: 10.1145/151333.151343. URL: https://doi.org/10.1145/151333.
151343 (visited on 05/06/2022).
[73] The JavaScript Call Stack - What It Is and Why It’s Necessary.
freeCodeCamp.org. Jan. 11, 2018. URL: https : / / www . freecodecamp .
org/news/understanding-the-javascript-call-stack-861e41ae61d4/
(visited on 08/20/2022).
[74] Trampoline (computing). In: Wikipedia. Page Version ID: 1082481996.
Apr. 13, 2022. URL: https://en.wikipedia.org/w/index.php?title=
Trampoline_(computing)&oldid=1082481996 (visited on 05/06/2022).
[75] Trampolines (GNU Compiler Collection (GCC) Internals). URL: https :
/ / gcc . gnu . org / onlinedocs / gccint / Trampolines . html (visited on
05/06/2022).
[76] Trampolining in R. URL: https://cran.microsoft.com/snapshot/2022-
04-10/web/packages/trampoline/vignettes/tampolining.html (visited
on 05/06/2022).
79
[77] Trend, William. St Andrews Algol to Javascript compiler project. Jan. 3,
2016. 50 pp. URL: https : / / info . cs . st - andrews . ac . uk / student -
handbook/files/project-library/old/sh/Trend.pdf.
[78] Try It Online. URL: https://tio.run/# (visited on 02/27/2022).
[79] TypeError - JavaScript | MDN. URL: https://developer.mozilla.org/
en - US / docs / Web / JavaScript / Reference / Global _ Objects / TypeError
(visited on 11/27/2022).
[80] V8 JavaScript engine. URL: https://v8.dev/ (visited on 08/26/2022).
[81] vanessalevesque. “Ethics in Sustainability”. In: (). Book Title: Sustainability
Methods and Perspectives. URL: https : / / sustainabilitymethods .
pressbooks . com / chapter / ethics - in - sustainability/ (visited on
09/09/2022).
[82] Vouillon, Jérôme and Balat, Vincent. “From bytecode to JavaScript: the
Js_of_ocaml compiler”.
In: Software: Practice and Experience 44.8 (Feb. 26, 2013). _eprint:
https://onlinelibrary.wiley.com/doi/pdf/10.1002/spe.2187, pp. 951–972.
ISSN: 1097-024X. DOI: 10 . 1002 / spe . 2187. URL: https : / /
onlinelibrary . wiley . com / doi / abs / 10 . 1002 / spe . 2187 (visited on
12/03/2021).
[83] WebAssembly. URL: https : / / webassembly . org/ (visited on
02/27/2022).
[84] WebKit. WebKit. URL: https://webkit.org/ (visited on 08/28/2022).
[85] What is WebAssembly? How WebAssembly Works (with Examples).
Articles for Developers Building High Performance Systems. Sept. 5, 2019.
URL: https : / / blog . stackpath . com / webassembly/ (visited on
02/27/2022).
[86] Work Breakdown Structure. workbreakdownstructure.com. URL: https:
//www.workbreakdownstructure.com (visited on 05/24/2022).
[87] Work breakdown structure. In: Wikipedia. Page Version ID: 1081371044.
Apr. 7, 2022. URL: https://en.wikipedia.org/w/index.php?title=
Work_breakdown_structure&oldid=1081371044 (visited on 05/24/2022).
[88] Yin, Robert K. Case study research: design and methods. 4th ed. Applied
social research methods v. 5. Los Angeles, Calif: Sage Publications, 2009.
219 pp. ISBN: 978-1-4129-6099-1.
80
81
TRITA-EECS-EX-2022:883
www.kth.se

Formation Js Back End

Uploaded by

Document Informationclick to expand document informationformation java script pour back end

Document Informationclick to expand document information

Copyright:

Available Formats

Formation Js Back End

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Formation Js Back End

Uploaded by

Copyright:

Available Formats

DEGREE PROJECT IN TECHNOLOGY,

FIRST CYCLE, 15 CREDITS

KTH ROYAL INSTITUTE OF TECHNOLOGY

In this report, development challenges, implementation methods, and techniques

I denna rapport diskuteras och utvärderas även utvecklingsutmaningar,

Stockholm, November 2022

Place for Project

List of Program Code x

Abbreviation Meaning Page

The Miking framework and language workbench will be capable of producing

The Miking framework is based on a core functional meta language, Miking

Due to the growth of browser-based applications, JavaScript is used everywhere

A recent trend among modern programming languages is hosting online

The objective of this thesis is to implement compilation support for targeting

Likewise, pattern matching expressions should be compiled correctly. The last

1.6 Benefits, Ethics and Sustainability

The delimitations therefore become a non-formal report with documentation for

2.1 Related Work

2.1.1 SMLtoJs: Hosting a Standard ML Compiler in a Web

This paper presents an optimizing compiler from Standard ML to JavaScript

2.1.2 St Andrews Algol to JavaScript compiler project

The js_of_ocaml project implements an OCaml bytecode to the JavaScript

2.1.4 Hop Client-Side Compilation

Hop is a language that “aims to replace HTML, JavaScript, and server-side

2.1.5 A Compiler from CakeML to JavaScript

This master thesis report presents a complete source-to-source compiler from

3.1 Research Method

Another aspect is to compare the results based on the set requirements:

3.2 Software Engineering Process

3.2.1 Project Plan

Research Design Implementation Evaluation

Supported ECMAScript Convert constants to

Compile pattern matching

Figure 3.1: Work Breakdown Structure

3.3 Testing and Validation

3.3.1 Unit Testing

Benchmark runtimes are collected, normalized over multiple runs, visualized

4.1 Pipeline Overview

Input Source code List of tokens MExpr AST

Compile MExpr Generate

Output JS source Third-Party

Figure 4.1: Code Flow of Compilation Process

The compiler from MExpr to JSExpr computes a transformed equivalent internal

Parsed Final Generated

Figure 4.2: Functional Model of Compilation Process

The model above (Figure 4.2) takes on a functional modeling perspective

All ECMAScript specifications are strictly backward compatible, allowing

Although the most recent version of ECMAScript would be tempting to target, it

By utilizing the features provided by the ES6 version of JavaScript, it is possible to

4.3.1 Variable Declaration

1 var a = 1; // Mutable, nearest global or function scope

Program code 1: Variable declaration and initialization

1 let lst = [1, 2, 3]; // Allocated list

Program code 2: Allocating and freeing data

JavaScript provides lambda expressions called arrow functions. A modern

Another difference is that arrow functions support either a single expression

1 function a(x) { return x; } // Named function