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 Campuswire.

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 you understand how the Lisp matcher works -- how special cases are handled in small simple subfunctions, how binding lists are updated non-destructively, why success is a list of binding list not just one binding list, how multiple binding lists can arise and need to be supported.

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 .

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.

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

[{ "?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"].

As in the Lisp matcher, keep an array of binding lists while matching:

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

JS #4: Match Regular Expressions

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

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 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" }]

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.

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

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

Test sets: Match and, Match or, Match not, Match some

Implement logical pattern combination, analogous to the ?AND, ?OR, and ?NOT forms in the Lisp matcher. All of these forms take one or more subpatterns as arguments. The subpatterns can be constants, variables or more complex nested patterns.

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.