Hacker News new | past | comments | ask | show | jobs | submit login
BLisp: A Statically Typed Lisp Like Language (ytakano.github.io)
121 points by agentofuser on June 27, 2021 | hide | past | favorite | 50 comments



Since the point of s-expression syntax/homoiconicity is macros, I'm surprised to not see any mention of them in the feature list linked here. Does BLisp support macros? If so, what kind?

Also, is there an example of the type inference working?


Another reason for "code as data" is to enable (safe) remote code execution via RPC.

For example you may want to query a database with a custom filter predicate function. If you pass one of BLisp's `Pure` functions across the wire, the database could execute the function with relative safety (compared with using `eval` with a string, or whatever).

I find it frustrating that almost all popular languages lack any safe facility for this, so people have to create some limited query schema (with it's own custom wire encoding and mini-interpretter), or instantiate a sandbox for a non-pure language like Lua and eval a string, or else invent their own fully-blown programming language along the lines of BLisp.


I don't see a difference between (eval s-expression) and eval("some code"). `eval` is inherently insecure without special restricted runtime. Pureness doesn't guarantee security.


One side benefit of wasm appears to be enabling this scenario, but across many languages. The client gets to use almost any language they want, it's fast, and the wasm engines let's the service define a very specific api surface.


> Since the point of s-expression syntax/homoiconicity is macros

I don't equate S-expressions with macros. S-expressions make many things easier, including: simple and regular but expressive syntax, expressive function and variable names with basically any character sequence allowed, copy and paste-able code that just works, easy automatic code formatting.


I always feel that for lisp-like languages it's just not a good idea to make them statically typed. Their power is derived from macros and the fact that code is data and the other way around.

For statically typed languages, they only feel ergonomic to me if they have highly specialized syntax and if they really leverage the type-system (which is often in conflict with macros and runtime flexibility).


> I always feel that for lisp-like languages it's just not a good idea to make them statically typed. Their power is derived from macros and the fact that code is data and the other way around.

I completely agree with the idea that their power is derived from macros, but I vehemently disagree that macros are incompatible with a static type system. The type of a form can be just a simple ADT

    data Form = FInt Int
              | FCons Form Form
              | FNil
              | FString String
              | ...
and a macro is just a function taking Form as arguments and returning a Form. With standard HM type inference, your macros can look exactly like they do in a dynamically typed Lisp. If the backquote is just a reader macro that produces a Form:

    (defmacro double (x)
       `(* x x))
that would be expanded into

    (defmacro double (x)
       (FCons '* (FCons x (FCons x FNil))))
and type inference would determine that the type of double is

    double :: Form -> Form
And destructuring Forms is just normal ADT pattern matching.


> (defmacro double (x)

> `(* x x))

Two bugs in two lines. Lisp is indeed a powerful language.


This wasn't meant to be valid code in any existing lisp, just lisp pseudo code. The behaviors you describe as bugs don't exist in all macro systems; for example, some macro systems automatically splice symbols from the context, some automatically prevent double-evaluation, and in purely functional languages double-evaluation doesn't matter anyway. I didn't want to get distracted by these irrelevant details from my main point, which, alas, has happened anyway.


What are the bugs? I am not familiar with lisp


Not OP so there might be others, but the two that I see are:

* most crucially, x isn't actually spliced in, meaning that the macro always literally expands to (+ x x). For example, (+ (double 2) 5) just expands to (+ (+ x x) 5), which will either crash if x is undefined or do something unexpected if x is.

* Even if x were spliced in properly, it gets evaluated twice. That's wasteful at best, and if x has some kind of side effect you (arguably) would get unexpected behaviour - the side effects would run twice.


Just for completeness, the correct macro would look like this:

  (defmacro double (x)
    (let ((temp (gensym))
    `(let ((,temp ,x))
       (+ temp temp))))
This way, when you write (double (parse-integer (read-line)) it would expand to

  (let ((#:uniqueName123 (parse-integer (read-line)))
    (+ #:uniqueName123 #:unique_symbol_123))
This guarantees that that the macro will not accidentally refer to some outside variable, and that it's argument will only be evaluated once (so that we don't read two lines of input in this example).

To explain a little bit what is going on: normally if you want to have an s-expression as a piece of data, you can use the quote special form - (quote (a b c)), usually shortened to '(a b c), returns a list containing three symbols (think of these as special strings), "a", "b", "c". If you want instead to evaluate a variable named "a", you can use the ` syntax, together with , and ,@. That is, `(,a b ,@c) will produce a list containing the value of a variable named "a", the symbol "b", and the value of a variable named "c", spliced in. If a is '(1 2 3) and c is '(4 5 6), `(,a b ,@c) will return the 5-element list ((1 2 3) b 4 5 6). Depending on how this is used further, b itself may be evaluated or just printed as is.

So, when expanding the macro, x will be initialized to the form provided as argument to double (not the value of that form). Then, temp will first be assigned a value that is produced by gensym, which generates a unique symbol; then, we'll return a list that represents some Lisp code binding the form represented by x to a variable whose name is the value returned by gensym, and then using this same variable name in a call to +. Finally, if this macro was "called" from regular lisp code, the expression it returned will be compiled or interpreted.

The macro could also be called from a special form like macroexpand-1, which would just return the list returned by the macro, without evaluating it; or macroexpand, which would do the same but recursively until there are no more macros in the expansion.

Note: a symbol is basically a string that can be used as a Lisp identifier, and is registered as such in the Lisp runtime. It is a separate type from string, but you can create a string from a symbol, or try to create a symbol from a string (which fails if the string is not a valid Lisp identifier).


I made a mistake when copy pasting and renaming something, the expanded code should have been

  (let ((#:uniqueName123 (parse-integer (read-line)))
    (+ #:uniqueName123 #:uniqueName123))


Surely

    (defmacro double (x)
        (let ((temp (gensym))
        `(let ((,temp ,x))
           (+ ,temp ,temp))))


The correct Common Lisp "macro" is

   (declaim (inline double))

   (defun double (x) (+ x x))


Oops, yes...


And this thread is why types help :)


Actually, if I had compiled the code produced by macroexpanding the macro, I would have gotten a warning:

  (compile nil '(lambda (x) (double x)))
  ;Compiler warnings :
  ;   In an anonymous lambda form: Undeclared free variable TEMP
  ;   In an anonymous lambda form: Unused lexical variable #:G520
Unfortunately, HN doesn't compile code you add in the comments...

Note, this is a warning and not an error because of CL's semantics, as the following is a valid program:

  (let ((temp 100))
    (double 10))
  ;returns 200
If you really wanted this effect though, normally you would have to declare that `temp` is a special variable:

  (declaim (special temp))
  (compile 'nil (lambda (x) (double x))
  ;Compiler warnings :
  ;   In an anonymous lambda form: Unused lexical variable #:G524


> meaning that the macro always literally expands to (+ x x)

Make that three bugs. The macro is called "double," but the numeric result is square.


Yep, see for example [0].

https://www.emacswiki.org/emacs/MacroUtilities


> and a macro is just a function taking Form as arguments and returning a Form

Why would it not just be a normal function then?


For the same reason that it wouldn't be a normal function in any Lisp. The difference is that the macro expander keeps a list of macros (separate from the set of normal functions in the program), so that when it sees a list with a symbol in the first position, it can look up that symbol in its macro list, and if it is a macro, it can call the macro and replace the macro call form with the return value of the macro. Then that gets fed into the evaluator, just like how macros work in any lisp.


I see, thank you so much for the explanation.

I think to clarify what I said - I didn't mean that static typing and macros are excluding each other. But I think you can either have a sound static type system and highly restricted macros, or less restricted macros but only an unsound type system. That's what I meant with "conflict".


No problem.

I'm interested to hear though why you think unrestricted macros make the type system unsound. Can you explain? The code generated by macros would be type-checked in the scheme I described, and type-unsafe code can't be executed by the macro itself, so it seems safe to me.


That is more of my impression that I have gathered from watching programming languages evolving. Rust is a good example, where they tried hard and the macros still become unsound. Scala is another good example where macros where unsound first and they had a really hard time to make them sound and work with the type-system - they lost a lot of power in the process.

Now, that doesn't have to mean that there is some inherential that stops the combination from super powerful macros and sound statical types from working together, but if anything, there is at least a compromise to be made in terms of resources, because it seems you would have to put a lot of effort into it.

> The code generated by macros would be type-checked in the scheme I described, and type-unsafe code can't be executed by the macro itself

Well, I would already consider this to be quite a big restriction though.


OCaml comes to mind as a static language with a macro system that sees a lot of use. I have no idea, though, how sound its type system is.

For my part, my sense is that it would be appropriate for a static lisp to choose completeness over soundness in its type system. Gödel's incompleteness theorem tells us that a static type checker can't be both sound and complete. So you've got to pick one, and there's something about sacrificing liberty for the sake of security that strikes me as being fundamentally un-lispy. All the talk further up about CL-style unhygienic macros seems like a good illustration of the relevant culture. You can't ignore Scheme and Racket, of course, but the longer tradition in Lisp is to say, "We'll give you all the power and all the footguns, and leave it up to you to use them responsibly."


> Well, I would already consider this to be quite a big restriction though.

Which part, the type-checking? Don't we want it to be type-checked?


I think it's a trade-off. By enforcing type-checking you now prevent people from altering the language in a way that could be both helpful and still safe even when not type-checking. (just because code doesn't type-check doesn't mean it will or could fail)


In some languages they can be, and macro calls are specially marked at the call site instead of (or in addition to) the definition.

But in LISP they are called and expanded implicitly, with the compiler/interpretter keeping track of what's what.


Because it's evaluated at compilation time.


Nitpicking: I think we say „expanded“ since evaluation is reserved for runtime.


Nim is statically typed and has a powerful macro facility:

https://nim-lang.org/docs/manual.html#macros

https://nim-lang.org/docs/macros.html


Here's a Lisp that's statically typed with macros:

https://github.com/lexi-lambda/hackett


Seems like you could still have macros, they would just evaluate before type checking. Rust works this way


To my knowledge, Rust's macros are not generally safe/sound by definition. And that can be a big problem down the line. Compare it to Scala. When they developed Scala 3, they changed macros and dropped a lot of their powers to make the safe/sound by definition and compatible with the typesystem. But they are now severely restricted when compared to Lisp macros.

EDIT: here's an example of a discussion about that in Rust: https://github.com/rust-lang/unsafe-code-guidelines/issues/2...


How do you feel about typed Racket?


I have never used racket, but what I have seen so far is pretty cool. But for typed Racket, I don't have a good feeling about it either. In particular because it is gradually typed, which kind of defeats the purpose, even though it might be practically useful. But I prefer to have actually compiler guarantees and not just best-effort help.


This might be a confusion about what "gradual typing" means. Typed Racket is a sound type system, and not just best effort. You get real compiler guarantees.


I don't think so. Here's an example: https://docs.racket-lang.org/ts-guide/typed-untyped-interact...

What that means is: I might call a function that tells me it will give me type X but instead it blows up. It's good that it blows up btw - that is the best thing a language with gradual typing can do for these cases. But it's not something I would be satisfied with.

Now, you can say that "blowing up" is part of any function anyways, but then my response would be that this severely hurts my ability to reason about how code will behave when run, so I'm giving up a huge benefit of a static type-system in general.


Why require Pure to be an annotation - why not make that the default without annotation - no effects? (Same as in Haskell)


Because it’s an effect system, it’s not returning monads. It’s a different kind of type system with different restrictions and benefits. You could make every function implicitly pure, but that would be syntactic sugar, as opposed to Haskell where pure-as-default is a consequence of how the type system is structured.


All functions in Haskell are pure: the function `putStrLn :: String -> IO ()` returns the same IO action for the given input.


But you don't need to annotate that, i.e `putStrLn :: Pure (String -> IO ())` (or as in the OP lisp: `Pure (-> String (IO ()))`)


I'm an author of BLisp. Thank you for your interest and discussion.

I'm now designing macros, but I cannot spend sufficient time to do. Anyway, macros will be implemented in the near future.

This language is being implemented for bare-metal or no_std environments in Rust. This is often called shell. I don't want to control OSes or devices by YAML or unsafe scripting languages.


Finally. I hope to get some time to see whether there are persistent data structures and how errors are reported and how dynamic the runtime is (in order to pass/evaluate s-expressions on runtime). My understanding is that it compiles directly to rust, so some compilation to web assembly, and almost direct C interop should be possible, right?


I wasn't fully able to tell if this was interpreted or compiled?

In any case, it looks neat, I think the intersection of static types and Lisps is a space that needs more experimentation with, so I'm happy to see that.

I hope eventually it gains more effects as well, with only Pure and IO, you can't do much of the cool things that effect systems bring.


It seems to be embedded in Rust: https://github.com/ytakano/blisp#how-to-use

so I would guess interpreted


Is this a lisp? It looks like an ml with s-expressions.


Lisp isn't necessarily just CL or Scheme. Further, if I recall correctly, ML started out as a lisp that later adopted infix syntax.


Not really. ML was developed as a new statically typed functional programming language for the LCF theorem prover. It was implemented in "Stanford Lisp". It did not have Lisp's s-expression based syntax.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: