diff options
| -rw-r--r-- | papers/LOCO-24/contents.latex | 273 |
1 files changed, 96 insertions, 177 deletions
diff --git a/papers/LOCO-24/contents.latex b/papers/LOCO-24/contents.latex index 38196f1..76d51a1 100644 --- a/papers/LOCO-24/contents.latex +++ b/papers/LOCO-24/contents.latex @@ -208,7 +208,7 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom } \textit{processes}, \textit{shared-memory threads}, \textit{hierarchical filesystems} and \textit{system calls}. -\subsubsection{The Shell} +\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}. @@ -216,42 +216,37 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom } words, \textit{"text streams [are] the universal interface"} \cite{QuarterCenturyUnix:Salus}. -\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. - -% ELF/Mach-O/EXE -> the kernel acts as an interpreter for them. -% Virtual memory separates one program from another. -% The CPU helps with that. -% Each program is a process (invented concept) -% Each process can launch threads \cite{Threads:Lee} - - \paragraph{Concurrency} - If programs need to operate concurrently they can create many - \textit{processes} or use \textit{threads}. A \textit{thread} is a - lightweight version of a \textit{process} that shares the memory with the - \textit{process} that created it. Resource sharing in a concurrent system has - many security and reliability implications, and has proven to be a difficult - subject for computer programmers over the years - \cite{Threads:Lee}. - - -\subsubsection{Interpreters} - Interpreters, like one in the \textit{shell}, are a fundamental part of - modern day programming. Interpreters are run as userspace programs, acting as - a \textit{host} for the program they interpret. The interpreter effectively - hides the details of the Operating System, often even implementing a virtual - machine for that job, in order to provide \textit{portability} and - \textit{usability} to the programmers. That is why the most used and demanded - programming languages nowadays are interpreted \cite{PLCommunity:Tambad}. +%\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 +% lightweight version of a \textit{process} that shares the memory with the +% \textit{process} that created it. Resource sharing in a concurrent system has +% many security and reliability implications, and has proven to be a difficult +% subject for computer programmers over the years +% \cite{Threads:Lee}. +% +% +%\subsubsection{Interpreters} +% Interpreters, like one in the \textit{shell}, are a fundamental part of +% modern day programming. Interpreters are run as userspace programs, acting as +% a \textit{host} for the program they interpret. The interpreter effectively +% hides the details of the Operating System, often even implementing a virtual +% machine for that job, in order to provide \textit{portability} and +% \textit{usability} to the programmers. That is why the most used and demanded +% programming languages nowadays are interpreted \cite{PLCommunity:Tambad}. % Unix was marketed as a system for multiple languages / supports many % languages via interpreters that ease the development experience. Describe how @@ -282,94 +277,18 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom } 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. Focusing on providing - facilities for \textit{vernacular programmers}\cite{MythsPL:Shaw} shapes a - good compromise between available technical literacy from the user side and a - wide audience to benefit. + programming facilities that computing systems provide. -% %% TODO: embracing the language means embracing the people -% -% From what we just discussed we can see most interesting things in Unix's -% ideas are dangerous from von Neumann to shared-resource concurrency and -% others are not comfortable for programmers, who prefer to use interpreted -% languages instead as the abstractions they provide are easier to deal with. -% But CPUs are optimized for the Unix case, instead of embracing the facilities -% the programmers prefer to use. - -\subsection{Personal computers} - -%% TODO: do this the other way around!!! (to make it shorter) -% Before the Unix model won, personal computers were mainstream: they were -% simple and so on. We think those computers had the base where we can build -% computers that embrace the language and the person - Before the Unix model flooded the personal computer market, computers were - simple devices designed to be operated by a single person, each brand - marketed their own \textit{ad-hoc} operating system and most of them had a - vehicular language. Computer users were familiarized with the system and were - able to manipulate it down to the electronics, creating a large generation of - computer enthusiasts that still lasts today. - - The introduction of Graphical User Interfaces, \textit{GUI}, widened the - spectrum of users \cite{EvolutionComputing:Larus} but at the expense of the - access to lower level capabilities, as \textit{protecting the user}, and the - computing literacy that traditional usage encouraged. - - Treating the users as adults (not protecting them from themselves), like - early personal computers did, and providing them the adequate interface for - exploration happens to be a extremely powerful way to explore optimization - and simplification of computing systems \cite{Oberon:Wirth}. - -% %% TODO: is this part of the intro really? -% -% %% TODO: What's `personal` in personal computer? embrace the user-programmer -% %% TODO: make sure dates are right -% -% Personal computers like those before the 90s were simple. A user could -% maintain them and even manipulate the electronics. They often made a strong -% bet for one language (ZX Spectrum / Apple II with BASIC), but the languages -% had poor abstraction capabilities. -% -% The introduction of larger RAM memories and more complex CPUs, made the -% personal computing industry pivot towards Unix-based operating systems, as -% they were proven to work in complex scenarios. This shift contributed to the -% extinction of many \textit{simple} operating systems that flourished during -% the previous era but facilitated the galloping increase personal computing -% specs in the following years\cite{EvolutionComputing:Larus}. -% -% %% TODO graphical user interfaces hid the programming part -% -% Graphical User Interfaces, \textit{GUI}, became widespread in the early 1980s -% and made computers accessible and useful to many -% people\cite{EvolutionComputing:Larus} but at the expense of the access to -% lower level capabilities, as \textit{protecting the user}, and the computing -% literacy that traditional text-oriented usage encouraged. -% -% -% Operating systems like Oberon \cite{Oberon:Wirth} blur the line between -% \textit{GUI}s and programming, making them work together instead of hiding -% the programming part of the system, while keeping a simple core in its design -% that keeps the system maintainable, still making a strong bet for the -% language (Oberon). -% -% Our proposal is to recover the feeling of personal computers from the 80s, -% but with the powerful abstraction capabilities we widely regard as -% comfortable. -% -% %% TODO: explain the GUI apparition and how before everyone was a vernacular -% %% programmer and now it's not like that -% %% TODO: if we want to improve the connection with the vernacular programmer, -% %% we need to ask ourselves: what's a language? \cite{MythsPL:Shaw} -% -% For \textit{vernacular programmers}, because they represent the vast majority -% of programmers \cite{MythsPL:Shaw}: simplicity (few concepts), explorability -% (repl), flexible, practical, also valid for professional programmers, -% extendable, can represent other kind of goals like \textit{HDLs} and even -% \textit{data} via DSLs. + 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} -\subsection{The language} +\subsection{Choosing Scheme} The \textit{Lisp} family of languages have proven to be flexible and powerful - (Lisp Machines and currently Emacs) and \textit{Scheme} has a long history of - research in language and CPU design (lambda papers). + for system design \cite{LispMachine:Greenblatt} and particularly + \textit{Scheme} has a long history of research in language and CPU design + (lambda papers). \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 @@ -379,46 +298,20 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom } 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). + needs (Typed Racket, Kawa). This eliminates the need to rely on unstructured + text \ref{shell}. -% If we want to embrace the language we need to choose a language to embrace. -% We have to place a bet: but we are betting to the widest option we know that -% is also \textit{practical}. -% -% Scheme: -% \begin{itemize} -% \item It's abstract enough -% \item Other languages can compile to it (Wisp: srfi-119) (srfi-110 for the -% difficulty of reading) -% \item Simple concepts but powerful abstractions -% \item Minimal standard -% \item Extensibility -% \item Language oriented programming (Racket) -% \item Proven experience with the lambda papers and lisp machines => abandoned, -% but still living in Emacs. -% \item Typed Racket / Kawa / ... -% \end{itemize} - - - -\subsection{Operating System} - -% Unix based operating systems, have demonstrated to have several troublesome -% concepts that are stuck in modern day programmers and users, but valid -% alternatives had also been successfully proven in other areas of the -% programming practice. Betting in a language enables applying those in the -% operating system level. - -\subsubsection{The kernel-interpreter} - From the programming perspective, the \textit{kernel} and programming - language \textit{interpreters} act as hosts: they prepare an isolated - environment for the running program and manage resources for it via - system-calls vs function calls, while running what it is written in the - program body. - - When a interpreter as a \textit{userspace} program, there are two layers of - interpretation. Engineering the kernel as an interpreter reduces its - complexity and allows for further specialization for the chosen language. + 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{Research opportunities in the OS} + + 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{Managed memory} Virtual memory is an attempt to isolate programs from each other but it is a @@ -429,51 +322,77 @@ Computing}{December 05, 2024}{Glasgow, Scotland, United Kingdom } \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. + 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. + Unix. No \textit{user} support. [3L] \subsubsection{Filesystem} This allows for new paradigms in Filesystem design. -\subsection{Hardware for the kernel-interpreter} +\subsection{Research opportunities in the Hardware} + 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. + 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 structures that can be created from it (\textit{lists} and \textit{trees}). Optimizing the CPU for that case, with fast lookups and \code{car} and - \code{cdr} operations hugely impacts in its performance. + \code{cdr} operations hugely impacts in its performance. This can also affect + the memory, but as it is managed, the user would never notice any difference. + +\subsubsection{CPU as a reducer} + \textit{Scheme} supports many paradigms but the basis of the language is the + expression reduction, not like imperative language, where the basis is the + \textit{statement}. This opens the door for optimizations like those applied + in current \textit{Scheme} interpreters but in a hardware level. [REDUCER + CPUs] \subsubsection{Hardware garbage collection} When the whole system uses managed memory, the Garbage Collection, \textit{GC}, can be pushed down in the stack. Oberon's GC is in the kernel, but we could push it down to the hardware. -\subsubsection{Extendable CPU} - In order to test all those options, we could work in a FPGA, even using a HDL - written in \textit{Scheme}. 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 personal computing. Also, letting the user configure the CPU from - the computer itself reduces the need for constant upgrades, uses commodity +\subsubsection{FPGA} + Focusing on personal computing can be a extremely powerful way to explore + optimization and simplification of computing systems to the point they can be + run in custom unoptimized CPUs implemented in FPGAs \cite{Oberon:Wirth}. + + 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. + + 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 + personal computing. Also, letting the user configure the CPU from the + computer itself reduces the need for constant upgrades, uses commodity hardware instead of very specialized devices and reduces the chance of a supply chain attack in many levels \cite{riscvSelfHostingComputer:Somlo}. \section{Conclusion} - The usage of commodity hardware like FPGAs and the reduction of needs from - the CPU by eliminating the Kernel and some of the associated complexity could - reduce the environmental (\textit{shipping}, waste associated with - \textit{periodic upgrades}) and human cost (\textit{security}, - \textit{awareness}) of personal computers. + There have been several attempts to use Scheme in bare-metal, and make + Lisp/FP machines. + + Choosing 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 |