Lisp is Sin (2006)(sriramkrishnan.com)

26 pointsby RiderOfGiraffes16 anni fa33 comments

Lisp is Sin (2006)

http://www.sriramkrishnan.com/blog/2006/01/lisp-is-sin.html

6 comments

Wow, why did this get posted after so many years? It's a bit embarrassing to see my writing from back then. Its amateurish, a bit tacky and I sorely needed to edit it.

As for my opinions now, I think classic Lisp is forever doomed to be a niche language. I think it's legacy will be contribution of ideas to mainstream languages.

Having said that, Clojure is fascinating and could prove me wrong.

mahmud16 anni fa

Actually, I clicked on the link thinking it was by another "Sriram Krishn*":

http://www.cs.brown.edu/~sk/Publications/Papers/Published/

I thought Dr. Krishnamurthi finally saw the Dark ;-)

jerf16 anni fa

Assuming by Lisp we mean either "Common Lisp" or "what somebody would have called Lisp in 2006", there is now an exception to "All roads lead to Lisp" that has moved from total obscurity to all-language-geeks-should-know-about-this: Haskell. You can not take a 2006 Lisp and macro your way to purity. You could build a pure subset, but that would be a new language in every way that matters because you couldn't use non-pure libraries without a lot of wrapping.

You can of course also start a new Lisp-like language with new primitives that do include immutability, but I would suggest that that shows Lisp moving forward by taking a feature from another heritage, which means you've no longer got all roads leading to Lisp/2006, you've got at least one leading away.

If there's anything strange about Lisp, it is that it really was a local optimum posing as the global optimum for so long. We should end up with a few more local optima before all is said and done; there aren't enough yet.

ohyes16 anni fa

The whole point of lisp is that it rolls around picking up new ideas. Haskell was originally implemented in lisp.

Examples: Lexical scoping (ALGOL)

The 'format' macro(I believe Fortran)

The 'loop' macro (COBOL? Pascal? not sure?)

Type systems ala Qi and Haskell (ML and typed lambda calculus influenced)

Optional type declaration are probably to approximate C.

You can implement prolog it...

I believe lisp machines even had GC'd versions of C, Pascal, and other languages written for them.

Personally, when I read "all roads lead to lisp," it is taken with tongue firmly in cheek. Lisp isn't really the 'best' language, it just ends up being able to subsume all of the ideas from them. In RPG terms, Lisp is the red mage.

This is why I like it a lot; given a certain problem domain, you can approximate the global optima that is reached in another language.

zephyrfalcon16 anni fa

"The whole point of lisp is that it rolls around picking up new ideas."

Kind of like the Katamari Damacy of programming languages... :-)

frou_dh16 anni fa

When I played that game I was ruining and picking up junky city debris! That sounds a scary language.

gaius16 anni fa

Not only Haskell: F#, OCaml, Erlang and Scala too. While Lispers were basking in the 50-year-old glow of being 30 years ahead once, all of these languages leapfrogged them and they don't even know it.

cageface16 anni fa

One killer feature remains exclusive to Lisp: macros. However, in languages as flexible as those you mention, with higher order functions and good type inference, you don't need macros as much as you might in less flexible languages. I'd love to see a serious evaluation of the cost/benefit of s-exprs and macros in real-world production code but I'm not sure how exactly how you'd measure this.

My own cursory examination of the clojure-contrib library's use of macros, for example, suggested to me that many of them wouldn't be necessary in a language like Scala, but I'd love to see a more rigorous study.

gaius16 anni fa

One killer feature remains exclusive to Lisp: macros

Lisp can't rest on its laurels here either:

http://www.haskell.org/haskellwiki/Template_Haskell

Luyt16 anni fa

He mentions a lot of LISP dialects, but not Clojure.

EDIT: Ah, there was no Clojure back then ;-)

fexl16 anni fa

I programmed in Lisp back in 1985 and liked it a lot. Today I consider it too imperative for my tastes, and also too heavyweight. So lately I've been embedding a little interpreter for my Fexl language ( http://fexl.com ) into my systems written in Perl. That way I can opportunistically use a pure functional language for script-like purposes such as dynamic web sites and report generation, without committing to rewriting my entire system in another language. The Fexl interpreter is tiny and only has 7 grammar rules, so it's really easy to deploy in very focused areas of the system.

It's going well so far in testing. I suspect that over time I will migrate an increasing amount of system logic out of Perl and into Fexl, so eventually all that remains in Perl is the Fexl interpreter itself. Then I'll swap that out for my interpreter written in C and be done with Perl.

