Table of Contents

Bisp is a typed lisp, with a little less parenthesis, infix/postfix-notation when it makes sense, Julia-like optional static typing and multi-dispatching.

1 Zen

1.1 The essense of programming

The most important 4 aspects of programming in my opinion are:

  1. awareness of purely functional programming, i.e. write side effect free functions
  2. interactive development driven by REPL
  3. multiple dispatch. The gradual typing is useful for annotation purpose as well as enabling multiple dispatching, and typing should be annotated natually, right after the variable and inside function def (instead of before as in typed racket)
  4. syntactic abstraction in the form of DSLs. The zen of Python states that there should be one way to do one thing, the obvious way. Well, that way is the best language for the domain, which is not very obvious to support in Python.

I didn't write serious Haskell and OCaml, but I did not find that sophisticated typing very necessary, and Monads and Lazyness did not manifest loud enough to me.

1 and 2 are operational techniques, while 3 and 4 are features of language. Although almost all new languages provide meta-programming (the basic of syntactic abstraction) of varing levels, racket provides the most comprehensive syntactic abstraction toolkit, far beyond all others, and I think it is not very possible to achieve the same level of support on non-lispy languages. E.g. it is not very natural to create DSLs using Julia.

However, racket does not have proper and natural multiple dispatch. The Haskell-style typing annotation in typed racket is not as natural, the typing did not appear at the best location. The racket/generics library provides single dispatch, and the usage is quite cumbersome: users should just define the function without worrying about the gen:XXX interface and fallback implementation staff. The multimethod package has multiple dispatch. However, the typing annotation is even weirder, and there's no proper typing system and dispatching strategy in this little package.

Modern languages all have a proper module system. However, all languages are based on files, except the unison language. But the hash is not too useful other than the fact that the renaming is painless. OK, back to the module and file, my core idea is that there should not be file at all! And making the module and file system collaborate is most likely the most confusing thing in a language's module system. In BISP, you just write function defs under some module namespace. One of the reason for uisng a file system was that Unix has it, and there's only one way to write code: to open a file in an (CMD-based) text editor. BISP will provide some better way to write your program, a visual way with some features such as proper server/client separation. Another issue is that inside a file, existing languages typically do not distinguish internal functions and external APIs very well. Not to say that I want a system that have (HEBI: internal helper functions and APIs at arbitrary granularity).

One more thing, I would love to use BISP on microcontrollers too. This would require some thinking regarding racket's backend to satisfy the small memory footprint as well as a proper and native REPL and front-end interface, the bisp notebook maybe?. Besides microcontrollers, I would want to extend the usage landscape to all low-level scenarios, e.g. the once used to be C, to remove the \#ifdefs (i.e. ir-elegant machine-dependence check) and \#defines (i.e. macros-done-wrong).

If everything goes well, I should provide a (HEBI: serverless cloud computing infra)! To abstract over the OS/VM/container and language runtime.

1.2 Rationale

Parenthesis is a good thing, as always, because:

  • easy to parse, thus easy for syntax extension
  • unambiguous
  • structural editing

However, too much parenthesis creates readability problem, less elegent than Haskell, OCaml and Julia.

And due to insisting on parenthesis, some intuitive syntax becomes cubersome:

  • struct field accessing, the dot-notation, is missing
  • hard to do array indexing and slicing, e.g. arr[3,0:7,:]

Lisp sytems traditionally use dynamic typing. But static typing can be very useful annotations for programming in general. It is hard to add inline type annotations elegently due that additional parenthesis must be created for grouping purpose. Prior art: typed racket, contracts, clojure specs.

Lisp dialects also fall short on multi-dispatch generic functions, i.e. functions can be dispatched based on type and number of its arguments. This matters a lot to save the namespace of functions, and makes the program elegent and extensible. Although racket and gerbil have generic methods, clojure has defmulti, the support not as great as those in Julia.

Bisp is designed to maintain the good part of lisp, while overcoming the afore-mentioned cons.

1.3 Implementation

The semantic is mostly identical to that of Julia. Thus, it is probably best to implement the syntax atop Julia or Julia's IR.

It might also make sense to freely mix Julia and Bisp at the top-level and by a (JL 1+2*3) syntax for e.g. mathematical equations:

;; julia code
struct Pad end
foo(a,b) = a + b
;; Bisp code
(defn bar [a] (foo a 1))
(def var (JL
          1 .+ ones(3,2) .* zeros(2,3)))

Julia and Bisp functions can be freely called by each other as well.

In summary, implementing Bisp on top of Julia gives:

  • easy to implement
  • Julia's JIT compiler, optimization, LLVM backend provides a solid performance fundation.
  • access to all those Julia libraries, thus this might be the first lisp-for-statistics

1.3.1 UPDATE 1

