/WalleyLanguage

a simple lisp dialect written in c

Primary LanguageC

Walley Language

Copyright (c) 2012-2014 Yiyi Wang (shd101wyy)
All Rights Reserved

Language Version: 0.3.8499

This language is not finished yet...

Walley Language (Beta Version 0.3) is a simple lisp dialect written in C. Both Compiler and Virtual Machine are implemented in C. This Toy Language is still under development, lots of bugs exist, so please don't use it for production. And this Readme mainly aims to teach you how to use walley language from the start. Not finished yet...

Installation:

under .nix (eg Linux,Mac OS X)
open terminal

cd [walley-language project folder that u download, where Makefile is there]
sudo make
sudo make install

Windows is not currently supported (T_T)

Uninstallation:

under .nix (eg Linux, Mac OS X)
open terminal

cd [walley-language project folder that u download, where Makefile is there]  
sudo make uninstall

Compile to JavaScript using Emscripten

You need to install Emscripten first 

cd [walley-language project folder that u download, where Makefile is there]
make emscripten

after running the command above
you will get a file called walley.js (I already compiled one for you using emscripten 1.25.0)
this file will contain a JavaScript object called
walley
below is an example of how to use walley.js

/*
  the Object "walley" will contain two functions:
    init: initialize walley language
    runStr: run a give string: compile it and run it on vm, return the result.
*/
walley.init();
walley.runStr("(def x 12)")  // x => 12
walley.runStr("(+ x 4)")     // 16

To try Walley Language online, go to

