### Index # Help index Please start by reading the [Manual](Manual.md) You may find yourself coming back to * [the description of the Carp language](LanguageGuide.md) * [its libraries.](Libraries.md) Also there is documentation about: * [C Interop](CInterop.md); * [how to contribute](Contributing.md); * [support for implementig interfaces for datatypes based on their members](Derive.md); * [custom resource deallocation](Drop.md); * [the dynamic evaluator VM architecture](EvaluatorVM.md); * [historical dynamic evaluator semantics notes](DynamicSemantics.md); * [programming embedded devices](Embedded.md); * [formatted output with (fmt) and (fstr)](Format_Strings.md); * [hacking the compiler itself](hacking.md); * [working with the REPL](HowToRunCode.md); * [how to install and set up Carp](Install.md); * [working with Macros](Macros.md); * [Memory Management](Memory.md); * [an invitation to use Carp for sound and graphics](Multimedia.md); * [common patterns in Carp programs](patterns.md); * [using quasi-quotation in macros and dynamic functions](Quasiquotation.md); * [things to remember for each new Carp release](ReleaseChecklist.md); * [some clarification on the terminology we use to explain things](Terminology.md); * [editor support and tooling](Tooling.md). --- ### CInterop # C Interop This is an extension of what is covered in the [Language Guide](./LanguageGuide.md#c-interop). ## Content - [How Carp generates identifiers]("#how-carp-generates-identifiers") - [Managed types](#managed-types) - [String](#string) - [Array](#array) - [Embedding C code in Carp](#embedding-c-code-in-carp) - [`deftemplate`](#deftemplate) - [`Basic example`](#basic-example) - [`Generics`](#generics) - [`emit-c`](#unsafe-emit-c) - [`preproc`](#unsafe-preproc) - [Registering Types](#register-types) - [Callbacks](#callbacks) - [Headerparse](#headerparse) ## How Carp generates identifiers When creating a function or def it might be useful to know what identifier gets generated on the C side. Here are some examples: ```clojure (def a-def 100) ; => a_MINUS_def (defn hello [] (println* "Hello")) ; => hello (sig true? (Fn [Bool] Bool)) (defn true? [b] b) ; true_QMARK_ (defmodule Reverse (defn hello [] (println* "Goodbye")) ; => Reverse_hello (defmodule ReReverse (defn hello [] (println* "Hello")))) ; => Reverse_ReReverse_hello ; Generic signature (sig print-first-and-add (Fn [(Ref (Array a)) b b] b)) (defn print-first-and-add [arr x y] (do (println* (Array.unsafe-first arr)) (+ x y))) ; Generates no code until it is called (print-first-and-add &[1] 1 1) ; => print_MINUS_first_MINUS_and_MINUS_add__int_int (print-first-and-add &[@"hello"] 2l 40l) ; => print_MINUS_first_MINUS_and_MINUS_add__String_Long ``` Looking at the examples should help illustrate how Carp transforms identifiers before producing C code, but let's break it down: Carp will replace illegal characters in C with a string representation of them (`- => _MINUS_`, `? => _QMARK_`, etc...) If in modules it will prefix the identifier with the modules name. When the arguments to a function are generic it will suffix the types to the identifiers, the identifiers are not able to be generated until it is used. If a function is potentially generic but you don't want it to be you can add a non-generic signature to it to make Carp generate your function like in our `true?` example. This process is called *mangling* and is necessary to ensure that identifiers that are valid in Carp but invalid in C don't produce invalid C code. ### Overriding Carp's default C identifier names When creating bindings to an existing C library in Carp, it's inconvenient to have to replicate C identifiers exactly as they're declared in C. For example, due to mangling, you couldn't wrap your Carp bindings in a module, since the resulting identifiers would be prefixed, and probably incorrect. It would be inconvenient and tedious to have to replicate existing C identifiers exactly whenever you had to create bindings to an existing library , so, to help with this, `register` and `register-type` accepts an optional argument to specify what identifiers to use: ```clojure (defmodule CURL (register-type HttpPost "curl_httppost") (register form-free (Fn [(Ref HttpPost)] ()) "curl_formfree")) ``` This enables you to define whatever structure you want in Carp code (for example, here we wrap cURL bindings in a CURL module) while ensuring the emitted identifiers are correct and map to the identifiers used by the existing C library you're calling. For example, the `form-free` identifier in Carp would normally be subject to mangling and emitted as `form_MINUS_free`, but the override argument ensures this identifier is emitted as `curl_formfree` instead. Likewise, you can override the C identifiers Carp generates for code exclusively defined in Carp. For instance, you may want to migrate safety-critical code in an existing C program into Carp, then call the resulting safe C code in your original C program. This can become tedious if your Carp code utilizes a lot of nested modules, custom types, or special characters in identifiers. You can use the `c-name` meta field to explicitly set the C identifier Carp generates for a given definition. This can help make your compiled C more readable and easier to call from other languages. For example, given the definition and c-name call: ```clojure (defn foo-bar [] 2) (c-name foo-bar "foo_bar") ``` Carp will generate a corresponding identifier `foo_bar` in its C output, instead of the default `foo_MINUS_bar`. ## Managed types In Carp types like `String` and `Array` are _managed_ types in that they are allocated on the Heap and the compiler will automatically free the allocated memory when they go out of scope. We'll see how we can go from these managed type to C and back. ### String To use a managed `String` with a C function requiring a `char*` you can use the `String.cstr` function that will turn your `(Ref String)` into `(Ptr CChar)`: ```clojure (register puts (Fn [(Ptr CChar)] ())) (let [a-str @"A string."] (puts (String.cstr &a-str))) (puts (String.cstr "Hello")) ``` You may want to hide the C type from the end-user: ```clojure (defmodule MyMod (hidden puts-c) (private puts-c) (register puts-c (Fn [(Ptr CChar)] ()) "puts") (defn puts [str-ref] (puts-c (String.cstr str-ref)))) (let [a-str @"A string."] (MyMod.puts &a-str)) (MyMod.puts "Hello") ``` --- If you are given a `char*` and want to turn it into a managed `String` you can use `String.from-cstr`. It will allocate and copy the content of the C string. ```c // static-str.h char* returns_a_static_str() { return "Hello"; } ``` ```clojure (relative-include "static-str.h") (register returns-a-static-str (Fn [] (Ptr CChar)) "returns_a_static_str") (let [a-str (String.from-cstr (returns-a-static-str))] (println* (String.concat &[a-str @" " @"Carp"]))) ``` --- The function you're consuming might be allocating the string on the Heap for you. In that case you can declare the function as returning a managed `String`. However this might be unsafe, you need to ensure that the string is actually Heap-allocated and that the allocator is the same as the one that Carp is using. ```c char* returns_a_heap_string() { char *hello = "Hello from the heap"; char *str = malloc((strlen(hello)+1)); strcpy(str, hello); return str; } ``` ```clojure (relative-include "heap-string.h") (register returns-a-heap-str (Fn [] String) "returns_a_heap_string") (let [a-str (returns-a-heap-str)] (println* a-str)) ``` If you are the one writing the C code, you can use the `CARP_MALLOC` macro to ensure you are using the same allocator as the Carp compiler: ```c char* returns_a_heap_string() { char *hello = "Hello from the heap"; char *str = CARP_MALLOC((strlen(hello)+1)); strcpy(str, hello); return str; } ``` ### Array `Array.unsafe-raw` can be used in case you have a function taking an C array as a parameter. ```c int sum(int *arr, int len) { int acc = 0; for (int i = 0; i < len; i++) { acc += arr[i]; } return acc; } ``` ```clojure (relative-include "sum.h") (register sum-c (Fn [(Ptr Int) Int] Int) "sum") (let [ints [1 2 3]] (println* (sum-c (Array.unsafe-raw &ints) (Array.length &ints)))) ``` Again, you might want to wrap the bare C function in more Carp-esque interface. ```clojure (relative-include "sum.h") (defmodule MyMod (hidden sum-c) (private sum-c) (register sum-c (Fn [(Ptr Int) Int] Int) "sum") (sig sum (Fn [(Ref (Array Int))] Int)) (defn sum [ints] (sum-c (Array.unsafe-raw ints) (Array.length ints)))) (MyMod.sum &[1 2 3]) ``` --- In cases where the consuming function takes ownership over the data, `Array.raw` can be used. It becomes the responsibility of the consuming function to call `free` on the pointer and any managed types it contains. ```c // printall.h void println_all(char **arr, int len) { for (int i = 0; i < len; i++) { printf("%s\n", arr[i]); CARP_FREE(arr[i]); } CARP_FREE(arr); } ``` ```clojure (relative-include "printall.h") (register println-all (Fn [(Ptr String) Int] ()) "println_all") (let [lines [@"One" @"Two" @"Three"] len (Array.length &lines)] (println-all (Array.raw lines) len)) ``` ## Embedding C code in Carp When interfacing C libraries it is sometimes beneficial to wrap the libraries function with some custom C code. An entirely valid method is the write your code in a header file, include it from the Carp side and `register` it: ```c // print.h // String is a carp core alias for char* void print_that_takes_ownership(String str) { printf("%s", str); CARP_FREE(str); } ``` ```clojure (relative-include "print.h") (register print (Fn [String] ()) "print_that_takes_ownership") (print @"Print this!") ``` However you might prefer to keep your C code close to your Carp code, enter `deftemplate`... ### `deftemplate` #### Basic example We can instead define the previous example like so: ```clojure (deftemplate print (Fn [String] ()) "void $NAME(String str)" "$DECL { printf(\"%s\", str); CARP_FREE(str); }") (print @"Print this!") ``` Let's break down what's going on here: The **first** argument to `deftemplate` is the name we'll use to refer to the function. The **second** is a type signature and is identical to the one found in our previous `register` call. The **third** is our function declaration, it'll be injected at the top of the generated C file. The **last** argument represent the function definition. Two more things to look at: `$NAME` is a variable that will be derived from the name you've given the function plus any module it's defined in, so no need to worry about name clashes with other `print` functions in other modules. `$DECL` will be replaced with the declaration passed as a third argument when the function is defined So we've seen how `deftemplate` can be used to keep Carp and C code close to each other and help you write less code in general but it's real power lies somewhere else... #### Generics Let's say one would like to write a function that adds two numbers, it would be tedious to write a version for every type of number, let's see how `deftemplate` can help us with that. ```clojure (deftemplate add (Fn [a a] a) "$a $NAME($a x, $a y)" "$DECL { return x + y; }") (add 1 2) (add 20l 22l) (add 2.0f 5.0f) ; Can't do that as they're different types ; (add 2.0f 22l) ``` Carp allows us to use generic type in type signatures, `a` in that example. You can use `$` plus the generic name you used in your signature to refer to that type in your C code. Carp will then generate a separate function everytime the template is used with a different type. Warning! You'll need to be careful when calling that function as you've lost all type safety the Carp compiler guarantees. You will have to hope the C compiler will catch it. ``` clojure (deftemplate add (Fn [a a] a) "$a $NAME($a x, $a y)" "$DECL { return x + y; }") (add @"A string" @" another string") ``` This thankfully result in this Clang error, but it's probably good not to rely on it. ``` out/main.c:9153:29: error: invalid operands to binary expression ('String' (aka 'char *') and 'String') return x + y; ~ ^ ~ 1 error generated. ``` ### `Unsafe.emit-c` While `deftemplate` is flexible and sufficient for most use cases, there are certain scenarios in which it won't accomplish what you need. For example, some C macros, such as c11's `static_assert` require a string literal argument. `deftemplate` can't accomplish this. In such cases, you can use `Unsafe.emit-c` to emit a literal string in the Carp compiler's C output. `emit-c` is perfect for scenarios like `static_assert` calls. Assuming `static_assert` is `register`ed as `static-assert`, we can use `emit-c` in the following way to ensure it is passed a string literal in the compiler's emitted C code: ``` (register static-assert (Fn [a C] ())) (static-assert 0 (Unsafe.emit-c "\"foo\"")) ``` which will emit the corresponding C: ``` static_assert(0, "foo") ``` `emit-C` returns values of the `C` type, a special type that represents literal C code in Carp. ### `Unsafe.preproc` The Carp compiler emits C code in an order that ensures the dependencies of functions are available before functions are called. Sometimes, you may want to include C code before the Carp compiler's output. For instance, you might want to provide some preprocessor directives to a C compiler. The `Unsafe.preproc` function was designed with this use case in mind. You can use `preproc` to inject arbitrary C code prior to the Carp compiler's normal C output. Any code passed to `preproc` will be emitted after file `includes` but before any other emitted C code. `preproc` takes a value of type `C` as an argument, so it must be used in combination with `Unsafe.emit-c`. The C code you pass to `preproc` isn't checked at all, so be careful! If you do define C symbols using `preproc`, you'll still need to call `register` to reference them in Carp code. For example, the following snippet uses `preproc` to make a C macro and function available in the Carp compiler's output and then calls `register` to reference these symbols in the `main` function in the Carp source: ``` (Unsafe.preproc (Unsafe.emit-c "#define FOO 0")) (Unsafe.preproc (Unsafe.emit-c "void foo() { printf(\"%d\\n\", 1); }")) (register FOO Int) (register foo (Fn [] ())) (defn main [] (do (foo) (IO.println &(fmt "%d" FOO)))) ``` You can use this technique to add provisional definitions you need to reference in compiler output. If your helper functions, macros, or preprocessor directives are lengthy or complex, you may want to define them in a separate `h` file and `relative-include` it in your Carp source instead. ### Registering Types Carp supports a few different ways of registering types defined in C. You can register types using the `register-type` function. Calling `register-type` with only a symbol argument registers the C type with a name corresponding to the symbol. For example, the following code registers the C type `A` as the type `A` in Carp. ```c typedef int A; ``` ```clojure (register-type A) ``` After this call to `register-type`, you can use the type `A` anywhere type names are valid in Carp code. For example, you can use it in function signatures: ```clojure (sig a-prn (Fn [A] String)) ``` The prior type registration *only* registers the type name in Carp. In other words, the type is entirely "opaque" from the perspective of your Carp program. Carp knows the type exists, but it knows nothing about its implementation or how to construct values of the type--all of that is left up to your C code. If you want to construct values of this type from Carp code, you have two options: 1. You can define your own initializers for the type in C and register them in Carp. 2. You can use `register-type` to generate initializers for the type in Carp. If you define an initializer for the type in C, you can access it from Carp by using `register`: ```c typedef int A; A initializer() { return 0; } ``` ```clojure (register-type A) (register initializer (Fn [] A)) ;; returns a value of type A (initializer) ``` Alternatively, you can add a non-empty array of type members in your `register-type` call to have Carp generate initializers, getters and setters, and printing functions for the external type. The initializer Carp generates will only initialize the fields you specify. If you omit or misname a field, the generated initializer might cause errors. ```clojure (register-type B []) :i B => B : Type init : (Fn [] B) prn : (Fn [(Ref B q)] String) str : (Fn [(Ref B q)] String) } (register-type C [x Int]) :i C => C : Type C : Module { init : (Fn [Int] C) prn : (Fn [(Ref C q) String]) str : (Fn [(Ref C q) String]) set-x : (Fn [C, Int] C) set-x! : (Fn [(Ref C q), Int] ()) update-x : (Fn [C, (Ref (Fn [Int] Int) q)] C) x : (Fn [(Ref C q)] (Ref Int q)) } ``` The `prn` and `str` functions for the type will also automatically implement their corresponding interfaces. Be mindful that Carp *does not manage the memory associated with external types by default!* Unlike types defined in Carp, Carp will not generate `copy` and `delete` functions for registered types. If you use generated initializers for a registered type for convenience, remember that you still need to manage the memory associated with values of the type manually. If you want Carp to manage the memory for a registered type, you can provide implementations of the `copy` and `delete` interfaces. If needed, you can override the name Carp emits for a registered type by providing an additional string argument. This comes in handy when the type's name in C does not follow lisp or Carp naming conventions. For example, the type in C might begin with a lowercase letter, while Carp requires all types to begin with uppercase letters: ```clojure ;; Emitted in C code as "A" (register-type A) ;; Emitted in C code a "a_type" (register-type A "a_type") ;; Emitted in C code as "b_type" (register-type B "b_type" [x Int]) ``` ## Callbacks Some C APIs rely on callbacks, let's define a C function that accepts a callback and an argument and returns the result of calling that function as an example: ```clojure (deftemplate runner (Fn [(Ptr ()) (Ptr ())] a) "$a $NAME(void* fnptr, void* args)" "$DECL { return (($a(*)(void*))fnptr)(args); }") ; Using a lambda capturing variables from its environment (let [x 20 y 22 fnfn (fn [] (+ @&x @&y))] (= (runner (Function.unsafe-ptr &fnfn) (Function.unsafe-env-ptr &fnfn)) 42)) ; Using a static function (defn double [x] (Int.* @x 2)) (let [x 42] (= (runner (Function.unsafe-ptr &double) (Unsafe.coerce &x)) 84)) ``` In the first example we want to use a lambda capturing some variable, we can use `Function.unsafe-ptr` to get a `void*` to the function and in the case of lambdas capturing environment the first argument to that function is the environment so we have to use `Function.unsafe-env-ptr` to pass in that environment. In the second example we want to use a static function so we can use `Function.unsafe-ptr` again, and the argument we pass in needs to be coerced from a `Ref` into a `(Ptr ())`. Because everything gets turned into a void pointer all type safety is lost so it is the responsibility of the caller to ensure the operation is safe. It is also important to ensure the lifetime of the `Ptr` doesn't not exceed the lifetime of the function/env it represents. ## Headerparse `headerparse` is a Haskell script to aid in writing C bindings by parsing a C header and generating `register` and `register-type` for you. It resides in the `./headersparse` folder in Carp source repo and can be used in the following way: ```sh stack runhaskell ./headerparse/Main.hs -- ../path/to/c/header.h ``` The script accepts the following flags: * `[-p|--prefixtoremove thePrefix]` Removes a prefix from the C identifiers * `[-f|--kebabcase]` Converts identifiers to kebab-case * `[-c|--emitcname]` Always emit the C identifier name after the binding ### Example Invoking the script on this C header: ```sh stack runhaskell ./headerparse/Main.hs -- -p "MyModule_" -f ../path/to/aheader.h ``` ```c // aheader.h bool MyModule_runThisFile(const char *file); ``` Will output the following: ```clojure (register run-this-file (λ [(Ptr CChar)] Bool) "MyModule_runThisFile") ``` --- ### Contributing # Contributing Guide Thank you for considering contributing to Carp! This document currently focuses on developer contributions but we welcome all kinds of contributions. ## Community The best place to start is to join the Carp Gitter channel over at [https://gitter.im/carp-lang/Carp](https://gitter.im/carp-lang/Carp). ## Understanding the Compiler See [Hacking.md](hacking.md) for a gentle introduction to the Carp compiler internals. ## Committing to the repo We follow [Conventional Commits](https://www.conventionalcommits.org), there is a `commit-msg` hook to ensure the messages follow the convention, please make sure you have run `./scripts/git-hooks/setup.sh` before you commit the first time so that the hook is in place. License ------- Carp is currently released under the terms of the ASL 2.0 license. --- ### Derive # Derive `derive` is a mechanism that automatically determines how to implement interfaces for datatypes based on their members. It also allows you to write your own rules for `derive`, called a `deriver`. If you’d like to learn how to `derive` interfaces for your types, read the [first section](#i-using-derive) of this document. If you’d like to provide a deriver for an interface, read [the second section](#ii-writing-derivers) of this document. ## I: Using `derive` In most cases, using `derive` should be as simple as calling it with the type name and interface to implement: ```clojure (deftype Point [ x Int y Int ]) (derive Point zero) (derive Point =) ; if you’d like to generate a different function name ; pass it as a third argument. This is useful to avoid ; name collisions (derive Point str my-str) ``` The code above will provide implementations of `zero` and `=` for the type `Point` based on its members. The prerequisites for this to work are that types are *concrete*—there are no type variables present—and *its members implement the interface*. This is because the definition of both functions hinges on the definition of its members: `zero` on a type is just `zero` of all its members, equality of a type just equality of all of its members. Carp only provides automatic derivation of `=`, `zero`, and `str`. Since the code you depend on might provide other derivers, you can inspect them by calling `(derivables)`. If you want to find out if a certain interface is derivable, you can call `(derivable? )`. Please note that the interface name needs to be quoted. If either of the preconditions above is not met, you will have to write your own version of these functions, and may not use `derive`. Some users might want to be able to derive update interfaces that take a type, do the same thing to all its members, and return it. A good example for this in the context of `Point` is `inc`. While generally this might require you to write your own deriver—see [section II](#ii-writing-derivers) of this document to learn how to do that—, Carp provides a special dynamic function called `make-update-deriver`. It takes a unary interface that updates a value and returns it, and extrapolates a definition for the encompassing type. This is what this would look like for `Point`: ```clojure (make-update-deriver 'inc) ; notice the quote (derive Point inc) (inc (Point.zero)) ; => (Point 1 1) ``` While this can be useful at times, it is limited to the special case of functions outlined above: it can only used on functions you would also be able to pass into `update-` style functions. ## II: Writing derivers Sometimes you might want to provide your own derivation strategy for other interfaces than the ones provide out of the box. In these cases you can provide your own deriver using `make-deriver`. The dynamic function `make-deriver` takes three arguments: the quoted name of the interface, the names of the arguments it will be passed, and a function that, given a type, knows how to generate an implementation for that type. This might sound a little strange, so let’s consider the deriver for `zero` as an example: ```clojure (make-deriver 'zero [] (fn [t] (cons 'init (map (fn [_] '(zero)) (members t))))) ``` It usually makes sense to read `make-deriver` similar to a function definition: its interface name is `zero`, which takes no argument, and we know that if we’re given a type we can create a definition for `zero` if we just emit a call to `zero` for every member, wrapped in an `init`. Thus the definition for `zero` for the type `Point` from above will end up looking like this: ```clojure (init (zero) (zero)) ``` `derive` itself will emit all the surrounding boilerplate, such that the entire call to `(derive Point zero)` will be rewritten to: ```clojure (defmodule Point (defn zero [] (init (zero) (zero))) (implements Point.zero zero) ) ``` This means that all a deriver has to know is how to generate a function body when it’s given a type. Since it also has control over the argument names, it can use the arguments in its definition as well. --- ### Drop # Drop One of the “special” interfaces implementable by any type in Carp is `drop`, the signature of which is `(Fn [&a] ())`. It takes a reference to a type and is run before that type is deleted. This is meant for types that need special treatment before being deallocated, such as files that need to be closed. ```clojure (deftype A []) (defmodule A (sig drop (Fn [(Ref A)] ())) (defn drop [a] (IO.println "Hi from drop!")) ) (defn main [] (let [a (A)] ())) ``` In the case above, `A.drop` will be run and `Hi from drop` will be printed when the `let` scope ends. --- ### DynamicSemantics # Dynamic Semantics This document describes historical goals for rewriting Carp's dynamic evaluator. The evaluator has since moved to a VM-backed architecture. For the current implementation, see [Dynamic Evaluator VM](EvaluatorVM.md). ## Goals of the rewrite * Fix the various bugs related to dynamic evaluation that has been found (see "Relevant issues" below). * Add missing features that are to be expected in a dynamic Lisp (see below). * Make it easy to extend the dynamic evaluator with new features in the future. ## Relevant issues * https://github.com/carp-lang/Carp/issues/560 * https://github.com/carp-lang/Carp/issues/555 * https://github.com/carp-lang/Carp/issues/545 * https://github.com/carp-lang/Carp/issues/476 * https://github.com/carp-lang/Carp/issues/556 * https://github.com/carp-lang/Carp/issues/659 * https://github.com/carp-lang/Carp/issues/660 * https://github.com/carp-lang/Carp/issues/453 ## Desired features (currently missing) * Documentation on how to use the dynamic language and the macro system * Complete macro facilities (quasiquoting, splicing, complete error reporting, etc) * Dynamic stack traces * Auto completion of user-defined names
## Index [TODO] ## 0. Terms used in this document * form : Any valid Carp data struture as represented in text. * top level : Any form that isn't embedded in another form. * Static Carp : The compiled version of the Carp language. * Dynamic Carp : The interpreted, functional, GC'ed version of the Carp language. ## 1. Scoping Rules Related issues: * https://github.com/carp-lang/Carp/issues/659 Questions: #### How does Carp figure out what the value of the symbol X is? Lexical scoping (look in the current scope, then any enclosing scope, up until global scope). Things that create scopes: - function definitions (defn, defndynamic, fn) - let - modules #### How do you set the value for symbol X? `(set! )` #### Are there any reserved names? Yes (see the Parsing module for more info) - defn - def - do - while - fn - let - break - if - match - true - false - address - set! - the - ref - deref - with More things should be moved to the reserved list, actually. The `:rest` token in defmacro is also reserved. #### What is a keyword? There are no keywords. Maybe will be in the macros, see this implementation https://gist.github.com/sdilts/73a811a633bb0ef3dd7e31b84a138a5a. #### Are there different namespaces for dynamic and static Carp? They use the same modules but dynamic lookup will only find dynamic functions, and static lookup will only find static functions. ### 1.1 Global Variables Questions: #### Are global variables mutable? Yes. #### How are they mutated? When do these mutations come into affect? Using `set!`. The mutation comes into effect immedately (using IORefs internally). #### Do global variables have lexical or dynamic scope? Lexical (no dynamic scope for anything). ### 1.2 Local variables Questions: #### Are local variables mutable? Yup. #### When do local variables come in and out of scope? Lexical scoping rules, functions and let create new variables. #### What is a closure? What are the important rules for variables inside closures? No captured variables are mutable. The dynamic lambdas captures the whole environment at the time the closure is created (when the `(fn ...)` form is evaluated). ### 1.3. Namespace Rules Questions: #### Given symbols `a` in the `Foo` module and `a` in the `Bar` module, how do I refer to each of them? Using `.`, Foo.a and Bar.a. By using `(use )` you can avoid having to specify the module. #### What happens if multiple modules are imported and they contain the same symbol? Runtime error when looking up the symbol. #### Given the symbols`Foo.a` and `Bar.a`, exist, which symbol does `a` refer to? Neither, unless any single one of the modules (Foo/Bar) is imported with `use`. If both are imported the lookup is an error since it can't be resolved to a single value. #### Do functions and variables live in the same namespace? Yes. Types live in a different namespace. ### 1.4 Definitions Questions: #### What kinds of definitions are there and how are they created? Dynamic context: - defndynamic (creates dynamic functions) - defdynamic (creates dynamic global variables) - defmacro (creates macros) Static context: - defn (creates static functions) - def (creates static global variables) - deftype (for defining product- and sumtypes) - register (for making external functions available) All contexts: - defmodule ## 2. Evaluation Rules Related issues: * https://github.com/carp-lang/Carp/issues/555 Questions: #### When are macros evaluated? #### When are symbols evaluated? #### When are forms evaluated? #### Are forms evaluated left-to-right or right-to-left? #### How does error reporting work? ### 2.1 Macros Questions: * What is a macro? * What functions are available at macro-expansion time? * What is quasi-quoting and what is its syntax? * What is splicing, and what is its syntax? ### 2.2 REPL Questions: * How does the REPL know when to evalutate something in the dynamic or static context? * When does it decide to run the given code in the dynamic or static context? ## 3. Types Issues: * [#560 Add Reflection Module Proposal](https://github.com/carp-lang/Carp/issues/560) Questions: * What types are available? * When is a form typechecked? * How do you refer to a specific type? Are types [first class citizens](https://en.wikipedia.org/wiki/First-class_citizen)? --- ### Embedded # Embedded Programming for embedded devices is a bit like living in the desert. Everything is scarce, you have to constantly ration, and you better stay out of the sun. This document aims to be a guide for how to ration with Carp. To do that, we first have to identify what resource it is that we’re most concerned about: is it executable size? Do we have timing-critical code? Do we want to avoid allocations? Once you have an answer to those questions, this guide can help you get there. Because Carp compiles to C, a lot of the same considerations, tricks, and reasoning apply to Carp. If you already know what flags you need to get the job done, great! Carp will probably work with them out of the box. Still, getting acquainted with the tools it provides might help you have an easier time getting productive. ## A picture is worth... Just to give you an idea of what is possible, here's a picture to whet your appetite: ## Fundamentals In order to tame the compiler to do as you tell it to, a firm grasp on the configuration options it gives you is in order. This section aims to help you get an overview of what you can do to make your project compile. ### Compiler There are a few dynamic functions for you to peruse to instruct the compiler. Here is a list of them: ```clojure ; tells Carp what C compiler executable to use (Project.config "compiler" "mycompiler") ; tells Carp to add this flag to the compiler invocation (add-cflag "-myflag") ; tells Carp to add this library flag to the compiler invocation (add-lib "-mylibflag") ; tells Carp to run pkg-config for the libs and cflags of a library (add-pkg "mypkg") ``` ### Cross-compiling On embedded systems it's quite usual to use cross-compilers. See the cross-compiling section of the Manual for details on how to use a cross-compiler. ### Compile-time conditional code There are some macros to help you find out stuff about the host system you are compiling on. Here are a few helpful functions to get you started: ```clojure ; will return the host OS (host-os) ; will return the host architecture bit width (e.g. 32 or 64 bit) (host-bit-width) ``` Most of the time you'll be interested in the target platform details instead. ```clojure ; will return the target architecture (target-arch) ; will return the target OS (target-os) ; will return the target ABI (target-abi) ``` There're some macros for conditional code in `Macros.carp`. If your target doesn't have an underlying OS you'll probably want to roll your own macros for a `freestanding` target. ### The Way Out Sometimes you have to do funky stuff like using your own linker scripts and other such tricks. If it comes to that, it’s often best to just instruct Carp to generate the C only, and deal with it yourself from there. This can be achieved by telling Carp to `--generate-only`. Sometimes you will even have to exclude some files that are usually loaded by the prelude from loading at all and instead generating your own core load file. This can be done by using `--no-core`. You can then use [the default prelude as a template for your own](https://github.com/carp-lang/Carp/blob/master/core/Core.carp). ## What to optimize for ### Binary size Binary size is something that Carp does not optimizie for by default. You can usually shave off a fairly large amount of memory by using [Link Time Optimization (LTO)](https://wiki.debian.org/LTO) and telling your compiler to optimize for size (if you are using GCC or Clang, `(add-cflag "-Os")` will do the trick). ### Speed Often, speed is not as important as other factors might be. Still, using the highest optimization setting (often `-O3`, together with the Carp flag `--optimize`) might be appropriate if you need to squeeze out those extra milliseconds. This is of course not a catch-all: speed is usually more about how your code is structured than what the compiler does. If you avoid allocations, copies, and cache misses, that will probably do more for speed than optimizers ever could. ### Allocations There are a few tricks for avoiding allocations. Literal strings are not allocated but embedded in the binary by default, and if you don’t have to touch them for a copy, this can be golden. Likewise, there are static arrays (using the literal `$[]`) which will avoid you having to allocate. Their size and structure must be known at compile-time, however. To log memory allocations during development and debugging, pass `--log-memory` to the Carp compiler and put the form `(Debug.log-memory-balance! true)` at the beginning of your program. This will log all allocations for you, helping you track down any stray allocations that might happen without your knowledge. --- ### EvaluatorVM # Dynamic Evaluator VM Carp's dynamic evaluator is VM-backed. This document is both a high-level architecture overview and a maintainer guide for future VM work. ## Scope The dynamic evaluator is the compile-time execution engine used for: 1. dynamic code (`defndynamic`, commands, primitives), 2. macro expansion and macro execution, 3. evaluator-time forms such as `let`, `if`, `while`, `set!`, and function calls. `src/Eval.hs` is the public API surface (`evalDynamic`, `evalStatic`, `eval`) and delegates execution to the VM path. ## Pipeline The evaluator pipeline is: 1. `XObj` -> `EvalIR` lowering (`lowerExpr` in `src/EvalIR.hs`). 2. `EvalIR` -> `EvalCode` bytecode compilation (`compileEvalIR` in `src/EvalVM.hs`). 3. Bytecode execution (`runEvalCode` in `src/EvalVM.hs`). Callables may be: 1. eagerly compiled (`VMPrecompiled`), 2. compile-on-first-call (`VMCompileOnCall`) with cached compiled code. ## Module map - `src/Eval.hs`: public evaluator entry points and integration with expansion. - `src/EvalIR.hs`: evaluator IR, lowering, and raising (`raiseExpr`). - `src/EvalCode.hs`: bytecode instruction and resolver-handle definitions. - `src/EvalVM.hs`: compile pipeline, lookup logic, dispatch, opcode loop, caches. - `src/EvalVMCore.hs`: low-level frame/code-store execution for registered callable code. - `src/EvalSlotLowering.hs`: function-local slot lowering for fast local variable access. - `src/EvalBound.hs`, `src/EvalBind.hs`: bound reference representation/helpers. - `src/EvalTypes.hs`: evaluator lookup and execution-mode types. ## Execution modes and lookup preference Evaluator behavior is mode-driven via `LookupPreference`: 1. `PreferDynamic` 2. `PreferGlobal` 3. `PreferLocal ... ExecFunction|ExecDynamic|ExecMacro` Mode controls lookup and callable compilation policy: 1. Function mode expects local slots to exist and fails fast when missing. 2. Dynamic and macro modes keep dynamic-friendly lookup behavior. ## Bytecode model `EvalCode` is a list plus array form of instructions. Important instruction classes: 1. stack/value ops: `IPushConst`, `IMakeArray`, `IMakeStaticArray`, `IDrop`, 2. control flow: `IJumpIfFalseRel`, `IJumpRel`, `IHalt`, `ITrap`, 3. symbol/call dispatch: `IResolveSymbol`, `IExecCallSymbol`, `IExecCall`, 4. special-form execution ops: `IExecLet`, `IExecFn`, `IExecWhile`, `IExecWith`, `IExecSet`. `IExecCallSymbol` and `IExecCall` carry both raw argument IR and precompiled argument code, so non-macro argument evaluation avoids recursive IR re-entry in hot paths. ## Callable representation and transparency The VM introduces `VMClosure` for executable callable payloads, but language-level semantics should remain transparent. Current contract: 1. dynamic/macro definitions keep legacy outer shape `(dynamic|macro name params body)`, 2. executable body may be a VM-backed closure internally, 3. user-visible macro and dynamic behavior should match pre-VM semantics unless explicitly changed. ## Caching There are three relevant caches: 1. IR-to-bytecode cache keyed by positive `Info.infoIdentifier` (`evalIRCacheKey`), 2. symbol resolution cache in opcode loop keyed by `(contextBindingEpoch, symbolId)`, 3. callable resolution cache (same keying strategy) for call dispatch. `contextBindingEpoch` is used to invalidate cached bindings when environment state changes. ## Symbol resolution model Compilation assigns each symbol a `ResolverHandle`: 1. `RHLocalSlot` 2. `RHGlobal` 3. `RHDynamic` 4. `RHQualified` 5. `RHUnqualified` The opcode loop resolves by handle shape first and only falls back to broader lookup where required by semantics. ## Slot lowering invariants Function mode relies on slot lowering: 1. function parameters and local references are lowered to slot refs, 2. unresolved local refs after slot lowering are treated as an error, 3. `set!` updates sync back into local slot state to keep reads coherent after mutation. If you change binding/lowering behavior, keep these invariants intact or update tests and docs together. ## How to make VM changes safely When changing evaluator behavior: 1. decide if this is implementation-only or intended language semantics, 2. if implementation-only, preserve outer forms and error surface, 3. update/extend evaluator tests (`test/TestEvalIR.hs`, `test/TestEvalSlotLowering.hs`, `test/TestEvalVM.hs`, `test/TestEvalVMCore.hs`), 4. run macro-heavy and dynamic-closure tests (`test/macros.carp`, `test/dynamic-closures.carp`), 5. benchmark (`./bench/run-evaluator-bench.sh`) and compare medians, not single runs. ## Performance workflow Primary benchmark script: 1. `./bench/run-evaluator-bench.sh` Use medians from repeated runs and compare at least: 1. baseline startup, 2. evaluator benchmark (`bench/evaluator.carp`), 3. real-world macro workload (`test/macros.carp`). ## Current non-goal The evaluator VM is internal compiler infrastructure. It is not a user runtime VM and does not change Carp's compiled-code execution model. --- ### Format Strings # Format Strings {% raw %} Carp as to ways to format strings, `fmt` and `fstr`. In this document, we explore both functions in detail. ## `fmt` `fmt` allows for more control than `fstr`, but also requires more knowledge about the data. ```clojure (fmt "this is an integer %d and this is a string %s." 1 "hi") ``` It’s works similarly to [`printf`](https://en.wikipedia.org/wiki/Printf_format_string) in C. `fmt` will check that the amount of arguments and format specifiers in the format string match. All arguments to `fmt` must implement the `format` interface, which is defined as: ```clojure (definterface format (Fn [String a] String) ``` The types are expected to take a format specifier and format according to it. As such, which format specifiers are supported is dependent on the implementation of `format` on that type. Standard library types expose regular format specifiers as in C. Please note that, because `format` is often implemented on top of `snprintf` and similar functions, using faulty format specifiers might lead to problems. Also, all `fmt` format strings must be literals. ## `fstr` Similarly to `fmt`, `fstr` takes a literal string. It uses a simpler interface than `fmt`, however, in which the expressions are embedded directly into the string and formatted using `str`. As such, the return types of all expressions in a `fstr` must implement the `str` interface. ```clojure (def x 1) (def y "hi") (fstr "this is an integer {x} and this is the first character of a string {(head x)}") ``` Any parseable expression may be embedded in a `fstr`. Expressions are delimited using `{}`. Any lone `}` will be interpreted as a literal, whereas literal `{` need to be escaped as `{{`. ```clojure (fstr "{{}") ; => {} ``` While possible, it is discouraged to use complicated or even multiline expressions inside `fstr`. {% endraw %} --- ### HowToRunCode # How to run code This document is aimed at people just starting out with Carp, in particular if you want to try out the [examples](../examples). ## Prerequisites Make sure that you have [installed the Carp compiler and its dependencies](Install.md) and that you can start it without any error messages. Here's how it should look: ```text $ carp Welcome to Carp X.Y.Z This is free software with ABSOLUTELY NO WARRANTY. Evaluate (help) for more information. 鲤 ``` The `鲤` character on the last line is the [REPL](https://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop) prompt, it means that Carp is waiting for you to enter a command. ## Running code from the REPL You can load some code with: ```bash 鲤 (load "some_file.carp") ``` The path to the file should be relative to where you started `carp` (or the file has to be in your [search-path](Libraries.md) path). It is also possible to paste a block of code (even multiple top-level expressions) into the REPL. To build and run, first do: ```bash 鲤 (build) ``` And then: ``` 鲤 (run) ``` ## Running code from the terminal If you don't want to work in the REPL and use a more classic "compile & run" setup, do this: ```bash $ carp some_file.carp -x ``` Any files you list as arguments to `carp` will be loaded (this works when starting the REPL too). The `-x` flag means that you want to compile and run the code immedately, exiting afterwards. If you just want to build the executable, use `-b` instead: ```bash $ carp some_file.carp -b ``` --- ### Install # Installation ## Latest release See [https://github.com/carp-lang/Carp/releases](https://github.com/carp-lang/Carp/releases). ## Building the Carp executable from source 1. Make sure you have a recent version of [Stack](https://docs.haskellstack.org/en/stable/README/) installed. 2. Clone this repo to your machine. 3. Run ```stack build``` in the root of the project directory. 4. ```stack install``` will install the Carp command line tool for easy access on your system. 5. Make sure that the directory where stack installs executables is on your PATH, i.e: ```export PATH=~/.local/bin:$PATH```. ## Setting the CARP_DIR To be able to run `carp` from anywhere on you system, the executable must know where to find its core libraries and other files. Set the environment variable CARP_DIR so that it points to the root of the Carp repo. For example, add this to your `.bashrc` or similar: ```bash export CARP_DIR=~/Carp/ ``` You should now be able to start Carp from anywhere: ```bash $ carp ``` ## Ensuring an UTF-8 aware LC_CTYPE locale in POSIX environments To be able to handle UTF-8 correctly when using `carp`'s interactive repl (binaries from `carp` always handle UTF-8 correctly), all POSIX aware environments (Linux, MacOs or even Emacs's eshell inside a Windows 10) need to have an `LC_CTYPE` environment variable set and exported to an UTF-8 aware value. For example, add this to your `.bashrc` or similar: ```bash export LC_CTYPE=C.UTF-8 ``` Take into account that the the environment variable `LC_ALL`, when set, overrides the value of `LC_CTYPE`. So you may want to `unset` `LC_ALL` or to set and export it to an UTF-8 aware value. You can see the values of `LC_ALL` and `LC_CTYPE` with the command `locale`. ## C compiler The `carp` executable will emit a single file with C code, `main.c` and try to compile it using an external C compiler. On macOS and Linux it defaults to `clang`, so make sure you have that installed (On macOS this is preferably done by installing XCode, including its developer tools). On Windows the default C compiler used by Carp is `clang-cl.exe` which compiles the code using Clang but links it with the Visual Studio linker. Tip: use the package manager [Scoop](https://scoop.sh/) to install LLVM for an easy way to set this up on Windows. Also make sure you have Visual Studio with the C/C++ addon installed. Please note that you *don't* need WSL (Windows Subsystem for Linux) to use Carp. If you want to use another compiler, you can configure the exact build command like so: ```clojure (Project.config "compiler" "gcc --important-flag") ``` ## SDL, GLFW, etc The examples involving graphics/sound/interaction will require the following libraries installed on your system: * [SDL 2](https://www.libsdl.org/download-2.0.php) (cross platform game/interactivity library) * [SDL_image 2](https://www.libsdl.org/projects/SDL_image/) (image helpers) * [SDL_ttf 2](https://www.libsdl.org/projects/SDL_ttf/) (font rendering) * [SDL_mixer 2](https://www.libsdl.org/projects/SDL_mixer/) (audio playback) * [glfw](http://www.glfw.org) (Create a rendering context for OpenGL or Vulcan) On macOS and Linux we use [pkg-config](https://www.freedesktop.org/wiki/Software/pkg-config/) to handle include paths and linking flags, so make sure you have that properly installed and configured to find the external libraries. Please let us know if you have trouble getting these bindings to work! We have tried making everything as reliable as possible but there are often corner cases when it comes to dependency management. And remember that you're always welcome to start an issue or ask questions in [the gitter channel](https://gitter.im/carp-lang/Carp). ## Footnote for Windows You can install clang with mingw64 but you'll also want to run `vcvarsall.bat amd64` or `vcvarsall.bat x86` each time you start your shell to help clang find the right headers. See https://github.com/carp-lang/Carp/issues/700 or https://github.com/carp-lang/Carp/issues/1323 for more information. Also when compiling files with `carp` from Windows you must ensure that : * the file is encoded either as ANSI or UTF-8. (Using another encoding like UTF-8-BOM doesn't work.) * using either Unix (LF) or Windows (CR LF) as linefeed/newline. (Using Macintosh (CR) as newline doesn't work.) --- ### LanguageGuide ## The Language ### Introduction Carp borrows its looks from Clojure but the runtime semantics are much closer to those of ML or Rust. Types are inferred but can be annotated for readability using the `the` keyword (see below). Memory management is handled by static analysis, a value is owned by the function where it was created. When a value is returned or passed to another function the initial function will give up ownership of it and any subsequent use will lead to a compiler error. To temporarily lend a value to another function (for example to print it) a reference must be created, using the `ref` special form (or the `&` reader macro). To learn more about the details of memory management, check out [Memory.md](Memory.md) ### Comments ```clojure ;; Comments begin with a semicolon and continue until the end of the line. ``` ### Data Literals ```clojure 100 ;; Int 1500l ;; Long 3.14f ;; Float 10.0 ;; Double 1b ;; Byte true ;; Bool "hello" ;; &String #"hello" ;; &Pattern \e ;; Char [1 2 3] ;; (Array Int) {1 1.0 2 2.0} ;; (Map Int Double) ``` ### Type Literals ```clojure t ;; Type variables begin with a lowercase letter (f t) ;; Type constructor variables; matches `(Maybe Int)` but not `Int` Int Long Float Double Byte Bool String Pattern Char (Array t) (Map ) (Fn [ ...] ) ;; Function type ``` ### Dynamic-only Data Literals Right now the following data types are only available for manipulation in non-compiled code. ```clojure (1 2 3) ; list foo ; symbol ``` ### Defining things ```clojure (defn function-name [ ...] ) ;; Define a function (will be compiled, can't be called at the REPL) (definterface interface-name (Fn [ ] )) ;; Define a generic function that can have multiple implementations (def variable-name value) ;; Define a global variable (only handles primitive constants for the moment) (defmacro [ ...] ) ;; Define a macro, its argument will not be evaluated when called (defdynamic ) ;; A variable that can only be used at the REPL or during compilation (defndynamic [ ...] ) ;; A function that can only be used at the REPL or during compilation (defmodule ...) ;; The main way to organize your program into smaller parts ``` Top-level `defn` and `def` forms can reference each other regardless of definition order within a file. This means you can call a function before it is defined, and mutually recursive functions work without any special declaration: ```clojure (defn main [] (IO.println &(Int.str (add-one 41)))) (defn add-one [x] (+ x 1)) ;; Mutual recursion (defn is-even [n] (if (= n 0) true (is-odd (- n 1)))) (defn is-odd [n] (if (= n 0) false (is-even (- n 1)))) ``` Note that order independence only applies to `defn` and `def` forms within a single file. Other forms like `defmodule`, `use`, `sig`, and macros are still processed in source order. Files loaded via `(load ...)` are also processed in the order they are loaded. Self-recursive functions in tail position are automatically optimized into loops, avoiding stack overflow on deep recursion. This works even when managed types (like `String`) are in scope: ```clojure (defn sum-to [n acc] (if (= n 0) acc (sum-to (- n 1) (+ acc n)))) (defn repeat-str [n acc] (if (= n 0) acc (let [piece @"x"] (repeat-str (- n 1) (StringCopy.append &acc &piece))))) ``` Tail position is recognized through `if`, `do`, `let`, and `the` forms. The optimization is not applied when any parameter has a reference type. Groups of mutually recursive functions are also optimized when they share the same parameter types, parameter names, and return type: ```clojure (defn is-even [n] (if (= n 0) true (is-odd (- n 1)))) (defn is-odd [n] (if (= n 0) false (is-even (- n 1)))) ``` ### Conditional statements with `cond` The `cond` statement executes a block of code if a specified condition is true. If the condition is false, another block of code can be executed. ```clojure (doc cond "this is the documentation for cond") ``` Usage: ```clojure (cond () () ;; code_1 gets executed if condition_1 is true () () ;; code_2 gets executed if condition_2 is true () ;; code_3 gets executed if condition_1 and condition_2 are false ``` Here's an example about printing a statement depending on whether it is < or > 10: ```clojure (cond (< 10 1) (println "Don't print!") (> 10 1) (println msg) (println "Don't print!")) ``` ### Special Forms The following forms can be used in Carp source code and will be compiled to C after type checking and other static analysis. The first three of them are also available in dynamic functions. ```clojure (fn [ ...] ) ;; Create a lambda function (a.k.a. closure) (let [ ...] ) ;; Create local bindings (do ... ) ;; Perform side-effecting functions, then return a value (if ) ;; Branching (while ) ;; Loop until expression is false (use ) ;; Brings all symbols inside into the scope (with ...) ;; Locally scoped `use` statement where all expressions after it will look up symbols in the (match ...) ;; Pattern matches an against a set of sumtype constructors (match-ref ...) ;; Pattern matches an of reference type, not taking ownership of its members (ref ) ;; Borrow an owned value (set! ) ;; Mutate a variable (the ) ;; Explicitly declare the type of an expression ``` Here's an example of how to use the `the` form to make an identity function that only accepts Integers: ```clojure (defn f [x] (the Int x)) ``` ### Reader Macros ```clojure &x ;; same as (ref x) @x ;; same as (copy x) ``` ### Named Holes When using a statically typed language like Carp it can sometimes be hard to know what value should be used at a specific point in your program. In such cases the concept of 'holes' can be useful. Just add a hole in your source code and reload (":r") to let the Carp compiler figure out what type goes there. ```clojure (String.append ?w00t "!") ;; Will generate a type error telling you that the type of '?w00t' is &String ``` ### Special forms during evaluation of dynamic code ```clojure (quote ) ;; Avoid further evaluation of the expression (and) (or) (not) ;; Logical operators ``` ### Dynamic functions These can only be used at the REPL and during macro evaluation. Here's a subset with some of the most commonly used ones: ```clojure (car ) ;; Return the first element of a list or array (cdr ) ;; Return all but the first element of a list or array (cons ) ;; Add the value of as the first element the (cons-last ) ;; Add the value of as the last element the (list ...) ;; Create a list from a series of evaluated expressions (array ...) ;; Create an array from a series of evaluated expressions ``` To see all functions available in the `Dynamic` module, enter `(info Dynamic)` at the REPL. ### Structs Any structure type defined in Carp has an init method that can be used to create a new instance. It must be called with all the arguments in the order they are defined. ```clojure (deftype Vector2 [x Int, y Int]) (let [my-pos (Vector2.init 10 20)] ...) ;; Additionally, a 'lens' is automatically generated for each member; signatures for reference: ;; Vector2.x (Fn [(Ref Vector2)] (Ref Int)) (Vector2.x &my-pos) ;; => 10 ;; Vector2.set-x (Fn [Vector2 Int] Vector2) (Vector2.set-x my-pos 30) ;; => (Vector2 30 20) ;; Vector2.set-x! (Fn [(Ref Vector2), Int] ()) (Vector2.set-x! &my-pos 30) ;; => Will update the vector my-pos in place and return () ;; Note the inner reference to a function ;; Vector2.update-x (Fn [Vector2, (Ref (Fn [Int] Int))] Vector2) (Vector2.update-x my-pos inc) ;; => (Vector2 11 20) ;; This can also be a lambda (Vector2.update-x my-pos &(fn [n] (* n 3))) ;; => (Vector2 30 20) ``` ### Sumtypes There are two ways to define `sumtypes`: **Enumeration:** ```clojure (deftype MyEnum Kind1 Kind2 Kind3) ``` **Data:** ```clojure (deftype (Either a b) (Left [a]) (Right [b])) ``` A Variant can be created with the same syntax as call expression: ```clojure (MyEnum.Kind1) (Either.Left 10) (Either.Right 11) ;; Or use `use` statement (use Either) (Left 10) (Right 11) (use MyEnum) (Kind1) (Kind2) (Kind3) ``` You can use pattern matching to extract values in a safe way: ```clojure (defn get [either] (match either (Either.Left a) a (Either.Right b) b)) (with MyEnum ;; You can give a generic "otherwise" statement as well (match myenum (Kind1) (logic1) _ (logic-other))) ``` Note that match works with *values* (not references) takes ownership over the value being matched on. If you instead want to match on a reference, you can use `match-ref`: ```clojure (match-ref &might-be-a-string (Just s) (IO.println s) Nothing (IO.println "Got nothing")) ``` Note that this code would not take ownership over `might-be-a-string`. Also, the `s` in the first case is a reference, since it wouldn't be safe to destructure the `Maybe` into values in this situation. **Note:** A sumtype cannot have more than 128 inhabitants, also known as constructors. If that reads to you like a byte limitation, you’re on the right track. While this is a limitation, it has not proved to be a problem as of yet. ### Recursive Types Carp supports recursive types when the recursion goes through indirection, i.e. `Box` or `Ptr`. Direct recursion is rejected because the compiler must be able to compute a concrete, finite size for each type. Examples (allowed): ```clojure ;; A linked list using a sumtype (deftype (List a) (Nil) (Cons [a (Box (List a))])) ;; A recursive struct (deftype Node [value Int next (Box Node)]) ``` Direct recursion (not allowed): ```clojure (deftype Bad [self Bad]) ``` `Box` is a managed, linear pointer type, so ownership rules apply. `Ptr` is unmanaged and is for advanced use cases where you handle lifetime and deallocation yourself. ### Modules and Name Lookup Functions and variables can be stored in modules which are named and can be nested. To use a symbol inside a module you need to qualify it with the module name, like this: `Float.cos`. *Using* a module makes it possible to access its members without qualifying them: ```clojure (use Float) (defn f [] (cos 3.2f)) ``` If there are several used modules that contain symbols with the same name, the type inferer will try to figure out which one of the symbols you really mean (based on the types in your code). If it can't, it will display an error. For example, both the module `String` and `Array` contain a function named 'length'. In the following code it's possible to see that it's the array version that is needed, and that one will be called: ```clojure (use String) (use Array) (defn f [] (length [1 2 3 4 5])) ``` In the following example it's not possible to figure out which type is intended: ```clojure (use String) (use Array) (defn f [x] (length x)) ``` Specifying the type solves this error: ```clojure (use String) (use Array) (defn f [x] (String.length x)) ``` When you `use` a module, its declarations are brought into the current scope. If you `use` a module in the global scope, all of its declarations are brought into global scope after the call to `use`. Similarly, if you `use` a module in another module's scope, its declarations can be referred to without qualifiers within the scope of the module: ```clojure (use String) ;; Only the `String` module is used in the global scope, ;; so we can refer to `length` without a module qualifier. (defn f [x] (length x)) (defmodule Foo (use Array) ;; Since the the `String` module is used in the global scope, ;; and the Foo module `use`s `Array`, we again need to qualify calls to `length` ;; to disambiguate which declaration we're referring to. (defn g [xs] (Array.length xs))) ``` Sometimes, it's more convenient to bring a module's declarations into scope only for a limited number of forms. You can do this using the `with` form: ```clojure (defmodule Foo ;; we need to use a module qualifier here, ;; since there's no call to `use` in the `Foo` module scope. (defn f [x] (String.length x)) ;; Using the `with` form, we can reference the module's declarations ;; unqualified in all the forms contained in the `with`'s scope. (with String (defn g [x] (length x)))) ``` It can be useful to keep some bindings internal to a module, to achieve that one can use `private` and `hidden`: ```clojure (defmodule Say ; Makes `hell` inaccessible outside of module `Say` (private hell) ; Will prevent `hell` from being visible when listing bindings in `Say` (hidden hell) (defn hell [] @"hell") ; `private` & `hidden` work with `def` and `defn` (private o) (hidden o) (def o @"o") ; Can access `hell` and `o` inside the module (defn hello [] (String.concat &[(hell) @&o]))) ; Valid call as `hello` is not private (Say.hello) ; Will result in an compile time error as `hell` is private to the `Say` module (Say.hell) ``` `defn-` and `def-` can be used as a shorthand for defining a binding and marking it as `private` & `hidden`, the following example is equivalent to the previous one: ```clojure (defmodule Say (defn- hell [] @"hell") (def- o @"o") (defn hello [] (String.concat &[(hell) @&o]))) ``` ### Interfaces Interfaces specify a generic function signature that multiple concrete functions may implement. You can define an interface using `definterface`, passing a name and type signature of a function: ```clojure (definterface speak (Fn [a] String)) ``` You can declare a function as an implementation of an interface using `implements`. For example, the following snippet declares `Dog.bark` and `Cat.meow` as an implementation of `speak`: ```clojure (definterface speak (Fn [a] String)) (defmodule Dog (defn bark [aggressive?] (if aggressive? @"WOOF!" @"woof!")) (implements speak Dog.bark)) (defmodule Cat (defn meow [times] (String.repeat times "meow!")) (implements speak Cat.meow)) ``` Only functions that satisfy an interface's signature can implement it. For exmaple, the following function isn't a valid implementation of `speak` because it has the wrong number of arguments and its return type does not match the return type of `speak`: ```clojure (defmodule Number ;; who knew numbers could talk? (defn holler [] "WOO!") (implements speak Number.holler)) => [INTERFACE ERROR] Number.holler : (Fn [] (Ref String a)) doesn't match the interface signature (Fn [a] String) ``` When you call an interface by name, Carp uses the current context and the type signature of each implementation to call an implementation that type checks: ```clojure (speak 2) ;; Int -> String, Cat.meow => "meow!meow!" (speak false) ;; Bool -> String, Dog.bark => "woof!" ``` If more than one interface implementation satisfies Carp's type checker in a given context, Carp will complain about the ambiguity: ```clojure (defmodule Pikachu (defn pika [times] (String.repeat times "pika!")) (implements speak Pikachu.pika)) (speak 2) ;; Int -> String, Cat.meow OR Pikachu.pika => There are several exact matches for the interface `speak` of type `(Fn [Int] String)` at line 1, column 2 in 'REPL' Possibilities: Cat.meow : (Fn [Int] String) Pikachu.pika : (Fn [Int] String) at REPL:1:1. ``` In such cases, you'll have to help the Carp compiler disambiguate the call by calling the implementing function you need directly. It usually isn't useful to provide multiple implementations that have the same function signature. ### C Interop ```clojure (system-include "math.h") ;; compiles to #include (relative-include "math.h") ;; compiles to #include "$carp_file_dir/math.h" where carp_file_dir is the absolute path to the folder containing the invoking .carp file (register blah (Fn [Int Int] String)) ;; Will register the function 'blah' that takes two Int:s and returns a String (register pi Double) ;; Will register the global variable 'pi' of type Double (register blah (Fn [Int Int] String) "exit") ;; Will register the function 'blah' but use the name 'exit' in the emitted C code. (register-type Apple) ;; Register an opaque C type (register-type Banana [price Double, size Int]) ;; Register an external C-struct, this will generate getters, setters and updaters. ``` Often type names in C are lowercase (e.g. `size_t`) and just registering them will be problematic since Carp thinks that such variables are generic types. To be able to interop wich such types, `register-type` takes an optional string after the type name, like this: ```clojure (register-type SizeT "size_t") ``` This will make the name of the type in Carp code be `SizeT`, while the emitted C code will use `size_t` instead. [More information on C interop...](./CInterop.md) ### Patterns Patterns are similar to, but not the same as, Regular Expressions. They were derived from [Lua](http://lua-users.org/wiki/PatternsTutorial), and are useful whenever you want to find something within or extract something from strings. They are simpler than Regular Expressions, as they do not provide alternation. Nonetheless, they are often very useful and, because they are simpler, also faster and more predictable. Here is a little overview of the API: ```clojure ; you can initialize a pattern with a literal or create one from a string #"[a-z]" (Pattern.init "[a-z]") ; you can also get a string back from it (str #"[a-z]") (prn #"[a-z]") ; you can find things in strings by index (Pattern.find #"[a-z]" "1234a") ; => 4 (Pattern.find #"[a-z]" "1234") ; => -1 ; also multiple things at once! (Pattern.find-all #"[a-z]" "1234a b") ; => [4 6] ; matches? checks whether a string matches a pattern (Pattern.matches? #"(\d+) (\d+)" " 12 13") ; => true ; match-groups returns all match groups of the first match (Pattern.match-groups #"(\d+) (\d+)" " 12 13") ; => ["12" "13"] ; match-str returns the whole string of the first match (Pattern.match-str #"(\d+) (\d+)" " 12 13") ; => "12 13" ; global-match gets all match groups of all matches (Pattern.global-match #"(\d+) (\d+)" " 12 13 14 15") ; => [["12" "13"] ["14" "15"]] ; substitute helps you replace patterns in a string n times (Pattern.substitute #"sub-me" "sub-me sub-me sub-me" "replaced" 1) ; => "replaced sub-me sub-me" ; if you want to replace every occurrence, use -1 (Pattern.substitute #"sub-me" "sub-me sub-me sub-me" "replaced" -1) ; => "replaced replaced replaced" ``` #### Limitations of Patterns As mentioned above, patterns are not as expressive as regular expressions. The fundamental difference is that patterns do not backtrack. This means that they cannot express alternation (because we can’t go back to where we branched) and we cannot reduce non-greedy matches on the left. The latter point might not be obvious, so let us look at an example: ``` (Pattern.match-all-groups #"1.-2" "1 1 2") ; => [[@"1 1 2"]] ``` A valid, less greedy match would have been `"1 2"`, but since it would have required us to go back to the left after we had started matching to reduce the match size, this is not done. As such, while `-` is similar to `*?` in regular expressions, it is not the same. Often, a more explicit variant of the pattern can be found that is able to resolve the issues (in the case above, `#"1\s-2"` might have been desirable, for instance). --- ### Libraries ## Working with libraries and modules Carp comes with a standard library called Core, sources are [here](../core/). It consists of a number of modules. Documentation is available [online](http://carp-lang.github.io/carp-docs/core/core_index.html) as well as [locally](./core/core_index.html) for most of them. The majority of modules are loaded by default, see [Core.carp](../core/Core.carp) for details. If your `CARP_DIR` environment variable is set up [properly](Install.md#setting-the-carp_dir), then the remaining libraries can easily be imported using the `load` command. For example, to get access to the Bench module, do the following: ```clojure (load "Bench.carp") ``` Using the functions in the Bench module still requires pre-pending them with the module name, i.e. `(Bench.bench fib)`. To avoid that, also do `(use Bench)`. To see what functions a certain module contains, use the `info` command: ```clojure (info Bench) ``` External librares can be loaded by using their relative or absolute location in your file system as the path. To make a library publically available in a more general way you can add it to your Carp project's search path:s (found by running `:p` in the repl). For instance, here's how you would add the NCurses library so that it can be loaded with just `(load "NCurses.carp")`. ```clojure (Project.config "search-path" "~/Projects/carp-ncurses") ``` This line of configuration can be put into [profile.carp](Manual.md#Profile-settings) to make it apply in all your projects. ## Loading via git You can also load libraries via Git like that: ```clojure (load "git@github.com:hellerve/anima.carp@master") ``` This will download the [Anima](https://github.com/hellerve/anima) library to `~/.carp/libs//` and load the file `anima.carp` in it. To get a stable version of the library you should specify a git tag rather than `@master`. If you want to make a library ready for loading, either prepare a file that has the same name as the library—in the case above, `anima.carp`—or a file called `main.carp` as an entrypoint. Please note that for private repos only loading through SSH is supported. For public repos you can use HTTPS: ```clojure (load "https://github.com/hellerve/anima@master") ``` ## Documentation You can generate HTML documentation for a set of modules by running `save-docs` in the REPL: ```clojure > (save-docs Int Float String) ``` See the [ReadMe](./core/README.md) for updating the entire standard library documentation or the [program](./core/generate_core_docs.carp) for examples of how to configure the documentation generator. ## Auto generated API documentation * [online docu for Carp standard library](http://carp-lang.github.io/carp-docs/core/core_index.html) * [local docu for Carp standard library](./core/core_index.html) * [SDL](http://carp-lang.github.io/carp-docs/sdl/SDL_index.html) ## Some External Libraries * [Anima](https://github.com/hellerve/anima) (A simple drawing and animation framework) * [Stdint](https://github.com/hellerve/stdint) (A wrapper around the types defined in stdint.h) * [Socket](https://github.com/hellerve/socket) (A wrapper around C sockets) * [Physics](https://github.com/hellerve/physics) (A port of phys.js) * [NCurses](https://github.com/eriksvedang/carp-ncurses) ([https://www.gnu.org/software/ncurses/](https://www.gnu.org/software/ncurses/)) * [Curl](https://github.com/eriksvedang/carp-curl) (Simple bindings to the Curl library) For a growing list of Carp packages, see [Carpentry](https://github.com/carpentry-org). Do you have a library that you want to plug here? Pleas make a PR! --- ### Macros # Macros Macros are among the most divisive features about any Lisp. There are many different design decisions to be made, and all of them have proponents and detractors. This document aims to give a comprehensive overview of the macro system and how to use it. If you’re in a hurry or want to see whether Carp implements your favorite macro feature, you probably want to read the section [“In a Nutshell”](#in-a-nutshell). If you want to spend some quality time understanding how to work on or with the macro systems, the sections [“Working with Macros”](#working-with-macros) and [“Inner Workings”](#inner-workings) will probably be more useful to you. ## In a Nutshell The macro system we’ve settled on for Carp is fairly simple. It is: - not hygienic, but provides `gensym` capabilities, - does not currently provide quasiquoting (this is not a requirement, it is currently just not implemented); thus the bread and butter in your macro toolbox will be `car`, `cdr`, `cons`, and `list`, - defines macros with a fairly simple `defmacro`-based syntax, and has support for compile-time or dynamic functions (for more information on this aspect, please read [“Working with Macros”](#working-with-macros) below), and - it sees the dynamic environment not just as an environment in which to generate code through expanding macros, but also as a place for telling the compiler more about the source. As an example, consider the dynamic function `Project.config`, which allows you to set such things as the C compiler to use, the name of the compiled project, or the output directory. To see this in action, consider [this Carp snippet](https://github.com/carpentry-org/snippets/blob/master/build_system.carp) which implements a simple multi-compiler build system for Carp in the dynamic environment. ## Working with Macros Macros are defined using the `defmacro` primitive form, like this: ```clojure (defmacro apply [f args] (cons f args)) (apply + (1 2)) ; => (+ 1 2) (apply Array.replicate (5 "hello")) ; => (Array.replicate 5 "hello") ``` The example above defines `apply`, a macro that takes a function and a set of arguments defined as a list and rewrites it so that the function gets applied to these arguments by `cons`tructing a list with `f` as a head and `args` as tail. Because `apply` is a macro you will not need to quote the list passed to it. If that looks strange, you might want to define `apply` as a dynamic function instead. The main difference between macros and dynamic functions is that dynamic functions evaluate their arguments and macros are expanded inside their definitions. You may define a dynamic function like this: ```clojure (defndynamic apply [f args] (cons f args)) (apply '+ '(1 2)) ; => (+ 1 2) (apply 'Array.replicate '(5 "hello")) ; => (Array.replicate 5 "hello") ``` If you compare this code example to the macro example above, you’ll see that they are extremely similar, except for the invocation `defndynamic` and the quotes in their invocation. Macros also provide rest arguments; this basically means that you may define variadic macros by providing a “catch-all” argument as the last argument. ```clojure (defmacro apply-or-sym [head :rest tail] (if (= (length tail) 0) head (cons head tail))) (apply-or-sym *global*) ; => *global* (apply-or-sym + 1 2) ; => (+ 1 2) ``` The macro `apply-or-sym` is slightly ridiculous, but it should drive the point home. It takes one formal argument, `head`. You may provide any number of arguments after that—they will be bound to `tail`. Thus, tail will be a list of zero or more arguments. If we do not provide any, `apply-or-sym` will just return `head`. If we do, we treat it as a regular invocation. This kind of macro might look slightly silly, but rest assured that using rest arguments has many legitimate use cases. If you’d like to see more examples of macros big and small, you should now be equipped to understand a lot of the macros in [the standard library](/core/Macros.carp) and even [`fmt`](/core/Format.carp), a fairly complex piece of macro machinery. Some helpful functions for exploring macros in the REPL are `expand`, `eval`, and `macro-log`. `expand` will expand macros for you, while `eval` evaluates the resulting code. `macro-log` is useful for tracing your macro, a form of “printf debugging”. ## Inner Workings The Carp compiler is split in a few different stages. The diagram below illustrates the flow of the compiler. The dynamic evaluator is arguably one of the most central pieces of the Carp compiler. It orchestrates macro expansion, borrow checking, and type inference, as it encounters forms that have requirements for these services, such as function definitions, variables, or `let` bindings. Therefore, understanding the evaluator will give you a lot of insight into how Carp works generally. The practical starting points for understanding the current evaluator are: - `eval` in [`src/Eval.hs`](/src/Eval.hs) (public entry points), - lowering in [`src/EvalIR.hs`](/src/EvalIR.hs), - VM execution in [`src/EvalVM.hs`](/src/EvalVM.hs). For a compact architecture overview, see [Dynamic Evaluator VM](EvaluatorVM.md). ### Data Structures The key evaluator entry points are: ```haskell evalDynamic :: Context -> XObj -> IO (Context, Either EvalError XObj) evalStatic :: Context -> XObj -> IO (Context, Either EvalError XObj) eval :: Context -> XObj -> LookupPreference -> IO (Context, Either EvalError XObj) ``` Thus, to understand it, we’ll have to understand at least `Context`, `XObj`, and `EvalError`. The types `IO` and `Either` are part of the Haskell standard library and will not be covered extensively—please refer to your favorite tool for Haskell documentation (we recommend [Stackage](https://stackage.org)) to find out more about them. All data structures that are discussed here are defined in [`src/Obj.hs`](/src/Obj.hs). #### `XObj` `XObj` is short for “`Obj` with eXtras”. `Obj` is the type for AST nodes in Carp, and it’s used throughout the compiler. Most often, you’ll find it wrapped in an `XObj`, though, which annotates such an `Obj` with an optional source location information—in the field `info`, modelled as a `Maybe Info`—and type information—in the field `ty`, modelled as a `Maybe Ty`. While both of these fields are important, for the purposes of this document we will overlook them and treat a `XObj` as an ordinary AST node. Thus, `eval` becomes a function that takes a context and an AST node, and returns a pair consisting of a new context, and either an `EvalError` or a new AST node. #### `Context` `Context` is a data structure that holds all of the state of the Carp compiler. It is fairly extensive, holding information ranging from the type and value environments to the history of evaluation frames that were traversed for tracebacks. The entire state of the compiler should be inspectable by inspecting its context. #### `EvalError` An `EvalError` is emitted whenever the dynamic evaluator encounters an error. It consists of an error message and meta information (such as a traceback and source location information). ### Evaluation The dynamic evaluator in Carp takes care both of evaluation and meta-level information like definitions. This means that definitions are treated much like dynamic primitives to evaluate rather than special constructs. In fact, many of them are not treated as special forms, but are implemented as `Primitive`s. Because we already introduced multiple constructs by name, let us define what kinds of Carp constructs there are for the evaluator: - Special forms: these are forms that have their own representation in the abstract syntax tree and are treated directly in the evaluator loop. `fn` and `the` are examples for this category. They cannot be passed around by value, as you would do in higher order functions. - Primitives: these are regular Carp forms that do not evaluate their arguments, and they resemble builtin macros implemented in Haskell. Examples for this category include `defmacro`, `defn`, and `quote`. - Commands: these, too, are regular Carp forms. They evaluate their arguments and behave like builtin functions. Examples for this category include `Project.config`, `car`, and `cons`. Primitives are mostly defined in [`src/Primitives.hs`](/src/Primitives.hs), commands can be found in [`src/Commands.hs`](/src/Commands.hs), and special forms are handled by evaluator lowering/execution (`EvalIR` / `EvalVM`). They are wired up into the environment and given names in [`src/StartingEnv.hs`](/src/StartingEnv.hs). #### Adding your own special forms, primitives, or commands While there is a lot of machinery involved in getting your own primitives or commands into the Carp evaluator, there are a lot of simple functions around to help you get started. If the name for the primitive or command is already present as a runtime function, it should try to mimic its behavior as closely as possible. Adding special forms is a little more involved and we try to exercise caution in what to add, since every form makes `eval` harder to understand and reason about. You should probably get in touch [on the chat](https://gitter.im/carp-lang/carp) before embarking on a quest to implement a new special form to avoid frustration. #### A current list of special forms Since special forms are “magical”, they deserve an enumeration. They are recognized during evaluator lowering/execution. Currently there are: - `if` for branching, - `defn` for defining functions, - `def` for defining global variables, - `let` for defining local variables, - `the` for type annotations, - `fn` for function literals. --- ### Manual ## The Compiler Manual ### Related pages * [Installation](Install.md) - how to acquire and configure the Carp compiler * [How To Run Code](HowToRunCode.md) - compile and execute .carp files * [Tooling](Tooling.md) - supported editors * [Libraries](Libraries.md) - how to work with libraries and modules * [Multimedia](Multimedia.md) - graphics, sounds, etc * [Macros](Macros.md) - a guide to the Carp macro system * [Embedded](Embedded.md) - tips and tricks for working with Carp on embedded system * [Terminology](Terminology.md) - commonly used terms and what we mean with them To learn more about the Carp language and its syntax and semantics, check out the [Carp Language Guide](LanguageGuide.md). ### REPL Basics The Carp language is very tightly integrated with the REPL, everything you want to do to your program can be controlled from here. To load code from disk, use ```(load "filename.carp")```, this will add the source file `filename.carp` to the current 'project'. A project is a light weight concept in the repl that ties together source files and compiler settings much like in an IDE like Eclipse or Visual Studio. To build your current project, call ```(build)```. This will emit an executable or dynamic library depending on if you have defined a main-function or not. Please note that a project emitting a library will not initialize global variables automatically, the user of the library needs to call the C function `carp_init_globals` or the Carp function `System.carp-init-globals` instead. Everything emitted by the compiler will be saved in a directory named ```out``` by default. This, and other settings regarding the project can be changed by various commands. To see a list of available commands, call ```(help "project")```. There are a bunch of handy shortcuts for doing common things at the REPL: ``` :r Reload all the files of the project :b Build the project :x Run the executable (if it exists) :c Look at the emitted C code :e Display the environment with all the function bindings and their types :p Show project information and settings :h Show the help screen :q Quit the repl ``` ### Differences compared to REPL:s in other Lisp:s While powerful, the REPL in Carp currently has some big limitations compared to most other Lisp:s. If you type in an expression and press enter one of the following things will happen: 1. If you're calling a dynamic function (something defined with `defndynamic`, or a built in `command`) it will be executed right away by Carp's dynamic evaluator (implemented as an internal evaluator VM). The dynamic functions are not available in compiled code. Their main usage is in macros and to programatically control your build settings. 2. If you're calling a function defined with `defn` it's a "normal" Carp function which will be compiled (via C) to an executable binary, which is then run in a child process to the REPL. This means that the function has no chance to modify anything else in your program, like global variables and the like. 3. If the top-level form isn't a function call, the REPL might get confused. For example, entering an array of calls to a Carp function will give unexpected results (the array will be dynamic but the function calls will not). The easiest way to work around that at the moment is to wrap the expression in a `defn` and call that one instead. This will be fixed in a future version of Carp. ### Adding annotations Carp has a flexible metadata system (inspired by the one in Clojure) that lets anyone add and retrieve data on the bindings in the environment. The general way to do that is with `(meta-set! )` and `(meta )`. A couple of useful macros are implemented on top of this system: ```clojure (doc "This is a nice function.") ; Documentation (sig (Fn [Int] Bool)) ; Type annotation (private ) ; Will make the function inaccesible to other modules ``` Note that `` in all these cases are symbols, e.g. `foo` or `Game.play`. To generate html docs from the doc strings, run: ```clojure (save-docs ) ``` ### Getting types from bindings ```clojure 鲮 (type ) 鲮 :t ``` ### Listing bindings in a module ```clojure 鲮 (info ) 鲮 :i ``` ### Expanding a macro ```clojure 鲮 (expand 'yourcode) 鲮 :m yourcode ``` ### Configuring a project The current session in the repl is called a "project" and can be configured using the `(Project.config )` command. The following settings can be configured with this command: * ```"cflag"``` - Add a flag to the compiler. * ```"libflag"``` - Add a library flag to the compiler. * ```"pkgconfigflag"``` - Add a flag to pkg-config invocations. * ```"compiler"``` - Set what compiler should be run with the 'build' command. * ```"target"``` - Set the target triple (useful when cross-compiling). * ```"title"``` - Set the title of the current project, will affect the name of the binary produced. * ```"prompt"``` - Set the prompt in the repl. * ```"search-path"``` - Add a path where the Carp compiler will look for '*.carp' files. * ```"output-directory"``` - Where to put build artifacts. * ```"docs-directory"``` - Where to put generated docs. * ```"generate-only"``` - Set to true if you don't want to run the C compiler when building. * ```"echo-c"``` - When a form is defined using 'def' or 'defn' its C code will be printed. * ```"echo-compiler-cmd"``` - When building the project the command for running the C compiler will be printed. * ```"print-ast"``` - The 'info' command will print the AST for a binding. For example, to set the title of your project: ```clojure 鲮 (Project.config "title" "Fishy") ``` To use another compiler: ```clojure 鲮 (Project.config "compiler" "tcc") ``` ### Profile settings If a file called ```profile.carp``` is placed in the XDG config folder ```carp/```, that file will get loaded after the compiler has started (after loading the core libraries but before any other source files are loaded). This file is meant for user specific settings that you want in all your projects, like little helper functions and other customizations. On Windows this file is located at ```C:/Users/USERNAME/AppData/Roaming/carp/profile.carp```. ### Compiler flags When invoking the compiler from the command line you can supply the following flags to configure the behaviour: * ```-b``` Build the code, then quit the compiler. * ```-x``` Build and run the code (make sure it has a main function defined), then quit the compiler. * ```--no-core``` Run the compiler without loading any of the core libraries. * ```--log-memory``` The executable will log all calls to malloc and free. * ```--optimize``` Removes safety checks (like array bounds access, etc.) and runs the C-compiler with the `-O3` flag. * ```--check``` Run the compiler without emitting any binary, just report all errors found (in a machine readable way). * ```--generate-only``` Don't compile the C source. * ```--eval-preload``` Evaluate the provided string before loading any code (but after loading ```profile.carp```). ### Inspecting the C code generated by an expression ```clojure 鲮 (c '(+ 2 3)) ``` ### Cross-compiling Cross-compilation needs to be enabled early. You can do so in ```profile.carp``` as: ```clojure (Project.config "compiler" "zig cc --target=x86_64-windows-gnu") (Project.config "target" "x86_64-windows-gnu") ``` Or using ```--eval-preload``` as: ```sh carp --eval-preload '(Project.config "compiler" "zig cc --target=x86_64-windows-gnu") (Project.config "target" "x86_64-windows-gnu")' -b whatever.carp ``` --- ### Memory # Memory Management - a closer look Carp uses a *linear type system* to manage the memory associated with different values throughout a program. Carp's memory management system is designed and implemented with the following goals in mind: * Predictable: The memory management system's behavior should be easy to reason about. * Efficient: The memory management system should not have significant impacts on performance. * Safe: The memory management system should prevent errors related to memory management, such as "use after free" and "double free" This document introduces the basic concepts behind the kind of linear type system Carp uses. In addition, it takes a deeper look at how the system is currently implemented. ## Linear Types and Memory Management Carp's linear type system tracks the *ownership* of the memory associated with a given value as part of its type signature. A *linear type* is a traditional type with additional information called a *lifetime* that allows the type system to track a value's association with a given memory location. The memory management system *only* manages linear types; not all types are linear. Some of Carp's builtin types are linear by default: - The String type is linear and managed by the memory system. - The Pattern type is linear and managed by the memory system. - The Array type is linear and managed by the memory system. - The Box type is linear and managed by the memory system. - Function types are linear and managed by the memory system. All other builtin types are *not* linear, and thus aren't managed by the memory system. A few conditions determine whether or not a user defined type is linear: - **Implementation of the `blit` interface**: this interface explicitly marks a type as *non-linear*. Any type that implements it is ignored by the memory management system and is assumed to pose no risks in relation to memory allocation and deallocation. - **Implementation of the `delete` interface**: this interface explicitly marks a type as *linear*. Any type that implements it is managed by the memory management system. Carp will call the implementation of this interface whenever the memory management system decides it's safe to deallocate the memory associated with a value of the type that implements this interface. When you define a type directly in Carp code, using `deftype` Carp will *automatically implement the delete interface for you*. As a consequence, any type that you declare using `deftype` will be managed by the memory management system. In the most cases, this automatic management of user defined types is beneficial. You can always redefine `delete` for your type if you need to write a custom memory deallocation routine. However, if you need to define a type that requires fine-grained control over its memory deallocation, it might be better to define both the type and its deallocation routines in C, and register them in Carp. ## Recursive Types Recursive types are supported when the recursion goes through indirection (`Box` or `Ptr`). Direct recursion is rejected because the compiler must be able to determine a concrete size for every type. ```clojure (deftype (List a) (Nil) (Cons [a (Box (List a))])) ``` `Box` is linear and managed by the memory system, so ownership rules apply to recursive structures. `Ptr` is unmanaged and is intended for advanced use cases where you explicitly handle lifetime and deallocation. The same conditions hold for [registered types][3] as well. If you register an external type defined in C, Carp won't manage it unless you provide an implementation of `delete` for the corresponding Carp type. See the [C interop documentation][3] for more information. In the following sections, we'll explore a few key memory system operations. Along the way, we'll present examples using Carp's builtin linear String type to illustrate how the system manages values of linear types. ## Bindings, Ownership, and Lexical Scopes Unless your program is incredibly short, you'll likely have one or more *bindings* that associate names with values in your program. Typically, we can assign the value of one binding to another. Consider the following local variables in a let form: ```clojure (let [x 1 y x z x] x) ``` In the example above, we assign the non-linear value *1* to `x`, then assign the value of `x` to `y`, then assign the value of `x` to `z`. In Carp, linear values are treated differently. When we assign a linear value to a binding, such as a local variable name, the *memory location* associated with the value is also bound to the name. This changes the rules about how we can assign values and pass them around a program. If we try to write the same program as we did above, using a value of the linear type, `String`, we get quite a different result: ```clojure ;; Don't worry about the @ before the string literal. We'll explain it soon. (let [string @"linear types!" other-string string ;; used here! yet-another-string string] ;; and here! string) ;; and again here! ``` If you try to pass this program to the Carp compiler, you'll get an error in return: `You’re using a given-away value string`. This illustrates the 'golden rule' that the memory management system enforces: **every linear value can only be used once**. When we first assign `@"linear types!"` to the variable `string`, we've already used it once. When we attempt to assign `string` to `other-string` *and* `yet-another-string`, the memory management system will detect that we're attempting to use the single value `@"linear types!"` multiple times, which it won't allow. Note that *only* assigning the value to string, then `string` to `other-string` is OK, as long as we return `other-string`—we'll explain why in a later section. In casual terminology, this concept is called *ownership*. The binding to which the linear value is assigned *owns* its associated memory. We can call such a binding the value's *owner*. In this example, `string` is the initial owner of the memory allocated for the linear value `@"linear types!"`. Every binding in Carp has a *lexical scope* that determines where in the program the binding name is defined and can be validly referenced. The lexical scope of `string` in our example happens to be our let form. The lexical scope of a function parameter is only the body of the function. A linear value can only be used *once* in a single *lexical scope*. We "use" a linear value whenever we *pass it to a different lexical scope*. For example, we "use" `string`, if we return it: ```clojure (let [string @"linear types!"] string) ;; used here! ``` We also use it when we pass it to another function: ```clojure (let [string @"linear types!"] (do (reverse string) ;; used here! ())) ``` What do both of these cases have in common? They raise the possibility that `string`'s value (and it's assocaited memory) is passed to *another binding* (when we pass it to a function, it's rebound to the function parameter; when we return it, the caller might bind it to a new name in the lexical scope that contains our let). As we'll see later, these are two particular examples of a specific form of an operation we'll call *moving*. Binding the value of an existing linear binding, as in `(let [string @"linear types!" other-string string] ()))` is also a case of moving. ### Safe Deallocations The "use once" restriction is the mechanism that allows the memory management system to prevent classical memory errors such as "use after free" and "double free". Enforcing that a linear value is only used *once* in any lexical scope, allows the management system to determine precisely when a binding's associated memory can be freed. When the memory management system determines some linear value will no longer be used in the lexical scope of it's *owner*, it automatically calls the corresponding linear type's `delete` implementation to free the associated memory. Now that we have an initial sense about the restrictions the memory management system enforces around our use of linear values, we'll explore a few operations the system performs that allow us to have greater flexibility. ## Moving, Borrowing, and Copying At a high level, the functionality of the linear type system can be organized into three primary operations: *moving*, *borrowing*, and *copying*. These are casual, intuitive terms for what the system does with linear values as it manages them across your program. We'll explore precise technical terminology for each of these operations later on. ### Moving: Transferring Ownership The memory management system ensures that only one binding ever owns the memory associated with a given linear value. As a result, unlike non-linear values, the compiler won't let you bind the same linear value to more than one variable. Instead, when you reassign a linear value to another variable, The old binding is invalidated, as we saw earlier: ```clojure (let [string @"linear types!" other-string string yet-another-string string] ;; error here! ()) ``` In the prior example, the binding `string` is invalidated as soon as we assign it to the binding `other-string`. The memory associated with `string` is now associated with the binding `other-string`, and `other-string` is the linear string's new owner. This process is called a *transfer of ownership*, or *moving*. If we were to move our value across a number of bindings in sequence, we'd fix our problem! There's no issue with moving some linear value across different bindings in a lexical scope, there's only an issue if we attempt to move a value out of *the same binding* more than once: ```clojure (let [string @"linear types!" ;; linear string value here. other-string string ;; moved over to this binding yet-another-string other-string] ;; still ok, moved to this binding ()) ``` The important, and only rule about moving linear values is: *you can only move a linear value from an individual binding __once__* in any given lexical scope. If your code attempts to move a linear value from a binding more than once, the memory management system will chastise you! #### Moving to a New Scope Just as we transferred ownership of a linear value to another binding in the same lexical scope, we can use ownership transfers to move a linear value into a binding *beyond* its lexical scope. Consider this next example: ```clojure (let [string @"linear moves!"] string) ``` Though it's not as obvious, a move is happening here! In this case, a transfer of ownership occurs across lexical scope boundaries. The linear string associated with `string` and its corresponding memory are returned from the let form. If the result of this let form is bound to some other variable, that new binding will receive ownership of the linear string. Thus, the lifetimes of linear values are not only limited to their lexical scopes. We can move linear values in and out of other scopes, and the memory management system will determine in which part of our code the value can be safely deallocated. Again, since returning the value is a *move*, or ownership transfer, the same rules around moves apply: we can only make *one* move out of a given binding in a single lexical scope: ```clojure (let [string @"linear moves!" other-string string] ;; ok; first move out of string string) ;; error! Second move out of string ``` Passing a linear value as an argument to a function is another example of a move across lexical scopes. For instance, consider the following example: ```clojure (let [string @"linear moves!" reversed (reverse string)] ;; moved here! reversed) ``` In this example, we *move* the linear value associated with `string` into the function's lexical scope, binding it to whatever parameter name the function declaration used for its first argument. Since we only moved the value out of `string` once, the memory management system happily accepts this program. #### Beyond Moves In some cases, transferring ownership might be too limiting. Let's reconsider the earlier example, in which we tried to transfer ownership from `string` more than once: ```clojure (let [string @"linear moves!" other-string string yet-another-string string] ;; error! ()) ``` We might want to write "multi-move" code like this, but under the current rules of the linear type system, we can't. Luckily, there's a way out: references. ### Borrowing: Lending Ownership As we explored in the previous section, we can’t assign a linear value to multiple bindings without transferring ownership. If we move a value from one binding to another, we can only do so once, even if one of those moves transfers ownership beyond the current scope. At any given point in a lexical scope, only one binding can ever own the linear value. This restriction ensures the type system knows exactly when to deallocate the memory associated with a linear value, but it can be a bit limiting. For example, what if we wanted to process the value using a function, then use our original value afterwards? ```clojure (let [string @"linear borrow!" reversed (reverse string)] (concatenate string reversed)) ;; error! ``` This short let block calls some imaginary functions to first reverse our linear string, then join it with itself, returning the result. However there’s a big problem here, once we move our string to `reverse`'s parameter the memory management system won’t let us use it in `concatenate` since it violates the "one move" rule. This time, the rule has put us in quite a difficult situation. We want to write a program that uses `string` twice, but there's no way for us to use it twice directly, thanks to the linear type system rules. Just passing `string` along to other bindings won't help us here either. Luckily, there’s a mechanism that allows us to reuse `string` more than once in our let block: *references*. References are another special type that the memory management system understands how to work with. References are *not* linear types, but they give us another way of working with linear types that allows us to get around the type system’s “one owner” and "one move" restriction safely. A reference value points to some linear value, but because the reference is not linear value itself, but rather a new, non-linear value, we’re allowed to pass them around freely, just like we can with other non-linear values. Assigning a reference to a linear value to some binding is called *borrowing*. Instead of transferring ownership of a linear value to a new binding, we’re giving it a temporary way to access the value, without taking it over and moving it. Use the `&` operator, or `ref` special form, to create a reference: ```clojure (let [string @"hello, linear world!" reversed (reverse &string)] ;; reference to string (concatenate string reversed) ;; ok; first move of string ``` Using references, we can get our initial string reversal and concatenation program to work, the memory manager won’t complain. Since `string` is *borrowed* by `reverse`, using a reference, there’s no longer an issue using it directly in `concatenate` since this is now the one and only time it transfers ownership (moves). In this case, we have no idea how `reverse` actually uses the reference to produce a reversed string, but we’ve followed the memory management system’s rules correctly. In the next section, we'll explore how we can actually make use of the reference in an implementation of a function like reverse. ### Copying: Increasing Supply Now that we’ve explored references and borrowing, you might wonder what we can do with references. Again, references are not linear values themselves, but they “point” to linear values. Their behaviors and relation to the type system differ. So, what can we accomplish with references? In Carp, references, in general, (but we'll see that there are some special cases) support only a single operation, called *copying*. Copying a reference creates a new linear value that *duplicates* the linear value the reference is pointing to. This new linear value is completely distinct from the original linear value the reference points to. It has its own owner, and, just like other linear values, the memory management system will determine when to remove it. Copying allows us to work with some linear value in multiple places in a safe way. To copy the value pointed to by a reference, use the `@` operator. The following example shows how the `reverse` function might be implemented: ```clojure (defn reverse [string-ref] (reverse-internal @string-ref)) ;; reference copied here! ``` The function takes a reference to a linear string value, makes a copy of it, reverses the copy, then returns the resulting linear value to the caller. Note that we haven’t touched the original linear string pointed to by the `string-ref` reference, we only work with a copy! We can also now understand the general string literal syntax we've used throughout this text: ```clojure string @"hello, linear world!" ``` This binds a *copy* of the string literal to the variable `string`. This reveals an important aspect of Carp’s builtin string literals: they are references! We’ll explore why this makes sense a bit later. ## Rule of thumb To know whether a function takes over the responsibility of freeing some memory (through its args) or generates some new memory that the caller has to handle (through the return value), just look at the type of the function (right now the easiest way to do that is with the `(env)` command). If the value is a non-referenced struct type like String, Vector3, or similar, it means that the memory ownership gets handed over. If it's a reference signature (i.e. `(Ref String)`), the memory is just temporarily lended out and someone else will make sure it gets deleted. When interoping with existing C code it's often correct to send your data structures to C as refs or pointers (using `(Pointer.address )`), keeping the memory management inside the Carp section of the program. ## Working with arrays The most important thing in Carp is to process arrays of data. Here's an example of how that is supposed to look: ```clojure (defn weird-sum [] (let [stuff [3 5 8 9 10]] (reduce add 0 &(endo-map square (filter even? stuff))))) ``` All the array transforming functions 'endo-map' and 'filter' use C-style mutation of the array and return the same data structure back afterwards, no allocation or deallocation needed. The lifetime analyzer ("borrow checker" in [Rust][1] parlance) makes sure that the same data structure isn't used in several places. The restriction of 'endo-map' is that it must return an array of the same type as the input. If that's not possible, use 'copy-map' instead. It works like the normal 'map' found in other functional languages. The 'copy-' prefix is there to remind you of the fact that the function is allocating memory. To execute side-effects, use the `doall` macro: ``` (doall IO.println [@"Yo" @"Hola" @"Hej"]) ``` Or `foreach` (works like a foreach loop construct in a lot of other programming languages): ``` (foreach [x &[1 2 3]] (println* "x: " x)) ``` ## Under the Hood: The Implementation of Carp's Memory Management System This section explores the implementation of Carp's memory management system in greater technical detail. Most users won't need to read this, but if you'd like to have a deeper understanding of how the system works, you'll find an explanation in this section. ### AST Info, Identifiers, and Deleters Like other portions the Carp compiler, the memory management system operates on the abstract syntax tree (AST) representation of the forms in your program. When the compiler compiles your code, it assigns addition *information objects*, called `Info`, to each form in your program; these objects are particularly important to the memory management system. Among other things, these `Info` objects contain unique identifiers for each form in your program. The memory management system uses these identifiers to keep track of memory as it moves across different parts of your code. In addition to identifiers, form information objects also contain `Deleters`. These are a special data structure used to hold information about the `delete` functions needed for each linear value in your program. One of the memory management system's main responsibilities is to assign and keep track of these deleters for each form in your program that makes use of a linear value. Essentially, as the memory management system examines your code, if it finds a form that uses a linear value that should be deleted at a certain point, it adds an appropriate deleter to the info object for the form. If the linear value is *moved* to some other part of your code, the memory management system will remove the corresponding deleter, which will be added to the form it's moved into later. The key point to understand is that the memory management system primarily models the movements of linear values using the presence or absence of these deleter objects. When the compiler's code emission component encounters a form, if the form has an associated deleter, the emitter will produce a call to the deletion routine in the corresponding output C code. As we'll see in a moment, there are some further complications, but this is the basic approach taken by the memory management system. ### Lifetimes The basic operation of the memory management system entails moving deleters across different Info objects for the forms in your program. As the system performs this task, it also has to account for the way *references* are used throughout your code, and how they relate to linear values. In order to track this, the memory management system uses *lifetimes* which determine whether or not a reference is valid in a given form. The following function provides an example of this reference validity tracking in action: ```clojure (defn invalid-ref [] &[1 2 3]) ``` In the prior example, our `invalid-ref` function returns a reference to the literal linear array value `[1 2 3]`. This code is problematic because the linear array value will be deleted at the end of the function, so the returned reference will point to nothing! The memory management system catches this for us and let's us know about the problem. Contrarily, the following code is perfectly fine: ```clojure (def an-array [1 2 3]) (defn valid-ref [] &an-array) ``` The `valid-ref` function also returns a reference, but this reference is valid since it points to a linear array value (`an-array`) that won't be deleted (it will still be "alive") by the time the function returns the reference. The system will also catch cases when we attempt to reference a linear value that's already been *moved* into a different location/binding: ```clojure (defn unowned-ref [] (let [a [1 2 3] b a c &a] ())) ``` In this example, we move the linear array from `a` into `b`, but then try to set `c` to a reference to `a`, which, after the move, no longer points to anything. Internally, the memory management system uses *lifetimes* to model the relationships between references and linear values and track the validity of reference across your code. #### Lifetimes in Detail Carp's lifetimes are made up of two pieces of information. Only references have lifetimes, and every reference has *exactly one* lifetime assigned to it: - A unique type variable that identifies the lifetime. - A lifetime mode, which takes one of three forms: - `LifetimeOutsideFunction`: the reference points to a value whose scope extends beyond the current function (e.g. a function parameter or global). - `LifetimeInsideFunction`: the reference depends on one or more local variables, tracked as a set of source variable names. - `LifetimeMixed`: the lifetime has both external and internal sources. This arises when a reference creation (`&x`) shares a lifetime variable with a function parameter (typically through an explicit lifetime annotation in a `sig` form). During traversal, the external source guarantees safety. At the final return check, the internal sources are verified to ensure no dangling references escape the function. In general, a reference is valid only when *all* of the values it may point to have either an equivalent or greater lexical scope. This property is encoded in its lifetime. Let's look at some examples to help illustrate this: ```clojure (def an-array [1 2 3]) (defn valid-ref [] (let [array-ref &an-arry]) ()) ``` In this example, the anonymous reference `&an-array` has a unique lifetime that *extends beyond the lexical scope* of the reference itself. The lexical scope of the reference value `[1 2 3]` is greater than or equal to the lexical scope of the reference, which only extends across the let form, so, this reference is valid. Contrarily, the following reference is not valid: ```clojure (defn invalid-ref [] &[1 2 3]) ``` Here, the reference has a greater lexical scope than the linear value it points to. The anonymous linear value `[1 2 3]` will be deleted at the end of the function scope, but the reference will be returned from the function, so its lifetime is potentially greater than that of the value it points to. The memory management system performs two key checks around ref usage: 1. Check that a newly created reference doesn't point to a linear value binding that has already transferred away ownership. 2. Check that a reference is alive at a certain point in the program. Both of these are implemented as separate checks, but they may be viewed as specializations of a general operation that checks if every reference form in your program is "alive" at the point of use. Liveness analysis revolves around checking if *all* of the source variables a reference depends on are still alive -- that is, each source has a deleter in scope, indicating the scope properly owns the value. If any source variable's deleter is missing, the reference outlives that value and is invalid. The system collects lifetime variables exhaustively from all positions in a type: ref lifetimes, closure lifetimes, struct member lifetimes, and return type lifetimes. It does not recurse into function argument types, since those are the caller's responsibility. Two checks are performed: - **Traversal check** (`refTargetIsAlive`): runs as each form is visited. `LifetimeInsideFunction` sources must be alive. `LifetimeOutsideFunction` and `LifetimeMixed` are safe (the external source is alive in scope). - **Final check** (`returnRefTargetIsAlive`): runs after the function body has been analyzed and all local variables have been deleted. Only checks lifetime variables from the function's return type. Uses the set of function parameter deleters (recorded at function entry) as the live set, so parameters are considered alive but locals are not. Both `LifetimeInsideFunction` and `LifetimeMixed` internal sources are checked. #### Explicit Lifetime Annotations Carp supports explicit lifetime variables in type signatures: ```clojure (sig id (Fn [(Ref String a)] (Ref String a))) (defn id [x] x) ``` The lifetime variable `a` ties the return reference's lifetime to the argument's lifetime. The type checker enforces that the function body is consistent with this annotation. When a `sig` forces a local reference to share a lifetime variable with a parameter, the memory system detects the conflict. Only reference creations (`&x`) trigger a merge into the lifetime map; other forms (function call results, symbol lookups, match-ref bindings) use first-mapping-wins. This ensures that a genuinely new reference source is tracked without polluting the map with derived references that merely propagate an existing lifetime. For example, the following code is rejected: ```clojure (sig f (Fn [(Ref String a)] (Ref String a))) (defn f [x] (let [local @"hi"] &local)) ``` The parameter `x` maps lifetime `a` to `LifetimeOutsideFunction`. The reference creation `&local` merges `LifetimeInsideFunction {local}` into that mapping, producing `LifetimeMixed {local}`. At the final check, `local` is dead (its let scope has ended), so the system reports that the reference is not alive. #### Mutation and Lifetime Invalidation The `set!` special form can rebind a reference variable to point at a different value. When this happens, the lifetime mapping for the reference must be updated to reflect the new source. The memory management system handles this by *clearing* the old lifetime mapping before visiting the new value. This allows the mapping to be rebuilt from the new value's reference sources, rather than retaining stale information from the initial binding. This is important for catching use-after-free bugs involving `set!`. Consider: ```clojure (defn dangling [] (let-do [x ""] (let [a [@"hello" @"world"]] (set! x (Array.unsafe-nth &a 1))) (println* x))) ;; error! x depends on a, which is dead here ``` In this example, `x` is initially bound to a string literal reference. Inside the inner `let`, `set!` rebinds `x` to a reference that depends on the array `a`. When the inner `let` ends, `a` is deleted. At the `println*` call, `x` still refers to memory owned by `a`, which is no longer alive. The memory management system detects this and reports an error. Conversely, rebinding a reference to another value in the same or wider scope is fine: ```clojure (defn valid-set [] (let-do [a [@"hello" @"world"] x (Array.unsafe-nth &a 0)] (set! x (Array.unsafe-nth &a 1)) ;; ok: x still depends on a (println* x))) ``` Here, both the initial binding and the `set!` target depend on `a`, which outlives `x`, so the reference remains valid. ### Type Dependencies The final key piece of information the memory system manages are the *type dependencies* of the deletion functions for linear values. Since Carp supports generic programming and polymorphic functions, it's possible that some deleter is needed in a polymorphic context. In particular, generic functions that "take ownership" of generic values need to be able to find the correct deletion routines for the value. For example, in the generic function: ```clojure (sig my-generic-force-delete (Fn [a] Unit)) (defn my-generic-force-delete [a] ()) ``` This `my-generic-force-delete` function takes ownership of whatever argument it receives and does nothing. Since it takes ownership, however, the value passed to `a`, if it's linear, needs to be deleted at the end of the function scope. Since the function is generic, the memory management system can't know for certain what value is being passed. In some cases it might be a linear value, in some cases it might not be. Sometimes it might be a `String`, sometimes an `Int`, or sometimes an `Array`. Each of these types has a different `delete` implementation. Rather than having the memory management system figure out what function to use, the system instead just keeps track of the types of all the values for the forms it analyzes. Later, the component already dedicated to resolving generic functions handles finding the right deletion routine for the values passed to the generic function. In order to accomplish this, it uses the type information captured by the memory system as it analyzes each form. ### Memory State As we've explored, the memory management system needs to keep track of three key pieces of information as it analyzes the forms in your program: 1. The deleters assigned to each AST node to track ownership of linear values and delete them at the right time. 2. The Lifetimes assigned to each reference to check reference validity. 3. The types of each form it analyzes to resolve generic deletion functions. Each of these units of information is bundled into a single data structure, called the *memory state* or `MemState` of your program. As the memory management system analyzes each of the AST nodes in your program source, it updates the memory state accordingly. Deleters are added and removed from the state at different points as ownership transfers of linear values occur. When the system finishes analyzing a node, it update's the node's `Info` object, attaching the deleters associated with the current memory state. At any point, if the memory management system encounters a problem with the way memory is being transferred across your program's AST nodes, it reports an error. A simple piece of code: ```clojure (use Int) (use String) (use IO) (defn say-hi [text] (while true (if (< (length &text) 10) (println "Too short!") (println &text)))) ``` This compiles to the following C program: ```C void say_MINUS_hi(string text) { bool _5 = true; while (_5) { string* _14 = &text; // ref int _12 = String_length(_14); bool _10 = Int__LT_(_12, 10); if (_10) { string _19 = "Too short!"; string *_19_ref = &_19; IO_println(_19_ref); } else { string* _22 = &text; // ref IO_println(_22); } _5 = true; } String_delete(text); } ``` If-statements are kind of tricky in regards to memory management: ```clojure (defn say-what [text] (let [manage (copy &text)] (if (< (length &text) 10) (copy "Too short") manage))) ``` The 'manage' variable is the return value in the second branch, but should get freed if "Too short" is returned. The output is a somewhat noisy C program: ```C string say_MINUS_what(string text) { string _5; /* let */ { string* _11 = &text; // ref string _9 = String_copy(_11); string manage = _9; string _13; string* _19 = &text; // ref int _17 = String_length(_19); bool _15 = Int__LT_(_17, 10); if (_15) { string _24 = "Too short"; string *_24_ref = &_24; string _22 = String_copy(_24_ref); String_delete(manage); _13 = _22; } else { _13 = manage; } _5 = _13; } String_delete(text); return _5; } ``` ## Custom deletion functions The Carp compiler will auto-generate a deletion function for types created on the Carp side. The `delete` function is responsible for cleaning up any memory associated with its associated value when it goes out of scope. Type that are defined in C do not have a `delete` function generated for them automatically, you can write your own deletion function, declare it to be implementing `delete` and the Carp compiler will call it automatically for you. You can check if a type has `delete` implemented by using `Dynamic.managed?`. As the `delete` interface is responsible for freeing memory, it is **unsafe** to override it, if you are looking for how to release other type of resources (sockets, file handle, etc...) when a value goes out of scope use the [`drop` interface](./Drop.md) instead. Let’s look at an example program of how to add a deletion function to a type defined in C: ```clojure (register-type Foo) (register-type Bar) (defmodule Foo (register init (Fn [] Foo)) (register delete (Fn [Foo] ())) (implements delete Foo.delete)) (defmodule Bar (register init (Fn [] Bar))) (defn f [] (let [a (Foo.init) b (Bar.init)] ())) ``` The code for `f` will look like this: ```c void f() { /* let */ { Foo _6 = Foo_init(); Foo a = _6; Bar _9 = Bar_init(); Bar b = _9; /* () */ Foo_delete(a); } } ``` Note that a deleter is emitted for the value of type `Foo` once the `let` block ends and it goes out of scope, but not for the value of type `Bar`, which has no deleter associated with it. ### Related pages * [Drop][2] - a deeper look at the `drop` interface [1]: https://www.rust-lang.org [2]: Drop.md [3]: CInterop.md#register-types --- ### Multimedia ## Multimedia Libraries The Carp compiler comes bundled with bindings for a few common games/multimedia libraries. For installation instructions, see [Install.md](Install.md). ### SDL You can find the API documentation for the SDL bindings [here](http://carp-lang.github.io/carp-docs/sdl/SDL_index.html). Many of the [examples](../examples) use these bindings -- check them out! ### OpenGL See [OpenGL.carp](../core/OpenGL.carp) --- ### Quasiquotation # Quasiquotation Quasiquotation is a way to quote parts of a list while evaluating others. It’s only available in the dynamic parts of the program. Quasiquotation enables the user to intersperse evaluated or “unquoted” portions into a unevaluated or “quoted” list. ```clojure (defdynamic x 2) (quasiquote (+ (unquote x) 1)) ; => (+ 2 1) ; also available as literals, quasiquote becomes ` ; and unquote becomes % `(+ %x 1) ; => (+ 2 1) ``` Note that unquoting only makes sense inside `quasiquote` forms and using it outside will lead to errors at macro expansion time. Since quasiquotation primarily deals with lists, the user might sometimes want to intersperse another list of values flatly, “splicing” them in. For this case Carp provides `unquote-splicing`. ```clojure (defdynamic x '(1 2)) (quasiquote (+ (unquote-splicing x))) ; => (+ 1 2) ; the literal for unquote-splicing is %@ `(+ %@x) ; => (+ 1 2) ``` Please note that while the code examples above only use variables, any expression can be used inside the `unquote` variants. ```clojure (quasiquote (+ (unquote-splicing (map inc [1 2])))) ; => (+ 2 3) ; or `(+ %@(map inc [1 2])) ; => (+ 2 3) ``` --- ### ReleaseChecklist # Release Checklist Do all of these things (somewhat) in order: ## 1. Update Cabal project version See the second line of the file [CarpHask.cabal](../CarpHask.cabal). ## 2. Update the "Welcome to Carp X.Y.Z" REPL message See [Main.hs](../App/Main.hs). ## 3. Update the blurb in README.md See [README.md](../README.md) ## 4. Update the changelog See [CHANGELOG.md](../CHANGELOG.md) ## 5. Make a commit on master ```bash $ git add . $ git commit -m "build: Release X.Y.Z" ``` ## 6. Tag the commit and push it ```bash $ git tag vX.Y.Z $ git push --tags ``` --- ### Terminology # Terminology (WORK IN PROGRESS) ## Introduction This document contains commonly used words, concepts and jargon for the Carp programming language. It should be particularly helpful when naming things and writing documentation. Ideally it will remove ambiguity, make us spell things the same way, and generally make the Carp ecosystem feel more unified. Pull requests for this document are very welcome, and please tell us in the [Gitter Channel](https://gitter.im/eriksvedang/Carp?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge&utm_content=badge) if something is missing! ### Mutating function What should this mean exactly? Ideally it should only be used for functions ending in a `!` that return `()`. Perhaps it should be called "externally mutating function"..? Or maybe "exo-functions" :) ### Owning function An *owning* function is a function that takes ownership over the value it is passed. This means that is has responsibility of freeing that memory (or pass it to another owning function, or return it). ### Borrowing function A *borrowing* function is a function that does not take ownership over the value it is passed. This means that is is not allowed to free the memory of that value but must leave it intact. ### Transforming function / endo-functions What is a good name for a function that is both owning and internally mutating, like `endo-map`? These functions are common in Carp and allow for a functional programming style without the need to copy or allocate memory. ### Unsafe function Unsafe functions (most often) start with the prefix `unsafe-` and *can* crash the program if certain preconditions are not met. A good example is `Array.unsafe-first` which gets the first value in an array. Calling this if the array is empty will crash the program. The `unsafe-` prefix is an optional naming convention; there *are* a few functions that are not safe which does not use this naming scheme. A notable example is `Array.nth` which crashes if given an invalid index. Any other unsafe functions should be thoroughly documented as such, and using the `unsafe-` prefix is very much encouraged in library code! ### REPL *REPL* stands for "Read Eval Print Loop" and is a common feature of a Lisp system. It allows expressions to be entered and executed at a command prompt. In Carp it is spelled with uppercase letters. --- ### Tooling # Tooling ## Vim [https://github.com/hellerve/carp-vim](https://github.com/hellerve/carp-vim) ## Emacs [https://github.com/carp-lang/carp-emacs](https://github.com/carp-lang/carp-emacs) ## Atom [language-carp](https://atom.io/packages/language-carp) offers highlight with both TextMate and Tree-sitter, where tree-sitter grammar is more powerful. ## Other editors Clojure syntax highlighting works very well with Carp since it uses the same symbols for most things. If you have written an editor mode, please tell us and it will be added here! --- ### Hacking # Hacking the Carp Compiler This doc contains various tips and tricks, notes, explanations and examples that can help you make changes to the Carp compiler. Be forewarned that it's not an exhaustive guide book, and likely will remain a hodgepodge of accumulated remarks, observations and hints contributed by people that have modified the compiler in the past. > Note: General familiarity with compilers and compilation terminology is > assumed. ## Structure The Carp compiler source lives in the `src/` directory. Carp is, roughly speaking, organized into four primary passes or components: Each source file plays a part in one or more components/phases in the compiler. The sections below briefly describe the purpose of each stage and list important source files. You can use these sections to get a rough idea of what files you might need to edit in order to alter the functionality of a particular phase. > Note: Some sources contain definitions that are important or used in pretty > much every phase of the compiler, in result some files may appear more than > once in the sections below. ### Parsing The parsing phase translates `.carp` source files into abstract syntax trees (AST). In carp, AST nodes are represented using an abstract data type called `XObj`. `XObj`s are ubiquitous across the compiler and are used in several different phases and contexts. Every `XObj` consists of: - An `Obj` which is the representation of some carp source code as an abstract data type - `Info`: which contains additional information about the source code that generated an `Obj` (e.g. its location in a source file) - `Ty`: An valid carp Type for the `Obj`, as determined by the [type system](#type-system). The following sources are important for parsing: - `Parsing.hs` -- parsing logic that translates carp source code into abstract syntax. - `XObj.hs` -- defines the valid Carp AST nodes. ### Dynamic Evaluator As stated in the [Macro guide](Macros.md#inner-workings) the dynamic evaluator is the central component in the compiler. As the name suggests, the evaluator evaluates parsed carp code (`XObjs`) and prepares it for [emission](#code-emission). Evaluation entails: - Expanding macros and dynamic functions - Resolving bindings to other forms - Requesting type inference for forms - Requesting borrow checking for forms In addition to the `XObjs` corresponding to the source file being compiled, the evaluator relies on a `Context`--`Context` is a global object that contains state for the compiler. The compiler's `Context` is comprised of several environments, defined by the `Env` type--which hold references to known bindings. Different environments are used by different phases of the compiler to evaluate forms, resolve types, and, generally speaking prepare code for emission. `Binders` are another important abstract data type used in evaluation. Any value that's bound to a name in a source program is translated into a `binder`, which is comprised of the `XObj` of the form bound to the name, as well as additional metadata for the binding. `Binders` are added to the environments in the `Context`. The following sources are important for evaluation: - `Eval.hs` -- public entry point for the evaluator. - `EvalIR.hs` -- evaluator IR and lowering from `XObj`. - `EvalVM.hs` -- evaluator VM compile-and-run path (`runEvalIRVM`). - `EvalCode.hs` / `EvalVMCore.hs` -- evaluator bytecode and low-level VM runtime. - `Obj.hs` -- Defines `Context` which carries compiler state across evaluation passes in the form of `Env`s, defines `Env` which holds `Binders` from names to `XObjs`. - `Primitives.hs` -- builtin functions or "keywords" that **do not** evaluate their arguments - `Commands.hs` -- builtin functions or "keywords" that evaluate their arguments - `StartingEnv.hs` -- defines the starting environment for the compiler to work with. All commands and primitives are registered here, so that evaluation passes can use them. - `Lookup.hs` -- Functions for looking up `Binders` in a given environment (`Env`). - `Expand.hs` -- Functions for traversing forms and doing syntactic analysis. Historically also expanded macros (that functionality was moved into `Eval.macroExpand`). - `Infer.hs` -- Functions for performing type inference -- entry point into the type system. - `Qualify` -- Qualifies symbols with appropriate module names. Some other pieces of the type system and borrow checking mechanisms could be included in this list as well, but this list captures the core functionality related to evaluation. Generally speaking, the evaluation component is the conductor of our compilation symphony and orchestrates all the other parts of the compiler. > Note: For a more in depth look at the dynamic evaluator, see [the section on > inner workings in the Macro guide](Macros.md#inner-workings) and > [Dynamic Evaluator VM](EvaluatorVM.md). ### Type System The type system is responsible for checking the types of Carp forms and ensuring programs are type safe. It also supports polymorphism and is responsible for replacing polymorphic types with concrete types. Carp types are represented by the `Ty` data type. The following sources are important for the type system: - `Types.hs` -- defines the `Ty` data type, which represents valid carp types. Also contains unification checking code to determine whether or not two types are compatible. Also contains mangling code, that translates carp type names with valid C identifiers. - `TypeError.hs` -- defines type checking errors. - `AssignTypes.hs` -- Assigns concrete types to variables. - `Polymorphism.hs` -- Given a concretized polymorphic function, determines the correct valid C identifier for the concrete function. - `Validate.hs` -- Checks that user-defined types are valid. - `Constraints.hs` -- Determines and solves constraints between types and type variables in an environment. - `Concretize.hs` -- Transforms forms that involve polymorphic types into concrete types. - `InitialTypes.hs` -- determines the initial type of a given `XObj` (AST node). - `GenerateConstraints.hs` -- determines type constraints for a given form. ### Borrow Checking/Ownership System Borrow checking an lifetime parameters are an extension of the [type system](#type-system). All of the files that are important to the type system are likewise important for the borrow checker. ### Code Emission The compiler's final job is to emit C code corresponding to the source Carp input. Emission relies heavily on the concept of `Templates` -- effectively a structured way to generate C strings based on evaluated Carp AST nodes. The following sources are important for the code emission system: - `ArrayTemplates.hs` -- Templates for C code corresponding to Array use in Carp. - `StaticArrayTemplates.hs` -- Templates for C code corresponding to StaticArray use in Carp. - `Deftype.hs` -- Templates for C code corresponding to user defined structs in Carp (aka product types) (also contains some other logic for registering bindings for such types). - `Sumtypes.hs` -- Templates for C code corresponding to user defined sumtypes in Carp (also contains some other logic for registering bindings for such types). - `StructUtils.hs` -- Templates for C code corresponding to utility functions for Carp structs. - `Template.hs` -- General compiler instructions for generating C code. - `ToTemplate.hs` -- Helper for creating templates from strings of C code. - `Scoring.hs` -- determines an appropriate sort order for emitted C bindings based on typing and `XObj` information. - `Emit.hs` -- Emits generated C code based on evaluated, compiled Carp source code. ### Other sources In addition to the sources listed above, there are other miscellaneous source files that serve different purposes in the compiler: - `Repl.hs` -- defines repl functionality, such as keyword completion, repl commands, etc. - `Util.hs` -- various utility functions - `ColorText.hs` -- supports colored output in the Repl/compiler output. - `Path.hs` -- Filepath manipulation functions. - `RenderDocs.hs` -- Functionality for generating documentation from annotated carp Code. ## Mini HowTos Select compiler changes are more frequent than others and have common high-level steps. The following sections provide some guidance on making such changes. ### Adding a new Primitive If it doesn't require anything fancy or out of the ordinary, adding a new primitive to the compiler entails the following: 1. Define your new primitive in `Primitives.hs` 2. Add your primitive to the starting environment using `makePrim` in `StartingEnv.hs` #### Define your Primitive Primitives are functions of the `Primitive` type: ``` type Primitive = XObj -> Context -> [XObj] -> IO (Context, Either EvalError XObj) ``` Every primitive takes an xobj, the form that represents the primitive, a compiler context, and a list of XObjs the primitive form's arguments. Primitives return a new `Context`, updated based on the logic they performed, and either an XObj or evaluation error that's reported to the user. For example, here's how the `defmodule` primitive maps to the `Primitive` type: ``` (defmodule Foo (defn bar [] 1)) | |-----------------| XObj [XObj] (arguments) ``` > The `Context` argument captures the state of the compiler and doesn't have a > corresponding direct representation in Carp forms. In `Primitives.hs`, you should name your primitive using the naming scheme `primitive`, where `` is the name of the symbol that will call your primitive in Carp code. For example, `defmodule` is given by the primitive `primitiveDefmodule`. Most of the time, primitives have three core steps: - Pattern match on their argument XObjs - Lookup existing binders in the current `Context` - Perform some logic based on the type of argument XObjs, then update the `Context` as needed. Let's step through each of these core steps by implementing a simple `immutable` primitive. The `immutable` primitive will take a variable (the name of a form passed to a `def`) and mark it as `immutable`, preventing users from calling `set!` on it. - Step 1. Pattern match on arguments. First thing's first, our primitive, in carp code, should look like this: ``` (immutable my-var) ``` This means that our primitive should only take a single argument XObj, and that argument should be a `Sym`. Let's match some patterns: ``` primitiveImmutable :: Primitive -- our new primitive primitiveImmutable xobj ctx [XObj (Sym path@(SymPath) _)] = -- TODO: Implement me! primitiveImmutable _ _ xobjs = -- any other number or types of xobj arguments are incorrect! Let's error. return $ evalError ctx ("`immutable` expected a single symbol argument, but got" ++ show xobjs) (info xobj) ``` And that's all we need to do to pattern match! - Step 2. Lookup binders in the current context Assuming `immutable` gets a correct argument, our next step is to use the `Sym` XObj it received to find out if the symbol is bound to a variable or not. `Lookup.hs` defines functions for looking up bindings in the various environments contained in a context. We'll call lookup functions to check whether or not the symbol argument we get is bound to a `def` form (in which case it's a variable). If the symbol isn't bound to a `def` we'll error. So, we'll get the binding for our argument (a `Binder`), match against the binding's `XObj` and continue working only if it's a `def`. ``` primitiveImmutable :: Primitive -- our new primitive primitiveImmutable xobj ctx [XObj (Sym path@(SymPath) _)] = let global = contextGlobalEnv ctx binding = lookupInEnv path global in case binding of Just (_, Binder meta (XObj )) -> -- TODO: This is a def! Great. Do more work here. _ -> -- anything that isn't a def; error return $ evalError ctx ("`immutable` expects a variable as an argument") (info xobj) primitiveImmutable _ _ xobjs = -- any other number or types of xobj arguments are incorrect! Let's error. return $ evalError ctx ("`immutable` expected a single symbol argument, but got" ++ show xobjs) (info xobj) ``` - Step 3. Perform logic; update the `Context` Finally, now that we're certain we've got a def, we'll just perform our special logic then update the context with our modified binder. To keep things simple, all we'll do in this primitive is update the binder's `MetaData` with a new key called `immutable` set to `true`. We can later use the value of this meta field to prevent calls to `set!`. ``` primitiveImmutable :: Primitive -- our new primitive primitiveImmutable xobj ctx [XObj (Sym path@(SymPath) _)] = let global = contextGlobalEnv ctx binding = lookupInEnv path global in case binding of Just (_, Binder meta def@(XObj Def _ _)) -> let oldMeta = getMeta meta newMeta = meta {getMeta = Map.insert "immutable" trueXObj oldMeta} -- update the binder metadata in return $ ctx {contextGlobalEnv = Env (envInsertAt global path (Binder newMeta def))} -- update the context with the binder and it's new meta and return _ -> -- anything that isn't a def; error return $ evalError ctx ("`immutable` expects a variable as an argument") (info xobj) primitiveImmutable _ _ xobjs = -- any other number or types of xobj arguments are incorrect! Let's error. return $ evalError ctx ("`immutable` expected a single symbol argument, but got" ++ show xobjs) (info xobj) ``` And that wraps up the core logic of our primitive. To make it available, we just need to register it in `StartingEnv.hs`. #### Add your primitive to the starting environment To add a primitive to the starting environment, call `makePrim`: ``` , makePrim "immutable" 1 "annotates a variable as immutable" "(immutable my-var)" primitiveImmutable ``` That's about it. Note that this implementation just adds special metadata to bindings--to actually prevent users from calling `set!` on an immutable `def` we'd need to update `set!`'s logic to check for the presence of the `immutable` metadata. --- ### Patterns # Carp Patterns This doc captures some common programming patterns in Carp. ## Ref-let You may occasionally want to compute the result of running two different ownership-taking functions on a non-ref argument from an enclosing scope. Consider the following function: ```clojure (defn needs-ref-let [x] (Pair.init (Maybe.or-zero x) (Maybe.or-zero x))) ``` Carp will complain about this function since `Maybe.or-zero` *takes ownership* of the non-ref, managed argument `x`1 -- this is nice since it ensures we don't somehow mutate the memory associated with `x` -- if we did, we would get unpredictable results, especially in multi-threaded contexts in which `Maybe.or-zero` may try to access `x` simultaneously. But you may still want to compute both `Maybe.or-zero` calls on the single `x` value! For these cases, it's useful to introduce a variable bound to a `Ref` to `x`: ```clojure (defn needs-ref-let [x] (let [x* &x] (Pair.init (Maybe.or-zero @x*) (Maybe.or-zero @x*)))) ``` `x*`, which is just a reference to the `x` argument, allows you to flexibly copy `x` at will throughout the function body. Of course, the second copy here is actually unnecessary, since once we've copied `x` once, we're free to use `x` itself again: ```clojure (defn needs-ref-let [x] (let [x* &x] (Pair.init (Maybe.or-zero @x*) (Maybe.or-zero x)))) ``` --- 1: In Carp, sumtypes like `Maybe` are *managed* by the borrow checker. This means that Carp will ensure any memory associated with them has proper ownership and is deleted when they are no longer needed. Not all types are managed. `Int`, for example, is not a managed type, and so the issue described above won't be relevant for `Int` arguments. For more information see [docs/memory.md](Memory.md) ---