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    fn eval_first(code: &str, ctx: &semantics::Context) -> String {
282        eval(code, ctx)
283            .unwrap()
284            .front()
285            .unwrap()
286            .as_ref()
287            .unwrap()
288            .clone()
289    }
290
291    #[test]
292    fn test_macro() {
293        let expr = "
294(macro add
295    ((add $e1 $e2) (+ $e1 $e2))
296    ((add $e1 $e2 $e3 ...) (+ $e1 (add $e2 $e3 ...))))
297
298(macro minus
299    ((_ $e1 $e2) (- $e1 $e2))
300    ((_ $e1 $e2 $e3 ...) (- $e1 (minus $e2 $e3 ...))))
301
302(macro tuple_to_list
303    ((_ []) ((lambda (x) x) '()))
304    ((_ [$e ...]) ((lambda (x) x) '($e ...))))
305
306(macro none ((_ _) ([])))
307
308(tuple_to_list [])
309(tuple_to_list [1 2 3])
310
311(add 1 2 3 4 5)
312
313(defun test_add () (Pure (-> () Int))
314    (add 1 2 3 4 (minus 5 6 7) 8))
315
316(add 1)
317
318(none 123)
319";
320
321        let typing_context = init(expr, vec![]).unwrap();
322
323        for expr in typing_context.exprs.iter() {
324            println!("{expr}");
325        }
326    }
327
328    #[test]
329    fn test_macro_hygiene_lambda() {
330        let expr = "
331(macro with_tmp
332    ((_ $x) ((lambda (tmp) (+ tmp $x)) 1)))
333
334(export test (tmp) (Pure (-> (Int) Int))
335    (with_tmp tmp))
336";
337
338        let ctx = typing(init(expr, vec![]).unwrap()).unwrap();
339        assert_eq!(eval_first("(test 10)", &ctx), "11");
340    }
341
342    #[test]
343    fn test_macro_hygiene_let() {
344        let expr = "
345(macro with_tmp
346    ((_ $x) (let ((tmp 1)) (+ tmp $x))))
347
348(export test (tmp) (Pure (-> (Int) Int))
349    (with_tmp tmp))
350";
351
352        let ctx = typing(init(expr, vec![]).unwrap()).unwrap();
353        assert_eq!(eval_first("(test 10)", &ctx), "11");
354    }
355
356    #[test]
357    fn test_macro_hygiene_match() {
358        let expr = "
359(macro match_some
360    ((_ $x)
361        (match (Some 1)
362            ((Some v) (+ v $x))
363            (None 0))))
364
365(export test (v) (Pure (-> (Int) Int))
366    (match_some v))
367";
368
369        let ctx = typing(init(expr, vec![]).unwrap()).unwrap();
370        assert_eq!(eval_first("(test 10)", &ctx), "11");
371    }
372
373    fn eval_result(code: &str, ctx: &semantics::Context) {
374        for r in eval(code, ctx).unwrap() {
375            println!("{} -> {}", code, r.unwrap());
376        }
377    }
378
379    #[test]
380    fn ops() {
381        let exprs = init("", vec![]).unwrap();
382        let ctx = typing(exprs).unwrap();
383        eval_result("(neq (Some \"Hello\") 10)", &ctx);
384        eval_result("(chars \"Hello, World!\")", &ctx);
385        eval_result("(str '(`H` `e` `l` `l` `o`))", &ctx);
386        eval_result("`\\``", &ctx);
387        eval_result("(= `h` `h`)", &ctx);
388        eval_result("(<< 8 4)", &ctx);
389        eval_result("(>> 128 4)", &ctx);
390        eval_result("\"Hello, World!\"", &ctx);
391        eval_result("(= \"Hello, World!\" \"Hello, World!\")", &ctx);
392        eval_result("(= (Some 1) (Some 2))", &ctx);
393        eval_result("(< (Some 1) (Some 2))", &ctx);
394        eval_result("(> (Some 1) (Some 2))", &ctx);
395        eval_result("(= \"Hello\" \"Hel\")", &ctx);
396        eval_result("(eq \"Hello\" 10)", &ctx);
397        eval_result("(lt \"Hello\" 10)", &ctx);
398        eval_result("(lt 5 10)", &ctx);
399        eval_result("(+ 0x10 0x20)", &ctx);
400        eval_result("(+ 0b111 0b101)", &ctx);
401        eval_result("(+ 0o777 0o444)", &ctx);
402        eval_result("(+ 10 20)", &ctx);
403        eval_result("(pow 10 20)", &ctx);
404        eval_result("(band 1 0)", &ctx);
405        eval_result("(band 1 1)", &ctx);
406        eval_result("(bor 1 0)", &ctx);
407        eval_result("(bor 1 1)", &ctx);
408        eval_result("(bxor 1 0)", &ctx);
409        eval_result("(bxor 1 1)", &ctx);
410        eval_result("(sqrt 16)", &ctx);
411        eval_result("(sqrt -1)", &ctx);
412    }
413
414    #[test]
415    fn lambda() {
416        let expr = "(export lambda-test (f)
417    (Pure (-> ((Pure (-> (Int Int) Int))) Int))
418    (f 10 20))
419";
420        let exprs = init(expr, vec![]).unwrap();
421        let ctx = typing(exprs).unwrap();
422        let e = "(lambda-test (lambda (x y) (* x y)))";
423        eval_result(e, &ctx);
424
425        let e = "(lambda-test +)";
426        eval_result(e, &ctx);
427    }
428
429    #[test]
430    fn list() {
431        let expr = "
432(export head (x) (Pure (-> ('(Int)) (Option Int)))
433    (match x
434        ((Cons n _) (Some n))
435        (_ None)))
436(export tail (x) (Pure (-> ('(Int)) (Option Int)))
437    ; match expression
438    (match x
439        (Nil None)
440        ((Cons n Nil) (Some n))
441        ((Cons _ l) (tail l))))
442";
443        let exprs = init(expr, vec![]).unwrap();
444        let ctx = typing(exprs).unwrap();
445
446        let e = "(head '(30 40 50))";
447        eval_result(e, &ctx);
448
449        let e = "(tail '(30 40 50))";
450        eval_result(e, &ctx);
451    }
452
453    #[test]
454    fn tuple() {
455        let expr = "(export first (x) (Pure (-> ([Int Bool]) Int))
456    (match x
457        ([n _] n)))
458";
459        let exprs = init(expr, vec![]).unwrap();
460        let ctx = typing(exprs).unwrap();
461        let e = "(first [10 false])";
462        eval_result(e, &ctx);
463    }
464
465    #[test]
466    fn prelude() {
467        let expr = "
468(export factorial (n) (Pure (-> (Int) Int))
469    (factorial' n 1))
470(defun factorial' (n total) (Pure (-> (Int Int) Int))
471    (if (<= n 0)
472        total
473        (factorial' (- n 1) (* n total))))
474";
475        let exprs = init(expr, vec![]).unwrap();
476        let ctx = typing(exprs).unwrap();
477
478        let e = "(Some 10)";
479        eval_result(e, &ctx);
480
481        let e = "(car '(1 2 3))";
482        eval_result(e, &ctx);
483
484        let e = "(cdr '(1 2 3))";
485        eval_result(e, &ctx);
486
487        let e = "(map (lambda (x) (* x 2)) '(8 9 10))";
488        eval_result(e, &ctx);
489
490        let e = "(fold + 0 '(1 2 3 4 5 6 7 8 9))";
491        eval_result(e, &ctx);
492
493        let e = "(reverse '(1 2 3 4 5 6 7 8 9))";
494        eval_result(e, &ctx);
495
496        let e = "(filter (lambda (x) (= (% x 2) 0)) '(1 2 3 4 5 6 7 8 9))";
497        eval_result(e, &ctx);
498
499        let e = "(factorial 2000)";
500        eval_result(e, &ctx);
501    }
502
503    #[test]
504    fn callback() {
505        let expr = "
506(export callback (x y z) (IO (-> (Int Int Int) (Option Int)))
507    (call-rust x y z))";
508        let exprs = init(expr, vec![]).unwrap();
509        let mut ctx = typing(exprs).unwrap();
510
511        use num_bigint::BigInt;
512        use std::boxed::Box;
513        let fun = |x: &BigInt, y: &BigInt, z: &BigInt| {
514            let n = x * y * z;
515            println!("n = {}", n);
516            Some(n)
517        };
518        ctx.set_callback(Box::new(fun));
519
520        let e = "(callback 100 2000 30000)";
521        eval_result(e, &ctx);
522    }
523
524    #[test]
525    fn do_transpile() {
526        let expr = "
527        (defun snoc (l y)
528        (Pure (-> (
529            '(t) t)
530        '(t)))
531        (match l
532            (nil (Cons y nil))
533            ((Cons h b) (Cons h (snoc b y)))))
534
535        (defun rev (l)
536        (Pure (-> (
537            '(t))
538        '(t)))
539        (match l
540            (nil nil)
541            ((Cons h t) (snoc (rev t) h))))
542            ";
543        let exprs = init(expr, vec![]).unwrap();
544        let ctx = typing(exprs).unwrap();
545
546        println!("{}", transpile(&ctx));
547    }
548
549    #[test]
550    fn test_multibyte() {
551        let expr = "あ";
552        let _exprs = init(expr, vec![]).unwrap();
553
554        let expr = "";
555        let exprs = init(expr, vec![]).unwrap();
556        let ctx = typing(exprs).unwrap();
557
558        let e = "\"あ\"";
559        let r = eval(e, &ctx).unwrap();
560        println!("{r:?}");
561
562        let e = "`あ`";
563        let r = eval(e, &ctx).unwrap();
564        println!("{r:?}");
565    }
566}
blisp/lib.rs

blisp/
lib.rs
