• Advertisement

Archived

This topic is now archived and is closed to further replies.

Will LISP Finally Be Replaced?

This topic is 5042 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Will LISP, the perenial AI toolkit, finally be replaced by a more modern language? C# version 2.0 will provide native support for first class functions (lambda function objects). From the graduate class I took in programming languages, I got the impression that support for lambda functions is the key feature of LISP (or even ML/SML.NJ) that enable an elegant solution to a problem that would be otherwise painful and tedious to write in a procedural language like C++. Will this make C# a viable alternative for sophisticated AI programming? Do you think that with support for lambda functions being provided in a mainstream language, that the functional programming paradigm will find a new applications? I can see several potential uses for first class functions in constructing a data-driven AI for something like an empire-building strategy game. If not smarter opponents, it may allow for more varied AI play with less work. Of course, LISP will probably live forever, as its conceptually dense code seems to appeal to people who can think that way. I myself find it counter-intuitive and am excited that this feature has escaped the confines of LISP and its descendants. Read about C# 2.0 language innovations http://msdn.microsoft.com/vstudio/productinfo/roadmap.aspx ---------------------------------------- Let be be finale of seem, seems to me. ---------------------------------------- Shedletsky''s Code Library: Open source projects and demos

Share this post


Link to post
Share on other sites
Advertisement
quote:
Original post by Telamon
I got the impression that support for lambda functions is the key feature of LISP (or even ML/SML.NJ) that enable an elegant solution to a problem that would be otherwise painful and tedious to write in a procedural language like C++.

No. Lambda functions are present in many languages, and are only a small part of the beauty of Lisp.

Share this post


Link to post
Share on other sites
Frankly, I can't see what you could write using anonymous functions that you couldn't write without them. All you have to do is add another named function, which can sometimes be annoying but is far from painful or tedious.

Of course, I'm speaking in terms of the imperative approach to programming that C# lends itself to. I've never felt myself limited by a lack of anonymous functions when programming the C# way, but their absence would make Lisp very uncomfortable.

[edited by - twix on April 12, 2004 8:20:14 PM]

Share this post


Link to post
Share on other sites
Can you show me a source that states that C# 2 will have first class functions? (And the anonymous method syntax described in the link you posted does not actually define first class functions.)

Share this post


Link to post
Share on other sites
quote:
Original post by SiCrane
Can you show me a source that states that C# 2 will have first class functions? (And the anonymous method syntax described in the link you posted does not actually define first class functions.)


The anonymous function syntax in C# wraps the function in a delegate. Delegates will remain the only method for passing around functions.

[edited by - twix on April 12, 2004 8:48:29 PM]

Share this post


Link to post
Share on other sites
So what you''re saying is that C# 2 doesn''t actually have first class functions as claimed in the original post?

Share this post


Link to post
Share on other sites
quote:
Original post by SiCrane
So what you''re saying is that C# 2 doesn''t actually have first class functions as claimed in the original post?

Delegates are a somewhat clunky way of providing the same functionality as first class functions, no? Anonymous delegates just take you one step closer to the Lisp method by eliminating the named function that the delegate refers to.

So no, C# will not have real first class functions, or at least I''ve heard no rumors of such a thing.

Share this post


Link to post
Share on other sites
I''m a little confused.

Isn''t the definition of a first class function an object that can be returned as the result of another function, saved in some type of reference object, and then executed later? That seems to be the capability that they are offering here.

As for why this is useful, it allows your program to write code and then run it. To do this in C, you would need to write your own compiler. This kind of thing might come up when dealing with making a scripting language or building a finite automata. The most oft-quoted example in class was expression parsing. I actually wrote a simple expression parser for class in ML, and while the code was godawful ugly, it was succinct and the ideas behind it elegant (not to mention easily extendable).

I don''t see why they wouldn''t add first class functions to .Net - the CLR appears to provide a lot of the necessary support already.

----------------------------------------
Let be be finale of seem, seems to me.
----------------------------------------

Shedletsky''s Code Library:

Open source projects and demos

Share this post


Link to post
Share on other sites
quote:
Original post by Telamon
Isn't the definition of a first class function an object that can be returned as the result of another function, saved in some type of reference object, and then executed later? That seems to be the capability that they are offering here.


I've had no formal classes on languages that support them, but AFAIK the defenition of a "first class function" is simply a function that can be used as an argument or be returned by another function.
quote:

As for why this is useful, it allows your program to write code and then run it.

