Lisp in Lisp


; The Lisp defined in McCarthy's 1960 paper, translated into CL.
; Assumes only quote, atom, eq, cons, car, cdr, cond.
; Bug reports to lispcode@paulgraham.com.

(defun null. (x)
  (eq x '()))

(defun and. (x y)
  (cond (x (cond (y 't) ('t '())))
        ('t '())))

(defun not. (x)
  (cond (x '())
        ('t 't)))

(defun append. (x y)
  (cond ((null. x) y)
        ('t (cons (car x) (append. (cdr x) y)))))

(defun list. (x y)
  (cons x (cons y '())))

(defun pair. (x y)
  (cond ((and. (null. x) (null. y)) '())
        ((and. (not. (atom x)) (not. (atom y)))
         (cons (list. (car x) (car y))
               (pair. (cdr x) (cdr y))))))

(defun assoc. (x y)
  (cond ((eq (caar y) x) (cadar y))
        ('t (assoc. x (cdr y)))))

(defun eval. (e a)
  (cond
    ((atom e) (assoc. e a))
    ((atom (car e))
     (cond
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
       ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
       ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
       ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'cond)  (evcon. (cdr e) a))
       ('t (eval. (cons (assoc. (car e) a)
                        (cdr e))
                  a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
            (cons (list. (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr e) a))
                     a)))))

(defun evcon. (c a)
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        ('t (evcon. (cdr c) a))))

(defun evlis. (m a)
  (cond ((null. m) '())
        ('t (cons (eval.  (car m) a)
                  (evlis. (cdr m) a)))))

— Paul Graham

.

.

2018.03.15 Thursday ACHK

Shape of a program

(defun bad-reverse (lst)
  (let* ((len (length lst))
	 (ilimit (truncate (/ len 2))))
    (do ((i 0 (1+ i))
	 (j (1- len) (1- j)))
	((>= i ilimit))
      (rotatef (nth i lst) (nth j lst)))))

It used to be thought that you could judge someone’s character by looking at the shape of his head. Whether or not this is true of people, it is generally true of Lisp programs. Functional programs have a different shape from imperative ones. The structure in a functional program comes entirely from the composition of arguments within expressions, and since arguments are indented, functional code will show more variation in indentation. Functional code looks fluid on the page; imperative code looks solid and blockish, like Basic.

Even from a distance, the shapes of bad- and good-reverse suggest which is the better program. And despite being shorter, good-reverse is also more efficient: O(n) instead of O(n^2).

(defun good-reverse (lst)
  (labels ((rev (lst acc)
		(if (null lst)
		    acc
		  (rev (cdr lst) (cons (car lst) acc)))))
    (rev lst nil)))

— p.30

— On Lisp

— Paul Graham

.

.

2018.03.02 Friday ACHK

On Lisp

paulgraham_2202_3475946

Lisp is an especially good language for writing extensible programs because it is itself an extensible program.

Because Lisp gives you the freedom to define your own operators, you can mold it into just the language you need. If you’re writing a text-editor, you can turn Lisp into a language for writing text-editors. If you’re writing a CAD program, you can turn Lisp into a language for writing CAD programs. And if you’re not sure yet what kind of program you’re writing, it’s a safe bet to write it in Lisp. Whatever kind of program yours turns out to be, Lisp will, during the writing of it, have evolved into a language for writing that kind of program.

— On Lisp: Advanced Techniques for Common Lisp

— Paul Graham

.

.

2018.02.21 Wednesday ACHK

SICP, 3

Just as every day thoughts are expressed in natural language, and formal deductions are expressed in mathematical language, methodological thoughts are expressed in programming languages. A programming language is a method for communicating methods, not just a means for getting a computer to perform operations – programs are written for people to read as much as they are written for machines to execute.

— Lisp: A language for stratified design

— Harold Abelson, Gerald Jay Sussman

— SICP distilled

— jao 

2013.05.31 Friday ACHK

Professor 2

lisper 4 days ago | link

I was never in academia, but I was a researcher (at NASA) so I played the publishing game. And if you look at my record, I was relatively good at it. Not only was my publications list fairly long, but my work was also pretty widely referenced. But since my career no longer depends on it, I am now free to say that I credit my success almost entirely to gaming the system. This is not to say that I didn’t do good work (I think I did), but there was virtually no correlation between what I thought was quality work and what I actually got rewarded for. The vast majority of my publications were minor tweaks on previous work that were specifically engineered to get past the program committees of key conferences. My best work (by my own quality metric) either went unnoticed, or could not get accepted for publication at all. When it got to the point where I was faced with a very stark choice between continuing to produce bullshit and get rewarded for it, or to do what I thought was good work and eventually get fired, I quit.

   
Evbn 4 days ago | link

Industry isn’t so different. My salary is determined by 2 days of interviews and negotiations, and only slightly perturbed by my performance over the next several years.

— Hacker News

2013.01.11 Friday ACHK

Paul Graham

zatara 59 days ago | link

I am almost afraid to ask you this, but here it goes.

On the last few weeks/months before starting Viaweb, did you consider yourself a failure for being almost 30, well-educated but out of the formal career track, “poor” and unmarried? If so, was that the fuel behind your many amazing achievements later on?

—–
   
   
pg 59 days ago | link

No, not really. I’d written the two Lisp books, and people liked those. Not a lot of people, but they were people whose opinions I cared about. Actually Viaweb felt like more of a compromise than the way I’d been living before, because it was something I was doing mostly for money.

—–
   
   
sayemm 58 days ago | link

So, you finally had your first taste of startup success at age 34. And you started Y Combinator at 41.

Think your story, along with many others in the Valley (e.g. Jim Clark), goes to show that this is a long-term game, and it only gets better with age and experience.

— Hacker News

2013.01.11 Friday ACHK

Functional programming 6

A central concept in functional languages is that the result of a function is determined by its input, and only by its input. There are no side-effects! 

— Why Haskell matters

My question is, if a function makes changes only within its local environment, and returns the result, how can it interact with a database or a file system? By definition, wouldn’t that be accessing what is in effect a global variable or global state?

What is the most common pattern used to get around or address this?
   
— edited Dec 7 ’11 at 2:10, Matt Fenwick
   
— asked Dec 6 ’11 at 20:18, juwiley

The most common pattern for dealing with side-effects and impurity in functional languages is:

  •     be pragmatic, not a purist
  •     provide built-ins that allow impure code and side-effects
  •     use them as little as possible!

Examples:

  •     Lisp/Scheme: set!
  •     Clojure: refs, and using mutating methods on java objects
  •     Scala: creating variables with var
  •     ML: not sure of specifics, but Wikipedia says it allows some impurity

Haskell cheats a little bit — its solution is that for functions that access the file system, or the database, the state of the entire universe at that instant, including the state of the filesystem/db, will be passed in to the function.(1) Thus, if you can replicate the state of the entire universe at that instant, then you can get the same results twice from such a function. Of course, you can’t replicate the state of the entire universe at that instant, and so the functions return different values …

But Haskell’s solution, IMHO, is not the most common.

(1) Not sure of the specifics here. Thanks to CAMcCann for pointing out that this metaphor is overused and maybe not all that accurate.   

— edited Dec 7 ’11 at 2:11

— answered Dec 6 ’11 at 22:00, Matt Fenwick

— Stack Overflow

2012.08.12 Sunday ACHK

Meaningful 7

upgrade path

有出路

— Me@2012-08-06 8:28:47 AM

Somewhere in the course of doing Viaweb, someone gave me a very useful piece of advice: users always want an upgrade path, even though as a rule they’ll never take it. Rtml was our upgrade path. If you wanted to, you could get absolute control over everything on your pages.

— Lisp in Web-Based Applications

— Paul Graham

2012.08.11 Saturday (c) All rights reserved by ACHK

The Dragon Book, 2

Most people don’t realize that writing a compiler like this is only about 2 months work for one talented person who read the Dragon book. Since the compiler only has one body of code to compile, it is much easier to write. It doesn’t have to be a general-purpose compiler. It doesn’t have a math library, for example.

And we have the ability to add any feature to the language that we want easily… this is the same power Paul Graham talks about in On Lisp, the power to invent new language features that suit your exact application domain. Lisp does this through a mechanism called macros.

— Wasabi

— Joel on Software

— Joel Spolsky

2012.06.20 Wednesday ACHK

Python

Basically, Python can be seen as a dialect of Lisp with “traditional” syntax (what Lisp people call “infix” or “m-lisp” syntax).

Python can be seen as either a practical (better libraries) version of Scheme, or as a cleaned-up (no $@&% characters) version of Perl.

One of Python’s controversial features, using indentation level rather than begin/end or braces, was driven by this philosophy: since there are no braces, there are no style wars over where to put the braces. Interestingly, Lisp has exactly the same philosphy on this point: everyone uses emacs to indent their code, so they don’t argue over the indentation.

Take a Lisp program, indent it properly, and delete the opening parens at the start of lines and their matching close parens, and you end up with something that looks rather like a Python program.

— Python for Lisp Programmers

— Peter Norvig

2012.05.22 Tuesday ACHK

Lisp macros 2.2

I think one of the problems with Lisp is that it is too powerful. It has so much meta ability that it allows people to invent their own little worlds, and it takes a while to figure out each person’s little world (SoftwareGivesUsGodLikePowers).

— Lisp is Too Powerful

2012.02.19 Sunday ACHK

Lisp macros 2

People complain macros are difficult to understand. Macros are easy. If you can understand a program that concatenates lists to make a new list, you can understand a macro. Macros are quite literally ‘just lisp code’.

— ohyes 2 weeks ago

— Lisp is Too Powerful

— Hacker News

2012.01.07 Saturday ACHK

Computer

Steven Paul “Steve” Jobs (February 24, 1955 – October 5, 2011)

= Apple Inc. + Pixar Animation Studios

Dennis MacAlistair Ritchie (b. September 9, 1941; found dead October 12, 2011)

= the C programming language + the UNIX operating system

John McCarthy (September 4, 1927 – October 24, 2011)

= Artificial Intelligence (AI) + the LISP programming language

— Me@2011.10.27

2011.10.27 Thursday (c) All rights reserved by ACHK

Category Theory | Lisp, 4

這段改編自 2010 年 3 月 6 日的對話。

我在前晚發現,我一直在研究的兩個課題,原來在某個角度之下,是同一樣東西。

(安:哪兩樣東西呢?)

一個就是 Paul Graham 強烈推介的 Lisp programming language(Lisp 編程語言)。另一個就是 John Baez 強烈推介的 Category Theory(範疇論)。

利用「範疇論」,我們可以將「相對論」的數學語言和「量子力學」的數學語言,統一成一套數學語言。留意,我不是指統一「相對論」和「量子力學」本身,而是指統一它們的數學語言。「相對論」所用的數學語言是 differential geometry(微分幾何)。「量子力學」所用的數學語言是 representation theory(表示論)。

Lisp 和「範疇論」都是我幾年前就開始關心的課題。最近才發現,它們竟然是「同一樣」東西,令我十分驚奇。幾天前,我還正正考慮著,好不好暫時放棄其中一門,因為我沒有時間同時深入研究 Lisp 和「範疇論」。現在,問題突然消失。

彷彿是同時愛上了兩位女仕,最終要二擇其一。正當面臨痛苦決擇之際,發現她們,竟然是同一個人。

— Me@2011.08.03

2011.08.03 Thursday (c) All rights reserved by ACHK

Clojure

Rich Hickey developed Clojure because he wanted a modern Lisp for functional programming, symbiotic with the established Java platform, and designed for concurrency.

Clojure’s approach to concurrency is characterized by the concept of identities, which represent a series of immutable states over time. Since states are immutable values, any number of workers can operate on them in parallel, and concurrency becomes a question of managing changes from one state to another. For this purpose, Clojure provides several mutable reference types, each having well-defined semantics for the transition between states.

— Wikipedia on Clojure

2011.08.03 Wednesday ACHK

On Lisp

I hope reading this book will be fun. Of all the languages I know, I like Lisp the best, simply because it’s the most beautiful. This book is about Lisp at its lispiest. I had fun writing it, and I hope that comes through in the text.

— Paul Graham

2011.07.01 Friday ACHK

MapReduce

By abstracting away the very concept of looping, you can implement looping any way you want, including implementing it in a way that scales nicely with extra hardware.

Without understanding functional programming, you can’t invent MapReduce, the algorithm that makes Google so massively scalable. The terms Map and Reduce come from Lisp and functional programming. MapReduce is, in retrospect, obvious to anyone who remembers from their 6.001-equivalent programming class that purely functional programs have no side effects and are thus trivially parallelizable.

The very fact that Google invented MapReduce, and Microsoft didn’t, says something about why Microsoft is still playing catch up trying to get basic search features to work, while Google has moved on to the next problem: building Skynet^H^H^H^H^H^H the world’s largest massively parallel supercomputer. I don’t think Microsoft completely understands just how far behind they are on that wave.

— Can Your Programming Language Do This?

— Joel Spolsky

2011.04.22 Friday ACHK

ANSI Common LISP

.

ANSI Common LISP (by Paul Graham) was the book I borrowed for a Machine Intelligence course project in 2000. My memory was that the author was called “Paul something”. I thought that Paul was the one who had invented LISP.

No. It should be John McCarthy.

Later on, during my teaching-in-high-school period, by a Wikipedia biography, I realized that that Paul was not as great as I thought, because he was not the one who had invented LISP.

However, now, I regard him as one of my five most important teachers.

— Me@2010.03.08

— Me@2011.03.14

.

.

.

2011.03.14 Monday (c) All rights reserved by ACHK

Blub programmer

大世界 3.2

    Our hypothetical Blub programmer wouldn’t use either [Cobol or assembly]. Of course he wouldn’t program in machine language. That’s what compilers are for. And as for Cobol, he doesn’t know how anyone can get anything done with it. It doesn’t even have x (Blub feature of your choice).

    As long as our hypothetical Blub programmer is looking down the power continuum, he knows he’s looking down. Languages less powerful than Blub are obviously less powerful, because they’re missing some feature he’s used to. But when our hypothetical Blub programmer looks in the other direction, up the power continuum, he doesn’t realize he’s looking up. What he sees are merely weird languages. He probably considers them about equivalent in power to Blub, but with all this other hairy stuff thrown in as well. Blub is good enough for him, because he thinks in Blub.

    When we switch to the point of view of a programmer using any of the languages higher up the power continuum, however, we find that he in turn looks down upon Blub. How can you get anything done in Blub? It doesn’t even have y.

    By induction, the only programmers in a position to see all the differences in power between the various languages are those who understand the most powerful one. (This is probably what Eric Raymond meant about Lisp making you a better programmer.) You can’t trust the opinions of the others, because of the Blub paradox: they’re satisfied with whatever language they happen to use, because it dictates the way they think about programs.
   
— Paul Graham

2011.03.02 Wednesday ACHK

Metamagical Themas

There are three articles centered on the Lisp programming language, where Hofstadter first details the language itself, and then shows how it relates to Godel’s incompleteness theorem.

The title is an example of wordplay: it is an anagram of Mathematical Games, the title of Martin Gardner’s column that Hofstadter’s column succeeded in Scientific American.

— Wikipedia on Metamagical Themas

2011.02.23 Wednesday ACHK