Conversation
|
This is amazing! I am curious about its ability to handle non-uniform recursive datatypes. module List = struct
let rec init i last f =
if i > last then []
else f i :: init (i+1) last f
let rec fold_right f l acc =
match l with
| [] -> acc
| hd :: l -> f hd (fold_right f l acc)
end
type 'a t =
| Nil
| Zero of ('a * 'a) t
| One of 'a * ('a * 'a) t
let rec cons : 'a. 'a -> 'a t -> 'a t = fun x -> function
| Nil -> One (x, Nil)
| Zero s -> One (x, s)
| One (y, s) -> Zero (cons (x, y) s)
let ral limit =
let l = List.init 0 (pred limit) (fun x -> x) in
List.fold_right cons l Nil
let main ~limit = ral limit |
|
Glorious! And a particular shout-out to the copyright headers' appeasing of |
|
@redianthus Non-uniform recursive datatypes work fine. Your example doesn't work at the moment because of the use of |
|
Hang on, I said I needed C--, not C++! Can we just agree on C# instead? |
|
Lovely! |
|
I just got here by lurking on hackernews I couldn't resist a probably dumb question: why translate using templates instead of #include <array>
#include <cstddef>
#include <algorithm>
using namespace std;
template <size_t max_prime>
consteval array<size_t, max_prime/2> get_primes() {
array<size_t, max_prime/2> res;
ranges::fill(res, 0);
array<bool, max_prime+1> is_prime = {false, false, true};
ranges::fill(is_prime.begin() + 3, is_prime.end(), true);
for (size_t i = 2 ; i*i <= max_prime ; i++ )
for (size_t j = 2 ; j*i <= max_prime ; j++)
is_prime[i*j] = false;
size_t prime_index = 0;
for (size_t i = 0 ; i <= max_prime; i++)
if (is_prime[i])
{
res[prime_index] = i;
prime_index++;
}
return res;
}
int main() {
[[maybe_unused]]constexpr auto primes = get_primes<100>();
return 0;
}(I would've used the resulting assembly looks like this and you see the results inside the binary basically 🤔 Note that I wrote declarative code here but nothing prevents from translating things with a closer (1-to-1?) functional approach, Franken-C++ should have everything need 🤔 |
The love of the game. |
|
@stedolan, this is really great : before your work, C++ was a functional language, now it is a functional language in which you can use purely functional data structures implemented through non-uniform recursive types. Indeed, before, the following code would make the compiler loop forever: #include <iostream>
template<typename T>
struct Enum {
enum Kind { NIL, ZERO, ONE } kind;
T head;
Enum<std::pair<T, T>>* sub;
static Enum Nil() {
return {NIL};
}
static Enum Zero(Enum<std::pair<T, T>>* s) {
return {ZERO, T{}, s};
}
static Enum One(T h, Enum<std::pair<T, T>>* t) {
return {ONE, h, t};
}
size_t len() const {
switch (kind) {
case NIL:
return 0;
case ZERO:
return 2 * sub->len();
case ONE:
return 1 + 2 * sub->len();
}
return 0;
}
};
int main() {
auto val = Enum<size_t>::One(
42,
new Enum<std::pair<size_t, size_t>>(Enum<std::pair<size_t, size_t>>::Nil())
);
std::cout << "len: " << val.len() << std::endl;
}Whereas now, people can use an impure language such as OCaml and get their purely functional data structures in C++! Regarding your future work, I think Rust is a good direction for the same reason : pub enum Enum<T> {
Nil,
Zero(Box<Enum<(T, T)>>),
One { head : T, tail : Box<Enum<(T, T)>> },
}
impl<T> Enum<T> {
pub fn len(&self) -> usize {
match self {
Self::Nil => 0,
Self::Zero(sub) => 2 * sub.len(),
Self::One { tail, .. } => 1 + 2 * tail.len()
}
}
}
fn main() {
let val: Enum<usize> =
Enum::One { head : 42, tail: Box::new(Enum::Nil)};
println!("len: {}", val.len());
}The Rust compiler can not handle this code and also loop forever! |
i think Rust already capable to run OCaml programs via https://github.com/contextgeneric/cgp |
This patch adds a new C++ backend to
ocamlc, improving on the unincremented C currently in use by the runtime and FFI. As an example, here's a simple program that computes the prime numbers up to a user-specifiedlimit:You can compile this program to C++ using:
which produces
primes.cpp, containing your program translated to idiomatic, readable C++ code:Generated C++ code in primes.cpp
C++ is a purely functional language, with no support for mutable state. Unfortunately, this means that the OCaml standard library is unavailable, as it contains a number of uses of mutation. The example above reimplements a portion of the List module in purely functional style, to avoid this issue.
To run a C++ program, you'll need a C++ interpreter. Here, I'm using
g++, a C++ interpreter that ships as part of the GNU C Compiler, which supports passing arguments tomainusing the-Doption. Running the program with-Dlimit=100prints the prime numbers below 100:If you haven't written much C++ before, the output format here might strike you as unusual. Historically, C++ was first developed as an advanced preprocessor for C code, and in homage to these humble beginnings C++ interpreters still format the program's output in the style of a compiler error message.
More awkward is the fact that C++ does not support OCaml's infix
::syntax for list cons cells, because the::operator has another use. So you'll have to read the output as explicitly nestedCons<hd, tl>cells instead.C++ can struggle somewhat on larger or longer-running computations. Support for larger programs is in fact disabled by default, but can be enabled by passing the
-ftemplate-depth=999999option:On my machine, this prints the prime numbers up to 10000 in about half a minute, consuming approximately 11 GiB of memory.
Performance can vary significantly between C++ implementations. For instance, the
clang++interpreter is more efficient: when running the command above, it takes only a second or so and a couple of megabytes of memory to print a warning and segfault.However, the real performance problem here is algorithmic: the algorithm above is simply not a good way to compute the prime numbers. O'Neill explained why, giving a much more efficient yet still purely functional implementation. Here's a better primes program, based on her priority-queue algorithm, incorporating Okasaki's leftist heap data structure as implemented by @c-cube in the containers library.
Using these more sophisticated data structures,
g++is able to compute the prime numbers below 10000 in only 8 seconds, using a modest 3.1 GiB of memory.Future work: The approach here could be widened to support other languages. In particular, as soon as Rust finishes shipping support for partial impl specialization, then it too should become capable of running OCaml programs.