Modern JavaScript for AI

JavaScript from its beginning was a language that had first-class functions, just like lambda closures in Scheme and Lisp. But only relatively recently has the functional style of programming come to dominate JavaScript coding.

If your JavaScript looks like C code, these exercises will be quite eye-opening. Some references on modern JavaScript:

Using JavaScript Exercise Tester

To do the JavaScript exercises, download the CS325 JavaScript Exercise Tester code repository first. The best way to do this is with git clone, because then you can get updates with git pull.

To run the tests for an exercise set, start a local web server, as described in the tester README. The specifications for each exercise, including test cases, are given on the JS Tester web page that is displayed.

JavaScript Style

There are two popular style guides for JavaScript: Google and Airbnb. Use the one from Airbnb. It is pickier and more opinionated, but appears to be more popular.

Writing Clean JavaScript — ES6 Edition has many good tips, although some are worth discussing in class or on Piazza.

In this class, do not use the self-proclaimed misleadingly-named JavaScript Standard Style. For reasons why, see this discussion.

JS #1: Basic Exercises

Test sets: Do the tests labeled Conditionals, Loops, and Mapping in the tester.

Part of the sequence bundle

In the Code Critic, the Conditionals and Loops are one submission, and Mapping is a separate submission. Incorporate the inital feedback you get on Conditionals and Loops before submitting your Mapping solutions.

JS #2: Core JSON Matcher

Do not do these exercises until we have discussed in class how the Lisp matcher works, how binding lists are structured and updated non-destructively, why success is a list of binding list not just one binding list, how multiple binding lists can arise, and how pattern extensions can be added to the matcher without changing matcher source code.

Test sets: Your code needs to pass the tests labeled Match Primitives, Match Arrays, Match Objects, and Match Variables in the tester.

Match bundle

Define a general recursive matcher for JavaScript objects, analogous to the Lisp pattern matcher .

Defining JSON matching

Matching for JavaScript data is defined as follows:

A variable is a string beginning with a question mark, such as "?x" or "?movie".

"Equal value" in programming is a complicated concept. Is 1 equal to 1.0? Is the array [1, 2] equal to another array with the same elements in the same order? Is the object {a: 1, b: 2} equal to {b: 2, a: 1}? For this matcher, the answers should be yes. This is the same as the lodash function isEqual() though you should not use that library.

Binding lists

To track variable bindings, keep a list of binding lists. Each binding list should be a JavaScript object with the variables as keys. For example, 

[{ "?x": 1, "?y": ["a", "b"] }]

is a list of one binding list where the variable "?x" bound to 1 and the variable "?y" bound to the array ["a", "b"].

This means that

Note: in Lisp, mapcan is very useful for managing the list of binding lists. In JavaScript, the direct analogue is the array method flatMap().

Supporting extensibility

Almost every application of pattern-directed inference needs domain-specific pattern matching forms. For example, a system dealing with geographic data may need patterns to match locations that are "near" some location.

An extensible pattern matcher lets users add new pattern forms to a pattern matcher without editing the source of the pattern matcher. To implement this, you need some way to associate matching functions to pattern symbols, and define the matcher to call those functions when it sees those symbols.

To do this, include the following in your code for the core JSON matcher: 

const matchers =  new Object();

export const addMatchers = (newMatchers) => {
  Object.assign(matchers, newMatchers);
};

const getMatcher = (pat, matchers) => {
  const key = Object.keys(matchers).find(key => pat.hasOwnProperty(key));
  return key ? matchers[key] : undefined
};

This defines a variable to hold an object whose keys will be pattern symbols and whose values will be matching functions. It defines getMatcher() to return the function for a key, if any, or undefined. Note that addMatchers() is exported.

Then, modify your match() function to call the function that getMatcher() returns, if there is one, passing it the pattern, the item being matched, and the binding lists. It's up to you to determine the appropriate place to call this code.

This code is not used for this exercise, but must be in place for subsequent matcher exercises.

Exporting the matcher

Put your core matcher in the file match-core.js. Then import and export your definition of match() in solutions.js like this: 

import { match } from './match-core.js';
export { match };

Do not submit code for the other JSON matcher exercises until your core matcher code has been approved as done.

JS #4: Match Regular Expressions

Test set: Pass the tests labeled Match Regular Expressions in the tester.

The goal of this exercise is to make it possible to integrate regular expressions as first-class citizens into the the structured patterns. A simple example would be a pattern that matches a last, first name string like "Smith, John" and binds the variables ?last and ?first appropriately.