Don't get me wrong -- I've been using Perl for 12 years and I know how to write disciplined code in it, so I am grateful to Perl. But I find the pure functional approach to be liberating, making many tasks seem almost effortless.

In fact, I've even been applying the functional concepts to my Perl code itself, with great reward. For example, when I'm parsing text, I don't use the usual destructive position pointer. Instead, I use a functional representation of the text, with head, tail, prefix, suffix, and such. It's liberating.

Another example: when I use my key-value maps with automatic hierarchical structuring by disjoint prefix, I no longer use a destructive "put" operation to change entries. Instead, the "put" operation in effect returns a brand new key-value map with just that one entry changed. It's amazing how efficient this is because of structure sharing, and it also adds much clarity to the code and avoids a lot of thorny implementation issues (especially because I actually need a super-efficient "virtual copy" of large key-value maps for what I'm doing.)

So my main points here are:

1. You can deploy a small embedded interpreter for a purely functional language, inside a system written in any language (yes, even Perl). You don't have to rewrite your entire system in a "pure" language all in one fell swoop, or ever. You can just systematically migrate more logic into the functional side, completely at your leisure, in an evolutionary fashion.

2. You can apply functional concepts and techniques to code written in any language (yes, even Perl). That works even if you don't go as far as using an embedded interpreter.

I am finding both of these techniques to be highly rewarding, and the most exciting thing I've done since I started programming in 1975.

Imbue16 anni fa

Is Fexl open-source, or even available for download? It looks pretty neat.

fexl16 anni fa

Funny, I was just thinking about that very thing when I noticed your post. Problem is, I'm a little "ashamed" to release the code right now because I'm in the middle of some major revisions:

