The Roots of Lisp
paulgraham.com
paulgraham.com
But by the mid 2000s I started doing the kind of programming I used to do in LISP in Ruby. It's not that Ruby is a better language, but mostly it was the momentum factor and the availability of modern libraries for interfacing with the vast array of services out there. Using the crappy unreliable or outdated LISP libraries -- if they worked at all -- was tedious. Plus the LISP implementations were so outmoded. It was very hard to get other programers (except a couple enthusiasts) to work that way.
Ruby struct a decent compromise. And it's type system and object model are better than CL anyway. The syntax is more inconsistent, and the macro model nowhere near as good. But it turns out. Libraries and implementation matter a lot. Still, you can feel lots and lots of LISP influence in all the new runtime typed languages (Ruby, Python, etc). And 30 years later, listeners still rule!
In the end, we moved to Python for similar reasons.
But you inspired me. Thanks.
We want to know all about your Lisp experiences; or at least, I would personally love to hear about them.
Sir. I have no idea what to say. You were my direct inspiration for a long time. I'm a gamedev (worked at a couple studios now) and I've wanted to integrate Lisp into gameplay for years. I even got a Franz CL evaluation. The discovery of GOAL/Crash Bandicoot further motivated my efforts.
Ultimately nothing came out of it; Lua and Python are just so much easier to integrate into a realtime C++ simulation (video game) and are nearly as effective. However, I became a better programmer for life. Discovering GOAL enabled me to think like "if Naughty Dog could do it, then so could I", which sparked me along a path of learning that profoundly impacted my sense of programming aesthetics and quality. Thank you.
One of the interesting things about LISP is that it's actually a pretty easy language to parse, interpret, and compile. This isn't actually an accident as the S-expression syntax I'm sure was initially chosen for it's machine regularity (in those early days of underpowered machines). Newer languages are syntactically much more complicated. Ironically most normal programmers, being human, seem to find the more complicated syntax easier and the "simple" S-expression syntax confusing (being backward much of the time to normal human convention). I always found it unambiguous, but go figure. It's also precisely this regularity that makes the awesome macrology of LISP possible. In Ruby you can manually build up strings and feed them into the interpreter, which is equivalent to simple backquote. But you can't do the kind of cool nested constructions that are trivial in LISP.
I still don't know How to start learning lisp as a beginner and use it for my day to day needs?
I don't think anybody today has the time to study the science behind lisp and then see where its useful to them.
We want some thing that we can browse through and straight away go and use now!
Is there a recipe book?
If you then decide you want to learn Lisp more deeply:
How to Design Programs is a book that teaches basic Scheme programming. It is oriented towards beginners, so if you want to understand recursion, higher order functions and data structures this book is for you. Conversely, if you already understand those things, this book is not for you. http://www.htdp.org/2003-09-26/Book/curriculum.html
Structure and Interpretation of Computer Programming is a more advanced and probably challenging book that goes through all aspects of recursion, data structures, symbolic mathematics, generic operations & implementing an object system in Scheme, continuations, writing a Scheme interpreter, writing a Prolog interpreter, and writing a hardware simulator and a compiler that compiles Scheme to that hardware's assembly language. http://mitpress.mit.edu/sicp/full-text/book/book.html
While Structure and Interpretation of Computer Programming all about code=data, it doesn't actually teach you about macros. For that you could read Paul Graham's On Lisp, which is essentially a whole book on macros. It is a good book to learn about macros which are useful in any Lisp but it uses Common Lisp which I'd not advice using.
In ruby you can[1] do this, and in python more natively[2]. It is not pretty though.
I couldn't disagree with this more. I don't see what is so different about their type system but SBCL is doing more and more type inference for you.
As far as object model, generic functions are a superset of message passive. One good way to gauge the power of different languages is to look at the kinds of language-deficiency patterns you have to use. What drew me to Smalltalk was that it needed so few compared to, e.g. Java. What made me leave Smalltalk for Lisp was double-dispatch patterns. Double-dispatch patterns (e.g. Visitor) simply aren't needed in a language with generic functions.
>And 30 years later, listeners still rule!
With this, do you mean the REPL or something else?
Not that I think that is a good trade-off vs all the advantages of generic functions. Besides, the things people accomplish with doesNotUnderstand are much better accomplished with macros anyway.
I would say they are. Generic functions can dispatch on a single object if they want to.
As far as doesNotUnderstand, most OO languages don't support it anyway. Further, while I can't find it just now, I seem to recall MOP or CLOS itself providing doesNotUnderstand functionality. You could also either provide a doesNotUnderstand specialization on T, or set up a single handler for it.
If you insist on similar semantics to Smalltalk/Ruby/JS(?) then it wouldn't be hard to use MOP to create a new kind of method dispatch that simply turned the call for a failed specialization lookup into a does-not-understand call as a last step instead of signaling error.
class Foo
def method_missing(meth, *args)
puts "#{meth}(#{args.join(',')})"
end
end
f = Foo.new
f.foo() # prints foo()
f.bar(1,2) # prints bar(1,2)
f[2] = "hello" # prints []=("hello")
Why is this interesting? For example because with this you can implement transparent remote objects. When you make a call on the object, it makes a network request, on the other computer the call is made and the result is sent back over the network, and finally the original method call returns. So the code would end up looking something like this:
# server on ip 1.2.3.4
shared_object = Array.new
shared_object[3] = "good morning"
serve_object("foo", shared_object)
# client
remote_object = RemoteObject.new("1.2.3.4", "foo")
remote_object.length # makes a network call to 1.2.3.4 and computes the length
remote_object[3] # returns "good morning"
remote_object[3] = "hello" # sets the index 3 to the string "hello"
# code in the server can now access shared_object[3] and it will get "hello"
All in all, I think that generic functions are better than message passing, but generic functions are definitely not strictly more powerful.
Smalltalk, more than Lisp or Java, is just not suited to little programs that get the job done. It is really great for rapid development of things that live in the Smalltalk image and play with other Smalltalk objects... but stepping outside of those boundaries is often painful and frustrating. Squeak, for example, is plagued by arcane and undocumented classes for socket I/O or HTTP.
It just feels like its own isolated world compared to a simple Ruby hashbang script that reads from stdin and writes to stdout.
Are you using Ruby in game runtimes, or just tools? How do you feel the use of Racket worked out in the Uncharted games? It seems like an embeddable Lisp (like Racket) might just hit the sweet spot for enabling DSLs and dynamism without bogging you down in an outdated platform like CL.
(P.S. big Naughty Dog fan here... I've always wondered about these sorts of details. I think a lot of programmers are very curious about your war stories.)
http://all-things-andy-gavin.com/2011/10/25/lispings-ala-joh...
We lost founders of both in the last couple weeks. Ritchie for C, McCarthy for Lisp.
What's cool about the paper Paul is talking about here: if you start with car, cdr, cons, quote, cond, atom, eq, and a notation for functions expressed as lists, you can write an "eval" function reimplementing the language. The rest can be built on top of it.
Graham calls this an "axiomatization of computation". The notion of a Turing machine was already well known before McCarthy's paper, and is its own fundamental description of computation. Then came this high-level language which constitues a new one. It isn't "THE axiomatization of computation", just "AN axiomatization of computation".
PG continues the story in a later essay, "Revenge of the Nerds":
"What happened next was that, some time in late 1958, Steve Russell, one of McCarthy's grad students, looked at this definition of eval and realized that if he translated it into machine language, the result would be a Lisp interpreter."
"This was a big surprise at the time. Here is what McCarthy said about it later in an interview:"
"'Steve Russell said, look, why don't I program this eval..., and I said to him, ho, ho, you're confusing theory with practice, this eval is intended for reading, not for computing. But he went ahead and did it. That is, he compiled the eval in my paper into [IBM] 704 machine code, fixing bugs, and then advertised this as a Lisp interpreter, which it certainly was. So at that point Lisp had essentially the form that it has today....'"
"Suddenly, in a matter of weeks I think, McCarthy found his theoretical exercise transformed into an actual programming language-- and a more powerful one than he had intended."
http://www.paulgraham.com/icad.html
Pretty cool story :)
The Ml/Haskell family of languages. Logic languages (though these are somewhat subsumed by the former). Dependent-type languages.
Smalltalk.
What family does APL belong to?
Lisp thus does not really subsume these languages.
I take it you're not familiar with all the evidence that has Racket against that statement.
In anycase, that's not my real point. Lisp has a simple yet powerful meta system. ML/Haskell do not. But their models weren't designed to provide that kind of simple consistent power.
You can not just macro your way in a (conventional) Lisp over to Haskell, because Haskell is fundamentally built on limitations being not merely suggestions, but things you can then further build on. If you do, with something like Clojure and its data model, you've got something that isn't the same language any more, and you need all-new libraries to make it work.
Haskell may be one of the rare exceptions. Haskell's STM was not implemented in Haskell, and AFAIK cannot be implemented in type safe Haskell due to limitations of its type system unless you add specific extensions required for things like STM.
So to say that STM is enabled by the limitations in Haskell is exactly backwards.
Sure, but they don't work. STMs don't work because whenever a transaction is retried, anything that operated on "real state" gets redone, and attempts to deal with that with unrestricted side effects are generally agreed to have been a failure.
(Except Clojure, which built it in either from day 1 or at least very early, and in fact does manage effects.)
"Haskell's STM was not implemented in Haskell, and AFAIK cannot be implemented in type safe Haskell"
I just skimmed the entire STM library in Haskell and have no idea what you are talking about. I don't see anything terribly exotic in the LANGUAGE declarations: CPP, DeriveDataTypeable, FlexibleInstances, MultiParamTypeClasses, MagicHash. That may not be Haskell 98 but nobody cares, those are all either very standard at this point or completely boring (CPP ("use the C preprocessor"), MagicHash ("let me end variables with #")). unsafePerformIO doesn't even show up.
By the way, "skimming the entire library" is about a minute of your time. The whole thing's just shy of 16KB of source.
As far as I know you cannot implement typed variables (monadic, of course) in Haskell in a type safe way. Note that I'm not even talking about efficient references, but any implementation of references. I could be wrong though.
A natural way would be to start with the State monad and make a State of Heap, where Heap is a data type that will hold all the variables and passing around this Heap will be hidden by the State monad. Unfortunately you're now stuck when trying to implement operations for allocating a new variable and for setting/getting the value of a variable. If Haskell were dynamically typed this would be easy: just make Heap an array or list.
I'd disagree with you that those STMs are broken. Yeah, you have to do all your state in transactional variables, but then the same is true for Haskell. True, Haskell enforces this in its type system, but that's hardly a requirement for a library. By the same logic Clojure's string library is broken, because it does not statically enforce that you actually pass strings to the library. Neither do all Haskell libraries enforce all their preconditions/invariants statically, or at all. And actually Haskell doesn't really enforce that you don't use external effects in STM, since you can always do unsafePerformIO. When working with other languages you should regard external effects as you would regard unsafePerformIO in Haskell.
See the other languages section.
The point I wanted to make was, if you are willing to give some benefit of the doubt to Paul Graham's statement in the article (which I quoted) singling out C and Lisp, then the last couple weeks are very significant indeed in terms of the loss to the field of computing.
On the other hand, I suspect an abstract machine for executing Lisp—one that accounted for reader macros and the like—would be of roughly the same complexity as the STG machine.
The simple description of lazy evaluation is graph reduction. ML doesn't even use lazy evalution.
(Forth is usually the first HLL to get working on a new chip due to its simplicity.)
If you're looking for a modern stack-language implementation, give Factor a try: http://factorcode.org/
Forth has what might be described as an "interactive compiler" which can be easily extended during the compilation process. Since an immediate word can hijack the parser, you could theoretically build Forth out into a reasonable facsimilie of any other language if you so desired. These capabilities are already used in most Forth distributions to provide things like flow control, comments and string literals.
Here is the point in the story where we need Norvig's annotation from PAIP (p. 777):
"So the first Lisp interpreter was the result of a programmer ignoring his boss's advice."
I like to think that the "ho, ho" in the original quote means that McCarthy appreciated this.
Hey! That's what I think, too!
Around 2007 when I'd had quite a bit of exposure to both Python and then Ruby I'd started to think the same thing. Although I didn't have the foresight to say it in a public essay I would tell my friends "In five years Javascript will start to become a popular general (i.e. non-web only) programming language and Lisp in 20."
I now think think the big Lisp (or Scheme) event will happen even sooner--say in 5 to 7 years. (Meaning you will see the kinds of articles you see around Node today on HN about Lisp.)