I found syntactic abstraction harder to reimplement than multiple dispatch, thus it seems quite easy to implement the rough BISP on top of racket, and I should be able to use all racket's amazing libraries. However, naive multiple dispatching might produce inefficient code, thus I probably need to look into optimization at some point.

And I still want to use Julia's library and all other language's libraries. But instead of native foreign function interface, I prefer something that I coined (HEBI: "source-level FFI"). This is a HUGE idea. For Julia, I will need to implement a syntactic expander for Julia's macros, and a Julia syntac transformer to load Julia's code directly into racket. Julia code might make base library calls or C FFIs. In this case, I would need to map Julia base library call to racket, and make corresponding C native FFI. I'm not sure how possible it is to map the entire Julia base library.

Actually, I don't need to really implement the subtyping and union type. That is needed, but not urgently useful, I can live without it for now. This will make the dispatching much simpler, because the ordering of methods based on specificity is easier, I just need to order all custom types before non-typed ones. And I need to properly mix the primitive types and user-defined types. Most likely I need to have a wrapper name (via syntax) for each of the primitive types. See https://docs.racket-lang.org/ts-reference/type-ref.html for a list.

Importantly, the struct field access should be converted to generic methods.

2 The Language

2.1 Field Accessing with Dot-Notation

Prior art: cubersome struct field accessing, the dot-notation is missing

;; struct
(struct Rect w h)
(let ([r (Rect 2 3)])
  ;; field accessing is cubersome
  (* (Rect-w r)
     (Rect-h r)))

The problems:

  • (foo-a x), not elegent
  • The pattern matching with destructuring binds
    • fragile
    • have to bind all the fields

Instead, Bisp uses dot-notation:

(defstruct Rect
  w::Number h)

(defstruct Circle r)

(let [a (Rect)
      b (Circle)]
  ;; access using dot notation
  (+ a.w b.r))

2.2 Multi-Dimensional Array: Indexing and Slicing

Prior art: hard to do array indexing and slicing, e.g. the racket way:

;; array indexing and slicing
(array-ref arr #(2 3))
(array-set! brr #(2 3) 10)
(array-slice-ref arr (list (::) (:: #f #f -1)))

Bisp uses postfix indexing and slicing:

;; define an array
(def arr (ones 3 2))
;; indexing: I found comma probably makes it more clear here
arr[1, 2]
;; slicing
arr[:, 0:1]

;; array type
(defn foo [a::Array{Any 3} b]

2.3 Optional Inline Type Annotation

Previous lisp is hard to do inline type annotations. Prior art: typed racket, contracts, clojure specs.

For example, typed racket:

;; outline annotation
(: distance (-> pt pt Real))
(define (distance p1 p2)
  (sqrt (+ (sqr (- (pt-x p2) (pt-x p1)))
           (sqr (- (pt-y p2) (pt-y p1))))))

;; inline annotations
(let ([x : Number 7])
  (add1 x))
(lambda ([x : Number] [y : String]) (+ x 5))

The problems:

  • I prefer inline type annotation
  • the inline notation of the typed racket introduces extra parenthesis, due to added spaced words.

Instead, the type annotations in Bisp simply uses y::String without extra spaces, and it should be nice and clear:

;; optional type
(defn foo [a::Number b] nil)
(defn foo [a::String b] nil)
;; union type
(defn foo [a::Union{Integer, Float} b] nil)

Support parametric types

;; parametric type
(defn foo [a::Number b c::T d::T
           #:where (<: T Real)]

2.4 Multi-Dispatch Generic Functions by Default

ALL functions are generic methods. You define the same name multiple times (instead of define foobar-number, foobar-string), and they are dispatched upon calling:

;; by default, all functions are methods
(defn foo [a] nil)
(defn foo [a b] "no annotation")
;; optional type
(defn foo [a::Number b] "number")
(defn foo [a::String b] "string")

; => generic function with 4 methods

2.5 function defs, default and keyword arguments

Bisp is lisp-1, i.e. unified namespace for functions and variables. Functions are first-class, the following defs are equivalent:

(defn foo [a b] nil)
;; same as
(def foo (λ [a b] nil))

Default arguments are given by infix notation. You don't specify type and default value together because it can be inferred by the value. All default values must be after non-default ones.

(defn foo [a b=3 c="default"] nil)

Keyword arguments are whatever after &:

;; keyword arguments separated by #:key. Here default values can be in any order
(defn foo [a::Number b c=3
           & x::String y z="defz"]
;; function call with keyword arguments
(foo 1 2 x="X" y=8)

varargs support with intuitive ... syntax as Julia, in both function defs and callsite, and wherever makes sense:

;; var args in both function definition and callsite
(defn foo [a::String b::Number args...]
(foo "hello" 8 '(a l i s t)...)

;; also support slicing inside a list or wherever appropriate, not just function callsite
(1 2 '(3 4 5)... 6 7)