First of all, I need to explain:
"Extreme Beauty" does not mean Yue'er's article, because I am not so arrogant yet:P, it describes the beautiful form of combining Lisp and JavaScript.
Originally, the following content was to be released on Wuyou, but unfortunately, I suddenly found Wuyou "bombed" on the day of completing the article. It was not restored until last weekend. Since I couldn't wait that long, I put it on Yue'er's blog on CSDN first.
As the title describes, the following is about the skills of implementing Lisp-like languages in JavaScript. However, the focus is not on how to implement a programming language, but on demonstrating the simplicity and flexibility of JavaScript and the beauty of Lisp through thinking and implementation processes.
Perhaps not many people come into contact with Lisp here, so many people will definitely be surprised by the following content or form. If you have never been exposed to it at all, don't be too surprised. Lisp is indeed different from all programming languages you have seen before, because, uh, it is Lisp, a unique Lisp, a wonderful idea of elegant, concise, complete, independent. Maybe you will find it difficult to understand, but once you understand, you will like it.
Okay, let’s start our LispScript journey~
Recently, I accidentally saw an article online saying that javascript = C+Lisp, so I thought about this question. Since javascript contains some of the blood of Lisp, what would it look like to use javascript to implement an artificial intelligence script similar to Lisp?
As a "functional" language family, the LISt Processing language family has conquered many researchers and enthusiasts with its simple and beautiful style and simple and efficient structure since its birth.
At present, this ancient language and grammar is still used and loved by many people, and plays a very huge role in fields such as artificial intelligence.
I think that the flexibility of javascript and the simplicity of Lisp should be able to create a very beautiful language, but what does this language look like? I believe everyone wants to know too, so let’s study this very attractive issue together.
(Before reading the following content carefully, it is recommended that you pour a cup of hot tea first, sit down and calm your mood, take a deep breath, and concentrate, because the following process will be interesting and brain-consuming...^^)
Before entering the Lisp Kingdom, let's do some preparations for javascript... Please read the following code carefully
NIL = [];
= function()
{
if( <= 0) return "NIL";
var str = "";
for (var i = 0; i < ; i++)
{
if(this[i] instanceof Array)
str += "," + this[i].toEvalString();
else str += "," + this[i];
}
return "[" + (1) + "]";
};
(function(){
LispScript = {
Run : run
};
function run(code)
{
if(code instanceof Array)
{
var elements = new Array();
for (var i = 0; i < ; i++)
{
code[i] = run(code[i]); //Recursively read downward
if(code[i] instanceof Function) //Parse the expression
{
if(code[i].length <= 0)//The function without parameters can be omitted[] and called directly with the function name
{
code[i] = code[i].call(null);
}
else if(i == 0) //Calling the function with parameters [funcall,args...]
{
return code[i].apply(null, (1));
}
}
}
return code;
}
return Element(code);
};
})();
function Assert(msg, cond)
{
if(cond)
return true;
else
{
alert(msg);
throw new Error(msg);
}
};
function Element(arg)
{
if(arg == null)
return [];
else if(arg instanceof Function && <= 0)
return (null);
else
return arg;
};
__funList = new Array();
The above simple javascript code, which is only tens of lines, consists of three auxiliary functions, a body object, a constant NIL (we will know later that it represents an empty table or logical false), and a stack that stores the function name.
The LispScript static object forms the body of the LispScript parser. It has only one Run method, which parses the passed LispScript code in a downward recursive way. The type of code - I believe that careful readers have discovered it - is directly using a JavaScript array, that is, a sequence composed of "[", "]" and delimiter ",".
Using JavaScript's natural array characteristics makes our parser very simple to design - without splitting and parsing each token, so a piece of code that is as short as 50 lines of code surprisingly implements the core of the entire LispScript parser!
The functions of the three auxiliary functions are to provide parsing (toEvalString) for function iteration, detecting sequence exceptions (Assert, which is not actually used in the subsequent implementation), and parsing instruction words (Element)
Next, we define an expression. The expression is either an atom [atom], which is an alphabetical sequence (such as foo), or a list of zero or more expressions. The expressions are separated by commas and placed in a pair of brackets. The following are some expressions:
(Note: The expressions of the original Lisp syntax are separated by spaces and placed in a pair of brackets. Because it is an implementation of JavaScript, it is relatively concise to use brackets and commas)
foo
[]
[foo]
[foo,bar]
[a,b,[c],d]
The last expression is a table composed of four elements, and the third element itself is a table composed of one element.
In arithmetic expression 1 + 1 gives the value 2. The correct Lisp expression also has a value. If the expression e gives the value v, we say e returns v. Next we will define several expressions and their return values.
If an expression is a table, we call the first element an operator and the rest an argument. We will define seven original (axial) operators: quote, atom, eq, car, cdr, cons, and cond.
[quote,x] Return to x. We abbreviated [quote,x] as [_,x].
> [quote,a]
a
> [_,a]
a
> [quote,[a b c]]
[a,b,c]
quote = _ = function(args)
{
if( < 1)
return [];
else if( >= 1)
{
return arguments[0];
}
};
[atom,x] returns atom true. If the value of x is an atom or an empty table, otherwise it returns []. In Lisp, we use atom true to represent true according to convention, and use empty table to represent false.
> [atom,[_,a]]
true
> [atom,[_,[a,b,c]]]
[]
> [atom,[_,[]]]
true
atom = function(arg)
{
var tmp = (arg); //First evaluate the parameters
if(!(tmp instanceof Array) || <= 0)
return true;
else
return [];
};
Since there is an operator that needs to be evaluated for an independent variable, we can take a look at the function of quote. By quote a table, we avoid it being evaluated. An unquoted table is passed as an independent variable to an operator like atom, which will be regarded as code:
> [atom,[atom,[_,a]]]
true
On the contrary, a referenced table is only considered a table, in this example, a table with two elements:
> [atom,[_,[atom,[_,a]]]]
[]
This is consistent with how we use quotes in English. Cambridge is a town with a population of 90,000 in Massachusetts. And "Cambridge" is a word composed of 9 letters.
Quotations may seem a bit strange because very few other languages have similar concepts. It is closely related to Lisp's most distinctive feature: code and data are composed of the same data structure, and we use the quote operator to distinguish them.
[eq,x,y] returns t If the values of x and y are the same atom or are both empty tables, otherwise return [].
> [eq,[_,a],[_,a]]
true
> [eq,[_,a],[_,b]]
[]
> [eq,[_,[]],[_,[]]]
true
equal = eq = function(arg1, arg2)
{
var tmp1 = (arg1);
var tmp2 = (arg2); //First evaluate the parameters
if(!(tmp1 instanceof Array) && !(tmp2 instanceof Array) &&
() == () ||
(tmp1 instanceof Function) && (tmp2 instanceof Function) && () == () ||
(tmp1 instanceof Array) && (tmp2 instanceof Array) && ( == 0) && ( == 0))
return true;
else
return [];
};
[car,x] expects the value of x to be a table and returns the first element of x.
> [car,[_,[a b c]]]
a
car = function(arg)
{
var tmp = (arg); //First evaluate the parameters
if(tmp instanceof Array && > 0)
return tmp[0];
else
return [];
};
[cdr,x] expects the value of x to be a table and returns all elements after the first element of x.
> [cdr,[_,[a b c]]]
[b,c]
cdr = function(arg)
{
var tmp = (arg); //First evaluate the parameters
if(tmp instanceof Array && > 0)
return (1);
else
return [];
};
[cons,x,y] expects the value of y to be a table and returns a new table. Its first element is the value of x, followed by each element of the value of y.
> [cons,[_,a],[_,[b,c]]]
[a,b,c]
> [cons,[_,a],[cons,[_,b],[cons,[_,c],[_,[]]]]]
[a,b,c]
> [car,[cons,[_,a],[_,[b c]]]]
a
> [cdr,[cons,[_,a],[_,[b,c]]]]
[b,c]
cons = function(arg1, arg2)
{
var tmp1 = (arg1);
var tmp2 = (arg2); //First evaluate the parameters
if(tmp2 instanceof Array)
{
var list = new Array();
(tmp1);
return (tmp2);
}
else
return [];
};
[cond [...] …[...]] The evaluation rules are as follows. The p expressions are evaluated in sequence until one returns t. If such a p expression can be found, the corresponding e expression value is used as the return value of the entire cond expression.
> [cond,[[eq,[_,a],[_,b]],[_,first]],
[,[atom,[_,a]], [_,second]]]
second
cond = function(args)
{
for (var i = 0; i < ; i++)
{
if(arguments[i] instanceof Array)
{
var cond = (arguments[i][0]); //First evaluate the parameters
//alert(cond);
if(cond == true && arguments[i][1] != null)
return (arguments[i][1]);
}
}
return [];
};
When an expression starts with five of the seven original operators, its argument always requires a value. 2 We call such an operator a function.
Next we define a token to describe the function. The function is represented as [lambda, [...], e], where … is an atom (called a parameter), and e is an expression. If the first element of the expression is as above
[[lambda,[...],e],...]
This is called a function call. Its value is calculated as follows. Each expression is evaluated first, and then e is evaluated. During the evaluation process of e, each value that appears in e is the corresponding value in the most recent function call.
> [[lambda,['x'],[cons,'x',[_,[c]]]],[_,a]]
[a,c]
> [[lambda,['x','y'],[cons,'x',[cdr,'y']]],[_,z],[_,[a,b,c]]]
[z,b,c]
lambda = function(args, code)
{
if(code instanceof Array)
{
var fun = new Function(args,
"for(var i = 0; i < ; i++) arguments[i] = (arguments[i]);return ("+()+");");
var globalFuncName = __funList.pop();
fun._funName = globalFuncName;
if(globalFuncName != null)
self[globalFuncName] = fun;
return fun;
}
return [];
};
If the first element of an expression f is an atom and f is not the original operator
[f ...]
And the value of f is a function [lambda,[...]], then the value of the above expression is
[[lambda,[...],e],...]
The value of . In other words, parameters can be used not only as independent variables but also as operators in expressions:
> [[lambda,[f],[f,[_,[b,c]]],[_,[lambda,[x],[cons,[_,a],x]]]
[a,b,c]
There is another function token that allows the function to mention itself, so that we can easily define recursive functions. Tokens
[label,f,[lambda,[...],e]]
Represents a function like [lambda,[...],e], plus the following characteristics: Any f that appears in e will be evaluated as this label expression, as if f is a parameter of this function.
Suppose we want to define the function [subst, x, y, z], which takes the expression x, atom y and table z as parameters, and returns a table like z, but the y that appears in z (at any nesting level) is replaced by x.
> [subst,[_,m],[_,b],[_,[a,b,[a,b,c],d]]]
[a,m,[a,m,c],d]
"Extreme Beauty" does not mean Yue'er's article, because I am not so arrogant yet:P, it describes the beautiful form of combining Lisp and JavaScript.
Originally, the following content was to be released on Wuyou, but unfortunately, I suddenly found Wuyou "bombed" on the day of completing the article. It was not restored until last weekend. Since I couldn't wait that long, I put it on Yue'er's blog on CSDN first.
As the title describes, the following is about the skills of implementing Lisp-like languages in JavaScript. However, the focus is not on how to implement a programming language, but on demonstrating the simplicity and flexibility of JavaScript and the beauty of Lisp through thinking and implementation processes.
Perhaps not many people come into contact with Lisp here, so many people will definitely be surprised by the following content or form. If you have never been exposed to it at all, don't be too surprised. Lisp is indeed different from all programming languages you have seen before, because, uh, it is Lisp, a unique Lisp, a wonderful idea of elegant, concise, complete, independent. Maybe you will find it difficult to understand, but once you understand, you will like it.
Okay, let’s start our LispScript journey~
Recently, I accidentally saw an article online saying that javascript = C+Lisp, so I thought about this question. Since javascript contains some of the blood of Lisp, what would it look like to use javascript to implement an artificial intelligence script similar to Lisp?
As a "functional" language family, the LISt Processing language family has conquered many researchers and enthusiasts with its simple and beautiful style and simple and efficient structure since its birth.
At present, this ancient language and grammar is still used and loved by many people, and plays a very huge role in fields such as artificial intelligence.
I think that the flexibility of javascript and the simplicity of Lisp should be able to create a very beautiful language, but what does this language look like? I believe everyone wants to know too, so let’s study this very attractive issue together.
(Before reading the following content carefully, it is recommended that you pour a cup of hot tea first, sit down and calm your mood, take a deep breath, and concentrate, because the following process will be interesting and brain-consuming...^^)
Before entering the Lisp Kingdom, let's do some preparations for javascript... Please read the following code carefully
NIL = [];
= function()
{
if( <= 0) return "NIL";
var str = "";
for (var i = 0; i < ; i++)
{
if(this[i] instanceof Array)
str += "," + this[i].toEvalString();
else str += "," + this[i];
}
return "[" + (1) + "]";
};
(function(){
LispScript = {
Run : run
};
function run(code)
{
if(code instanceof Array)
{
var elements = new Array();
for (var i = 0; i < ; i++)
{
code[i] = run(code[i]); //Recursively read downward
if(code[i] instanceof Function) //Parse the expression
{
if(code[i].length <= 0)//The function without parameters can be omitted[] and called directly with the function name
{
code[i] = code[i].call(null);
}
else if(i == 0) //Calling the function with parameters [funcall,args...]
{
return code[i].apply(null, (1));
}
}
}
return code;
}
return Element(code);
};
})();
function Assert(msg, cond)
{
if(cond)
return true;
else
{
alert(msg);
throw new Error(msg);
}
};
function Element(arg)
{
if(arg == null)
return [];
else if(arg instanceof Function && <= 0)
return (null);
else
return arg;
};
__funList = new Array();
The above simple javascript code, which is only tens of lines, consists of three auxiliary functions, a body object, a constant NIL (we will know later that it represents an empty table or logical false), and a stack that stores the function name.
The LispScript static object forms the body of the LispScript parser. It has only one Run method, which parses the passed LispScript code in a downward recursive way. The type of code - I believe that careful readers have discovered it - is directly using a JavaScript array, that is, a sequence composed of "[", "]" and delimiter ",".
Using JavaScript's natural array characteristics makes our parser very simple to design - without splitting and parsing each token, so a piece of code that is as short as 50 lines of code surprisingly implements the core of the entire LispScript parser!
The functions of the three auxiliary functions are to provide parsing (toEvalString) for function iteration, detecting sequence exceptions (Assert, which is not actually used in the subsequent implementation), and parsing instruction words (Element)
Next, we define an expression. The expression is either an atom [atom], which is an alphabetical sequence (such as foo), or a list of zero or more expressions. The expressions are separated by commas and placed in a pair of brackets. The following are some expressions:
(Note: The expressions of the original Lisp syntax are separated by spaces and placed in a pair of brackets. Because it is an implementation of JavaScript, it is relatively concise to use brackets and commas)
foo
[]
[foo]
[foo,bar]
[a,b,[c],d]
The last expression is a table composed of four elements, and the third element itself is a table composed of one element.
In arithmetic expression 1 + 1 gives the value 2. The correct Lisp expression also has a value. If the expression e gives the value v, we say e returns v. Next we will define several expressions and their return values.
If an expression is a table, we call the first element an operator and the rest an argument. We will define seven original (axial) operators: quote, atom, eq, car, cdr, cons, and cond.
[quote,x] Return to x. We abbreviated [quote,x] as [_,x].
> [quote,a]
a
> [_,a]
a
> [quote,[a b c]]
[a,b,c]
quote = _ = function(args)
{
if( < 1)
return [];
else if( >= 1)
{
return arguments[0];
}
};
[atom,x] returns atom true. If the value of x is an atom or an empty table, otherwise it returns []. In Lisp, we use atom true to represent true according to convention, and use empty table to represent false.
> [atom,[_,a]]
true
> [atom,[_,[a,b,c]]]
[]
> [atom,[_,[]]]
true
atom = function(arg)
{
var tmp = (arg); //First evaluate the parameters
if(!(tmp instanceof Array) || <= 0)
return true;
else
return [];
};
Since there is an operator that needs to be evaluated for an independent variable, we can take a look at the function of quote. By quote a table, we avoid it being evaluated. An unquoted table is passed as an independent variable to an operator like atom, which will be regarded as code:
> [atom,[atom,[_,a]]]
true
On the contrary, a referenced table is only considered a table, in this example, a table with two elements:
> [atom,[_,[atom,[_,a]]]]
[]
This is consistent with how we use quotes in English. Cambridge is a town with a population of 90,000 in Massachusetts. And "Cambridge" is a word composed of 9 letters.
Quotations may seem a bit strange because very few other languages have similar concepts. It is closely related to Lisp's most distinctive feature: code and data are composed of the same data structure, and we use the quote operator to distinguish them.
[eq,x,y] returns t If the values of x and y are the same atom or are both empty tables, otherwise return [].
> [eq,[_,a],[_,a]]
true
> [eq,[_,a],[_,b]]
[]
> [eq,[_,[]],[_,[]]]
true
equal = eq = function(arg1, arg2)
{
var tmp1 = (arg1);
var tmp2 = (arg2); //First evaluate the parameters
if(!(tmp1 instanceof Array) && !(tmp2 instanceof Array) &&
() == () ||
(tmp1 instanceof Function) && (tmp2 instanceof Function) && () == () ||
(tmp1 instanceof Array) && (tmp2 instanceof Array) && ( == 0) && ( == 0))
return true;
else
return [];
};
[car,x] expects the value of x to be a table and returns the first element of x.
> [car,[_,[a b c]]]
a
car = function(arg)
{
var tmp = (arg); //First evaluate the parameters
if(tmp instanceof Array && > 0)
return tmp[0];
else
return [];
};
[cdr,x] expects the value of x to be a table and returns all elements after the first element of x.
> [cdr,[_,[a b c]]]
[b,c]
cdr = function(arg)
{
var tmp = (arg); //First evaluate the parameters
if(tmp instanceof Array && > 0)
return (1);
else
return [];
};
[cons,x,y] expects the value of y to be a table and returns a new table. Its first element is the value of x, followed by each element of the value of y.
> [cons,[_,a],[_,[b,c]]]
[a,b,c]
> [cons,[_,a],[cons,[_,b],[cons,[_,c],[_,[]]]]]
[a,b,c]
> [car,[cons,[_,a],[_,[b c]]]]
a
> [cdr,[cons,[_,a],[_,[b,c]]]]
[b,c]
cons = function(arg1, arg2)
{
var tmp1 = (arg1);
var tmp2 = (arg2); //First evaluate the parameters
if(tmp2 instanceof Array)
{
var list = new Array();
(tmp1);
return (tmp2);
}
else
return [];
};
[cond [...] …[...]] The evaluation rules are as follows. The p expressions are evaluated in sequence until one returns t. If such a p expression can be found, the corresponding e expression value is used as the return value of the entire cond expression.
> [cond,[[eq,[_,a],[_,b]],[_,first]],
[,[atom,[_,a]], [_,second]]]
second
cond = function(args)
{
for (var i = 0; i < ; i++)
{
if(arguments[i] instanceof Array)
{
var cond = (arguments[i][0]); //First evaluate the parameters
//alert(cond);
if(cond == true && arguments[i][1] != null)
return (arguments[i][1]);
}
}
return [];
};
When an expression starts with five of the seven original operators, its argument always requires a value. 2 We call such an operator a function.
Next we define a token to describe the function. The function is represented as [lambda, [...], e], where … is an atom (called a parameter), and e is an expression. If the first element of the expression is as above
[[lambda,[...],e],...]
This is called a function call. Its value is calculated as follows. Each expression is evaluated first, and then e is evaluated. During the evaluation process of e, each value that appears in e is the corresponding value in the most recent function call.
> [[lambda,['x'],[cons,'x',[_,[c]]]],[_,a]]
[a,c]
> [[lambda,['x','y'],[cons,'x',[cdr,'y']]],[_,z],[_,[a,b,c]]]
[z,b,c]
lambda = function(args, code)
{
if(code instanceof Array)
{
var fun = new Function(args,
"for(var i = 0; i < ; i++) arguments[i] = (arguments[i]);return ("+()+");");
var globalFuncName = __funList.pop();
fun._funName = globalFuncName;
if(globalFuncName != null)
self[globalFuncName] = fun;
return fun;
}
return [];
};
If the first element of an expression f is an atom and f is not the original operator
[f ...]
And the value of f is a function [lambda,[...]], then the value of the above expression is
[[lambda,[...],e],...]
The value of . In other words, parameters can be used not only as independent variables but also as operators in expressions:
> [[lambda,[f],[f,[_,[b,c]]],[_,[lambda,[x],[cons,[_,a],x]]]
[a,b,c]
There is another function token that allows the function to mention itself, so that we can easily define recursive functions. Tokens
[label,f,[lambda,[...],e]]
Represents a function like [lambda,[...],e], plus the following characteristics: Any f that appears in e will be evaluated as this label expression, as if f is a parameter of this function.
Suppose we want to define the function [subst, x, y, z], which takes the expression x, atom y and table z as parameters, and returns a table like z, but the y that appears in z (at any nesting level) is replaced by x.
> [subst,[_,m],[_,b],[_,[a,b,[a,b,c],d]]]
[a,m,[a,m,c],d]
123456Next pageRead the full text