Hi. This is stereobooster's personal blog

I’m a software developer interested in UX, a11y, type systems, performance.

Github · Twitter

Notes on parsing theory, part 1

When I tried to read papers on parsing algorithms I found a lot of terminologies (sometimes used inconsistently), a lot of abbreviations, and contradictory claims. I decided to make some notes - write down definitions and abbreviations to understand papers.

An overview of parsing algorithms

Parser users tend to separate themselves into bottom-up and top-down tribes. Top-down users value the readability of recursive descent (RD) implementations of LL parsing along with the ease of semantic action incorporation. Bottom-up users value the extended parsing power of LR parsers, in particular the admissibility of left recursive grammars, although LR parsers cannot cope with hidden left recursion and even LR(0) parse tables can be exponential in the size of the grammar, while an LL parser is linear in the size of the grammar.

On Lisp Syntax

Why Lisp? Lisp is a micro language - it is trivial to implement basic Lisp interpreter. Lisp is a source of many discoveries in computer science, for example, garbage collection, tail call optimization, macros, etc. Lisp is used for teaching - SICP, MIT 6.001, How to design programs. Lisp is used for production - Clojure, Clasp. Lisp is used for research - Scheme, Racket. It is a majestic language, except for the syntax.

Awesome VS Code dev containers

Let’s imagine you want to play with a new language or technology. To do this you need: Some tutorial or exercise or katas/koans Development environment… and it is not that simple Side note: possible candidates for exercise are: MAL, todomvc, hnpwa, realworld. Development environment When I want to play - I want to jump directly to coding. I don’t want to figure out what is the state of the art for tooling.

My experience of writing Lisp in Pony

This is the second part of my reflection on implementing Lisp in Pony (following Make-A-Lisp tutorial). I don’t have previous experience in Pony. This is an impression of the newcomer. Also keep in mind, that Pony is still being actively developed. They have ambitious ideas, but they are not quite there yet. What I like I like that Pony doesn’t afraid to break some programming language “traditions”, which leads to cleaner language.

Make a Lisp - review

Writing a Lisp is a good learning exercise for a programmer. It will provide you with a deeper understanding of basic concepts: what is lambda, what is closure, what is binding etc. Is it relevant to modern programming (LISP was invented in 1958)? Well yes. First of all, because modern Lisps are quite different from the original version (it got the main revamp in 1975 when Scheme was created). Second, a lot of modern languages borrow basic concepts from Lisp, for example, JavaScript uses some concepts from Scheme: lexical scope, call-by-reference, anonymous functions (sometimes called Lambdas), closures, etc.

Call-by-name, by-reference, by-sharing

Value vs reference There are a lot of parameter-passing strategies. Let’s start from two: call-by-value, the argument for a function parameter is a copy of the value of the argument call-by-reference, the function is given the address of the argument For example, C uses call-by-value strategy for all arguments except pointers, for which it uses call-by-reference Variable assignment Described strategies are always mentioned in the context of the variable binding for function calls, but they apply to all variable bindings e.

Referential vs structural comparison

Comparison of values is one of the basic operations in programming. 1a === b; It is easy to compare atomic types, like a number, boolean, strings, symbols (or atoms) - we need to compare their values. It is a bit harder to compare collections, like lists, arrays (vectors, tuples), hash maps (dictionaries). There are two approaches: referential and structural. The referential comparison would compare only references (if this the same instance of the object), so two similar data structures would not be equal

Cargo cult programming

Cargo cult software engineering is a term coined by Steve McConnell. McConnell describes software development organizations that attempt to emulate more successful development houses, either by slavishly following a software development process without understanding the reasoning behind it… – Wikipedia It is called “cargo cult” because Feynman used this term to describe pseudoscience In the South Seas there is a Cargo Cult of people. During the war they saw airplanes land with lots of good materials, and they want the same thing to happen now.

Except where otherwise noted, content on this site is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 4.0