Divyansh Prakash divs1210

Writing a Stackless Evaluator

Divyansh Prakash, September 2023

Preface

NOTE: Please read the previous post to understand the context of this post.

Cut me some stack

(a deep dive into trampolines)

Divyansh Prakash, September 2023

Preface

# copy libraries' configs
clj-kondo --lint "$(lein classpath)" --dependencies --parallel --copy-configs

;; export current ns types
;; (require '[malli.clj-kondo :as mc])
;; (-> (mc/collect *ns*) (mc/linter-config))
((requiring-resolve 'malli.clj-kondo/emit!))

Mylang

Features

Functional

like Clojure / Elixir
not fanatic like Haskell

Algol-derived syntax

syntax like JS / Python / Ruby / Elixir

	(defmacro trampolined
	"Wraps recursive calls."
	[& body]
	`(fn [] ~@body))

	(defn trampolined-k-fn
	"Takes a k-fn and returns a stackless fn.
	k-fn should be a CPS function with k as the first arg.
	In k-fn, all recursive calls should be wrapped using `trampolined`."
	[k-fn]

	(defn eager-cat
	"Eager concat.
	Doesn't blow up the stack.
	Returns a vector."
	([]
	[])
	([xs]
	(vec xs))
	([xs ys]
	(into (vec xs) ys))

	(defn BFS [tree]
	(loop [roots [tree]
	ret []]
	(if (empty? roots)
	ret
	(let [children (->> roots
	(mapcat :children)
	(remove nil?))
	this-level (map :val roots)]
	(recur children

	(defrecord Retry [bindings])

	(defmacro with-retry
	"It's really inconvenient not being able to recur from within (catch)
	expressions. This macro wraps its body in a (loop [bindings] (try ...)).
	Provides a (retry & new bindings) form which is usable within (catch) blocks:
	when this form is returned by the body, the body will be retried with the new
	bindings."
	[initial-bindings & body]
	(assert (vector? initial-bindings))

	javascript:(function(){
	function parseDollarVal(_txt) {
	let txt = _txt.split("$")[1] \|\| "0";

	let lastChar = txt[txt.length-1];
	let multiplier =
	lastChar == 'M' ? 1000000
	: lastChar == 'K' ? 1000
	: 1;

	<!DOCTYPE html>
	<html>
	<head>
	<meta charset="UTF-8">
	</head>

	<body>
	<div>
	<center>
	<h3>Lisp.js</h3>