I agree that this is a great benefit and it's one of the things I love most about Lisp, but I don't think that C# is capable of that. Perhaps I ought to look into it some more, but I haven't heard of the ability to use C# own compiler from inside a C# program.

[edited by - twix on April 12, 2004 9:20:59 PM]

Share this post


Link to post
Share on other sites
Ah, I was wrong. C# can indeed generate code on the fly, but that has nothing to do with first class functions.

Here's a snippet of generating a very simple class.

using System;
using System.Reflection;
using System.Reflection.Emit; // To emit MSIL

using System.Threading; // To get Current AppDomain

public class MSILGen
{
public MSILGen()
{
// Create a simple name for the assembly.

AssemblyName assemblyName = new AssemblyName();
assemblyName.Name = "CodeGenAssembly";
// Create the dynamic assembly.

AppDomain appDomain = Thread.GetDomain();
AssemblyBuilder assembly = appDomain.DefineDynamicAssembly
(assemblyName,
AssemblyBuilderAccess.Run);
// Create a dynamic module.

ModuleBuilder module = assembly.DefineDynamicModule
("CodeGenModule");
// Define a public class named "CodeGenClass" in the assembly.

TypeBuilder helloWorldClass = module.DefineType("CodeGenClass",
TypeAttributes.Public);
// Define a private String field named "Message" in the type.

FieldBuilder greetingField = helloWorldClass.DefineField
("Message", typeof(String),
FieldAttributes.Private);
// Create the constructor.

Type[] constructorArgs = { typeof(String) };
ConstructorBuilder constructor = helloWorldClass.
DefineConstructor(
MethodAttributes.Public,
CallingConventions.Standard,
constructorArgs);
// Generate IL for the method. The constructor calls its

// superclass constructor. The constructor stores its argument

// in the private field.

ILGenerator constructorIL = constructor.GetILGenerator();
constructorIL.Emit(OpCodes.Ldarg_0);
ConstructorInfo superConstructor = typeof(Object).
GetConstructor(new Type[0]);
constructorIL.Emit(OpCodes.Call, superConstructor);
constructorIL.Emit(OpCodes.Ldarg_0);
constructorIL.Emit(OpCodes.Ldarg_1);
constructorIL.Emit(OpCodes.Stfld, greetingField);
constructorIL.Emit(OpCodes.Ret);
// Create the GetMessage method.

MethodBuilder getGreetingMethod = helloWorldClass.DefineMethod(
"GetMessage",
MethodAttributes.Public,
typeof(String), null);
// Generate IL for GetGreeting.

ILGenerator methodIL = getGreetingMethod.GetILGenerator();
methodIL.Emit(OpCodes.Ldarg_0);
methodIL.Emit(OpCodes.Ldfld, greetingField);
methodIL.Emit(OpCodes.Ret);
// Fry the class CodeGenClass.

typ = helloWorldClass.CreateType();
}
Type typ;
public Type T
{
get { returm this.typ; }
}
}

To be honest, I think I'll stick with Lisp.

[edited by - twix on April 12, 2004 9:20:03 PM]

Share this post


Link to post
Share on other sites
In addition to Emit''ting MSIL, the C# and VB.Net compilers are part of the CLR as well. So you can load a .cs or .vb source file and compile it into an assembly (then load the assembly) on-the-fly as well.

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
In addition to Emit''ting MSIL, the C# and VB.Net compilers are part of the CLR as well. So you can load a .cs or .vb source file and compile it into an assembly (then load the assembly) on-the-fly as well.

That''s pretty nice.

Still, I think .NET is missing the one other thing it needs to make this sort of functionality really useful, and that''s the concept of code-as-data, which I think is what Telamon was referring to in the first place.

Share this post


Link to post
Share on other sites
quote:
Original post by twix
Delegates are a somewhat clunky way of providing the same functionality as first class functions, no?

No. They aren''t. Delegates are more like typesafe replacement for function pointers.

quote:
Original post by Telamon
Isn''t the definition of a first class function an object that can be returned as the result of another function, saved in some type of reference object, and then executed later? That seems to be the capability that they are offering here.

If you try to use that definition, then C/C++ functions are also first class data types, and I don''t think you''ll be able to find anyone who will back you up on that matter.

To meet my definition of a first class function, which incidently is the definition given by my copy of "Essential of Programming Languages" in order for a function to be first class, then the function itself has to be storable as data in a form intrinsic to the language. Not just a reference to the function. Which is a subtle difference and it''s somewhat easy to understand why you have confused what C# is offering with true first class functions.

quote:

To do this in C, you would need to write your own compiler.