Mysterious S Expression (#_#)

Walley Language, like all lisp dialects, uses S expression. Therefore, its syntax is extremely simple.

Here are some questions below, just compare ur answers with the solutions later.

  • (+ 3 4)
  • (- 3 4)
  • (* 3 4)
  • (+ 3 4 5)

Here are solutions for the questions above:

  • 7 ; from 3 + 4
  • -1 ; from 3 - 4
  • 12 ; from 3 * 4
  • 12 ; from 3 + 4 + 5

if you understand the solutions above, you have understood S expression:
S expression is in format of (func-name, arg1, arg2) its head is a function, with several parameters behind for example, in S exp (+ 3 4), + is the function, and 3, 4 are parameters.
so (+ 3 4) runs + function with 3 4 as parameters, which produces 7 as result and here are lots of builtin functions in walley language
we call those functions => lambda (can also be written as fn)

Hello World

print is a lambda, which can print out its parameter.
for example

 (print "Hello World")

will print out

  Hello World

How to run your program

now u already know how the print lambda works, but how do we run it in walley language?

after installation, open ur terminal,
type

walley

then you will see something like

Walley Language 0.3.8465
Copyright (c) 2012-2014 Yiyi Wang
All Rights Reserved

walley>

This is Walley Language repl environment,
try to type (print "Hello World") after walley> and then press "enter"

walley > (print "Hello World")

you will see the string Hello World print out.
also, try to type something like (+ 3 4), (- 3 4 5) (* 1 2 3) to see what u can get

Define Your Own Lambda

now we already know how to use S expression to run a lambda.
Sometimes, we want to define our own lambda, like

   (@@my-awesome-lambda@@ 3 4),

and how do we do that?
First, let's do something simple,
Guess the answer of the following S expression:

((lambda (a b) (+ a b)) 3 4)

the solution is 7, here we defined an anonymous lambda:

(lambda (a b) (+ a b))

and we then passed 3 4 as parameters to it

((lambda (a b) (+ a b)) 3 4)

which produced the answer 7.
Now try to guess the answer of the following S expression:

((lambda (a b) (+ a b)) 5 6)
((lambda (a b) (+ a b)) 1 2)
((lambda (a b) (- a b)) 3 4)
((lambda (a b c) (+ a b c)) 1 2 3)

the solutions are:

  • 11
  • 3
  • 7
  • 6

However, it is so inconvenient to run lambda like that ((lamda (a b ...

So how do we give the lambda a name,
like

(my-lambda 3 4)  ;; which evaluates (+ 3 4) and produces 7 as result?

here we need to define a variable as lambda:
and below is how we do that

(def my-lambda (lambda (a b) (+ a b)))

and call it like

(my-lambda 3 4)

since

my-lambda <=> (lambda (a b) (+ a b))

when evaluating (my-lambda 3 4), we just replace my-lambda with

(lambda (a b) (+ a b))

, which is

((lambda (a b) (+ a b)) 3 4)

  • After version 0.3.8, we can also define function like this:

    (def my-lambda (a b) (+ a b))

  • If you still can't understand what's going on,
    think about the function in math like:
    f(x) = x+1 and
    f(3) = 4
    to define such a math function, we can write it in walley like:

     (def f(x) (+ x 1))   ;; we defined function f
 (f 3)                ;; => give us 3 + 1 = 4
 (f 5)                ;; => give us 5 + 1 = 6

Now, we don't need to write that long lambda as head anymore. ;)
Try to define ur own lambda in walley repl, and run it!.

More about defining a variable

we just learnt how to bind a lambda to a variable called my-lambda In fact, in walley language, you can also bind any other values to a variable. for example

(def a 12)
(print a)

will print out a's value, which is 12

(def b (+ 3 4))
(print b)

will print out b's value, which is 7

However, when we try to run the following code, one error will occur

(def x 12)
(def x 30)

In Walley Language, we can only define a variable once.
Since we already defined a variable called x
we cannot define it again
So what should we do if we want to change the value of x

Change me!!!

just like def, a magical "lambda" that we used to define a variable,
we can use another magical "lambda", set!, to change the original value of a variable. see the following code:

(def x 12)
(set! x (+ 4 5))

We first defined a variable called x with value 12.
then we changed it value to 9 And that's all ;)

Other than lambda and number???

Now, we learnt how to bind a lambda or number to a variable.
Furthermore, walley language supports lot's of data types.

we can bind a string to a variable like

(def x "Hello World")
(print x) ; this will print out Hello World

however, I am too lazy to type "" all the time, so I "choose" to use '(single quote) to help me reduce the "workload"

to define a string like "hi", we can do

(def x 'hi)  ;; instead of (def x "hi")

here, we use only one single quote to quote a string.
Now we don't need to use "" anymore.
Wait, we still need to use "" sometimes. When here is space in the string, we cannot use '. eg "Hello World" is correct, but 'Hello World is wrong.
in this case, we can only use ""

What's more.

Now, I am gonna introduce u guys a new data type. pair First, can u tell me the answer of the S exp

(+ 3 4)

If u answer 7, then u are correct. Now try to answer the answer of the S exp

'(+ 3 4)

If ur answer is still 7, then sorry, u are wrong.
The answer of '(+ 3 4) is still (+ 3 4).
Notice that We put a single quote ' before the parentheses (, thus this S expression is not evaluated. The single quote is an abbreviation of lambda quote.
so

'(+ 3 4)
(quote (+ 3 4))

are the same, they both stopped the evaluation of the S expression (+ 3 4).

Now try to run the following code in walley repl and see that u can get

(def x '(x 4 5))
(print x)

Quote?

Pair, like lambda and number and string, is a builtin data type in walley language.
the code below

(def x '(x 4 5))
(print x)

will print out

(x 4 5)

as result. the value of x is a pair.

Do u still remember the single quote string that we talked about before?

(def x 'hi)
(print x)

it is actually the same as

(def x (quote hi))
(print x)

the quote lambda stopped the evaluation of the variable hi. Now consider the following code, which doesn't use quote lambda.

(def hi 12)
(def x hi)
(print x)

will print out the value 12. In this case, without quote variable hi is evaluated, which gives variable x the value 12.

Quote is a very import lambda, which can stop the evaluation of a variable. And we will see more applications about it in the future.

More about Pair

So far, we have learnt just a little about the data type pair . I know u want to know more about it ;)
Now, I will talk more about it.

NOW Introducing two new lambdas.
car , cdr

  • car : give u the first element of the pair
  • cdr : give the rest elements(except for the first element) of the pair

for example

(def x '(a b c))
(def y (car x))
(print y)

will print out string a . here (car x) gets the first element of the pair x,
which is the string a

another example

(def x '(a b c))
(def y (cdr x))
(print y)

will print output pair (b c) .
here (cdr x) gives us the rest elements of the pair x, which is the pair (b c) .

with lambdas car and cdr , we can get the elements from a pair easily.
We can also define some interesting lambdas using those two lambdas.
for example.

(def cadr (a)         ;; give us the 2nd element of pair
    (car (cdr a)))
(def caddr (a)        ;; give us the 3rd element of pair
    (car (cdr (cdr a))))
(def cddr (a)         ;; give us the rest rest elements of pair
    (cdr (cdr a)))

now try to define a variable x with pair value
(1 2 3 4 5 6).
and try to think about the answer of the following S expressions:

(car x)
(cadr x)
(caddr x)
(cddr x)

PS: run it later in walley repl to check ur answers. cadr caddr cddr are already defined, so u don't need to define them again.

Make Pair in other ways

We learnt how to use the quote to stop the evaluation of the S expression and get pair or string as result.
In Walley Language, there are also other ways to make a pair. The first new lambda that I will introduce to u is List.
Consider the following code:

(List 'a 'b 'c)

this code will give use the pair (a b c).
In contrast to quote, List will evaluate all of its parameters and connect them to generate a list(pair)
So the following code:

(def x 12)
(List x 'x)

will generate pair (12 x)
where

  • the first param x generates number 12
  • the second param 'x generates string x

The second new lambda that I will introduce to u
is cons.
Consider the following code:

(cons 'a ())

will produce the pair (a) .
We can conside it as we connect string a to an empty pair ()

So how about:

(cons 'a 'b)

this code will produce the pair (a . b) .
Before we discussion this result,
U might think why it is not (a b) ,
because to get (a b) , we need to use the empty pair () as the tail.
So in order to get (a b), we need to run the following code:

(cons 'a (cons 'b ()))

Now let's go back to (a . b) .
the . between a and b
means that we connect a with b directly,
and here is no empty pair () in the end.

thus

(def x (cons 'a 'b)) ;; x => (a . b)
(car x)              ;;   => a
(cdr x)              ;;   => b

while

(def x (cons 'a (cons 'b ()))) ;; x => (a b), the same as (a . (b . ()))
(car x)                        ;;   => a
(cdr x)                        ;;   => (b)
(car (cdr x))                  ;;   => b
(cdr (cdr x))                  ;;   => ()

This part is quite hard.
If u still have problem, I recommend u to read http://en.wikipedia.org/wiki/Cons
to see more about cons and how it works.

The "empty pair" and If

From the last part, we learnt a kind of empty pair written as ()
In Walley Language, () is considered as another data type:
null
So it is actually not a kind of pair.
We use () to construct pair, and we can also use it in the new lambda if . If you have ever programmed in C, then u understand the following code

if(1){
    printf("do-if"); // this will be print out
}
else{
    printf("do-else"); // this won't
}

and

if(0){
    printf("do-if:); // this won't be print out
}
else{
    printf("do-else"); // this will be print out
}

This if in Walley Language is quite similar.
we use (if test do-if do-else).
In C we check whether test is 0 to decide the branch.
In Walley Language, we check whether test is () to decide the branch. For example

(if 1 (print "do-if") (print "do-else"))  ;; print do-if
(if () (print "do-if") (print "do-else")) ;; print do-else

That's it, very easy ;)

Sometimes, we want to run more than one S expression in do-if and do-else.
To do this, we need to use a new lambda called begin. (begin S-exp1 S-exp2 ...)
For Instance

(if 1
    (begin (print "do-if1")
           (print "do-if2"))  ;; will print do-if1do-if2
    (print "do-else")) ;; wont print out

The better use of If

From the last topic, we learnt how to use if.

we put value to test and then decide whether we should run
do-if or do-else.
For the most times, we don't want to pass () or any other value directly to test
For the most times, we want to pass the result of comparision to test.

Now, I will introduce a new lambda called eq?.
this lambda will compare two objects, if they are equal, string true will be returned, otherwise () will be returned. we can also use this to compare two numbers.

Here are some examples:

(eq? 3 3)      ;; true
(eq? 3 4)      ;; ()
(eq? 'a 'a)    ;; true
(eq? 'a 'c)    ;; ()
(eq? () ())    ;; true
(def x '(1 2))
(def y x)
(eq? x y)      ;; true.  x and y point to the same object, same memory locations.
(def z '(1 2))
(eq? x z)      ;; (). although x and z are both (1 2), the are actually two different objects. those two objects are at two different memory locations

so now we could define a lambda like:

(def null? (n)
    (if (eq? n ())
        'true
        ()))

to check whether a value is ().

(null? ())        ;; true
(null? 2)         ;; ()
(null? (eq? 2 2)) ;; ()
(null? (eq? 2 3)) ;; true

Walley Language also offeres many other lambdas for comparision use.
= > < >= <= can be used to compare numbers.
string=? string>? string<? string>=? string<=? can be used to compare strings.

Attention: error might occur if u passed wrong type params.

Cond, another kind of If

Now we have learnt how to use if in walley language.
In fact, here is another "lambda" that works in a similar way.
It is called as cond .

;; cond is in format of
(cond test1 do-cond1
      test2 do-cond2
      ...
      else  do-else)

So let's try to write a lambda that gets the absolute value of a number.

(def abs0 (n)
    (cond (= n 0) 0          ;; n equals 0
          (> n 0) n          ;; n is positive
          (< n 0) (- 0 n)))  ;; n is negative

;; or a much simpler way
(def abs1 (n)
    (cond (> n 0) n            ;; n is positive
          else    (- 0 n)))    ;; else: n is not positive
                               ;; if none of the exprs above else are run
                               ;; else will be evaluated.
;; or just use if
(def abs2 (n)
    (if (> n 0)
        n
        (- 0 n)))

That's all for cond ;).

A new data type: Table

Table is a data type in walley language.
It is a kind of hash table, which uses string as keyword.
To define an empty table, we can write:

(def my-table {})

To add key/value pair to table:

(set! my-table:x 12)      ;; now the table is like {:x 12}
(set! my-table:y 15)      ;; now the table is like {:x 12, :y 15}
(set! my-table:add (fn (a b) (+ a b))) ;;      {:y 15, :add #<user-defined-lambda (_ _)>, :x 12}

To access a value according to keyword:

my-table:x      ;; => 12
(print my-table:x)  ;; will print 12
my-table:y      ;; => 15
(my-table:add 3 4)  ;; => 7
(my-table:add my-table:x my-table:y) ;; => 27

current functions related to table:

  • keys
  • foreach
  • length
  • delete

Variable table is a table that contains above functions. To get keys in a table:

(table:keys my-table) ;; => return list '(y add x)

To get length of a table:

(table:length my-table) ;; => return 3

To delete a value from table according to keyword:

(table:delete! my-table 'x) ;; remove its value. if delete value successfully, return true, otherwise return ()

To check a value is a table:

(table? my-table)  ;; => true

To iterate a table:

(def a-table {:a 1 :b 2 :c 3}) ;; define a table
(table:foreach a-table (fn (key val)
                          (print key " " val "\n")))
                          ;; the code above will print
                          ;; c 3
                          ;; b 2
                          ;; a 1

More about: List

In walley language, we can use List function to build a list.

(def x (List 1 2 3)) ;; <=> same as (def x (cons 1 (cons 2 (cons '()))))

And here are several builtin functions related to list:

  • ref
  • foreach
  • zip
  • length
  • slice
  • filter
  • map
  • assoc
  • reverse
  • ->vector
  • append

All those functions are in a table called list

  • ref
(def x '(1 2 3))
(list:ref x 1)   ;; => give us the 2nd element => 2
  • foreach
(def x '(1 2 3))
(list:foreach x (fn (i) (print i))) ;; will print 1 2 3
  • zip
(list:zip '(1 2 3) '(4 5 6)) ;; => ((1 4) (2 5) (3 6))
  • length
(list:length '(1 2 3)) ;; => return the length of list: 3
  • slice
(list:slice '(1 2 3 4 5) 2)   ;; => slice starting from offset 2 :  (3 4 5)  
(list:slice '(1 2 3 4 5) 2 4) ;; => slice starting from offset 2 to 4:  (3 4)
  • filter
(list:filter (fn (x) (> x 0)) '(-1 -2 -3 4 6 -7 8)) ;; get list with all elements greater than 0 : (4 6 8)
  • map
(list:map (fn (x) (* x x)) '(1 2 3)) ;; map the list : (1 4 9)
  • assoc
(list:assoc '((a . 12) (b . 14)) 'a) ;; => 12
  • reverse
(list:reverse '(1 2 3 4 5 6)) ;; reverse the list => (6 5 4 3 2 1)
  • ->vector
(list:->vector '(1 2 3)) ;; convert list to vector #[1 2 3]
  • append
(list:append '(1 2 3) 4) ;; append element at end =>  (1 2 3 4)
(list:append '(1 2 3) '(4 5)) ;; => (1 2 3 4 5)

Data Type: Vector

Vector is a data type in walley language.
Vector grants us O(1) element access time.

;; to create a vector
(def x [1 2 3 4])

;; to access element at offset
x[0]           ;; get first element of vector => 1
(+ x[0] x[1])  ;; add first two elements

;; set element at offset
(x 0 12)      ;; x is now => [12 2 3 4]

There are several builtin functions in table vector

  • ->list

  • filter

  • map

  • zip

  • length

  • foreach

  • slice

  • find

  • push!

  • pop!

  • ->list

(vector:->list [1 2 3]) ;; convert vector to list => (1 2 3)
  • filter
(vector:filter (fn (x) (> x 0)) [1 -2 3 -4 5]) ;; same like list:filter, but take vector as parameter and return a vector => [1 3 5]
  • map
(vector:map (fn (x) (* x 2)) [1 2 3]) ;; => [1 4 6]
  • zip
(vector:zip [1 2 3] [4 5 6]) ;; => [[1 4] [2 5] [3 6]]
  • length
(vector:length [1 2 3]) ;; length of vector =>3
  • foreach
(vector:foreach [3 4 5] (fn (value offset) (print offset " : " value "\n")))
;; iterate over vector
;; print
;; ===========
;; 0 : 3
;; 1 : 4
;; 2 : 5

  • slice
    Same as list:slice, but return a vector

  • find

(vector:find [1 2 3 4] 3) ;; find value 3 and return its offset => 2
(vector:find [1 2 3] 4) ;; if value not found, return -1 => -1
(vector:find [1 2 3 4 5] 1 2) ;; search 1 starting from offset 2 => -1
  • push!
(def x [1])
(vector:push! x 2)  ;; x now is => [1 2]
  • pop!
(def x [1])
(vector:pop! x)  ;; x now is => [], return value 1

Prototype Based Object Oriented Programming

walley language implements prototype based oop like
Io

Let's start with some examples.

Object is a special data type.
we will build other objects based on Object.
so what is Object.

(print Object) ;; => {:clone #<user-defined-lambda (_)>, :type Object}

Object is a special Table that has two properties:

  • clone
  • type
    To access the key/value from an object is the same as referring key/value from an table:
(print Object:type)  ;; => Object
(print Object:clone) ;; => #<user-defined-lambda (_)>

Now we can define a new object based on Object.
Suppose we want to define a small dog object:

(def a-small-dog (Object:clone))     ;; so now we create a new object called a-small-dog based on Object
(print a-small-dog:type)             ;; => Object
(print a-small-dog)                  ;; => {}

;; to get the proto of an object, use "proto" function
(proto a-small-dog)                  ;; will re

;; the proto of a-small-dog is Object
;; so the code below will return 'true
(eq? (proto a-small-dog) Object)     ;; => true

;; to add property to an Object is the same as Table
(set! a-small-dog:x 12)              ;; => {:x 12}  
(set! a-small-dog:y 15)              ;; => {:y 15, :x 12}
(set! a-small-dog:type 'A-Small-Dog)           ;; => {:type A-Small-Dog, :y 15, :x 12}  

;; so now a-small-dog:type will give us string "A-Small-Dog" instead of "Object" because
;; this time we overwrite property "type":
(print a-small-dog:type)                       ;; => A-Small-Dog  

;; the structure of a-small-dog is virtually like:
;; {:clone #<user-defined-lambda (_)>, :type Object}    Object
;; {:type A-Small-Dog, :y 15, :x 12}                    a-small-dog
;; the prototype of a-small-dog is Object

;; now we set "age" of that a-small-dog
(set! a-small-dog:age 5)            ;; => { :age 5, :type A-Small-Dog, :y 15, :x 12 }

;; to define an object method, we need to add an extra argument to function, which is called "self".
;; for example, we want to declare a fn that can print the age of a-small-dog:
(set! a-small-dog:print-age (lambda (self) (print self:age)))

;; to call an object method.
(a-small-dog:print-age)      ;; => 5
;; when we call this function, we will pass a-small-dog as the first argument to print-age since a-small-dog is an object and this function is an object method
;; so now self <=> a-small-dog
;; and    (print self:age) <=> (print a-small-dog:age)  which print 5

;; consider the following code:
(def another-small-dog (a-small-dog:clone)) ;; another-small-dog is a new object created based on a-small-dog
(set! another-small-dog:age 4)              ;; {:age 4}
(eq? a-small-dog (proto another-small-dog)) ;; true, as the prototype of another-small-dog is a-small-dog
(another-small-dog:print-age)               ;; will print 5

Multi-Method

to support polymorphism

eg:

(def poly (multi (fn (x) (typeof x))))

;; if (typeof x) matches 'string, return "This is String"
(defmethod poly 'string (fn (x) "This is String"))

;; if (typeof x) matches 'vector, return "This is Vector"
(defmethod poly 'vector (fn (x) "This is Vector"))

;; if (typeof x) matches 'table, return "This is Table"
(defmethod poly 'table (fn (x) "This is Table"))

(poly "Hello ") ;; => "This is String"
(poly {:a 12 }) ;; => "This is Table"

I am Lazy

Because I am too lazy to type "lambda" each time, now lambda can also be defined using "fn"
The following two lines of codes are the same:

(def add (fn (a b) (+ a b)))
(def add (lambda (a b) (+ a b)))

Also we can define fn in this way:

(def add (fn (a b) (+ a b)))
;; same as  
(def add (a b) (+ a b))

(#_#)

Module Management

  • file1.wa
(def x 12)                  ;; define x
(def y 20)                  ;; define y
(def add (a b) (+ a b))     ;; define add
{:x 12 :add add}            ;; export that value
  • file2.wa
(def file1-module (require 'file1)) ;; load file1
(print file1-module)                ;; => {:add #<user-defined-lambda (_ _)>, :x 12}
(file1-module:add file-module:x 4)  ;; => 16
The same module will only be loaded once.

Eval Lisp in Lisp

So far, we have learnt several lambdas

  • car
  • cdr
  • cond
  • quote
  • lambda
  • eq?
  • cons
  • string? which can help check whether the parameter is string and so forth.

Now I will teach u how to build a very simple lisp interpreter in walley language.

To be continued

License

MIT

Free Software, Hell Yeah!

Thanks

Change Log

  • 2015/1/2
    Version 0.3.8499
    I feel it is too hard to implement call/cc.
    And I just learnt that parallelism and concurrency are different.
    Fixed some memory leak of the program.

  • 2014/12/29
    Try to support call/cc function
    and continuation data type
    But there is potential memory leak.
    Continuation implementation not finished yet.
    eg:

        (def return 0)
    (+ 1 (call/cc
            (fn (k)
                (set! return k) ; save continuation
                (+ 2 (k 3)))))
    ;; => 4

    (return 4) ;; => 5 .  resume continuation.

  • 2014/12/29 Idea
    For asynchronization, I was thinking about something like

        (def result
        (let async-0 (future (my-func param0 param1)
             async-1 (future (my-func param2 param3)))
             [async-0 async-1]))

    where param of future function will run asynchronously.
    in this case:

            (my-func param0 param1)  
        (my-func param1 param2)

    will run at the same time.
    and under my-func, all non-local variables (here non-local means all variables defined not inside my-func) are not allowed to change.
    Lower Level frame cannot modify Higher Level frame and

            [async-0 async-1]

    will join the running result.

Attention

Some terms that I used in this tutorial are actually wrong, I use them just to offer a better explanation for the tutorial.(eg, "if" is actually not lambda)

;; 下面的这段代码是我在微博上看到的
;; 感觉很有意思，所哟我用 walley language 伪代码重写。

(def a-life (Life:clone))
(while (eq? (a-life:get-state) 'alive)
    (print "I have a new Plan!")
    (let a-plan (Plan:clone)
        (while (not (a-plan:succeed))
            (a-plan:struggle)
            (if (eq? 'fail (a-plan:get-state))
                (print "Come on!")))
        (print "What A Beautiful Day!")))
(print "No Regrets.")


生命是一段漫长的旅程。
想了，就去做。
输了，从头再来。
摔了，爬起来继续。
赢了，还要再往前走。
死了，没留下任何遗憾。