Day 4 -- JavaScript in a week

previous post <-> next post

I accidentally started playing SimCity3000 and it ate big amount of my time..

return

https://github.com/ujihisa/jinaw/commit/2dbc9ed0b3240d9081932c5a519a9767a3763ee4

return is the only one feature to cancel executing the rest of statements, since there's no try/catch exception handling in this subset. Since the run- function to sequentially execute statements isn't something like a loop but an explicit recursion, to implement return, just simply don't recur.

(run '[(var f (function []
                        [(fcall 'console.log [1])
                         (return 9)
                         (fcall 'console.log [2])]))
       (fcall 'console.log [(fcall 'f [])])])

This outputs 1 and 9 but not 2.

typeof

https://github.com/ujihisa/jinaw/commit/c499b1bc23a11799ffe119d8a974729c6936c4ad

JavaScript has a unary operator typeof to tell the type of a value/variable-name.

> typeof 1
"number"
> var x = 1
> typeof x
"number"
> typeof y
"undefined"

Since typeof isn't a function it has more power than functions; it also accepts undefined variables without throwing ReferenceError.

(run '[(fcall 'console.log [(typeof 1)]);=> "number"
       (var x 1)
       (fcall 'console.log [(typeof x)]);=> "number"
       (fcall 'console.log [(typeof y)]);=> "undefined"
       (fcall 'console.log [(typeof (fcall '+ ['x 2]))])]);=> "number"

==

== is one of the most difficult aspect of JavaScript. The behavior is too tricky to understand.

> 1 == ['1']
true
> [] == []
false
> [] == ''
true
> 1 == true
true
> 1 == 'true'
false
> '1' == true
true

According to specification, the definition of == is

If the two operands are not of the same type, JavaScript converts the operands then applies strict comparison. If either operand is a number or a boolean, the operands are converted to numbers if possible; else if either operand is a string, the other operand is converted to a string if possible. If both operands are objects, then JavaScript compares internal references which are equal when operands refer to the same object in memory.

Well, I couldn't clearly understand it. What if one operand is a number and the other is a boolean? What is an operand is a number but the other operand isn't possible to be converted? They aren't written.

I gave up and made one that works fine for now..

(run '[(fcall 'console.log [(fcall '== [1 1])]);=> true
       (fcall 'console.log [(fcall '== [1 2])]);=> false
       (fcall 'console.log [(fcall '== ["1" 1])]);=> true
       (fcall 'console.log [(fcall '== ["1" 2])]);=> false
       (fcall 'console.log [(fcall '== ["1" "1"])]);=> true
       (fcall 'console.log [(fcall '== ["1" "2"])]);=> false
       (fcall 'console.log [(fcall '== ["aaa" "aab"])])]);=> false

[]

https://github.com/ujihisa/jinaw/commit/8878e40f5a21f8a79067aa822d088db12cb87029

[] is a unary operator for objects. Note that "object" is a hash-map or an array in JavaScript terminology. I named it as aref borrowed from Ruby's parser which means array ref, since Clojure doesn't recognize '[] as Symbol but as vector. To distinguish it with user-defined something which name is aref, I named it as -aref.

