summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorEkaitz Zarraga <ekaitz@elenq.tech>2024-09-02 23:22:11 +0200
committerEkaitz Zarraga <ekaitz@elenq.tech>2024-09-02 23:22:11 +0200
commit4eec39aea9771fa9fede5fdc2e0a00fedce716f3 (patch)
tree8e1b99bc9683154cf35fd14babc999c0b76b86fb
parent6cb36df95d11fa8e888c9e61168714dc3ff71c05 (diff)
LOCO: repurposing to simplification
-rw-r--r--papers/LOCO-24/contents.latex187
1 files changed, 96 insertions, 91 deletions
diff --git a/papers/LOCO-24/contents.latex b/papers/LOCO-24/contents.latex
index 76d51a1..45f398c 100644
--- a/papers/LOCO-24/contents.latex
+++ b/papers/LOCO-24/contents.latex
@@ -88,7 +88,8 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom }
%% The "title" command has an optional parameter,
%% allowing the author to define a "short title" to be used in page headers.
-\title{A computing system that embraces the language}
+\title{Simplifying modern computing by embracing the language}
+\subtitle{A case study using Scheme}
%%
%% The "author" command and its associated commands are used to define
@@ -173,20 +174,20 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom }
by any industry are oftentimes driven by previous decisions taken in the same
subject. Specifically, the computing industry, arguably due to its rapid
emergence, has been heavily influenced by previous technology and
- \textit{backwards compatibility}. Reviewing the most influential ideas of
- computing one can obtain valuable information to be able to criticise current
- computing systems and propose pioneering alternatives.
+ \textit{backwards compatibility}.
+%% TODO: remove this and put some personal computing instead?
\subsection{Von Neumann model}
The von Neummann model introduced in 1945 proposes a general purpose device
consisting of a \textit{Central Processing Unit} (CPU) and a \textit{Store}.
The \textit{Store} is often implemented as a \textit{Random Access Memory}
- (RAM or, simply, \textit{memory}), which stores data in bytes, each of them
- with an \textit{address}, in a tabulated fashion.
+ (RAM or, simply, \textit{memory}).
In the von Neumann model the data and the program are both written to and
- read from the \textit{Store}. This arrangement had carried criticism over the
- years but it is also a fundamental part of how modern Operating Systems work.
+ read from the \textit{Store}. This fact imposes limitations in any design
+ that aims to have direct access to memory and multitasking, as any running
+ program could read and manipulate other running program's, and even
+ manipulate its behavior, overwriting the program itself.
\subsection{Unix's heritage}
\epigraph{
@@ -200,7 +201,6 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom }
and other objects and a powerful \textit{shell} that facilitates program
composition.
-\subsubsection{The Kernel}
In the Unix model, the Kernel, the core of the Operating System, is
responsible for managing the hardware resources. For that job, it uses
several concepts that systems designers and programmers are familiarized with
@@ -208,27 +208,22 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom }
\textit{processes}, \textit{shared-memory threads}, \textit{hierarchical
filesystems} and \textit{system calls}.
-\subsubsection{The Shell}\label{shell}
- The shell is run as a userspace program that has the hability to launch other
- programs using an outdated fork+exec mechanism that encourages memory
- overshoot\cite{fork:Baumann}.
- The shell in Unix systems is optimized for text processing as, in McIlroy's
- words, \textit{"text streams [are] the universal interface"}
- \cite{QuarterCenturyUnix:Salus}.
+ The \textit{shell} is run as a userspace program that has the ability to
+ launch other programs using an outdated fork+exec mechanism that encourages
+ memory overshoot\cite{fork:Baumann}. The shell in Unix systems is optimized
+ for text processing as, in McIlroy's words, \textit{"text streams [are] the
+ universal interface"} \cite{QuarterCenturyUnix:Salus}.
+
+ Userspace programs are loaded in and given access to \textit{virtual memory},
+ and they can only run the \textit{unprivileged} subset of the CPU
+ instructions. For restricted operations, programs need to call the
+ \textit{Kernel} using a \textit{system-call} that can be accepted or rejected
+ by the latter, according to \textit{permissions} or resource availability. In
+ order to achieve multitasking, many programs can be loaded in memory
+ (\textit{processes}) simultaneously and the \textit{Kernel}
+ \textit{schedules} which of the them will run at a given moment in time.
+
-%\subsubsection{Userspace programs}
-%
-% Programs are loaded in and given access to \textit{virtual memory}, and they
-% can only run a subset of the CPU instructions of the machine, the
-% \textit{unprivileged} set. For restricted operations, programs need to call
-% the \textit{Kernel} using a \textit{system-call} that can be accepted or
-% rejected by the latter, according to some rules for \textit{permissions} or
-% resource availability. In order to achieve multitasking, many programs can be
-% loaded in memory (\textit{processes}) simultaneously and the \textit{Kernel}
-% \textit{schedules} which of the them will run at a given moment in time and
-% pauses the rest accordingly.
-%
-%
% \paragraph{Concurrency}
% If programs need to operate concurrently they can create many
% \textit{processes} or use \textit{threads}. A \textit{thread} is a
@@ -262,87 +257,89 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom }
order to facilitate \textit{system-calls} and \textit{interrupt} and
\textit{virtual memory} control.
- Contrary to what one could expect, most of the improvements in the processor
- architectures come from specialization for the said case, and not from
- generalization.
-
- Modern processors are heavily optimized for Operating Systems that follow the
+ Contrary to what one could expect, improvements in the processor
+ architectures come from specialization, instead of generalization, making
+ processors heavily optimized machines for Operating Systems that follow the
Unix model (including MS Windows), and a memory layout that resembles that of
a \textit{C-like} program, which also comes from the days of Unix
\cite{GeneralPurposeProcessor:Chisnall}, reducing the chance for other
paradigms to succeed.
-\section{Embracing the language}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- If a computing system aims to embrace the language, it needs to make a proper
- analysis of what a programming language is and how people make use of the
- programming facilities that computing systems provide.
+\section{Simplification enables optimization}
- From the perspective of Operating System and Programming Language
- implementations, there is a duplication of work. Embracing a language does
- not only eliminate the duplication but opens a new opportunity for
- interesting optimizations to flourish. \cite{MIMOSA:Yvon}
+ Choosing a language and committing to it enables aggressive simplification of
+ the computing systems, taking advantage of that, many research areas open,
+ most of them confront Unix's heritage and modern computing but which could
+ provide a powerful but simple set of constructs that allow to create simple
+ computers that can be maintained by an individual.
-\subsection{Choosing Scheme}
- The \textit{Lisp} family of languages have proven to be flexible and powerful
- for system design \cite{LispMachine:Greenblatt} and particularly
- \textit{Scheme} has a long history of research in language and CPU design
- (lambda papers).
+\subsection{Embracing the language: Scheme}
+ This makes \textit{Scheme} and its possible extensions a good choice to
+ please \textit{vernacular programmers}\cite{MythsPL:Shaw}, that comprehend a
+ good compromise between available technical literacy from the user side and a
+ wide audience to benefit.
\textit{Scheme} is a simple language, with a minimal standard, but that
enables a huge level of abstraction thanks to its minimal but powerful core
concepts which are also present in mainstream programming languages today
(Python, JavaScript) reducing the friction with seasoned programmers.
+ The \textit{Lisp} family of languages have proven to be flexible and powerful
+ for system design \cite{LispMachine:Greenblatt} and particularly
+ \textit{Scheme} has a long history of research in language and CPU design
+ (lambda papers).
+
The nature of the Lisp family of languages also makes them suitable as file
formats (sxml) for storage and configuration files, writing DSLs (language
oriented programming), or extending the language (GOOPS, WISP) to the users'
needs (Typed Racket, Kawa). This eliminates the need to rely on unstructured
- text \ref{shell}.
+ text.
- This makes \textit{Scheme} and its possible extensions a good choice to
- please \textit{vernacular programmers}\cite{MythsPL:Shaw}, that comprehend a
- good compromise between available technical literacy from the user side and a
- wide audience to benefit.
+\subsection{An Operating System that embraces the language}
-\subsection{Research opportunities in the OS}
+ An Operating System that embraces the language becomes a bare metal
+ interpreter, eliminating the duplication of tasks present in Unix operating
+ systems \cite{MIMOSA:Yvon}. The Operating System is just accessible in the
+ runtime environment of the programs. \textit{System calls} become
+ \textit{procedure calls}. The \textit{Shell} is a system \textit{REPL}, an
+ interactive environment for programming that exposes Operating System's
+ facilities.
- The reduction of the kernel to a kernel-interpreter eliminates the
- duplication of tasks, while also allowing to use higher level concepts in a
- lower-level structure, like the operating system. \textit{System calls}
- become \textit{function calls}.
+\subsubsection{Capability based security "lambda-style"}
+ Most modern computers do not have more than a single user,
+ but they preserve an antique user management system, inherited from Unix,
+ recycled for program permission.
+ 3L \cite{3L:Hintz} explored an OS where permission control is reduced to
+ \textit{environments} with access to a limited set of bindings
+ \cite{securityKernelLambda:Rees}. A program can only access the bindings
+ provided by the system, which also facilitates fine grained control letting
+ the user replace system bindings by ad-hoc versions when needed.
\subsubsection{Managed memory}
- Virtual memory is an attempt to isolate programs from each other but it is a
+ Virtual memory is an attempt to isolate programs from each other and provide
+ a permission system on top of a flawed von Neumann model but it is a
leaky abstraction that can be exploited\cite{SpectreMeltdown:HillMasters}.
Removing direct access to memory, replacing it with managed memory, removes
- the need of virtual memory.
+ the need of virtual memory and decouples underlying implementations from user
+ programs.
-\subsubsection{No threads/processes but tasks}
- Unix-style parallelism, reinforced by modern \textit{multi-core} CPU design,
- focuses on the implementation rather than the usage. Browser-like task design
- based on Coroutines/Generators/Asynchronous calls. No shared-memory threads,
- as they are hard to reason about\cite{Threads:Lee}.
-
-\subsubsection{Capability based security "lambda-style"}
- Reduces the amount of permission issues inherited from von Neumann style and
- Unix. No \textit{user} support. [3L]
+\subsubsection{Concurrency}
+ Unix-style concurrency, reinforced by modern \textit{multi-core} CPU design
+ and threads, is hard to reason about\cite{Threads:Lee}. A multitasking system
+ can be approached in terms of \textit{Scheme}'s
+ \textit{continuations}\cite{ContinuationsConcurrency:Hieb}.
-\subsubsection{Filesystem}
- This allows for new paradigms in Filesystem design.
-\subsection{Research opportunities in the Hardware}
+\subsection{Computer hardware that embraces the language}
Attempts have been done to run Scheme in a bare-metal environment
\cite{MIMOSA:Yvon} [LOKO], but none of them approached the problem of a CPU
that is heavily optimized for a software model that has other underlying
concepts.
- Once the language is chosen and the structure of the kernel is well-defined,
- many optimizations can be applied to the underlying hardware, the same way it
- is done nowadays, but with different goals.
-
\subsubsection{Optimization for tree structures}
\textit{Scheme} is based (not only that, the language itself is a list) in
the \textit{cons cell}, similar to a \textit{linked-list} node, and the data
@@ -370,11 +367,12 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom }
For our case, a FPGA facilitates the testing and the evaluation of the
impacts of the proposed optimizations. If a Hardware Description Language,
- \textit{HDL}, is provided with the system and the Operating System is able to
- program the FPGA, the whole system can be updated together, improving the OS
- and the needed hardware at the same time. A \textit{rollback}[GUIX/NIX]
- mechanism could always recover the state of both hardware and software as if
- they were the same thing.
+ \textit{HDL}, is provided with the system and the Operating System has
+ support for Partial and Dynamic Reconfiguration\cite{FPGAReconf:Vipin}, the
+ whole system can be updated together, improving the OS and the needed
+ hardware at the same time. A \textit{rollback}[GUIX/NIX] mechanism could
+ always recover the state of both hardware and software as if they were the
+ same thing.
The FPGAs are more power hungry and not as fast as ASICs but
the reduction of complexity proposed in this paper should be enough for
@@ -387,19 +385,26 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom }
\section{Conclusion}
There have been several attempts to use Scheme in bare-metal, and make
- Lisp/FP machines.
+ Lisp/FP machines, but few combined their ideas with commodity FPGAs.
- Choosing an FPGA and a simplified approach opens for many optimization
+ Combining an FPGA and a simplified approach opens for many optimization
options where novel research ideas can be express due to the language
- oriented design of Scheme. This research can be applied in other languages
- that use similar constructs (FP languages, but also Python and JS).
-
- Extending the reach of the language enriches the relationship the user has
- with the computer. If the selected language is powerful in terms of the level
- of abstraction it can provide, it could become the only tool a user needs for
- every single administration task, including hardware upgrade or optimization.
-
- Embracing the language is embracing the person in charge of the computer.
+ oriented design of Scheme, some were proposed in this paper but more can be
+ developed and potentially applied in other languages that use similar
+ constructs (FP languages, but also Python and JS).
+
+ The cited literature, more specifically Oberon, demonstrate a minimal system
+ can be easily implemented and maintained by a single individual and the level
+ of simplification approached in its design is parallel to the one proposed in
+ this document, meaning that a computing system like the one proposed here
+ would be possibly created and maintained by anyone, while keeping it secure
+ and accessible.
+
+ On the other hand, extending the reach of the language enriches the
+ relationship the user has with the computer. If the selected language is
+ powerful in terms of the level of abstraction it can provide, it could become
+ the only tool a user needs for every single administration task, including
+ hardware upgrade or optimization.
\clearpage