blisp/
lib.rs

1//! # BLisp
2//!
3//! BLisp is a well typed Lisp like programming language which adopts effect
4//! system for no_std environments.
5//! BLisp supports higher order RPCs like higher order functions
6//! of functional programing languages.
7//!
8//! This repository provides only a library crate.
9//! Please see [blisp-repl](https://github.com/ytakano/blisp-repl) to use BLisp,
10//! or [baremetalisp](https://github.com/ytakano/baremetalisp) which is a toy OS.
11//!
12//! [Homepage](https://ytakano.github.io/blisp/) is here.
13//!
14//! ## Features
15//!
16//! - Algebraic data type
17//! - Generics
18//! - Hindley–Milner based type inference
19//! - Effect system to separate side effects from pure functions
20//! - Big integer
21//! - Supporting no_std environments
22//!
23//! ## Examples
24//!
25//! ### Simple Eval
26//!
27//! ```
28//! let code = "
29//! (export factorial (n) (Pure (-> (Int) Int))
30//!     (factorial' n 1))
31//!
32//! (defun factorial' (n total) (Pure (-> (Int Int) Int))
33//!     (if (<= n 0)
34//!         total
35//!         (factorial' (- n 1) (* n total))))";
36//!
37//! let exprs = blisp::init(code, vec![]).unwrap();
38//! let ctx = blisp::typing(exprs).unwrap();
39//! let expr = "(factorial 10)";
40//! for result in blisp::eval(expr, &ctx).unwrap() {
41//!    println!("{}", result.unwrap());
42//! }
43//! ```
44//!
45//! ### Foreign Function Interface
46//!
47//! ```
48//! use blisp::{self, embedded};
49//! use num_bigint::BigInt;
50//!
51//! #[embedded]
52//! fn add_four_ints(a: BigInt, b: (BigInt, BigInt), c: Option<BigInt>) -> Result<BigInt, String> {
53//!     let mut result = a + b.0 + b.1;
54//!     if let Some(n) = c {
55//!         result += n;
56//!     }
57//!
58//!     Ok(result)
59//! }
60//!
61//! let code = "
62//! (export call_add_four_ints (n)
63//!     (IO (-> ((Option Int)) (Result Int String)))
64//!     (add_four_ints 1 [2 3] n))"; // call `add_four_ints` in Rust here.
65//!
66//! let exprs = blisp::init(code, vec![Box::new(AddFourInts)]).unwrap(); // extern `add_four_ints`
67//! let ctx = blisp::typing(exprs).unwrap();
68//! let result = blisp::eval("(call_add_four_ints (Some 4))", &ctx).unwrap();
69//!
70//! let front = result.front().unwrap().as_ref().unwrap();
71//! assert_eq!(front, "(Ok 10)");
72//! ```
73//!
74//! ### Expressions
75//!
76//! ```lisp
77//! "Hello, World!" ; string
78//! (+ 0x10 0x20)   ; 48
79//! (+ 0b111 0b101) ; 12
80//! (+ 0o777 0o444) ; 803
81//! (car '(1 2 3))  ; (Some 1)
82//! (cdr '(1 2 3))  ; '(2 3)
83//! (map (lambda (x) (* x 2)) '(8 9 10)) ; '(16 18 20)
84//! (fold + 0 '(1 2 3 4 5 6 7 8 9))      ; 45
85//! (reverse '(1 2 3 4 5 6 7 8 9))       ; '(9 8 7 6 5 4 3 2 1)
86//! (filter (lambda (x) (= (% x 2) 0)) '(1 2 3 4 5 6 7 8 9)) ; '(2 4 6 8)
87//! ```
88
89#![cfg_attr(not(test), no_std)]
90
91extern crate alloc;
92
93use core::fmt::Display;
94
95use alloc::{
96    boxed::Box,
97    collections::linked_list::LinkedList,
98    format,
99    string::{String, ToString},
100    vec::Vec,
101};
102
103pub mod coq;
104pub mod r#macro;
105pub mod parser;
106pub mod runtime;
107pub mod semantics;
108
109pub use blisp_embedded::embedded;
110use r#macro::{process_macros, Macros};
111use runtime::FFI;
112
113#[derive(Debug, Clone, Copy)]
114pub enum FileType {
115    Prelude,
116    User,
117    Eval,
118    Extern(u64),
119}
120
121/// indicate a position of file
122#[derive(Debug, Clone, Copy)]
123pub struct Pos {
124    pub file_id: FileType,
125    pub line: usize,   // line number, 0 origin
126    pub column: usize, // column number, 0 origin
127}
128
129impl Display for Pos {
130    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
131        write!(f, "{:?}:{}:{}", self.file_id, self.line, self.column)
132    }
133}
134
135/// error message
136#[derive(Debug)]
137pub struct LispErr {
138    pub msg: String,
139    pub pos: Pos,
140}
141
142impl LispErr {
143    fn new(msg: String, pos: Pos) -> LispErr {
144        LispErr { msg, pos }
145    }
146}
147
148pub struct TypingContext {
149    exprs: LinkedList<parser::Expr>,
150    ext_funs: Vec<Box<dyn FFI + Send>>,
151    macros: Macros,
152}
153
154/// initialize BLisp with code
155///
156/// # Example
157///
158/// ```
159/// let code = "(export factorial (n) (Pure (-> (Int) Int))
160///    (if (<= n 0)
161///        1
162///        (* n (factorial (- n 1)))))";
163///
164/// blisp::init(code, vec![]).unwrap();
165/// ```
166pub fn init(code: &str, ext_funs: Vec<Box<dyn FFI + Send>>) -> Result<TypingContext, LispErr> {
167    let prelude = include_str!("prelude.lisp");
168    // let prelude = "";
169    let mut ps = parser::Parser::new(prelude, FileType::Prelude);
170    let mut exprs = match ps.parse() {
171        Ok(e) => e,
172        Err(e) => {
173            let msg = format!("Syntax Error: {}", e.msg);
174            return Err(LispErr::new(msg, e.pos));
175        }
176    };
177
178    for (i, fun) in ext_funs.iter().enumerate() {
179        let mut ps = parser::Parser::new(fun.blisp_extern(), FileType::Extern(i as u64));
180        match ps.parse() {
181            Ok(mut e) => {
182                exprs.append(&mut e);
183            }
184            Err(e) => {
185                let msg = format!("Syntax Error: {}", e.msg);
186                return Err(LispErr::new(msg, e.pos));
187            }
188        }
189    }
190
191    let mut ps = parser::Parser::new(code, FileType::User);
192    match ps.parse() {
193        Ok(mut e) => {
194            exprs.append(&mut e);
195
196            let macros = match process_macros(&mut exprs) {
197                Ok(macros) => macros,
198                Err(e) => {
199                    let msg = format!("Macro Error: {}", e.msg);
200                    return Err(LispErr::new(msg, e.pos));
201                }
202            };
203
204            Ok(TypingContext {
205                exprs,
206                ext_funs,
207                macros,
208            })
209        }
210        Err(e) => {
211            let msg = format!("Syntax Error: {}", e.msg);
212            Err(LispErr::new(msg, e.pos))
213        }
214    }
215}
216
217/// perform type checking and inference
218///
219/// # Example
220///
221/// ```
222/// let code = "(export factorial (n) (Pure (-> (Int) Int))
223///    (if (<= n 0)
224///        1
225///        (* n (factorial (- n 1)))))";
226///
227/// let exprs = blisp::init(code, vec![]).unwrap();
228/// blisp::typing(exprs).unwrap();
229/// ```
230pub fn typing(exprs: TypingContext) -> Result<semantics::Context, LispErr> {
231    match semantics::exprs2context(exprs) {
232        Ok(c) => Ok(c),
233        Err(e) => {
234            let msg = format!("Typing Error: {}", e.msg);
235            Err(LispErr::new(msg, e.pos))
236        }
237    }
238}
239
240/// evaluate an expression
241///
242/// # Example
243///
244/// ```
245/// let code = "(export factorial (n) (Pure (-> (Int) Int))
246///    (if (<= n 0)
247///        1
248///        (* n (factorial (- n 1)))))";
249///
250/// let exprs = blisp::init(code, vec![]).unwrap();
251/// let ctx = blisp::typing(exprs).unwrap();
252/// let expr = "(factorial 30)";
253/// for result in blisp::eval(expr, &ctx).unwrap() {
254///    println!("{}", result.unwrap());
255/// }
256/// ```
257pub fn eval(
258    code: &str,
259    ctx: &semantics::Context,
260) -> Result<LinkedList<Result<String, String>>, LispErr> {
261    runtime::eval(code, ctx)
262}
263
264pub fn transpile(ctx: &semantics::Context) -> String {
265    let mut s = "".to_string();
266    for (_, d) in ctx.data.iter() {
267        s = format!("{}{}\n", s, coq::to_coq_data(d));
268    }
269
270    for (_, f) in ctx.funs.iter() {
271        s = format!("{}{}\n", s, coq::to_coq_func(f));
272    }
273
274    format!("{}\n\n{}", coq::import(), s)
275}
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280
281    #[test]
282    fn test_macro() {
283        let expr = "
284(macro add
285    ((add $e1 $e2) (+ $e1 $e2))
286    ((add $e1 $e2 $e3 ...) (+ $e1 (add $e2 $e3 ...))))
287
288(macro minus
289    ((_ $e1 $e2) (- $e1 $e2))
290    ((_ $e1 $e2 $e3 ...) (- $e1 (minus $e2 $e3 ...))))
291
292(macro tuple_to_list
293    ((_ []) ((lambda (x) x) '()))
294    ((_ [$e ...]) ((lambda (x) x) '($e ...))))
295
296(macro none ((_ _) ([])))
297
298(tuple_to_list [])
299(tuple_to_list [1 2 3])
300
301(add 1 2 3 4 5)
302
303(defun test_add () (Pure (-> () Int))
304    (add 1 2 3 4 (minus 5 6 7) 8))
305
306(add 1)
307
308(none 123)
309";
310
311        let typing_context = init(expr, vec![]).unwrap();
312
313        for expr in typing_context.exprs.iter() {
314            println!("{expr}");
315        }
316    }
317
318    fn eval_result(code: &str, ctx: &semantics::Context) {
319        for r in eval(code, ctx).unwrap() {
320            println!("{} -> {}", code, r.unwrap());
321        }
322    }
323
324    #[test]
325    fn ops() {
326        let exprs = init("", vec![]).unwrap();
327        let ctx = typing(exprs).unwrap();
328        eval_result("(neq (Some \"Hello\") 10)", &ctx);
329        eval_result("(chars \"Hello, World!\")", &ctx);
330        eval_result("(str '(`H` `e` `l` `l` `o`))", &ctx);
331        eval_result("`\\``", &ctx);
332        eval_result("(= `h` `h`)", &ctx);
333        eval_result("(<< 8 4)", &ctx);
334        eval_result("(>> 128 4)", &ctx);
335        eval_result("\"Hello, World!\"", &ctx);
336        eval_result("(= \"Hello, World!\" \"Hello, World!\")", &ctx);
337        eval_result("(= (Some 1) (Some 2))", &ctx);
338        eval_result("(< (Some 1) (Some 2))", &ctx);
339        eval_result("(> (Some 1) (Some 2))", &ctx);
340        eval_result("(= \"Hello\" \"Hel\")", &ctx);
341        eval_result("(eq \"Hello\" 10)", &ctx);
342        eval_result("(lt \"Hello\" 10)", &ctx);
343        eval_result("(lt 5 10)", &ctx);
344        eval_result("(+ 0x10 0x20)", &ctx);
345        eval_result("(+ 0b111 0b101)", &ctx);
346        eval_result("(+ 0o777 0o444)", &ctx);
347        eval_result("(+ 10 20)", &ctx);
348        eval_result("(pow 10 20)", &ctx);
349        eval_result("(band 1 0)", &ctx);
350        eval_result("(band 1 1)", &ctx);
351        eval_result("(bor 1 0)", &ctx);
352        eval_result("(bor 1 1)", &ctx);
353        eval_result("(bxor 1 0)", &ctx);
354        eval_result("(bxor 1 1)", &ctx);
355        eval_result("(sqrt 16)", &ctx);
356        eval_result("(sqrt -1)", &ctx);
357    }
358
359    #[test]
360    fn lambda() {
361        let expr = "(export lambda-test (f)
362    (Pure (-> ((Pure (-> (Int Int) Int))) Int))
363    (f 10 20))
364";
365        let exprs = init(expr, vec![]).unwrap();
366        let ctx = typing(exprs).unwrap();
367        let e = "(lambda-test (lambda (x y) (* x y)))";
368        eval_result(e, &ctx);
369
370        let e = "(lambda-test +)";
371        eval_result(e, &ctx);
372    }
373
374    #[test]
375    fn list() {
376        let expr = "
377(export head (x) (Pure (-> ('(Int)) (Option Int)))
378    (match x
379        ((Cons n _) (Some n))
380        (_ None)))
381(export tail (x) (Pure (-> ('(Int)) (Option Int)))
382    ; match expression
383    (match x
384        (Nil None)
385        ((Cons n Nil) (Some n))
386        ((Cons _ l) (tail l))))
387";
388        let exprs = init(expr, vec![]).unwrap();
389        let ctx = typing(exprs).unwrap();
390
391        let e = "(head '(30 40 50))";
392        eval_result(e, &ctx);
393
394        let e = "(tail '(30 40 50))";
395        eval_result(e, &ctx);
396    }
397
398    #[test]
399    fn tuple() {
400        let expr = "(export first (x) (Pure (-> ([Int Bool]) Int))
401    (match x
402        ([n _] n)))
403";
404        let exprs = init(expr, vec![]).unwrap();
405        let ctx = typing(exprs).unwrap();
406        let e = "(first [10 false])";
407        eval_result(e, &ctx);
408    }
409
410    #[test]
411    fn prelude() {
412        let expr = "
413(export factorial (n) (Pure (-> (Int) Int))
414    (factorial' n 1))
415(defun factorial' (n total) (Pure (-> (Int Int) Int))
416    (if (<= n 0)
417        total
418        (factorial' (- n 1) (* n total))))
419";
420        let exprs = init(expr, vec![]).unwrap();
421        let ctx = typing(exprs).unwrap();
422
423        let e = "(Some 10)";
424        eval_result(e, &ctx);
425
426        let e = "(car '(1 2 3))";
427        eval_result(e, &ctx);
428
429        let e = "(cdr '(1 2 3))";
430        eval_result(e, &ctx);
431
432        let e = "(map (lambda (x) (* x 2)) '(8 9 10))";
433        eval_result(e, &ctx);
434
435        let e = "(fold + 0 '(1 2 3 4 5 6 7 8 9))";
436        eval_result(e, &ctx);
437
438        let e = "(reverse '(1 2 3 4 5 6 7 8 9))";
439        eval_result(e, &ctx);
440
441        let e = "(filter (lambda (x) (= (% x 2) 0)) '(1 2 3 4 5 6 7 8 9))";
442        eval_result(e, &ctx);
443
444        let e = "(factorial 2000)";
445        eval_result(e, &ctx);
446    }
447
448    #[test]
449    fn callback() {
450        let expr = "
451(export callback (x y z) (IO (-> (Int Int Int) (Option Int)))
452    (call-rust x y z))";
453        let exprs = init(expr, vec![]).unwrap();
454        let mut ctx = typing(exprs).unwrap();
455
456        use num_bigint::BigInt;
457        use std::boxed::Box;
458        let fun = |x: &BigInt, y: &BigInt, z: &BigInt| {
459            let n = x * y * z;
460            println!("n = {}", n);
461            Some(n)
462        };
463        ctx.set_callback(Box::new(fun));
464
465        let e = "(callback 100 2000 30000)";
466        eval_result(e, &ctx);
467    }
468
469    #[test]
470    fn do_transpile() {
471        let expr = "
472        (defun snoc (l y)
473        (Pure (-> (
474            '(t) t)
475        '(t)))
476        (match l
477            (nil (Cons y nil))
478            ((Cons h b) (Cons h (snoc b y)))))
479
480        (defun rev (l)
481        (Pure (-> (
482            '(t))
483        '(t)))
484        (match l
485            (nil nil)
486            ((Cons h t) (snoc (rev t) h))))
487            ";
488        let exprs = init(expr, vec![]).unwrap();
489        let ctx = typing(exprs).unwrap();
490
491        println!("{}", transpile(&ctx));
492    }
493
494    #[test]
495    fn test_multibyte() {
496        let expr = "あ";
497        let _exprs = init(expr, vec![]).unwrap();
498
499        let expr = "";
500        let exprs = init(expr, vec![]).unwrap();
501        let ctx = typing(exprs).unwrap();
502
503        let e = "\"あ\"";
504        let r = eval(e, &ctx).unwrap();
505        println!("{r:?}");
506
507        let e = "`あ`";
508        let r = eval(e, &ctx).unwrap();
509        println!("{r:?}");
510    }
511}
blisp/lib.rs

blisp/
lib.rs