Right, and to do it in C# you have to access a MSIL compiler as well. Creating a new function at runtime in C# requires extra linguistic measures.

Share this post


Link to post
Share on other sites
quote:
Original post by SiCrane
quote:
Original post by twix
Delegates are a somewhat clunky way of providing the same functionality as first class functions, no?

No. They aren''t. Delegates are more like typesafe replacement for function pointers.


Fair enough. But what functionality of first class functions are delegates missing? Judging by that little code snippet in the roadmap, I guess you can do this:

do_something( new MyDelegate (int a, int b) { return a + b; } )

or

public static void return_del ()
{
return new MyDelegate (int a, int b) { return a + b; };
}

That seems to more or less fulfill the requirements, or is there something I''m missing here?

Share this post


Link to post
Share on other sites
quote:
Original post by twix
That seems to more or less fulfill the requirements, or is there something I''m missing here?


Well, first you need to realize that delegates are actually classes in the C# type system. They wrap a function pointer and its environment. The function itself cannot be passed.

And again, to meet my definition of first-class function, you need to store the function as data. Any layer of indirection means that functions are not truly first class.

Let me quote from an article I saved from the msdn website to explain why the new syntax doesn''t help achieve first-classness. It''s entitled "The C# Programming Language Future Features" (The author''s name doesn''t seem in any of the usual places):
"When an anonymous delegate is encountered, the C# compiler automatically converts the code in its scope of execution into a uniquely named function within a uniquely named class. The delegate in which the code block is stored is then set to reference the compiler-genarated object and method. When the delegate is invoked, the anonymous method block is executed via the compiler-generated method."


In other words, it''s just another compiled class except that you don''t name it yourself. The function itself is not created at runtime, it''s created at compile time, and a new instance of the delegate binding it is created at runtime. If you didn''t consider C# to have first class functions in its previous release, there''s no reason for you to consider them first class now; as anonymous delegates are just syntactic sugar around class creation.

For one final argument as to why I don''t consider C# functions to be first class types: try passing an instance method without an object as a delegate. The language won''t let you do it. (And for good reasons, I might add. I don''t disagree with the language choice, I just don''t consider the language to have first class functions.)

Share this post


Link to post
Share on other sites
SiCrane:

Since you are just quoting a book, while I have done problem sets involving figuring out how languages implement first class functions, it''s easy to see how you might be confused.

The first class functions returned as a result of executed code have to be saved on a heap, as opposed to the stack, because there are scoping issues (known as the funarg problem). The generated code is actually saved on the heap until there are no references left pointing to it, as which point it can be collected by mark and sweep GC.

So my definition of a first class function is correct.

Explain to me how this works without references. There has to be a level of indirection. It doesn''t really matter that delegates are objects - you have to store the reference someplace. Why not in an object? It''s neater that way.


----------------------------------------
Let be be finale of seem, seems to me.
----------------------------------------

Shedletsky''s Code Library:

Open source projects and demos

Share this post


Link to post
Share on other sites
First off, I'm not just quoting a book. I've probably done as much language design work as you have.

However, let's assume I'm wrong. Now prove to me that C++ doesn't have first class functions.

edit: Actually, I just re-read your post and ....
quote:
Original post by Telamon
The first class functions returned as a result of executed code have to be saved on a heap, as opposed to the stack, because there are scoping issues (known as the funarg problem). The generated code is actually saved on the heap until there are no references left pointing to it, as which point it can be collected by mark and sweep GC.


What are you talking about? The code of an anonymous delegate is known at compile time, there's no reason that the code proper is on the heap or the stack.

[edited by - SiCrane on April 12, 2004 12:49:54 AM]

Share this post


Link to post
Share on other sites
If the method body of an anonymous function needs to be changed at runtime, then the anonymous function must have its own stack frame (for local variables, ect...) - but this frame must be outside The Stack, because of the afforementioned funarg problem.

From the roadmap:

"Anonymous methods are defined dynamically at the point at which they are used, rather then being pre-defined as a named method of a specific class. Anonymous methods make some types of operations more convenient, particularly when the method signature or body needs to be changed at runtime."

If you can change the method body during runtime, it cannot be precompiled.

This seems like first class function support to me, as it supports the general "functions as data" paradigm. The difference between what happens here versus what happens in C++ is that the functions themselves are being created at runtime. They require that the stack frame that defines the scope of the first class function maintain a reference to a closure for the function (as opposed to C++ where the closest analog is a function pointer).