(run '[(fcall 'console.log [(fcall '-aref [{"0" "a" "1" "b" "2" "c"} 0])])]);=> "a"
(run '[(fcall 'console.log [(fcall '-aref [{"0" "a" "1" "b" "2" "c"} "1"])])]);=> "b"
(run '[(fcall 'console.log [(fcall '-aref [{"0" "a" "1" "b" "2" "c"} 3])])]);=> "undefined"
(run '[(fcall 'console.log [(fcall '-aref [{"0" "a" "1" "b" "2" "c"} "4"])])]); => "undefined"

Day 3 -- JavaScript in a week

previous post <-> next post

I made many commits but most of them were improvements for internal structure. Actual new features are if and (strict) equal/notequal.

if

I implemented if as an expression like a ? b : c as below.

(defn evaluate [expr env]
  "assumption: env won't change"
  (if (list? expr)
    (let [[car & cdr] expr]
      (case car
        if (let [[cond- then- else-] cdr]
             (if (js-boolean (evaluate cond- env))
               (evaluate then- env)
               (evaluate else- env)))
        ...snip...

Too straightforward to explain. Since cond looked ambiguous to Clojure's one, so I added dash as suffix, and just for naming consistency, I added it to all the names..

equal/not equal

Strict equal (===)

Returns true if the operands are strictly equal (see above) with no type conversion.
https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Operators/Comparison_Operators

Luckily I could simply use Clojure's = function.

(defn evaluate [expr env]
  "assumption: env won't change"
  (if (list? expr)
    (let [[car & cdr] expr]
      (case car
        if (let [[cond- then- else-] cdr]
             (if (js-boolean (evaluate cond- env))
               (evaluate then- env)
               (evaluate else- env)))
        function (let [params (first cdr)
                       body (second cdr)]
                   {:type :function :params params :body body})
        fcall (let [func (evaluate (first cdr) env)
                    args (map #(evaluate % env) (second cdr))]
                (case func
                  console.log (println (js-string (first args)))
                  + (if (every? number? args)
                      (+ (first args) (second args))
                      (str (js-string (first args)) (js-string (second args))))
                  === (= (first args) (second args))
                  !== (not= (first args) (second args))
                  (if (= (:type func) :function)
                    (let [applied-params (into {} (map (fn [x y] [x y])
                                                       (:params func)
                                                       args))]
                      (run- (:body func) (merge env applied-params)))
                    (prn 'must-not-happen 'missing-function func))))
        quote (get env (first cdr) 'missing-local-var)
        expr))
    expr))

Now you have if and a predicate function, you can make a safe loop with recursive function calls.

var f = function(n) {
  (n === 10) ? console.log('end') : f(n + 1);
}
f();

It'll be represented as the below.

(run '[(var f (function [n]
                        [(fcall 'console.log ['n])
                         (if (fcall '=== ['n 10])
                           (fcall 'console.log ["end"])
                           (fcall 'f [(fcall '+ ['n 1])]))]))
       (fcall 'f [0])])

It outputs 0 to 10 and "end"

Refactoring to make it more declarative

You may have noticed that the evaluate function is already long and have guessed that it would get longer and longer as I add more builtin functions. First I made change to separate each built-in functions with updating a global variable *builtins*. That's still not well readable because of the boilerplate code. I made another change to provide defbuiltin macro. Now you can add a new builtin function with like the following code.

(defbuiltin + [x y]
  (if (and (number? x) (number? y))
    (+ x y)
    (str (js-string x) (js-string y))))

It looks very like Clojure's defn.

Day 2 -- JavaScript in a week

previous post <-> next post

summary:

• type conversions
  • JavaScript's Boolean(), Number() and String()
  • console.log and + now implicitly convert its arguemnts into String
• function literal without closure
  • (function(x) { console.log(x); })(2) works

Type conversions: Boolean(), Number() and String()

https://github.com/ujihisa/jinaw/commit/f28e7f55559f4919d6718539d413f0e65bd4a9e0

(defn js-boolean
  "https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Boolean"
  [value]
  (not (get #{0 'null false 'NaN 'undefined} value false)))

(defn js-number
  "https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Number"
  [value]
  (condp instance? value
    String (if (empty? value)
             0
             (let [x (read-string value)]
               (if (number? x) x 'NaN)))
    Long value
    'NaN))

(defn js-string
  "https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/String"
  [value]
  (.toString value))

Looks fairly straightforward.

Type conversions in + operator

It works both for numbers and strings.

• • for numbers https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Operators/Arithmetic_Operators
• • for strings https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Operators/String_Operators

The rule which to choose is really simple. If either one of the operands is not a number, it chooses the string's one and converts both operands to strings.

> 1 + 2
3
> '1' + 2
"12"
> 1 + '2'
"12"
> '1' + '2'
"12"
> [1] + [2]
"12"
> 1 + [2]
"12"

so

(defn evaluate [expr env]
  "assumption: env won't change"
  (if (list? expr)
    (let [[car & cdr] expr]
      (case car
        fcall (let [func (evaluate (first cdr) env)
                     args (map #(evaluate % env) (second cdr))]
                 (case func
                   console.log (println (js-string (first args)))
                   + (if (every? number? args)
                       (+ (first args) (second args))
                       (str (js-string (first args)) (js-string (second args))))
                   (prn 'must-not-happen 'missing-function func)))
        quote (get env (first cdr))
        expr))
    expr))

now the runtime outputs "1hello" by console.log(1 + 'hello').

function literal without closure

https://github.com/ujihisa/jinaw/commit/a50de0f344951e2e36a60131458d8533ea75241a

A function object which doesn't have lexical scope is represented simply as a tuple of parameter names and body (a sequence of statements.) Here just for readability in the future I'll use a hash-map which has :type, :params, and :body for function objects.

(defn evaluate [expr env]
  "assumption: env won't change"
  (if (list? expr)
    (let [[car & cdr] expr]
      (case car
        function (let [params (first cdr)
                       body (second cdr)]
                   {:type :function :params params :body body})
        fcall (let [func (evaluate (first cdr) env)
                    args (map #(evaluate % env) (second cdr))]
                (case func
                  console.log (println (js-string (first args)))
                  + (if (every? number? args)
                      (+ (first args) (second args))
                  (if (= (:type func) :function)
                    (let [applied-params (into {} (map (fn [x y] [x y])
                                                       (:params func)
                                                       args))]
                      (run- (:body func) (merge env applied-params)))
                    (prn 'must-not-happen 'missing-function func))))
        quote (get env (first cdr) 'missing-local-var)
  ...snip...

It doesn't support return yet.

Day 1 -- JavaScript in a week

https://github.com/ujihisa/jinaw

I'll make an implementation of a subset of programming language JavaScript within a week.

next post

Defining a subset of JavaScript

The implementation should execute the following JavaScript code.

var acc = 'dummy';
var f = function() {
  var acc = [];
  return function(x) {
    return x ? acc.push(x)&&f(x - 1) : acc;
  };
  console.log("this won't show up!");
}();

String.prototype.ujihisa = function() {
  var x = 10;
  return this + f(x);
}

console.log("hello".ujihisa());
console.log(acc == 'dummy');
console.log({'a': 2}.a == 2);

output:

hello10,9,8,7,6,5,4,3,2,1
true
true

That sample JS code covers the following important aspects.

• statements and expressions
• literals (String, Number, Function, Array and Object)
• function call, method call, operators, and index/key access of Object
• implicit convertion (String + Number)
• lexical scope (see acc var)
• method addition by prototype
• return exits from the current function

The implementation consists of the following 2 parts.

• parser (JS code to internal representation in S-expression)
• runtime

I'll work on runtime first in Clojure, then work on parser in Haskell with parsec.

parsing

I don't implement the parser for now but I simply parse the sample code by hand. the first 2 statements will be like the below.

before:

var acc = 'dummy';
var f = function() {
    var acc = [];
    return function(x) {
        return x ? acc.push(x)&&f(x - 1) : acc;
    };
}();

after:

'[(var 'acc "dummy")
  (var 'f
       (call
         (function []
                   [[(var 'acc (array))
                     (return
                       (function ['x]
                                 [[(return (if 'x
                                             (and (mcall 'push 'acc ['x])
                                                  (call 'f [(minus 'x 1)]))
                                             'acc))]]))]])
         []))]

Day 1 progress

https://github.com/ujihisa/jinaw/commit/6902cd4e9382e2da58fb9d43f8069256e8fe1ded

• just finished implementing var and console.log

  (run '[(var x "hello")
         (fcall 'console.log ['x])])

• currently console.log is just a single name of built-in function

https://github.com/ujihisa/jinaw/commit/30ad8c898a1c806735eaa990656258537b65a34c

• changed the structure a little bit.. to separate run to handle statements and evaluate to handle an expression

• now it supports nested function calls

  (run '[(var x 1)
         (fcall 'console.log [(fcall '+ ['x 2])])])

I'll be in Japan and Taiwan for a while

• Taiwan: Oct 28
• Japan: Oct 28 to Nov 21
• Taiwan: Nov 21 to Nov 23

I have no particular plans in Taiwan yet besides having awesome 小籠包s there.

小籠包 from wikipedia

Whereas I have plans in Japan -- I'll be organizing 4 conferences/meetups there.

• ujihisa.vim#3: Vim conference
• JVM study meetup: about Scala and Clojure
• Vim study meetup
• LiveCoding#11

If you are interested in either some of the topics above or me, and have plan to visit Kanto or Kansai area, you should check it out and give a presentation there.

Mergesort in Haskell, Clojure and Scheme

In Haskell

Mergesort requires O(1) index access so I used Data.Vector instead of List.

import qualified Data.Vector as V

-- length (sort2 x y) == 2
-- sorted (sort2 x y) is true
sort2 :: Ord a => a -> a -> V.Vector a
sort2 x y = if x < y then V.fromList [x, y] else V.fromList [y, x]

-- contract: sorted xs && sorted ys
-- length (merge xs ys) == length xs + length ys
-- sorted (merge xs ys) is true
merge :: Ord a => V.Vector a -> V.Vector a -> V.Vector a
merge xs ys = case (xs V.!? 0, ys V.!? 0) of
  (Nothing, _) -> ys
  (_, Nothing) -> xs
  (Just x, Just y) -> if x < y
    then x `V.cons` merge (V.tail xs) ys
    else y `V.cons` merge xs (V.tail ys)

-- length (mergeSort xs) == length xs
-- sorted (mergeSort xs) is true
mergeSort' :: Ord a => V.Vector a -> V.Vector a
mergeSort' xs = case V.length xs of
  0 -> xs
  1 -> xs
  2 -> sort2 (V.head xs) (V.last xs)
  otherwise -> let (a, b) = split2 xs in
               merge (mergeSort' a) (mergeSort' b)

mergeSort :: Ord a => [a] -> [a]
mergeSort = V.toList . mergeSort' . V.fromList


-- contract: length xs > 2
-- (a, b) = split2 xs => length a + length b == length xs
split2 :: Ord a => V.Vector a -> (V.Vector a, V.Vector a)
split2 xs = (V.take (V.length xs `div` 2) xs, V.drop (V.length xs `div` 2) xs)

main = do
  print $ mergeSort [3, 1, 4, 1, 5, 9, 2]

In Clojure

(defn sort2 [x y]
  (if (< x y) [x y] [y x]))

(defn merge2 [xs ys]
  (cond
    (empty? xs) ys
    (empty? ys) xs
    :else
    (let [x (first xs) y (first ys)]
      (if (< x y)
        (cons x (merge2 (rest xs) ys))
        (cons y (merge2 (rest ys) xs))))))

(defn merge-sort [xs]
  (cond
    (> 2 (count xs)) xs
    (= 2 (count xs)) (apply sort2 xs)
    :else (let [[a b] (split-at (/ (count xs) 2) xs)]
            (merge2 (merge-sort a) (merge-sort b)))))

(prn (merge-sort [3 1 4 1 5 9 2]))

Scheme (Gauche)

With List (slow)

(use srfi-1)

(define (sort2 x y)
  (if (< x y) (list x y) (list y x)))

(define (nil? xs)
  (eq? xs '()))

(define (merge2 xs ys)
  (cond
    ((nil? xs) ys)
    ((nil? ys) xs)
    ((let ((x (car xs))
           (y (car ys)))
       (if (< x y)
         (cons x (merge2 (cdr xs) ys))
         (cons y (merge2 xs (cdr ys))))))))

(define (merge-sort xs)
  (cond
    ((> 2 (length xs)) xs)
    ((= 2 (length xs)) (apply sort2 xs))
    ((receive (a b) (split-at xs (/ (length xs) 2))
       (merge2 (merge-sort a) (merge-sort b))))))

(print (merge-sort '(3 1 4 1 5 9 2 6)))

With Vector (fast)

(use srfi-43)

(define (sort2 x y)
  (if (< x y) (vector x y) (vector y x)))

(define (merge2 xs ys)
  (cond
    ((vector-empty? xs) ys)
    ((vector-empty? ys) xs)
    ((let ((x (~ xs 0))
           (y (~ ys 0)))
       (if (< x y)
         (vector-append (vector x) (merge2 (vector-copy xs 1 -1) ys))
         (vector-append (vector y) (merge2 xs (vector-copy ys 1 -1))))))))

(define (merge-sort xs)
  (cond
    ((> 2 (vector-length xs)) xs)
    ((= 2 (vector-length xs)) (sort2 (~ xs 0) (~ xs 1)))
    ((let ((a (vector-copy xs 0 (div (vector-length xs) 2)))
           (b (vector-copy xs (div (vector-length xs) 2) -1)))
       (merge2 (merge-sort a) (merge-sort b))))))

(print (merge-sort #(3 1 4 1 5 9 2 6)))

Quicksort in Lua

function rest(xs)
  local ys = {}
  for i = 2, #xs do
    table.insert(ys, xs[i])
  end
  return ys
end

function concat(xs, ys)
  local zs = {}
  for _, v in ipairs(xs) do
    table.insert(zs, v)
  end
  for _, v in ipairs(ys) do
    table.insert(zs, v)
  end
  return zs
end

function qsort(xs)
  if (#xs < 2) then
    return xs
  end
  local p, xs = xs[1], rest(xs)
  local lesser, greater = {}, {}
  for _, x in ipairs(xs) do
    if x < p then
      table.insert(lesser, x)
    else
      table.insert(greater, x)
    end
  end
  return concat(qsort(lesser), concat({p}, qsort(greater)))
end

xs = {3, 1, 4, 1, 5, 9}
for _, x in ipairs(qsort(xs)) do
  io.write(x .. ' ')
end
print()
-- to check if the original xs isn't destroyed
for _, x in ipairs(xs) do
  io.write(x .. ' ')
end

This works, but the code looks more complicated than it should be.

I rewrote it with using Underscore.lua and it made the code much easier to read.

_ = require 'underscore'

function concat(xs, ys)
  return _(ys):reduce(xs, function(m, x)
    return _(m):push(x)
  end)
end

function qsort(xs)
  if (#xs < 2) then
    return xs
  end
  local p, xs = xs[1], _(xs):rest()
  return concat(
    _(qsort(_(xs):select(function(x) return x < p end))):push(p),
    qsort(_(xs):select(function(x) return x >= p end)))
end

xs = {3, 1, 4, 1, 5, 9}
_(qsort(xs)):each(function(x)
  io.write(x .. ' ')
end)
print()
_(xs):each(function(x)
  io.write(x .. ' ')
end)