1. Use DeBruin notation for referring to bound lambda values positionally, instead of my current approach of actually using the lambda symbol in an associative list. (Don't laugh, it works.)

2. Change the C implementation so it just uses an array of longs for the whole working space, with integer offsets, instead of node structs with pointers. At that point the whole implementation will be "nothin' but int", and avoid malloc altogether.

3. Change both the Perl and C implementations so that I supply external function definitions as function pointers. Right now when a high-order function is reduced to a normal form (lambda form), I actually look at the name of the external function being called and do a big if-else on that. (Don't laugh, it works.) This will no longer be an option when I go with DeBruin notation. Besides, the function pointer approach will be a lot more solid, serious, and extensible.

Thanks for expressing an interest. When I'm a little more proud of my code and have something available for download, I'll announce it on HN.

Imbue16 anni fa

This is probably a stupid question. If you have Fexl written in Perl now, what are the chances of just throwing a sand-boxed interpreter online for people to play with? I'm thinking just a form with an input field and a submit button which runs the script and displays any printed values.

fexl16 anni fa

It's a brilliant question, and it's now on my TODO list. I'll aim to get this done by the end of August.

You're right about the sandboxing too -- the Fexl interpreter runs with two limits: the maximum number of cycles, and the maximum amount of memory. If it reaches either of those limits, it halts. So it should be perfectly safe to run it on the public web.

fexl16 anni fa

Update: It might not be ready by the end of August. I just returned from a week-long trip, and I'm now busy rewriting the whole Fexl interpreter in terms of pure combinatorics (see http://fexl.com/#combinatorics ).

The interpreter understands only the two fundamental combinators S and C. Although it is possible to define high-order combinators in the interpreter using function pointers, I am limiting myself to S and C to minimize the code size and illustrate the principle that all computable functions can be defined as applications of only S and C.

So, for example, even the Y combinator itself is defined in terms of S and C as:

  \I = (S C C)
  \Q = (S (S (C S) C) (C (S I I)))
  \Y = (S Q Q)

I'm now doing some bootstrapping, eliminating code formerly written in Perl. I'm writing the Fexl parser in Fexl, and manually converting it to S and C. I can then eliminate the parser written in Perl.

Imbue16 anni fa

I'm not trying to rush you or anything. Just want to let you know that at least one person is still looking forward to seeing it.

fexl16 anni fa

Thanks, that's very good to know. I've made excellent progress on the Perl implementation, doing everything in terms of combinatorics. Much thought has gone into this.

I think before I put up the sandboxed interpreter at fexl.com, I'll just release a tar.gz file of the Perl code. That way I can release something even earlier. Also, it will give me more time to take a look at a case that causes a segmentation fault. One of my test cases is a "metastasis" function which runs forever using an increasing amount of memory. That function is:

  Y S f g

Where Y is the fixpoint function, S is the fusion function, and f and g are any functions.

I can limit the evaluation to let's say 3,000,000 cycles, so it does terminate just fine. But at that point I've built a deeply nested data structure in Perl, and when I drop it and the reference count goes to zero, Perl begins freeing that structure recursively. Well, that causes a stack overflow and hence a segmentation fault.

My workaround was to store a pointer to the big structure in a global variable. That way the structure stays live until the program terminates, at which point Perl simply abandons the structure instead of trying to free it recursively.

Of course, I easily avoid this problem in the C implementation because I free structures lazily.

Another workaround is to write a destroy routine which frees a structure non-recursively. I did try that, but the problem is that it goes all the way down, even destroying my standard structures for the Y and I combinators. So it's only something that could be used once during a program run.

In any case I'd rather not put up the sandboxed interpreter until I can get a good handle on the metastasis case. I just need to work around this one issue with Perl.

I think the code will illustrate how easy it is to augment an existing programming language such as Perl or C with a high-order functional interpreter. I'll keep you posted.

fexl16 anni fa

Actually there's a much simpler metastasis function, perhaps the most evil function of all, namely, the result of applying the Y combinator to the Y combinator itself:

Y Y

If you expand this function two steps, you'll notice that it equals:

  Y Y (Y (Y Y))

And so you end up with an infinitely left-recursive thing from hell.

Fortunately my implementation of Fexl does not use built-in recursion, which would quickly throw up a segmentation fault due to stack overflow. Fexl does its own stack with a chain of nodes. Also, Fexl runs inside a completely bounded "arena", which is a fixed-size array of machine integers. All node "pointers" are actually just integer offsets into this arena. This makes it possible to increase the size of the arena by allocating a brand new one and doing a mass copy from the old to the new. But I have not bothered with this yet, because I figure that deciding on your upper bound on memory once up front is just fine for now. Note also that my approach allows for nested arenas, so for example you could have a Fexl function which allocates an arena and runs a Fexl interpreter inside there. The whole thing is completely reflective in the most profound way you could imagine, so the sky's the limit. The use of pure functions enables abstractions which are not leaky.

This leads me to my main point. I've decided to stick with the C implementation because it gives me the complete control which I need. When I want to call Fexl from Perl, I will simply fork a separate Fexl process and have Perl pump a Fexl function into its standard input. That initial function can then read any remaining input. You can do any sort of bootstrapping this way, for example the initial function may expect another Fexl function at the head of the remaining input. Any file names on the Fexl command line would simply be treated as if their contents had appeared on standard input first.

The Perl code then reads the standard output of the Fexl process, and that's its answer. On the web, it could connect the output directly to the client socket and be done with it.

One nice thing about this approach is that it's utterly safe. Your code could read the evil (Y Y) function straight off a socket from a known black hat and evaluate it with confidence, knowing that it would simply reach your upper bound on memory -- or cycles, whichever comes first -- and halt in the most ordinary way.

Another nice thing is that I don't have support an endless list of implementations in other languages, or even bindings for other languages. There is one authoritative piece of code written in C and that's that.

If you feel that this approach is too slow, then you can simply move more of your logic from Perl into the Fexl program itself. If you take this principle to its extreme, you would end up with a Perl process which does nothing except feed a program into Fexl -- at which point you would drop Perl altogether. Note that Fexl programs can be extremely compact, and you could even read auxiliary functions from files on demand.

Ultimately the entire API at https://loom.cc will be based on Fexl. Instead of doing a bunch of grungy back-and-forth API calls and doing all your branching and looping on the client side, you can just ship an entire Fexl program to the Loom server and have it run there, delivering precisely the answer you want in the format you want. You could even send back a single number such as "42" if that's all you need.

To avoid shipping the same program to Loom repeatedly, you could store the program in an Archive slot once. Then whenever you want to run that program, you only have to send the archive ID.

Imbue16 anni fa

It sounds like you're having a lot of fun with it.

I think a C implementation would be better anyway. C is the common denominator between almost every language. Have you already done the foreign function interface to C?

When do you think we might see either source code or a live web demo to play with?

For a web demo, couldn't you just add a quick CGI interface to your C program?

fexl16 anni fa

Not only have I done foreign function interface to C, the entire system depends on it.

Every atomic item begins with a pointer to its "type". Following the type pointer is an arbitrary vector of 0 or more machine words which constitute the data for that atomic item.

The type consists of a pair of C routine pointers: a "step" routine and a "show" routine. To write a new type X, you create two C files "type_X.h" and "type_X.c". The .h file typically contains a single "extern" declaration making the type structure visible to the rest of the system. As it stands right now, you must statically link your new type into the Fexl executable. I suppose eventually I or someone else can create a type which allows access to dynamic libraries, but I'm not messing with that right now.

The step routine is called when the atomic item is used as a Fexl function. Typically it should do a small and quick bit of surgery on the stack and return fairly quickly. It should never loop or fail to terminate in a predictable time. I believe this can eventually form the basis for "threading" multiple function reductions in a single process, but for now I'm sticking with a single reduction.

The show routine is used only for introspection, allowing the display of structures for tracing purposes during development and debugging. It returns a string representation of the atomic item, in the form of a valid Fexl token which can be parsed and easily distinguished from other types of atomic items.

With this feature, one can write a Fexl function which lazily converts a raw memory structure into a functional binary tree with tokens at the leaves. Then it is easy to write a Fexl function which lazily converts that binary binary tree into a functional string, or simply prints it directly.

That way even when you're debugging you never have to write a recursive C routine to traverse the memory structures aggressively, or worry about buffering large string representations.

All that is required for general purpose computation is the core "reduce" routine, which handles function application, along with the atomic types for the S and C combinators. To enhance efficiency, I also provide atomic types for the I and Y combinators, which could otherwise be defined in terms of S and C.

The reduce routine itself is under 10 lines of C code, consisting of a "while (1)" loop with some simple logic in the middle. It terminates when the reduction reaches a normal form, or when it loops beyond a maximum number of cycles, or when the memory arena is exhausted -- whichever comes first. So it is guaranteed to terminate.

Regarding the web demo, I have to be very careful with that. I'll be exposing a universal Turing machine to the World Wide Web. Certainly I'll be sand-boxing it, embedding the client's Fexl function inside an environment which does not allow arbitrary operating system calls. Nevertheless, because this is a very new product, I'll need to do extensive verification and testing on it to make sure it's properly sealed off.

Until now I've been fairly cavalier about it, because I've just been using a half-assed Perl interpreter which only calls a few safe routines, and was only exposed to a few trusted users. This new thing is a far more powerful beast, but it's code I can be proud of.

As for the schedule, I'll have to shoot for end of September. Typically I must devote the first half of every month to getting the hedge fund accounting done. After that I have more time for side projects.

One thing that has slipped my schedule is the need to do my own memory allocation inside the arena (the master array of ints). I can't trust any outside memory allocators. I call calloc once to create that arena, but after that it's all my own code. I'm doing the trick where a node begins and ends with a length, and I have a doubly-linked free list, so I can easily coalesce adjacent small free nodes into larger ones.

All my function application nodes are the same size, but there is no such constraint on Atomic! So I have to allow for variably sized data.

Thanks for your interest! Now that I have an audience of at least one, it's fun "blogging" about it here at HN. Thanks Paul Graham!

fexl16 anni fa

The Fexl interpreter is simple, elegant, and fast. The core "reduce" routine runs about 43.5 million cycles per second on a simple infinite loop. If I set max_cycles to a billion it stops after about 23 seconds.

To test it with something more real, I wrote the "cat" program in Fexl as follows:

  \cat = (get_char \ch eq EOF ch I; put_char ch cat)

Then I pumped 30MB of data into it, which took about 42 seconds:

  time (head -c 30000000 /dev/zero | fexl_cat >/dev/null)

Of course that's a lot slower that pushing the data through the Unix cat program, which only takes about 0.14 seconds:

  time (head -c 30000000 /dev/zero | cat >/dev/null)

But think about all the gyrations happening here:

  \cat = (get_char \ch eq EOF ch I; put_char ch cat)

That is translated into the closed (variable-free) form:

  (Y (S (C get_char) (S (C (S (S (eq EOF) (C I))))
  (S (C (S put_char)) C))))

Then that runs like the wind, applying combinator rules such as these many millions of times:

  C x y = x
  S x y z = x z (y z)
  I x = x
  Y x = x (Y x)

Not to mention that get_char and put_char are handling and building characters one at a time, and the "eq" function runs as a combinator as well.

By the way it is quite trivial to add new combinators written in C. For example, the fabled Y combinator is defined in a single file "type_Y.c" as follows:

  #include "node.h"
  #include "type_Y.h"

  /*
  Fixpoint function (Y combinator):  (Y f) = (f (Y f))
  */
  static void step(void)
      { 
      int f1 = pop();
      if (!f1) return;

      set_pair(f1, R(f1), P(L(f1),R(f1)));
      } 

  int type_Y(void)
      { 
      static int node = 0;
      if (node == 0) node = new_combinator(step);
      return node;
      }

The type_Y.h file just says:

  extern int type_Y(void);

fexl16 anni fa

The whole thing is about 800 lines of C code so far, and I aim to get that lower. :) For one thing, I'm busy bootstrapping the Fexl parser into Fexl itself. It's really neat to be able to express executable concepts simply and completely like this:

  # Parse a nested parenthesized expression.
  \parse_nested =
    (
    \yes
    \no
    skip_char ch_lparen
        (
        parse_expr
            (\expr skip_char ch_rparen (yes expr) no)
            no
        )
        no
    )

And it's simple to do either-or parsing like this:

  # Parse a factor:  either an id or a nested expression.
  \parse_factor =
      (
      \yes
      \no
      parse_id (\id yes (var id));
      parse_nested yes;
      no
      )

Even such mundane tasks as skipping white space and comments have a satisfying elegance about them:

  # Skip filler, including white space and comments.
  \skip_filler =
      (
      \done
      skip_space;
      skip_comment
          (skip_filler done)
          done
      )

Imbue16 anni fa

Not sure if I am understanding this correctly. By bootstrapping, do you mean C does only the most basic syntax parsing, and then a fexl script (written in a basic fexl subset) does the more complete parsing?

All this stuff is really neat. Your C code interface looks quite nice and clean. I hope you release some source code soon.

And thanks for taking the time to write all this. Even though a lot of it is over my head, it's quite interesting. I'm really looking forward to playing around with it a bit and learning.

fexl16 anni fa

By the way, the initial release of Fexl will take a very simple form: A Universal Filter. The "fexl" executable will be nothing more than a program which maps standard input to standard output. So it's a filter. But it's universal because it is Turing-equivalent, capable of performing any conceivable function from stdin to stdout.

When Fexl runs, the first thing it does is read a Fexl function from standard input. The Fexl process then "becomes" that function, processing the tail of the input accordingly. Simple!

fexl16 anni fa

That was the general idea. But it's taken quite an interesting turn lately! Turns out I can parse Fexl one character at a time and build the closed executable form in a single pass as I go along -- thanks to a concept which I discovered several months ago but shelved as a mere curiosity at the time. But I'm sure using it now!

I started a proper blog here: http://fexl.com/blog , but we can still use ycombinator.com for discussion.

fexl16 anni fa

I created a Fexl discussion group at http://groups.google.com/group/fexl .

You can reach everything from http://fexl.com, including the Blog and Discussion group.

[deleted]16 anni fa

fexl16 anni fa

OK, here's one more example of how to write a Fexl combinator. Back in 1924 the great Moses Schönfinkel demonstrated that all computable functions can be defined in terms of just two primitive functions: C (the constant function), and S (the fusion function). So here is the source code for S, the Mother of all functions:

  #include "node.h"
  #include "type_S.h"

  /*
  Fusion function (Verschmelzungfunktion)
  S x y z = ((x z) (y z))
  */
  static void step(void)
      {
      int f1 = pop();
      int f2 = pop();
      int f3 = pop();
      if (!f3) return;

      set_pair(f3, P(R(f1),R(f3)), P(R(f2),R(f3)));
      }

  int type_S(void)
      {
      static int node = 0;
      if (node == 0) node = new_combinator(step);
      return node;
      }

[deleted]16 anni fa

fexl16 anni fa

I have decided not to store type pointers directly in the Fexl arena. Instead, I will use a type number, which will be an integer offset into a static array of function pointers in the C program.

That way I could use a memory-mapped array for the arena, making it suitable as a persistent state for a Fexl computation, which could easily be stopped and resumed.

This also avoids the need for a special "show" function pointer in a type structure. Instead, the show functions could be stored in a parallel array of function pointers -- again, indexed by type number.

Imbue16 anni fa

Great! I'll be looking forward to it. I kind of have a thing for small languages.

fexl16 anni fa

If you're interested in dabbling a bit, here's the grammar I'm using:

Here is the basic Fexl language, which can express all computable functions.

   expr = \atom expr
   expr = factor
   expr = factor expr

   factor = atom
   factor = (expr)

 The full language includes two additional notations for convenience.

   expr = \atom=factor expr
        = (\atom expr) factor

   expr = factor; expr
        = factor (expr)

shrikant16 anni fa

4 years down the line, sriramk, any updates?

udzinari16 anni fa

"Lisp is like the villainesses present in the Bond movies. It seduces you with its sheer beauty and its allure is irresistible. A fleeting encounter plays on your mind for a long,long time. However, it may not be the best choice if you're looking for a long term commitment. But in the short term, it sure is fun! In that way, Lisp is...sin. " Oh, is it? I think it is exactly the opposite.