Statically Typed Lisp

An example

#lang typed/racket ;; Using higher-order occurrence typing (define-type SrN (U String Number)) (: tog ((Listof SrN) -> String)) (define (tog l) (apply string-append (filter string? l))) (tog (list 5 "hello " 1/2 "world" (sqrt -1)))

I don't think this is really accurate anymore. Using the list data type as the compiler's internal representation causes problems as there is nowhere to store information the compiler needs need, such as locations for error reporting, or value representation for optimisation, and so on. You either end up using some awful hack (e.g. the second element of each list is an a-list of compiler specific info) or you use a different data type. This latter is the approach that Racket, the Lisp I'm most familiar with, takes. Programs are represented using a "syntax" data structure that is not list, though it can be converted into one.

See HLists (e.g. https://hackage.haskell.org/package/HList) for heterogeneous lists in Haskell. The techniques for implementing these are relatively (last 10 years or so).

All the cleverness of static typing falls apart with heterogeneous lists.

You can have heterogeneous lists in Haskell. What you don't have is open heterogeneity as in Scala (where List[Any] is a valid type). You have to decide how much heterogeneity you'll allow a priori, like so:

    data MyLang = Number Double | Str String | Sexp [MyLang] | Fn (MyLang -> MyLang)
    expr = Sexp [Str "+", Number 5, Number 7]

What Haskell doesn't give you (unless you use Data.Dynamic) is open heterogeneity. If you want to add ByteString to the above, you have to recompile it with a new case in the union. While you could add an extensible object-oriented system to Haskell (all major languages being Turing-complete, you can write a Ruby or Lisp in Haskell) the types in this language would probably not be recognized by Haskell. For most cases, this defeats the purpose of using Haskell, because we want the expressive types (at the expense of slightly reduced language expressivity). We'd rather have a type signature of (a -> b) -> [a] -> [b] than HRubyObject -> HRubyObject -> HRubyObject, with a bunch of runtime error checks (that take time to specify, reduce performance, and clutter source code).

With advanced uses of typeclasses, you can buy back a lot of the heterogeneity and code-level expressiveness of dynlangs (at the expense of dealing with complicated type signatures, language extensions, and scary-sounding concepts like "monad transformers"). There's little that you "can't" do in Haskell, insofar as you can build an arbitrary dynamic language within it. Haskell just requires you to decide a priori how much heterogeneity and reflection you want, and makes it hard to change that on the fly.

What I like about Haskell is how much discipline it demands. I don't expect to see the static vs. dynamic debate resolved within my lifetime, because those families of languages excel in different ways, but I like the intellectual exercise of having to make sure my design is sound before it even compiles. Static typing isn't "a silver bullet" and only catches ~30-50% of errors if used naively, but if you know how to use it and have a good design sense, you can bring that number way up (90%?). If your goal is to write robust code, you spend as much time thinking about testing in Haskell as in Python. The advantage of "the Haskell Way" is that most of those unit tests don't exist in code; they're implicit in the type system, or very tersely specified (with superior coverage) in QuickCheck.

What we want in a language, loosely speaking, is O(log n) added work ("accidental complexity") in terms of the size of the problem/functionality achieved. We can never get rid of that, but we'd like it to be sublinear as a function of what we're accomplishing. (Since our goals are most often subjective, the big-O notation is used loosely.) Inexpressive languages throw O(n) accidental complexity at you, but poor use of expressive languages throws O(n^2) or worse (in fact, potentially incomputably worse, since arbitrary code comprehension is formally undecidable) maintenance complexity at you. I don't know if Haskell is at the O(log n) level, for a priori accidental complexity, yet. But it's definitely sublinear (maybe O(n1/3)) and, in the real world, that's good enough. (If you program for the business, there's plenty of "other" complexity that is O(n) or worse, and more infuriating than any technical challenge.)

I'd rephrase that to use way as the noun that it is: Everything is on the way it is, because it goed^W went that way.

> It would be in the same category as dynamically typed Haskell.

But that's possible (and available).

It's not a contradiction -- we've built it: http://docs.racket-lang.org/ts-guide/

Also: https://github.com/clojure/core.typed

I've said it before, but I'll say it again. Common Lisp already features strong static typing (the example below uses SBCL):

  * (defun foo (x) x)

  FOO
  * (declaim (ftype (function (fixnum)) foo))

  * (defun bar (y) (declare (string y)) (foo y))
  ; in: DEFUN BAR
  ;     (FOO Y)
  ; 
  ; caught WARNING:
  ;   Derived type of Y is
  ;     (VALUES STRING &OPTIONAL),
  ;   conflicting with its asserted type
  ;     FIXNUM.
  ;   See also:
  ;     The SBCL Manual, Node "Handling of Types"
  ; 
  ; compilation unit finished
  ;   caught 1 WARNING condition

  BAR

One could also declare the function signature first (perhaps in skeleton code generated by modelling tools). Then, if someone implements it incorrectly, the compiler will throw an error (again, SBCL):

  * (declaim (ftype (function (fixnum)) qux))

  * (defun qux (z) (car z))
  ; in: DEFUN QUX
  ;     (CAR Z)
  ; 
  ; caught WARNING:
  ;   Derived type of Z is
  ;     (VALUES FIXNUM &OPTIONAL),
  ;   conflicting with its asserted type
  ;     LIST.
  ;   See also:
  ;     The SBCL Manual, Node "Handling of Types"
  ; 
  ; compilation unit finished
  ;   caught 1 WARNING condition

  QUX

Here's a good discussion of static typing in Common Lisp:

http://www.lispforum.com/viewtopic.php?f=2&t=191

TL;DR is that many CL implementations will check types at compile time, but for appropriate speed and safety settings, they will also generate code that checks types at runtime, too.