Lisp, univers persistant, et le reste
// mars 14th, 2008 // Pas de Commentaires » // Cogni
C’était le 28 février dernier. J’avais attendu pendant quelques temps des étudiants à qui je devais parler d’IA dans Second Life, et les seules personnes que j’ai vues ont été des étudiants (et leurs profs) d’une autre école, venus découvrir le campus qui me sert de home page sur SL. Je servais donc de guide depuis une heure, quand une IM sur le groupe Artficial Intelligence est tombée, nous invitant à un exposé sur Lisp dans Second Life.
Et j’ai pu assister à une conférence volante non identifiée. Jugez plutôt. Galileo Broome: Hello all. Perhaps I will begin. Thank you for coming. Lisp is a language developed about 1960 for AI research, it is the second oldest…after fortran it remains one of the most important languages in computer science many features of lisp slowly find their way into more mainstream languages, e.g., garbage collection in java originated with lisp in 1960 I would like to show you a series of implementations for Scheme which i have constructed here in sl. One of my interests is distributed computing. This is breaking up a problem and solving it collectively on 100’s or thousands of separate processors. SL is *ideal* for research in dist. computing because building scripted objects here in sl requires making many small scripts which communicate via message passing. This is a basic component of distributed computing. The implementations i will show…esp. the last one, are rather pretty. I would be lying if i told you that my motivations weren’t partly aesthetic… also…i am a computer science educator i think that SL has great potential for teaching *serious* computer science including artificial intelligence this is because (unlike other mmog’s) computer programming itself is a major component of gameplay in sl we build things and script them and sell them to each other in some sense…sl is a game *about* programming Aymeric Yalin: (never thought of doing it in open sims ?) On open sims you could have open source access
Galileo Broome: my plan is to release everything i do here as opensource InterfaceD Dreamscape: bless you
Galileo Broome: I have sat across the table at a sushi restaurant from Richard STallman….the GNU founder Galileo Broome: i think i said some of this Sl is interesting because things whichh would normally be purely abstract become physical in a very compelling way here inside the virtual world. What is normally considered to be a flaw in reasoning (regarding the abstract as physical) instead becomes an actual possibility
Galileo Broome: I have taught Scheme to undergrads at the Univ. of New Mexico since 1999. I think it is a very beautiful and powerful language. i will show you an example… Scheme has no iteration… everything is done via recursion. it has *first class* functions, which means that functions are a type of data like any other…eg. like numbers or strings. here we see a simple scheme program for computing fibonacci numbers which says that the nth fib number is 0 or 1 if n < 1 and the sum of the n-1 and n-2 fib numbers otherwise scheme uses a funny prefix based syntax like lisp so that we write (+ 1 1) instead of 1+1. you are all familiar with scripting in lsl...so i wont dwell on it. here are some points worth making though. lsl is kind of a broken language : it has no pointers, no arrays, no structs, it has lists...but...lists cant contain lists :). the most serious limitation is that scripts are limited to 16K, that is 16K total...for code...stack...and heap, very little room to work. this forces programmers to be creative. it forces them todistribute complex problems among many simple pieces which communicate. which is the basic model of dist. computing.
this is what needs to be done to write an interpreter. a parser takes program text and converts it into a more useful data structure… a list in the case of scheme. the evaluator simulates the program…evaluates it… and the printer prints the answer. each of these is a moderately complex program, which must access the heap in dozens of places, a heap that wont fit in 16K. the problem is that if we try to distribute the heap among objects in the world, and we are forced to communicate with those objects via event handlers which do not preserve state information…. there is no way we can access a dist. heap and return to any one of 20 places in a complex recursive code. this seems to be a deal killer. ok. here is a soln. i devised. Galileo Broome: can everyone see the cube above me? it consists of 243 prims actually 244 prims 243 of those funtion as memory for a distributed heap the last holds the scripts for the parser and evaluator Galileo Broome: when a memory element is activated…it briefly glows the memory consists of three banks of 9 x 9 for 243 pieces it has a full 16K address space so it can perform computations which involve up to 16K objects Galileo Broome: i have just told it the defn. of factorial Galileo Broome: you may recall that n!= 1* 2*3* … * n so that 6! = 1 * 2 * 3 * 4* 5* 6. lets watch it compute 10! Galileo Broome: 10! = 3628800. in this computer the « heap » has been distributed. however…the « stack » has not been. it still grows. this limits the size of the computation. if we move from an interpreter to a compiler…then we can distribute the stack as well. this is what a compiler looks like it translates one language into a simpler langauge which can be executed on a virtual machine. scheme into a special bytecode in this case. lsl works like this too. this shows how Scheme can be translate into bytecode. each bytecode performs a simple transformation of the state of a virtual machine. Scheme Sphere 16K (compiler): Beginning memory board reset… Galileo Broome: here is a second computer Galileo Broome: i just told it the defn. of fact Galileo Broome: it has compiled it now we can use it to compute fact just like before Galileo Broome: this computer is a compiler with a distributed virtual machine Galileo Broome: the blue fish represent something called a « symbol ». symbols function as names for things. the brown fish are primitive functions. like + – * / and cons car cdr. cons car and cdr are functions for building and referencing lists. Galileo Broome: i have just told it the defn. of factorial Galileo Broome: you can see the bytecodes which the scheme source code has been compiled into. they are the fish with the turquoise labels. the jellyfish are pairs. they are used to build linklists. can anyone see the clownfish? up near the top? the clownfish? he is the lexical closure which blotto asked about Galileo Broome: you will see numbers representing intermediate quantities come into existence they are the black and white angel fish also…lots of jellyfish (pairs) will be created they are used to form the data structures of the virtual machine…i.e. its stack if you turn your sun to midnight…you can watch the fish blink when you see a turquoise fish blink it means a continuation has been sent to it Galileo Broome: www.cs.unm.edu/~williams however, there will be nothing about this on it yet this is a work in progress…you are seeing it first or very nearly
L’intervenant est Galileo Broome, et il nous parle certes de Lisp, mais surtout de son implémentation distribuée dans Second Life.
Distribué dans des centaines de prims, qui forment un cube, une sphère ou une bande de joyeux poissons. Et chaque prim change de couleur quand un message passe à travers elle.
En mode nuit on voit un peu mieux (et encore mieux tout à l’heure avec la sphère). Lisp est implémentée sous forme d’objets distribués, qui s’échangent des messages.
Laissons la parole à Galileo (extraits du chat transcript).
« Scheme » is a small elegant dialect of lisp.
an idea which is important to me is « reification »
I am not selling my computers
i am very pro opensource
Scheme Cube 16K (interpreter): Beginning memory board reset…
Scheme Cube 16K (interpreter): Broome Cybernetics Scheme 1.0
Scheme Cube 16K (interpreter): Starting parse of sentence: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Cube 16K (interpreter): parsing time: 3.338919s
Scheme Cube 16K (interpreter): parsed: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Cube 16K (interpreter): evaluation time: 0.244490s
Scheme Cube 16K (interpreter): evaluated: #
Scheme Cube 16K (interpreter): sexprs: 148
Scheme Cube 16K (interpreter): Starting parse of sentence: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Cube 16K (interpreter): parsing time: 3.259443s
Scheme Cube 16K (interpreter): parsed: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Cube 16K (interpreter): evaluation time: 0.245096s
Scheme Cube 16K (interpreter): evaluated: #
Scheme Cube 16K (interpreter): sexprs: 220
Scheme Cube 16K (interpreter): Starting parse of sentence: (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
Scheme Cube 16K (interpreter): parsing time: 2.761297s
Scheme Cube 16K (interpreter): parsed: (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
Scheme Cube 16K (interpreter): evaluation time: 0.245042s
Scheme Cube 16K (interpreter): evaluated: #
Scheme Cube 16K (interpreter): sexprs: 281
Scheme Cube 16K (interpreter): Starting parse of sentence: (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
Scheme Cube 16K (interpreter): parsing time: 2.715685s
Scheme Cube 16K (interpreter): parsed: (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
Scheme Cube 16K (interpreter): evaluation time: 0.224101s
Scheme Cube 16K (interpreter): evaluated: #
Scheme Cube 16K (interpreter): sexprs: 341
Scheme Cube 16K (interpreter): Starting parse of sentence: (fact 10)
Scheme Cube 16K (interpreter): parsing time: 0.334567s
Scheme Cube 16K (interpreter): parsed: (fact 10)
Scheme Cube 16K (interpreter): evaluation time: 28.774502s
Scheme Cube 16K (interpreter): evaluated: 3628800
Scheme Cube 16K (interpreter): sexprs: 412
Scheme Sphere 16K (compiler): Broome Cybernetics Scheme 1.0
241 prims. the orange panels are used to distribute the heap….the silver sphere holds the parser compiler and virtual machine. the virtual machine’s stack is stored in the distributed heap. this computer can run larger computations for this reason…computatiosnw which would cause a stack heap collision in the cube.
Scheme Cube 16K (interpreter): Starting parse of sentence: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Sphere 16K (compiler): Starting parse of sentence: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Cube 16K (interpreter): parsing time: 3.272770s
Scheme Sphere 16K (compiler): parsing time: 3.316862s
Scheme Cube 16K (interpreter): parsed: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Sphere 16K (compiler): parsed: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Cube 16K (interpreter): evaluation time: 0.245523s
Scheme Cube 16K (interpreter): evaluated: #
Scheme Cube 16K (interpreter): sexprs: 484
Scheme Cube 16K (interpreter): Starting parse of sentence: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Sphere 16K (compiler): compilation time: 2.136429s
Scheme Cube 16K (interpreter): parsing time: 3.428838s
Scheme Sphere 16K (compiler): compiled: {close ((n) . {frame {test {refer n {return}} {frame {argument {frame {argument {refer + {apply}}} {frame {argument {refer fib {apply}}} {constant 1 {argument {refer n {argument {refer – {apply}}}}}}}}} {frame {argument {refer fib {apply}}} {constant 2 {argument {refer n {argument {refer – {apply}}}}}}}}} {constant 2 {argument {refer n {argument {refer < {apply}}}}}}}) {assign fib {halt}}}
Scheme Sphere 16K (compiler): evaluation time: 0.178113s
Scheme Sphere 16K (compiler): evaluated: #
Scheme Sphere 16K (compiler): sexprs: 154
Scheme Cube 16K (interpreter): parsed: (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
Scheme Cube 16K (interpreter): evaluation time: 0.245064s
Scheme Cube 16K (interpreter): evaluated: #
Scheme Cube 16K (interpreter): sexprs: 556
Galileo Broome: let me get rid of the cube lets watch it compiler compile a scheme function into bytecode
Scheme Sphere 16K (compiler): Starting parse of sentence: (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
Scheme Sphere 16K (compiler): parsing time: 2.700174s
Scheme Sphere 16K (compiler): parsed: (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
Scheme Sphere 16K (compiler): compilation time: 1.648215s
Scheme Sphere 16K (compiler): compiled: {close ((n) . {frame {test {constant 1 {return}} {frame {argument {refer n {argument {refer * {apply}}}}} {frame {argument {refer fact {apply}}} {constant 1 {argument {refer n {argument {refer – {apply}}}}}}}}} {constant 0 {argument {refer n {argument {refer = {apply}}}}}}}) {assign fact {halt}}}
Scheme Sphere 16K (compiler): evaluation time: 0.176826s
Scheme Sphere 16K (compiler): evaluated: #
Scheme Sphere 16K (compiler): sexprs: 243
Scheme Sphere 16K (compiler): Starting parse of sentence: (fact 10)
Scheme Sphere 16K (compiler): parsing time: 0.335277s
Scheme Sphere 16K (compiler): parsed: (fact 10)
Scheme Sphere 16K (compiler): compilation time: 0.287530s
Scheme Sphere 16K (compiler): compiled: {frame {halt} {constant 10 {argument {refer fact {apply}}}}}
Scheme Sphere 16K (compiler): evaluation time: 25.509741s
Scheme Sphere 16K (compiler): evaluated: 3628800
Scheme Sphere 16K (compiler): sexprs: 467
Galileo Broome: the next thing i would like to show you is very radical…it is a completely distributed computer… in anycase…speed is not so much the point here…let me show you the last computer which is the most interesting
fishy Scheme 2.4 (distributed vm): Broome Cybernetics Scheme 2.0
the parser compiler and printer are in a ring on my finger. the fish you see swimming around are a distributed heap and virtual machine.
fishy Scheme 2.4 (distributed vm): resetting…
fishy Scheme 2.4 (distributed vm): Broome Cybernetics Scheme 2.0
fishy Scheme 2.4 (distributed vm): Starting parse of sentence: (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
fishy Scheme 2.4 (distributed vm): parsing time: 13.366325s
fishy Scheme 2.4 (distributed vm): parsed: (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
fishy Scheme 2.4 (distributed vm): compilation time: 8.680180s
fishy Scheme 2.4 (distributed vm): compiled: {close ((n) . {frame {test {constant 1 {return}} {frame {argument {refer n {argument {refer * {apply}}}}} {frame {argument {refer fact {apply}}} {constant 1 {argument {refer n {argument {refer – {apply}}}}}}}}} {constant 0 {argument {refer n {argument {refer = {apply}}}}}}}) {assign fact {halt}}}
fishy Scheme 2.4 (distributed vm): 122, 5, 0, 0, 0
fishy Scheme 2.4 (distributed vm): sexprs: 122
fishy Scheme 2.4 (distributed vm): evaluated: #
fishy Scheme 2.4 (distributed vm): Garbage collecting…
fishy Scheme 2.4 (distributed vm): Done garbage collecting.
he is a user defined function. the definition of factorial. the virtual machine is distributed amongst the fish with turquoise labels…the bytecodes. the virtual machine works by means of something called continuation passing. a continuation is like a baton in a relay race and the bytecodes are like runners; the program executes as the baton is passsed from bytecode to bytecode…like relay racers passing a baton. the baton holds the values of the registers of the virtual machine. which each bytecode trasnforms before passsing it on to the next. lets watch it compute 10!
fishy Scheme 2.4 (distributed vm): Starting parse of sentence: (fact 10)
fishy Scheme 2.4 (distributed vm): parsing time: 1.604049s
fishy Scheme 2.4 (distributed vm): parsed: (fact 10)
fishy Scheme 2.4 (distributed vm): compilation time: 1.559564s
fishy Scheme 2.4 (distributed vm): compiled: {frame {halt} {constant 10 {argument {refer fact {apply}}}}}
watch for larger numbers coming into existence near the end
fishy Scheme 2.4 (distributed vm): 346, 345, 0, 0, 0
fishy Scheme 2.4 (distributed vm): sexprs: 346
fishy Scheme 2.4 (distributed vm): evaluated: 3628800
fishy Scheme 2.4 (distributed vm): Garbage collecting…
fishy Scheme 2.4 (distributed vm): Done garbage collecting. 
i am happy to answer any questions any of you may still have if there are no questions then let me thank you very much for attending my impromptu lecture
