Lambda the Ultimate

Dan's presentation is definitely one that I need to catch. Then again, maybe I need to pull my Lego Mindstorm set off the bottom of the heap in the closet.

Anyhow, thanks for filling up my weekend. :-)

[edit: ok, now it's dead again...; back again...(no sound, dammit!); hurray!]

acme - testing for distributed systems.

how do you test a distributed, robust system. that wasn't designed for testing (no logging etc). can we probe it? dont want to affect scalability. overheads illegible on webcast.

static analysis interface - dependencies, histories, etc etc.

execution environment - racks of blade style servers. don't want someone having physical access to configure. now do 100s of tests over the weekend. push button system - polaris. define test use cases, click on a (web?) interface, see what happens.

not much about little languages so far.

ah. created parallel agent system using a ll - ruby (is ruby lightweight?). architecture - botlets, databus, botlet manager. botlets are test agents - not same as the agent system under test. communicate via jabber(?). event driven, xml messaging. xml-rpc to other languages.

irc chat-bot structure. conversational metaphor. peer-to-peer. buzzword buzzword. several backplanes for comms. one for for [broadcast dropped] - probably one for system, one for testing, so that you can cut testing system.

uses cougaar (on /. yesterday i think) nodes.

xmpp - extensible messaging and presence protocol. jabber. protocol for im. ietf standard. xml format. messages + ontrol info amongst chat apps. simple, compact, readable. can understand it without knowing what it is. oh yeah? server based (clients talk to servers, servers peer-to-peer).

new book out on jabber from people giving talk.

server arch allows firewall penetration.

xmpp defines several services - messaging, presence, roster (buddy list), chat rooms, user db management, and server to server relay (different packet fmt than server-client).

ok, xml really is quite readable, even at low webcast resolution.

adresses are name@dot.address/resource - resource disambiguates sessions (work, home etc).

if i keep drinking this wine i'm not going to be able to type as fast!

relay system status throgh xmpp. buddy list contains computer. one not present - so compuer off-line.

messages convey commands. i hope they have a good firewall. ask host for available commands (existing bots? not clear). java / python code can do this too (don't need to use gui).

oh - talk ending! more about xmpp than ll. loosely coupled components that test a system of looseley coupled components. questions.

[inaudible question]. how reliable is java? jabber server is free. protocol design is reliable. maybe questioner saw bug? no ack for messages (could put that in client). so what did tehy mean about reliable protocol?

[question with word "scheme" in it] - what is lightweight about this? (good questions). answer: couldn't have been done without ll. java would have taken too long. you can write middelware in, say, ruby/python. (whoo is surprised?). (maybe i think ll should be dsl?). [more inaudible comments from audience].

something about types. ah. a static type advocate, i think? boring static/dynamic type argument. even at mit.

[another inaudible question]. this is an architecture.

[get a better mike for f*'s sake]. [missed a bunch of questions.]

[speak up]

haskell?! [difficutl to hear]

web changed to dynamic pages (i just used zope at work - not bad).

cgi is easy, but hard to do right for big apps. problems: protoocl stateless; string refs between scripts; name-value pairs only; manual error checking; html forms nasty; duplication in form structure; string manipulation for html gives results that may not be calid (aha - dsl alert!); security/synch on shared resources.

so family of ll for web apps in haskell (yay!). why haskell? adts, type safe iface, compositionality.

languages: document, sesson, widget, persistence.

documnt lang - quasi-valid html. (why quasi?). cosntructor fucntions for xhtml document nodes. the usual stuff. sequences of nodes are actions. "empty" for empty set of nodes. "do, >>=, >>> and ##" for composition. wash2hs preprocessor. (so action is monad, presumably). example coming on next slide... compiled to jsp?!

do p (text "my first prog")
   p (do text "hobbies are"
      ul (do (ll (text ("knitting")
             (ll (text ("something else"

oops. slide changed.

can also do this using a function (duh!). variables replace text.

another benefit - guarantee (almost) validity. [connection dropped] something about not guaranteeing order. overhead with types for above fucntions. something i don't understand. ah. use types for different chunks of html, so that sequencing is ok. so you can only add listitems to lists, for example, i guess.

session language. session is alternating sequence of forms and posts.

state may be stored in different ways - url rewriting, cookies, hidden input fields. how to deal with dreaded browser back button? (keeps me awake at night). window cloning. bookmarks (mummy, help!).

[connection keeps dropping]

entire app in one program - sessin state handled transparently by system. (wow - as good as (better than?) microsoft tools?!)

uses hidden fields. no state on server. browser nav fully supported. (good idea).

oerations: ask, tell, io, run. CGI is type for session. IO integrated, so can use external files, DBs etc.

main = run (ask (standardPage "ellowOwolf" myInfo))


myInfo =
do p (text (...

but missing interaction. widget sublanguage. (maybe i'm already drunk, but this is cool). types for each html doodah. user input appears in constructed code? submit buttons. web programs like gui programming.

attach callback functions to "pages". valid/invalid values reflected in type, so guaranteed validated by type suystem. heh.

main = run firstpage


firstpage = 
standardquery "example"
  (do inf <- p (do text ...
  submit inf secondpage ...


secondpage inf
  (p (text "your answer was...

[damn. battery warning on laptop. choclate biscuite finsihed too.]

persistency langauge. (presumably underlies what we've already seen). full type saftey again. across program boundaries. server and client side state.

comamnds like init, get, set.

example that i won't try to copy. "hall of fame" stored on server.

related work - uses/influenced by other people's libs.

conclusion - rich type system useful. future work - caching of programs. http://www.informatik.uni-freiburg.de/~thiemann/study.html try at http://www.informatik.uni-freiburg.de/~thiemann/haskell/WASH/

calculator example at 1hr 9m. very very sweet.

good talk! [and connection drops!]

[hmm. connection seems to be hosed. hope it comes back in time for next talk.]

prog env for lego mindstorms.

rcx is central processor unit. 16 bit. small ram, i think (can't understand everuything said, sorry). 3 ports for control, 3 sensor ports. lots of batteries (why so many? - my cellular phone is tiny). ir to communicate with "tower", which, in turn, is oonnected to computer (serial or usb).

provides read-eval loop. :o) dynamic allocation/gc. tail recursive. no first class continuations (saves on stack space?). asynch event support. [connection dropped]. "lambda closures" (different to full closures?).

constants. boring language details. comment for bye is "sayonara" - what does that mean? (goodbye, apparently. ah well). this lisp implementation includes car and cdr apparently. fascinating.

lego specific functions to cope with poor connections. not clear how much work is done on robot and how much on laptop. (would be nice if robot could off-load compute tasks). timer overflows in 13 min! ifae with sensors.

this talk is just a list of functions. there's one to control the lcd display. one to see if a button has been pressed. etc.

[drinks wine and surfs web]

[returns to see a diagram indicating how boxed values are stored. drinks more wine.]

mark + sweep gc. (does the robot stop while it's running?!)

windows + linux. http://www.xslisp.com (open source soon). (maybe this is cool if you have the hardware. wouldn't logo be cooler, though? (isn't logo almost lisp anyway?)).

demonstration. [don't think it worked (but wasn't watching much)]

shot of audience. all(?!) white (caucasian) males. (me too) (talker isn't; hope/believe my lack of enthusiasm for talk is unrelated; audience seems to be happy)

demo seems to be working now. heh - maybe the thing moved, but the web link is so jerky i can't tell. laughter suggests failure.

(ooh. split screen graphics - would prefer them to spend more effort on the sound quality.) and the robot moved!

[if anyone from mit reads this - up the volume! can't make out what the announcer is saying]

bluespec - asic related (is this the one in haskell in the fun of prog?). (yay! - volume just went up!).

typical process - model in c++/lisp etc, then rtl encode in verilog/vhdl (mix of wiring and behavioural notation). then expensive tool to generate gate level netlist. [onnection down] then physical layout and finally someone makes the thing. long process 9-18 months.

testing at every stage. some formal tools for equivalence checking.

repeating the process is expensive. more verification engineers than designers. "tools running out of gas."

hardware decription languages. (hdls). first wrote out circuits by hand. then started using languages. verilog, vhdl. not much has changed since early 90s. standardization in 95. last 2 or 3 years, industry wide effort to move to "system verilog". next generation.

buespec a little earlier than system verilog. sv doesn't add much for teh designer, only for the tester. bluespec also helps designer.

something vague about using more dyanmic languages. behavioural vhdl/systemc. seems to have failed.

semantic gap between threads, stacks, dynamic data and hardware descriptions (cooperating fsms (finite state machines?)). bluespec stays with fsms.

consider as a preprocessor for rtl.

used haskell first time round. but hardware people don't want to know. so instead embed inside system verilog.

example - 2 stage pipeline cpu. compose modules hierarchicaly. basic modules are registers etc - state. then describe behaviour. finalyl interface. modules like objects - state, behaviour, interface.

fifo - enque, deque, read first, clear. [dropped].

methods don't just tell you about connections. also includes timing etc. not clear to me how.

rule - describes branch on zero. pattern matching in language. other rules for other instructions. rules for prefetch + execute. term rewriting semantics - atomicity. defines clearly sequence of actions and allows reasoning about state. new for verilog, old for term rewriting.

implicit conditions - tedious bookkeeping - in the background.

can add extra conditions to check for writing to memory already cached. higher order functins in there somewhere.

examples - faster to design, but tend to have slightly more gates.

see also: lava, celoxica, signal/lustre, systemverilog (www.accellera.com)

question - asynch circuits? rules aren't one per clock. mapping is to clocked hardware, but may be thousands of rules per clock. so could also map to asynch. maybe haven't done much work on it yet.

[dropped]

lua. conventional sytnax. associative arrays as *single* data structure. first class values. any value as index. efficient. sugared (a.x is lookup). first class fns with lexical scope. tail call. coroutines. "dynamic overloading".

light - simple + small. portable. runs on many systems. efficient. easy to embed (even in ruby!). http://www.lua.org

used in many games. minimal linux. robots etc.

traditionally use virtual machine, stack based.

stacks too low level. high overhead per instruction. register machine allows more powerful instructions. overhead compensated by fewer isntructions. registers for each functin alloated on executin stack (so what's teh difference with a stack - still need to fetch + save?) large number of registers (256).

32 bits per instruction - divided into opcode, registers etc (as risc machines). different format for jumps, blobals etc where need more bits (18 bit address limitation?)

ah. shift from stack to register approach from lua 4 to 5. efficiency gain because stack messing around *inside* a single vm instruction, rathe rthan separate vm instructions. i think.

vm looks quite tidy. does anyone else target it?

assoc array implementation has optimizn for use as simple indexed array (split into simple array and hash table) (again, this is new for 5). when to use sparse array and when to move numeric indices into hash? (a bit too much detail?! - i am looking at lua site instead of taking notes on this)

performance results - faster than perl. changes in 5 mixed.

no more than 256 local variables (is this hidden by the compiler or does it hit long fucntins?!)

questions

not worried about size of bytecode.

6 bits for opcode. why (difficult/slow to mask/shift). not measured. but practical reason is don't have 2 bits to spare (to get to 8).

popular for games because portable (embeddable). and easy to learn (game designers, rathe rthan programmers).

(looks quite like jscript, i think).

(interesting paper: http://www.lua.org/spe.html)

[conexn down]

embedded language history. rexx, tcl/tk, lua.

building compiler for c--. compiler driver done in lua. call embedded fucntions from lua - run compiler, send to backend.

each backend is described using lua table. flexible. (comamnd line options interpreted, change lua code, change behaviour).

c-- written in ml. lua-ml interpreter. driver, config, stack layout written in lua. glue code needed between lua and c.

[dropped]

example of using lua glue code in c. lots of nasty checking of types and conversion. use tools instead. toLua - 4,000 lines of code. or swig (although not for lua), but that's 30.000 lines of code.

[dropped] [long time] [very long time] (pity - looked interesting) [says it's playing, but no signal. looks like problem at mit]

And seconds on the thanks to andrew.

To answer a couple of Andrew's Lua questions (it is a sweet little scripting language, remarkably easy to embed, whose syntax is conducive to using it as a sort of executable data description language):

32 bits per instruction - divided into opcode, registers etc (as risc machines). different format for jumps, globals etc where need more bits (18 bit address limitation?)

All jumps are relative, so the 18-bit limit limits the size of loops and conditional clauses, rather than the size of a function. I have certainly given it functions which are well beyond 2^18 opcodes (i.e. the function creates an enormous complex data structure with several million elements). No problem.

no more than 256 local variables (is this hidden by the compiler or does it hit long fucntins?!)

It hits long functions. If you write a function which requires that many locals and temps, it will tell you that your function is too complex. It is probably right :) The count doesn't include closed values, and it doesn't include locals which are out of scope. For example, the following uses only one local:

function foo()
for i = 1, 10 do print(i) end
for j = 1, 10 do print(j) end
end

because i and j are in the same stack slot (in a Lua for loop, the iterator variable is local to the iteration.)

(looks quite like jscript, i think).

It has some points in common, but jscript is a lot closer to C syntax. Lua is more like typeless Pascal, I would say -- it has a lot less punctuation than C. (The language is almost unambiguous without statement separators, so they are generally optional. Version 4 was actually unambiguous without statement separators, but in version 5 there is one case where you need them.)

The really interesting thing about Lua is its commitment to dictionaries as a primary data structure. They are very general: any object except nil can be a key or value; they can be defined as weak-keyed and/or weak-valued; and there is a metaobject protocol which they can respond to. But it also has HOFs

I don't know that it raises any complex theoretical questions such as those generally raised here, but it is an interesting example of how far you can get with an unswerving commitment to simplicity ("the best feature is the one you left out")

The main question I was left with was on stack based vs. register based VM's. Main thing I'm wondering is what impact going to a register scheme would have on the Byte Code Verification process (and thus indirectly on security)? Beyond that, I'm wondering why the VM specs seem to be cheapskates? If registers are good and stacks are good, and most modern processors implement both forms, then why do the VM's not allow both? And why the arbitrary limit on the number of registers? And why be limited to just one measly stack?

The VM's are not something that I usually care about, as the compilers perform their (what is to me) magic. But in this age of fast cpu's and cheap memory, I'm not sure I understand the move to be chintzy with the compression of opcodes/data into the minimum amount of space available. Ok, so it's really about optimization and performance. But it seems that compression schemes should not limit the instruction set length, as make it variable. Make the most common operations fit into a byte or two, and let the least common ones span multiple bytes of larger and larger magnitude.

Perhaps it's just that I miss my old assembly language days. The downside of ASM programming was that it was machine portable. Well, having a VM frees us from that problem, but then they don't allow us to speak to the machine in it's native language making it somewhat cumbersome - you need to write in a higher level language so the compiler is the only one that targets the instruction set. Programming in a Java bytecode assembler (like Jasmine) is a pain. A register based VM is easier to program in manually, but then you still need stack manipulation for the tricky problems.

http://www.makeoutcity.com/Downloads/2003-LL3.html http://www.makeoutcity.com/Downloads/2003-LL3.opml

Dave

[edit - ah, sorry, didn't read everything before posting]

It makes it trickier. However, if you insist that the byte code have a reducible flow graph, you can verify that every stack slot is defined before use in a single linear scan of the byte code.

If registers are good and stacks are good, and most modern processors implement both forms, then why do the VM's not allow both?

The Lua VM actually does use the stack in particular cases where direct addressing would be tricky.

And why the arbitrary limit on the number of registers?

Addressing limitations. It actually doesn't get in the way.

And why be limited to just one measly stack?

Interesting question. Multiple stacks would be useful, for example, for non-deterministic execution. However, that is probably a different research effort.

The thing I noticed scanning through the paper I referenced that looked new was fallbacks.

I think fallbacks are/were a limited form of MOP, under a different name. But Lua 5 no longer uses the terminology; it now uses "metatables" which are a somewhat clearer MOP allusion.

Multiple stacks can be problematic, though--you have the choice of tossing speed (if they're segmented), memory (if they're big), or utility (if they're small). I'd love it if some CPU or MMU had multiple independent addressible memory segments but, alas, no joy there.

I liked Bluespec because the language makes a clear distinction between using powerful tools for "static elaboration" of a program, versus using less-powerful tools for runtime execution. I find that kind of approach very interesting, because I'd like to be able to do things like write under-specified programs. That would require powerful static elaboration features, and would also require making a clear distinction between the static aspects versus the runtime aspects. Unfortunately I didn't get anything concrete out of the Bluespec talk, other than this vague similarity in approach.

The Father Time talk was by far the most interesting one. It's basically a spreadsheet-style evaluation mechanism for reactive systems. The most familiar "reactive system" is probably user interfaces, which react to mouse movements and keyboard presses. However the idea is also useful for things like monitoring and control systems, or more generally any system where you currently use event handling or polling.

I'm familiar with only a couple previous examples of this kind of dataflow-oriented programming being embedded within an imperative language. One is Visual Basic's "Data Binding" and another is Internet Explorer's "Dynamic Properties". A few years ago, I also spent a while thinking about how to implement such a thing in Java; I called it Ripple. I found it interesting that I had designed Ripple as a pre-processor, and Father Time is implemented as a macro system (i.e. a Scheme preprocessor).