Bookmarks
Notes/Primer on Clang Compiler Frontend (1) : Introduction and Architecture
Notes/Primer on Clang Compiler Frontend: Introduction and Architecture
These are my notes on chapters 1 & 2 of the Clang Compiler Frontend by Ivan Murashko. The book is focused on teaching the fundamentals of LLVM to C++ engineers who are interested in learning about compilers to optimize their daily workflow by enhancing their code quality and overall development process. (I’ve referened this book extensively, and a lot of the snippets here are from this book.
Why async Rust?
I genuinely can’t understand how anybody could look at the mess that’s Rust’s async and think that it was a good design for a language that already had the reputation of being very complicated to write.
Template Haskell
Intuitively Template Haskell provides new language features that allow us to convert back and forth between concrete syntax, i. e.
A friendly introduction to machine learning compilers and optimizers
[Twitter thread, Hacker News discussion]
The Making of Python
Guido van Rossum is the author of Python, an interpreted, interactive object-oriented programming language.
Why Attention Is All You NeedWhy Attention Is All You Need
The Transformer architecture introduced in this paper was a major breakthrough in sequence transduction methodologies, particularly within neural machine translation (NMT) and broader natural language processing (NLP).
tt-mlir documentation
The following document provides an overview of the TT-MLIR project, with a focus on the technical specifications of an MLIR-based compiler stack. So what exactly is an MLIR-based compiler stack?
Programming Really Is Simple Mathematics
A re-construction of the fundamentals of programming as a small mathematical theory (PRISM) based on elementary set theory. Highlights:
$\bullet$ Zero axioms. No properties are assumed, all are proved (from standard set theory).
$\bullet$ A single concept covers specifications and programs.
$\bullet$ Its definition only involves one relation and one set.
$\bullet$ Everything proceeds from three operations: choice, composition and restriction.
$\bullet$ These techniques suffice to derive the axioms of classic papers on the "laws of programming" as consequences and prove them mechanically.
$\bullet$ The ordinary subset operator suffices to define both the notion of program correctness and the concepts of specialization and refinement.
$\bullet$ From this basis, the theory deduces dozens of theorems characterizing important properties of programs and programming.
$\bullet$ All these theorems have been mechanically verified (using Isabelle/HOL); the proofs are available in a public repository.
This paper is a considerable extension and rewrite of an earlier contribution [arXiv:1507.00723]
Tilde, my LLVM alternative
I'm Yasser and I've made it my mission to produce an alternative to LLVM, the current king of compiler backend libraries.
A WebAssembly compiler that fits in a tweet
Starting with a 192-byte one-liner that implements a Reverse Polish Notation arithmetic compiler, we'll work backward to transform it into readable JavaScript by removing one code golf trick at a time
Ödeme - Pozitif Teknoloji
*Lütfen açıklama kısmına sipariş numaranızı giriniz, Sipariş numarası yazılmayan havale işlemlerinde ki gecikmelerden firmamız sorumlu değildir.
Demystifying Debuggers, Part 2: The Anatomy Of A Running Program
On the concepts involved in a running program. What happens, exactly, when you double click an executable file, or launch it from the command line, and it begins to execute?
Algebraic Databases
Databases have been studied category-theoretically for decades. The database schema---whose purpose is to arrange high-level conceptual entities---is generally modeled as a category or sketch. The data itself, often called an instance, is generally modeled as a set-valued functor, assigning to each conceptual entity a set of examples. While mathematically elegant, these categorical models have typically struggled with representing concrete data such as integers or strings.
In the present work, we propose an extension of the set-valued functor model, making use of multisorted algebraic theories (a.k.a. Lawvere theories) to incorporate concrete data in a principled way. This also allows constraints and queries to make use of operations on data, such as multiplication or comparison of numbers, helping to bridge the gap between traditional databases and programming languages.
We also show how all of the components of our model---including schemas, instances, change-of-schema functors, and queries - fit into a single double categorical structure called a proarrow equipment (a.k.a. framed bicategory).
On Ousterhout’s Dichotomy Oct 6, 2024
Why are there so many programming languages? One of the driving reasons for this is that some
languages tend to produce fast code, but are a bit of a pain to use (C++), while others are a breeze
to write, but run somewhat slow (Python). Depending on the ratio of CPUs to programmers, one or the
other might be relatively more important.
The categorical abstract machine
The Cartesian closed categories have been shown by several authors to provide the right framework of the model theory of λ-calculus. The second author…
Position: Categorical Deep Learning is an Algebraic Theory of All Architectures
We present our position on the elusive quest for a general-purpose framework
for specifying and studying deep learning architectures. Our opinion is that
the key attempts made so far lack a coherent bridge between specifying
constraints which models must satisfy and specifying their implementations.
Focusing on building a such a bridge, we propose to apply category theory --
precisely, the universal algebra of monads valued in a 2-category of parametric
maps -- as a single theory elegantly subsuming both of these flavours of neural
network design. To defend our position, we show how this theory recovers
constraints induced by geometric deep learning, as well as implementations of
many architectures drawn from the diverse landscape of neural networks, such as
RNNs. We also illustrate how the theory naturally encodes many standard
constructs in computer science and automata theory.
Fundamental Components of Deep Learning: A category-theoretic approach
Deep learning, despite its remarkable achievements, is still a young field.
Like the early stages of many scientific disciplines, it is marked by the
discovery of new phenomena, ad-hoc design decisions, and the lack of a uniform
and compositional mathematical foundation. From the intricacies of the
implementation of backpropagation, through a growing zoo of neural network
architectures, to the new and poorly understood phenomena such as double
descent, scaling laws or in-context learning, there are few unifying principles
in deep learning. This thesis develops a novel mathematical foundation for deep
learning based on the language of category theory. We develop a new framework
that is a) end-to-end, b) unform, and c) not merely descriptive, but
prescriptive, meaning it is amenable to direct implementation in programming
languages with sufficient features. We also systematise many existing
approaches, placing many existing constructions and concepts from the
literature under the same umbrella. In Part I we identify and model two main
properties of deep learning systems parametricity and bidirectionality by we
expand on the previously defined construction of actegories and Para to study
the former, and define weighted optics to study the latter. Combining them
yields parametric weighted optics, a categorical model of artificial neural
networks, and more. Part II justifies the abstractions from Part I, applying
them to model backpropagation, architectures, and supervised learning. We
provide a lens-theoretic axiomatisation of differentiation, covering not just
smooth spaces, but discrete settings of boolean circuits as well. We survey
existing, and develop new categorical models of neural network architectures.
We formalise the notion of optimisers and lastly, combine all the existing
concepts together, providing a uniform and compositional framework for
supervised learning.
Logical Complexity of Proofs
If you cannot find proofs, talk about them. Robert Reckhow with his advsior Stephen Cook famously started the formal study of the complexity of proofs with their 1979 paper. They were interested in…
Richard Hamming - Wikipedia
Richard Wesley Hamming (February 11, 1915 – January 7, 1998) was an American mathematician whose work had many implications for computer engineering and telecommunications.
What is the "question" that programming language theory is trying to answer?
I've been interested in various topics like Combinatory Logic, Lambda Calculus, Functional Programming for a while and have been studying them. However, unlike the "Theory of Computation" which str...
Introducing Limbo: A complete rewrite of SQLite in Rust
we forked SQLite with the libSQL project. What would it be like if we just rewrote it?
Fundamental Components of Deep Learning: A category-theoretic approach
Deep learning, despite its remarkable achievements, is still a young field.
Like the early stages of many scientific disciplines, it is marked by the
discovery of new phenomena, ad-hoc design decisions, and the lack of a uniform
and compositional mathematical foundation. From the intricacies of the
implementation of backpropagation, through a growing zoo of neural network
architectures, to the new and poorly understood phenomena such as double
descent, scaling laws or in-context learning, there are few unifying principles
in deep learning. This thesis develops a novel mathematical foundation for deep
learning based on the language of category theory. We develop a new framework
that is a) end-to-end, b) unform, and c) not merely descriptive, but
prescriptive, meaning it is amenable to direct implementation in programming
languages with sufficient features. We also systematise many existing
approaches, placing many existing constructions and concepts from the
literature under the same umbrella. In Part I we identify and model two main
properties of deep learning systems parametricity and bidirectionality by we
expand on the previously defined construction of actegories and Para to study
the former, and define weighted optics to study the latter. Combining them
yields parametric weighted optics, a categorical model of artificial neural
networks, and more. Part II justifies the abstractions from Part I, applying
them to model backpropagation, architectures, and supervised learning. We
provide a lens-theoretic axiomatisation of differentiation, covering not just
smooth spaces, but discrete settings of boolean circuits as well. We survey
existing, and develop new categorical models of neural network architectures.
We formalise the notion of optimisers and lastly, combine all the existing
concepts together, providing a uniform and compositional framework for
supervised learning.
Advanced programming languages
Students often ask for a recommendation on what language they should learn next.
How Many Computers Are In Your Computer?
Any ‘computer’ is made up of hundreds of separate computers plugged together, any of which can be hacked. I list some of these parts.
Haskell as fast as C: working at a high altitude for low level performance
After the last post about high performance, high level programming, Slava Pestov, of Factor fame, wondered whether it was generally true that “if you want good performance you have to write C…
Performance
Moreover, it's often not clear if two programs which supposedly have the same functionality really do the same thing.
Proof Explorer
Inspired by Whitehead and Russell's monumental Principia Mathematica, the Metamath Proof Explorer has over 26,000 completely worked out proofs in its main sections (and over 41,000 counting "mathboxes", which are annexes where contributors can develop additional topics), starting from the very foundation that mathematics is built on and eventually arriving at familiar mathematical facts and beyond.
An Invitation to Applied Category Theory
Abstract page for arXiv paper 1803.05316: Seven Sketches in Compositionality: An Invitation to Applied Category Theory
An Invitation to Applied Category Theory
Cambridge Core - Programming Languages and Applied Logic - An Invitation to Applied Category Theory
Introducing io_uring_spawn
The traditional mechanism for launching a program in a new process on Unix systems—forking and execing—has been with us for decades, but it is not really the most efficient of operations.
Competitive Programming
This is the supporting web page for a book titled: "Competitive Programming 4: The Lower Bound of Programming Contests in the 2020s" written by Steven Halim, Felix Halim, and Suhendry Effendy.
Algorithms for Modern Hardware
Its intended audience is everyone from performance engineers and practical algorithm researchers to undergraduate computer science students who have just finished an advanced algorithms course and want to learn more practical ways to speed up a program than by going from O(nlogn) to O(nloglogn).
Zig's new declaration literals
A look at Zig's new declaration literals
How LLVM Optimizes a Function
In some compilers the IR format remains fixed throughout the optimization pipeline, in others the format or semantics change.
Tell the Compiler What You Know
Compilers a lot of times use magic to uncover hidden mysteries of your program and optimize it aggressively.
Numerical Recipes
We are Numerical Recipes, one of the oldest continuously operating sites on the Internet.
For Beginners
Occasional writings about Haskell.
6.824 Schedule: Spring 2022
Here is the tentative schedule of lectures and due dates. The lecture notes and paper questions for future dates are copies from previous years, and may change.
Async Rust can be a pleasure to work with (without `Send + Sync + 'static`)
Async Rust is powerful. And it can be a pain to work with (and learn). Async Rust can be a pleasure to work with, though, if we can do it without `Send + Sync + 'static`.
Linus Torvalds talks AI, Rust adoption, and why the Linux kernel is 'the only thing that matters'
In a wide-ranging conversation with Verizon open-source officer Dirk Hohndel, 'plodding engineer' Linus Torvalds discussed where Linux is today and where it may go tomorrow.
Intercepting and modifying Linux system calls with ptrace
Intercepting and modifying Linux system calls with ptrace
Zig and Emulators
Some quick Zig feedback in the context of a new 8-bit emulator project I starteda little while ago:
Linkers part 1
I’ve been working on and off on a new linker.
A ToC of the 20 part linker essay
I release this message (the ToC and comments) into the public domain, no right reserved.
`zig cc`: a Powerful Drop-In Replacement for GCC/Clang
If you have heard of Zig before, you may know it as a promising new programming language which is ambitiously trying to overthrow C as the de-facto systems language.
Resources for Amateur Compiler Writers
I know complete pans of the literature are left out, but this is a page for amateur compiler writers. Anything that I did not find practical is not listed here.
How to Compile Your Language
The guide also covers how to create a platform-specific executable with the help of the LLVM compiler infrastructure, which all of the previously mentioned languages use for the same purpose.
Introduction to the Odin Programming Language
Preface This article is an introduction the Odin Programming Language. It is aimed at people who know a bit of programming, but have never touched Odin. It is not a reference guide, rather I try to keep things informal and talk about what I think are important aspects of the language. There will be some notes on differences to C/C++, as Odin in many ways tries to be better C. If you enjoy this article and want to support me, then you can do so by becoming a patron.
bytecode interpreters for tiny computers
I've previously come to the conclusion that there's little reason for using bytecode in the modern world, except in order to get more compact code, for which it can be very effective.
How I built zig-sqlite
When you prepare a statement zig-sqlite creates a brand new type only for this prepared statement.
Microfeatures I'd like to see in more languages
There are roughly three classes of language features: Features that the language is effectively designed around, such that you can't add it after the fact....
Google’s Fully Homomorphic Encryption Compiler — A Primer
Back in May of 2022 I transferred teams at Google to work on Fully Homomorphic Encryption (newsletter announcement). Since then I’ve been working on a variety of projects in the space, includ…
Will I be able to access proprietary platform APIs (e.g. Android / iOS)?
The kind of binary format being considered for WebAssembly can be natively decoded much faster than JavaScript can be parsed (experiments show more than 20× faster).
Files are hard
Writing files in a way that ensures their robustness is challenging due to the complexity involved. The paper discusses various issues related to file corruption and data loss, such as crash consistency, filesystem semantics, filesystem correctness, error handling, and error recovery. It highlights the differences in how different filesystems handle errors and points out bugs and inconsistencies found in popular filesystems. The paper also addresses the frequency of disk errors and data corruption, emphasizing the need for caution when writing files and the importance of using libraries or tools to ensure safety. Overall, the document emphasizes the difficulty of reasoning about file-related problems and the need for careful considerations when working with filesystems.
Ringing in a new asynchronous I/O API
The new "io_uring" interface simplifies asynchronous I/O in the Linux kernel by using two ring buffers for submission and completion queues. Applications can set up these buffers with a system call and submit I/O requests through a structured format. This method aims to reduce complaints about AIO by improving efficiency and ease of use.
Brian Robert Callahan
This blog post starts a series on creating programs that demystify how programs work. The first program is a disassembler that reads bytecode and converts it into assembly language, while a future post will cover creating an assembler. The disassembler uses a table of mnemonics and instruction sizes to print out the corresponding assembly instructions from bytecode.
QBE vs LLVM
QBE and LLVM are both compiler backends, but QBE is a smaller, more accessible project aimed at amateur language designers. While LLVM is feature-rich and complex, QBE focuses on simplicity and efficiency, making it easier to use for quick projects. QBE provides straightforward operations and a cleaner intermediate language, reducing the complexity often found in LLVM.
Tiled Matrix Multiplication
Tiled matrix multiplication is an efficient algorithm used on GPUs that reduces memory access by utilizing shared memory. By organizing threads into blocks, each thread can perform calculations more quickly and with fewer memory accesses. This method is important for improving performance in tasks like graphics rendering and machine learning.
Rust Atomics and Locks
This book by Mara Bos explores Rust programming language's concurrency features, including atomics, locks, and memory ordering. Readers will gain a practical understanding of low-level concurrency in Rust, covering topics like mutexes and condition variables. The book provides insights on implementing correct concurrency code and building custom locking and synchronization mechanisms.
Cache-Oblivious Algorithms
Cache-oblivious algorithms are designed to use processor caches efficiently without needing to know specific cache details. They work by dividing data into smaller parts, allowing more computations to happen in cache and reducing memory access. This leads to better performance, especially in parallel algorithms, by minimizing shared memory bottlenecks.
Implementing interactive languages
Implementing an interactive language requires considering both compile-time and run-time performance. Traditional switch-based bytecode interpreters are easy to implement but have lower run-time performance compared to optimizing compilers. A sweet spot in performance can be found by aiming for combined compile-time and run-time performance within a certain range. Various options for implementing fast interpreters, existing compilers like LLVM and Cranelift, custom compilers, and using WebAssembly as a backend are discussed. The idea of having two backends for a language to support quick startup and aggressive optimization is also explored. There are still many unknowns and further research is needed to determine the feasibility and performance of different approaches.
Parse, don’t validate
The text discusses the importance of parsing over validating in Haskell to prevent errors and enhance code reliability by using strong argument types. Parsing upfront helps maintain consistency and avoids potential issues with partial input processing, demonstrating the benefits of type-driven design in Haskell programming. The text also touches on the subjective nature of programming languages, highlighting differing perceptions of Haskell and the challenges faced by learners in navigating diverse opinions.
Too Fast, Too Megamorphic: what influences method call performance in Java?
The performance of method calls in Java can be improved through techniques like inlining and using inline caches. Monomorphic calls, where only one method can be invoked, are the fastest, while bimorphic and megamorphic calls are slower due to increased lookup costs. The study highlights that simply adding the "final" keyword or overriding methods does not significantly enhance performance.
Resources for Building Programming Languages
The article shares resources for learning how to create programming languages, focusing on Rust and C. It highlights the book "Crafting Interpreters," which provides practical insights into building interpreters using different programming approaches. The author also discusses their personal experience building a language and the tools they've found helpful, like LLVM and Cranelift.
Little 'Big Ideas' in Programming Language Design
Colin Davis discusses "little big ideas" in programming language design, focusing on the balance between innovative features and conventional choices. He highlights Mojo and Go as examples, noting how Mojo combines modern improvements with familiar concepts, while Go prioritizes simplicity and a strong ecosystem. Davis suggests that small design decisions, like memory management and parameter passing, can greatly enhance a language's usability and performance.
Computer Networking: A Top-Down Approach
Jim Kurose and Keith Ross are prominent computer science professors with extensive experience in networking and related fields. They have received multiple awards for their teaching and research, and both have held leadership roles in academic and professional organizations. Their work focuses on topics like network protocols, security, and multimedia communication.
Zip Files All The Way Down
The text discusses creating self-reproducing programs and files like zip files that can decompress to themselves. It explores using Lempel-Ziv compression for self-reproduction and the challenges of translating these concepts into real opcode encodings like DEFLATE used in gzip and zip files. The ultimate goal is to create a zip file that contains a larger copy of itself recursively, creating a chain of expanding zip files.
Minimal Boolean Formulas
The post discusses how to compute the minimum number of AND and OR operators needed for Boolean functions with five variables. It describes the author's program that efficiently calculates this minimum for various functions while also improving algorithms for speed. The findings contribute to understanding the complexity of Boolean functions and their representations.
Hacking the OS X Kernel for Fun and Profiles Posted on Tuesday, August 13, 2013.
The article discusses a bug in the OS X kernel related to how profiling signals are delivered in multithreaded processes. It explains that the kernel incorrectly sends the SIGPROF signal to the entire process instead of the specific running thread. The author outlines a fix involving a small edit to the kernel code to ensure the signal is sent to the correct thread.
An Encoded Tree Traversal
The text discusses different ways to traverse binary trees and how these methods can be generalized to k-ary trees. It highlights a new ordering for traversing k-ary trees that results in a regular numbering pattern, which is not present in the traditional methods. The author seeks references or examples of this k-ary-coded traversal order, which he has not yet found.
The Magic of Sampling, and its Limitations Posted on Saturday, February 4, 2023.
Sampling can help estimate the percentage of items with a specific trait accurately. The number of samples taken greatly affects the accuracy of the estimate. To get precise estimates, all items must have an equal chance of being selected during sampling.
CompilerTalkFinal
The content discusses various compilers and their features, including Clang, GCC, V8, CakeML, Chez Scheme, and more. It also touches on the history of interpreters and compilers, with examples like ENIAC and the first compiler developed by Grace Hopper. Different approaches to compilation and interpretation are highlighted, showcasing the evolution of compiler technology.
Graydon Hoare: 21 compilers and 3 orders of magnitude in 60 minutes
Graydon Hoare's talk explains different approaches to building compilers, from traditional giants to more efficient variants. He highlights the importance of using compiler-friendly languages and theory-driven meta-languages. The presentation covers key concepts like sophisticated partial evaluation and implementing compilers directly by hand.
p75-hoare
The author recounts experiences in designing a computer programming language and issues a warning about language complexity. Despite challenges, a subset of the language was successfully implemented. The author emphasizes the importance of simplicity and reliability in programming languages for critical applications.
Baby Steps to a C Compiler
Writing a simple compiler can help you understand how computers work. Start with a minimal project that compiles a small subset of a language, and then gradually add more features. This approach makes learning about compilers and programming enjoyable and rewarding.
Kernel Programming Guide
Essential information for programming in the OS X kernel. Includes a high-level overview.
Crafting an Interpreter in Zig - part 1
The author is learning Zig by implementing an interpreter for the Lox programming language, inspired by the book "Crafting Interpreters." They are documenting their journey, focusing on interesting aspects of Zig and how it differs from C. So far, they have enjoyed the process, particularly the simplicity and power of Zig's generic programming.
What Every Computer Scientist Should Know About Floating-Point Arithmetic
The text discusses the challenges and considerations of floating-point arithmetic in computer science. It emphasizes the importance of rounding in floating-point calculations and the implications of different precision levels. Additionally, it highlights the need for careful implementation to ensure correctness and accuracy in programs that rely on floating-point arithmetic.
Zig Interfaces for the Uninitiated, an update
The post discusses a new idiom for runtime polymorphism in Zig, focusing on using fat pointers instead of @fieldParentPtr. It provides a step-by-step guide on creating a formal Iterator interface and implementing it with an example range iterator. The drawbacks of this pattern include potential performance issues and the requirement for the original implementor to remain alive for the interface to function correctly.
Aro - a C compiler
Aro is a C compiler created as an alternative to Zig's compiler. It includes the aro module for the compiler and a language-agnostic aro_backend module for translating code into machine code. Aro uses self-hosted backends from the Zig compiler for optimization.
Database Systems
This course at CMU covers database management systems, including data models, query languages, storage architectures, and more. It uses case studies to show real-world applications and is suitable for students with basic systems programming skills. The course also thanks companies for their support in equipment donations and course development.
Discovering and exploring mmap using Go
Memory-mapped files allow programs to access disk data larger than available memory. By using mmap in Go, you can map a file directly into memory for easier manipulation. Virtual memory techniques, like mmap, can help solve memory limitations in handling large files efficiently.
reHow memory mapped files, filesystems and cloud storage works
Kelly discusses the challenges of memory-mapped files and cloud storage in response to a comment about space reservation in Voron. Cloud providers may allocate more space than needed, leading to unexpected charges and unreliable data handling. Testing reveals issues with sparse files and memory mapping in cloud scenarios, highlighting the importance of understanding storage limitations.
Implementing a file pager in Zig
Implementing a file pager in Zig involves delaying disk writes until a threshold is reached. Two eviction strategies include least recently used and least frequently used models. Prioritizing pages based on usage can help optimize performance.
Heap Memory and Allocators
The text discusses different types of memory allocators in Zig programming language.
It explains how memory allocation and deallocation work using alloc and free functions.
Various allocator types like GeneralPurposeAllocator and FixedBufferAllocator are highlighted for managing memory efficiently.
Emulator 101
A detailed, step by step guide to writing an emulator
Data Compression Explained
Data compression involves modeling and coding to reduce the size of data files. Modern compressors typically use arithmetic coding for efficient compression. Algorithms like Huffman coding and run-length encoding are commonly used to achieve better compression results.
Twitter's Recommendation Algorithm
Twitter uses a recommendation algorithm to select the top tweets for users' timelines. The algorithm is based on core models and features that extract information from tweet, user, and engagement data. The recommendation pipeline consists of three main stages: candidate sourcing, ranking, and applying heuristics and filters. Twitter uses both in-network and out-of-network sources to find relevant tweets, and employs embedding spaces to determine content similarity. The final step involves blending tweets with other non-tweet content before sending them to users' devices. The goal of Twitter's open source endeavor is to provide transparency to users about how the recommendation system works.
Programming languages resources
This page is a collection of the author's favorite resources for people getting started writing programming languages. The resources cover various aspects such as compilers, runtimes, runtime optimization, pointer tagging, JIT compilers, assembler libraries, and interesting tools. The author also mentions topics they want to write about in the future and papers they want to read. The page is meant to be a helpful reference for those interested in programming language implementation.
An opinionated beginner’s guide to Haskell in mid-2019
This guide is for beginners in Haskell or those transitioning from similar languages, offering advice on learning resources and tools. It emphasizes the importance of writing Haskell code, getting help online, choosing popular platforms, and sticking to the default Prelude. The guide also touches on application architecture, using records, debugging techniques, and the experimental nature of Haskell as both a research and industrial language.
Are tagged unions overrated?
The author discusses the limitations of tagged unions and pattern matching in language development, suggesting that they are overrated for implementing language ASTs and IRs. Despite the benefits of tagged unions, the complexity they add may not always justify their use, especially in cases where simpler alternatives like class hierarchies can offer similar functionality. The post also highlights the potential for enhancing pattern-matching capabilities in mainstream languages to improve code readability and maintainability.
What every systems programmer should know about concurrency
The document delves into the complexities of concurrency for systems programmers, explaining the challenges of running multithreaded programs where code is optimized and executed in unexpected sequences. It covers fundamental concepts like atomicity, enforcing order in multithreaded programs, and memory orderings. The text emphasizes the importance of understanding how hardware, compilers, programming languages, and applications interact to create a sense of order in multithreaded programs. Key topics include atomic operations, read-modify-write operations, compare-and-swap mechanisms, and memory barriers in weakly-ordered hardware architectures.
compiler_construction
Building a compiler can be straightforward by breaking the development into small steps and using Scheme as the implementation language. The tutorial focuses on translating a subset of Scheme to assembly code, with a step-by-step approach to achieve a fully working compiler. Testing and refining the compiler incrementally leads to a powerful tool capable of compiling an interactive evaluator.
The next fifty years
The text discusses the future of computing science over the next fifty years, emphasizing the importance of simplicity and elegance in design to prevent complexity. It highlights the close connection between program design and proof design, suggesting that advancements in program design can impact general mathematics. The author encourages embracing the opportunity to simplify processes and design systems that rely on formal mathematics.
Recommender Systems: A Primer
Personalized recommendations have become a common feature of modern online
services, including most major e-commerce sites, media platforms and social
networks. Today, due to their high practical relevance, research in the area of
recommender systems is flourishing more than ever. However, with the new
application scenarios of recommender systems that we observe today, constantly
new challenges arise as well, both in terms of algorithmic requirements and
with respect to the evaluation of such systems. In this paper, we first provide
an overview of the traditional formulation of the recommendation problem. We
then review the classical algorithmic paradigms for item retrieval and ranking
and elaborate how such systems can be evaluated. Afterwards, we discuss a
number of recent developments in recommender systems research, including
research on session-based recommendation, biases in recommender systems, and
questions regarding the impact and value of recommender systems in practice.
Introduction to Compilers and Language Design
A compiler translates high-level code to lower-level code, and building one is a common project in computer science education. This book provides a beginner-friendly guide to building a compiler for a C-like language, suitable for undergraduates with programming experience. The author offers free online access to the textbook and related code resources, with options to purchase a physical copy.
Bare Metal Zig
The text discusses compiling a freestanding Zig binary to run on "bare metal" without relying on an operating system. It shows how to create a simple freestanding binary, make it multiboot compliant, and add custom console functionality for output. The process involves targeting specific architectures, handling linker warnings, and ultimately creating a bootable "kernel" to run on virtual machines like QEMU.
C Isn't A Programming Language Anymore
C is no longer just a programming language but a vital protocol for all languages. Parsing C headers is a complex task best left to C compilers. Maintaining ABI compatibility in C can be challenging and may require versioning schemes.
Writing a C Compiler, Part 1
This text is about creating a C compiler in multiple stages, starting with lexing, parsing, and code generation. The process involves breaking down the source code, building an abstract syntax tree, and generating x86 assembly code. The compiler will handle simple programs with a single main function and a return statement.
Unknown
Hardware prefetching in multicore processors can be too aggressive, wasting resources and impacting performance for co-running threads. Combining hardware and software prefetching can optimize performance by efficiently handling irregular memory accesses. A method described in Paper II offers a low-overhead framework for accurate software prefetching in applications with irregular access patterns.
von Neumann architecture - Wikipedia
The von Neumann architecture is a computer design with a processing unit, control unit, memory, and input/output mechanisms. It allows for instructions and data operations to be stored in memory, advancing computer technology from fixed-function machines like the ENIAC. This architecture was influenced by the work of Alan Turing and John von Neumann and has been widely used in the development of modern computers.
Compiling tree transforms to operate on packed representations
The article explains how tree traversals in programming can be optimized by compiling them to work on serialized tree structures without using pointers. This approach can make programs run significantly faster on current x86 architectures. The authors developed a prototype compiler for a functional language that generates efficient code for traversing trees using packed data representations.
What happens when you start a process on Linux?
The process of starting a new program on Linux involves using the fork and exec system calls. Fork creates a clone of the current process, while exec replaces that clone with the new program to be executed. The new process inherits most attributes from its parent, with memory being shared through copy-on-write to optimize performance.
Debug your programs like they're closed source!
The author discusses debugging programs without looking at the source code by using system calls like open, execve, and write. System calls allow you to understand and monitor a program's behavior without needing access to its source code. By learning and utilizing system calls, you gain debugging superpowers that are platform-independent and useful for closed-source programs.
How I got better at debugging
Julia Evans shares her journey of improving her debugging skills through logical thinking, confidence, expanding knowledge, communication, and using tools like strace and tcpdump. By being systematic, confident, knowledgeable, and open to collaboration, she transformed debugging from a challenging task to an exciting learning opportunity. Her story emphasizes the importance of persistence, curiosity, and practical problem-solving in mastering the art of debugging.
Zig Bare Metal Programming on STM32F103 — Booting up
The text explains how to program the STM32F103 microcontroller using the Zig programming language. It covers topics such as memory layout, linker scripts, and compiling code for embedded systems. By following the provided instructions, readers can successfully compile and run their first embedded program on the microcontroller.
Undefined Behavior deserves a better reputation
Undefined Behavior is often viewed negatively, but it can be a valuable tool for language designers. It allows programmers to convey insights to the compiler for optimizations. Responsible use of Undefined Behavior can enhance language design and code performance.
Some Were Meant for C
The document "Some Were Meant for C" explores the enduring significance of the C programming language, highlighting its dual role as both an application and systems programming language. It challenges common assumptions about C, emphasizing its unique communicative design that differs from managed languages. The document argues that C's explicit representations and memory access foster effective system-building and communication, making it a preferred choice for certain technical challenges. Additionally, it critiques the prevailing discourse that demonizes C, advocating for a nuanced understanding of its role in the programming landscape.
Should you learn C to "learn how the computer works"?
The author discusses whether learning C is necessary to understand how computers work, ultimately concluding that C is not a direct representation of computer operations. Learning C can still be beneficial for understanding computing concepts and history, but it operates within a virtual machine and abstracts certain hardware details. By learning C, you can gain insight into the relationship between programming languages, hardware, and the historical development of computing.
Zig-style generics are not well-suited for most languages
Zig-style generics, like those in C++, may not work well for all languages due to limitations in compiler support and type inference. Armchair suggestions about adopting Zig-style generics in other languages may overlook these challenges. The flexibility and metaprogramming capabilities in Zig may not easily translate to other statically-typed languages.
The_Night_Watch
The text discusses the importance of systems programmers in dealing with complex technical challenges, emphasizing their unique skills in debugging and problem-solving. It contrasts the roles of systems programmers with other computer professionals like GUI designers and PHP developers, highlighting the critical nature of systems programming in challenging scenarios. The text humorously portrays the intense and sometimes absurd experiences of systems programmers, showcasing their indispensable role in addressing technical issues efficiently and effectively.
A Freestanding Rust Binary
To create a freestanding Rust executable for operating system development, we need to disable linking to the standard library and define our own entry point function. By compiling for a bare metal target like thumbv7em-none-eabihf, we can avoid linker errors and run Rust code without an underlying operating system. Additional linker arguments are required for specific operating systems like Linux, Windows, and macOS to resolve linker errors and build the freestanding Rust binary successfully.
Manually linking Rust binaries to support out-of-tree LLVM passes
LLVM is a compiler infrastructure used by frontends like rustc to generate machine code. To add custom LLVM passes to a Rust binary, extra flags can be used during compilation to produce LLVM-IR and then link the binary properly using LLVM tools. By understanding how Rust's static libraries work and leveraging cargo for dependency management, custom LLVM passes can be integrated into Rust binaries efficiently.
The Rust Reference
The Rust compiler can generate different types of output artifacts, such as runnable executables, Rust libraries, dynamic libraries, and static system libraries. Dependencies between crates can be linked in various formats, such as rlib and dynamic library formats, following specific rules set by the compiler. Understanding how to specify output formats like --crate-type=bin or --crate-type=lib can help control the compilation process for Rust crates, while also considering options for linking C runtimes dynamically or statically based on target features.
Rust Compiler Development Guide
The Rust compiler processes and transforms your code for compilation. It uses different stages like lexing, parsing, and abstract syntax tree lowering. The compiler aims for correctness, performance, and supporting incremental compilation.
How to speed up the Rust compiler one last time
The author at Mozilla is concluding their work on speeding up the Rust compiler after several years of dedicated effort.
They wrote multiple blog posts detailing their performance optimizations and shared valuable lessons learned from the process.
The author expressed gratitude to those who supported their work and highlighted the importance of ongoing contributions to Rust's development.
How to speed up the Rust compiler in March 2024
In March 2024, updates on the Rust compiler's performance highlighted several key improvements. Changes like using a single codegen unit, marking Debug::fmt methods with #[inline], introducing a cache, and upgrading LLVM versions led to notable reductions in wall-time, binary size, and hash table lookups. Additionally, the availability of the Cranelift codegen backend for x86-64/Linux and ARM/Linux offers an alternative for faster compile times. While the author didn't contribute to speed improvements this time, overall performance from August 2023 to March 2024 showed reductions in wall-time, peak memory usage, and binary size, indicating steady progress in enhancing the Rust compiler's efficiency.
Do We Really Need A Link Step?
The author questions the need for a link step in native-code compilation for faster performance. They propose a "zero-link" approach where compilers directly write object code into the final executable file. This method could improve efficiency by avoiding unnecessary object files and incorporating symbol resolution within the executable itself.
jamiebuilds/the-super-tiny-compiler: :snowman: Possibly the smallest compiler ever
The Super Tiny Compiler is a simplified example of a modern compiler using easy-to-read JavaScript. It helps you understand how compilers work from start to finish. Compilers play a big role in the tools we use daily.
5 Days to Virtualization: A Series on Hypervisor Development
A series on hypervisor development for Intel processors with virtualization support will be published next week, covering topics like setting up a test environment, driver skeleton creation, and multi-processor initialization. The series aims to aid new readers in building, testing, and understanding type-2 hypervisor development using C programming language. Recommended reading and detailed explanations will be provided to enhance knowledge and understanding of virtualization concepts.
Exploit Development: No Code Execution? No Problem! Living The Age of VBS, HVCI, and Kernel CFG
The text discusses various techniques used in exploit development, particularly focusing on targeting the Windows kernel. It mentions concepts like Hypervisor-Protected Code Integrity (HVCI) and how exploits can manipulate memory to execute attacker-controlled code in kernel mode. The text also delves into details like leaking kernel-mode memory, constructing ROP chains on the kernel-mode stack, and utilizing functions like NtQuerySystemInformation to escalate privileges and perform malicious actions in the system.
CheerpX versus WebContainers
CheerpX is a client-side virtualization technology for running x86 executables and operating systems in the browser without modifications or recompilation. It offers cost-effective, secure, and private execution of native code, making it suitable for various web-based applications. CheerpX stands out from other solutions by supporting any x86 executable and providing a robust two-tier emulator for efficient code execution.
Creating a Rootkit to Learn C
The text demonstrates creating a userland rootkit in C to hide malicious activities like network connections and files. By hooking into system calls like access() and write(), the rootkit can manipulate userland programs and evade detection by tools like netstat. The rootkit uses shared library injections and hooks to intercept and manipulate system calls, showcasing the power of C for malicious activities.
CS 361: Systems Programming
The Systems Programming course at UIC includes assigned readings, video lectures, labs, and quizzes scheduled throughout the week. Students can access additional resources and submit assignments through the course gradescope page. Office hours, content quizzes, discussions, and exams are held on specific days via Zoom and YouTube.
Resolving Rust Symbols
Linking combines object files into an executable or shared library in Rust. The linker resolves symbols and dependencies between object files. Rust prefers static linking to create a single distributable binary with all dependencies included.
Problems of C, and how Zig addresses them
This blog post discusses issues with C and how Zig addresses them through features like comptime evaluations and improved memory management. Zig offers solutions like error handling improvements and treating everything as an expression, making it a modern alternative to C with enhanced functionalities. The comparison highlights Zig's advantages in areas such as memory management, error handling, and expressive coding practices.
Leslie Lamport
Leslie Lamport wrote several papers on verifying and specifying concurrent systems using TLA. He discovered algorithms through formal derivation and emphasized mechanical verification of concurrent algorithms. His work influenced the development of the TLAPS proof system.
448997590_1496256481254967_2304975057370160015_n
The LLM Compiler is a suite of pre-trained models designed for code optimization tasks, based on Code Llama. It has been trained on a large corpus of LLVM-IR and assembly code to enhance compiler behavior understanding. The release of LLM Compiler aims to support further research in compiler optimization for both academia and industry.
Bare Bones
This text explains how to create an operating system by first cross-compiling and using existing technology. It guides you through writing a kernel in C or C++, creating a bootloader, and linking the kernel for x86 systems. Following these steps ensures your operating system can be loaded and executed correctly.
Dioxus Labs + “High-level Rust”
An article criticized Rust's gamedev hype, but its popularity stems from meeting modern programming needs like speed and safety. Efforts are underway to enhance Rust's capabilities for various industries and improve compile times significantly. Proposed enhancements include incremental linking, parallel frontend, and macro expansion caching to make Rust more efficient for developers.
Compile-Time Configuration For Zig Libraries
To expose compile-time configuration options in Zig libraries, developers can use global declarations in the root source file or through Zig's build system. By setting configuration flags, developers can customize behavior such as enabling or disabling assertions in library code. Compile-time configuration can improve performance by allowing certain checks to be done at compile-time rather than runtime.
Generics
Generics in Zig allow for creating data structures and algorithms that can work with different types. By using generics, code can be written once and reused with various data types. Zig's approach to generics involves leveraging compile-time metaprogramming capabilities.
Causal ordering
Causal ordering is essential for understanding distributed systems, where events may not have a clear time order. This concept helps determine the causal relationship between events in a system. It enables reasoning about causality, leading to simpler solutions in distributed computing.
Assorted thoughts on zig (and rust)
Zig is simpler than Rust and offers similar features through compile-time execution. Rust provides strong type safety guarantees for generic functions, while Zig lacks automatic type constraint documentation and may face challenges with IDE support. Zig excels in custom allocators and handling out-of-memory errors, while Rust excels in preventing memory leaks and resource management.
An opinionated map of incremental and streaming systems
The text discusses various design choices and characteristics of incremental and streaming systems. It highlights the core idea of these systems, which is to process inputs to generate outputs efficiently. The systems are categorized based on unstructured vs structured design, high temporal locality vs low temporal locality workloads, internal consistency vs internal inconsistency, and eager vs lazy computation approaches. The text explains the advantages and disadvantages of each design choice and provides examples of systems that fall into different categories. Additionally, it emphasizes the importance of understanding these design choices in selecting the appropriate system for specific workloads.
Internal consistency in streaming systems
The text discusses the importance of internal consistency in streaming systems. It explains how eventual consistency can lead to incorrect outputs and the need for systems to wait for all relevant inputs before emitting results. Maintaining internal consistency ensures correct outputs and prevents confusion between changes and corrections.
Prospecting for Hash Functions
The text discusses the process of designing non-cryptographic integer hash functions, exploring different operations and constraints to create effective hash functions. It also compares various 32-bit hash functions and their bias levels, highlighting the search for high-quality hash functions with minimal bias for both 32-bit and 64-bit integers.
Nanosystems
This text is about a book called "Nanosystems" by K. Eric Drexler, which is considered groundbreaking in the field of molecular nanotechnology. The book explains how to create manufacturing systems at the molecular level and discusses the significant impact nanotechnology will have on various industries. Experts praise the book for providing a foundation for future research in molecular systems engineering and molecular manufacturing.
the rr debugging experience
rr is a debugging tool for Linux that records failures for deterministic replay under gdb. It helps debug real applications efficiently and supports reverse execution for finding bugs. rr aims to make debugging easier with low overhead and powerful features like hardware data watchpoints.
What Is The Minimal Set Of Optimizations Needed For Zero-Cost Abstraction?
Rust and C++ offer "zero-cost abstractions" where high-level code compiles to low-level code without added runtime overhead, but enabling necessary compiler optimizations can slow down compilation and impact debugging. The challenge is to find the minimal set of optimizations that maintain zero-cost abstractions while improving build speed and debug information quality. Balancing fast debuggable builds with zero-cost abstractions is crucial for performance and developer experience in languages like Rust and C++.
Why is Python slow
Python's performance issues stem from spending most time in the C runtime, rather than the Python code itself. Pyston focuses on speeding up the C code to improve performance. Suggestions to improve Python's speed by using other JIT techniques overlook the fundamental issue of optimizing C code.
What is Systems Programming, Really?
The term "systems programming" combines low-level programming and systems design. It involves creating and managing complex components, often focusing on machine implementation details. Over time, the distinction between systems programming and other programming languages has become less clear.
UB Might Be a Wrong Term for Newer Languages Apr 2, 2023
The author suggests that using the term "undefined behavior" in newer languages like Zig and Rust may not be the best choice due to differences in semantics. In C, implementations can define some behaviors left undefined by the standard, but in Rust and Zig, any program showing undefined behavior is considered invalid. The author proposes using terms like "non-trapping programming error" or "invalid behavior" to better convey the intended semantics in these languages.
What Every C Programmer Should Know About Undefined Behavior #1/3
This blog post explains that many seemingly reasonable things in C actually have undefined behavior, leading to common bugs in programs. Undefined behavior in C allows for optimizations that improve performance but can result in unexpected outcomes like formatting your hard drive. Understanding undefined behavior is crucial for C programmers to prevent potential issues and improve code efficiency.
The Rustonomicon
The Rustonomicon is a book for understanding Unsafe Rust programming details. It complements The Rust Programming Language by delving into combining language pieces and potential issues. The book covers topics like (un)safety, creating safe abstractions with unsafe primitives, and working with memory, but does not provide exhaustive API details.
chrono-Compatible Low-Level Date Algorithms
The text explains algorithms for handling dates and determining leap years. It includes functions for calculating the last day of a month and converting dates between different calendar systems. The algorithms are designed to be efficient and accurate for various date calculations.
So Many New Systems Programming Languages II
The text discusses new systems programming languages like Rust, Zig, and Odin, highlighting their safety features and syntax. These languages offer improved memory management and safety compared to older languages like C and C++. Rust, in particular, stands out for its memory safety, threading support, and borrow checker.
Mapping the whole internet with Hilbert curves
The author mapped the internet using Hilbert curves to visualize IP addresses. The curves help display the vast network structure in a more comprehensible way. The scan revealed interesting patterns and changes in IP address allocations over time.
xorvoid
Anthony Bonkoski, a computer enthusiast and engineer, shares his experiences in programming and working in quantitative finance. He enjoys working on various projects and has expertise in low-level programming, distributed systems, and reverse-engineering. Currently taking a break from full-time work, he is open to part-time consulting projects and enjoys writing and exploring new interests.
An interactive study of queueing strategies
This text explores different queueing strategies for handling requests, emphasizing the importance of prioritizing requests effectively to prevent dropping important ones. It introduces concepts like FIFO and priority queues, as well as active queue management techniques to optimize request processing. Understanding these strategies can help in efficiently managing queues and improving overall system performance.
ethereumbook/04keys-addresses.asciidoc at develop · ethereumbook/ethereumbook · GitHub
This chapter introduces public key cryptography used in Ethereum for securing ownership of funds through private keys and addresses. Public keys are derived from private keys and are represented as points on an elliptic curve. Ethereum addresses are unique identifiers generated from public keys using the Keccak-256 hash function.
Accidentally Turing-Complete
The document "Accidentally Turing-Complete" explores various unexpected systems and technologies that unintentionally exhibit Turing completeness, a property that allows them to perform any computation. Examples include C++ templates, TypeScript, Java generics, X86 mov instructions, Magic: The Gathering card game, HTML5, Minecraft, Dwarf Fortress game, SQL, Apache Rewrite Rules, Pokemon Yellow game, Scala type system, MediaWiki templates, Little Big Planet game, Sendmail, Vim Normal-Mode, Border Gateway Protocol (BGP), Excel, Super Mario World glitches, PowerPoint, Font Shaping, JBIG2 Image Compression, and Stupid RDMA NICs. The document showcases how these diverse systems, from games to internet protocols, can unexpectedly demonstrate the computational power of Turing completeness.
Problems with BQN
BQN has issues with incoherent monad-dyad pairs and train structures, making code readability and implementation challenging. Modifications like the Constant modifier ˙ attempt to address these challenges. However, there are still limitations in tacit code construction and array reductions that impact the language's usability.
The borrow checker within
The text discusses improvements to Rust's borrow checker to align better with its core design ethos of mutation xor sharing. These changes aim to make Rust code patterns feel more intuitive and work seamlessly with the borrow checker's rules. The proposed enhancements include features like conditional return references, view types, and addressing phased initialization issues.
How should I read type system notation?
A type system in programming languages follows rules for expressions and types. Typing rules are written as relationships between expressions and their types for checking and inferring types. Contexts are used to keep track of variable types in type judgments.
A decade of developing a programming language
The author spent a decade developing the programming language Inko, transitioning from gradual to static typing and using Rust for the compiler. Recommendations include avoiding gradual typing, self-hosting compilers, and focusing on functionality over performance when building a new language. Building a language for long-term use is a time-consuming process that requires prioritizing user needs over technical complexities.
The Rust I Wanted Had No Future
The author preferred certain design choices in early Rust over the current state, such as the treatment of certain language features and performance considerations. They express a desire for a simpler, less performance-focused language with different priorities than those commonly held in the Rust community. The author reflects on their preferences for language design and the trade-offs they would have made for a more straightforward and expressive programming experience.
The Garbage Collection Handbook
The Garbage Collection Handbook is a comprehensive guide on automatic memory management, covering modern techniques and challenges faced by programmers. This second edition updates the handbook with insights from over 60 years of research and development in the field. It is essential reading for programmers looking to understand and navigate the complexities of garbage collection in modern programming languages.
PRACTICAL COMPILER CONSTRUCTION
"Practical Compiler Construction" is a textbook on writing compilers with annotated source code. The second edition is now available in print with improvements and bug fixes. The book covers compiler construction concepts and advanced techniques for optimizing code.
A Distributed Systems Reading List
This reading list covers materials for understanding distributed systems design and challenges. It includes resources on topics like latency, Amazon's organizational culture, Google's cutting-edge technologies, consistency models, theory, languages, tools, infrastructure, storage, Paxos consensus, and gossip protocols. The list aims to help readers adapt their thinking to effectively tackle distributed system complexities.
Matrix multiplication in Mojo
The text discusses matrix multiplication in Mojo. It is written by modular.com and can be found on docs.modular.com.
Building and operating a pretty big storage system called S3
Dr. Werner Vogels shares insights from working on Amazon's S3 storage system, highlighting the scale and unique challenges faced. S3's design incorporates innovative strategies to efficiently handle vast amounts of data across millions of hard drives while prioritizing customer experience. Vogels emphasizes the need for a broader perspective on software systems and the rewarding journey of scaling as an engineer at Amazon.
LADW_2017-09-04
This text discusses properties of vector spaces and matrices, particularly focusing on bases and eigenvalues. It establishes that any linearly independent system of vectors can be completed to form a basis in a finite-dimensional vector space. Additionally, it explains that operators in inner product spaces have an upper triangular matrix representation under certain conditions.
New Scaling Laws for Large Language Models
DeepMind's new paper challenges existing scaling laws for training large language models, proposing more optimal use of compute resources. By training a smaller 70-billion parameter model using their new scaling laws, DeepMind demonstrated superior performance compared to larger models like GPT-3 and their own 270-billion parameter model. This discovery may lead to more cost-effective and efficient training of large language models in the future.
king - man + woman is queen; but why?
The text explains how the word2vec algorithm transforms words into vectors for analyzing similarities and relationships between words. By using vector arithmetic, it can find analogies such as "king - man + woman = queen." Understanding word co-occurrences can provide insight into the meaning of words through the distributional hypothesis.
1-bit Model
Quantizing small models like Llama2-7B at 1-bit yields poor performance but fine-tuning with low-rank adapters significantly improves output quality. The HQQ+ approach shows potential in extreme low-bit quantization for machine learning models, reducing memory and computational requirements while maintaining performance. Training larger models with extreme quantization can lead to superior performance compared to training smaller models from scratch.
Human Knowledge Compression Contest
The Human Knowledge Compression Contest measures intelligence through data compression ratios. Better compression leads to better prediction and understanding, showcasing a link between compression and artificial intelligence. The contest aims to raise awareness of the relationship between compression and intelligence, encouraging the development of improved compressors.
A Gentle Introduction to LLVM IR
Learning LLVM IR can be beneficial for generalist working programmers to understand what their compiler is doing to create highly optimized code. LLVM IR is well-documented and can be treated as a slightly weird programming language. It is strongly typed and requires explicit type annotations. LLVM IR is a static single assignment form (SSA) IR and has properties that make optimizations simpler to write. It supports control flow operations, arithmetic instructions for different types, and memory operations. There are also LLVM intrinsics available for specific functions. However, some parts of LLVM's semantics, such as undefined behavior and pointer provenance, can be challenging to navigate.
How to round to 2 decimals with Python? [duplicate]
To round a number to 2 decimals in Python, the usual method is using round(value, significantDigit), but it can behave unexpectedly when the digit before the one being rounded is a 5. To address this, a workaround involves adding a small value to ensure proper rounding. This method allows for traditional rounding commonly used in statistics without needing to import additional libraries like Decimal. By incorporating this workaround into a function, you can achieve the desired rounding results without encountering the issue with numbers ending in 5.
Hypercomputation
Hypercomputation and super-Turing computation involve models of computation that can produce non-Turing-computable outputs. Introduced in the early 1990s, super-Turing computing is inspired by neurological and biological systems and serves as the foundation for Lifelong Machine Learning. Hypercomputation, a field introduced in the late 1990s, includes philosophical constructs and aims to compute functions beyond what a Turing machine can. The Church-Turing thesis states that any "computable" function can be computed by a Turing machine, but hypercomputers can compute functions that are not computable in the Church-Turing sense. Various hypercomputer models exist, ranging from theoretical concepts like oracle machines to more plausible models like quantum computing. Some proposals suggest that hypercomputation may be achievable through systems like neural networks or analog computers. Critics argue that hypercomputation is not physically realizable.
Bremermann's limit
Bremermann's limit is a maximum rate of computation that can be achieved in a self-contained system in the material universe. It is based on Einstein's mass-energy equivalency and the Heisenberg uncertainty principle. This limit has implications for designing cryptographic algorithms, as it can determine the minimum size of encryption keys needed to create an uncrackable algorithm. The limit has also been analyzed in relation to the maximum rate at which a system with energy spread can evolve into an orthogonal state.
numerical_recipes
The content provided is the table of contents for a book titled "Numerical Recipes: The Art of Scientific Computing, Third Edition." It includes various topics such as linear algebra, interpolation and extrapolation, integration of functions, evaluation of functions, special functions, random numbers, sorting and selection, root finding and nonlinear sets of equations, minimization or maximization of functions, eigensystems, and more.
2309.10668
This article discusses the relationship between language modeling and compression. The authors argue that large language models can be viewed as powerful compressors due to their impressive predictive capabilities. They demonstrate that these models can achieve state-of-the-art compression rates across different data modalities, such as images and audio. The authors also explore the connection between compression and prediction, showing that models that compress well also generalize well. They conclude by advocating for the use of compression as a framework for studying and evaluating language models.
Memory in Plain Sight: A Survey of the Uncanny Resemblances between Diffusion Models and Associative Memories
Diffusion Models (DMs) have become increasingly popular in generating benchmarks, but their mathematical descriptions can be complex. In this survey, the authors provide an overview of DMs from the perspective of dynamical systems and Ordinary Differential Equations (ODEs), revealing a mathematical connection to Associative Memories (AMs). AMs are energy-based models that share similarities with denoising DMs, but they allow for the computation of a Lyapunov energy function and gradient descent to denoise data. The authors also summarize the 40-year history of energy-based AMs, starting with the Hopfield Network, and discuss future research directions for both AMs and DMs.
K-Level Reasoning with Large Language Models
Large Language Models (LLMs) have shown proficiency in complex reasoning tasks, but their performance in dynamic and competitive scenarios remains unexplored. To address this, researchers have introduced two game theory-based challenges that mirror real-world decision-making. Existing reasoning methods tend to struggle in dynamic settings that require k-level thinking, so the researchers propose a novel approach called "K-Level Reasoning" that improves prediction accuracy and informs strategic decision-making. This research sets a benchmark for dynamic reasoning assessment and enhances the proficiency of LLMs in dynamic contexts.
Competitive Programmer's Handbook
The article discusses various algorithms and data structures used in computer programming, such as Kadane's algorithm, binary indexed trees, segment trees, Dijkstra's algorithm, and Floyd's algorithm. The author also explains concepts like successor graphs, index compression, and minimum spanning trees. The time complexity of each algorithm is also discussed.
Writing an OS in Rust
This blog series provides tutorials on creating a small operating system in the Rust programming language. Each post includes all the necessary code and is accompanied by a corresponding GitHub repository. The series covers topics such as creating a Rust executable without linking the standard library, building a bootable disk image, implementing VGA text mode, performing unit and integration testing, handling CPU exceptions, setting up the interrupt descriptor table, implementing paging and heap allocation, and exploring cooperative multitasking and the async/await feature of Rust. The posts also include status updates and information on supporting the author.
Ever wanted to make your own programming language or wondered how they are designed and built?
Crafting Interpreters is a book that provides everything you need to create your own programming language. It covers both high-level concepts like parsing and semantics, as well as technical details such as bytecode representation and garbage collection. The book guides you through building a language from scratch, including features like dynamic typing, lexical scope, functions, classes, and inheritance. It is available in multiple formats, including print, ebook, and online for free. The author, Robert Nystrom, is an experienced language developer who currently works at Google on the Dart language.
MemGPT: Towards LLMs as Operating Systems
MemGPT is a system that manages different memory tiers to provide extended context within the limited context window of large language models (LLMs). Using an OS-inspired design, MemGPT can handle unbounded context using LLMs that have finite context windows. It is successful in domains where existing LLMs' limited context windows severely limit their performance, such as document analysis and multi-session chat. MemGPT supports self-directed editing and retrieval, memory-hierarchy, OS functions, and event-based control flow to manage unbounded context.
Mathematics for Machine Learning
I'm sorry, but there is no content provided for me to summarize.
Generative Agents: Interactive Simulacra of Human Behavior
The article describes the concept of "generative agents", which are computational software agents that simulate believable human behavior for interactive applications. The agents are created using a large language model and can remember, reflect, and plan based on their past experiences. The article demonstrates generative agents by populating a sandbox environment with 25 agents, where users can observe and intervene as agents plan their days, form relationships, and coordinate group activities. The article discusses the architecture that enables generative agents and their potential applications in various domains.
Subcategories
- applications (15)
- computer_architecture (1)
- ethics (1)
- expert_systems (2)
- game_ai (5)
- knowledge_representation (4)
- machine_learning (324)
- natural_language_processing (3)
- planning_and_scheduling (2)
- robotics (2)
- software_development (1)
- theory (1)