One Line
Ribbit is a small and portable Scheme implementation that includes a virtual machine, compiler, and standard library.
Slides
Slide Presentation (7 slides)
Key Points
- The Ribbit system is a compact and portable Scheme implementation that conforms to the R4RS standard.
- It consists of three main components: the Ribbit VM (RVM), the Ribbit Scheme Compiler (RSC), and the standard library.
- The encoding of the RIBN (Ribbit Intermediate Byte Notation) has been optimized for compactness and efficiency.
- The decoding of the RIBN is done using a stack and decoding instructions.
- The Ribbit system has made improvements in encoding strategy, LZSS compression, R4RS compliance, portable I/O system, and compactness.
Summaries
21 word summary
Ribbit is a portable R4RS-compliant Scheme implementation with a compact 6.5 KB footprint, including a virtual machine, compiler, and standard library.
74 word summary
Ribbit is a portable Scheme implementation that follows the R4RS standard. It includes the Ribbit Virtual Machine (RVM), Ribbit Scheme Compiler (RSC), and a standard library. The RVM is portable and compact, while the RSC is an AOT compiler that generates a specialized RVM for each program. Ribbit uses optimized encoding with Variable-Length Quantity (VLQ) and LZSS compression for efficient encoding. It also has a compact 6.5 KB footprint and a portable I/O system.
123 word summary
The Ribbit system is a compact and portable Scheme implementation that adheres to the R4RS standard. It consists of the Ribbit Virtual Machine (RVM), the Ribbit Scheme Compiler (RSC), and a standard library. The RVM is portable and compact, while the RSC is an Ahead Of Time (AOT) compiler that generates a specialized RVM for each program. The encoding of the Ribbit Intermediate Byte Notation (RIBN) is optimized for compactness using an array of bytes with a base of 256. The decoding instructions construct the code graph from the RIBN. The new Ribbit system uses Variable-Length Quantity (VLQ) encoding and the LZSS compression algorithm for more efficient encoding. It also provides a portable I/O system and has a compact footprint of 6.5 KB.
408 word summary
The Ribbit system is a compact Scheme implementation that conforms to the R4RS standard. It includes variadic procedures, rest parameters, file I/O procedures, and measures to compact the code. The system consists of the Ribbit Virtual Machine (RVM), the Ribbit Scheme Compiler (RSC), and a standard library.
The RVM is portable and compact, while the RSC is an Ahead Of Time (AOT) compiler that generates a specialized RVM for each program. The standard library provides additional functionality through primitives and features defined in Scheme code.
The encoding of the Ribbit Intermediate Byte Notation (RIBN) is crucial for the system's compactness. The RIBN is an encoded form of the RVM code that is decoded to create the code graph used by the interpreter. The encoding has been optimized in the current version using an array of bytes with a base of 256. It also supports loops and join points in the code graph, reducing code growth.
Decoding the RIBN involves a stack and decoding instructions. These instructions have a type and argument encoded in either a short or long form. The decoding instructions construct the code graph from the RIBN.
The Ribbit system provides a compact and portable Scheme implementation that conforms to the R4RS standard. It utilizes the Ribbit Virtual Machine and Scheme Compiler to generate a tailored RVM for each program. The encoding of RIBN and decoding instructions contribute to the system's compactness and efficiency.
The new Ribbit system uses Variable-Length Quantity (VLQ) encoding for more efficient and flexible encoding of Scheme programs. It adapts the encoding strategy to the RIBN base and specializes it to the code graph produced by the compiler.
The LZSS compression algorithm compresses RIBN codes by replacing recurring slices of text with back-pointers. The Ribbit system adheres to the R4RS standard and implements it using design choices that optimize for size.
Ribbit provides a portable I/O system that adapts to different host languages. Input and output ports are represented as ribs with specific layouts. The system has been evaluated in terms of its footprint and execution speed. The footprint of the REPL is 6.5 KB, and the execution speed compares well with other Scheme interpreters.
In conclusion, the Ribbit system has made improvements in encoding strategy, encoding specialization, LZSS compression, R4RS compliance, portable I/O system, and compactness. These improvements have resulted in a more efficient and flexible REPL implementation that adheres to the R4RS standard in a compact footprint of 6.5 KB.
474 word summary
The Ribbit system is a compact Scheme implementation that runs on the Ribbit Virtual Machine (RVM). It supports a Foreign Function Interface (FFI) and conforms to the R4RS standard. The system includes variadic procedures, rest parameters, file I/O procedures, and measures to compact the code. The RVM, RSC, and standard library are the three main components of the Ribbit system. The RVM is portable and compact, while the RSC is an Ahead Of Time (AOT) compiler that generates a specialized RVM for each program. The standard library provides additional functionality through primitives and features defined in Scheme code.
The encoding of the RIBN (Ribbit Intermediate Byte Notation) is crucial for the system's compactness. The RIBN is an encoded form of the RVM code that is decoded to create the code graph used by the interpreter. The RIBN encoding has been optimized in the current version using an array of bytes with a base of 256, which is more space efficient. The encoding also supports loops and join points in the code graph, reducing code growth.
Decoding the RIBN involves a stack and decoding instructions. These instructions have a type and argument encoded in either a short or long form. The RSC compiler assigns ranges of codes to each instruction and argument, allowing efficient encoding and decoding. The decoding instructions construct the code graph from the RIBN.
The Ribbit system provides a compact and portable Scheme implementation that conforms to the R4RS standard. It utilizes the Ribbit Virtual Machine and Scheme Compiler to generate a tailored RVM for each program. The encoding of RIBN and decoding instructions contribute to the system's compactness and efficiency.
The new Ribbit system uses Variable-Length Quantity (VLQ) encoding for more efficient and flexible encoding of Scheme programs. It adapts the encoding strategy to the RIBN base and specializes it to the code graph produced by the compiler. The programmer can choose between the original encoding and the optimal encoding, which searches for the best ranges for each decoding instruction.
The LZSS compression algorithm compresses RIBN codes by replacing recurring slices of text with back-pointers. The Ribbit system adheres to the R4RS standard, which defines essential procedures and syntaxes. It implements the standard using design choices that optimize for size.
Ribbit provides a portable I/O system that adapts to different host languages. Input and output ports are represented as ribs with specific layouts. The system has been evaluated in terms of its footprint and execution speed. The footprint of the REPL is 6.5 KB, and the execution speed compares well with other Scheme interpreters.
In conclusion, the Ribbit system has made improvements in encoding strategy, encoding specialization, LZSS compression, R4RS compliance, portable I/O system, and compactness. These improvements have resulted in a more efficient and flexible REPL implementation that adheres to the R4RS standard in a compact footprint of 6.5 KB.
1141 word summary
The Ribbit system is a compact Scheme implementation running on the Ribbit Virtual Machine (RVM). It supports a Foreign Function Interface (FFI) that allows extensions to the RVM directly from the program's source code. The system has been extended to offer conformance to the R4RS standard while staying compact. This has resulted in a R4RS compliant REPL that fits in a 7 KB Linux executable. The main enhancements to the system include support for variadic procedures and rest parameters, implementation of all required file I/O procedures, and various measures to better compact the generated code. The choice to support the R4RS Scheme standard was made due to its practicality and small size, as well as the availability of existing code that can run in an R4RS system.
The Ribbit system consists of three main components: the Ribbit VM (RVM), the Ribbit Scheme Compiler (RSC), and the standard library. The RVM is designed to be portable and compact, with a simple stack machine architecture and a focus on memory management. The RSC is an Ahead Of Time (AOT) compiler that combines the source program with the standard library to generate a specialized RVM in the chosen host language. The compiler uses annotations within the RVM's code to selectively include, exclude, or adapt sections of the code, resulting in a tailored RVM for each program. The standard library provides additional functionality to the RVM through primitives and features defined in Scheme code.
The encoding of the RIBN (Ribbit Intermediate Byte Notation) is a key aspect of the system's compactness. The RIBN is an encoded form of the RVM code that is decoded by the RVM to create the code graph used by the interpreter. In the previous version of Ribbit, the RIBN was a string of characters with a base of 92, but this has been optimized in the current version. The RIBN encoding now uses an array of bytes with a base of 256, which is more space efficient in compiled hosts. The RIBN encoding also supports the representation of loops and join points in the code graph, allowing for the expression of sharing and reducing the exponential growth of code when multiple non-tail if forms are in sequence.
The decoding of the RIBN is done using a stack and a set of decoding instructions. The decoding instructions have a type and an argument, which can be encoded either in a short form or a long form. The RSC compiler assigns ranges of codes to each type of decoding instruction and argument, allowing for efficient encoding and decoding of the RIBN. The decoding instructions are used to construct the code graph from the RIBN, with each instruction adding an RVM instruction to the sequence and modifying the decoding stack state.
In conclusion, the Ribbit system provides a compact and portable Scheme implementation that conforms to the R4RS standard. Through its use of the Ribbit Virtual Machine and the Ribbit Scheme Compiler, it is able to generate a tailored RVM for each program while maintaining a small size. The encoding of the RIBN and the decoding instructions further contribute to the system's compactness and efficiency.
The Ribbit system has been improved with a new encoding strategy that allows for more efficient and flexible encoding of Scheme programs. The encoding is based on Variable-Length Quantity (VLQ) encoding, which uses a starting value in the accumulator equal to the difference between the code and the lower boundary of the range. This allows for more compact encoding of instructions.
The previous Ribbit system used a fixed RIBN base of 92 and had ranges determined through trial and error on the source code of the REPL. The ranges were accessible to the decoder through a table indicating the size of the short form of each decoding instruction. The new Ribbit system still uses the same encoding strategy but adapts it to the RIBN base of the RVM implementation and specializes it to the code graph produced by the compiler. The programmer can choose between the original encoding, which is backward compatible and fast to generate, and the optimal encoding, which searches for the best ranges for each decoding instruction based on a ratio between the number of bits needed to encode the range and the number of bits saved by encoding it with a single RIBN code.
To support the optimal encoding, the annotation system has been extended to allow for the replacement of information known by the compiler. This is done through an extended replace annotation. The JavaScript RVM provides an example where an internal procedure of the compiler is used to replace a sequence of codes with a string generated by the list->host procedure. The feature system is used to automatically choose the right decoder implementation in the RVM based on the encoding used.
The LZSS compression algorithm is used to compress the RIBN codes, replacing recurring slices of text with back-pointers to previous occurrences. This algorithm is chosen for its simplicity and compactness, as more complex algorithms like Zip or Bzip2 would take up more space than they save.
The R4RS library in Ribbit adheres to the R4RS standard to compare its implementation to other Scheme interpreters and compilers. The R4RS standard offers a good balance between expressiveness and a relatively small number of essential features. The R4RS standard defines 164 essential procedures and 18 essential syntaxes, while the R5RS standard defines 207 essential procedures and 26 essential syntaxes. The R4RS standard is implemented in Ribbit using design choices and tradeoffs that optimize for size. For example, the fold procedure is used to define procedures like +, *, and -, which reduces the size of the generated code.
Ribbit provides a portable I/O system that adapts to different host languages. Input and output ports are represented as ribs with specific layouts. The input-port includes a file descriptor field and a peeked-char/open? field, while the output-port includes a file descriptor field and an open? field. The RVM provides primitive procedures for I/O operations, which are then used by Scheme procedures defined on top of them.
The Ribbit system has been evaluated in terms of its footprint and execution speed. The footprint of the REPL, including the generated RVM for the x86 assembly host, is 6.5 KB when using the Prim-no-arity, Optimal (256), and LZSS compilation settings. The execution speed of the x86 REPL compares well with the Gambit Scheme Interpreter, with programs compiled with Ribbit being faster in most cases. The JavaScript host has a slightly larger footprint and slower execution speed compared to the x86 assembly host.
In conclusion, the Ribbit system has made improvements in encoding strategy, encoding specialization, LZSS compression, R4RS compliance, portable I/O system, and compactness. These improvements have resulted in a more efficient and flexible REPL implementation that adheres to the R4RS standard in a compact footprint of 6.5 KB.