diff options
| author | Arnaud Bailly <arnaud.bailly@iohk.io> | 2025-01-25 10:45:41 +0100 |
|---|---|---|
| committer | Arnaud Bailly <arnaud.bailly@iohk.io> | 2025-01-25 10:45:41 +0100 |
| commit | 7752d73216578d5961751b5d0535088d384b4aa6 (patch) | |
| tree | 786e46fe1276e93ade0a48398cd4c9ac13081707 /lambda-calcul | |
| parent | d6f68e919db51d366c8ca3c1509bea12aa81d692 (diff) | |
| download | lambda-nantes-7752d73216578d5961751b5d0535088d384b4aa6.tar.gz | |
Move λ-calcul workshop code to subdirectory
Diffstat (limited to 'lambda-calcul')
64 files changed, 8915 insertions, 0 deletions
diff --git a/lambda-calcul/clojure/.gitignore b/lambda-calcul/clojure/.gitignore new file mode 100644 index 0000000..883fee3 --- /dev/null +++ b/lambda-calcul/clojure/.gitignore @@ -0,0 +1,6 @@ +.cpcache +.nrepl-port +.calva + +target + diff --git a/lambda-calcul/clojure/deps.edn b/lambda-calcul/clojure/deps.edn new file mode 100644 index 0000000..b43182c --- /dev/null +++ b/lambda-calcul/clojure/deps.edn @@ -0,0 +1,13 @@ +{:paths ["src"] + :deps + {metosin/reitit {:mvn/version "0.7.0"} + metosin/reitit-middleware {:mvn/version "0.7.0"} + ring/ring-jetty-adapter {:mvn/version "1.12.1"} + ring/ring-devel {:mvn/version "1.12.1"} + clj-http/clj-http {:mvn/version "3.13.0"}} + + :aliases + {;; Run with clj -T:build function-in-build + :build {:deps {io.github.clojure/tools.build {:git/tag "v0.10.0" :git/sha "3a2c484"}} + :ns-default build}}} +
\ No newline at end of file diff --git a/lambda-calcul/clojure/src/lccl/app.clj b/lambda-calcul/clojure/src/lccl/app.clj new file mode 100644 index 0000000..522d8bf --- /dev/null +++ b/lambda-calcul/clojure/src/lccl/app.clj @@ -0,0 +1,30 @@ +(ns lccl.app + (:require [reitit.ring :as ring-reitit] + [reitit.coercion.malli] + [reitit.ring.malli] + [reitit.dev.pretty :as pretty] + [reitit.ring.middleware.muuntaja :as muuntaja] + [muuntaja.core :as m])) + +(defn eval + [request] + (let [sexpr (slurp (:body request))] + (println "Demande d'évaluation de l'expression :" sexpr) + {:status 200, :body sexpr})) + +(defn api-handler + [] + (ring-reitit/ring-handler + (ring-reitit/router + [["/eval" {:post eval}]] + + {:exception pretty/exception + :data { + :muuntaja m/instance + :middleware [muuntaja/format-response-middleware]}}))) + +(defn app-handler + [] + (ring-reitit/routes (api-handler))) + + diff --git a/lambda-calcul/clojure/src/lccl/fwk/middlewares.clj b/lambda-calcul/clojure/src/lccl/fwk/middlewares.clj new file mode 100644 index 0000000..973cffc --- /dev/null +++ b/lambda-calcul/clojure/src/lccl/fwk/middlewares.clj @@ -0,0 +1,15 @@ +(ns lccl.fwk.middlewares + (:require [ring.middleware.reload :as reload])) + +; https://bogoyavlensky.com/blog/auto-reloading-ring/ +(defn reloading-ring-handler + "Reload ring handler on each request." + [f] + (let [reload! (#'reload/reloader ["src"] true)] + (fn + ([request] + (reload!) + ((f) request)) + ([request respond raise] + (reload!) + ((f) request respond raise)))))
\ No newline at end of file diff --git a/lambda-calcul/clojure/src/lccl/lc/ast.clj b/lambda-calcul/clojure/src/lccl/lc/ast.clj new file mode 100644 index 0000000..58bad11 --- /dev/null +++ b/lambda-calcul/clojure/src/lccl/lc/ast.clj @@ -0,0 +1,7 @@ +(ns lccl.lc.ast) + +(defrecord Var [name]) +(defrecord Abs [arg body]) +(defrecord App [left right]) + +(def IDENTITY (->Abs "x" (->Var "x"))) diff --git a/lambda-calcul/clojure/src/lccl/lc/evaluator.clj b/lambda-calcul/clojure/src/lccl/lc/evaluator.clj new file mode 100644 index 0000000..70e972e --- /dev/null +++ b/lambda-calcul/clojure/src/lccl/lc/evaluator.clj @@ -0,0 +1,28 @@ +(ns lccl.lc.evaluator + (:import [lccl.lc.ast Var Abs App]) + (:require [lccl.lc.ast :refer [->Abs ->App]])) + +(declare substitute) + +(defmulti evaluate (fn [term] [(type term)])) +(defmethod evaluate [Var] ([term] term)) +(defmethod evaluate [Abs] ([term] term)) +(defmethod evaluate [App] + ([term] + (let [left (-> term :left)] + (condp = (type left) + Abs (substitute (:body left) (:arg left) (:right term)) + term)))) + +(defmulti substitute (fn [body arg val] [(type body)])) +(defmethod substitute [Var] + ([body arg val] + (if (= (:name body) arg) val body))) +(defmethod substitute [Abs] + ([body arg val] + (if (= (:arg body) arg) + body + (->Abs (:arg body) (substitute (:body body) arg val))))) +(defmethod substitute [App] + ([body arg val] + (->App (substitute (:left body) arg val) (substitute (:right body) arg val)))) diff --git a/lambda-calcul/clojure/src/lccl/main.clj b/lambda-calcul/clojure/src/lccl/main.clj new file mode 100644 index 0000000..071d7c6 --- /dev/null +++ b/lambda-calcul/clojure/src/lccl/main.clj @@ -0,0 +1,36 @@ +(ns lccl.main + (:require [ring.adapter.jetty :as ring-jetty] + [clj-http.client :as client] + [lccl.app :as app] + [lccl.fwk.middlewares :as middlewares]) + (:gen-class)) + +(def TEAM_NAME "LCCL") +(def SELF_PORT 8888) +(def SELF_URL (str "http://127.0.0.1:" SELF_PORT)) +(def TESTER_URL "http://127.0.0.1:8080") + +(defn run-http-server! + [{:keys [dev-mode? server-options]}] + (let [create-handler-fn #(app/app-handler) + handler* (if dev-mode? + (middlewares/reloading-ring-handler create-handler-fn) + (create-handler-fn))] + (ring-jetty/run-jetty handler* server-options) + (println "Evaluateur à l'écoute sur le port" (:port server-options)))) + +(defn- run! [{dev-mode? :dev-mode?}] + (run-http-server! {:dev-mode? dev-mode? + :server-options {:join? false :port SELF_PORT}}) + (let [response (client/post (str TESTER_URL "/register") + {:body (str "{\"url\": \"" SELF_URL "/eval\", \"name\": \"" TEAM_NAME "\"}") + :content-type :json + :accept :json})] + (println "Résultat de l'enregistrement : " (:body response)))) + +(defn -main + [& _] + (run! {:dev-mode? false})) + +(comment + (run! {:dev-mode? true})) diff --git a/lambda-calcul/clojure/test/lccl/lc/evaluator_test.clj b/lambda-calcul/clojure/test/lccl/lc/evaluator_test.clj new file mode 100644 index 0000000..d1e9c41 --- /dev/null +++ b/lambda-calcul/clojure/test/lccl/lc/evaluator_test.clj @@ -0,0 +1,46 @@ +(ns lccl.lc.evaluator-test + (:require + [clojure.test :refer [deftest testing is]] + [lccl.lc.ast :refer [->Var ->Abs ->App IDENTITY]] + [lccl.lc.evaluator :refer [substitute evaluate]])) + +(def x (->Var "x")) +(def y (->Var "y")) +(def z (->Var "z")) + +(defn- assertEvalTo + [termToEvaluate result] + (is (= result (evaluate termToEvaluate)))) + +(deftest evaluation + (testing "l'evaluation d'une variable rend la même variable" + ; evaluate(x) == x + (assertEvalTo x x)) + (testing "l'evaluation d'une abstraction rend la même abstraction" + ; evaluate(λx.x) == λx.x + (assertEvalTo IDENTITY IDENTITY)) + (testing "l'evaluation de l'application de deux vars rend la même abstraction" + ; evaluate(x y) == x y + (assertEvalTo (->App x y) (->App x y))) + (testing "l'evaluation de l'application de l'identite sur un argument rend l'argument" + ; evaluate((λx.x) y) == y + (assertEvalTo (->App IDENTITY y) y)) + (testing "l'evaluation de l'application d'une abstraction substitue son argument" + ; evaluate((λx.x x) y) == y y + (assertEvalTo (->App (->Abs "x" (->App x x)) y) (->App y y))) + (testing "l'evaluation de l'application d'une abstraction d'abstraction substitue recursivement son argument" + ; evaluate((λx.λy.x) z) == λy.z + (assertEvalTo (->App (->Abs "x" (->Abs "y" x)) z) (->Abs "y" z))) + (testing "l'evaluation de l'application d'une abstraction ne substitue pas ses variables libres" + ; evaluate((λx.y) z) == y + (assertEvalTo (->App (->Abs "x" y) z) y)) + (testing "l'evaluation de l'application d'une abstraction d'abstraction ne substitue pas les variables redéfinies" + ; evaluate((λx.λx.x) z) == λx.x + (assertEvalTo (->App (->Abs "x" (->Abs "x" x)) z) (->Abs "x" x))) + ) + +(deftest substitution + (testing "la substitution d'une variable rend la même variable" + ; substitute(x x, y) == y y + (is (= y (substitute x "x" y))))) + diff --git a/lambda-calcul/elixir/.formatter.exs b/lambda-calcul/elixir/.formatter.exs new file mode 100644 index 0000000..d2cda26 --- /dev/null +++ b/lambda-calcul/elixir/.formatter.exs @@ -0,0 +1,4 @@ +# Used by "mix format" +[ + inputs: ["{mix,.formatter}.exs", "{config,lib,test}/**/*.{ex,exs}"] +] diff --git a/lambda-calcul/elixir/.gitignore b/lambda-calcul/elixir/.gitignore new file mode 100644 index 0000000..12fd196 --- /dev/null +++ b/lambda-calcul/elixir/.gitignore @@ -0,0 +1,26 @@ +# The directory Mix will write compiled artifacts to. +/_build/ + +# If you run "mix test --cover", coverage assets end up here. +/cover/ + +# The directory Mix downloads your dependencies sources to. +/deps/ + +# Where third-party dependencies like ExDoc output generated docs. +/doc/ + +# Ignore .fetch files in case you like to edit your project deps locally. +/.fetch + +# If the VM crashes, it generates a dump, let's ignore it too. +erl_crash.dump + +# Also ignore archive artifacts (built via "mix archive.build"). +*.ez + +# Ignore package tarball (built via "mix hex.build"). +workshop1-*.tar + +# Temporary files, for example, from tests. +/tmp/ diff --git a/lambda-calcul/elixir/README.md b/lambda-calcul/elixir/README.md new file mode 100644 index 0000000..fe5b773 --- /dev/null +++ b/lambda-calcul/elixir/README.md @@ -0,0 +1,21 @@ +# Workshop1 + +**TODO: Add description** + +## Installation + +If [available in Hex](https://hex.pm/docs/publish), the package can be installed +by adding `workshop1` to your list of dependencies in `mix.exs`: + +```elixir +def deps do + [ + {:workshop1, "~> 0.1.0"} + ] +end +``` + +Documentation can be generated with [ExDoc](https://github.com/elixir-lang/ex_doc) +and published on [HexDocs](https://hexdocs.pm). Once published, the docs can +be found at <https://hexdocs.pm/workshop1>. + diff --git a/lambda-calcul/elixir/ast.ex b/lambda-calcul/elixir/ast.ex new file mode 100644 index 0000000..4305b7b --- /dev/null +++ b/lambda-calcul/elixir/ast.ex @@ -0,0 +1,34 @@ +defmodule Ast do + def var(name), do: {:var, name} + def abs(param, body), do: {:abs, param, body} + def app(func, param), do: {:app, func, param} + + def pprint(expr) do + case expr do + {:var, name} -> name + {:abs, param, body} -> "(λ #{param} . #{pprint(body)})" + {:app, func, param} -> "#{pprint(func)} #{pprint(param)}" + end + end + + def free_vars(expr) do + case expr do + {:var, name} -> MapSet.new([name]) + {:abs, param, body} -> MapSet.delete(free_vars(body), param) + {:app, func, param} -> MapSet.union(free_vars(func), free_vars(param)) + end + end + + def subst(expr, old_var, new_expr) do + case expr do + {:var, name} -> + if name == old_var, do: new_expr, else: expr + + {:abs, param, body} -> + if param == old_var, do: expr, else: {:abs, param, subst(body, old_var, new_expr)} + + {:app, func, param} -> + {:app, subst(func, old_var, new_expr), subst(param, old_var, new_expr)} + end + end +end diff --git a/lambda-calcul/elixir/ast_test.exs b/lambda-calcul/elixir/ast_test.exs new file mode 100644 index 0000000..b10c959 --- /dev/null +++ b/lambda-calcul/elixir/ast_test.exs @@ -0,0 +1,70 @@ +defmodule AstTest do + use ExUnit.Case + + test "pprint/1" do + assert Ast.pprint(Ast.var("x")) == "x" + assert Ast.pprint(Ast.abs("x", Ast.var("x"))) == "(λ x . x)" + assert Ast.pprint(Ast.app(Ast.var("x"), Ast.var("y"))) == "x y" + end + + test "pprint with if expression lambda calculus" do + assert Ast.pprint(Ast.abs("f", Ast.abs("y", Ast.app(Ast.var("f"), Ast.var("x"))))) == + "(λ f . (λ y . f x))" + end + + test "free_vars-1" do + program = Ast.var("x") + expected = MapSet.new(["x"]) + repr_expected = "x" + repr_subs_expected = "y" + + assert MapSet.equal?(Ast.free_vars(program), expected) + assert Ast.pprint(program) == repr_expected + + assert Ast.pprint(Ast.subst(program, "x", Ast.var("y"))) == repr_subs_expected + end + + test "free_vars-2" do + program = Ast.abs("x", Ast.var("x")) + expected = MapSet.new([]) + repr_expected = "(λ x . x)" + repr_subs_expected = "(λ x . x)" + + assert MapSet.equal?(Ast.free_vars(program), expected) + assert Ast.pprint(program) == repr_expected + + assert Ast.pprint(Ast.subst(program, "x", Ast.var("y"))) == repr_subs_expected + end + + test "free_vars-3" do + program = Ast.app(Ast.var("f"), Ast.var("x")) + expected = MapSet.new(["f", "x"]) + repr_expected = "f x" + + assert MapSet.equal?(Ast.free_vars(program), expected) + assert Ast.pprint(program) == repr_expected + end + + test "free_vars-4" do + program = + Ast.abs( + "f", + Ast.app(Ast.var("x"), Ast.abs("x", Ast.app(Ast.var("f"), Ast.var("x")))) + ) + + expected = MapSet.new(["x"]) + repr_expected = "(λ f . x (λ x . f x))" + + assert MapSet.equal?(Ast.free_vars(program), expected) + assert Ast.pprint(program) == repr_expected + end + + test "free_vars-5" do + program = Ast.abs("f", Ast.abs("y", Ast.app(Ast.var("f"), Ast.var("x")))) + expected = MapSet.new(["x"]) + repr_expected = "(λ f . (λ y . f x))" + + assert MapSet.equal?(Ast.free_vars(program), expected) + assert Ast.pprint(program) == repr_expected + end +end diff --git a/lambda-calcul/elixir/mix.exs b/lambda-calcul/elixir/mix.exs new file mode 100644 index 0000000..df46a80 --- /dev/null +++ b/lambda-calcul/elixir/mix.exs @@ -0,0 +1,28 @@ +defmodule Workshop1.MixProject do + use Mix.Project + + def project do + [ + app: :workshop1, + version: "0.1.0", + elixir: "~> 1.17", + start_permanent: Mix.env() == :prod, + deps: deps() + ] + end + + # Run "mix help compile.app" to learn about applications. + def application do + [ + extra_applications: [:logger] + ] + end + + # Run "mix help deps" to learn about dependencies. + defp deps do + [ + # {:dep_from_hexpm, "~> 0.3.0"}, + # {:dep_from_git, git: "https://github.com/elixir-lang/my_dep.git", tag: "0.1.0"} + ] + end +end diff --git a/lambda-calcul/elixir/test_helper.exs b/lambda-calcul/elixir/test_helper.exs new file mode 100644 index 0000000..869559e --- /dev/null +++ b/lambda-calcul/elixir/test_helper.exs @@ -0,0 +1 @@ +ExUnit.start() diff --git a/lambda-calcul/elixir/workshop1.ex b/lambda-calcul/elixir/workshop1.ex new file mode 100644 index 0000000..caf85d7 --- /dev/null +++ b/lambda-calcul/elixir/workshop1.ex @@ -0,0 +1,5 @@ +defmodule Workshop1 do + def hello do + :world + end +end diff --git a/lambda-calcul/elixir/workshop1_test.exs b/lambda-calcul/elixir/workshop1_test.exs new file mode 100644 index 0000000..f0b4603 --- /dev/null +++ b/lambda-calcul/elixir/workshop1_test.exs @@ -0,0 +1,8 @@ +defmodule Workshop1Test do + use ExUnit.Case + doctest Workshop1 + + test "greets the world" do + assert Workshop1.hello() == :world + end +end diff --git a/lambda-calcul/java/lcgoji/.gitignore b/lambda-calcul/java/lcgoji/.gitignore new file mode 100644 index 0000000..af515ad --- /dev/null +++ b/lambda-calcul/java/lcgoji/.gitignore @@ -0,0 +1,2 @@ +.idea +target/ diff --git a/lambda-calcul/java/lcgoji/pom.xml b/lambda-calcul/java/lcgoji/pom.xml new file mode 100644 index 0000000..f4a4f30 --- /dev/null +++ b/lambda-calcul/java/lcgoji/pom.xml @@ -0,0 +1,65 @@ +<?xml version="1.0" encoding="UTF-8"?> +<project xmlns="http://maven.apache.org/POM/4.0.0" + xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <groupId>org.lambdanantes</groupId> + <artifactId>lcgoji</artifactId> + <version>1.0-SNAPSHOT</version> + + <properties> + <maven.compiler.source>21</maven.compiler.source> + <maven.compiler.target>21</maven.compiler.target> + <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> + <lombok.version>1.18.30</lombok.version> + <log4j.version>2.16.0</log4j.version> + + <jetty-util.version>9.4.31.v20200723</jetty-util.version> + <spark-core.version>2.9.3</spark-core.version> + <httpclient.version>4.3.1</httpclient.version> + + <junit.version>4.10</junit.version> + </properties> + + <dependencies> + <dependency> + <groupId>org.projectlombok</groupId> + <artifactId>lombok</artifactId> + <version>${lombok.version}</version> + <scope>provided</scope> + </dependency> + <dependency> + <groupId>org.apache.logging.log4j</groupId> + <artifactId>log4j-slf4j-impl</artifactId> + <version>${log4j.version}</version> + </dependency> + <dependency> + <groupId>org.apache.logging.log4j</groupId> + <artifactId>log4j-core</artifactId> + <version>${log4j.version}</version> + </dependency> + + <dependency> + <groupId>org.eclipse.jetty</groupId> + <artifactId>jetty-util</artifactId> + <version>${jetty-util.version}</version> + </dependency> + <dependency> + <groupId>com.sparkjava</groupId> + <artifactId>spark-core</artifactId> + <version>${spark-core.version}</version> + </dependency> + <dependency> + <groupId>org.apache.httpcomponents</groupId> + <artifactId>fluent-hc</artifactId> + <version>${httpclient.version}</version> + </dependency> + + <dependency> + <groupId>junit</groupId> + <artifactId>junit</artifactId> + <version>${junit.version}</version> + </dependency> + </dependencies> +</project>
\ No newline at end of file diff --git a/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/LCEvaluator.java b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/LCEvaluator.java new file mode 100644 index 0000000..b0fe69b --- /dev/null +++ b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/LCEvaluator.java @@ -0,0 +1,59 @@ +package org.lambdanantes.lcgoji; + +import org.lambdanantes.lcgoji.ast.Abs; +import org.lambdanantes.lcgoji.ast.App; +import org.lambdanantes.lcgoji.ast.Term; +import org.lambdanantes.lcgoji.ast.Var; + +import static org.lambdanantes.lcgoji.ast.Abs.λ; +import static org.lambdanantes.lcgoji.ast.App.apply; + +public class LCEvaluator { + + public static Term evaluate(Term term) { + switch (term) { + case Var var -> { + return var; + } + case Abs abs -> { + return abs; + } + case App app -> { + switch (app.left) { + case Abs abs -> { + return substitute(abs.body, abs.arg, app.right); + } + case App _app -> { + return app; + } + case Var _var -> { + return app; + } + } + } + } + } + + private static Term substitute(Term body, String arg, Term val) { + switch (body) { + case Var var -> { + if (var.name.equals(arg)) { + return val; + } else { + return body; + } + } + case App app -> { + return apply(substitute(app.left, arg, val), substitute(app.right, arg, val)); + } + case Abs abs -> { + if (abs.arg.equals(arg)) { + // Pas de substitution des variables redéfinies + return abs; + } else { + return λ(abs.arg, substitute(abs.body, arg, val)); + } + } + } + } +}
\ No newline at end of file diff --git a/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/Main.java b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/Main.java new file mode 100644 index 0000000..76cb839 --- /dev/null +++ b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/Main.java @@ -0,0 +1,49 @@ +package org.lambdanantes.lcgoji; + +import lombok.extern.slf4j.Slf4j; +import org.apache.http.client.fluent.Request; +import org.apache.http.client.fluent.Response; +import org.apache.http.entity.StringEntity; + +import static spark.Spark.*; + +@Slf4j +public class Main { + + public static final String TEAM_NAME = "LCGOJI"; + public static final int SELF_PORT = 8888; + public static final String SELF_URL = "http://127.0.0.1:" + SELF_PORT; + public static final String TESTER_URL = "http://127.0.0.1:8080"; + + public static void main(String[] args) throws Exception { + port(SELF_PORT); + + before((request, response) -> log.info("Requête entrante : " + request.requestMethod() + " " + request.pathInfo() + ", query params : " + request.queryString())); + + // API pour l'évaluation de λ-term + // Le body est une S-expression sous sa forme textuelle + post("/eval", (request, response) -> { + String body = request.body(); + log.info("Demande d'évaluation de l'expression : " + body); + + // TODO Parser, contruire l'AST, l'évaluer + String result = body; // Renvoie la s-expression à l'identique pour le moment + + log.info("Réponse envoyée : " + body); + + return result.getBytes(); + }); + + init(); + + // Enregistrement de notre API auprès du tester d'API + String jsonBody = "{\"url\":\"" + SELF_URL + "/eval\", \"name\": \"" + TEAM_NAME + "\"}"; + Response response = Request.Post(TESTER_URL + "/register") + .addHeader("Content-type", "application/json") + .body(new StringEntity(jsonBody)) + .execute(); + + log.info("Résultat de l'enregistrement : "+response.returnContent().toString()); + } + +}
\ No newline at end of file diff --git a/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/Abs.java b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/Abs.java new file mode 100644 index 0000000..9d1c146 --- /dev/null +++ b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/Abs.java @@ -0,0 +1,26 @@ +package org.lambdanantes.lcgoji.ast; + +import lombok.AccessLevel; +import lombok.AllArgsConstructor; +import lombok.EqualsAndHashCode; + +import static org.lambdanantes.lcgoji.ast.Var.var; + +@AllArgsConstructor(access = AccessLevel.PROTECTED) +@EqualsAndHashCode +public final class Abs implements Term { + + public static final Abs IDENTITY = λ("x", var("x")); + + public String arg; + public Term body; + + public static Abs λ(String arg, Term body) { + return new Abs(arg, body); + } + + @Override + public String toString() { + return "λ" + arg + "." + body; + } +}
\ No newline at end of file diff --git a/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/App.java b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/App.java new file mode 100644 index 0000000..2f3e04d --- /dev/null +++ b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/App.java @@ -0,0 +1,22 @@ +package org.lambdanantes.lcgoji.ast; + +import lombok.AccessLevel; +import lombok.AllArgsConstructor; +import lombok.EqualsAndHashCode; + +@AllArgsConstructor(access = AccessLevel.PROTECTED) +@EqualsAndHashCode +public final class App implements Term { + + public Term left; + public Term right; + + public static App apply(Term left, Term right) { + return new App(left, right); + } + + @Override + public String toString() { + return "(" + left + ") " + right; + } +}
\ No newline at end of file diff --git a/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/Term.java b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/Term.java new file mode 100644 index 0000000..2dcc9fe --- /dev/null +++ b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/Term.java @@ -0,0 +1,5 @@ +package org.lambdanantes.lcgoji.ast; + +public sealed interface Term permits Var, Abs, App { + +}
\ No newline at end of file diff --git a/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/Var.java b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/Var.java new file mode 100644 index 0000000..ed710b6 --- /dev/null +++ b/lambda-calcul/java/lcgoji/src/main/java/org/lambdanantes/lcgoji/ast/Var.java @@ -0,0 +1,21 @@ +package org.lambdanantes.lcgoji.ast; + +import lombok.AccessLevel; +import lombok.AllArgsConstructor; +import lombok.EqualsAndHashCode; + +@AllArgsConstructor(access = AccessLevel.PROTECTED) +@EqualsAndHashCode +public final class Var implements Term{ + + public String name; + + public static Var var(String name) { + return new Var(name); + } + + @Override + public String toString() { + return name; + } +}
\ No newline at end of file diff --git a/lambda-calcul/java/lcgoji/src/main/resources/log4j2.xml b/lambda-calcul/java/lcgoji/src/main/resources/log4j2.xml new file mode 100644 index 0000000..f938085 --- /dev/null +++ b/lambda-calcul/java/lcgoji/src/main/resources/log4j2.xml @@ -0,0 +1,17 @@ +<?xml version="1.0" encoding="UTF-8"?> +<configuration monitorInterval="60"> + <appenders> + <console name="console" target="SYSTEM_OUT"> + <patternLayout pattern="%d{HH:mm:ss} [%t] %-5level %logger{36} - %msg%n"/> + </console> + </appenders> + + <loggers> + <root level="debug"> + <appender-ref ref="console"/> + </root> + <logger name="org.eclipse.jetty" level="warn"/> + <logger name="spark" level="info"/> + </loggers> +</configuration> + diff --git a/lambda-calcul/java/lcgoji/src/test/java/org/lambdanantes/lcgoji/LCEvaluatorTest.java b/lambda-calcul/java/lcgoji/src/test/java/org/lambdanantes/lcgoji/LCEvaluatorTest.java new file mode 100644 index 0000000..ec2f027 --- /dev/null +++ b/lambda-calcul/java/lcgoji/src/test/java/org/lambdanantes/lcgoji/LCEvaluatorTest.java @@ -0,0 +1,74 @@ +package org.lambdanantes.lcgoji; + +import org.junit.Test; +import org.lambdanantes.lcgoji.ast.Term; +import org.lambdanantes.lcgoji.ast.Var; + +import static org.hamcrest.CoreMatchers.is; +import static org.junit.Assert.assertThat; +import static org.lambdanantes.lcgoji.LCEvaluator.evaluate; +import static org.lambdanantes.lcgoji.ast.Abs.IDENTITY; +import static org.lambdanantes.lcgoji.ast.Abs.λ; +import static org.lambdanantes.lcgoji.ast.App.apply; +import static org.lambdanantes.lcgoji.ast.Var.var; + +public class LCEvaluatorTest { + + Var x = var("x"); + Var y = var("y"); + Var z = var("z"); + + @Test + public void l_evaluation_d_une_variable_rend_la_meme_variable() { + // evaluate(x) == x + assertEvalTo(x, x); + } + + @Test + public void l_evaluation_d_une_abstraction_rend_la_meme_abstraction() { + // evaluate(λx.x) == λx.x + assertEvalTo(IDENTITY, IDENTITY); + } + + @Test + public void l_evaluation_de_l_application_de_deux_vars_rend_la_meme_application() { + // evaluate(x y) == x y + assertEvalTo(apply(x, y), apply(x, y)); + } + + @Test + public void l_evaluation_de_l_application_de_l_identite_sur_un_argument_rend_l_argument() { + // evaluate((λx.x) y) == y + assertEvalTo(apply(IDENTITY, y), y); + } + + @Test + public void l_evaluation_de_l_application_d_une_abstraction_substitue_son_argument() { + // evaluate((λx.x x) y ) == y y + assertEvalTo(apply(λ("x", apply(x, x)), y), apply(y, y)); + } + + @Test + public void l_evaluation_de_l_application_d_une_abstraction_d_abstraction_substitue_recursivement_son_argument() { + // evaluate((λx.λy.x) z) == λy.z + assertEvalTo(apply(λ("x", λ("y", x)), z), λ("y", z)); + } + + @Test + public void l_evaluation_de_l_application_d_une_abstraction_ne_substitue_pas_ses_variables_libres() { + // evaluate((λx.y) z) == y + assertEvalTo(apply(λ("x", y), z), y); + } + + @Test + public void l_evaluation_de_l_application_d_une_abstraction_d_abstraction_ne_substitue_pas_les_variables_redefinies() { + // evaluate((λx.λx.x) z) == λx.x + assertEvalTo(apply(λ("x", λ("x", x)), z), λ("x", x)); + } + + ///// + + private static void assertEvalTo(Term termToEvaluate, Term result) { + assertThat(evaluate(termToEvaluate), is(result)); + } +} diff --git a/lambda-calcul/java/lcgoji/src/test/java/org/lambdanantes/lcgoji/ast/TermTest.java b/lambda-calcul/java/lcgoji/src/test/java/org/lambdanantes/lcgoji/ast/TermTest.java new file mode 100644 index 0000000..f11ca77 --- /dev/null +++ b/lambda-calcul/java/lcgoji/src/test/java/org/lambdanantes/lcgoji/ast/TermTest.java @@ -0,0 +1,38 @@ +package org.lambdanantes.lcgoji.ast; + +import org.junit.Test; + +import static org.hamcrest.CoreMatchers.is; +import static org.hamcrest.CoreMatchers.not; +import static org.junit.Assert.assertThat; +import static org.lambdanantes.lcgoji.ast.Abs.λ; +import static org.lambdanantes.lcgoji.ast.App.apply; +import static org.lambdanantes.lcgoji.ast.Var.var; + +public class TermTest { + + @Test + public void les_equals_des_termes_sont_corrects() { + // x == x + assertThat(var("x"), is(var("x"))); + // x != y + assertThat(var("x"), is(not(var("y")))); + // λx.x == λx.x + assertThat(λ("x", var("x")), is(λ("x", var("x")))); + // λx.x != λy.x + assertThat(λ("x", var("x")), is(not(λ("y", var("x"))))); + // x y == x y + assertThat(apply(var("x"), var("y")), is(apply(var("x"), var("y")))); + // x x != x y + assertThat(apply(var("x"), var("x")), is(not(apply(var("x"), var("y"))))); + } + + @Test + public void les_toString_des_termes_utilisent_la_notation_consacree() { + assertThat(var("x").toString(), is("x")); + assertThat(λ("x", var("x")).toString(), is("λx.x")); + assertThat(apply(λ("x", var("x")), var("x")).toString(), is("(λx.x) x")); + assertThat(apply(λ("x", λ("x", var("x"))), var("y")).toString(), is("(λx.λx.x) y")); + } + +}
\ No newline at end of file diff --git a/lambda-calcul/papers/sestoft-lamreduce.pdf b/lambda-calcul/papers/sestoft-lamreduce.pdf Binary files differnew file mode 100644 index 0000000..2013f1d --- /dev/null +++ b/lambda-calcul/papers/sestoft-lamreduce.pdf diff --git a/lambda-calcul/rust/.gitignore b/lambda-calcul/rust/.gitignore new file mode 100644 index 0000000..2f7896d --- /dev/null +++ b/lambda-calcul/rust/.gitignore @@ -0,0 +1 @@ +target/ diff --git a/lambda-calcul/rust/Cargo.lock b/lambda-calcul/rust/Cargo.lock new file mode 100644 index 0000000..bdb2dd9 --- /dev/null +++ b/lambda-calcul/rust/Cargo.lock @@ -0,0 +1,2753 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "actix-codec" +version = "0.5.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5f7b0a21988c1bf877cf4759ef5ddaac04c1c9fe808c9142ecb78ba97d97a28a" +dependencies = [ + "bitflags", + "bytes", + "futures-core", + "futures-sink", + "memchr", + "pin-project-lite", + "tokio", + "tokio-util", + "tracing", +] + +[[package]] +name = "actix-http" +version = "3.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d48f96fc3003717aeb9856ca3d02a8c7de502667ad76eeacd830b48d2e91fac4" +dependencies = [ + "actix-codec", + "actix-rt", + "actix-service", + "actix-utils", + "ahash", + "base64", + "bitflags", + "brotli", + "bytes", + "bytestring", + "derive_more", + "encoding_rs", + "flate2", + "futures-core", + "h2 0.3.26", + "http 0.2.12", + "httparse", + "httpdate", + "itoa", + "language-tags", + "local-channel", + "mime", + "percent-encoding", + "pin-project-lite", + "rand", + "sha1", + "smallvec", + "tokio", + "tokio-util", + "tracing", + "zstd", +] + +[[package]] +name = "actix-macros" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e01ed3140b2f8d422c68afa1ed2e85d996ea619c988ac834d255db32138655cb" +dependencies = [ + "quote", + "syn", +] + +[[package]] +name = "actix-router" +version = "0.5.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "13d324164c51f63867b57e73ba5936ea151b8a41a1d23d1031eeb9f70d0236f8" +dependencies = [ + "bytestring", + "cfg-if", + "http 0.2.12", + "regex", + "regex-lite", + "serde", + "tracing", +] + +[[package]] +name = "actix-rt" +version = "2.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "24eda4e2a6e042aa4e55ac438a2ae052d3b5da0ecf83d7411e1a368946925208" +dependencies = [ + "futures-core", + "tokio", +] + +[[package]] +name = "actix-server" +version = "2.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7ca2549781d8dd6d75c40cf6b6051260a2cc2f3c62343d761a969a0640646894" +dependencies = [ + "actix-rt", + "actix-service", + "actix-utils", + "futures-core", + "futures-util", + "mio", + "socket2", + "tokio", + "tracing", +] + +[[package]] +name = "actix-service" +version = "2.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3b894941f818cfdc7ccc4b9e60fa7e53b5042a2e8567270f9147d5591893373a" +dependencies = [ + "futures-core", + "paste", + "pin-project-lite", +] + +[[package]] +name = "actix-utils" +version = "3.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "88a1dcdff1466e3c2488e1cb5c36a71822750ad43839937f85d2f4d9f8b705d8" +dependencies = [ + "local-waker", + "pin-project-lite", +] + +[[package]] +name = "actix-web" +version = "4.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9180d76e5cc7ccbc4d60a506f2c727730b154010262df5b910eb17dbe4b8cb38" +dependencies = [ + "actix-codec", + "actix-http", + "actix-macros", + "actix-router", + "actix-rt", + "actix-server", + "actix-service", + "actix-utils", + "actix-web-codegen", + "ahash", + "bytes", + "bytestring", + "cfg-if", + "cookie", + "derive_more", + "encoding_rs", + "futures-core", + "futures-util", + "impl-more", + "itoa", + "language-tags", + "log", + "mime", + "once_cell", + "pin-project-lite", + "regex", + "regex-lite", + "serde", + "serde_json", + "serde_urlencoded", + "smallvec", + "socket2", + "time", + "url", +] + +[[package]] +name = "actix-web-codegen" +version = "4.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f591380e2e68490b5dfaf1dd1aa0ebe78d84ba7067078512b4ea6e4492d622b8" +dependencies = [ + "actix-router", + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "addr2line" +version = "0.24.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f5fb1d8e4442bd405fdfd1dacb42792696b0cf9cb15882e5d097b742a676d375" +dependencies = [ + "gimli", +] + +[[package]] +name = "adler2" +version = "2.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "512761e0bb2578dd7380c6baaa0f4ce03e84f95e960231d1dec8bf4d7d6e2627" + +[[package]] +name = "ahash" +version = "0.8.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e89da841a80418a9b391ebaea17f5c112ffaaa96f621d2c285b5174da76b9011" +dependencies = [ + "cfg-if", + "getrandom", + "once_cell", + "version_check", + "zerocopy", +] + +[[package]] +name = "aho-corasick" +version = "1.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8e60d3430d3a69478ad0993f19238d2df97c507009a52b3c10addcd7f6bcb916" +dependencies = [ + "memchr", +] + +[[package]] +name = "alloc-no-stdlib" +version = "2.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cc7bb162ec39d46ab1ca8c77bf72e890535becd1751bb45f64c597edb4c8c6b3" + +[[package]] +name = "alloc-stdlib" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "94fb8275041c72129eb51b7d0322c29b8387a0386127718b096429201a5d6ece" +dependencies = [ + "alloc-no-stdlib", +] + +[[package]] +name = "android-tzdata" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e999941b234f3131b00bc13c22d06e8c5ff726d1b6318ac7eb276997bbb4fef0" + +[[package]] +name = "android_system_properties" +version = "0.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "819e7219dbd41043ac279b19830f2efc897156490d7fd6ea916720117ee66311" +dependencies = [ + "libc", +] + +[[package]] +name = "anstream" +version = "0.6.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "64e15c1ab1f89faffbf04a634d5e1962e9074f2741eef6d97f3c4e322426d526" +dependencies = [ + "anstyle", + "anstyle-parse", + "anstyle-query", + "anstyle-wincon", + "colorchoice", + "is_terminal_polyfill", + "utf8parse", +] + +[[package]] +name = "anstyle" +version = "1.0.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1bec1de6f59aedf83baf9ff929c98f2ad654b97c9510f4e70cf6f661d49fd5b1" + +[[package]] +name = "anstyle-parse" +version = "0.2.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "eb47de1e80c2b463c735db5b217a0ddc39d612e7ac9e2e96a5aed1f57616c1cb" +dependencies = [ + "utf8parse", +] + +[[package]] +name = "anstyle-query" +version = "1.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6d36fc52c7f6c869915e99412912f22093507da8d9e942ceaf66fe4b7c14422a" +dependencies = [ + "windows-sys 0.52.0", +] + +[[package]] +name = "anstyle-wincon" +version = "3.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5bf74e1b6e971609db8ca7a9ce79fd5768ab6ae46441c572e46cf596f59e57f8" +dependencies = [ + "anstyle", + "windows-sys 0.52.0", +] + +[[package]] +name = "async-channel" +version = "1.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "81953c529336010edd6d8e358f886d9581267795c61b19475b71314bffa46d35" +dependencies = [ + "concurrent-queue", + "event-listener 2.5.3", + "futures-core", +] + +[[package]] +name = "async-channel" +version = "2.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "89b47800b0be77592da0afd425cc03468052844aff33b84e33cc696f64e77b6a" +dependencies = [ + "concurrent-queue", + "event-listener-strategy", + "futures-core", + "pin-project-lite", +] + +[[package]] +name = "async-executor" +version = "1.13.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "30ca9a001c1e8ba5149f91a74362376cc6bc5b919d92d988668657bd570bdcec" +dependencies = [ + "async-task", + "concurrent-queue", + "fastrand", + "futures-lite", + "slab", +] + +[[package]] +name = "async-global-executor" +version = "2.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "05b1b633a2115cd122d73b955eadd9916c18c8f510ec9cd1686404c60ad1c29c" +dependencies = [ + "async-channel 2.3.1", + "async-executor", + "async-io", + "async-lock", + "blocking", + "futures-lite", + "once_cell", +] + +[[package]] +name = "async-io" +version = "2.3.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "444b0228950ee6501b3568d3c93bf1176a1fdbc3b758dcd9475046d30f4dc7e8" +dependencies = [ + "async-lock", + "cfg-if", + "concurrent-queue", + "futures-io", + "futures-lite", + "parking", + "polling", + "rustix", + "slab", + "tracing", + "windows-sys 0.59.0", +] + +[[package]] +name = "async-lock" +version = "3.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ff6e472cdea888a4bd64f342f09b3f50e1886d32afe8df3d663c01140b811b18" +dependencies = [ + "event-listener 5.3.1", + "event-listener-strategy", + "pin-project-lite", +] + +[[package]] +name = "async-std" +version = "1.13.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c634475f29802fde2b8f0b505b1bd00dfe4df7d4a000f0b36f7671197d5c3615" +dependencies = [ + "async-channel 1.9.0", + "async-global-executor", + "async-io", + "async-lock", + "crossbeam-utils", + "futures-channel", + "futures-core", + "futures-io", + "futures-lite", + "gloo-timers", + "kv-log-macro", + "log", + "memchr", + "once_cell", + "pin-project-lite", + "pin-utils", + "slab", + "wasm-bindgen-futures", +] + +[[package]] +name = "async-task" +version = "4.7.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8b75356056920673b02621b35afd0f7dda9306d03c79a30f5c56c44cf256e3de" + +[[package]] +name = "atomic-waker" +version = "1.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1505bd5d3d116872e7271a6d4e16d81d0c8570876c8de68093a09ac269d8aac0" + +[[package]] +name = "atty" +version = "0.2.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d9b39be18770d11421cdb1b9947a45dd3f37e93092cbf377614828a319d5fee8" +dependencies = [ + "hermit-abi 0.1.19", + "libc", + "winapi", +] + +[[package]] +name = "autocfg" +version = "1.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0c4b4d0bd25bd0b74681c0ad21497610ce1b7c91b1022cd21c80c6fbdd9476b0" + +[[package]] +name = "backtrace" +version = "0.3.74" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8d82cb332cdfaed17ae235a638438ac4d4839913cc2af585c3c6746e8f8bee1a" +dependencies = [ + "addr2line", + "cfg-if", + "libc", + "miniz_oxide", + "object", + "rustc-demangle", + "windows-targets", +] + +[[package]] +name = "base64" +version = "0.22.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "72b3254f16251a8381aa12e40e3c4d2f0199f8c6508fbecb9d91f575e0fbb8c6" + +[[package]] +name = "bit-set" +version = "0.5.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0700ddab506f33b20a03b13996eccd309a48e5ff77d0d95926aa0210fb4e95f1" +dependencies = [ + "bit-vec", +] + +[[package]] +name = "bit-vec" +version = "0.6.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "349f9b6a179ed607305526ca489b34ad0a41aed5f7980fa90eb03160b69598fb" + +[[package]] +name = "bitflags" +version = "2.6.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b048fb63fd8b5923fc5aa7b340d8e156aec7ec02f0c78fa8a6ddc2613f6f71de" + +[[package]] +name = "block-buffer" +version = "0.10.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3078c7629b62d3f0439517fa394996acacc5cbc91c5a20d8c658e77abd503a71" +dependencies = [ + "generic-array", +] + +[[package]] +name = "blocking" +version = "1.6.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "703f41c54fc768e63e091340b424302bb1c29ef4aa0c7f10fe849dfb114d29ea" +dependencies = [ + "async-channel 2.3.1", + "async-task", + "futures-io", + "futures-lite", + "piper", +] + +[[package]] +name = "brotli" +version = "6.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "74f7971dbd9326d58187408ab83117d8ac1bb9c17b085fdacd1cf2f598719b6b" +dependencies = [ + "alloc-no-stdlib", + "alloc-stdlib", + "brotli-decompressor", +] + +[[package]] +name = "brotli-decompressor" +version = "4.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9a45bd2e4095a8b518033b128020dd4a55aab1c0a381ba4404a472630f4bc362" +dependencies = [ + "alloc-no-stdlib", + "alloc-stdlib", +] + +[[package]] +name = "bumpalo" +version = "3.16.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "79296716171880943b8470b5f8d03aa55eb2e645a4874bdbb28adb49162e012c" + +[[package]] +name = "byteorder" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1fd0f2584146f6f2ef48085050886acf353beff7305ebd1ae69500e27c67f64b" + +[[package]] +name = "bytes" +version = "1.7.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "428d9aa8fbc0670b7b8d6030a7fadd0f86151cae55e4dbbece15f3780a3dfaf3" + +[[package]] +name = "bytestring" +version = "1.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "74d80203ea6b29df88012294f62733de21cfeab47f17b41af3a38bc30a03ee72" +dependencies = [ + "bytes", +] + +[[package]] +name = "cc" +version = "1.1.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3bbb537bb4a30b90362caddba8f360c0a56bc13d3a5570028e7197204cb54a17" +dependencies = [ + "jobserver", + "libc", + "shlex", +] + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "chrono" +version = "0.4.38" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a21f936df1771bf62b77f047b726c4625ff2e8aa607c01ec06e5a05bd8463401" +dependencies = [ + "android-tzdata", + "iana-time-zone", + "js-sys", + "num-traits", + "serde", + "wasm-bindgen", + "windows-targets", +] + +[[package]] +name = "clap" +version = "4.5.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7be5744db7978a28d9df86a214130d106a89ce49644cbc4e3f0c22c3fba30615" +dependencies = [ + "clap_builder", + "clap_derive", +] + +[[package]] +name = "clap_builder" +version = "4.5.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a5fbc17d3ef8278f55b282b2a2e75ae6f6c7d4bb70ed3d0382375104bfafdb4b" +dependencies = [ + "anstream", + "anstyle", + "clap_lex", + "strsim", +] + +[[package]] +name = "clap_derive" +version = "4.5.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4ac6a0c7b1a9e9a5186361f67dfa1b88213572f427fb9ab038efb2bd8c582dab" +dependencies = [ + "heck", + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "clap_lex" +version = "0.7.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1462739cb27611015575c0c11df5df7601141071f07518d56fcc1be504cbec97" + +[[package]] +name = "colorchoice" +version = "1.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d3fd119d74b830634cea2a0f58bbd0d54540518a14397557951e79340abc28c0" + +[[package]] +name = "concurrent-queue" +version = "2.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4ca0197aee26d1ae37445ee532fefce43251d24cc7c166799f4d46817f1d3973" +dependencies = [ + "crossbeam-utils", +] + +[[package]] +name = "convert_case" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6245d59a3e82a7fc217c5828a6692dbc6dfb63a0c8c90495621f7b9d79704a0e" + +[[package]] +name = "cookie" +version = "0.16.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e859cd57d0710d9e06c381b550c06e76992472a8c6d527aecd2fc673dcc231fb" +dependencies = [ + "percent-encoding", + "time", + "version_check", +] + +[[package]] +name = "core-foundation" +version = "0.9.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "91e195e091a93c46f7102ec7818a2aa394e1e1771c3ab4825963fa03e45afb8f" +dependencies = [ + "core-foundation-sys", + "libc", +] + +[[package]] +name = "core-foundation-sys" +version = "0.8.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "773648b94d0e5d620f64f280777445740e61fe701025087ec8b57f45c791888b" + +[[package]] +name = "cpufeatures" +version = "0.2.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "608697df725056feaccfa42cffdaeeec3fccc4ffc38358ecd19b243e716a78e0" +dependencies = [ + "libc", +] + +[[package]] +name = "crc32fast" +version = "1.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a97769d94ddab943e4510d138150169a2758b5ef3eb191a9ee688de3e23ef7b3" +dependencies = [ + "cfg-if", +] + +[[package]] +name = "crossbeam-utils" +version = "0.8.20" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "22ec99545bb0ed0ea7bb9b8e1e9122ea386ff8a48c0922e43f36d45ab09e0e80" + +[[package]] +name = "crypto-common" +version = "0.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1bfb12502f3fc46cca1bb51ac28df9d618d813cdc3d2f25b9fe775a34af26bb3" +dependencies = [ + "generic-array", + "typenum", +] + +[[package]] +name = "deranged" +version = "0.3.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b42b6fa04a440b495c8b04d0e71b707c585f83cb9cb28cf8cd0d976c315e31b4" +dependencies = [ + "powerfmt", +] + +[[package]] +name = "derive_more" +version = "0.99.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5f33878137e4dafd7fa914ad4e259e18a4e8e532b9617a2d0150262bf53abfce" +dependencies = [ + "convert_case", + "proc-macro2", + "quote", + "rustc_version", + "syn", +] + +[[package]] +name = "digest" +version = "0.10.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9ed9a281f7bc9b7576e61468ba615a66a5c8cfdff42420a70aa82701a3b1e292" +dependencies = [ + "block-buffer", + "crypto-common", +] + +[[package]] +name = "encoding_rs" +version = "0.8.34" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b45de904aa0b010bce2ab45264d0631681847fa7b6f2eaa7dab7619943bc4f59" +dependencies = [ + "cfg-if", +] + +[[package]] +name = "env_logger" +version = "0.8.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a19187fea3ac7e84da7dacf48de0c45d63c6a76f9490dae389aead16c243fce3" +dependencies = [ + "atty", + "humantime", + "log", + "regex", + "termcolor", +] + +[[package]] +name = "equivalent" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5" + +[[package]] +name = "errno" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "534c5cf6194dfab3db3242765c03bbe257cf92f22b38f6bc0c58d59108a820ba" +dependencies = [ + "libc", + "windows-sys 0.52.0", +] + +[[package]] +name = "event-listener" +version = "2.5.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0206175f82b8d6bf6652ff7d71a1e27fd2e4efde587fd368662814d6ec1d9ce0" + +[[package]] +name = "event-listener" +version = "5.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6032be9bd27023a771701cc49f9f053c751055f71efb2e0ae5c15809093675ba" +dependencies = [ + "concurrent-queue", + "parking", + "pin-project-lite", +] + +[[package]] +name = "event-listener-strategy" +version = "0.5.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0f214dc438f977e6d4e3500aaa277f5ad94ca83fbbd9b1a15713ce2344ccc5a1" +dependencies = [ + "event-listener 5.3.1", + "pin-project-lite", +] + +[[package]] +name = "fastrand" +version = "2.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e8c02a5121d4ea3eb16a80748c74f5549a5665e4c21333c6098f283870fbdea6" + +[[package]] +name = "flate2" +version = "1.0.34" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a1b589b4dc103969ad3cf85c950899926ec64300a1a46d76c03a6072957036f0" +dependencies = [ + "crc32fast", + "miniz_oxide", +] + +[[package]] +name = "fnv" +version = "1.0.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1" + +[[package]] +name = "foreign-types" +version = "0.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f6f339eb8adc052cd2ca78910fda869aefa38d22d5cb648e6485e4d3fc06f3b1" +dependencies = [ + "foreign-types-shared", +] + +[[package]] +name = "foreign-types-shared" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "00b0228411908ca8685dba7fc2cdd70ec9990a6e753e89b6ac91a84c40fbaf4b" + +[[package]] +name = "form_urlencoded" +version = "1.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e13624c2627564efccf4934284bdd98cbaa14e79b0b5a141218e507b3a823456" +dependencies = [ + "percent-encoding", +] + +[[package]] +name = "futures" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "645c6916888f6cb6350d2550b80fb63e734897a8498abe35cfb732b6487804b0" +dependencies = [ + "futures-channel", + "futures-core", + "futures-executor", + "futures-io", + "futures-sink", + "futures-task", + "futures-util", +] + +[[package]] +name = "futures-channel" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "eac8f7d7865dcb88bd4373ab671c8cf4508703796caa2b1985a9ca867b3fcb78" +dependencies = [ + "futures-core", + "futures-sink", +] + +[[package]] +name = "futures-core" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dfc6580bb841c5a68e9ef15c77ccc837b40a7504914d52e47b8b0e9bbda25a1d" + +[[package]] +name = "futures-executor" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a576fc72ae164fca6b9db127eaa9a9dda0d61316034f33a0a0d4eda41f02b01d" +dependencies = [ + "futures-core", + "futures-task", + "futures-util", +] + +[[package]] +name = "futures-io" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a44623e20b9681a318efdd71c299b6b222ed6f231972bfe2f224ebad6311f0c1" + +[[package]] +name = "futures-lite" +version = "2.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "52527eb5074e35e9339c6b4e8d12600c7128b68fb25dcb9fa9dec18f7c25f3a5" +dependencies = [ + "fastrand", + "futures-core", + "futures-io", + "parking", + "pin-project-lite", +] + +[[package]] +name = "futures-macro" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "87750cf4b7a4c0625b1529e4c543c2182106e4dedc60a2a6455e00d212c489ac" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "futures-sink" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9fb8e00e87438d937621c1c6269e53f536c14d3fbd6a042bb24879e57d474fb5" + +[[package]] +name = "futures-task" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38d84fa142264698cdce1a9f9172cf383a0c82de1bddcf3092901442c4097004" + +[[package]] +name = "futures-util" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3d6401deb83407ab3da39eba7e33987a73c3df0c82b4bb5813ee871c19c41d48" +dependencies = [ + "futures-channel", + "futures-core", + "futures-io", + "futures-macro", + "futures-sink", + "futures-task", + "memchr", + "pin-project-lite", + "pin-utils", + "slab", +] + +[[package]] +name = "generic-array" +version = "0.14.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "85649ca51fd72272d7821adaf274ad91c288277713d9c18820d8499a7ff69e9a" +dependencies = [ + "typenum", + "version_check", +] + +[[package]] +name = "getrandom" +version = "0.2.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c4567c8db10ae91089c99af84c68c38da3ec2f087c3f82960bcdbf3656b6f4d7" +dependencies = [ + "cfg-if", + "libc", + "wasi", +] + +[[package]] +name = "gimli" +version = "0.31.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "32085ea23f3234fc7846555e85283ba4de91e21016dc0455a16286d87a292d64" + +[[package]] +name = "gloo-timers" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bbb143cf96099802033e0d4f4963b19fd2e0b728bcf076cd9cf7f6634f092994" +dependencies = [ + "futures-channel", + "futures-core", + "js-sys", + "wasm-bindgen", +] + +[[package]] +name = "h2" +version = "0.3.26" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "81fe527a889e1532da5c525686d96d4c2e74cdd345badf8dfef9f6b39dd5f5e8" +dependencies = [ + "bytes", + "fnv", + "futures-core", + "futures-sink", + "futures-util", + "http 0.2.12", + "indexmap", + "slab", + "tokio", + "tokio-util", + "tracing", +] + +[[package]] +name = "h2" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "524e8ac6999421f49a846c2d4411f337e53497d8ec55d67753beffa43c5d9205" +dependencies = [ + "atomic-waker", + "bytes", + "fnv", + "futures-core", + "futures-sink", + "http 1.1.0", + "indexmap", + "slab", + "tokio", + "tokio-util", + "tracing", +] + +[[package]] +name = "handlebars" +version = "5.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d08485b96a0e6393e9e4d1b8d48cf74ad6c063cd905eb33f42c1ce3f0377539b" +dependencies = [ + "log", + "pest", + "pest_derive", + "serde", + "serde_json", + "thiserror", + "walkdir", +] + +[[package]] +name = "hashbrown" +version = "0.15.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1e087f84d4f86bf4b218b927129862374b72199ae7d8657835f1e89000eea4fb" + +[[package]] +name = "heck" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2304e00983f87ffb38b55b444b5e3b60a884b5d30c0fca7d82fe33449bbe55ea" + +[[package]] +name = "hermit-abi" +version = "0.1.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "62b467343b94ba476dcb2500d242dadbb39557df889310ac77c5d99100aaac33" +dependencies = [ + "libc", +] + +[[package]] +name = "hermit-abi" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d231dfb89cfffdbc30e7fc41579ed6066ad03abda9e567ccafae602b97ec5024" + +[[package]] +name = "hermit-abi" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fbf6a919d6cf397374f7dfeeea91d974c7c0a7221d0d0f4f20d859d329e53fcc" + +[[package]] +name = "http" +version = "0.2.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "601cbb57e577e2f5ef5be8e7b83f0f63994f25aa94d673e54a92d5c516d101f1" +dependencies = [ + "bytes", + "fnv", + "itoa", +] + +[[package]] +name = "http" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "21b9ddb458710bc376481b842f5da65cdf31522de232c1ca8146abce2a358258" +dependencies = [ + "bytes", + "fnv", + "itoa", +] + +[[package]] +name = "http-body" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1efedce1fb8e6913f23e0c92de8e62cd5b772a67e7b3946df930a62566c93184" +dependencies = [ + "bytes", + "http 1.1.0", +] + +[[package]] +name = "http-body-util" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "793429d76616a256bcb62c2a2ec2bed781c8307e797e2598c50010f2bee2544f" +dependencies = [ + "bytes", + "futures-util", + "http 1.1.0", + "http-body", + "pin-project-lite", +] + +[[package]] +name = "httparse" +version = "1.9.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7d71d3574edd2771538b901e6549113b4006ece66150fb69c0fb6d9a2adae946" + +[[package]] +name = "httpdate" +version = "1.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "df3b46402a9d5adb4c86a0cf463f42e19994e3ee891101b1841f30a545cb49a9" + +[[package]] +name = "humantime" +version = "2.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9a3a5bfb195931eeb336b2a7b4d761daec841b97f947d34394601737a7bba5e4" + +[[package]] +name = "hyper" +version = "1.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "50dfd22e0e76d0f662d429a5f80fcaf3855009297eab6a0a9f8543834744ba05" +dependencies = [ + "bytes", + "futures-channel", + "futures-util", + "h2 0.4.6", + "http 1.1.0", + "http-body", + "httparse", + "itoa", + "pin-project-lite", + "smallvec", + "tokio", + "want", +] + +[[package]] +name = "hyper-rustls" +version = "0.27.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "08afdbb5c31130e3034af566421053ab03787c640246a446327f550d11bcb333" +dependencies = [ + "futures-util", + "http 1.1.0", + "hyper", + "hyper-util", + "rustls", + "rustls-pki-types", + "tokio", + "tokio-rustls", + "tower-service", +] + +[[package]] +name = "hyper-tls" +version = "0.6.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "70206fc6890eaca9fde8a0bf71caa2ddfc9fe045ac9e5c70df101a7dbde866e0" +dependencies = [ + "bytes", + "http-body-util", + "hyper", + "hyper-util", + "native-tls", + "tokio", + "tokio-native-tls", + "tower-service", +] + +[[package]] +name = "hyper-util" +version = "0.1.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "41296eb09f183ac68eec06e03cdbea2e759633d4067b2f6552fc2e009bcad08b" +dependencies = [ + "bytes", + "futures-channel", + "futures-util", + "http 1.1.0", + "http-body", + "hyper", + "pin-project-lite", + "socket2", + "tokio", + "tower-service", + "tracing", +] + +[[package]] +name = "iana-time-zone" +version = "0.1.61" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "235e081f3925a06703c2d0117ea8b91f042756fd6e7a6e5d901e8ca1a996b220" +dependencies = [ + "android_system_properties", + "core-foundation-sys", + "iana-time-zone-haiku", + "js-sys", + "wasm-bindgen", + "windows-core", +] + +[[package]] +name = "iana-time-zone-haiku" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f31827a206f56af32e590ba56d5d2d085f558508192593743f16b2306495269f" +dependencies = [ + "cc", +] + +[[package]] +name = "idna" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "634d9b1461af396cad843f47fdba5597a4f9e6ddd4bfb6ff5d85028c25cb12f6" +dependencies = [ + "unicode-bidi", + "unicode-normalization", +] + +[[package]] +name = "impl-more" +version = "0.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "206ca75c9c03ba3d4ace2460e57b189f39f43de612c2f85836e65c929701bb2d" + +[[package]] +name = "indexmap" +version = "2.6.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "707907fe3c25f5424cce2cb7e1cbcafee6bdbe735ca90ef77c29e84591e5b9da" +dependencies = [ + "equivalent", + "hashbrown", +] + +[[package]] +name = "ipnet" +version = "2.10.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ddc24109865250148c2e0f3d25d4f0f479571723792d3802153c60922a4fb708" + +[[package]] +name = "is_terminal_polyfill" +version = "1.70.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7943c866cc5cd64cbc25b2e01621d07fa8eb2a1a23160ee81ce38704e97b8ecf" + +[[package]] +name = "itoa" +version = "1.0.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "49f1f14873335454500d59611f1cf4a4b0f786f9ac11f4312a78e4cf2566695b" + +[[package]] +name = "jobserver" +version = "0.1.32" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "48d1dbcbbeb6a7fec7e059840aa538bd62aaccf972c7346c4d9d2059312853d0" +dependencies = [ + "libc", +] + +[[package]] +name = "js-sys" +version = "0.3.70" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1868808506b929d7b0cfa8f75951347aa71bb21144b7791bae35d9bccfcfe37a" +dependencies = [ + "wasm-bindgen", +] + +[[package]] +name = "kv-log-macro" +version = "1.0.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0de8b303297635ad57c9f5059fd9cee7a47f8e8daa09df0fcd07dd39fb22977f" +dependencies = [ + "log", +] + +[[package]] +name = "language-tags" +version = "0.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d4345964bb142484797b161f473a503a434de77149dd8c7427788c6e13379388" + +[[package]] +name = "lazy_static" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bbd2bcb4c963f2ddae06a2efc7e9f3591312473c50c6685e1f298068316e66fe" + +[[package]] +name = "libc" +version = "0.2.158" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d8adc4bb1803a324070e64a98ae98f38934d91957a99cfb3a43dcbc01bc56439" + +[[package]] +name = "libm" +version = "0.2.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4ec2a862134d2a7d32d7983ddcdd1c4923530833c9f2ea1a44fc5fa473989058" + +[[package]] +name = "linux-raw-sys" +version = "0.4.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "78b3ae25bc7c8c38cec158d1f2757ee79e9b3740fbc7ccf0e59e4b08d793fa89" + +[[package]] +name = "local-channel" +version = "0.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b6cbc85e69b8df4b8bb8b89ec634e7189099cea8927a276b7384ce5488e53ec8" +dependencies = [ + "futures-core", + "futures-sink", + "local-waker", +] + +[[package]] +name = "local-waker" +version = "0.1.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4d873d7c67ce09b42110d801813efbc9364414e356be9935700d368351657487" + +[[package]] +name = "lock_api" +version = "0.4.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "07af8b9cdd281b7915f413fa73f29ebd5d55d0d3f0155584dade1ff18cea1b17" +dependencies = [ + "autocfg", + "scopeguard", +] + +[[package]] +name = "log" +version = "0.4.22" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a7a70ba024b9dc04c27ea2f0c0548feb474ec5c54bba33a7f72f873a39d07b24" +dependencies = [ + "value-bag", +] + +[[package]] +name = "memchr" +version = "2.7.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "78ca9ab1a0babb1e7d5695e3530886289c18cf2f87ec19a575a0abdce112e3a3" + +[[package]] +name = "mime" +version = "0.3.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6877bb514081ee2a7ff5ef9de3281f14a4dd4bceac4c09388074a6b5df8a139a" + +[[package]] +name = "miniz_oxide" +version = "0.8.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e2d80299ef12ff69b16a84bb182e3b9df68b5a91574d3d4fa6e41b65deec4df1" +dependencies = [ + "adler2", +] + +[[package]] +name = "mio" +version = "1.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "80e04d1dcff3aae0704555fe5fee3bcfaf3d1fdf8a7e521d5b9d2b42acb52cec" +dependencies = [ + "hermit-abi 0.3.9", + "libc", + "log", + "wasi", + "windows-sys 0.52.0", +] + +[[package]] +name = "native-tls" +version = "0.2.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a8614eb2c83d59d1c8cc974dd3f920198647674a0a035e1af1fa58707e317466" +dependencies = [ + "libc", + "log", + "openssl", + "openssl-probe", + "openssl-sys", + "schannel", + "security-framework", + "security-framework-sys", + "tempfile", +] + +[[package]] +name = "num-conv" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "51d515d32fb182ee37cda2ccdcb92950d6a3c2893aa280e540671c2cd0f3b1d9" + +[[package]] +name = "num-traits" +version = "0.2.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841" +dependencies = [ + "autocfg", + "libm", +] + +[[package]] +name = "object" +version = "0.36.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "084f1a5821ac4c651660a94a7153d27ac9d8a53736203f58b31945ded098070a" +dependencies = [ + "memchr", +] + +[[package]] +name = "once_cell" +version = "1.19.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3fdb12b2476b595f9358c5161aa467c2438859caa136dec86c26fdd2efe17b92" + +[[package]] +name = "openssl" +version = "0.10.66" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9529f4786b70a3e8c61e11179af17ab6188ad8d0ded78c5529441ed39d4bd9c1" +dependencies = [ + "bitflags", + "cfg-if", + "foreign-types", + "libc", + "once_cell", + "openssl-macros", + "openssl-sys", +] + +[[package]] +name = "openssl-macros" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a948666b637a0f465e8564c73e89d4dde00d72d4d473cc972f390fc3dcee7d9c" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "openssl-probe" +version = "0.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ff011a302c396a5197692431fc1948019154afc178baf7d8e37367442a4601cf" + +[[package]] +name = "openssl-sys" +version = "0.9.103" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7f9e8deee91df40a943c71b917e5874b951d32a802526c85721ce3b776c929d6" +dependencies = [ + "cc", + "libc", + "pkg-config", + "vcpkg", +] + +[[package]] +name = "parking" +version = "2.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f38d5652c16fde515bb1ecef450ab0f6a219d619a7274976324d5e377f7dceba" + +[[package]] +name = "parking_lot" +version = "0.12.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f1bf18183cf54e8d6059647fc3063646a1801cf30896933ec2311622cc4b9a27" +dependencies = [ + "lock_api", + "parking_lot_core", +] + +[[package]] +name = "parking_lot_core" +version = "0.9.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1e401f977ab385c9e4e3ab30627d6f26d00e2c73eef317493c4ec6d468726cf8" +dependencies = [ + "cfg-if", + "libc", + "redox_syscall", + "smallvec", + "windows-targets", +] + +[[package]] +name = "paste" +version = "1.0.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "57c0d7b74b563b49d38dae00a0c37d4d6de9b432382b2892f0574ddcae73fd0a" + +[[package]] +name = "percent-encoding" +version = "2.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e3148f5046208a5d56bcfc03053e3ca6334e51da8dfb19b6cdc8b306fae3283e" + +[[package]] +name = "pest" +version = "2.7.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fdbef9d1d47087a895abd220ed25eb4ad973a5e26f6a4367b038c25e28dfc2d9" +dependencies = [ + "memchr", + "thiserror", + "ucd-trie", +] + +[[package]] +name = "pest_derive" +version = "2.7.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4d3a6e3394ec80feb3b6393c725571754c6188490265c61aaf260810d6b95aa0" +dependencies = [ + "pest", + "pest_generator", +] + +[[package]] +name = "pest_generator" +version = "2.7.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "94429506bde1ca69d1b5601962c73f4172ab4726571a59ea95931218cb0e930e" +dependencies = [ + "pest", + "pest_meta", + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "pest_meta" +version = "2.7.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ac8a071862e93690b6e34e9a5fb8e33ff3734473ac0245b27232222c4906a33f" +dependencies = [ + "once_cell", + "pest", + "sha2", +] + +[[package]] +name = "pin-project-lite" +version = "0.2.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bda66fc9667c18cb2758a2ac84d1167245054bcf85d5d1aaa6923f45801bdd02" + +[[package]] +name = "pin-utils" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8b870d8c151b6f2fb93e84a13146138f05d02ed11c7e7c54f8826aaaf7c9f184" + +[[package]] +name = "piper" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "96c8c490f422ef9a4efd2cb5b42b76c8613d7e7dfc1caf667b8a3350a5acc066" +dependencies = [ + "atomic-waker", + "fastrand", + "futures-io", +] + +[[package]] +name = "pkg-config" +version = "0.3.31" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "953ec861398dccce10c670dfeaf3ec4911ca479e9c02154b3a215178c5f566f2" + +[[package]] +name = "polling" +version = "3.7.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cc2790cd301dec6cd3b7a025e4815cf825724a51c98dccfe6a3e55f05ffb6511" +dependencies = [ + "cfg-if", + "concurrent-queue", + "hermit-abi 0.4.0", + "pin-project-lite", + "rustix", + "tracing", + "windows-sys 0.59.0", +] + +[[package]] +name = "powerfmt" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "439ee305def115ba05938db6eb1644ff94165c5ab5e9420d1c1bcedbba909391" + +[[package]] +name = "ppv-lite86" +version = "0.2.20" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "77957b295656769bb8ad2b6a6b09d897d94f05c41b069aede1fcdaa675eaea04" +dependencies = [ + "zerocopy", +] + +[[package]] +name = "proc-macro2" +version = "1.0.86" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5e719e8df665df0d1c8fbfd238015744736151d4445ec0836b8e628aae103b77" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "proptest" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b4c2511913b88df1637da85cc8d96ec8e43a3f8bb8ccb71ee1ac240d6f3df58d" +dependencies = [ + "bit-set", + "bit-vec", + "bitflags", + "lazy_static", + "num-traits", + "rand", + "rand_chacha", + "rand_xorshift", + "regex-syntax", + "rusty-fork", + "tempfile", + "unarray", +] + +[[package]] +name = "quick-error" +version = "1.2.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0" + +[[package]] +name = "quote" +version = "1.0.37" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b5b9d34b8991d19d98081b46eacdd8eb58c6f2b201139f7c5f643cc155a633af" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "rand" +version = "0.8.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404" +dependencies = [ + "libc", + "rand_chacha", + "rand_core", +] + +[[package]] +name = "rand_chacha" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88" +dependencies = [ + "ppv-lite86", + "rand_core", +] + +[[package]] +name = "rand_core" +version = "0.6.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c" +dependencies = [ + "getrandom", +] + +[[package]] +name = "rand_xorshift" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d25bf25ec5ae4a3f1b92f929810509a2f53d7dca2f50b794ff57e3face536c8f" +dependencies = [ + "rand_core", +] + +[[package]] +name = "redox_syscall" +version = "0.5.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9b6dfecf2c74bce2466cabf93f6664d6998a69eb21e39f4207930065b27b771f" +dependencies = [ + "bitflags", +] + +[[package]] +name = "regex" +version = "1.10.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4219d74c6b67a3654a9fbebc4b419e22126d13d2f3c4a07ee0cb61ff79a79619" +dependencies = [ + "aho-corasick", + "memchr", + "regex-automata", + "regex-syntax", +] + +[[package]] +name = "regex-automata" +version = "0.4.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38caf58cc5ef2fed281f89292ef23f6365465ed9a41b7a7754eb4e26496c92df" +dependencies = [ + "aho-corasick", + "memchr", + "regex-syntax", +] + +[[package]] +name = "regex-lite" +version = "0.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "53a49587ad06b26609c52e423de037e7f57f20d53535d66e08c695f347df952a" + +[[package]] +name = "regex-syntax" +version = "0.8.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7a66a03ae7c801facd77a29370b4faec201768915ac14a721ba36f20bc9c209b" + +[[package]] +name = "reqwest" +version = "0.12.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f713147fbe92361e52392c73b8c9e48c04c6625bce969ef54dc901e58e042a7b" +dependencies = [ + "base64", + "bytes", + "encoding_rs", + "futures-core", + "futures-util", + "h2 0.4.6", + "http 1.1.0", + "http-body", + "http-body-util", + "hyper", + "hyper-rustls", + "hyper-tls", + "hyper-util", + "ipnet", + "js-sys", + "log", + "mime", + "native-tls", + "once_cell", + "percent-encoding", + "pin-project-lite", + "rustls-pemfile", + "serde", + "serde_json", + "serde_urlencoded", + "sync_wrapper", + "system-configuration", + "tokio", + "tokio-native-tls", + "tower-service", + "url", + "wasm-bindgen", + "wasm-bindgen-futures", + "web-sys", + "windows-registry", +] + +[[package]] +name = "ring" +version = "0.17.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c17fa4cb658e3583423e915b9f3acc01cceaee1860e33d59ebae66adc3a2dc0d" +dependencies = [ + "cc", + "cfg-if", + "getrandom", + "libc", + "spin", + "untrusted", + "windows-sys 0.52.0", +] + +[[package]] +name = "rust" +version = "0.1.0" +dependencies = [ + "actix-web", + "async-std", + "chrono", + "clap", + "env_logger", + "futures", + "handlebars", + "log", + "proptest", + "rand", + "reqwest", + "serde", + "serde_json", + "tokio", + "uuid", +] + +[[package]] +name = "rustc-demangle" +version = "0.1.24" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "719b953e2095829ee67db738b3bfa9fa368c94900df327b3f07fe6e794d2fe1f" + +[[package]] +name = "rustc_version" +version = "0.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cfcb3a22ef46e85b45de6ee7e79d063319ebb6594faafcf1c225ea92ab6e9b92" +dependencies = [ + "semver", +] + +[[package]] +name = "rustix" +version = "0.38.37" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8acb788b847c24f28525660c4d7758620a7210875711f79e7f663cc152726811" +dependencies = [ + "bitflags", + "errno", + "libc", + "linux-raw-sys", + "windows-sys 0.52.0", +] + +[[package]] +name = "rustls" +version = "0.23.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "415d9944693cb90382053259f89fbb077ea730ad7273047ec63b19bc9b160ba8" +dependencies = [ + "once_cell", + "rustls-pki-types", + "rustls-webpki", + "subtle", + "zeroize", +] + +[[package]] +name = "rustls-pemfile" +version = "2.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dce314e5fee3f39953d46bb63bb8a46d40c2f8fb7cc5a3b6cab2bde9721d6e50" +dependencies = [ + "rustls-pki-types", +] + +[[package]] +name = "rustls-pki-types" +version = "1.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0e696e35370c65c9c541198af4543ccd580cf17fc25d8e05c5a242b202488c55" + +[[package]] +name = "rustls-webpki" +version = "0.102.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "64ca1bc8749bd4cf37b5ce386cc146580777b4e8572c7b97baf22c83f444bee9" +dependencies = [ + "ring", + "rustls-pki-types", + "untrusted", +] + +[[package]] +name = "rusty-fork" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cb3dcc6e454c328bb824492db107ab7c0ae8fcffe4ad210136ef014458c1bc4f" +dependencies = [ + "fnv", + "quick-error", + "tempfile", + "wait-timeout", +] + +[[package]] +name = "ryu" +version = "1.0.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f3cb5ba0dc43242ce17de99c180e96db90b235b8a9fdc9543c96d2209116bd9f" + +[[package]] +name = "same-file" +version = "1.0.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "93fc1dc3aaa9bfed95e02e6eadabb4baf7e3078b0bd1b4d7b6b0b68378900502" +dependencies = [ + "winapi-util", +] + +[[package]] +name = "schannel" +version = "0.1.24" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e9aaafd5a2b6e3d657ff009d82fbd630b6bd54dd4eb06f21693925cdf80f9b8b" +dependencies = [ + "windows-sys 0.59.0", +] + +[[package]] +name = "scopeguard" +version = "1.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "94143f37725109f92c262ed2cf5e59bce7498c01bcc1502d7b9afe439a4e9f49" + +[[package]] +name = "security-framework" +version = "2.11.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "897b2245f0b511c87893af39b033e5ca9cce68824c4d7e7630b5a1d339658d02" +dependencies = [ + "bitflags", + "core-foundation", + "core-foundation-sys", + "libc", + "security-framework-sys", +] + +[[package]] +name = "security-framework-sys" +version = "2.12.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ea4a292869320c0272d7bc55a5a6aafaff59b4f63404a003887b679a2e05b4b6" +dependencies = [ + "core-foundation-sys", + "libc", +] + +[[package]] +name = "semver" +version = "1.0.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "61697e0a1c7e512e84a621326239844a24d8207b4669b41bc18b32ea5cbf988b" + +[[package]] +name = "serde" +version = "1.0.210" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c8e3592472072e6e22e0a54d5904d9febf8508f65fb8552499a1abc7d1078c3a" +dependencies = [ + "serde_derive", +] + +[[package]] +name = "serde_derive" +version = "1.0.210" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "243902eda00fad750862fc144cea25caca5e20d615af0a81bee94ca738f1df1f" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "serde_json" +version = "1.0.128" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6ff5456707a1de34e7e37f2a6fd3d3f808c318259cbd01ab6377795054b483d8" +dependencies = [ + "itoa", + "memchr", + "ryu", + "serde", +] + +[[package]] +name = "serde_urlencoded" +version = "0.7.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d3491c14715ca2294c4d6a88f15e84739788c1d030eed8c110436aafdaa2f3fd" +dependencies = [ + "form_urlencoded", + "itoa", + "ryu", + "serde", +] + +[[package]] +name = "sha1" +version = "0.10.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e3bf829a2d51ab4a5ddf1352d8470c140cadc8301b2ae1789db023f01cedd6ba" +dependencies = [ + "cfg-if", + "cpufeatures", + "digest", +] + +[[package]] +name = "sha2" +version = "0.10.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "793db75ad2bcafc3ffa7c68b215fee268f537982cd901d132f89c6343f3a3dc8" +dependencies = [ + "cfg-if", + "cpufeatures", + "digest", +] + +[[package]] +name = "shlex" +version = "1.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0fda2ff0d084019ba4d7c6f371c95d8fd75ce3524c3cb8fb653a3023f6323e64" + +[[package]] +name = "signal-hook-registry" +version = "1.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a9e9e0b4211b72e7b8b6e85c807d36c212bdb33ea8587f7569562a84df5465b1" +dependencies = [ + "libc", +] + +[[package]] +name = "slab" +version = "0.4.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8f92a496fb766b417c996b9c5e57daf2f7ad3b0bebe1ccfca4856390e3d3bb67" +dependencies = [ + "autocfg", +] + +[[package]] +name = "smallvec" +version = "1.13.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3c5e1a9a646d36c3599cd173a41282daf47c44583ad367b8e6837255952e5c67" + +[[package]] +name = "socket2" +version = "0.5.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ce305eb0b4296696835b71df73eb912e0f1ffd2556a501fcede6e0c50349191c" +dependencies = [ + "libc", + "windows-sys 0.52.0", +] + +[[package]] +name = "spin" +version = "0.9.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6980e8d7511241f8acf4aebddbb1ff938df5eebe98691418c4468d0b72a96a67" + +[[package]] +name = "strsim" +version = "0.11.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7da8b5736845d9f2fcb837ea5d9e2628564b3b043a70948a3f0b778838c5fb4f" + +[[package]] +name = "subtle" +version = "2.6.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "13c2bddecc57b384dee18652358fb23172facb8a2c51ccc10d74c157bdea3292" + +[[package]] +name = "syn" +version = "2.0.77" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9f35bcdf61fd8e7be6caf75f429fdca8beb3ed76584befb503b1569faee373ed" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "sync_wrapper" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a7065abeca94b6a8a577f9bd45aa0867a2238b74e8eb67cf10d492bc39351394" +dependencies = [ + "futures-core", +] + +[[package]] +name = "system-configuration" +version = "0.6.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3c879d448e9d986b661742763247d3693ed13609438cf3d006f51f5368a5ba6b" +dependencies = [ + "bitflags", + "core-foundation", + "system-configuration-sys", +] + +[[package]] +name = "system-configuration-sys" +version = "0.6.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8e1d1b10ced5ca923a1fcb8d03e96b8d3268065d724548c0211415ff6ac6bac4" +dependencies = [ + "core-foundation-sys", + "libc", +] + +[[package]] +name = "tempfile" +version = "3.12.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "04cbcdd0c794ebb0d4cf35e88edd2f7d2c4c3e9a5a6dab322839b321c6a87a64" +dependencies = [ + "cfg-if", + "fastrand", + "once_cell", + "rustix", + "windows-sys 0.59.0", +] + +[[package]] +name = "termcolor" +version = "1.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "06794f8f6c5c898b3275aebefa6b8a1cb24cd2c6c79397ab15774837a0bc5755" +dependencies = [ + "winapi-util", +] + +[[package]] +name = "thiserror" +version = "1.0.64" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d50af8abc119fb8bb6dbabcfa89656f46f84aa0ac7688088608076ad2b459a84" +dependencies = [ + "thiserror-impl", +] + +[[package]] +name = "thiserror-impl" +version = "1.0.64" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "08904e7672f5eb876eaaf87e0ce17857500934f4981c4a0ab2b4aa98baac7fc3" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "time" +version = "0.3.36" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5dfd88e563464686c916c7e46e623e520ddc6d79fa6641390f2e3fa86e83e885" +dependencies = [ + "deranged", + "itoa", + "num-conv", + "powerfmt", + "serde", + "time-core", + "time-macros", +] + +[[package]] +name = "time-core" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ef927ca75afb808a4d64dd374f00a2adf8d0fcff8e7b184af886c3c87ec4a3f3" + +[[package]] +name = "time-macros" +version = "0.2.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3f252a68540fde3a3877aeea552b832b40ab9a69e318efd078774a01ddee1ccf" +dependencies = [ + "num-conv", + "time-core", +] + +[[package]] +name = "tinyvec" +version = "1.8.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "445e881f4f6d382d5f27c034e25eb92edd7c784ceab92a0937db7f2e9471b938" +dependencies = [ + "tinyvec_macros", +] + +[[package]] +name = "tinyvec_macros" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1f3ccbac311fea05f86f61904b462b55fb3df8837a366dfc601a0161d0532f20" + +[[package]] +name = "tokio" +version = "1.40.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e2b070231665d27ad9ec9b8df639893f46727666c6767db40317fbe920a5d998" +dependencies = [ + "backtrace", + "bytes", + "libc", + "mio", + "parking_lot", + "pin-project-lite", + "signal-hook-registry", + "socket2", + "tokio-macros", + "windows-sys 0.52.0", +] + +[[package]] +name = "tokio-macros" +version = "2.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "693d596312e88961bc67d7f1f97af8a70227d9f90c31bba5806eec004978d752" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "tokio-native-tls" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bbae76ab933c85776efabc971569dd6119c580d8f5d448769dec1764bf796ef2" +dependencies = [ + "native-tls", + "tokio", +] + +[[package]] +name = "tokio-rustls" +version = "0.26.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0c7bc40d0e5a97695bb96e27995cd3a08538541b0a846f65bba7a359f36700d4" +dependencies = [ + "rustls", + "rustls-pki-types", + "tokio", +] + +[[package]] +name = "tokio-util" +version = "0.7.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "61e7c3654c13bcd040d4a03abee2c75b1d14a37b423cf5a813ceae1cc903ec6a" +dependencies = [ + "bytes", + "futures-core", + "futures-sink", + "pin-project-lite", + "tokio", +] + +[[package]] +name = "tower-service" +version = "0.3.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8df9b6e13f2d32c91b9bd719c00d1958837bc7dec474d94952798cc8e69eeec3" + +[[package]] +name = "tracing" +version = "0.1.40" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c3523ab5a71916ccf420eebdf5521fcef02141234bbc0b8a49f2fdc4544364ef" +dependencies = [ + "log", + "pin-project-lite", + "tracing-core", +] + +[[package]] +name = "tracing-core" +version = "0.1.32" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c06d3da6113f116aaee68e4d601191614c9053067f9ab7f6edbcb161237daa54" +dependencies = [ + "once_cell", +] + +[[package]] +name = "try-lock" +version = "0.2.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e421abadd41a4225275504ea4d6566923418b7f05506fbc9c0fe86ba7396114b" + +[[package]] +name = "typenum" +version = "1.17.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "42ff0bf0c66b8238c6f3b578df37d0b7848e55df8577b3f74f92a69acceeb825" + +[[package]] +name = "ucd-trie" +version = "0.1.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2896d95c02a80c6d6a5d6e953d479f5ddf2dfdb6a244441010e373ac0fb88971" + +[[package]] +name = "unarray" +version = "0.1.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "eaea85b334db583fe3274d12b4cd1880032beab409c0d774be044d4480ab9a94" + +[[package]] +name = "unicode-bidi" +version = "0.3.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5ab17db44d7388991a428b2ee655ce0c212e862eff1768a455c58f9aad6e7893" + +[[package]] +name = "unicode-ident" +version = "1.0.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e91b56cd4cadaeb79bbf1a5645f6b4f8dc5bde8834ad5894a8db35fda9efa1fe" + +[[package]] +name = "unicode-normalization" +version = "0.1.24" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5033c97c4262335cded6d6fc3e5c18ab755e1a3dc96376350f3d8e9f009ad956" +dependencies = [ + "tinyvec", +] + +[[package]] +name = "untrusted" +version = "0.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8ecb6da28b8a351d773b68d5825ac39017e680750f980f3a1a85cd8dd28a47c1" + +[[package]] +name = "url" +version = "2.5.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "22784dbdf76fdde8af1aeda5622b546b422b6fc585325248a2bf9f5e41e94d6c" +dependencies = [ + "form_urlencoded", + "idna", + "percent-encoding", +] + +[[package]] +name = "utf8parse" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "06abde3611657adf66d383f00b093d7faecc7fa57071cce2578660c9f1010821" + +[[package]] +name = "uuid" +version = "1.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "81dfa00651efa65069b0b6b651f4aaa31ba9e3c3ce0137aaad053604ee7e0314" +dependencies = [ + "getrandom", + "rand", + "serde", + "uuid-macro-internal", +] + +[[package]] +name = "uuid-macro-internal" +version = "1.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ee1cd046f83ea2c4e920d6ee9f7c3537ef928d75dce5d84a87c2c5d6b3999a3a" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "value-bag" +version = "1.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5a84c137d37ab0142f0f2ddfe332651fdbf252e7b7dbb4e67b6c1f1b2e925101" + +[[package]] +name = "vcpkg" +version = "0.2.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "accd4ea62f7bb7a82fe23066fb0957d48ef677f6eeb8215f372f52e48bb32426" + +[[package]] +name = "version_check" +version = "0.9.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0b928f33d975fc6ad9f86c8f283853ad26bdd5b10b7f1542aa2fa15e2289105a" + +[[package]] +name = "wait-timeout" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9f200f5b12eb75f8c1ed65abd4b2db8a6e1b138a20de009dacee265a2498f3f6" +dependencies = [ + "libc", +] + +[[package]] +name = "walkdir" +version = "2.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "29790946404f91d9c5d06f9874efddea1dc06c5efe94541a7d6863108e3a5e4b" +dependencies = [ + "same-file", + "winapi-util", +] + +[[package]] +name = "want" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bfa7760aed19e106de2c7c0b581b509f2f25d3dacaf737cb82ac61bc6d760b0e" +dependencies = [ + "try-lock", +] + +[[package]] +name = "wasi" +version = "0.11.0+wasi-snapshot-preview1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423" + +[[package]] +name = "wasm-bindgen" +version = "0.2.93" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a82edfc16a6c469f5f44dc7b571814045d60404b55a0ee849f9bcfa2e63dd9b5" +dependencies = [ + "cfg-if", + "once_cell", + "wasm-bindgen-macro", +] + +[[package]] +name = "wasm-bindgen-backend" +version = "0.2.93" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9de396da306523044d3302746f1208fa71d7532227f15e347e2d93e4145dd77b" +dependencies = [ + "bumpalo", + "log", + "once_cell", + "proc-macro2", + "quote", + "syn", + "wasm-bindgen-shared", +] + +[[package]] +name = "wasm-bindgen-futures" +version = "0.4.43" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "61e9300f63a621e96ed275155c108eb6f843b6a26d053f122ab69724559dc8ed" +dependencies = [ + "cfg-if", + "js-sys", + "wasm-bindgen", + "web-sys", +] + +[[package]] +name = "wasm-bindgen-macro" +version = "0.2.93" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "585c4c91a46b072c92e908d99cb1dcdf95c5218eeb6f3bf1efa991ee7a68cccf" +dependencies = [ + "quote", + "wasm-bindgen-macro-support", +] + +[[package]] +name = "wasm-bindgen-macro-support" +version = "0.2.93" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "afc340c74d9005395cf9dd098506f7f44e38f2b4a21c6aaacf9a105ea5e1e836" +dependencies = [ + "proc-macro2", + "quote", + "syn", + "wasm-bindgen-backend", + "wasm-bindgen-shared", +] + +[[package]] +name = "wasm-bindgen-shared" +version = "0.2.93" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c62a0a307cb4a311d3a07867860911ca130c3494e8c2719593806c08bc5d0484" + +[[package]] +name = "web-sys" +version = "0.3.70" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "26fdeaafd9bd129f65e7c031593c24d62186301e0c72c8978fa1678be7d532c0" +dependencies = [ + "js-sys", + "wasm-bindgen", +] + +[[package]] +name = "winapi" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419" +dependencies = [ + "winapi-i686-pc-windows-gnu", + "winapi-x86_64-pc-windows-gnu", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" + +[[package]] +name = "winapi-util" +version = "0.1.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cf221c93e13a30d793f7645a0e7762c55d169dbb0a49671918a2319d289b10bb" +dependencies = [ + "windows-sys 0.59.0", +] + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" + +[[package]] +name = "windows-core" +version = "0.52.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "33ab640c8d7e35bf8ba19b884ba838ceb4fba93a4e8c65a9059d08afcfc683d9" +dependencies = [ + "windows-targets", +] + +[[package]] +name = "windows-registry" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e400001bb720a623c1c69032f8e3e4cf09984deec740f007dd2b03ec864804b0" +dependencies = [ + "windows-result", + "windows-strings", + "windows-targets", +] + +[[package]] +name = "windows-result" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1d1043d8214f791817bab27572aaa8af63732e11bf84aa21a45a78d6c317ae0e" +dependencies = [ + "windows-targets", +] + +[[package]] +name = "windows-strings" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4cd9b125c486025df0eabcb585e62173c6c9eddcec5d117d3b6e8c30e2ee4d10" +dependencies = [ + "windows-result", + "windows-targets", +] + +[[package]] +name = "windows-sys" +version = "0.52.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "282be5f36a8ce781fad8c8ae18fa3f9beff57ec1b52cb3de0789201425d9a33d" +dependencies = [ + "windows-targets", +] + +[[package]] +name = "windows-sys" +version = "0.59.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1e38bc4d79ed67fd075bcc251a1c39b32a1776bbe92e5bef1f0bf1f8c531853b" +dependencies = [ + "windows-targets", +] + +[[package]] +name = "windows-targets" +version = "0.52.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9b724f72796e036ab90c1021d4780d4d3d648aca59e491e6b98e725b84e99973" +dependencies = [ + "windows_aarch64_gnullvm", + "windows_aarch64_msvc", + "windows_i686_gnu", + "windows_i686_gnullvm", + "windows_i686_msvc", + "windows_x86_64_gnu", + "windows_x86_64_gnullvm", + "windows_x86_64_msvc", +] + +[[package]] +name = "windows_aarch64_gnullvm" +version = "0.52.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "32a4622180e7a0ec044bb555404c800bc9fd9ec262ec147edd5989ccd0c02cd3" + +[[package]] +name = "windows_aarch64_msvc" +version = "0.52.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "09ec2a7bb152e2252b53fa7803150007879548bc709c039df7627cabbd05d469" + +[[package]] +name = "windows_i686_gnu" +version = "0.52.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8e9b5ad5ab802e97eb8e295ac6720e509ee4c243f69d781394014ebfe8bbfa0b" + +[[package]] +name = "windows_i686_gnullvm" +version = "0.52.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0eee52d38c090b3caa76c563b86c3a4bd71ef1a819287c19d586d7334ae8ed66" + +[[package]] +name = "windows_i686_msvc" +version = "0.52.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "240948bc05c5e7c6dabba28bf89d89ffce3e303022809e73deaefe4f6ec56c66" + +[[package]] +name = "windows_x86_64_gnu" +version = "0.52.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "147a5c80aabfbf0c7d901cb5895d1de30ef2907eb21fbbab29ca94c5b08b1a78" + +[[package]] +name = "windows_x86_64_gnullvm" +version = "0.52.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "24d5b23dc417412679681396f2b49f3de8c1473deb516bd34410872eff51ed0d" + +[[package]] +name = "windows_x86_64_msvc" +version = "0.52.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "589f6da84c646204747d1270a2a5661ea66ed1cced2631d546fdfb155959f9ec" + +[[package]] +name = "zerocopy" +version = "0.7.35" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1b9b4fd18abc82b8136838da5d50bae7bdea537c574d8dc1a34ed098d6c166f0" +dependencies = [ + "byteorder", + "zerocopy-derive", +] + +[[package]] +name = "zerocopy-derive" +version = "0.7.35" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fa4f8080344d4671fb4e831a13ad1e68092748387dfc4f55e356242fae12ce3e" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "zeroize" +version = "1.8.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ced3678a2879b30306d323f4542626697a464a97c0a07c9aebf7ebca65cd4dde" + +[[package]] +name = "zstd" +version = "0.13.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fcf2b778a664581e31e389454a7072dab1647606d44f7feea22cd5abb9c9f3f9" +dependencies = [ + "zstd-safe", +] + +[[package]] +name = "zstd-safe" +version = "7.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "54a3ab4db68cea366acc5c897c7b4d4d1b8994a9cd6e6f841f8964566a419059" +dependencies = [ + "zstd-sys", +] + +[[package]] +name = "zstd-sys" +version = "2.0.13+zstd.1.5.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38ff0f21cfee8f97d94cef41359e0c89aa6113028ab0291aa8ca0038995a95aa" +dependencies = [ + "cc", + "pkg-config", +] diff --git a/lambda-calcul/rust/Cargo.lock.rej b/lambda-calcul/rust/Cargo.lock.rej new file mode 100644 index 0000000..3e5e0dc --- /dev/null +++ b/lambda-calcul/rust/Cargo.lock.rej @@ -0,0 +1,9 @@ +diff a/rust/Cargo.lock b/rust/Cargo.lock (rejected hunks) +@@ -1777,6 +1777,7 @@ dependencies = [ + "log", + "proptest", + "rand", ++ "regex", + "reqwest", + "serde", + "serde_json", diff --git a/lambda-calcul/rust/Cargo.toml b/lambda-calcul/rust/Cargo.toml new file mode 100644 index 0000000..c742302 --- /dev/null +++ b/lambda-calcul/rust/Cargo.toml @@ -0,0 +1,45 @@ +[package] +name = "rust" +version = "0.1.0" +edition = "2021" + +[dependencies] +rand = { version = "0.8.5", features = ["small_rng"] } +serde = { version = "1.0", features = ["derive"] } +serde_json = "1.0.128" +chrono = { version= "0.4.38", features = ["serde"]} +actix-web = "4.9.0" +env_logger = "0.8" +log = "0.4" +futures = "0.3.30" +async-std = "1.13.0" +reqwest = "0.12.8" +tokio = { version = "1.40.0", features = ["rt", "macros", "rt-multi-thread"]} +clap = { version = "4.5.19", features = ["derive"] } +proptest = "1.0.0" +handlebars = { version = "5", features = ["dir_source"] } + +[dependencies.uuid] +version = "1.10.0" +features = [ + "v4", # Lets you generate random UUIDs + "fast-rng", # Use a faster (but still sufficiently random) RNG + "macro-diagnostics", # Enable better diagnostics for compile-time UUIDs + "serde" +] + +[lib] +name = "lambda" +path = "src/lib.rs" + +[[bin]] +name = "eval" +path = "src/main.rs" + +[[bin]] +name = "tester" +path = "src/tester.rs" + +[[bin]] +name = "server" +path = "src/web.rs" diff --git a/lambda-calcul/rust/README.md b/lambda-calcul/rust/README.md new file mode 100644 index 0000000..7dfc03b --- /dev/null +++ b/lambda-calcul/rust/README.md @@ -0,0 +1,42 @@ +# Rust λ-calcul reference implementation + +This directory contains a reference implementation of a normal order semantics λ-calculus based language. +Current syntax is based on S-expressions, ie. Lisp. There is a command-line interpreter for batch and interactive evaluation of input, and an embryonic tester daemon. + +# Tester + +The tester daemon is inspired by [Extreme Startup](https://github.com/rchatley/extreme_startup): It's a REST-ish server and client that allows to repeatedly send λ-terms to a remote execution engine and compare the result against its expectations. + +The interaction flow is simple: + +* HTTP server starts on some known port (eg. 8080) +* Client sends a `POST /register` request, passing in as payload a JSON object with a `url` and `name` string fields + ``` + curl -v -X POST -d '{"url":"http://127.0.0.1:8888/eval", "name": "toto"}' -H 'Content-type: application/json' http://localhost:8080/register + ``` +* Obviously, client needs to start a HTTP server able to respond to a `GET` request at the given URL +* If URL is not already registered, server accepts the registration (returning a 200 result) and starts a _testing thread_ +* The _tester_ then repeatedly sends `POST` requests to the client's registered URL + * The body of the request is plain text S-expression representing a λ-term + * The tester expects the response to be the plain text result of the evaluation of those terms +* If the client fails to answer, or answers wrongly, the server keeps sending the same request +* If the client's answer is correct, the server sends another term to evaluate and awards 1 point to the client +* The `/leaderboard` endpoint provides a crude HTML page listing each clients' current score + +## Building + +This software is written in Rust (sorry @xvdw), so one needs a Rust toolchain installed, then: + +``` +cargo build && cargo test +``` + +## Running + +To run the server: + +``` +cargo run --bin server +``` + +There are `--port` and `--host` arguments should one want to change the defaults `127.0.0.1:8080` diff --git a/lambda-calcul/rust/cover.sh b/lambda-calcul/rust/cover.sh new file mode 100755 index 0000000..c7befa6 --- /dev/null +++ b/lambda-calcul/rust/cover.sh @@ -0,0 +1,4 @@ +#!/usr/bin/env bash +CARGO_INCREMENTAL=0 RUSTFLAGS='-Cinstrument-coverage' LLVM_PROFILE_FILE='cargo-test-%p-%m.profraw' cargo test +rm -fr target/coverage/html +grcov . --binary-path ./target/debug/deps/ -s . -t html --branch --ignore-not-existing --ignore '../*' --ignore "/*" -o target/coverage/html diff --git a/lambda-calcul/rust/distrib b/lambda-calcul/rust/distrib new file mode 100644 index 0000000..ba11467 --- /dev/null +++ b/lambda-calcul/rust/distrib @@ -0,0 +1,3022 @@ +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +11118 +13127 +47069 +65868 +1000000 +1000000 +1000000 +1000000 +1000000 +1000000 +1000000 +1000009 +1000100 +1000100 +1044631 +1200000 +1221941 +1231208 +1258444 +1289969 +1322858 +1430897 +1434673 +1434673 +1481480 +1481480 +1586597 +1665757 +1688197 +1763938 +1773860 +1800569 +1801494 +1822883 +1854270 +1865490 +1957114 +2001200 +2007228 +2029803 +2050621 +2062184 +2228964 +2267244 +2386319 +2443789 +2450653 +2486679 +2500000 +2562761 +2609445 +2618354 +2621434 +2623282 +2639298 +2646822 +2729004 +2735858 +2742048 +2823411 +2915210 +2925923 +2925923 +2953199 +2990070 +3070591 +3080875 +3092547 +3455860 +3570478 +3625350 +3629838 +3678935 +3981480 +3991496 +4000000 +4048591 +4191429 +4233056 +4310452 +4427641 +4581261 +4585779 +4593662 +4613646 +4613866 +5000000 +5154646 +5223772 +5398685 +5577986 +5624250 +5800118 +5879394 +5885306 +6000000 +6000000 +6000000 +6001245 +6135954 +6399036 +6444552 +6453117 +6470103 +6638814 +6863246 +7054091 +7401751 +7414749 +7475689 +7620000 +7621654 +7622358 +7624514 +7629486 +7629486 +7634370 +7900602 +7952568 +8247561 +8249917 +8602239 +8618750 +8705929 +8755036 +9248208 +9471895 +9486132 +9490391 +9618398 +9618530 +9619058 +9630058 +9802291 +9823059 +9825875 +9892022 +10000000 +10181917 +10276880 +10276968 +10276968 +10277188 +10277188 +10277276 +10843473 +10984954 +11000000 +11095972 +11286634 +11633160 +11700000 +12000000 +12017087 +12145784 +12440621 +12611753 +12621038 +12691233 +12851369 +13276968 +14776577 +17236444 +17425265 +17427226 +17509389 +17619014 +17620334 +17719612 +17988077 +18269664 +18599471 +18621214 +18737033 +18816176 +19232201 +19424099 +19453176 +19736460 +20000000 +20015900 +20061667 +22420601 +22424605 +22971625 +23420165 +23433361 +23613933 +24517029 +24923870 +25098487 +25300000 +25825259 +27595522 +27597982 +27617078 +27624822 +29445355 +29620216 +30477971 +31323894 +32036957 +32150290 +32637619 +32724696 +35245376 +36118889 +36313357 +37987754 +39624703 +39983004 +40326929 +41986459 +42018412 +44304481 +44454085 +47821475 +49055495 +49678250 +49782708 +50005115 +50425749 +51339332 +52037404 +52237703 +53694740 +53706194 +53738926 +55456744 +55651486 +57425793 +57602998 +59460400 +59603626 +61914723 +62602470 +65887919 +66488296 +67456466 +69720767 +70449031 +70473160 +70535921 +74670202 +76837286 +77512682 +77848386 +79065199 +80466289 +81498032 +86883798 +89153217 +90420676 +92090039 +92633094 +93505493 +94912118 +95424561 +96634341 +96794849 +97023027 +97052335 +97510309 +97620466 +97623898 +97624556 +97624734 +97924379 +98624030 +98903851 +99280884 +99442997 +100000000 +100000000 +100025743 +100257520 +100609921 +100838685 +101080977 +101227512 +101250210 +101376006 +101924863 +102228700 +102232264 +102616550 +102624998 +103000000 +103000000 +103000000 +103070019 +103072351 +103164846 +103230899 +103607970 +104493534 +104596453 +105132223 +105235662 +105303081 +106115657 +106623722 +107145887 +107224476 +107413297 +107414793 +107431117 +107845589 +108761740 +109028510 +109063264 +109611710 +110622006 +111625658 +112693362 +112711109 +112744004 +113068208 +114280001 +114848902 +115453029 +116330953 +116709162 +116948336 +117618178 +118910750 +119036341 +119116223 +119504595 +120549939 +121436315 +121484627 +121740362 +122078687 +122084935 +122213685 +126003727 +126660459 +127046347 +127837672 +127878040 +128905489 +132502367 +133400000 +135106409 +136644068 +138742943 +139818659 +143353157 +145825699 +147624426 +147661322 +148091537 +148435878 +148796601 +150000000 +150610962 +154247620 +156277982 +160317709 +160730261 +163039113 +163755733 +164620642 +165628320 +167368737 +169936908 +174968922 +177440451 +177788132 +177935758 +178259850 +183265277 +183277705 +188239958 +189691746 +195445945 +195954037 +197125746 +197226148 +197226148 +197226280 +197237368 +197299065 +197430721 +197456153 +197616022 +197619190 +197619190 +197619190 +197624030 +199600000 +200000000 +200810035 +203182474 +203250629 +205618530 +208581547 +212498157 +217955135 +218055983 +218615274 +220848661 +223360860 +223866352 +229374109 +233375391 +233445021 +234628065 +240722383 +241299438 +244646977 +245204781 +246637145 +247210196 +247237293 +247700679 +251000039 +266665872 +277173167 +281976853 +291472771 +295935325 +297094817 +300093772 +300822669 +304278509 +306685167 +306763214 +308097517 +313285815 +314271584 +316147380 +316914476 +321624382 +326466865 +330742127 +340339941 +340417081 +340922310 +341624605 +342417653 +343734222 +343736822 +347620334 +350501298 +354952691 +356830510 +357849567 +360524775 +366625702 +367289456 +368178331 +373760410 +374410917 +375469867 +376518669 +381263120 +384919390 +385377493 +385500629 +386440554 +388321443 +391087660 +391105694 +396714456 +397178663 +397921363 +397940567 +399168123 +400944493 +407405934 +413801996 +416934572 +424685339 +429144410 +432075956 +432816574 +437621830 +443098286 +444287597 +455976917 +458257808 +464078945 +465409359 +466084377 +466984959 +472976532 +476652900 +478757616 +489240394 +494831058 +495282744 +496562740 +496719173 +497420337 +497432393 +497625262 +497625350 +499489389 +500000000 +500000000 +500000000 +500412330 +500624074 +500954444 +501033989 +501132556 +502251844 +502300231 +502365742 +502580210 +502624954 +503725382 +504101303 +504683670 +507102535 +507236356 +507423329 +507449333 +507449373 +507621786 +509235798 +509766415 +511697133 +512065971 +512621610 +515476511 +515619014 +516425793 +516461389 +517625000 +517703111 +519044358 +520082000 +525042337 +525372401 +527290227 +528015204 +531488042 +532618310 +533517462 +536842986 +538425594 +540700677 +544125690 +545772868 +545778456 +545954517 +545978937 +546890394 +546890394 +546890394 +546890394 +546890394 +546890394 +546890394 +547629794 +548340078 +548606340 +551719342 +552424253 +554651740 +564425881 +568150653 +568163192 +572915210 +586099654 +593799895 +594564135 +596889206 +597625746 +598614966 +607393771 +607724090 +626690294 +627115849 +631048656 +635210245 +638756010 +640942071 +642048577 +642121377 +645079510 +653014581 +658619725 +658852361 +666500221 +668741592 +676699901 +680266470 +695426541 +697439961 +698292896 +700169687 +701407805 +707520898 +709842356 +726170453 +738215807 +760828483 +766842596 +776657131 +784476660 +809142273 +812165326 +816886634 +820025746 +851328895 +862976284 +868469289 +870877150 +872085077 +894599514 +897047887 +903951793 +910342644 +915406660 +922009012 +923691183 +928651575 +939083298 +942823411 +946757501 +964601654 +967820719 +970921601 +983781249 +997620818 +998257168 +999825743 +1000000000 +1000713424 +1000819149 +1000833986 +1001063730 +1001425841 +1001670616 +1001676644 +1002437424 +1005175300 +1006277905 +1008551601 +1008611006 +1008640310 +1009939347 +1012075370 +1014271248 +1018842337 +1032212606 +1032235168 +1034088522 +1037490472 +1043463985 +1045574031 +1047231164 +1047621962 +1053239172 +1055552627 +1057631925 +1059010727 +1062558799 +1062873813 +1068026209 +1073037195 +1074408468 +1075435349 +1084589756 +1087461798 +1087822733 +1093094791 +1094719930 +1097230020 +1099411067 +1100522781 +1103489806 +1112619894 +1115774522 +1117431611 +1122038051 +1123182320 +1144071818 +1144474695 +1145957833 +1155789836 +1157134418 +1162065545 +1162108630 +1166785736 +1171558392 +1178371972 +1178645015 +1187238209 +1190761831 +1206074434 +1212621566 +1222471073 +1230538750 +1232444199 +1252760574 +1257550057 +1257789162 +1271948106 +1272255210 +1291305394 +1294750981 +1300746858 +1312854346 +1313172885 +1313835444 +1319343533 +1320400771 +1328590923 +1340486162 +1346753281 +1354324795 +1373294480 +1382006124 +1382921328 +1401271790 +1401641693 +1405326847 +1426822522 +1442483670 +1465471754 +1467747766 +1481390053 +1492842946 +1498795122 +1500600798 +1501139082 +1501200000 +1537820303 +1544341958 +1545808690 +1560678754 +1562213912 +1579036646 +1584279164 +1588049383 +1595203260 +1602699093 +1605577377 +1624415312 +1624578741 +1630616373 +1652303744 +1686687763 +1690364826 +1733824563 +1739103467 +1769822884 +1773424838 +1803750610 +1807002289 +1808521302 +1822684341 +1828161971 +1835142148 +1838324182 +1845225224 +1853696443 +1898923995 +1905182270 +1913108997 +1959295288 +1967312227 +1967323190 +1970064530 +2005908625 +2007224344 +2007823514 +2010436661 +2015433009 +2043866091 +2062083345 +2062719440 +2068638613 +2073354402 +2085425390 +2087287575 +2097621830 +2126516983 +2132836767 +2139335348 +2141065397 +2143559813 +2162167160 +2166443110 +2185473740 +2192059776 +2209544259 +2241707795 +2252575182 +2256562616 +2270958676 +2273931246 +2293233363 +2319060076 +2338718760 +2340633105 +2342124049 +2342381143 +2349016313 +2399203983 +2452995576 +2491888820 +2492146501 +2530037735 +2532541028 +2534400511 +2555076489 +2568212709 +2576835838 +2579588877 +2586439425 +2586554977 +2666797935 +2671108363 +2689502728 +2706664774 +2742203972 +2752688285 +2761946533 +2798567280 +2832231589 +2839123365 +2862511736 +2865449967 +2868893050 +2920621038 +2961853978 +2963394789 +2973279064 +2983360040 +2999286455 +3009507338 +3027701347 +3044099794 +3045807206 +3046727776 +3068811017 +3111297391 +3114836741 +3140661415 +3141246591 +3143999618 +3174074558 +3183547849 +3184517673 +3202189619 +3235145197 +3240830147 +3244477628 +3258401079 +3259062887 +3325425846 +3342063943 +3360713955 +3361294749 +3362440323 +3388748623 +3396396549 +3402847137 +3409011964 +3431328488 +3460734977 +3486358693 +3502420645 +3504492886 +3504731226 +3515654434 +3520782752 +3525442456 +3534459381 +3577538843 +3592830569 +3660083336 +3684745565 +3698660010 +3734720474 +3807649110 +3815239683 +3841060475 +3854097533 +3857047153 +3859620760 +3860705625 +3866076017 +3903228748 +3914912996 +3927934149 +4033899362 +4067721006 +4072302660 +4095742493 +4113653362 +4142342163 +4259437485 +4269285597 +4272549203 +4292361625 +4295972311 +4303456068 +4366629956 +4501383251 +4502792062 +4506603467 +4542267679 +4549109833 +4557490354 +4559949286 +4579530164 +4579597207 +4598618506 +4692675353 +4743211146 +4749808601 +4767922558 +4779601797 +4803539356 +4823463893 +4842868356 +4907458502 +4940301320 +4940580436 +4955035353 +4988631386 +4993254694 +5005385376 +5005501668 +5005690577 +5005690577 +5006400908 +5006401040 +5006401040 +5006401040 +5006401040 +5006401040 +5006589905 +5016829727 +5018662003 +5021439761 +5047663460 +5060719070 +5097623546 +5100830925 +5114922901 +5122521586 +5172169595 +5181203855 +5183914431 +5204234546 +5250307114 +5266515615 +5295411616 +5332739649 +5341736360 +5383518020 +5396794817 +5399069147 +5421133387 +5477524588 +5495576820 +5505087142 +5505260529 +5505449262 +5505634736 +5505826992 +5506634739 +5506823648 +5508627200 +5534346013 +5585614991 +5611705943 +5643104132 +5647630894 +5729819308 +5766811717 +5777870727 +5805804939 +5807729763 +5817089850 +5828192999 +5865827814 +5902168208 +5915429018 +5922701064 +5926679611 +5927242564 +5953961242 +6008222335 +6043495827 +6108812087 +6119945026 +6192921948 +6235559617 +6287073701 +6357800530 +6361179346 +6361824303 +6379905318 +6545108724 +6570051739 +6625925994 +6647683557 +6707636362 +6708854687 +6734321082 +6773072547 +6777251649 +6954077606 +6961520218 +6977766329 +6995401709 +7036603226 +7060811542 +7174319745 +7190833552 +7195455435 +7212598776 +7238825810 +7283963802 +7341936445 +7395261117 +7406315985 +7493027773 +7526077830 +7555735877 +7594177636 +7707423908 +7727136525 +7786285385 +7860850235 +7907549576 +8009081322 +8012919654 +8060329280 +8141162421 +8193054356 +8208256175 +8247425397 +8268167106 +8284335119 +8368432191 +8387367396 +8413284648 +8490580319 +8561276755 +8573062334 +8575953329 +8631314979 +8677497309 +8749648203 +8780532788 +8858762849 +8977645645 +8988304031 +9028150574 +9095700179 +9121677991 +9121743535 +9308804645 +9525183073 +9665378771 +10000033939 +10001826841 +10010883882 +10023790644 +10062447266 +10093542993 +10104234572 +10137954961 +10142080850 +10175696117 +10193697827 +10201810681 +10206841039 +10274361569 +10286953804 +10297450331 +10301698801 +10314134659 +10331029925 +10332251008 +10417664878 +10440076907 +10473829979 +10476196439 +10495223149 +10573027034 +10716764409 +10731313434 +10754655804 +10857952418 +11061408070 +11083547903 +11104025578 +11273564695 +11301534858 +11313808040 +11325084428 +11480492451 +11536676262 +11625848783 +11682509253 +11744806827 +11776778617 +11850295212 +11859791909 +11970400153 +12037639443 +12060992506 +12202381821 +12297455276 +12327417890 +12363226671 +12365615288 +12381954972 +12395137882 +12422119858 +12457455168 +12625637976 +12655342922 +12674172223 +12722930793 +12771028015 +12821769312 +12981370864 +13051110200 +13102218292 +13118010042 +13216000539 +13456933998 +13574730253 +13819890288 +13905752028 +14119689781 +14476153680 +14533528790 +14804902888 +14805657811 +14986194862 +15138493118 +15160177348 +15245732530 +15353472193 +15512924144 +15525042189 +15645243685 +15966985610 +16022950283 +16028088873 +16062989388 +16119110438 +16259313487 +16350597558 +16429803195 +16605982476 +17012014811 +17154042465 +17251914497 +17711546284 +17853779131 +18026761778 +18083506410 +18137202111 +18275420906 +18497395549 +19002597457 +19359460156 +19378143795 +19503536547 +19640603255 +20027820181 +20156195509 +20369775749 +20419669518 +20497620862 +20559133742 +20684441149 +20736188560 +20755159837 +20825937233 +21011982349 +21269084948 +21274559773 +21284271597 +21382320648 +21504128708 +21578046232 +21658425894 +21927758500 +22037975299 +22094139443 +22230526013 +22836315543 +22935323440 +23086771822 +23332897048 +23346286872 +23410106289 +23836128105 +25130034791 +25180782550 +25207035311 +25260930066 +25539160274 +26132088633 +26365745442 +26563959405 +26585723383 +26641381084 +26726358705 +27881594320 +28101403275 +28159365230 +28679053639 +28772028944 +28876279824 +28889034933 +28893162406 +29436678010 +29681999080 +29755512977 +29780998084 +29942873966 +30049710114 +30471557042 +30506174005 +30648988302 +30895048883 +30901318724 +30945183151 +31019794875 +31044398950 +31236944012 +31442900570 +31761336266 +32053366269 +32201955613 +32453689363 +32758869134 +32780750451 +33635486176 +33807992913 +34506120042 +34533711042 +34669757721 +34973360583 +35249722947 +35392451029 +35439518169 +35567330507 +36333543923 +36375194089 +36732618442 +36763175545 +36821812033 +37093780787 +37172350432 +37679092194 +37755849359 +37909806327 +37932825619 +38412037746 +38455975003 +38491365864 +38610581044 +38715417450 +38755787273 +40406361751 +40416256640 +40459562385 +40599249445 +41226879055 +41263458389 +42014878868 +42046187030 +42119698538 +42724198820 +43048912307 +43696716372 +43851653916 +43883145909 +44424150430 +44970433517 +45200111572 +45449551579 +45582479317 +46096646397 +46171889046 +46511690352 +46942688890 +47098749612 +47362516149 +47532941355 +48239052081 +48740181896 +50543029862 +51057597291 +51093675235 +51363919295 +51426670597 +51498021487 +51618797986 +51894695967 +51989720521 +52419779401 +52746402628 +54181642493 +55853918006 +56403104253 +56613334998 +56658474015 +56881972951 +56956829509 +57436266933 +57669488002 +58121060645 +58610815355 +58718251619 +58740242561 +59327791580 +59794233350 +60376629368 +60737966607 +61022927501 +61488192179 +62559153870 +63737270819 +64680248179 +64692695532 +64708952944 +64761704205 +65156104703 +65583351883 +65842383704 +66173843155 +67173559142 +67389473956 +67414232189 +67629366480 +67906613271 +69181849476 +70690441386 +70806200266 +71538558467 +73254481881 +73744493698 +73924633882 +74597368355 +75067476136 +75300883750 +75376430684 +75440360129 +76305536831 +76360000535 +76848546548 +76999055527 +77524591324 +77998664841 +78134828598 +78242900629 +78368540603 +79064114458 +79828373161 +79892456722 +79951438824 +81068435024 +81563015911 +81958617748 +82617644325 +82858038172 +83388550077 +83736484761 +83777758895 +83787742296 +84727971052 +85477520224 +86226544069 +86565466794 +86786669750 +87143158212 +87681694224 +88742128596 +88849236744 +90570918088 +91738653832 +91856338057 +92117088534 +92368115005 +93154145932 +95117508695 +95430360763 +97497796080 +97965445233 +98500201513 +100002251543 +100124896006 +100980617482 +101110103171 +101448568036 +101747256080 +101951287458 +102389085054 +103520598372 +103838707406 +105611356519 +107322115355 +107355973557 +107651232857 +107845306226 +107928631903 +108640433339 +108851896469 +108868940600 +109870574167 +110503354467 +115701836754 +115935409241 +116225897748 +116315500671 +116419626218 +116692475134 +116891017787 +117606385727 +118423871629 +118437973249 +118632640412 +118707045047 +119447489391 +120419552566 +120445856915 +121275518304 +121347510881 +122448430926 +122680092731 +122691741048 +122773196807 +123046192099 +123932352700 +124124412269 +124466900441 +124497618310 +125759890444 +127244136823 +128498053663 +129213055409 +130379542594 +131488285000 +131777077775 +132495587187 +136155897212 +136264384696 +136865597655 +138493509592 +138729159296 +139246820627 +140030737959 +140154026602 +140793121550 +141588606874 +143477686641 +144259481021 +144769697700 +145048081515 +145471448917 +146159307276 +148023434212 +150646234077 +150990903879 +151827719039 +152017274751 +155395940655 +155819572975 +156188730232 +156701987685 +156770681542 +156830050368 +157363022784 +157397795975 +158285748746 +159047643241 +159099349162 +160190415635 +161144135898 +162183694155 +163290152906 +164062329723 +164171388354 +164257660708 +165160631845 +165425486277 +166230845878 +168261067322 +169124857216 +169901452799 +170514030090 +173785560841 +174768816778 +175209148928 +177792898579 +177859998667 +182631650350 +183491319493 +184022723939 +185721071907 +187385838025 +188181775959 +188399585263 +188966518017 +189420472746 +189897551269 +190601514677 +190952015081 +191324711178 +192650066636 +194729861615 +195499865671 +198870387164 +199193959974 +200009081675 +200414405326 +200861864639 +201173339755 +201581393855 +202484918830 +204276853130 +209480669485 +211285430613 +215103827469 +215552282283 +220457266096 +221501835551 +222235025833 +224762055997 +225101040553 +226618495961 +227757047018 +230206986339 +230799774550 +231314162581 +233635612528 +233765375302 +235830381736 +236509252810 +237244414158 +239303468804 +243295285674 +244485397841 +245443412938 +246647767653 +247959713760 +248130386655 +252249811901 +254508056659 +256506358884 +256806893472 +257408257735 +258003544654 +259449614310 +260611040589 +262518180117 +263317376715 +263445027395 +264324253435 +265342954220 +265433241245 +266400018079 +267327138657 +268697291304 +270568924783 +271942513406 +272148243673 +274128587892 +276033019038 +276797894091 +277999467527 +278752939545 +279358143398 +279399369865 +280551725854 +281378895760 +283214877277 +283379867269 +283689643618 +284927303171 +286912977002 +287807735376 +292137416965 +293023987700 +293238876990 +293865163806 +294338468147 +294386452520 +295337482554 +296829237385 +296970592431 +303546080640 +306360486151 +307346397947 +307533350478 +308088866751 +308835047330 +311286195318 +313548566009 +314005881820 +314650772794 +317846375987 +318428120386 +319034806839 +327188466156 +327482558930 +328398820066 +328489526185 +329868760079 +330488707117 +332258617416 +337264175807 +342758712955 +344746395150 +346834795177 +349892470613 +350755812150 +352217104242 +354266180810 +355041364568 +358221703479 +358815870038 +359092532403 +360611052126 +369492586994 +370161623457 +371294192712 +375106443202 +379951534327 +381111795688 +383341646941 +385838343190 +386759362065 +386813244977 +389231871367 +391475562498 +392141854226 +393612145616 +394749552839 +396435834415 +397311536557 +398550120289 +399108161505 +401506917399 +405132997666 +407773623183 +407857010642 +408890316943 +410769242936 +413205991613 +413436405205 +413710862256 +417201219245 +418318751381 +419212462590 +420826767965 +421064776219 +423860985814 +426044227736 +428131521084 +431206278328 +435538751686 +437590601745 +448159504747 +449909279041 +456002233589 +460799806976 +461948969105 +462093112878 +465614953659 +465731483948 +470877968051 +475087547994 +475835246300 +476767312495 +478303267912 +485499675015 +486580658158 +492922713648 +495195134516 +495357114253 +500547381872 +500596183796 +504167539419 +505317479725 +506108599440 +509734839293 +510672042186 +510946167440 +513446525914 +514156590931 +514798273672 +514859454894 +520002711209 +520217253592 +520393317273 +520661052453 +520959313694 +523243202837 +525914737845 +526097070311 +527515664605 +527541239362 +528692169102 +530163163287 +530173229222 +530362850103 +532339837747 +533262360730 +535237262100 +537816805485 +542276074299 +542914557302 +545733300588 +547044467935 +548718392107 +551271747390 +573284904357 +576092477588 +579978033195 +580750797719 +582161955806 +586260656042 +591634337324 +594939021405 +595378103564 +596053482764 +600951285655 +602648007357 +604022648302 +604405292520 +605706474929 +613683439988 +615786335049 +618136497166 +618590451318 +620466339003 +622398325515 +628638469617 +634699462789 +635554403735 +637984726897 +640165680899 +640183852072 +642448592379 +643815318534 +644146412440 +647805776992 +648268688767 +651722061473 +677997464709 +696091472094 +697566995100 +698633952485 +701093077461 +702749267347 +706543961140 +707528931409 +709940472678 +711587645304 +712979301322 +713218865614 +716638461532 +720541263126 +724206506715 +726593833513 +727120076799 +729378049534 +731418885462 +733872025204 +735674806709 +739586153236 +742205005946 +744813796439 +747895643148 +758274322503 +763611243409 +768323099140 +769710838221 +773646119814 +781871810962 +787401476042 +801327963266 +809145452687 +810414047483 +811952735421 +813971948955 +814135569319 +814734789631 +815707002454 +826448203031 +828147045403 +832075518805 +832230831789 +838263643813 +842842897117 +852752082878 +859164041381 +861612406503 +866246026535 +877629899833 +895147199129 +896707526826 +899364380926 +924751448855 +924775807784 +925978946887 +933357944250 +935320506111 +935768166773 +936111364447 +939266141586 +944333314660 +946680971295 +948779349995 +951702355461 +956162534261 +961744285530 +970437060329 +975860780021 +990081619861 +1002096877670 +1002721079957 +1008902523996 +1012932161709 +1014837220166 +1019147419372 +1027799279335 +1035385601028 +1036679908402 +1038306862038 +1042977399630 +1043857640144 +1053599166145 +1058831066281 +1062455585779 +1069876313136 +1084553604545 +1088702129707 +1089448464031 +1090583092959 +1091341973674 +1100678509810 +1103598243324 +1105407774844 +1108139907570 +1108390872015 +1110245174594 +1111466830953 +1111876970145 +1111924428460 +1115220904935 +1117142495686 +1121324932459 +1123850881327 +1132351217231 +1154986442787 +1155973510209 +1157870029385 +1161184465044 +1167539167495 +1176171106238 +1178302678850 +1179701909886 +1180187184702 +1182537055173 +1184452480083 +1198995830704 +1201470968087 +1202342502716 +1203872994193 +1205927040405 +1215663779345 +1221910101003 +1222896391352 +1222929944158 +1223513210665 +1240746735820 +1242688799830 +1248974512783 +1264540834444 +1265300911448 +1266228342137 +1267832176477 +1268120112068 +1268420081016 +1283654728932 +1287022767413 +1297361846417 +1313371123155 +1331265277802 +1341849281813 +1355010935164 +1357229927512 +1358661990357 +1359008507383 +1365014832129 +1371571440660 +1373520626087 +1377865519182 +1382725996265 +1393530857958 +1410728024685 +1425957256291 +1426754039186 +1436334877866 +1443883972608 +1448923155903 +1455575747622 +1457017046664 +1462364025508 +1466290455083 +1471295325796 +1487221729674 +1498094368308 +1513511418970 +1519955370351 +1529020356200 +1530337425580 +1534378993812 +1536105721591 +1549024352184 +1549131913250 +1557013771808 +1566681704349 +1569827230828 +1573039813770 +1574297205268 +1575770577904 +1581269015957 +1591257594860 +1593206021622 +1610320331720 +1611569193469 +1618445651654 +1630551306049 +1657749877994 +1665466184445 +1668815241422 +1671684832337 +1672186241423 +1675296094686 +1690510807390 +1697253551352 +1703801489696 +1711298089082 +1761754506039 +1769132691906 +1771734493320 +1797773173306 +1802669955700 +1821851618882 +1828377461571 +1835091391390 +1843457989908 +1869471443836 +1887383962419 +1888612747330 +1891798507378 +1905663515264 +1909306650875 +1949324649919 +1958251550190 +1961011348197 +1984686368781 +2022381891369 +2039225715195 +2070917753613 +2080497735669 +2081234875837 +2088548981239 +2100710744297 +2104066198082 +2106335600600 +2108318475629 +2108515787747 +2110733189934 +2118696330405 +2124422082074 +2127149862331 +2129987566582 +2130045224469 +2130348779972 +2132880719930 +2138846240432 +2155781419051 +2163836386756 +2204327233148 +2209186114600 +2211273115878 +2213751347783 +2228013239238 +2230455947971 +2262704684807 +2263326560884 +2273335314661 +2284810128793 +2291231629358 +2308573849411 +2370921051787 +2388758849424 +2395459336060 +2414038379562 +2420554753212 +2432652958722 +2434430554874 +2454600213786 +2470540624340 +2474854884684 +2478440946692 +2483389985062 +2490953995995 +2492850753164 +2526248919724 +2528983157915 +2539178011650 +2540449429286 +2545967508081 +2563744451020 +2585158437170 +2589326850320 +2595457117612 +2622906870830 +2636626261941 +2644859030393 +2665570420990 +2681818823480 +2701165602316 +2720394114778 +2727132528019 +2733642227724 +2734714860798 +2754239329576 +2772986518524 +2802286013045 +2807784524271 +2847054476440 +2847905940158 +2851305496636 +2875790032159 +2885551796048 +2889912582034 +2907511079862 +2910929252888 +2930644427541 +2931178210195 +2939956839483 +2943798666003 +2971539488535 +2972877883467 +2992264998318 +2996635675787 +3006826252864 +3060254752072 +3068252623157 +3074537110444 +3084018572905 +3085589837412 +3109258203177 +3121869316899 +3130540965062 +3151455838728 +3156812236136 +3159218682860 +3181410587466 +3194918409134 +3197164400658 +3205096169109 +3212035146554 +3227648050616 +3233656903291 +3239937249577 +3251373905068 +3257436485027 +3259051365784 +3273222196127 +3288931839421 +3302278041729 +3312523712926 +3319302941208 +3346429071419 +3346769049295 +3389101395468 +3401444294704 +3433864680270 +3447933587633 +3449736675062 +3454326043767 +3473654362804 +3581744862376 +3602081620697 +3633430459227 +3653578834649 +3673118677505 +3678920535733 +3710448455762 +3719225384855 +3726355626576 +3744728191746 +3765864787072 +3768061285463 +3775915469648 +3789127372692 +3815463923919 +3827523755071 +3831057693409 +3840258282139 +3864986527307 +3868622815530 +3891885408728 +3893652933231 +3920563270509 +3928659740104 +3934569920014 +3945857662557 +3963442063151 +3985171394224 +3989293833292 +3989689549098 +3994377884903 +4002425205172 +4010235351886 +4018800527188 +4090929258798 +4112056644392 +4118544445195 +4146440165563 +4161768411916 +4231050879575 +4239927041231 +4290269178843 +4292506047793 +4306424078369 +4331376158295 +4343704937539 +4360681260808 +4391766680585 +4410938188313 +4424735098799 +4425398054308 +4442848766368 +4519272073227 +4523515747284 +4545459324134 +4565221336398 +4609681074555 +4620419763968 +4625838628241 +4642656745035 +4643939762419 +4647173109584 +4719860702072 +4797052678428 +4803401496110 +4830944117381 +4851730258812 +4860715205655 +4870872723908 +4880943806128 +4903496636302 +4906873688593 +4917689075988 +4922154993819 +4975601748411 +4997229164240 +5007845036594 +5007847962996 +5011900894961 +5014501903991 +5023405154253 +5038684394734 +5041645942572 +5052306838466 +5073045918573 +5126949818291 +5147848753944 +5168256331471 +5187386849017 +5208987141790 +5239187070708 +5243452039720 +5251774457879 +5272741953694 +5277696551287 +5306820006882 +5310586222397 +5322329904842 +5353211721226 +5354916904868 +5365270392915 +5375983232842 +5411653563759 +5433015425802 +5452421177310 +5501020844678 +5530137563626 +5584791789410 +5586808807311 +5671680717522 +5681796011247 +5735063435950 +5753215012797 +5803397537546 +5825747978564 +5838857509208 +5891382275491 +5940914635774 +5945221183115 +5982191448874 +5985547937980 +6001187486126 +6004170243657 +6006595313861 +6037513372055 +6061858213194 +6069842249361 +6091917990723 +6103969032335 +6354604718717 +6363867458095 +6458265901894 +6462806991812 +6486180807221 +6497818582394 +6513115921848 +6544867323745 +6567583604016 +6587320538189 +6649412990088 +6675436149309 +6762487404254 +6822862112299 +6886045598604 +6907172453979 +7002729789983 +7024251933006 +7100777506783 +7111182544839 +7127786978748 +7147367653235 +7183688230049 +7211492408617 +7237003993001 +7239558367362 +7322918356285 +7353805429278 +7369829218926 +7418711255310 +7459816909815 +7481144294403 +7512590604359 +7555197059454 +7630462255675 +7655449241557 +7680734432681 +7691788100976 +7730817674920 +7781087680357 +7849289629914 +7906750150420 +7920402999349 +7922993952830 +7969780394253 +7994306279679 +8002994231434 +8005198467513 +8046000988760 +8179013183878 +8186651526118 +8215009561350 +8221747675307 +8244890021204 +8254098468688 +8263983603499 +8268652533988 +8278258914306 +8291876993500 +8383997519204 +8395993834186 +8574568065517 +8685842093257 +8716074802133 +8766721903256 +8781564027163 +8823775038736 +8893429952214 +8923923123872 +8955524834810 +9095081583023 +9103797903084 +9107162823637 +9142972015174 +9184715518183 +9196775120753 +9214215969712 +9235387380786 +9388043047445 +9584784938495 +9768160905794 +9769327359837 +9843857474078 +9864253394643 +9923668059179 +9943691370362 +9959681312986 +9998527123598 +10024903056907 +10057208780963 +10081176486240 +10106114602262 +10133875950499 +10146273676448 +10169379380988 +10234158942534 +10294127533453 +10324951186348 +10344950015104 +10345088517256 +10364416080816 +10431916639629 +10441423719763 +10547042820290 +10648587982528 +10722247243007 +10732543701060 +10795104419870 +10965098486837 +10994789210770 +11039689757553 +11099179169413 +11118372242960 +11241884568199 +11345855149219 +11383459822195 +11398477513327 +11495307691233 +11586189091478 +11628475621507 +11748306138602 +11796855492777 +11813586308455 +11826152696548 +11940850778268 +12010423971954 +12171456441522 +12229115923557 +12383791009354 +12473831580008 +12590056964801 +12603473794177 +12768876707037 +12808729278487 +12858757395462 +12901010577203 +12914573045771 +13035474222521 +13140622043219 +13145118189548 +13248128527415 +13259503360129 +13366686605793 +13751768279359 +13776245864767 +13928678261260 +14034252970160 +14035438374996 +14078133277013 +14126598956174 +14169802258166 +14278617321444 +14591077301431 +14597243119372 +14633148218886 +14765114041019 +14975879453899 +15001876644068 +15046238316767 +15060973788698 +15396145547106 +15495161009753 +15641724037702 +15680694844877 +15909981951624 +15932614550346 +15999899974033 +16146565370552 +16212456828032 +16259533930611 +16292463002055 +16295762999484 +16334718444739 +16406610298479 +16433866256837 +16515331452488 +16580593323767 +17008738046634 +17090527756683 +17093694809208 +17349395330187 +17363896543728 +17426265570609 +17454808974989 +17521390277458 +17595087717173 +17699891837444 +17750236611402 +17835047847578 +18010556491355 +18169245932897 +18226845677602 +18387881776609 +18434082949772 +18483866033648 +18488161361436 +18524529426270 +18607749349764 +18633371428001 +18673701869253 +18805090568523 +18807777483377 +19081145754783 +19082106508322 +19086796420235 +19219699318509 +19293026221244 +19388867527055 +19483281954695 +19502067141825 +19561444861263 +19653445790449 +19784891084316 +20072305649281 +20118333462077 +20272137005170 +20347695927606 +20355007729311 +20387074111952 +20497775819813 +20763669576250 +20797408112833 +20801515130390 +20887098503426 +20949968319457 +20954215265712 +21046576310079 +21248866693564 +21283720594337 +21331454277029 +21337038326883 +21369010814940 +21429447057554 +21463867671278 +21539004203004 +21636659826711 +21764680991706 +21798614845705 +21806209677029 +21827961662344 +21964409079484 +22002886417707 +22138846987813 +22159217994844 +22201677157591 +22284992026012 +22351411692977 +22438129122682 +22460043845751 +22637520978820 +22638636983298 +22773742712479 +22845848695932 +22846357887730 +22926819396967 +22954929429909 +22990163251540 +22991322423540 +23039114447608 +23108690973052 +23207626880092 +23299286184895 +23446754149429 +23611599614995 +23833718680000 +23850432225194 +23990094055417 +24117948051449 +24147534375179 +24178696458856 +24267302347766 +24322861209215 +24483558968885 +24575502658708 +24688127873247 +24838994564812 +24911225949163 +24927670207580 +24969134375782 +25437012545190 +25729949054145 +25850368884858 +25902266906358 +25948530003537 +26263505351360 +26413621235305 +26419477407821 +26427815763119 +26530751303777 +26563854840530 +26965220420854 +27246866472070 +27354610145901 +27421400948156 +27444170474144 +27551476326836 +27576097985201 +27660181380349 +27756346208495 +27760593517068 +27769942780089 +27967464333113 +28135058153386 +28144580867047 +28164504216186 +28188062531292 +28236288124967 +28271427162612 +28289958871469 +28311339929384 +28317103634705 +28354916359953 +28372962536580 +28406305878224 +28412419351276 +28506007004489 +28535178859933 +28692721650377 +29178177520957 +29230621851622 +29311742898993 +29475026965666 +29548791252655 +29823176119932 +29973448643876 +30122802759415 +30181325601197 +30228757186018 +30308042485227 +30441490566271 +30625890139190 +30700246779200 +30850164623329 +30872523284682 +30904888260986 +31145363432749 +31282259103816 +31432004963044 +31660847229251 +31829364518210 +31877024929349 +31957180214446 +31964327357713 +32110994695471 +32113025974494 +32114658506800 +32118867243425 +32124135899176 +32124921914061 +32125739604889 +32130420871909 +32131593807669 +32134852593809 +32136014548641 +32142022342405 +32151772381681 +32159075789321 +32171950188469 +32177775222956 +32181031175618 +32215030806375 +32221471147728 +32239410500332 +32245377078446 +32252776824722 +32272517772915 +32344623180508 +32431561189012 +32492152956117 +32525143956857 +32578674509958 +32605267125021 +32694742838666 +32752564626995 +33032529635783 +33067769087757 +33561128419070 +33863610663360 +33893048444431 +34094998908587 +34411387078058 +34729173755157 +34974104633399 +35010047778434 +35013470690773 +35023554392404 +35024821321820 +35031695623233 +35064068947361 +35075508438201 +35094706123313 +35104497888983 +35119623237583 +35171833054264 +35579356341043 +35580540670111 +35719387593268 +35775988504284 +35888490677462 +35949605332719 +35965754842350 +35971025161578 +36081141695191 +36113440967660 +36284163647213 +36502364254840 +36620963746877 +36675610554935 +36748240019307 +36837382654086 +37099352345748 +37351498960510 +37511916672940 +38215680859493 +38228463521566 +38255553531993 +38413453958642 +38704383673896 +38798371953187 +38822048380308 +39039485131162 +39408798476202 +39934331449133 +40108071256930 +40175908906550 +40316016316313 +40373373320846 +40407391213013 +40911686260868 +41477406651574 +41764111352922 +41843303362307 +42000125596639 +42134707478398 +42327003215637 +42534577079033 +42855021542256 +43081924757946 +43189677084026 +43618383750128 +43741324343485 +44028688899118 +44053472985208 +44465587564376 +44493275860677 +44575288150090 +44581568489238 +44587176570272 +44819806651637 +44897700877507 +45497362558714 +45871519069003 +46289836111659 +46344868654263 +46421669292882 +46424547656014 +46496709778549 +46624507537717 +47146421230353 +47298972548174 +48088517484196 +48127469505482 +48346201993952 +49241515478591 +49361018334471 +49495711320428 +49550367386432 +49565582743815 +49687074939503 +49999906543209 +50000000000000 +50000000000000 +50000106630058 +50000337393995 +50006996286899 +50010593368183 +50039297497365 +50058311777181 +50099648350997 +50121787543637 +50428173388468 +50785923423179 +50924277399281 +51461186712937 +51613463696352 +51821307581578 +52163672815765 +52186008455721 +52192028614357 +52287381596278 +52521167119823 +52574523710158 +52672458276396 +52804150267636 +53069438869761 +53420006685525 +53487713930786 +53800543308113 +53826992703929 +54024493509490 +54337311314914 +54887012418993 +54901897553855 +55227614875369 +55228599920001 +55524304104656 +55877163945938 +55931629388075 +56337210599311 +56343378039530 +56371414093476 +56770746140763 +57036014695640 +57411476446828 +57591766903156 +57639038789953 +58077963325046 +58125719417731 +58151535988236 +58495298334169 +58672610426914 +59237705210131 +59298262140915 +59519641402838 +59631146040043 +60223264077831 +60364168943206 +60426036428227 +60661075871207 +60689245854036 +60866252099702 +60945585426179 +60956808355665 +61930640708589 +62061601639436 +62234124269205 +62243043607799 +62569005106546 +62732994327293 +62805624875144 +63163980006292 +63174145980378 +63333506894818 +64175744606748 +64249465998446 +64328596815617 +64328655986831 +64329498883566 +64372570992762 +64550272376622 +64606076581686 +64968482197256 +65765735341742 +66051038895212 +66479529512465 +66718083708209 +66741511006189 +67095062349663 +67431015997117 +67456548948609 +67606754148021 +68393047347237 +69071328982290 +69174369087661 +69181749385449 +69277278118852 +69321516629824 +69382565518506 +69502760172144 +69818576461956 +69903834130025 +70019238278444 +70020758635779 +70022408630916 +70022667538006 +70023046591689 +70023990860835 +70024942523372 +70025328553301 +70025890876285 +70026745865418 +70028060031468 +70028686954959 +70029144109562 +70029432493234 +70029517899411 +70032542305696 +70038175911360 +70039463406061 +70044600421852 +70044911919558 +70053716693439 +70066245367167 +70189151364856 +70216158793643 +70233652198178 +70266544438145 +70308652345002 +70356129987956 +70502118999158 +70588973570551 +70676678899417 +70707573083215 +70724839070648 +70739720775539 +70740113610310 +70744799431876 +70850693571020 +70856850969228 +70961177672030 +70964170251274 +71104638695344 +71127936500591 +71233804334119 +71497798654021 +71540208858243 +71606595177636 +71624604381104 +71821465793254 +72635299340538 +72796726523418 +72860332258242 +72867187067984 +73010429509244 +73067096648391 +73502527004769 +73548916086020 +73822070202199 +74008203416928 +74009887611183 +74398773861300 +74556629896383 +74692372306901 +74749105076196 +75122028642077 +105408513666370 diff --git a/lambda-calcul/rust/proptest-regressions/ast.txt b/lambda-calcul/rust/proptest-regressions/ast.txt new file mode 100644 index 0000000..7a8c8d1 --- /dev/null +++ b/lambda-calcul/rust/proptest-regressions/ast.txt @@ -0,0 +1,7 @@ +# Seeds for failure cases proptest has generated in the past. It is +# automatically read and these particular cases re-run before any +# novel cases are generated. +# +# It is recommended to check this file in to source control so that +# everyone who runs the test benefits from these saved cases. +cc 5ce217238e9cf11ab2c5369b545fd374a630a943184d4b61579b65aa4d8f49b8 # shrinks to mut atoms = [Sym("ꧠ"), Sym("ቊ")] diff --git a/lambda-calcul/rust/proptest-regressions/lambda.txt b/lambda-calcul/rust/proptest-regressions/lambda.txt new file mode 100644 index 0000000..2867930 --- /dev/null +++ b/lambda-calcul/rust/proptest-regressions/lambda.txt @@ -0,0 +1,7 @@ +# Seeds for failure cases proptest has generated in the past. It is +# automatically read and these particular cases re-run before any +# novel cases are generated. +# +# It is recommended to check this file in to source control so that +# everyone who runs the test benefits from these saved cases. +cc 1589680cd328dc53046b4c3d6dd3956c643d75b4a8cdca25b69acfc4b5e80070 # shrinks to i = 0 diff --git a/lambda-calcul/rust/proptest-regressions/parser.txt b/lambda-calcul/rust/proptest-regressions/parser.txt new file mode 100644 index 0000000..cd13f63 --- /dev/null +++ b/lambda-calcul/rust/proptest-regressions/parser.txt @@ -0,0 +1,7 @@ +# Seeds for failure cases proptest has generated in the past. It is +# automatically read and these particular cases re-run before any +# novel cases are generated. +# +# It is recommended to check this file in to source control so that +# everyone who runs the test benefits from these saved cases. +cc 369f514eb0f4e92e4809a33e1af32452801757a413be00426c99ba26bead4fa9 # shrinks to values = [Sym(" ")] diff --git a/lambda-calcul/rust/sample/test.txt b/lambda-calcul/rust/sample/test.txt new file mode 100644 index 0000000..76dc68a --- /dev/null +++ b/lambda-calcul/rust/sample/test.txt @@ -0,0 +1,5 @@ +12 +foo + true + +(x x) diff --git a/lambda-calcul/rust/sample/test01/input b/lambda-calcul/rust/sample/test01/input new file mode 100644 index 0000000..48082f7 --- /dev/null +++ b/lambda-calcul/rust/sample/test01/input @@ -0,0 +1 @@ +12 diff --git a/lambda-calcul/rust/sample/test01/output b/lambda-calcul/rust/sample/test01/output new file mode 100644 index 0000000..48082f7 --- /dev/null +++ b/lambda-calcul/rust/sample/test01/output @@ -0,0 +1 @@ +12 diff --git a/lambda-calcul/rust/sample/test02/input b/lambda-calcul/rust/sample/test02/input new file mode 100644 index 0000000..81a0443 --- /dev/null +++ b/lambda-calcul/rust/sample/test02/input @@ -0,0 +1,6 @@ +(def pair (lam (a b f) (f a b))) + +(def fst (lam p (p (lam ( a b) a)))) +(def snd (lam p (p (lam ( a b) b)))) + +(fst (snd (pair 1 (pair 2 0)))) diff --git a/lambda-calcul/rust/sample/test02/output b/lambda-calcul/rust/sample/test02/output new file mode 100644 index 0000000..c61e10e --- /dev/null +++ b/lambda-calcul/rust/sample/test02/output @@ -0,0 +1,4 @@ +true +true +true +2 diff --git a/lambda-calcul/rust/sample/test03/input b/lambda-calcul/rust/sample/test03/input new file mode 100644 index 0000000..6cff466 --- /dev/null +++ b/lambda-calcul/rust/sample/test03/input @@ -0,0 +1,12 @@ +(def zero (lam (f s) s)) +(def succ (lam (n f s) (f (n f s)))) + +(def one (succ zero)) +(def two (succ one)) +(def three (succ two)) +(def four (succ three)) +(def five (succ four)) + +(def plus (lam (a b f s) (a f (b f s)))) + +(plus one three) diff --git a/lambda-calcul/rust/sample/test03/output b/lambda-calcul/rust/sample/test03/output new file mode 100644 index 0000000..fd56297 --- /dev/null +++ b/lambda-calcul/rust/sample/test03/output @@ -0,0 +1,9 @@ +true +true +true +true +true +true +true +true +four diff --git a/lambda-calcul/rust/sample/test_bool.txt b/lambda-calcul/rust/sample/test_bool.txt new file mode 100644 index 0000000..a1b1309 --- /dev/null +++ b/lambda-calcul/rust/sample/test_bool.txt @@ -0,0 +1,15 @@ +(def True (lam (x y) x)) +(def False (lam (x y) y)) +(def and (lam (a b) (a b False))) +(def or (lam (a b) (a True b))) +(def not (lam a (a False True))) + +(and True True) +(and True False) +(and False True) +(and False False) + +(or True True) +(or True False) +(or False True) +(or False False) diff --git a/lambda-calcul/rust/sample/test_full.txt b/lambda-calcul/rust/sample/test_full.txt new file mode 100644 index 0000000..ece76b8 --- /dev/null +++ b/lambda-calcul/rust/sample/test_full.txt @@ -0,0 +1 @@ +(((lam x (lam x x)) 13) true) diff --git a/lambda-calcul/rust/sample/test_let.txt b/lambda-calcul/rust/sample/test_let.txt new file mode 100644 index 0000000..6027cd0 --- /dev/null +++ b/lambda-calcul/rust/sample/test_let.txt @@ -0,0 +1 @@ +(let (foo (lam x x)) ((let (foo foo) foo) 13)) diff --git a/lambda-calcul/rust/sample/test_nat.txt b/lambda-calcul/rust/sample/test_nat.txt new file mode 100644 index 0000000..81a6e9d --- /dev/null +++ b/lambda-calcul/rust/sample/test_nat.txt @@ -0,0 +1,9 @@ +(def pair (lam (a b f) (f a b))) +(def fst (lam p (p (lam (a b) a)))) +(def snd (lam p (p (lam (a b) b)))) + +(def zero (lam (f s) s)) +(def succ (lam (n f s) (f (n f s)))) + +(def is-zero (lam n + (n (lam x False) true))) diff --git a/lambda-calcul/rust/sample/test_normal.txt b/lambda-calcul/rust/sample/test_normal.txt new file mode 100644 index 0000000..00abde9 --- /dev/null +++ b/lambda-calcul/rust/sample/test_normal.txt @@ -0,0 +1 @@ +((lam x 1) ((lam x (x x)) (lam x (x x)))) diff --git a/lambda-calcul/rust/src/ast.rs b/lambda-calcul/rust/src/ast.rs new file mode 100644 index 0000000..d0f1d6f --- /dev/null +++ b/lambda-calcul/rust/src/ast.rs @@ -0,0 +1,117 @@ +use proptest::{ + prelude::*, + string::{string_regex, RegexGeneratorStrategy}, +}; +use serde::{Deserialize, Serialize}; +use std::fmt::{self, Display}; + +#[derive(Debug, PartialEq, Clone, Serialize, Deserialize)] +pub enum Value { + Num(i32), + Bool(bool), + Sym(String), + App(Box<Value>, Box<Value>), + Lam(String, Box<Value>), + Def(String, Box<Value>), + Let(String, Box<Value>, Box<Value>), +} + +use Value::*; + +impl Value { + /// Return the spine of an application + fn spine(&self) -> Vec<Value> { + match self { + App(l, r) => { + let mut spine = l.spine(); + spine.push(*r.clone()); + spine + } + _ => vec![self.clone()], + } + } +} + +impl Display for Value { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Value::Num(i) => write!(f, "{}", i), + Value::Bool(b) => write!(f, "{}", b), + Value::Sym(s) => write!(f, "{}", s), + Value::App(_, _) => { + let app = self + .spine() + .iter() + .map(|v| v.to_string()) + .collect::<Vec<String>>() + .join(" "); + write!(f, "({})", app) + } + Value::Lam(var, body) => write!(f, "(lam {} {})", var, body), + Value::Def(var, value) => write!(f, "(def {} {})", var, value), + Value::Let(var, value, body) => write!(f, "(let ({} {}) {})", var, value, body), + } + } +} + +pub const IDENTIFIER: &str = "\\pL(\\pL|\\pN)*"; + +pub fn identifier() -> RegexGeneratorStrategy<String> { + string_regex(IDENTIFIER).unwrap() +} + +pub fn ascii_identifier() -> RegexGeneratorStrategy<String> { + string_regex("[a-zA-Z][a-zA-Z0-9]*").unwrap() +} + +impl Arbitrary for Value { + type Parameters = (); + type Strategy = BoxedStrategy<Self>; + + fn arbitrary_with(_args: ()) -> Self::Strategy { + let any_num = any::<i32>().prop_map(Num); + let any_bool = any::<bool>().prop_map(Bool); + let leaf = prop_oneof![ + any_num, + any_bool, + // see https://unicode.org/reports/tr18/#General_Category_Property for one letter unicode categories + identifier().prop_map(Sym), + ]; + let expr = leaf.prop_recursive(4, 128, 5, move |inner| { + prop_oneof![ + (inner.clone(), inner.clone()).prop_map(|(l, r)| App(Box::new(l), Box::new(r))), + (identifier(), inner.clone()).prop_map(|(var, body)| Lam(var, Box::new(body))), + (identifier(), inner.clone(), inner.clone()).prop_map(|(var, body, expr)| { + Value::Let(var, Box::new(body), Box::new(expr)) + }), + ] + }); + prop_oneof![ + expr.clone(), + (identifier(), expr).prop_map(|(var, body)| Def(var, Box::new(body))) + ] + .boxed() + } +} + +#[cfg(test)] +mod ast_tests { + + use super::Value::{self, *}; + use proptest::collection::vec; + use proptest::prelude::*; + + proptest! { + + #[test] + fn display_multiple_applications_as_a_sequence(atoms in vec("[a-z]".prop_map(Sym), 2..10)) { + let init = atoms.first().unwrap().clone(); + let value = atoms.iter().skip(1).fold(init, |acc, expr| { + Value::App(Box::new(acc.clone()), Box::new(expr.clone())) + }); + assert_eq!(value.to_string(), + format!("({})", + atoms.iter().map(|v| v.to_string()).collect::<Vec<String>>().join(" "))); + } + } +} diff --git a/lambda-calcul/rust/src/io.rs b/lambda-calcul/rust/src/io.rs new file mode 100644 index 0000000..8c628ba --- /dev/null +++ b/lambda-calcul/rust/src/io.rs @@ -0,0 +1,73 @@ +use std::{ + fs::read_to_string, + io::{BufRead, BufReader, Read, Write}, +}; + +use crate::{ + ast::Value, + lambda::{eval_all, eval_whnf, Environment}, + parser::parse, +}; + +pub fn eval_file(file_name: &str) -> String { + let content = read_to_string(file_name).unwrap(); + let values = parse(&content.to_string()); + eval_all(&values) + .iter() + .map(|v| v.to_string()) + .collect::<Vec<String>>() + .join(" ") +} + +pub fn batch_eval<I: Read, O: Write>(inp: &mut I, outp: &mut O) { + let mut env = Environment::new(); + let mut reader = BufReader::new(inp); + loop { + let mut input = String::new(); + outp.flush().unwrap(); + match reader.read_line(&mut input) { + Ok(0) => break, + Ok(_) => (), + Err(e) => { + writeln!(outp, "{}", e).unwrap(); + break; + } + } + let values = parse(&input); + let results = values + .iter() + .map(|v| eval_whnf(v, &mut env)) + .collect::<Vec<Value>>(); + for result in results { + writeln!(outp, "{}", result).unwrap(); + outp.flush().unwrap(); + } + } +} + +pub fn repl<I: Read, O: Write>(inp: &mut I, outp: &mut O) { + let mut env = Environment::new(); + let mut reader = BufReader::new(inp); + loop { + let mut input = String::new(); + write!(outp, "> ").unwrap(); + outp.flush().unwrap(); + match reader.read_line(&mut input) { + Ok(0) => break, + Ok(_) => (), + Err(e) => { + writeln!(outp, "{}", e).unwrap(); + break; + } + } + let values = parse(&input); + let results = values + .iter() + .map(|v| eval_whnf(v, &mut env)) + .collect::<Vec<Value>>(); + for result in results { + writeln!(outp, "{}", result).unwrap(); + outp.flush().unwrap(); + } + } +} diff --git a/lambda-calcul/rust/src/lambda.rs b/lambda-calcul/rust/src/lambda.rs new file mode 100644 index 0000000..a73ca34 --- /dev/null +++ b/lambda-calcul/rust/src/lambda.rs @@ -0,0 +1,292 @@ +use proptest::{ + arbitrary::any, + prelude::*, + strategy::{Strategy, ValueTree}, + test_runner::TestRunner, +}; +use rand::Rng; +use std::collections::HashMap; + +use crate::ast::*; + +#[derive(Debug, PartialEq)] +pub struct Environment<'a> { + parent: Box<Option<&'a Environment<'a>>>, + bindings: HashMap<String, Value>, +} + +impl<'a> Environment<'a> { + pub fn new() -> Self { + Environment { + parent: Box::new(None), + bindings: HashMap::new(), + } + } + + fn bind(&mut self, var: &str, value: &Value) { + self.bindings.insert(var.to_string(), value.clone()); + } + + fn extends(&'a self) -> Self { + Environment { + parent: Box::new(Some(self)), + bindings: HashMap::new(), + } + } + + fn lookup(&self, var: &str) -> Option<&Value> { + self.bindings.get(var).or_else(|| match *self.parent { + Some(parent) => parent.lookup(var), + None => None, + }) + } +} + +impl<'a> Default for Environment<'a> { + fn default() -> Self { + Self::new() + } +} + +pub fn eval_all(values: &[Value]) -> Vec<Value> { + let mut env = Environment::new(); + values.iter().map(|v| eval_whnf(v, &mut env)).collect() +} + +/// Reduce the given value to weak head normal form using call-by-name +/// evaluation strategy. +/// +/// call-by-name reduces the leftmost outermost redex first, which is +/// not under a lambda abstraction. +pub fn eval_whnf(arg: &Value, env: &mut Environment) -> Value { + match arg { + Value::Def(var, value) => { + env.bind(var, value); + Value::Bool(true) // TODO: return a more meaningful value? + } + Value::Let(var, value, expr) => { + let mut newenv = env.extends(); + newenv.bind(var, value); + eval_whnf(expr, &mut newenv) + } + Value::App(l, r) => match eval_whnf(l, env) { + Value::Lam(v, body) => eval_whnf(&subst(&v, &body, r), env), + Value::Sym(var) => match env.lookup(&var) { + Some(val) => eval_whnf(&Value::App(Box::new(val.clone()), r.clone()), env), + None => arg.clone(), + }, + other => Value::App(Box::new(other), r.clone()), + }, + Value::Sym(var) => env.lookup(var).unwrap_or(arg).clone(), + other => other.clone(), + } +} + +fn subst(var: &str, body: &Value, e: &Value) -> Value { + match body { + Value::Sym(x) if x == var => e.clone(), + Value::Lam(x, b) if x == var => { + let y = gensym(); + let bd = subst(x, b, &Value::Sym(y.clone())); + Value::Lam(y, Box::new(bd)) + } + Value::Lam(x, b) => Value::Lam(x.to_string(), Box::new(subst(var, b, e))), + Value::App(l, r) => Value::App(Box::new(subst(var, l, e)), Box::new(subst(var, r, e))), + other => other.clone(), + } +} + +pub fn gensym() -> String { + let mut rng = rand::thread_rng(); + + let n1: u8 = rng.gen(); + format!("x_{}", n1) +} + +pub fn generate_expr(size: u32, runner: &mut TestRunner) -> Value { + match size { + 0 | 1 => { + let n = any::<u16>().new_tree(runner).unwrap().current(); + Value::Num(n.into()) + } + 2 => Value::Sym(ascii_identifier().new_tree(runner).unwrap().current()), + 3 => any_sym().new_tree(runner).unwrap().current(), + 4 => simple_app().new_tree(runner).unwrap().current(), + 5 => nested_simple_app().new_tree(runner).unwrap().current(), + 6 => simple_lambda().new_tree(runner).unwrap().current(), + 7 => app_to_lambda().new_tree(runner).unwrap().current(), + 8 => multi_app().new_tree(runner).unwrap().current(), + _ => any::<u32>() + .prop_flat_map(gen_terms) + .new_tree(runner) + .unwrap() + .current(), + } +} + +pub fn generate_exprs(size: u32, runner: &mut TestRunner) -> Vec<Value> { + let sz = (0..size).new_tree(runner).unwrap().current(); + (0..sz) + .collect::<Vec<_>>() + .into_iter() + .map(|_| generate_expr(size, runner)) + .collect() +} + +fn simple_app() -> impl Strategy<Value = Value> { + let leaf = prop_oneof![any_num(), any_sym()]; + (leaf.clone(), leaf.clone()).prop_map(|(l, r)| Value::App(Box::new(l), Box::new(r))) +} + +fn multi_app() -> impl Strategy<Value = Value> { + let leaf = prop_oneof![any_num(), any_sym()]; + (leaf.clone(), leaf.clone()).prop_map(|(l, r)| Value::App(Box::new(l), Box::new(r))) +} + +fn any_num() -> impl Strategy<Value = Value> { + any::<i32>().prop_map(Value::Num) +} + +fn nested_simple_app() -> impl Strategy<Value = Value> { + let leaf = prop_oneof![any_num(), ascii_identifier().prop_map(Value::Sym)]; + leaf.prop_recursive(4, 128, 5, move |inner| { + (inner.clone(), inner.clone()).prop_map(|(l, r)| Value::App(Box::new(l), Box::new(r))) + }) +} + +fn any_sym() -> impl Strategy<Value = Value> { + identifier().prop_map(Value::Sym) +} + +fn simple_lambda() -> impl Strategy<Value = Value> { + // TODO: there's nothing to guarantee the variable appears in the body + (ascii_identifier(), nested_simple_app()).prop_map(|(v, b)| Value::Lam(v, Box::new(b))) +} + +fn app_to_lambda() -> impl Strategy<Value = Value> { + let lam = simple_lambda(); + let arg = prop_oneof![any_num(), any_sym(), nested_simple_app()]; + (lam, arg).prop_map(|(l, a)| Value::App(Box::new(l), Box::new(a))) +} + +/// Cantor pairing function +/// See https://en.wikipedia.org/wiki/Pairing_function +fn pairing(k: u32) -> (u32, u32) { + let a = ((((8 * (k as u64) + 1) as f64).sqrt() - 1.0) / 2.0).floor(); + let b = (a * (a + 1.0)) / 2.0; + let n = (k as f64) - b; + (n as u32, (a - n) as u32) +} + +fn gen_terms(u: u32) -> impl Strategy<Value = Value> { + if u % 2 != 0 { + let j = (u - 1) / 2; + if j % 2 == 0 { + let k = j / 2; + let (n, m) = pairing(k); + let r = (gen_terms(n), gen_terms(m)) + .prop_map(move |(l, r)| Value::App(Box::new(l), Box::new(r))); + r.boxed() + } else { + let k = (j - 1) / 2; + let (n, m) = pairing(k); + let r = gen_terms(m).prop_map(move |v| Value::Lam(format!("x_{}", n), Box::new(v))); + r.boxed() + } + } else { + let j = u / 2; + Just(Value::Sym(format!("x_{}", j))).boxed() + } +} + +#[cfg(test)] +mod lambda_test { + use crate::parser::parse; + + use super::{eval_all, eval_whnf, Environment, Value}; + + fn parse1(string: &str) -> Value { + parse(string).pop().unwrap() + } + + fn eval1(value: &Value) -> Value { + eval_whnf(value, &mut Environment::new()) + } + + #[test] + fn evaluating_a_non_reducible_value_yields_itself() { + let value = parse1("(foo 12)"); + assert_eq!(value, eval1(&value)); + } + + #[test] + fn evaluating_application_on_an_abstraction_reduces_it() { + let value = parse1("((lam x x) 12)"); + assert_eq!(Value::Num(12), eval1(&value)); + } + + #[test] + fn substitution_occurs_within_abstraction_body() { + let value = parse1("(((lam x (lam y x)) 13) 12)"); + assert_eq!(Value::Num(13), eval1(&value)); + } + + #[test] + fn substitution_occurs_within_application_body() { + let value = parse1("(((lam x (lam y (y x))) 13) 12)"); + assert_eq!( + Value::App(Box::new(Value::Num(12)), Box::new(Value::Num(13))), + eval1(&value) + ); + } + + #[test] + fn substitution_does_not_capture_free_variables() { + let value = parse1("(((lam x (lam x x)) 13) 12)"); + assert_eq!(Value::Num(12), eval1(&value)); + } + + #[test] + fn interpretation_applies_to_both_sides_of_application() { + let value = parse1("((lam x x) ((lam x x) 12))"); + assert_eq!(Value::Num(12), eval1(&value)); + } + + #[test] + fn reduction_is_applied_until_normal_form_is_reached() { + let value = parse1("((((lam y (lam x (lam y (x y)))) 13) (lam x x)) 11)"); + assert_eq!(Value::Num(11), eval1(&value)); + } + + #[test] + fn reduction_always_select_leftmost_outermost_redex() { + // this should not terminate if we evaluate the rightmost redex first, eg. + // applicative order reduction + let value = parse1("((lam x 1) ((lam x (x x)) (lam x (x x))))"); + assert_eq!(Value::Num(1), eval1(&value)); + } + + #[test] + fn defined_symbols_are_evaluated_to_their_definition() { + let values = parse("(def foo 12) foo"); + assert_eq!(vec![Value::Bool(true), Value::Num(12)], eval_all(&values)); + } + + #[test] + fn let_expressions_bind_symbol_to_expression_in_environment() { + let values = parse("(let (foo (lam x x)) (foo 12))"); + assert_eq!(vec![Value::Num(12)], eval_all(&values)); + } + + #[test] + fn let_expressions_introduce_new_scope_for_bindings() { + let values = parse("(let (foo (lam x x)) ((let (foo foo) foo) 13))"); + assert_eq!(vec![Value::Num(13)], eval_all(&values)); + } + + #[test] + fn bound_symbol_in_higher_scope_are_resolved() { + let values = parse("(let (id (lam x x)) (let (foo 12) (id foo)))"); + assert_eq!(vec![Value::Num(12)], eval_all(&values)); + } +} diff --git a/lambda-calcul/rust/src/lib.rs b/lambda-calcul/rust/src/lib.rs new file mode 100644 index 0000000..a8cf18e --- /dev/null +++ b/lambda-calcul/rust/src/lib.rs @@ -0,0 +1,4 @@ +pub mod ast; +pub mod io; +pub mod lambda; +pub mod parser; diff --git a/lambda-calcul/rust/src/main.rs b/lambda-calcul/rust/src/main.rs new file mode 100644 index 0000000..8d52c46 --- /dev/null +++ b/lambda-calcul/rust/src/main.rs @@ -0,0 +1,18 @@ +use std::{ + env::args, + io::{stdin, stdout, IsTerminal}, +}; + +use lambda::io::{batch_eval, eval_file, repl}; + +fn main() { + if args().count() > 1 { + for file in args().skip(1) { + println!("{}", eval_file(&file)); + } + } else if stdin().is_terminal() { + repl(&mut stdin(), &mut stdout()); + } else { + batch_eval(&mut stdin(), &mut stdout()); + } +} diff --git a/lambda-calcul/rust/src/parser.rs b/lambda-calcul/rust/src/parser.rs new file mode 100644 index 0000000..52aad5a --- /dev/null +++ b/lambda-calcul/rust/src/parser.rs @@ -0,0 +1,392 @@ +use crate::ast::*; + +#[derive(Debug, PartialEq)] +enum Token { + LParen, + RParen, + Lambda, + Word(String), + Define, + Let, +} + +#[derive(Debug)] +struct Parser { + tokens: Vec<Token>, + index: usize, +} + +impl Parser { + fn expect(&mut self, token: Token) -> Result<(), String> { + if self.tokens.get(self.index) == Some(&token) { + Ok(()) + } else { + Err(format!( + "Expected {:?}, got {:?}", + token, + self.tokens.get(self.index) + )) + } + .map(|_| { + self.next(); + }) + } + + fn expect_symbol(&mut self) -> Result<String, String> { + if let Token::Word(s) = self.tokens.get(self.index).ok_or("Expected a symbol")? { + Ok(s.clone()) + } else { + Err("Expected a symbol".to_string()) + } + .map(|s| { + self.next(); + s + }) + } + + fn next(&mut self) { + self.index += 1; + } + + fn backtrack(&mut self) { + self.index -= 1; + } +} + +pub fn parse(arg: &str) -> Vec<Value> { + parse_total(arg) + .map_err(|e| panic!("Syntax error: {}", e)) + .unwrap() +} + +pub fn parse_total(arg: &str) -> Result<Vec<Value>, String> { + let tokens = tokenize(arg); + let mut parser = Parser { tokens, index: 0 }; + let mut result = Vec::new(); + while parser.index < parser.tokens.len() { + let expr = parse_toplevel(&mut parser)?; + result.push(expr); + } + Ok(result) +} + +fn parse_toplevel(parser: &mut Parser) -> Result<Value, String> { + parse_definition(parser).or_else(|_| parse_expression(parser)) +} + +fn parse_definition(parser: &mut Parser) -> Result<Value, String> { + parser.expect(Token::LParen)?; + parser.expect(Token::Define).map_err(|e| { + parser.backtrack(); + e.to_string() + })?; + let var = parse_variable(parser)?; + let body = parse_expression(parser)?; + parser.expect(Token::RParen)?; + Ok(Value::Def(var, Box::new(body))) +} + +fn parse_expression(parser: &mut Parser) -> Result<Value, String> { + parse_value(parser) + .or_else(|_| parse_abstraction(parser)) + .or_else(|_| parse_let(parser)) + .or_else(|_| parse_application(parser)) +} + +fn parse_abstraction(parser: &mut Parser) -> Result<Value, String> { + parser.expect(Token::LParen)?; + parser.expect(Token::Lambda).map_err(|e| { + parser.backtrack(); + e.to_string() + })?; + let vars = parse_variables(parser)?; + let body = parse_expression(parser)?; + parser.expect(Token::RParen)?; + let result = vars + .iter() + .rev() + .fold(body, |acc, var| Value::Lam(var.clone(), Box::new(acc))); + Ok(result) +} + +fn parse_variables(parser: &mut Parser) -> Result<Vec<String>, String> { + parse_variable(parser) + .map(|s| vec![s]) + .or_else(|_| parse_variables_list(parser)) +} + +fn parse_variables_list(parser: &mut Parser) -> Result<Vec<String>, String> { + let mut vars = Vec::new(); + parser.expect(Token::LParen)?; + while let Ok(var) = parse_variable(parser) { + vars.push(var); + } + parser.expect(Token::RParen)?; + Ok(vars) +} + +fn parse_variable(parser: &mut Parser) -> Result<String, String> { + let var = parser.expect_symbol()?; + Ok(var) +} + +fn parse_let(parser: &mut Parser) -> Result<Value, String> { + parser.expect(Token::LParen)?; + parser.expect(Token::Let).map_err(|e| { + parser.backtrack(); + e.to_string() + })?; + parser.expect(Token::LParen)?; + let var = parse_variable(parser)?; + let body = parse_expression(parser)?; + parser.expect(Token::RParen)?; + let expr = parse_expression(parser)?; + parser.expect(Token::RParen)?; + Ok(Value::Let(var, Box::new(body), Box::new(expr))) +} + +fn parse_application(parser: &mut Parser) -> Result<Value, String> { + parser.expect(Token::LParen)?; + let init = parse_expression(parser)?; + let mut exprs = Vec::new(); + while let Ok(expr) = parse_expression(parser) { + exprs.push(expr); + } + if exprs.is_empty() { + return Err("Application needs two values".to_string()); + } + parser.expect(Token::RParen)?; + let app: Value = exprs.iter().fold(init, |acc, expr| { + Value::App(Box::new(acc.clone()), Box::new(expr.clone())) + }); + Ok(app.to_owned()) +} + +fn parse_value(parser: &mut Parser) -> Result<Value, String> { + let token = parser.tokens.get(parser.index).ok_or("Expected a value")?; + let val = parse_number(token) + .or_else(|_| parse_bool(token)) + .or_else(|_| parse_symbol(token))?; + parser.next(); + Ok(val) +} + +fn tokenize(arg: &str) -> Vec<Token> { + let mut result = Vec::new(); + let mut word = String::new(); + + for c in arg.chars() { + match c { + '(' => { + terminate(&mut result, &mut word); + result.push(Token::LParen) + } + ')' => { + terminate(&mut result, &mut word); + result.push(Token::RParen) + } + c if c.is_whitespace() => terminate(&mut result, &mut word), + c => word.push(c), + } + } + terminate(&mut result, &mut word); + result +} + +fn terminate(result: &mut Vec<Token>, word: &mut String) { + if !word.is_empty() { + let w = word.clone(); + if w == "lam" { + result.push(Token::Lambda); + } else if w == "def" { + result.push(Token::Define); + } else if w == "let" { + result.push(Token::Let); + } else { + result.push(Token::Word(w)); + } + word.clear(); + } +} + +fn parse_symbol(token: &Token) -> Result<Value, String> { + match token { + Token::Word(s) => Ok(Value::Sym(s.clone())), + _ => Err(format!("Expected a symbol, got {:?}", token)), + } +} + +fn parse_bool(token: &Token) -> Result<Value, String> { + match token { + Token::Word(s) => s + .parse::<bool>() + .map(Value::Bool) + .map_err(|e| e.to_string()), + _ => Err("Expected a boolean".to_string()), + } +} + +fn parse_number(token: &Token) -> Result<Value, String> { + match token { + Token::Word(s) => s.parse::<i32>().map(Value::Num).map_err(|e| e.to_string()), + _ => Err("Expected an integer".to_string()), + } +} + +#[cfg(test)] +mod tests { + use super::parse_total; + + use super::Token::*; + use super::Value; + use super::Value::*; + use super::{parse, tokenize}; + use proptest::prelude::*; + + proptest! { + #[test] + fn parse_integer_as_number(i in -1000i32..1000) { + let result = parse(&i.to_string()); + assert_eq!(vec![Num(i)], result); + } + + } + + #[test] + fn parse_truth_values_as_booleans() { + assert_eq!(vec![Bool(true)], parse("true")); + assert_eq!(vec![Bool(false)], parse("false")); + } + + #[test] + fn parse_identifiers_values_as_symbols() { + assert_eq!(vec![Sym("foo".to_string())], parse("foo")); + } + + #[test] + fn ignores_whitespace() { + assert_eq!(vec![Sym("foo".to_string())], parse(" foo \n\r")); + assert_eq!(vec![Num(-42)], parse("\n-42")); + } + + #[test] + fn tokenize_several_values() { + assert_eq!( + vec![ + Word("42".to_string()), + Word("foo".to_string()), + Word("true".to_string()) + ], + tokenize("42 foo \ntrue ") + ); + } + + #[test] + fn tokenize_string_with_parens() { + assert_eq!( + vec![ + LParen, + LParen, + RParen, + Word("42".to_string()), + RParen, + Word("true".to_string()), + LParen, + ], + tokenize("( \r() 42) \ntrue( ") + ); + } + + #[test] + fn tokenize_lambda_symbol() { + assert_eq!(vec![Lambda, LParen,], tokenize("lam (")); + } + + #[test] + fn parse_application_of_two_values() { + assert_eq!( + vec![App(Box::new(Sym("foo".to_string())), Box::new(Num(42)))], + parse("(foo 42)") + ); + } + + #[test] + fn reject_application_of_single_value() { + assert_eq!( + Err("Application needs two values".to_string()), + parse_total("(foo )") + ); + } + + #[test] + fn desugar_application_of_more_than_two_values() { + assert_eq!( + vec![App( + Box::new(App( + Box::new(App(Box::new(Sym("foo".to_string())), Box::new(Num(42)))), + Box::new(Bool(true)) + )), + Box::new(Sym("f".to_string())) + )], + parse("(foo 42 true f)") + ); + } + + #[test] + fn parse_abstraction() { + assert_eq!( + vec![Lam( + "x".to_string(), + Box::new(App( + Box::new(Sym("x".to_string())), + Box::new(Sym("x".to_string())) + )) + )], + parse("(lam x (x x))") + ); + } + + #[test] + fn desugar_abstraction_with_several_variables_into_nested_lambdas() { + assert_eq!( + vec![Lam( + "x".to_string(), + Box::new(Lam("y".to_string(), Box::new(Sym("y".to_string())))) + )], + parse("(lam (x y) y)") + ); + } + + #[test] + fn parse_definition() { + assert_eq!( + vec![Def("x".to_string(), Box::new(Num(12)))], + parse("(def x 12)") + ); + } + + #[test] + fn parse_multiple_values() { + assert_eq!(vec![Sym("foo".to_string()), Num(42)], parse("foo 42")); + } + + #[test] + fn parse_let_expressions() { + assert_eq!( + vec![Value::Let( + "x".to_string(), + Box::new(Num(12)), + Box::new(Sym("x".to_string())) + )], + parse("(let (x 12) x)") + ); + } + + proptest! { + #[test] + fn parse_is_inverse_to_display(values in any::<Vec<Value>>()) { + let result : Vec<String> = values.iter().map(|v:&Value| v.to_string()).collect(); + assert_eq!(values, result.iter().flat_map(|s| parse(s)).collect::<Vec<Value>>()); + } + } +} diff --git a/lambda-calcul/rust/src/tester.rs b/lambda-calcul/rust/src/tester.rs new file mode 100644 index 0000000..eb66d4e --- /dev/null +++ b/lambda-calcul/rust/src/tester.rs @@ -0,0 +1,100 @@ +use serde::{Deserialize, Serialize}; +use std::{ + fs::{self, read_to_string, File}, + path::PathBuf, + process::{Command, Stdio}, + time::Instant, +}; + +pub fn main() { + let mut args: Vec<String> = std::env::args().collect(); + // name of the process to run + let proc = args.remove(1); + if args.len() > 1 { + let run = traverse(&args) + .and_then(|paths| run_test(&proc, &paths)) + .expect("Failed to traverse directory"); + println!("{}", serde_json::to_string_pretty(&run).unwrap()); + } else { + println!( + r#"Usage: tester [options] <directory>+ + +Options: + -p, --process The process to run. If the given process is not a + an absolute path, it will be resolved against the + PATH environment variable. + -j, --json Output the results in JSON format (default: false) + -h, --help Display this help message + -v, --version Display the version of the tester +"# + ); + } +} + +fn traverse(args: &[String]) -> Result<Vec<PathBuf>, String> { + let mut files: Vec<PathBuf> = Vec::new(); + for arg in args.iter().skip(1) { + let entries = fs::read_dir(arg).map_err(|e| e.to_string())?; + for entry in entries { + let dir = entry.map_err(|e| e.to_string())?; + let f = dir.metadata().map_err(|e| e.to_string())?; + if f.is_dir() { + files.push(dir.path()); + } + } + } + Ok(files) +} + +#[derive(Debug, Serialize, Deserialize)] +pub enum TestResult { + TestSucceeded, + TestFailed(String, String), +} + +#[derive(Debug, Serialize, Deserialize)] +pub struct TestRun { + file: String, + test_result: TestResult, + duration: u128, +} + +fn run_test(proc: &str, files: &Vec<PathBuf>) -> Result<Vec<TestRun>, String> { + let mut result = Vec::new(); + for file in files { + let mut inp = file.clone(); + let mut outp = file.clone(); + inp.push("input"); + outp.push("output"); + let (test_result, duration) = run_test_case(proc, &inp, &outp)?; + result.push(TestRun { + file: inp.as_path().to_str().unwrap().to_string(), + test_result, + duration, + }); + } + Ok(result) +} + +fn run_test_case( + proc: &str, + inp: &std::path::PathBuf, + outp: &std::path::PathBuf, +) -> Result<(TestResult, u128), String> { + let input = File::open(inp).map_err(|e| e.to_string())?; + let expected = read_to_string(outp).map_err(|e| e.to_string())?; + let start = Instant::now(); + + let actual = Command::new(proc) + .stdin(Stdio::from(input)) + .output() + .map_err(|e| e.to_string())?; + + let duration = (Instant::now() - start).as_millis(); + if expected.as_bytes() == actual.stdout { + Ok((TestResult::TestSucceeded, duration)) + } else { + let actual_string = String::from_utf8(actual.stdout).map_err(|e| e.to_string())?; + Ok((TestResult::TestFailed(expected, actual_string), duration)) + } +} diff --git a/lambda-calcul/rust/src/web.rs b/lambda-calcul/rust/src/web.rs new file mode 100644 index 0000000..3f8f056 --- /dev/null +++ b/lambda-calcul/rust/src/web.rs @@ -0,0 +1,899 @@ +use actix_web::{get, middleware::Logger, post, web, App, HttpResponse, HttpServer, Responder}; +use chrono::{DateTime, Utc}; +use clap::Parser; +use handlebars::{DirectorySourceOptions, Handlebars}; +use log::info; +use proptest::test_runner::{Config, RngAlgorithm, TestRng, TestRunner}; +use rand::Rng; +use serde::{Deserialize, Serialize}; +use std::sync::Mutex; +use std::time::Duration; +use std::{collections::HashMap, sync::Arc}; +use tokio::task::{self, JoinHandle}; +use uuid::Uuid; + +use lambda::lambda::{eval_all, eval_whnf, generate_expr, generate_exprs, gensym, Environment}; +use lambda::parser::{parse, parse_total}; + +#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)] +struct Registration { + url: String, + name: String, +} + +#[derive(Debug, Serialize, Deserialize, Clone)] +struct ClientData { + name: String, + grade: u8, + last_query: DateTime<Utc>, + success: bool, +} + +impl ClientData { + fn from(client: &Client) -> Self { + ClientData { + name: client.name.clone(), + grade: client.grade, + last_query: client + .results + .last() + .map_or(chrono::offset::Utc::now(), |q| q.timestamp), + success: client + .results + .last() + .map_or(false, |q| matches!(q.result, TestResult::TestSucceeded)), + } + } +} + +#[derive(Debug, Serialize, Deserialize, Clone)] +struct Leaderboard { + clients: Vec<ClientData>, +} + +trait AppState: Send + Sync { + fn register(&mut self, registration: &Registration) -> RegistrationResult; + fn unregister(&mut self, url: &String); +} + +#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)] +enum RegistrationResult { + RegistrationSuccess { id: String, url: String }, + UrlAlreadyRegistered { url: String }, +} + +#[derive(Debug, Clone)] +struct Client { + id: Uuid, + name: String, + url: String, + grade: u8, + runner: TestRunner, + results: Vec<Test>, + delay: std::time::Duration, +} + +#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)] +struct Test { + timestamp: DateTime<Utc>, + result: TestResult, +} + +#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)] +enum TestResult { + TestFailed(String), + ErrorSendingTest(String), + TestSucceeded, +} + +impl Client { + fn new(url: String, name: String, delay: Duration) -> Self { + let id = Uuid::new_v4(); + let runner = TestRunner::new_with_rng( + Config::default(), + TestRng::from_seed(RngAlgorithm::XorShift, &id.to_bytes_le()), + ); + Self { + id, + url, + name, + grade: 1, + runner, + results: Vec::new(), + delay, + } + } + + fn time_to_next_test(&self) -> Duration { + self.delay + } + + fn generate_expr(&mut self) -> (String, String) { + if self.grade >= 10 { + self.generate_exprs() + } else { + let input = generate_expr(self.grade.into(), &mut self.runner); + let expected = eval_whnf(&input, &mut Environment::new()); + (input.to_string(), expected.to_string()) + } + } + + fn generate_exprs(&mut self) -> (String, String) { + let exprs = generate_exprs(self.grade.into(), &mut self.runner); + let input = exprs + .iter() + .map(|v| format!("{}", v)) + .collect::<Vec<_>>() + .join("\n"); + let expected = eval_all(&exprs); + ( + input, + expected + .iter() + .map(|v| format!("{}", v)) + .collect::<Vec<_>>() + .join("\n"), + ) + } + + /// Applies a `Test` to update client's state + fn apply(&mut self, test: &Test) { + match test.result { + TestResult::TestSucceeded => { + self.grade = self.grade.saturating_add(1); + self.delay = Duration::from_secs_f64(self.delay.as_secs_f64() * 0.8); + if self.delay.as_millis() < 500 { + self.delay = Duration::from_millis(500); + } + } + TestResult::TestFailed(_) => { + self.delay = Duration::from_secs_f64(self.delay.as_secs_f64() * 1.2); + if self.delay.as_secs() > 30 { + self.delay = Duration::from_secs(30); + } + } + _ => (), + } + self.results.push(test.clone()); + } + + fn check_result(&self, expected: &String, response: &Result<String, TestResult>) -> Test { + let result = match response { + Ok(expr) => { + let vals = parse(expr); + let actual = eval_all(&vals) + .iter() + .map(|v| format!("{}", v)) + .collect::<Vec<_>>() + .join("\n"); + if actual == *expected { + TestResult::TestSucceeded + } else { + TestResult::TestFailed(actual) + } + } + Err(res) => res.clone(), + }; + Test { + result, + timestamp: chrono::offset::Utc::now(), + } + } +} + +#[derive(Debug)] +struct State { + base_duration: Duration, + clients: HashMap<String, (Arc<Mutex<Client>>, JoinHandle<()>)>, +} + +impl State { + fn new() -> Self { + State::with_duration(Duration::from_secs(10)) + } + + fn with_duration(base_duration: Duration) -> Self { + Self { + base_duration, + clients: HashMap::new(), + } + } + + fn client_events(&self, url: &String) -> usize { + let client = self.clients.get(url).unwrap().0.lock().unwrap(); + client.results.len() + } +} + +impl AppState for State { + fn register(&mut self, registration: &Registration) -> RegistrationResult { + if self.clients.contains_key(®istration.url) { + RegistrationResult::UrlAlreadyRegistered { + url: registration.url.clone(), + } + } else { + let client = Client::new( + registration.url.clone(), + registration.name.clone(), + self.base_duration, + ); + let id = client.id.to_string(); + let client_ref = Arc::new(Mutex::new(client)); + // let it run in the background + // FIXME: should find a way to handle graceful termination + let client_handle = task::spawn(send_tests(client_ref.clone())); + + self.clients.insert( + registration.url.clone(), + (client_ref.clone(), client_handle), + ); + + RegistrationResult::RegistrationSuccess { + id, + url: registration.url.clone(), + } + } + } + + fn unregister(&mut self, url: &String) { + let (_, handle) = self.clients.get(url).unwrap(); + handle.abort() + } +} + +#[post("/register")] +async fn register( + app_state: web::Data<Arc<Mutex<State>>>, + registration: web::Json<Registration>, +) -> impl Responder { + let result = app_state.lock().unwrap().register(®istration); + match result { + RegistrationResult::RegistrationSuccess { .. } => HttpResponse::Ok().json(result), + RegistrationResult::UrlAlreadyRegistered { .. } => HttpResponse::BadRequest().json(result), + } +} + +#[post("/eval")] +async fn eval(input: String) -> impl Responder { + let exprs = parse_total(&input); + match exprs { + Ok(exprs) => { + let mut rng = rand::thread_rng(); + if rng.gen_range(0..10) <= 2 { + return HttpResponse::Ok().body(gensym()); + } + let output = eval_all(&exprs) + .iter() + .map(|v| format!("{}", v)) + .collect::<Vec<_>>() + .join("\n"); + HttpResponse::Ok().body(output.to_string()) + } + Err(e) => HttpResponse::BadRequest().body(e.to_string()), + } +} + +#[get("/leaderboard")] +async fn leaderboard( + app_state: web::Data<Arc<Mutex<State>>>, + hb: web::Data<Handlebars<'_>>, +) -> impl Responder { + let clients = &app_state.lock().unwrap().clients; + let mut client_data = vec![]; + for client in clients.values() { + let client = client.0.lock().unwrap(); + client_data.push(ClientData::from(&client)); + } + client_data.sort_by(|a, b| b.grade.cmp(&a.grade)); + + let body = hb + .render( + "leaderboard", + &Leaderboard { + clients: client_data, + }, + ) + .unwrap(); + + web::Html::new(body) +} + +#[derive(Parser, Debug)] +struct Options { + /// The port to listen on + /// Defaults to 8080 + #[arg(short, long, default_value_t = 8080)] + port: u16, + /// The host to bind the server to + /// Defaults to 127.0.0.1 + #[arg(long, default_value = "127.0.0.1")] + host: String, +} + +#[tokio::main] +async fn main() -> std::io::Result<()> { + let options = Options::parse(); + let app_state = Arc::new(Mutex::new(State::new())); + + env_logger::init(); + // Handlebars uses a repository for the compiled templates. This object must be + // shared between the application threads, and is therefore passed to the + // Application Builder as an atomic reference-counted pointer. + let mut handlebars = Handlebars::new(); + handlebars + .register_templates_directory( + "./templates", + DirectorySourceOptions { + tpl_extension: ".html".to_owned(), + hidden: false, + temporary: false, + }, + ) + .unwrap(); + + HttpServer::new(move || { + App::new() + .wrap(Logger::default()) + .app_data(web::Data::new(app_state.clone())) + .app_data(web::Data::new(handlebars.clone())) + .service(register) + .service(eval) + .service(leaderboard) + }) + .bind((options.host, options.port))? + .run() + .await +} + +fn get_test(client_m: &Mutex<Client>) -> (String, String, String) { + let mut client = client_m.lock().unwrap(); + let (input, expected) = client.generate_expr(); + (input, client.url.clone(), expected) +} + +async fn send_tests(client_m: Arc<Mutex<Client>>) { + loop { + let sleep = sleep_time(&client_m); + tokio::time::sleep(sleep).await; + { + let (input, url, expected) = get_test(&client_m); + + let response = send_test(&input, &url, sleep).await; + + apply_result(&client_m, expected, response); + } + } +} + +fn apply_result(client_m: &Mutex<Client>, expected: String, response: Result<String, TestResult>) { + let mut client = client_m.lock().unwrap(); + let test = client.check_result(&expected, &response); + client.apply(&test); +} + +fn sleep_time(client_m: &Arc<Mutex<Client>>) -> Duration { + client_m.lock().unwrap().time_to_next_test() +} + +async fn send_test(input: &String, url: &String, timeout: Duration) -> Result<String, TestResult> { + info!("Sending {} to {}", input, url); + let body = input.clone(); + let response = reqwest::Client::new() + .post(url) + .timeout(timeout) + .header("content-type", "text/plain") + .body(body) + .send() + .await; + match response { + Ok(response) => { + let body = response.text().await.unwrap(); + info!("Response from {}: {}", url, body); + Ok(body) + } + Err(e) => { + info!("Error sending test: {}", e); + Err(TestResult::ErrorSendingTest(e.to_string())) + } + } +} + +#[cfg(test)] +mod app_tests { + use std::str::from_utf8; + use std::sync::Arc; + + use actix_web::http::header::TryIntoHeaderValue; + use actix_web::{body, http::header::ContentType, middleware::Logger, test, App}; + use lambda::ast::Value; + + use super::*; + + #[actix_web::test] + async fn post_registration_returns_success_with_unique_id() { + let state = Arc::new(Mutex::new(State::new())); + // FIXME should only be called once, move to setup + env_logger::init(); + + let app = test::init_service( + App::new() + .wrap(Logger::default()) + .app_data(web::Data::new(state)) + .service(register), + ) + .await; + let url = "http://192.168.1.1".to_string(); + let req = test::TestRequest::post() + .uri("/register") + .set_json(Registration { + url: url.clone(), + name: "foo".to_string(), + }) + .insert_header(ContentType::json()) + .to_request(); + + let resp = test::call_service(&app, req).await; + + assert!(resp.status().is_success()); + + let body = resp.into_body(); + let bytes = body::to_bytes(body).await; + match serde_json::from_slice::<RegistrationResult>(bytes.as_ref().unwrap()).unwrap() { + RegistrationResult::RegistrationSuccess { id: _, url: url1 } => assert_eq!(url1, url), + _ => panic!("Expected RegistrationSuccess, got {:?}", bytes.unwrap()), + }; + } + + #[actix_web::test] + async fn post_registration_returns_400_when_register_fails() { + let state = Arc::new(Mutex::new(State::new())); + + let app = test::init_service( + App::new() + .wrap(Logger::default()) + .app_data(web::Data::new(state.clone())) + .service(register), + ) + .await; + let url = "http://192.168.1.1".to_string(); + let registration = Registration { + url: url.clone(), + name: "foo".to_string(), + }; + + state.lock().unwrap().register(®istration); + + let req = test::TestRequest::post() + .uri("/register") + .set_json(registration) + .insert_header(ContentType::json()) + .to_request(); + + let resp = test::call_service(&app, req).await; + + assert!(resp.status().is_client_error()); + assert_eq!( + ContentType::json().try_into_value().unwrap(), + resp.headers().get("content-type").unwrap() + ); + } + + #[actix_web::test] + async fn post_expression_returns_evaluation() { + let app = test::init_service(App::new().wrap(Logger::default()).service(eval)).await; + + let req = test::TestRequest::post() + .uri("/eval") + .set_payload("((lam (x y) x) 1 2)") + .insert_header(ContentType::plaintext()) + .to_request(); + + let resp = test::call_service(&app, req).await; + + assert!(resp.status().is_success()); + + let body = resp.into_body(); + let bytes = body::to_bytes(body).await.unwrap(); + assert_eq!(bytes, "1".to_string().into_bytes()); + } + + #[actix_web::test] + async fn post_expression_returns_multiple_evaluations() { + let app = test::init_service(App::new().wrap(Logger::default()).service(eval)).await; + + let req = test::TestRequest::post() + .uri("/eval") + .set_payload("((lam (x y) x) 1 2)\n42") + .insert_header(ContentType::plaintext()) + .to_request(); + + let resp = test::call_service(&app, req).await; + + assert!(resp.status().is_success()); + + let body = resp.into_body(); + let bytes = body::to_bytes(body).await.unwrap(); + assert_eq!("1\n42".to_string().into_bytes(), bytes); + } + + #[actix_web::test] + async fn get_leaderboard_returns_html_page_listing_clients_state() { + let app_state = Arc::new(Mutex::new(State::new())); + app_state.lock().unwrap().register(&Registration { + url: "http://1.2.3.4".to_string(), + name: "client1".to_string(), + }); + + let mut handlebars = Handlebars::new(); + handlebars + .register_templates_directory( + "./templates", + DirectorySourceOptions { + tpl_extension: ".html".to_owned(), + hidden: false, + temporary: false, + }, + ) + .unwrap(); + + let app = test::init_service( + App::new() + .wrap(Logger::default()) + .app_data(web::Data::new(app_state.clone())) + .app_data(web::Data::new(handlebars.clone())) + .service(leaderboard), + ) + .await; + + let req = test::TestRequest::get().uri("/leaderboard").to_request(); + + let resp = test::call_service(&app, req).await; + + assert!(resp.status().is_success()); + + let bytes = body::to_bytes(resp.into_body()).await.unwrap(); + assert!(from_utf8(&bytes).unwrap().contains("client1")); + } + + #[test] + async fn app_does_not_register_same_url_twice() { + let mut app_state = State::new(); + let registration = Registration { + name: "foo".to_string(), + url: "http://1.2.3.4".to_string(), + }; + + app_state.register(®istration); + let result = app_state.register(®istration); + + assert_eq!( + RegistrationResult::UrlAlreadyRegistered { + url: "http://1.2.3.4".to_string() + }, + result + ); + } + + #[test] + async fn unregistering_registered_client_stops_tester_thread_from_sending_tests() { + let mut app_state = State::with_duration(Duration::from_millis(100)); + let registration = Registration { + name: "foo".to_string(), + url: "http://1.2.3.4".to_string(), + }; + + let reg = app_state.register(®istration); + assert!(matches!( + reg, + RegistrationResult::RegistrationSuccess { .. } + )); + + tokio::time::sleep(Duration::from_millis(500)).await; + + app_state.unregister(®istration.url); + + let grade_before = app_state.client_events(®istration.url); + tokio::time::sleep(Duration::from_millis(500)).await; + let grade_after = app_state.client_events(®istration.url); + + assert_eq!(grade_before, grade_after); + } + + fn client() -> Client { + Client::new( + "http://1.2.3.4".to_string(), + "foo".to_string(), + Duration::from_secs(10), + ) + } + + #[test] + async fn client_generates_constant_at_level_1() { + let mut client = client(); + + let (input, _) = client.generate_expr(); + + match parse(&input)[..] { + [Value::Num(_)] => (), + _ => panic!("Expected constant 3"), + } + } + + #[test] + async fn client_generates_different_inputs_on_each_call() { + let mut client = client(); + + let (input1, _) = client.generate_expr(); + let (input2, _) = client.generate_expr(); + + assert_ne!(input1, input2); + } + + #[test] + async fn client_generates_ascii_variables_at_level_2() { + let mut client = client(); + client.grade = 2; + + let (input, _) = client.generate_expr(); + + let parsed = parse(&input); + match &parsed[..] { + [Value::Sym(name)] => { + assert!(name.chars().all(|c| c.is_ascii_alphanumeric())); + } + _ => panic!("Expected symbol, got {:?}", parsed), + } + } + + #[test] + async fn client_generates_unicode_variables_at_level_3() { + let mut client = client(); + client.grade = 3; + + let (input, _) = client.generate_expr(); + + let parsed = parse(&input); + match &parsed[..] { + [Value::Sym(_)] => (), + _ => panic!("Expected symbol, got {:?}", parsed), + } + } + + #[test] + async fn client_generates_binary_application_at_level_4() { + let mut client = client(); + client.grade = 4; + + let (input, _) = client.generate_expr(); + + let parsed = parse(&input); + match &parsed[..] { + [Value::App(_, _)] => (), + _ => panic!("Expected symbol, got {:?}", parsed), + } + } + + #[test] + async fn client_generates_nested_applications_and_constants_at_level_5() { + let mut client = client(); + client.grade = 5; + + let (input, _) = client.generate_expr(); + + let parsed = parse(&input); + match &parsed[..] { + [Value::App(_, _)] => (), + [Value::Sym(_)] => (), + [Value::Num(_)] => (), + _ => panic!("Expected symbol, got {:?}", parsed), + } + } + + #[test] + async fn client_generates_lambda_terms_at_level_6() { + let mut client = client(); + client.grade = 6; + + let (input, _) = client.generate_expr(); + + let parsed = parse(&input); + match &parsed[..] { + [Value::Lam(_, _)] => (), + _ => panic!("Expected symbol, got {:?}", parsed), + } + } + + #[test] + async fn client_generates_application_with_lambda_terms_at_level_7() { + let mut client = client(); + client.grade = 7; + + let (input, _) = client.generate_expr(); + + let parsed = parse(&input); + match &parsed[..] { + [Value::App(t1, _)] if matches!(**t1, Value::Lam(_, _)) => (), + _ => panic!("Expected symbol, got {:?}", parsed), + } + } + + #[test] + async fn client_generates_applications_with_more_than_2_terms_at_level_8() { + let mut client = client(); + client.grade = 8; + + let (input, _) = client.generate_expr(); + + let parsed = parse(&input); + if let [Value::App(_, _)] = &parsed[..] { + assert!(input.split(' ').count() >= 2) + } + } + + #[test] + async fn client_generates_more_complex_terms_at_level_9() { + let mut client = client(); + client.grade = 9; + + let (input, _) = client.generate_expr(); + + let parsed = parse(&input); + + assert!(!parsed.is_empty()); + } + + #[test] + async fn client_generates_multiple_terms_at_level_10() { + let mut client = client(); + client.grade = 10; + + let (input, _) = client.generate_expr(); + + let parsed = parse(&input); + + assert!(!parsed.is_empty()); + } + + #[test] + async fn client_increases_grade_on_successful_test() { + let mut client = client(); + let test = Test { + timestamp: chrono::offset::Utc::now(), + result: TestResult::TestSucceeded, + }; + + client.apply(&test); + + assert_eq!(2, client.grade); + } + + #[test] + async fn client_stores_test_results() { + let mut client = client(); + let test = Test { + timestamp: chrono::offset::Utc::now(), + result: TestResult::TestSucceeded, + }; + + client.apply(&test); + + assert_eq!(test, client.results.first().unwrap().clone()); + } + + #[test] + async fn client_returns_test_successful_if_result_match() { + let client = client(); + let expected = "1".to_string(); + let response = Ok("1".to_string()); + + let test = client.check_result(&expected, &response); + + assert_eq!(TestResult::TestSucceeded, test.result); + } + + #[test] + async fn client_returns_test_failed_given_result_do_not_match() { + let client = client(); + let expected = "1".to_string(); + let response = Ok("2".to_string()); + + let test = client.check_result(&expected, &response); + + assert_eq!(TestResult::TestFailed("2".to_string()), test.result); + } + + #[test] + async fn client_does_not_increase_grade_on_failed_test() { + let mut client = client(); + let test = Test { + timestamp: chrono::offset::Utc::now(), + result: TestResult::TestFailed("2".to_string()), + }; + + client.apply(&test); + + assert_eq!(1, client.grade); + } + + #[test] + async fn client_starts_delay_to_next_test_at_10s() { + let client = client(); + + let delay = client.time_to_next_test(); + + assert_eq!(std::time::Duration::from_secs(10), delay); + } + + #[test] + async fn client_increases_delay_to_next_upon_failed_test() { + let mut client = client(); + let test = Test { + timestamp: chrono::offset::Utc::now(), + result: TestResult::TestFailed("2".to_string()), + }; + let delay_before = client.time_to_next_test(); + + client.apply(&test); + + assert!(delay_before < client.time_to_next_test()); + } + + #[test] + async fn client_increases_delay_to_maximum_of_30s() { + let mut client = client(); + let test = Test { + timestamp: chrono::offset::Utc::now(), + result: TestResult::TestFailed("2".to_string()), + }; + + for _ in 0..100 { + client.apply(&test); + } + + assert_eq!(Duration::from_secs(30), client.time_to_next_test()); + } + + #[test] + async fn client_score_cannot_go_beyond_255() { + let mut client = client(); + let test = Test { + timestamp: chrono::offset::Utc::now(), + result: TestResult::TestSucceeded, + }; + + for _ in 0..256 { + client.apply(&test); + } + + assert_eq!(255, client.grade); + } + + #[test] + async fn client_decreases_delay_to_next_upon_successful_test() { + let mut client = client(); + let test = Test { + timestamp: chrono::offset::Utc::now(), + result: TestResult::TestSucceeded, + }; + let delay_before = client.time_to_next_test(); + + client.apply(&test); + + assert!(delay_before > client.time_to_next_test()); + } + + #[test] + async fn client_decreases_delay_to_minimum_of_500ms() { + let mut client = client(); + let test = Test { + timestamp: chrono::offset::Utc::now(), + result: TestResult::TestSucceeded, + }; + + for _ in 0..100 { + client.apply(&test); + } + + assert_eq!(Duration::from_millis(500), client.time_to_next_test()); + } +} diff --git a/lambda-calcul/rust/templates/leaderboard.html b/lambda-calcul/rust/templates/leaderboard.html new file mode 100644 index 0000000..82992d1 --- /dev/null +++ b/lambda-calcul/rust/templates/leaderboard.html @@ -0,0 +1,50 @@ +<!DOCTYPE html> +<html> + +<head> + <meta charset="utf-8"> + <title>Leaderboard</title> + <meta name="viewport" content="width=device-width, initial-scale=1"> + <style> + table { + width: 80%; + border-collapse: collapse; + } + + table, th, td { + border: 1px solid black; + } + + th, td { + padding: 15px; + text-align: left; + } + + th { + background-color: #f2f2f2; + } + + tr:nth-child(even) { + background-color: #f2f2f2; + } + + .success { + background-color: green; + } + + .fail { + background-color: red; + } + </style> +</head> + +<body> + <h1>Leaderboard</h1> + <table> + <tr><th>Name</th><th>Grade</th><th>Last test</th></tr> + {{#each this.clients}} + <tr><td>{{this.name}}</td><td>{{this.grade}}</td><td class="{{#if this.success}}success{{else}}fail{{/if}}">{{this.last_query}}</td></tr> + {{/each}} + </table> +</body> +</html> diff --git a/lambda-calcul/rust/tests/interpret_test.rs b/lambda-calcul/rust/tests/interpret_test.rs new file mode 100644 index 0000000..16e7fb7 --- /dev/null +++ b/lambda-calcul/rust/tests/interpret_test.rs @@ -0,0 +1,25 @@ +use lambda::io::{batch_eval, eval_file, repl}; + +#[test] +fn interpreter_can_read_and_interpret_file() { + assert_eq!("12 foo true (x x)", eval_file("sample/test.txt")); + assert_eq!("true", eval_file("sample/test_full.txt")); + assert_eq!("1", eval_file("sample/test_normal.txt")); + assert_eq!("13", eval_file("sample/test_let.txt")); +} + +#[test] +fn repl_can_read_and_interpret_input() { + let input = "(def id (lam x x))\n(id 12)"; + let mut output = Vec::new(); + repl(&mut input.as_bytes(), &mut output); + assert_eq!("> true\n> 12\n> ", String::from_utf8(output).unwrap()); +} + +#[test] +fn repl_can_read_and_interpret_input_in_batch_mode() { + let input = "(def id (lam x x))\n(id 12)"; + let mut output = Vec::new(); + batch_eval(&mut input.as_bytes(), &mut output); + assert_eq!("true\n12\n", String::from_utf8(output).unwrap()); +} diff --git a/lambda-calcul/support/2024-10-10.md b/lambda-calcul/support/2024-10-10.md new file mode 100644 index 0000000..390ff10 --- /dev/null +++ b/lambda-calcul/support/2024-10-10.md @@ -0,0 +1,216 @@ +% Lambda Nantes \newline Compréhension, Interprétation et implémentation du $\lambda$-calcul +% **Workshop 1:** 10 Octobre 2024 @ **Palo IT Nantes** +% **Arnaud Bailly** (Cardano Foundation) et **Xavier Van de Woestyne** (Tarides) + +# Une nouvelle formule ! + +> En complément des présentations (habituelles), on voudrait proposer +> un nouveau format, plus interactif, potentiellement plus accessible +> et probablement plus _transportable_ en visio-conférence ! + +\pause + +- Des **workshops interactifs** +- **Indépendants** des langages et technologies (tout est le bienvenu) +- **Pérennes** dans le temps (en permettant notamment plusieurs + sessions sur un même sujet) +- Construction du platforme web pour le **suivi** des workshops (dans + un futur _proche_) + +# Pleins d'idées de sujets + +- **Compréhension, interprétation et implémentation du + $\lambda$-calcul** + +- Implémentation d'applications web, **dans un style fonctionnel** + (pour remplacer, par exemple, les affreuses applications + propriétaires que l'on utilise, comme Meetup, et **parce que c'est + très rigolo de réinventer la roue !**) + +- **Vos sujets** (en tant que suggestion, en tant qu'organisateurs, ce + _que vous voulez_), nous somme très ouverts à la contribution et à + l'apprentissage + +# Compréhension, Interprétation et implémentation du $\lambda$-calcul + +> On dit souvent qu'une compréhension fine du $\lambda$-calcul, la +> base de la programmation fonctionnelle est nécéssaire pour la +> comprendre. + +\pause + +> **Je prétend que c'est faux** (de la même manière qu'une +> compréhension fine de la théorie des catégories) n'est absolument un +> prérequis (ou une nécéssité) pour faire du Haskell efficacement. + +# Alors pourquoi ce premier Workshop ? + +- **Ça permet de s'initier à la construction d'un langage** +- C'est tout de même intéressant +- Le $\lambda$-calcul permet de **comprendre** certains points + théoriques liés à la compilation et l'interprétation de langages de + programmation +- Permet de se familiariser avec certains encodages dans des langages + plus riches +- Ça se découpe bien en plusieurs parties + +# C'est quoi le $\lambda$-calcul ? + +- Un système formel inventé dans les années 30, par **Alonzo Church** + qui décrit/fonde les concepts de **fonctions et d'applications de + fonctions** (qui est, en fait, un langage de programmation théorique) + +- Premier formalisme permettant de décrire et caractériser **les + fonctions récursives**, permettant de décrire la notion de + **calculabilité** (que l'on appellera, plus tard, la + _Turing-completude_)\newline\newline + +\pause + +> Comme pour le modèle de Herbrand-Gödel et les machines de turing, il +> est un des fondaments de la calculabilité, donc de la programmation +> et offre le même niveau d'expressivité. + + +# Aujourd'hui + +- Base conceptuelle des langages de programmations fonctionnels + modernes (laissant à la machine de Turing le rôle de base + conceptuelle des langages impératifs) + +- Permet de servir de base pour des modèles de programmations + (certains motifs de conceptions par exemple) + +- Sert le travail de l'ingénieur quotidiennement, notamment pour la + construction d'outils (ie: _refactor Engine_ qui est généralement + une conséquence de la $\beta$-reduction ou encore l'indexation + d'occurences via des formes de normalisation) + +- Permet d'implémenter des langages en étant étendu, de servir de + cible de compilation et aussi d'outil de comparaison entre des + langages (via des procédés d'analyse sémantique)\pause + +- Permet d'organiser des Workshops (dans lesquels on pourra ajouter + des fonctionnalités, un système de type etc) ! + +# Une grammaire **incroyablement** simple ! + +Les constituants du $\lambda$-calcul sont appelés des +$\lambda$-termes. + +## Variables : `<nom>` +`x` est une variable de nom `x`. + +## Abstraction : $\lambda$`<paramètres>.<corps>` + +$\lambda x. x$ est la fonction **identité**. + +## Application : `<fonction><lambda-terme>` + +($\lambda x. x$)`a`, on applique l'identité à `a`. + + +# En d'autres termes: + +``` +Term (M, N, O, ...): + M ::= x (variable) + M ::= λx.M (abstraction) + M ::= M N (application) +``` + + +> Comment résoudre des fonctions à plusieurs argument ? La +> **curryfication** ! + +# Avec quelques conventions de parenthèsages + +``` +(M) ≡ M +λx.(M N) ≡ λx.M N +λx.(λy.M) ≡ λx.λy.M +(M N) O ≡ M N O +``` + + +--- + +Avec ces trois éléments, on peut déjà construire beaucoup de choses ! +Le fait d'utiliser uniquement des fonctions et des applications pour +encoder des choses s'appelle l'utilisation de +**church-encodings**. (La base de l'OOP en vrai) + +## Des booléens + +- `TRUE := λx.λy.x` +- `FALSE := λx.λy.y` + +\pause + +- `AND := λp.λq.p q p` +- `OR := λp.λq.p p q` +- `NOT := λp.p FALSE TRUE` + +\pause + +- `IFTD := λp.λa.λb.p a b` + +--- + +## De l'arithmétiques + +- `0 := λfx.x` +- `1 := λfx.f x` +- `2 := λfx.f (f x)` +- `3 := λfx.f (f (f x))` +- etc. + +\pause + +- `SUCC := λn.λf.λx.f (n f x)` +- `PLUS := λm.λn.m SUCC n` +- etc. + + +# Première étape: décrire un AST + +Un **AST** (ou, Arbre de Syntaxe Abstrait) est une représentation +manipulable de notre syntaxe. + +Avec un AST, on peut, par exemple, considérer que les deux expressions +sont équivalentes : + +- `let f x = x + 1` +- `let f x = (+) x 1` + +Il est usuel d'utiliser des **sommes** pour décrire les différentes +branches (souvent récursives) de notre arbre ! + +# Concepts de variables **libres** + +> **Une peu naïvement** : Ensembles des variables qui ne sont pas des +> arguments (dans un scope donné). Par exemple: + +``` +λx.x # Pas de variables libres +λx.x+y # y est libre +``` + +Quand une variable n'est pas libre, elle est **liée** + +# Réductions + +Permettant de décrire des équivalence de Lambda Termes. + +- $\alpha$-conversion: la **résolution des noms** (`λx.x` = `λy.y`) + (qui entraine des **Substitutions**) +- $\beta$-conversion: l'**application de fonction** (`(λx.x × + 2) 7` + = `7 + 2` = `9`) +- $\eta$-reduction: `(λx.f x)` = `f` si `x` n'est pas **libre** + +La base de stratégie d'évaluation et d'optimisation ! (En effet, on +réduira généralement durant l'évaluation d'un programme) + +--- + +On a suffisamment de "bases" pour démarrer ! diff --git a/lambda-calcul/support/2024-10-10.pdf b/lambda-calcul/support/2024-10-10.pdf Binary files differnew file mode 100644 index 0000000..68a3c7b --- /dev/null +++ b/lambda-calcul/support/2024-10-10.pdf diff --git a/lambda-calcul/support/Makefile b/lambda-calcul/support/Makefile new file mode 100644 index 0000000..2a45ef1 --- /dev/null +++ b/lambda-calcul/support/Makefile @@ -0,0 +1,11 @@ +all: 2024-10-10.pdf + +%.pdf: %.md + pandoc -t beamer -f markdown+implicit_figures \ + -V theme:default -V aspectratio:169 \ + --pdf-engine=xelatex \ + -V monofont='DejaVu Sans Mono' \ + $(<) -o $(@) + +clean: + rm -rf *.pdf |
