News for hackers. Stuff that matters.
Re:The Roots of Lisp by charlieok on Monday October 24, 2011 @06:19PM (#3151895)
PG: "It seems to me that there have been two really clean, consistent models of programming so far: the C model and the Lisp model. These two seem points of high ground, with swampy lowlands between them."

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 :)

Re:The Roots of Lisp by gruseom on Monday October 24, 2011 @08:11PM (#3152184)
"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."

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.

Re:The Roots of Lisp by erichocean on Monday October 24, 2011 @07:51PM (#3152133)
Forth is the third model -- very clean and consistent, and still widely used.

(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/

Re:The Roots of Lisp by RodgerTheGreat on Monday October 24, 2011 @09:09PM (#3152330)
I think Forth is particularly notable for providing metaprogramming facilities which are arguably on par with Lisp while taking a completely different approach. Lisp represents code and data the same way and can manipulate both with ease.

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.

Re:The Roots of Lisp by Peaker on Monday October 24, 2011 @07:23PM (#3152060)
There are more clean, consistent and interesting models of programming besides the C and Lisp models.

The Ml/Haskell family of languages. Logic languages (though these are somewhat subsumed by the former). Dependent-type languages.

Re:The Roots of Lisp by charlieok on Monday October 24, 2011 @08:33PM (#3152226)
Here on hacker news, we can (and do) argue all day about how to categorize and rank programming languages. I'll readily confess that I do not have enough depth or breadth in the field to be any kind of authority when it comes to that.

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.

Re:The Roots of Lisp by swannodette on Monday October 24, 2011 @07:47PM (#3152123)
The Lisp system is a meta model. Thus you can implement a Lisp that works like ML/Haskell/Prolog if you like. ML/Haskell don't seem to provide that kind of meta power as cleanly or consistently IME. Prolog has a good meta model, but it doesn't seem to subsume other models as cleanly, consistently, or efficiently as Lisp.
Re:The Roots of Lisp by Peaker on Monday October 24, 2011 @08:05PM (#3152168)
Implementing a Lisp that works like ML/Haskell will be as much work as implementing a compiler/interpreter of these languages outside of Lisp. The macro system is not a great compiler toolkit for languages with semantics radically different from Lisp.

Lisp thus does not really subsume these languages.

Re:The Roots of Lisp by swannodette on Monday October 24, 2011 @08:25PM (#3152213)
> The macro system is not a great compiler toolkit for languages with semantics radically different from Lisp.

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.

Re:The Roots of Lisp by jerf on Monday October 24, 2011 @09:11PM (#3152339)
Lisp and Haskell to my mind form the two leading languages of two fundamentally contradictory families. Lisp works by empowering programmers and building on that power, and Haskell works by limiting the programmer and building on those limitations. Despite what the leading word "limitation" may lead you to believe, both philosophies can lead to great results. For example, for the same basic reasons you can't even build an STM in C#, it's probably even more impossible to build an STM in Lisp, whereas in Haskell it's pretty easy, because of the limitations.

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.

Re:The Roots of Lisp by jules on Tuesday October 25, 2011 @09:36AM (#3153989)
You can build an STM in pretty much any language. There have been STMs in at least C++, Java, C#, Common Lisp, Clojure and OCaml.

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.

Re:The Roots of Lisp by jerf on Tuesday October 25, 2011 @11:56AM (#3154494)
"You can build an STM in pretty much any language."

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.

Re:The Roots of Lisp by jules on Tuesday October 25, 2011 @02:57PM (#3155360)
Where do I find this library? The only thing I've been able to find is a bunch of files doing no real stuff except building a nicer interface on top of more primitive STM operations.

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.

Re:The Roots of Lisp by Peaker on Monday October 24, 2011 @09:18PM (#3152358)
Can you elaborate how Racket is evidence against that statement?
Re:The Roots of Lisp by irahul on Tuesday October 25, 2011 @04:42AM (#3153327)
PLT Racket has implemented languages with different semantics within Racket - http://docs.racket-lang.org/

See the other languages section.

Re:The Roots of Lisp by 0x12 on Monday October 24, 2011 @07:34PM (#3152097)
TILs such as forth.

Smalltalk.

What family does APL belong to?

Re:The Roots of Lisp by gruseom on Monday October 24, 2011 @08:09PM (#3152178)
Certainly its own family, along with its successors J and K.
Re:The Roots of Lisp by Peaker on Tuesday October 25, 2011 @06:18AM (#3153526)
You could argue those languages are not very clean, at least syntactic-wise.
Re:The Roots of Lisp by silentbicycle on Tuesday October 25, 2011 @10:13AM (#3154100)
Don't confuse having lots of operators with being unclean. They're syntactically more internally consistent than Common Lisp, for example.
Re:The Roots of Lisp by rayiner on Tuesday October 25, 2011 @12:35AM (#3152826)
You can describe the execution semantics of a "C" machine or a "Lisp" machine in a paragraph. Can't really do the same for a Spineless Tagless G-Machine...
Re:The Roots of Lisp by andolanra on Tuesday October 25, 2011 @03:45AM (#3153229)
The semantics for System F could be explained in roughly a paragraph. Lisp is, more or less, simply typed lambda calculus + code-as-nested-lists + compile-time computation mechanisms; Haskell and ML are System F + various type mechanisms (e.g. typeclasses or modules.)

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.

Re:The Roots of Lisp by skew on Tuesday October 25, 2011 @03:51AM (#3153239)
Apples and oranges. Can you explain implicit continuation representation in a paragraph?

The simple description of lazy evaluation is graph reduction. ML doesn't even use lazy evalution.

Re:The Roots of Lisp by jhuni on Monday October 24, 2011 @11:00PM (#3152642)
Everyone using functional languages (ML/Haskell) or logic languages (Prolog) should respect the considerable contributions McCarthy made to these areas throughout his entire life.
Re:The Roots of Lisp by vorg on Wednesday October 26, 2011 @07:09AM (#3158049)
In a meeting, the person who suggests a good idea and the person who recognizes a good idea are usually two different people.