You would have to go through great contortions to make this work in C++. I''m not saying that you couldn''t, since obviously both C++ and LISP are Turing complete and thus equivalent in power of expression - but the modifications that you would have to make in C++ (writing your own compiler, or interpreter, or embedding a scripting language, ect) are not trivial.

So you may be right that these anonymous functions amount to "syntaxic sugar", but compared to the code that twix posted to do the same thing in C# now, I don''t think there can be too much argument that it is quite a bit of sugar.

Regardless, it seems like the answer to my original question is "No."

----------------------------------------
Let be be finale of seem, seems to me.
----------------------------------------

Shedletsky''s Code Library:

Open source projects and demos

Share this post


Link to post
Share on other sites
quote:
Original post by Telamon
"Anonymous methods are defined dynamically at the point at which they are used, rather then being pre-defined as a named method of a specific class. Anonymous methods make some types of operations more convenient, particularly when the method signature or body needs to be changed at runtime."


That actually contridicts several other descriptions of the implementation of anonyomous delegates on the microsoft website and other places.

I''ll tell you what, when C# 2 actually gets released we can look at the actual code generated and revisit this issue. But until then, I don''t think either of us will be able to convince the other either way.

Share this post


Link to post
Share on other sites
I don''t mean to step in the middle of an argument, but I''m curious about something...how is it possible for a compiled language to have functions as first-class data types? My knowledge of functions as data extends only to Lua; it makes perfect sense in that context, since functions are just big strings, and Lua is very good at holding strings as variables and passing them around. Obviously the same isn''t true for a compiled language, yet I''ve read at least one of the myriad flavors of Lisp is compiled, and Lisp just wouldn''t be Lisp without treating functions as data (or so I gather; I lack personal experience in the matter). How can that be? In Lisp, can you execute an arbitrary buffer of binary data as code?

Share this post


Link to post
Share on other sites
quote:
Original post by Muse
Obviously the same isn't true for a compiled language, yet I've read at least one of the myriad flavors of Lisp is compiled, and Lisp just wouldn't be Lisp without treating functions as data (or so I gather; I lack personal experience in the matter). How can that be? In Lisp, can you execute an arbitrary buffer of binary data as code?

I believe that since functions are first class objects in Lisp, their binary data is treated exactly the same way as any other variable, i.e. stored on the heap. So it's no problem to have functions that are compiled on the fly, stored on the heap, and exectued as necessary. The thing about lisp is that the compiler is part of the language, so all you ever have to do to execute an arbitrary piece of machine code is call (compile) on a list (although this is not strictly necessary for some implementations).

So basically, the answer to your question is yes. Corman Lisp, for example, does not have an interpreter. Instead, if you enter a function into the toplevel loop, memory will be allocated to store it on the heap and it will be compiled into machine code and saved. If you choose to call the function, execution will just branch to that location in memory.

[edited by - twix on April 13, 2004 9:46:46 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Muse
I don''t mean to step in the middle of an argument, but I''m curious about something...how is it possible for a compiled language to have functions as first-class data types?

With difficulty. There are any number of tricks to do so, many of them including multiple representations of functions at different points. That is to say, at runtime a function could be either a graph of symbols, a string, a blurb of bytecode and/or compiled native code all at different periods of its lifetime. Or at least components that goto make up the function may be all these different things.

For example, lets say you have a function to make a function in text on the disk. You can read it off the file, and turn it into a symbol list pretty easily in lisp. Then you can take that symbol list and compile it into a function. The internal representation might be native code with a blob of byte code that represents the function template that it will use when composing the function that the function will return. Then when the function creates the function, the blob will be combined with data to form the actual function. (ok, I''ve rewritten this paragraph three times already and enough is enough. Just let me know if I''m completely incomprehensible.)

Share this post


Link to post
Share on other sites
BTW, I think the thing that makes Lisp useful for AI is its extensibility. I mean, if you look at a typical planning system, you see things like:

(operator PICK-UP-BLOCK
Parameters (block)
Preconditions (not (on ?X block))
Postconditions ...)

If you look at the code for something like mycin, you might see things like this:

(disease BACTERIAL-MENINGITIS
symptoms
HIGH-FEVER OR (MEDIUM-FEVER AND COLD-SWEAT)
AND ...)

These clauses are typically compiled into code using the macro system.




[edited by - Nekhmet on April 14, 2004 9:42:37 PM]

Share this post


Link to post
Share on other sites
Lisp will never be "replaced" by a langauge like C#. Ever.

My Kung Fu is stronger.
neo88

Share this post


Link to post
Share on other sites

  • Advertisement