Implement a matching subfunction for regular expressions so that matching 

{ regexp: "(.*), *(.*)", pats: ["?last", "?first"] }

against the string "Smith, John" returns: 

[{ "?last": "Smith", "?first": "John" }]

This exercise requires a basic understanding of regular expressions in JavaScript. In particular, you need to know what "capture groups" are, and how to get them in JavaScript when matching a regular expression to a string.

The normal rules for pattern match failure and adding to bindings lists apply. For example, if ?last is already bound to "Jones", the above match should fail.

Defining a pattern extension

The regular expression matcher should be defined as a pattern extension. Create a new file, matchers.js. At the top, put 

import { match } from './match-core.js';

match() is imported because many pattern extensions call match() recursively. No other function from the core matcher should be imported.

Define a function that takes a pattern like { regexp: "(.*), *(.*)", pats: ["?last", "?first"] }, some item to match against, and a list of binding lists. The function should return the updated bindings lists, or [] if the match fails.

Export the function you defined using the pattern key as the name. For example, if you called the function matchRegExp(), you'd write 

export {
  matchRegExp as regexp,
 };

Then add the lines in italics to solutions.js to import the extension: 

import { match, addMatchers } from './match-core.js';
import * as matchers from './matchers.js';
addMatchers(matchers);
export { match };

import * as matchers creates a JavaScript moduie that be accessed through a module namespace object. Calling addMatchers() adds the key-value pairs in the module to tne internal matchers object. Note that only match() is exported.

JS #5: Match AND, OR, NOT, SOME patterns

Test set: Pass the tests labeled Match And, Match Or, Match Not, and Match Some in the tester.

Implement pattern extensions to support logical pattern combination, like ?AND, ?OR, and ?NOT in the Lisp matcher. All of these pattern forms are JavaScript objects. All of these should be defined as extensions, just like the regular expresssion matcher. They should not be defined in the core matcher file nor have access to any matcher function other than match(). It's simplest to define them in the same file as the regular expression matcher.

AND and OR take a list of zero or more subpatterns: 

{ and: [pat1, pat2, ...] }
{ or: [pat1, pat2, ...] }

An AND pattern matches an input if every subpattern matches that input. If a variable appears in more than one subpattern, it must match an equal value in each case.

For example

match({ and: ["?x", "?y"] }, "a", [{}])

would return 

[{ "?x": "a", "?y": "a" }]

because the empty binding list can be extended with both bindings. But

match({and: [["?x", "?y"], ["?y", "?x"]]}, [1, 2])

would return: 

[]

because you can't bind ?x and ?y to both 1 and 2.

An OR pattern matches an input for every subpattern matches that input. Each match independently adds bindings to the current binding lists, if possible.

For example

match({ or: ["?x", "?y"] }, "a", [{}])

would return a list of two binding lists: 

[{ "?x": "a" }, { "?y": "a" }]

because the empty binding list can be extended with either binding. And 

or({and: [["?x", "?y"], ["?y", "?x"]]}, [1, 2])

returns two bindings lists, 

[{"?x": 1, "?y": 2}, {"?y": 1, "?x": 2}]	[{"?x": 1, "?y": 2}, {"?y": 1, "?x": 2}]

But

match({ or: ["?x", "?y"] }, "a", [{ "?x": "b" }])

would return just one binding list: 

[{ "?x": "b", "?y": "a" }]

because ?x can't be bound to a in the given binding lists.

A NOT pattern takes one subpattern and matches an input if the subpattern does not match. No new bindings are created, but some binding lists may be eliminated. For example

match({ not: "?x" }, "a", [{ "?x": "a"}, {"?x": "b" }])

would return 

[{ "?x": "b" }]

because that is the only binding that makes ?x not match a.

A SOME pattern takes one subpattern and matches it to an input array, returning the binding lists for every element that matches the subpattern.

For example

match({ some: "?x" }, ["a", "b", "c"])

would return 

[ { "?x": "a" }, { "?x": "b" }, { "?x": "c" } ]

Note: The above examples use subpatterns that are just variables to keep things simple. But your code should allow subpatterns to be anything.

Exporting the extensions

Put your code in the file matchers.js where you put the regular expression code. Export them under the names needed for the patterns, e.g., 

export { 
  matchRegExp as regexp,
  matchAnd as and,
  ...
}

Then the new extensions will be exported and available for the tester with no change to solutions.js needed.